# 2.11BSD#431 - /usr/src/games/fortune/rnd.c

##### Functions

    initstate         X
    random            X
    rnd               X
    setstate          X
    srandom           X
    srnd              X

##### Macros

    BREAK_0           X
    BREAK_1           X
    BREAK_2           X
    BREAK_3           X
    BREAK_4           X
    DEG_0             X
    DEG_1             X
    DEG_2             X
    DEG_3             X
    DEG_4             X
    MAX_TYPES         X
    SEP_0             X
    SEP_1             X
    SEP_2             X
    SEP_3             X
    SEP_4             X
    TYPE_0            X
    TYPE_1            X
    TYPE_2            X
    TYPE_3            X
    TYPE_4            X

       1: /*
       2:  * code for when the good (berkeley) random number generator is around
       3:  */
       4:
       5: rnd(num)
       6: {
       7:     return (random() % num);
       8: }
       9:
      10: srnd(num)
      11: {
      12:     srandom(num);
      13: }
      14:
      15: #ifdef  NO_RANDOM
      16:
      17: #ifndef lint
      18: static char sccsid[] = "@(#)random.c	4.2	(Berkeley)	83/01/02";
      19: #endif
      20:
      21: #include    <stdio.h>
      22:
      23: /*
      24:  * random.c:
      25:  * An improved random number generation package.  In addition to the standard
      26:  * rand()/srand() like interface, this package also has a special state info
      27:  * interface.  The initstate() routine is called with a seed, an array of
      28:  * bytes, and a count of how many bytes are being passed in; this array is then
      29:  * initialized to contain information for random number generation with that
      30:  * much state information.  Good sizes for the amount of state information are
      31:  * 32, 64, 128, and 256 bytes.  The state can be switched by calling the
      32:  * setstate() routine with the same array as was initiallized with initstate().
      33:  * By default, the package runs with 128 bytes of state information and
      34:  * generates far better random numbers than a linear congruential generator.
      35:  * If the amount of state information is less than 32 bytes, a simple linear
      36:  * congruential R.N.G. is used.
      37:  * Internally, the state information is treated as an array of longs; the
      38:  * zeroeth element of the array is the type of R.N.G. being used (small
      39:  * integer); the remainder of the array is the state information for the
      40:  * R.N.G.  Thus, 32 bytes of state information will give 7 longs worth of
      41:  * state information, which will allow a degree seven polynomial.  (Note: the
      42:  * zeroeth word of state information also has some other information stored
      43:  * in it -- see setstate() for details).
      44:  * The random number generation technique is a linear feedback shift register
      45:  * approach, employing trinomials (since there are fewer terms to sum up that
      46:  * way).  In this approach, the least significant bit of all the numbers in
      47:  * the state table will act as a linear feedback shift register, and will have
      48:  * period 2^deg - 1 (where deg is the degree of the polynomial being used,
      49:  * assuming that the polynomial is irreducible and primitive).  The higher
      50:  * order bits will have longer periods, since their values are also influenced
      51:  * by pseudo-random carries out of the lower bits.  The total period of the
      52:  * generator is approximately deg*(2**deg - 1); thus doubling the amount of
      53:  * state information has a vast influence on the period of the generator.
      54:  * Note: the deg*(2**deg - 1) is an approximation only good for large deg,
      55:  * when the period of the shift register is the dominant factor.  With deg
      56:  * equal to seven, the period is actually much longer than the 7*(2**7 - 1)
      57:  * predicted by this formula.
      58:  */
      59:
      60:
      61:
      62: /*
      63:  * For each of the currently supported random number generators, we have a
      64:  * break value on the amount of state information (you need at least this
      65:  * many bytes of state info to support this random number generator), a degree
      66:  * for the polynomial (actually a trinomial) that the R.N.G. is based on, and
      67:  * the separation between the two lower order coefficients of the trinomial.
      68:  */
      69:
      70: #define     TYPE_0      0       /* linear congruential */
      71: #define     BREAK_0     8
      72: #define     DEG_0       0
      73: #define     SEP_0       0
      74:
      75: #define     TYPE_1      1       /* x**7 + x**3 + 1 */
      76: #define     BREAK_1     32
      77: #define     DEG_1       7
      78: #define     SEP_1       3
      79:
      80: #define     TYPE_2      2       /* x**15 + x + 1 */
      81: #define     BREAK_2     64
      82: #define     DEG_2       15
      83: #define     SEP_2       1
      84:
      85: #define     TYPE_3      3       /* x**31 + x**3 + 1 */
      86: #define     BREAK_3     128
      87: #define     DEG_3       31
      88: #define     SEP_3       3
      89:
      90: #define     TYPE_4      4       /* x**63 + x + 1 */
      91: #define     BREAK_4     256
      92: #define     DEG_4       63
      93: #define     SEP_4       1
      94:
      95:
      96: /*
      97:  * Array versions of the above information to make code run faster -- relies
      98:  * on fact that TYPE_i == i.
      99:  */
     100:
     101: #define     MAX_TYPES   5       /* max number of types above */
     102:
     103: static  int     degrees[ MAX_TYPES ]    = { DEG_0, DEG_1, DEG_2,
     104:                                 DEG_3, DEG_4 };
     105:
     106: static  int     seps[ MAX_TYPES ]   = { SEP_0, SEP_1, SEP_2,
     107:                                 SEP_3, SEP_4 };
     108:
     109:
     110:
     111: /*
     112:  * Initially, everything is set up as if from :
     113:  *		initstate( 1, &randtbl, 128 );
     114:  * Note that this initialization takes advantage of the fact that srandom()
     115:  * advances the front and rear pointers 10*rand_deg times, and hence the
     116:  * rear pointer which starts at 0 will also end up at zero; thus the zeroeth
     117:  * element of the state information, which contains info about the current
     118:  * position of the rear pointer is just
     119:  *	MAX_TYPES*(rptr - state) + TYPE_3 == TYPE_3.
     120:  */
     121:
     122: static  long        randtbl[ DEG_3 + 1 ]    = { TYPE_3,
     123:                 0x9a319039, 0x32d9c024, 0x9b663182, 0x5da1f342,
     124:                 0xde3b81e0, 0xdf0a6fb5, 0xf103bc02, 0x48f340fb,
     125:                 0x7449e56b, 0xbeb1dbb0, 0xab5c5918, 0x946554fd,
     126:                 0x8c2e680f, 0xeb3d799f, 0xb11ee0b7, 0x2d436b86,
     127:                 0xda672e2a, 0x1588ca88, 0xe369735d, 0x904f35f7,
     128:                 0xd7158fd6, 0x6fa6f051, 0x616e6b96, 0xac94efdc,
     129:                 0x36413f93, 0xc622c298, 0xf5a42ab8, 0x8a88d77b,
     130:                     0xf5ad9d0e, 0x8999220b, 0x27fb47b9 };
     131:
     132: /*
     133:  * fptr and rptr are two pointers into the state info, a front and a rear
     134:  * pointer.  These two pointers are always rand_sep places aparts, as they cycle
     135:  * cyclically through the state information.  (Yes, this does mean we could get
     136:  * away with just one pointer, but the code for random() is more efficient this
     137:  * way).  The pointers are left positioned as they would be from the call
     138:  *			initstate( 1, randtbl, 128 )
     139:  * (The position of the rear pointer, rptr, is really 0 (as explained above
     140:  * in the initialization of randtbl) because the state table pointer is set
     141:  * to point to randtbl[1] (as explained below).
     142:  */
     143:
     144: static  long        *fptr           = &randtbl[ SEP_3 + 1 ];
     145: static  long        *rptr           = &randtbl[ 1 ];
     146:
     147:
     148:
     149: /*
     150:  * The following things are the pointer to the state information table,
     151:  * the type of the current generator, the degree of the current polynomial
     152:  * being used, and the separation between the two pointers.
     153:  * Note that for efficiency of random(), we remember the first location of
     154:  * the state information, not the zeroeth.  Hence it is valid to access
     155:  * state[-1], which is used to store the type of the R.N.G.
     156:  * Also, we remember the last location, since this is more efficient than
     157:  * indexing every time to find the address of the last element to see if
     158:  * the front and rear pointers have wrapped.
     159:  */
     160:
     161: static  long        *state          = &randtbl[ 1 ];
     162:
     163: static  int     rand_type       = TYPE_3;
     164: static  int     rand_deg        = DEG_3;
     165: static  int     rand_sep        = SEP_3;
     166:
     167: static  long        *end_ptr        = &randtbl[ DEG_3 + 1 ];
     168:
     169:
     170:
     171: /*
     172:  * srandom:
     173:  * Initialize the random number generator based on the given seed.  If the
     174:  * type is the trivial no-state-information type, just remember the seed.
     175:  * Otherwise, initializes state[] based on the given "seed" via a linear
     176:  * congruential generator.  Then, the pointers are set to known locations
     177:  * that are exactly rand_sep places apart.  Lastly, it cycles the state
     178:  * information a given number of times to get rid of any initial dependencies
     179:  * introduced by the L.C.R.N.G.
     180:  * Note that the initialization of randtbl[] for default usage relies on
     181:  * values produced by this routine.
     182:  */
     183:
     184: srandom( x )
     185:
     186:     unsigned        x;
     187: {
     188:         register  int       i, j;
     189:
     190:     if(  rand_type  ==  TYPE_0  )  {
     191:         state[ 0 ] = x;
     192:     }
     193:     else  {
     194:         j = 1;
     195:         state[ 0 ] = x;
     196:         for( i = 1; i < rand_deg; i++ )  {
     197:         state[i] = 1103515245*state[i - 1] + 12345;
     198:         }
     199:         fptr = &state[ rand_sep ];
     200:         rptr = &state[ 0 ];
     201:         for( i = 0; i < 10*rand_deg; i++ )  random();
     202:     }
     203: }
     204:
     205:
     206:
     207: /*
     208:  * initstate:
     209:  * Initialize the state information in the given array of n bytes for
     210:  * future random number generation.  Based on the number of bytes we
     211:  * are given, and the break values for the different R.N.G.'s, we choose
     212:  * the best (largest) one we can and set things up for it.  srandom() is
     213:  * then called to initialize the state information.
     214:  * Note that on return from srandom(), we set state[-1] to be the type
     215:  * multiplexed with the current value of the rear pointer; this is so
     216:  * successive calls to initstate() won't lose this information and will
     217:  * be able to restart with setstate().
     218:  * Note: the first thing we do is save the current state, if any, just like
     219:  * setstate() so that it doesn't matter when initstate is called.
     220:  * Returns a pointer to the old state.
     221:  */
     222:
     223: char  *
     224: initstate( seed, arg_state, n )
     225:
     226:     unsigned        seed;           /* seed for R. N. G. */
     227:     char        *arg_state;     /* pointer to state array */
     228:     int         n;          /* # bytes of state info */
     229: {
     230:     register  char      *ostate     = (char *)( &state[ -1 ] );
     231:
     232:     if(  rand_type  ==  TYPE_0  )  state[ -1 ] = rand_type;
     233:     else  state[ -1 ] = MAX_TYPES*(rptr - state) + rand_type;
     234:     if(  n  <  BREAK_1  )  {
     235:         if(  n  <  BREAK_0  )  {
     236:         fprintf( stderr, "initstate: not enough state (%d bytes) with which to do jack; ignored.\n" );
     237:         return;
     238:         }
     239:         rand_type = TYPE_0;
     240:         rand_deg = DEG_0;
     241:         rand_sep = SEP_0;
     242:     }
     243:     else  {
     244:         if(  n  <  BREAK_2  )  {
     245:         rand_type = TYPE_1;
     246:         rand_deg = DEG_1;
     247:         rand_sep = SEP_1;
     248:         }
     249:         else  {
     250:         if(  n  <  BREAK_3  )  {
     251:             rand_type = TYPE_2;
     252:             rand_deg = DEG_2;
     253:             rand_sep = SEP_2;
     254:         }
     255:         else  {
     256:             if(  n  <  BREAK_4  )  {
     257:             rand_type = TYPE_3;
     258:             rand_deg = DEG_3;
     259:             rand_sep = SEP_3;
     260:             }
     261:             else  {
     262:             rand_type = TYPE_4;
     263:             rand_deg = DEG_4;
     264:             rand_sep = SEP_4;
     265:             }
     266:         }
     267:         }
     268:     }
     269:     state = &(  ( (long *)arg_state )[1]  );    /* first location */
     270:     end_ptr = &state[ rand_deg ];   /* must set end_ptr before srandom */
     271:     srandom( seed );
     272:     if(  rand_type  ==  TYPE_0  )  state[ -1 ] = rand_type;
     273:     else  state[ -1 ] = MAX_TYPES*(rptr - state) + rand_type;
     274:     return( ostate );
     275: }
     276:
     277:
     278:
     279: /*
     280:  * setstate:
     281:  * Restore the state from the given state array.
     282:  * Note: it is important that we also remember the locations of the pointers
     283:  * in the current state information, and restore the locations of the pointers
     284:  * from the old state information.  This is done by multiplexing the pointer
     285:  * location into the zeroeth word of the state information.
     286:  * Note that due to the order in which things are done, it is OK to call
     287:  * setstate() with the same state as the current state.
     288:  * Returns a pointer to the old state information.
     289:  */
     290:
     291: char  *
     292: setstate( arg_state )
     293:
     294:     char        *arg_state;
     295: {
     296:     register  long      *new_state  = (long *)arg_state;
     297:     register  int       type        = new_state[0]%MAX_TYPES;
     298:     register  int       rear        = new_state[0]/MAX_TYPES;
     299:     char            *ostate     = (char *)( &state[ -1 ] );
     300:
     301:     if(  rand_type  ==  TYPE_0  )  state[ -1 ] = rand_type;
     302:     else  state[ -1 ] = MAX_TYPES*(rptr - state) + rand_type;
     303:     switch(  type  )  {
     304:         case  TYPE_0:
     305:         case  TYPE_1:
     306:         case  TYPE_2:
     307:         case  TYPE_3:
     308:         case  TYPE_4:
     309:         rand_type = type;
     310:         rand_deg = degrees[ type ];
     311:         rand_sep = seps[ type ];
     312:         break;
     313:
     314:         default:
     315:         fprintf( stderr, "setstate: state info has been munged; not changed.\n" );
     316:     }
     317:     state = &new_state[ 1 ];
     318:     if(  rand_type  !=  TYPE_0  )  {
     319:         rptr = &state[ rear ];
     320:         fptr = &state[ (rear + rand_sep)%rand_deg ];
     321:     }
     322:     end_ptr = &state[ rand_deg ];       /* set end_ptr too */
     323:     return( ostate );
     324: }
     325:
     326:
     327:
     328: /*
     329:  * random:
     330:  * If we are using the trivial TYPE_0 R.N.G., just do the old linear
     331:  * congruential bit.  Otherwise, we do our fancy trinomial stuff, which is the
     332:  * same in all ther other cases due to all the global variables that have been
     333:  * set up.  The basic operation is to add the number at the rear pointer into
     334:  * the one at the front pointer.  Then both pointers are advanced to the next
     335:  * location cyclically in the table.  The value returned is the sum generated,
     336:  * reduced to 31 bits by throwing away the "least random" low bit.
     337:  * Note: the code takes advantage of the fact that both the front and
     338:  * rear pointers can't wrap on the same call by not testing the rear
     339:  * pointer if the front one has wrapped.
     340:  * Returns a 31-bit random number.
     341:  */
     342:
     343: long
     344: random()
     345: {
     346:     long        i;
     347:
     348:     if(  rand_type  ==  TYPE_0  )  {
     349:         i = state[0] = ( state[0]*1103515245 + 12345 )&0x7fffffff;
     350:     }
     351:     else  {
     352:         *fptr += *rptr;
     353:         i = (*fptr >> 1)&0x7fffffff;    /* chucking least random bit */
     354:         if(  ++fptr  >=  end_ptr  )  {
     355:         fptr = state;
     356:         ++rptr;
     357:         }
     358:         else  {
     359:         if(  ++rptr  >=  end_ptr  )  rptr = state;
     360:         }
     361:     }
     362:     return( i );
     363: }
     364:
     365: #endif	NO_RANDOM

#### Defined functions

initstate defined in line 223; never used
random defined in line 343; used 2 times

- in line 7, 201

rnd defined in line 5; used 3 times

- in /usr/src/games/fortune/fortune.c line 187, 219
- in /usr/src/games/fortune/strfile.c line 388

setstate defined in line 291; never used
srandom defined in line 184; used 2 times

- in line 12, 271

srnd defined in line 10; used 2 times

- in /usr/src/games/fortune/fortune.c line 185
- in /usr/src/games/fortune/strfile.c line 361

#### Defined variables

degrees defined in line 103; used 1 times

- in line 310

end_ptr defined in line 167; used 4 times

- in line 270, 322, 354-359(2)

fptr defined in line 144; used 6 times

- in line 199, 320, 352-355(4)

rand_deg defined in line 164; used 11 times

- in line 196-201(2), 240, 246, 252, 258-263(2), 270, 310, 320-322(2)

rand_sep defined in line 165; used 8 times

- in line 199, 241, 247, 253, 259-264(2), 311, 320

rand_type defined in line 163; used 18 times

- in line 190, 232-233(3), 239, 245, 251, 257-262(2), 272-273(3), 301-302(3), 309, 318, 348

randtbl defined in line 122; used 4 times

- in line 144-145(2), 161, 167

rptr defined in line 145; used 9 times

- in line 200, 233, 273, 302, 319, 352-359(4)

sccsid defined in line 18; never used
seps defined in line 106; used 1 times

- in line 311

state defined in line 161; used 27 times

- in line 191-200(6), 230-233(4), 269-273(5), 299-302(4), 317-322(4), 349(2), 355-359(2)

#### Defined macros

BREAK_0 defined in line 71; used 1 times

- in line 235

BREAK_1 defined in line 76; used 1 times

- in line 234

BREAK_2 defined in line 81; used 1 times

- in line 244

BREAK_3 defined in line 86; used 1 times

- in line 250

BREAK_4 defined in line 91; used 1 times

- in line 256

DEG_0 defined in line 72; used 2 times

- in line 103, 240

DEG_1 defined in line 77; used 2 times

- in line 103, 246

DEG_2 defined in line 82; used 2 times

- in line 103, 252

DEG_3 defined in line 87; used 5 times

- in line 104, 122, 164-167(2), 258

DEG_4 defined in line 92; used 2 times

- in line 104, 263

MAX_TYPES defined in line 101; used 7 times

- in line 103-106(2), 233, 273, 297-302(3)

SEP_0 defined in line 73; used 2 times

- in line 106, 241

SEP_1 defined in line 78; used 2 times

- in line 106, 247

SEP_2 defined in line 83; used 2 times

- in line 106, 253

SEP_3 defined in line 88; used 4 times

- in line 107, 144, 165, 259

SEP_4 defined in line 93; used 2 times

- in line 107, 264

TYPE_0 defined in line 70; used 7 times

- in line 190, 232, 239, 272, 301, 318, 348

TYPE_1 defined in line 75; used 1 times

- in line 245

TYPE_2 defined in line 80; used 1 times

- in line 251

TYPE_3 defined in line 85; used 3 times

- in line 122, 163, 257

TYPE_4 defined in line 90; used 1 times

- in line 262

Last modified: 1986-01-10 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1732 |