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

Wednesday, February 01, 2012

MacPorts texlive Broken by zlib 1.2.6

It's this time of the year - zlib gets updated, and things break. I run texlive latex distribution from MacPorts, and a recent update to zlib (from 1.2.5 to 1.2.6) broke texlua. When trying to activate texlive packages,  mtxrun (executed by texlua) throws the following error:

texlua PANIC: unprotected error in call to Lua API (zlib library version does not match - header: 1.2.5, library: 1.2.6)

Thus, we have to downgrade to zlib 1.2.5. I'll presume you routinely clean your outdated ports, thus it's not a simple matter of deactivating zlib 1.2.6 and reactivating the old one. That's the price one pays on being a bit OCD with that. The root of the problem is, of course, that port clean outdated does not allow selecting packages whose replacements were installed before a certain date. You'd need that functionality to only clean up ports whose upgraded replacements have hung around for a bit to prove their worth.

First, we have to determine the ports repository revision where the port got updated. The simplest way is to go to the websvn interface for macports subversion, and look up zlib there. Thus we see that 1.2.6 came to be in rev 89487. We need a revision prior to that (89486).

It's assumed that you run bash as your shell. If you don't, simply run bash before running any of the commands below.

If don't have a private ports source tree, here's how you can create one in your home directory:

mkdir -p ports/archivers
echo file://$(pwd)/ports | cat /dev/stdin "$srcconf" > "$newconf"
sudo bash -c "cat $newconf > $srcconf"
rm "$newconf"

We then check out the old zlib, and reindex the tree:

cd ~/ports
svn co -r 89486 archivers/zlib

At that point, you're ready for the downgrade:

sudo port uninstall -f zlib
sudo port clean --all zlib
sudo port install zlib +universal

If you're not interested in a universal variant, you can skip '+universal'.

You'll want to reactivate texlive (and any related packages):

texlive=$(port installed | awk '/(texlive|texlive-[^ ]+)/ { print $1 }')
sudo port deactivate -f $texlive
sudo port activate $texlive