Re: CCITT-CRC16 in kernel

[linux@horizon.com]

> Does anybody know what the CRC of a known string is supposed
> to be? I have documentation that states that the CCITT CRC-16
> of "123456789" is supposed to be 0xe5cc and "A" is supposed
> to be 0x9479. The kernel one doesn't do this. In fact, I
> haven't found anything on the net that returns the "correct"
> value regardless of how it's initialized or how it's mucked
> with after the CRC (well I could just set the CRC to 0 and
> add the correct number). Anyway, how do I use the crc_citt
> in the kernel? I've grepped through some drivers that use
> it and they all seem to check the result against some
> magic rather than performing the CRC of data, but not the
> CRC, then comparing it to the CRC. One should not have
> to use magic to verify a CRC, one should just perform
> a CRC on the data, but not the CRC, then compare the result
> with the CRC. Am I missing something here?

There are two common 16-bit CRC polynomials.
The original IBM CRC-16 is x^16 + x^15 + x^2 + 1.
The more popular CRC-CCITT is x^16 + x^12 + x^5 + 1.

Both of thse include (x+1) as a factor, so provide parity detection,
detecting all odd-bit errors, at the expense of reducing the largest
detectable 2-bit error from 65535 bits to 32767.

All CRC algorithms work on bit strings, so an endianness convention
for bits within a byte is always required.  Unless specified, the
little-endian RS-232 serial transmission order is generally assumed.
That isl the least significant bit of the first byte is "first".

This bit string is equated to a polynomial where the first bit is
the coefficient of the highest power of x, and the last bit (msbit of
the last byte) is the coefficient of x^0.

(Some people think of this as big-endian, and get all confused.)

Using this bit-ordering, and omitting the x^16 term as is
conventional (it's implicit in the implementation), the polynomials
come out as:
CRC-16: 0xa001
CRC-CCITT: 0x8408

The mathematically "cleanest" CRC has the unfortunate property that
leading or trailing zero bits can be added or removed without affecting
the CRC computation.  That is, they are not detected as errors.
For fixed-size messages, this does not matter, but for variable-sized
messages, a way to detect inserted or deleted padding is desirable.

To detect leading padding, it is customary to invert the first 16 bits
of the message.  This is equivalent to initializing the CRC accumulator
to all-ones rather than 0, and is invariably implemented that way.

This change is duplicated on CRC verification, and has no effect on the
final result.

To detect trailing padding, it is customary to invert all 16 bits of
the CRC before appending it to the message.  This has an effect on
CRC verification.

One way to CRC-check a message is to compute the CRC of the entire
message *including* the CRC.  You can see this in many link-layer protocol
specifications which place the trailing frame delimiter after the CRC,
because the decoding hardware doesn't need to know in advance where the
message stops and the CRC starts.

If the CRC is NOT inverted, the CRC of a correct message should be zero.
If the CRC is inverted, the correct CRC is a non-zero constant.  You can
still use the same "checksum everything, including the original CRC"
technique, but you have to compare with a non-zero result value.

For CRC-16, the final result is x^15 + x^3 + x^2 + 1 (0xb001).
For CRC-CCITT, the final result is x^13+x^11+x^10+x^8+x^x^3+x^2+x+1 (0xf0b8).

The *other* think you have to do is append the checksum to the message
correctly.  As mentioned earlier, the lsbit of a byte is considered
first, so the lsbyte of the 16-bit accumulator is appended first.


Anyway, with all this, and using preset-to-all-ones:
CRC-CCITT of "A" is 0x5c0a, or f5 a3 when inverted and converted to bytes.
CRC-CCITT of "123456789" is 0x6f91, or 63 90.
(When preset to zero, the values are 0x538d and 0x2189, respectively.
That would be 8d 53 or 89 21 if *not* inverted.)
-
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/