adnan@sgtech.UUCP (Adnan Yaqub) (05/24/89)
I'm looking for software which generates the 32 bit LLC frame check sequence (CRC). I once wrote a routine which generated a CRC-16. It was based on a table look up method where, for each byte of the message, one generated a new crc from the old crc and the byte as follows: new_crc = ((old_crc>>8)^crc_tbl[byte^(old_crc&0xff)]); The crc table consisted of 256 16-bit values I generated from considering 256 trivial one byte messages. I would like to use this method for the LLC CRC-32, but I can't seem to generate a correct table. BTW, the generating polynomial for the LLC FCS is: g(x)=x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1 -- Adnan Yaqub Star Gate Technologies, 29300 Aurora Rd., Solon, OH, USA, +1 216 349 1860 ...uunet!abvax!sgtech!adnan
Christian.Huitema@MIRSA.INRIA.FR (Christian Huitema) (05/26/89)
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.