← Back to branch summary

~vcs-imports/gawk/master

« back to all changes in this revision

Viewing changes to random.c

  • Committer: Arnold D. Robbins
  • Date: 2010-07-16 11:47:02 UTC
  • Revision ID: git-v1:315bd501ca696bc3e3c938b4604d8dac7a6f512f
Tags: gawk-3.1.5
Move to gawk 3.1.5.

Show diffs side-by-side

added added

removed removed

Lines of Context:
random.c
29
29
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30
30
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31
31
 * SUCH DAMAGE.
32
 
 *
33
 
 * $FreeBSD: src/lib/libc/stdlib/random.c,v 1.13 2000/01/27 23:06:49 jasone Exp $
34
 
 *
35
32
 */
36
33
 
37
34
#if defined(LIBC_SCCS) && !defined(lint)
38
35
static const char sccsid[] = "@(#)random.c      8.2 (Berkeley) 5/19/95";
39
36
#endif /* LIBC_SCCS and not lint */
40
37
 
 
38
#ifdef HAVE_CONFIG_H            /* gawk addition */
 
39
#include <config.h>
 
40
#endif
 
41
 
 
42
#ifdef HAVE_FCNTL_H
 
43
#include <fcntl.h>
 
44
#endif
 
45
#include <stdio.h>
 
46
#include <stdlib.h>
 
47
#ifdef HAVE_UNISTD_H
 
48
#include <unistd.h>
 
49
#endif
 
50
 
41
51
#include "random.h"             /* gawk addition */
42
52
 
43
 
/*
44
 
 * srandomdev() isn't used by gawk, and it causes numerous
45
 
 * compile headaches, so just blow it away.
46
 
 */
 
53
#ifdef HAVE_SYS_TIME_H          /* gawk addition */
 
54
#include <sys/time.h>
 
55
#endif
 
56
 
47
57
#if 0
48
 
#if !defined (_MSC_VER) && !defined (__MINGW32__) && !defined (VMS)
 
58
#include <sys/cdefs.h>
 
59
__FBSDID("$FreeBSD: /repoman/r/ncvs/src/lib/libc/stdlib/random.c,v 1.24 2004/01/20 03:02:18 das Exp $");
 
60
 
 
61
#include "namespace.h"
49
62
#include <sys/time.h>          /* for srandomdev() */
50
 
#else
51
 
#include <time.h>              /* for clock() */
52
 
#define ssize_t size_t
53
 
#endif /* !defined (_MSC_VER) && !defined (__MINGW32__) && !defined (VMS) */
54
 
#endif
55
 
 
 
63
#include <fcntl.h>             /* for srandomdev() */
 
64
#include <stdint.h>
56
65
#include <stdio.h>
57
 
 
58
 
/* For gawk, don't this, use the decl of random() in random.h */
59
 
#if 0
60
66
#include <stdlib.h>
61
 
#endif
62
 
 
63
 
/* same thing here: */
64
 
#if 0
65
 
#ifdef HAVE_UNISTD_H
66
67
#include <unistd.h>            /* for srandomdev() */
67
 
#endif
68
 
#ifdef HAVE_FCNTL_H
69
 
#include <fcntl.h>             /* for srandomdev() */
70
 
#endif
 
68
#include "un-namespace.h"
71
69
#endif
72
70
 
73
71
/*
86
84
 * congruential generator.  If the amount of state information is less than
87
85
 * 32 bytes, a simple linear congruential R.N.G. is used.
88
86
 *
89
 
 * Internally, the state information is treated as an array of longs; the
 
87
 * Internally, the state information is treated as an array of uint32_t's; the
90
88
 * zeroeth element of the array is the type of R.N.G. being used (small
91
89
 * integer); the remainder of the array is the state information for the
92
 
 * R.N.G.  Thus, 32 bytes of state information will give 7 longs worth of
 
90
 * R.N.G.  Thus, 32 bytes of state information will give 7 ints worth of
93
91
 * state information, which will allow a degree seven polynomial.  (Note:
94
92
 * the zeroeth word of state information also has some other information
95
93
 * stored in it -- see setstate() for details).
105
103
 * period of the generator is approximately deg*(2**deg - 1); thus doubling
106
104
 * the amount of state information has a vast influence on the period of the
107
105
 * generator.  Note: the deg*(2**deg - 1) is an approximation only good for
108
 
 * large deg, when the period of the shift register is the dominant factor.
 
106
 * large deg, when the period of the shift is the dominant factor.
109
107
 * With deg equal to seven, the period is actually much longer than the
110
108
 * 7*(2**7 - 1) predicted by this formula.
111
109
 *
167
165
 */
168
166
#define MAX_TYPES       5               /* max number of types above */
169
167
 
170
 
static long degrees[MAX_TYPES] =        { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 };
171
 
static long seps [MAX_TYPES] =  { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 };
 
168
#ifdef  USE_WEAK_SEEDING
 
169
#define NSHUFF 0
 
170
#else   /* !USE_WEAK_SEEDING */
 
171
#define NSHUFF 50       /* to drop some "seed -> 1st value" linearity */
 
172
#endif  /* !USE_WEAK_SEEDING */
 
173
 
 
174
static const int degrees[MAX_TYPES] =   { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 };
 
175
static const int seps [MAX_TYPES] =     { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 };
172
176
 
173
177
/*
174
178
 * Initially, everything is set up as if from:
184
188
 *      MAX_TYPES * (rptr - state) + TYPE_3 == TYPE_3.
185
189
 */
186
190
 
187
 
static long randtbl[DEG_3 + 1] = {
 
191
static uint32_t randtbl[DEG_3 + 1] = {
188
192
        TYPE_3,
189
193
#ifdef  USE_WEAK_SEEDING
190
194
/* Historic implementation compatibility */
219
223
 * in the initialization of randtbl) because the state table pointer is set
220
224
 * to point to randtbl[1] (as explained below).
221
225
 */
222
 
static long *fptr = &randtbl[SEP_3 + 1];
223
 
static long *rptr = &randtbl[1];
 
226
static uint32_t *fptr = &randtbl[SEP_3 + 1];
 
227
static uint32_t *rptr = &randtbl[1];
224
228
 
225
229
/*
226
230
 * The following things are the pointer to the state information table, the
232
236
 * this is more efficient than indexing every time to find the address of
233
237
 * the last element to see if the front and rear pointers have wrapped.
234
238
 */
235
 
static long *state = &randtbl[1];
236
 
static long rand_type = TYPE_3;
237
 
static long rand_deg = DEG_3;
238
 
static long rand_sep = SEP_3;
239
 
static long *end_ptr = &randtbl[DEG_3 + 1];
240
 
 
241
 
static long good_rand __P((long));
242
 
 
243
 
static long good_rand (x)
244
 
        register long x;
 
239
static uint32_t *state = &randtbl[1];
 
240
static int rand_type = TYPE_3;
 
241
static int rand_deg = DEG_3;
 
242
static int rand_sep = SEP_3;
 
243
static uint32_t *end_ptr = &randtbl[DEG_3 + 1];
 
244
 
 
245
static inline uint32_t good_rand(int32_t);
 
246
 
 
247
static inline uint32_t good_rand (x)
 
248
        int32_t x;
245
249
{
246
250
#ifdef  USE_WEAK_SEEDING
247
251
/*
259
263
 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
260
264
 * October 1988, p. 1195.
261
265
 */
262
 
        register long hi, lo;
 
266
        int32_t hi, lo;
263
267
 
 
268
        /* Can't be initialized with 0, so use another value. */
 
269
        if (x == 0)
 
270
                x = 123459876;
264
271
        hi = x / 127773;
265
272
        lo = x % 127773;
266
273
        x = 16807 * lo - 2836 * hi;
267
 
        if (x <= 0)
 
274
        if (x < 0)
268
275
                x += 0x7fffffff;
269
276
        return (x);
270
277
#endif  /* !USE_WEAK_SEEDING */
286
293
srandom(x)
287
294
        unsigned long x;
288
295
{
289
 
        register long i;
 
296
        int i, lim;
290
297
 
 
298
        state[0] = (uint32_t)x;
291
299
        if (rand_type == TYPE_0)
292
 
                state[0] = x;
 
300
                lim = NSHUFF;
293
301
        else {
294
 
                state[0] = x;
295
302
                for (i = 1; i < rand_deg; i++)
296
303
                        state[i] = good_rand(state[i - 1]);
297
304
                fptr = &state[rand_sep];
298
305
                rptr = &state[0];
299
 
                for (i = 0; i < 10 * rand_deg; i++)
300
 
                        (void)random();
 
306
                lim = 10 * rand_deg;
301
307
        }
 
308
        for (i = 0; i < lim; i++)
 
309
                (void)random();
302
310
}
303
311
 
 
312
#if 0 /* gawk doesn't use this */
304
313
/*
305
314
 * srandomdev:
306
315
 *
307
316
 * Many programs choose the seed value in a totally predictable manner.
308
317
 * This often causes problems.  We seed the generator using the much more
309
 
 * secure urandom(4) interface.  Note that this particular seeding
 
318
 * secure random(4) interface.  Note that this particular seeding
310
319
 * procedure can generate states which are impossible to reproduce by
311
320
 * calling srandom() with any value, since the succeeding terms in the
312
321
 * state buffer are no longer derived from the LC algorithm applied to
313
322
 * a fixed seed.
314
323
 */
315
 
#if 0
316
324
void
317
325
srandomdev()
318
326
{
325
333
                len = rand_deg * sizeof state[0];
326
334
 
327
335
        done = 0;
328
 
#ifdef O_RDONLY
329
 
        fd = open("/dev/urandom", O_RDONLY, 0);
 
336
        fd = open("/dev/random", O_RDONLY, 0);
330
337
        if (fd >= 0) {
331
338
                if (read(fd, (void *) state, len) == (ssize_t) len)
332
339
                        done = 1;
333
340
                close(fd);
334
341
        }
335
 
#endif  /*O_RDONLY*/
336
342
 
337
343
        if (!done) {
 
344
                struct timeval tv;
338
345
                unsigned long junk;
339
 
#if !defined (_MSC_VER) && !defined (__MINGW32__)
340
 
                struct timeval tv;
341
346
 
342
347
                gettimeofday(&tv, NULL);
343
 
                srandom(getpid() ^ tv.tv_sec ^ tv.tv_usec ^ junk);
344
 
#else
345
 
                clock_t ret_clock_t = clock();
346
 
                /*
347
 
                 * I don't like the idea of reading uninitialized memory
348
 
                 * even to generate a random number, but we do it anyway.
349
 
                 * SD.
350
 
                 */
351
 
                srandom(getpid() ^ ret_clock_t ^ junk);
352
 
#endif
353
 
 
 
348
                srandom((getpid() << 16) ^ tv.tv_sec ^ tv.tv_usec ^ junk);
354
349
                return;
355
350
        }
356
351
 
380
375
 *
381
376
 * Returns a pointer to the old state.
382
377
 *
383
 
 * Note: The Sparc platform requires that arg_state begin on a long
 
378
 * Note: The Sparc platform requires that arg_state begin on an int
384
379
 * word boundary; otherwise a bus error will occur. Even so, lint will
385
380
 * complain about mis-alignment, but you should disregard these messages.
386
381
 */
390
385
        char *arg_state;                /* pointer to state array */
391
386
        long n;                         /* # bytes of state info */
392
387
{
393
 
        register char *ostate = (char *)(&state[-1]);
394
 
        register long *long_arg_state = (long *) arg_state;
 
388
        char *ostate = (char *)(&state[-1]);
 
389
        uint32_t *int_arg_state = (uint32_t *)arg_state;
395
390
 
396
391
        if (rand_type == TYPE_0)
397
392
                state[-1] = rand_type;
423
418
                rand_deg = DEG_4;
424
419
                rand_sep = SEP_4;
425
420
        }
426
 
        state = (long *) (long_arg_state + 1); /* first location */
 
421
        state = int_arg_state + 1; /* first location */
427
422
        end_ptr = &state[rand_deg];     /* must set end_ptr before srandom */
428
423
        srandom(seed);
429
424
        if (rand_type == TYPE_0)
430
 
                long_arg_state[0] = rand_type;
 
425
                int_arg_state[0] = rand_type;
431
426
        else
432
 
                long_arg_state[0] = MAX_TYPES * (rptr - state) + rand_type;
 
427
                int_arg_state[0] = MAX_TYPES * (rptr - state) + rand_type;
433
428
        return(ostate);
434
429
}
435
430
 
448
443
 *
449
444
 * Returns a pointer to the old state information.
450
445
 *
451
 
 * Note: The Sparc platform requires that arg_state begin on a long
 
446
 * Note: The Sparc platform requires that arg_state begin on an int
452
447
 * word boundary; otherwise a bus error will occur. Even so, lint will
453
448
 * complain about mis-alignment, but you should disregard these messages.
454
449
 */
456
451
setstate(arg_state)
457
452
        char *arg_state;                /* pointer to state array */
458
453
{
459
 
        register long *new_state = (long *) arg_state;
460
 
        register long type = new_state[0] % MAX_TYPES;
461
 
        register long rear = new_state[0] / MAX_TYPES;
 
454
        uint32_t *new_state = (uint32_t *)arg_state;
 
455
        uint32_t type = new_state[0] % MAX_TYPES;
 
456
        uint32_t rear = new_state[0] / MAX_TYPES;
462
457
        char *ostate = (char *)(&state[-1]);
463
458
 
464
459
        if (rand_type == TYPE_0)
479
474
                (void)fprintf(stderr,
480
475
                    "random: state info corrupted; not changed.\n");
481
476
        }
482
 
        state = (long *) (new_state + 1);
 
477
        state = new_state + 1;
483
478
        if (rand_type != TYPE_0) {
484
479
                rptr = &state[rear];
485
480
                fptr = &state[(rear + rand_sep) % rand_deg];
508
503
long
509
504
random()
510
505
{
511
 
        register long i;
512
 
        register long *f, *r;
 
506
        uint32_t i;
 
507
        uint32_t *f, *r;
513
508
 
514
509
        if (rand_type == TYPE_0) {
515
510
                i = state[0];
531
526
 
532
527
                fptr = f; rptr = r;
533
528
        }
534
 
        return(i);
 
529
        return((long)i);
535
530
}