How to do CRC16 right?

Log in or register to post comments
Go To Last Post
15 posts / 0 new
Author
Message
ygoe
ygoe's picture
Level: Rookie
Joined: Thu. Dec 26, 2019
Posts: 49 View posts
Location: erlangen.de
#1
Posted by ygoe: Mon. Dec 30, 2019 - 04:31 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

So there's already tons of information (and code samples and opinions) about CRC16 available. But there's no data on how each of these bits is compatible with anything else. What I've done now doesn't work and I can't find an elegant solution.

 

I have two devices and applications. One is an ATtiny1614 that's programmed in C++ with Atmel Studio. There's the util/crc16.h header and the _crc16_update function. I understand how to call it. It gets a number of bytes including two final bytes of 0. I write the result in these final bytes (as number, so little endianess applies here). This message is sent via RS-485 to a PC.

 

The other is the PC that's programmed in C# with Visual Studio. There's sample code available to compute the CRC16 of some bytes. I do the same here. The same procedure is used, setting a uint16 field and getting the memory bytes for it, so here, too, little endianess applies. To verify the checksum, I should just compute the value for all received bytes and it should be 0.

 

But it's not. It isn't even 0 when I add the checksum in C# and immediately let it verify its own checksum. Both sides, C and C#, consider the other side's CRC16 wrong.

 

So what's going on here? Is my assumption correct about how to use CRC? Are the two algorithms compatible with each other? Is the verification result always 0? Should I use my own code to compute a CRC and port it to the other language, to guarantee that I'm using the same algorithm? Can I still call that "CRC16" should I decide to publish my communication protocol and allow third-party implementations?

 

How do you use CRC16 in your applications? This is the first time I need a solution that's compatible across platforms. The rest of the message, a C struct of a few uint16's, can be sent and received on both ends correctly. It's just the checksum that causes trouble.

Tags:

AVR Microcontrollers, megaAVR and tinyAVR
Top
Bronze Markawneil
awneil's picture
Level: 10k+ Postman
Joined: Fri. Jul 1, 2005
Posts: 25563 View posts
Location: Basingstoke, Hampshire, UK
Posted by awneil: Mon. Dec 30, 2019 - 04:34 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Note that "CRC16" simply tells you that the CRC has 16 bits - it does not specify the polynomial used, initialisation values, etc.

 

You need to be specific as to which particular 16-bit CRC you are talking about!

 

Sounds like your 2 devices are using two different 16-bit CRCs ...

 

 

Top Tips:

  1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
  2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
  3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
  4. Difference between a crystal, and a crystal oscillator: https://www.avrfreaks.net/comment...
  5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
  6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
Top
ygoe
ygoe's picture
Level: Rookie
Joined: Thu. Dec 26, 2019
Posts: 49 View posts
Location: erlangen.de
Posted by ygoe: Mon. Dec 30, 2019 - 04:50 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

AVR function (see documentation): Polynomial 0xa001, Initial value: 0xffff

C# function (extracted from code): Polynomial 0xa001, Initial value: unknown

 

What other parameters do I need to accurately define the algorithm?

Top
ki0bk
ki0bk's picture
Level: 10k+ Postman
Joined: Mon. Sep 8, 2014
Posts: 10611 View posts
Location: Over the rainbow
Posted by ki0bk: Mon. Dec 30, 2019 - 05:10 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

I would copy the source on one end and use it on the other.

Jim

 

 

FF = PI > S.E.T

 

Top
N.Winterbottom
N.Winterbottom's picture
Level: Raving Lunatic
Joined: Tue. Oct 1, 2002
Posts: 2823 View posts
Location: Redbourn, Herts, UK
Posted by N.Winterbottom: Mon. Dec 30, 2019 - 05:20 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

ygoe wrote:
Is the verification result always 0?

No!

You have used the words CRC16 and checksum interchangably whereas computationally they are not interchangeable.

 

Sender should generate the CRC16 from the payload bytes and append the value to the data packet.

Receiver should perform exactly the same operation on the payload but compare the local CRC16 with the transmitted CRC16.

If all is well, they should be equal.

 

Top
ygoe
ygoe's picture
Level: Rookie
Joined: Thu. Dec 26, 2019
Posts: 49 View posts
Location: erlangen.de
Posted by ygoe: Mon. Dec 30, 2019 - 05:21 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The AVR function is defined as optimised assembler code. I can't port that to anywhere. And when I port the C# code to C, it's probably much slower and requires more memory.

 

So my question remains: How is everybody else handling CRC when communicating between an MCU and a PC? And what are these CRC implementations worth if they are not interoperable with anything else?

Top
ki0bk
ki0bk's picture
Level: 10k+ Postman
Joined: Mon. Sep 8, 2014
Posts: 10611 View posts
Location: Over the rainbow
Posted by ki0bk: Mon. Dec 30, 2019 - 05:22 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Here is code I have used successfully:

///////////////////////////////////////////////////////////////////////////////
//  FUNCTION:    u16ComputeCRC                                               //
//  DESCRIPTION: This routine takes a pointer to a data array, the length of //
//               the array, and a CRC seed and returns the calculated CRC for//
//               that data. CRC seed is 0xFFFF 							     //
//  GLOBALS      none                                                        //
//  INPUTS:      u16CRC - seed, pData - pointer to array, u8Length - number  //
//               bytes to process.                                           //
//  OUTPUTS:     u16CRC - Calculated Result.                                 //
//  AUTHOR:      unknown                                     //
//  HISTORY:     02/06/2014 - Initial - EJK                                  //
//               xx/xx/xxxx - Modification desc... - initials                //
///////////////////////////////////////////////////////////////////////////////
uint16_t u16ComputeCRC( uint16_t u16CRC, uint8_t *pData, uint8_t u8Length )
{
  uint8_t u8Bit, i;
  uint16_t u16Odd;

  for (i = 0; i < u8Length; i++)
  {
    u16CRC ^= ((uint16_t) * pData << 8);
    for (u8Bit = 0; u8Bit < 8; u8Bit++)
    {
      u16Odd = u16CRC & 0x8000;
      u16CRC <<= 1;
      if (u16Odd == 0x8000)
      {
        u16CRC ^=0x1021;  //C13 + C6 + C1
      }
    }
    pData++;
  }
  return (u16CRC);
}

Jim

 

 

FF = PI > S.E.T

 

Last Edited: Mon. Dec 30, 2019 - 05:27 PM
Top
ygoe
ygoe's picture
Level: Rookie
Joined: Thu. Dec 26, 2019
Posts: 49 View posts
Location: erlangen.de
Posted by ygoe: Mon. Dec 30, 2019 - 05:23 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

N.Winterbottom wrote:

ygoe wrote:
Is the verification result always 0?

No!

 

Interesting. This is the first time I read that this is not the way to verify it. So I'll explore the other (more logical and less magical) approach.

Top
Bronze Markawneil
awneil's picture
Level: 10k+ Postman
Joined: Fri. Jul 1, 2005
Posts: 25563 View posts
Location: Basingstoke, Hampshire, UK
Posted by awneil: Mon. Dec 30, 2019 - 06:05 PM (Reply to #5)
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Some CRCs are designed so that performing the CRC calculation over the payload plus the CRC will give a result of zero.

 

Again, that's why it's important to know which particular CRC you are using.

Top Tips:

  1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
  2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
  3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
  4. Difference between a crystal, and a crystal oscillator: https://www.avrfreaks.net/comment...
  5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
  6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
Top
apcountryman
apcountryman's picture
Level: Hangaround
Joined: Sun. Sep 11, 2016
Posts: 152 View posts
Location: WA, USA
Posted by apcountryman: Mon. Dec 30, 2019 - 06:13 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

If you want to understand how CRCs work, how to implement them, implementation optimizations, and the variations that can be encountered (polynomial width, polynomial value, initial value, input reflection, output reflection, and output XOR) you should read A Painless Guide to CRC Error Detection Algorithms. The catalogue of parametrised CRC algorithms is also very useful as it documents (with supporting references) the parameters used by many (all?) commonly used CRCs, and provides implementation check values (used with the test payload documented in A Painless Guide to CRC Error Detection Algorithms).

build-avr-gcc: avr-gcc build script

toolchain-avr-gcc: CMake toolchain for cross compiling for the AVR family of microcontrollers

avr-libcpp: C++ standard library partial implementation (C++17 only) for use with avr-gcc/avr-libc

picolibrary: C++ microcontroller driver/utility library targeted for use with resource constrained microcontrollers

picolibrary-microchip-megaavr: picolibrary HIL for megaAVR microcontrollers

picolibrary-microchip-megaavr0: picolibrary HIL for megaAVR 0-series microcontrollers

Top
ygoe
ygoe's picture
Level: Rookie
Joined: Thu. Dec 26, 2019
Posts: 49 View posts
Location: erlangen.de
Posted by ygoe: Mon. Dec 30, 2019 - 07:57 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

So, I changed my code to not rely on a verification result of 0. Instead, creating and verifying the CRC on both sides is now the same, ignoring the CRC bytes altogether. The sender sends its result and the receiver compares it with its own computation. Now it works fine, the two implementations seem to be compatible.

 

apcountryman wrote:

If you want to understand how CRCs work, (…) read A Painless Guide to CRC Error Detection Algorithms. The catalogue of parametrised CRC algorithms is also very useful as it documents (…) the parameters used by many (all?) commonly used CRCs (…).

 

Thank you for these links. Unfortunately my main goal was using a (as common as possible) CRC successfully, not to study and research their theoretical background and redo all the work. So the first document wasn't too helpful to me. And it's funny how the second one doesn't even list the only two variants I've ever heard about until today ("IBM" 0xa001 and "CCITT" 0x8408), yet these are the ones most commonly referred to out there (in the Googleverse visible to me).

Top
Kartman
Kartman's picture
Level: 10k+ Postman
Joined: Thu. Dec 30, 2004
Posts: 24978 View posts
Location: Melbourne,Australia
Posted by Kartman: Mon. Dec 30, 2019 - 09:31 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Note: there’s two main techniques for calculating crcs- ilooped and table. Looped is smaller in code size where table requires a 512byte array. The table technique in C will be faster than looped in asm.

Top
apcountryman
apcountryman's picture
Level: Hangaround
Joined: Sun. Sep 11, 2016
Posts: 152 View posts
Location: WA, USA
Posted by apcountryman: Mon. Dec 30, 2019 - 09:38 PM (Reply to #11)
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The second link does list both the IBM and CCITT CRCs. It uses the "normal" polynomial notation (IBM 0x8005 and CCITT 0x1021) while you are using the "reversed" notation. See this.

 

If you are trying to use generalized CRC libraries it is important to understand the contents of the first link so that you will be able to properly configure the library. If you are implementing it yourself, it is even more important to understand it.

build-avr-gcc: avr-gcc build script

toolchain-avr-gcc: CMake toolchain for cross compiling for the AVR family of microcontrollers

avr-libcpp: C++ standard library partial implementation (C++17 only) for use with avr-gcc/avr-libc

picolibrary: C++ microcontroller driver/utility library targeted for use with resource constrained microcontrollers

picolibrary-microchip-megaavr: picolibrary HIL for megaAVR microcontrollers

picolibrary-microchip-megaavr0: picolibrary HIL for megaAVR 0-series microcontrollers

Top
N.Winterbottom
N.Winterbottom's picture
Level: Raving Lunatic
Joined: Tue. Oct 1, 2002
Posts: 2823 View posts
Location: Redbourn, Herts, UK
Posted by N.Winterbottom: Mon. Dec 30, 2019 - 09:51 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

awneil wrote:
Some CRCs are designed so that performing the CRC calculation over the payload plus the CRC will give a result of zero.

Interesting; I never knew that. Indeed, the A Painless Guide to CRC Error Detection Algorithms. is anything but painless but does include this gem:

At the other end, the receiver can do one of two things:

   a. Separate the message and checksum. Calculate the checksum for
      the message (after appending W zeros) and compare the two
      checksums.

   b. Checksum the whole lot (without appending zeros) and see if it
      comes out as zero!

These two options are equivalent. However, in the next section, we
will be assuming option b because it is marginally mathematically
cleaner.

I'll have to play with this Method (b) sometime.

 

It seems OP was actually trying Method (b) but could not get it to work.

 

Top
ygoe
ygoe's picture
Level: Rookie
Joined: Thu. Dec 26, 2019
Posts: 49 View posts
Location: erlangen.de
Posted by ygoe: Mon. Dec 30, 2019 - 10:36 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yes, I've read this article before (German only) and it assumed the 0 remainder thing as natural, as if there was no other way. It doesn't apply to the "standard" "IBM" CRC16, though. This has caused quite some confusion in the beginning. Now I've reverted to the SHA way (like for example with SHA-1 or similar, recompute on data only, then compare). Mathematically cleaner or not – I need something that works.

Top