bugAVR C Runtime Library - Bugs: bug #37901, CRC-CCITT calculation incorrect

 
 

You are not allowed to post comments on this tracker with your current authentication level.

bug #37901: CRC-CCITT calculation incorrect

Submitter:  mojo <mojo>
Submitted:  Tue 11 Dec 2012 01:42:22 PM UTC
   
 
Category:  Library Severity:  3 - Normal
Priority:  5 - Normal Item Group:  libc code
Status:  Invalid Assigned to:  joerg_wunsch
Percent Complete:  0% Open/Closed:  Closed
Release:  1.8.0 Fixed Release:  None

Jump to the original submission

Mon 21 Oct 2013 04:03:19 PM UTC, comment #7: 

Closing bug, as it is marked as Invalid and no updated patch in 10 months.

Eric Weddington <arcanum>
Group administrator
Tue 11 Dec 2012 05:14:52 PM UTC, comment #6: 

Well, we cannot impose a 1 KiB lookup table on everyone using this
header file.  Also, a usable patch needs documentation.  No problem
if you don't have the time to do it right now.


Regarding the reference to CCITT, there's a simple proof: the X.25
document (which all this eventually refers to) is publically
available, and it contains examples for their CRC calculation in
appendix I.  One of them is:

10000000     11001110    11000001 11101010
Address = B  UA(F = 1)   Frame check sequence

Remember that this is a communications standard, so the first bit
transferred is the low-order one.  Consequently, the message contains
two octets, 0x01, followed by 0x73.  If you pass this through
avr-libc's _crc_ccitt_update() function (with an initial CRC value of
0xffff), you get a CRC of 0xa87c, or 0x7c 0xa8 in octet-order.  If you
turn this into the X.25 bit-order, it's 00111110 00010101.  For odd
reasons, X.25 states they transfer their FCS in a negated way, which
yields the 11000001 11101010 you see in their example.

Another example:

11000000     11111100        11011010 00110111
Address = A  SABM(P = 1)     Frame check sequence

0x03         0x3F

=> CRC 0x13a4 = 00100101 11001000, inverted 11011010 00110111

Joerg Wunsch <joerg_wunsch>
Group administrator
Tue 11 Dec 2012 04:52:58 PM UTC, comment #5: 

Okay, apologies for the roughness of this patch, but I have a full time job so I'm afraid someone else will have to batter it into shape.

CRC32 is rather slow without a 1k LUT, but could be optimized a bit by using a nibble based LUT (only 16 entries, 64 bytes).



// CRC32 LUT
const PROGMEM uint32_t crc32_table[256] = {
        0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F,
        0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
        0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2,
        0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
        0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,
        0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
        0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C,
        0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
        0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423,
        0xCFBA9599, 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
        0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190, 0x01DB7106,
        0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
        0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D,
        0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
        0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,
        0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
        0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7,
        0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
        0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA,
        0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
        0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81,
        0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
        0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84,
        0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
        0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,
        0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
        0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E,
        0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
        0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55,
        0x316E8EEF, 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
        0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28,
        0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
        0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F,
        0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
        0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
        0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
        0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69,
        0x616BFFD3, 0x166CCF45, 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
        0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC,
        0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
        0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693,
        0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
        0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
};


/**************************************************************************************************
** CRC32 update, inlined for speed
**
** Implements IEEE 802.3. Remember to invert the result when finished updating. Start
** with 0xFFFFFFFF.
*/
uint32_t inline crc32_update(uint32_t crc, uint8_t data)
{
        crc = ((crc>>8) & 0x00FFFFFF) ^ pgm_read_dword(&crc32_table[ (crc ^ data) & 0xFF ]);
        return(crc);
}


#define CRC32_POLY (0x0080001BUL) /* Polynomial for use with Xmega devices */

/**************************************************************************************************
** Atmel XMEGA NVM compatible CRC.
**
** Start with 0x00000000. Operates on a word at a time like the NVM controller.
*/
uint32_t inline crc_atmel_update(uint32_t crc, uint16_t data)
{
        uint32_t a, b;

        a  = crc << 1;
        a &= 0x00FFFFFEUL; /* Always act as 24-bit variable */

        b  = crc & (1UL << 23);

        if(b > 0)
        b = 0x00FFFFFFUL;

        crc = (a ^ (uint32_t)data) ^ (b & CRC32_POLY);
        crc = crc & 0x00FFFFFFUL;

        return(crc);
}


mojo <mojo>
Tue 11 Dec 2012 04:35:31 PM UTC, comment #4: 

I disagree. The way you are looking at it is bitwise, but programmers these days are probably looking at it bytewise. The USART takes care of bit order, all the programmer gets is their byte in the DATA register.

That is exactly what I expected, so on one device I just fed the bytes in to _crc_ccitt_update() and on the other one I spooled them into the XMEGA's CRC.DATAIN. The results did not match, despite both claiming to be an implementation of CRC-CCITT.

The XMEGA implementation matches all the publicly available code I found on Google with a few quick searches. Many big and popular libraries include such code. Naturally instead of re-inventing the wheel I use one of those implementations in my desktop app and as a fix for the _crc_ccitt_update() issue.

As I said, even if we don't rename anything it should at least be made clear in the documentation. Personally I would suggest implementing three new functions:

_crc_ccitt_avr_update()
_crc_ieee32_avr_update()
_crc_atmel_flash_avr_update()

I'm sure someone can think of better names. At least then people would be less confused and compatibility with the AVR CRC generator hardware would be explicitly mentioned.

I have code available for the ieee32 and atmel_flash CRCs, BTW. I will prepare a patch.

mojo <mojo>
Tue 11 Dec 2012 03:05:29 PM UTC, comment #3: 


> The standard CCITT CRC should produce an endian
> and bit-order independent result that is compatible
> with other implementations.


It's simply impossible to implement a bit-order independent CRC.  The
existing _crc_ccitt_update() is known to work with any kind of
communication protocol that transfers the low-order bit first (not
only IrDA but many others; probably any communication protocol except
USB works this way).

If anyone wants the opposite-bit-order CRC function that is compatible
with the Xmega CRC, they ought to use _crc_xmodem_update().

Yes, renaming anything is sheer impossible, as it would break
backwards compatibility for all those people who use the current
functions.

I reopen the bug report so you can append a patch that you think would
make the documentation clearer on this.  Perhaps mention that
_crc_xmodem_update() is the one that is compatible with the Xmega CRC?
Insert a paragraph describing the bit-order problem?

Joerg Wunsch <joerg_wunsch>
Group administrator
Tue 11 Dec 2012 02:28:57 PM UTC, comment #2: 

Okay, but in that case I think that needs to be made clear.

The standard CCITT CRC should produce an endian and bit-order independent result that is compatible with other implementations. I understand that it is designed to be compatible with the IRDA standard, but it appears to be a mistake on their part or at least the result of confusion over which version people are usually referring to by that name.

As I pointed out, the biggest issue for me is that it is incompatible with the XMEGA CRC module's implementation. Renaming the functions is probably out of the question now, but the documentation should at least be amended to make it clear which one you might want to use. There are lots of threads on AVR Freaks from confused programmers wondering why it doesn't work.

mojo <mojo>
Tue 11 Dec 2012 02:01:50 PM UTC, comment #1: 

The function you describe is provided by
_crc_xmodem_update() in <util/crc16.h>.  It uses
the same polynomial as _crc_ccitt_update()
(x^16 + x^12 + x^5 + 1), but the opposite bit order.

_crc_ccitt_update() is known to work well together with
typical communication protocols that transmit the low-order
bit first, e.g. IEEE 802.15.4.

Joerg Wunsch <joerg_wunsch>
Group administrator
Tue 11 Dec 2012 01:42:22 PM UTC, original submission:  

Using _crc_ccitt_update() gives the wrong result. You can verify the result by comparing it with known good implementations, e.g. the XMEGA CRC module, the Boost libraries (http://www.boost.org/doc/libs/1_41_0/libs/crc/index.html), or any number of online calculatored (e.g. http://www.zorc.breitbandkatze.de/crc.html or http://www.lammertbies.nl/comm/info/crc-calculation.html).

I wrote the following code that works, and allows communication between an XMEGA with CRC module and one without when CRC functions are needed:

uint16_t inline crc16_update(uint16_t crc, uint8_t data)
{
crc = (uint8_t)(crc >> 8) | (crc << 8);
crc ^= data;
crc ^= (uint8_t)(crc & 0xFF) >> 4;
crc ^= (crc << 8) << 4;
crc ^= ((crc & 0xFF) << 4) << 1;

return(crc);
}

For reference the correct CRC-CCITT value of "HELLO" (5 bytes ASCII) is 0x49D6. The _crc_ccitt_update() function gives 0x258A.

mojo <mojo>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by arcanum (Posted a comment)
  • -email is unavailable- added by joerg_wunsch (Posted a comment)
  • -email is unavailable- added by mojo (Submitted the item)
  • -email is unavailable- added by mojo
  •  

    Follow 6 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2013-10-21 arcanum Open/ClosedOpen Closed
    2012-12-11 joerg_wunsch Open/ClosedClosed Open
    2012-12-11 joerg_wunsch StatusNone Invalid
        Assigned toNone joerg_wunsch
        Open/ClosedOpen Closed
    2012-12-11 mojo Carbon-Copy- Added mojo

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code