# Replacing 0x1021 polynomial with 0x8005 in this CRC-16 code

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; }; ``