Do you have a question? Post it now! No Registration Necessary
March 22, 2017, 10:59 am

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

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

<snip>

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


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


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:
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 Wed, 22 Mar 2017 03:59:53 -0700, Jack wrote:

<< code snipped >>

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.

<< code snipped >>

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
Tim Wescott
Wescott Design Services
We've slightly trimmed the long signature. Click to see the full one.

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

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.

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.
Site Timeline
- » Cloud? IoT? How to start
- — Next thread in » Embedded Programming
-
- » MSP430g2553 and Matlab
- — Previous thread in » Embedded Programming
-
- » How to avoid a task not executed in a real-time OS?
- — Newest thread in » Embedded Programming
-
- » 18650 battery holder
- — The site's Newest Thread. Posted in » Hobby Electronics Basics
-