Yes, the Dallas Semi App Note is a good reference. Bernard, check the
diagrams at Fig. 2 and 6. This is basically all you need to know to do
it without a table. For each data bit the CRC register (stages X^0 ..
X^16) is shifted and some bits (corresponding to the polynomial value)
are inverted (shown with XOR gates) IF the stage x^16 value is
different from the data bit. So, for each data bit you would do the
following:

1) compare data bit and x^16 stage output, that would be the X^0 stage
value: x0 = x16 XOR data_bit.
2) if x0 == 1, invert the required stages.
3) shift CRC register

In C it might look like this:

(suppose we send higher bit first, and CRC stages X^1..X^16 correspond
to bits 0..15. X^0 will get shifted immediately in the register, so we
don't need an extra bit to store it)

unsigned int data;
unsigned int crc;

/*

  Compare data bit (MSB of data) and CRC stage x^16 (MSB of crc).

*/
if((crc ^ data) & 0x8000)
{
  /* If they differ, shift crc and invert some bits using polynomial

  x^16+x^15+x^2+1

  which is done with a bit mask 1000 0000 0000 0101   = 0x8005
                                |               |  \_
                                x^15            x^2  x^0

  */

  crc <<= 1; /* shift left crc, from stages x^0.. x^15 to x^1..x^16.
                use 0 for x^0 - this is ok as we invert it with the
                mask in the next line */
  crc ^= 0x8005;
}
else
{
  crc <<= 1; /* shift left crc, and use zero value for x^0 because it
             is zero! */
}


Then you just repeat this snippet for all your 16 (or whatever) data bits:

unsigned int data;
unsigned int crc;
unsigned char i;

for(i = 16; i != 0; i--)
{
  /*

    Compare data bit (MSB of data) and CRC stage x^16 (MSB of crc).

  */
  if((crc ^ data) & 0x8000)
  {
    /* If they differ, shift crc and invert some bits using polynomial

    x^16+x^15+x^2+1

    which is done with a bit mask 1000 0000 0000 0101   = 0x8005
                                  |               |  \_
                                  x^15            x^2  x^0

    */

    crc <<= 1; /* shift left crc, from stages x^0.. x^15 to x^1..x^16.
                  use 0 for x^0 - this is ok as we invert it with the
                  mask in the next line */
    crc ^= 0x8005;
  }
  else
  {
    crc <<= 1; /* shift left crc, and use zero value for x^0 because it
               is zero! */
  }
}

The initial crc value can be any, but it must be defined to get a
usable result. So use the same value as your receiver does.

See also

http://www.piclist.com/techref/microchip/crcs.htm

for some asm code.

Anyone wants to do the above in maybe 12 instructions and without
loops? :) Maybe for an 8-bit data case?


 Nikolai

Tuesday, July 31, 2001, 1:44:08 AM, James Hillman wrote:
>> Anyone got any non-table driven known good code
>> with explanation of the bit
>> shifting operations?

> I learnt about CRC checking from this article when I needed to write a crc16
> routine for Dallas keys

> (its a 16 page .pdf document)

> http://pdfserv.maxim-ic.com/arpdf/AppNotes/app27.pdf

> and heres the code I wrote (CCS c) after reading it (based on Table 5).
> Trouble is I can't remember how it works anymore and I think I've
> subsequently seen more efficient code on this list. Still for what its
> worth...

> Hope it helps,

> James Hillman


> /** Calculate the 16 bit crc **/

> /* lo and hi are global variables initialised to 0 at the start */
> /* lo is the low byte of the CRC */
> /* hi is the high byte of the CRC */
> /* a is the new byte of data to be crc'd */

> void calc_crc16(byte a)
> {
>    short c;    /* parity bit */
>    byte p;     /* local temp */
>    c=0;        /* initialise parity */
>    p=0;

> /* find the "parity" of lo and a  */
>    #asm
>    btfsc lo,7
>     incf p,f
>    btfsc lo,6
>     incf p,f
>    btfsc lo,5
>     incf p,f
>    btfsc lo,4
>     incf p,f
>    btfsc lo,3
>     incf p,f
>    btfsc lo,2
>     incf p,f
>    btfsc lo,1
>     incf p,f
>    btfsc lo,0
>     incf p,f
>    btfsc a,7
>     incf p,f
>    btfsc a,6
>     incf p,f
>    btfsc a,5
>     incf p,f
>    btfsc a,4
>     incf p,f
>    btfsc a,3
>     incf p,f
>    btfsc a,2
>     incf p,f
>    btfsc a,1
>     incf p,f
>    btfsc a,0
>     incf p,f
>    #endasm

>    if(bit_test(p,0))
>       c=1;              /* set "parity" bit if odd */

> /* crc16 routine */

>    a^=lo;          /* see explanation in Dallas appnote 27 */
>    lo=hi;
>    hi=a;
>    if(c)
>       lo^=0x01;
>    c=shift_right(&a,1,c);
>    if(c)
>       lo^=0x40;
>    c=(bit_test(a,7));
>    a^=hi;
>    c=shift_right(&a,1,c);
>    hi=a;
>    if(c)
>       lo^=0x80;
> }

> --
> http://www.piclist.com hint: PICList Posts must start with ONE topic:
> [PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads