diff options
| author | Bruce Hill <bruce@bruce-hill.com> | 2025-09-01 16:44:58 -0400 |
|---|---|---|
| committer | Bruce Hill <bruce@bruce-hill.com> | 2025-09-01 16:44:58 -0400 |
| commit | ed50c5fefb8892ad2ba5262491669f268ddbd436 (patch) | |
| tree | e93a6a8b7e963c37a001691751d6845d10e0cbf8 /lib/random | |
| parent | 02a99d24a310c04622a875dcf4b0c6fd2de71332 (diff) | |
Overhaul code to stop keeping examples and libraries in the same repo,
but instead spin each out into its own repo.
Diffstat (limited to 'lib/random')
| -rw-r--r-- | lib/random/CHANGES.md | 5 | ||||
| -rw-r--r-- | lib/random/README.md | 196 | ||||
| -rw-r--r-- | lib/random/chacha.h | 192 | ||||
| -rw-r--r-- | lib/random/random.tm | 234 | ||||
| -rw-r--r-- | lib/random/sysrandom.h | 17 |
5 files changed, 0 insertions, 644 deletions
diff --git a/lib/random/CHANGES.md b/lib/random/CHANGES.md deleted file mode 100644 index 42ae752c..00000000 --- a/lib/random/CHANGES.md +++ /dev/null @@ -1,5 +0,0 @@ -# Version History - -## v1.0 - -Initial version diff --git a/lib/random/README.md b/lib/random/README.md deleted file mode 100644 index 183b9d0b..00000000 --- a/lib/random/README.md +++ /dev/null @@ -1,196 +0,0 @@ -# Random Number Generators (RNG) - -This library provides an `RNG` type (Random Number Generator). This type -represents a self-contained piece of data that encapsulates the state of a -relatively fast and relatively secure pseudo-random number generator. The -current implementation is based on the [ChaCha20 stream -cipher,](https://en.wikipedia.org/wiki/Salsa20#ChaCha_variant) inspired by -[`arc4random` in OpenBSD.](https://man.openbsd.org/arc4random.3) - -An `RNG` object can be used for deterministic, repeatable generation of -pseudorandom numbers (for example, to be used in a video game for creating -seeded levels). The default random number generator for Tomo is called `random` -and is, by default, initialized with random data from the operating system when -a Tomo program launches. - -## RNG Functions - -This documentation provides details on RNG functions available in the API. -Lists also have some methods which use RNG values: -`list.shuffle()`, `list.shuffled()`, `list.random()`, and `list.sample()`. - -- [`func bool(rng: RNG, p: Num = 0.5 -> Bool)`](#bool) -- [`func byte(rng: RNG -> Byte)`](#byte) -- [`func bytes(rng: RNG, count: Int -> [Byte])`](#bytes) -- [`func copy(rng: RNG -> RNG)`](#copy) -- [`func int(rng: RNG, min: Int, max: Int -> Int)`](#int`, `int64`, `int32`, `int16`, `int8) -- [`func new(seed: [Byte] = (/dev/urandom).read_bytes(40)! -> RNG)`](#new) -- [`func num(rng: RNG, min: Num = 0.0, max: Num = 1.0 -> Num)`](#num`, `num32) - -------------- - -### `bool` -Generate a random boolean value with a given probability. - -```tomo -func bool(rng: RNG, p: Num = 0.5 -> Bool) -``` - -- `rng`: The random number generator to use. -- `p`: The probability of returning a `yes` value. Values less than zero and - `NaN` values are treated as equal to zero and values larger than zero are - treated as equal to one. - -**Returns:** -`yes` with probability `p` and `no` with probability `1-p`. - -**Example:** -```tomo ->> random.bool() -= no ->> random.bool(1.0) -= yes -``` - ---- - -### `byte` -Generate a random byte with uniform probability. - -```tomo -func byte(rng: RNG -> Byte) -``` - -- `rng`: The random number generator to use. - -**Returns:** -A random byte (0-255). - -**Example:** -```tomo ->> random.byte() -= 103[B] -``` - ---- - -### `bytes` -Generate a list of uniformly random bytes with the given length. - -```tomo -func bytes(rng: RNG, count: Int -> [Byte]) -``` - -- `rng`: The random number generator to use. -- `count`: The number of random bytes to return. - -**Returns:** -A list of length `count` random bytes with uniform random distribution (0-255). - -**Example:** -```tomo ->> random.bytes(4) -= [135[B], 169[B], 103[B], 212[B]] -``` - ---- - -### `copy` -Return a copy of a random number generator. This copy will be a parallel version of -the given RNG with its own internal state. - -```tomo -func copy(rng: RNG -> RNG) -``` - -- `rng`: The random number generator to copy. - -**Returns:** -A copy of the given RNG. - -**Example:** -```tomo ->> rng := RNG.new([]) ->> copy := rng.copy() - ->> rng.bytes(10) -= [224[B], 102[B], 190[B], 59[B], 251[B], 50[B], 217[B], 170[B], 15[B], 221[B]] - -# The copy runs in parallel to the original RNG: ->> copy.bytes(10) -= [224[B], 102[B], 190[B], 59[B], 251[B], 50[B], 217[B], 170[B], 15[B], 221[B]] -``` - ---- - -### `int`, `int64`, `int32`, `int16`, `int8` -Generate a random integer value with the given range. - -```tomo -func int(rng: RNG, min: Int, max: Int -> Int) -func int64(rng: RNG, min: Int64 = Int64.min, max: Int64 = Int64.max -> Int) -func int32(rng: RNG, min: Int32 = Int32.min, max: Int32 = Int32.max -> Int) -func int16(rng: RNG, min: Int16 = Int16.min, max: Int16 = Int16.max -> Int) -func int8(rng: RNG, min: Int8 = Int8.min, max: Int8 = Int8.max -> Int) -``` - -- `rng`: The random number generator to use. -- `min`: The minimum value to be returned. -- `max`: The maximum value to be returned. - -**Returns:** -An integer uniformly chosen from the range `[min, max]` (inclusive). If `min` -is greater than `max`, an error will be raised. - -**Example:** -```tomo ->> random.int(1, 10) -= 8 -``` - ---- - -### `new` -Return a new random number generator. - -```tomo -func new(seed: [Byte] = (/dev/urandom).read_bytes(40)! -> RNG) -``` - -- `seed`: The seed use for the random number generator. A seed length of 40 - bytes is recommended. Seed lengths of less than 40 bytes are padded with - zeroes. - -**Returns:** -A new random number generator. - -**Example:** -```tomo ->> my_rng := RNG.new([1[B], 2[B], 3[B], 4[B]]) ->> my_rng.bool() -= yes -``` - ---- - -### `num`, `num32` -Generate a random floating point value with the given range. - -```tomo -func num(rng: RNG, min: Num = 0.0, max: Num = 1.0 -> Int) -func num32(rng: RNG, min: Num = 0.0_f32, max: Num = 1.0_f32 -> Int) -``` - -- `rng`: The random number generator to use. -- `min`: The minimum value to be returned. -- `max`: The maximum value to be returned. - -**Returns:** -A floating point number uniformly chosen from the range `[min, max]` -(inclusive). If `min` is greater than `max`, an error will be raised. - -**Example:** -```tomo ->> random.num(1, 10) -= 9.512830439975572 -``` diff --git a/lib/random/chacha.h b/lib/random/chacha.h deleted file mode 100644 index 22015819..00000000 --- a/lib/random/chacha.h +++ /dev/null @@ -1,192 +0,0 @@ -// The ChaCha stream cipher used for pseudorandom number generation - -#pragma once -/* -chacha-merged.c version 20080118 -D. J. Bernstein -Public domain. -*/ - -/* $OpenBSD: chacha_private.h,v 1.3 2022/02/28 21:56:29 dtucker Exp $ */ -/* Tomo: chacha.h,v 1.0 2024/11/03 Bruce Hill */ - -typedef unsigned char u8; -typedef unsigned int u32; - -typedef struct { - u32 input[16]; /* could be compressed */ -} chacha_ctx; - -#define KEYSZ 32 -#define IVSZ 8 - -#define U8C(v) (v##U) -#define U32C(v) (v##U) - -#define U8V(v) ((u8)(v) & U8C(0xFF)) -#define U32V(v) ((u32)(v) & U32C(0xFFFFFFFF)) - -#define ROTL32(v, n) (U32V((v) << (n)) | ((v) >> (32 - (n)))) - -#define U8TO32_LITTLE(p) (((u32)((p)[0])) | ((u32)((p)[1]) << 8) | ((u32)((p)[2]) << 16) | ((u32)((p)[3]) << 24)) - -#define U32TO8_LITTLE(p, v) \ - do { \ - (p)[0] = U8V((v)); \ - (p)[1] = U8V((v) >> 8); \ - (p)[2] = U8V((v) >> 16); \ - (p)[3] = U8V((v) >> 24); \ - } while (0) - -#define ROTATE(v, c) (ROTL32(v, c)) -#define XOR(v, w) ((v) ^ (w)) -#define PLUS(v, w) (U32V((v) + (w))) -#define PLUSONE(v) (PLUS((v), 1)) - -#define QUARTERROUND(a, b, c, d) \ - a = PLUS(a, b); \ - d = ROTATE(XOR(d, a), 16); \ - c = PLUS(c, d); \ - b = ROTATE(XOR(b, c), 12); \ - a = PLUS(a, b); \ - d = ROTATE(XOR(d, a), 8); \ - c = PLUS(c, d); \ - b = ROTATE(XOR(b, c), 7); - -static const char sigma[16] = "expand 32-byte k"; - -static void chacha_keysetup(chacha_ctx *chacha, const u8 *k) { - chacha->input[0] = U8TO32_LITTLE(sigma + 0); - chacha->input[1] = U8TO32_LITTLE(sigma + 4); - chacha->input[2] = U8TO32_LITTLE(sigma + 8); - chacha->input[3] = U8TO32_LITTLE(sigma + 12); - chacha->input[4] = U8TO32_LITTLE(k + 0); - chacha->input[5] = U8TO32_LITTLE(k + 4); - chacha->input[6] = U8TO32_LITTLE(k + 8); - chacha->input[7] = U8TO32_LITTLE(k + 12); - chacha->input[8] = U8TO32_LITTLE(k + 16); - chacha->input[9] = U8TO32_LITTLE(k + 20); - chacha->input[10] = U8TO32_LITTLE(k + 24); - chacha->input[11] = U8TO32_LITTLE(k + 28); -} - -static void chacha_ivsetup(chacha_ctx *chacha, const u8 *iv) { - chacha->input[12] = 0; - chacha->input[13] = 0; - chacha->input[14] = U8TO32_LITTLE(iv + 0); - chacha->input[15] = U8TO32_LITTLE(iv + 4); -} - -static void chacha_encrypt_bytes(chacha_ctx *chacha, const u8 *m, u8 *c, u32 bytes) { - u32 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15; - u32 j0, j1, j2, j3, j4, j5, j6, j7, j8, j9, j10, j11, j12, j13, j14, j15; - u8 *ctarget = (u8 *)0; - u8 tmp[64]; - unsigned int i; - - if (!bytes) return; - - j0 = chacha->input[0]; - j1 = chacha->input[1]; - j2 = chacha->input[2]; - j3 = chacha->input[3]; - j4 = chacha->input[4]; - j5 = chacha->input[5]; - j6 = chacha->input[6]; - j7 = chacha->input[7]; - j8 = chacha->input[8]; - j9 = chacha->input[9]; - j10 = chacha->input[10]; - j11 = chacha->input[11]; - j12 = chacha->input[12]; - j13 = chacha->input[13]; - j14 = chacha->input[14]; - j15 = chacha->input[15]; - - for (;;) { - if (bytes < 64) { - for (i = 0; i < bytes; ++i) - tmp[i] = m[i]; - m = tmp; - ctarget = c; - c = tmp; - } - x0 = j0; - x1 = j1; - x2 = j2; - x3 = j3; - x4 = j4; - x5 = j5; - x6 = j6; - x7 = j7; - x8 = j8; - x9 = j9; - x10 = j10; - x11 = j11; - x12 = j12; - x13 = j13; - x14 = j14; - x15 = j15; - for (i = 20; i > 0; i -= 2) { - QUARTERROUND(x0, x4, x8, x12) - QUARTERROUND(x1, x5, x9, x13) - QUARTERROUND(x2, x6, x10, x14) - QUARTERROUND(x3, x7, x11, x15) - QUARTERROUND(x0, x5, x10, x15) - QUARTERROUND(x1, x6, x11, x12) - QUARTERROUND(x2, x7, x8, x13) - QUARTERROUND(x3, x4, x9, x14) - } - x0 = PLUS(x0, j0); - x1 = PLUS(x1, j1); - x2 = PLUS(x2, j2); - x3 = PLUS(x3, j3); - x4 = PLUS(x4, j4); - x5 = PLUS(x5, j5); - x6 = PLUS(x6, j6); - x7 = PLUS(x7, j7); - x8 = PLUS(x8, j8); - x9 = PLUS(x9, j9); - x10 = PLUS(x10, j10); - x11 = PLUS(x11, j11); - x12 = PLUS(x12, j12); - x13 = PLUS(x13, j13); - x14 = PLUS(x14, j14); - x15 = PLUS(x15, j15); - - j12 = PLUSONE(j12); - if (!j12) { - j13 = PLUSONE(j13); - /* stopping at 2^70 bytes per nonce is user's responsibility */ - } - - U32TO8_LITTLE(c + 0, x0); - U32TO8_LITTLE(c + 4, x1); - U32TO8_LITTLE(c + 8, x2); - U32TO8_LITTLE(c + 12, x3); - U32TO8_LITTLE(c + 16, x4); - U32TO8_LITTLE(c + 20, x5); - U32TO8_LITTLE(c + 24, x6); - U32TO8_LITTLE(c + 28, x7); - U32TO8_LITTLE(c + 32, x8); - U32TO8_LITTLE(c + 36, x9); - U32TO8_LITTLE(c + 40, x10); - U32TO8_LITTLE(c + 44, x11); - U32TO8_LITTLE(c + 48, x12); - U32TO8_LITTLE(c + 52, x13); - U32TO8_LITTLE(c + 56, x14); - U32TO8_LITTLE(c + 60, x15); - - if (bytes <= 64) { - if (bytes < 64) { - for (i = 0; i < bytes; ++i) - ctarget[i] = c[i]; - } - chacha->input[12] = j12; - chacha->input[13] = j13; - return; - } - bytes -= 64; - c += 64; - } -} diff --git a/lib/random/random.tm b/lib/random/random.tm deleted file mode 100644 index 107fad66..00000000 --- a/lib/random/random.tm +++ /dev/null @@ -1,234 +0,0 @@ -# Random Number Generator (RNG) implementation based on ChaCha - -use <assert.h> -use ./sysrandom.h -use ./chacha.h - -struct chacha_ctx(j0,j1,j2,j3,j4,j5,j6,j7,j8,j9,j10,j11,j12,j13,j14,j15:Int32; extern, secret) - func from_seed(seed:[Byte]=[] -> chacha_ctx) - return C_code:chacha_ctx( - chacha_ctx ctx; - uint8_t seed_bytes[KEYSZ + IVSZ] = {}; - for (int64_t i = 0; i < (int64_t)sizeof(seed_bytes); i++) - seed_bytes[i] = i < @seed.length ? *(uint8_t*)(@seed.data + i*@seed.stride) : 0; - chacha_keysetup(&ctx, seed_bytes); - chacha_ivsetup(&ctx, seed_bytes + KEYSZ); - ctx - ) - -random := RandomNumberGenerator.new() - -func _os_random_bytes(count:Int64 -> [Byte]) - return C_code:[Byte]( - uint8_t *random_bytes = GC_MALLOC_ATOMIC(@count); - assert(getrandom(random_bytes, (size_t)@count, 0) == (size_t)@count); - (List_t){.length=@count, .data=random_bytes, .stride=1, .atomic=1} - ) -struct RandomNumberGenerator(_chacha:chacha_ctx, _random_bytes:[Byte]=[]; secret) - func new(seed:[Byte]?=none, -> @RandomNumberGenerator) - ctx := chacha_ctx.from_seed(seed or _os_random_bytes(40)) - return @RandomNumberGenerator(ctx, []) - - func _rekey(rng:&RandomNumberGenerator) - rng._random_bytes = C_code:[Byte]( - Byte_t new_keystream[KEYSZ + IVSZ] = {}; - // Fill the buffer with the keystream - chacha_encrypt_bytes(&@rng->_chacha, new_keystream, new_keystream, sizeof(new_keystream)); - // Immediately reinitialize for backtracking resistance - chacha_keysetup(&@rng->_chacha, new_keystream); - chacha_ivsetup(&@rng->_chacha, new_keystream + KEYSZ); - List_t new_bytes = (List_t){.data=GC_MALLOC_ATOMIC(1024), .length=1024, .stride=1, .atomic=1}; - memset(new_bytes.data, 0, new_bytes.length); - chacha_encrypt_bytes(&@rng->_chacha, new_bytes.data, new_bytes.data, new_bytes.length); - new_bytes - ) - - func _fill_bytes(rng:&RandomNumberGenerator, dest:&Memory, needed:Int64) - C_code { - while (@needed > 0) { - if (@rng->_random_bytes.length == 0) - @(rng._rekey()); - - assert(@rng->_random_bytes.stride == 1); - - int64_t batch_size = MIN(@needed, @rng->_random_bytes.length); - uint8_t *batch_src = @rng->_random_bytes.data; - memcpy(@dest, batch_src, batch_size); - memset(batch_src, 0, batch_size); - @rng->_random_bytes.data += batch_size; - @rng->_random_bytes.length -= batch_size; - @dest += batch_size; - @needed -= batch_size; - } - } - - func bytes(rng:&RandomNumberGenerator, count:Int -> [Byte]) - count64 := Int64(count) - buf := C_code:@Memory(GC_MALLOC_ATOMIC(@count64)) - rng._fill_bytes(buf, count64) - return C_code:[Byte]((List_t){.data=@buf, .stride=1, .atomic=1, .length=@count64}) - - func byte(rng:&RandomNumberGenerator -> Byte) - byte : &Byte - rng._fill_bytes(byte, 1) - return byte[] - - func bool(rng:&RandomNumberGenerator, probability=0.5 -> Bool) - if probability == 0.5 - return rng.byte() < 0x80 - else - return rng.num(0., 1.) < 0.5 - - func int64(rng:&RandomNumberGenerator, min=Int64.min, max=Int64.max -> Int64) - fail("Random minimum value $min is larger than the maximum value $max") if min > max - return min if min == max - random_int64 : &Int64 - rng._fill_bytes(random_int64, 8) - if min == Int64.min and max == Int64.max - return random_int64 - - return C_code:Int64( - uint64_t range = (uint64_t)@max - (uint64_t)@min + 1; - uint64_t min_r = -range % range; - uint64_t r; - @random_int64 = (int64_t*)&r; - for (;;) { - @(rng._fill_bytes(random_int64, 8)); - if (r >= min_r) break; - } - (int64_t)((uint64_t)@min + (r % range)) - ) - - func int32(rng:&RandomNumberGenerator, min=Int32.min, max=Int32.max -> Int32) - fail("Random minimum value $min is larger than the maximum value $max") if min > max - return min if min == max - random_int32 : &Int32 - rng._fill_bytes(random_int32, 8) - if min == Int32.min and max == Int32.max - return random_int32 - - return C_code:Int32( - uint32_t range = (uint32_t)@max - (uint32_t)@min + 1; - uint32_t min_r = -range % range; - uint32_t r; - @random_int32 = (int32_t*)&r; - for (;;) { - @(rng._fill_bytes(random_int32, 8)); - if (r >= min_r) break; - } - (int32_t)((uint32_t)@min + (r % range)) - ) - - func int16(rng:&RandomNumberGenerator, min=Int16.min, max=Int16.max -> Int16) - fail("Random minimum value $min is larger than the maximum value $max") if min > max - return min if min == max - random_int16 : &Int16 - rng._fill_bytes(random_int16, 8) - if min == Int16.min and max == Int16.max - return random_int16 - - return C_code:Int16( - uint16_t range = (uint16_t)@max - (uint16_t)@min + 1; - uint16_t min_r = -range % range; - uint16_t r; - @random_int16 = (int16_t*)&r; - for (;;) { - @(rng._fill_bytes(random_int16, 8)); - if (r >= min_r) break; - } - (int16_t)((uint16_t)@min + (r % range)) - ) - - func int8(rng:&RandomNumberGenerator, min=Int8.min, max=Int8.max -> Int8) - fail("Random minimum value $min is larger than the maximum value $max") if min > max - return min if min == max - random_int8 : &Int8 - rng._fill_bytes(random_int8, 8) - if min == Int8.min and max == Int8.max - return random_int8 - - return C_code:Int8( - uint8_t range = (uint8_t)@max - (uint8_t)@min + 1; - uint8_t min_r = -range % range; - uint8_t r; - @random_int8 = (int8_t*)&r; - for (;;) { - @(rng._fill_bytes(random_int8, 8)); - if (r >= min_r) break; - } - (int8_t)((uint8_t)@min + (r % range)) - ) - - func num(rng:&RandomNumberGenerator, min=0., max=1. -> Num) - num_buf : &Num - return C_code:Num( - if (@min > @max) fail("Random minimum value (", @min, ") is larger than the maximum value (", @max, ")"); - if (@min == @max) return @min; - - union { - Num_t num; - uint64_t bits; - } r = {.bits=0}, one = {.num=1.0}; - @num_buf = &r.num; - @(rng._fill_bytes(num_buf, 8)); - - // Set r.num to 1.<random-bits> - r.bits &= ~(0xFFFULL << 52); - r.bits |= (one.bits & (0xFFFULL << 52)); - - r.num -= 1.0; - - (@min == 0.0 && @max == 1.0) ? r.num : ((1.0-r.num)*@min + r.num*@max) - ) - - func num32(rng:&RandomNumberGenerator, min=Num32(0.), max=Num32(1.) -> Num32) - return Num32(rng.num(Num(min), Num(max))) - - func int(rng:&RandomNumberGenerator, min:Int, max:Int -> Int) - return C_code:Int( - if (likely(((@min.small & @max.small) & 1) != 0)) { - int32_t r = @(rng.int32(Int32(min), Int32(max))); - return I_small(r); - } - - int32_t cmp = @(min <> max); - if (cmp > 0) - fail("Random minimum value (", @min, ") is larger than the maximum value (", @max, ")"); - if (cmp == 0) return @min; - - mpz_t range_size; - mpz_init_set_int(range_size, @max); - if (@min.small & 1) { - mpz_t min_mpz; - mpz_init_set_si(min_mpz, @min.small >> 2); - mpz_sub(range_size, range_size, min_mpz); - } else { - mpz_sub(range_size, range_size, *@min.big); - } - - gmp_randstate_t gmp_rng; - gmp_randinit_default(gmp_rng); - int64_t seed = @(rng.int64()); - gmp_randseed_ui(gmp_rng, (unsigned long)seed); - - mpz_t r; - mpz_init(r); - mpz_urandomm(r, gmp_rng, range_size); - - gmp_randclear(gmp_rng); - Int$plus(@min, Int$from_mpz(r)) - ) - - -func main() - >> rng := RandomNumberGenerator.new() - >> rng.num() - >> rng.num() - >> rng.num() - >> rng.num(0, 100) - >> rng.byte() - >> rng.bytes(20) - # >> rng.int(1, 100) - # >> rng.int(1, 100) - # >> rng.int(1, 100) - # >> rng.int(1, 100) diff --git a/lib/random/sysrandom.h b/lib/random/sysrandom.h deleted file mode 100644 index 3d6b800f..00000000 --- a/lib/random/sysrandom.h +++ /dev/null @@ -1,17 +0,0 @@ -// Logic for using system random numbers - -#pragma once - -#if defined(__FreeBSD__) || defined(__OpenBSD__) || defined(__NetBSD__) || defined(__APPLE__) -#include <stdlib.h> -static ssize_t getrandom(void *buf, size_t buflen, unsigned int flags) { - (void)flags; - arc4random_buf(buf, buflen); - return buflen; -} -#elif defined(__linux__) -// Use getrandom() -#include <sys/random.h> -#else -#error "Unsupported platform for secure random number generation" -#endif |
