/*****************************************************************************/
/* rand.c V5.11 for TMS3203x/4x                                             */
/* Copyright (c) 1992-1999 Texas Instruments Incorporated                    */
/*                                                                           */
/* NOTE:  This file should be compiled with the -mm (short multiply)         */
/*        switch for best results.                                           */
/*****************************************************************************/
#include <stdlib.h>

static unsigned next = 1;

/****************************************************************************/
/* RAND() - COMPUTE THE NEXT VALUE IN THE RANDOM NUMBER SEQUENCE.           */
/*                                                                          */
/*     The sequence used is x' = (A*x) mod M,  (A = 16807, M = 2^31 - 1).   */
/*     This is the "minimal standard" generator from CACM Oct 1988, p. 1192.*/
/*     The implementation is based on an algorithm using 2 31-bit registers */
/*     to represent the product (A*x), from CACM Jan 1990, p. 87.           */
/*                                                                          */ 
/****************************************************************************/ 
#define A 16807u                        /* MULTIPLIER VALUE    */

int rand()
{
     unsigned x0 = (next << 16) >> 16;  /* 16 LSBs OF SEED     */
     unsigned x1 = next >> 16;          /* 16 MSBs OF SEED     */
     unsigned p, q;   /* MSW (31 bits), LSW OF PRODUCT (31 bits) */

     /*---------------------------------------------------------------------*/
     /* COMPUTE THE PRODUCT (A * next) USING CROSS MULTIPLICATION OF        */
     /* 16-BIT HALVES OF THE INPUT VALUES.  THE RESULT IS REPRESENTED AS 2  */
     /* 31-BIT VALUES.  SINCE 'A' FITS IN 15 BITS, ITS UPPER HALF CAN BE    */
     /* DISREGARDED.  USING THE NOTATION val[m::n] TO MEAN "BITS n THROUGH  */
     /* m OF val", THE PRODUCT IS COMPUTED AS:                              */
     /*   q = (A * x)[0::30]  = ((A * x1)[0::14] << 16) + (A * x0)[0::30]   */
     /*   p = (A * x)[31::60] =  (A * x1)[15::30]       + (A * x0)[31]  + C */
     /* WHERE C = q[31] (CARRY BIT FROM q).  NOTE THAT BECAUSE A < 2^15,    */
     /* (A * x0)[31] IS ALWAYS 0.                                           */
     /*---------------------------------------------------------------------*/
     q = ((A * x1) << 17 >> 1) + (A * x0); /* q[31] is the carry    */
     p = ((A * x1) >> 15) + (q >> 31); /* q>>31 moves the carry to the lsb  */
     q = q << 1 >> 1;  /* CLEAR CARRY which is q[31]*/

     /*---------------------------------------------------------------------*/
     /* IF (p + q) < 2^31, RESULT IS (p + q).  OTHERWISE, RESULT IS         */
     /* (p + q) - 2^31 + 1.  This can be proved as follows:                 */
     /* A * x = [p, q] = p * 2^31 + q  = p * [(2^31 - 1) + 1] + q           */
     /*       = p * (2^31 - 1) + (p + q)                                    */
     /* Thus mod(a*x, 2^31 - 1) = mod( p+q, 2^31 - 1)                       */
     /*                         = p + q for  p + q < 2^31 -1                */
     /*                         = p + q - 2^31 + 1 otherwise              */
     /* The last line follows by observing that p+q is always less than     */
     /* 2^32.                                                               */
     /*---------------------------------------------------------------------*/
     p += q;  /* form p + q and now p is p + q */
     
     /* Now p has the value of p + q.  If p[31] = 1, p+q > 2^31 -1 and if   */
     /*  p[31] = 0, p+q <= 2^31 - 1.  Thus p >> 31 adds 0 or 1 as needed.   */
     /* ( ( ... ) << 1 ) >> 1 clears bit 31 which does nothing if it is     */
     /* already 0 but subtracts 2^31 if it is 1.                            */

     return next = ((p + (p >> 31)) << 1) >> 1; /* ADD CARRY, THEN CLEAR IT */
}

/****************************************************************************/
/* SRAND() - SET THE INITIAL SEED FOR RAND().                               */
/****************************************************************************/
void srand(unsigned seed)
{
     next = seed;
}