Visualize and verify the reverse engineered Commodore 64 SID LFSR
Recently, we looked at a simple LFSR and how it works.
- Shift the bits
- XOR some of the bits together; we call these the taps
- Replace a bit with the XORed value.
- Repeat
Easy peasy.
I’ve long been fascinated by the Sound Interface Device (SID) in the Commodore 64, mostly because you can use it to get random numbers.
But how does it work?
The Commodore 64 SID LFSR is 23-bits. It’s a maximal length LFSR, which means it will cycle through all 8,388,608 numbers before repeating. It’s often used to generate random numbers in games. Or if you’re nuts, you can use it to do cryptography on a Commodore 64. Who would ever do that?
The Taps
The taps are the bits that are XORed together to generate the new bit. The taps are the secret sauce of an LFSR, along with the seed value.
It turns out that someone seems to have figured this out.
SID uses a pseudo random mechanism based on a 23 bit shift register to generate the noise waveform. When clocked, the register is shifted to the left and bits 22 and 17 are fed through an exclusive or gate back to the least significant bit. (This was proposed by Marko Makela and Asger Alstrup, and seems to be correct) This results in a new pseudo random value that is used as the output sample of the voice. (Bits 22, 20, 16, 13, 11, 7, 4 and 2 are used as the output bits.) In normal circumstances, the register is clocked periodically and the generated sequence of random numbers is perceived as noise. https://web.archive.org/web/20220703212619/http://www.dekadence64.org/sidwav.txt
Let’s turn “seems to be correct” into “verified through several methods”.
Make one in hardware
As we looked at before, LFSRs are easy on a breadboard. We’ll use the same 74LS164 shift register and 74LS86 XOR gate. We’ll add two more shift registers to get the 23 bits we need and wire up the taps.
I wired up my Corsham KIM-1 clone to the board so that we can output the binary bits to a display in hexadecimal since we’ll be reading them in hexadecimal on our C64 monitor shortly. I also have it clocked on my signal generator so we can spin the dial, speed it up, and slow it down.
Back off, man, I’m a scientist!
Trust but verify
The most sensible solution is to take a few random starting points and verify that the numbers generated by the hardware LFSR match those generated by the Commodore 64 SID. Out of the 8 million numbers, we only need to check a small part of the sequence at random points to be pretty confident that the algorithm is correct.
We could try to collect all of the 8,388,608 numbers on a Commodore 64 and compare them to the numbers generated by the hardware LFSR. That would require at least 8MB of RAM to store the numbers. I have several Ram Expansion Units (REU), but the timing is tricky.
It’s wayyy too slow in BASIC to be practical. If there’s some interest, I’ll do a follow up article on how to do this in Assembly and try to capture ALL of the values to the REU.
Sequence checker
We’re going to recruit a modern computer to help us with this. We’ll generate ALL the numbers and then compare them to those generated by the hardware LFSR and what comes out of the SID. If we find sequences in all 3, we can be pretty confident that the hardware LFSR is correct.
Python
n = 0b11111111111111111111000 # Shifted 1 to the left before it starts.
states = []
values = []
def bits_to_8bit_integer(n):
# Extracting the states of specified bits
bit_22 = (n >> 22) & 1
bit_20 = (n >> 20) & 1
bit_16 = (n >> 16) & 1
bit_13 = (n >> 13) & 1
bit_11 = (n >> 11) & 1
bit_7 = (n >> 7) & 1
bit_4 = (n >> 4) & 1
bit_2 = (n >> 2) & 1
# Combine bits into an 8-bit integer
eight_bit_integer = (bit_22 << 7) | (bit_20 << 6) | (bit_16 << 5) | (bit_13 << 4) | (bit_11 << 3) | (bit_7 << 2) | (bit_4 << 1) | bit_2
return eight_bit_integer
for i in range(2**23):
eight_bit_integer = bits_to_8bit_integer(n)
#print(f"{i:7d} n: 0b{n:23b} - {n:7d} - {eight_bit_integer:3d} - {eight_bit_integer:08b} - {eight_bit_integer:02x}")
nb = ((n >> 22) ^ (n >> 17)) & 1
n = (n << 1) | nb # Shift left and add feedback bit on the right
n &= 0x7FFFFF # Mask to keep it 23 bits (truncate to 23 bits)
states.append(n)
values.append(eight_bit_integer)
def find_hex_sequence(data_list, hex_sequence):
# Convert hex sequence to integers for comparison
int_sequence = [int(h, 16) for h in hex_sequence]
# Check for the sequence in the data listh
for i in range(len(data_list) - len(int_sequence) + 1):
if data_list[i:i+len(int_sequence)] == int_sequence:
return i # Return the starting index of the sequence
return -1 # Return -1 if the sequence is not found
# Replace with your sequence of hex numbers, can be any length
hex_sequence = ['0xf7', '0xa5', '0xc2', '0x2f', '0xc8', '0x5e', '0x94']
# Find the sequence
index = find_hex_sequence(values, hex_sequence)
print(f"Sequence found at index: {index}" if index != -1 else "Sequence not found")
This takes about 10 seconds on my i7 laptop. It’s not an efficient algorithm, but it’s easy to understand.
If we put a few of our values displayed on my Corsham KIM-1 clone into our Python checker after letting it run for a few minutes:
hex_sequence = ['0x44', '0x33', '0x89', '0x0a', '0x3e', '0x50', '0x14']
and run the script we get:
Sequence found at index: 2083
Neat!
Our hardware LFSR is running very slowly, so the fact that we’re only 2083 iterations into the sequence is expected.
You don’t need a KIM-1 to read these. You could just run the clock slow and convert the binary by hand (or in your head if you’re a weirdo). It could also be fun to build a custom 7-segment decoder just for this project.
Checking with a real Commodore 64 SID
This is all a fun exercise, but it doesn’t mean much if this isn’t what an actual SID outputs. We can easily write values from a SID to RAM on a C64. I’m using an REU here, but there’s no reason you couldn’t just do this into free memory on a C64 since we’re only sampling a few values in a row.
lda #$ff
sta $df0e
sta $d40f ; set the max freqency on c3
lda #$80
sta $d412 ; noise waveform
sei ; disable interrupts
lda #$1b
sta $df02
lda #$d4
sta $df03 ; copy from $d41b
lda #$00
sta $df04
sta $df05 ; REU destination
sta $df06 ; bank number
sta $df07
sta $df08 ; length of 0 means 64k tx
lda #$80
sta $df0a ; Fixed C64 address ($d41b repeatedly)
lda $d011
and #$ef
sta $d011 ; disable screen
lda #$90
sta $df01 ; do transfer
lda $d011
ora #$10
sta $d011 ; reenable screen
cli ; reenable interrupts
rts
This will transfer 64k of data from the SID to the REU. We can see that the SID shows a different value about every 16 clock cycles. So, we collected about 4096 numbers in the sequence in this run in less than a second.
Now, if we look at the REU in a machine code monitor, we can see that it’s filled with the numbers from the SID. Let’s check some.
I paged down for a while and picked a random spot to stop. If we put the unique values starting at memory location $8408 into our python checker:
hex_sequence = ['0x5c', '0xbc', '0xdc', '0x71', '0xb9', '0xea', '0x3a']
and run the script we get:
Sequence found at index: 930963
This is great! That means this sequence is about 1/8 of the way through the LFSR. If we do this many times on several SIDs (I tried 7), and they all verify, we’ve proven that this is the correct LFSR algorithm.
Did we prove the algorithm?
This checks out on multiple real Commodore 64s and even a Commodore 128 in C64 mode, so we can be confident that it does.
If you try this and can further verify our experiment, OR if you seem to be getting something different, I’d love to hear about it!
Happy hacking!
More reading
We can use an LFSR along with an LCG combined to make much more random numbers than either can produce on their own: Making and breaking Ciphers on the Commodore 64 Part 7 - Pseudo Random with Linear Congruential Generators
Resources
A lot of credit goes to Robin Harbron. He did a lot of the heavy lifting on this, and I’ve cribbed several of his techniques to jumpstart this post.
http://www.oxyron.de/html/registers_sid.html
https://web.archive.org/web/20220703212619/http://www.dekadence64.org/sidwav.txt
https://web.archive.org/web/20150406004628/http://sid.kubarth.com/articles/interview_bob_yannes.html
BTW, those two archive.org articles are why I’m so adamant about keeping my work in an easy-to-archive form. If those were only available in a proprietary format (like a YouTube video now removed), they’d be lost to history.
KIM-1 “Decoder”
Here’s the code I used to generate the KIM-1 “decoder” that I used in the video.
.org $0200
lda #$00 ; set all to input
sta $1613 ; ddr a
; Corsham 6522 #2 is #$1x10-1f
sta $00fb
sta $00fa
again
lda $1611 ; port a 6522 #2
sta $00f9
jsr $1f1f ; SCANDS
jmp again
rts
Or if you prefer paper tape format:
;150200A9008D131685FB85FAAD111685F9201F1F4C09026007DC
;0000010001