Bomb Squad RNG

[walker7]

Does anyone know how the RNG works on Bomb Squad? It would be interesting to know the RNG iteration algorithm, as well as how it generates 1-digit, 2-digit, and 3-digit codes for the game.

[intvnut]

It uses the EXEC's built in pseudo-random number generator. Here's the relevant code that generates the 1 to 3 digits:

.

        MVI     G_016F, R0                      ; 511A   0280 016F
        MVII    #$0170, R4                      ; 511C   02BC 0170
        MOVR    R0,     R1                      ; 511E   0081
L_511F:
        MVII    #$000A, R0                      ; 511F   02B8 000A

        JSR     R5,     X_RAND2                 ; 5121   0004 0114 029E

        MVO@    R0,     R4                      ; 5124   0260
        DECR    R1                              ; 5125   0011
        BNEQ    L_511F                          ; 5126   022C 0008

.

The above loop calls the EXEC's random number generator (named X_RAND2 by my disassembler) 1 to 3 times, asking for random numbers in the range 0 - 9. The range is set by the value in R0 ($A, the number 10), initialized at location $511F.

 

The high level algorithm of the random number generator at X_RAND2 appears to be this: Count the number of bits in the desired range (4 bits for a number 0 - 9), and generate an N-bit random number. If that N-bit number is in range, return it, otherwise try again.

 

The routine that generates an N-bit random number looks like this:

.

L_167D:
        PSHR    R5                  ; 167D   Save return address
        MOVR    R0,     R5          ; 167E   Copy number of bits (N) to R5
        BEQ     L_17D4              ; 167F   If N was zero, return

        PSHR    R1                  ; 1681   Save R1
        PSHR    R2                  ; 1682   Save R2
        CLRR    R2                  ; 1683   Clear R2.  R2 will hold a mask
        MVI     G_035E, R0          ; 1684   Get current RNG seed into R0
L_1686:
        SLL     R0,     2           ; 1686   \_ R0 <<= 4
        SLL     R0,     2           ; 1687   /
        MOVR    R0,     R1          ; 1688   R1 = R0
        XOR     G_035E, R0          ; 1689   R0 = R0 ^ seed
        SWAP    R1,     1           ; 168B   R1 = (R1 >>  | (R1 << 
        SLL     R1,     1           ; 168C   R1 = R1 << 1
        XORR    R1,     R0          ; 168D   R0 = R0 ^ R1
        SLL     R1,     2           ; 168E   R1 <<= 2
        XORR    R1,     R0          ; 168F   R0 = R0 ^ R1
        RLC     R0,     1           ; 1690   C = MSB of R0
        MVI     G_035E, R0          ; 1691   \_ R0 = (seed << 1) | C
        RLC     R0,     1           ; 1693   /
        MVO     R0,     G_035E      ; 1694   seed = R0
        SETC                        ; 1696   \_ Shift a 1 into R2.  At the end
        RLC     R2,     1           ; 1697   /  R2 has a 1 for each output bit
        DECR    R5                  ; 1698   \_ Repeat until all bits have
        BNEQ    L_1686              ; 1699   /  been generated

        ANDR    R2,     R0          ; 169B   \_ Mask away unwanted bits and
        B       L_17D2              ; 169C   /  and return (restoring R2 and R1)


L_17D2:
        PULR    R2                  ; 17D2   Restore R2
        PULR    R1                  ; 17D3   Restore R1
L_17D4:
        PULR    R7                  ; 17D4   Return

.

Ok, that RNG looks like a hot mess. What's it actually doing? It's a linear feedback shift register.

 

If you look at all that computation involving R0 and R1, in the end only one bit is saved: bit 15 of R0 gets shifted into the carry bit by the instruction at $1690, and that bit gets shifted into the LSB of the seed by the instruction at $1693 and saved back to the seed.

 

What does that bit contain?

• The code at $1686, $1687 and $1689 make bit 15 the XOR of bits 15 and 11 of the seed.
• The code at $1688, $168B, $168C and $168D XORs in bit 2 of the original seed
• The code at $168E and $168F XORs in bit 0 of the original seed

This is a so-called Fibonacci realization of a 16-bit LFSR with the taps 0, 4, 13, 15. (The tap numbers are 15 minus the bit position.) This LFSR is the [16,15,13,4] polynomial in the list of maximal-sequence 16-bit LFSRs here. I've also written a C program to verify that it produces a maximal sequence.

 

The EXEC seeds the random number generator with $3FF at bootup, and then cycles it while the EXEC is idle. So, while you're sitting there at the title screen, or the EXEC's waiting for input, it's busy calling the random number generator over and over generating random numbers used for nothing. This causes the random number generator's actual output to vary based on inputs from the humans playing the games.

 

Note that a Galois realization of the same random number generator would have been much cheaper. In the Galois realization, you shift the seed left by one, and if C was set, you XOR in the polynomial for the RNG. This is the approach the RNG in SDK-1600 takes. They produce equivalent random number sequences, just shifted in time. (ie. it takes a different starting seed for the Galois implementation vs. the Fibonacci implementation to generate the exact same output sequence, but both generate the same sequence for the same polynomial.) Here's a Q&D version I just whipped up, with very little effort:

.

        MVI     G_035E, R0
        MVII    #$8805, R1
        CLRR    R2
        DECR    R2

loop:   SLLC    R0,     1
        BNC     no_xor
        XORR    R1,     R0

no_xor: SLL     R2
        DECR    R5
        BNEQ    loop

        MVO     R0,     G_035E
        COMR    R2
        ANDR    R2,     R0

.

So there ya go.

 

And in case you wonder why I happen to know so much about LFSRs, I happened to do a project involving one back in college. (Super-high res PDF of the design here. And yes, I laid out every one of those transistors myself, except for the 'pad frame' that surrounds the design.) The generation of random numbers is too important to be left to chance.

Edited May 30, 2015 by intvnut

[intvnut]

Does anyone know how the RNG works on Bomb Squad? It would be interesting to know the RNG iteration algorithm, as well as how it generates 1-digit, 2-digit, and 3-digit codes for the game.

 

I'm just curious... did this answer your question?

[walker7]

 

I'm just curious... did this answer your question?

Yes.