[TUHS] CRC calculation in the 1980s

[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?

[TUHS] Re: CRC calculation in the 1980s

[Robert Brockway]

[-- Attachment #1: Type: text/plain, Size: 380 bytes --]

On Tue, 19 Sep 2023, Paul Ruizendaal wrote:

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

Cheers,

Rob

[TUHS] Re: CRC calculation in the 1980s

[segaloco via TUHS]

> 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, admittedly these two instances are literally all I know about CRC, just enough to be dangerous :)

Still, a concrete example of ChunSoft's 6502 CRC calculation in the mid 80s, if that helps with the assessment of the time period/flow of ideas in the industry.

- Matt G.

[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

[TUHS] Re: CRC calculation in the 1980s

[Paul Winalski]

For what it's worth, the VAX had a table-driven CRC instruction.  It
wasn't very popular because on most VAX models it was actually slower
than by-hand coding.  It is one of the instructions dropped from the
microVAX instruction set used on all later VAXen, where it was
emulated by the operating system.

-Paul W.

[TUHS] Re: CRC calculation in the 1980s

[Dan Cross]

On Tue, Sep 19, 2023 at 11:34 AM Paul Winalski <paul.winalski@gmail.com> wrote:
> For what it's worth, the VAX had a table-driven CRC instruction.  It
> wasn't very popular because on most VAX models it was actually slower
> than by-hand coding.  It is one of the instructions dropped from the
> microVAX instruction set used on all later VAXen, where it was
> emulated by the operating system.

I thought that was a general polynomial root finder instruction that
used Horner's Method?  Obviously it could be used in CRC calculations,
but I remember it being more general. I also remember reading about it
in the VAX architecture manual and thinking, "wow,
that's...something."

        - Dan C.

[TUHS] Re: CRC calculation in the 1980s

[Paul Winalski]

On 9/19/23, Dan Cross <crossd@gmail.com> wrote:
(regarding the CRC instruction on VAX)
>
> I thought that was a general polynomial root finder instruction that
> used Horner's Method?  Obviously it could be used in CRC calculations,
> but I remember it being more general. I also remember reading about it
> in the VAX architecture manual and thinking, "wow,
> that's...something."

VAX had both a CRC instruction and a polynomial instruction.  CRC
operated on byte strings and did fixed-point calculation.  The
polynomial instructions (POLYF and POLYD) operated on single-precision
(F) or double-precision (D) data.  Unfortunately the algorithm used by
POLYF and POLYD wasn't very accurate--there were other algorithms that
did a better job preserving precision.  Anyone doing serious
calculations in floating point avoided POLYF and POLYD.  These were
two more of the instructions that were dropped from the microVAX
architecture and emulated by the OS.

-Paul W.

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