Checksum algorithms

By Grim.

A checksum is a number computed from an arbitrary block of data. This number can be used for detecting errors that may have been introduced during its transmission or storage. The integrity of the data can be checked at any later time by recomputing the checksum and comparing it with the stored one. If the checksums match, the data was likely not accidentally altered.

The procedure that yields the checksum from the data is called a checksum function or checksum algorithm. A good checksum algorithm will yield a different result with high probability when the data is accidentally corrupted; if the checksums match, the data has the same high probability of being free of accidental errors.

Checksum functions are often confused with Hashes or even Ciphers. They are all related but each one has its own uses and is designed differently.

Other posts in the series:

• Hash functions
• Cipher: AES-128 (coming soon on 64 NOPs!)

Hash Collision

No hashing method generates unique values. Hash collisions, the bogeyman of checksum and hash functions, will happen at some point. By a mathematical rule called the pigeonhole principle, you can’t uniquely map any possible data chunk to a shorter fingerprint. Statistically, there are multiple possible data that have the same hash.

By today’s standard, 16-bit checksum algorithms are considered weak (ie. prone to hash collision), but for 8-bit retrogramming, crc-16 and Fletcher-16 should be more than enough in most cases.

Benchmarks

Algorithm	Routine size (bytes)	Speed (K/s)
CRC-8 (unrolled)	62	17
CRC-16	32	8
CRC-32 (unrolled)	199	7.7
Fletcher-16	18	81.3

Cyclic Redundancy Checks

CRC-8 (Maxim/Dallas)

The CRC-8 routine is given for the sake of completeness. In practice, you will prefer using… well, anything else! :)

Understanding and Using Cyclic Redundancy Checks with Dallas Semiconductor iButton ProductsDownload

;; CRC-8 Maxim/Dallas checksum (unrolled)
;;
;; From Maxim/Dallas AP Note 27
;;
;; "Understanding and Using Cyclic Redundancy Checks with
;; Dallas Semiconductor iButton Products"
;;
;; Input:
;;  HL = DATA Pointer
;;  BC = DATA Length
;;
;; Output:
;;  A = CRC-8
;;  HL, D, BC and Flags modified

    ; CRC-8 ShiftXor
    MACRO CRC8XOR x
      rr d
      jr nc,$+4
        xor x
    MEND

crc8:
    xor a
    inc b
    dec bc
    inc c
_crc8
      xor (hl)
      ld d,a
      xor a

      CRC8XOR &5E
      CRC8XOR &BC
      CRC8XOR &61
      CRC8XOR &C2
      CRC8XOR &9D
      CRC8XOR &23
      CRC8XOR &46
      CRC8XOR &8C

      inc hl
      dec c
      jr nz,_crc8
      djnz _crc8

    ret

CRC-16 (CCITT)

;; CRC-16-CCITT checksum
;;
;; Poly: &1021
;; Seed: &FFFF
;;
;; Input:
;;  IX = Data address
;;  DE = Data length
;;
;; Output:
;;  HL = CRC-16
;;  IX,DE,BC,AF modified

crc16:
      ld hl,&FFFF
      ld c,8
_crc16_read
        ld a,h
        xor (ix+0)
        ld h,a
        inc ix
        ld b,c
_crc16_shift
        add hl,hl
        jr nc,_crc16_noxor
          ld a,h
          xor &10
          ld h,a
          ld a,l
          xor &21
          ld l,a
_crc16_noxor
        djnz _crc16_shift
        dec de
        ld a,d
        or e
        jr nz,_crc16_read
      ret

CRC-32

Also provided for the sake of completeness, CRC-32 is slow, even in full unrolled glory.

;; CRC-32 checksum (unrolled)
;;
;; Poly: &04C11DB7
;; Seed: &FFFFFFFF
;;
;; Input:
;;  IX = Data address
;;  BC = Data length
;;
;; Output:
;;  HLDE = CRC-32
;;  IX,BC,AF modified

    MACRO CRC32XOR x1,x2,x3,x4
      rr b
      jr nc,@nextBit
        ld a,e
        xor x1
        ld e,a
        ld a,d
        xor x2
        ld d,a
        ld a,l
        xor x3
        ld l,a
        ld a,h
        xor x4
        ld h,a
@nextBit
    MEND

crc32:
    ld hl,&FFFF
    ld d,h
    ld e,l
_crc32_loop
       ld a,(ix+0)
       inc ix
       push bc

       xor e
       ld b,a
       rr b
       jr c,_crc32_bit0
         ld e,d
         ld d,l
         ld l,h
         ld h,0
         jr _crc32_bit1

_crc32_bit0
         ld a,d
         xor &96
         ld e,a
         ld a,l
         xor &30
         ld d,a
         ld a,h
         xor &07
         ld l,a
         ld h,&77

_crc32_bit1
       CRC32XOR &2C,&61,&0E,&EE
       CRC32XOR &19,&C4,&6D,&07
       CRC32XOR &32,&88,&DB,&0E
       CRC32XOR &64,&10,&B7,&1D
       CRC32XOR &C8,&20,&6E,&3B
       CRC32XOR &90,&41,&DC,&76
       CRC32XOR &20,&83,&B8,&ED

       pop bc
       dec bc
       ld a,b
       or c
       jp nz,_crc32_loop

     dec b
     ; Final XOR value
     ; HLDE ^= &FFFFFFFF
     ld a,h
     xor b
     ld h,a
     ld a,l
     xor b
     ld l,a
     ld a,d
     xor b
     ld d,a
     ld a,e
     xor b
     ld e,a

     ret

;; Unit tests
;;
;; "Semilanceata" => &B78816DE
;; "Longueteau"   => &935384D5
;; "Severin"      => &E442806C
;; "Damoiseau"    => &95C8BAFA

Fletcher-16

• Author: John G. Fletcher
• Published: January 1982, “An Arithmetic Checksum for Serial Transmissions”. IEEE Transactions on Communications.
• Reference : Wikipedia – Fletcher’s checksum

;; Fletcher-16 checksum
;;
;; Input:
;;  HL = Data address
;;  BC = Data length
;;
;; Output:
;;  DE = Fletcher-16
;;  HL,BC,AF are modified

fletcher16:
     ; Initialize both sums to zero
     ld de,0
     ; Adjust 16-bit length for 2x8-bit loops
     inc b
     dec bc
     inc c
_fletcher16_loop
       ld a,(hl)
       inc hl
       ; sum1 += data
       add a,e
       ld e,a
       ; sum2 += sum1
       add a,d
       ld d,a
       dec c
       jr nz,_fletcher16_loop
       djnz  _fletcher16_loop
     ret

;; Unit tests
;;
;; "Semilanceata" => &B8C7
;; "Longueteau"   => &0D19
;; "Severin"      => &1BDC
;; "Damoiseau"    => &4098

Changelog

• 2020-11-07 – Recycled by MrEarwig