[TUHS] CRC calculation in the 1980s

Paul Ruizendaal pnr at planet.nl
Tue Sep 19 09:02:21 AEST 2023

When looking at old xmodem code I noticed that it calculated its CRC bit-by-bit, switching to byte-wise using a table in the late 80’s. It never seems to have used the byte-wise, “on-the-fly” algorithm. This seems to match a pattern: I often come across bit-wise and table implementations, but rarely on-the-fly implementations if any. The on-the-fly algorithm was known at least since 1983, following a paper by Perez: http://www.bitsavers.org/components/fairchild/_appNotes/Byte-wise_CRC_Jun83.pdf
The paper was noted, for example it is on the citation list of RFC1134, describing the PPP protocol. Today, a wikipedia page gives implementations for various polynomials: https://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks#Parallel_computation_without_table

Now, it would seem to me that on memory constrained personal computers and PDP-11’s the “on-the-fly” algorithm would have been a good choice, being just a few lines of code and maybe 30-50% slower than table lookup. The tables aren’t big, but a kilobyte is a lot when you only have 64.

Any suggestions as to why the on-the-fly algorithm did not catch on more in the 1980’s? Maybe it was simply less well known than I think?

More information about the TUHS mailing list