Testing 6502 Random Number Generators

The routine for testing the random number generator (RNG) is interesting. We want to generate 65536 random numbers so a nested loop is the obvious solution to this problem, but we also need to use the registers. Pushing the state of the loops to the stack before making the call to the RNG is the obvious solution. To improve the efficiency, which really is not needed for test code like this, I did the pulls separately so that only the inner most loop needs to be pulled all the time while the outermost loop only gets pulled from the stack when the inner most loop has ended.

JMP test
; variable declaration goes here
FakeRNG:
; muck up y just to make sure outer loop code works
LDY #99
; Use X to increment value in accumulator and mess up X
TAX
INX
TXA
; This RNG just increments value of accumulator - not very random
RTS
test:
; looping information stored as bytes on stack
LDA #0
PHA
PHA
test_inner_loop:
; this would be a call to the RNG being tested
JSR FakeRNG
; our randogram emulator uses nop to add the value of A
; to the list of random number that have been generated.
NOP
; Handle the inner loop
PLA
TAX
DEX
BEQ test_outer_loop
; this will be reached if outer loop not done
test_inner_loop_adj:
TXA
PHA
JMP test_inner_loop
test_outer_loop:
; Handle outer loop
PLA
TAY
DEY
BEQ done
; this will be reached only if outter loop still going
TYA
PHA
JMP test_inner_loop_adj
done: 
BRK

The test framework includes a simple test generator that simply returns the value in the accumulator incremented by one while mucking up the x and y registers to verify that the loop code is working properly. This will, when ran with the test, cause 1,0,255,254... to be generated which will result in a dotted line on the randogram as can be seen.

Applying the test framework to the two existing generators is trivially easy. We simply need to replace the jsr call to the appropriate random number generator. The results of the 8 bit generator are obviously not that great. If you were to look at the order that the numbers were generated, this is not too bad, the real problem is that there is only a single iteration of the numbers and once all the numbers have been picked, the loop repeats.

Going with 16 bits and taking the upper bits should solve this problem so lets take a look at the randogram for this generator

Not too shabby but a pattern can still be seen. The PCG generator, at least the simplest permutation of it, is very simple to add so next fortnight we will implement that and see how well it compares to our 16-bit LCG generator.

Building a Randogram Emulator

As I stated in last year's review of the PCG paper, Randograms are an informal way of looking at random number generators. They are generated by creating a 256x256 grid and then taking 32768 pairs of numbers,  plotting them on the grid. The code for doing this was given in that previous article and it is not too difficult so I will omit the drawing code. Since the numbers for the random number generator will be coming from assembly language code, the RNG component that provides the randogram it's data will need to be written. We will simply have the RNG have an array of 65536 elements that get looped through. Our 6502 interpreter will fill out this array when it is ran. This is pretty trivial code:

open class RNG {
val randomBytes = arrayListOf<Int>()
var indx = 0

init {
for (i in 0..65535) {
randomBytes.add(0)
}
}

open fun nextUByte():Int {
val temp = randomBytes[indx]
++indx
if (indx > 65535)
indx = 0
return temp and 255
}

}

We are now ready to build our Randogram Emulator's main display. This version is being done using JavaFX but could have been done in JavaScript. It would be nice if there was a standard cross-platform GUI library to use, but there are some third party attempts at such a beasts. Until there is a clear winner in this area, I will use JavaFX and plan on porting any GUI code to JavaScript when I am ready to get the js version of the emulator running. The GUI code simply sets up a canvas to draw the randogram on and a button for loading an assembly language file to be processed.

    override fun start(primaryStage: Stage?) {
randogram.generate()
randogram.drawToCanvas(canvas, 2.0)

val btn = Button("Test Assembly")
btn.setOnAction {handleLoadAsm()}
val root = VBox(10.0, canvas, btn)
val scene = Scene(root, 800.0, 600.0)

primaryStage!!.title = "JavaFX test"
primaryStage.scene = scene
primaryStage.show()
}

The button handler is where all the real work takes place. We will simply set up the emulator environment, then bring up a file dialog for obtaining the assembly language file that should be processed. As this is an internal tool, we are not doing any sanity checking on the contents of the assembly language file but instead are simply calling our assembler class and getting it to assemble the file. A proper program would check the results of the assembler to make sure the file assembled properly, but this is a quick and dirty test so this will not be done.

The code for running the machine language is very simple as we just run instructions until we hit a break instruction. The twist, and where we are cheating big time, is that when we run into a NOP instruction, we handle that instruction by taking the value of the accumulator and adding it to the RNG instances list of numbers. Once we have written a proper assembly testing framework, this will result in 65536 numbers being generated which will fill out the list.

Once the assembly language code has ran, we generate the randogram and update the display. We now have a way of testing our assembly language random number generators.

    private fun handleLoadAsm() {
var memoryManager = Cartridge()
var m6502 = M6502( memoryManager )
var byteData =  ByteArray(4096)

val fileChooser = FileChooser()
var assemblyFile = fileChooser.showOpenDialog(null)
if (assemblyFile.isFile) {
var assemblyList:ArrayList<String> = ArrayList(assemblyFile.readLines())

var assembler = Assembler(m6502)
assembler.assembleProgram(assemblyList)
for (cntrRom in 0..assembler.currentBank.size-1) {
byteData[cntrRom] = assembler.currentBank.readBankAddress(cntrRom).toByte()
memoryManager.write(cntrRom, assembler.currentBank.readBankAddress(cntrRom))
}

m6502.state.ip = 0
var ipAddress = m6502.state.ip
var indx = 0
while (memoryManager.read( ipAddress ) != 0) {
if (memoryManager.read( ipAddress )==0xEA) {
rng.randomBytes[indx] = m6502.state.acc
++indx
}
m6502.step()
ipAddress = m6502.state.ip
}
}

randogram.clear()
randogram.generate()
randogram.drawToCanvas(canvas, 2.0)
}

The problem we now have is that we need to write a testing framework for actually testing our random number generators. This will be done next fortnight.