C64 SID LFSR
Statement
Goal
The Commodore 64, released in 1982 is still, to this day, the highest-selling computer ever made.Part of the reason for its success was due to its truly groundbreaking audio synthesizer chip commonly referred to as the "SID" (Sound Interface Device).
The SID was able to generate four different waveforms : triangle, pulse, sawtooth and noise.
The goal of this exercise is to recreate, in software, the white noise generator.
To create a noise waveform, you need a pseudorandom number generator.
To this effect, the SID chip used a 23 bit linear-feedback shift register (LFSR), here is how it worked :
In its initial state, the LFSR is initialized with a series of
To extract an 8 bit number from the register, the SID chip is a little unconventional in that, instead of simply extracting the topmost 8 bits, it extracts the bits at the indices [20,18,14,11,9,5,2,0].
As you can see from this example, the very first number produced by the LFSR is therefore
22--------------------0
11111111111111111111100
__^_^___^__^_^___^__^_^
__1_1___1__1_1___1__1_0 = 254
NB : Here we chose to represent the register in MSB order, that is bit
Once a number has been produced, the LFSR needs to update its state, otherwise it would always give out the same number.
•First, bits
22--------------------0
11111111111111111111100
^____^_________________
1____1_________________
1^1=0
Here the result is
The following operations are then executed in this order:
• The MSB (bit
• Every bit is shifted one to the left
• The new LSB (bit
22--------------------0
<----------------------
1111111111111111111100?
......................^_result of the XOR
Once that operation is complete, the SID is ready to output a new number.
Every time a number is requested, the operation repeats in the same order.
Write an algorithm which will, for a given 0-based index representing the number of samples requested up to this point, return the value generated by the SID .
Input
Line 1 : an integer i for the index of the current sample
Output
A byte for the number generated by the SID.
Constraints
0<=i<=2^23
Example
Input
0
Output
254
Tags
Difficulty
Easy
Test cases
0 Test
Input
0
Output
254
1 Validator
Input
1
Output
252
9 Test
Input
9
Output
240
10 Validator
Input
10
Output
224
19 Test
Input
19
Output
3
23 Validator
Input
23
Output
6
27 Test
Input
27
Output
8
29 Validator
Input
29
Output
24
15000 Test
Input
15000
Output
159
14999 Validator
Input
14999
Output
29
65535 Test
Input
65535
Output
31
65534 Validator
Input
65534
Output
82
8388608 Test
Input
8388608
Output
252
8388600 Validator
Input
8388600
Output
63
Solution language
Solution
Stub generator input