tinymt-cpp  0.0.1
tinymt.h
Go to the documentation of this file.
1 /*
2  * tinymt.h (0.1.0-dev)
3  *
4  * A C++11 header-only implementation of the TinyMT pseudo-random number
5  * generator. The latest version and documentation can be found at:
6  *
7  * https://github.com/tueda/tinymt-cpp
8  *
9  * This is based on and heavily influenced by the original code base written by
10  * Mutsuo Saito and Makoto Matsumoto, which is available at:
11  *
12  * https://github.com/MersenneTwister-Lab/TinyMT
13  *
14  * =============================================================================
15  *
16  * Copyright (c) 2011, 2013 Mutsuo Saito, Makoto Matsumoto, Hiroshima University
17  * and The University of Tokyo.
18  *
19  * Copyright (c) 2020 Takahiro Ueda, Seikei University.
20  *
21  * All rights reserved.
22  *
23  * Redistribution and use in source and binary forms, with or without
24  * modification, are permitted provided that the following conditions are
25  * met:
26  *
27  * * Redistributions of source code must retain the above copyright
28  * notice, this list of conditions and the following disclaimer.
29  * * Redistributions in binary form must reproduce the above
30  * copyright notice, this list of conditions and the following
31  * disclaimer in the documentation and/or other materials provided
32  * with the distribution.
33  * * Neither the name of the Hiroshima University nor the names of
34  * its contributors may be used to endorse or promote products
35  * derived from this software without specific prior written
36  * permission.
37  *
38  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
39  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
40  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
41  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
42  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
43  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
44  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
45  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
46  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
47  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
48  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
49  */
50 
51 #ifndef TINYMT_TINYMT_H
52 #define TINYMT_TINYMT_H
53 
54 #include <array>
55 #include <cstddef>
56 #include <cstdint>
57 #include <istream>
58 #include <limits>
59 #include <ostream>
60 #include <type_traits>
61 
67 #define TINYMT_CPP_ENABLE_WHEN(...) \
68  typename TINYMT_CPP_ENABLE_WHEN_T_ = std::nullptr_t, \
69  typename std::enable_if < std::is_same<TINYMT_CPP_ENABLE_WHEN_T_, \
70  std::nullptr_t>::value && \
71  (__VA_ARGS__), \
72  std::nullptr_t > ::type = nullptr
73 
77 namespace tinymt {
78 
83 namespace detail {
84 
88 constexpr uint_least32_t tinymt32_default_param_mat1 = 0x8f7011eeU;
89 
93 constexpr uint_least32_t tinymt32_default_param_mat2 = 0xfc78ff1fU;
94 
98 constexpr uint_least32_t tinymt32_default_param_tmat = 0x3793fdffU;
99 
107 // This implementation must be probably almost portable; it covers 3 major
108 // signed integer representations:
109 //
110 // (-1) & (1) (-1) & (2)
111 // Two's complement 1 2
112 // One's complement 0 2
113 // Sign and magnitude 1 0
114 //
115 // Please point out if there is any compiler/system for which the following code
116 // gives a wrong result and the compiler still implements the C++11 standard
117 // correctly (possibly excess-K?).
118 template <class T>
120  : std::conditional<(typename std::make_signed<T>::type(-1) &
121  typename std::make_signed<T>::type(1)) &&
122  (typename std::make_signed<T>::type(-1) &
123  typename std::make_signed<T>::type(2)),
124 #ifndef TINYMT_CPP_TWOS_COMPLEMENT
125  std::true_type, std::false_type>::type {
126 #elif TINYMT_CPP_TWOS_COMPLEMENT
127  std::true_type, std::true_type>::type {
128 #else
129  std::false_type, std::false_type>::type {
130 #endif
131 
132  static_assert(std::is_integral<T>::value, "T must be an integral type");
133 };
134 
138 template <class UIntType>
140  UIntType mat1;
141  UIntType mat2;
142  UIntType tmat;
143 };
144 
148 template <class UIntType, std::size_t WordSize, std::uintmax_t Mat1,
149  std::uintmax_t Mat2, std::uintmax_t TMat>
151 
152 template <class UIntType, std::uintmax_t Mat1, std::uintmax_t Mat2,
153  std::uintmax_t TMat>
154 struct tinymt_engine_status<UIntType, 32, Mat1, Mat2, TMat> {
155  using result_type = UIntType;
156  std::array<result_type, 4> status;
157  static constexpr result_type mat1 = Mat1;
158  static constexpr result_type mat2 = Mat2;
159  static constexpr result_type tmat = TMat;
160  struct is_dynamic : std::false_type {};
161 };
162 
163 template <class UIntType>
164 struct tinymt_engine_status<UIntType, 32, 0, 0, 0>
165  : tinymt_engine_param<UIntType> {
166  using result_type = UIntType;
167  std::array<result_type, 4> status;
168  struct is_dynamic : std::true_type {};
169 };
170 
171 template <class UIntType1, class UIntType2, std::size_t WordSize,
172  std::uintmax_t Mat11, std::uintmax_t Mat12, std::uintmax_t Mat21,
173  std::uintmax_t Mat22, std::uintmax_t TMat1, std::uintmax_t TMat2>
174 inline bool operator==(
177  return a.mat1 == b.mat1 && a.mat2 == b.mat2 && a.tmat == b.tmat &&
178  a.status == b.status;
179 }
180 
181 template <class UIntType1, class UIntType2, std::size_t WordSize,
182  std::uintmax_t Mat11, std::uintmax_t Mat12, std::uintmax_t Mat21,
183  std::uintmax_t Mat22, std::uintmax_t TMat1, std::uintmax_t TMat2>
184 inline bool operator!=(
187  return !(a == b);
188 }
189 
190 template <class CharT, class Traits, class UIntType, std::size_t WordSize,
191  std::uintmax_t Mat1, std::uintmax_t Mat2, std::uintmax_t TMat>
192 inline std::basic_ostream<CharT, Traits>& operator<<(
193  std::basic_ostream<CharT, Traits>& os,
195  using status_type =
197 
198  bool first = true;
199  for (const auto& x : s.status) {
200  if (first) {
201  first = false;
202  } else {
203  os << ' ';
204  }
205  os << x;
206  }
207 
208  if (status_type::is_dynamic::value) {
209  os << ' ' << s.mat1;
210  os << ' ' << s.mat2;
211  os << ' ' << s.tmat;
212  }
213 
214  return os;
215 }
216 
217 template <
218  class CharT, class Traits, class UIntType, std::size_t WordSize,
219  std::uintmax_t Mat1, std::uintmax_t Mat2, std::uintmax_t TMat,
220  TINYMT_CPP_ENABLE_WHEN(!tinymt_engine_status<UIntType, WordSize, Mat1, Mat2,
221  TMat>::is_dynamic::value)>
222 inline std::basic_istream<CharT, Traits>& operator>>(
223  std::basic_istream<CharT, Traits>& is,
225  for (auto& x : s.status) {
226  is >> x >> std::ws;
227  }
228  return is;
229 }
230 
231 template <
232  class CharT, class Traits, class UIntType, std::size_t WordSize,
233  std::uintmax_t Mat1, std::uintmax_t Mat2, std::uintmax_t TMat,
234  TINYMT_CPP_ENABLE_WHEN(tinymt_engine_status<UIntType, WordSize, Mat1, Mat2,
235  TMat>::is_dynamic::value)>
236 inline std::basic_istream<CharT, Traits>& operator>>(
237  std::basic_istream<CharT, Traits>& is,
239  for (auto& x : s.status) {
240  is >> x >> std::ws;
241  }
242  is >> s.mat1 >> std::ws;
243  is >> s.mat2 >> std::ws;
244  is >> s.tmat >> std::ws;
245  return is;
246 }
247 
251 template <class UIntType, std::size_t WordSize, std::uintmax_t Mat1,
252  std::uintmax_t Mat2, std::uintmax_t TMat, bool DoPeriodCertification>
254 
255 template <class UIntType, std::uintmax_t Mat1, std::uintmax_t Mat2,
256  std::uintmax_t TMat, bool DoPeriodCertification>
257 struct tinymt_engine_impl<UIntType, 32, Mat1, Mat2, TMat,
258  DoPeriodCertification> {
259  using result_type = UIntType;
260  using signed_result_type = typename std::make_signed<result_type>::type;
263 
264  static constexpr std::size_t state_size = 4;
265  static constexpr std::uintmax_t max = 0xffffffffU;
266 
267  static constexpr std::size_t sh0 = 1;
268  static constexpr std::size_t sh1 = 10;
269  static constexpr std::size_t sh8 = 8;
270 
271  static constexpr result_type word_mask = static_cast<result_type>(max);
272  static constexpr result_type mask32 = word_mask;
273  static constexpr result_type mask = 0x7fffffffU;
274 
276  // In theory, this may happen but I don't know any example, so it is too
277  // difficult to cover these lines.
278 
279  // LCOV_EXCL_START
280  if ((s.status[0] & mask) == 0 && s.status[1] == 0 && s.status[2] == 0 &&
281  s.status[3] == 0) {
282  s.status[0] = 'T';
283  s.status[1] = 'I';
284  s.status[2] = 'N';
285  s.status[3] = 'Y';
286  }
287  // LCOV_EXCL_STOP
288  }
289 
290  static void init(status_type& s, result_type seed) {
291  const unsigned int MIN_LOOP = 8;
292  const unsigned int PRE_LOOP = 8;
293 
294  // Assume that mat1, mat2, tmat have been suitably initialized.
295 
296  s.status[0] = seed & mask32;
297  s.status[1] = s.mat1;
298  s.status[2] = s.mat2;
299  s.status[3] = s.tmat;
300 
301  // See Knuth TAOCP Vol2. 3rd Ed. p.106 for the multiplier.
302 
303  for (unsigned int i = 1; i < MIN_LOOP; i++) {
304  s.status[i & 3] ^= i + 1812433253 * (s.status[(i - 1) & 3] ^
305  (s.status[(i - 1) & 3] >> 30));
306  s.status[i & 3] &= mask32;
307  }
308 
309  if (DoPeriodCertification) {
310  period_certification(s);
311  }
312 
313  for (unsigned int i = 0; i < PRE_LOOP; i++) {
314  next_state(s);
315  }
316  }
317 
318  template <TINYMT_CPP_ENABLE_WHEN(!is_twos_complement<result_type>::value)>
319  static void next_state(status_type& s) {
320  result_type x = (s.status[0] & mask) ^ s.status[1] ^ s.status[2];
321  result_type y = s.status[3];
322  x ^= (x << sh0) & mask32;
323  y ^= (y >> sh0) ^ x;
324  s.status[0] = s.status[1];
325  s.status[1] = s.status[2];
326  s.status[2] = (x ^ (y << sh1)) & mask32;
327  s.status[3] = y;
328  if (y & 1) {
329  s.status[1] ^= s.mat1;
330  s.status[2] ^= s.mat2;
331  }
332  }
333 
334  template <TINYMT_CPP_ENABLE_WHEN(is_twos_complement<result_type>::value)>
335  static void next_state(status_type& s) {
336  result_type x = (s.status[0] & mask) ^ s.status[1] ^ s.status[2];
337  result_type y = s.status[3];
338  x ^= (x << sh0) & mask32;
339  y ^= (y >> sh0) ^ x;
340  s.status[0] = s.status[1];
341  s.status[1] = s.status[2];
342  s.status[2] = (x ^ (y << sh1)) & mask32;
343  s.status[3] = y;
344  // NOTE: the conditional branch in the portable version can be removed in
345  // the following way using negation in two's complement representation.
346  auto ymask =
347  static_cast<result_type>(-static_cast<signed_result_type>(y & 1));
348  s.status[1] ^= ymask & s.mat1;
349  s.status[2] ^= ymask & s.mat2;
350  }
351 
352  template <TINYMT_CPP_ENABLE_WHEN(!is_twos_complement<result_type>::value)>
353  static result_type temper(const status_type& s) {
354  result_type t0 = s.status[3];
355  result_type t1 = s.status[0] + (s.status[2] >> sh8);
356  t0 ^= t1;
357  if (t1 & 1) {
358  t0 ^= s.tmat;
359  }
360  return t0 & mask32;
361  }
362 
363  template <TINYMT_CPP_ENABLE_WHEN(is_twos_complement<result_type>::value)>
364  static result_type temper(const status_type& s) {
365  result_type t0 = s.status[3];
366  result_type t1 = s.status[0] + (s.status[2] >> sh8);
367  t0 ^= t1;
368  // NOTE: the conditional branch in the portable version can be removed in
369  // the following way using negation in two's complement representation.
370  auto t1mask =
371  static_cast<result_type>(-static_cast<signed_result_type>(t1 & 1));
372  t0 ^= t1mask & s.tmat;
373  return t0 & mask32;
374  }
375 };
376 
377 } // namespace detail
378 
394 template <class UIntType, std::size_t WordSize, UIntType Mat1, UIntType Mat2,
395  UIntType TMat, bool DoPeriodCertification = true>
397  static_assert(std::is_integral<UIntType>::value &&
398  std::is_unsigned<UIntType>::value,
399  "result_type must be an unsigned integral type");
400  static_assert(WordSize == 32, "word_size must be 32");
401 
402  using impl = detail::tinymt_engine_impl<UIntType, WordSize, Mat1, Mat2, TMat,
403  DoPeriodCertification>;
404  using status_type =
406 
407  static_assert(std::numeric_limits<UIntType>::max() >= impl::max,
408  "size of result_type must be lager than word_size");
409  static_assert(Mat1 <= impl::max, "Mat1 must be < 2^word_size");
410  static_assert(Mat2 <= impl::max, "Mat2 must be < 2^word_size");
411  static_assert(TMat <= impl::max, "TMat must be < 2^word_size");
412 
413  status_type s_;
414 
415  public:
419  using result_type = UIntType;
420 
424  using param_type = typename impl::param_type;
425 
429  static constexpr std::size_t word_size = WordSize;
430 
434  static constexpr std::size_t state_size = impl::state_size;
435 
439  static constexpr result_type default_seed = 1;
440 
446  template <TINYMT_CPP_ENABLE_WHEN(!status_type::is_dynamic::value)>
447  explicit tinymt_engine(result_type seed = default_seed) {
448  impl::init(s_, seed);
449  }
450 
457  template <TINYMT_CPP_ENABLE_WHEN(status_type::is_dynamic::value)>
458  explicit tinymt_engine(const param_type& param,
459  result_type seed = default_seed) {
460  s_.mat1 = param.mat1 & impl::word_mask;
461  s_.mat2 = param.mat2 & impl::word_mask;
462  s_.tmat = param.tmat & impl::word_mask;
463  impl::init(s_, seed);
464  }
465 
471  void seed(result_type value = default_seed) { impl::init(s_, value); }
472 
478  // Note: the use of `unsigned long long` is intentional, following the
479  // standard library and the Boost library.
480  void discard(unsigned long long z) { // NOLINT
481  for (unsigned long long i = 0; i < z; i++) { // NOLINT
482  impl::next_state(s_);
483  }
484  }
485 
491  static constexpr result_type min() { return 0; }
492 
498  static constexpr result_type max() { return impl::max; }
499 
506  impl::next_state(s_);
507  return impl::temper(s_);
508  }
509 
518  friend bool operator==(const tinymt_engine& a, const tinymt_engine& b) {
519  return a.s_ == b.s_;
520  }
521 
530  friend bool operator!=(const tinymt_engine& a, const tinymt_engine& b) {
531  return a.s_ != b.s_;
532  }
533 
541  template <class CharT, class Traits>
542  friend std::basic_ostream<CharT, Traits>& operator<<(
543  std::basic_ostream<CharT, Traits>& os, const tinymt_engine& e) {
544  return os << e.s_;
545  }
546 
554  template <class CharT, class Traits>
555  friend std::basic_istream<CharT, Traits>& operator>>(
556  std::basic_istream<CharT, Traits>& is, tinymt_engine& e) {
557  return is >> e.s_;
558  }
559 };
560 
564 using tinymt32 =
568 
573 
574 } // namespace tinymt
575 
576 #endif // TINYMT_TINYMT_H
typename impl::param_type param_type
Type of the generator parameter set.
Definition: tinymt.h:424
typename std::make_signed< result_type >::type signed_result_type
Definition: tinymt.h:260
tinymt_engine(result_type seed=default_seed)
Constructs the engine (non-DC mode).
Definition: tinymt.h:447
static constexpr result_type tmat
Definition: tinymt.h:159
Generator&#39;s parameter set.
Definition: tinymt.h:139
std::array< result_type, 4 > status
Definition: tinymt.h:167
Generator&#39;s state and parameter set.
Definition: tinymt.h:150
bool operator!=(const tinymt_engine_status< UIntType1, WordSize, Mat11, Mat21, TMat1 > &a, const tinymt_engine_status< UIntType2, WordSize, Mat12, Mat22, TMat2 > &b)
Definition: tinymt.h:184
friend std::basic_istream< CharT, Traits > & operator>>(std::basic_istream< CharT, Traits > &is, tinymt_engine &e)
Deserializes the state of the given engine from a stream.
Definition: tinymt.h:555
constexpr uint_least32_t tinymt32_default_param_mat2
Default parameter mat2 of TinyMT32 specified in RFC 8682.
Definition: tinymt.h:93
result_type operator()()
Returns the next pseudo-random number.
Definition: tinymt.h:505
friend std::basic_ostream< CharT, Traits > & operator<<(std::basic_ostream< CharT, Traits > &os, const tinymt_engine &e)
Serializes the state of the given engine into a stream.
Definition: tinymt.h:542
Core implementation of the TinyMT algorithms.
Definition: tinymt.h:253
UIntType mat2
Definition: tinymt.h:141
tinymt_engine(const param_type &param, result_type seed=default_seed)
Constructs the engine (DC mode).
Definition: tinymt.h:458
bool operator==(const tinymt_engine_status< UIntType1, WordSize, Mat11, Mat21, TMat1 > &a, const tinymt_engine_status< UIntType2, WordSize, Mat12, Mat22, TMat2 > &b)
Definition: tinymt.h:174
friend bool operator!=(const tinymt_engine &a, const tinymt_engine &b)
Compares two engines.
Definition: tinymt.h:530
void seed(result_type value=default_seed)
Reinitializes the engine.
Definition: tinymt.h:471
std::array< result_type, 4 > status
Definition: tinymt.h:156
std::basic_istream< CharT, Traits > & operator>>(std::basic_istream< CharT, Traits > &is, tinymt_engine_status< UIntType, WordSize, Mat1, Mat2, TMat > &s)
Definition: tinymt.h:222
UIntType mat1
Definition: tinymt.h:140
static constexpr result_type min()
Returns the smallest possible value in the output range.
Definition: tinymt.h:491
static constexpr result_type mat1
Definition: tinymt.h:157
friend bool operator==(const tinymt_engine &a, const tinymt_engine &b)
Compares two engines.
Definition: tinymt.h:518
constexpr uint_least32_t tinymt32_default_param_mat1
Default parameter mat1 of TinyMT32 specified in RFC 8682.
Definition: tinymt.h:88
static constexpr result_type mat2
Definition: tinymt.h:158
void discard(unsigned long long z)
Advances the state of the engine by the given amount.
Definition: tinymt.h:480
static result_type temper(const status_type &s)
Definition: tinymt.h:353
std::basic_ostream< CharT, Traits > & operator<<(std::basic_ostream< CharT, Traits > &os, const tinymt_engine_status< UIntType, WordSize, Mat1, Mat2, TMat > &s)
Definition: tinymt.h:192
Checks whether the given integral type T (or its signed type) uses 2&#39;s complement for the signed inte...
Definition: tinymt.h:119
#define TINYMT_CPP_ENABLE_WHEN(...)
Macro to enable/disable function via SFINAE.
Definition: tinymt.h:67
constexpr uint_least32_t tinymt32_default_param_tmat
Default parameter tmat of TinyMT32 specified in RFC 8682.
Definition: tinymt.h:98
static void init(status_type &s, result_type seed)
Definition: tinymt.h:290
static constexpr result_type max()
Returns the largest possible value in the output range.
Definition: tinymt.h:498
Pseudo-random number generator engine based on the TinyMT algorithms.
Definition: tinymt.h:396
UIntType tmat
Definition: tinymt.h:142
Namespace for classes that implement the TinyMT algorithms.
Definition: tinymt.h:77
UIntType result_type
Integral type generated by the engine.
Definition: tinymt.h:419