The future comes from the past

 It has been a long time since I took a break from working on my 2600 emulator. Next month I am going to return to that project. Things have changed a lot since I worked on that project so have a lot of decisions to make. Web Assembly has become a real thing and there are several good paths to using it. Kotlin is not one of them. I am trying to decide if I should port to C, or Assembly Script. I am also thinking of going with an IDE instead of just an emulator. 

The next few months will be looking at tools and technology available followed by porting my existing emulator code. From there will be a matter of finishing the emulator then possibly building an IDE around things.

Color Me TIA

One of the big, if not the biggest, challenge of programming the 2600 was simply getting the scan-lines to be rendered properly. You are drawing the display as it is being shown and only have 76 cycles per scan line to set up the registers. As with many graphics processors, the TIA can be thought of as a state machine with the values contained in the registers at the end of a scan line being retained at the start of the next scan-line. This fact must be considered when writing your renderer, known as a kernel in 2600 parlance. A well-designed kernel will take advantage of this fact while graphical artifacts will result from a poorly designed kernel.

Quick math shows that 160 pixels with only 76 cycles means that more than a single pixel is being drawn per CPU cycle. The TIA has its own clock which runs three times the speed of the CPU. This means that there are 228 TIA cycles per scan-line. To distinguish TIA cycles from CPU cycles, the TIA cycles have been given the name color clocks. The first 68 of these color clock ticks are used for horizontal blanking so do not draw anything to the screen but does give the kernel time to set up some of the TIA registers. The remaining 160 color clocks draw the pixels of the display based on the register settings at the time a pixel is being drawn.

Pixels can be one of four colors based on what is being drawn in that location. The background color is what is used if there is nothing to draw in that location. The play-field color is the color of the play-field and the ball. Finally each player and their missile have a color.

The colors are selected from a palette of 128 colors by simply setting the appropriate color register to the desired color. The color byte is in the format HHHHLLLX with the 4 H bits being the Hue, the L bits being the Luminosity, and X being unused. The hue is the base color of the pixel while the luminosity is the brightness of the pixel. While the color could be calculated, with only 128 colors it is much quicker just to have a table of colors.

class TIAColors() {
val colorTable:Array<Int> = arrayOf(
// Hue 0
0xFF000000.toInt(),0xFF000000.toInt(),0xFF404040.toInt(), 0xFF404040.toInt(),0xFF6c6c6c.toInt(), 0xFF6c6c6c.toInt(),0xFF909090.toInt(), 0xFF909090.toInt(),
0xFFb0b0b0.toInt(),0xFFb0b0b0.toInt(),0xFFc8c8c8.toInt(),0xFFc8c8c8.toInt(),
0xFFdcdcdc.toInt(),0xFFdcdcdc.toInt(),0xFFececec.toInt(),0xFFececec.toInt(),
// Hue 1
0xFF444400.toInt(),0xFF444400.toInt(),0xFF646410.toInt(),0xFF646410.toInt(),
0xFF848424.toInt(),0xFF848424.toInt(),0xFFa0a034.toInt(),0xFFa0a034.toInt(),
0xFFb8b840.toInt(),0xFFb8b840.toInt(),0xFFd0d050.toInt(),0xFFd0d050.toInt(),
0xFFe8e85c.toInt(),0xFFe8e85c.toInt(),0xFFfcfc68.toInt(),0xFFfcfc68.toInt(),
//Hue 2
0xFF702800.toInt(),0xFF702800.toInt(),0xFF844414.toInt(),0xFF844414.toInt(),
0xFF985c28.toInt(),0xFF985c28.toInt(),0xFFac783c.toInt(),0xFFac783c.toInt(),
0xFFbc8c4c.toInt(),0xFFbc8c4c.toInt(),0xFFcca05c.toInt(),0xFFcca05c.toInt(),
0xFFdcb468.toInt(),0xFFdcb468.toInt(),0xFFecc878.toInt(),0xFFecc878.toInt(),
// Hue 3
0xFF841800.toInt(),0xFF841800.toInt(),0xFF983418.toInt(),0xFF983418.toInt(),
0xFFac5030.toInt(),0xFFac5030.toInt(),0xFFc06848.toInt(),0xFFc06848.toInt(),
0xFFd0805c.toInt(),0xFFd0805c.toInt(),0xFFe09470.toInt(),0xFFe09470.toInt(),
0xFFeca880.toInt(),0xFFeca880.toInt(),0xFFfcbc94.toInt(),0xFFfcbc94.toInt(),
// Hue 4
0xFF880000.toInt(),0xFF880000.toInt(),0xFF9c2020.toInt(),0xFF9c2020.toInt(),
0xFFb03c3c.toInt(),0xFFb03c3c.toInt(),0xFFc05858.toInt(),0xFFc05858.toInt(),
0xFFd07070.toInt(),0xFFd07070.toInt(),0xFFe08888.toInt(),0xFFe08888.toInt(),
0xFFeca0a0.toInt(),0xFFeca0a0.toInt(),0xFFfcb4b4.toInt(),0xFFfcb4b4.toInt(),
// Hue 5
0xFF78005c.toInt(),0xFF78005c.toInt(),0xFF8c2074.toInt(),0xFF8c2074.toInt(),
0xFFa03c88.toInt(),0xFFa03c88.toInt(),0xFFb0589c.toInt(),0xFFb0589c.toInt(),
0xFFc070b0.toInt(),0xFFc070b0.toInt(),0xFFd084c0.toInt(),0xFFd084c0.toInt(),
0xFFdc9cd0.toInt(),0xFFdc9cd0.toInt(),0xFFecb0e0.toInt(),0xFFecb0e0.toInt(),
// Hue 6
0xFF480078.toInt(),0xFF480078.toInt(),0xFF602090.toInt(),0xFF602090.toInt(),
0xFF783ca4.toInt(),0xFF783ca4.toInt(),0xFF8c58b8.toInt(),0xFF8c58b8.toInt(),
0xFFa070cc.toInt(),0xFFa070cc.toInt(),0xFFb484dc.toInt(),0xFFb484dc.toInt(),
0xFFc49cec.toInt(),0xFFc49cec.toInt(),0xFFd4b0fc.toInt(),0xFFd4b0fc.toInt(),
// Hue 7
0xFF140084.toInt(),0xFF140084.toInt(),0xFF302098.toInt(),0xFF302098.toInt(),
0xFF4c3cac.toInt(),0xFF4c3cac.toInt(),0xFF6858c0.toInt(),0xFF6858c0.toInt(),
0xFF7c70d0.toInt(),0xFF7c70d0.toInt(),0xFF9488e0.toInt(),0xFF9488e0.toInt(),
0xFFa8a0ec.toInt(),0xFFa8a0ec.toInt(),0xFFbcb4fc.toInt(),0xFFbcb4fc.toInt(),
// Hue 8
0xFF000088.toInt(),0xFF000088.toInt(),0xFF1c209c.toInt(),0xFF1c209c.toInt(),
0xFF3840b0.toInt(),0xFF3840b0.toInt(),0xFF505cc0.toInt(),0xFF505cc0.toInt(),
0xFF6874d0.toInt(),0xFF6874d0.toInt(),0xFF7c8ce0.toInt(),0xFF7c8ce0.toInt(),
0xFF90a4ec.toInt(),0xFF90a4ec.toInt(),0xFFa4b8fc.toInt(),0xFFa4b8fc.toInt(),
// Hue 9
0xFF00187c.toInt(),0xFF00187c.toInt(),0xFF1c3890.toInt(),0xFF1c3890.toInt(),
0xFF3854a8.toInt(),0xFF3854a8.toInt(),0xFF5070bc.toInt(),0xFF5070bc.toInt(),
0xFF6888cc.toInt(),0xFF6888cc.toInt(),0xFF7c9cdc.toInt(),0xFF7c9cdc.toInt(),
0xFF90b4ec.toInt(),0xFF90b4ec.toInt(),0xFFa4c8fc.toInt(),0xFFa4c8fc.toInt(),
// Hue 10
0xFF002c5c.toInt(),0xFF002c5c.toInt(),0xFF1c4c78.toInt(),0xFF1c4c78.toInt(),
0xFF386890.toInt(),0xFF386890.toInt(),0xFF5084ac.toInt(),0xFF5084ac.toInt(),
0xFF689cc0.toInt(),0xFF689cc0.toInt(),0xFF7cb4d4.toInt(),0xFF7cb4d4.toInt(),
0xFF90cce8.toInt(),0xFF90cce8.toInt(),0xFFa4e0fc.toInt(),0xFFa4e0fc.toInt(),
// Hue 11
0xFF003c2c.toInt(),0xFF003c2c.toInt(),0xFF1c5c48.toInt(),0xFF1c5c48.toInt(),
0xFF387c64.toInt(),0xFF387c64.toInt(),0xFF509c80.toInt(),0xFF509c80.toInt(),
0xFF68b494.toInt(),0xFF68b494.toInt(),0xFF7cd0ac.toInt(),0xFF7cd0ac.toInt(),
0xFF90e4c0.toInt(),0xFF90e4c0.toInt(),0xFFa4fcd4.toInt(),0xFFa4fcd4.toInt(),
// Hue 12
0xFF003c00.toInt(),0xFF003c00.toInt(),0xFF205c20.toInt(),0xFF205c20.toInt(),
0xFF407c40.toInt(),0xFF407c40.toInt(),0xFF5c9c5c.toInt(),0xFF5c9c5c.toInt(),
0xFF74b474.toInt(),0xFF74b474.toInt(),0xFF8cd08c.toInt(),0xFF8cd08c.toInt(),
0xFFa4e4a4.toInt(),0xFFa4e4a4.toInt(),0xFFb8fcb8.toInt(),0xFFb8fcb8.toInt(),
// Hue 13
0xFF143800.toInt(),0xFF143800.toInt(),0xFF345c1c.toInt(),0xFF345c1c.toInt(),
0xFF507c38.toInt(),0xFF507c38.toInt(),0xFF6c9850.toInt(),0xFF6c9850.toInt(),
0xFF84b468.toInt(),0xFF84b468.toInt(),0xFF9ccc7c.toInt(),0xFF9ccc7c.toInt(),
0xFFb4e490.toInt(),0xFFb4e490.toInt(),0xFFc8fca4.toInt(),0xFFc8fca4.toInt(),
// Hue 14
0xFF2c3000.toInt(),0xFF2c3000.toInt(),0xFF4c501c.toInt(),0xFF4c501c.toInt(),
0xFF687034.toInt(),0xFF687034.toInt(),0xFF848c4c.toInt(),0xFF848c4c.toInt(),
0xFF9ca864.toInt(),0xFF9ca864.toInt(),0xFFb4c078.toInt(),0xFFb4c078.toInt(),
0xFFccd488.toInt(),0xFFccd488.toInt(),0xFFe0ec9c.toInt(),0xFFe0ec9c.toInt(),
// Hue 15
0xFF442800.toInt(),0xFF442800.toInt(),0xFF644818.toInt(),0xFF644818.toInt(),
0xFF846830.toInt(),0xFF846830.toInt(),0xFFa08444.toInt(),0xFFa08444.toInt(),
0xFFb89c58.toInt(),0xFFb89c58.toInt(),0xFFd0b46c.toInt(),0xFFd0b46c.toInt(),
0xFFe8cc7c.toInt(),0xFFe8cc7c.toInt(),0xFFfce08c.toInt(),0xFFfce08c.toInt()
)

fun getARGB(indx:Int):Int {
if ((indx < 0) or (indx > 255))
return 0
else
return colorTable[indx]
}

fun getHTMLColor(indx:Int):String {
val noAlphaColor = getARGB(indx) and 0xFFFFFF
return "#${noAlphaColor.toString(16)}"
}
}

To aid in the selection of color values, my TIA testing program has a palette picker as seen in figure below.

This leaves the color clock. A simple function for handling a clock tick is simple enough to implement. I simply determine the pixel being rendered by subtracting the horizontal sync time from the color clock tick. If the column is negative, we don’t do anything otherwise we process the pixel at that column. The processing of the pixel will be implemented over the next several articles. Once the pixel is processed, we increment the color clock. If the color clock has reached it’s end we reset the color clock to zero and return true to indicate to the caller that the scanline is finished.

fun nextClockTick():Boolean {
// run current pixel
val column = colorClock - 68
if (column >= 0) {
var pixelColor = backgroundColor

// TODO render playfield
// TODO render player-missile graphics and set collisions

rasterLine[column] = pixelColor
}
++colorClock
return if (colorClock >= 228) {
colorClock = 0
true
} else false
}


Setting the colors is very simple as you simply set the appropriate color register to the desired value. These registers are COLUBK for the background color, COLUPF for the play-field and ball color, COLUP0 for player 0 and missile 0, and COLUP1 for player 1 and missile 1.

fun writeRegister(address:Int, value:Int) {
  when (address) {
    TIAPIARegs.COLUBK -> backgroundColor = value
    TIAPIARegs.COLUPF -> playfieldBallColor = value
    TIAPIARegs.COLUP0 -> playerMissile0Color = value
    TIAPIARegs.COLUP1 -> playerMissile1Color = value
    else -> println("TIA register $address not implemented!")
  }
}

Accessing the TIA

This was suppose to be posted last Saturday but I got messed up and posted an entry to my Blazing Games Development Blog instead.  Then I had an anniversary party to attend last night and forgot to post this before leaving. To get things back on the proper schedule, I will post the next installment next week instead of next fortnight. It should be noted that once the TIA rendering material is posted I may be slowing down to monthly as I really don't have much time for work on my emulation project.

 We are at the point in the project where we want to display graphics on the screen. We also want to write code so that it will work on the JVM as well as on the browser and possibly native code. The Kotlin language supports exactly this by using the “expect” and “actually” keywords. This works by letting you set up classes and functions with the expect keyword that will be implemented in a platform dependent way. Each platform that you are supporting would then have an implementation of the classes and functions using the actual keyword. This allows you to have generic code be able to call platform specific code and makes it easy to add new platforms by simply writing the expect classes and functions for that platform.

Unfortunately, I started using the IntelliJ IDE for my Kotlin development and set up the project before they added support for multiplatform projects. While I probably could create a new project as a multi-platform project and then try to pull my repository into that project, I suspect that would lead to a huge mess which would waste a lot of my time. Instead my plan going forward is to just do a JavaFX version and later port to JavaScript once I have everything working. 

One thing that happens when you are working on a project is that your initial ideas about how things will work will often have missing or incorrect assumptions. This is one reason why the waterfall method of development fails so often. As you work on a project you gain a better understanding of the problems involved. One assumption that I had was that the TIA chip could simply read the memory to perform its rendering. Unfortunately, after reviewing the TIA documentation, it seems that several registers work by being written to, even if the value written is the same value in memory. 

To solve this issue, I am going to have to rework the way memory is handled. What I am planning on doing is having both the A2600 class and the cartridge be memory managers with the A2600 class being the one that the m6502 instance uses. That way when memory is written or read from within the TIA register range, the TIA gets called so it can perform register operations. 

Internally, I could represent the registers with a block of memory, but we still need to track trigger writes. As we are having methods to handle reading and writing it is probably easier to have a different internal representation to allow for easier rendering by having classes for display objects which will greatly simplify the emulation. 

Having raw numbers is not useful, so I created an enumeration of the registers and their address. The problem here is that when I am calling the functions, the register is specified as an address so to use the enumeration you need to access the address component of the enumeration. A better approach would be to have static class constants. The problem is that Kotlin doesn’t support them. Companion objects could be used to perform a similar function but they are very inefficient.

This got me thinking that as the enum is just a class, why not use a singleton class in it’s place. Kotlin has a built-in singleton class type which is declared using object instead of class as there is only one instance.  This means that any const val declared in the object will be static constants. So I set up a TIAPIARegs object that holds all the TIA as well as the PIA registers. I have not yet decided if I will combine the TIA and PIA emulators together or create a separate class. I am using the constants from the Stella documentation which I found on the internet archives (\url{https://archive.org/details/StellaProgrammersGuide}).

@Suppress("unused")
object TIAPIARegs {
const val VSYNC  = 0x00     // vertical sync - set to 2 to start sync and to 0 to stop
const val VBLANK = 0x01     // vertical blank
const val WSYNC  = 0x02     // wait for sync
const val RSYNC  = 0x03     // Reset sync - for testing
const val NUSIZ0 = 0x04     // number-size player-missile 0  -> xxMMxPPP =Missile size, Player size/copies)
const val NUSIZ1 = 0x05     // number-size player-missile 1  -> xxMMxPPP =Missile size, Player size/copies)
const val COLUP0 = 0x06     // color-luminosity player 0
const val COLUP1 = 0x07     // color-luminosity player 2
const val COLUPF = 0x08     // color-luminosity playfield
const val COLUBK = 0x09     // color-luminosity background
const val CTRLPF = 0x0A     // control playfield ball size & collisions
const val REFP0  = 0x0B     // reflect player 0
const val REFP1  = 0x0C     // reflect player 1
const val PF0    = 0x0D     // Playfield register 0 =upper nibble display order 4..7)
const val PF1    = 0x0E     // Playfield register 1 =display order 7..0)
const val PF2    = 0x0F     // Playfield register 2 =display order 0..7)
const val RESP0  = 0x10     // reset player 0
const val RESP1  = 0x11     // reset player 1
const val RESM0  = 0x12     // reset missile 0
const val RESM1  = 0x13     // reset missile 1
const val RESBL  = 0x14     // reset Ball
const val AUDC0  = 0x15     // audio control 0
const val AUDC1  = 0x16     // audio control 1
const val AUDF0  = 0x17     // audio frequency 0
const val AUDF1  = 0x18     // audio frequency 1
const val AUDV0  = 0x19     // audio volume 0
const val AUDV1  = 0x1A     // audio volume 1
const val GRP0   = 0x1B     // graphics player 0 =bit pattern)
const val GRP1   = 0x1C     // graphics player 1
const val ENAM0  = 0x1D     // graphics =enable) missile 0
const val ENAM1  = 0x1E     // graphics =enable) missile 1
const val ENABL  = 0x1F     // graphics =enable) ball
const val HMP0   = 0x20     // horizontal motion player 0
const val HMP1   = 0x21     // horizontal motion player 1
const val HMM0   = 0x22     // horizontal motion missile 0
const val HMM1   = 0x23     // horizontal motion missile 1
const val HMBL   = 0x24     // horizontal motion ball
const val VDELP0 = 0x25     // vertical delay player 0
const val VDELP1 = 0x26     // vertical delay player 1
const val VDELBL = 0x27     // vertical delay ball
const val RESMP0 = 0x28     // Reset missile 0 to player 0
const val RESMP1 = 0x29     // Reset missile 1 to player 1
const val HMOVE  = 0x2A     // Apply horizontal motion
const val HMCLR  = 0x2B     // clear horizontal motion registers
const val CXCLR  = 0x2C     // clear collision latches

// Read registers
const val CXM0P  = 0x30     // read collision =bit 7) MO with P1 =Bit 6) M0 with P0
const val CXM1P  = 0x31     // read collision =bit 7) M1 with P0 =Bit 6) M1 with P1
const val CXP0FB = 0x32     // read collision =bit 7) PO with PF =Bit 6) P0 with BL
const val CXP1FB = 0x33     // read collision =bit 7) P1 with PF =Bit 6) P1 with BL
const val CXM0FB = 0x34     // read collision =bit 7) MO with PF =Bit 6) M0 with BL
const val CXM1FB = 0x35     // read collision =bit 7) M1 with PF =Bit 6) M1 with BL
const val CXBLPF = 0x36     // read collision =bit 7) BL with PF =Bit 6) unused
const val CXPPMM = 0x37     // read collision =bit 7) P0 with P1 =Bit 6) M0 with M1
const val INPT0  = 0x38     // Dumped =Paddle) input port 0
const val INPT1  = 0x39     // Dumped =Paddle) input port 1
const val INPT2  = 0x3A     // Dumped =Paddle) input port 2
const val INPT3  = 0x3B     // Dumped =Paddle) input port 3
const val INPT4  = 0x3C     // Latched =Joystick) input port 4
const val INPT5  = 0x3D     // Latched =Joystick) input port 5

const val SWCHA  = 0x280
const val SWACNT = 0x281
const val SWCHB  = 0x282
const val SWBCNT = 0x283
const val INTIM  = 0x284
const val TIMINT = 0x285

const val TIM1T  = 0x294
const val TIM8T  = 0x295
const val TIM64T = 0x296
const val T1024T = 0x297

const val TIM1I  = 0x29c
const val TIM8I  = 0x29d
const val TIM64I = 0x29e
const val T1024I = 0x29f

// Player sprite scale/copy modes
const val PMG_NORMAL = 0
const val PMG_TWO_CLOSE = 1
const val PMG_TWO_MEDIUM = 2
const val PMG_THREE_CLOSE = 3
const val PMG_TWO_WIDE = 4
const val PMG_DOUBLE_SIZE = 5
const val PMG_THREE_MEDIUM = 6
const val PMG_QUAD_PLAYER = 7

// Internal collision bits
const val ICOL_PFBL = 1
const val ICOL_PFP0 = 2
const val ICOL_PFM0 = 8
const val ICOL_PFP1 = 64
const val ICOL_PFM1 = 1024
const val ICOL_BLP0 = 4
const val ICOL_BLM0 = 16
const val ICOL_BLP1 = 128
const val ICOL_BLM1 = 2048
const val ICOL_P0M0 = 32
const val ICOL_P0P1 = 256
const val ICOL_P0M1 = 4096
const val ICOL_M0P1 = 512
const val ICOL_M0M1 = 8192
const val ICOL_P1M1 = 16384

// internal sprite indexes
const val ISPRITE_BALL = 0
const val ISPRITE_PLAYER1 = 1
const val ISPRITE_MISSILE1 = 2
const val ISPRITE_PLAYER0 = 3
const val ISPRITE_MISSILE0 = 4
}

The registers are assigned 5 to 6 character labels which are condensed descriptions of what the register does. After working with the 2600, the labels do start to make sense. The reason for the condensed names was likely due to limitations of the assemblers of the time. It was not unheard of for labels to be very limited in length, with eight characters being a common limit. 

We will be covering the registers in large groups as the respective functionality of the TIA is implemented. Our first task, however, is to get the color clock working.

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!

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.

Building a 16-bit Linear Congruential Generator

The 16 bit seed version of the Linear Congruential Generator (LCG) is very similar to the 8 bit version in that every time it is called it returns a byte. The big difference is that the seed is 16 bits instead of 8 bits so we will have a longer time before numbers start repeating and a bit more randomness. To get the longer cycle (and more randomness) we need to use the upper byte of the results.

For those of you who haven't read the earlier blog entries in this series or who want a quick refresher, LCG uses the formula $S_n = A*S_{n-1}+C$ for getting the next seed so we are simply multiplying the seed by a constant A and then adding a constant C to the result. We will use 141
for A and 3 for C though other carefully chosen values could be used.

We already have the multiplication which we wrote last fortnight, so now all we have to do is use that multiplication routine and then add a constant to that value. This is very simple code as you can see.

; set up our constants for A and C
.EQU LCG_A 141
.EQU LCG_C 3
; create placeholder for RNG seed
seedLo: .BYTE 0
seedHi: .BYTE 0
; ...
; multiply16x8 setup and code would be put here
; ...

lcg16bit:
; 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 lcg16bit_update_seed
INY
lcg16bit_update_seed:
; save the results in the seed
STA seedLo
STY seedHi
; put results in accumulator for return value
TYA
RTS

To test this simply call the random number generator 257 times and look at the sequence of numbers that are generated.

test:
JSR lcg16bit
; now lets do this 256 more times
LDX #0
test_loop:
TXA
PHA
JSR lcg16bit
PLA
TAX
DEX
BNE test_loop
NOP ; using this as easy to find separator
BRK

While this does demonstrate that it is working and gives us a longer sequence than the first method, it is not a very good test. For our needs we don't need statistically sound random number generation, but a simple test like generating randograms would be sufficient for getting a rough idea of how the generator was working. Randograms were covered in an earlier blog post but are essentially a 256 * 256 grid that you plot by taking two random numbers and plotting the point on the graph. This is a good idea but not really implementable on a 64k machine as the minimum size for holding the grid is 65536 bytes and we would still need some way to save the data. However, we have our own emulator so could cheat a bit to get the result. More on this next fortnight.

Multi-byte Multiplication 8x16

When you get right down to it, there is an interesting property about the number of bits involved in a multiplication. The maximum value for a multiplication is the number of bits in the multiplicand plus the number of bits in the multiplier. This means that our 8x8 multiplier should produce a 16 bit number. Likewise a 16x16 bit multiply would properly need 32 bits to store the results. For my needs we don't care about overflow situations as for the random number generator but if you wanted proper accuracy chaining more bytes to have larger results is certainly something that could easily be done. What we need to have a 16 bit seed is to multiply a 16 bit number by an 8 bit number.

This is actually not that much different than the 8x8 multiplier that we created earlier. There are two big differences. First, we are going to need to shift a 16 bit number. This can be done simply enough using the carry flag just as was done with the multi-byte additions. The shift left would then look like:

CLC
ROL LOW
ROL HIGH

This would work just fine, but we can save a byte and a few cycles by getting rid of the CLC instruction and instead using the ASL instruction in the place of the first ROL instruction. This always rotates in a 0 while still putting the shifted out bit into the carry flag.

The second issue is how to deal with a 16-bit result. There are two solutions to this problem. We could store the results in some reserved memory (ideally in page 0) which if we were going to output a 24 bit number would be a requirement. With a little bit of register shifting, we can actually keep the results of the multiplication in the registers winch gives us a bit of a speed boost as well as reducing the bytes needed for the program and memory storage. The new multiplication routine now looks like this:

JMP test
; create a placeholder for the multiplicand
multiplicandLo: 
.BYTE 0
multiplicandHi: 
.BYTE 0
multiplierLo: 
.BYTE 0
;
; Multiply method 
; A = multiplicand lo, Y = multiplicand Hi, X = multiplier
; result returned in A (lo) and Y (hi)
multiply16x8:
; init by setting zero page vars
STX multiplierLo
STA multiplicandLo
STY multiplicandHi
; start result at zero
LDA #0
TAY
multiply16x8_loop:
; see if still bits in multiplier 
LDX multiplierLo
BEQ multiply16x8_done
; shift multiplier right. C set indicates need to add
LSR multiplierLo
BCC multiply16x8_adjust
; add current power of 2 multiplicand
CLC
ADC multiplicandLo
TAX ; save low result in X register 
TYA ; transfer high result to Acc for second half of add
ADC multiplicandHi
TAY ; return high result to Y
TXA ; return low result to Acc
multiply16x8_adjust:
; Set up next power of 2
ASL multiplicandLo
ROL multiplicandHi
JMP multiply16x8_loop
multiply16x8_done:
RTS

test:

; 300 x 5 test
LDA #$2C
LDY #$1
LDX #$5
JSR multiply16x8

; fourty-two test
LDA #7
LDY #0
LDX #6
JSR multiply16x8

; LCG Mulitply step test
LDA #42
LDY #0
LDX #141
JSR multiply16x8

NOP
BRK

Here is a trace of the first test.

(0) 0:JMP $31
(3) 31:LDA #$2C ; A:$0 -> $2c
(5) 33:LDY #$1 ; Y:0 -> $1
(7) 35:LDX #$5 ; X:0 -> $5
(9) 37:JSR $6
(15) 6:STX $5 ; [5]:-> $5
(19) 9:STA $3 ; [3]:-> $2c
(23) c:STY $4 ; [4]:-> 1
(27) f:LDA #$0  ; A:$44 -> $0, Flags:32 -> $22
(29) 11:TAY ; Y:1 -> $0
(31) 12:LDX $5 ; X:5 -> 5
(35) 15:BEQ $30
(37) 17:LSR $5 ; [5]:$5 -> $2, C=1
(43) 1a:BCC $27
(45) 1c:CLC ; C=0
(47) 1d:ADC $3 ; A:$0 -> $2c
(51) 20:TAX ; X:5 -> $2c
(53) 21:TYA  ; A:$2C -> $0
(55) 22:ADC $4 ; A:$0 -> $1
(59) 25:TAY ; Y:0 -> $1
(61) 26:TXA  ; A:$1 -> $2c
(63) 27:ASL $3 ; [3]:$2C -> $58
(69) 2a:ROL $4 ; [4]:$1 -> $2
(75) 2d:JMP $12
(78) 12:LDX $5 ; X:$2c -> $2
(82) 15:BEQ $30
(84) 17:LSR $5 ; [4]:$2 -> $1
(90) 1a:BCC $27
(93) 27:ASL $3 ; [3]:$58 -> $B0
(99) 2a:ROL $4 ; [4]:$2 -> 4
(105) 2d:JMP $12
(108) 12:LDX $5, X:$2 -> $1
(112) 15:BEQ $30
(114) 17:LSR $5 ; [5]:1 -> 0, C=1
(120) 1a:BCC $27
(122) 1c:CLC ; C=0
(124) 1d:ADC $3 ; A:$2c -> $dc
(128) 20:TAX ; X:1 -> $dc
(130) 21:TYA  ; A:$dc -> $1
(132) 22:ADC $4 ; A:$1 -> $5
(136) 25:TAY ; Y:1 -> $5
(138) 26:TXA  ; A:$5 -> $dc
(140) 27:ASL $3
(146) 2a:ROL $4
(152) 2d:JMP $12
(155) 12:LDX $5, X:$dc -> $0, Z=1
(159) 15:BEQ $30
(162) 30:RTS 

As you can see that this works very similar to the original version with only a few changes. A better 8x8 multiply that returns a 16 bit result would be easy to do by simply using this version but always setting Y to 0 when calling. We now have a multiply routine that will allow us to implement both the 16-bit seed version of the LCG algorithm as well as the PCG algorithm. We will start implementing those next fortnight!