1 // Copyright 2009 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 rand implements pseudo-random number generators suitable for tasks
6 // such as simulation, but it should not be used for security-sensitive work.
7 //
8 // Random numbers are generated by a [Source], usually wrapped in a [Rand].
9 // Both types should be used by a single goroutine at a time: sharing among
10 // multiple goroutines requires some kind of synchronization.
11 //
12 // Top-level functions, such as [Float64] and [Int],
13 // are safe for concurrent use by multiple goroutines.
14 //
15 // This package's outputs might be easily predictable regardless of how it's
16 // seeded. For random numbers suitable for security-sensitive work, see the
17 // crypto/rand package.
18 package rand
19 20 import (
21 "internal/godebug"
22 "sync"
23 "sync/atomic"
24 _ "unsafe" // for go:linkname
25 )
26 27 // A Source represents a source of uniformly-distributed
28 // pseudo-random int64 values in the range [0, 1<<63).
29 //
30 // A Source is not safe for concurrent use by multiple goroutines.
31 type Source interface {
32 Int63() int64
33 Seed(seed int64)
34 }
35 36 // A Source64 is a [Source] that can also generate
37 // uniformly-distributed pseudo-random uint64 values in
38 // the range [0, 1<<64) directly.
39 // If a [Rand] r's underlying [Source] s implements Source64,
40 // then r.Uint64 returns the result of one call to s.Uint64
41 // instead of making two calls to s.Int63.
42 type Source64 interface {
43 Source
44 Uint64() uint64
45 }
46 47 // NewSource returns a new pseudo-random [Source] seeded with the given value.
48 // Unlike the default [Source] used by top-level functions, this source is not
49 // safe for concurrent use by multiple goroutines.
50 // The returned [Source] implements [Source64].
51 func NewSource(seed int64) Source {
52 return newSource(seed)
53 }
54 55 func newSource(seed int64) *rngSource {
56 var rng rngSource
57 rng.Seed(seed)
58 return &rng
59 }
60 61 // A Rand is a source of random numbers.
62 type Rand struct {
63 src Source
64 s64 Source64 // non-nil if src is source64
65 66 // readVal contains remainder of 63-bit integer used for bytes
67 // generation during most recent Read call.
68 // It is saved so next Read call can start where the previous
69 // one finished.
70 readVal int64
71 // readPos indicates the number of low-order bytes of readVal
72 // that are still valid.
73 readPos int8
74 }
75 76 // New returns a new [Rand] that uses random values from src
77 // to generate other random values.
78 func New(src Source) *Rand {
79 s64, _ := src.(Source64)
80 return &Rand{src: src, s64: s64}
81 }
82 83 // Seed uses the provided seed value to initialize the generator to a deterministic state.
84 // Seed should not be called concurrently with any other [Rand] method.
85 func (r *Rand) Seed(seed int64) {
86 if lk, ok := r.src.(*lockedSource); ok {
87 lk.seedPos(seed, &r.readPos)
88 return
89 }
90 91 r.src.Seed(seed)
92 r.readPos = 0
93 }
94 95 // Int63 returns a non-negative pseudo-random 63-bit integer as an int64.
96 func (r *Rand) Int63() int64 { return r.src.Int63() }
97 98 // Uint32 returns a pseudo-random 32-bit value as a uint32.
99 func (r *Rand) Uint32() uint32 { return uint32(r.Int63() >> 31) }
100 101 // Uint64 returns a pseudo-random 64-bit value as a uint64.
102 func (r *Rand) Uint64() uint64 {
103 if r.s64 != nil {
104 return r.s64.Uint64()
105 }
106 return uint64(r.Int63())>>31 | uint64(r.Int63())<<32
107 }
108 109 // Int31 returns a non-negative pseudo-random 31-bit integer as an int32.
110 func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) }
111 112 // Int returns a non-negative pseudo-random int.
113 func (r *Rand) Int() int {
114 u := uint(r.Int63())
115 return int(u << 1 >> 1) // clear sign bit if int == int32
116 }
117 118 // Int63n returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n).
119 // It panics if n <= 0.
120 func (r *Rand) Int63n(n int64) int64 {
121 if n <= 0 {
122 panic("invalid argument to Int63n")
123 }
124 if n&(n-1) == 0 { // n is power of two, can mask
125 return r.Int63() & (n - 1)
126 }
127 max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
128 v := r.Int63()
129 for v > max {
130 v = r.Int63()
131 }
132 return v % n
133 }
134 135 // Int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n).
136 // It panics if n <= 0.
137 func (r *Rand) Int31n(n int32) int32 {
138 if n <= 0 {
139 panic("invalid argument to Int31n")
140 }
141 if n&(n-1) == 0 { // n is power of two, can mask
142 return r.Int31() & (n - 1)
143 }
144 max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
145 v := r.Int31()
146 for v > max {
147 v = r.Int31()
148 }
149 return v % n
150 }
151 152 // int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n).
153 // n must be > 0, but int31n does not check this; the caller must ensure it.
154 // int31n exists because Int31n is inefficient, but Go 1 compatibility
155 // requires that the stream of values produced by math/rand remain unchanged.
156 // int31n can thus only be used internally, by newly introduced APIs.
157 //
158 // For implementation details, see:
159 // https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction
160 // https://lemire.me/blog/2016/06/30/fast-random-shuffling
161 func (r *Rand) int31n(n int32) int32 {
162 v := r.Uint32()
163 prod := uint64(v) * uint64(n)
164 low := uint32(prod)
165 if low < uint32(n) {
166 thresh := uint32(-n) % uint32(n)
167 for low < thresh {
168 v = r.Uint32()
169 prod = uint64(v) * uint64(n)
170 low = uint32(prod)
171 }
172 }
173 return int32(prod >> 32)
174 }
175 176 // Intn returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n).
177 // It panics if n <= 0.
178 func (r *Rand) Intn(n int) int {
179 if n <= 0 {
180 panic("invalid argument to Intn")
181 }
182 if n <= 1<<31-1 {
183 return int(r.Int31n(int32(n)))
184 }
185 return int(r.Int63n(int64(n)))
186 }
187 188 // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0).
189 func (r *Rand) Float64() float64 {
190 // A clearer, simpler implementation would be:
191 // return float64(r.Int63n(1<<53)) / (1<<53)
192 // However, Go 1 shipped with
193 // return float64(r.Int63()) / (1 << 63)
194 // and we want to preserve that value stream.
195 //
196 // There is one bug in the value stream: r.Int63() may be so close
197 // to 1<<63 that the division rounds up to 1.0, and we've guaranteed
198 // that the result is always less than 1.0.
199 //
200 // We tried to fix this by mapping 1.0 back to 0.0, but since float64
201 // values near 0 are much denser than near 1, mapping 1 to 0 caused
202 // a theoretically significant overshoot in the probability of returning 0.
203 // Instead of that, if we round up to 1, just try again.
204 // Getting 1 only happens 1/2⁵³ of the time, so most clients
205 // will not observe it anyway.
206 again:
207 f := float64(r.Int63()) / (1 << 63)
208 if f == 1 {
209 goto again // resample; this branch is taken O(never)
210 }
211 return f
212 }
213 214 // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0).
215 func (r *Rand) Float32() float32 {
216 // Same rationale as in Float64: we want to preserve the Go 1 value
217 // stream except we want to fix it not to return 1.0
218 // This only happens 1/2²⁴ of the time (plus the 1/2⁵³ of the time in Float64).
219 again:
220 f := float32(r.Float64())
221 if f == 1 {
222 goto again // resample; this branch is taken O(very rarely)
223 }
224 return f
225 }
226 227 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
228 // in the half-open interval [0,n).
229 func (r *Rand) Perm(n int) []int {
230 m := []int{:n}
231 // In the following loop, the iteration when i=0 always swaps m[0] with m[0].
232 // A change to remove this useless iteration is to assign 1 to i in the init
233 // statement. But Perm also effects r. Making this change will affect
234 // the final state of r. So this change can't be made for compatibility
235 // reasons for Go 1.
236 for i := 0; i < n; i++ {
237 j := r.Intn(i + 1)
238 m[i] = m[j]
239 m[j] = i
240 }
241 return m
242 }
243 244 // Shuffle pseudo-randomizes the order of elements.
245 // n is the number of elements. Shuffle panics if n < 0.
246 // swap swaps the elements with indexes i and j.
247 func (r *Rand) Shuffle(n int, swap func(i, j int)) {
248 if n < 0 {
249 panic("invalid argument to Shuffle")
250 }
251 252 // Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
253 // Shuffle really ought not be called with n that doesn't fit in 32 bits.
254 // Not only will it take a very long time, but with 2³¹! possible permutations,
255 // there's no way that any PRNG can have a big enough internal state to
256 // generate even a minuscule percentage of the possible permutations.
257 // Nevertheless, the right API signature accepts an int n, so handle it as best we can.
258 i := n - 1
259 for ; i > 1<<31-1-1; i-- {
260 j := int(r.Int63n(int64(i + 1)))
261 swap(i, j)
262 }
263 for ; i > 0; i-- {
264 j := int(r.int31n(int32(i + 1)))
265 swap(i, j)
266 }
267 }
268 269 // Read generates len(p) random bytes and writes them into p. It
270 // always returns len(p) and a nil error.
271 // Read should not be called concurrently with any other Rand method.
272 func (r *Rand) Read(p []byte) (n int, err error) {
273 switch src := r.src.(type) {
274 case *lockedSource:
275 return src.read(p, &r.readVal, &r.readPos)
276 case *runtimeSource:
277 return src.read(p, &r.readVal, &r.readPos)
278 }
279 return read(p, r.src, &r.readVal, &r.readPos)
280 }
281 282 func read(p []byte, src Source, readVal *int64, readPos *int8) (n int, err error) {
283 pos := *readPos
284 val := *readVal
285 rng, _ := src.(*rngSource)
286 for n = 0; n < len(p); n++ {
287 if pos == 0 {
288 if rng != nil {
289 val = rng.Int63()
290 } else {
291 val = src.Int63()
292 }
293 pos = 7
294 }
295 p[n] = byte(val)
296 val >>= 8
297 pos--
298 }
299 *readPos = pos
300 *readVal = val
301 return
302 }
303 304 /*
305 * Top-level convenience functions
306 */
307 308 // globalRandGenerator is the source of random numbers for the top-level
309 // convenience functions. When possible it uses the runtime fastrand64
310 // function to avoid locking. This is not possible if the user called Seed,
311 // either explicitly or implicitly via GODEBUG=randautoseed=0.
312 var globalRandGenerator atomic.Pointer[Rand]
313 314 var randautoseed = godebug.New("randautoseed")
315 316 // randseednop controls whether the global Seed is a no-op.
317 var randseednop = godebug.New("randseednop")
318 319 // globalRand returns the generator to use for the top-level convenience
320 // functions.
321 func globalRand() *Rand {
322 if r := globalRandGenerator.Load(); r != nil {
323 return r
324 }
325 326 // This is the first call. Initialize based on GODEBUG.
327 var r *Rand
328 if randautoseed.Value() == "0" {
329 randautoseed.IncNonDefault()
330 r = New(&lockedSource{})
331 r.Seed(1)
332 } else {
333 r = &Rand{
334 src: &runtimeSource{},
335 s64: &runtimeSource{},
336 }
337 }
338 339 if !globalRandGenerator.CompareAndSwap(nil, r) {
340 // Two different goroutines called some top-level
341 // function at the same time. While the results in
342 // that case are unpredictable, if we just use r here,
343 // and we are using a seed, we will most likely return
344 // the same value for both calls. That doesn't seem ideal.
345 // Just use the first one to get in.
346 return globalRandGenerator.Load()
347 }
348 349 return r
350 }
351 352 //go:linkname runtime_rand runtime.rand
353 func runtime_rand() uint64
354 355 // runtimeSource is an implementation of Source64 that uses the runtime
356 // fastrand functions.
357 type runtimeSource struct {
358 // The mutex is used to avoid race conditions in Read.
359 mu sync.Mutex
360 }
361 362 func (*runtimeSource) Int63() int64 {
363 return int64(runtime_rand() & rngMask)
364 }
365 366 func (*runtimeSource) Seed(int64) {
367 panic("internal error: call to runtimeSource.Seed")
368 }
369 370 func (*runtimeSource) Uint64() uint64 {
371 return runtime_rand()
372 }
373 374 func (fs *runtimeSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) {
375 fs.mu.Lock()
376 n, err = read(p, fs, readVal, readPos)
377 fs.mu.Unlock()
378 return
379 }
380 381 // Seed uses the provided seed value to initialize the default Source to a
382 // deterministic state. Seed values that have the same remainder when
383 // divided by 2³¹-1 generate the same pseudo-random sequence.
384 // Seed, unlike the [Rand.Seed] method, is safe for concurrent use.
385 //
386 // If Seed is not called, the generator is seeded randomly at program startup.
387 //
388 // Prior to Go 1.20, the generator was seeded like Seed(1) at program startup.
389 // To force the old behavior, call Seed(1) at program startup.
390 // Alternately, set GODEBUG=randautoseed=0 in the environment
391 // before making any calls to functions in this package.
392 //
393 // Deprecated: As of Go 1.20 there is no reason to call Seed with
394 // a random value. Programs that call Seed with a known value to get
395 // a specific sequence of results should use New(NewSource(seed)) to
396 // obtain a local random generator.
397 //
398 // As of Go 1.24 [Seed] is a no-op. To restore the previous behavior set
399 // GODEBUG=randseednop=0.
400 func Seed(seed int64) {
401 if randseednop.Value() != "0" {
402 return
403 }
404 randseednop.IncNonDefault()
405 406 orig := globalRandGenerator.Load()
407 408 // If we are already using a lockedSource, we can just re-seed it.
409 if orig != nil {
410 if _, ok := orig.src.(*lockedSource); ok {
411 orig.Seed(seed)
412 return
413 }
414 }
415 416 // Otherwise either
417 // 1) orig == nil, which is the normal case when Seed is the first
418 // top-level function to be called, or
419 // 2) orig is already a runtimeSource, in which case we need to change
420 // to a lockedSource.
421 // Either way we do the same thing.
422 423 r := New(&lockedSource{})
424 r.Seed(seed)
425 426 if !globalRandGenerator.CompareAndSwap(orig, r) {
427 // Something changed underfoot. Retry to be safe.
428 Seed(seed)
429 }
430 }
431 432 // Int63 returns a non-negative pseudo-random 63-bit integer as an int64
433 // from the default [Source].
434 func Int63() int64 { return globalRand().Int63() }
435 436 // Uint32 returns a pseudo-random 32-bit value as a uint32
437 // from the default [Source].
438 func Uint32() uint32 { return globalRand().Uint32() }
439 440 // Uint64 returns a pseudo-random 64-bit value as a uint64
441 // from the default [Source].
442 func Uint64() uint64 { return globalRand().Uint64() }
443 444 // Int31 returns a non-negative pseudo-random 31-bit integer as an int32
445 // from the default [Source].
446 func Int31() int32 { return globalRand().Int31() }
447 448 // Int returns a non-negative pseudo-random int from the default [Source].
449 func Int() int { return globalRand().Int() }
450 451 // Int63n returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n)
452 // from the default [Source].
453 // It panics if n <= 0.
454 func Int63n(n int64) int64 { return globalRand().Int63n(n) }
455 456 // Int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n)
457 // from the default [Source].
458 // It panics if n <= 0.
459 func Int31n(n int32) int32 { return globalRand().Int31n(n) }
460 461 // Intn returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n)
462 // from the default [Source].
463 // It panics if n <= 0.
464 func Intn(n int) int { return globalRand().Intn(n) }
465 466 // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0)
467 // from the default [Source].
468 func Float64() float64 { return globalRand().Float64() }
469 470 // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0)
471 // from the default [Source].
472 func Float32() float32 { return globalRand().Float32() }
473 474 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
475 // in the half-open interval [0,n) from the default [Source].
476 func Perm(n int) []int { return globalRand().Perm(n) }
477 478 // Shuffle pseudo-randomizes the order of elements using the default [Source].
479 // n is the number of elements. Shuffle panics if n < 0.
480 // swap swaps the elements with indexes i and j.
481 func Shuffle(n int, swap func(i, j int)) { globalRand().Shuffle(n, swap) }
482 483 // Read generates len(p) random bytes from the default [Source] and
484 // writes them into p. It always returns len(p) and a nil error.
485 // Read, unlike the [Rand.Read] method, is safe for concurrent use.
486 //
487 // Deprecated: For almost all use cases, [crypto/rand.Read] is more appropriate.
488 // If a deterministic source is required, use [math/rand/v2.ChaCha8.Read].
489 func Read(p []byte) (n int, err error) { return globalRand().Read(p) }
490 491 // NormFloat64 returns a normally distributed float64 in the range
492 // [-[math.MaxFloat64], +[math.MaxFloat64]] with
493 // standard normal distribution (mean = 0, stddev = 1)
494 // from the default [Source].
495 // To produce a different normal distribution, callers can
496 // adjust the output using:
497 //
498 // sample = NormFloat64() * desiredStdDev + desiredMean
499 func NormFloat64() float64 { return globalRand().NormFloat64() }
500 501 // ExpFloat64 returns an exponentially distributed float64 in the range
502 // (0, +[math.MaxFloat64]] with an exponential distribution whose rate parameter
503 // (lambda) is 1 and whose mean is 1/lambda (1) from the default [Source].
504 // To produce a distribution with a different rate parameter,
505 // callers can adjust the output using:
506 //
507 // sample = ExpFloat64() / desiredRateParameter
508 func ExpFloat64() float64 { return globalRand().ExpFloat64() }
509 510 type lockedSource struct {
511 lk sync.Mutex
512 s *rngSource
513 }
514 515 func (r *lockedSource) Int63() (n int64) {
516 r.lk.Lock()
517 n = r.s.Int63()
518 r.lk.Unlock()
519 return
520 }
521 522 func (r *lockedSource) Uint64() (n uint64) {
523 r.lk.Lock()
524 n = r.s.Uint64()
525 r.lk.Unlock()
526 return
527 }
528 529 func (r *lockedSource) Seed(seed int64) {
530 r.lk.Lock()
531 r.seed(seed)
532 r.lk.Unlock()
533 }
534 535 // seedPos implements Seed for a lockedSource without a race condition.
536 func (r *lockedSource) seedPos(seed int64, readPos *int8) {
537 r.lk.Lock()
538 r.seed(seed)
539 *readPos = 0
540 r.lk.Unlock()
541 }
542 543 // seed seeds the underlying source.
544 // The caller must have locked r.lk.
545 func (r *lockedSource) seed(seed int64) {
546 if r.s == nil {
547 r.s = newSource(seed)
548 } else {
549 r.s.Seed(seed)
550 }
551 }
552 553 // read implements Read for a lockedSource without a race condition.
554 func (r *lockedSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) {
555 r.lk.Lock()
556 n, err = read(p, r.s, readVal, readPos)
557 r.lk.Unlock()
558 return
559 }
560