Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

Nomenclature of CRC functions #12

Closed
bminer opened this Issue February 12, 2013 · 7 comments

2 participants

Blake Miner Alex Gorbatchev
Blake Miner

@alexgorbatchev - I ran a few of the CRC functions and came up with the following (as of the last commit affe249):

  • crc16Arc(...) is "normal" CRC-16 with 0x8005 polynomial. Why is it called crc16Arc? I've personally never heard that before...
  • crc16(...) is not normal CRC-16 with 0x8005 polynomial; it's CRC-CCITT (XModem, 0x1021 polynomial)
  • crc16CCITT(...) is no longer implemented, but it used to be CRC-CCITT (0xFFFF).

Checkout http://www.lammertbies.nl/comm/info/crc-calculation.html for more info.

Alex Gorbatchev

Hm... so it's all wrong essentially? :) I didn't anticipate this module getting any attention, but it feels like it could use some love. What do you think?

Blake Miner

Nah, it's not all that bad. It's a great lib, really! I'd be glad to contribute via pull requests or whatever. Just let me know what you think.

Alex Gorbatchev

@bminer if you are still up for contributing proper function naming, I would really appreciate it!

It would have to be released as a major version, but i'm not quite sure how to handle the fact that crc16arc will become crc16

Alex Gorbatchev

@bminer, wanted to follow up with you on this. What do you think?

Blake Miner

@alexgorbatchev - Sorry for not responding. I currently don't have any time to contribute to this lib, but I know that it's pretty widely used.

So, after doing some research about cyclic redundancy checks (CRCs), I've determined the following:

  • CRCs are calculated by performing polynomial long division in which the message is the dividend and the so-called generator polynomial is the divisor. The remainder of this polynomial long division operation is the CRC.
  • There are an infinite number of CRC algorithm variations :) You can make your own unique algorithm by tweaking any of the following parameters:
    • number of bits of the CRC (i.e. CRC-16, CRC-32, etc.) -- this affects the degree of the generator polynomial
    • generator polynomial (its coefficients)
    • initialized value of the CRC value (initialized value before the CRC computation begins)
    • whether or not the CRC value is inverted after the CRC computation (see Variations )
    • Is the input data reflected (i.e. reversed bitwise before computing the CRC)?
    • Is the CRC reflected?
    • Is the CRC XOR'ed with a fixed value after the computation?
  • The selection of the generator polynomial is the most important aspect of designing an effective CRC algorithm to maximize the error-detecting capabilities while minimizing overall collision probabilities.
  • There is a fairly complete catalogue of all "standardized" CRC algorithms located here: http://reveng.sourceforge.net/crc-catalogue/all.htm

With all of that said, the node-crc library has incorrectly labelled a few of the CRC functions. I would recommend that you take a look at the catalogue to see what's what.

As far as changing the lib goes, I would consider the next release to be a major, breaking release. There will be some applications that have persistently stored the CRCs generated by this library, and changing the names of the CRC algorithms could have severe consequences for some users.

Anyway, I hope that helps. Please feel free to write back here with your comments, etc. Thanks again for such a great lib!

Blake Miner

Also, I was scratching my head for a while trying to figure out what CCITT meant. As far as I can tell, it means "The ITU Telecommunication Standardization Sector," formerly called the International Telegraph and Telephone Consultative Committee (CCITT, from French: Comité Consultatif International Téléphonique et Télégraphique).

So, there you have it!

Alex Gorbatchev
Owner

full rewrite based on a Ruby Digest::CRC module.

Alex Gorbatchev alexgorbatchev closed this March 24, 2014
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.