6502.org

After looking at the algorithm again, I can see that.
I did some monkeying around with the timer and determined that following power-on (but not reset while already powered), the 28L92’s counter/timer starts with a random value in its (16-bit) presets.  So some entropy is possible there.  Unfortunately, a reset after power-on won’t disturb the presets, but will stop the timer, essentially freezing it with whatever the count was at the moment of reset.  If I were to read the timer at that moment, do some sort of bit-twiddle on it, e.g., XOR it with some other value, and write it back (writing changes the preset but not the timer itself until started), that should add a little entropy.
That’s a possibility, although the only real variable would be in the time needed for the SCSI subsystem to get ready, and that would be unpredictable only from a cold start (due to disk spin-up time), not a reset while the system is powered.  Serial I/O at reset is always the same while POST is being carried out and the console is being driven with start-up messages.
Yep, that thought had occurred to me.

I’m currently running the timer at the rate of X1 ÷ 16, where X1 is the DUART’s clock frequency (3.6864 MHz).  That produces an effective timer frequency of 115.2 KHz, due to the timer changing phase on every other transition of the X1 clock, i.e., one-half the X1 rate.  That rate produces an interval of 8.68 µsecs between timer “ticks,” which is pretty coarse.  With the timer running at that rate, the 65C816 (which runs at 16 MHz in POC V1.3) could do many consecutive reads of the timer before it changes, despite the one-cycle wait-state that occurs on DUART accesses.

The timer may also be configured to run at X1 ÷ 1, which would reduce the interval to 0.54 µsecs.  Even at that rate, closely-spaced reads of the timer are likely to return the same value.

Beyond that, the 28L92 has a provision for driving the timer with an external clock signal of 8 MHz maximum, which would produce an effective timer frequency of 4 MHz, an interval of 0.25 µsecs.  That would all but eliminate the likelihood of consecutive reads returning the same value.  However, using an external clock would mean adding a third oscillator to the unit, or using a flop to tap off a signal from the Ø2 clock.
The entire I/O subsystem is interrupt-driven, so interrupt intervals during serial or SCSI I/O can be unpredictable.  Access to a particular disk, however, tends to be predictable due to buffering, unless seeking requires head movement and a buffer refresh.  Even there, things happen so fast relative to the processing speed of the 65C816 that I doubt enough entropy would be added to matter.
The timer is a 16-bit source (and is big-endian, although that in itself doesn’t matter) but anything involving the I/O subsystem would be eight bits.  The more I think about it, the more inclined I am to consider only the (free-running) timer as an entropy source.
In playing around with this, I am reading the timer and XORing it with $FFFF just for grins.  I don’t know that doing so is gaining anything...
Probably more so with SATA disks that SCSI ones, as the latter have substantial buffers to reduce the frequency of medium accesses.

However, in my POC units, despite running the host adapter in SCSI-1 asynchronous mode (the slowest mode), the bus is still substantially faster than the POC unit.    SCSI-1 async mode runs the bus at 3.5 MB/second, which is roughly four times faster than the rate at which 65C816 can fetch/store bytes from/to the host adapter.  So the seek time on a disk would be a tiny fraction of the total time required to complete a read operation.  The only SCSI device I’ve got connected that exhibits significant seek time is the CD-ROM, and that is only if a medium is loaded.

It's always the low-order bits of timings that hold the entropy - you can choose to think of it not in the latencies but in the variation of latencies.

> EOR the timer with FFFF
I can't see that would make any difference one way or the other. My point is very much more that you shouldn't be overwriting any bytes in your entropy pool, you should be mixing into them.

If I understand what you mean, then I think that could work - you XOR the value read from the presets with the value of the timer, and use the mixed result to seed the RNG. On a cold boot the preset value is contributing entropy as it's in a random state, while on a warm boot the timer is contributing entropy because the amount it counted during the previous boot is likely to vary a lot (so long as it is left running freely and not manipulated). It ought to be enough to generally ensure that you usually get a different seed on each reset.
It doesn't really matter if consecutive reads would read the same value - it's more a matter of how the coarseness of the counter compares with the variance in the duration of the thing you are timing. For example if you're timing something that usually takes between 300us and 310us, then the range of values is 10us. With 8us granularity you wouldn't get much out of it, 8us is too coarse for that, but with 0.5us granularity that 10us range is going to give a range of about 20 possible values for your random seed, which is quite a lot. The speed of the MPU doesn't matter so long as it's also at least fast enough to observe these different values.

If you had another independent source with a similar range, you could then combine them together (at different positions in the seed vector) and get 20x20=400 different possible startup seed values, which is hopefully plenty!

That’s basically it, with a slight bit of complication.

A read of the timer when in counter mode (the default after reset) always returns whatever is in the registers, not the presets.  The registers’ content might the same as the presets...or might not—there is no way to directly read the presets.  However, I determined that the trick to getting the presets was to start the timer and then immediately stop it, after it has been configured to the X1 ÷ 1 mode (X1 being the DUART’s 3.6864 MHz clock).  Starting and stopping the timer involves a passive read on two different registers, at a cost of five Ø2 cycles (four cycles for a read operation, plus a wait-state) per operation.

So the procedure is to start the timer, immediately stop it and read the registers.  Starting the timer copies the presets into the registers before counting commences.  The start and stop operations are consecutive LDX absolute instructions with the index registers set to eight bits, which means the interval from when the timer is started to when it is stopped is five Ø2 cycles.  The timer will be “live” for about 312 ns, which isn’t enough time for the timer to decrement before being stopped.  Ergo a read immediately after the stop will return the preset value, whatever that might have been following reset.

Anyhow, that’s the theory! 
I did some testing of this with the timer running at X1 ÷ 1, in which I read the timer (which has to be momentarily paused during the read), stored the fetched value in an idle direct page location, read the timer again and compared the fetched value to the previous one—all fetches and comparisons were 16-bits.  I did this in a loop for 10 times, and incremented a counter each time the two timer values were the same.

At the end of the loop, the counter was still zero.  A second test looped for 20 times, with the same results. So it would appear the odds of not fetching the same value with consecutive reads are very high. which makes sense when you look at how long it takes to stop the timer (five cycles), read it (seven cycles), write back the timer value to restore the presets (seven cycles) and the restart it (five cycles).

As previously noted, the timer interval is 540 ns, and the MPU clock period is 62.5 ns (16 MHz clock).  The timer fetch sequence consumes 1.5 µsecs, which is approximately 2.8 times the interval between successive timer “ticks.”  The total time between successive fetches is actually a little higher due to the time required to store the first fetch in direct page.

So I think it is safe to say that if the timer is free-running at X1 ÷ 1 (which makes it endlessly count down from $FFFF to $0000), it may be considered a good entropy source, even with closely-spaced reads.
I haven’t identified another entropy source that would be reliable following a power-on reset, other than possibly the real-time clock (RTC).  However, the quickest-changing register in the RTC is the seconds register, so that would be an unreliable source at best.

BTW, my interest in all of this random stuff is being fueled by a feature I hope to incorporate into my 65C816 kernel on which I am slowly working.  Since there will be support for a filesystem, I want to incorporate the means to generate a temporary filename along the lines of the tmpnam() function in many *NIX operating systems.  Such a filename is randomly generated, so I need a source of random values that can be converted to the ASCII alphabet range.

Building on the above, below is a program I cobbled together that seeds the state using multiple timer readings with bitwise transformations and then computes the pseudo-random number (PRN).  Seeding, of course, should only be done one time, before calling the PRNG part.

For grins, I do a timer read at the start of the PRN computation and use that as the entry value for the first addition.

The reason for all the timer malarkey during the seeding process is to reduce the likelihood of state always coming up the same at system boot.  I’m using the counter/timer in one of POC V1.3’s DUARTs, which endlessly free-runs from $FFFF to $0000.

That sounds fine to me - again though, you don't need closely-spaced reads, you just need one read that has the potential to have a decent range of values. Even if it took 1000 cycles to perform the read, so long as the timing of the first cycle relative to the timer leads to a lot of potentially different results, that's fine. It's like if I were using a stopwatch to time something, but instead of stopping it, I took a photograph, then took out the SD card, put it in a computer, copied the file into an email, and sent it to you - it would take ages, but the actual value that comes out still depends mostly on the resolution of the original stopwatch. Whereas if I only considered taking a photograph once per minute, that would reduce the granularity to my own frequency, and either way taking a sequence of photographs in succession also doesn't make much difference (whether they're one second apart or one minute apart).
Actually I think that's a really good source nonetheless - not of entropy, but it's fine to use at startup because unless you are going to restart the computer twice within the same second, it will guarantee that every restart leads to a different random seed because the RTC itself will never repeat values. For your purposes I think you could probably just use that - conditioned a bit as I suggested before to make sure the RNG "warms up" quickly - and it's a common thing to do. Adding a more "random" timer-based value alongside it in the state vector would be fine too, but don't combine them in exactly the same bits or you increase the risk of getting an identical seed.

Apologies I forgot to press "Send" this morning - later today I will catch up with the code you posted.

Nice, is it giving you the kind of results you want? I was going to suggest logging the seed values that you're seeing on startup to a long-term storage so that you can look back later and see whether your entropy sources are actually leading to unique values.

Regarding seeding - it is really important to run the function a few times after any seeding process, discarding the results, because otherwise the first few values returned will have a strong correlation with the seed value. I did some testing on that today which I'll post shortly. The short story is that I'd call "randget" at least 8 times after seeding - 16 would be better - to let it thoroughly shuffle the seed.
I'm not sure that's a good idea is it compromises the bit of the algorithm that guarantees a long period. If you just wrote the EOR result back into state14 instead it would probably be better. The trouble with changes like this though is that it is very hard to test whether they are helping or hindering - as you can't really replicate the effect of the change in a consistent way for offline testing.

A safer way may be to just EOR the timer result with the output value, so that at least the original output value is guaranteed to be strongly random, and then what you layer on the top with operations like EOR or ADC certainly can't make it get worse.

> just EOR the timer result with the output value

I like that! It makes it obvious that any bias in the timer can't affect any randomness of any bits: a random bit that's flipped is still a random bit. It can't hinder, and it might help.

I've been looking at how important the seeding process is and the need to "warm up" the RNG after seeding it. I used the 32-bit version that BDD is using for this testing, as it's probably the worst case as it has the most state.

The TL;DR is that whatever you do with seeding, I'd recommend running the RNG straight away afterwards at least 8 times, preferably 16 times, and discarding the results, as the first samples can show significant bias based on the seed. A second point is that it doesn't matter too much exactly how you set the state based on your seed (whether you spread the entropy around the state vector's bits, etc) - it affects things a bit, but the best way to do this shuffling is probably just to run the RNG itself because that's its specialty.

I experimented with - but didn't observe any benefit in - picking different "LDA" values. It does affect the quality of the random sequences overall (usually negatively) but it doesn't seem to have a noticeable effect on the correlation issues I was looking at here.

As an initial illustration, here's a graph showing successive 32-bit values (scaled down of course!) returned immediately after setting the seed very lazily to all zeros but with a small number (1, 2, 3, ..., 7, 8 ) in state vector entry 0: It's pretty clear that the first few samples are all very similar regardless of the change in seed value. However after 4 or 5 samples things start to look better. Of course this is only looking at 8 different seed values, and not making any effort to spread the bits around even the first 16-bit word, let alone the whole 128-bit vector.

It's hard to visualise a large number of seeds but what I decided to do was to plot - for each of 2048 different seed values horizontally - the first value returned vertically, and then repeat for the second value on another frame, and the third on another, and so on, up to 8 frames, and put it in an animated GIF. So the animation shows the evolution of values returned, for each seed, over the first 8 calls to the random function. The correlations with the seed values are always clearly visible in the first few frames, and you can see how many frames it takes to get a random-looking arrangement, for various strategies of setting the whole seed vector.

I would again like to highlight that even in the worst case, after 16 samples there's no visible pattern and also that even in the best case, it still takes 6/7/8 samples before there's no visible pattern. This is why I advise to always discard the first 8 samples, and if you just discard the first 16 you can worry less about how you actually populated the seed vector.

These are animated GIFs but you might need to click through to play them and see all the frames.

First up - this is setting state[0] to the seed number (0-2047) directly, with the other state entries all set to zero. It is pretty much the worst thing you can do (actually setting a later state entry is worse...) and you can see it takes until about frame 6 before you see any irregularity in the pattern at all, and frame 8 before it looks fairly random. I put extra frames in this one because it was so slow to become random. Next - still only setting state[0], but scaling the seed number to span the whole range of 16-bit values. This is quite a lot better, with irregularities in frame 4 and frame 6 being the last one that doesn't look random to my eye. Now I did something like state[0] = seed + (seed << 4) + (seed << 8 ) + (seed << 12) so that the most varying bits are spread more widely over the word. It is a bit different but still pretty much takes until frame 7 to look random. What if we go back to the version that scaled the seed up to span the whole 16-bit value, but now write that same value to all 8 state vector entries? I would say this still takes until frame 7 to look reasonably random, but it is easier to do and saves a lot of bitshifting. Now the same thing but with the "mixed up" version that added bitshifted copies of seed to spread the entropy around. This is now better and frame 6 looks pretty random: And finally, I made changed it to set different values in all of the state entries, still based on the same 11-bit seed number but just adding more variety across the state vector. This performs similarly to the previous one, I think, perhaps looking almost random on frame 5 but not quite - and, critically, it is still really bad before that point: I think the summary is pretty much what I said in the TL;DR at the top - discard about 16 samples (it is the quickest and easiest way to avoid these problems) and aside from that so long as you find a decent way to get a unique number of up to 64 bits to use as a seed, you can just write it straight into the bottom of the state vector (in this version of the algorithm - some others would want it at the top), and you're guaranteed to get a unique sequence of numbers as a result.

Great visualisations. I would agree - if things look random after 8 rounds, then give it 16. We're not great at judging randomness, although we are good at detecting order.

I modified my test code to do what you suggested.  After seeding state, 16 calls are made to the PRNG function (now structured as a subroutine) and then it’s ready for use.

POC V1.3 doesn’t have a convenient way to store data over long-term, other than directly writing into disk blocks—there’s no filesystem.  However, I did run the setup function earlier today and copied the state variables to an unused corner of RAM for later comparison.  I again ran setup right before I made this post, but this time without doing the timer configuration—the timer was already running from the previous session, and compared the new state to the saved state.  All words were different.  I will repeat this test in a few more hours and see how it goes.

I did the seeding test again without disturbing the timer setup.  Once again, all state words were different.  At this point, I am reasonably confident the seeding code is unlikely to exactly repeat a previous seeding session (“unlikely” means just that, not that a repeat will not happen).

I also ran the PRNG inside a loop to collect an array of PRNs to see if any duplicates were generated.  As POC V1.3 has mass storage, but no filesystem, I can’t store data to a disk in an organized way at this time.  So what I did was call the PRNG 16,384 times to produce an array of 32-bit PRNs, storing them in RAM from $010000 to $01FFFF.  Following that, the array was “walked” to determine if there were any PRNs that were duplicated.  There were no duplicates.

As I above noted, one of the functions the PRNG will eventually support is the generation of random filenames for creating temporary files.  Basic to that is taking the 32-bit output of the PRNG and converting it in alphanumeric characters.  Four characters could be generated from each number, but when decomposed to byte-size pieces, some are outside of the seven-bit ASCII range.  For example, just now I ran the PRNG and it returned $76A466F1.  $76 and $66 will directly convert to printable ASCII, ‘v’ and ‘F’, respectively.  On the other hand, $A4 and $F1 would have to undergo some bit-twiddling in order to produce printable ASCII.

There will be some PRNs whose bytes will fall into the ASCII control range $01-$1F and a $00 may sneak in there as well.  Also, for filenames, it’s best to avoid characters that aren’t alphanumeric, other than the underscore and tilde.  So I will have to formulate some rules on how to translate values that don’t neatly fall in the printable ASCII range.

Hmm. Perhaps trickier than I thought. The first approach that came to mind was, "well, just AND each byte with $3F and OR with $40 to get a value in the range $40-$7F." That's the general idea, though $7F is probably not a good filename character.

Anyway, the immediate problem that happens with that approach is that four different byte values map to each possible result byte value, as the top two bits of each byte just get chopped off. That reduces the range of possible temporary names and increases the probability of accidentally creating duplicate names. There might be ways to mitigate that, but I suspect it would always be possible.

So some other approach might be better. A quick scan of the Python module for creating temporary filenames gives me the impression that it first chooses eight random letters from the string "abcdedfhijklmnopqrstuvwxyz0123456789_" and then checks to see if that file already exists. If not, great, if so, try again up to some max number of times before giving up.

It occurs to me that a string of 32 characters might be a better fit for a 6502-family machine, but that's an implementation detail.

It may be that whatever method used to come up with a name has to check if that name is already in use.

$7F is a non-printing character, usually produced when you type the Delete key on most modern keyboards.  So that too would have to be translated.

There are actually two separate but interrelated translation requirements that depend on the pseudo-random character string’s intended usage.

1. Filename generation.  Depending on the filesystem and operating environment in use, there are bound to be some limitations on what is allowed in a filename, e.g., you can’t use a ‘/’ in a *NIX filename.  Therefore, the character set should be limited to ‘A-Z’, ‘a-z’, and ‘0-9’ to assure compatibility.
    
2. String generation. This would cover all cases other than filename generation.  The allowable range can be any of the printable seven-bit ASCII characters, including punctuation, with the possible exception of a blank.

 
A call to the random character string generation function would have to indicate which translation must be used.  In the POSIX environment, a call includes a pointer to a string buffer that is partially or completely filled with consecutive ‘X’ characters.  The name generation subfunction replaces each ‘X’ with a randomly-generated ASCII character.
In the case of filename generation, functions such as the mkstemp() POSIX call check to see if a file with the generated filename already exists in the subdirectory in which the new file is to be created.  I haven’t reviewed the code for mkstemp(), but imagine that if it discovers a duplicate, it generates a new name and tries again.

If you have an uptime counter with sufficient resolution, can't you just make that part of the temporary file name and not even worry about generating pseudo-random characters?