A Permuted Congruental Generator for the 6502

The Permuted Congruental Generator is a family of random number generators which I covered last year when I reviewed the paper from which they were introduced. A quick summary is that PCG does for Linear Congruential Generators (LCG) what XORShift* does for XORShift. It takes the LCG generated value and applies one or more permuted functions to this value to come up with a more random number based on the hypothesis that the fewer bits that are required to pass the TestU01 suite of tests. There are a variety of permutations that can be combined but for the 6502 I am just going to go with shifting.

The basic idea behind shifting is that we use the upper two bits (the most random bits) to pick which set of the remaining 14 bits will be used for the final 8 bits that are returned to the user. For LCG, we normally just return the highest eight bits. By having a pseudo-randomly selected shift we can get better results.

The code for this is just the lcg code we created in an earlier post with the shifting code added to the end of the routine. There is a need for the 16-bit seed value from the LCG as well as an additional two byte temp value for performing the shifting as it is easier and faster to do this work in memory.

PCG uses the multiply16x8 routine that we developed in an earlier post to do the multiplication work. We multiply the seed by the A variable and then we add the C variable to it. We are using 141 and 3 for these values but other carefully selected values could be used. Now we have effectively performed a LCG function so we then apply the permutation.

We first save off the seed and a copy of it to our temp variable. The upper two bits are needed so we transfer the upper seed result into the accumulator and then take advantage of the ROL instruction to shift the last two bits into the first two bits of the accumulator. This bit of code may seem confusing as 3 ROL instructions are used. This is necessary as the first one shifts the high order byte into the carry flag then the second one rotates this bit into the low order bit and the third one completes the transfer of two bits from the end of the byte to the beginning. We use an AND instruction to clear out the rest of the byte and then add 3 to this result to end up with a value between 3 and 6 which we use to determine how many times to shift the results.

The shifting is done by using the combination of LSR and ROR to perform a 16 bit shift on the temp value. This is done in a loop so it is done 3 to 6 times. The low order temp byte is then returned as the result of this operation.

JMP test

; set up our constants for A and C
.EQU LCG_A 141
.EQU LCG_C 3

; create a placeholder for the multiplicand
multiplicandLo: .BYTE 0
multiplicandHi: .BYTE 0
multiplierLo: .BYTE 0
; create placeholder for RNG seed
seedLo: .BYTE 0
seedHi: .BYTE 0
; create temporary int 16
tempLo: .BYTE 0
tempHi: .BYTE 0

;
; multiply16x8 goes here (code in earlier post)
;

pcg16bit:
; load in the current value of the seed into the multiply registers
LDA seedLo
LDY seedHi
; now multiply by the A constant
LDX #LCG_A
JSR multiply16x8
; add the C constant to the reult
CLC
ADC #LCG_C
BCC pcg16bit_update_seed
INY
pcg16bit_update_seed:
; save the results in the seed
STA seedLo
STY seedHi

; store the temp result bytes
STA tempLo
STY tempHi

; build the shift value to determine how much to shift
TYA
ROL A
ROL A
ROL A
AND #3
CLC
ADC #3

; perform the shift
TAX
pcg16bit_shifting_loop:
LSR tempHi
ROR tempLo
DEX
BNE pcg16bit_shifting_loop

; put results in accumulator for return value
LDA tempLo
RTS

test:
;
; testing code from last post goes here
; jsr changed to pcg16bit
;
\end{lstlisting}
}

If you take a look at the randograms from the LCG and the PCG, you can easily see that the PCG appears to be more random than the lcg version.

Before

After

Now that we have our random number generator we can create a version of Snake for the 2600. But before we can start on the snake game, we need to have a 2600 emulator, so next fortnight it is TIA time!