Re: [John Robinson <jr@LF-SERVER-2.BBN.COM>: Re: TCP performanc...]


on UK.MOD.RSRE (LAWS%rsre.mod.uk@NSS.Cs.Ucl.AC.UK)
Sun, 11 Oct 87 00:18


Vint,

I guess this reply should be to the John Robinson portion of your
msg - but my mailer is not that smart.

Concerning CRC checksum computation. More than 17 years ago I read a
paper on this topic which used matrix algebra to construct look-up
tables. You took your choice - one large table and a simple one
line equation, or more smaller tables and more complicated equations.
I could still remember enough maths then to follow the algebra
through and did a single table version for the CRC-16 checksum. I
used it in EIN and passed it around the European centres (there was
no chips then for this and most folks were having to do it in one-off
hardware of the day). My code implementation for a CTL Modular-One
(a UK m/c with some interesting inovations that were to appear in DEC
PDP 11) ran at 10 micro-secs per byte and only a little longer in
Corai-66. My only export of this to the US was Ed Cain about 2/3 years
ago.

What does suprise me is the steady rain of papers on this topic which
often propose less effective solutions (and also get the algorithm
wrong) and never reference this old paper. Just a mo......

....found it -

P E Boudreau and R F Steen
(IBM Corp, Research Triangle Park, N.C.)
Cyclic Redundancy checking by program.
AFIPS Conf Proc Vol.39 1971, pp 9-15

and the latest I just found this week and in my briefcase waiting
to be read

Georgia Griffiths and G Carlyle Stones
The tea-leaf reader algorithm: an efficient implementation of
CRC-16 and CRC-32.
Comms of the ACM July 1987 Vol.30 No.7 pp 617-620

typos: tbles = tables, Corai-66 = Coral-66

John



This archive was generated by hypermail 2.0b3 on Thu Mar 09 2000 - 14:39:35 GMT