Sunday, February 19, 2012

Fast CRC16 in Z8 and Z80 Assembly

I was wondering how few instructions does it really take to update the value of a 16 bit CRC, given an input character, on Zilog's Z8/eZ8 and Z80 architectures. As it turns out, it's only 6 instructions on Z8, and 8 fast instructions on Z80. If you want to preserve the input character, there's an extra load involved (not shown).

The precomputed CRC table must be specially formatted as described below, but first -- the code.

; Z8/eZ8/Encore! architecture
; _crc_table - crc table, 512 bytes long, see text
; RR12 (in/out) - crc to be updated
; R1 (in/out) - input character, clobbered
; R0 (out) - clobbered

ld   r0, #high(_crc_table) ; table is aligned to 256 bytes
xor  r1, r13    ; RR0 = crc_table + (data ^ crc.l)

ldc  r13, @rr0  ; crc.l = crc_table[].l
xor  r13, r12   ; crc.l = crc.h ^ crc_table[].l
inc  r0
ldc  r12, @rr0  ; crc.h = crc_table[].h

; Z80 architecture
; _crc_table - crc table, 512 bytes long, see text
; BC (in/out) - crc to be updated
; A (in/out) - input character, clobbered
; HL (out) - clobbered

ld  H, high(_crc_table)
xor C
ld  L, A        ; HL = crc_table + (data ^ crc.l)

ld  A, B        ; A = crc.h
xor (HL)        ;     crc.h ^ crc_table[].l
ld  C, A        ; crc.l = crc.h ^ crc_table[].l
inc H
ld  B, (HL)     ; crc.h = crc_table[].h

If anyone knows how to do it any faster on Z80, let me know. I last used Z80 15+ years ago. The instructions used are all fast (1-1.5us @4MHz) IIRC.

The precomputed CRC table is generated using Rocksoft^tm Model CRC Algorithm Table Generation, with 2 byte width, and reverse set to true. The table must be aligned at the 256 byte boundary -- its address's LSB must be equal to 0. The table is stored in the code memory on the Harvard architecture Z8 family. The formatting of the table as used by the assembly routine is different than nominal, though. The required formatting is such that each word element of the table is split, and LSBs are grouped in the first 256 bytes of the table, followed by MSBs in the following 256 bytes of the table. This allows the entire calculation of the address for table lookup to be so efficient (only 2-3 instructions).

A C program reformatting the table as necessary is shown below.

unsigned char input_table[512];
unsigned char output_table[512];

// big endian version (Z8/eZ8/Encore!)
for (int i = 0; i < 255; ++i) {
  output_table[i] = input_table[i*2 + 1]; // LSB
  output_table[256+i] = input_table[i*2 + 0]; // MSB

// little endian version (Z80)
for (int i = 0; i < 255; ++i) {
  output_table[i] = input_table[i*2 + 0]; // LSB
  output_table[256+i] = input_table[i*2 + 1]; // MSB

No comments:

Post a Comment