/
starstar.go
153 lines (130 loc) · 3.99 KB
/
starstar.go
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// Derived from http://prng.di.unimi.it/xoshiro256starstar.c:
//
// Written in 2018 by David Blackman and Sebastiano Vigna (vigna@acm.org)
//
// To the extent possible under law, the author has dedicated all copyright
// and related and neighboring rights to this software to the public domain
// worldwide. This software is distributed without any warranty.
//
// See <http://creativecommons.org/publicdomain/zero/1.0/>.
// Package xoshiro256 implements the xoshiro256** random number generator.
package xoshiro256
import (
"encoding/binary"
"errors"
"math/bits"
"github.com/greatroar/randstat/splitmix64"
)
// A Source is a xoshiro256** 1.0 random number generator.
//
// The zero Source is not usable; it produces a stream of zeros.
//
// Note that Sources constructed by New or initialized with Seed can
// produce 2^64 distinct streams of random numbers.
// The state S is public for applications that need more.
type Source struct {
S [4]uint64 // Generator state (256 bits).
}
// New returns a Source initialized with the given seed.
// It is equivalent to allocating a Source and calling Seed on it.
func New(seed uint64) *Source {
s := &Source{}
s.Seed(int64(seed))
return s
}
// Int63 returns a non-negative pseudo-random 63-bit integer as an int64.
func (s *Source) Int63() int64 { return int64(s.Uint64() >> 1) }
// Jump advances the Source by 2^128 positions.
func (s *Source) Jump() {
jump := [...]uint64{
0x180ec6d33cfd0aba, 0xd5a61266f0c9392c,
0xa9582618e03fc9aa, 0x39abdc4529b1661c}
var s0, s1, s2, s3 uint64
for i := 0; i < len(jump); i++ {
for b := byte(0); b < 64; b++ {
if jump[i]&(1<<b) != 0 {
s0 ^= s.S[0]
s1 ^= s.S[1]
s2 ^= s.S[2]
s3 ^= s.S[3]
}
s.Uint64()
}
}
s.S = [4]uint64{s0, s1, s2, s3}
}
// Seed uses the provided seed value to initialize the generator to a
// deterministic state.
// The seed value may be any 64-bit integer.
//
// It uses a SplitMix64 generator to turn seed into four non-zero
// pseudo-random numbers.
func (s *Source) Seed(seed int64) {
sm := splitmix64.Source(seed)
retry:
s0 := sm.Uint64()
s1 := sm.Uint64()
s2 := sm.Uint64()
s3 := sm.Uint64()
if s0|s1|s2|s3 == 0 {
goto retry
}
s.S = [4]uint64{s0, s1, s2, s3}
}
// Uint64 returns a pseudo-random 64-bit value as a uint64.
func (s *Source) Uint64() uint64 {
st := &s.S
r := bits.RotateLeft64(5*st[1], 7) * 9
t := st[1] << 17
st[2] ^= st[0]
st[3] ^= st[1]
st[1] ^= st[2]
st[0] ^= st[3]
st[2] ^= t
st[3] = bits.RotateLeft64(st[3], 45)
return r
}
const (
header = "xoshiro256**1.0\x00"
marshalSize = len(header) + 4*8
)
// MarshalBinary encodes s in a binary format for serialization.
//
// The format starts with a 16-byte header, followed by the four 64-bit
// integers of state in little-endian format.
//
// The returned error is always nil.
func (s *Source) MarshalBinary() (data []byte, err error) {
data = make([]byte, marshalSize)
copy(data, header)
for i, x := range s.S {
binary.LittleEndian.PutUint64(data[len(header)+8*i:], x)
}
return
}
// UnmarshalBinary decodes s from the binary format used by MarshalBinary.
func (s *Source) UnmarshalBinary(data []byte) error {
switch {
case len(data) != marshalSize:
return errors.New("unmarshal xoshiro256: incorrect data length")
case string(data[:len(header)]) != header:
return errors.New("unmarshal xoshiro256: incorrect header")
}
data = data[len(header):]
for i := range s.S {
s.S[i] = binary.LittleEndian.Uint64(data)
data = data[8:]
}
return nil
}