So a couple of months ago, I was going through a whole “random number” phase, reading everything I could about them. I eventually came across clock drift as a legit way of creating random numbers from a probabilistic machine (i.e. a computer). Clock drift is based on the slight fluctuation of quartz crystal oscillations found in both the CPU and Motherboard clocks on most modern computers.
I busily derived a function that should technically work, assuming the fact that rdtsc queries the CPU clock, whilst QueryPerformanceCounter (Windows only) queries the motherboard clock, which is a relatively safe assumption. I wrote this in VC++, so the assembly syntax would have to be changed if anyone ports this to any other OS:
[cpp]
void QueryRDTSC(__int64* tick) {
__asm {
xor eax, eax
rdtsc
mov edi, dword ptr tick
mov dword ptr [edi], eax
mov dword ptr [edi+4], edx
}
}
[/cpp]
And the actual RNG:
[cpp]
__int64 clockDriftRNG() {
__int64 CPU_start, CPU_end, OS_start, OS_end;
// get CPU ticks
QueryRDTSC(&CPU_start);
Sleep(1);
QueryRDTSC(&CPU_end);
// get OS ticks
QueryPerformanceCounter((LARGE_INTEGER*)&OS_start);
Sleep(1);
QueryPerformanceCounter((LARGE_INTEGER*)&OS_end);
// due to the low resolution of the mobo clock,
// sometimes, there will be zero time between ticks..
// I catch it, return it, and just get another more reliable number
if (OS_end – OS_start == 0)
return -1;
// return 0 or 1 randomly
// CPU clock is ~1000x faster than mobo clock
return ((CPU_end – CPU_start)/(OS_end – OS_start)%2);
}
[/cpp]
Now, the numbers actually looked pretty good, I wrote a C++ program that ouput 512×512 0s and 1s in a text file. And, in the spirit of RANDOM.org and Bo Allen, I plotted the data:
Relatively happy with the results (even if, realistically, I could only use my RNG to seed PRNGs), I just wanted to make sure I didn’t screw anything up so I posted a question on SO. Stephen Nutt had a very good comment, which made me feel slightly uneasy:
The Sleep function is limited by the resolution of the system clock, so Sleep (1) may not be doing what you want.
I actually agreed with him and wanted to figure out a more robust way of testing the clock drift between the motherboard and CPU timers. I decided that instead of Sleep(1), I would use an ASM nop loop:
[cpp]
void loop() {
__asm {
mov ecx, 1000
cylcles:
nop
loop cylcles
}
}
[/cpp]
1000 nops seemed like a pretty good equivalent to Sleep(t). I ran the program and got the text file. But when I plotted it, I was stupefied:
Whoa, what’s up with the streaks? Why does using an ASM sleep (independent of the system clock resolution) screw up the actual numbers? I knew I’d maybe have to do some Whitening to fix up the numbers, but I wasn’t expecting streaks.
I tried a superficial fix and changed mov ecx, 1000 to mov ecx, 5000:
Still no dice 🙁 The image is darker (I’m getting more 1s than 0s), which is expected (longer wait-time = larger sample = higher chance of %2). To this day I can’t figure out why Sleep(1) gives such a pretty answer, but the ASM solution is just abysmal (from a visual standpoint). With that said, after running some 4 million randomly-generated bytes (via the Sleep(1) method) through DIEHARD, the results are kind of awful. I think I might be able to use this as a PRNG seed, but I still need to run more tests (and maybe fix some implementation details) before I use it as a RNG.
If you’re wondering, I wrote the RNG for a non-deterministic Virtual Machine I’m working on. I just wanted to post this on here because I’ll probably lose the code and hey, I have a blog now.