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

 
 

bug #37901: CRC-CCITT calculation incorrect

Submitted by:  mojo <mojo>
Submitted on:  Tue 11 Dec 2012 01:42:22 PM UTC  
 
Category: LibrarySeverity: 3 - Normal
Priority: 5 - NormalItem Group: libc code
Status: InvalidPercent Complete: 0%
Assigned to: Joerg Wunsch <joerg_wunsch>Open/Closed: Closed
Release: 1.8.0Fixed Release: None

Add a New Comment (Rich MarkupRich Markup):
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission 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>
Project 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>
Project AdministratorIn charge of this item.
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).

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>
Project AdministratorIn charge of this item.
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>
Project AdministratorIn charge of this item.
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.)

Attach File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 6 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon 21 Oct 2013 04:03:19 PM UTCarcanumOpen/ClosedOpen=>Closed
    Tue 11 Dec 2012 03:05:29 PM UTCjoerg_wunschOpen/ClosedClosed=>Open
    Tue 11 Dec 2012 02:01:50 PM UTCjoerg_wunschStatusNone=>Invalid
      Assigned toNone=>joerg_wunsch
      Open/ClosedOpen=>Closed
    Tue 11 Dec 2012 01:42:22 PM UTCmojoCarbon-Copy-=>Added mojo

    Back to the top


    Powered by Savane 3.1-cleanup