101 lines · c
1/*2 * random.c - random number generator for producing mathlib test cases3 *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-exception7 */8 9#include "types.h"10#include "random.h"11 12static uint32 seedbuf[55];13static int seedptr;14 15void 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 25uint32 base_random(void) {26 seedptr %= 55;27 seedbuf[seedptr] += seedbuf[(seedptr+31)%55];28 return seedbuf[seedptr++];29}30 31uint32 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 range45 * 0,...,limit-1. (Precondition: limit > 0.)46 *47 * random_upto_biased: generate a number in the same range, but with48 * the probability skewed towards the high end by means of taking the49 * maximum of 8*bias+1 samples from the uniform distribution on the50 * 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 the54 * two stages of (a) generate a bitmask which reduces a 32-bit random55 * number to within a factor of two of the right range, (b) repeatedly56 * generate numbers in that range until one is small enough. Splitting57 * it up like that means that random_upto_biased can do (a) only once58 * even when it does (b) lots of times.59 */60 61static 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 70static 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 78uint32 random_upto(uint32 limit) {79 uint32 mask = random_upto_makemask(limit);80 return random_upto_internal(limit, mask);81}82 83uint32 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