Title: 8080 PRNG Date: October 27, 2018 Tags: altair programming ======================================== I decided that my first assembly program on my Altair would be a Pseudo-Random Number Generator (well, the first after doing 16 bit multiplication using iterative addition, but that's not as interesting to talk about). Not sure how I came to choosing a PRNG. I think I was just looking for something interesting to write and thought of randomness and wondered how you could generate random numbers on a simple 8 bit system since modern randomness uses large numbers and pulls entropy from networks and user input, etc. An Altair doesn't have networking or even much in the way of user input. I wasn't looking for cryptographically secure randomness, but something that could work in a game, for example. I happened to stumble upon this blog about Xorshift pseudorandom number generator[0] algorithms with code for 8 and 16 bit values. I chose to implement the 16 bit algorithm because 8 bit is too easy, everything fits in a single register, and it only gets you 255 numbers of randomness. The algorithm is simply a method of iterating through a "random" sequence of the numbers between 1 and 65535 (for 16 bits) starting at a seed number. Just as a reminder, when I say "assembly program" at this point I don't mean writing code in a text editor and assembling to machine code. I am working on paper writing the assembly OP codes, keeping track of memory addresses and hand assembling to binary machine code so I can enter the program through the Altair's front panel. On one hand, I am forcing myself to interact with the Altair like a programmer would have when they bought there computer new in it's first days. I feel like it's the best way to deeply learn how the system works, and by extension, computers in general. On the other hand, it can really get tedious. For those not wanting to click away to the referenced blog about xorshift, the algorithm for 16 bit xorshift is very simple in C. // returns values from 1 to 65535 inclusive, period is 65535 uint16_t xorshift16(void) { y16 ^= (y16 << 13); y16 ^= (y16 >> 9); return y16 ^= (y16 << 7); } On paper, (even ignoring my terrible handwriting) that starts out looking like a huge mess[1]. But seven pages later I had a working program running on the Altair and manually verified. There were a couple of times I had to write part of the algorithm as a stand-alone program to test it and manually verify the results. It's a little hard to do because taking a piece of the code out of context usually means any referenced memory addresses aren't going to be the same and there is no longer anything to provide input and so you have to write code around it to read input from memory (which you load yourself with the switches) and write the output to memory (which you read after execution by examining that memory location and reading the lights). Makes you appreciate named functions and a unit test framework. I don't know the instruction set very well yet so it's slow going as I have to look up instructions in the "8080 Programmer's Manual". I have notes in the margins where I've since founds faster ways to accomplish things after finishing the program. For example, I needed to clear the carry bit and my naive approach, since there is no direct instruction to clear the bit, was to set it to 1 then compliment it. Each of those instructions takes 1 clock cycle, so 2 cycles to clear a single bit. It's mentioned in the "Altair 8800 Operator's Manual" that you can do it in 1 cycle by XORing the accumulator with itself which clears the carry bit as a side effect. ================================================================================ || OP code || Machine code || Comment || ================================================================================ | STC 067 ; Set carry bit to 1 - 1 cycle | | CMC 077 ; Compliment carry bit - 1 cycle | |------------------------------------------------------------------------------| | Or, use a side effect | |------------------------------------------------------------------------------| | XRA A 257 ; XOR accumulator with itself - 1 cycle | -------------------------------------------------------------------------------- At the time of writing the program, I wasn't tracking the cycle counts of instructions. I should be doing that and looking for optimization opportunities where I can. More experience and familiarity will help, as well. More complex programs will benefit more and have clearer bottlenecks to focus on. You'll notice also that the OP codes (and so memory locations and data) are represented in octal. At the time octal was common, but hexadecimal was taking over. The Altair is geared more towards octal by virtue of being an 8 bit system but later programs used hex. The seed for the PRNG is hard-coded into a memory location and read at the start of the program. The Altair can take input from the sense switches on the front panel, but you only get 8 bits and I wasn't doing all that work to implement a 16 bit algorithm just to be restricted to an 8 bit seed. I've seen many BASIC programs prompt the user for a seed if a RNG was used (of course you also have access to a terminal or teletype). The algorithm also has a set of valid shift values that result in the full range of numbers being generated. There are 60 sets for the 16 bit algorithm and I just used the 13, 9, and 7 from the example C code. The generated random number gets written to the same memory location as the original seed in order to use it as the next seed and continue though the sequence. This program could be tied to an interrupt and constantly update the random number which could then be consumed from the given memory address by the main program for constant randomness. Or have each call iterate to the next number in the sequence for repeatable randomness. Interrupts and using the the real time clock are what I attempted to learn next. [0] http://www.arklyffe.com/main/2010/08/29/xorshift-pseudorandom-number-generator/ [1] gopher://kagu-tsuchi.com:70/I/blog/images/PRNG_notes.jpg