Parallel CRC16 Collection 2

Hello folks,

I recently posted a collection of byte-parallel CRC16 implementations and thought I'd add a few more.

Firstly, a 6800 version. Since I don't have the original BSI volume, I don't know exactly how it was coded then, but I vaguely remember it being about 26 instructions long. The 6800 version is actually shorter and faster than my 6809 version despite the 6809 being a far better CPU with better CPI and more registers. That's because I end up having to use 0 page for speed and that's still faster than stack indexing:

Crc16_6800: ;a:b=CRC, X^data.

;uses page 0 temp0, temp1, Len.
Crc16_6800Loop:
eora 0,x
staa temp1 ;hi now swapped
lsra
lsra
lsra
lsra
eora temp1
staa temp1

stab temp0
lsla
lsla
lsla
lsla
eora temp0
staa temp0
rorb
rorb
rorb
tba
anda #31
eora temp0
rorb
andb #0xe0
eorb temp1

inx
dec len
bne Crc16_6800Loop
rts

Next, the Hitachi H8 version. In this version, R0=CRC, R1^data, R2=Len. R3 is a temp. The H8 is interesting, because it was part of a 1990s generation of Microcontrollers designed for high-level languages like 'C'. Hitachi claimed it was RISC, though it isn't due to the excessive number of instruction formats and addressing modes. It's more like a 16-bit micro-controller version of the 68000 or pdp-11. The performance looks decent at 57 ø-clock cycles, but it isn't really that great because a ø-clock cycle is half the XTAL clock frequency, making it 114 XTAL oscillations per CRC byte.

Crc16_H8:

push r3

Crc16_H8Loop: ;start by pretending to swap.

mov.b @r1+,r3h ;get the next byte.

xor.b r3h,r0h ;

mov.b r0h,r3h ;need a copy.

shlr r3h

shlr r3h

shlr r3h

shlr r3h ; >>4

xor.b r3h,r0h ;

mov.b r0h,r3h ;copy again.

shll r3h

shll r3h

shll r3h

shll r3h ; <<4

xor.b r3h,r0l ;Into what was the low byte.

mov.b r0l,r3h

rotr r3h

rotr r3h

rotr r3h

mov.b r3h,r3l

and.b #31,r3l

xor.b r0h,r3l

and.b #0xe0,r3h

xor.b r0l,r3h

mov.w r3,r0

subs #1,r2

bne Crc16_H8Loop

pop r3

rts

So, let's compare that with the PIC I originally coded it for, a PIC16C55. This isn't the actual code, I don't have rights to that, so I've just rewritten the equivalent algorithm, and anyway, the version I used would probably have calculated the CRC on the fly, as each byte was received. Surprisingly, the humble PIC cpu (which predates Commerical RISC CPUs by a decade), manages to implement the algorithm in 25 instructions and 25 instruction cycles per byte, which works out as 100 clocks per byte.

Crc16_Pic16C55: ;pretend we've swapped.

movf ind,w ;got the next byte.

incf fsr

xorwf gCrc16+1,f ;xor with lo byte.

swap gCrc16,w ;copy and swap.

andlw 15 ;this is the >>4!

xorwf gCrc16+1,w ;'lo' byte again.

movwf gTemp2

swap gCrc16,w ;copy and swap

andlw 0xf0

xorwf gCrc16,f ;this time into 'hi' byte.

rrf gTemp2,w ;get 'lo' mostly calc'd Crc.

movwf gTemp1 ;save in temp1.

rrf gTemp1,f ;Have to rotate into f, because

rrf gTemp1,f ;can't rotate w by itself.

movf gTemp1,w

andlw 31

xorwf gCrc16,w

movwf gCrc16+1 ;OK to overwrite, since new 'lo' byte in gTemp2

rrf gTemp1,w ;and again, because of the carry.

andlw 0xe0

xorwf gTemp2,w

movwf gCrc16

decfsz gCrcLen

goto Crc16_Pic16C55

retlw 0 ;done.

We've mentioned the 68000 CPU a couple of times, so let's compare it. Here, we can see how the 68000 is well suited to high-level languages, the straight-forward implementation closely matches the algorithm and is  only 19words, 38 bytes long, almost as short as a Z80! The timing on the other hand - yike, 134 cycles per byte, only slightly more efficient than a Z80. This is mostly due to the fact that a 68000 had a 4 clock bus cycle, but also because the 68000 isn't very good at byte manipulation. On the other hand, the 68000 has a decent decrement and branch instruction.

Crc16_68K:

move.l d2.w,-(sp)

bra.s Crc16_68KWhile

Crc16_68KLoop:

rol.w #8,d0 ;this time we have to rotate to begin with.

eor.b (a0)+,d0 ;

move.b d0,d2 ;crc&0xff just need byte ops this time

lsr.b #4,d2 ;..>>4

eor.b d2,d0 ;crc^= above calculation.

move.b d0,d2 ;crc&0xff (we'll shift out upper 8 bits).

lsl.w #8,d2 ;..<<8

lsl.w #4,d2 ;..<<4

eor.w d2,d0 ;crc^= above calculation.

moveq #0,d2 ;(Faster than a move.b and and.w #0xff)

move.b d0,d2 ;crc&0xff

lsl.w #5,d2 ;..<<5

eor.w d2,d0 ;done.

Crc16_68KWhile:

dbra d1,Crc16_68KLoop

move.l (sp)+,d2

rts

Finally, let's also compare it with the 68000's arch-rival, the 8086. Here we can see that the 8086 isn't so well suited to a high-level language, mostly due to the optimisations needed for the byte operations and judging single bit shifts vs shifting with cl. The length is the second worst at 54 bytes and the standard instruction timings for the 8086 would give a total cycle time of 80 cycles (as efficient as a 6809) but this fails to take into account how the prefetch queue empties when executing linear code whose instructions are < 4 cycles. This bumps it up to 112 cycles per byte, which means a standard 8MHz 68000 would be about 33% faster than a 5MHz 8086. Both of them, however, are much faster than a pdp-11/34, (2.8x and 2.13x respectively).

Crc16_8086:

push dx

Crc16_8086Loop:

mov dh,al ;2(4)

mov dl,ah ;swap to begin with. 2(2)

lodsb ;al=[si]+ 12(6)

xor dl,al ;3(5)

mov al,dl ;2(3)

shr al,1 ;2(1)

shr al,1 ;4(0)

shr al,1 ;4(0)

shr al,1 ;4(0), still faster than mov cl,4: shr al,cl

xor dl,al ;4(0)

mov al,dl ;4(0) upper byte.

shl al,1 ;4(0)

shl al,1 ;4(0)

shl al,1 ;4(0)

shl al,1 ;4(0)

xor dh,al ;4(0) the <<12

xor ah,ah ;4(0)

mov al,dl ;4(0)

shl ax,1 ;4(0)

shl ax,1 ;4(0)

shl ax,1 ;4(0)

shl ax,1 ;4(0)

shl ax,1 ;4(0) Perform a straight-forward <<5

xor ax,dx ;4(0)

loop Crc16_8086Loop ;17c. 2 bytes fetched = 4c, so 13c can refill BIU

pop dx

ret