CRC Calculations by Paul Guertin
[Up to Source Code Repository]

CRC Calculations

How to compute a CRC error detecting code in 6502 assembly.
By Paul Guertin (pg@sff.net), 18 August 2000.

a. CRC-16 (CCITT version)

Usage

1. Call MAKECRCTABLE to set up the CRCLO and CRCHI tables.
2. Initialize CRC and CRC+1 to $FF.
3. For each byte in the data, LDA it and call UPDCRC.
4. The CRC is in CRC (low byte) and CRC+1.

UPDCRC clobbers A and X. It can be easily changed to clobber Y instead of X or, at a performance cost, to preserve registers.

UPDCRC takes 22 cycles per byte if inlined and the tables are page-aligned.

We initialize the CRC to $FFFF instead of zero so that the algorithm will react to null bytes at the beginning of a block of data.

CRC      EQU $6          ; 2 bytes in ZP
CRCLO    EQU $8000       ; Two 256-byte tables for quick lookup
CRCHI    EQU $8100       ; (should be page-aligned for speed)

MAKECRCTABLE:
         LDX #0          ; X counts from 0 to 255
BYTELOOP LDA #0          ; A contains the low 8 bits of the CRC-16
         STX CRC         ; and CRC contains the high 8 bits
         LDY #8          ; Y counts bits in a byte
BITLOOP  ASL
         ROL CRC         ; Shift CRC left
         BCC NOADD       ; Do nothing if no overflow
         EOR #$21        ; else add CRC-16 polynomial $1021
         PHA             ; Save low byte
         LDA CRC         ; Do high byte
         EOR #$10
         STA CRC
         PLA             ; Restore low byte
NOADD    DEY
         BNE BITLOOP     ; Do next bit
         STA CRCLO,X     ; Save CRC into table, low byte
         LDA CRC         ; then high byte
         STA CRCHI,X
         INX
         BNE BYTELOOP    ; Do next byte
         RTS

UPDCRC:
         EOR CRC+1       ; Quick CRC computation with lookup tables
         TAX
         LDA CRC
         EOR CRCHI,X
         STA CRC+1
         LDA CRCLO,X
         STA CRC
         RTS

         JSR MAKECRCTABLE
         LDY #$FF
         STY CRC
         STY CRC+1
         INY
LOOP     LDA $1000,Y
         JSR UPDCRC
         INY
         BNE LOOP
         RTS

b. CRC-32

Usage

1. Call MAKECRCTABLE to set up the CRCT0 through CRCT3 tables.
2. Initialize CRC, CRC+1, CRC+2, CRC+3 to $FF.
3. For each byte in the data, LDA it and call UPDCRC.
4. Exclusive-or each of CRC, CRC+1, CRC+2, CRC+3 with $FF.
5. The CRC is in CRC (low byte) through CRC+3.

UPDCRC clobbers A and X. It can be easily changed to clobber Y instead of X or, at a performance cost, to preserve registers.

UPDCRC takes 42 cycles per byte if inlined and the tables are page-aligned.

Why complement the result? Because the CRC-32 standard says so. I guess it made things easier for with hardware compatibility, and now we're stuck with it.

CRC      EQU $6          ; 4 bytes in ZP
CRCT0    EQU $8000       ; Four 256-byte tables
CRCT1    EQU $8100       ; (should be page-aligned for speed)
CRCT2    EQU $8200
CRCT3    EQU $8300

MAKECRCTABLE:
         LDX #0          ; X counts from 0 to 255
BYTELOOP LDA #0          ; A contains the high byte of the CRC-32
         STA CRC+2       ; The other three bytes are in memory
         STA CRC+1
         STX CRC
         LDY #8          ; Y counts bits in a byte
BITLOOP  LSR             ; The CRC-32 algorithm is similar to CRC-16
         ROR CRC+2       ; except that it is reversed (originally for
         ROR CRC+1       ; hardware reasons). This is why we shift
         ROR CRC         ; right instead of left here.
         BCC NOADD       ; Do nothing if no overflow
         EOR #$ED        ; else add CRC-32 polynomial $EDB88320
         PHA             ; Save high byte while we do others
         LDA CRC+2
         EOR #$B8        ; Most reference books give the CRC-32 poly
         STA CRC+2       ; as $04C11DB7. This is actually the same if
         LDA CRC+1       ; you write it in binary and read it right-
         EOR #$83        ; to-left instead of left-to-right. Doing it
         STA CRC+1       ; this way means we won't have to explicitly
         LDA CRC         ; reverse things afterwards.
         EOR #$20
         STA CRC
         PLA             ; Restore high byte
NOADD    DEY
         BNE BITLOOP     ; Do next bit
         STA CRCT3,X     ; Save CRC into table, high to low bytes
         LDA CRC+2
         STA CRCT2,X
         LDA CRC+1
         STA CRCT1,X
         LDA CRC
         STA CRCT0,X
         INX
         BNE BYTELOOP    ; Do next byte
         RTS

UPDCRC:
         EOR CRC         ; Quick CRC computation with lookup tables
         TAX
         LDA CRC+1
         EOR CRCT0,X
         STA CRC
         LDA CRC+2
         EOR CRCT1,X
         STA CRC+1
         LDA CRC+3
         EOR CRCT2,X
         STA CRC+2
         LDA CRCT3,X
         STA CRC+3
         RTS

         JSR MAKECRCTABLE
         LDY #$FF
         STY CRC
         STY CRC+1
         STY CRC+2
         STY CRC+3
         INY
LOOP     LDA $1000,Y
         JSR UPDCRC
         INY
         BNE LOOP
         LDY #3
COMPL    LDA CRC,Y
         EOR #$FF
         STA CRC,Y
         DEY
         BPL COMPL
         RTS

c. CRC-8

Usage

1. Call MAKECRCTABLE to set up the CRCTBL table.
2. Initialize CRC to $00
3. For each byte in the data, LDA it and call UPDCRC.
4. The CRC is in CRC.

The 8-bit variety of the CRC is rarer than CRC-32 or CRC-16. From what I've found on the Web, its polynomial is x^8 + x^2 + x + 1, which is $07 in hex, and it initializes the CRC to zero instead of $FF.

UPDCRC clobbers A and X. It can be easily changed to clobber Y instead of X or, at a performance cost, to preserve registers.

The CRC calculation takes 10 cycles per byte if inlined as in the example.

CRC      EQU $6          ; 1 byte in ZP (unneeded if you inline)
CRCTBL   EQU $8000       ; One 256-byte table for quick lookup

MAKECRCTABLE:
         LDX #0
BYTELOOP TXA             ; A contains the CRC-8
         LDY #8
BITLOOP  ASL             ; Shift CRC left
         BCC NOADD       ; If no overflow, do nothing
         EOR #$07        ; else add CRC-8 polynomial $07
NOADD    DEY
         BNE BITLOOP     ; Do next bit
         STA CRCTBL,X    ; All bits done, store in table
         INX
         BNE BYTELOOP    ; Do next byte
         RTS

UPDCRC:
         EOR CRC         ; You really should inline this,
         TAX             ; in which case you don't even need
         LDA CRCTBL,X    ; the CRC zero page location. See
         STA CRC         ; example below.
         RTS

         JSR MAKECRCTABLE
         LDY #0
         TYA             ; Initialize CRC
LOOP     EOR $1000,Y     ; EOR old CRC with data
         TAX             ; and index into table
         LDA CRCTBL,X    ; to get the new CRC
         INY
         BNE LOOP
         RTS             ; Accumulator contains the CRC-8