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

Question

I found a highly optimized CRC-16 implementation originally intended for microcontrollers. It is noticeably faster than the traditional method, but is hard-coded to model the specific unreflected polynomial 0x1021, or x^12 + x^5 + x^0.

I was then able to determine, when slightly modified, the reflected variant of this polynomial can be modelled 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. Though I'm unsure of the specifics of how it works. I've also found examples of CRC-32 that use this approach, but require many more operations.

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 it's highly cryptic. This is a essentially an edge case of CRC, amounting to clever usage of bitwise optimizations.

Here is the code for the unreflected CRC-16 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 work. In fact, in that code, the (t << 12) cannot be changed, though other terms can, if they're less than (t << 8). So this only covers polynomials 4096 through 4607.

As I said before, I was able to correctly model the reflected version of 0x1021 as well using a similar 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;
};

Answer 1

Yes, it's possible, but there is no magic formula. Each polynomial requires a unique set of operations, and the number of operations required can vary highly. A solid grasp of CRC math is also necessary to craft these solutions. Unfortunately I only have a cursory understanding, so my explanation may be limited.

The best way to illustrate this is to compare them. Here's the code for 0x1021:

 t = (c >> 8) ^ d;
 t ^= t >> 4;
 c = (c << 8) ^ (t << 12) ^ (t << 5) ^ t;

And here is the equivalent for 0x8005:

 t = (c >> 8) ^ d;
 z = t;
 t ^= t >> 4;
 t ^= t >> 2;
 t ^= t >> 1;
 t &= 1;
 t |= z << 1;
 c = (c << 8) ^ (t << 15) ^ (t << 1) ^ t;

As you can see, the code required to implement different polynomials, can be highly variable. The second implementation requires more operations and intermediates.

The 0x1021 polynomial appears to require very few operations, and so it's a good choice for microcontrollers which are slower and have little RAM. It may be exceptionally unique in this regard.