Tuesday, January 13, 2015

Trivial Triumph

Today I did something clever on the Apple II.  I applied some recently acquired knowledge to address a gap in the random number generation for my Fahrfall port, and I was proud of it.  Unfortunately, I may have solved a problem that didn't exist...

Standing Start

Previously I discussed the use of a software-based linear feedback shift register (LFSR) for generating pseudo-random number sequences.  The LFSR is really just an equation that generates a sequence of numbers, each based upon the value of the previous number in the sequence.  Given a fixed starting point, the LFSR will always generate the exact same number sequence.  Consequently it is important to "seed" the LFSR so that it starts at an unpredictable point in its sequence.  A common technique for seeding an LFSR would be to use a rapidly changing variable (such as a time-based counter) to seed the LFSR.  Since the Apple II lacks any timing source, I looked for other options.

Clever Display

After a while, I recalled learning about a quirk of the Apple II hardware that allows a program to read the byte of video data currently being displayed on the screen by reading from one of the "soft switches".  Others have used this mechanism to synchronize a program for the proper timing of video updates by writing appropriate "sentinel" data to the video buffer.  That method of synchronization relies on precise cycle counting and seems unsuitable for a game or other interactive program.  But maybe the mechanism it uses could be pressed into service here?

It is very difficult for a human to know what portion of the video buffer is being displayed at any given moment, so reading the displayed video data during program setup should yield the data from a more-or-less random position in the video buffer.  Of course, the video buffer will often contain largely uniform values (e.g. spaces on the text screen).  For best results, steps should be taken to minimize the duplication of data values within the video buffer.  Consequently, I wrote an ordered sequence of values to the video buffer.  During program initialization I read from a video "soft switch" to retrieve values to use for seeding the LFSR.  This yielded satisfactorily random sequences across multiple program starts.

Reality Bites

With my LFSR getting a reasonable seed value, I was feeling rather pleased with myself.  After just a couple of weeks of playing with the Apple II, I may have just invented a new technique for generating a random number seed!  Even if it turns out that others have done this before me, I still discovered this all on my own!  Nevertheless, I wondered if I could find any evidence of someone else doing something like this?

For what its worth, I did not find any documentation of anyone using this technique for generating a random number seed on an Apple II.  That doesn't mean that no one has ever done it, and it doesn't even mean that no one ever wrote it down.  It only means that I didn't find any evidence of that in a few minutes with Google -- YMMV!

However, in my search of Apple II random number generation techniques I did find another interesting tidbit.  Apparently the firmware on the Apple II updates a loop counter in the zero page (at locations $4e and $4f) every time the keyboard is checked for input.  While the value of this number might be predictable if a program is automatically started after boot (perhaps when using an emulator?), in the real world this method is just as good and it is a lot easier to use.

So, I guess I'll just seed the LFSR the easy way -- at least I got to feel smart for a little while!  This is the sort of stuff that makes the Retrochallenge lots of fun, so I wanted to post this update for everyone's enjoyment.  There will still be more to come, so I hope everyone will stay tuned!


  1. What if...

    - Display Title screen, with "Press any key to begin"
    - Loop and increment a 16-bit counter at CPU speed while user doesn't press key
    - User does press key
    - The last few bits of the counter now have reasonable entropy.

    1. Yes, that probably works fine too. It isn't really much different from just using the 16-bit counter at $004e that the monitor already maintains, but I suppose that your proposal would be a better in the case of an autostart of the program (like with an emulator). :-)