Hello all, I was browsing the source code repository and remembered I had written a fast CRC routine a few years ago. So I thought I would contribute it, as it might come in useful for anyone developing TCP/IP stacks etc.

These routines are entered with the next byte of data in A and the current CRC in zero page memory. For the first byte of data CRCLO and CRCHI should contain $FF, and in the case of CRC8, CRC should contain $00. On exit A is clobbered and the updated CRC is in the zero page locations.

All code below is relocatable. Sizes and execution times listed do not include the final RTS, and code is assumed to be page-aligned.

The following routine implements a CRC-16 cycle in constant time, without tables.


36 bytes, 62 cycles, AXYP clobbered.

Alternative ending:

39 bytes, 66 cycles, AXP clobbered, Y preserved.

With a starting CRC of $FFFF, the binary string $01 $02 $03 $04 should evaluate to $89C3.

For comparison, a shorter routine can be derived from Paul Guertin's MAKECRCTABLE in the repository:


24 bytes, 128..256 cycles, AXP clobbered

* * *

Here is a CRC-8 routine in near-constant time where memory constraints do not permit tables:


20 bytes, 25..27 cycles, AP clobbered, XY preserved.

With a starting CRC of $00, the binary string $01 $02 $03 $04 should evaluate to $E3.

Variations:
a) If the application demands constant time then BCC *+2 ($90 $00) can be inserted at UP1 and UP2:
24 bytes, 31 cycles.

b) Making a loop from the repeated code is barely worth one's while:
18 bytes, 36..38 cycles, AXP clobbered, Y preserved.

Greg,

Thanks for the submission. I've added it to the Source Code Repository.

Best Regards,
Mike

_________________
- Mike Naberezny (mike@naberezny.com) http://6502.org

Thanks Mike, it's much appreciated.

Greg

I have also written some optimised code for the widely-used ARC algorithm. It has to calculate the parity of an intermediate result, and various parity algorithms can do this in 10 bytes of code or 10 cycles, so code size and speed can be traded-off over a broad range.

Here's one (quoted from a previous post)

Noting that:

1) A simple arithmetic sum of two bits is the same as XORing them.
2) You can propagate bits through a word using carries.

like so:

d00a
0111

and the sum has a xor d in the d bit position



You can collect the bits of a word and XOR them together (generate parity for the word)
at the same time

like so (pseudo assember):


and end up with the parity in the high bit.

If you want to XOR bits across more than one byte you just have to start with the bytes
XORed together in WORD

13 bytes and 16 cycles - nice! It may beat quite a few algorithms in the table (you can sometimes get in a mindlock that a bit shift == a string of LSRs etc.) so I'd like to replace them with this fragment - attributed of course. Thanks.

I've looked at this, and even tried to work it out on paper when I got the chance at work. But I just don't see how this works. The ASL causes bit 7 of the A register to be put into the carry, so it *seems* to me that bit 7 is not properly taken into account. Can anyone please demonstrate how this really works, as it appears I'm a bit thick-headed in grokking this at the moment. Thanks.

I've looked at this, and even tried to work it out on paper when I got the chance at work. But I just don't see how this works. The ASL causes bit 7 of the A register to be put into the carry, so it *seems* to me that bit 7 is not properly taken into account.[/quote]

The EOR uses bit 7, so it is still in there.

There are two tricks being used here. First, you can XOR bits by adding them. Second, you can move a bit into another position by adding it to a string of 1s. This code is doing both in the same instruction.

What we want is the XOR of all 8 bits. The ASL and EOR XOR adjacent bits, so we have the result of four pairs: AxBxCxDx. The AND removes the x bits: A0B0C0D0.

Then add 3 to B and D. If they were 0, this won't affect A and C. If they were 1, A or C will toggle. Now A and C are each the XOR of four bits.

The next AND clears everything but those two, then the final ADC adds C into A, toggling it if C was 1. That's the result we need.

Delightfully clever.