CRC calculation

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

Reply to
Jack
Loading thread data ...

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

Dimiter

------------------------------------------------------ Dimiter Popoff, TGI

formatting link

------------------------------------------------------

formatting link

Reply to
Dimiter_Popoff

ption.

ash.

oops on every bits of the words):

find any that have a 16bit word as input, every version that I've found on the web has 8bit input.

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.

Reply to
Jack

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.

Reply to
David Brown

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
Reply to
Tauno Voipio

ruption.

flash.

loops on every bits of the words):

't find any that have a 16bit word as input, every version that I've found on the web has 8bit input.

at a time. I need something that calculate 2bytes at a time.

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):

formatting link

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

Reply to
Jack

orruption.

e flash.

it loops on every bits of the words):

an't find any that have a 16bit word as input, every version that I've foun d on the web has 8bit input.

e at a time. I need something that calculate 2bytes at a time.

algorithm that I found in the web until now.

one (check the link for good/bad definition).

ok, at the end I found out. Got the code form here:

formatting link

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

Reply to
Jack

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 
 Click to see the full signature
Reply to
Tim Wescott

Exactly that was I tried to explain.

--

-TV
Reply to
Tauno Voipio

to:

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

Reply to
Jack

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

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.

Reply to
David Brown

critto:

ut

is a factor 6 speedup.

mizing things.

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

Thanks Bye Jack

Reply to
Jack

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.