[TUHS] CRC calculation in the 1980s

[Paul Ruizendaal <pnr@planet.nl>]

>> 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.