Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Super Simple CRC32 Implementation

github.com

Post reply on HN
Print view View original

1–10 of 17 posts

Re: Show HN: Super Simple CRC32 Implementation

#2

Post by Someone »

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();

Re: Show HN: Super Simple CRC32 Implementation

#3

Post by dch82 »

Someone wrote: post #2

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();

How would you suggest I replace that? I am a C novice but I have heard of the buffer overflows caused by scanf.

Re: Show HN: Super Simple CRC32 Implementation

#4

Post by dch82 »

Someone wrote: post #2

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();

I replaced that code with

  // loop until an EOF is read
  while ((ch = getchar()), ch != EOF) {
Would this be better?

Re: Show HN: Super Simple CRC32 Implementation

#6

Post by ranger_danger »

Sianko wrote: post #5

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...

I would really appreciate someone documenting exactly which variant of CRC32 is being used here.

Re: Show HN: Super Simple CRC32 Implementation

#8

Post by self_awareness »

ranger_danger wrote: post #6
Sianko wrote: post #5

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...

I would really appreciate someone documenting exactly which variant of CRC32 is being used here.

CRC-32/ISO-HDLC

https://www.crccalc.com/?crc=123456789&method=CRC-32%2FISO-H...

Re: Show HN: Super Simple CRC32 Implementation

#9

Post by palsecam »

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 >> 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

Re: Show HN: Super Simple CRC32 Implementation

#10

Post by fargle »

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/

Post reply on HN