Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.1

0.6.1 / src / ak / random.lucb

#==============================================================================================
#
#   random - the CSPRNG, uniform integers, random UUIDs and the xorshift128+ generator
#
#   DESCRIPTION:
#       Port of AK/Random.h (lines 1-68) and AK/Random.cpp (lines 1-176). csprng takes the
#       arc4random_buf branch, which covers macOS and glibc 2.36 and later, and the Windows
#       branch through the os module's random_bytes.
#
#==============================================================================================

extern func arc4random_buf(buf: void*, nbytes: usize)

## Ported from AK/Random.cpp:23 csprng.
# We shouldn't use OpenSSL's RAND_bytes function here, because we want to avoid adding dependencies to AK.
# Therefore, we will use the best platform-specific CSPRNG.
pub func csprng(buf: void*?, size: usize) -> !:
    let pointer = buf else return
    if os.windows:
        # Documented to always return TRUE (ProcessPrng, reached through the os module)
        try os.random_bytes(u8[]((u8*)pointer, size))
        return
    # This target also covers MacOS and iOS and they both seem to support arc4random_buf
    arc4random_buf(pointer, size)

## Ported from AK/Random.cpp:56 AK::fill_with_random.
pub func fill_with_random(bytes: u8[]):
    if bytes.length == 0:
        return
    csprng(bytes.data, bytes.length) else trap("MUST: csprng")

## Ported from AK/Random.h:24 AK::get_random.
pub func get_random[T]() -> T:
    var t: T = ---
    fill_with_random(u8[]((u8*)&t, memory.size_of(T)))
    return t

## Ported from AK/Random.cpp:61 AK::get_random_uniform.
pub func get_random_uniform(max_bounds: u32) -> u32:
    # If we try to divide all 2**32 numbers into groups of "max_bounds" numbers, we may end up
    # with a group around 2**32-1 that is a bit too small. For this reason, the implementation
    # `arc4random() % max_bounds` would be insufficient. Here we compute the last number of the
    # last "full group". Note that if max_bounds is a divisor of UINT32_MAX,
    # then we end up with UINT32_MAX:
    let max_usable: u32 = u32_max - (u32)(((u64)u32_max + 1) % (u64)max_bounds)
    var random_value = get_random[u32]()
    var i = 0
    while i < 20 and random_value > max_usable:
        # By chance we picked a value from the incomplete group. Note that this group has size at
        # most 2**31-1, so picking this group has a chance of less than 50%.
        # In practice, this means that for the worst possible input, there is still only a
        # once-in-a-million chance to get to iteration 20. In theory we should be able to loop
        # forever. Here we prefer marginally imperfect random numbers over weird runtime behavior.
        random_value = get_random[u32]()
        i += 1
    return random_value % max_bounds

## Ported from AK/Random.cpp:81 AK::get_random_uniform_64.
pub func get_random_uniform_64(max_bounds: u64) -> u64:
    # Uses the same algorithm as `get_random_uniform`,
    # by replacing u64 with u128 and u32 with u64.
    # (u128(UINT64_MAX) + 1) % max_bounds, computed without a 128-bit type.
    let wrap = ((u64_max % max_bounds) + 1) % max_bounds
    let max_usable = u64_max - wrap
    var random_value = get_random[u64]()
    var i = 0
    while i < 20 and random_value > max_usable:
        random_value = get_random[u64]()
        i += 1
    return random_value % max_bounds

# The lowercase hexadecimal digits of `{:02x}`.
let random_hex_digits: u8[16] = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f']

## Ported from AK/Random.cpp:94 AK::generate_random_uuid.
# https://w3c.github.io/webcrypto/#dfn-generate-a-random-uuid
pub func generate_random_uuid() -> String:
    # 1. Let bytes be a byte sequence of length 16.
    var bytes: u8[16]

    # 2. Fill bytes with cryptographically secure random bytes.
    fill_with_random(bytes)

    # 3. Set the 4 most significant bits of bytes[6], which represent the UUID version, to 0100.
    bytes[6] = (bytes[6] & 0x0f) | 0x40

    # 4. Set the 2 most significant bits of bytes[8], which represent the UUID variant, to 10.
    bytes[8] = (bytes[8] & 0x3f) | 0x80

    # 5. Return the string concatenation of «
    #     hexadecimal representation of bytes[0], ... bytes[3], "-", bytes[4], bytes[5], "-",
    #     bytes[6], bytes[7], "-", bytes[8], bytes[9], "-", bytes[10], ... bytes[15]
    # ».
    var text: u8[36]
    format_uuid(bytes, text)
    return string_from_utf8_without_validation(text)

# String::formatted("{:02x}{:02x}{:02x}{:02x}-{:02x}{:02x}-{:02x}{:02x}-{:02x}{:02x}-{:02x}...", bytes...).
func format_uuid(bytes: const u8[], text: u8[]):
    var position: usize = 0
    for i in 0..<16usize:
        if i == 4 or i == 6 or i == 8 or i == 10:
            text[position] = '-'
            position += 1
        text[position] = random_hex_digits[bytes[i] >> 4]
        text[position + 1] = random_hex_digits[bytes[i] & 0xf]
        position += 2

## Ported from AK/Random.h:50 AK::shuffle, over a span.
pub func shuffle[T](collection: T[]):
    # Fisher-Yates shuffle
    var i = collection.length -% 1
    while i >= 1:
        let j: usize = get_random_uniform((u32)(i + 1))
        swap_5(&collection[i], &collection[j])
        i -= 1

## Ported from AK/Random.cpp:139 AK::XorShift128PlusRNG::XorShift128PlusRNG.
pub func xor_shift128_plus_rng_construct(this: XorShift128PlusRng*):
    # Splitmix64 is used as xorshift is sensitive to being seeded with all 0s
    var seed = get_random[u64]()
    this.m_low = xor_shift128_plus_rng_splitmix64(this, &seed)
    seed = get_random[u64]()
    this.m_high = xor_shift128_plus_rng_splitmix64(this, &seed)

## Ported from AK/Random.cpp:148 AK::XorShift128PlusRNG::get.
pub func xor_shift128_plus_rng_get(this: XorShift128PlusRng*) -> f64:
    let value = xor_shift128_plus_rng_advance(this) & (((u64)1 << 53) - 1)
    return f64(value) * (1.0 / f64((u64)1 << 53))

## Ported from AK/Random.cpp:154 AK::XorShift128PlusRNG::splitmix64.
pub func xor_shift128_plus_rng_splitmix64(this: XorShift128PlusRng*, state: u64*) -> u64:
    _ = this
    *state = *state +% 0x9e3779b97f4a7c15
    var z = *state
    z = (z ^ (z >> 30)) *% 0xbf58476d1ce4e5b9
    z = (z ^ (z >> 27)) *% 0x94d049bb133111eb
    return z ^ (z >> 31)

## Ported from AK/Random.cpp:163 AK::XorShift128PlusRNG::advance.
# Apparently this set of constants is better: https://stackoverflow.com/a/34432126
pub func xor_shift128_plus_rng_advance(this: XorShift128PlusRng*) -> u64:
    var s1 = this.m_low
    let s0 = this.m_high
    let result = s0 +% s1
    this.m_low = s0
    s1 = s1 ^ (s1 << 23)
    s1 = s1 ^ (s1 >> 18)
    s1 = s1 ^ (s0 ^ (s0 >> 5))
    this.m_high = s1
    return result +% s1