tobogganSe connecter

louise

Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.

203 lignes · 4937 octetsBrut · Historique
1/// Randomness, as an effect (ADR 0036).
2///
3/// random.int(6) + 1 // a die
4/// random.token(16) // 32 hex characters, for a session
5/// random.shuffle([1, 2, 3])
6///
7/// Every function here reads random bytes through the `random` effect's one
8/// operation. The runtime handles it around `main`, each test and each
9/// actor, with the kernel's generator (`getrandom`/`/dev/urandom`): good
10/// for tokens and salts. A test can choose the bytes instead:
11///
12/// random.with_seed(7, fn() { random.int(100) }) // always the same
13///
14/// A handler installed with `with_seed` (or `handle`) does not follow
15/// `process.spawn`: a new actor always gets the system's randomness.
16
17import std/array.{type Array}
18import std/bytes as raw
19import std/float
20import std/int as bits
21import std/list
22import std/prng
23import std/ref
24import std/string
25import std/u64
26
27/// Random bytes.
28pub effect random
29{
30 /// `count` random bytes; panics if `count` is negative.
31 fn bytes :: count: Int -> Bytes
32}
33
34/// A uniformly random Int in `0..below` (`below` excluded); panics unless
35/// `below` is positive. Any size: `random.int(bits.shift_left(1, 128))`.
36pub fn int :: below: Int -> Int / <random>
37{
38 if below < 1
39 {
40 panic "random.int: the bound must be positive, got {below}"
41 }
42 let width = bits.bit_length (below - 1)
43 below_by_rejection below width
44}
45
46/// Rejection sampling: draw `width` bits until they are below `below`, so
47/// every value is equally likely (fewer than 2 draws on average).
48fn below_by_rejection :: below: Int width: Int -> Int / <random>
49{
50 if width == 0
51 {
52 0
53 }
54 else
55 {
56 let v = bits.low_bits (big_endian (bytes ((width + 7) / 8))) width
57 if v < below
58 {
59 v
60 }
61 else
62 {
63 below_by_rejection below width
64 }
65 }
66}
67
68/// A uniformly random Int in `low..=high` (both included); panics if
69/// `high < low`.
70pub fn range :: low: Int high: Int -> Int / <random>
71{
72 if high < low
73 {
74 panic "random.range: {high} is below {low}"
75 }
76 low + int (high - low + 1)
77}
78
79/// A uniformly random Float in `[0, 1)`, from 53 random bits.
80pub fn float :: -> Float / <random>
81{
82 let v = bits.shift_right (big_endian (bytes 7)) 3
83 float.from_int v / 9007199254740992.0
84}
85
86/// `xs` in a random order (Fisher–Yates: every order equally likely).
87pub fn shuffle :: xs: List<a> -> List<a> / <random>
88{
89 array.to_list (shuffle_from (array.from_list xs) (list.length xs - 1))
90}
91
92fn shuffle_from :: a: Array<a> i: Int -> Array<a> / <random>
93{
94 if i < 1
95 {
96 a
97 }
98 else
99 {
100 let j = int (i + 1)
101 match (array.get a i, array.get a j)
102 { (Some(x), Some(y)) ->
103 shuffle_from (array.set (array.set a i y) j x) (i - 1)
104 , _ -> a
105 }
106 }
107}
108
109/// A random element of `xs`; `None` if it is empty.
110pub fn choice :: xs: List<a> -> Option<a> / <random>
111{
112 match xs
113 { [] -> None, _ -> array.get (array.from_list xs) (int (list.length xs)) }
114}
115
116/// `count` random bytes as lowercase hexadecimal (`2 * count` characters),
117/// for tokens and salts.
118pub fn token :: count: Int -> String / <random>
119{
120 let digits = raw.to_list (bytes count) |> list.map hex_byte
121 string.concat digits
122}
123
124fn hex_byte :: b: Int -> String
125{
126 "{hex_digit (b / 16)}{hex_digit (b % 16)}"
127}
128
129fn hex_digit :: d: Int -> String
130{
131 match d
132 { 10 -> "a"
133 , 11 -> "b"
134 , 12 -> "c"
135 , 13 -> "d"
136 , 14 -> "e"
137 , 15 -> "f"
138 , _ -> show d
139 }
140}
141
142/// The bytes as an unsigned big-endian integer.
143fn big_endian :: b: Bytes -> Int
144{
145 list.fold (raw.to_list b) 0 fn acc x { bits.or (bits.shift_left acc 8) x }
146}
147
148/// Run `action` with random bytes from a SplitMix64 generator seeded with
149/// `seed` (`std/prng`): the same seed gives the same values, on every
150/// backend and every run. Each `bytes(n)` draws `ceil(n / 8)` outputs and
151/// takes their bytes, low first. **Not for secrets**, only for tests and
152/// simulations.
153pub fn with_seed :: seed: Int action: fn() -> a / <random | e> -> a / <e>
154{
155 region
156 {
157 let state = ref.new (prng.seeded seed)
158 handle
159 {
160 action ()
161 }
162 with
163 { bytes count ->
164 {
165 if count < 0
166 {
167 panic "random.bytes: negative count {count}"
168 }
169 let (out, next) = draw (ref.get state) count (raw.builder ())
170 ref.set state next
171 out
172 }
173 }
174 }
175}
176
177/// `count` bytes from `g`, appended to `acc`; the generator after them.
178fn draw :: g: prng.Prng count: Int acc: raw.Builder -> (Bytes, prng.Prng)
179{
180 if count <= 0
181 {
182 (raw.build acc, g)
183 }
184 else
185 {
186 let (x, next) = prng.next g
187 draw next (count - 8) (append_low acc x if count < 8 { count } else { 8 })
188 }
189}
190
191/// The `n` low bytes of `x`, lowest first.
192fn append_low :: acc: raw.Builder x: u64.U64 n: Int -> raw.Builder
193{
194 if n == 0
195 {
196 acc
197 }
198 else
199 {
200 let byte = u64.to_int (u64.and x (u64.from_int 255))
201 append_low (raw.append_byte acc byte) (u64.shift_right x 8) (n - 1)
202 }
203}