On Fri, 23 Aug 2002, Tony K|bek wrote:

> Hi,
> Scott wrote:
> <snip>
> >It's probably clear from the comments how it works. :)
>
> as crystal :)

Then this oughta cloud things up:

;----------------------------------------------------------------------
; CRC_Update Subroutine
;
; Optimized 16-bit CRC routine for the polynomial 0x8005 - reversed
; Inspired by Dave Dribin.
;
; The algorithm for computing a 16-bit CRC using nibble tables
; can be generically described. Suppose the 16-bit is described
; by:
;
;  CRC = STUV
;
; Where S, T, U, and V are the 4 nibbles of the CRC.
;
; And suppose the next byte in the message stream is
;
; Message byte = PQ
;
; Where P and Q are the nibbles.
;
; In this algorithm there are two tables (or arrays); one for the high
; byte and one for the low byte of the CRC. Each table is 16 bytes long
; and indexed by the lowest nibble of the current CRC value like so:
;
; Index = V ^ Q
;
; The CRC is shifted right 4 bit positions and the elements from the high
; and low byte tables are exclusive ored to create the new CRC:
;
; Shift right 4 ( CRC = CRC >> 4 )
;  CRC  = 0STU
;
;   YZ = TU ^ CRC_TableLow[Index];
;   WX = 0S ^ CRC_TableHigh[Index];
;
; Where WXYZ is the new CRC value.
;
; This step needs to be repeated once more for the second nibble
; of the message byte:
;
; Index = Z ^ P    ; This time the high nibble of the message is used
;
; CRC = 0WXY       ; Shift the CRC right 4 positions
;
;   New Low byte  = XY ^ CRC_TableLow[Index];
;   New High byte = 0W ^ CRC_TableHigh[Index];
;
; and we're done!
;
; Now, it's possible to collapse many of these XOR operations into
; just a few steps. Before doing that, let's make a few observations.
;
; The computed Index is used to access a byte from the low and high
; tables at each step. Combine these bytes and into a 16-bit word
; and express them in terms of nibbles:
;
;   A1 B1 C1 D1  => A1,B1 are the nibbles of the high byte
;                   and C1,D1 are the nibbles of the low byte
;
; the '1' refers to the first access of the table.
;
; The second access is:
;
;   A2 B2 C2 D2
;
; Now we can re-express the algorithm as:
;
;  Index = V ^ Q   ; low nibble of crc and message byte
;  A1 B1 C1 D1 = CRC_table[Index];
;  WXYZ  = 0STU ^ A1 B1 C1 D1;
;
;  Index = Z ^ P   ; low nibble of crc and high nibble of message
;  A2 B2 C2 D2 = CRC_table[Index];
;  STUV  = 0WXY ^ A2 B2 C2 D2
;
; Ignoring the index computation for a moment, we can collapse
; the two 16-bit exclusive or operations:
;
;  STUV = 00ST ^ (0 A1 B1 C1) ^ (A2 B2 C2 D2)
;
; Or in terms of nibbles:
;
;  V = T ^ C1 ^ D2
;  U = S ^ B1 ^ C2
;  T = A1 ^ B2
;  S = A2
;
; Now we need to calculate the Nibbles for Ai - Di. This is where it
; becomes necessary to analyze the CRC Polynomial. Dave Dribin has
; shown that the nibble indexed tables for the low and high bytes
; are:
;
; CRC16_LookupLow[16]  = { 0x00,0x01,0x01,0x00,0x01,0x00,0x00,0x01,
;                          0x01,0x00,0x00,0x01,0x00,0x01,0x01,0x00};
; CRC16_LookupHigh[16] = { 0x00,0xCD,0xD9,0x14,0xF1,0x3C,0x28,0xE5,
;                          0xA1,0x6C,0x78,0xB5,0x50,0x9D,0x89,0x44};
;
;Observation 1
;  C, the high nibble of the low byte, is always 0.
;Observation 2
;  D, the low nibble of the low byte, is either 0 or 1. Also, the
; lsb of D is equal to the MSB of A.
;
; If we express the nibble that indexes into the table as:
;
;  Index = abcd, abcd are the individual bits of the Index nibble,
; then with a little effort you can see that the bits of A, the
; high nibble of the high byte, can be expressed as:
;
;  bit3 = a^b^c^d
;  bit2 = b^c^d
;  bit1 = a^b
;  bit0 = b^c
;
; Similarly, B, the low nibble of the high byte can be expressed as:
;
;  bit3 = c^d
;  bit2 = d
;  bit1 = 0
;  bit0 = 0
;
;
; Okay, that should be enough background to enable writing the code

CRC_Update:

        XORWF   CRC16_Low,w     ;UV^PQ - The next message byte and the
        MOVWF   Temp            ;current crc xor'd for the indexes into
                                ;the tables
        MOVF    CRC16_High,W    ;Shift the CRC right 8 bits, i.e.
        MOVWF   CRC16_Low       ;UV = ST
                                ;
        CLRW                    ;Build CRC_TableHigh from Index1
        BTFSC   Temp,0          ;From the description above, we're
         MOVLW  0xcc            ;forming the A1 B1 byte. However,
        BTFSC   Temp,1          ;as a little twist, we actually
         XORLW  0x8d            ;form B1 A1 since we need to shift
        BTFSC   Temp,2          ;this right 4 bits before xor'ing
         XORLW  0x0f            ;
        BTFSC   Temp,3          ;
         XORLW  0x0a            ;
                                ;
        MOVWF   CRC16_High      ;Set the high byte to B1 A1
        ANDLW   0xf0            ;grab B1
        XORWF   CRC16_High,f    ;Remove it from the high byte (now 0 A1)
        XORWF   CRC16_Low,f     ;and put it in the low byte
                                ;
        CLRW                    ;We need to grab the LSB of D1 (same as
msb
        BTFSC   CRC16_High,3    ;of A1) and xor it with the LSB of Index2.
         MOVLW  0xcc            ;
        BTFSC   Temp,4          ;Now we build CRC_TableHigh from Index2
         XORLW  0xcc            ;We basically do the same thing as
        BTFSC   Temp,5          ;above, but this time we build the
         XORLW  0xd8            ;nibbles in order: A2 B2
        BTFSC   Temp,6          ;
         XORLW  0xf0            ;
        BTFSC   Temp,7          ;
         XORLW  0xa0            ;
                                ;
        XORWF   CRC16_High,f    ;Now combine it with the high byte
        MOVLW   0x01            ;The lsb of D2 (same as msb of A2)
        BTFSC   CRC16_High,7    ;needs to be combined with the low
         XORWF  CRC16_Low,f     ;byte
        RETURN

--------------


Whew!

At least two instructions can be saved if we use the 18xxx parts.

Scott

--
http://www.piclist.com hint: To leave the PICList
mailto:piclist-unsubscribe-request@mitvma.mit.edu