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  	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  
    33  var globalInc atomic.Uint64 // PCG stream
    34  
    35  const multiplier uint64 = 6364136223846793005
    36  
    37  // pcgRand is a PRNG. It should not be copied or shared. No Rand methods are
    38  // concurrency safe.
    39  type 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  
    45  func 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.
    60  func 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  
    75  func (r *pcgRand) step() {
    76  	r.state *= multiplier
    77  	r.state += r.inc
    78  }
    79  
    80  func (r *pcgRand) save(randState, randInc *uint64) {
    81  	*randState = r.state
    82  	*randInc = r.inc
    83  }
    84  
    85  func (r *pcgRand) restore(randState, randInc uint64) {
    86  	r.state = randState
    87  	r.inc = randInc
    88  }
    89  
    90  // uint32 returns a pseudo-random uint32.
    91  func (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.
    99  func (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
   111  func (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).
   127  func (r *pcgRand) exp2() int {
   128  	return bits.TrailingZeros32(r.uint32())
   129  }
   130  
   131  // bool generates a random bool.
   132  func (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.
   141  type noCopy struct{}
   142  
   143  // Lock is a no-op used by -copylocks checker from `go vet`.
   144  func (*noCopy) Lock()   {}
   145  func (*noCopy) Unlock() {}
   146
View as plain text