Messages in this thread
 Date 12 Aug 2005 06:48:03 -0400 From linux@horizon ... Subject Re: CCITT-CRC16 in kernel
`> The "Bible" has been:>  	http://www.joegeluso.com/software/articles/ccitt.htmThis fellow is just plain Confused.First of all, The Standard Way to do it is to preset to -1 *and* toinvert the result.  Any combination is certainly valid, but if you don'tinvert the CRC before appending it, you fail to detect added or deletedtrailing zero bits, which can be A Bad Thing in some applications.Secondly, I see what he's on about "trailing zero bits", but he isn'taware that *everyone* uses the "implicit" algorithm, so the reason thatthe specs don't explain that very well is that the spec writers forgotthere was any other way to do it.So his long-hand calculations are just plain WRONG.  Presetting the CRCaccumulator to -1 is equivalent to *inverting the first 16 bits of themessage*, and NOT to prepending 16 1 bits.Also, he's got his bit ordering wrong.The correct way to do it, long-hand, is this:Polynomial: x^16 + x^12 + x^5 + 1.  In bits, that's 10001000000100001Message: ascii "A", 0x41.Convert to bits, lsbit first: 10000010Append trailing padding to hold CRC: 100000100000000000000000Invert first 16 bits: 011111011111111100000000Now let's do the long division.  You can compute the quotient, but it'snot needed for anything, so I'm not bothering to write it down:011111011111111100000000 10001000000100001 -----------------  11100111110111010  10001000000100001  -----------------   11011111100110110   10001000000100001   -----------------    10101111000101110    10001000000100001    -----------------      10011100000111100      10001000000100001      -----------------        0101000000111010 - Final remainderXOR trailing padding with computed CRC (since we used padding of zero,that's equivalent to overwriting it): 100000100101000000111010 Or, if the CRC is inverted: 100000101101011111000101To double-check, let's verify that CRC.  I'm verifying thenon-inverted CRC, so I expect a remainder of zero:Received message:     100000100101000000111010 Invert first 16 bits: 011111011010111100111010 011111011010111100111010  10001000000100001 -----------------  11100110100111011  10001000000100001  -----------------   11011101000110101   10001000000100001   -----------------    10101010000101001    10001000000100001    -----------------      10001000000100001      10001000000100001      -----------------         000000000000000 - Final remainderNow, note how in each step, the decision whether to XOR with the 17-bitpolynomial is made based soley on the leading bit of the remainder.The trailing 16 bits are modified (by XOR with the polynomial), butnot examined.This leads to a standard optimization, where the bits from the dividendare not merged into the working remainder until the moment they areneeded.  Each step, the leading bit of the 17-bit remainder is XORedwith the next dividend bit, and the polynomial is XORed in as requiredto force the leading bit to 0.  Then the remainder is shifted, discardingthe leading 0 bit and shifting in a trailing 0 bit.This technique avoids the need for explicit padding, and is the waythat the computation is invariably performed in all but pedagogicalimplementations.Also, the awkward 17-bit size of the remainder register can be reducedto 16 bits with care, as at any given moment, one of the bits is knownto be zero.  It is usually the trailing bit, but between the XOR andthe shift, it is the leading bit.(Again, recall that in a typical software implementation, the "leadingbit" is the lsbit and the "trailing bit" is the msbit.  Because theCRC algorithm does not use addition or carries or anything of the sort,it does not care which convention software uses.)> I have spent over a week grabbing everything on the Web that> could help decipher the CCITT CRC and they all show this> same kind of code and same kind of organization. Nothing> I could find on the Web is like the linux kernel ccitt_crc.> Go figure.Funny, I can find it all over the place:http://www.nongnu.org/avr-libc/user-manual/group__avr__crc.htmlhttp://www.aerospacesoftware.com/checks.htmhttp://www.bsdg.org/SWAG/CRC/0011.PAS.htmlhttp://www.ethereal.com/lists/ethereal-dev/200406/msg00414.htmlhttp://pajhome.org.uk/progs/crcsrcc.htmlhttp://koders.com/c/fidE2A434B346BFDCD29DA556A54E37C99E403ED26B.aspx> Do you suppose it was bit-swapped to bypass a patent?There's no patent.  That's just the way that the entire SDLC family ofprotocols (HDLC, LAPB, LAPD, SS#7, X.25, AX.25, PPP, IRDA, etc.) do it.They transmit lsbit-first, so they compute lsbit-first.-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/`

Last update: 2005-08-12 12:50    [W:0.042 / U:1.388 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site