```
172 /**
173 * Tiny Mersenne Twister only 127 bit internal state.
174 * Derived from the reference implementation version 1.1 (2015/04/24)
175 * by Mutsuo Saito (Hiroshima University) and Makoto Matsumoto
176 * (Hiroshima University).
177 */
178 #include
```
180 /**
181 * tinymt32 internal state vector and parameters
182 */
183 typedef struct {
184 uint32_t status[4];
185 uint32_t mat1;
186 uint32_t mat2;
187 uint32_t tmat;
188 } tinymt32_t;
190 static void tinymt32_next_state (tinymt32_t* s);
191 static uint32_t tinymt32_temper (tinymt32_t* s);
193 /**
194 * Parameter set to use for this IETF specification. Don't change.
195 * This parameter set is the first entry of the precalculated
196 * parameter sets in file tinymt32dc/tinymt32dc.0.1048576.txt, by
197 * Kenji Rikitake, available at:
198 * https://github.com/jj1bdx/tinymtdc-longbatch/
199 * It is also the parameter set used:
200 * Rikitake, K., "TinyMT Pseudo Random Number Generator for
201 * Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12),
202 * September, 2012.
203 */
204 const uint32_t TINYMT32_MAT1_PARAM = UINT32_C(0x8f7011ee);
205 const uint32_t TINYMT32_MAT2_PARAM = UINT32_C(0xfc78ff1f);
206 const uint32_t TINYMT32_TMAT_PARAM = UINT32_C(0x3793fdff);
208 /**
209 * This function initializes the internal state array with a
210 * 32-bit unsigned integer seed.
211 * @param s pointer to tinymt internal state.
212 * @param seed a 32-bit unsigned integer used as a seed.
213 */
214 void tinymt32_init (tinymt32_t* s, uint32_t seed)
215 {
216 const uint32_t MIN_LOOP = 8;
217 const uint32_t PRE_LOOP = 8;
218 s->status[0] = seed;
219 s->status[1] = s->mat1 = TINYMT32_MAT1_PARAM;
220 s->status[2] = s->mat2 = TINYMT32_MAT2_PARAM;
221 s->status[3] = s->tmat = TINYMT32_TMAT_PARAM;
222 for (int i = 1; i < MIN_LOOP; i++) {
223 s->status[i & 3] ^= i + UINT32_C(1812433253)
224 * (s->status[(i - 1) & 3]
225 ^ (s->status[(i - 1) & 3] >> 30));
226 }
227 /*
228 * NB: the parameter set of this specification warrants
229 * that none of the possible 2^^32 seeds leads to an
230 * all-zero 127-bit internal state. Therefore, the
231 * period_certification() function of the original
232 * TinyMT32 source code has been safely removed. If
233 * another parameter set is used, this function will
234 * have to be re-introduced here.
235 */
236 for (int i = 0; i < PRE_LOOP; i++) {
237 tinymt32_next_state(s);
238 }
240 }
242 /**
243 * This function outputs a 32-bit unsigned integer from
244 * the internal state.
245 * @param s pointer to tinymt internal state.
246 * @return 32-bit unsigned integer r (0 <= r < 2^32).
247 */
248 uint32_t tinymt32_generate_uint32 (tinymt32_t* s)
249 {
250 tinymt32_next_state(s);
251 return tinymt32_temper(s);
252 }
254 /**
255 * Internal tinymt32 constants and functions.
256 * Users should not call these functions directly.
257 */
258 const uint32_t TINYMT32_SH0 = 1;
259 const uint32_t TINYMT32_SH1 = 10;
260 const uint32_t TINYMT32_SH8 = 8;
261 const uint32_t TINYMT32_MASK = UINT32_C(0x7fffffff);
263 /**
264 * This function changes the internal state of tinymt32.
265 * @param s pointer to tinymt internal state.
266 */
267 static void tinymt32_next_state (tinymt32_t* s)
268 {
269 uint32_t x;
270 uint32_t y;
272 y = s->status[3];
273 x = (s->status[0] & TINYMT32_MASK)
274 ^ s->status[1]
275 ^ s->status[2];
276 x ^= (x << TINYMT32_SH0);
277 y ^= (y >> TINYMT32_SH0) ^ x;
278 s->status[0] = s->status[1];
279 s->status[1] = s->status[2];
280 s->status[2] = x ^ (y << TINYMT32_SH1);
281 s->status[3] = y;
282 /*
283 * The if (y & 1) {...} block below replaces:
284 * s->status[1] ^= -((int32_t)(y & 1)) & s->mat1;
285 * s->status[2] ^= -((int32_t)(y & 1)) & s->mat2;
286 * The adopted code is equivalent to the original code
287 * but does not depend on the representation of negative
288 * integers by 2's complements. It is therefore more
289 * portable, but includes an if-branch which may slow
290 * down the generation speed.
291 */
292 if (y & 1) {
293 s->status[1] ^= s->mat1;
294 s->status[2] ^= s->mat2;
295 }
296 }
298 /**
299 * This function outputs a 32-bit unsigned integer from
300 * the internal state.
301 * @param s pointer to tinymt internal state.
302 * @return 32-bit unsigned pseudo-random number.
303 */
304 static uint32_t tinymt32_temper (tinymt32_t* s)
305 {
306 uint32_t t0, t1;
307 t0 = s->status[3];
308 t1 = s->status[0] + (s->status[2] >> TINYMT32_SH8);
309 t0 ^= t1;
310 /*
311 * The if (t1 & 1) {...} block below replaces:
312 * t0 ^= -((int32_t)(t1 & 1)) & s->tmat;
313 * The adopted code is equivalent to the original code
314 * but does not depend on the representation of negative
315 * integers by 2's complements. It is therefore more
316 * portable, but includes an if-branch which may slow
317 * down the generation speed.
318 */
319 if (t1 & 1) {
320 t0 ^= s->tmat;
321 }
322 return t0;
323 }
324 ```
326 Figure 1: TinyMT32 Reference Implementation
328 3.2. TinyMT32 Usage
330 This PRNG MUST first be initialized with the following function:
332 void tinymt32_init (tinymt32_t* s, uint32_t seed);
334 It takes as input a 32-bit unsigned integer used as a seed (note that
335 value 0 is permitted by TinyMT32). This function also takes as input
336 a pointer to an instance of a tinymt32_t structure that needs to be
337 allocated by the caller but left uninitialized. This structure will
338 then be updated by the various TinyMT32 functions in order to keep
339 the internal state of the PRNG. The use of this structure admits
340 several instances of this PRNG to be used in parallel, each of them
341 having its own instance of the structure.
343 Then, each time a new 32-bit pseudo-random unsigned integer between 0
344 and 2^32 - 1 inclusive is needed, the following function is used:
346 uint32_t tinymt32_generate_uint32 (tinymt32_t * s);
348 Of course, the tinymt32_t structure must be left unchanged by the
349 caller between successive calls to this function.
351 3.3. Specific Implementation Validation and Deterministic Behavior
353 PRNG determinism, for a given seed, can be a requirement (e.g., with
354 [RLC-ID]). Consequently, any implementation of the TinyMT32 PRNG in
355 line with this specification MUST have the same output as that
356 provided by the reference implementation of Figure 1. In order to
357 increase the compliancy confidence, this document proposes the
358 following criteria. Using a seed value of 1, the first 50 values
359 returned by tinymt32_generate_uint32(s) as 32-bit unsigned integers
360 are equal to values provided in Figure 2, to be read line by line.
361 Note that these values come from the tinymt/check32.out.txt file
362 provided by the PRNG authors to validate implementations of TinyMT32,
363 as part of the MersenneTwister-Lab/TinyMT Github repository.
365 2545341989 981918433 3715302833 2387538352 3591001365
366 3820442102 2114400566 2196103051 2783359912 764534509
367 643179475 1822416315 881558334 4207026366 3690273640
368 3240535687 2921447122 3984931427 4092394160 44209675
369 2188315343 2908663843 1834519336 3774670961 3019990707
370 4065554902 1239765502 4035716197 3412127188 552822483
371 161364450 353727785 140085994 149132008 2547770827
372 4064042525 4078297538 2057335507 622384752 2041665899
373 2193913817 1080849512 33160901 662956935 642999063
374 3384709977 1723175122 3866752252 521822317 2292524454
376 Figure 2: First 50 decimal values (to be read per line) returned by
377 tinymt32_generate_uint32(s) as 32-bit unsigned integers, with a seed
378 value of 1.
380 In particular, the deterministic behavior of the Figure 1 source code
381 has been checked across several platforms: high-end laptops running
382 64-bits Mac OSX and Linux/Ubuntu; a board featuring a 32-bits ARM
383 Cortex-A15 and running 32-bit Linux/Ubuntu; several embedded cards
384 featuring either an ARM Cortex-M0+, a Cortex-M3 or a Cortex-M4 32-bit
385 microcontroller, all of them running RIOT [Baccelli18]; two low-end
386 embedded cards featuring either a 16-bit microcontroller (TI MSP430)
387 or a 8-bit microcontroller (Arduino ATMEGA2560), both of them running
388 RIOT.
390 This specification only outputs 32-bit unsigned pseudo-random numbers
391 and does not try to map this output to a smaller integer range (e.g.,
392 between 10 and 49 inclusive). If a specific use-case needs such a
393 mapping, it will have to provide its own function. In that case, if
394 PRNG determinism is also required, the use of floating point (single
395 or double precision) to perform this mapping should probably be
396 avoided, these calculations leading potentially to different rounding
397 errors across different target platforms. Great care should also be
398 put on not introducing biases in the randomness of the mapped output
399 (it may be the case with some mapping algorithms) incompatible with
400 the use-case requirements. The details of how to perform such a
401 mapping are out-of-scope of this document.
403 4. Security Considerations
405 The authors do not believe the present specification generates
406 specific security risks per se. However, neither the TinyMT nor MT
407 PRNG are meant to be used for cryptographic applications.
409 5. IANA Considerations
411 This document does not require any IANA action.
413 6. Acknowledgments
415 The authors would like to thank Belkacem Teibi with whom we explored
416 TinyMT32 specificities when looking to an alternative to the Park-
417 Miller Linear Congruential PRNG. The authors would like to thank
418 Carl Wallace, Stewart Bryant, Greg Skinner, Mike Heard, the three
419 TSVWG chairs, Wesley Eddy, our shepherd, David Black and Gorry
420 Fairhurst, as well as Spencer Dawkins and Mirja Kuhlewind. Last but
421 not least, the authors are really grateful to the IESG members, in
422 particular Benjamin Kaduk, Eric Rescorla, Adam Roach, Roman Danyliw,
423 Barry Leiba, Martin Vigoureux, Eric Vyncke for their highly valuable
424 feedbacks that greatly contributed to improve this specification.
426 7. References
427 7.1. Normative References
429 [C99] "Programming languages - C: C99, correction 3:2007",
430 International Organization for Standardization, ISO/IEC
431 9899:1999/Cor 3:2007, November 2007.
433 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
434 Requirement Levels", BCP 14, RFC 2119,
435 DOI 10.17487/RFC2119, March 1997,
436
```.
438 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
439 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
440 May 2017, .
442 7.2. Informative References
444 [AdaptiveCrush]
445 Haramoto, H., "Automation of statistical tests on
446 randomness to obtain clearer conclusion", Monte Carlo and
447 Quasi-Monte Carlo Methods 2008,
448 DOI:10.1007/978-3-642-04107-5_26, November 2009,
449 .
452 [Baccelli18]
453 Baccelli, E., Gundogan, C., Hahm, O., Kietzmann, P.,
454 Lenders, M., Petersen, H., Schleiser, K., Schmidt, T., and
455 M. Wahlisch, "RIOT: An Open Source Operating System for
456 Low-End Embedded Devices in the IoT", IEEE Internet of
457 Things Journal (Volume 5, Issue 6), DOI:
458 10.1109/JIOT.2018.2815038, December 2018.
460 [KR12] Rikitake, K., "TinyMT Pseudo Random Number Generator for
461 Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12),
462 September 14, 2012, Copenhagen, Denmark, DOI:
463 http://dx.doi.org/10.1145/2364489.2364504, September 2012.
465 [MT98] Matsumoto, M. and T. Nishimura, "Mersenne Twister: A
466 623-dimensionally equidistributed uniform pseudorandom
467 number generator", ACM Transactions on Modeling and
468 Computer Simulation (TOMACS), Volume 8 Issue 1, Jan. 1998,
469 pp.3-30, January 1998, DOI:10.1145/272991.272995, January
470 1998.
472 [PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery,
473 "Numerical Recipies in C; Second Edition", Cambridge
474 University Press, ISBN: 0-521-43108-5, 1992.
476 [RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity
477 Check (LDPC) Staircase and Triangle Forward Error
478 Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170,
479 June 2008, .
481 [RLC-ID] Roca, V. and B. Teibi, "Sliding Window Random Linear Code
482 (RLC) Forward Erasure Correction (FEC) Scheme for
483 FECFRAME", Work in Progress, Transport Area Working Group
484 (TSVWG) draft-ietf-tsvwg-rlc-fec-scheme (Work in
485 Progress), February 2019, .
488 [TestU01] L'Ecuyer, P. and R. Simard, "TestU01: A C Library for
489 Empirical Testing of Random Number Generators", ACM
490 Transactions on Mathematical Software, Vol. 33, article
491 22, 2007, 2007,
492 .
494 [TinyMT-dev]
495 Saito, M. and M. Matsumoto, "Tiny Mersenne Twister
496 (TinyMT) github site",
497 .
499 [TinyMT-params]
500 Rikitake, K., "TinyMT pre-calculated parameter list github
501 site", .
503 [TinyMT-web]
504 Saito, M. and M. Matsumoto, "Tiny Mersenne Twister
505 (TinyMT) web site",
506 .
508 Authors' Addresses
510 Mutsuo Saito
511 Hiroshima University
512 Japan
514 EMail: saito@math.sci.hiroshima-u.ac.jp
516 Makoto Matsumoto
517 Hiroshima University
518 Japan
520 EMail: m-mat@math.sci.hiroshima-u.ac.jp
521 Vincent Roca
522 INRIA
523 Univ. Grenoble Alpes
524 France
526 EMail: vincent.roca@inria.fr
528 Emmanuel Baccelli
529 INRIA
530 France
532 EMail: emmanuel.baccelli@inria.fr