Path: utzoo!attcan!uunet!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!MIRSA.INRIA.FR!Christian.Huitema
From: Christian.Huitema@MIRSA.INRIA.FR (Christian Huitema)
Newsgroups: comp.protocols.iso
Subject: Re: Looking for IEEE 802.3 (LLC) CRC Generating Software
Message-ID: <8905260720.AA28540@jerry.inria.fr>
Date: 26 May 89 07:19:59 GMT
References: <ADNAN.89May24092053@sgtech.UUCP>
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The Internet
Lines: 22

The method that you refer to is quite clear. You have to compute the
rest of the division of a polynom by a generator, say D32.

Most hardware implement it with shift register technics:
let	P(n) = a n bits polynom,
	P(n+1) = x.P(n) + a(n+1),
	R(n) = P(n) [D32]
then	R(n+1) = x.R(n) + a(n+1) [D32]
If the polynom is well formed, the latter can be computed by looking for a 
x**31 component in R(n):
	if exists x**31 in R(n),
	then:	R(n+1) = (x.(R(n) - x**31) + a(n+1))^R32
		where	R32 = x**32 [D32],
	else	R(n+1) = x.R(n) + a(n+1).
That can be wired with a shift register + xor operation.

The software algorithm basically does the same, but operates on octets
instead of single bits. Instead of xoring R32, one xors R[x], where
R[x] is the remainder of an 8 bits polynoms x, times X**32, by D32.
Computation is trivial.