```
/**
* Tiny Mersenne Twister only 127 bit internal state.
* Derived from the reference implementation version 1.1 (2015/04/24)
* by Mutsuo Saito (Hiroshima University) and Makoto Matsumoto
* (Hiroshima University).
*/
#include
```
@@ -299,74 +300,87 @@
* the internal state.
* @param s pointer to tinymt internal state.
* @return 32-bit unsigned pseudo-random number.
*/
static uint32_t tinymt32_temper (tinymt32_t* s)
{
uint32_t t0, t1;
t0 = s->status[3];
t1 = s->status[0] + (s->status[2] >> TINYMT32_SH8);
t0 ^= t1;
- t0 ^= -((int32_t)(t1 & 1)) & s->tmat;
+ /*
+ * The if (t1 & 1) {...} block below replaces:
+ * t0 ^= -((int32_t)(t1 & 1)) & s->tmat;
+ * The adopted code is equivalent to the original code
+ * but does not depend on the representation of negative
+ * integers by 2's complements. It is therefore more
+ * portable, but includes an if-branch which may slow
+ * down the generation speed.
+ */
+ if (t1 & 1) {
+ t0 ^= s->tmat;
+ }
return t0;
}
```
Figure 1: TinyMT32 Reference Implementation
3.2. TinyMT32 Usage
This PRNG MUST first be initialized with the following function:
void tinymt32_init (tinymt32_t * s, uint32_t seed);
It takes as input a 32-bit unsigned integer used as a seed (note that
- value 0 is authorized by TinyMT32). This function also takes as
- input a pointer to an instance of a tinymt32_t structure that needs
- to be allocated by the caller but left uninitialized. This structure
- will then updated by the various TinyMT32 functions in order to keep
- the internal state of the PRNG. The use of this structure authorizes
+ value 0 is permitted by TinyMT32). This function also takes as input
+ a pointer to an instance of a tinymt32_t structure that needs to be
+ allocated by the caller but left uninitialized. This structure will
+ then be updated by the various TinyMT32 functions in order to keep
+ the internal state of the PRNG. The use of this structure admits
several instances of this PRNG to be used in parallel, each of them
having its own instance of the structure.
Then, each time a new 32-bit pseudo-random unsigned integer between 0
and 2^32 - 1 inclusive is needed, the following function is used:
uint32_t tinymt32_generate_uint32 (tinymt32_t * s);
Of course, the tinymt32_t structure must be left unchanged by the
caller between successive calls to this function.
3.3. Specific Implementation Validation and Deterministic Behavior
PRNG determinism, for a given seed, can be a requirement (e.g., with
[RLC-ID]). Consequently, any implementation of the TinyMT32 PRNG in
- line with this specification MUST comply with the following criteria.
- Using a seed value of 1, the first 50 values returned by
- tinymt32_generate_uint32(s) as 32-bit unsigned integers MUST be equal
- to values provided in Figure 2. Note that these values come from the
- tinymt/check32.out.txt file provided by the PRNG authors to validate
- implementations of TinyMT32, as part of the MersenneTwister-Lab/
- TinyMT Github repository.
+ line with this specification MUST have the same output as that
+ provided by the reference implementation of Figure 1. In order to
+ increase the compliancy confidence, this document proposes the
+ following criteria. Using a seed value of 1, the first 50 values
+ returned by tinymt32_generate_uint32(s) as 32-bit unsigned integers
+ are equal to values provided in Figure 2, to be read line by line.
+ Note that these values come from the tinymt/check32.out.txt file
+ provided by the PRNG authors to validate implementations of TinyMT32,
+ as part of the MersenneTwister-Lab/TinyMT Github repository.
2545341989 981918433 3715302833 2387538352 3591001365
3820442102 2114400566 2196103051 2783359912 764534509
643179475 1822416315 881558334 4207026366 3690273640
3240535687 2921447122 3984931427 4092394160 44209675
2188315343 2908663843 1834519336 3774670961 3019990707
4065554902 1239765502 4035716197 3412127188 552822483
161364450 353727785 140085994 149132008 2547770827
4064042525 4078297538 2057335507 622384752 2041665899
2193913817 1080849512 33160901 662956935 642999063
3384709977 1723175122 3866752252 521822317 2292524454
- Figure 2: First 50 decimal values returned by
+ Figure 2: First 50 decimal values (to be read per line) returned by
tinymt32_generate_uint32(s) as 32-bit unsigned integers, with a seed
value of 1.
In particular, the deterministic behavior of the Figure 1 source code
has been checked across several platforms: high-end laptops running
64-bits Mac OSX and Linux/Ubuntu; a board featuring a 32-bits ARM
Cortex-A15 and running 32-bit Linux/Ubuntu; several embedded cards
featuring either an ARM Cortex-M0+, a Cortex-M3 or a Cortex-M4 32-bit
microcontroller, all of them running RIOT [Baccelli18]; two low-end
embedded cards featuring either a 16-bit microcontroller (TI MSP430)
@@ -393,43 +407,52 @@
PRNG are meant to be used for cryptographic applications.
5. IANA Considerations
This document does not require any IANA action.
6. Acknowledgments
The authors would like to thank Belkacem Teibi with whom we explored
TinyMT32 specificities when looking to an alternative to the Park-
- Miler Linear Congruential PRNG. The authors would like to thank Carl
- Wallace, Stewart Bryant, Greg Skinner, the three TSVWG chairs, Wesley
- Eddy, our shepherd, David Black and Gorry Fairhurst, as well as
- Spencer Dawkins and Mirja Kuhlewind. Last but not least, the authors
- are really grateful to the IESG members, in particular Benjamin
- Kaduk, Eric Rescorla, and Adam Roach for their highly valuable
+ Miller Linear Congruential PRNG. The authors would like to thank
+ Carl Wallace, Stewart Bryant, Greg Skinner, Mike Heard, the three
+ TSVWG chairs, Wesley Eddy, our shepherd, David Black and Gorry
+ Fairhurst, as well as Spencer Dawkins and Mirja Kuhlewind. Last but
+ not least, the authors are really grateful to the IESG members, in
+ particular Benjamin Kaduk, Eric Rescorla, Adam Roach, Roman Danyliw,
+ Barry Leiba, Martin Vigoureux, Eric Vyncke for their highly valuable
feedbacks that greatly contributed to improve this specification.
7. References
7.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
```.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, .
7.2. Informative References
+ [AdaptiveCrush]
+ Haramoto, H., "Automation of statistical tests on
+ randomness to obtain clearer conclusion", Monte Carlo and
+ Quasi-Monte Carlo Methods 2008,
+ DOI:10.1007/978-3-642-04107-5_26, November 2009,
+ .
+
[Baccelli18]
Baccelli, E., Gundogan, C., Hahm, O., Kietzmann, P.,
Lenders, M., Petersen, H., Schleiser, K., Schmidt, T., and
M. Wahlisch, "RIOT: An Open Source Operating System for
Low-End Embedded Devices in the IoT", IEEE Internet of
Things Journal (Volume 5, Issue 6), DOI:
10.1109/JIOT.2018.2815038, December 2018.
[KR12] Rikitake, K., "TinyMT Pseudo Random Number Generator for
Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12),
@@ -452,20 +475,26 @@
Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170,
June 2008, .
[RLC-ID] Roca, V. and B. Teibi, "Sliding Window Random Linear Code
(RLC) Forward Erasure Correction (FEC) Scheme for
FECFRAME", Work in Progress, Transport Area Working Group
(TSVWG) draft-ietf-tsvwg-rlc-fec-scheme (Work in
Progress), February 2019, .
+ [TestU01] L'Ecuyer, P. and R. Simard, "TestU01: A C Library for
+ Empirical Testing of Random Number Generators", ACM
+ Transactions on Mathematical Software, Vol. 33, article
+ 22, 2007, 2007,
+ .
+
[TinyMT-dev]
Saito, M. and M. Matsumoto, "Tiny Mersenne Twister
(TinyMT) github site",
.
[TinyMT-params]
Rikitake, K., "TinyMT pre-calculated parameter list github
site", .
[TinyMT-web]