`>> 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 0x8408You're wrong in two ways:1) You've got CRC-16 and CRC-CCITT mixed up, and2) 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 0x1021CRC-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 notunderstanding.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 togethertwo messages (with valid CRCs) of equal length.  The result has a validCRC 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 rareexcept in software written by people who don't know better.  Hardwareinvariably 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_tcrc_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_tcrc_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 validmessages of the same length, form their XOR, and try a few differentpolynomials.  (There's a way to do it more efficiently using a GCD, buton a modern machine, it's faster to try all 32768 possible polynomialsthan 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-bitconstant that you can include at the beginning or the end, but ifyou have variable-length messages, it matters.-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/`