xref: /dports/games/stonesoup/crawl-0.27.1/crawl-ref/source/random.cc

#include "AppHdr.h"

#include "random.h"

#include <cinttypes>
#include <cmath>
#if defined(UNIX) || defined(TARGET_COMPILER_MINGW)
# include <unistd.h>
#else
# include <process.h>
#endif

#include "pcg.h"
#include "syscalls.h"
#include "branch-type.h"
#include "state.h"
#include "store.h"
#include "options.h"

namespace rng
{
    // global/persistent rng state that will be saved
    static FixedVector<PcgRNG, rng::NUM_RNGS> _global_state;

    // temporary rng state
    static rng_type _generator = rng::GAMEPLAY;
    // TODO: once we have c++17, convert to type optional<PcgRNG>
    static PcgRNG * _sub_generator = nullptr;

    CrawlVector generators_to_vector()
    {
        CrawlVector store;
        for (PcgRNG& rng : _global_state)
            store.push_back(rng.to_vector()); // TODO is this ok memory-wise?
        return store;
    }

    vector<uint64_t> get_states()
    {
        // this doesn't return the internal state per se, but it returns the count
        // of 32 bit integers that have been drawn, which amounts to the same thing.
        // This isn't saved, though, so it's mainly useful for debugging within a
        // session.
        vector<uint64_t> result;
        for (PcgRNG& rng : _global_state)
            result.push_back(rng.get_count());
        return result;
    }

    void load_generators(const CrawlVector &v)
    {
        // as-is, decreasing the number of rngs (e.g. by removing a branch) will
        // break save compatibility.
        ASSERT(v.size() <= _global_state.size());
        for (int i = 0; i < v.size(); i++)
        {
            CrawlVector state = v[i].get_vector();
            _global_state[i] = PcgRNG(state);
        }
    }

    generator::generator(rng_type g) : previous(_generator)
    {
        ASSERT(g != rng::SUB_GENERATOR);
        _generator = g;
    }

    rng_type get_branch_generator(const branch_type b)
    {
        return static_cast<rng_type>(rng::LEVELGEN + static_cast<int>(b));
    }

    generator::generator(branch_type b) : previous(_generator)
    {
        _generator = get_branch_generator(b);
    }

    generator::~generator()
    {
        _generator = previous;
    }

    subgenerator::subgenerator(uint64_t seed, uint64_t sequence)
        : current(seed, sequence),
          previous(_sub_generator),
          previous_main(_generator)
    {
        _generator = rng::SUB_GENERATOR;
        _sub_generator = &current;
    }

    subgenerator::~subgenerator()
    {
        _generator = previous_main;
        _sub_generator = previous;
    }

    subgenerator::subgenerator(uint64_t seed)
        : subgenerator(seed, get_uint64())
    { }

    // call the 1-arg constructor so as to ensure a sequence point between the
    // two get_uint64 calls.
    subgenerator::subgenerator()
        : subgenerator(get_uint64())
    { }

    PcgRNG *get_generator(rng_type r)
    {
        UNUSED(r);
        ASSERT(_generator != ASSERT_NO_RNG);
        if (_generator == SUB_GENERATOR)
            return _sub_generator;
        else
            return &_global_state[_generator];
    }

    PcgRNG &current_generator()
    {
        PcgRNG *ret = get_generator(_generator);
        ASSERT(ret);
        return *ret;
    }

    uint32_t get_uint32()
    {
        return current_generator().get_uint32();
    }

    uint32_t peek_uint32()
    {
        PcgRNG tmp = current_generator(); // make a copy
        return tmp.get_uint32();
    }

    uint64_t get_uint64()
    {
        return current_generator().get_uint64();
    }

    uint64_t peek_uint64()
    {
        PcgRNG tmp = current_generator(); // make a copy
        return tmp.get_uint64();
    }

    static void _do_seeding(PcgRNG &master)
    {
        // TODO: don't initialize gameplay/ui rng?
        // Use the just seeded RNG to initialize the rest.
        for (PcgRNG& rng : _global_state)
        {
            uint64_t init_state = master.get_uint64();
            uint64_t seq = master.get_uint64();
            rng = PcgRNG(init_state, seq);
        }
    }

    void seed(uint64_t seed)
    {
        // use the default stream
        PcgRNG master = PcgRNG(seed);
        _do_seeding(master);
    }

    void seed()
    {
        // seed both state and sequence from system randomness.
        uint64_t seed_key[2];
        bool seeded = read_urandom((char*)(&seed_key), sizeof(seed_key));
        ASSERT(seeded);
        PcgRNG master = PcgRNG(seed_key[0], seed_key[1]);
        _do_seeding(master);
    }

    /**
     * Reset RNG to Options seed, and if that seed is 0, generate a new one.
     */
    void reset()
    {
        crawl_state.seed = Options.seed;
        while (!crawl_state.seed) // 0 = random seed
        {
            rng::seed(); // reset entirely via read_urandom
            crawl_state.seed = get_uint64();
        }
        dprf("Setting game seed to %" PRIu64, crawl_state.seed);
        you.game_seed = crawl_state.seed;
        rng::seed(crawl_state.seed);
    }
}

// TODO: probably this could all be in the rng namespace

// [low, high]
int random_range(int low, int high)
{
    ASSERT(low <= high);
    return low + random2(high - low + 1);
}

// [low, high]
int random_range(int low, int high, int nrolls)
{
    ASSERT(nrolls > 0);
    const int roll = random2avg(high - low + 1, nrolls);
    return low + roll;
}

// [0, max)
int random2(int max)
{
    if (max <= 1)
        return 0;

    return rng::current_generator().get_bounded_uint32(max);
}

// [0, max), separate RNG state
int ui_random(int max)
{
    rng::generator ui(rng::UI);

    return random2(max);
}

// [0, 1]
bool coinflip()
{
    return static_cast<bool>(random2(2));
}

// Returns random2(x) if random_factor is true, otherwise the mean.
// [0, x)
int maybe_random2(int x, bool random_factor)
{
    if (x <= 1)
        return 0;
    if (random_factor)
        return random2(x);
    else
        return x / 2;
}

// [0, ceil(nom/denom)]
int maybe_random_div(int nom, int denom, bool random_factor)
{
    if (nom <= 0)
        return 0;
    if (random_factor)
        return random2(nom + denom) / denom;
    else
        return nom / 2 / denom;
}

// [num, num*size]
int maybe_roll_dice(int num, int size, bool random)
{
    if (random)
        return roll_dice(num, size);
    else
        return (num + num * size) / 2;
}

// [num, num*size]
int roll_dice(int num, int size)
{
    int ret = 0;

    // If num <= 0 or size <= 0, then we'll just return the default
    // value of zero. This is good behaviour in that it will be
    // appropriate for calculated values that might be passed in.
    if (num > 0 && size > 0)
    {
        ret += num;     // since random2() is zero based

        for (int i = 0; i < num; i++)
            ret += random2(size);
    }

    return ret;
}

int dice_def::roll() const
{
    return roll_dice(num, size);
}

dice_def calc_dice(int num_dice, int max_damage, bool random)
{
    dice_def ret(num_dice, 0);

    if (num_dice <= 1)
    {
        ret.num  = 1;
        ret.size = max_damage;
    }
    else if (max_damage <= num_dice)
    {
        ret.num  = max_damage;
        ret.size = 1;
    }
    else if (random)
        ret.size = div_rand_round(max_damage, num_dice);
    else
        ret.size = max_damage / num_dice; // round down

    return ret;
}

// Calculates num/den and randomly adds one based on the remainder.
// [floor(num/den), ceil(num/den)]
int div_rand_round(int num, int den)
{
    int rem = num % den;
    if (rem)
        return num / den + (random2(den) < rem);
    else
        return num / den;
}

// Converts a double to an integer by randomly rounding.
// Currently does not handle negative inputs.
int rand_round(double x)
{
    ASSERT(x >= 0);
    return int(x) + decimal_chance(fmod(x, 1.0));
}

int div_round_up(int num, int den)
{
    return num / den + (num % den != 0);
}

// random2avg() returns same mean value as random2() but with a lower variance
// never use with rolls < 2 as that would be silly - use random2() instead {dlb}
// [0, max)
int random2avg(int max, int rolls)
{
    int sum = random2(max);

    for (int i = 0; i < (rolls - 1); i++)
        sum += random2(max + 1);

    return sum / rolls;
}

// biased_random2() takes values in the same range [0, max) as random2() but
// with mean value (max - 1)/(n + 1) biased towards the bottom end.
// This can be thought of as the smallest of n _distinct_ random integers
// chosen in [0, max + n - 1).
// Never use with n < 2.
int biased_random2(int max, int n)
{
    for (int i = 0; i < max; i++)
        if (x_chance_in_y(n, n + max - 1 - i))
            return i;
    return 0;
}

// originally designed to randomise evasion -
// values are slightly lowered near (max) and
// approach an upper limit somewhere near (limit/2)
// [0, max]
int random2limit(int max, int limit)
{
    int sum = 0;

    if (max < 1)
        return 0;

    for (int i = 0; i < max; i++)
        if (random2(limit) >= i)
            sum++;

    return sum;
}

/** Sample from a binomial distribution.
 *
 * This is the number of successes in a sequence of independent trials with
 * fixed probability.
 *
 * @param n_trials The number of trials.
 * @param trial_prob The numerator of the probability of success of each trial.
 *                   If greater than scale, the probability is 1.0.
 * @param scale The denominator of trial_prob, default 100.
 * @return the number of successes, range [0, n_trials]
 */
int binomial(unsigned n_trials, unsigned trial_prob, unsigned scale)
{
    int count = 0;
    for (unsigned i = 0; i < n_trials; ++i)
        if (::x_chance_in_y(trial_prob, scale))
            count++;

    return count;
}

// range [0, 1.0)
// This uses a technique described by Saito and Matsumoto at
// MCQMC'08. Given that the IEEE floating point numbers are
// uniformly distributed over [1,2), we generate a number in
// this range and then offset it onto the range [0,1). The
// choice of bits (masking v. shifting) is arbitrary and
// should be immaterial for high quality generators.
double random_real()
{
    static const uint64_t UPPER_BITS = 0x3FF0000000000000ULL;
    static const uint64_t LOWER_MASK = 0x000FFFFFFFFFFFFFULL;
    const uint64_t value = UPPER_BITS | (rng::get_uint64() & LOWER_MASK);
    double result;
    // Portable memory transmutation. The union trick almost always
    // works, but this is safer.
    memcpy(&result, &value, sizeof(value));
    return result - 1.0;
}

// Roll n_trials, return true if at least one succeeded. n_trials might be
// not integer.
// [0, 1]
bool bernoulli(double n_trials, double trial_prob)
{
    if (n_trials <= 0 || trial_prob <= 0)
        return false;
    return !decimal_chance(pow(1 - trial_prob, n_trials));
}

bool one_chance_in(int a_million)
{
    return random2(a_million) == 0;
}

bool x_chance_in_y(int x, int y)
{
    if (x <= 0)
        return false;

    if (x >= y)
        return true;

    return random2(y) < x;
}

// [val - lowfuzz, val + highfuzz]
int fuzz_value(int val, int lowfuzz, int highfuzz, int naverage)
{
    const int lfuzz = lowfuzz * val / 100,
        hfuzz = highfuzz * val / 100;
    return val + random2avg(lfuzz + hfuzz + 1, naverage) - lfuzz;
}

bool decimal_chance(double chance)
{
    return random_real() < chance;
}

// This is used when the front-end randomness is inconclusive. There are
// never more than two possibilities, which simplifies things.
bool defer_rand::x_chance_in_y_contd(int x, int y, int index)
{
    if (x <= 0)
        return false;

    if (x >= y)
        return true;

    do
    {
        if (index == int(bits.size()))
            bits.push_back(rng::get_uint32());

        uint64_t expn_rand_1 = uint64_t(bits[index++]) * y;
        uint64_t expn_rand_2 = expn_rand_1 + y;
        uint64_t expn_minimum_fail = uint64_t(x) << 32;

        if (expn_minimum_fail <= expn_rand_1)
            return false;

        if (expn_rand_2 <= expn_minimum_fail)
            return true;

        // y = expn_rand_2 - expn_rand_1;  no-op
        x = expn_minimum_fail - expn_rand_1;
    } while (1);
}

int defer_rand::random2(int maxp1)
{
    if (maxp1 <= 1)
        return 0;

    if (bits.empty())
        bits.push_back(rng::get_uint32());

    uint64_t expn_rand_1 = uint64_t(bits[0]) * maxp1;
    uint64_t expn_rand_2 = expn_rand_1 + maxp1;

    int val1 = int(expn_rand_1 >> 32);
    int val2 = int(expn_rand_2 >> 32);

    if (val2 == val1)
        return val1;

    // val2 == val1 + 1
    uint64_t expn_thresh = uint64_t(val2) << 32;

    return x_chance_in_y_contd(int(expn_thresh - expn_rand_1),
                               maxp1, 1)
         ? val1 : val2;
}

defer_rand& defer_rand::operator[](int i)
{
    return children[i];
}

int defer_rand::random_range(int low, int high)
{
    ASSERT(low <= high);
    return low + random2(high - low + 1);
}

int defer_rand::random2avg(int max, int rolls)
{
    int sum = (*this)[0].random2(max);

    for (int i = 0; i < (rolls - 1); i++)
        sum += (*this)[i+1].random2(max + 1);

    return sum / rolls;
}