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
+}