Generating random numbers in 68k asm

; Exploring K240, a disassembly project

This article looks at the random number generator code used by the Commodore Amiga game K240, written in 68k assembly language, and how it is used in practice to generate random chances.

  1. K240’s random number generator code
  2. Function
  3. How it is called

K240’s random number generator code

_SeedRNG:                      ; called during game startup
        TST.L   D0
        BEQ.S   _GenerateSeed
        MOVE.L  D0,intRNG2
        RTS

_GenerateSeed:
        MOVEQ   #0,D1
        MOVE.W  VHPOSR,D1      ; read CRT beam position, Amiga-specific
        DIVU    #$0064,D1
        SWAP    D1
loop00C02:
        MOVEQ   #100,D0
        BSR.S   _RandInt       ; Generate a random number from 0 to 99
        DBF     D1,loop00C02
        RTS

_RandInt:
        MOVEM.L D1-D4,-(A7)
        MOVE.B  intRNG5,D1
        MOVE.B  intRNG4,D2
        MOVE.B  intRNG3,D3
        MOVE.B  D2,D4
        LSL.B   #1,D4
        EOR.B   D3,D4
        ROXL.B  #2,D4          ; shuffling bytes around
        ROXR.B  #1,D1
        ROXR.B  #1,D2
        ROXR.B  #1,D3
        MOVE.B  D1,intRNG3
        MOVE.B  D2,intRNG5
        MOVE.B  D3,intRNG4
        MOVEQ   #0,D1
        MOVE.W  intRNG4,D1
        DIVS    D0,D1
        SWAP    D1
        MOVE.W  D1,D0
        MOVEM.L (A7)+,D1-D4
        TST.W   D0             ; set condition codes
        RTS

intRNG0:
        DS.L    1              ; 00 00 00 00
intRNG2:
        DS.B    1              ; 00
intRNG3:
        DC.B    $13            ; 19
intRNG4:
        DC.B    $a5            ; 165
intRNG5:
        DC.B    $1d            ; 29

Function

Since the most popular models of Amiga did not include a real-time clock, this game seeds the initial random value from VHPOSR, the register which contains the current horizontal position of the CRT beam on screen. The exact position isn’t important, only that it provides unpredictable number.

This number is used to determine the number of initial times to call _RandInt, the random number generator subroutine that is often called during the game. The results of these initial rolls are discarded, but each time _RandInt is called it advances the RNG internally.

The subroutine _RandInt takes the number in register d0 and returns a randomly selected value between 0 and d0 minus one. For example, if d0 is 100 when _RandInt is called, d0 will then contain a random number from 0 to 99.

Each time _RandInt is called, it shuffles the numbers held in three bytes in a certain manner, using LSL.B (logical shift left, here effectively divide by two), EOR.B (exclusive OR) and a series of ROXL and ROXR (rotate left and right), storing the results in the three bytes in a different order.

In other words, the RNG is purely deterministic, and the only question is how many iterations into the RNG the player will achieve. Since K240 calls on the RNG a lot, and it shuffles each time it is called, it’s difficult to predict or bias the RNG (“RNG manipulation”) to the player’s benefit.

After the shuffle, it takes the last two of the shuffled bytes as a word, which may be between $0000 and $FFFF, i.e. between 0 and 65536. It then performs a DIVS to divide that by the number provided in d0, taking the modulo of that and returning it in d0.

Note that it only produces 16-bit numbers, i.e. 0 to 65536. This is plenty for the game’s purposes. The biggest random number range I see K240 generate is 1,000, used to calculate the alien population in a false intel report (although the maximum result of 999 will be rounded to 992).

How it is called

The subroutine _RandInt is called at a number of places in K240, often to decide a chance for an event to take place or not. Sometimes, it instead determines a number, such as a random value or location.

An example of both is generating the amount of ore is in an asteroid:

_InitOre:
        LEA     tblInitOre,A1  ; table with chance and amount of each ore
        LEA     (60,A0),A2     ; ore
        MOVEQ   #9,D1          ; set up a loop from 0-9
loop12CFC:
        CLR.W   (A2)           ; reset ore to 0
        MOVEQ   #100,D0
        JSR     _RandInt       ; 0-99
        CMP.W   (A1),D0        ; Draws chance from table
        BPL.S   .next_12D20
        MOVE.W  (4,A1),D0      ; maximum ore amount from table
        SUB.W   (2,A1),D0      ; minimum ore amount from table
        ADDQ.W  #1,D0          ; +1
        JSR     _RandInt       ; return 0 to (min-max)
        ADD.W   (2,A1),D0      ; +min
        MOVE.W  D0,(A2)        ; store that amount
.next_12D20:
        ADDQ.L  #6,A1          ; Next entry in table
        ADDQ.L  #2,A2          ; Next ore
        DBF     D1,loop12CFC
        RTS

Chance calculations are usually performed by generating a random number, then comparing it to a given value (using CMP, CMPI or TST). It then either branches or continues based on some condition code (e.g. BPL, BMI, etc).

In the ore generation, for example, CMP and BPL (compare and branch if positive) are used to continue on a percentage chance:

        MOVEQ   #100,D0
        JSR     _RandInt
        CMP.W   (A1),D0        ; Draws chance from table
        BPL.S   .next_12D20    ; The code after this generates the ore

With CMP and BPL, the code continues with a chance of the value given to CMP divided by the value in d0. Another example of this is the 20% chance to shoot (technically CMPI here since it’s comparing an immediate value, but the effect is the same):

        MOVEQ   #100,D0
        JSR     _RandInt
        CMPI.B  #20,D0        ; 20% chance
        BPL.S   ret10D84      ; The code after this fires the Vortex
LaunchVortex:                 ; This code will run 20% of the time

Here’s another example using a four in ten chance for the Shipyard to continue working during a manpower shortage:

        MOVEQ   #10,D0
        JSR     _RandInt
        CMPI.B  #$04,D0
        BPL.S   ret143C4      ; The next lines process shipbuilding

The reverse, branching on a percentage chance, can be performed using CMPI and BMI. From the code which fires Vortex Mine from alien ships:

_AlienVortex04:
        MOVEQ   #100,D0
        JSR     _RandInt
        CMPI.B  #10,D0        ; 10%
        BMI.S   LaunchVortex  ; LaunchVortex will trigger 10% of the time
        RTS                   ; It will reach here the other 90% of the time

Care must be taken to avoid errors. In the following example, the programmer has written a continue-on-chance, usually CMP and BPL. However, they’ve instead used CMP and BMI, and reversed the operands in the CMP. The result is an off-by-one error that makes the chance to continue 1% higher:

        MOVE.B  (0,A1,D1.W),D1  ; d1 = radiation chance
        MOVEQ   #100,D0
        JSR     _RandInt
        CMP.B   D0,D1           ; note: D0,D1 instead of D1,D0
        BMI.S   _14988          ; chance is 1% higher than table suggests
        SUBQ.W  #1,D6
_14988:

TST is essentially just CMPI with zero, and easy to use with BEQ or BNE to give a one in d0 chance of something.

For example:

        MOVEQ   #2,D0
        JSR     _RandInt    ; will return 0 or 1
        TST.B   D0          ; essentially the same as CMPI.B #0,D0
        BEQ.S   _0F292      ; branch on 0, continue on 1

Another way to do continue-on-chance with a one in d0 chance, for example, 1 in 10:

        MOVEQ   #10,D0
        JSR     _RandInt
        BNE.S   ret109A4    ; will branch on non-zero

« Back to index page