libc/AOR_v20.02/math/test/rtest/random.c

   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
  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
  25 uint32 base_random(void) {
  26     seedptr %= 55;
  27     seedbuf[seedptr] += seedbuf[(seedptr+31)%55];
  28     return seedbuf[seedptr++];
  29 }
  30
  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
  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
  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
  78 uint32 random_upto(uint32 limit) {
  79     uint32 mask = random_upto_makemask(limit);
  80     return random_upto_internal(limit, mask);
  81 }
  82
  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 }