pcg.go

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