8-bit LFSR Randomizer

The program in action.

8-bit LFSR Randomizer is a program I wrote in FreeBASIC which demonstrates one of the ways programmers used a linear-feedback shift register to generate pseudorandom numbers. This method of generating pseudorandom numbers was developed in 1965 and is no longer used in modern programming because the random sequence has various problems. However, it was very popular with 8-bit computers because it uses very little memory, takes only around a dozen clock cycles, and is random enough for non-secure use.

Below is the source and a compiled Windows binary. As it is written, it actually uses 16-bit integers, but, that's only because FreeBASIC doesn't have native access to the CPUs registers. However, there is a link to how you would write the program using 8-bit 6502 assembly.

Source

' This program uses a linear-feedback shift register (LFSR) to generate 
' pseudorandom numbers. The result is all the numbers from 0-255 rearranged 
' in an order that looks kind-of random, but are fully determined from the 
' starting number (seed). The result is by no means a quality random number 
' generator, for example, somewhere in the sequence you will always see the 
' clearly non-random pattern "1, 2, 4, 8, 16, 32, 64, 128, 0," but this 
' algorithm uses very little memory or CPU cycles, so even extremely 
' weak hardware like an old 8-bit computer can utilize it with ease. In 
' fact, a lot of old video games would use an algorithm like this to generate 
' random numbers since didn't have access to stronger hardware.

' This code was written by Dean Tersigni, adapted from the 6502 assembly code 
' described on Codebase 64: 
' https://codebase64.org/doku.php?id=base:small_fast_8-bit_prng

Declare Function NextLFSRNumber (Seed As UByte) As UByte

' This number is the value we're going to use to xor the input each time 
' through the LFSR function. Only some numbers will result in an even spread 
' of all the numbers from 0-255. The following will work, and each produces a 
' different order, so change them up as you need them: 
' 29, 43, 45, 77, 95, 99, 101, 105, 113, 135, 141, 169, 195, 207, 231, 245
Const As UByte XorVal = 29

' This section generates a seed (starting value) based on when the user 
' starts the program after the title screen is displayed. Games would often 
' generate a seed this way because consoles didn't have access to a clock 
' which is the most common seed generator. Below, I'm using the same LFSR to 
' generate pseudorandom numbers for the seed in order to make the display 
' show random numbers, but old video games rarely went through this hassle. 
' It was much easier to just have a single incrementing byte loop through the 
' numbers 0-255, and, whatever number it was on when the user started the 
' game, use that for the seed. Although this makes it easier to game the 
' randomizer, it was still pretty safe because the user didn't know the seed 
' was based on when they started the game, and, even if they did, they 
' couldn't see what number the counter was at in order to try for a specific 
' number, and, even if they could, few people have reflexes so well-tuned 
' they can start the game on a specific clock cycle!
Print "Press any key to start."

Dim As UByte Seed
Do
	' Get the next number in the sequence.
	Seed = NextLFSRNumber(Seed)

	' Display the seed, so the user knows we're working.
	Locate 3, 1, 0
	Print "Seed: " & Seed & "  "
Loop While Inkey = ""

Print
Print "Your random sequence is: "
Print

' Now run through the LFSR 256 times to generate a sequence of pseudorandom 
' numbers for the user to see.
Dim As UShort I
For I = 0 To 255
	Print Seed;
	If I < 255 Then Print ", ";	' Every number except the last gets a comma.
	If (I + 1) Mod 16 = 0 Then Print ""	' Print 16 numbers per line.

	' Get the next number in the sequence.
	Seed = NextLFSRNumber(Seed)
Next I

Sleep
End

Function NextLFSRNumber (Seed As UByte) As UByte
	' This function uses the linear feedback shift register to generate the 
	' next pseudorandom number in the series.
	Dim As UShort Work = Seed

	' Start by shifting the bits left (a single shift is the same as 
	' multiplying by 2, but shifting is faster). This will increase all seed 
	' values except for 0.
	Work = Work SHL 1
	
	' We have a special trap for 256 (which means our seed was 128). Since no 
	' input seed will result in a 0 for output, we don't xor this in order to 
	' force it to be a 0 to get all 256 possible numbers.
	If Work <> 256 Then
		' On an 8-bit computer, you'd have to check the carry flag, but, 
		' since we have access to a 16-bit integer, we can just check if the 
		' 8th bit is set to know if the left-shift overflowed the byte. If it 
		' did, we need to xor the number to get linear feedback. We also need 
		' to xor 0 (even though the 8th bit is off) or the LFSR will remain 
		' stuck on 0 forever.
		If Bit(Work, 8) = True Or Work = 0 Then
			' Performing the xor on the acceptable numbers will decrease the 
			' number by a seemingly random amount.
			Work = Work Xor XorVal
		End If
	End If
	
	' Clear the 8th bit to keep the value below 256. This also ensures a seed 
	' input of 128 will result in a 0 to ensure even distribution.
	Work = BitReset(Work, 8)

	' Return the new number.
	NextLFSRNumber = Work
End Function

Download

This includes the program and source code.

• Download (Info)

Links

• codebase64.org/doku.php?id=base:small_fast_8-bit_prng - 6502 source.