Dallas CRC8 Routines

[Tom Estes]

Three different PBP programs to calculate the Dallas 8bit CRC.


' PIC16F628
' These routines are documented in Dallas Semiconductor Application Note 27
' Understanding and Using Cyclic Redundancy Checks
' This program contains three subroutines for calculating the Dallas 1Wire 8bit CRC.
' The computationally intensive short version is called CRC8. Use this one when
' you don't have enough PIC memory to store the table version (approx 270 words)
' and can afford the processing time.
' The table version CRC8LU is computationally fast since it works on byte at a time
' rather than bit at a time as CRC8 does.
' The Assembly Language version of the computationally intensive version is CRC8AL.
' Times per 8 bit CRCByte:
' CRC8LU 35usec
' CRC8AL 115usec
' CRC8 260usec
DEFINE OSC 4
@ DEVICE XT_OSC
@ DEVICE MCLR_OFF
@ DEVICE LVP_OFF
CMCON = 7

TestBit var Bit ' CRC8
TestByte var Byte ' CRC8AL
CRCData var Byte ' CRC8 & CRC8LU & CRC8AL
CRC var Byte ' CRC8 & CRC8LU & CRC8AL
I var Byte ' CRC8 & CRC8AL
' Test data
CRCData = $02
CRC = 0
'Gosub CRC8
'Gosub CRC8LU
Call CRC8AL
' Test CRC should be $BC
END

' ********** Subroutine CRC8 **********
' PBP Version not using lookup table
' Expects CRC starting value and CRCData
' CRC will be cumulative unless reset externally
' Gives ending CRC value and destroys CRCData
' Uses I-Byte, TestBit-Bit, CRC-Byte, CRCData-Byte
CRC8:
For I = 0 to 7 ' Do for all 8 bits in data byte
TestBit = CRC.0 ^ CRCData.0 ' XOR bit0 of data byte and crc
CRCData = CRCData >> 1 ' Position data byte for next bit test
If TestBit = 0 then Shift ' If test bit not set, just shift CRC
CRC = CRC ^ $18 ' If set, account for EXOR feedback
Shift: ' Shift right the CRC byte
CRC = CRC >> 1 ' CRC bit 0 to bit bucket
CRC.7 = TestBit ' Test bit rotates into CRC bit 7
Next I
Return

' ********** Subroutine CRC8AL **********
' Assembly Language version of Dallas CRC8 calculator
' Expects CRC starting value and CRCData
'CRC will be cumulative unless reset externally to routine
' Gives ending CRC value in CRC and destroys CRCData
' Uses I-Byte, TestByte-Byte, CRC-Byte, CRCData-Byte
ASM
_CRC8AL ; Dallas CRC8 Assembly Language PIC16F628
MOVLW 8
MOVWF _I ; Do this for all 8 bits of CRCByte
CRCLOOP
MOVF _CRC,0 ; Put CRC into W
XORWF _CRCData,0 ; XOR CRC with CRCData
MOVWF _TestByte ; Put results in TestByte
RRF _TestByte,1 ; Shift TestByte.0 into Carry bit
BTFSS STATUS,C ; If Carry = 1, account for EXOR feedback gates
GOTO CRCSHIFT ; Otherwise just shift CRC and CRCByte
MOVF _CRC,0 ; Get latest copy of CRC
XORLW 0x18 ; XOR with 18Hex
MOVWF _CRC ; Keep a copy of results
CRCSHIFT
RRF _CRC,1 ; Rotate CRC incorporating carry
RRF _CRCData,1 ; Rotate CRCData, carry shifts in but not important
DECFSZ _I,1 ; Keep track of #times through loop
GOTO CRCLOOP ; Go to start if not looped through the 8 bits
RETURN ; Return if all 8 bits analyzed
ENDASM

' ********** Subroutine CRC8LU **********
' Expects CRC at some starting value with data to CRC
' passed in CRCData.
' Gives ending CRC value and destroys CRCData
' Uses CRCData-Byte, CRC-Byte
CRC8LU:
CRCData = CRCData ^ CRC
Lookup CRCData, [0,94,188,226,97,63,221,131,194,156,126,32,163,253, 31,65,_
157,195,33,127,252,162,64,30,95,1,227,189,62,96,13 0,220,_
35,125,159,193,66,28,154,160,225,191,93,3,128,222, 60,98,_
190,224,2,92,223,129,99,61,124,34,192,158,29,67,16 1,255,_
70,24,250,164,39,121,155,197,132,218,56,102,229,18 7,89,7,_
219,133,103,57,186,228,6,88,25,71,165,251,120,38,1 96,154,_
101,59,217,135,4,90,184,230,167,249,29,69,198,152, 122,36,_
248,166,68,26,153,199,37,123,58,100,134,216,91,5,2 31,185,_
140,210,48,110,237,179,81,15,78,16,242,172,47,113, 147,205,_
17,79,173,243,112,46,204,146,211,141,111,49,178,23 6,14,80,_
175,241,19,77,206,144,114,44,109,51,209,143,12,82, 176,238,_
50,108,142,208,83,13,239,177,140,174,76,18,145,207 ,45,115,_
202,148,118,40,171,245,23,73,8,86,180,234,105,55,2 13,139,_
87,9,235,181,54,104,138,212,149,203,41,119,244,170 ,72,22,_
233,183,85,11,136,214,52,106,43,117,151,201,74,20, 246,168,_
116,42,200,150,21,75,169,247,182,232,10,84,215,137 ,107], CRC
' PBP only handles 255 constants in the list (256 for 18Cxxx). Since table is
' indexed starting at zero, special case for $FF (256th element).
If CRCData = $FF Then
CRC = 53
EndIF
Return

[CocaColaKid]

If I used this line of code:

owin portb.7, 0, [temp.byte0,temp.byte1,SKIP 6,crc_value]

Would the calculated CRC be the same value as crc_value?

[Tom Estes]

More than likely no.

You don't state which and I may not be familiar with the 1 wire device you are using but normally you would not be able to skip any characters it transmits. They would all need to be received and included in the CRC calculation. You will need to read the data sheet for the 1 wire device you are using to see what all is included in the CRC total.

To get that total feed each byte into the CRC routine, The CRC will be calculated and after all bytes that the manufacturer has included in the CRC total have been passed trough it, the CRC should be the same as the CRC received from the 1 wire device.

Tom

[CocaColaKid]

I actually working with the DS18S20 chip. From what I'm reading though it sounds like I calculate the CRC from the bytes read. Is this correct?

[Tom Estes]

I am not familiar with the DS18S20 but a quick look at the data sheet shows the CRC is calculated by reading all 8 bytes of the scratchpad memory, running them through the CRC routine and comparing its output to the 9th byte read from the scratchpad which is the CRC value generated by the DS18S20. See example 3 in the datasheet.

[CocaColaKid]

I think I can now safely say I'm completely lost as this is making no sense to me. Do I calculate the CRC for each bit using bit0 ^ bit1... and then XOR all the bytes one at a time or do I just XOR the bytes themselves? Please excuse my lack of understanding as this is all new to me.

[Tom Estes]

You should read Dallas Application note #27 Understanding and using cyclic redundancy checks.

You will need to select one of the three provided crc8 routines and put that in your PBP program. You call it as a subroutine. Each routine does the same thing but take different amounts of time/different amounts of programming space doing it. These routines operate on a byte at a time not a bit at a time. They do the bit calculations for you.

Receive one byte from the device or more likely, you will have to receive all bytes that are included in the crc check and place them in appropriate variables or an array. Make the variable CRCData = the first byte then do a gosub to the name of the CRC subroutine. Do the same thing for the second byte, third, etc. After all the bytes have been passed through the CRC routine then the variable CRC will contain the crc value that should match the one sent from the device.

[taats]

Hi Tom,

I read your posts too about the CRC8, but i'm confused.
I have a divice connected to my COM1-port and I want to read the information the device sends. This device demands the CRC8-protocol is used.

the form of communications is like this:
=====
functioncode(1 byte), number of data-bytes(2 bytes),data(x byte),checkbyte(1 byte)
=====

i'm doing my project in Visual Basic 6.0.

the sub has this code in it right now. this doesn't work... have got any ideas?? or anyone else?


=====

Private Sub CRC8(ByRef data() As Variant)
'--------------------------------------------------------------------------
' Function : (Private) CRC8
' Description : computes a 1 byte checksum using bytes 1 to 7 of the
' Header 8-byte array (Protocol Header)
'
' Parameter : Data ()As Byte | each byte group is assumed to be High byte first, Low byte last
' Return Value : CRC8 as Byte | CRC value
'--------------------------------------------------------------------------
Dim crc As Byte
Dim Length As Byte
Dim Index As Byte
Dim CRCtable1() As Variant
crc = 0
Length = 1
CRCtable1 = Array( _
&H0, &H7, &HE, &H9, &H1C, &H1B, &H12, &H15, &H38, &H3F, &H36, &H31, &H24, &H23, &H2A, &H2D, &H70, &H77, &H7E, &H79, &H6C, &H6B, &H62, &H65, &H48, &H4F, &H46, &H41, &H54, &H53, &H5A, &H5D, _
&HE0, &HE7, &HEE, &HE9, &HFC, &HFB, &HF2, &HF5, &HD8, &HDF, &HD6, &HD1, &HC4, &HC3, &HCA, &HCD, &H90, &H97, &H9E, &H99, &H8C, &H8B, &H82, &H85, &HA8, &HAF, &HA6, &HA1, &HB4, &HB3, &HBA, &HBD, _
&HC7, &HC0, &HC9, &HCE, &HDB, &HDC, &HD5, &HD2, &HFF, &HF8, &HF1, &HF6, &HE3, &HE4, &HED, &HEA, &HB7, &HB0, &HB9, &HBE, &HAB, &HAC, &HA5, &HA2, &H8F, &H88, &H81, &H86, &H93, &H94, &H9D, &H9A, _
&H27, &H20, &H29, &H2E, &H3B, &H3C, &H35, &H32, &H1F, &H18, &H11, &H16, &H3, &H4, &HD, &HA, &H57, &H50, &H59, &H5E, &H4B, &H4C, &H45, &H42, &H6F, &H68, &H61, &H66, &H73, &H74, &H7D, &H7A, _
&H89, &H8E, &H87, &H80, &H95, &H92, &H9B, &H9C, &HB1, &HB6, &HBF, &HB8, &HAD, &HAA, &HA3, &HA4, &HF9, &HFE, &HF7, &HF0, &HE5, &HE2, &HEB, &HEC, &HC1, &HC6, &HCF, &HC8, &HDD, &HDA, &HD3, &HD4, _
&H69, &H6E, &H67, &H60, &H75, &H72, &H7B, &H7C, &H51, &H56, &H5F, &H58, &H4D, &H4A, &H43, &H44, &H19, &H1E, &H17, &H10, &H5, &H2, &HB, &HC, &H21, &H26, &H2F, &H28, &H3D, &H3A, &H33, &H34, _
&H4E, &H49, &H40, &H47, &H52, &H55, &H5C, &H5B, &H76, &H71, &H78, &H7F, &H6A, &H6D, &H64, &H63, &H3E, &H39, &H30, &H37, &H22, &H25, &H2C, &H2B, &H6, &H1, &H8, &HF, &H1A, &H1D, &H14, &H13, _
&HAE, &HA9, &HA0, &HA7, &HB2, &HB5, &HBC, &HBB, &H96, &H91, &H98, &H9F, &H8A, &H8D, &H84, &H83, &HDE, &HD9, &HD0, &HD7, &HC2, &HC5, &HCC, &HCB, &HE6, &HE1, &HE8, &HEF, &HFA, &HFD, &HF4, &HF3 _
)
Do While Length < 7
Index = crc Xor data(Length)
crc = CRCtable1(Index)
Length = Length + 1
Loop
CHK8 = crc
End Sub

=====

thanks,

Taats

[Tom Estes]

I'm not a VB person, don't even own a copy to try your routine.

The routines I wrote were for the Dallas Semiconductor CRC8 check. Any other CRC routine may not work in the same manner. I note you changed the table entries which may be in a effort to fix this but that may not always work either. Some CRC routines calculate with a different poly or "reflected" or changed in other ways. You will need to find out the particulars of the CRC your device is sending.

If you are trying to emulate the Dallas 1wire CRC8 then the table values you have are incorrect.

[CocaColaKid]

Tom,

I finally have everything working properly. Thank you so very much for your help and understanding.

[taats]

after a couple of hours of hard work, i got it working now...

so thanks anyway!!,

Taats

[CocaColaKid]

Is there an easier way to do this?

owin portb.7,0,[data_in[0], data_in[1], data_in[2], data_in[3], data_in[4], data_in[5], data_in[6], data_in[7], data_in[8]]

[Tom Estes]

Using other 1wire devices I have been able to do the following:

' Read the next 32 bytes, calculate running CRC but discard the bytes
For Index = 1 to 32
OWIn OWPort, 0, [CRCData]
GoSub CRC
Next Index
OWIn OWPort,0,[DesiredData]
CRCData = DesiredData
GoSub CRC

In other words there may be enough time in between data bytes sent from the 1 wire device to calculate the CRC on a running basis. If you don't need all the data the CRC can be calculated and the data discarded, retaining only that data you need.

[CocaColaKid]

I was wondering if that would actually work or not. This is my final line. Again thanks for all your help.

    for x = 0 to 8
    owin portb.7,0,[i]
    dq[x] = i
    next x

[Norbert]

Found an error in the CRC8LU subroutine when validating CRC byte after doing a 1-wire search.
A CRC of $F0 on a device returns an error.
This is because of a typo in Tom's code, the value 140 highlighted in red in the quote below is incorrect.
From the table of Example 3 in Dallas AN27, the value here should be 240.

Norbert

Three different PBP programs to calculate the Dallas 8bit CRC.
....

' ********** Subroutine CRC8LU **********
' Expects CRC at some starting value with data to CRC
' passed in CRCData.
' Gives ending CRC value and destroys CRCData
' Uses CRCData-Byte, CRC-Byte
CRC8LU:
CRCData = CRCData ^ CRC
Lookup CRCData, [0,94,188,226,97,63,221,131,194,156,126,32,163,253, 31,65,_
157,195,33,127,252,162,64,30,95,1,227,189,62,96,13 0,220,_
35,125,159,193,66,28,154,160,225,191,93,3,128,222, 60,98,_
190,224,2,92,223,129,99,61,124,34,192,158,29,67,16 1,255,_
70,24,250,164,39,121,155,197,132,218,56,102,229,18 7,89,7,_
219,133,103,57,186,228,6,88,25,71,165,251,120,38,1 96,154,_
101,59,217,135,4,90,184,230,167,249,29,69,198,152, 122,36,_
248,166,68,26,153,199,37,123,58,100,134,216,91,5,2 31,185,_
140,210,48,110,237,179,81,15,78,16,242,172,47,113, 147,205,_
17,79,173,243,112,46,204,146,211,141,111,49,178,23 6,14,80,_
175,241,19,77,206,144,114,44,109,51,209,143,12,82, 176,238,_
50,108,142,208,83,13,239,177,140,174,76,18,145,207,45,115,_
202,148,118,40,171,245,23,73,8,86,180,234,105,55,2 13,139,_
87,9,235,181,54,104,138,212,149,203,41,119,244,170 ,72,22,_
233,183,85,11,136,214,52,106,43,117,151,201,74,20, 246,168,_
116,42,200,150,21,75,169,247,182,232,10,84,215,137 ,107], CRC
' PBP only handles 255 constants in the list (256 for 18Cxxx). Since table is
' indexed starting at zero, special case for $FF (256th element).
If CRCData = $FF Then
CRC = 53
EndIF
Return

[Charlie]

found 2 more typos for total of 3...

line with 35,125,159,193,66,28,"154", Dallas has 254
line with 101,59,217,135,4,90,184,230,167,249,"29", Dallas has 27
line with 50,108,142,208,83,13,239,177,"140", but Dallas example is 240 (as noted above)

[Mike, K8LH]

Has anyone ever converted Scott Dattalo's method (1-Wire Polynomial) to PBP?

;
;  Scott Dattalo's version (20 words, 23 cycles per byte)
;
crc_8
        xorwf   CRC,F           ;
        clrw                    ;
        btfsc   CRC,0           ;
        xorlw   0x5E            ; 
        btfsc   CRC,1           ; 
        xorlw   0xBC            ; 
        btfsc   CRC,2           ; 
        xorlw   0x61            ; 
        btfsc   CRC,3           ; 
        xorlw   0xC2            ; 
        btfsc   CRC,4           ; 
        xorlw   0x9D            ; 
        btfsc   CRC,5           ;
        xorlw   0x23            ; 
        btfsc   CRC,6           ; 
        xorlw   0x46            ; 
        btfsc   CRC,7           ; 
        xorlw   0x8C            ; 
        movwf   CRC             ; 
        return                  ;

It seems like a pretty good compromise between size and performance.

Regards, Mike

[Ioannis]

If your concern is size and speed, why not use it as is with he addition of _ before CRC variable (_CRC)?

I think it will work just fine.

Ioannis

[Mike, K8LH]

If your concern is size and speed, why not use it as is with he addition of _ before CRC variable (_CRC)?

I think it will work just fine.

Hi Ioannis:

Since the Dattalo method wasn't mentioned in the thread, I simply wanted to pass it along, hoping it might be useful or helpful to PBP users. I'm afraid I don't know how you would implement it in PBP.

While I've tried all of the methods discussed in this thread in the past, now days in my C programs I use bit level cumulative CRC built into my low level 1-Wire read/write bit driver. Total cost for doing it this way is 8 words of program memory, 1 byte of RAM, and 0 cycles processing overhead since the CRC code executes during a portion of the delay required to fill out the 60 usec read slot timing.

Cheerful regards, Mike

[Ioannis]

Hmm, yes I see what you mean. In Basic this does not seem an easy job to do.

I will try it and see if it works.

Ioannis

[Ioannis]

My main concern is how to save the W register and then restore it.

I tried

MOVW _wsave

but did not compile.

Ioannis

[SteveB]

My main concern is how to save the W register and then restore it.

I tried

MOVW _wsave

but did not compile.

Ioannis

The command would be: movwf

Here is a quick attempt at converting the asm to PBP. Note that this is not the most efficeint/elegant conversion, but it should be a bit clearer was to what's happening.

crc VAR BYTE
i_w VAR BYTE

goto start                  

crc_8:
   crc = i_w ^ crc        ;xorwf crc,f
   i_w = 0                   ;clrw

   IF crc.0 = 1 THEN     ;btfsc crc,0
      i_w = i_w ^ $5E    ;xorlw 0x5e
      END IF
   IF crc.1 = 1 THEN     ;btfsc crc,0
      i_w = i_w ^ $BC    ;xorlw 0xbc
      END IF
   IF crc.2 = 1 THEN     ;btfsc crc,0
      i_w = i_w ^ $61    ;xorlw 0x61
      END IF
   IF crc.3 = 1 THEN     ;btfsc crc,0
      i_w = i_w ^ $C2    ;xorlw 0xc2
      END IF
   IF crc.4 = 1 THEN     ;btfsc crc,0
      i_w = i_w ^ $9D    ;xorlw 0x9d
      END IF
   IF crc.5 = 1 THEN     ;btfsc crc,0
      i_w = i_w ^ $23    ;xorlw 0x23
      END IF
   IF crc.6 = 1 THEN     ;btfsc crc,0
      i_w = i_w ^ $46    ;xorlw 0x46
      END IF
   IF crc.7 = 1 THEN     ;btfsc crc,0
      i_w = i_w ^ $8C    ;xorlw 0x8c
      END IF

   crc = i_w             ;movwf crc
RETURN

start:
 crc = 0                    ;clrf crc
 i_w = 1                    ;movlw 1
 GOSUB crc_8            ;call  crc_8

 crc = 0                    ;clrf crc
 i_w = 2                    ;movlw 2
 GOSUB crc_8            ;call  crc_8
 
 crc = 0                    ;clrf crc
 i_w = 4                    ;movlw 4
 GOSUB crc_8            ;call  crc_8

 crc = 0                   ;clrf crc
 i_w = 8                   ;movlw 8
 GOSUB crc_8            ;call  crc_8

 crc = 0                   ;clrf crc
 i_w = $10                ;movlw 0x10
 GOSUB crc_8            ;call  crc_8

 crc = 0                   ;clrf crc
 i_w = $20                ;movlw 0x20
 GOSUB crc_8            ;call  crc_8

 crc = 0                   ;clrf crc
 i_w = $40                ;movlw 0x40
 GOSUB crc_8            ;call  crc_8

 crc = 0                   ;clrf crc
 i_w = $80                ;movlw 0x80
 GOSUB crc_8            ;call  crc_8
END

[languer]

This is a translation for another basic compiler:
Function crc_dattalo(crc As Byte, crc_data As Byte) As Byte

'dattalo's CRC-8 Function
'(328_Tcy / 41.0_us)
    Dim i As Byte
    i = crc_data Xor crc
    i = i And 0xff
    crc = 0
    If i.0 = 1 Then
        crc = crc Xor 0x5e
    Endif
    If i.1 = 1 Then
        crc = crc Xor 0xbc
    Endif
    If i.2 = 1 Then
        crc = crc Xor 0x61
    Endif
    If i.3 = 1 Then
        crc = crc Xor 0xc2
    Endif
    If i.4 = 1 Then
        crc = crc Xor 0x9d
    Endif
    If i.5 = 1 Then
        crc = crc Xor 0x23
    Endif
    If i.6 = 1 Then
        crc = crc Xor 0x46
    Endif
    If i.7 = 1 Then
        crc = crc Xor 0x8c
    Endif
    crc_dattalo = crc
End Function

Some additional info and comparison between three different approaches: http://www.ccsinfo.com/forum/viewtop...015&highlight=

[Mike, K8LH]

Even though I'm not a PBP developer, I've always enjoyed exchanging ideas and experiences with members here. That said, I wonder if anyone is interested in my zero overhead CRC8 method, even if it isn't a PBP example?

In my zero overhead CRC8 method I use a portion of the 60-usec read/write 'slot' time to implement CRC8 at the bit level within the OneWire read bit routine. Here's the tail end of a read bit routine from code for an enhanced mid-range 16F device;

;
;  bit level cumulative CRC (data bit in Carry at entry & exit)
;
        clrf   WREG             ;                                 |00
        rlf    WREG,W           ; save C in wreg (0x00 or 0x01)   |00
        xorwf  crc,F            ; xor b0 bits, result in 'crc'    |00
        rrf    crc,F            ; is xor result 0 (Carry = 0)?    |00
        skpnc                   ; yes, skip, else                 |00
        iorlw  0x18             ; w = x8+x5+x4+1 poly and bit 0   |00
        rrf    WREG,W           ; restore C, wreg = 0x8C or 0x00  |00
        xorwf  crc,F            ; apply the polynomial or not     |00
;
;  remainder of 60-usec read/write 'slot'
;
        DelayCy(46*usecs-14)    ; 46-usecs minus 14 cycles        |00
        banksel owtris          ; bank 1                          |01
        bsf     owtris,owpin    ; output hi-z '1' @ 61-usecs      |01
        banksel 0               ; bank 0                          |00
        bsf     INTCON,GIE      ; interrupts on                   |00
        return                  ; Carry = data bit                |00

Using CRC in my DS18x20 programs is simply a matter of clearing the 'crc' variable before reading the 9 byte DS18x20 'scratchpad' or an 8 byte ROMID and verifying that the 'crc' variable equals zero afterwards. You must read all 9 'scratchpad' bytes to have a valid 'crc'. Just ignore or throw away the bytes you don't need.

I admit I have no idea if this method could be implemented in PBP with its intrinsic OneWire commands but I suspect you gurus will find a way to use it if you think the method is worthwhile.

Have fun. Cheerful regards, Mike (K8LH)