[libc++] Use correct rand.eng.mers all-zeroes seed sequence fallback

[hubert.reinterpretcast]

Summary

When a seed sequence would lead to having no non-zero significant bits in the initial state of a mersenne_twister_engine, the fallback is to flip the most significant bit of the first value that appears in the textual representation of the initial state.

rand.eng.mers describes this as setting the value to be 2 to the power of one less than w; the previous value encoded in the implementation, namely one less than "2 to the power of w", is replaced by the correct value in this patch.

[mclow.lists]

Is this test that's being added libc++ specific, or would it apply to other implementations as well?

test/libcxx/numerics/rand/rand.eng.mers/cnstr_sseq_all_zero.pass.cpp

18 ↗

(On Diff #160687)

Please add a comment here about what's being tested, because when I look at this a year from now, I won't know what's going on.

Something like:
// Finally, if the most significant w − r bits of X−n are zero, and if each of the other resulting Xi is 0, changes X−n to 2w−1.

47 ↗

(On Diff #160687)

Need a line break before void

[hubert.reinterpretcast]

In D50736#1200761, @mclow.lists wrote:

Is this test that's being added libc++ specific, or would it apply to other implementations as well?

The test can apply to other implementations as well (although I am not sure how the initializer_list include behaves under C++03 on other implementations). Is there some other place to put such tests?

test/libcxx/numerics/rand/rand.eng.mers/cnstr_sseq_all_zero.pass.cpp

47 ↗

(On Diff #160687)

I have no objection to adding a line break, but I would like to clarify that this line came straight out of a recent build of clang-format with --style=llvm. I would like to know whether there is something else here that I should be doing with clang-format, including if it is deemed that clang-format does not do the right thing here.

[hubert.reinterpretcast]

In D50736#1200774, @hubert.reinterpretcast wrote:

In D50736#1200761, @mclow.lists wrote:

Is this test that's being added libc++ specific, or would it apply to other implementations as well?

The test can apply to other implementations as well (although I am not sure how the initializer_list include behaves under C++03 on other implementations). Is there some other place to put such tests?

It seems that test/std/numerics/rand/rand.eng/rand.eng.mers/ may be the place to add the test. I am looking into it.

test/libcxx/numerics/rand/rand.eng.mers/cnstr_sseq_all_zero.pass.cpp

18 ↗

(On Diff #160687)

I will add a comment to this effect. In an effort to be clear in the formatting, I will use the LaTeX snippet for the text.

[hubert.reinterpretcast]

Address review comments by Marshall

Add a line break after the template-head. Add a comment with the requested quote from the Standard. Move test from the test/libcxx/ tree to the test/std/ tree, and guard against inclusion of <initializer_list> under C++03.

[mclow.lists]

Thanks for doing this.
This looks good to me; but I want to play with it a bit before committing. I'll do that tonight.

[mclow.lists]

This LGTM. Do you want me to commit it for you?

[hubert.reinterpretcast]

I can commit sometime today; thanks.

• HT

include/random

mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
     const result_type __mask = __r == _Dt ? result_type(~0) :
                                        (result_type(1) << __r) - result_type(1);
     __i_ = 0;
     if ((__x_[0] & ~__mask) == 0)
     {
         for (size_t __i = 1; __i < __n; ++__i)
             if (__x_[__i] != 0)
                 return;
-        __x_[0] = _Max;
+        __x_[0] = result_type(1) << (__w - 1);
     }
 }
 
 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 template<class _Sseq>
 void
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
     const result_type __mask = __r == _Dt ? result_type(~0) :
                                        (result_type(1) << __r) - result_type(1);
     __i_ = 0;
     if ((__x_[0] & ~__mask) == 0)
     {
         for (size_t __i = 1; __i < __n; ++__i)
             if (__x_[__i] != 0)
                 return;
-        __x_[0] = _Max;
+        __x_[0] = result_type(1) << (__w - 1);
     }
 }
 
 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 _UIntType
 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,

test/std/numerics/rand/rand.eng/rand.eng.mers/ctor_sseq_all_zero.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <random>
+
+// template <class UIntType, size_t w, size_t n, size_t m, size_t r,
+//           UIntType a, size_t u, UIntType d, size_t s,
+//           UIntType b, size_t t,
+//           UIntType c, size_t l, UIntType f>
+// class mersenne_twister_engine;
+
+// template <class Sseq> explicit mersenne_twister_engine(Sseq &q);
+//
+//     [ ... ] Finally, if the most significant $w-r$ bits of $X_{-n}$ are zero,
+//     and if each of the other resulting $X_i$ is $0$, changes $X_{-n}$ to
+//     $ 2^{w-1} $.
+
+#include <random>
+
+#include <algorithm>
+#include <cassert>
+#include <cstddef>
+#if TEST_STD_VER >= 11
+#include <initializer_list>
+#endif
+
+struct all_zero_seed_seq {
+  typedef unsigned int result_type;
+
+  all_zero_seed_seq() {}
+
+  template <typename InputIterator>
+  all_zero_seed_seq(InputIterator, InputIterator) {}
+#if TEST_STD_VER >= 11
+  all_zero_seed_seq(std::initializer_list<result_type>) {}
+#endif
+
+  template <typename RandomAccessIterator>
+  void generate(RandomAccessIterator rb, RandomAccessIterator re) {
+    std::fill(rb, re, 0u);
+  }
+
+  std::size_t size() const { return 0u; }
+  template <typename OutputIterator> void param(OutputIterator) const {}
+};
+
+template <typename result_type, std::size_t word_size>
+void test(void) {
+  const std::size_t state_size = 1u;
+  const std::size_t shift_size = 1u;
+  const std::size_t tempering_l = word_size;
+
+  all_zero_seed_seq q;
+  std::mersenne_twister_engine<result_type, word_size, state_size,
+                               shift_size,
+                               0u,
+                               0x0,
+                               0u, 0x0, 0u, 0x0, 0u, 0x0,
+                               tempering_l,
+                               0u>
+      e(q);
+
+  const result_type Xneg1 = result_type(1) << (word_size - 1);
+  const result_type Y = Xneg1;
+  const result_type X0 = Xneg1 ^ (Y >> 1);
+  assert(e() == X0);
+}
+
+int main() {
+  // Test for k == 1: word_size <= 32.
+  test<unsigned short, 3u>();
+
+  // Test for k == 2: (32 < word_size <= 64).
+  test<unsigned long long, 33u>();
+}