Andrew Cooke: C[omp]ute

16bit CRC Algorithms

From: andrew cooke <andrew@...>

Date: Wed, 31 Jul 2013 16:24:58 -0400

If you need to implement a 16bit CRC algorithm, this is an excellent
reference:

  http://www.barrgroup.com/Embedded-Systems/How-To/CRC-Calculation-C-Code

If you have some data and are trying to work out what CRC was used, this
excellent tool is a huge help:

  http://www.lammertbies.nl/comm/info/crc-calculation.html

The only missing puzzle is that no-one explains the difference between
CRC-CCITT (0xffff) and XModem.  It turns out that XModem has an initial
remainder of zero.  So you could say that XModem is CRC-CCITT (0x0000).

That is the ONLY difference.  I have working code with test vectors.  God
knows what crack some people were smoking when they wrote that they are
different beasts...

What a painful, wasted afternoon.
Andrew

CRC16 Code

From: andrew cooke <andrew@...>

Date: Sat, 3 Aug 2013 15:13:39 -0400

Here's the C code.  As I noted above it's basically from
http://www.barrgroup.com/Embedded-Systems/How-To/CRC-Calculation-C-Code but it
includes explicit values, validated via
http://www.lammertbies.nl/comm/info/crc-calculation.html


uint16_t straight_16(uint16_t value) {
    return value;
}

uint16_t reverse_16(uint16_t value) {
    uint16_t reversed = 0;
    for (int i = 0; i < 16; ++i) {
        reversed <<= 1;
        reversed |= value & 0x1;
        value >>= 1;
    }
    return reversed;
}

uint8_t straight_8(uint8_t value) {
    return value;
}

uint8_t reverse_8(uint8_t value) {
    uint8_t reversed = 0;
    for (int i = 0; i < 8; ++i) {
        reversed <<= 1;
        reversed |= value & 0x1;
        value >>= 1;
    }
    return reversed;
}

uint16_t crc16(uint8_t const *message, int nBytes,
        bit_order_8 data_order, bit_order_16 remainder_order,
        uint16_t remainder, uint16_t polynomial) {
    for (int byte = 0; byte < nBytes; ++byte) {
        remainder ^= (data_order(message[byte]) << 8);
        for (uint8_t bit = 8; bit > 0; --bit) {
            if (remainder & 0x8000) {
                remainder = (remainder << 1) ^ polynomial;
            } else {
                remainder = (remainder << 1);
            }
        }
    }
    return remainder_order(remainder);
}


uint16_t crc16ccitt(uint8_t const *message, int nBytes) {
    return crc16(message, nBytes, straight_8, straight_16, 0xffff, 0x1021);
}

uint16_t crc16ccitt_xmodem(uint8_t const *message, int nBytes) {
    return crc16(message, nBytes, straight_8, straight_16, 0x0000, 0x1021);
}

uint16_t crc16ccitt_kermit(uint8_t const *message, int nBytes) {
    uint16_t swap = crc16(message, nBytes, reverse_8, reverse_16, 0x0000, 0x1021);
    return swap << 8 | swap >> 8;
}

uint16_t crc16ccitt_1d0f(uint8_t const *message, int nBytes) {
    return crc16(message, nBytes, straight_8, straight_16, 0x1d0f, 0x1021);
}

uint16_t crc16ibm(uint8_t const *message, int nBytes) {
    return crc16(message, nBytes, reverse_8, reverse_16, 0x0000, 0x8005);
}


I've modified the code slightly to remove various private things and simplify
slightly, so it's just possible I broke something - please check before
using.  Also, remmeber that this is not as efficient as using a lookup-table
per byte (but you can generate the table from the info above).

Andrew

Missed a bit

From: andrew cooke <andrew@...>

Date: Sat, 3 Aug 2013 15:37:20 -0400

You also need this...

typedef uint16_t bit_order_16(uint16_t value);
typedef uint8_t bit_order_8(uint8_t value);

(which was hiding in a header file).

Andrew

thanks for CRC16-CCITT XMODEM

From: "Sanchez, Denis" <Denis.Sanchez@...>

Date: Thu, 5 Dec 2013 15:39:36 +0000

Hello,

Just a little mail to say thank you for your post on your blog.
I finally find the way to calculate this CRC and convert into excel macro.
I was hard to find algo for XMODEM.

Denis

Update on CRCs

From: andrew cooke <andrew@...>

Date: Sat, 5 Apr 2014 10:43:20 -0300

The last month or so I've learned a lot more about CRCs (as part of a longer
term project to understand finite fields).

Here are two references for CRCs that are better / more authoritative than
anything I could produce:

  http://www.zlib.net/crc_v3.txt
  http://reveng.sourceforge.net/crc-catalogue/

The first link above clarifies why there are two implementations for
algorithms that reverse the input bytes: one is slow but obviously correct
(just reverse each byte); the other is faster but looks very odd at first
glance (reverse the rest of the world).

According to the second link above, what I have called crc16ccitt is actually
CCITT-FALSE ("An algorithm commonly misidentified as CRC-CCITT").  See
http://reveng.sourceforge.net/crc-catalogue/16.htm for full details.

Finally, I have implemented fast versions (with tables and, where appropriate,
"reverse the world" implementations) for ALL the algorithms described in the
catalogue.  The code is written in Julia and is available at 
https://github.com/andrewcooke/CRC.jl

I hope to extend that code at some point so that it can be used as a
command-line tool for calculating CRCs (so you don't need to use julia).  But
even if you don't know julia it should be fairly easy to use in its current
state (email me at andrew@... if this is important to you and I can
give instructions).

Andrew

Comment on this post

C[omp]ute

Personal Projects

Last 100 entries

16bit CRC Algorithms

CRC16 Code

Missed a bit

thanks for CRC16-CCITT XMODEM

Update on CRCs