[Return to Main Page]

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.
Notes
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
Example: Computing the CRC-16 of 256 bytes of data in $1000-$10FF.
         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.
Notes
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
Example: Computing the CRC-32 of 256 bytes of data in $1000-$10FF.
         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.
Notes
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
Example: Computing the CRC-8 of 256 bytes of data in $1000-$10FF.
         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
Last page update: August 19, 1999.