TinyMT32 Pseudo Random Number Generator (PRNG)
draft-roca-tsvwg-tinymt32-00

Document shepherd changed to Susan Haresquot;, ACM 11th SIGPLAN Erlang Workshop (Erlang'12),
    *    September, 2012.
    */
   const uint32_t  TINYMT32_MAT1_PARAM = UINT32_C(0x8f7011ee);
   const uint32_t  TINYMT32_MAT2_PARAM = UINT32_C(0xfc78ff1f);
   const uint32_t  TINYMT32_TMAT_PARAM = UINT32_C(0x3793fdff);

   /**
    * This function initializes the internal state array with a
    * 32-bit unsigned integer seed.
    * @param s     pointer to tinymt internal state.
    * @param seed  a 32-bit unsigned integer used as a seed.
    */
   void tinymt32_init (tinymt32_t * s, uint32_t seed)
   {
       const uint32_t    MIN_LOOP = 8;
       const uint32_t    PRE_LOOP = 8;
       s->status[0] = seed;
       s->status[1] = s->mat1 = TINYMT32_MAT1_PARAM;
       s->status[2] = s->mat2 = TINYMT32_MAT2_PARAM;
       s->status[3] = s->tmat = TINYMT32_TMAT_PARAM;
       for (int i = 1; i < MIN_LOOP; i++) {
           s->status[i & 3] ^= i + UINT32_C(1812433253)
               * (s->status[(i - 1) & 3]
                  ^ (s->status[(i - 1) & 3] >> 30));
       }
       /*
        * NB: the parameter set of this specification warrants
        * that none of the possible 2^^32 seeds leads to an
        * all-zero 127-bit internal state. Therefore, the
        * period_certification() function of the original
        * TinyMT32 source code has been safely removed. If
        * another parameter set is used, this function will
        * have to be re-introduced here.
        */
       for (int i = 0; i < PRE_LOOP; i++) {
           tinymt32_next_state(s);
       }
   }

   /**

Saito, et al.            Expires August 15, 2019                [Page 5]
Internet-Draft                TinyMT32 PRNG                February 2019

    * This function outputs a 32-bit unsigned integer from
    * the internal state.
    * @param s     pointer to tinymt internal state.
    * @return      32-bit unsigned integer r (0 <= r < 2^32).
    */
   uint32_t tinymt32_generate_uint32 (tinymt32_t * s)
   {
       tinymt32_next_state(s);
       return tinymt32_temper(s);
   }

   /**
    * Internal tinymt32 constants and functions.
    * Users should not call these functions directly.
    */
   const uint32_t  TINYMT32_SH0 = 1;
   const uint32_t  TINYMT32_SH1 = 10;
   const uint32_t  TINYMT32_SH8 = 8;
   const uint32_t  TINYMT32_MASK = UINT32_C(0x7fffffff);

   /**
    * This function changes the internal state of tinymt32.
    * @param s     pointer to tinymt internal state.
    */
   static void tinymt32_next_state (tinymt32_t * s)
   {
       uint32_t x;
       uint32_t y;

       y = s->status[3];
       x = (s->status[0] & TINYMT32_MASK)
           ^ s->status[1]
           ^ s->status[2];
       x ^= (x << TINYMT32_SH0);
       y ^= (y >> TINYMT32_SH0) ^ x;
       s->status[0] = s->status[1];
       s->status[1] = s->status[2];
       s->status[2] = x ^ (y << TINYMT32_SH1);
       s->status[3] = y;
       s->status[1] ^= -((int32_t)(y & 1)) & s->mat1;
       s->status[2] ^= -((int32_t)(y & 1)) & s->mat2;
   }

   /**
    * This function outputs a 32-bit unsigned integer from
    * the internal state.
    * @param s     pointer to tinymt internal state.
    * @return      32-bit unsigned pseudo-random number.

Saito, et al.            Expires August 15, 2019                [Page 6]
Internet-Draft                TinyMT32 PRNG                February 2019

    */
   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;
       return t0;
   }
   <CODE ENDS>

                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
   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.

Saito, et al.            Expires August 15, 2019                [Page 7]
Internet-Draft                TinyMT32 PRNG                February 2019

   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
   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)
   or a 8-bit microcontroller (Arduino ATMEGA2560), both of them running
   RIOT.

   This specification only outputs 32-bit unsigned pseudo-random numbers
   and does not try to map this output to a smaller integer range (e.g.,
   between 10 and 49 inclusive).  If a specific use-case needs such a
   mapping, it will have to provide its own function.  In that case, if
   PRNG determinism is also required, the use of floating point (single
   or double precision) to perform this mapping should probably be
   avoided, these calculations leading potentially to different rounding
   errors across different target platforms.  Great care should also be
   put on not introducing biases in the randomness of the mapped output
   (it may be the case with some mapping algorithms) incompatible with
   the use-case requirements.  The details of how to perform such a
   mapping are out-of-scope of this document.

4.  Security Considerations

   The authors do not believe the present specification generates
   specific security risks per se.

5.  IANA Considerations

   This document does not require any IANA action.

Saito, et al.            Expires August 15, 2019                [Page 8]
Internet-Draft                TinyMT32 PRNG                February 2019

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 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 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,
              <https://www.rfc-editor.org/info/rfc2119>.

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <https://www.rfc-editor.org/info/rfc8174>.

7.2.  Informative References

   [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),
              September 14, 2012, Copenhagen, Denmark, DOI:
              http://dx.doi.org/10.1145/2364489.2364504, September 2012.

   [RFC5170]  Roca, V., Neumann, C., and D. Furodet, "Low Density Parity
              Check (LDPC) Staircase and Triangle Forward Error
              Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170,
              June 2008, <https://www.rfc-editor.org/info/rfc5170>.

Saito, et al.            Expires August 15, 2019                [Page 9]
Internet-Draft                TinyMT32 PRNG                February 2019

   [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, <https://tools.ietf.org/html/
              draft-ietf-tsvwg-rlc-fec-scheme>.

Authors' Addresses

   Mutsuo Saito
   Hiroshima University
   Japan

   EMail: saito@math.sci.hiroshima-u.ac.jp

   Makoto Matsumoto
   Hiroshima University
   Japan

   EMail: m-mat@math.sci.hiroshima-u.ac.jp

   Vincent Roca
   INRIA
   Univ. Grenoble Alpes
   France

   EMail: vincent.roca@inria.fr

   Emmanuel Baccelli
   INRIA
   France

   EMail: emmanuel.baccelli@inria.fr

Saito, et al.            Expires August 15, 2019               [Page 10]