Rolling CRC #11

Activity

1. lemire commented on Apr 14, 2019

   

   lemire

   on Apr 14, 2019

   Owner

   More actions

   Yes, Craig, I am interested.
2. cmcqueen commented on Apr 21, 2019

   

   cmcqueen

   on Apr 21, 2019

   Author

   More actions

   Okay, I'm working on a write-up.
3. cmcqueen commented on Mar 11, 2022

   

   cmcqueen

   on Mar 11, 2022

   Last edited by cmcqueen

   Author

   More actions

   Outline

   • Refer to classic doc on CRCs: A Painless Guide to CRC Error Detection Algorithms, by Ross Williams
   • For the purposes of a rolling CRC, it is sensible to avoid doing any initial/final XOR as often done in classic CRC algorithms. That would just add unnecessary complexity for use in a rolling CRC.
   • Classically, CRCs have been described as calculating the remainder of binary long-division. Another way of describing it is, polynomial reduction using a reducing polynomial. Then CRCs can be thought of as operations in a Galois field such as GF(2^32), where the CRC polynomial is the reducing polynomial of the Galois Field.
   • A CRC "permutes" in each byte cycle by being multiplied by 0x100 and then reduced by the polynomial (ie modulo the polynomial in the Galois field). So a CRC value permuted through n bytes can be thought of as being multiplied by pow(0x100, n) modulo the polynomial in the Galois field.
   • CRCs combine linearly (using XOR). So
     • CRC(0x03) = CRC(0x01) XOR CRC(0x02)
     • CRC(0x01 0x02 0x03 0x04 0x05) = CRC(0x01 0x00 0x00 0x00 0x00) XOR CRC(0x00 0x02 0x03 0x04 0x05)
   • So when calculating a n-byte sliding window, the oldest byte can be "removed" from the CRC value by calculating the CRC of the byte "delayed" by n bytes.
   • A look-up table can be made of all 256 byte values "delayed" by n bytes, for an efficient "removal" of each oldest byte from the sliding window in a rolling CRC.
   • Because CRCs combine linearly, a 256-entry look-up table can be constructed by first calculating the CRC of the 8 1-bit values "delayed" by n bytes, then building each of the 256 entries by XORing the appropriate combination of the 8 values.

   See

   • Catalogue of parametrised CRC algorithms — CRC-16/XMODEM
   • Catalogue of parametrised CRC algorithms — CRC-32
   • BartMassey/rolling-crc: original Zhugansin C code for rolling hash
4. lemire commented on Mar 11, 2022

   

   lemire

   on Mar 11, 2022

   Owner

   More actions

   +1