alexgorbatchev / crc

Blazingly fast CRC implementations for node.js and browser
MIT License
349 stars 72 forks source link

CRC-32 incorrect handling of the 0 seed #70

Open SheetJSDev opened 2 years ago

SheetJSDev commented 2 years ago

discussed in #66 but the original analysis was incorrect because it did not actually test the case where 0 is the previous value.

Ruby code:

require 'zlib'

puts("no initial value   : #{(Zlib::crc32('1')).to_s(16)}")     # no initial value   : 83dcefb7
puts("with initial value : #{Zlib::crc32('1', 0).to_s(16)}")    # with initial value : 83dcefb7

Using crc-32:

const CRC32 = require('crc-32');
console.log(`no initial value   : ${(CRC32.bstr('1')>>>0).toString(16)}`);    // no initial value   : 83dcefb7
console.log(`with initial value : ${(CRC32.bstr('1', 0)>>>0).toString(16)}`); // with initial value : 83dcefb7

Using crc:

const {crc32} = require('crc');
console.log(`no initial value   : ${crc32('1').toString(16)}`);     // no initial value   : 83dcefb7
console.log(`with initial value : ${crc32('1', 0).toString(16)}`);  // with initial value : ae21ffc5

The error is in the special 0 case, which probably stems from a misinterpretation of the english description.

The APPNOTE.TXT specification states:

       The proper CRC pre and post
       conditioning is used, meaning that the CRC register
       is pre-conditioned with all ones (a starting value
       of 0xffffffff) and the value is post-conditioned by
       taking the one's complement of the CRC residual.

Some developers misinterpret that to mean the seed starts at -1. but it's actually saying that the crc variable starts at -1:

const crc32: CRCCalculator<Uint8Array> = (current, previous) => {
  // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
  let crc = previous === 0 ? 0 : ~~previous! ^ -1;
  // ^^^^ This `crc` variable is the "CRC register"

  for (let index = 0; index < current.length; index++) {
    crc = TABLE[(crc ^ current[index]) & 0xff] ^ (crc >>> 8);
  }

  return crc ^ -1;
};

There is no need to special-case the 0, and the TS code might as well be simplified to:

const crc32: CRCCalculator<Uint8Array> = (current, previous = 0) => {
  let crc = previous ^ -1; // no need to coerce to 32 bit signed int

  for (let index = 0; index < current.length; index++) {
    crc = TABLE[(crc ^ current[index]) & 0xff] ^ (crc >>> 8);
  }

  return crc ^ -1;
};
c0depwn commented 2 years ago

@SheetJSDev Thank you so much for your clarification I spent hours trying to figure out why the signature wasn't correct 🥲

SheetJSDev commented 2 years ago

The website cited in the other issue uses the phrase "Initial Value" at the top of the page and the phrase "Initial CRC value" in the Description, so it's easy to see how @alexgorbatchev misinterpreted the default case.