CCS C Software and Maintenance Offers
FAQFAQ   FAQForum Help   FAQOfficial CCS Support   SearchSearch  RegisterRegister 

ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

CCS does not monitor this forum on a regular basis.

Please do not post bug reports on this forum. Send them to support@ccsinfo.com

Faster code for CRC8 ?

 
Post new topic   Reply to topic    CCS Forum Index -> General CCS C Discussion
View previous topic :: View next topic  
Author Message
waranet



Joined: 05 Jan 2006
Posts: 10
Location: France

View user's profile Send private message Visit poster's website

Faster code for CRC8 ?
PostPosted: Mon Dec 08, 2008 8:11 am     Reply with quote

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

View user's profile Send private message

Re: Faster code for CRC8 ?
PostPosted: Mon Dec 08, 2008 8:43 am     Reply with quote

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

View user's profile Send private message

PostPosted: Mon Dec 08, 2008 5:10 pm     Reply with quote

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

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

View user's profile Send private message

PostPosted: Tue Dec 09, 2008 12:25 am     Reply with quote

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

View user's profile Send private message Visit poster's website

Thanks
PostPosted: Sat Dec 13, 2008 7:03 am     Reply with quote

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

View user's profile Send private message

PostPosted: Thu Dec 18, 2008 2:09 am     Reply with quote

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

View user's profile Send private message Visit poster's website

CRC8 Fast Code
PostPosted: Thu Dec 18, 2008 2:29 am     Reply with quote

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

View user's profile Send private message

PostPosted: Thu Dec 18, 2008 7:22 pm     Reply with quote

languer wrote:
It is not hard to imagine which one I used, but all three are useful.
I always like these optimization comparisons. Cool

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

View user's profile Send private message

PostPosted: Thu Dec 18, 2008 9:48 pm     Reply with quote

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

View user's profile Send private message

PostPosted: Fri Dec 19, 2008 12:43 am     Reply with quote

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

View user's profile Send private message

PostPosted: Sun May 20, 2012 6:09 pm     Reply with quote

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

View user's profile Send private message

PostPosted: Mon May 21, 2012 1:37 am     Reply with quote

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.
Display posts from previous:   
Post new topic   Reply to topic    CCS Forum Index -> General CCS C Discussion All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
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