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