Re: CCITT-CRC16 in kernel

[linux@horizon.com]

> The "Bible" has been:
>  	http://www.joegeluso.com/software/articles/ccitt.htm

This fellow is just plain Confused.

First of all, The Standard Way to do it is to preset to -1 *and* to
invert the result.  Any combination is certainly valid, but if you don't
invert the CRC before appending it, you fail to detect added or deleted
trailing 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't
aware that *everyone* uses the "implicit" algorithm, so the reason that
the specs don't explain that very well is that the spec writers forgot
there was any other way to do it.

So his long-hand calculations are just plain WRONG.  Presetting the CRC
accumulator to -1 is equivalent to *inverting the first 16 bits of the
message*, 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 10001000000100001
Message: ascii "A", 0x41.
Convert to bits, lsbit first: 10000010
Append trailing padding to hold CRC: 100000100000000000000000
Invert first 16 bits: 011111011111111100000000

Now let's do the long division.  You can compute the quotient, but it's
not needed for anything, so I'm not bothering to write it down:

011111011111111100000000
 10001000000100001
 -----------------
  11100111110111010
  10001000000100001
  -----------------
   11011111100110110
   10001000000100001
   -----------------
    10101111000101110
    10001000000100001
    -----------------
      10011100000111100
      10001000000100001
      -----------------
        0101000000111010 - Final remainder

XOR trailing padding with computed CRC (since we used padding of zero,
that's equivalent to overwriting it): 100000100101000000111010 
Or, if the CRC is inverted: 100000101101011111000101

To double-check, let's verify that CRC.  I'm verifying the
non-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 remainder

Now, note how in each step, the decision whether to XOR with the 17-bit
polynomial is made based soley on the leading bit of the remainder.
The trailing 16 bits are modified (by XOR with the polynomial), but
not examined.

This leads to a standard optimization, where the bits from the dividend
are not merged into the working remainder until the moment they are
needed.  Each step, the leading bit of the 17-bit remainder is XORed
with the next dividend bit, and the polynomial is XORed in as required
to force the leading bit to 0.  Then the remainder is shifted, discarding
the leading 0 bit and shifting in a trailing 0 bit.

This technique avoids the need for explicit padding, and is the way
that the computation is invariably performed in all but pedagogical
implementations.

Also, the awkward 17-bit size of the remainder register can be reduced
to 16 bits with care, as at any given moment, one of the bits is known
to be zero.  It is usually the trailing bit, but between the XOR and
the shift, it is the leading bit.

(Again, recall that in a typical software implementation, the "leading
bit" is the lsbit and the "trailing bit" is the msbit.  Because the
CRC 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.html
http://www.aerospacesoftware.com/checks.htm
http://www.bsdg.org/SWAG/CRC/0011.PAS.html
http://www.ethereal.com/lists/ethereal-dev/200406/msg00414.html
http://pajhome.org.uk/progs/crcsrcc.html
http://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 of
protocols (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" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/