3
$\begingroup$

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-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 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;
};
$\endgroup$
  • $\begingroup$ Is your question about a problem in your code? That makes it more on-topic for Stack Overflow. Either way, it would seem helpful to go in armed with a working definition of CRC in your question, and an explanation of what the ^= is doing in the first place. If you don’t know that, ask that question first. (I’m not saying you don’t know; I’m trying to avoid assuming too much. I had a hard time following the question, so I’m really saying it could use some clarity, as it sounds like part of the problem is the code...) $\endgroup$ – D. Ben Knoble Dec 30 '19 at 4:37
  • $\begingroup$ Code works fine. This is a highly specific method of implementing CRC-16 with a specific polynomial, optimized for speed, using bitwise tricks. CRC is a type of checksum or "cyclic redundancy code". I am trying to understand the logic behind this algorithm (not CRC in general), and adapt it for a different polynomial. I'll try to clarify and add comments. I posted at CS thinking there'd be people more versed in studying algorithms here. $\endgroup$ – bryc Dec 30 '19 at 5:28
  • $\begingroup$ [is it] possible to use this same approach [using] other polynomials I take the approach to be partial evaluation, which is valid generally. There are different approaches to implementing the core operation, from using a lookup table over implementing it in a general purpose processor (fixed polynomial, e.g. CRC32 using 0x11EDC6F41, or implementing "carryless multiplication") to having a "compiler" configure "field programmable" hardware. $\endgroup$ – greybeard Jan 2 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.