CRC32 with "nibble" table

[Virtual1]

fhw72 wrote:

It was not about getting a kind of checksum but getting a CRC32 computed as fast as possible on the 6502.

That's why I spoke up, seeing if a "lower quality" checksum would be acceptable, if it could run much faster. I suspect a CRC32 (or CRC16 for that matter) will be much slower than mine. (which is why I posted my speed for comparison) I haven't done extensive testing with my method but it appears to be good entropy, as long as you have at least a few bytes. It doesn't show as much entropy in the digest when given only 1-2 bytes since it's not a "block digest" like the more popular ones are. But then one can't expect a lot of variety in a 16 bit output when you're only feeding it 8 or 16 bits in I suppose!

I can post my code here if they (or anyone else) is interested. The working goal behind my code is something of a staple of hashing - toggling any one bit in the input stream should result in approximately half of the bits in the output toggling". Mine seems to do that well, with no detectable patterns being produced.

[BigDumbDinosaur]

Virtual1 wrote:

fhw72 wrote:

It was not about getting a kind of checksum but getting a CRC32 computed as fast as possible on the 6502.

That's why I spoke up, seeing if a "lower quality" checksum would be acceptable, if it could run much faster...

The OP was quite specific in what he (?) was trying to achieve, which is to compute a CRC32 as quickly as possible on an unspecified NMOS 6502-powered device that apparently is somewhat memory-starved.  I suspect that if a lesser checksum was acceptable, he would have said as much.

That said, I’d be interested in seeing the fastest possible CRC32 routine for the 6502 or 65C02.

[Virtual1]

well, further research found me https://rosettacode.org/wiki/CRC-32 which conveniently provides 6502 assembly for CRC32. (in addition to an Apple II implementation!)

So I entered that and was a bit surprised to see it run in 3.4 seconds (faster than MY checksum generator), probably due to not using any of the expensive ADC? I looked over the assembly and it looks pretty well optimized, I doubt there's much fat to trim there for faster processing. But if OP is truly starved for memory, creating $400 in tables may be unacceptable?

[BigEd]

It would be good to see your two byte checksum code, Vector1 - best idea is to start a new thread.

We very often do have thread drift here, and we do rather often have someone suggest a different idea which is not what the original poster had in mind. It's not always welcome to make such suggestions, but it's always OK to start a new thread and drop a short note with a link to that new thread in the existing one. Cross-linked topics make this forum much more useful to future visitors.

Start new threads for new thoughts - it's very easy. A good title for a thread will make it even more useful in the future.

[GARTHWILSON]

BigEd wrote:

It would be good to see your two byte checksum code, Vector1 - best idea is to start a new thread.

We very often do have thread drift here, and we do rather often have someone suggest a different idea which is not what the original poster had in mind. It's not always welcome to make such suggestions, but it's always OK to start a new thread and drop a short note with a link to that new thread in the existing one. Cross-linked topics make this forum much more useful to future visitors.

Start new threads for new thoughts - it's very easy. A good title for a thread will make it even more useful in the future.

Let's let the original poster, "strik," decide that.  If I myself had been the original poster asking about a 32-bit CRC, I might have considered Virtual1's post to be a welcome wake-up if I had gotten tunnel-visioned and thought I needed a 32-bit CRC when maybe what Virtual1 is suggesting might meet the real need more simply.  Strik might be grateful, or he might let us know he'd prefer, at least until further discussion takes place, to keep to the 32-bit CRC.  It's for him to decide.

[6502inside]

I did a fast SHA-1 on the 6502: https://github.com/classilla/totp-c64/blob/main/sha1.xa

It's part of a TOTP tool. The bigger issue was actually managing an RTC than doing the hashing.

[fhw72]

Another idea:

We could bake the result of the prologue of the 1st byte:

Code: Select all

	tya
	eor tab0l,x <- SPOILER: THIS ONE is unnecessary -> saving 5 cycles
	lsr
	lsr
	lsr
	lsr
	tay

into the tables. Looking at the table tab0l[x] we see that only 4 values are actually
present which means that means our precomputed table bytes are effectively XOR'ed
with one of - depending on the highest two bits of the byte coming in:

Code: Select all

0b00xxxxxx -> 0x00000000
0b01xxxxxx -> 0x76DC4190
0x10xxxxxx -> 0xEDB88320
0x11xxxxxx -> 0x9B64C2B0

Integrating (i.e. EOR'ing) these into the other tables and making

Code: Select all

tab0l byte $00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00

Effectively making tab0l[x] futile.

This leads to this new version which saves 5 cycles per byte (~705k in our use case) and 19 bytes footprint:

Code: Select all

CRC0   = $FB
CRC1   = CRC0 + 1
CRC2   = CRC1 + 1
CRC3   = CRC2 + 1

count   = $2

CRC_START = $A000
CRC_COUNT = $2000

*=$0810
        sei

        lda #>CRC_START
        ldx #>CRC_COUNT

CalcCRC
        ; A = Start address high
        ; X = count
        sta readvalue+2
        stx count

        lda #$FF
        sta CRC0
        sta CRC1
        sta CRC2
        sta CRC3

CRC_Loop
readvalue
        lda $FF00
        eor CRC0
        tay

        and #$0f        ; compute "x"
        tax

        tya             ; compute "y"
        lsr
        lsr
        lsr
        lsr
        tay

        lda CRC1
        eor tab1l0h,x
        eor tab0,y
        sta CRC0

        lda CRC2
        eor tab2l1h,x
        eor tab1,y
        sta CRC1

        lda CRC3
        eor tab3l2h,x
        eor tab2,y
        sta CRC2

        lda tab3h,x
        eor tab3,y
        sta CRC3

        inc readvalue+1
        bne CRC_Loop
not_high
        inc readvalue+2
        dec count
        bne CRC_Loop
done
        ldx #3
loopinv
        lda CRC0,x
        eor #$ff
        sta CRC0,x
        dex
        bpl loopinv

        cli
        rts

align 256
tab3h   byte $00,$77,$EE,$99,$07,$70,$E9,$9E,$0E,$79,$E0,$97,$09,$7E,$E7,$90
tab3l2h byte $00,$07,$0E,$09,$6D,$6A,$63,$64,$DB,$DC,$D5,$D2,$B6,$B1,$B8,$BF
tab2l1h byte $00,$30,$61,$51,$C4,$F4,$A5,$95,$88,$B8,$E9,$D9,$4C,$7C,$2D,$1D
tab1l0h byte $00,$96,$2C,$BA,$19,$8F,$35,$A3,$32,$A4,$1E,$88,$2B,$BD,$07,$91

tab3   byte $00,$1D,$3B,$26,$76,$6B,$4D,$50,$ED,$F0,$D6,$CB,$9B,$86,$A0,$BD
tab2   byte $00,$B7,$6E,$D9,$DC,$6B,$B2,$05,$B8,$0F,$D6,$61,$64,$D3,$0A,$BD
tab1   byte $00,$10,$20,$30,$41,$51,$61,$71,$83,$93,$A3,$B3,$C2,$D2,$E2,$F2
tab0   byte $00,$64,$C8,$AC,$90,$F4,$58,$3C,$20,$44,$E8,$8C,$B0,$D4,$78,$1C

PS: I'm really out of more ideas... but let's wait another half-year.