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

You are viewing proxied material from kagu-tsuchi.com. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.