random.c

/*
 * random.c - random number generator for producing mathlib test cases
 *
 * Copyright (c) 1998-2019, Arm Limited.
 * SPDX-License-Identifier: MIT OR Apache-2.0 WITH LLVM-exception
 */

#include "types.h"
#include "random.h"

static uint32 seedbuf[55];
static int seedptr;

void seed_random(uint32 seed) {
    int i;

    seedptr = 0;
    for (i = 0; i < 55; i++) {
        seed = seed % 44488 * 48271 - seed / 44488 * 3399;
        seedbuf[i] = seed - 1;
    }
}

uint32 base_random(void) {
    seedptr %= 55;
    seedbuf[seedptr] += seedbuf[(seedptr+31)%55];
    return seedbuf[seedptr++];
}

uint32 random32(void) {
    uint32 a, b, b1, b2;
    a = base_random();
    b = base_random();
    for (b1 = 0x80000000, b2 = 1; b1 > b2; b1 >>= 1, b2 <<= 1) {
        uint32 b3 = b1 | b2;
        if ((b & b3) != 0 && (b & b3) != b3)
            b ^= b3;
    }
    return a ^ b;
}

/*
 * random_upto: generate a uniformly randomised number in the range
 * 0,...,limit-1. (Precondition: limit > 0.)
 *
 * random_upto_biased: generate a number in the same range, but with
 * the probability skewed towards the high end by means of taking the
 * maximum of 8*bias+1 samples from the uniform distribution on the
 * same range. (I don't know why bias is given in that curious way -
 * historical reasons, I expect.)
 *
 * For speed, I separate the implementation of random_upto into the
 * two stages of (a) generate a bitmask which reduces a 32-bit random
 * number to within a factor of two of the right range, (b) repeatedly
 * generate numbers in that range until one is small enough. Splitting
 * it up like that means that random_upto_biased can do (a) only once
 * even when it does (b) lots of times.
 */

static uint32 random_upto_makemask(uint32 limit) {
    uint32 mask = 0xFFFFFFFF;
    int i;
    for (i = 16; i > 0; i >>= 1)
        if ((limit & (mask >> i)) == limit)
            mask >>= i;
    return mask;
}

static uint32 random_upto_internal(uint32 limit, uint32 mask) {
    uint32 ret;
    do {
        ret = random32() & mask;
    } while (ret > limit);
    return ret;
}

uint32 random_upto(uint32 limit) {
    uint32 mask = random_upto_makemask(limit);
    return random_upto_internal(limit, mask);
}

uint32 random_upto_biased(uint32 limit, int bias) {
    uint32 mask = random_upto_makemask(limit);

    uint32 ret = random_upto_internal(limit, mask);
    while (bias--) {
        uint32 tmp;
        tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
        tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
        tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
        tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
        tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
        tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
        tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
        tmp = random_upto_internal(limit, mask); if (tmp < ret) ret = tmp;
    }

    return ret;
}