[TUHS] CRC calculation in the 1980s
Paul Ruizendaal
pnr at planet.nl
Wed Sep 20 00:10:13 AEST 2023
>> 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.
More information about the TUHS
mailing list