Implementing CRC32 hashing in TypeScript

CRC32 (Cyclic Redundancy Check 32-bit) is a checksum algorithm used to check data integrity.

It is widely used to check whether data is corrupted during communications or file transfers.

Implementation policy

To speed up CRC32 calculations, we use a 256-entry lookup table.

Once the table is generated, subsequent calculations can be performed quickly.

Generate lookup table

First, create a function to generate a table for CRC32 calculation.

let crc32Table: number[] | undefined;

function getTable(): number[] {
  if (crc32Table !== undefined && crc32Table.length > 0) return crc32Table;

  crc32Table = [];
  for (let i = 0; i < 256; ++i) {
    let r = i;
    for (let j = 0; j < 8; ++j) {
      r = (r & 1) === 1 ? 0xedb88320 ^ (r >>> 1) : r >>> 1;
    }
    crc32Table[i] = r >>> 0;
  }
  return crc32Table;
}

Create a new table only if no table has been created yet.

Each entry represents the result of polynomial division on an 8-bit value.

Calculating the CRC32 hash

Calculates a CRC32 hash of the input data using a lookup table.

function crc32Hash(data: Uint8Array): number {
  const table = getTable();

  let crc = 0xffffffff;
  for (let o of data) {
    crc = (crc >>> 8) ^ table[(crc ^ o) & 0xff];
  }
  crc = crc ^ 0xffffffff;
  return crc >>> 0;
}

It takes input data in Uint8Array format and returns a CRC32 hash as a 32-bit unsigned integer.

Complete code

The complete implementation combining the above two functions is as follows.

let crc32Table: number[] | undefined;

function getTable(): number[] {
  if (crc32Table !== undefined && crc32Table.length > 0) return crc32Table;

  crc32Table = [];
  for (let i = 0; i < 256; ++i) {
    let r = i;
    for (let j = 0; j < 8; ++j) {
      r = (r & 1) === 1 ? 0xedb88320 ^ (r >>> 1) : r >>> 1;
    }
    crc32Table[i] = r >>> 0;
  }
  return crc32Table;
}

function crc32Hash(data: Uint8Array): number {
  const table = getTable();

  let crc = 0xffffffff;
  for (let o of data) {
    crc = (crc >>> 8) ^ table[(crc ^ o) & 0xff];
  }
  crc = crc ^ 0xffffffff;
  return crc >>> 0;
}

Usage example

An example of calculating a CRC32 hash of a string.

console.log(crc32Hash(new TextEncoder().encode("hello")));

Convert it to Uint8Array with TextEncoder and then pass it to the crc32Hash function.

summary

CRC32 is a simple but practical checksum algorithm.

You can use lookup tables to perform calculations quickly in TypeScript. It can be used in a variety of situations, such as checking file integrity and generating cache keys.