| Author |
Message |
spamiam
Joined: 13 Nov 2005
|
|
Posted: 04 November 2007, 18:08 PM Post subject: Dallas 1-Wire CRC-8 calculator |
|
|
Here is an adaptation of the CRC-8 calculator I found which was written by P H Anderson (www.phanderson.com).
It is reasonably compact and uses relatively little stack space.
You give it the current CRC (which is zero if this is the first byte in the CRC calculation sequence) and the data byte. It will return the new CRC value.
-Tony
| Description: |
|
Download |
| Filename: |
CRC8.bas |
| Filesize: |
847 Bytes |
| Downloaded: |
1150 Time(s) |
|
|
| Back to top |
|
 |
mikep
Joined: 24 Sep 2005
Location: Austin, TX
|
|
Posted: 04 November 2007, 19:45 PM Post subject: |
|
|
According to the Dallas application note the polynomial for the 8-bit CRC is 0x31.
Given the intensive amount of computation I think you should implement the 256 byte lookup table. This is quite small and can be easily stored in EEPROM. If you remember previously when I was investigating CRC16 for Modbus, I showed some performance results of the difference between calculating each bit and using a lookup table. The results speak for themselves and I believe helped Don decide that it was worth implementing in the ZVM.
|
|
| Back to top |
|
|
spamiam
Joined: 13 Nov 2005
|
|
Posted: 04 November 2007, 22:12 PM Post subject: |
|
|
Mike, thanks for the feedback.
I do recall the Modbus CRC discussion, though at the time i was focusing more on the hardware at the time.
I am not sure how I can use the polynomial value you gave me to calculate the CRC, I tried to use CRC16() giving it a byte and the polynomial. But neither the HiByte nor the LoByte of the resulting CRC16 matched the CRC8 I had calculated. ALso, I did not see a reference to that polynomial value in the AppNote you referenced. I did see other potential polynomial values, and I tried them too, also without success.
I took your advice and wrote the MUCH simpler look-up table technique. I used ByteVectorData. It was trivial to write, unlike your CRC16 version.
I timed the results with 1000 iterations of an 8 byte CRC calculation. The look-up table version is 13 times faster!
I am attaching the updated CRC8 module with both techniques.
-Tony
| Description: |
| Updated module with both the calculated and look-up techniques of determining the CRC-8 |
|
Download |
| Filename: |
CRC8.bas |
| Filesize: |
2.47 KB |
| Downloaded: |
873 Time(s) |
|
|
| Back to top |
|
|
mikep
Joined: 24 Sep 2005
Location: Austin, TX
|
|
Posted: 05 November 2007, 1:25 AM Post subject: |
|
|
| spamiam wrote: | I am not sure how I can use the polynomial value you gave me to calculate the CRC, I tried to use CRC16() giving it a byte and the polynomial. But neither the HiByte nor the LoByte of the resulting CRC16 matched the CRC8 I had calculated. ALso, I did not see a reference to that polynomial value in the AppNote you referenced. I did see other potential polynomial values, and I tried them too, also without success.
|
The polynomial is specified in figure 2 of the application note. I don't think it is possible to use CRC16 for a 8-bit CRC. The polynomial is useful for the CRC test site referenced in the ZBasic manual.
| spamiam wrote: | I took your advice and wrote the MUCH simpler look-up table technique. I used ByteVectorData. It was trivial to write, unlike your CRC16 version.
I timed the results with 1000 iterations of an 8 byte CRC calculation. The look-up table version is 13 times faster! |
Told ya  You may want to write a function with a loop to calculate the CRC for the full ID which will save a little more time than calling your function 8 times (or 7 times if you prefer). Also don't forget that your table routine is 78 bytes shorter than the calculation so you are only using an extra 177 bytes of program memory.
|
|
| Back to top |
|
|
spamiam
Joined: 13 Nov 2005
|
|
Posted: 05 November 2007, 13:41 PM Post subject: |
|
|
Yes, I did not see any way to use a CRC-16 to get the effect of the Dallas CRC-8, but I did not do exhaustive analysis at all.
| mikep wrote: | | Also don't forget that your table routine is 78 bytes shorter than the calculation so you are only using an extra 177 bytes of program memory. |
Yes, in the scheme of things, 177 bytes extra is nothing.
Since the majority of the code size burden was the look-up table, I can economically write a second version of the CRC-8 calculator to work on a data "array" (I wanted to write "vector" since I was meaning a 1-dimensional array, but we don't call them that as far as I know).
I wrote the single byte version first because my first need for the CRC calculation was for the search algorithm that determines ROM codes for all the devices on the 1-wire bus. You get the data only byte-by-byte, so the CRC calculation is done incrementally.
I may call the two versions CRC8Byte(), and CRC8Data().
The reason for the 2 versions is to save the effort of adding all the unnecessary stuff in the call for a single byte, and also to avoid the overhead of single iteration loops.
-Tony
|
|
| Back to top |
|
|
mikep
Joined: 24 Sep 2005
Location: Austin, TX
|
|
Posted: 05 November 2007, 14:24 PM Post subject: |
|
|
| mikep wrote: | | Also don't forget that your table routine is 78 bytes shorter than the calculation so you are only using an extra 177 bytes of program memory. |
Just in case anyone has noticed. The above sentence should say 178 not 177. Either way it doesn't make much difference when you have 32K or even 64K of program memory.
|
|
| Back to top |
|
|
|
