CRC-16 result doesn't match results from two other implementations

Log in or register to post comments
Go To Last Post
12 posts / 0 new
Author
Message
ejwipp
ejwipp's picture
Level: New Member
Joined: Wed. Aug 30, 2006
Posts: 13 View posts
#1
Posted by ejwipp: Tue. Apr 7, 2015 - 06:46 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Years ago I found this assembly implementation of CRC-16 and have been using it for eeprom memory verification:

//=============================================================================
// Copyright Atmel Corporation 2003. All Rights Reserved.
//
// File:			crc.asm
// Compiler:		IAR Atmel AVR Assembler
// Output Size:
// Created:			20-Feb-2003	JP (Atmel Finland)
// Modified:	
//
// Support Mail:	avr@atmel.com
//
// Description:		CRC calculation routine
//
// Other Info:
//=============================================================================

//=============================================================================
// Polynome used in CRC calculations

#define	CRC_POLYNOME  0x8005    //0x1021


//=============================================================================

PUBLIC	CRC

RSEG	CODE

//=============================================================================
// CRC calculation routine

CRC:
	ldi		r20, 0x08
	ldi		r21, LOW(CRC_POLYNOME)
	ldi		r22, HIGH(CRC_POLYNOME)

CRC_Loop:
	; Rotate left. If MSb is 1 -> divide with Generator-polynome.
	lsl		r18
	rol		r16
	rol		r17
	brcc	CRC_SkipEor

	eor		r16, r21
	eor		r17, r22

CRC_SkipEor:
	dec		r20
	brne	CRC_Loop
	ret

//=============================================================================

END

The header file contains this:

extern CPU_INT16U CRC(CPU_INT16U crc, CPU_INT08U ch);

The CRC is used like this:

CPU_INT08U TestBuffer[10u] = {0x31u,0x32u,0x33u,0x34u,0x35u,0x36u,0x37u,0x38u,0x39u};    // test sequence of "123456789"

static CPU_INT16U crc_test(void)
{
    CPU_INT16U crc = 0u;
    
    for (CPU_INT16U ii=0u; ii < 9u; ii++)
    {
        crc = CRC(crc, TestBuffer[ii]);
    }
    
    return crc;
}

In the above example, the computed result is 0xD52E.  However, my other two implementations (one in c# and one on a Renesas RX62N) yield a result of 0xBB3D.  This is the expected result according to Michael Barr's article - near the end there is a table of expected results for an input of "123456789".  Can anyone see an error in the above assembly?  Or provide me with known working assembly for a CRC16 implementation?

Tags:

AVR Microcontrollers, megaAVR and tinyAVR
Last Edited: Tue. Apr 7, 2015 - 08:02 PM
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: Tue. Apr 7, 2015 - 07:55 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Note that "CRC-16" really only tells you the number of bits - it doesn't tell you what polynomial is used, nor what initial conditions.

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
ejwipp
ejwipp's picture
Level: New Member
Joined: Wed. Aug 30, 2006
Posts: 13 View posts
Posted by ejwipp: Tue. Apr 7, 2015 - 08:03 PM (Reply to #2)
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The polynomial is 0x8005 and the initial value is 0.

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: Tue. Apr 7, 2015 - 08:45 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

That's what the code you posted says - but what about the other implementations?

 

In addition, a silicon implementation may also have variations in the way it handles the bits/bytes/words...

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
ejwipp
ejwipp's picture
Level: New Member
Joined: Wed. Aug 30, 2006
Posts: 13 View posts
Posted by ejwipp: Tue. Apr 7, 2015 - 09:00 PM (Reply to #3)
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The other implementations use the same polynomial and initial value.

 

After comparing the assembly to the c-source on the Barr Group's website, I see that the assembly is completely missing the following part of the CRC algorithm:

remainder ^= (REFLECT_DATA(message[byte]) << (WIDTH - 8));

For reference, the complete function from Barr is:

crc
crcSlow(unsigned char const message[], int nBytes)
{
    crc            remainder = INITIAL_REMAINDER;
	int            byte;
	unsigned char  bit;


    /*
     * Perform modulo-2 division, a byte at a time.
     */
    for (byte = 0; byte < nBytes; ++byte)
    {
        /*
         * Bring the next byte into the remainder.
         */
        remainder ^= (REFLECT_DATA(message[byte]) << (WIDTH - 8));

        /*
         * Perform modulo-2 division, a bit at a time.
         */
        for (bit = 8; bit > 0; --bit)
        {
            /*
             * Try to divide the current data bit.
             */
            if (remainder & TOPBIT)
            {
                remainder = (remainder << 1) ^ POLYNOMIAL;
            }
            else
            {
                remainder = (remainder << 1);
            }
        }
    }

    /*
     * The final remainder is the CRC result.
     */
    return (REFLECT_REMAINDER(remainder) ^ FINAL_XOR_VALUE);

}   /* crcSlow() */

 

I guess I'll just use this c-implementation...hopefully the optimizer will shink it down.

 

Top
Bronze Markdavid.prentice
david.prentice's picture
Level: 10k+ Postman
Joined: Sat. Feb 12, 2005
Posts: 31925 View posts
Location: Wormshill, England
Posted by david.prentice: Tue. Apr 7, 2015 - 09:39 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

There have always been several incompatible "CRC-16" implementations.    I can think of at least 3 in widespread use.   e.g. by ZMODEM, ZIP, ...

 

If you are just doing an internal CRC on a block of your own data,   it does not matter which one you use.

 

However,   if you are trying to verify some foreign data,   you must use the same method at each end.

I have only seen one CRC-32 in common use.

 

David.

Top
Bronze Markbobgardner
bobgardner's picture
Level: 10k+ Postman
Joined: Wed. Sep 4, 2002
Posts: 26609 View posts
Location: Orlando Florida
Posted by bobgardner: Wed. Apr 8, 2015 - 01:19 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

For some reason I think it should start at all 11111s. Worth a try?

Imagecraft compiler user

Top
CmdrZin
CmdrZin's picture
Level: Wannabe
Joined: Wed. Apr 8, 2015
Posts: 78 View posts
Location: Los Angeles, CA
Posted by CmdrZin: Wed. Apr 8, 2015 - 05:01 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The easiest why to debug this is to capture intermediate products at the top of the loops and compare the ASM with the C version.

Follow the bit patterns for clues.

"If you find yourself in an even battle, you didn't plan very well."
https://www.gameactive.org
https://github.com/CmdrZin

Top
Gold Markclawson
clawson's picture
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 105140 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
Posted by clawson: Wed. Apr 8, 2015 - 08:58 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The following explains how CRCs using the same bit width, polynomial and start value can still be different:

 

http://en.wikipedia.org/wiki/Cyc...

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: Wed. Apr 8, 2015 - 10:01 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Wikipedia wrote:
... sixteen conflicting definitions of "CRC-16" ...

 

As I said earlier, "CRC-16" really tells you nothing beyond the number of bits!

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
Bronze Markdavid.prentice
david.prentice's picture
Level: 10k+ Postman
Joined: Sat. Feb 12, 2005
Posts: 31925 View posts
Location: Wormshill, England
Posted by david.prentice: Wed. Apr 8, 2015 - 10:18 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

In practical terms,   you use the same implementation as the foreign software.    e.g. if you are reading a ZIP file,   you use source code from a proven ZIP program.

 

Yes,   the source code is probably in C.    You probably want to use ASM.    (or some other language)

So you need to thoroughly test your 'hand-written' translation.

 

As can be seen from the Wikipedia article,    there are many versions.    Speed or effectiveness may be important for an internal application.    If you are talking to the outside world,  you need to use the same CRC as the foreign application.

 

David.

Top
Gold Markclawson
clawson's picture
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 105140 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
Posted by clawson: Wed. Apr 8, 2015 - 10:31 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I once implemented the "other side" of the CRC16 that is in Srecord (srec_cat) but, even knowing the polynomial, it took me ages to determine exactly how they were "massaging" the operation to get the result they did!

Top