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
|
// Copyright 2017 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package rand
import (
"math/big"
"math/rand"
"testing"
)
var bigMaxUint64 = big.NewInt(0).SetUint64(maxUint64)
func bigInt(xHi, xLo uint64) *big.Int {
b := big.NewInt(0).SetUint64(xHi)
b.Lsh(b, 64)
b.Or(b, big.NewInt(0).SetUint64(xLo))
return b
}
func splitBigInt(b *big.Int) (outHi, outLo uint64) {
outHi = big.NewInt(0).Rsh(b, 64).Uint64()
outLo = big.NewInt(0).And(b, bigMaxUint64).Uint64()
return
}
func bigMulMod128bits(xHi, xLo, yHi, yLo uint64) (outHi, outLo uint64) {
bigX := bigInt(xHi, xLo)
bigY := bigInt(yHi, yLo)
return splitBigInt(bigX.Mul(bigX, bigY))
}
func bigAddMod128bits(xHi, xLo, yHi, yLo uint64) (outHi, outLo uint64) {
bigX := bigInt(xHi, xLo)
bigY := bigInt(yHi, yLo)
return splitBigInt(bigX.Add(bigX, bigY))
}
type arithTest struct {
xHi, xLo uint64
}
const (
iLo = increment & maxUint64
iHi = (increment >> 64) & maxUint64
)
var arithTests = []arithTest{
{0, 0},
{0, 1},
{1, 0},
{0, maxUint64},
{maxUint64, 0},
{maxUint64, maxUint64},
// Randomly generated 64-bit integers.
{3757956613005209672, 17983933746665545631},
{511324141977587414, 5626651684620191081},
{1534313104606153588, 2415006486399353367},
{6873586429837825902, 13854394671140464137},
{6617134480561088940, 18421520694158684312},
}
func TestPCGAdd(t *testing.T) {
for i, test := range arithTests {
p := &PCGSource{
low: test.xLo,
high: test.xHi,
}
p.add()
expectHi, expectLo := bigAddMod128bits(test.xHi, test.xLo, iHi, iLo)
if p.low != expectLo || p.high != expectHi {
t.Errorf("%d: got hi=%d lo=%d; expect hi=%d lo=%d", i, p.high, p.low, expectHi, expectLo)
}
}
}
const (
mLo = multiplier & maxUint64
mHi = (multiplier >> 64) & maxUint64
)
func TestPCGMultiply(t *testing.T) {
for i, test := range arithTests {
p := &PCGSource{
low: test.xLo,
high: test.xHi,
}
p.multiply()
expectHi, expectLo := bigMulMod128bits(test.xHi, test.xLo, mHi, mLo)
if p.low != expectLo || p.high != expectHi {
t.Errorf("%d: got hi=%d lo=%d; expect hi=%d lo=%d", i, p.high, p.low, expectHi, expectLo)
}
}
}
func TestPCGMultiplyLong(t *testing.T) {
if testing.Short() {
return
}
for i := 0; i < 1e6; i++ {
low := rand.Uint64()
high := rand.Uint64()
p := &PCGSource{
low: low,
high: high,
}
p.multiply()
expectHi, expectLo := bigMulMod128bits(high, low, mHi, mLo)
if p.low != expectLo || p.high != expectHi {
t.Fatalf("%d: (%d,%d): got hi=%d lo=%d; expect hi=%d lo=%d", i, high, low, p.high, p.low, expectHi, expectLo)
}
}
}
func BenchmarkPCGMultiply(b *testing.B) {
low := rand.Uint64()
high := rand.Uint64()
p := &PCGSource{
low: low,
high: high,
}
for i := 0; i < b.N; i++ {
p.multiply()
}
}
|
