Add more complex mixing of random seed.

sdk/lib/_internal/lib/math_patch.dart

Index: sdk/lib/_internal/lib/math_patch.dart
diff --git a/sdk/lib/_internal/lib/math_patch.dart b/sdk/lib/_internal/lib/math_patch.dart
index e3aabe3d4265451d9d114742159a247e6342fe9e..3991e6368eb452884839186f5b6a01a1d3bee5a5 100644
--- a/sdk/lib/_internal/lib/math_patch.dart
+++ b/sdk/lib/_internal/lib/math_patch.dart
@@ -80,23 +80,82 @@ class _Random implements Random {
   static const int _MASK32 = 0xFFFFFFFF;
 
   // State comprised of two unsigned 32 bit integers.
-  int _lo;
-  int _hi;
+  int _lo = 0;
+  int _hi = 0;
 
   // Implements:
+  //   uint64_t hash = 0;
   //   do {
-  //     seed = (seed + 0x5A17) & _Random._MASK_64;
-  //   } while (seed == 0);
-  //   _lo = seed & _MASK_32;
-  //   _hi = seed >> 32;
+  //      hash = hash * 1037 ^ mix64((uint64_t)seed);
+  //      seed >>= 64;
+  //   } while (seed != 0 && seed != -1);  // Limits for pos/neg seed.
+  //   if (hash == 0) {
+  //     hash = 0x5A17;
+  //   }
+  //   _lo = hash & _MASK_32;
+  //   _hi = hash >> 32;
   // and then does four _nextState calls to shuffle bits around.
   _Random(int seed) {
-    // Works the same as the VM version for positive integers up to 2^53.
-    // For bigints, the VM always uses zero as seed. That is really a bug, and
-    // we don't simulate that.
-    seed += 0x5A17;
-    _lo = seed & _MASK32;
-    _hi = (seed - _lo) ~/ _POW2_32;
+    // Works the same as the VM version for positive integers up to 2^64.
+    var empty_seed = 0;

[floitsch, 2014/02/06 15:39:48]

type is mising.

[Lasse Reichstein Nielsen, 2014/02/07 08:38:54]

Done.

+    if (seed < 0) {
+      empty_seed = -1;
+    }
+    do {
+      var low = (seed & _MASK32) >> 0;

[floitsch, 2014/02/06 15:39:48]

What's the ">> 0" for?

[floitsch, 2014/02/06 15:39:48]

type is missing.

[Lasse Reichstein Nielsen, 2014/02/07 08:38:54]

Convert to uint32_t. Any bitwise noop would do.
I did this in JS first, to ensure that it worked, and converted the JS >>> to
Dart >>.

[Lasse Reichstein Nielsen, 2014/02/07 08:41:11]

Changed all ">> 0" to "&& _MASK32".
Won't assume that bit-ops generate a uint64 (so the code should work if run on
the dart VM too).

+      seed = (seed - low) ~/ _POW2_32;
+      var high = (seed & _MASK32) >> 0;
+      seed = (seed - high) ~/ _POW2_32;
+
+      // Thomas Wang's 64-bit mix function.
+      // http://www.concentric.net/~Ttwang/tech/inthash.htm
+      // via. http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm
+
+      // key = ~key + (key << 21);
+      var tmplow = (low << 21);
+      var tmphigh = ((high << 21) | (low >> 11));
+      tmplow = (~low) + tmplow;

[floitsch, 2014/02/06 15:39:48]

~low will always be positive.

[Lasse Reichstein Nielsen, 2014/02/07 08:38:54]

Which is fine. It's simulating ~ on a uint64.

+      low = tmplow >> 0;

[floitsch, 2014/02/06 15:39:48]

why shift?

+      high = (~high + tmphigh + ((tmplow - low) ~/ 0x100000000)) >> 0;

[floitsch, 2014/02/06 15:39:48]

why the shift?
~high will never be negative.

[Lasse Reichstein Nielsen, 2014/02/07 08:38:54]

It's may be bigger than 32 bits. This converts to uint32.

+      // key = key ^ (key >> 24).
+      tmphigh = high >> 24;
+      tmplow = (low >> 24) | (high << 8);
+      low = (low ^ tmplow);
+      high = (high ^ tmphigh);
+      // key = key * 265
+      tmplow = low * 265;
+      low = tmplow >> 0;

[floitsch, 2014/02/06 15:39:48]

why shift?

[Lasse Reichstein Nielsen, 2014/02/07 08:38:54]

AS above.

+      high = (high * 265 + (tmplow - low) ~/ 0x100000000) >> 0;

[floitsch, 2014/02/06 15:39:48]

unnecessary shift.

[Lasse Reichstein Nielsen, 2014/02/07 08:38:54]

It makes the value an uint32.
It might not be necessary since all this "high" is used for later is shift
operations. The compiler should be able to see that if it makes a difference.

+      // key = key ^ (key >> 14);
+      tmphigh = high >> 14;
+      tmplow = (low >> 14) | (high << 18);
+      low = (low ^ tmplow);
+      high = (high ^ tmphigh);
+      // key = key * 21
+      tmplow = low * 21;
+      low = tmplow >> 0;

[floitsch, 2014/02/06 15:39:48]

shift.

+      high = (high * 21 + (tmplow - low) ~/ 0x100000000) >> 0;

[floitsch, 2014/02/06 15:39:48]

shift.

+      // key = key ^ (key >> 28).
+      tmphigh = high >> 28;
+      tmplow = ((low >> 28) | (high << 4));
+      low = (low ^ tmplow);
+      high = (high ^ tmphigh);
+      // key = key + (key << 31);
+      tmplow = (low << 31);
+      tmphigh = ((high << 31) | (low >> 1));
+      tmplow += low;
+      low = tmplow >> 0;
+      high = (high + tmphigh + (tmplow - low) ~/ 0x100000000) >> 0;
+      // Mix end.
+
+      // seed = seed * 1037 ^ key;
+      tmplow = _lo * 1037;
+      _lo = tmplow >> 0;
+      _hi = (_hi * 1037 + (tmplow - _lo) ~/ 0x100000000) >> 0;
+      _lo ^= low;
+      _hi ^= high;
+    } while (seed != empty_seed);
+
     if (_hi == 0 && _lo == 0) {
       _lo = 0x5A17;
     }