Post by thread:[OT]:Question on CRC ( based on notes by Ross Will

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 address pointer? 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 spam_OUTpiclist-unsubscribe-requestTakeThisOuTmitvma.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 > address pointer? 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-requestKILLspam@spam@mitvma.mit.edu

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" <ashKILLspamDIGITALNEMESIS.COM> To: <.....PICLISTKILLspam.....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}> 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 > > address pointer? > > 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 {Quote hidden}> > > > > 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 {Quote hidden}> 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 > EraseMEpiclist-unsubscribe-requestspam_OUTTakeThisOuTmitvma.mit.edu > > > > {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 for your application, maybe not. 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 reader :) 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}> 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? -- http://www.piclist.com hint: To leave the PICList piclist-unsubscribe-requestspam_OUTmitvma.mit.edu