[TUHS] Re: CRC calculation in the 1980s

[TUHS] Re: CRC calculation in the 1980s

[Noel Chiappa]

    > From: 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?

I can't answer that directly, but I will point you at IEN-56, "CRC Checksum
Calculation", by Dave Reed (11-Sep-78):

    https://www.rfc-editor.org/ien/ien56.pdf

Dave wanted the INWG to use a more powerful (in terms of detecting errors)
CRC, instead of the simple summation eventually adopted, in TCP and IP. So he
produced code to implement a particular CRC, to show people that it would not
be particularly expensive (whether in time, or space, I don't alas recall
definitively; speed would have been an important consideration, when
competing with the summation, though).

This would have been close to the leading edge of our knowledge at the time;
Dave liked playing around with math, and at about that time he did a very
fast DES implementation.

	Noel

[TUHS] Re: CRC calculation in the 1980s

[Lars Brinkhoff]

Noel Chiappa writes:
> I can't answer that directly, but I will point you at IEN-56, "CRC
> Checksum Calculation", by Dave Reed (11-Sep-78):
>
>     https://www.rfc-editor.org/ien/ien56.pdf

I can't help but notice the first program is PDP-10 code for running
on ITS.  ObTUHS: the other is a PDP-11 asssembly language program for
Unix.  Machine readable versions for both can be procured.

[TUHS] Re: CRC calculation in the 1980s

[Paul Ruizendaal]

> On 19 Sep 2023, at 13:42, Noel Chiappa <jnc@mercury.lcs.mit.edu> wrote:
> 
>> From: 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?
> 
> I can't answer that directly, but I will point you at IEN-56, "CRC Checksum
> Calculation", by Dave Reed (11-Sep-78):
> 
>    https://www.rfc-editor.org/ien/ien56.pdf
> 
> Dave wanted the INWG to use a more powerful (in terms of detecting errors)
> CRC, instead of the simple summation eventually adopted, in TCP and IP. So he
> produced code to implement a particular CRC, to show people that it would not
> be particularly expensive (whether in time, or space, I don't alas recall
> definitively; speed would have been an important consideration, when
> competing with the summation, though).
> 
> This would have been close to the leading edge of our knowledge at the time;
> Dave liked playing around with math, and at about that time he did a very
> fast DES implementation.
> 
> 	Noel

That is a very interesting paper and it uses the same polynomial. The algorithm seems different from the one that Perez published in 1983, but in the same general direction. So it would seem that this “on-the-fly” method was not (well) known prior to 1983. By the looks of it, it was not well known afterwards either.

You were part of the group that invented it and I’m telling you stuff you know better than I do, but the adopted summation in TCP/IP had a lot of advantages: it could be efficiently calculated on 36, 32 and 16 bit machines, it did not care about endianness and was efficient on both two’s and one’s complement machines. I don’t think CRC had all those properties.

I don’t think in 1978 the IEN group was aiming for the LAN use case, but as it turned out a few years later the simple summation consumed 25% of a VAX-750 CPU to saturate 3 Mbps ethernet. Even a 30% slowdown in checksumming would have been costly -- but you already pointed out that speed was an important consideration.

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