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