diff options
Diffstat (limited to 'examples')
| -rw-r--r-- | examples/core/core.tm | 1 | ||||
| -rw-r--r-- | examples/random/README.md | 196 | ||||
| -rw-r--r-- | examples/random/chacha.h | 196 | ||||
| -rw-r--r-- | examples/random/random.tm | 240 | ||||
| -rw-r--r-- | examples/random/sysrandom.h | 14 |
5 files changed, 647 insertions, 0 deletions
diff --git a/examples/core/core.tm b/examples/core/core.tm index b49448d2..f7259b7f 100644 --- a/examples/core/core.tm +++ b/examples/core/core.tm @@ -7,3 +7,4 @@ use shell use colorful use log use pthreads +use random diff --git a/examples/random/README.md b/examples/random/README.md new file mode 100644 index 00000000..697f3f7c --- /dev/null +++ b/examples/random/README.md @@ -0,0 +1,196 @@ +# 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. +Arrays also have some methods which use RNG values: +`array:shuffle()`, `array:shuffled()`, `array:random()`, and `array: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 an array 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:** +An array 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([:Byte]) +>> 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/examples/random/chacha.h b/examples/random/chacha.h new file mode 100644 index 00000000..7df352f9 --- /dev/null +++ b/examples/random/chacha.h @@ -0,0 +1,196 @@ +#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 = NULL; + u8 tmp[64]; + u_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/examples/random/random.tm b/examples/random/random.tm new file mode 100644 index 00000000..7db02016 --- /dev/null +++ b/examples/random/random.tm @@ -0,0 +1,240 @@ +# Random Number Generator (RNG) implementation based on ChaCha + +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 inline C : 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; + } + +default_random := RandomNumberGenerator.new() + +func _os_random_bytes(count:Int64 -> [Byte]): + return inline C : [Byte] { + uint8_t *random_bytes = GC_MALLOC_ATOMIC(_$count); + getrandom(random_bytes, _$count, 0); + (Array_t){.length=_$count, .data=random_bytes, .stride=1, .atomic=1}; + } + +struct RandomNumberGenerator(_chacha:chacha_ctx, _random_bytes=[:Byte]; secret): + func new(seed=none:[Byte], -> @RandomNumberGenerator): + ctx := chacha_ctx.from_seed(seed or _os_random_bytes(40)) + return @RandomNumberGenerator(ctx, [:Byte]) + + func _rekey(rng:&RandomNumberGenerator): + rng._random_bytes = inline C : [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); + Array_t new_bytes = (Array_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): + inline C { + while (_$needed > 0) { + if (_$rng->_random_bytes.length == 0) + _$random$RandomNumberGenerator$_rekey(_$rng); + + 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]): + return inline C : [Byte] { + int64_t count64 = Int64$from_int(_$count, false); + Array_t ret = {.data=GC_MALLOC_ATOMIC(count64), .stride=1, .atomic=1, .length=count64}; + _$random$RandomNumberGenerator$_fill_bytes(_$rng, ret.data, count64); + ret; + } + + func byte(rng:&RandomNumberGenerator -> Byte): + return inline C : Byte { + Byte_t b; + _$random$RandomNumberGenerator$_fill_bytes(_$rng, &b, sizeof(b)); + b; + } + + 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 + if min == Int64.min and max == Int64.max: + return inline C : Int64 { + int64_t i; + _$random$RandomNumberGenerator$_fill_bytes(_$rng, &i, sizeof(i)); + i; + } + + return inline C : Int64 { + uint64_t range = (uint64_t)_$max - (uint64_t)_$min + 1; + uint64_t min_r = -range % range; + uint64_t r; + for (;;) { + _$random$RandomNumberGenerator$_fill_bytes(_$rng, (uint8_t*)&r, sizeof(r)); + 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 + if min == Int32.min and max == Int32.max: + return inline C : Int32 { + int32_t i; + _$random$RandomNumberGenerator$_fill_bytes(_$rng, &i, sizeof(i)); + i; + } + + return inline C : Int32 { + uint32_t range = (uint32_t)_$max - (uint32_t)_$min + 1; + uint32_t min_r = -range % range; + uint32_t r; + for (;;) { + _$random$RandomNumberGenerator$_fill_bytes(_$rng, (uint8_t*)&r, sizeof(r)); + 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 + if min == Int16.min and max == Int16.max: + return inline C : Int16 { + int16_t i; + _$random$RandomNumberGenerator$_fill_bytes(_$rng, &i, sizeof(i)); + i; + } + + return inline C : Int16 { + uint16_t range = (uint16_t)_$max - (uint16_t)_$min + 1; + uint16_t min_r = -range % range; + uint16_t r; + for (;;) { + _$random$RandomNumberGenerator$_fill_bytes(_$rng, (uint8_t*)&r, sizeof(r)); + 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 + if min == Int8.min and max == Int8.max: + return inline C : Int8 { + int8_t i; + _$random$RandomNumberGenerator$_fill_bytes(_$rng, &i, sizeof(i)); + i; + } + + return inline C : Int8 { + uint8_t range = (uint8_t)_$max - (uint8_t)_$min + 1; + uint8_t min_r = -range % range; + uint8_t r; + for (;;) { + _$random$RandomNumberGenerator$_fill_bytes(_$rng, (uint8_t*)&r, sizeof(r)); + if (r >= min_r) break; + } + (int8_t)((uint8_t)_$min + (r % range)); + } + + func num(rng:&RandomNumberGenerator, min=0., max=1. -> Num): + return inline C : 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}; + _$random$RandomNumberGenerator$_fill_bytes(_$rng, (uint8_t*)&r, sizeof(r)); + + // 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 inline C : Int { + if (likely(((_$min.small & _$max.small) & 1) != 0)) { + int32_t r = _$random$RandomNumberGenerator$int32(_$rng, (int32_t)(_$min.small >> 2), (int32_t)(_$max.small >> 2)); + return I_small(r); + } + + int32_t cmp = Int$compare_value(_$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 = _$random$RandomNumberGenerator$int64(_$rng, INT64_MIN, INT64_MAX); + 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/examples/random/sysrandom.h b/examples/random/sysrandom.h new file mode 100644 index 00000000..ea29296b --- /dev/null +++ b/examples/random/sysrandom.h @@ -0,0 +1,14 @@ +#pragma once + +#if defined(__FreeBSD__) || defined(__OpenBSD__) || defined(__NetBSD__) || defined(__APPLE__) +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 |