CRC calculation

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Hello,
I'm working on a 16bit microcontroller. I need to check for flash corruption.
Flash is adressed at words (16bits).
The linker calculate a CRC_CCITT and put the result in a cell of the flash.

The algorithm that the chip manufacurer gave us is painfully slow (it loops on every bits of the words):


size = FLASH_END_ADDR - FLASH_START_ADDR; //32kB in total
segment_p = FLASH_START_ADDR;
flash_CRC = 0xFFFF;

for ( ; size > 0; size-- )
{
  if ( segment_p != (uint16 *) FLASH_CRC_ADDR )
  {
     uint16_t data = *segment_p;

     for (uint16_t count = 16; count > 0; count-- )
     {
    uint16_t xor_flag = (flash_CRC & 0x8000);  

    flash_CRC <<= 1;

    if(data & 0x8000U)
    {
       flash_CRC++;
    }
    data <<= 1;

    if(xor_flag != 0)
    {
       flash_CRC ^= POLY;
    }
     }
   }
   segment_p++;
}

I'm aware of version that use tables of smart bit shifting, but I can't find any that have a 16bit word as input, every version that I've found on the web has 8bit input.
Do you know a better/faster version of the same algorithm?

Thanks Bye Jack

Re: CRC calculation
On 22.3.2017 ?. 12:59, Jack wrote:
Quoted text here. Click to load it

Look at rfc1331, it has the lookup table values and algorithms
etc.

Dimiter

------------------------------------------------------
Dimiter Popoff, TGI             http://www.tgi-sci.com
------------------------------------------------------
http://www.flickr.com/photos/didi_tgi/


Re: CRC calculation

Quoted text here. Click to load it
ption.
ash.
oops on every bits of the words):
Quoted text here. Click to load it
 find any that have a 16bit word as input, every version that I've found on
 the web has 8bit input.
Quoted text here. Click to load it

thanks, but data are given in bytes (ie the algorithm calculate 1 byte at a
 time. I need something that calculate 2bytes at a time.

Re: CRC calculation
On 22/03/17 13:02, Jack wrote:

Quoted text here. Click to load it
<snip>
Quoted text here. Click to load it

No, you don't - you want to run it a byte at a time.  For each 16-bit
word, first pass in the low byte of the word, then the high byte of the
word - or vice versa (different CRC algorithms vary here - just try it
and see what gives the right answer).  When working with bytes, your
tables is 256 entries of 16-bit, or 512 bytes.  If you try to use tables
with 16 bits at a time, you need 65536 16-bit entries - 128KB of table.
 Depending on your microcontroller and how its memory works, it might
not even be faster.

Re: CRC calculation
On 22.3.17 14:02, Jack wrote:

Quoted text here. Click to load it


You do not win any with a two-byte table, but the table size will
expand out of reach for most microcontrollers (from 512 bytes to
131072 bytes).

--  

-TV


Re: CRC calculation

tto:
Quoted text here. Click to load it

Quoted text here. Click to load it
ruption.
flash.
 loops on every bits of the words):
Quoted text here. Click to load it
't find any that have a 16bit word as input, every version that I've found  
on the web has 8bit input.
Quoted text here. Click to load it
at a time. I need something that calculate 2bytes at a time.
Quoted text here. Click to load it

I don't want a 2 byte table.
I want an algorithm that process a word (16bit) and not a byte, as every al
gorithm that I found in the web until now.

The algorithm that I have to use is this (the "good" one):
http://srecord.sourceforge.net/crc16-ccitt.html

but the algorithm that uses tables/shifts,ecc. seems to follow the "bad" on
e (check the link for good/bad definition).

So splitting the 16bit word in 2 doesn't work....

Thank Bye Jack

Re: CRC calculation


ritto:
Quoted text here. Click to load it

Quoted text here. Click to load it
orruption.
e flash.
it loops on every bits of the words):
Quoted text here. Click to load it
an't find any that have a 16bit word as input, every version that I've foun
d on the web has 8bit input.
Quoted text here. Click to load it
e at a time. I need something that calculate 2bytes at a time.
Quoted text here. Click to load it
algorithm that I found in the web until now.
Quoted text here. Click to load it
one (check the link for good/bad definition).
Quoted text here. Click to load it

ok, at the end I found out.
Got the code form here:
http://srecord.sourceforge.net/

same link as the "good/bad" algorithm.

The source code contains also the code for the algorithm with the table.
I just have to split the 16bit words in two.

Thanks Bye Jack

Re: CRC calculation
On 22.3.17 18:33, Jack wrote:


Quoted text here. Click to load it

Quoted text here. Click to load it

Exactly that was I tried to explain.

--  

-TV


Re: CRC calculation
On Wed, 22 Mar 2017 03:59:53 -0700, Jack wrote:

Quoted text here. Click to load it

<< code snipped >>

Quoted text here. Click to load it

First, the speedup from doing it byte-by-byte will be enormous (I'm  
pretty sure it's more than a factor of 8 speedup on most processors, but  
I'm open to being told I'm nuts).

Second, doing it N bits at a time requires two tables that are 2^N  
entries long.  So with 16-bit numbers you're talking 2 bytes * 2 tables *  
2^16 entries per table = 2^18 bytes, vs. 1024 for the tables for 8 bits.

Third, if you want, you can work this out yourself.  The CRC calculation  
is linear on a binary field, meaning that superposition works.  So the  
result of an N-bit calculation is the sum of two results: the result of  
putting N zeros into the calculation given your starting state, and the  
result of putting your N bits of data into the calculation given a  
starting state of zero.

So, make up two tables, one for each of those above results.  Look up the  
result in each one given the state and the input, and add the results  
together modulo 2 (meaning, do an exclusive-or on them bit-by-bit).  
That's your new state.

--  

Tim Wescott
Wescott Design Services
We've slightly trimmed the long signature. Click to see the full one.
Re: CRC calculation

to:

Quoted text here. Click to load it
  
Quoted text here. Click to load it

doing it byte by byte (splitting the word in 2 bytes) with table there is a
 factor 6 speedup.
Could be better I think, but the compiler doesn't do a good job in optimizi
ng things.

Thanks Bye Jack

Re: CRC calculation
On 23/03/17 09:26, Jack wrote:

Quoted text here. Click to load it

The speedup can often be more than a factor of 8 - you are not nuts.
(Well, not in this case...)

Quoted text here. Click to load it

If you need to speed it up more, then you'll have to post details of the
chip, details of the compiler, compiler options, and of course the
actual source code.  I can't promise that anyone can make it faster,
especially if it is an unusual processor, but it can be fun to try.



Re: CRC calculation

:
Quoted text here. Click to load it

critto:
Quoted text here. Click to load it
ut  
Quoted text here. Click to load it
is a factor 6 speedup.
Quoted text here. Click to load it
mizing things.

thanks for the offer, for the moment I'm happy with this.
If the case, I'll ask again.

Thanks Bye Jack

Site Timeline