Changeset 743


Ignore:
Timestamp:
Sep 29, 2003, 1:39:48 AM (22 years ago)
Author:
bird
Message:

Ported random from current FreeBSD CVS.

Location:
trunk/src/emx
Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/emx/bsd/libc/random.c

    • Property cvs2svn:cvs-rev changed from 1.1 to 1.2
    r742 r743  
    11/*
    2  * Copyright (c) 1983 Regents of the University of California.
    3  * All rights reserved.
     2 * Copyright (c) 1983, 1993
     3 *      The Regents of the University of California. All rights reserved.
    44 *
    55 * Redistribution and use in source and binary forms, with or without
     
    3333
    3434#if defined(LIBC_SCCS) && !defined(lint)
    35 static char sccsid[] = "@(#)random.c    5.9 (Berkeley) 2/23/91";
     35static char sccsid[] = "@(#)random.c    8.2 (Berkeley) 5/19/95";
    3636#endif /* LIBC_SCCS and not lint */
    37 
     37#include <sys/cdefs.h>
     38__FBSDID("$FreeBSD: src/lib/libc/stdlib/random.c,v 1.23 2003/08/10 17:49:55 ache Exp $");
     39
     40#ifndef __EMX__
     41#include "namespace.h"
     42#endif
     43#include <sys/time.h>          /* for srandomdev() */
     44#include <fcntl.h>             /* for srandomdev() */
    3845#include <stdio.h>
    3946#include <stdlib.h>
    40 #if defined (__EMX__)
    41 #include "emxbsd.h"
     47#include <unistd.h>            /* for srandomdev() */
     48#ifndef __EMX__
     49#include "un-namespace.h"
    4250#endif
    4351
     
    6573 * the zeroeth word of state information also has some other information
    6674 * stored in it -- see setstate() for details).
    67  * 
     75 *
    6876 * The random number generation technique is a linear feedback shift register
    6977 * approach, employing trinomials (since there are fewer terms to sum up that
     
    7785 * the amount of state information has a vast influence on the period of the
    7886 * generator.  Note: the deg*(2**deg - 1) is an approximation only good for
    79  * large deg, when the period of the shift register is the dominant factor.
     87 * large deg, when the period of the shift is the dominant factor.
    8088 * With deg equal to seven, the period is actually much longer than the
    8189 * 7*(2**7 - 1) predicted by this formula.
     90 *
     91 * Modified 28 December 1994 by Jacob S. Rosenberg.
     92 * The following changes have been made:
     93 * All references to the type u_int have been changed to unsigned long.
     94 * All references to type int have been changed to type long.  Other
     95 * cleanups have been made as well.  A warning for both initstate and
     96 * setstate has been inserted to the effect that on Sparc platforms
     97 * the 'arg_state' variable must be forced to begin on word boundaries.
     98 * This can be easily done by casting a long integer array to char *.
     99 * The overall logic has been left STRICTLY alone.  This software was
     100 * tested on both a VAX and Sun SpacsStation with exactly the same
     101 * results.  The new version and the original give IDENTICAL results.
     102 * The new version is somewhat faster than the original.  As the
     103 * documentation says:  "By default, the package runs with 128 bytes of
     104 * state information and generates far better random numbers than a linear
     105 * congruential generator.  If the amount of state information is less than
     106 * 32 bytes, a simple linear congruential R.N.G. is used."  For a buffer of
     107 * 128 bytes, this new version runs about 19 percent faster and for a 16
     108 * byte buffer it is about 5 percent faster.
    82109 */
    83110
     
    120147#define MAX_TYPES       5               /* max number of types above */
    121148
    122 static int degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 };
    123 static int seps [MAX_TYPES] =   { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 };
     149#ifdef  USE_WEAK_SEEDING
     150#define NSHUFF 0
     151#else   /* !USE_WEAK_SEEDING */
     152#define NSHUFF 50       /* to drop some "seed -> 1st value" linearity */
     153#endif  /* !USE_WEAK_SEEDING */
     154
     155static long degrees[MAX_TYPES] =        { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 };
     156static long seps [MAX_TYPES] =  { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 };
    124157
    125158/*
    126159 * Initially, everything is set up as if from:
    127160 *
    128  *      initstate(1, &randtbl, 128);
     161 *      initstate(1, randtbl, 128);
    129162 *
    130163 * Note that this initialization takes advantage of the fact that srandom()
     
    139172static long randtbl[DEG_3 + 1] = {
    140173        TYPE_3,
     174#ifdef  USE_WEAK_SEEDING
     175/* Historic implementation compatibility */
     176/* The random sequences do not vary much with the seed */
    141177        0x9a319039, 0x32d9c024, 0x9b663182, 0x5da1f342, 0xde3b81e0, 0xdf0a6fb5,
    142178        0xf103bc02, 0x48f340fb, 0x7449e56b, 0xbeb1dbb0, 0xab5c5918, 0x946554fd,
     
    145181        0x36413f93, 0xc622c298, 0xf5a42ab8, 0x8a88d77b, 0xf5ad9d0e, 0x8999220b,
    146182        0x27fb47b9,
     183#else   /* !USE_WEAK_SEEDING */
     184        0x991539b1, 0x16a5bce3, 0x6774a4cd, 0x3e01511e, 0x4e508aaa, 0x61048c05,
     185        0xf5500617, 0x846b7115, 0x6a19892c, 0x896a97af, 0xdb48f936, 0x14898454,
     186        0x37ffd106, 0xb58bff9c, 0x59e17104, 0xcf918a49, 0x09378c83, 0x52c7a471,
     187        0x8d293ea9, 0x1f4fc301, 0xc3db71be, 0x39b44e1c, 0xf8a44ef9, 0x4c8b80b1,
     188        0x19edc328, 0x87bf4bdd, 0xc9b240e5, 0xe9ee4b1b, 0x4382aee7, 0x535b6b41,
     189        0xf3bec5da
     190#endif  /* !USE_WEAK_SEEDING */
    147191};
    148192
     
    175219 */
    176220static long *state = &randtbl[1];
    177 static int rand_type = TYPE_3;
    178 static int rand_deg = DEG_3;
    179 static int rand_sep = SEP_3;
     221static long rand_type = TYPE_3;
     222static long rand_deg = DEG_3;
     223static long rand_sep = SEP_3;
    180224static long *end_ptr = &randtbl[DEG_3 + 1];
     225
     226static inline long good_rand(long);
     227
     228static inline long good_rand (x)
     229        long x;
     230{
     231#ifdef  USE_WEAK_SEEDING
     232/*
     233 * Historic implementation compatibility.
     234 * The random sequences do not vary much with the seed,
     235 * even with overflowing.
     236 */
     237        return (1103515245 * x + 12345);
     238#else   /* !USE_WEAK_SEEDING */
     239/*
     240 * Compute x = (7^5 * x) mod (2^31 - 1)
     241 * wihout overflowing 31 bits:
     242 *      (2^31 - 1) = 127773 * (7^5) + 2836
     243 * From "Random number generators: good ones are hard to find",
     244 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
     245 * October 1988, p. 1195.
     246 */
     247        long hi, lo;
     248
     249        /* Can't be initialized with 0, so use another value. */
     250        if (x == 0)
     251                x = 123459876;
     252        hi = x / 127773;
     253        lo = x % 127773;
     254        x = 16807 * lo - 2836 * hi;
     255        if (x < 0)
     256                x += 0x7fffffff;
     257        return (x);
     258#endif  /* !USE_WEAK_SEEDING */
     259}
    181260
    182261/*
     
    194273void
    195274srandom(x)
    196         u_int x;
     275        unsigned long x;
    197276{
    198         register int i, j;
    199 
     277        long i, lim;
     278
     279        state[0] = x;
    200280        if (rand_type == TYPE_0)
    201                 state[0] = x;
     281                lim = NSHUFF;
    202282        else {
    203                 j = 1;
    204                 state[0] = x;
    205283                for (i = 1; i < rand_deg; i++)
    206                         state[i] = 1103515245 * state[i - 1] + 12345;
     284                        state[i] = good_rand(state[i - 1]);
    207285                fptr = &state[rand_sep];
    208286                rptr = &state[0];
    209                 for (i = 0; i < 10 * rand_deg; i++)
    210                         (void)random();
     287                lim = 10 * rand_deg;
     288        }
     289        for (i = 0; i < lim; i++)
     290                (void)random();
     291}
     292
     293/*
     294 * srandomdev:
     295 *
     296 * Many programs choose the seed value in a totally predictable manner.
     297 * This often causes problems.  We seed the generator using the much more
     298 * secure random(4) interface.  Note that this particular seeding
     299 * procedure can generate states which are impossible to reproduce by
     300 * calling srandom() with any value, since the succeeding terms in the
     301 * state buffer are no longer derived from the LC algorithm applied to
     302 * a fixed seed.
     303 */
     304void
     305srandomdev()
     306{
     307        int fd, done;
     308        size_t len;
     309
     310        if (rand_type == TYPE_0)
     311                len = sizeof state[0];
     312        else
     313                len = rand_deg * sizeof state[0];
     314
     315        done = 0;
     316        fd = _open("/dev/random", O_RDONLY, 0);
     317        if (fd >= 0) {
     318                if (_read(fd, (void *) state, len) == (ssize_t) len)
     319                        done = 1;
     320                _close(fd);
     321        }
     322
     323        if (!done) {
     324                struct timeval tv;
     325                unsigned long junk;
     326
     327                gettimeofday(&tv, NULL);
     328                srandom((getpid() << 16) ^ tv.tv_sec ^ tv.tv_usec ^ junk);
     329                return;
     330        }
     331
     332        if (rand_type != TYPE_0) {
     333                fptr = &state[rand_sep];
     334                rptr = &state[0];
    211335        }
    212336}
     
    220344 * one we can and set things up for it.  srandom() is then called to
    221345 * initialize the state information.
    222  * 
     346 *
    223347 * Note that on return from srandom(), we set state[-1] to be the type
    224348 * multiplexed with the current value of the rear pointer; this is so
    225349 * successive calls to initstate() won't lose this information and will be
    226350 * able to restart with setstate().
    227  * 
     351 *
    228352 * Note: the first thing we do is save the current state, if any, just like
    229353 * setstate() so that it doesn't matter when initstate is called.
    230354 *
    231355 * Returns a pointer to the old state.
     356 *
     357 * Note: The Sparc platform requires that arg_state begin on a long
     358 * word boundary; otherwise a bus error will occur. Even so, lint will
     359 * complain about mis-alignment, but you should disregard these messages.
    232360 */
    233361char *
    234362initstate(seed, arg_state, n)
    235         u_int seed;                     /* seed for R.N.G. */
     363        unsigned long seed;             /* seed for R.N.G. */
    236364        char *arg_state;                /* pointer to state array */
    237         int n;                          /* # bytes of state info */
     365        long n;                         /* # bytes of state info */
    238366{
    239         register char *ostate = (char *)(&state[-1]);
     367        char *ostate = (char *)(&state[-1]);
     368        long *long_arg_state = (long *) arg_state;
    240369
    241370        if (rand_type == TYPE_0)
     
    245374        if (n < BREAK_0) {
    246375                (void)fprintf(stderr,
    247                     "random: not enough state (%d bytes); ignored.\n", n);
     376                    "random: not enough state (%ld bytes); ignored.\n", n);
    248377                return(0);
    249378        }
     
    269398                rand_sep = SEP_4;
    270399        }
    271         state = &(((long *)arg_state)[1]);      /* first location */
     400        state = (long *) (long_arg_state + 1); /* first location */
    272401        end_ptr = &state[rand_deg];     /* must set end_ptr before srandom */
    273402        srandom(seed);
    274403        if (rand_type == TYPE_0)
    275                 state[-1] = rand_type;
     404                long_arg_state[0] = rand_type;
    276405        else
    277                 state[-1] = MAX_TYPES*(rptr - state) + rand_type;
     406                long_arg_state[0] = MAX_TYPES * (rptr - state) + rand_type;
    278407        return(ostate);
    279408}
     
    293422 *
    294423 * Returns a pointer to the old state information.
     424 *
     425 * Note: The Sparc platform requires that arg_state begin on a long
     426 * word boundary; otherwise a bus error will occur. Even so, lint will
     427 * complain about mis-alignment, but you should disregard these messages.
    295428 */
    296429char *
    297430setstate(arg_state)
    298         char *arg_state;
     431        char *arg_state;                /* pointer to state array */
    299432{
    300         register long *new_state = (long *)arg_state;
    301         register int type = new_state[0] % MAX_TYPES;
    302         register int rear = new_state[0] / MAX_TYPES;
     433        long *new_state = (long *) arg_state;
     434        long type = new_state[0] % MAX_TYPES;
     435        long rear = new_state[0] / MAX_TYPES;
    303436        char *ostate = (char *)(&state[-1]);
    304437
     
    321454                    "random: state info corrupted; not changed.\n");
    322455        }
    323         state = &new_state[1];
     456        state = (long *) (new_state + 1);
    324457        if (rand_type != TYPE_0) {
    325458                rptr = &state[rear];
     
    351484{
    352485        long i;
    353 
    354         if (rand_type == TYPE_0)
    355                 i = state[0] = (state[0] * 1103515245 + 12345) & 0x7fffffff;
    356         else {
    357                 *fptr += *rptr;
    358                 i = (*fptr >> 1) & 0x7fffffff;  /* chucking least random bit */
    359                 if (++fptr >= end_ptr) {
    360                         fptr = state;
    361                         ++rptr;
    362                 } else if (++rptr >= end_ptr)
    363                         rptr = state;
     486        long *f, *r;
     487
     488        if (rand_type == TYPE_0) {
     489                i = state[0];
     490                state[0] = i = (good_rand(i)) & 0x7fffffff;
     491        } else {
     492                /*
     493                 * Use local variables rather than static variables for speed.
     494                 */
     495                f = fptr; r = rptr;
     496                *f += *r;
     497                i = (*f >> 1) & 0x7fffffff;     /* chucking least random bit */
     498                if (++f >= end_ptr) {
     499                        f = state;
     500                        ++r;
     501                }
     502                else if (++r >= end_ptr) {
     503                        r = state;
     504                }
     505
     506                fptr = f; rptr = r;
    364507        }
    365508        return(i);
  • trunk/src/emx/include/stdlib.h

    • Property cvs2svn:cvs-rev changed from 1.9 to 1.10
    r742 r743  
    149149extern char **environ;
    150150
    151 extern __const__ char * __const__ sys_errlist[]; 
     151extern __const__ char * __const__ sys_errlist[];
    152152extern __const__ int sys_nerr;
    153153
     
    174174long ulimit (int, ...);
    175175
     176/* BSD - start */
    176177int heapsort (void *, size_t, size_t,
    177178    int (*)(__const__ void *, __const__ void *));       /* BSD */
    178 char *initstate (unsigned, char *, int);                /* BSD */
    179 long random (void);                                     /* BSD */
    180 char *setstate (char *);                                /* BSD */
    181 void srandom (unsigned);                                /* BSD */
     179char    *initstate(unsigned long /* XSI requires u_int */, char *, long);
     180char    *setstate(/* const */ char *);
     181long     random(void);
     182void     srandom(unsigned long);
     183void     srandomdev(void);
     184/* BSD - end */
    182185
    183186char *itoa (int, char *, int);
     
    197200
    198201extern char **_environ;
    199 extern __const__ char * __const__ _sys_errlist[]; 
     202extern __const__ char * __const__ _sys_errlist[];
    200203extern __const__ int _sys_nerr;
    201204
Note: See TracChangeset for help on using the changeset viewer.