Show HN: Super Simple CRC32 Implementation

A normal table-based crc32. Since we don't see the generator, we cannot see the polynom. You usually put the generator in the code

I suggest you write a few test cases to verify that it works reliably. I have my doubts about that, given this code fragment:

    // stop hashing when there is nothing left to hash
    while (scanf("%d", &ch) != EOF) {
        // get the current byte
        ch = getchar();

If you don't want a hard coded table, you could always do this.

    unsigned kCastagnoli[256];

    void InitializeCrc32(unsigned table[256], unsigned polynomial) {
      unsigned d, i, r;
      for (d = 0; d < 256; ++d) {
        r = d;
        for (i = 0; i < 8; ++i)
          r = r >> 1 ^ (r & 1 ? polynomial : 0);
        table[d] = r;
      }
    }

    unsigned Castagnoli(unsigned h, unsigned long w, long n) {
      long i;
      static int once;
      if (!once) {
        InitializeCrc32(kCastagnoli, 0x82f63b78);
        once = 1;
      }
      for (i = 0; i < n; ++i) {
        h = h >> 8 ^ kCastagnoli[(h & 255) ^ (w & 255)];
        w >>= 8;
      }
      return h;
    }

That does the same thing as the crc32 instructions in x86.

FTR, an implementation in “low-level” JavaScript:

  /** Precomputed CRC-32 lookup table for half-bytes (aka “nibbles”).
   * Trade more compute time for less memory and less code to transmit.
   * @see https://create.stephan-brumme.com/crc32/#half-byte
   */
  const CRC32_NIBBLE_TABLE = new Uint32Array([
             0, 0x1DB71064, 0x3B6E20C8, 0x26D930AC, 0x76DC4190, 0x6B6B51F4, 0x4DB26158, 0x5005713C,
    0xEDB88320, 0xF00F9344, 0xD6D6A3E8, 0xCB61B38C, 0x9B64C2B0, 0x86D3D2D4, 0xA00AE278, 0xBDBDF21C
  ]);

  /** @return {number} CRC-32 (polynomial 0x04C11DB7) of the input data.
   * @param {!BufferSource} data  The input data.
   * @param {number=} previousValue  The previous CRC value, if resuming a computation.
   * @see https://en.wikipedia.org/wiki/Cyclic_redundancy_check
   */
  function crc32(data, previousValue = 0) {
    const bytes = ArrayBuffer.isView(data)
      ? new Uint8Array(data.buffer, data.byteOffset, data.byteLength)
      : new Uint8Array(data);
    let crc = ~previousValue;

    for (let i = 0; i < bytes.length; i++) {
      crc = (crc >>> 4) ^ CRC32_NIBBLE_TABLE[0x0f & (crc ^ bytes[i])];
      crc = (crc >>> 4) ^ CRC32_NIBBLE_TABLE[0x0f & (crc ^ (bytes[i] >> 4))];
    }
    return ~crc;
  }

From https://GitHub.com/PaulCapron/pwa2uwp/blob/master/src/zip.js

this simply matches the `crc_reflected()` in section 18 of "A Painless Guide to CRC Error Detection Algorithms" [1] with hardcoded init and final xor's to match one specific CRC-32 spec. nothing wrong with that, but it isn't original at all either.

i recommend the "painless guide" for anyone constructing CRC algorithms in software. it breaks down the entire algorithm, including various trade-offs and choices, as well as for different polynomials and other parameters.

then you also have the catalogs of parameters [2] and [3]

[1] https://www.zlib.net/crc_v3.txt [2] https://reveng.sourceforge.io/crc-catalogue/ [3] https://users.ece.cmu.edu/~koopman/crc/

OT: I copied the error detection code that AcuRite uses in their temperature sensors for use in my rain gauge. (I got the code by taking a look at the decoder for AcuRite temperature sensors that is included in rtl_433).

At the time I thought it was a CRC, but later I realized that it isn't. I've been trying to find out what the name is for that kind of code but have failed. I wonder if anyone here happens to know?

Here is the code:

  byte check_code(byte const message[], unsigned nbytes, byte gen, byte key)
  {
    byte sum = 0;
    for (unsigned k = 0; k < nbytes; ++k) {
        byte data = message[k];
        for (int i = 7; i >= 0; --i) {
            if ((data >> i) & 1)
                sum ^= key;

            if (key & 1)
                key = (key >> 1) ^ gen;
            else
                key = (key >> 1);
        }
    }
    return sum;
  }

I thought it was a CRC because I saw it shifting and saw it xoring when it shifted out a 1. That's quite reminiscent of the method of CRC computation that treats bit strings as representing polynomials in GF(2) and computes the CRC by doing polynomial division essentially the same way we would do it by hand.

But when computing a CRC that way what you xor the data with is a constant (the representation of the generator polynomial). In the algorithm above the constant is not xor'ed with the data. In fact nothing is xor'ed with the data.

The constant, named 'gen' which is another reason I thought at first it was a CRC, is actually the feedback polynomial for a Galois linear feedback shift register (LFSR), which is seeded with the 'key' parameter. That LFSR generates one byte for every bit of the message, and the bytes that are generated for the message bits that are set are xor'ed together, and it is the result of that that is the check code.

In higher level terms the general approach it is using can be described like this in a Pythonish pseudocode, assuming PRNG() is a psuedorandom byte generator, and seed_PRNG() is a function to seed that generator:

  def check_code(message, key):
    sum = 0
    seed_PRNG(key)
    foreach bit in message:
      next_random = PRNG()
      if bit == 1:
        sum ^= next_random
    return sum

Pick a Galois LSFR with feedback polynomial 'gen' as your PRNG and that matches the AcuRite code.

So there are many different flavors of crc32. Usually you can always change the initialization value. This algorithm is only one use case.

Check this table out https://www.crccalc.com/?crc=123456789&method=&datatype=0&ou...