git.cworth.org Git - vogl/blob - src/voglcore/vogl_rand.h

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: vogl_rand.h
  28 #pragma once
  29
  30 #include "vogl_core.h"
  31 #include "vogl_threading.h"
  32
  33 #define VOGL_SHR3 (jsr ^= (jsr << 17), jsr ^= (jsr >> 13), jsr ^= (jsr << 5))
  34 #define VOGL_CONG (jcong = 69069 * jcong + 1234567)
  35
  36 namespace vogl
  37 {
  38     class md5_hash;
  39
  40     class kiss99
  41     {
  42     public:
  43         kiss99();
  44
  45         void seed(uint32 i, uint32 j, uint32 k);
  46
  47         inline uint32 next();
  48
  49     private:
  50         uint32 x;
  51         uint32 y;
  52         uint32 z;
  53         uint32 c;
  54     };
  55
  56     class well512
  57     {
  58     public:
  59         well512();
  60
  61         enum
  62         {
  63             cStateSize = 16
  64         };
  65         void seed(uint32 seed[cStateSize]);
  66         void seed(uint32 seed);
  67         void seed(uint32 seed1, uint32 seed2, uint32 seed3);
  68         void seed(uint32 seed1, uint32 seed2, uint32 seed3, uint seed4);
  69
  70         inline uint32 next();
  71
  72     private:
  73         uint32 m_state[cStateSize];
  74         uint32 m_index;
  75     };
  76
  77     class ranctx
  78     {
  79     public:
  80         ranctx()
  81         {
  82             seed(0xDE149737);
  83         }
  84
  85         void seed(uint32 seed);
  86
  87         inline uint32 next();
  88
  89     private:
  90         uint32 a;
  91         uint32 b;
  92         uint32 c;
  93         uint32 d;
  94     };
  95
  96     // Originally from Numerical Recipes in C
  97     // Interesting because the seed is just a 64-bit counter.
  98     class pdes
  99     {
 100     public:
 101         pdes()
 102             : m_ctr(0)
 103         {
 104         }
 105
 106         void seed(uint64_t s)
 107         {
 108             m_ctr = s;
 109         }
 110
 111         inline uint64_t get_seed() const
 112         {
 113             return m_ctr;
 114         }
 115
 116         inline uint32 next32()
 117         {
 118             uint32 l = static_cast<uint32>(m_ctr);
 119             uint32 h = static_cast<uint32>(m_ctr >> 32U);
 120             psdes_hash_64(&h, &l);
 121             m_ctr++;
 122             return l;
 123         }
 124
 125         inline uint64_t next64()
 126         {
 127             uint32 l = static_cast<uint32>(m_ctr);
 128             uint32 h = static_cast<uint32>(m_ctr >> 32U);
 129             psdes_hash_64(&h, &l);
 130             m_ctr++;
 131             return static_cast<uint64_t>(l) | (static_cast<uint64_t>(h) << 32U);
 132         }
 133
 134     private:
 135         void psdes_hash_64(uint *pword0, uint *pword1)
 136         {
 137             const uint NITER = 4;
 138             uint i, iswap, ia, iah, ial, ib, ic;
 139             static const uint c1[NITER] = { 0xbaa96887, 0x1e17d32c, 0x03bcdc3c, 0x0f33d1b2 };
 140             static const uint c2[NITER] = { 0x4b0f3b58, 0xe874f0c3, 0x6955c5a6, 0x55a7ca46 };
 141             for (i = 0; i < NITER; i++)
 142             {
 143                 iswap = *pword1;
 144                 ia = iswap ^ c1[i];
 145                 ial = ia & 0xffff;
 146                 iah = ia >> 16;
 147                 ib = ial * ial + ~(iah * iah);
 148                 ic = (ib >> 16) | ((ib & 0xffff) << 16);
 149                 *pword1 = (*pword0) ^ ((ic ^ c2[i]) + ial * iah);
 150                 *pword0 = iswap;
 151             }
 152         }
 153
 154         uint64_t m_ctr;
 155     };
 156
 157     class random
 158     {
 159     public:
 160         random();
 161         random(uint32 i);
 162
 163         void seed();
 164         void seed(uint32 i);
 165         void seed(uint32 i1, uint32 i2, uint32 i3);
 166         void seed(uint32 i1, uint32 i2, uint32 i3, uint32 i4);
 167         void seed(const md5_hash &h);
 168         void seed_from_urandom();
 169
 170         uint8 urand8()
 171         {
 172             return static_cast<uint8>(urand32());
 173         }
 174         uint16 urand16()
 175         {
 176             return static_cast<uint16>(urand32());
 177         }
 178         uint32 urand32();
 179         uint64_t urand64();
 180
 181         // "Fast" variant uses no multiplies.
 182         uint32 fast_urand32();
 183
 184         uint32 get_bit();
 185
 186         // Returns random double between [0, 1)
 187         double drand(double l, double h);
 188
 189         float frand(float l, float h);
 190
 191         // Returns random signed int between [l, h)
 192         int irand(int l, int h);
 193
 194         // Returns random signed int between [l, h]
 195         int irand_inclusive(int l, int h);
 196
 197         // Returns random unsigned int between [l, h)
 198         uint urand(uint l, uint h);
 199
 200         // Returns random unsigned int between [l, h]
 201         uint urand_inclusive(uint l, uint h);
 202
 203         // Returns random 64-bit unsigned int between [l, h)
 204         uint64_t urand64(uint64_t l, uint64_t h);
 205
 206         // Returns random 64-bit unsigned int between [l, h]
 207         uint64_t urand64_inclusive(uint64_t l, uint64_t h);
 208
 209         double gaussian(double mean, double stddev);
 210
 211     private:
 212         ranctx m_ranctx;
 213         kiss99 m_kiss99;
 214         well512 m_well512;
 215         pdes m_pdes;
 216     };
 217
 218     class thread_safe_random
 219     {
 220     public:
 221         thread_safe_random();
 222         thread_safe_random(uint32 i);
 223
 224         void seed();
 225         void seed(uint32 i);
 226         void seed(uint32 i1, uint32 i2, uint32 i3);
 227         void seed(uint32 i1, uint32 i2, uint32 i3, uint32 i4);
 228         void seed(const md5_hash &h);
 229         void seed_from_urandom();
 230
 231         uint8 urand8();
 232         uint16 urand16();
 233         uint32 urand32();
 234         uint64_t urand64();
 235
 236         // "Fast" variant uses no multiplies.
 237         uint32 fast_urand32();
 238
 239         uint32 get_bit();
 240
 241         // Returns random double between [0, 1)
 242         double drand(double l, double h);
 243
 244         float frand(float l, float h);
 245
 246         // Returns random signed int between [l, h)
 247         int irand(int l, int h);
 248
 249         // Returns random signed int between [l, h]
 250         int irand_inclusive(int l, int h);
 251
 252         // Returns random unsigned int between [l, h)
 253         uint urand(uint l, uint h);
 254
 255         // Returns random unsigned int between [l, h]
 256         uint urand_inclusive(uint l, uint h);
 257
 258         // Returns random 64-bit unsigned int between [l, h)
 259         uint64_t urand64(uint64_t l, uint64_t h);
 260
 261         // Returns random 64-bit unsigned int between [l, h]
 262         uint64_t urand64_inclusive(uint64_t l, uint64_t h);
 263
 264         double gaussian(double mean, double stddev);
 265
 266     private:
 267         random m_rm;
 268         spinlock m_spinlock;
 269     };
 270
 271     // Simpler, minimal state PRNG - combines SHR3 and CONG.
 272     // This thing fails many tests (Gorilla, Collision, Birthday).
 273     class fast_random
 274     {
 275     public:
 276         inline fast_random()
 277             : jsr(0xABCD917A), jcong(0x17F3DEAD)
 278         {
 279         }
 280         inline fast_random(const fast_random &other)
 281             : jsr(other.jsr), jcong(other.jcong)
 282         {
 283         }
 284         inline fast_random(uint32 i)
 285         {
 286             seed(i);
 287         }
 288         inline fast_random &operator=(const fast_random &other)
 289         {
 290             jsr = other.jsr;
 291             jcong = other.jcong;
 292             return *this;
 293         }
 294
 295         inline void seed(uint32 i);
 296         inline void set_default_seed()
 297         {
 298             jsr = 0xABCD917A;
 299             jcong = 0x17F3DEAD;
 300         }
 301
 302         inline uint32 urand32();
 303         inline uint64_t urand64();
 304         inline uint32 get_bit();
 305
 306         int irand(int l, int h);
 307         uint urand(uint l, uint h);
 308
 309         double drand(double l, double h);
 310
 311         float frand(float l, float h);
 312
 313     private:
 314         uint32 jsr;
 315         uint32 jcong;
 316     };
 317
 318     // inlines
 319
 320     inline void fast_random::seed(uint32 i)
 321     {
 322         jsr = i;
 323         VOGL_SHR3;
 324         jcong = (~i) ^ 0xDEADBEEF;
 325     }
 326
 327     inline uint32 fast_random::urand32()
 328     {
 329         return VOGL_SHR3 ^ VOGL_CONG;
 330     }
 331
 332     inline uint32 fast_random::get_bit()
 333     {
 334         uint32 k = urand32();
 335         return ((k >> 31U) ^ (k >> 29U)) & 1;
 336     }
 337
 338     inline uint64_t fast_random::urand64()
 339     {
 340         uint64_t result = urand32();
 341         result <<= 32ULL;
 342         result |= urand32();
 343         return result;
 344     }
 345
 346     inline void memset_random(fast_random &context, void *pDst, uint n)
 347     {
 348         while (n >= 4)
 349         {
 350             *reinterpret_cast<uint32 *>(pDst) = context.urand32();
 351             pDst = reinterpret_cast<uint32 *>(pDst) + 1;
 352             n -= 4;
 353         }
 354
 355         while (n)
 356         {
 357             *reinterpret_cast<uint8 *>(pDst) = static_cast<uint8>(context.urand32());
 358             pDst = reinterpret_cast<uint8 *>(pDst) + 1;
 359             --n;
 360         }
 361     }
 362
 363     // non-thread safe global instances, for simplicity in single threaded tools/experiments
 364     extern random g_random;
 365     extern fast_random g_fast_random;
 366     extern thread_safe_random g_thread_safe_random;
 367
 368     bool rand_test();
 369
 370 } // namespace vogl