Skip to main content

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
}


Comments

Popular posts from this blog

Both INCLUDEPATH and DEPENDPATH are usually needed in qmake .pro project files.

qmake, the build tool provided with the Qt toolkit, converts project files written in its own mini-language to platform-specific Makefiles.

This process includes adding necessary dependencies to the Makefile, so that changes in source files trigger rebuilding of the outputs that depend on said sources.

If your project is spread across directories, you'll likely add an INCLUDEPATH line to your .pro file so that the #include directives look sane -- say #include "library/foo.h" instead of #include "../library/foo.h". This can be done by adding INCLUDEPATH += "../" to the .pro project file.

This, by itself, doesn't cause the files in include directories to be treated as dependencies. This is a sane default, since you likely don't want to rebuild your whole project if a system library changes -- assuming, of course, that the library is meant to stay binary compatible between releases!

Thus, if any of your source files references a file from somewhe…

Asterisk 1.8 with SELinux on RHEL 6 / CentOS 6

Asterisk 1.8 is the current long term support (LTS) version of Asterisk. You can find it in the atrpms repository. Using atrpms requires a bit of ingenuity, since you must enable yum priorities. Here's how I've set up my yum priorities and excludes to play well with RHEL (lower priority is higher):

# /etc/yum/pluginconf.d/rhnplugin.conf
priority = 9

# files in /etc/yum/repos.d - current samba and subversion override those of RHEL
sernet-samba - 5
wandisco - 6
rhnplugin - 9
centos-base - 20, includepkgs=xfs* fftw-* glpk-* dell-firmware-repository - 30 dell-omsa-repository - 30 rpmforge-repo - 50, exclude=hdf5*
epel - 60, exclude=dahdi* atrpms - 70
I'm using a bunch of non-redhat packages, including Asterisk, recent subversion, octave, xfs tools, and Dell server management tools.

For Asterisk proper, I'm running an AGI caller id script, and a fax receiving script. The fax script uses cups to print. Those scripts require exceptions to the targeted SELinux policy. Note that the polic…

Details of Migrating Zimbra 6 to Zimbra 8

I have a small Zimbra system that needed to be migrated from 6.0 to 8.0. Generally:
You must update to 6.0.16 on the source system. The account export functionality is broken in versions prior to 6.0.15 and will fail on some accounts.Start with a fresh 8.0 install. On a small system (dozens of users), that seems like the simplest option.Keep the 6.0 system running. Use the migration wizard in 8.0's admin console (Tools & Migration -> Account Migration) to move over account records only.
Set "type of mail server" to Zimbra Collaboration Suite. Set "would you like to import mail" to No.Import from another Zimbra LDAP directory.Set the LDAP Search Base to "dc=foo,dc=com" where foo.com would be your domain. This saves work on manually moving accounts between systems.
To move account contents and filter settings between servers, you can do the following on the source server:
su - zimbra
ACCT=user@foo.com      # account to move
DEST=root@destination  # ss…