diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-16 19:25:22 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-16 19:25:22 +0000 |
commit | f6ad4dcef54c5ce997a4bad5a6d86de229015700 (patch) | |
tree | 7cfa4e31ace5c2bd95c72b154d15af494b2bcbef /src/math/rand/rand.go | |
parent | Initial commit. (diff) | |
download | golang-1.22-f6ad4dcef54c5ce997a4bad5a6d86de229015700.tar.xz golang-1.22-f6ad4dcef54c5ce997a4bad5a6d86de229015700.zip |
Adding upstream version 1.22.1.upstream/1.22.1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/math/rand/rand.go')
-rw-r--r-- | src/math/rand/rand.go | 547 |
1 files changed, 547 insertions, 0 deletions
diff --git a/src/math/rand/rand.go b/src/math/rand/rand.go new file mode 100644 index 0000000..a8ed9c0 --- /dev/null +++ b/src/math/rand/rand.go @@ -0,0 +1,547 @@ +// 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 *runtimeSource: + 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: &runtimeSource{}, + s64: &runtimeSource{}, + } + } + + 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 runtime_rand runtime.rand +func runtime_rand() uint64 + +// runtimeSource is an implementation of Source64 that uses the runtime +// fastrand functions. +type runtimeSource struct { + // The mutex is used to avoid race conditions in Read. + mu sync.Mutex +} + +func (*runtimeSource) Int63() int64 { + return int64(runtime_rand() & rngMask) +} + +func (*runtimeSource) Seed(int64) { + panic("internal error: call to runtimeSource.Seed") +} + +func (*runtimeSource) Uint64() uint64 { + return runtime_rand() +} + +func (fs *runtimeSource) 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 runtimeSource, 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 +} |