Implementation of TI Basic's PRNG

ti-prng.c

/**
 * Implementation of the TI BASIC PRNG
 *
 * Copyright (C) 2009, Tim Hentenaar
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met: 
 *
 * 1. Redistributions of source code must retain the above copyright notice, this
 *    list of conditions and the following disclaimer. 
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution. 
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

/* These are test results from runs of the GPL Rand function in a TI emulator */
uint16_t gpl_rand_test_results[][2] = {
    { 0x34, 0xe8dc },
    { 0x5b, 0x2b85 },
    { 0x57, 0x13b2 },
    { 0x4e, 0x46f3 },
    { 0x17, 0x4f18 },
    { 0x07, 0xa331 },
    { 0x20, 0xb48e }
};

/* The first ten sequences generated from RND */
const char *rnd_test_results[10] = {
    ".5291877823",
    ".3913360723",
    ".5343438556",
    ".3894551053", 
    ".2555008073",
    ".5621974824",
    ".2553391677",
    ".5882911741",
    ".7000201301",
    ".0010849577",
};

/* Value of the seed after RANDOMIZE */
int32_t randomize_test_results[14][2] = {
    { 0, 0 },
    { 1,   0x4001 },
    { 2,   0x4002 },
    { 100, 0x4101 },
    { 200, 0x4102 },
    { 256, 0x4102 },
    { 1000, 0x410a },
    { 1500, 0x410f },
    { 10000, 0x4201 },
    { 100000, 0x420a },
    { 1000000, 0x4301 },
    { 1506631, 0x4301 },
    { -1, 0xbfff },
    { -100, 0xbeff }
};

/* The initial seed */
uint16_t seed = 0x3567;

/* RAND: Generate a 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));
}

/* 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;
}

/* TI Basic RANDOMIZE */
void randomize(int32_t s) {
    /* Randomize appears to compute the seed this way */
    int ex = 0; uint32_t x = (s < 0) ? (~s+1) : s;
    if (s == 0) { seed = 0; return; }

    /* The seed is: 0x4000 + (exponent << 8) + (s / 100^exponent) */
    while ((x / 100) > 0) { ex++; x /= 100; }
    seed = 0x4000 + (ex << 8) + x;

    /* Handle negative numbers */
    if (s < 0) seed = ~(seed-1);
}

int main() {
    int i,x; char *f;

    /* Test the GPL 'RAND' function */
    printf("RAND:\n");
    for (i=1;i<8;i++) {
        x = gpl_rand(100);
        printf("\tIteration: %02d, Modulus: %02d (0x%02x), Seed: 0x%04x [%s]\n",i,x,x,seed,
              ((x == gpl_rand_test_results[i-1][0] && 
             seed == gpl_rand_test_results[i-1][1]) ? "PASS" : "FAIL"));
    }
    
    /* Reset seed */
    seed = 0x3567;

    /* Test TI Basic RND function */
    printf("\nBasic RND():\n");
    for (i=1;i<11;i++) {
        f = rnd();
        printf("\tIteration: %02d, Number: %s [%s]\n",i,f,
               ((!strncmp(f,rnd_test_results[i-1],strlen(rnd_test_results[i-1]))) ? "PASS" : "FAIL"));
        free(f);
    }

    /* Test TI Basic RANDOMIZE function */
    printf("\nBasic RANDOMIZE():\n");
    for (i=1;i<15;i++) {
        randomize(randomize_test_results[i-1][0]);
        printf("\tIteration: %02d, Number: %d, Seed: 0x%04x [%s]\n",i,randomize_test_results[i-1][0],seed,
               ((seed == (uint16_t)randomize_test_results[i-1][1]) ? "PASS" : "FAIL"));
    }

    return 0;
}

/* vi:set ts=4 sw=4 expandtab sta: */