1// Copyright 2020 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package fuzz
6
7import (
8	"math/bits"
9	"os"
10	"strconv"
11	"strings"
12	"sync/atomic"
13	"time"
14)
15
16type mutatorRand interface {
17	uint32() uint32
18	intn(int) int
19	uint32n(uint32) uint32
20	exp2() int
21	bool() bool
22
23	save(randState, randInc *uint64)
24	restore(randState, randInc uint64)
25}
26
27// The functions in pcg implement a 32 bit PRNG with a 64 bit period: pcg xsh rr
28// 64 32. See https://www.pcg-random.org/ for more information. This
29// implementation is geared specifically towards the needs of fuzzing: Simple
30// creation and use, no reproducibility, no concurrency safety, just the
31// necessary methods, optimized for speed.
32
33var globalInc atomic.Uint64 // PCG stream
34
35const multiplier uint64 = 6364136223846793005
36
37// pcgRand is a PRNG. It should not be copied or shared. No Rand methods are
38// concurrency safe.
39type pcgRand struct {
40	noCopy noCopy // help avoid mistakes: ask vet to ensure that we don't make a copy
41	state  uint64
42	inc    uint64
43}
44
45func godebugSeed() *int {
46	debug := strings.Split(os.Getenv("GODEBUG"), ",")
47	for _, f := range debug {
48		if strings.HasPrefix(f, "fuzzseed=") {
49			seed, err := strconv.Atoi(strings.TrimPrefix(f, "fuzzseed="))
50			if err != nil {
51				panic("malformed fuzzseed")
52			}
53			return &seed
54		}
55	}
56	return nil
57}
58
59// newPcgRand generates a new, seeded Rand, ready for use.
60func newPcgRand() *pcgRand {
61	r := new(pcgRand)
62	now := uint64(time.Now().UnixNano())
63	if seed := godebugSeed(); seed != nil {
64		now = uint64(*seed)
65	}
66	inc := globalInc.Add(1)
67	r.state = now
68	r.inc = (inc << 1) | 1
69	r.step()
70	r.state += now
71	r.step()
72	return r
73}
74
75func (r *pcgRand) step() {
76	r.state *= multiplier
77	r.state += r.inc
78}
79
80func (r *pcgRand) save(randState, randInc *uint64) {
81	*randState = r.state
82	*randInc = r.inc
83}
84
85func (r *pcgRand) restore(randState, randInc uint64) {
86	r.state = randState
87	r.inc = randInc
88}
89
90// uint32 returns a pseudo-random uint32.
91func (r *pcgRand) uint32() uint32 {
92	x := r.state
93	r.step()
94	return bits.RotateLeft32(uint32(((x>>18)^x)>>27), -int(x>>59))
95}
96
97// intn returns a pseudo-random number in [0, n).
98// n must fit in a uint32.
99func (r *pcgRand) intn(n int) int {
100	if int(uint32(n)) != n {
101		panic("large Intn")
102	}
103	return int(r.uint32n(uint32(n)))
104}
105
106// uint32n returns a pseudo-random number in [0, n).
107//
108// For implementation details, see:
109// https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction
110// https://lemire.me/blog/2016/06/30/fast-random-shuffling
111func (r *pcgRand) uint32n(n uint32) uint32 {
112	v := r.uint32()
113	prod := uint64(v) * uint64(n)
114	low := uint32(prod)
115	if low < n {
116		thresh := uint32(-int32(n)) % n
117		for low < thresh {
118			v = r.uint32()
119			prod = uint64(v) * uint64(n)
120			low = uint32(prod)
121		}
122	}
123	return uint32(prod >> 32)
124}
125
126// exp2 generates n with probability 1/2^(n+1).
127func (r *pcgRand) exp2() int {
128	return bits.TrailingZeros32(r.uint32())
129}
130
131// bool generates a random bool.
132func (r *pcgRand) bool() bool {
133	return r.uint32()&1 == 0
134}
135
136// noCopy may be embedded into structs which must not be copied
137// after the first use.
138//
139// See https://golang.org/issues/8005#issuecomment-190753527
140// for details.
141type noCopy struct{}
142
143// Lock is a no-op used by -copylocks checker from `go vet`.
144func (*noCopy) Lock()   {}
145func (*noCopy) Unlock() {}
146