mersenne.h

Go to the documentation of this file.

// mersenne.h - written and placed in public domain by Jeffrey Walton.
 
#ifndef CRYPTOPP_MERSENNE_TWISTER_H
#define CRYPTOPP_MERSENNE_TWISTER_H
 
#include "cryptlib.h"
#include "secblock.h"
#include "misc.h"
 
NAMESPACE_BEGIN(CryptoPP)
 
 
template <unsigned int K, unsigned int M, unsigned int N, unsigned int F, word32 S>
class MersenneTwister : public RandomNumberGenerator
{
public:
        CRYPTOPP_STATIC_CONSTEXPR const char* StaticAlgorithmName() { return (S==5489 ? "MT19937ar" : (S==4537 ? "MT19937" : "MT19937x")); }
 
        ~MersenneTwister() {}
 
        MersenneTwister(word32 seed = S) : m_idx(N)
        {
                Reset(seed);
        }
 
        bool CanIncorporateEntropy() const {return true;}
 
        void IncorporateEntropy(const byte *input, size_t length)
        {
                // Handle word32 size blocks
                FixedSizeSecBlock<word32, 1> temp;
                temp[0] = 0;
 
                if (length > 4)
                        length = 4;
 
                for (size_t i=0; i<length; ++i)
                {
                        temp[0] <<= 8;
                        temp[0] = temp[0] | input[i];
                }
 
                Reset(temp[0]);
        }
 
        void GenerateBlock(byte *output, size_t size)
        {
                // Handle word32 size blocks
                FixedSizeSecBlock<word32, 1> temp;
                for (size_t i=0; i < size/4; i++, output += 4)
                {
                        temp[0] = NextMersenneWord();
                        memcpy(output, temp+0, 4);
                }
 
                // No tail bytes
                if (size%4 == 0)
                        return;
 
                // Handle tail bytes
                temp[0] = NextMersenneWord();
                switch (size%4)
                {
                        case 3: output[2] = CRYPTOPP_GET_BYTE_AS_BYTE(temp[0], 1); /* fall through */
                        case 2: output[1] = CRYPTOPP_GET_BYTE_AS_BYTE(temp[0], 2); /* fall through */
                        case 1: output[0] = CRYPTOPP_GET_BYTE_AS_BYTE(temp[0], 3); break;
 
                        default: CRYPTOPP_ASSERT(0);;
                }
        }
 
        word32 GenerateWord32(word32 min=0, word32 max=0xffffffffL)
        {
                const word32 range = max-min;
                if (range == 0xffffffffL)
                        return NextMersenneWord();
 
                const int maxBits = BitPrecision(range);
                word32 value;
 
                do{
                        value = Crop(NextMersenneWord(), maxBits);
                } while (value > range);
 
                return value+min;
        }
 
        void DiscardBytes(size_t n)
        {
                for(size_t i=0; i < RoundUpToMultipleOf(n, 4U); i++)
                        NextMersenneWord();
        }
 
protected:
 
        void Reset(word32 seed)
        {
                m_idx = N;
 
                m_state[0] = seed;
                for (unsigned int i = 1; i < N+1; i++)
                        m_state[i] = word32(F * (m_state[i-1] ^ (m_state[i-1] >> 30)) + i);
        }
 
        word32 NextMersenneWord()
        {
                if (m_idx >= N) { Twist(); }
 
                word32 temp = m_state[m_idx++];
 
                temp ^= (temp >> 11);
                temp ^= (temp << 7)  & 0x9D2C5680; // 0x9D2C5680 (2636928640)
                temp ^= (temp << 15) & 0xEFC60000; // 0xEFC60000 (4022730752)
 
                return temp ^ (temp >> 18);
        }
 
        void Twist()
        {
                static const word32 magic[2]={0x0UL, K};
                word32 kk, temp;
 
                CRYPTOPP_ASSERT(N >= M);
                for (kk=0;kk<N-M;kk++)
                {
                        temp = (m_state[kk] & 0x80000000)|(m_state[kk+1] & 0x7FFFFFFF);
                        m_state[kk] = m_state[kk+M] ^ (temp >> 1) ^ magic[temp & 0x1UL];
                }
 
                for (;kk<N-1;kk++)
                {
                        temp = (m_state[kk] & 0x80000000)|(m_state[kk+1] & 0x7FFFFFFF);
                        m_state[kk] = m_state[kk+(M-N)] ^ (temp >> 1) ^ magic[temp & 0x1UL];
                }
 
                temp = (m_state[N-1] & 0x80000000)|(m_state[0] & 0x7FFFFFFF);
                m_state[N-1] = m_state[M-1] ^ (temp >> 1) ^ magic[temp & 0x1UL];
 
                // Reset index
                m_idx = 0;
 
                // Wipe temp
                SecureWipeArray(&temp, 1);
        }
 
private:
 
        FixedSizeSecBlock<word32, N+1> m_state;
        word32 m_idx;
};
 
#if CRYPTOPP_DOXYGEN_PROCESSING
class MT19937 : public MersenneTwister<0x9908B0DF /*2567483615*/, 397, 624, 0x10DCD /*69069*/, 4537> {};
#else
typedef MersenneTwister<0x9908B0DF /*2567483615*/, 397, 624, 0x10DCD /*69069*/, 4537> MT19937;
#endif
 
#if CRYPTOPP_DOXYGEN_PROCESSING
class MT19937ar : public MersenneTwister<0x9908B0DF /*2567483615*/, 397, 624, 0x6C078965 /*1812433253*/, 5489> {};
#else
typedef MersenneTwister<0x9908B0DF /*2567483615*/, 397, 624, 0x6C078965 /*1812433253*/, 5489> MT19937ar;
#endif
 
NAMESPACE_END
 
#endif // CRYPTOPP_MERSENNE_TWISTER_H