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