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$
3
  • $\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$ Dec 30, 2019 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, 2019 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, 2020 at 7:52

1 Answer 1

0
$\begingroup$

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.

It is only by chance, that the 0x1021 polynomial happens to require very few operations, and so it's a good choice for microcontrollers which are slower and have little RAM.

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 registers.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.