Reverse Engineering the TI BASIC PRNG

Blog Administration

Friday, November 13. 2009

Posted by Tim Hentenaar in Programming at 17:46 | Comments (0) | Trackbacks (0)

Reverse Engineering the TI BASIC PRNG

The other day, I decided to reverse engineer the TI BASIC pseudo-random number generator. I was curious to see what sort of algorithm it used, and I couldn't find such an analysis elsewhere on the internet. I've read the book "TI 99/4A Intern" by Heiner Martin (I'd recommend it to any TI enthusiast), and it provides a ton of useful insight into the inner workings of the BASIC ROMs. However, I wanted to reverse engineer the algorithm myself, without the comments from the book.

Source code of my C implementation of TI BASIC's PRNG with test data can be found: here.

Below is an explanation of the exact routines:

The GPL RAND command is the core of the TI BASIC PRNG (comments added):



LI   R4,>6FE5      ; R4 = >6fe5

MPY  @>83C0,R4     ; R4,R5 = R4 × @>83C0 (initially >3567 when BASIC loads)

AI   R5,>7AB9      ; R5 += >7ab9

MOV  *R5,@>83C0    ; R5 -> @>83C0

MOVB R13,R6        ; 'm' (>64 when called from BASIC) -> R6

SRL  R6,8          ; R6 & 0xff

INC  R6            ; R6++ (prevent division by zero)

CLR  R4	           ; R4 = 0

SWPB R5	           ; Swap bytes in R5

DIV  R6,R4	   ; R5 / R6 -> R4 (mod -> R5)

MOVB @>83EB,@>8378 ; Return pseudo-random number (R5 % R6)

JMP  >02AA

By the above code, you can already see that this is a simple linear congruential generator with a twist. The GPL code above implements the recurrence relation: Given: a = 0x6fe5, c = 0x7ab9, m = value passed into function (0x64 when called from TI BASIC)

X_n+1 = aX_n + c

and yields an 8-bit integer N by:

N = (X_byte[0] <--> X_byte[1]) mod m

This equates to the following simple C code:

static uint16_t seed;

/* RAND: Generate an 8-bit pseudo-random number */
uint8_t gpl_rand(uint8_t divisor) {
/* Update the seed */
seed = ((uint32_t)(seed * 0x6fe5) & 0xffff) + 0x7ab9;

/* Swap bytes, and compute modulus */
return ((((seed & 0xff00) >> 8) | ((seed & 0x00ff) << 8)) % (!divisor ? 1 : divisor));
}

However, there's more to TI BASIC's PRNG than this one simple calculation. The actual BASIC RND function is implemented in GPL as follows: (comments added)



4F00: ST   @>834A,>3F		; Zero loop counter: >3F (63)

4F03: ST   @>8310,>4B    	; Number buffer address: >834B 

4F06: RAND >63           	; Get a pseudo-random number (using 100 as the divisor)

4F08: CZ   @>8378        	; If then number isn't zero, goto >4F16

4F0A: BR   >4F16    	

4F0C: DEC  @>834A       	; Decrement the zero loop counter             

4F0E: CZ   @>834A        	; If the zero loop counter is 0, goto >4F23 (return 0)

4F10: BS   >4F23    	

4F12: BR   >4F06    		; Otherwise, continue the loop

4F14: RAND >63           	; Get the next pseudo-random number

4F16: ST   @>8378,*>8310 	; Store it at *>8310

4F1A: CEQ  @>8310,>51    	; if the number buffer address is >8351

4F1D: BS   >4F25		; Exit the routine

4F1F: INC  @>8310        	; Otherwise, prepare to store the next number

4F21: BR   >4F14		; Loop to generate it

4F23: CLR  @>834B        

4F25: CONT			; Return

This generates a set of seven 8-bit pseudo-random numbers. These number are all used as part of a larger, 14-precision fixed-point number. However, the PRINT command truncates these 14-precision numbers down to 10 by way of simple rounding. The original representation is only used internally.

When generating the first number, if the GPL RAND function returns zero 63 times, then the number returned is simply zero. This appears to have been written this way to guard against a broken RAND implementation. Back then programmers really new how to think ahead.

In C, I have crafted an implementation of the above as follows:

/* Equivalent to PRINT RND in TI Basic */
char *rnd() {
uint8_t rnds[7]; int i; char *n;

/* Try up to 64 times to come up with a non-zero pseudo-random integer */
for (i=0;i<63;i++) if ((rnds[0] = gpl_rand(100)) != 0) break;
if (rnds[0] == 0) return strdup("0");

/* Generate the rest of the set */
for (i=1;i<7;i++) rnds[i] = gpl_rand(100);

/* PRINT rounds up if the 6th number generated is >= 0x32 (50) */
if (rnds[5] >= 0x32) rnds[4]++;

/* PRINT prepends a leading zero if the first byte is < 0x10 */
if (rnds[0] < 0x10) {
memmove(&rnds[1],&rnds[0],6);
rnds[0] = 0;
}

/* Convert to string */
n = malloc(22);
snprintf(n,22,".%02d%02d%02d%02d%02d",rnds[0],rnds[1],rnds[2],rnds[3],rnds[4]);
return n;
}

This analysis is proven by my implementation as shown below: (Source Code)

tim@tim-laptop:~/code$ gcc -o ti-prng ti-prng.c

tim@tim-laptop:~/code$ ./ti-prng

RAND:

	Iteration: 01, Modulus: 52 (0x34), Seed: 0xe8dc [PASS]

	Iteration: 02, Modulus: 91 (0x5b), Seed: 0x2b85 [PASS]

	Iteration: 03, Modulus: 87 (0x57), Seed: 0x13b2 [PASS]

	Iteration: 04, Modulus: 78 (0x4e), Seed: 0x46f3 [PASS]

	Iteration: 05, Modulus: 23 (0x17), Seed: 0x4f18 [PASS]

	Iteration: 06, Modulus: 07 (0x07), Seed: 0xa331 [PASS]

	Iteration: 07, Modulus: 32 (0x20), Seed: 0xb48e [PASS]



Basic RND():

	Iteration: 01, Number: .5291877823 [PASS]

	Iteration: 02, Number: .3913360723 [PASS]

	Iteration: 03, Number: .5343438556 [PASS]

	Iteration: 04, Number: .3894551053 [PASS]

	Iteration: 05, Number: .2555008073 [PASS]

	Iteration: 06, Number: .5621974824 [PASS]

	Iteration: 07, Number: .2553391677 [PASS]

	Iteration: 08, Number: .5882911741 [PASS]

	Iteration: 09, Number: .7000201301 [PASS]

	Iteration: 10, Number: .0010849577 [PASS]

Note: I didn't cover BASIC's RANDOMIZE, because it's not pertinent to the algorithm itself. When you call RANDOMIZE without arguments in BASIC, the low byte of the seed is set to the last random number generated by RAND.

If you want to see how RANDOMIZE sets the seed, view the code.

Trackbacks

Trackback specific URI for this entry

No Trackbacks

Comments

Display comments as (Linear | Threaded)

No comments

Add Comment

Name
Email
Homepage
In reply to
Comment	You can use [geshi lang=lang_name [,ln={y\|n}]][/lang] tags to embed source code snippets Enclosing asterisks marks text as bold (word), underscore are made via _word_. Standard emoticons like :-) and ;-) are converted to images. To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly. Enter the string from the spam-prevention image above:
	Remember Information?