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.