File size: 2,593 Bytes
5316c4e
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
-- SPDX-License-Identifier: AGPL-3.0-or-later

-- | SplitMix64 (Steele, Lea, Flood 2014; the constants of Java's
-- @SplittableRandom@), written out rather than imported so
-- the harness has no dependency the gate would have to trust.
--
-- The generator is a pure state transition. Determinism matters more than
-- statistical quality here: a failing property must be reproducible from the
-- seed it prints.
module MP.Check.Random
  ( Seed
  , mkSeed
  , nextWord64
  , splitSeed
  , boundedBelow
  ) where

import Data.Bits (shiftR, xor, (.|.), popCount)
import Data.Word (Word64)

data Seed = Seed !Word64 !Word64 -- state, odd gamma
  deriving (Eq, Show)

goldenGamma :: Word64
goldenGamma = 0x9e3779b97f4a7c15

mkSeed :: Word64 -> Seed
mkSeed s = Seed s goldenGamma

mix64 :: Word64 -> Word64
mix64 z0 =
  let z1 = (z0 `xor` (z0 `shiftR` 33)) * 0xff51afd7ed558ccd
      z2 = (z1 `xor` (z1 `shiftR` 33)) * 0xc4ceb9fe1a85ec53
   in z2 `xor` (z2 `shiftR` 33)

mix64variant13 :: Word64 -> Word64
mix64variant13 z0 =
  let z1 = (z0 `xor` (z0 `shiftR` 30)) * 0xbf58476d1ce4e5b9
      z2 = (z1 `xor` (z1 `shiftR` 27)) * 0x94d049bb133111eb
   in z2 `xor` (z2 `shiftR` 31)

-- | A gamma must be odd and must not have too few bit transitions, or the
-- split streams correlate. This is the published fix-up.
mixGamma :: Word64 -> Word64
mixGamma z0 =
  let z1 = mix64 z0 .|. 1
      n = popCount (z1 `xor` (z1 `shiftR` 1))
   in if n >= 24 then z1 else z1 `xor` 0xaaaaaaaaaaaaaaaa

nextWord64 :: Seed -> (Word64, Seed)
nextWord64 (Seed s g) = let s' = s + g in (mix64variant13 s', Seed s' g)

splitSeed :: Seed -> (Seed, Seed)
splitSeed (Seed s g) =
  let s1 = s + g
      s2 = s1 + g
   in (Seed s2 g, Seed (mix64variant13 s1) (mixGamma s2))

-- | Uniform integer in @[0, n)@ for @n >= 1@, by rejection, so there is no
-- modulo bias. For @n < 1@ the result is 0; callers never pass that, and the
-- function stays total rather than calling 'error'.
boundedBelow :: Integer -> Seed -> (Integer, Seed)
boundedBelow n seed
  | n <= 1 = (0, seed)
  | otherwise = go seed
  where
    -- Enough 64-bit limbs to exceed n, then reject above the largest multiple.
    limbs = length (takeWhile (> 0) (iterate (`div` (2 ^ (64 :: Int))) n))
    range = 2 ^ (64 * limbs) :: Integer
    limit = range - (range `mod` n)
    draw k sd acc
      | k <= (0 :: Int) = (acc, sd)
      | otherwise =
          let (w, sd') = nextWord64 sd
           in draw (k - 1) sd' (acc * 2 ^ (64 :: Int) + toInteger w)
    go sd =
      let (x, sd') = draw limbs sd 0
       in if x < limit then (x `mod` n, sd') else go sd'