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

**posted on**

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

segment

flash_CRC = 0xFFFF;

for ( ; size > 0; size-- )

{

if ( segment

{

uint16

for (uint16_t count = 16; count > 0; count-- )

{

uint16

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 totalsegment

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

- » 4G embedded router
- — Newest thread in » Embedded Programming

- » DSI Screen
- — The site's Newest Thread. Posted in » Raspberry Pi Group