[lkml]   [2005]   [Aug]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: CCITT-CRC16 in kernel
> The "Bible" has been:

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:

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
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

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:

> 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
More majordomo info at
Please read the FAQ at

 \ /
  Last update: 2005-08-12 12:50    [from the cache]
©2003-2014 Jasper Spaans. hosted at Digital Ocean