CRC7 Polynomial?

Javalin

Hiya all,

I have a question, and I have to admit that I may not fully understand the answer. Sadly my maths are not wonderfull... :-(

I've been trying to get the CRC7 & CRC16 working on my SD card object, and after lots of reading have re-written a C example in SPIN - which works:

PUB crc7(buffer,count) | crc, c
    crc := 0
    repeat count
        c := byte[buffer++]        
        repeat 8
            crc <<= 1
            if (c ^ crc) & $80
                crc ^= $9
            c <<= 1
    result := crc & $7F

However why is the poly $9 not $89 (%1000_1001)? as it is generated by x^7 + x^3 + 1?

Thanks,

James

Phil Pilgrim (PhiPi)

Since Spin is indentation-sensitive, it's impossible to follow your code. Please repost it between [noparse]

and

[/noparse] tags to preserve the indentation.

-Phil

Javalin

Hiya Phil - done. Didn't know how to do that with this new forum software...

:-)

J

Phil Pilgrim (PhiPi)

Javalin wrote:

However why is the poly $9 not $89 ... ?

Could it be the last line in your routine (result := crc & $7F), perhaps?

-Phil

Javalin

No I don't think so. Thats just masking the bits. If I change:

            if (c ^ crc) & $80
                crc ^= [COLOR="Red"]$9[/COLOR]

to

            if (c ^ crc) & $80
                crc ^= [COLOR="Red"]$89[/COLOR]

I get a different result. I don't get it - I thought the x^7 + x^3 + 1 = %1000_1001, but the $9 is just %1001 so why? Unless its just how this implemention works?

James

PS - how do you do bold, itallics and colour on this forum software now????

Phil Pilgrim (PhiPi)

Javalin wrote:

No I don't think so. Thats just masking the bits.

That's what I meant: $89 & $7F == $09.

For formatting assistance, go to the forum FAQ and do a search on bbcode.

-Phil

Javalin

oh - ok. I'll be home in an hour or so and i'll try the combinations and see. Sure I tested it with both - but will double check.

Thanks Phil.

James

KaosKidd

Javalin wrote: »

PS - how do you do bold, itallics and colour on this forum software now????

Use [ I ] text to be italics [ / I ] For italics, use [ U ] text to be underline [ / U ] for underline and use [ B ] text to be bold [ / B ] for bold.
PS: Remove all spaces between the [ and ]!

Or you can use the B / I / U buttons (under the font selection box in the editor)

Now for the color...
[ COLOR = "Red" ][ / COLOR ] will produce Red,
[ COLOR = "Green" ][ / COLOR ] will produce Green, etc.
PS: Remove all spaces between the [ and ]!
Or, in the editor, next to the sizes drop down list, is a big A with a color line under it
select that drop down and pick your color!

Javalin

ah ok - got it - ta.

James

Phil Pilgrim (PhiPi)

KK,

You can also put your BBcode examples between [noparse][noparse] and [/noparse][/noparse] tags so you don't have to insert the extra spaces.

-Phil

Dave Hein

Wow, most of the responses in this thread seem to be about formatting instead of answering the original question. I've never fully understood the binary polynomial math that is used in CRC's and correcting code. However, from what I can tell the highest polynomial bit postition is never included in the ex-or computation, but does determine which bit is tested and the final number of bits retained.

I believe the "crc ^= $9" is correct. You should verify it with data that includes a known good CRC7 code.

Dave

Javalin

Hiya Dave, Phil,

This is odd, I guess Dave is right. If I use $89 or $9 it still works. I've only got one test case at the moment (the CMD0 init string for SD cards) - so might behave differently with more testing

Was sure I tested both - perhaps that was a previous attempt....

Cheers both.

James

Dave Hein

I found a table-driven version of the CRC7 algorithm that is written in C. I tested it against your routine (converted to C) and it matches. The C code is shown below.

Dave

#include <stdio.h>
#include <stdlib.h>

unsigned char crc7_syndrome_table[256] = {
        0x00, 0x09, 0x12, 0x1b, 0x24, 0x2d, 0x36, 0x3f,
        0x48, 0x41, 0x5a, 0x53, 0x6c, 0x65, 0x7e, 0x77,
        0x19, 0x10, 0x0b, 0x02, 0x3d, 0x34, 0x2f, 0x26,
        0x51, 0x58, 0x43, 0x4a, 0x75, 0x7c, 0x67, 0x6e,
        0x32, 0x3b, 0x20, 0x29, 0x16, 0x1f, 0x04, 0x0d,
        0x7a, 0x73, 0x68, 0x61, 0x5e, 0x57, 0x4c, 0x45,
        0x2b, 0x22, 0x39, 0x30, 0x0f, 0x06, 0x1d, 0x14,
        0x63, 0x6a, 0x71, 0x78, 0x47, 0x4e, 0x55, 0x5c,
        0x64, 0x6d, 0x76, 0x7f, 0x40, 0x49, 0x52, 0x5b,
        0x2c, 0x25, 0x3e, 0x37, 0x08, 0x01, 0x1a, 0x13,
        0x7d, 0x74, 0x6f, 0x66, 0x59, 0x50, 0x4b, 0x42,
        0x35, 0x3c, 0x27, 0x2e, 0x11, 0x18, 0x03, 0x0a,
        0x56, 0x5f, 0x44, 0x4d, 0x72, 0x7b, 0x60, 0x69,
        0x1e, 0x17, 0x0c, 0x05, 0x3a, 0x33, 0x28, 0x21,
        0x4f, 0x46, 0x5d, 0x54, 0x6b, 0x62, 0x79, 0x70,
        0x07, 0x0e, 0x15, 0x1c, 0x23, 0x2a, 0x31, 0x38,
        0x41, 0x48, 0x53, 0x5a, 0x65, 0x6c, 0x77, 0x7e,
        0x09, 0x00, 0x1b, 0x12, 0x2d, 0x24, 0x3f, 0x36,
        0x58, 0x51, 0x4a, 0x43, 0x7c, 0x75, 0x6e, 0x67,
        0x10, 0x19, 0x02, 0x0b, 0x34, 0x3d, 0x26, 0x2f,
        0x73, 0x7a, 0x61, 0x68, 0x57, 0x5e, 0x45, 0x4c,
        0x3b, 0x32, 0x29, 0x20, 0x1f, 0x16, 0x0d, 0x04,
        0x6a, 0x63, 0x78, 0x71, 0x4e, 0x47, 0x5c, 0x55,
        0x22, 0x2b, 0x30, 0x39, 0x06, 0x0f, 0x14, 0x1d,
        0x25, 0x2c, 0x37, 0x3e, 0x01, 0x08, 0x13, 0x1a,
        0x6d, 0x64, 0x7f, 0x76, 0x49, 0x40, 0x5b, 0x52,
        0x3c, 0x35, 0x2e, 0x27, 0x18, 0x11, 0x0a, 0x03,
        0x74, 0x7d, 0x66, 0x6f, 0x50, 0x59, 0x42, 0x4b,
        0x17, 0x1e, 0x05, 0x0c, 0x33, 0x3a, 0x21, 0x28,
        0x5f, 0x56, 0x4d, 0x44, 0x7b, 0x72, 0x69, 0x60,
        0x0e, 0x07, 0x1c, 0x15, 0x2a, 0x23, 0x38, 0x31,
        0x46, 0x4f, 0x54, 0x5d, 0x62, 0x6b, 0x70, 0x79
};

int crc7(unsigned char *buffer, int count)
{
    int i, c, crc;
    crc = 0;
    while (count-- > 0)
    {
	c = *buffer++;
        for (i = 0; i < 8; i++)
        {
	    crc <<= 1;
	    if ((c ^ crc) & 0x80) crc ^= 0x9;
	    c <<= 1;
        }
    }
    return crc & 0x7f;
}

int crc7x(unsigned char *buffer, int count)
{
    int c, crc;
    crc = 0;
    while (count-- > 0)
    {
	c = *buffer++;
        crc = crc7_syndrome_table[(crc << 1) ^ c];
    }
    return crc;
}

void main(void)
{
    int i;
    unsigned char buffer[1000];

    for (i = 0; i < 1000; i++) buffer[i] = rand() & 0xff;

    printf("crc7 = %02x, crc7x = %02x\n", crc7(buffer, 1000), crc7x(buffer, 1000));
}

Javalin

Wow - thanks Dave.

You haven't anything for the crc16 CCITT one have you??? - thats the next task to get it working for the SD card data blocks...

Found this so far:

unsigned short crc16(data_p, length)
char *data_p;
unsigned short length;
{
       unsigned char i;
       unsigned int data;
       unsigned int crc;
       
       crc = 0xffff;
       
       if (length == 0)
              return (~crc);
       
       do {
              for (i = 0 data = (unsigned int)0xff & *data_p++;
                  i < 8;
                  i++, data >>= 1) {
                    if ((crc & 0x0001) ^ (data & 0x0001))
                           crc = (crc >> 1) ^ POLY;
                    else
                           crc >>= 1;
              }
       } while (--length);
       
       crc = ~crc;
       
       data = crc;
       crc = (crc << 8) | (data >> 8 & 0xFF);
       
       return (crc);
}

from http://www.drdobbs.com/199904926;jsessionid=5XQ05NE50QGWLQE1GHPCKH4ATMY32JVN

which i've translated as :

PUB crc16a(buffer,count) | crc, c
    crc := $FFFF
    repeat count
        c := byte[buffer++]
        repeat 8
            if (crc & $1) ^ (c & $1)
                crc := (crc >> 1) ^ $8404
            else
                crc >>=1
            c >>= 1
    crc := ~crc
    c := crc
    crc := (crc << 8) | (c >> 8 & $FF)        
    return crc

Doesn't work though - comes out at

CRC16 = -011265 or $D3FF or %110100111111111

thanks again,

James

Dave Hein

The CRC16 routine I use for YMODEM is as follows:

PUB ComputeCRC(ptr, num)
  repeat num
    result ^= (byte[ptr++] << 8)
    repeat 8
      result <<= 1
      if result & $10000
        result ^= $1021
  result &= $ffff

$8408 is the bit-reversed value of $1021. It depends on whether the data is shifted out MSB first or LSB first.

Dave

Javalin

Dave - your a star. Top man. That works!

CRC16 = 032673 or $7FA1 or %0111111110100001  CORRECT!

Thanks!

James

Beau Schwabe

Javalin,


An important property of the polynomial generator is the width, which is defined as the position of its highest bit set to 1. The high-order bit of the polynomial is omitted when representing the divisor itself because the high-order bit should always be equal to 1. This makes sense if you look at the CRC in binary long hand.

Here is a link to something I did awhile back for our RF modules...

http://forums.parallax.com/showthread.php?t=117333&highlight=polynomial+schwabe

Reference:
http://www.ross.net/crc/download/crc_v3.txt

Javalin

thanks Beau

tonyp12

Run this code in a loop five times, input is the 5 bytes sdio-cmd, crc to be started with 0.
On the result, just add the stop bit and you all set.
for example:
CMD17 (Argument=0) --> 01 010001 00000000000000000000000000000000 "0101010" 1

1.  temp 
= 
XOR(input[],crc)
 
     //
begin 
high 
nibble

2.  temp
 =
 AND(temp,0xf0)
 
       //
four 
bit‐pair
 XOR
 values 
ready

3.  temp2
 =
 RIGHT
SHIFT(temp,3)

4.  temp
 =
 XOR(temp,temp2)
 
      //
eight
 bit‐pair
 XOR
 values 
ready

5.  crc
 =
 LEFT
SHIFT(crc,4)
 
      //
unpaired
 values 
positioned

6.  crc
 =
 XOR(crc,
temp)

 
         //
new
 CRC7
 complete
7.  temp
 = 
LEFT
SHIFT(input,4)
    //
begin
 low
 nibble

8.  temp
 = 
XOR(temp,crc)

9.  temp
 =
 AND(temp,0xf0)
       
 //
four
bit‐pair 
XOR 
values
 ready

10. temp2
 =
 RIGHT
SHIFT(temp,3)

11. temp
 =
 XOR(temp,temp2)
 
      //
eight
bit‐pair
 XOR 
values 
ready

12. crc
 =
 LEFT
SHIFT(crc,4)
 
      //
unpaired 
values 
positioned

13. crc
 =
 XOR(crc,
temp)

 
         //
new
 CRC7 
complete