 |
 |
| View previous topic :: View next topic |
| Author |
Message |
waranet
Joined: 05 Jan 2006
Posts: 10
Location: France
|
| Faster code for CRC8 ? |
 Posted: Mon Dec 08, 2008 8:11 am |
 |
|
Hi, I'm working on a CRC8 checksum, I found a solution, it works fine but takes a lot of time... about 100 ms with a string of 100 cars. Do you know a better and faster solution, here is my code. Thanks for your help, JP.
| Code: | int crc8,iresult,j,i,k;
int x;
crc8=0;
iresult=strlen(mystring);
for(i=0;i<iresult;i++)
{
x=mystring[i];
for(k=0;k<8;k++)
{
j=(1 & (x ^ crc8));
crc8=floor(crc8/2);
x=floor(x/2);
if(j!=0)
{crc8=crc8 ^ 0x8c;}
}
} |
|
|
 |
RLScott
Joined: 10 Jul 2007
Posts: 465
|
| Re: Faster code for CRC8 ? |
| Posted: Mon Dec 08, 2008 8:43 am |
|
|
| waranet wrote: | Hi, I'm working on a CRC8 checksum, I found a solution, it works fine but takes a lot of time... about 100 ms with a string of 100 cars. Do you know a better and faster solution, here is my code. Thanks for your help, JP.
| Code: | int crc8,iresult,j,i,k;
int x;
crc8=0;
iresult=strlen(mystring);
for(i=0;i<iresult;i++)
{
x=mystring[i];
for(k=0;k<8;k++)
{
j=(1 & (x ^ crc8));
crc8=floor(crc8/2);
x=floor(x/2);
if(j!=0)
{crc8=crc8 ^ 0x8c;}
}
} |
|
You could speed this up by at least a factor of 8 by processing one byte at a time instead of one bit at a time in the inner loop:
| Code: | int crc8,iresult,j,i,k;
int x;
crc8=0;
iresult=strlen(mystring);
for(i=0;i<iresult;i++)
{
x=mystring[i];
crc8 = crc8 ^ CrcTable[ crc8 ^ x];
}
|
I don't have the 256-byte lookup table handy, but you should be able to find it or develop it from scratch. In fact, you can use your bit-by-bit algorithm (in a desktop environment, not in a PIC) to develop CrcTable. CrcTable would, of course, be a const array in program space, not in RAM.
_________________
Robert Scott
Real-Time Specialties
Embedded Systems Consulting |
|
|
ckielstra
Joined: 18 Mar 2004
Posts: 3680
Location: The Netherlands
|
|
| Posted: Mon Dec 08, 2008 5:10 pm |
|
|
| Quote: | crc8=floor(crc8/2);
x=floor(x/2);
|
Most obvious optimization is to get rid of the two 'floor' calls. Floor is a floating point function and will take ages when compared to integer arithmetic. On a PIC18F452 I rewrote these two lines to the equivalent: | Code: | crc8 = crc8/2;
x = x/2; |
Note that integer arithmetic will loose the fractional part, i.e. an automatic floor operation for free!
This simple change reduced the code size by almost 2400 bytes. Or when tested in the MPLAB Simulator with a simple string "Hello world" it reduced the instruction cycle count from 161382 to 1954 cycles. That is 82 times faster!!! 
If you don't care about the exact CRC8 algorithm you will find an even more optimized version of the Dallas 1-wire CRC-8 in the Code Library which is about 4 times faster than the above version.
CRC-8: http://www.ccsinfo.com/forum/viewtopic.php?t=26264
Or an just as fast CRC-16: http://www.ccsinfo.com/forum/viewtopic.php?t=24977 |
|
|
FvM
Joined: 27 Aug 2008
Posts: 2337
Location: Germany
|
|
| Posted: Tue Dec 09, 2008 12:25 am |
|
|
As said, table crc routine and assembly coded variant are fastest. In many cases, e.g. when performed during serial UART send or receive, that has a lot of idle time anyway, standard C code is sufficient. The usual form is using shift instructions, that are to supposed not to be misunderstood by a C compiler.
| Code: | for (i=0;i<8;i++)
{
if ((inchar ^ crc8) & 0x01)
{
crc8 >>=1;
crc8 ^= 0x8c; // 0x31 reversed
}
else crc8 >>= 1;
inchar >>= 1;
} |
|
|
|
waranet
Joined: 05 Jan 2006
Posts: 10
Location: France
|
| Thanks |
| Posted: Sat Dec 13, 2008 7:03 am |
|
|
Thanks a lot for your help, I will try these solutions ASAP. My PIC is 18F2523, 20 MHz.
JP |
|
|
languer
Joined: 09 Jan 2004
Posts: 144
Location: USA
|
|
| Posted: Thu Dec 18, 2008 2:09 am |
|
|
***
EDIT: Credits for original code...
crc1: Original code by Tom Estes
crc2: Original code by T. Scott Dattalo
crc3: Original code by jds-pic
***
Not too long ago, I looked for something similar. I found three code snippets which implemented the desired CRC-8 code. Below I show them with some statistics attached to them.
| Code: | // CRC8 Function (ROM=53 / RAM=6 / Average => 1268_Tcy / 158.5_us for 8MHz clock)
int8 crc1(int8 crc, int8 crc_data)
{
int8 i, testbyte;
int1 testbit;
for (i=0;i<8;i++)
{
testbit = (crc & 1) ^ (crc_data & 1); //'XOR bit0 of data byte and crc
crc_data = crc_data >> 1; //'Position data byte for next bit test
if (!testbit) //'If test bit not set, just shift CRC
{
crc = crc >> 1; //'CRC bit 0 to bit bucket
//crc.7 = testbit; //'Test bit rotates into CRC bit 7
crc = crc|(testbit << 7); //'Test bit rotates into CRC bit 7
}
else
{
crc = crc ^ 0x18; //'If set, account for EXOR feedback
crc = crc >> 1; //'CRC bit 0 to bit bucket
//crc.7 = testbit; //'Test bit rotates into CRC bit 7
crc = crc|(testbit << 7); //'Test bit rotates into CRC bit 7
}
}
return(crc);
} |
| Code: | // CRC8 Function (ROM=39 / RAM=4 / Average => 196_Tcy / 24.5_us for 8MHz clock)
int8 crc2(int8 crc, int8 crc_data)
{
int8 i;
i = (crc_data ^ crc) & 0xff;
crc = 0;
if(i & 1)
crc ^= 0x5e;
if(i & 2)
crc ^= 0xbc;
if(i & 4)
crc ^= 0x61;
if(i & 8)
crc ^= 0xc2;
if(i & 0x10)
crc ^= 0x9d;
if(i & 0x20)
crc ^= 0x23;
if(i & 0x40)
crc ^= 0x46;
if(i & 0x80)
crc ^= 0x8c;
return(crc);
} |
| Code: | // CRC8 Function (ROM=37 / RAM=7 / Average => 1564_Tcy / 195.5_us for 8MHz clock)
int crc3(int crc, int crc_data)
{
//int8 shift_reg, data_bit, sr_lsb, fb_bit, j;
//shift_reg = crc;
int8 j, data_bit, sr_lsb, fb_bit;
for(j=0; j<8; j++)
{ // for each bit
data_bit = (crc_data >> j) & 0x01;
//sr_lsb = shift_reg & 0x01;
sr_lsb = crc & 0x01;
fb_bit = (data_bit ^ sr_lsb) & 0x01;
//shift_reg = shift_reg >> 1;
crc = crc >> 1;
if (fb_bit)
{
//shift_reg = shift_reg ^ 0x8c;
crc = crc ^ 0x8c;
}
}
//return(shift_reg);
return(crc);
} |
It is not hard to imagine which one I used, but all three are useful.
Last edited by languer on Thu Dec 18, 2008 9:45 pm; edited 2 times in total |
|
|
waranet
Joined: 05 Jan 2006
Posts: 10
Location: France
|
| CRC8 Fast Code |
| Posted: Thu Dec 18, 2008 2:29 am |
|
|
Hi,
Thanks for your help.
I tried out the cKielstra solution, I released only the "floor" from my code... and it's percfect, easy to handle and secure.
regards
JP |
|
|
ckielstra
Joined: 18 Mar 2004
Posts: 3680
Location: The Netherlands
|
|
| Posted: Thu Dec 18, 2008 7:22 pm |
|
|
| languer wrote: | | It is not hard to imagine which one I used, but all three are useful. |
I always like these optimization comparisons.
Your fast CRC2 function is a C-version of the Dallas 1-wire CRC8 I mentioned above, see also the Code Library
For calculating the CRC of a single character there won't be a big difference between the C and asm-versions but for calculating the CRC over an array or string the assembly version is a lot faster.
The assembly version has the advantage that it can use the POSTINC register for an highly optimized array traversing while the C-version has to do extensive calculations for accessing the bytes in a string/array.
| Code: | void main()
{
char string[20] = "Hello world";
int8 i;
int8 crc;
// Assembly version
crc = Calc_Crc8(string, sizeof(string) );
// C-version
crc=0;
for (i=0; i< sizeof(string); i++)
crc = crc2(crc String[i]);
} |
Assembly version: 478 cycles total
C version: 1183 cycles total
(Compiler v4.077, PIC18F452) |
|
|
languer
Joined: 09 Jan 2004
Posts: 144
Location: USA
|
|
| Posted: Thu Dec 18, 2008 9:48 pm |
|
|
Updated the previous post with credits to the original authors.
All three codes implemented the Dallas 1-wire poly. |
|
|
FvM
Joined: 27 Aug 2008
Posts: 2337
Location: Germany
|
|
| Posted: Fri Dec 19, 2008 12:43 am |
|
|
Curiously, my snippet, that wasn't meant to be optimized anyhow, turns out to be more effective in terms of ROM usage, comparable with the ASM code mentioned by ckielstra (omitting the string loop). It''s also considerably faster than crc1 and crc3, but of course, can't compete with the linear crc2 or ASM codes. I used PCM V4.083 as the results have been apparently achieved for PIC16.
| Code: | // ROM=24 RAM=4
int8 crc4(int8 crc8, int8 inchar)
{
char i;
for (i=0;i<8;i++)
{
if ((inchar ^ crc8) & 0x01)
{
crc8 >>=1;
crc8 ^= 0x8c; // 0x31 reversed
}
else crc8 >>= 1;
inchar >>= 1;
} |
|
|
|
mmclaren
Joined: 20 May 2012
Posts: 1
Location: Michigan, USA
|
|
| Posted: Sun May 20, 2012 6:09 pm |
|
|
Forgive me for resurrecting an old thread Gentlemen but I just came across it and it struck me that another approach might be used for CRC8 with 1-Wire devices..
It seems the CRC8 algorithm can be used a number of different ways, especially at the bit level, and so I decided to give it a try using BoostC (sorry) and a set of experimental low level 1-Wire drivers of my own design. The code I added to handle the bit level cumulative CRC8 calculation uses 8 words of program memory, 1 variable, and 0 cycles processing overhead if you consider that the code runs in the place of a portion of the delay required to fill-out the 60-usec read/write slot timing. Here's an excerpt from my read/write bit driver of the CRC8 code (this is a 16F1828 project);
| Code: | /* *
* K8LH cumulative CRC8 calculation (preserves data bit in Carry) *
* */
asm clrf _wreg //
asm rlf _wreg,W // save C (wreg = 0x00 or 0x01)
asm xorwf _crc,F // xor b0 bits, result in 'crc'
asm rrf _crc,F // zero result from xor (C=0)?
asm skpnc // yes, skip, else
asm iorlw 0x18 // wreg = x8+x5+x4+1 poly and b0 bit
asm rrf _wreg,W // restore C (wreg = 0x8C or 0x00)
asm xorwf _crc,F // apply the polynomial, or not
|
Like other CRC8 methods, you need to clear the 'crc' variable before reading a 1-Wire ROM ID or Scratchpad memory and then confirm that 'crc' equals zero after reading the last ('crc') byte.
I hope someone finds this idea and method useful.
Cheerful regards, Mike
Last edited by mmclaren on Mon May 21, 2012 5:54 am; edited 1 time in total |
|
|
ckielstra
Joined: 18 Mar 2004
Posts: 3680
Location: The Netherlands
|
|
| Posted: Mon May 21, 2012 1:37 am |
|
|
Mike,
Thanks for posting the new approach to a similar problem.
Your code is very efficient when used in the 1-wire protocol. For every bit received you update the CRC and when the whole message has arrived the CRC is known immediately. No extra processing time required and small code base.
The other CRC-8 algorithms as discussed in this thread are better for calculating the CRC over an array of bytes already present, for example configuration data stored in EEPROM.
When receiving data with a UART you will get bytes instead of bits, then your approach could be combined with the algorithm of CRC2 (CRC8 from Code library) for a very efficient program.
Conclusion:
Depending on your requirements the 'best' solution can be very different. |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ 
Search
Register
Profile 
Log in to check your private messages 
Log in
