Visualize and verify the reverse engineered Commodore 64 SID LFSR

By Michael Doornbos

- 8 minutes read - 1577 words

Recently, we looked at a simple LFSR and how it works.

  1. Shift the bits
  2. XOR some of the bits together; we call these the taps
  3. Replace a bit with the XORed value.
  4. 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.

up arrow

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