CRC calculation

On 22.3.2017 ?. 12:59, Jack wrote:


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/

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.

On 22/03/17 13:02, Jack wrote:


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

On 22.3.17 14:02, Jack wrote:




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

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

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

On 22.3.17 18:33, Jack wrote:






Exactly that was I tried to explain.

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.

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

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.

:


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