v

1
// Copyright (c) 2019-2024 Alexander Medvednikov. All rights reserved.
2
// Use of this source code is governed by an MIT license
3
// that can be found in the LICENSE file.
4

5
module rand
6

7
import math.bits
8
import math.big
9
import encoding.binary
10

11
// int_u64 returns a random unsigned 64-bit integer `u64` read from a real OS source of entropy.
12
pub fn int_u64(max u64) !u64 {
13
	bitlen := bits.len_64(max)
14
	if bitlen == 0 {
15
		return u64(0)
16
	}
17
	k := (bitlen + 7) / 8
18
	mut b := u64(bitlen % 8)
19
	if b == u64(0) {
20
		b = u64(8)
21
	}
22
	mut n := u64(0)
23
	for {
24
		mut bytes := read(k)!
25
		bytes[0] &= u8(int(u64(1) << b) - 1)
26
		x := bytes_to_u64(bytes)
27
		n = x[0]
28
		// NOTE: maybe until we have bigint could do it another way?
29
		// if x.len > 1 {
30
		// 	n = u64(u32(x[1])<<u32(32)) | n
31
		// }
32
		if n < max {
33
			return n
34
		}
35
	}
36
	return n
37
}
38

39
fn bytes_to_u64(b []u8) []u64 {
40
	ws := 64 / 8
41
	mut z := []u64{len: ((b.len + ws - 1) / ws)}
42
	mut i := b.len
43
	for k := 0; i >= ws; k++ {
44
		z[k] = binary.big_endian_u64(b[i - ws..i])
45
		i -= ws
46
	}
47
	if i > 0 {
48
		mut d := u64(0)
49
		for s := u64(0); i > 0; s += u64(8) {
50
			d |= u64(b[i - 1]) << s
51
			i--
52
		}
53
		z[z.len - 1] = d
54
	}
55
	return z
56
}
57

58
// int_big creates a random `big.Integer` with range [0, n)
59
// returns an error if `n` is 0 or negative.
60
pub fn int_big(n big.Integer) !big.Integer {
61
	if n.signum < 1 {
62
		return error('`n` cannot be 0 or negative.')
63
	}
64

65
	max := n - big.integer_from_int(1)
66
	len := max.bit_len()
67

68
	if len == 0 {
69
		// max = n - 1, if max = 0 then return max, as it is the only valid integer in [0, 1)
70
		return max
71
	}
72

73
	// k is the maximum byte length needed to encode a value < n
74
	k := (len + 7) / 8
75

76
	// b is the number of bits in the most significant byte of n-1
77
	mut b := u8(len % 8)
78
	if b == 0 {
79
		b = 8
80
	}
81

82
	mut result := big.Integer{}
83
	for {
84
		mut bytes := read(k)!
85

86
		// Clear bits in the first byte to increase the probability that the result is < max
87
		bytes[0] &= u8(int(1 << b) - 1)
88

89
		result = big.integer_from_bytes(bytes)
90
		if result < max {
91
			break
92
		}
93
	}
94
	return result
95
}
96