Add more complex mixing of random seed.

Add more complex mixing of random seed.

This changes the sequences generated by Random for a given seed,
since the internal state will not be the same as for the unmixed
seed.
It is consistent between VM and dart2js.

The provided integer seed is hashed as follows:
   uint64 hash = 0;
   while (seed > 0) {
      hash = hash * 1037 + mix64((int64)seed);
      seed >>= 64;
   }
where mix64 mixes the bits of a 64-bit value.
The hash is used to initialize the random generator's internal state.

R=floitsch@google.com, iposva@google.com

Committed: https://code.google.com/p/dart/source/detail?r=32412

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

LGTM with comments.

https://codereview.chromium.org/156533002/diff/1/runtime/lib/math.cc
File runtime/lib/math.cc (right):

https://codereview.chromium.org/156533002/diff/1/runtime/lib/math.cc#newcode118
runtime/lib/math.cc:118: n = (~n) + (n << 21);           // n = (n << 21) - n -
1;
Shouldn't these bit-optimizations be done by the compiler?

https://codereview.chromium.org/156533002/diff/1/runtime/lib/math.cc#newcode120
runtime/lib/math.cc:120: n = (n + (n << 3)) + (n << 8);  // n * 265
This can definitely be done by the compiler.

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
File sdk/lib/_internal/lib/math_patch.dart (right):

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:100: var empty_seed = 0;
type is mising.

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:105: var low = (seed & _MASK32) >> 0;
What's the ">> 0" for?

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:105: var low = (seed & _MASK32) >> 0;
type is missing.

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:117: tmplow = (~low) + tmplow;
~low will always be positive.

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:118: low = tmplow >> 0;
why shift?

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:119: high = (~high + tmphigh + ((tmplow -
low) ~/ 0x100000000)) >> 0;
why the shift?
~high will never be negative.

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:127: low = tmplow >> 0;
why shift?

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:128: high = (high * 265 + (tmplow - low)
~/ 0x100000000) >> 0;
unnecessary shift.

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:136: low = tmplow >> 0;
shift.

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:137: high = (high * 21 + (tmplow - low) ~/
0x100000000) >> 0;
shift.

[Ivan Posva, 2014-02-07 00:15:20]

LGTM -ip

https://codereview.chromium.org/156533002/diff/1/runtime/lib/math.cc
File runtime/lib/math.cc (right):

https://codereview.chromium.org/156533002/diff/1/runtime/lib/math.cc#newcode118
runtime/lib/math.cc:118: n = (~n) + (n << 21);           // n = (n << 21) - n -
1;
On 2014/02/06 15:39:48, floitsch wrote:
> Shouldn't these bit-optimizations be done by the compiler?

In my experience it does not hurt to do it by hand. Provided you do not make a
mistake.

https://codereview.chromium.org/156533002/diff/1/runtime/lib/math.cc#newcode120
runtime/lib/math.cc:120: n = (n + (n << 3)) + (n << 8);  // n * 265
On 2014/02/06 15:39:48, floitsch wrote:
> This can definitely be done by the compiler.

ditto

https://codereview.chromium.org/156533002/diff/1/runtime/lib/math.cc#newcode155
runtime/lib/math.cc:155: // Negate bits again (by xor with negatE_mask) when
extracted below,
negatE_mask -> negate_mask

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

https://codereview.chromium.org/156533002/diff/1/runtime/lib/math.cc
File runtime/lib/math.cc (right):

https://codereview.chromium.org/156533002/diff/1/runtime/lib/math.cc#newcode118
runtime/lib/math.cc:118: n = (~n) + (n << 21);           // n = (n << 21) - n -
1;
The multiplication is simpler than the shifts, so if the compiler does just as
good a job, we might as well use multilication. 
This line, on the other hand, is simpler with the bit-not, so I'll keep it.

https://codereview.chromium.org/156533002/diff/1/runtime/lib/math.cc#newcode120
runtime/lib/math.cc:120: n = (n + (n << 3)) + (n << 8);  // n * 265
I'll trust the original author's comment here and make it a multiplication.
Ditto for *21 below.

https://codereview.chromium.org/156533002/diff/1/runtime/lib/math.cc#newcode155
runtime/lib/math.cc:155: // Negate bits again (by xor with negatE_mask) when
extracted below,
Good catch

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
File sdk/lib/_internal/lib/math_patch.dart (right):

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:100: var empty_seed = 0;
On 2014/02/06 15:39:48, floitsch wrote:
> type is mising.

Done.

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:105: var low = (seed & _MASK32) >> 0;
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 >>.

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:117: tmplow = (~low) + tmplow;
Which is fine. It's simulating ~ on a uint64.

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:119: high = (~high + tmphigh + ((tmplow -
low) ~/ 0x100000000)) >> 0;
It's may be bigger than 32 bits. This converts to uint32.

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:127: low = tmplow >> 0;
AS above.

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:128: high = (high * 265 + (tmplow - low)
~/ 0x100000000) >> 0;
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.

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

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
File sdk/lib/_internal/lib/math_patch.dart (right):

https://codereview.chromium.org/156533002/diff/1/sdk/lib/_internal/lib/math_p...
sdk/lib/_internal/lib/math_patch.dart:105: var low = (seed & _MASK32) >> 0;
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).

[Lasse Reichstein Nielsen, 2014-02-07 08:42:51]

Committed patchset #2 manually as r32412 (presubmit successful).