CRC32 with "nibble" table

Programming the 6502 microprocessor and its relatives in assembly and other languages.
User avatar
Virtual1
Posts: 17
Joined: 01 Aug 2025

Re: CRC32 with "nibble" table

Post by 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.
User avatar
BigDumbDinosaur
Posts: 9425
Joined: 28 May 2009
Location: Midwestern USA (JB Pritzker’s dystopia)
Contact:

Re: CRC32 with "nibble" table

Post by 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.
x86?  We ain't got no x86.  We don't NEED no stinking x86!
User avatar
Virtual1
Posts: 17
Joined: 01 Aug 2025

Re: CRC32 with "nibble" table

Post by 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?
User avatar
BigEd
Posts: 11463
Joined: 11 Dec 2008
Location: England
Contact:

Re: CRC32 with "nibble" table

Post by 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.
User avatar
GARTHWILSON
Forum Moderator
Posts: 8773
Joined: 30 Aug 2002
Location: Southern California
Contact:

Re: CRC32 with "nibble" table

Post by 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.
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?
6502inside
Posts: 101
Joined: 03 Jan 2007
Location: Sunny So Cal
Contact:

Re: CRC32 with "nibble" table

Post by 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.
Post Reply