CCITT-CRC16 in kernel

CCITT-CRC16 in kernel

[linux-os (Dick Johnson)]

Hello CRC Wizards,

I am trying to use ../linux-2.6.12/lib/crc_citt in a driver.
Basically, it doesn't return anything that closely resembles
the CCIT-16 CRC. I note that drivers that use it expect it
to return 0xf0b8 if it performs the CRC of something that
has the CRC appended (weird).

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?


Cheers,
Dick Johnson
Penguin : Linux version 2.6.12 on an i686 machine (5537.79 BogoMips).
Warning : 98.36% of all statistics are fiction.
.
I apologize for the following. I tried to kill it with the above dot :

****************************************************************
The information transmitted in this message is confidential and may be privileged.  Any review, retransmission, dissemination, or other use of this information by persons or entities other than the intended recipient is prohibited.  If you are not the intended recipient, please notify Analogic Corporation immediately - by replying to this message or by sending an email to DeliveryErrors@analogic.com - and destroy all copies of this information, including any attachments, without reading or disclosing them.

Thank you.

Re: CCITT-CRC16 in kernel

[Paul Fulghum]

linux-os (Dick Johnson) wrote:

>the CCIT-16 CRC. I note that drivers that use it expect it
>to return 0xf0b8 if it performs the CRC of something that
>has the CRC appended (weird).
>

That is the remainder you get when checking
a received CRC for correctness. If the value
is not 0xf0b8, there is an error in the block.

--
Paul Fulghum
Microgate Systems, Ltd

Re: CCITT-CRC16 in kernel

[linux]

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

Re: CCITT-CRC16 in kernel

[linux-os (Dick Johnson)]

[-- Attachment #1: Type: text/plain, Size: 6173 bytes --]


On Wed, 10 Aug 2005 linux@horizon.com wrote:

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

Huh? That's the problem.

X^16 + X^12 + X^5 + X^0 = 0x1021, not 0xa001

Also,

X^16 + X^15 + X^2 + X^0 = 0x8005, not 0x8408

Attached is a program that will generate a table of polynomials
for the conventional CRC lookup-table code. If you look at
the table in the kernel code, offset 1, you will see that
the polynomial is 0x1189. This corresponds to the CRC of
the value 1. It does not correspond to either your polynomials
or the ones documented on numerous web pages.

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

So yes, we start with 0xffff.

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

I think somebody just guessed and came up with "magic" because the
table being used isn't correct.

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

Right, but the hardware did that. I have no control over that. I
have to figure out if:

(1) It started with 0xffff or something else.
(2) It was inverted after.
(3) The result was byte-swapped.

With the "usual" CRC-16 that I used before, using the lookup-
table that is for the 0x1021 polynomial, hardware was found
to have inverted and byte-swapped, but started with 0xefde
(0x1021 inverted). Trying to use the in-kernel CRC, I was
unable to find anything that made sense.

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

Thanks.


Cheers,
Dick Johnson
Penguin : Linux version 2.6.12 on an i686 machine (5537.79 BogoMips).
Warning : 98.36% of all statistics are fiction.
.
I apologize for the following. I tried to kill it with the above dot :


****************************************************************
The information transmitted in this message is confidential and may be privileged.  Any review, retransmission, dissemination, or other use of this information by persons or entities other than the intended recipient is prohibited.  If you are not the intended recipient, please notify Analogic Corporation immediately - by replying to this message or by sending an email to DeliveryErrors@analogic.com - and destroy all copies of this information, including any attachments, without reading or disclosing them.

Thank you.

[-- Attachment #2: gentable.c --]
[-- Type: TEXT/PLAIN, Size: 2328 bytes --]

//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
//
//  Copyright(c)  2004  Analogic Corporation
//
//  This program may be distributed under the GNU Public License
//  version 2, as published by the Free Software Foundation, Inc.,
//  59 Temple Place, Suite 330 Boston, MA, 02111.
//
//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
//
// Calculate the value to XOR into the shifted CRC register for the
// given input. Bits should be the "width" of the chunk being operated on.
// Poly is the polynomial to use like 0x1021.
//
// Created 12-MAY-2004 Richard B. Johnson       rjohnson@analogic.com
//
uint16_t crc16(uint16_t val, size_t bits, uint16_t poly)
{
        uint16_t xor;
                
        val <<= (16 - bits);

        while(bits--)
        {
            xor = (val & 0x8000) ? poly : 0;
            val <<= 1;
            val ^= xor;
        }
        return val;
}
//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

#define NR_BITS 8

int main(int args, char *argv[])
{
    size_t i, count;
    uint32_t poly;
    if(args < 2)
    {
        fprintf(stderr, "Usage:\n%s [poly]\n", argv[0]);
        exit(EXIT_FAILURE);
    }
    poly = 0x00;
    sscanf(argv[1], "%04x", &poly);
    if(!poly)
    {
        fprintf(stderr, "%s is not a valid parameter\n", argv[1]);
        exit(EXIT_FAILURE);
    }
    count = 1 << NR_BITS;
    printf("//\n// CRC-16 Lookup table for %u bits per iteration."\
           " Full WORD per entry\n//\n", NR_BITS );
    printf("static const uint16_t CRC%s_table[%u] = {", argv[1], count );
    for(i = 0; i < count; i++)
    {
        if(!(i % 8))
            printf("\n\t");
        printf("0x%04x", crc16(i, NR_BITS, poly));
        if(i+1 != count)
            printf(", ");
    }
    printf("\n};\n" );
    return 0;
}
//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Re: CCITT-CRC16 in kernel

[linux]

>> 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
> 
> Huh? That's the problem.
> 
> X^16 + X^12 + X^5 + X^0 = 0x1021, not 0xa001
> 
> Also,
> 
> X^16 + X^15 + X^2 + X^0 = 0x8005, not 0x8408

You're wrong in two ways:
1) You've got CRC-16 and CRC-CCITT mixed up, and
2) You've got the bit ordering backwards.  Remember, I said very clearly,
   the lsbit is the first bit, and the first bit is the highest power
   of x.  You can reverse the convention and still have a CRC, but that's
   not the way it's usually done and it's more awkward in software.

CRC-CCITT = X^16 + X^12 + X^5 + X^0 = 0x8408, and NOT 0x1021
CRC-16 =  X^16 + X^15 + X^2 + X^0 = 0xa001, and NOT 0x8005

> Attached is a program that will generate a table of polynomials
> for the conventional CRC lookup-table code. If you look at
> the table in the kernel code, offset 1, you will see that
> the polynomial is 0x1189. This corresponds to the CRC of
> the value 1. It does not correspond to either your polynomials
> or the ones documented on numerous web pages.

No, it doesn't.  The table entry at offset *128* is the CRC polynomial,
which is 0x8408, exactly as the comment just above the table says.


> I think somebody just guessed and came up with "magic" because the
> table being used isn't correct.

The table being used is 100% correct.  There is no mistake.
If you think you've found a mistake, there's something you're not
understanding.

Sorry to be so blunt, but it's true.

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

> Right, but the hardware did that. I have no control over that. I
> have to figure out if:
> 
> (1) It started with 0xffff or something else.
> (2) It was inverted after.
> (3) The result was byte-swapped.
> 
> With the "usual" CRC-16 that I used before, using the lookup-
> table that is for the 0x1021 polynomial, hardware was found
> to have inverted and byte-swapped, but started with 0xefde
> (0x1021 inverted). Trying to use the in-kernel CRC, I was
> unable to find anything that made sense.

You can get rid of the starting value and inversion by XORing together
two messages (with valid CRCs) of equal length.  The result has a valid
CRC with preset to 0 and no inversion.  You can figure that out later.

Then, the only questions are the polynomial and bit ordering.
(You can also have a screwed-up CRC byte ordering, but that's rare
except in software written by people who don't know better.  Hardware
invariably gets it right.)

As I said, the commonest case is to consider the lsbit first.
However, some implementations take the msbit of each byte first.

Here's code to do it both ways.  This is the bit-at-a-time version,
not using a table.  You can verify that the first implementation,
fed an initial crc=0, poly=0x8408, and all possible 1-byte messages,
produces the table in crc-ccitt.c.

/*
 * Expects poly encoded so 0x8000 is x^0 and 0x0001 is x^15.
 * CRC should be appended lsbyte first.
 */
uint16_t
crc_lsb_first(uint16_t crc, uint16_t poly, unsigned char const *p, size_t len)
{
	while (len--) {
		unsigned i;
		crc ^= (unsigned char)*p++;
		for (i = 0; i < 8; i++)
			crc = (crc >> 1) ^ ((crc & 1) ? poly : 0);
	}
	return crc;
}

/*
 * Expects poly encoded so 0x0001 is x^0 and 0x8000 is x^15.
 * CRC should be appended msbyte first.
 */
uint16_t
crc_msb_first(uint16_t crc, uint16_t poly, unsigned char const *p, size_t len)
{
	while (len--) {
		unsigned i;
		crc ^= (uint16_t)(unsigned char)*p++ << 8;
		for (i = 0; i < 8; i++)
			crc = (crc << 1) ^ ((crc & 0x8000) ? poly : 0);
	}
	return crc;
}

If you're trying to reverse-engineer an unknown CRC, get two valid
messages of the same length, form their XOR, and try a few different
polynomials.  (There's a way to do it more efficiently using a GCD, but
on a modern machine, it's faster to try all 32768 possible polynomials
than to write and debug the GCD code.)

After that, you can figure out the preset and final inversion, if any.
For fixed-length messages, you can merge them into a single 16-bit
constant that you can include at the beginning or the end, but if
you have variable-length messages, it matters.

Re: CCITT-CRC16 in kernel

[linux-os (Dick Johnson)]

On Thu, 11 Aug 2005 linux@horizon.com wrote:

>>> 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
>>
>> Huh? That's the problem.
>>
>> X^16 + X^12 + X^5 + X^0 = 0x1021, not 0xa001
>>
>> Also,
>>
>> X^16 + X^15 + X^2 + X^0 = 0x8005, not 0x8408
>
> You're wrong in two ways:
> 1) You've got CRC-16 and CRC-CCITT mixed up, and
> 2) You've got the bit ordering backwards.  Remember, I said very clearly,
>   the lsbit is the first bit, and the first bit is the highest power
>   of x.  You can reverse the convention and still have a CRC, but that's
>   not the way it's usually done and it's more awkward in software.
>
> CRC-CCITT = X^16 + X^12 + X^5 + X^0 = 0x8408, and NOT 0x1021
> CRC-16 =  X^16 + X^15 + X^2 + X^0 = 0xa001, and NOT 0x8005
>

Thank you very much for your time, but what you say is completely
different than anything else I have found on the net.

Do the math:

 	2^ 16 = 65536
 	2^ 12 =  4096
 	2^  5 =    32
 	2^  0 =     1
----------------------
                 69655 = 0x11021

That's by convention 0x1021 as the X^16 is thrown away. I have
no clue how you could possibly get 0x8408 out of this, nor
how the CRC of 1 could possibly lie at offset 128 in a table
of CRC polynomials. Now I read it in the header, but that
doesn't make it right.

The "RS-232C" order to which you refer simply means that the
string of "bits" needs to handled as a string of bytes, not
words or longwords, in other words, not interpreted as
words, just bytes. If this isn't correct then ZMODEM and
a few other protocols are wrong. You certainly don't
swap every BIT in a string do you? You are not claiming
that (0x01 == 0x80) and (0x02 == 0x40), etc, are you?

According to the stuff on the web, CCITT just refers
to a CRC-16 with all bits set to begin with, and the
polynominal cited above. The end result is not inverted
nor byte-swapped.

>> Attached is a program that will generate a table of polynomials
>> for the conventional CRC lookup-table code. If you look at
>> the table in the kernel code, offset 1, you will see that
>> the polynomial is 0x1189. This corresponds to the CRC of
>> the value 1. It does not correspond to either your polynomials
>> or the ones documented on numerous web pages.
>

Well the table provided worked for a couple of years. I was
just trying to use the stuff in the kernel rather than some
"roll-your-own".

> No, it doesn't.  The table entry at offset *128* is the CRC polynomial,
> which is 0x8408, exactly as the comment just above the table says.
>
>
>> I think somebody just guessed and came up with "magic" because the
>> table being used isn't correct.
>
> The table being used is 100% correct.  There is no mistake.
> If you think you've found a mistake, there's something you're not
> understanding.
>
> Sorry to be so blunt, but it's true.
>
>>> 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.
>
>> Right, but the hardware did that. I have no control over that. I
>> have to figure out if:
>>
>> (1) It started with 0xffff or something else.
>> (2) It was inverted after.
>> (3) The result was byte-swapped.
>>
>> With the "usual" CRC-16 that I used before, using the lookup-
>> table that is for the 0x1021 polynomial, hardware was found
>> to have inverted and byte-swapped, but started with 0xefde
>> (0x1021 inverted). Trying to use the in-kernel CRC, I was
>> unable to find anything that made sense.
>
> You can get rid of the starting value and inversion by XORing together
> two messages (with valid CRCs) of equal length.  The result has a valid
> CRC with preset to 0 and no inversion.  You can figure that out later.
>
> Then, the only questions are the polynomial and bit ordering.
> (You can also have a screwed-up CRC byte ordering, but that's rare
> except in software written by people who don't know better.  Hardware
> invariably gets it right.)
>
> As I said, the commonest case is to consider the lsbit first.
> However, some implementations take the msbit of each byte first.
>
> Here's code to do it both ways.  This is the bit-at-a-time version,
> not using a table.  You can verify that the first implementation,
> fed an initial crc=0, poly=0x8408, and all possible 1-byte messages,
> produces the table in crc-ccitt.c.
>
> /*
> * Expects poly encoded so 0x8000 is x^0 and 0x0001 is x^15.
> * CRC should be appended lsbyte first.
> */
> uint16_t
> crc_lsb_first(uint16_t crc, uint16_t poly, unsigned char const *p, size_t len)
> {
> 	while (len--) {
> 		unsigned i;
> 		crc ^= (unsigned char)*p++;
> 		for (i = 0; i < 8; i++)
> 			crc = (crc >> 1) ^ ((crc & 1) ? poly : 0);
> 	}
> 	return crc;
> }
>
> /*
> * Expects poly encoded so 0x0001 is x^0 and 0x8000 is x^15.
> * CRC should be appended msbyte first.
> */
> uint16_t
> crc_msb_first(uint16_t crc, uint16_t poly, unsigned char const *p, size_t len)
> {
> 	while (len--) {
> 		unsigned i;
> 		crc ^= (uint16_t)(unsigned char)*p++ << 8;
> 		for (i = 0; i < 8; i++)
> 			crc = (crc << 1) ^ ((crc & 0x8000) ? poly : 0);
> 	}
> 	return crc;
> }
>
> If you're trying to reverse-engineer an unknown CRC, get two valid
> messages of the same length, form their XOR, and try a few different
> polynomials.  (There's a way to do it more efficiently using a GCD, but
> on a modern machine, it's faster to try all 32768 possible polynomials
> than to write and debug the GCD code.)
>
> After that, you can figure out the preset and final inversion, if any.
> For fixed-length messages, you can merge them into a single 16-bit
> constant that you can include at the beginning or the end, but if
> you have variable-length messages, it matters.
>

Cheers,
Dick Johnson
Penguin : Linux version 2.6.12 on an i686 machine (5537.79 BogoMips).
Warning : 98.36% of all statistics are fiction.
.
I apologize for the following. I tried to kill it with the above dot :

****************************************************************
The information transmitted in this message is confidential and may be privileged.  Any review, retransmission, dissemination, or other use of this information by persons or entities other than the intended recipient is prohibited.  If you are not the intended recipient, please notify Analogic Corporation immediately - by replying to this message or by sending an email to DeliveryErrors@analogic.com - and destroy all copies of this information, including any attachments, without reading or disclosing them.

Thank you.

Re: CCITT-CRC16 in kernel

[Kyle Moffett]

On Aug 11, 2005, at 11:19:59, linux-os (Dick Johnson) wrote:
> On Thu, 11 Aug 2005 linux@horizon.com wrote:
>> You're wrong in two ways:
>> 1) You've got CRC-16 and CRC-CCITT mixed up, and
>> 2) You've got the bit ordering backwards.  Remember, I said very  
>> clearly,
>>   the lsbit is the first bit, and the first bit is the highest power
>>   of x.  You can reverse the convention and still have a CRC, but  
>> that's
>>   not the way it's usually done and it's more awkward in software.
>>
>> CRC-CCITT = X^16 + X^12 + X^5 + X^0 = 0x8408, and NOT 0x1021
>> CRC-16 =  X^16 + X^15 + X^2 + X^0 = 0xa001, and NOT 0x8005
>
> Thank you very much for your time, but what you say is completely
> different than anything else I have found on the net.
>
> Do the math:
>
>      2^ 16 = 65536
>      2^ 12 =  4096
>      2^  5 =    32
>      2^  0 =     1
> ----------------------
>                  69655 = 0x11021

No, it's like this: first, the 16 term is ignored, then:

     2^ ( 15 - 12 ) = 2^  3 =     8 = 0x0008
     2^ ( 15 -  5 ) = 2^ 10 =  1024 = 0x0400
     2^ ( 15 -  0 ) = 2^ 15 = 32768 = 0x8000
-----------------------------------------------
                                    = 0x8408

This has 2 things:
     1) The least-significant bit is the first bit
     2) The first bit is the _highest_ power of X.

Cheers,
Kyle Moffett

-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
GCM/CS/IT/U d- s++: a18 C++++>$ UB/L/X/*++++(+)>$ P+++(++++)>$ L++++(+ 
++) E
W++(+) N+++(++) o? K? w--- O? M++ V? PS+() PE+(-) Y+ PGP+++ t+(+++) 5  
X R?
tv-(--) b++++(++) DI+ D+ G e->++++$ h!*()>++$ r  !y?(-)
------END GEEK CODE BLOCK------

Re: CCITT-CRC16 in kernel

[linux-os (Dick Johnson)]

On Thu, 11 Aug 2005, Kyle Moffett wrote:

> On Aug 11, 2005, at 11:19:59, linux-os (Dick Johnson) wrote:
>> On Thu, 11 Aug 2005 linux@horizon.com wrote:
>>> You're wrong in two ways:
>>> 1) You've got CRC-16 and CRC-CCITT mixed up, and
>>> 2) You've got the bit ordering backwards.  Remember, I said very
>>> clearly,
>>>   the lsbit is the first bit, and the first bit is the highest power
>>>   of x.  You can reverse the convention and still have a CRC, but
>>> that's
>>>   not the way it's usually done and it's more awkward in software.
>>>
>>> CRC-CCITT = X^16 + X^12 + X^5 + X^0 = 0x8408, and NOT 0x1021
>>> CRC-16 =  X^16 + X^15 + X^2 + X^0 = 0xa001, and NOT 0x8005
>>
>> Thank you very much for your time, but what you say is completely
>> different than anything else I have found on the net.
>>
>> Do the math:
>>
>>      2^ 16 = 65536
>>      2^ 12 =  4096
>>      2^  5 =    32
>>      2^  0 =     1
>> ----------------------
>>                  69655 = 0x11021
>
> No, it's like this: first, the 16 term is ignored, then:
>
>     2^ ( 15 - 12 ) = 2^  3 =     8 = 0x0008
>     2^ ( 15 -  5 ) = 2^ 10 =  1024 = 0x0400
>     2^ ( 15 -  0 ) = 2^ 15 = 32768 = 0x8000
> -----------------------------------------------
>                                    = 0x8408
>
> This has 2 things:
>     1) The least-significant bit is the first bit
>     2) The first bit is the _highest_ power of X.
>
> Cheers,
> Kyle Moffett


Okay. Thanks. This means that hardware somehow swapped bits
before doing a CRC. I wasn't aware that this was even possible
as it would require additional storage, well I guess anything
is now possible in a FPGA.

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

Note that on the very first page, reference, is made to
the 0x1021 poly. Then there is source-code that is entirely
incompatible with anything in the kernel, but is supposed to
work (it does work on my hardware).

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.

Do you suppose it was bit-swapped to bypass a patent?


Cheers,
Dick Johnson
Penguin : Linux version 2.6.12 on an i686 machine (5537.79 BogoMips).
Warning : 98.36% of all statistics are fiction.
.
I apologize for the following. I tried to kill it with the above dot :

****************************************************************
The information transmitted in this message is confidential and may be privileged.  Any review, retransmission, dissemination, or other use of this information by persons or entities other than the intended recipient is prohibited.  If you are not the intended recipient, please notify Analogic Corporation immediately - by replying to this message or by sending an email to DeliveryErrors@analogic.com - and destroy all copies of this information, including any attachments, without reading or disclosing them.

Thank you.

Re: CCITT-CRC16 in kernel

[Kyle Moffett]

On Aug 11, 2005, at 13:08:56, linux-os (Dick Johnson) wrote:
> Okay. Thanks. This means that hardware somehow swapped bits
> before doing a CRC. I wasn't aware that this was even possible
> as it would require additional storage, well I guess anything
> is now possible in a FPGA.
>
> The "Bible" has been:
>      http://www.joegeluso.com/software/articles/ccitt.htm
>
> Note that on the very first page, reference, is made to
> the 0x1021 poly. Then there is source-code that is entirely
> incompatible with anything in the kernel, but is supposed to
> work (it does work on my hardware).
>
> 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.
>
> Do you suppose it was bit-swapped to bypass a patent?

It could be that, or it could be some kernel genius figured
out that one method is faster or better or more magical than
the other on most platforms.  Since the code works well, I
would be disinclined to tinker with it. :-D.

Cheers,
Kyle Moffett

--
Q: Why do programmers confuse Halloween and Christmas?
A: Because OCT 31 == DEC 25.

Re: CCITT-CRC16 in kernel

[linux]

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

Re: CCITT-CRC16 in kernel

[linux]

>> CRC-CCITT = X^16 + X^12 + X^5 + X^0 = 0x8408, and NOT 0x1021
>> CRC-16 =  X^16 + X^15 + X^2 + X^0 = 0xa001, and NOT 0x8005
>>
> 
> Thank you very much for your time, but what you say is completely
> different than anything else I have found on the net.
> 
> Do the math:
> 
>  	2^ 16 = 65536
>  	2^ 12 =  4096
>  	2^  5 =    32
>  	2^  0 =     1
> ----------------------
>                  69655 = 0x11021
> 
> That's by convention 0x1021 as the X^16 is thrown away. I have
> no clue how you could possibly get 0x8408 out of this, nor
> how the CRC of 1 could possibly lie at offset 128 in a table
> of CRC polynomials. Now I read it in the header, but that
> doesn't make it right.

The thing is that X is not 2.  x is a formal variable with
no defined value.

	x^0  is represented as to 0x8000
	x^5  is represented as to 0x0400
	x^12 is represented as to 0x0008
        x^16 is not represented by any bit
	TOTAL:                    0x8408

> The "RS-232C" order to which you refer simply means that the
> string of "bits" needs to handled as a string of bytes, not
> words or longwords, in other words, not interpreted as
> words, just bytes. If this isn't correct then ZMODEM and
> a few other protocols are wrong. You certainly don't
> swap every BIT in a string do you? You are not claiming
> that (0x01 == 0x80) and (0x02 == 0x40), etc, are you?

Not at all.  To repeat:

- A CRC is computed over a string of *bits*.  All of its error-corection
  properties are described in terms of *bit* patterns and *bit* positions
  and runs of adjacent *bits*.  It does not know or care about larger
  structures such a bytes.

- The CRC algorithm requires that the *first* bit it sees is the
  coefficient of the highest power of x, and the *last* bit it sees is
  the coefficient of x^0.  This is because it's basically long division.

- If you are working in software, you (the implementor) must define a
  mapping between a byte string and a bit string.  There are only two
  mappings that make any sense at all:
  1) The least-significant bit of each byte is considered "first",
     and the most-significant is considered "last".
  2) The most-significant bit of each byte is considered "first",
     and the least-significant is considered "last".

The logic of the CRC *does not care* which one you choose, but you have
to choose one.  If the bytes are to be converted to bit-serial form, it
is best to choose the form actually used for transmission to preserve the
burst error detection properies of the CRC.  Note that:

- Many people (including, apparently, you) find the second choice a bit
  easier to visualize, as bit i is the coefficient of x^i.
- The first choice is
  a) Easier to implement in software, and
  b) Matches RS-232 transmission order, and
  c) Is used by hardware such as the Z8530 SCC and MPC860 QUICC, and
  d) Is the form invariably used by experienced software implementors.

If you have some wierd piece of existing hardware, it might have chosen
either.  Just try them both and see which works.

However, if your hardware uses the opposite bit ordering within bytes,
DO NOT ATTEMPT to "fix" lib/crc-ccitt.c.  It will break all of the
existing users of the code.