Maths (Arithmetic): GetRandomNumbers

       Name: GetRandomNumbers                                        [Show more]
       Type: Subroutine
   Category: Maths (Arithmetic)
    Summary: Generate pseudo-random numbers from the random number seeds
  Deep dive: Random numbers
    Context: See this subroutine in context in the source code
 References: This subroutine is called as follows:
             * AddDebrisParticleToBuffer calls GetRandomNumbers
             * AddMovingParticleToBuffer calls GetRandomNumbers
             * AddSmokeParticleToBuffer calls GetRandomNumbers
             * AddSprayParticleToBuffer calls GetRandomNumbers
             * DropARockFromTheSky calls GetRandomNumbers
             * DropRocksFromTheSky calls GetRandomNumbers
             * PlaceObjectsOnMap calls GetRandomNumbers


 This algorithm appears in the original 1986 ARM Assembler manual that came
 with Acorn's ARM Evaluation System (it's in section 11.2 on page 96). It also
 appears in later Acorn manuals, such as Acorn Desktop Assembler (release 2),
 where it's on page 186.

 Here's the algorithm's description from the manual:

 "It is often necessary to generate (pseudo-)random numbers and the most
 efficient algorithms are based on shift generators with exclusive-or feedback
 rather like a cyclic redundancy check generator. Unfortunately the sequence of
 a 32-bit generator needs more than one feedback tap to be maximal length (that
 is 2^32-1 cycles before repetition). A 33-bit shift generator with taps at
 bits 20 and 33 is required. The basic algorithm is newbit := bit33 eor bit20,
 shift left the 33 bit number and put in newbit at the bottom. Then do this for
 all the newbits needed, that is 32 of them. Luckily this can all be done in
 five S cycles."


 Returns:

   R0                               A random number

   R1                               A random number


.GetRandomNumbers

 STMFD   R13!, {R14}                \ Store the return address on the stack

 LDR     R0, randomSeed1            \ Set R0 = randomSeed1

 LDR     R1, randomSeed2            \ Set R1 = randomSeed2

 TST     R1, R1, LSR #1             \ Set flags on R1 AND (R1 >> 1)

 MOVS    R14, R0, RRX               \ Rotate R0 right, incorporating the C flag,
                                    \ and store the result in R14, replacing the
                                    \ C flag with bit 0 from R0

 ADC     R1, R1, R1                 \ R1 = R1 + R1 + C

 EOR     R14, R14, R0, LSL #12      \ R14 = R14 EOR (R0 << 12)

 EOR     R0, R14, R14, LSR #20      \ R0 = R14 EOR (R14 >> 20)

 STR     R1, randomSeed1            \ Set randomSeed1 = R1

 STR     R0, randomSeed2            \ Set randomSeed2 = R0

 LDMFD   R13!, {PC}                 \ Return from the subroutine