1 /*---------------------------------------------------------------------------*
2   Project:  Horizon
3   File:     math_MersenneTwister.cpp
4 
5   Copyright (C)2009-2012 Nintendo Co., Ltd.  All rights reserved.
6 
7   These coded instructions, statements, and computer programs contain
8   proprietary information of Nintendo of America Inc. and/or Nintendo
9   Company Ltd., and are protected by Federal copyright law. They may
10   not be disclosed to third parties or copied or duplicated in any form,
11   in whole or in part, without the prior written consent of Nintendo.
12 
13   $Rev: 47665 $
14  *---------------------------------------------------------------------------*/
15 
16 #include <nn/types.h>
17 #include <nn/assert.h>
18 #include <nn/math/math_MersenneTwister.h>
19 #include <nn/crypto.h>
20 
21 namespace nn { namespace math {
22 
23     const int   MersenneTwister::PARAMETER_N;
24 
25     namespace
26     {
MixMsb2(bit32 v)27         inline bit32 MixMsb2(bit32 v)
28         {
29             return v ^ (v >> 30);
30         }
31 
GenerateInitialValue(const bit32 * pState,int index,bit32 d)32         bit32 GenerateInitialValue(const bit32* pState, int index, bit32 d)
33         {
34             const bit32 s0 = pState[index + 0];
35             const bit32 s1 = pState[index + 1];
36 
37             const bit32 a = MixMsb2(s0);
38             const bit32 b = s1 ^ (a * d);
39 
40             return b;
41         }
42     }
43     // anonymous namespace
44 
45 
46 
47     /* ------------------------------------------------------------------------
48             public
49        ------------------------------------------------------------------------ */
50 
Initialize()51     void MersenneTwister::Initialize()
52     {
53         crypto::GenerateRandomBytes(m_State, sizeof(m_State));
54         m_Index = 0;
55     }
56 
Initialize(bit32 seed)57     void MersenneTwister::Initialize(bit32 seed)
58     {
59         m_State[0] = seed;
60 
61         for( int i = 1; i < PARAMETER_N; i++ )
62         {
63             const bit32 v = MixMsb2(m_State[i - 1]);
64             m_State[i] = v * 0x6c078965 + i;
65         }
66 
67         m_Index = 0;
68     }
69 
Initialize(const bit32 * pSeed,int num)70     void MersenneTwister::Initialize(const bit32* pSeed, int num)
71     {
72         Initialize(0x012bd6aa);
73 
74         int stateIndex = 0;
75 
76         {
77             const int numLoop = Max(PARAMETER_N, num);
78             int seedIndex = 0;
79 
80             for( int i = 0; i < numLoop; ++i )
81             {
82                 const bit32 v = GenerateInitialValue(m_State, stateIndex, 0x0019660d);
83 
84                 stateIndex++;
85 
86                 m_State[stateIndex] = v + pSeed[seedIndex] + seedIndex;
87 
88                 if( stateIndex >= PARAMETER_N - 1 )
89                 {
90                     m_State[0] = m_State[PARAMETER_N - 1];
91                     stateIndex = 0;
92                 }
93 
94                 seedIndex++;
95                 if( seedIndex >= num )
96                 {
97                     seedIndex = 0;
98                 }
99             }
100         }
101 
102         for( int i = 0; i < PARAMETER_N - 1; ++i )
103         {
104             const bit32 v = GenerateInitialValue(m_State, stateIndex, 0x5d588b65);
105 
106             stateIndex++;
107 
108             m_State[stateIndex] = v - stateIndex;
109 
110             if( stateIndex >= PARAMETER_N - 1 )
111             {
112                 m_State[0] = m_State[PARAMETER_N - 1];
113                 stateIndex = 0;
114             }
115         }
116 
117         m_State[0] = 0x80000000;
118     }
119 
SaveState(MersenneTwister::State * pStateBuffer)120     void MersenneTwister::SaveState(MersenneTwister::State* pStateBuffer)
121     {
122         NN_POINTER_TASSERT_(pStateBuffer);
123 
124         for( int i = 0; i < PARAMETER_N; ++i )
125         {
126             pStateBuffer->state[i] = m_State[i];
127         }
128 
129         pStateBuffer->index = m_Index;
130     }
131 
RestoreState(const MersenneTwister::State * pStateBuffer)132     void MersenneTwister::RestoreState(const MersenneTwister::State* pStateBuffer)
133     {
134         NN_POINTER_TASSERT_(pStateBuffer);
135         NN_MINMAX_TASSERT_(pStateBuffer->index, 0, PARAMETER_N - 1);
136 
137         for( int i = 0; i < PARAMETER_N; ++i )
138         {
139             m_State[i] = pStateBuffer->state[i];
140         }
141 
142         m_Index = pStateBuffer->index;
143     }
144 
GenerateRandomU32()145     u32 MersenneTwister::GenerateRandomU32()
146     {
147         u32 v;
148 
149         // Updates the state
150         {
151             int currIndex = m_Index;
152             int nextIndex = currIndex + 1;
153             int baseIndex = currIndex + PARAMETER_M;
154 
155             if( nextIndex >= PARAMETER_N )
156             {
157                 nextIndex -= PARAMETER_N;
158             }
159             if( baseIndex >= PARAMETER_N )
160             {
161                 baseIndex -= PARAMETER_N;
162             }
163 
164             v = GenerateXkn(m_State[baseIndex], m_State[currIndex], m_State[nextIndex]);
165 
166             m_State[currIndex] = v;
167             m_Index = nextIndex;
168         }
169 
170 
171         // tempering
172         v ^= (v >> PARAMETER_U);
173         v ^= (v << PARAMETER_S) & PARAMETER_B;
174         v ^= (v << PARAMETER_T) & PARAMETER_C;
175         v ^= (v >> PARAMETER_L);
176 
177         return v;
178     }
179 
GenerateRandomBytes(void * p,size_t size)180     void MersenneTwister::GenerateRandomBytes(void* p, size_t size)
181     {
182         uptr begin  = reinterpret_cast<uptr>(p);
183         uptr end    = begin + size;
184         uptr begin4 = RoundUp(begin, 4);
185         uptr end4   = RoundDown(end, 4);
186 
187         if( begin < begin4 )
188         {
189             bit32 v = GenerateRandomU32();
190             std::memcpy(reinterpret_cast<void*>(begin), &v, begin4 - begin);
191         }
192 
193         {
194             bit32* p32  = reinterpret_cast<bit32*>(begin4);
195             bit32* pEnd = reinterpret_cast<bit32*>(end4);
196 
197             while( p32 < pEnd )
198             {
199                 *p32++ = GenerateRandomU32();
200             }
201         }
202 
203         if( end4 < end )
204         {
205             bit32 v = GenerateRandomU32();
206             std::memcpy(reinterpret_cast<void*>(end4), &v, end - end4);
207         }
208     }
209 
210 
211 
212     /* ------------------------------------------------------------------------
213             private
214        ------------------------------------------------------------------------ */
215 
MixBits(bit32 u,bit32 l)216     inline bit32 MersenneTwister::MixBits(bit32 u, bit32 l)
217     {
218         return (u & MIX_MASK) | (l & ~MIX_MASK);
219     }
220 
GenerateXkn(bit32 xkm,bit32 xk,bit32 xk1)221     inline bit32 MersenneTwister::GenerateXkn(bit32 xkm, bit32 xk, bit32 xk1)
222     {
223         bit32 v = (MixBits(xk, xk1) >> 1);
224 
225         if( (xk1 & 1) != 0 )
226         {
227             v ^= PARAMETER_A;
228         }
229 
230         return xkm ^ v;
231     }
232 
233 
234 
235 }}
236 
237