1 /*---------------------------------------------------------------------------*
2   Project:  Horizon
3   File:     math_TinyMt.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: 47727 $
14  *---------------------------------------------------------------------------*/
15 
16 #include <nn/types.h>
17 #include <nn/assert.h>
18 #include <nn/math/math_TinyMt.h>
19 #include <nn/crypto.h>
20 #include <algorithm>
21 
22 namespace nn { namespace math {
23 
24     namespace
25     {
MixMsb2(bit32 v)26         inline bit32 MixMsb2(bit32 v)
27         {
28             return v ^ (v >> 30);
29         }
30 
MixMsb5(bit32 v)31         inline bit32 MixMsb5(bit32 v)
32         {
33             return v ^ (v >> 27);
34         }
35     }
36     // anonymous namespace
37 
38 
39 
40     /* ------------------------------------------------------------------------
41             public
42        ------------------------------------------------------------------------ */
43 
Initialize()44     void TinyMt::Initialize()
45     {
46         crypto::GenerateRandomBytes(m_State, sizeof(m_State));
47     }
48 
Initialize(bit32 seed)49     void TinyMt::Initialize(bit32 seed)
50     {
51         m_State[0] = seed;
52         m_State[1] = PARAMETER_MAT1;
53         m_State[2] = PARAMETER_MAT2;
54         m_State[3] = PARAMETER_TMAT;;
55 
56         {
57             for( int i = 1; i < MIN_LOOP; ++i )
58             {
59                 const bit32 v = MixMsb2(m_State[(i - 1) % PARAMETER_N]);
60                 m_State[i % PARAMETER_N] ^= v * 0x6c078965 + i;
61             }
62         }
63 
64         FinalizeInitialization();
65     }
66 
Initialize(const bit32 * pSeed,int numSeed)67     void TinyMt::Initialize(const bit32* pSeed, int numSeed)
68     {
69         m_State[0] = 0;
70         m_State[1] = PARAMETER_MAT1;
71         m_State[2] = PARAMETER_MAT2;
72         m_State[3] = PARAMETER_TMAT;;
73 
74         {
75             const int numLoop = Max(numSeed + 1, MIN_LOOP) - 1;
76 
77             GenerateInitialValuePlus(m_State, 0, numSeed);
78 
79             int offset = 1;
80             for( int i = 0; i < numLoop; ++i )
81             {
82                 const bit32 seed = (i < numSeed) ? pSeed[i]: 0;
83                 GenerateInitialValuePlus(m_State, (offset + i) % PARAMETER_N, seed);
84             }
85 
86             offset = numLoop + 1;
87             for( int i = 0; i < PARAMETER_N; ++i )
88             {
89                 GenerateInitialValueXor(m_State, (offset + i) % PARAMETER_N);
90             }
91         }
92 
93         FinalizeInitialization();
94     }
95 
SaveState(TinyMt::State * pStateBuffer)96     void TinyMt::SaveState(TinyMt::State* pStateBuffer)
97     {
98         NN_POINTER_TASSERT_(pStateBuffer);
99 
100         std::memcpy(pStateBuffer->state, m_State, sizeof(pStateBuffer->state));
101     }
102 
RestoreState(const TinyMt::State * pStateBuffer)103     void TinyMt::RestoreState(const TinyMt::State* pStateBuffer)
104     {
105         NN_POINTER_TASSERT_(pStateBuffer);
106 
107         std::memcpy(m_State, pStateBuffer->state, sizeof(m_State));
108     }
109 
GenerateRandomU32()110     u32 TinyMt::GenerateRandomU32()
111     {
112         // Update the state
113         const bit32 a = (m_State[0] & BIT31_MASK) ^ m_State[1] ^ m_State[2];
114         const bit32 b = m_State[3];
115         const bit32 c = a ^ (a << 1);
116         const bit32 d = b ^ (b >> 1) ^ c;
117 
118         const bit32 s0 = m_State[1];
119               bit32 s1 = m_State[2];
120               bit32 s2 = c ^ (d << 10);
121         const bit32 s3 = d;
122 
123         if( (d & 1) != 0 )
124         {
125             s1 ^= PARAMETER_MAT1;
126             s2 ^= PARAMETER_MAT2;
127         }
128 
129         m_State[0] = s0;
130         m_State[1] = s1;
131         m_State[2] = s2;
132         m_State[3] = s3;
133 
134         // tempering
135         bit32 t = s0 + (s2 >> 8);
136         bit32 v = s3 ^ t;
137 
138         if( (t & 1) != 0 )
139         {
140             v ^= PARAMETER_TMAT;
141         }
142 
143         return v;
144     }
145 
GenerateRandomBytes(void * p,size_t size)146     void TinyMt::GenerateRandomBytes(void* p, size_t size)
147     {
148         uptr begin  = reinterpret_cast<uptr>(p);
149         uptr end    = begin + size;
150         uptr begin4 = RoundUp(begin, 4);
151         uptr end4   = RoundDown(end, 4);
152 
153         if( begin < begin4 )
154         {
155             bit32 v = GenerateRandomU32();
156             std::memcpy(reinterpret_cast<void*>(begin), &v, begin4 - begin);
157         }
158 
159         {
160             bit32* p32  = reinterpret_cast<bit32*>(begin4);
161             bit32* pEnd = reinterpret_cast<bit32*>(end4);
162 
163             while( p32 < pEnd )
164             {
165                 *p32++ = GenerateRandomU32();
166             }
167         }
168 
169         if( end4 < end )
170         {
171             bit32 v = GenerateRandomU32();
172             std::memcpy(reinterpret_cast<void*>(end4), &v, end - end4);
173         }
174     }
175 
176 
177 
178     /* ------------------------------------------------------------------------
179             private
180        ------------------------------------------------------------------------ */
181 
GenerateInitialValuePlus(bit32 * p,int d,bit32 k)182     void TinyMt::GenerateInitialValuePlus(bit32* p, int d, bit32 k)
183     {
184         bit32& s0 = p[d];
185         bit32& s1 = p[(d + 1) % PARAMETER_N];
186         bit32& s2 = p[(d + 2) % PARAMETER_N];
187         bit32& s3 = p[(d + 3) % PARAMETER_N];
188 
189         const bit32 a = MixMsb5(s0 ^ s1 ^ s3) * 0x0019660d;
190         const bit32 b = a + d + k;
191 
192         s0 = b;
193         s1 += a;
194         s2 += b;
195     }
196 
GenerateInitialValueXor(bit32 * p,int d)197     void TinyMt::GenerateInitialValueXor(bit32* p, int d)
198     {
199         bit32& s0 = p[d];
200         bit32& s1 = p[(d + 1) % PARAMETER_N];
201         bit32& s2 = p[(d + 2) % PARAMETER_N];
202         bit32& s3 = p[(d + 3) % PARAMETER_N];
203 
204         const bit32 a = MixMsb5(s0 + s1 + s3) * 0x5d588b65;
205         const bit32 b = a - d;
206 
207         s0 = b;
208         s1 ^= a;
209         s2 ^= b;
210     }
211 
FinalizeInitialization()212     void TinyMt::FinalizeInitialization()
213     {
214         const bit32 state031 = (m_State[0] & BIT31_MASK);
215 
216         if( (state031   == 0) && (m_State[1] == 0)
217          && (m_State[2] == 0) && (m_State[3] == 0) )
218         {
219             m_State[0] = 'T';
220             m_State[1] = 'I';
221             m_State[2] = 'N';
222             m_State[3] = 'Y';
223         }
224 
225         for( int i = 0; i < NUM_SKIP; ++i )
226         {
227             GenerateRandomU32();
228         }
229     }
230 
231 
232 
233 }}
234 
235