Return to random.c CVS log

Up to [Apple XNU] / GNUtools / libg++ / libiberty

Annotation of GNUtools/libg++/libiberty/random.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.