CRC32 Learning Example

gistfile1.txt

/**
 * Builds a lookup table (256 elements) for fast CRC-32 calculations.
 * 
 * The table is built using the standard polynomial 0xEDB88320 (also known as
 * the 'reverse' polynomial used in the CRC-32 algorithm). Each of the 256
 * possible byte values is processed to find the remainder when treated as
 * input to the polynomial division used in CRC-32.
 */
function buildLookupCRC32LookupTable(): Uint32Array {
  // Create a new 32-bit unsigned integer array of length 256.
  // Each entry will hold a precomputed CRC value for one possible byte.
  const table = new Uint32Array(256)

  // We iterate over all 256 possible byte values (0 to 255).
  for (let i = 0; i < 256; i++) {
    // Start with the byte value i, and store it in a working variable 'c'.
    // We'll run 'c' through a sequence of bit manipulations to compute
    // what the CRC remainder would be if we started from this byte.
    let c = i

    // Each byte gets processed bit by bit, for a total of 8 iterations.
    // On each iteration, we check the lowest-order bit:
    //   - If it's 1, we XOR with the polynomial (0xEDB88320) after right-shifting.
    //   - If it's 0, we just right-shift.
    // This effectively simulates one round of the polynomial's effect on the data.
    for (let k = 0; k < 8; k++) {
      // (c & 1) checks if the lowest bit is 1.
      // If it is, we XOR with 0xEDB88320 after shifting c to the right by 1 bit.
      // Otherwise, we just shift c to the right by 1 bit without the XOR.
      c = (c & 1)
        ? 0xEDB88320 ^ (c >>> 1)
        : (c >>> 1)
    }

    // After 8 iterations, 'c' is the CRC remainder for the initial byte 'i'.
    // Store this result in the lookup table for quick reference later.
    table[i] = c
  }

  // Return the fully built lookup table.
  return table
}

// Build the global lookup table once, so we can reuse it for any CRC computation.
const table = buildLookupCRC32LookupTable()

/**
 * Computes the CRC-32 of a given string.
 * 
 * @param input - The string to compute the CRC-32 for.
 * @returns     - The 32-bit unsigned CRC-32 value.
 */
export function CRC32(input: string): number {
  /**
   * Initialize the CRC with 0xFFFFFFFF (which is 0 ^ -1 in JavaScript).
   * 
   * - The "0 ^ -1" trick sets crc to ~0 (bitwise NOT of 0), which is 0xFFFFFFFF.
   * - In many CRC implementations, the starting CRC is 0xFFFFFFFF for a 'seed'.
   */
  let crc = 0 ^ -1

  // Process each character in the input string:
  //   1. Convert the character to its ASCII code using charCodeAt().
  //   2. XOR that value with the current CRC (low byte).
  //   3. Use that as an index into the table to get the precomputed partial CRC.
  //   4. XOR that with the shifted CRC (>>> 8).
  for (let i = 0; i < input.length; i++) {
    // Determine the index for the lookup table by combining the low byte of 'crc'
    // with the ASCII code of the current character, then mask to 0xFF
    // to ensure it's a valid table index (0-255).
    const index = (crc ^ input.charCodeAt(i)) & 0xff

    // Update the CRC by shifting out the processed byte (crc >>> 8)
    // and XOR-ing with the lookup table's precomputed value.
    crc = (crc >>> 8) ^ table[index]
  }

  /**
   * Finally, XOR the result with 0xFFFFFFFF (which is -1) to get the final CRC-32.
   * 
   * The ">>> 0" ensures the result is treated as an unsigned 32-bit value,
   * giving us the correct unsigned CRC-32 number in JavaScript.
   */
  return (crc ^ -1) >>> 0
}