rng.go

Documentation: go.mongodb.org/mongo-driver/internal/rand

     1  // Copied from https://cs.opensource.google/go/x/exp/+/24438e51023af3bfc1db8aed43c1342817e8cfcd:rand/rng.go
     2  
     3  // Copyright 2017 The Go Authors. All rights reserved.
     4  // Use of this source code is governed by a BSD-style
     5  // license that can be found in the LICENSE file.
     6  
     7  package rand
     8  
     9  import (
    10  	"encoding/binary"
    11  	"io"
    12  	"math/bits"
    13  )
    14  
    15  // PCGSource is an implementation of a 64-bit permuted congruential
    16  // generator as defined in
    17  //
    18  //	PCG: A Family of Simple Fast Space-Efficient Statistically Good
    19  //	Algorithms for Random Number Generation
    20  //	Melissa E. O’Neill, Harvey Mudd College
    21  //	http://www.pcg-random.org/pdf/toms-oneill-pcg-family-v1.02.pdf
    22  //
    23  // The generator here is the congruential generator PCG XSL RR 128/64 (LCG)
    24  // as found in the software available at http://www.pcg-random.org/.
    25  // It has period 2^128 with 128 bits of state, producing 64-bit values.
    26  // Is state is represented by two uint64 words.
    27  type PCGSource struct {
    28  	low  uint64
    29  	high uint64
    30  }
    31  
    32  const (
    33  	maxUint32 = (1 << 32) - 1
    34  
    35  	multiplier = 47026247687942121848144207491837523525
    36  	mulHigh    = multiplier >> 64
    37  	mulLow     = multiplier & maxUint64
    38  
    39  	increment = 117397592171526113268558934119004209487
    40  	incHigh   = increment >> 64
    41  	incLow    = increment & maxUint64
    42  
    43  	// TODO: Use these?
    44  	initializer = 245720598905631564143578724636268694099
    45  	initHigh    = initializer >> 64
    46  	initLow     = initializer & maxUint64
    47  )
    48  
    49  // Seed uses the provided seed value to initialize the generator to a deterministic state.
    50  func (pcg *PCGSource) Seed(seed uint64) {
    51  	pcg.low = seed
    52  	pcg.high = seed // TODO: What is right?
    53  }
    54  
    55  // Uint64 returns a pseudo-random 64-bit unsigned integer as a uint64.
    56  func (pcg *PCGSource) Uint64() uint64 {
    57  	pcg.multiply()
    58  	pcg.add()
    59  	// XOR high and low 64 bits together and rotate right by high 6 bits of state.
    60  	return bits.RotateLeft64(pcg.high^pcg.low, -int(pcg.high>>58))
    61  }
    62  
    63  func (pcg *PCGSource) add() {
    64  	var carry uint64
    65  	pcg.low, carry = Add64(pcg.low, incLow, 0)
    66  	pcg.high, _ = Add64(pcg.high, incHigh, carry)
    67  }
    68  
    69  func (pcg *PCGSource) multiply() {
    70  	hi, lo := Mul64(pcg.low, mulLow)
    71  	hi += pcg.high * mulLow
    72  	hi += pcg.low * mulHigh
    73  	pcg.low = lo
    74  	pcg.high = hi
    75  }
    76  
    77  // MarshalBinary returns the binary representation of the current state of the generator.
    78  func (pcg *PCGSource) MarshalBinary() ([]byte, error) {
    79  	var buf [16]byte
    80  	binary.BigEndian.PutUint64(buf[:8], pcg.high)
    81  	binary.BigEndian.PutUint64(buf[8:], pcg.low)
    82  	return buf[:], nil
    83  }
    84  
    85  // UnmarshalBinary sets the state of the generator to the state represented in data.
    86  func (pcg *PCGSource) UnmarshalBinary(data []byte) error {
    87  	if len(data) < 16 {
    88  		return io.ErrUnexpectedEOF
    89  	}
    90  	pcg.low = binary.BigEndian.Uint64(data[8:])
    91  	pcg.high = binary.BigEndian.Uint64(data[:8])
    92  	return nil
    93  }
    94
View as plain text