1 /*
2 * random.c - random number generator for producing mathlib test cases
3 *
4 * Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 * See https://llvm.org/LICENSE.txt for license information.
6 * SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 */
8
9 #include "types.h"
10 #include "random.h"
11
12 static uint32 seedbuf[55];
13 static int seedptr;
14
seed_random(uint32 seed)15 void seed_random(uint32 seed) {
16 int i;
17
18 seedptr = 0;
19 for (i = 0; i < 55; i++) {
20 seed = seed % 44488 * 48271 - seed / 44488 * 3399;
21 seedbuf[i] = seed - 1;
22 }
23 }
24
base_random(void)25 uint32 base_random(void) {
26 seedptr %= 55;
27 seedbuf[seedptr] += seedbuf[(seedptr+31)%55];
28 return seedbuf[seedptr++];
29 }
30
random32(void)31 uint32 random32(void) {
32 uint32 a, b, b1, b2;
33 a = base_random();
34 b = base_random();
35 for (b1 = 0x80000000, b2 = 1; b1 > b2; b1 >>= 1, b2 <<= 1) {
36 uint32 b3 = b1 | b2;
37 if ((b & b3) != 0 && (b & b3) != b3)
38 b ^= b3;
39 }
40 return a ^ b;
41 }
42
43 /*
44 * random_upto: generate a uniformly randomised number in the range
45 * 0,...,limit-1. (Precondition: limit > 0.)
46 *
47 * random_upto_biased: generate a number in the same range, but with
48 * the probability skewed towards the high end by means of taking the
49 * maximum of 8*bias+1 samples from the uniform distribution on the
50 * same range. (I don't know why bias is given in that curious way -
51 * historical reasons, I expect.)
52 *
53 * For speed, I separate the implementation of random_upto into the
54 * two stages of (a) generate a bitmask which reduces a 32-bit random
55 * number to within a factor of two of the right range, (b) repeatedly
56 * generate numbers in that range until one is small enough. Splitting
57 * it up like that means that random_upto_biased can do (a) only once
58 * even when it does (b) lots of times.
59 */
60
random_upto_makemask(uint32 limit)61 static uint32 random_upto_makemask(uint32 limit) {
62 uint32 mask = 0xFFFFFFFF;
63 int i;
64 for (i = 16; i > 0; i >>= 1)
65 if ((limit & (mask >> i)) == limit)
66 mask >>= i;
67 return mask;
68 }
69
random_upto_internal(uint32 limit,uint32 mask)70 static uint32 random_upto_internal(uint32 limit, uint32 mask) {
71 uint32 ret;
72 do {
73 ret = random32() & mask;
74 } while (ret > limit);
75 return ret;
76 }
77
random_upto(uint32 limit)78 uint32 random_upto(uint32 limit) {
79 uint32 mask = random_upto_makemask(limit);
80 return random_upto_internal(limit, mask);
81 }
82
random_upto_biased(uint32 limit,int bias)83 uint32 random_upto_biased(uint32 limit, int bias) {
84 uint32 mask = random_upto_makemask(limit);
85
86 uint32 ret = random_upto_internal(limit, mask);
87 while (bias--) {
88 uint32 tmp;
89 tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
90 tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
91 tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
92 tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
93 tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
94 tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
95 tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
96 tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
97 }
98
99 return ret;
100 }
101