Searching \ for '[OT]:Question on CRC ( based on notes by Ross Will' in subject line. () Help us get a faster server
FAQ page: www.piclist.com/techref/method/errors.htm?key=crc
Search entire site for: 'Question on CRC ( based on notes by Ross Will'.

Exact match. Not showing close matches.
'[OT]:Question on CRC ( based on notes by Ross Will'
2002\05\06@034919 by  Hi all,

I am currently reading some notes with the title 'CRC primer by Ross
Williams'. I am stuck at section 9-A table driven implementation. Wondering
if anyone has gone through the same notes and hopefully provide me some
guidance.
The link for the notes are as below - http://www.riccibitti.com/crcguide.htm

I do not understand what the C codes trying to do -

r = 0;
while ( len-- )
{
byte t = ( r >> 24 ) & 0xFF;
r = ( r << 8 )  | *p++;             // why OR with the contents of the
r^ =table[t];
}

where r = register, len = length of the message, t = temporary?, p = points
to the augmented message

I understand roughly the table way of implementation, but in the code above,
r was not loaded with a new value, so how does the bytes move on?

I will be gratefull for any guidance given.

Rgds,

Pang

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-request mitvma.mit.edu  Hi Pang,

I've not looked at these notes, but I can help with the C..

I'm assuming that "p" is pointing to the message being CRCed..

> r = 0;
> while ( len-- )
> {
>     byte t = ( r >> 24 ) & 0xFF;

>     r = ( r << 8 )  | *p++;             // why OR with the
> contents of the

This is rotating the CRC value currently stored in "r" by 8 bits and then it
assigns the current message byte into the lower 8 bits of "r" and then moves
the pointer to point to the next element in the message.

This is just a shorthand way of writing:

r = r << 8;             // rotate the CRC one byte left
r = r | (*p);   // set the lower byte to the current message value
// without changing the upper bytes of "r"
p++;                    // increment the pointer to the next byte in the message

>
>     r^ =table[t];
>

This is XORing the value in "r" with the result of the table lookup.

In "c", you can use the shorthand of X [operator]= value; to mean X = X
[operator] value;

The "^" means XOR in C.

Does that help? Can you see now where "r" is being updated?

If your going to port this to a PIC, remember - you will have different size
integers on the PIC. This looks like it is working with 32 bit ints.

I've implemented a CRC16 in a PIC with table lookups before. You need two
tables because it can't implement a table with a 16 bit value, so you need a
table for the "high" and "low" bytes.

Cheers,
Ash.

---
Ashley Roll
Digital Nemesis Pty Ltd
http://www.digitalnemesis.com
Mobile: +61 (0)417 705 718

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-request mitvma.mit.edu  You Can think of

*p++

as  func(p) where func is defined as:

int func(p)
{

int temp;       // assuming p is a pointer to int

temp = *p;      // save the value pointed by pointer p
p++;            // add to p the size in bytes of the items it points to
return temp
}

In C, p++ takes the value and then increment, ++p increments and then take
the
value.

Tal

> {Original Message removed}  Hi Ash,

Thanks for replying, but I hope you can help me further. Actually all i
wanted to do is to write a module for CRC-16, if I cannot move on from that
section of Ross Williams notes, I will just find some prewritten modules and
transfered it to the current assembly I am using. (Mot) But I am trying hard
to understand how the algorithm works.

The earlier portion of the notes details all the arithmetic needed for CRC
calculation. I understand how the checksum ( crc ) is calculated, what is a
poly and the message that is being divided. When it comes to table driven
implementation, it explains how one byte can be XOR with a precalculated
byte instead of doing it bit by bit.

The C codes example is actually for a CRC 32 bit implementation. The ' r '
is a 4 byte register, the table[x] also points to a 4 byte contents. The
size of the table is [ 0 - 255 ].
The algorithm is as below -

1. Shift the register left by one byte, reading in a new message byte.
2. Use the top byte just rotated out of the register to index the table of
256 32 bit values.
3. XOR the table value into the register.
4. Goto 1 if more augmented message bytes.
End.

I could not see the flow of the calculation,
- why is the shifted byte use as an off set to the table for XOR purpose?
- after XORing, the register is suppose to contain the remainder, but why is
only a single byte shifted in/out to the register?

Forgive me for my messy questions, I just can't see the flow ( the way
normal CRC division being done ). I will appreciate if you can point me to
any manual workings of such an implementation.

Thanks and have a nice day ahead.

Rgds,

pang

----- Original Message -----
From: "Ashley Roll" <ash DIGITALNEMESIS.COM>
To: <PICLIST MITVMA.MIT.EDU>
Sent: Monday, May 06, 2002 4:12 PM
Subject: Re: [OT]:Question on CRC ( based on notes by Ross Williams )

{Quote hidden}

it
> assigns the current message byte into the lower 8 bits of "r" and then
moves
> the pointer to point to the next element in the message.
>
> This is just a shorthand way of writing:
>
>         r = r << 8;             // rotate the CRC one byte left
>         r = r | (*p);   // set the lower byte to the current message value
>                                 // without changing the upper bytes of "r"
>         p++;                    // increment the pointer to the next byte
in the message
{Quote hidden}

size
{Quote hidden}

> > {Original Message removed}  Hi Pang

I'm not an expert of CRCs, but I'll have a go..

basically the CRC algorithms have a shift register with a XOR feedback taken
from selected bits in the register.. Smart people workout which taps for
best effect and then tell the rest of us. :)

Essentially the CRC is calculated by shifting in the message ONE bit at a
time. The bit that was just shifted out is then XORed back into the shift
register at particular bit locations. The location determine the strength of
the CRC for detecting corruption and luckily smart people have worked these
out and tell us.. :)

As you can imagine this is pretty slow on a processor taking many
instructions to do each bit of the message, custom hardware can do it very
easily however. But most of us use processors to do this so a "faster" way
is needed.

Basically the algorithm works on 8 bit chunks of the message at a time -
this is because processors tend to like 8 bit chunks.

You shift out 8 bits from the register and remember what they were because
we need them to calculate the appropriate feedback XOR step. Then the new
bits are "shifted in" by copying them to the low byte of the register. Now
to update the CRC with the feedback we could evaluate the feedback
polynomial for each bit shifted out one at a time or we could do this before
hand and make a table. Because we are only working on 8 bits at a time there
are only 256 possible combinations so we precalculate a table. The last step
is updating the content of the CRC register with the polynomial feedback of
the 8 bits shifted out, but it just gets done all at one go.

When implementing on a Microcontroller you have to trade speed for code
size. You could implement the CRC algorithm to operate one bit at a time and
therefore not need any tables but it would be pretty slow. This may be ok

If you need speed, you would have to implement a table system. It would be
possible to make a table work with 8 bit chunks of the message as your code
sample did, or your could choose a smaller number of bits and calculate your
own table. For instance you could do it for 4 bits at a time and only have a
table with 16 entries instead of 256 to save lots of code space.

If you used the smaller "4 bit" table you would have to shift in only 4 bits
of the message at a time, so it would take you 2 iterations to process a
byte from the message.

The trick of actually generating the tables is left as a exercise for the

Have a look at the CRC section on the Piclist web site:
http://www.piclist.com/techref/microchip/crcs.htm

Hope that helps
Cheers,
Ash.

---
Ashley Roll
Digital Nemesis Pty Ltd
http://www.digitalnemesis.com
Mobile: +61 (0)417 705 718

{Quote hidden}

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-request mitvma.mit.edu  In case is has not been mentioned,

Microchip has a CRC application note.