CRC-CCITT Implementation

Question

I am using the following function to generate a CRC sum and it doesn't appear to be returning the same checksum when compared to online CRC-CCITT calculators.

This function specifically uses the XMODEM CRC generation with a 0x8408 polynomial with an initial fcs of 0xFFFF.

uint16_t crc16(uint8_t byte, uint16_t fcs)
{
    uint8_t bit;

    for(bit=0; bit<8; bit++)
    {
        fcs ^= (byte & 0x01);
        fcs = (fcs & 0x01) ? (fcs >> 1) ^ 0x8408 : (fcs >> 1);
        byte = byte >> 1;
    }
    return fcs;
}

Am I doing something wrong? If I send 0xFF, or 0x00 I do not get the same checksum as I do on http://depa.usst.edu.cn/chenjq/www2/SDesign/JavaScript/CRCcalculation.htm

printf("%04X\n", crc16(0x31, 0xFFFF)); //returns 2F8D

Kassandrakassaraba

One notable difference is that you are using the "xmodem", not the "ccitt" flavour of the constant - which may explain why it's different. – Girlfriend

The .cn link doesn't work. – Battlement

depa.usst.edu.cn link is archived at web.archive.org/web/20170602055344/http://depa.usst.edu.cn:80/… – Blacken

Answer 1

I have read your questions and I also had the similar problem like you.

I have solved this issue for calculating CRC-CCITT in XMODEM. here I am attaching the sample program to calculate CRC-CCITT.

I have tried the data with the online converter and this program. Please use this if you wish.

unsigned short crc16(char *ptr, int count)
{
   int  crc;
   char i;
   crc = 0;
   while (--count >= 0)
   {
      crc = crc ^ (int) *ptr++ << 8;
      i = 8;
      do
      {
         if (crc & 0x8000)
            crc = crc << 1 ^ 0x1021;
         else
            crc = crc << 1;
      } while(--i);
   }
   return (crc);
}

CRC should be defined as unsigned short since the crc16 function returns an unsigned short. CRC is defined as an int which on most systems is 4 bytes.

Abstracted

This appears to be a correct answer, but the question was posted back in June, 2013. – Tysontyumen

Yes, but this one can help for the new people if they have similar doubt like this.. – Abstracted

helped me! Thank you for the explicit followup @Abstracted ! explicit types would be preferred (e.g. uint16_t) – Estival

I used this as the base to create my crc16_3 (changed initialisation to 0xFFFF, used uintX_t types, changed count to unsigned) which results in the values called Bad_CRC in srecord.sourceforge.net/crc16-ccitt.html -- Then I created my crc16_4 which exactly matches the Good_CRC of that page (which needed the augment handling, and using ch and v variables to XOR into the low bit of the crc variable after the shift/xor step). – Blacken

I think @ecm's crc16_4 implementation is referred to as CRC-16/AUG-CCITT and CRC-16/SPI-FUJITSU in this overview: reveng.sourceforge.io/crc-catalogue/16.htm – Gaylegayleen

Answer 2

Take a look at Greg Cook's excellent catalog of CRCs. There is a variant often falsely identified as the CCITT CRC, which it isn't. That is what your code, with the 0xFFFF initialization, appears to be computing, though reflected. The Kermit CRC is the actual CCITT CRC. To get the CCITT CRC, you should start with zero, not 0xFFFF. The XMODEM CRC is different still, like the Kermit CRC, but unreflected (so bits go in the top, and you exclusive-or with 0x1021).

KERMIT
width=16 poly=0x1021 init=0x0000 refin=true refout=true xorout=0x0000 check=0x2189 name="KERMIT"

XMODEM
width=16 poly=0x1021 init=0x0000 refin=false refout=false xorout=0x0000 check=0x31c3 name="XMODEM"

CRC-16/CCITT-FALSE
width=16 poly=0x1021 init=0xffff refin=false refout=false xorout=0x0000 check=0x29b1 name="CRC-16/CCITT-FALSE"

Battlement

0x15CA is returned for 0x31 with a start value of 0x0000 and using poly=0x1021 in the code above. The .cn calculator returns 0x2672 as the checksum. Where does the discrepancy come from? – Kassandrakassaraba

You can't use 0x1021 in the code above. You need to also change the code to feed in the bits from the top. You can't reverse the polynomial (or in this case unreverse it) without also reversing the bit ordering. – Battlement

How do you know what CRC you need? What are you communicating with? – Battlement

@Kassandrakassaraba - what code above? 0x2672 is the correct XMODEM crc for a single data byte of 0x31. I used ancient Intel 8080 CP/M XMODEM code for crc calculation to verify the algorithm. sarvankumar_t's answer appears to have the correct code. – Tysontyumen

Answer 3

static const unsigned short CRC_CCITT_TABLE[256] =
{
    0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7,
    0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF,
    0x1231, 0x0210, 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6,
    0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C, 0xF3FF, 0xE3DE,
    0x2462, 0x3443, 0x0420, 0x1401, 0x64E6, 0x74C7, 0x44A4, 0x5485,
    0xA56A, 0xB54B, 0x8528, 0x9509, 0xE5EE, 0xF5CF, 0xC5AC, 0xD58D,
    0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6, 0x5695, 0x46B4,
    0xB75B, 0xA77A, 0x9719, 0x8738, 0xF7DF, 0xE7FE, 0xD79D, 0xC7BC,
    0x48C4, 0x58E5, 0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823,
    0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948, 0x9969, 0xA90A, 0xB92B,
    0x5AF5, 0x4AD4, 0x7AB7, 0x6A96, 0x1A71, 0x0A50, 0x3A33, 0x2A12,
    0xDBFD, 0xCBDC, 0xFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1A,
    0x6CA6, 0x7C87, 0x4CE4, 0x5CC5, 0x2C22, 0x3C03, 0x0C60, 0x1C41,
    0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD, 0xAD2A, 0xBD0B, 0x8D68, 0x9D49,
    0x7E97, 0x6EB6, 0x5ED5, 0x4EF4, 0x3E13, 0x2E32, 0x1E51, 0x0E70,
    0xFF9F, 0xEFBE, 0xDFDD, 0xCFFC, 0xBF1B, 0xAF3A, 0x9F59, 0x8F78,
    0x9188, 0x81A9, 0xB1CA, 0xA1EB, 0xD10C, 0xC12D, 0xF14E, 0xE16F,
    0x1080, 0x00A1, 0x30C2, 0x20E3, 0x5004, 0x4025, 0x7046, 0x6067,
    0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C, 0xE37F, 0xF35E,
    0x02B1, 0x1290, 0x22F3, 0x32D2, 0x4235, 0x5214, 0x6277, 0x7256,
    0xB5EA, 0xA5CB, 0x95A8, 0x8589, 0xF56E, 0xE54F, 0xD52C, 0xC50D,
    0x34E2, 0x24C3, 0x14A0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
    0xA7DB, 0xB7FA, 0x8799, 0x97B8, 0xE75F, 0xF77E, 0xC71D, 0xD73C,
    0x26D3, 0x36F2, 0x0691, 0x16B0, 0x6657, 0x7676, 0x4615, 0x5634,
    0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9, 0xB98A, 0xA9AB,
    0x5844, 0x4865, 0x7806, 0x6827, 0x18C0, 0x08E1, 0x3882, 0x28A3,
    0xCB7D, 0xDB5C, 0xEB3F, 0xFB1E, 0x8BF9, 0x9BD8, 0xABBB, 0xBB9A,
    0x4A75, 0x5A54, 0x6A37, 0x7A16, 0x0AF1, 0x1AD0, 0x2AB3, 0x3A92,
    0xFD2E, 0xED0F, 0xDD6C, 0xCD4D, 0xBDAA, 0xAD8B, 0x9DE8, 0x8DC9,
    0x7C26, 0x6C07, 0x5C64, 0x4C45, 0x3CA2, 0x2C83, 0x1CE0, 0x0CC1,
    0xEF1F, 0xFF3E, 0xCF5D, 0xDF7C, 0xAF9B, 0xBFBA, 0x8FD9, 0x9FF8,
    0x6E17, 0x7E36, 0x4E55, 0x5E74, 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0
};

I use the following code to calculate a CRC-CCITT (0xFFFF):

unsigned short Calculate_CRC_CCITT(const unsigned char* buffer, int size)
{
    unsigned short tmp;
    unsigned short crc = 0xffff;

    for (int i=0; i < size ; i++)
    {
        tmp = (crc >> 8) ^ buffer[i];
        crc = (crc << 8) ^ CRC_CCITT_TABLE[tmp];
    }

    return crc;
}

Oceanography

without the table is just half the fun! – Badajoz

That is not a correct CCITT implementation and will fail on the test strings. please see srecord.sourceforge.net/crc16-ccitt.html – Torchwood

@Torchwood sorry but I just tried it with lammertbies.nl/comm/info/crc-calculation and it works. – Oceanography

Answer 4

As stated by Mark Adler above, the nomenclature of the different CRC algorithms is rather confusing and not always handled correctly. His reference to Greg Cook's excellent catalog of CRCs is probably your best bet for a somewhat concise nomenclature.

For a convenient implementation of the respective algorithms please refere to an example implementation in C++ below [16-bit CRCs only].

#include <climits>
#include <cstdint>
    
static_assert(8 == CHAR_BIT);

namespace Helpers
{

uint8_t bitSwap(uint8_t const value)
{
    uint8_t workValue = value;
    {
        uint8_t constexpr mask = 0xf0;
        workValue = ((workValue & mask) >> 4) | ((workValue & ~mask) << 4);
    }
    {
        uint8_t constexpr mask = 0xcc;
        workValue = ((workValue & mask) >> 2) | ((workValue & ~mask) << 2);
    }
    {
        uint8_t constexpr mask = 0xaa;
        workValue = ((workValue & mask) >> 1) | ((workValue & ~mask) << 1);
    }
    return workValue;
}

uint16_t bitSwap(uint16_t const value)
{
    uint16_t workValue = value;
    {
        uint16_t constexpr mask = 0xff00;
        workValue = ((workValue & mask) >> 8) | ((workValue & ~mask) << 8);
    }
    {
        uint16_t constexpr mask = 0xf0f0;
        workValue = ((workValue & mask) >> 4) | ((workValue & ~mask) << 4);
    }
    {
        uint16_t constexpr mask = 0xcccc;
        workValue = ((workValue & mask) >> 2) | ((workValue & ~mask) << 2);
    }
    {
        uint16_t constexpr mask = 0xaaaa;
        workValue = ((workValue & mask) >> 1) | ((workValue & ~mask) << 1);
    }
    return workValue;
}

} // namespace Helpers


namespace Internal_
{

template <typename T, bool reflect>
class BitSwap
{
public:
    static T of(T const value);

private:
    BitSwap() = delete;
};


template <typename T>
class BitSwap<T, false>
{
public:
    static T of(T const value)
    {
        return value;
    }

private:
    BitSwap() = delete;
};


template <typename T>
class BitSwap<T, true>
{
public:
    static T of(T const value)
    {
        return Helpers::bitSwap(value);
    }

private:
    BitSwap() = delete;
};

} // namespace Internal_



template <uint16_t polynomial,
         uint16_t initialCrc,
         bool reflectIn,
         bool reflectOut,
         uint16_t xorOut>
class Crc16
{
public:

    Crc16() noexcept
        : crc_(initialCrc)
    {
    }

    void process(uint8_t const * const data, size_t const octectCount) noexcept
    {
        for (uint8_t const * datumPointer = data; (data + octectCount) > datumPointer; ++datumPointer)
        {
            // Include the new data in the CRC calculation by virtually appending it to accumulated
            // and already processed data. Now make it represented in the CRC calculation by the
            // XOR operation [i.e. simply pretend, this datum has always been here and is thus reflected
            // in the remainder of the previous calculation already].
            // Do so with the upper byte, as to conform to the notion of "appending 16 bits of 0 for the
            // calculation" [8 bits shifted here, 8 bits shifted in below loop] - so as to perform the
            // XOR until the last bit of data and really only retain the remainder. Which is what the CRC
            // is supposed to be.
            crc_ ^= (static_cast<uint16_t>(
                         Internal_::BitSwap<uint8_t, reflectIn>::of(*datumPointer)
                         ) << 8);

            for (int bitIndex = 0; bitIndex < CHAR_BIT; ++bitIndex)
            {
                // Perform XOR only if the MSb [Most Significant bit] is set [as the CRC is "[...] the
                // remainder of a polynomial division, modulo two.", Jack Crenshaw's "Implementing CRCs"
                // article in the January 1992 issue of Embedded Systems Programming].
                bool const applyPolynomial = (0 != (0x8000 & crc_));

                // In the polynomial the MSb is not encoded and instead assumed to always be 1 [otherwise
                // the 16-order polynomial would have required 17-bits, which would exceed the value type].
                // So:
                //  - If we are going to apply the polynomial, we already know that 0 == (1 ^ 1) and thus
                //    we disregard this bit.
                //  - If we are not going to apply the polynomial, the bit was 0 and is simply discarded
                //    as well.
                // So in any case, simply shift out the MSb.
                crc_ <<= 1;

                if (applyPolynomial)
                {
                    crc_ ^= polynomial;
                }
            }
        }
    }

    uint16_t get() const noexcept
    {
        return (xorOut ^ Internal_::BitSwap<uint16_t, reflectOut>::of(crc_));
    }

private:

    uint16_t crc_;

};


// https://reveng.sourceforge.io/crc-catalogue/16.htm#crc.cat.crc-16-xmodem
// CRC-16/XMODEM
// width=16 poly=0x1021 init=0x0000 refin=false refout=false xorout=0x0000 check=0x31c3 residue=0x0000 name="CRC-16/XMODEM"
// Class: attested
// Alias: CRC-16/ACORN, CRC-16/LTE, CRC-16/V-41-MSB, XMODEM, ZMODEM
// The MSB-first form of the V.41 algorithm. For the LSB-first form see CRC-16/KERMIT. CRC presented high byte first.
// Used in the MultiMediaCard interface. In XMODEM and Acorn MOS the message bits are processed out of transmission order,
// compromising the guarantees on burst error detection.
// ITU-T Recommendation V.41 (November 1988)

typedef Crc16<0x1021, 0x0000, false, false, 0x0000> Crc16Xmodem;


// https://reveng.sourceforge.io/crc-catalogue/16.htm#crc.cat.crc-16-kermit
// CRC-16/KERMIT
// width=16 poly=0x1021 init=0x0000 refin=true refout=true xorout=0x0000 check=0x2189 residue=0x0000 name="CRC-16/KERMIT"
// Class: attested
// Alias: CRC-16/BLUETOOTH, CRC-16/CCITT, CRC-16/CCITT-TRUE, CRC-16/V-41-LSB, CRC-CCITT, KERMIT
// Used in Bluetooth error detection. Init=0x0000 is used in the Inquiry Response substate.
// Press et al. identify the CCITT algorithm with the one implemented in Kermit. V.41 is endianness-agnostic, referring
// only to bit sequences, but the CRC appears reflected when used with LSB-first modems. Ironically, the unreflected form
// is used in CRC-16/XMODEM.

typedef Crc16<0x1021, 0x0000, true, true, 0x0000> Crc16Kermit;


// https://reveng.sourceforge.io/crc-catalogue/16.htm#crc.cat.crc-16-ibm-3740
// CRC-16/IBM-3740
// width=16 poly=0x1021 init=0xffff refin=false refout=false xorout=0x0000 check=0x29b1 residue=0x0000 name="CRC-16/IBM-3740"
// Class: attested
// Alias: CRC-16/AUTOSAR, CRC-16/CCITT-FALSE
// An algorithm commonly misidentified as CRC-CCITT. CRC-CCITT customarily refers to the LSB-first form of the algorithm in
// ITU-T Recommendation V.41 (see CRC-16/KERMIT); its MSB-first counterpart is CRC-16/XMODEM.
// AUTOSAR (24 November 2022), AUTOSAR Classic Platform release R22-11, Specification of CRC Routines

typedef Crc16<0x1021, 0xffff, false, false, 0x0000> Crc16Ibm3740;


// https://reveng.sourceforge.io/crc-catalogue/16.htm#crc.cat.crc-16-spi-fujitsu
// CRC-16/SPI-FUJITSU
// width=16 poly=0x1021 init=0x1d0f refin=false refout=false xorout=0x0000 check=0xe5cc residue=0x0000 name="CRC-16/SPI-FUJITSU"
// Class: attested
// Alias: CRC-16/AUG-CCITT
// Init value is equivalent to an augment of 0xFFFF prepended to the message.
// Fujitsu Semiconductor (10 October 2007), FlexRay ASSP MB88121B User's Manual (courtesy of the Internet Archive)

typedef Crc16<0x1021, 0x1d0f, false, false, 0x0000> Crc16SpiFujitsu;

For the Xmodem CRC it will return 0x2672, as you expectet [see AlphabetaPhi's comment from Jun 19, 2013 at 19:05]:

uint8_t const data = 0x31;

Crc16Xmodem crc;

crc.process(&data, 1);

uint16_t const crcValue = crc.get(); // 0x2672

Ginetteginevra

Answer 5

For Java

Install: https://mvnrepository.com/artifact/com.github.snksoft/crc/1.0.2

Long returnValue = CRC.calculateCRC(Parameters.CCITT, "yourStringValue");

Breach

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Sanitarian

While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review – Galatia