contrib/bc/include/rand.h

   1 /*
   2  * *****************************************************************************
   3  *
   4  * SPDX-License-Identifier: BSD-2-Clause
   5  *
   6  * Copyright (c) 2018-2019 Gavin D. Howard and contributors.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions are met:
  10  *
  11  * * Redistributions of source code must retain the above copyright notice, this
  12  *   list of conditions and the following disclaimer.
  13  *
  14  * * Redistributions in binary form must reproduce the above copyright notice,
  15  *   this list of conditions and the following disclaimer in the documentation
  16  *   and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  19  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  21  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  22  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  25  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  26  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  27  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28  * POSSIBILITY OF SUCH DAMAGE.
  29  *
  30  * *****************************************************************************
  31  *
  32  * Parts of this code are adapted from the following:
  33  *
  34  * PCG, A Family of Better Random Number Generators.
  35  *
  36  * You can find the original source code at:
  37  *   https://github.com/imneme/pcg-c
  38  *
  39  * -----------------------------------------------------------------------------
  40  *
  41  * Parts of this code are also under the following license:
  42  *
  43  * Copyright (c) 2014-2017 Melissa O'Neill and PCG Project contributors
  44  *
  45  * Permission is hereby granted, free of charge, to any person obtaining a copy
  46  * of this software and associated documentation files (the "Software"), to deal
  47  * in the Software without restriction, including without limitation the rights
  48  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  49  * copies of the Software, and to permit persons to whom the Software is
  50  * furnished to do so, subject to the following conditions:
  51  *
  52  * The above copyright notice and this permission notice shall be included in
  53  * all copies or substantial portions of the Software.
  54  *
  55  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  56  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  57  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  58  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  59  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  60  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  61  * SOFTWARE.
  62  *
  63  * *****************************************************************************
  64  *
  65  * Definitions for the RNG.
  66  *
  67  */
  68
  69 #ifndef BC_RAND_H
  70 #define BC_RAND_H
  71
  72 #include <stdint.h>
  73 #include <inttypes.h>
  74
  75 #include <vector.h>
  76 #include <num.h>
  77
  78 #if BC_ENABLE_EXTRA_MATH
  79
  80 #if BC_ENABLE_RAND
  81
  82 typedef ulong (*BcRandUlong)(void*);
  83
  84 #if BC_LONG_BIT >= 64
  85
  86 #ifdef BC_RAND_BUILTIN
  87 #if BC_RAND_BUILTIN
  88 #ifndef __SIZEOF_INT128__
  89 #undef BC_RAND_BUILTIN
  90 #define BC_RAND_BUILTIN (0)
  91 #endif // __SIZEOF_INT128__
  92 #endif // BC_RAND_BUILTIN
  93 #endif // BC_RAND_BUILTIN
  94
  95 #ifndef BC_RAND_BUILTIN
  96 #ifdef __SIZEOF_INT128__
  97 #define BC_RAND_BUILTIN (1)
  98 #else // __SIZEOF_INT128__
  99 #define BC_RAND_BUILTIN (0)
 100 #endif // __SIZEOF_INT128__
 101 #endif // BC_RAND_BUILTIN
 102
 103 typedef uint64_t BcRand;
 104
 105 #define BC_RAND_ROTC (63)
 106
 107 #if BC_RAND_BUILTIN
 108
 109 typedef __uint128_t BcRandState;
 110
 111 #define bc_rand_mul(a, b) (((BcRandState) (a)) * ((BcRandState) (b)))
 112 #define bc_rand_add(a, b) (((BcRandState) (a)) + ((BcRandState) (b)))
 113
 114 #define bc_rand_mul2(a, b) (((BcRandState) (a)) * ((BcRandState) (b)))
 115 #define bc_rand_add2(a, b) (((BcRandState) (a)) + ((BcRandState) (b)))
 116
 117 #define BC_RAND_NOTMODIFIED(r) (((r)->inc & 1UL) == 0)
 118 #define BC_RAND_ZERO(r) (!(r)->state)
 119
 120 #define BC_RAND_CONSTANT(h, l) ((((BcRandState) (h)) << 64) + (BcRandState) (l))
 121
 122 #define BC_RAND_TRUNC(s) ((uint64_t) (s))
 123 #define BC_RAND_CHOP(s) ((uint64_t) ((s) >> 64UL))
 124 #define BC_RAND_ROTAMT(s) ((unsigned int) ((s) >> 122UL))
 125
 126 #else // BC_RAND_BUILTIN
 127
 128 typedef struct BcRandState {
 129
 130         uint_fast64_t lo;
 131         uint_fast64_t hi;
 132
 133 } BcRandState;
 134
 135 #define bc_rand_mul(a, b) (bc_rand_multiply((a), (b)))
 136 #define bc_rand_add(a, b) (bc_rand_addition((a), (b)))
 137
 138 #define bc_rand_mul2(a, b) (bc_rand_multiply2((a), (b)))
 139 #define bc_rand_add2(a, b) (bc_rand_addition2((a), (b)))
 140
 141 #define BC_RAND_NOTMODIFIED(r) (((r)->inc.lo & 1) == 0)
 142 #define BC_RAND_ZERO(r) (!(r)->state.lo && !(r)->state.hi)
 143
 144 #define BC_RAND_CONSTANT(h, l) { .lo = (l), .hi = (h) }
 145
 146 #define BC_RAND_TRUNC(s) ((s).lo)
 147 #define BC_RAND_CHOP(s) ((s).hi)
 148 #define BC_RAND_ROTAMT(s) ((unsigned int) ((s).hi >> 58UL))
 149
 150 #define BC_RAND_BOTTOM32 (((uint_fast64_t) 0xffffffffULL))
 151 #define BC_RAND_TRUNC32(n) ((n) & BC_RAND_BOTTOM32)
 152 #define BC_RAND_CHOP32(n) ((n) >> 32)
 153
 154 #endif // BC_RAND_BUILTIN
 155
 156 #define BC_RAND_MULTIPLIER \
 157         BC_RAND_CONSTANT(2549297995355413924ULL, 4865540595714422341ULL)
 158
 159 #define BC_RAND_FOLD(s) ((BcRand) (BC_RAND_CHOP(s) ^ BC_RAND_TRUNC(s)))
 160
 161 #else // BC_LONG_BIT >= 64
 162
 163 #undef BC_RAND_BUILTIN
 164 #define BC_RAND_BUILTIN (1)
 165
 166 typedef uint32_t BcRand;
 167
 168 #define BC_RAND_ROTC (31)
 169
 170 typedef uint_fast64_t BcRandState;
 171
 172 #define bc_rand_mul(a, b) (((BcRandState) (a)) * ((BcRandState) (b)))
 173 #define bc_rand_add(a, b) (((BcRandState) (a)) + ((BcRandState) (b)))
 174
 175 #define bc_rand_mul2(a, b) (((BcRandState) (a)) * ((BcRandState) (b)))
 176 #define bc_rand_add2(a, b) (((BcRandState) (a)) + ((BcRandState) (b)))
 177
 178 #define BC_RAND_NOTMODIFIED(r) (((r)->inc & 1UL) == 0)
 179 #define BC_RAND_ZERO(r) (!(r)->state)
 180
 181 #define BC_RAND_CONSTANT UINT64_C
 182 #define BC_RAND_MULTIPLIER BC_RAND_CONSTANT(6364136223846793005)
 183
 184 #define BC_RAND_TRUNC(s) ((uint32_t) (s))
 185 #define BC_RAND_CHOP(s) ((uint32_t) ((s) >> 32UL))
 186 #define BC_RAND_ROTAMT(s) ((unsigned int) ((s) >> 59UL))
 187
 188 #define BC_RAND_FOLD(s) ((BcRand) ((((s) >> 18U) ^ (s)) >> 27U))
 189
 190 #endif // BC_LONG_BIT >= 64
 191
 192 #define BC_RAND_ROT(v, r) \
 193         ((BcRand) (((v) >> (r)) | ((v) << ((0 - (r)) & BC_RAND_ROTC))))
 194
 195 #define BC_RAND_BITS (sizeof(BcRand) * CHAR_BIT)
 196 #define BC_RAND_STATE_BITS (sizeof(BcRandState) * CHAR_BIT)
 197
 198 #define BC_RAND_NUM_SIZE (BC_NUM_BIGDIG_LOG10 * 2 + 2)
 199
 200 #define BC_RAND_SRAND_BITS ((1 << CHAR_BIT) - 1)
 201
 202 typedef struct BcRNGData {
 203
 204         BcRandState state;
 205         BcRandState inc;
 206
 207 } BcRNGData;
 208
 209 typedef struct BcRNG {
 210
 211         BcVec v;
 212
 213 } BcRNG;
 214
 215 void bc_rand_init(BcRNG *r);
 216 #ifndef NDEBUG
 217 void bc_rand_free(BcRNG *r);
 218 #endif // NDEBUG
 219
 220 BcRand bc_rand_int(BcRNG *r);
 221 BcRand bc_rand_bounded(BcRNG *r, BcRand bound);
 222 void bc_rand_seed(BcRNG *r, ulong state1, ulong state2, ulong inc1, ulong inc2);
 223 void bc_rand_push(BcRNG *r);
 224 void bc_rand_pop(BcRNG *r, bool reset);
 225 void bc_rand_getRands(BcRNG *r, BcRand *s1, BcRand *s2, BcRand *i1, BcRand *i2);
 226 void bc_rand_srand(BcRNGData *rng);
 227
 228 extern const BcRandState bc_rand_multiplier;
 229
 230 #endif // BC_ENABLE_RAND
 231
 232 #endif // BC_ENABLE_EXTRA_MATH
 233
 234 #endif // BC_RAND_H