SHA-256 on a Commodore 64, Five Times Faster

At the end of part 10 of the ciphers series back in 2021, I wrote “Later in the series we’ll examine SHA-256 in detail on the Commodore 64.” Then I showed a teaser video of it running at 2.857 hashes per second and never wrote the follow-up. That was five years ago, so “later” is doing a lot of work in that sentence. ;-)

I wrote the original in Turbo Macro Pro, and it’s been in my archive ever since. The title bar says “SHA256 on C64-v1.0 (dumbest idea ever)”, and honestly, past me had a point. When I pulled it out this week, it turned out to have some problems, so we’re going to fix those first and then see how fast we can make it go.

What’s SHA-256 doing anyway?

The concept is simple enough (for a hash function, anyway). SHA-256 takes your message and pads it out to a multiple of 64 bytes. It sticks a $80 byte right after the message, fills the rest with zeros, and puts the length of the message IN BITS in the last 8 bytes. Remember that “in bits” part, because it’s going to come back and bite me in a minute.

Then each 64-byte block goes through 64 rounds, and every round mixes eight 32-bit working values, called a through h, with adds, ANDs, XORs, and rotates. When all the blocks are done, those eight values are your 256-bit hash.

None of that is hard for a 6502/6510. It’s just a LOT of 32-bit math on a CPU with an 8-bit accumulator, where every 32-bit add is four adc instructions and every rotate is four bytes shuffled around through the carry flag.

So what was wrong with v1?

I set up a test that runs the old hash routine on a pile of strings and compares the answers to Python’s hashlib. Short strings were fine, and “abc” was fine, but a 32-character string came out wrong, and so did 55 characters.

Here’s the routine that writes the length:

appendl
         .block
         ldx #63
         lda messagelen
         asl a
         asl a
         asl a
         sta messagehash,x
         rts
         .bend

It takes the length, multiplies it by 8 to get bits, and stores it in the last byte of the block. ONE byte. That’s fine for 31 characters, which is 248 bits, but 32 characters is 256 bits, so the high bit falls off into the carry flag and nobody ever looks at it again. Bleh.

That’s not the only one, either. v1 only ever handles a single 64-byte block, so anything over 55 characters was never going to work. The input loop also never puts a zero at the end of what you typed. The message buffer is only 32 bytes, and right after it in memory is an old test string, “are you keeping up with?” (some of you will recognize that one). So if you type something long, the hash runs right on into it.

I typed 35 characters, and it says the length is 56, because it hashed my string plus the end of the old test string. The right answer for that input is 5a30e4ca..., and v1 isn’t even in the neighborhood.

It gets better. Press space to start over and type something shorter, and the leftovers from last time are still in the buffer. The checksum never gets reset either, so it just keeps XORing on top of the last one.

The original also points the RESTORE key’s NMI vector at $0140, but that one’s on purpose. It’s Turbo Macro Pro’s re-entry point, so while you’re working on the program, hitting RESTORE drops you right back into TMP. Handy! v2 and v3 do the same thing. Just keep in mind that if TMP isn’t in memory, $0140 is the middle of the stack, and RESTORE will jump into whatever happens to be sitting there.

Version 2, make it right

So v2 is mostly about fixing things:

• The bit length is 16 bits now, and it handles two blocks. That covers a whole 80-character screen line, and the buffer allows up to 119.
• The buffers get cleared and the input gets properly ended every time you start over.
• It switches to lowercase mode and converts PETSCII to ASCII before hashing, so if you type Hello C64 with a shifted H, you get the same hash sha256sum gives you on a modern machine.

That last one is a Commodore thing. In uppercase mode, an unshifted letter comes in as $41-$5a, which just happens to be ASCII uppercase, so v1 always hashed in caps whether you meant it or not. In lowercase mode, unshifted letters show up on screen as lowercase, but they STILL come in as $41-$5a, while shifted letters come in as $c1-$da. Clear as mud? Here’s the conversion:

toascii
         .block
         cmp #$41
         bcc done
         cmp #$5b
         bcc lower
         cmp #$c1
         bcc done
         cmp #$db
         bcs done
;$c1-$da -> $41-$5a
         and #$7f
         rts
;$41-$5a -> $61-$7a
lower    ora #$20
done     rts
         .bend

While I was in there, I made it a little faster too. v1 had a routine to save and restore zero page, but the hash code never actually used zero page, which is kind of the worst of both worlds. Now it does use it. All the working values live at $02-$8f, and that area gets copied out first and put back afterward, so BASIC never knows we were there.

I also got smarter about the rotates. A 32-bit rotate right by 8 isn’t really a shift at all, since it’s just moving bytes around, and a rotate by 11 is a byte move plus 3 single-bit shifts. Each SHA-256 function needs three rotations XORed together, and v1 did every one of them a bit at a time, so Σ1 alone took 17 single-bit rotates at about 35 cycles each in a loop. v2 does the same thing with 5 shifts and some byte moves.

That got v2 from 328,431 cycles per block down to 130,795, which is about 2.5 times faster. Not too bad!

It still assembles in TMP, too, which means no macros, no .fill, and lines kept to 40 columns like the original. There’s one trap with zero page here, though. sta $02,y doesn’t exist on the 6502/6510, because there’s no zero page,Y mode for sta. Some cross assemblers will quietly turn it into absolute,Y for you, but I didn’t want to count on TMP doing that, so v2 only indexes zero page with X.

How fast can we make it go?

2.5 times faster is nice, but I wanted to see how far we could push it, and the biggest cost left in v2 was still the rotates. So let’s look at those again.

Take a single output byte of a rotate. Rotate right by 11 is “move over one byte, then shift right 3”, so output byte 2 is input byte 1 shifted right 3, ORed with input byte 0 shifted left 5. Every output byte is just two input bytes, each shifted by some fixed amount.

The Σ1 function is three of those rotates XORed together, so every output byte of Σ1 is a pile of shifted input bytes XORed together. If we group them by which input byte they came from, there are exactly 4 pieces per output byte, and each piece only depends on ONE input byte. One byte only has 256 possible values, so each piece can come straight out of a lookup table.

;t1 = s1(e) + h
         clc
         ldx v4+3
         lda b1t0,x
         ldx v4+2
         eor b1t1,x
         ldx v4+1
         eor b1t2,x
         ldx v4+0
         eor b1t3,x
         adc v7+3
         sta t1+3

That’s one byte of Σ1(e) plus h in 34 cycles. There’s no shifting at all, just four lookups XORed together.

Here’s the bit I like. eor doesn’t touch the carry flag, so the table lookups for the next byte can sit right in the middle of the add chain while the carry waits patiently for us. Σ1 of the whole word plus the add comes to about 136 cycles, when in v1 the rotates alone were around 600.

The four functions need 17 tables, which works out to 4,352 bytes. I wasn’t about to type 4K of .byte lines into TMP, so the program builds them when it starts up. Each table is described by a short list of shifts:

tdefs
;b1t0
         .byte $57,$06,$87,$00
;b1t1
         .byte $58,$82,$03,$00

The first line reads as “page $57: shift right 6, XOR with shift left 7”, where bit 7 set means shift left. Building all 17 takes about three-quarters of a second the first time you run it, and after that, they’re just there.

A few more tricks

At the end of every round, SHA-256 shifts all eight working values down one spot, so h gets g, g gets f, and so on. That’s 28 bytes of copying, 64 times a block. v3 unrolls 8 rounds instead and changes which zero page spot counts as “a” in each one, so after 8 rounds everything is back where it started, and we never copy anything at all.

The majority function gets cheaper too. You can write it as ((a^b) & (b^c)) ^ b, and since this round’s a becomes next round’s b and this round’s b becomes next round’s c, this round’s a^b IS next round’s b^c. We save it and use it again for free.

The 64 words of message schedule get worked out in one pass before the rounds start, and I picked the Y offsets so none of the indexed reads cross a page. A page crossing costs an extra cycle every single time it happens, and in a loop like this one, that adds up quickly.

And then there’s the screen. While the screen is on, the VIC-II steals cycles from the 6502/6510 on every 8th raster line, which costs v3 a little over 3,200 cycles per hash. So v3 blanks the screen while it works. It flickers for about 60 milliseconds, and you’ll live. ;-)

The unrolled code is about 2,200 lines of assembly, and I wasn’t typing that by hand either. A little Python script writes the round code and checks that the tables really do match the math, and what comes out is still plain TMP source with no macros. It also got too big to fit at $c000, so v3 lives at $4000 now, and you run it with sys 16384.

So how fast is it?

v3 times itself with the two CIA #2 timers chained together, so it prints actual CPU cycles instead of jiffies.

The table counts one full hash of “Hello C64” in each version, padding included. The screen says 58,537 because starting and stopping the timer adds 23 cycles of its own.

On an NTSC machine, that works out to about 17 hashes per second. The 2021 version did 2.857, so this one is six times faster than the teaser video, or 5.6 times faster than v1 if you’re counting cycles. It also gets the right answer, which I’m told is important for a hash function.

I ran all three through the same test against hashlib, with 50 strings from empty up to 119 characters, and v2 and v3 matched every single one.

Is it useful? Not REALLY, since nobody’s mining Bitcoin on a breadbin. But it’s a great workout for the 6502/6510, and the lookup tables made it a LOT faster than I expected.

There’s probably still more speed in there, too. Unrolling all 64 rounds would let the round constants be immediate values, but that’s around 25K of code, and it won’t fit in TMP alongside the source. Maybe in another five years.

Happy hashing!

• Code
• How-To
• Retro
• C64
• Commodore
• Assembly
• 6502
• Crypto
• Optimization