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.

Adding numbers on the 6502

Adding numbers is one of the more important parts of programming so an instruction to add numbers together makes sense. While we can do adding by incrementing many times, this is not very efficient.  Only the accumulator has an add instruction attached to it. The ADC command adds the contents of the accumulator with a value in memory with an extra 1 being added if the carry flag is set to allow for multi-byte numbers. Multi-byte number addition works by simply CLC for the low byte of the value then leaving the carry flag alone for latter bytes of the number as follows:

LDA NumberLowByte

CLC

ADC LowByteToBeAdded

STA NumberLowByte

LDA NumberHighByte

ADC HighByteToBeAdded

STA NumberHighByte

This is a surprising complex command as it not only has to deal with adding numbers, but must do the operation with both binary coded decimal numbers as well as normal binary numbers. As mentioned earlier, you set binary coded decimal using the SED command which enables working with binary coded decimal. Some variants of the 6502 processor, such as the one for the NES, do not support decimal mode but the 2600 does so we are going to have to implement BCD support.

The BCDtoBinary function breaks the provided byte into two nibbles then multiplies the high nibble by 10 to come up with the binary equivalent for the BCD number.

   private fun BCDtoBinary(bcdNum:Int):Int {

       val lowNibble = (bcdNum and 15) % 10

       val highNibble = ((bcdNum ushr 4) and 15) % 10

       return highNibble * 10 + lowNibble

   }

For converting a binary number back into a BCD number, we need to be concerned about numbers that are greater than 100. This is handled by setting the carry flag if the number is greater than 100. The high and low base 10 digits are worked out then converted into the appropriate nibbles.

   private fun binaryToBCD(bin:Int):Int {

       adjustFlag(CARRY_FLAG, bin > 99)

       val lowNibble = bin % 10

       val highNibble = (bin / 10) % 10

       return (highNibble shl 4) or lowNibble

   }

My method of dealing with BCD then is to see if the decimal flag is set and if it is, convert the number into binary, performing the add operation, then converting the binary value back into binary coded decimal.

The zero and negative flags are handled like usual but the ADC command also affects the carry and the overflow flag. Carry is used for unsigned numbers and is set when the number wraps meaning that the byte is too large to hold. The overflow flag is used for signed numbers and is used to indicate when a signed number has become too large. Remember that a signed number has the range -128 to 127 so 64+64 would cause an overflow as would -65+-64.

The overflow flag proved tricky to deal with until you realize that 127+-128 and -128+127 will be valid meaning the only time you will have an overflow is when the numbers being added are the same sign.

   private fun performAdd(first:Int, second:Int, ignoreBCD:Boolean = false):Int {

       if ( ( ! ignoreBCD ) and ((state.flags and DECIMAL_FLAG) == DECIMAL_FLAG) ) {

        return binaryToBCD(performAdd(BCDtoBinary(first), BCDtoBinary(second), true))

       }

       // if we reach here we are now in binary mode

       var addition = first + second

       if ((state.flags and CARRY_FLAG) == CARRY_FLAG)

        ++addition

       // set nev state of carry flag

       adjustFlag (CARRY_FLAG, addition > 255)

       // zero and negative flags

       addition = setNumberFlags(addition and 255)

       // overflow flag is a bit of work

       val firstNeg = (first and 128) == 128

       val secondNeg = (second and 128) == 128

       val resultNeg = (addition and 128) == 128

       if (firstNeg == secondNeg)

        adjustFlag (OVERFLOW_FLAG, secondNeg xor resultNeg)

       else

        adjustFlag (OVERFLOW_FLAG, false)

       return addition

   }

ADC – ADd Memory with accumulator with Carry

Address Mode	Decimal OPCode	Hexadecimal OpCode	Size	Cycles
#Immediate	105	$69	2	2
Zero Page	101	$65	2	3
Zero Page,X	117	$75	2	4
Absolute	109	$6D	3	4
Absolute,X	125	$7D	3	4-5
Absolute,Y	121	$79	3	4-5
(Indirect, X)	97	$61	2	6
(Indirect),Y	113	$71	2	5-6

Flags affected: CNVZ

Cycle Notes: Indirect and indexed modes take extra cycle if page boundaries crossed

Usage: Used to add numbers together. Memory value is added to value in accumulator. Important to remember that the value in the carry flag is added to the result so use CLC before using instruction.

Test Code:

; #immediate with overflow checked

CLD

LDA #64

CLC

ADC #64

BRK

;expect A=128, V=1, N=1 C=0, Z=0

; zero page using BCD

LDA #$10

SED

CLC

ADC 25

BRK

.ORG 25

.BYTE $15

;expect A=$25, N=0 C=0, Z=0

; Zero page,x with BCD and carry no carry result

LDA #$10

LDX #0

SED

SEC          ; force carry

ADC 25,X

BRK

.ORG 25

.BYTE $15

;expect A=$26, N=0 C=0, Z=0

; absolute with carry resulting in carry result and zero

CLD

LDA #128

SEC

ADC 512

BRK

.ORG 512  

.BYTE 128

;expect A=0 V=1, C=1, Z=1, N=0

; absolute,x overflow resulting in zero

CLD

LDX #2

LDA #128

CLC

ADC 512,X

BRK

.ORG 512  

.BYTE 0 0 128

; A=0, Z=1, C=1

; absolute,y normal add

CLD

LDY #0

LDA #50

CLC

ADC 512,Y

BRK

.ORG 512  

.BYTE 25

; A = 75, V=0, C=0

; (indirect, x) negative but normal add

CLD

LDX #1

LDA #255

CLC

ADC (25,X)

BRK

.ORG 26

.WORD 512

.ORG 512

.BYTE 254

; A=253 V=0 C=1

; (indirect),y negative + positive (carry but no overflow)

CLD

LDY #1

LDA #255

CLC

ADC (25),1

BRK

.ORG 25

.WORD 512

.ORG 512

.BYTE 0 127

; a=126 v=0 c=1

Implementation:

state.acc = performAdd(state.acc, mem.read(state.ip+1))

// zero page

state.acc = performAdd(mem.read(mem.read(state.ip+1)), state.acc)

// zero page,X

state.acc = performAdd(mem.read(mem.read(state.ip+1) + state.x), state.acc)

//absolute

state.acc = performAdd(mem.read(findAbsoluteAddress(state.ip)), state.acc)

//absolute,X

state.acc = performAdd(mem.read(findAbsoluteAddress(state.ip)+state.x), state.acc)

//absolute,Y

state.acc = performAdd(mem.read(findAbsoluteAddress(state.ip)+state.y), state.acc)

// (indirect, X)

state.acc = performAdd(mem.read(findAbsoluteAddress(((mem.read(state.ip+1)+state.x) and 255)-1)), state.acc)

// (indirect),Y

state.acc = performAdd(mem.read(findAbsoluteAddress(mem.read(state.ip+1) -1) + state.y), state.acc)