5

I'm trying to create a complete random number in assembly but it's every time I start the program it gives me the same numbers, in the same order. If the numbers are 12, 132, 4113 or something, it'll repeat them every time I start the code.

The program I'm trying to make is something like a guessing game.

    IDEAL
MODEL small
STACK 100h
DATASEG
;vars here
RNG_Seed dw ? 

CODESEG
; Generates a pseudo-random 15-bit number.
; Parameters: <none>
; Clobbers:   AX, DX
; Returns:    AX contains the random number
proc GenerateRandNum
   push bx
   push cx
   push si
   push di


   ; 32-bit multiplication in 16-bit mode (DX:AX * CX:BX == SI:DI)
   mov  ax, [RNG_Seed]
   xor  dx, dx
   mov  cx, 041C6h
   mov  bx, 04E6Dh
   xor  di, di
   push ax
   mul  bx
   mov  si, dx
   xchg di, ax
   mul  bx
   add  si, ax
   pop  ax
   mul  cx
   add  si, ax


   ; Do addition
   add  di, 3039h
   adc  si, 0


   ; Save seed
   mov [RNG_Seed], di


   ; Get result and mask bits
   mov  ax, si
   and  ah, 07Fh


   pop  di
   pop  si
   pop  cx
   pop  bx
   ret
endp GenerateRandNum

What can I do to get different random numbers every run?

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
S. josh
  • 79
  • 7
  • Is your program running without an OS? – James Aug 09 '17 at 12:11
  • @James what do you mean in os? – S. josh Aug 09 '17 at 12:19
  • Operating System – Ped7g Aug 09 '17 at 12:22
  • For a PRNG, you might want to use something more like xorshift+, to avoid needing a 32-bit multiply. OTOH, finding constants that don't suck for a 32-bit version would be non-trivial. [The reference version](http://xoroshiro.di.unimi.it/) is for 64-bit integers. (You could just implement the 64-bit version to get a fairly high quality PRNG, especially if you can use 386 SHRD / SHLD to make extended-precision shifts efficient.) – Peter Cordes Aug 09 '17 at 12:57
  • 1
    @PeterCordes The paper has constants for 32 bit, too. See, e.g. [here](https://github.com/fuzxxl/Xorshift/blob/master/src/Random/Xorshift/Int32.hs) – fuz Aug 09 '17 at 13:53
  • Ah, just xorshift, not xorshift+. Yeah, that's still plenty good for a game, and might even be faster than three 16-bit `mul` instructions, especially on CPUs with efficient SHRD (not AMD). [It is higher quality than a mul/add Linear Congruential Generator](https://stats.stackexchange.com/a/83557/69037), and maybe even good enough for Monte Carlo simulations. (Even the LCG is good enough for a game, though, given a random seed.) – Peter Cordes Aug 10 '17 at 00:08

1 Answers1

4

You need to initialize RNG_Seed with something "random". And that's actually a bit problematic on deterministic machine such as computer is.

Especially if you want that random to be strong enough for encryption, then it would take you just few hours to study current solutions, some industry solutions even involving special HW chip with white noise generator, used as random value generator.

As you want it only for a game, it's not that bad, but still a bit tricky.

I just guess you are in real mode (as you use 16b registers), so read BIOS ticks-since-midnight as one source of entropy:

xor ah,ah  ; ah = 0
int 1Ah    ; returns in cx:dx ticks since midnight (18.2Hz ticks)
; let's mix the cx:dx a bit together to get a bit more entropy out of it
rol cx,8
xor dx,cx
xor [RNG_Seed],dx ; "add" that entropy to the original seed

This will improve it a bit, but it's still a bit poor solution (running the game at the same time may easily produce the same random values), so here is another suggestion for "cheap" source of entropy:

Ask player for example to enter name (at least 3 chars), and time each keystroke by doing inc counter all the time while waiting for key, keeping lower 4 bits of counter every time (3 chars + enter = 4 * 4bits = 16 bits in total). Then "add" (xor) that to the RNG_Seed again.

These two things should produce enough entropy for game RNG (but not enough for security purposes, like encryption).


EDIT: as noted in comments, when mixing different seed values, make sure they either don't relate, or use rather add than xor. My original idea was to use BIOS ticks since midnight, xor-ed against some random memory of your variable (probably zero, BTW, cleared by OS during exe load), and then measuring time of keystrokes of user, those composed as 4:4:4:4 bits of 4 keystrokes (no xor, just appended to each other until full 16b are ready), and to use final value with xor over the main seed. As the keystrokes are not related in any way to the BIOS ticks, this shouldn't interfere and xor should work well in this particular case.

Also why 4:4:4:4 from keystrokes, and not single 16b value every time xor-ed over and over. I expect you to implement that keystroke delay-counter by calling int 16h, ah=1, so if you will loop infinitely over this one, and increment some counter, it's very likely it will run over 16 values very quickly (under thousand of second I guess). Then using the low 4 bits of such counter can be hardly related to the way how [fast] the user hits the keys. While on very slow computer using full 16b of waiting for user may actually produce somewhat similar bit patterns in upper bits (i.e. user hitting key every time somewhere between 10000-13000 value of counter -> top 2 bits are always zero and the whole top 8 bits will be very similar each time). So that's what I mean by using low 4 bits, joining four of them together to form 16b value. If the user enters longer name, I wouldn't even use those further keystrokes for seed adjusting, only the first four. And I would probably do some debugging to see how it works in reality, maybe I'm overly optimistic about the results and there's some hidden sync-like catch. But I'm too lazy to actually write it and try (it's like ~20 lines of code, but would require dosbox and some DOS debugger).

Ped7g
  • 16,236
  • 3
  • 26
  • 63
  • 4
    Creating entropy out of a (mostly) deterministic machine was always one of my favourite task - very creative! Would be fun to write a big list of entropy sources along with their size in bits (this can be difficult to prove). For example, beside `rdtsc`, `rdseed` and `rdrand`, the time (in whatever unit) to the next vertical retrace was a nice source :) – Margaret Bloom Aug 09 '17 at 12:35
  • 1
    @S.josh: [`RDRAND r16`](https://hjlebbink.github.io/x86doc/html/RDRAND.html) *should* work in 16-bit mode, since it doesn't use VEX encoding (which is why some BMI/BMI2 instructions aren't available in 16-bit mode). But of course only on CPUs that support it, and even then the RNG hardware in a specific CPU can be malfunctioning, causing it to return CF=0 non-random data. – Peter Cordes Aug 09 '17 at 13:05
  • 2
    @Ped7g: `xor` is a dangerous mixing function for things that might be correlated. [As @Yakk says](https://stackoverflow.com/questions/45069219/how-to-succinctly-portably-and-thoroughly-seed-the-mt19937-prng#comment77114547_45070076): `+` is usually better: `x+x` only burns 1 bit of entropy in `x`, while `x^x` burns them all, in the case where you ended up with the same value twice. – Peter Cordes Aug 09 '17 at 13:12