tests/util/mersenne.hpp

   1 /**************************************************************************
   2  *
   3  * Copyright 2012 VMware, Inc.
   4  * All Rights Reserved.
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sub license, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice (including the
  15  * next paragraph) shall be included in all copies or substantial portions
  16  * of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
  21  * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
  22  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  **************************************************************************/
  27
  28 #ifndef MERSENNE_HPP
  29 #define MERSENNE_HPP
  30
  31 #include <string>
  32 #include <stdio.h>
  33 #include <stdint.h>
  34
  35 /**
  36  * Variant of Mersenne Twister which can be skipped to any point in time.
  37  *
  38  * Instead of producing a new state table by mutating the previous table it initiates
  39  * again using a seed which is the last random value of the previous state
  40  */
  41
  42 class Mersenne
  43 {
  44 public:
  45    static const uint32_t n = 624;
  46    static const uint32_t m = 397;
  47    static const uint32_t b32 = 1 << 31;
  48    static const uint32_t rand_max = 0xFFFFFFFF;
  49
  50 public:
  51    Mersenne() :
  52       mSeed(0), mIndex(0), mState()
  53    {
  54    }
  55
  56    Mersenne(unsigned int seed)
  57    {
  58       init(seed);
  59    }
  60
  61    unsigned int value()
  62    {
  63       uint32_t x = mState[mIndex++];
  64       x ^= (x >> 11);
  65       x ^= (x << 7) & 0x9D2C5680;
  66       x ^= (x << 15) & 0xEFC60000;
  67       x ^= (x >> 18);
  68
  69       if (mIndex == n){
  70          init(x);
  71          return value();
  72       }
  73
  74       return x;
  75    }
  76
  77    unsigned int max()
  78    {
  79       return 0xFFFFFFFF;
  80    }
  81
  82    std::string state()
  83    {
  84       char buffer[32];
  85       sprintf(buffer, "%08x%03d", mSeed, mIndex);
  86       return buffer;
  87    }
  88
  89    void setState(const std::string& state){
  90       uint32_t seed, index;
  91       sscanf(state.c_str(), "%08x%03d", &seed, &index);
  92
  93       init(seed);
  94       mIndex = index;
  95    }
  96
  97    void init(uint32_t seed)
  98    {
  99       mIndex = 0;
 100       mSeed = seed;
 101
 102       /* Standard MT initialiser */
 103       mState[0] = seed;
 104
 105       for (uint32_t i = 1; i < n; ++i)
 106          mState[i] = 1812433253 * (mState[i - 1] ^ (mState[i - 1] >> 30)) + i;
 107
 108       /* Standard MT number generator, split into parts to avoid having to do % n */
 109       for (uint32_t i = 0; i < (n - m); ++i)
 110          mState[i] = mState[i + m] ^ twist(mState[i], mState[i + 1]);
 111
 112       for (uint32_t i = n - m; i < (n - 1); ++i)
 113          mState[i] = mState[i + m - n] ^ twist(mState[i], mState[i + 1]);
 114
 115       mState[n - 1] = mState[m - 1] ^ twist(mState[n - 1], mState[0]);
 116    }
 117
 118 private:
 119    inline uint32_t twist(uint32_t a, uint32_t b)
 120    {
 121       return (((a & b32) | (b & ~b32)) >> 1) ^ ((b & 1) ? 0x9908B0DF : 0);
 122    }
 123
 124 private:
 125    uint32_t mSeed;
 126    uint32_t mIndex;
 127    uint32_t mState[n];
 128 };
 129
 130 #endif // MERSENNE_HPP