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
CRC calculation
Started by ●March 22, 2017
Reply by ●March 22, 20172017-03-22
On 22.3.2017 г. 12:59, Jack wrote:> 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 >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/
Reply by ●March 22, 20172017-03-22
Il giorno mercoledì 22 marzo 2017 12:29:13 UTC+1, dp ha scritto:> On 22.3.2017 г. 12:59, Jack wrote: > > 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 > > > > Look at rfc1331, it has the lookup table values and algorithms > etc.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 by ●March 22, 20172017-03-22
On 22/03/17 13:02, Jack wrote:> Il giorno mercoledì 22 marzo 2017 12:29:13 UTC+1, dp ha scritto: >> On 22.3.2017 г. 12:59, Jack wrote: >>> 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): >>><snip>>>> >>> 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 >>> >> >> Look at rfc1331, it has the lookup table values and algorithms >> etc. > > 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. >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 by ●March 22, 20172017-03-22
On 22.3.17 14:02, Jack wrote:> Il giorno mercoledì 22 marzo 2017 12:29:13 UTC+1, dp ha scritto: >> On 22.3.2017 г. 12:59, Jack wrote: >>> 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 >>> >> >> Look at rfc1331, it has the lookup table values and algorithms >> etc. > > 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.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 by ●March 22, 20172017-03-22
Il giorno mercoledì 22 marzo 2017 14:56:03 UTC+1, Tauno Voipio ha scritto:> On 22.3.17 14:02, Jack wrote: > > Il giorno mercoledì 22 marzo 2017 12:29:13 UTC+1, dp ha scritto: > >> On 22.3.2017 г. 12:59, Jack wrote: > >>> 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 > >>> > >> > >> Look at rfc1331, it has the lookup table values and algorithms > >> etc. > > > > 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. > > > 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).I don't want a 2 byte table. I want an algorithm that process a word (16bit) and not a byte, as every algorithm 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" one (check the link for good/bad definition). So splitting the 16bit word in 2 doesn't work.... Thank Bye Jack
Reply by ●March 22, 20172017-03-22
Il giorno mercoledì 22 marzo 2017 16:04:07 UTC+1, Jack ha scritto:> Il giorno mercoledì 22 marzo 2017 14:56:03 UTC+1, Tauno Voipio ha scritto: > > On 22.3.17 14:02, Jack wrote: > > > Il giorno mercoledì 22 marzo 2017 12:29:13 UTC+1, dp ha scritto: > > >> On 22.3.2017 г. 12:59, Jack wrote: > > >>> 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 > > >>> > > >> > > >> Look at rfc1331, it has the lookup table values and algorithms > > >> etc. > > > > > > 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. > > > > > > 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). > > I don't want a 2 byte table. > I want an algorithm that process a word (16bit) and not a byte, as every algorithm 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" one (check the link for good/bad definition). > > So splitting the 16bit word in 2 doesn't work.... > > Thank Bye Jackok, 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
Reply by ●March 22, 20172017-03-22
On Wed, 22 Mar 2017 03:59:53 -0700, Jack wrote:> 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):<< code snipped >>> 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 JackFirst, 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 http://www.wescottdesign.com I'm looking for work -- see my website!
Reply by ●March 22, 20172017-03-22
On 22.3.17 18:33, Jack wrote:> Il giorno mercoledì 22 marzo 2017 16:04:07 UTC+1, Jack ha scritto: >> Il giorno mercoledì 22 marzo 2017 14:56:03 UTC+1, Tauno Voipio ha scritto: >>> On 22.3.17 14:02, Jack wrote: >>>> Il giorno mercoledì 22 marzo 2017 12:29:13 UTC+1, dp ha scritto: >>>>> On 22.3.2017 г. 12:59, Jack wrote: >>>>>> 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 >>>>>> >>>>> >>>>> Look at rfc1331, it has the lookup table values and algorithms >>>>> etc. >>>> >>>> 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. >>> >>> >>> 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). >> >> I don't want a 2 byte table. >> I want an algorithm that process a word (16bit) and not a byte, as every algorithm 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" one (check the link for good/bad definition). >> >> So splitting the 16bit word in 2 doesn't work.... >> >> Thank Bye Jack > > 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 >Exactly that was I tried to explain. -- -TV
Reply by ●March 23, 20172017-03-23
Il giorno mercoledì 22 marzo 2017 18:47:37 UTC+1, Tim Wescott ha scritto:> 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).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 optimizing things. Thanks Bye Jack
