The tea-leaf reader algorithm: an efficient implementation of CRC-16 and CRC-32

Reviewer: Michael W. Whitelaw

The Cyclical Redundancy Check (CRC) is an effective error-detecting checksum technique for data packages. The CRC relies on forming logical relationships between the bits of a message by shifting the message in a register. It is usually described and performed in a bitwise manner. This paper shows a method for drastically saving execution time. For a fixed length word, the relationships can be precomputed and stored in tables. This allows the encoding to be done by table-lookup at the byte level rather than by calculation at the bit level. Savings of at least an order of magnitude are reported. The paper is economical in presentation. The information provided allows a programmer to implement the tea-leaf reader algorithm if he or she is already conversant with CRCs. The reader not conversant with CRCs needs to refer to the references. The strategy for reducing run-time is a general one and makes the technique an interesting case study even for those who are not directly interested in CRCs. Unfortunately the authors limit their discussion of strategy inspiration to the point that there is not an adequate justification of the algorithm name “tea-leaf reader.” Having read and understood the paper, I can guess, I think.