[TUHS] CRC calculation in the 1980s

[TUHS] CRC calculation in the 1980s

[Paul Ruizendaal]

>> 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?
> 
> Could it have been the per-cpu-second billing that was (fairly?) common at the time.  I was only getting in to Unix in the early 90s but saw the tail end of that.


Good point, but wasn’t per-cpu-second billing mostly used for big iron? For machines without memory constraint the table method makes the most sense, also if billing was not a factor.


>> 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?
> 
> The CRC algorithm I'm familiar with shows up in Dragon Quest for the Famicom in 1986[1], written in 6502 assembly.  Admittedly though I only recognized it due to the EOR with 0x1021 on lines 318-323. That I then only know from a quick and dirty CRC I threw in an XMODEM-CRC client [2] I did to accommodate for a bug in the JH7100 RISC-V board's recovery ROM implementation.  Not sure if this is along the lines of the approach you're talking about ...
> 
> [1] - https://gitlab.com/segaloco/dq1disasm/-/blob/master/src/chr3/start_pw.s
> [2] - https://gitlab.com/segaloco/riscv-bits/-/blob/master/util/sxj.c


Both of these are what I call the bit-wise method: a loop iterating over bytes, with an inner loop iterating over bits. An example of the table method is here:
https://github.com/u-boot/u-boot/blob/master/lib/crc16-ccitt.c
and an example of the on-the-fly method is here:
https://github.com/tio/tio/blob/master/src/xymodem.c#L44-L54

Note how the latter also only has one loop iterating over the bytes, but effectively calculates the table entry ‘on the fly’ for each byte. That is only a handful of instructions more than doing the table lookup. Maybe it is a “stuck in the middle” solution that was quickly forgotten.

[TUHS] CRC calculation in the 1980s

[Paul Ruizendaal]

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?