Implementing CRC32 in TypeScript

Ensuring Data Integrity Verification with CRC32 Algorithm

Data integrity is crucial in various applications, including file transfers, network protocols, and storage systems. To ensure that data remains intact during transmission or storage, checksum algorithms such as CRC32 (Cyclic Redundancy Check 32 bits) are commonly used. In this article, we will explore the implementation of CRC32 in TypeScript/JavaScript, a popular language for web development.

Unlike other programming languages like Java, PHP or Python, JavaScript does not have native support for CRC32. However, in this article we will implement CRC32 compatible with mentioned languages (similar to what is used in zip archives).

Understanding CRC

CRC32 generates a 32-bit checksum value. This value can be used to detect errors during transmission or storage. Therefore one of the main requirements (among others like simplicity and speed) to the CRC is error detection capability. This means probability of collisions should be low.

CRC is based on the division process. The division is performed using the binary exclusive OR (XOR) operation. After processing all the bits of the message, the final remainder obtained from the division represents the checksum.

During CRC calculation bitwise left shift << and bitwise right shift >> can be used. We will implement right shift unsigned (CRC32 unsigned) version which is sometimes referenced as “reversed”.

CRC 3-bits Checksum Pseudo Algorithm

To better understand how it works, let’s start with a simple CRC 3-bits pseudo algorithm implementation which will generate 3-bits checksum.

const divisor = 0b111;
let crc = 0b000;

for (const byte of bytes) {
  let reminder = byte;
  for (let i = 0; i < 8; i++) {
    if (reminder & 1) {
      reminder = (reminder >>> 1) ^ divisor;
    } else {
      reminder = reminder >>> 1;
    }
  }

  // final division
  crc = crc ^ reminder;
}

We need to notice is that:

• Input is processing as a sequence of bits which are grouped into bytes.
• There is an initial state, set to 0b000.
• 3-bit reminder is calculated for every bit in a byte based on least significant bit (LSB) value. In case bit is not set division is not performed.
• There is a 3-bits divisor which is used in XOR operation to calculate reminder.
• 3-bit checksum is calculated for every incoming byte using XOR operation with 3-bit reminder.
• Divisor bit length impacts CRC bit length. For example, reducing divisor to 0b11 (2 bits) will increase number of collisions and significantly reduce the algorithm efficiency (see Output 2).

Let’s check the results:

console.log('1234567890', crc3('1234567890'));
console.log('123456789', crc3('123456789'));
console.log('12345678', crc3('12345678'));
console.log('hello', crc3('hello'));
console.log('hello crc3', crc3('hello crc3'));
console.log('some other text', crc3('some other text'));

Output 1:

{ '1234567890': '1' }
{ '123456789': '2' }
{ '12345678': '7' }
{ hello: '4' }
{ 'hello crc3': '3' }
{ 'some other text': '4' }
{ 'empty string': '0' }

Here we can see that resulting checksum is within decimal range 0–7 which reflects 3 bits value. Since there are only 8 possible checksums, we can see a probability of collisions is high. For example, calculated value for “hello” and “some other text” is the same.

It’s important to use a divisor of the same bits length as maximum possible checksum bits length (in this example it’s 3 bits). See how using divisor less than 3 bits, for example 2 bits, will impact the resulting code.

Output 2. Using divisor 0b11 leads to more collisions.

{ '1234567890': '2' }
{ '123456789': '0' }
{ '12345678': '2' }
{ hello: '0' }
{ 'hello crc3': '1' }
{ 'some other text': '2' }
{ 'empty string': '0' }

CRC32

One of the main differences between pseudo CRC3 that we have as example above and real CRC32 is using a polynomial as a divisor. The CRC32 algorithm uses a predefined polynomial, which can be written as a binary number of a specific length.

Here is a list of primitive irreducible polynomials for generating elements of a binary extension field GF(2m) from a base finite field. The list contains polynomials of 32 [Ref. 1].

x^32 + x^22 + x^2 + x^1 + 1
x^32 + x^22 + x^21 + x^20 + x^18 + x^17 + x^15 + x^13 + x^12 + x^10 + x^8 + x^6 + x^4 + x^1 + 1
x^32 + x^23 + x^17 + x^16 + x^14 + x^10 + x^8 + x^7 + x^6 + x^5 + x^3 + 1
x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1
x^32 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 + x^17 + x^13 + x^11 + x^10+x^9+x^8+x^7+x^2+x^1 + 1
x^32 + x^28 + x^19 + x^18 + x^16 + x^14 + x^11 + x^10 + x^9 + x^6 + x^5 + x^1 + 1

Most popular polynomial is 0x04C11DB7 and it’s reversed version (taken backwards) 0xEDB88320 [Ref. 2].

x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1
which is 00000100110000010001110110110111 or 0x04C11DB7
reversing the bits we will have 11101101101110001000001100100000 or 0xEDB88320

We will use 0xEDB88320 in our CRC32 implementation.

Implementation Unsigned CRC32 in TypeScript

Here is a dirty version of working CRC32 in TS.

const toUnsignedInt32 = (n: number): number => {
  if (n >= 0) {
    return n;
  }
  return 0xFFFFFFFF - (n * -1) + 1;
}
export const crc32UnsignedFull = (input: string): number => {
  const encoder = new TextEncoder();
  const bytes = encoder.encode(input);
  const divisor = 0xEDB88320;
  let crc = 0xFFFFFFFF;
  for (const byte of bytes) {
    crc = (crc ^ byte);
    for (let i = 0; i < 8; i++) {
      if (crc & 1) {
        crc = (crc >>> 1) ^ divisor;
      } else {
        crc = crc >>> 1;
      }
    }
  }
  return toUnsignedInt32(crc ^ 0xFFFFFFFF);
};

Output 3. Let’s calculate a checksum for “hello crc32”.

console.log(crc32UnsignedFull('hello crc32')); // 2560021400

It’s “dirty” because it’s not optimised. But calculations are correct. Here we need to notice:

• Initial state is set to 0xFFFFFFFF.
• Before returning, resulting checksum XOR operation with 0xFFFFFFFF is applied.
• Result is converted to unsigned integer.

Optimisation

In a for loop we calculate result for every byte. Each incoming byte may have 256 states and therefore we could build a lookup table with 256 pre-calculated results.

const buildCRC32LookupTable = (polynomial: number): number[] => {
  const table: number[] = [];
  for (let n = 0; n < 256; n++) {
    let reminder = n;
    for (let i = 0; i < 8; i++) {
      if (reminder & 1) {
        reminder = (reminder >>> 1) ^ polynomial;
      } else {
        reminder = reminder >>> 1;
      }
    }
    table.push(toUnsignedInt32(reminder));
  }
  return table;
}

Output 4. Lookup table

console.log(JSON.stringify(buildCRC32LookupTable(0xEDB88320)));
// [0, 1996959894, 3993919788, 2567524794, 124634137, 1886057615, 3915621685, 2657392035, 249268274, 2044508324, 3772115230, 2547177864, 162941995, 2125561021, 3887607047, 2428444049, 498536548, 1789927666, 4089016648, 2227061214, 450548861, 1843258603, 4107580753, 2211677639, 325883990, 1684777152, 4251122042, 2321926636, 335633487, 1661365465, 4195302755, 2366115317, 997073096, 1281953886, 3579855332, 2724688242, 1006888145, 1258607687, 3524101629, 2768942443, 901097722, 1119000684, 3686517206, 2898065728, 853044451, 1172266101, 3705015759, 2882616665, 651767980, 1373503546, 3369554304, 3218104598, 565507253, 1454621731, 3485111705, 3099436303, 671266974, 1594198024, 3322730930, 2970347812, 795835527, 1483230225, 3244367275, 3060149565, 1994146192, 31158534, 2563907772, 4023717930, 1907459465, 112637215, 2680153253, 3904427059, 2013776290, 251722036, 2517215374, 3775830040, 2137656763, 141376813, 2439277719, 3865271297, 1802195444, 476864866, 2238001368, 4066508878, 1812370925, 453092731, 2181625025, 4111451223, 1706088902, 314042704, 2344532202, 4240017532, 1658658271, 366619977, 2362670323, 4224994405, 1303535960, 984961486, 2747007092, 3569037538, 1256170817, 1037604311, 2765210733, 3554079995, 1131014506, 879679996, 2909243462, 3663771856, 1141124467, 855842277, 2852801631, 3708648649, 1342533948, 654459306, 3188396048, 3373015174, 1466479909, 544179635, 3110523913, 3462522015, 1591671054, 702138776, 2966460450, 3352799412, 1504918807, 783551873, 3082640443, 3233442989, 3988292384, 2596254646, 62317068, 1957810842, 3939845945, 2647816111, 81470997, 1943803523, 3814918930, 2489596804, 225274430, 2053790376, 3826175755, 2466906013, 167816743, 2097651377, 4027552580, 2265490386, 503444072, 1762050814, 4150417245, 2154129355, 426522225, 1852507879, 4275313526, 2312317920, 282753626, 1742555852, 4189708143, 2394877945, 397917763, 1622183637, 3604390888, 2714866558, 953729732, 1340076626, 3518719985, 2797360999, 1068828381, 1219638859, 3624741850, 2936675148, 906185462, 1090812512, 3747672003, 2825379669, 829329135, 1181335161, 3412177804, 3160834842, 628085408, 1382605366, 3423369109, 3138078467, 570562233, 1426400815, 3317316542, 2998733608, 733239954, 1555261956, 3268935591, 3050360625, 752459403, 1541320221, 2607071920, 3965973030, 1969922972, 40735498, 2617837225, 3943577151, 1913087877, 83908371, 2512341634, 3803740692, 2075208622, 213261112, 2463272603, 3855990285, 2094854071, 198958881, 2262029012, 4057260610, 1759359992, 534414190, 2176718541, 4139329115, 1873836001, 414664567, 2282248934, 4279200368, 1711684554, 285281116, 2405801727, 4167216745, 1634467795, 376229701, 2685067896, 3608007406, 1308918612, 956543938, 2808555105, 3495958263, 1231636301, 1047427035, 2932959818, 3654703836, 1088359270, 936918000, 2847714899, 3736837829, 1202900863, 817233897, 3183342108, 3401237130, 1404277552, 615818150, 3134207493, 3453421203, 1423857449, 601450431, 3009837614, 3294710456, 1567103746, 711928724, 3020668471, 3272380065, 1510334235, 755167117]

Final version

Below is a final version of Unsigned CRC32 implemented in TypeScript. Unlike other popular JS/TS implementations, this version rely on using TextEncoder instead of a Buffer, and it is supported in all modern browsers without extra polyfill dependencies.

/**
 * Calculate CRC32 unsigned for 0x04C11DB7 polynomial.
 * Browser and NodeJS compatible version.
 */
export class CRC32 {
  /**
   * Lookup table calculated for 0xEDB88320 divisor
   */
  protected lookupTable = [0, 1996959894, 3993919788, 2567524794, 124634137, 1886057615, 3915621685, 2657392035, 249268274, 2044508324, 3772115230, 2547177864, 162941995, 2125561021, 3887607047, 2428444049, 498536548, 1789927666, 4089016648, 2227061214, 450548861, 1843258603, 4107580753, 2211677639, 325883990, 1684777152, 4251122042, 2321926636, 335633487, 1661365465, 4195302755, 2366115317, 997073096, 1281953886, 3579855332, 2724688242, 1006888145, 1258607687, 3524101629, 2768942443, 901097722, 1119000684, 3686517206, 2898065728, 853044451, 1172266101, 3705015759, 2882616665, 651767980, 1373503546, 3369554304, 3218104598, 565507253, 1454621731, 3485111705, 3099436303, 671266974, 1594198024, 3322730930, 2970347812, 795835527, 1483230225, 3244367275, 3060149565, 1994146192, 31158534, 2563907772, 4023717930, 1907459465, 112637215, 2680153253, 3904427059, 2013776290, 251722036, 2517215374, 3775830040, 2137656763, 141376813, 2439277719, 3865271297, 1802195444, 476864866, 2238001368, 4066508878, 1812370925, 453092731, 2181625025, 4111451223, 1706088902, 314042704, 2344532202, 4240017532, 1658658271, 366619977, 2362670323, 4224994405, 1303535960, 984961486, 2747007092, 3569037538, 1256170817, 1037604311, 2765210733, 3554079995, 1131014506, 879679996, 2909243462, 3663771856, 1141124467, 855842277, 2852801631, 3708648649, 1342533948, 654459306, 3188396048, 3373015174, 1466479909, 544179635, 3110523913, 3462522015, 1591671054, 702138776, 2966460450, 3352799412, 1504918807, 783551873, 3082640443, 3233442989, 3988292384, 2596254646, 62317068, 1957810842, 3939845945, 2647816111, 81470997, 1943803523, 3814918930, 2489596804, 225274430, 2053790376, 3826175755, 2466906013, 167816743, 2097651377, 4027552580, 2265490386, 503444072, 1762050814, 4150417245, 2154129355, 426522225, 1852507879, 4275313526, 2312317920, 282753626, 1742555852, 4189708143, 2394877945, 397917763, 1622183637, 3604390888, 2714866558, 953729732, 1340076626, 3518719985, 2797360999, 1068828381, 1219638859, 3624741850, 2936675148, 906185462, 1090812512, 3747672003, 2825379669, 829329135, 1181335161, 3412177804, 3160834842, 628085408, 1382605366, 3423369109, 3138078467, 570562233, 1426400815, 3317316542, 2998733608, 733239954, 1555261956, 3268935591, 3050360625, 752459403, 1541320221, 2607071920, 3965973030, 1969922972, 40735498, 2617837225, 3943577151, 1913087877, 83908371, 2512341634, 3803740692, 2075208622, 213261112, 2463272603, 3855990285, 2094854071, 198958881, 2262029012, 4057260610, 1759359992, 534414190, 2176718541, 4139329115, 1873836001, 414664567, 2282248934, 4279200368, 1711684554, 285281116, 2405801727, 4167216745, 1634467795, 376229701, 2685067896, 3608007406, 1308918612, 956543938, 2808555105, 3495958263, 1231636301, 1047427035, 2932959818, 3654703836, 1088359270, 936918000, 2847714899, 3736837829, 1202900863, 817233897, 3183342108, 3401237130, 1404277552, 615818150, 3134207493, 3453421203, 1423857449, 601450431, 3009837614, 3294710456, 1567103746, 711928724, 3020668471, 3272380065, 1510334235, 755167117];

  public calculate(input: string): number {
    const bytes = this.strToBytes(input);
    let crc = 0xFFFFFFFF;
    for (const byte of bytes) {
      const tableIndex = (crc ^ byte) & 0xFF;
      const tableVal = this.lookupTable?.[tableIndex];
      if (tableVal === undefined) throw new Error('tableIndex out of range 0-255');
      crc = (crc >>> 8) ^ tableVal;
    }

    return this.toUint32(crc ^ 0xFFFFFFFF);
  }

  protected strToBytes(input: string): Uint8Array {
    const encoder = new TextEncoder();
    return encoder.encode(input);
  }

  protected toUint32(num: number): number {
    if (num >= 0) {
      return num;
    }
    const a = new Uint32Array(1);
    a[0] = num;
    return a[0];
  }
}

Output 5.

const crc = new CRC32();
console.log(crc.calculate('hello crc32')); // 2560021400 (0x9896d398)

Questions

1. Polynomial bits representation has 33 bits, how we get 0x4c11db7 number?

Answer. Since in polynomial cx³² + cx²⁶ + cx²³ + cx²² + cx¹⁶ + cx¹² + cx¹¹ + cx¹⁰ + cx⁸ + cx⁷ + cx⁵ + cx⁴ + cx² + cx¹ + 1 we omit coefficients which equal to 0 and left only c = 1, it’s full representation is 100000100110000010001110110110111 (33 bits). But CRC32 calculates 32 bits integer, and 33 bits simply does not fit. Therefore we need to drop extra MSB bits. See the code below.

const a = new Int32Array(1);
a[0] = 0b100000100110000010001110110110111; // put 33 bits into 32 bit registry
a[0].toString(16); // 4c11db7
a[0].toString(2); // 100110000010001110110110111 - leading 1 dropped, other leading 0 not printed

2. Why do we need to use a reversed polynomial? Or how divider 0xEDB88320 was derived from 0x04C11DB7?

Answer. We reverse 0x04C11DB7 bits.

'00000100110000010001110110110111'.split('').reverse().join(''); // 11101101101110001000001100100000
(0b11101101101110001000001100100000).toString(16); // edb88320

Also 0xEDB88320 is utilising 32 bits comparing to 27 bits of 0x04C11DB7, which is essential for reversed CRC algorithm (remember results after using 2 bits 0b11 divisor in CRC3 “Output 2” above).

(0x04C11DB7).toString(2).length; // 27
(0xEDB88320).toString(2).length; // 32

Increasing the number of bits (degree of polynomial) makes calculation more complex and the resulting checksum more unique (improves error detection).

3. Is there any difference to get bytes sequence from TextEncoder instead of charCodeAt?

Answer. Yes. They can produce different results for multibyte characters. The charCodeAt() focuses on Unicode code points, while TextEncoder returns bytes array based on encoding. [See example in Ref. 4]

Compatibility

Let’s check if checksum calculated in a few other programming languages for the same input string will match to the results obtained in Output 5.

Java

import java.util.zip.CRC32;
import java.util.zip.Checksum;

public class CRC32Test {
  public static void main(String[] args) {
    String input = "hello crc32";
    byte[] bytes = input.getBytes();
    Checksum checksum = new CRC32(); // java.util.zip.CRC32
    checksum.update(bytes, 0, bytes.length);
    System.out.println(checksum.getValue());
  }
}

Result is 2560021400 (0x9896d398).

Python

import binascii
binascii.crc32(b'hello crc32')

Result is 2560021400 (0x9896d398).

import zlib
zlib.crc32(b'hello crc32')

Same result: 2560021400 (0x9896d398).

PHP

php -r 'echo crc32("hello crc32"), "\n";'

Prints 2560021400 (0x9896d398).

Conclusion

Implementing the CRC32 algorithm in TypeScript provides a powerful tool for data integrity verification. By understanding the fundamentals and performing the CRC32 calculation, developers can ensure the reliability and integrity of data in various applications.

References

1. Primitive Polynomial List https://www.partow.net/programming/polynomials/index.html#deg32
2. FreeBSD CRC32 https://web.mit.edu/freebsd/head/sys/libkern/crc32.c
3. PHP CRC32 https://github.com/php/php-src/blob/master/ext/standard/crc32.h
4. Conversion UTF-8 string to bytes in JavaScript https://gist.github.com/vbabak/c47a67ff5e89cab8954097eeb2a33fb8
5. Final version of the CRC32 class https://gist.github.com/vbabak/c4e817100228e46ccd621cc4caf0f87f