I have some highly optimized code for a CRC-16 implementation. It focuses on speed rather than flexibility, and as a result, it is hard-coded to model the specific unreflected polynomial `0x1021`

, or x^12 + x^5 + x^0.

Using the same general approach (with slight modification), I was able to represent the reflected variant of this polynomial as well, which is `0x8408`

, or x^15 + x^10 + x^3. This is achieved by changing bit shift direction as well as the polynomial shifts.

Now, I am wondering if it is possible to use this same approach to use other polynomials, specifically `0x8005`

, or x^15 + x^2 +x^0. To do so I need to understand what this code is doing, but I haven’t quite figured it out yet. This is a essentially an edge case of CRC, amounting to clever usage of bitwise optimizations.

Here is the code for the unreflected CRC using polynomial `0x1021`

:

`// in JavaScript, but easily translates to C etc. function crc16(data, crc = 0, xorout = 0) { for(let i = 0, t; i < data.length; i++, crc &= 0xFFFF) { t = (crc >> 8) ^ data[i]; // shift high crc byte over t = (t ^ t >> 4); crc <<= 8; // shift left 1 byte crc ^= (t << 12) ^ (t << 5) ^ (t); } return crc ^ xorout; } `

This can model CRC-16 variants such as XMODEM or “CCITT-FALSE” depending on the initial value of `crc`

and `xorout`

.

The `crc`

variable stores the current CRC value, while the `t`

variable is temporary storage for intermediate calculations. The expression `(t << 12) ^ (t << 5) ^ (t)`

appears to model the actual polynomial, which gets XOR’d into the CRC for every byte of input.

For `0x8005`

, also an unreflected polynomial, one might assume a drop in replacement such as `(t << 15) ^ (t << 2) ^ (t)`

would do the trick, but it does not appear to give the correct output.

As I said before, I was able to correctly model the reflected version of `0x1021`

as well using this construction. Here is the code for that:

`function crc16b(data, crc = 0, xorout = 0) { for(let i = 0, t; i < data.length; i++, crc &= 0xFFFF) { t = (crc) ^ data[i]; t = (t ^ t << 4) & 255; // &255 is to remove overflow crc >>= 8; // shift right 1 byte crc ^= (t << 8) ^ (t >> 4) ^ (t << 3); } return crc ^ xorout; } `

This code correctly models the reflected variants such as CCITT-TRUE, ISO/IEC 14443 among others.

The code is slightly different to account for it being reflected, but the structure is essentially the same. However the expression that represents the polynomial is a bit strange: `(t << 8) ^ (t >> 4) ^ (t << 3)`

. It doesn’t seem to line up with the expected polynomial representation x^15 + x^10 + x^3.

The polynomial I want to translate to this structure is `0x8005`

(or its reflected version, `0xA001`

). It has both reflected and unreflected variants. I am referencing the different CRC-16 variants and vectors from here: http://reveng.sourceforge.net/crc-catalogue/16.htm

This page uses a test string “123456789”, to check implementation correctness, so I typically check it as an array:

`crc16([49, 50, 51, 52, 53, 54, 55, 56, 57]) `

And these are the expected values for two CRC-16 variants I am targeting (which use `0x8005`

polynomial or `0xA001`

reversed):

`For init=0x0000 and xorout=0x0000 ---------------------------------- CRC-16/UMTS (unreflected) = 0xfee8 CRC-16/ARC (reflected) = 0xbb3d `

What I want to do is modify the above code to implement the polynomials `0x8005`

and `0xA001`

, but I’m having trouble figuring out how it even works in the first place. I figured `0x8005`

would be a good fit because of the few number of bits which are used.

Any ideas on how this is actually implementing CRC-16, or what might be required to translate other polynomials?

A classic resource on CRC is A Painless Guide to CRC Error Detection Algorithms

Also if it helps, here are traditional implementations of CRC-16 (but are less efficient):

These implementations allow any polynomial to be supplied as input. Here is the unreflected version:

`// Targets XMODEM var crc16 = function(data) { var POLY = 0x1021, INIT = 0, XOROUT = 0; for(var crc = INIT, i = 0; i < data.length; i++) { crc = crc ^ (data[i] << 8); for(var j = 0; j < 8; j++) { crc = crc & 0x8000 ? crc << 1 ^ POLY : crc << 1; } } return (crc ^ XOROUT) & 0xFFFF; }; `

And the reflected equivalent (notice the change of shift direction…):

`// Targets KERMIT var crc16b = function(data) { var POLY = 0x8408, INIT = 0, XOROUT = 0; for(var crc = INIT, i = 0; i < data.length; i++) { crc = crc ^ data[i]; for(var j = 0; j < 8; j++) { crc = crc & 1 ? crc >> 1 ^ POLY : crc >> 1; } } return (crc ^ XOROUT) & 0xFFFF; }; `