View on GitHub

Quorten Blog 1

First blog for all Quorten's blog-like writings

CRC is reasonably easy and fast to compute in software with the use of a lookup table, not that much worse than XOR checksumming.

So, here’s the algorithm given on Wikipedia…

Function CRC32
   Input:
      data:  Bytes     //Array of bytes
   Output:
      crc32: UInt32    //32-bit unsigned crc-32 value

//Initialize crc-32 to starting value
crc32 ← 0xFFFFFFFF

for each byte in data do
   nLookupIndex ← (crc32 xor byte) and 0xFF;
   crc32 ← (crc32 shr 8) xor CRCTable[nLookupIndex] //CRCTable is an array of 256 32-bit constants

//Finalize the CRC-32 value by inverting all the bits
crc32 ← crc32 xor 0xFFFFFFFF
return crc32

This is really good to know. So it means it will be reasonably easy for me to implement a full TCP/IP over serial stack on my own, in software using standard C.

The table must be pre-computed in advance. I’ll cover more information on this.

Some other useful statements of fact:

  • 1-bit parity is in fact a special case of CRC.

  • “XOR checksums” (sequentially wrap-around XOR bytes into a finite buffer) is also another special case of CRC. The more formal name is longitudinal redundancy check (LRC). “Bit-interleaved parity.”

20190919/https://en.wikipedia.org/wiki/Cyclic_redundancy_check
20190919/https://en.wikipedia.org/wiki/Longitudinal_redundancy_check
20190919/https://en.wikipedia.org/wiki/BIP-8
20190919/https://en.wikipedia.org/wiki/Block_check_character

So, about the table computation. How do you do this? Build off of the great explanation of how the BinHex/MacBinary file format work. Basically, you can perform a 1-bit CRC computation step as follows.

  • Start with a CRC result register of zero.
  • Shift the CRC result register to the left, and your next data bit comes in from the right.
  • If the bit shifted out is 1, then XOR the polynomial with your register. Otherwise, do nothing.
  • Once you’ve shifted all data bits in, you have your result.

20190919/http://files.stairways.com/other/binhex-40-specs-info.txt

Please note that the table-based method of computing CRC checksums is only practical on processors that can shift by more than one bit at a time, i.e. modern 32-bit processors or better. For 8-bit processors, it may make more sense to use the 1-bit shifting computation method.