blob: cc1f95c88d5a0fecf6b7f30476573cfe0c265502 [file] [log] [blame]
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Package rand implements pseudo-random number generators suitable for tasks
// such as simulation, but it should not be used for security-sensitive work.
//
// Random numbers are generated by a [Source], usually wrapped in a [Rand].
// Both types should be used by a single goroutine at a time: sharing among
// multiple goroutines requires some kind of synchronization.
//
// Top-level functions, such as [Float64] and [Int],
// are safe for concurrent use by multiple goroutines.
//
// This package's outputs might be easily predictable regardless of how it's
// seeded. For random numbers suitable for security-sensitive work, see the
// crypto/rand package.
package rand
import (
"internal/godebug"
"sync"
"sync/atomic"
_ "unsafe" // for go:linkname
)
// A Source represents a source of uniformly-distributed
// pseudo-random int64 values in the range [0, 1<<63).
//
// A Source is not safe for concurrent use by multiple goroutines.
type Source interface {
Int63() int64
Seed(seed int64)
}
// A Source64 is a Source that can also generate
// uniformly-distributed pseudo-random uint64 values in
// the range [0, 1<<64) directly.
// If a Rand r's underlying Source s implements Source64,
// then r.Uint64 returns the result of one call to s.Uint64
// instead of making two calls to s.Int63.
type Source64 interface {
Source
Uint64() uint64
}
// NewSource returns a new pseudo-random Source seeded with the given value.
// Unlike the default Source used by top-level functions, this source is not
// safe for concurrent use by multiple goroutines.
// The returned Source implements Source64.
func NewSource(seed int64) Source {
return newSource(seed)
}
func newSource(seed int64) *rngSource {
var rng rngSource
rng.Seed(seed)
return &rng
}
// A Rand is a source of random numbers.
type Rand struct {
src Source
s64 Source64 // non-nil if src is source64
// readVal contains remainder of 63-bit integer used for bytes
// generation during most recent Read call.
// It is saved so next Read call can start where the previous
// one finished.
readVal int64
// readPos indicates the number of low-order bytes of readVal
// that are still valid.
readPos int8
}
// New returns a new Rand that uses random values from src
// to generate other random values.
func New(src Source) *Rand {
s64, _ := src.(Source64)
return &Rand{src: src, s64: s64}
}
// Seed uses the provided seed value to initialize the generator to a deterministic state.
// Seed should not be called concurrently with any other Rand method.
func (r *Rand) Seed(seed int64) {
if lk, ok := r.src.(*lockedSource); ok {
lk.seedPos(seed, &r.readPos)
return
}
r.src.Seed(seed)
r.readPos = 0
}
// Int63 returns a non-negative pseudo-random 63-bit integer as an int64.
func (r *Rand) Int63() int64 { return r.src.Int63() }
// Uint32 returns a pseudo-random 32-bit value as a uint32.
func (r *Rand) Uint32() uint32 { return uint32(r.Int63() >> 31) }
// Uint64 returns a pseudo-random 64-bit value as a uint64.
func (r *Rand) Uint64() uint64 {
if r.s64 != nil {
return r.s64.Uint64()
}
return uint64(r.Int63())>>31 | uint64(r.Int63())<<32
}
// Int31 returns a non-negative pseudo-random 31-bit integer as an int32.
func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) }
// Int returns a non-negative pseudo-random int.
func (r *Rand) Int() int {
u := uint(r.Int63())
return int(u << 1 >> 1) // clear sign bit if int == int32
}
// Int63n returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n).
// It panics if n <= 0.
func (r *Rand) Int63n(n int64) int64 {
if n <= 0 {
panic("invalid argument to Int63n")
}
if n&(n-1) == 0 { // n is power of two, can mask
return r.Int63() & (n - 1)
}
max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
v := r.Int63()
for v > max {
v = r.Int63()
}
return v % n
}
// Int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n).
// It panics if n <= 0.
func (r *Rand) Int31n(n int32) int32 {
if n <= 0 {
panic("invalid argument to Int31n")
}
if n&(n-1) == 0 { // n is power of two, can mask
return r.Int31() & (n - 1)
}
max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
v := r.Int31()
for v > max {
v = r.Int31()
}
return v % n
}
// int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n).
// n must be > 0, but int31n does not check this; the caller must ensure it.
// int31n exists because Int31n is inefficient, but Go 1 compatibility
// requires that the stream of values produced by math/rand remain unchanged.
// int31n can thus only be used internally, by newly introduced APIs.
//
// For implementation details, see:
// https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction
// https://lemire.me/blog/2016/06/30/fast-random-shuffling
func (r *Rand) int31n(n int32) int32 {
v := r.Uint32()
prod := uint64(v) * uint64(n)
low := uint32(prod)
if low < uint32(n) {
thresh := uint32(-n) % uint32(n)
for low < thresh {
v = r.Uint32()
prod = uint64(v) * uint64(n)
low = uint32(prod)
}
}
return int32(prod >> 32)
}
// Intn returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n).
// It panics if n <= 0.
func (r *Rand) Intn(n int) int {
if n <= 0 {
panic("invalid argument to Intn")
}
if n <= 1<<31-1 {
return int(r.Int31n(int32(n)))
}
return int(r.Int63n(int64(n)))
}
// Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0).
func (r *Rand) Float64() float64 {
// A clearer, simpler implementation would be:
// return float64(r.Int63n(1<<53)) / (1<<53)
// However, Go 1 shipped with
// return float64(r.Int63()) / (1 << 63)
// and we want to preserve that value stream.
//
// There is one bug in the value stream: r.Int63() may be so close
// to 1<<63 that the division rounds up to 1.0, and we've guaranteed
// that the result is always less than 1.0.
//
// We tried to fix this by mapping 1.0 back to 0.0, but since float64
// values near 0 are much denser than near 1, mapping 1 to 0 caused
// a theoretically significant overshoot in the probability of returning 0.
// Instead of that, if we round up to 1, just try again.
// Getting 1 only happens 1/2⁵³ of the time, so most clients
// will not observe it anyway.
again:
f := float64(r.Int63()) / (1 << 63)
if f == 1 {
goto again // resample; this branch is taken O(never)
}
return f
}
// Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0).
func (r *Rand) Float32() float32 {
// Same rationale as in Float64: we want to preserve the Go 1 value
// stream except we want to fix it not to return 1.0
// This only happens 1/2²⁴ of the time (plus the 1/2⁵³ of the time in Float64).
again:
f := float32(r.Float64())
if f == 1 {
goto again // resample; this branch is taken O(very rarely)
}
return f
}
// Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
// in the half-open interval [0,n).
func (r *Rand) Perm(n int) []int {
m := make([]int, n)
// In the following loop, the iteration when i=0 always swaps m[0] with m[0].
// A change to remove this useless iteration is to assign 1 to i in the init
// statement. But Perm also effects r. Making this change will affect
// the final state of r. So this change can't be made for compatibility
// reasons for Go 1.
for i := 0; i < n; i++ {
j := r.Intn(i + 1)
m[i] = m[j]
m[j] = i
}
return m
}
// Shuffle pseudo-randomizes the order of elements.
// n is the number of elements. Shuffle panics if n < 0.
// swap swaps the elements with indexes i and j.
func (r *Rand) Shuffle(n int, swap func(i, j int)) {
if n < 0 {
panic("invalid argument to Shuffle")
}
// Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
// Shuffle really ought not be called with n that doesn't fit in 32 bits.
// Not only will it take a very long time, but with 2³¹! possible permutations,
// there's no way that any PRNG can have a big enough internal state to
// generate even a minuscule percentage of the possible permutations.
// Nevertheless, the right API signature accepts an int n, so handle it as best we can.
i := n - 1
for ; i > 1<<31-1-1; i-- {
j := int(r.Int63n(int64(i + 1)))
swap(i, j)
}
for ; i > 0; i-- {
j := int(r.int31n(int32(i + 1)))
swap(i, j)
}
}
// Read generates len(p) random bytes and writes them into p. It
// always returns len(p) and a nil error.
// Read should not be called concurrently with any other Rand method.
func (r *Rand) Read(p []byte) (n int, err error) {
switch src := r.src.(type) {
case *lockedSource:
return src.read(p, &r.readVal, &r.readPos)
case *fastSource:
return src.read(p, &r.readVal, &r.readPos)
}
return read(p, r.src, &r.readVal, &r.readPos)
}
func read(p []byte, src Source, readVal *int64, readPos *int8) (n int, err error) {
pos := *readPos
val := *readVal
rng, _ := src.(*rngSource)
for n = 0; n < len(p); n++ {
if pos == 0 {
if rng != nil {
val = rng.Int63()
} else {
val = src.Int63()
}
pos = 7
}
p[n] = byte(val)
val >>= 8
pos--
}
*readPos = pos
*readVal = val
return
}
/*
* Top-level convenience functions
*/
// globalRandGenerator is the source of random numbers for the top-level
// convenience functions. When possible it uses the runtime fastrand64
// function to avoid locking. This is not possible if the user called Seed,
// either explicitly or implicitly via GODEBUG=randautoseed=0.
var globalRandGenerator atomic.Pointer[Rand]
var randautoseed = godebug.New("randautoseed")
// globalRand returns the generator to use for the top-level convenience
// functions.
func globalRand() *Rand {
if r := globalRandGenerator.Load(); r != nil {
return r
}
// This is the first call. Initialize based on GODEBUG.
var r *Rand
if randautoseed.Value() == "0" {
randautoseed.IncNonDefault()
r = New(new(lockedSource))
r.Seed(1)
} else {
r = &Rand{
src: &fastSource{},
s64: &fastSource{},
}
}
if !globalRandGenerator.CompareAndSwap(nil, r) {
// Two different goroutines called some top-level
// function at the same time. While the results in
// that case are unpredictable, if we just use r here,
// and we are using a seed, we will most likely return
// the same value for both calls. That doesn't seem ideal.
// Just use the first one to get in.
return globalRandGenerator.Load()
}
return r
}
//go:linkname fastrand64
func fastrand64() uint64
// fastSource is an implementation of Source64 that uses the runtime
// fastrand functions.
type fastSource struct {
// The mutex is used to avoid race conditions in Read.
mu sync.Mutex
}
func (*fastSource) Int63() int64 {
return int64(fastrand64() & rngMask)
}
func (*fastSource) Seed(int64) {
panic("internal error: call to fastSource.Seed")
}
func (*fastSource) Uint64() uint64 {
return fastrand64()
}
func (fs *fastSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) {
fs.mu.Lock()
n, err = read(p, fs, readVal, readPos)
fs.mu.Unlock()
return
}
// Seed uses the provided seed value to initialize the default Source to a
// deterministic state. Seed values that have the same remainder when
// divided by 2³¹-1 generate the same pseudo-random sequence.
// Seed, unlike the Rand.Seed method, is safe for concurrent use.
//
// If Seed is not called, the generator is seeded randomly at program startup.
//
// Prior to Go 1.20, the generator was seeded like Seed(1) at program startup.
// To force the old behavior, call Seed(1) at program startup.
// Alternately, set GODEBUG=randautoseed=0 in the environment
// before making any calls to functions in this package.
//
// Deprecated: As of Go 1.20 there is no reason to call Seed with
// a random value. Programs that call Seed with a known value to get
// a specific sequence of results should use New(NewSource(seed)) to
// obtain a local random generator.
func Seed(seed int64) {
orig := globalRandGenerator.Load()
// If we are already using a lockedSource, we can just re-seed it.
if orig != nil {
if _, ok := orig.src.(*lockedSource); ok {
orig.Seed(seed)
return
}
}
// Otherwise either
// 1) orig == nil, which is the normal case when Seed is the first
// top-level function to be called, or
// 2) orig is already a fastSource, in which case we need to change
// to a lockedSource.
// Either way we do the same thing.
r := New(new(lockedSource))
r.Seed(seed)
if !globalRandGenerator.CompareAndSwap(orig, r) {
// Something changed underfoot. Retry to be safe.
Seed(seed)
}
}
// Int63 returns a non-negative pseudo-random 63-bit integer as an int64
// from the default Source.
func Int63() int64 { return globalRand().Int63() }
// Uint32 returns a pseudo-random 32-bit value as a uint32
// from the default Source.
func Uint32() uint32 { return globalRand().Uint32() }
// Uint64 returns a pseudo-random 64-bit value as a uint64
// from the default Source.
func Uint64() uint64 { return globalRand().Uint64() }
// Int31 returns a non-negative pseudo-random 31-bit integer as an int32
// from the default Source.
func Int31() int32 { return globalRand().Int31() }
// Int returns a non-negative pseudo-random int from the default Source.
func Int() int { return globalRand().Int() }
// Int63n returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n)
// from the default Source.
// It panics if n <= 0.
func Int63n(n int64) int64 { return globalRand().Int63n(n) }
// Int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n)
// from the default Source.
// It panics if n <= 0.
func Int31n(n int32) int32 { return globalRand().Int31n(n) }
// Intn returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n)
// from the default Source.
// It panics if n <= 0.
func Intn(n int) int { return globalRand().Intn(n) }
// Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0)
// from the default Source.
func Float64() float64 { return globalRand().Float64() }
// Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0)
// from the default Source.
func Float32() float32 { return globalRand().Float32() }
// Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
// in the half-open interval [0,n) from the default Source.
func Perm(n int) []int { return globalRand().Perm(n) }
// Shuffle pseudo-randomizes the order of elements using the default Source.
// n is the number of elements. Shuffle panics if n < 0.
// swap swaps the elements with indexes i and j.
func Shuffle(n int, swap func(i, j int)) { globalRand().Shuffle(n, swap) }
// Read generates len(p) random bytes from the default Source and
// writes them into p. It always returns len(p) and a nil error.
// Read, unlike the Rand.Read method, is safe for concurrent use.
//
// Deprecated: For almost all use cases, crypto/rand.Read is more appropriate.
func Read(p []byte) (n int, err error) { return globalRand().Read(p) }
// NormFloat64 returns a normally distributed float64 in the range
// [-math.MaxFloat64, +math.MaxFloat64] with
// standard normal distribution (mean = 0, stddev = 1)
// from the default Source.
// To produce a different normal distribution, callers can
// adjust the output using:
//
// sample = NormFloat64() * desiredStdDev + desiredMean
func NormFloat64() float64 { return globalRand().NormFloat64() }
// ExpFloat64 returns an exponentially distributed float64 in the range
// (0, +math.MaxFloat64] with an exponential distribution whose rate parameter
// (lambda) is 1 and whose mean is 1/lambda (1) from the default Source.
// To produce a distribution with a different rate parameter,
// callers can adjust the output using:
//
// sample = ExpFloat64() / desiredRateParameter
func ExpFloat64() float64 { return globalRand().ExpFloat64() }
type lockedSource struct {
lk sync.Mutex
s *rngSource
}
func (r *lockedSource) Int63() (n int64) {
r.lk.Lock()
n = r.s.Int63()
r.lk.Unlock()
return
}
func (r *lockedSource) Uint64() (n uint64) {
r.lk.Lock()
n = r.s.Uint64()
r.lk.Unlock()
return
}
func (r *lockedSource) Seed(seed int64) {
r.lk.Lock()
r.seed(seed)
r.lk.Unlock()
}
// seedPos implements Seed for a lockedSource without a race condition.
func (r *lockedSource) seedPos(seed int64, readPos *int8) {
r.lk.Lock()
r.seed(seed)
*readPos = 0
r.lk.Unlock()
}
// seed seeds the underlying source.
// The caller must have locked r.lk.
func (r *lockedSource) seed(seed int64) {
if r.s == nil {
r.s = newSource(seed)
} else {
r.s.Seed(seed)
}
}
// read implements Read for a lockedSource without a race condition.
func (r *lockedSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) {
r.lk.Lock()
n, err = read(p, r.s, readVal, readPos)
r.lk.Unlock()
return
}