[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

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

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

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

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

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

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.