1 files changed, 287 insertions, 0 deletions
diff --git a/backend/src/lib/nanoid.zig b/backend/src/lib/nanoid.zig
new file mode 100644
index 0000000..64ab9bd
--- /dev/null
+++ b/backend/src/lib/nanoid.zig
@@ -0,0 +1,287 @@
+// Copied from:
+// https://github.com/SasLuca/zig-nanoid/blob/91e0a9a8890984f3dcdd98c99002a05a83d0ee89/src/nanoid.zig
+// As it doesn’t support ZON build yet.
+
+const std = @import("std");
+
+/// A collection of useful alphabets that can be used to generate ids.
+pub const alphabets = struct {
+    /// Numbers from 0 to 9.
+    pub const numbers = "0123456789";
+
+    /// English hexadecimal with lowercase characters.
+    pub const hexadecimal_lowercase = numbers ++ "abcdef";
+
+    /// English hexadecimal with uppercase characters.
+    pub const hexadecimal_uppercase = numbers ++ "ABCDEF";
+
+    /// Lowercase English letters.
+    pub const lowercase = "abcdefghijklmnopqrstuvwxyz";
+
+    /// Uppercase English letters.
+    pub const uppercase = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+
+    /// Numbers and english letters without lookalikes: 1, l, I, 0, O, o, u, v, 5, S, s, 2, Z.
+    pub const no_look_alikes = "346789ABCDEFGHJKLMNPQRTUVWXYabcdefghijkmnpqrtwxyz";
+
+    /// Same as nolookalikes but with removed vowels and following letters: 3, 4, x, X, V.
+    /// This list should protect you from accidentally getting obscene words in generated strings.
+    pub const no_look_alikes_safe = "6789BCDFGHJKLMNPQRTWbcdfghjkmnpqrtwz";
+
+    /// Combination of all the lowercase, uppercase characters and numbers from 0 to 9.
+    /// Does not include any symbols or special characters.
+    pub const alphanumeric = numbers ++ lowercase ++ uppercase;
+
+    /// URL friendly characters used by the default generate procedure.
+    pub const default = "_-" ++ alphanumeric;
+
+    /// An array of all the alphabets.
+    pub const all = [_][]const u8{
+        numbers,
+        hexadecimal_lowercase,
+        hexadecimal_uppercase,
+        lowercase,
+        uppercase,
+        no_look_alikes,
+        no_look_alikes_safe,
+        alphanumeric,
+        default,
+    };
+};
+
+/// The default length for nanoids.
+pub const default_id_len = 21;
+
+/// The mask for the default alphabet length.
+pub const default_mask = computeMask(alphabets.default.len);
+
+/// This should be enough memory for an rng step buffer when generating an id of default length regardless of alphabet length.
+/// It can be used for allocating your rng step buffer if you know the length of your id is `<= default_id_len`.
+pub const rng_step_buffer_len_sufficient_for_default_length_ids = computeSufficientRngStepBufferLengthFor(default_id_len);
+
+/// The maximum length of the alphabet accepted by the nanoid algorithm.
+pub const max_alphabet_len: u8 = std.math.maxInt(u8);
+
+/// Computes the mask necessary for the nanoid algorithm given an alphabet length.
+/// The mask is used to transform a random byte into an index into an array of length `alphabet_len`.
+///
+/// Parameters:
+/// - `alphabet_len`: the length of the alphabet used. The alphabet length must be in the range `(0, max_alphabet_len]`.
+pub fn computeMask(alphabet_len: u8) u8 {
+    std.debug.assert(alphabet_len > 0);
+
+    const clz: u5 = @clz(@as(u31, (alphabet_len - 1) | 1));
+    const mask = (@as(u32, 2) << (31 - clz)) - 1;
+    const result: u8 = @truncate(mask);
+    return result;
+}
+
+/// Computes the length necessary for a buffer which can hold the random byte in a step of a the nanoid generation algorithm given a
+/// certain alphabet length.
+///
+/// Parameters:
+/// - `id_len`: the length of the id you will generate. Can be any value.
+///
+/// - `alphabet_len`: the length of the alphabet used. The alphabet length must be in the range `(0, max_alphabet_len]`.
+pub fn computeRngStepBufferLength(id_len: usize, alphabet_len: u8) usize {
+    // @Note:
+    // Original dev notes regarding this algorithm.
+    // Source: https://github.com/ai/nanoid/blob/0454333dee4612d2c2e163d271af6cc3ce1e5aa4/index.js#L45
+    //
+    // "Next, a step determines how many random bytes to generate.
+    // The number of random bytes gets decided upon the ID length, mask,
+    // alphabet length, and magic number 1.6 (using 1.6 peaks at performance
+    // according to benchmarks)."
+
+    const id_len_f: f64 = @as(f64, @floatFromInt(id_len));
+    const mask_f: f64 = @as(f64, @floatFromInt(computeMask(alphabet_len)));
+    const alphabet_len_f: f64 = @as(f64, @floatFromInt(alphabet_len));
+    const step_buffer_len: f64 = @ceil(1.6 * mask_f * id_len_f / alphabet_len_f);
+    const result = @as(usize, @intFromFloat(step_buffer_len));
+
+    return result;
+}
+
+/// This function computes the biggest possible rng step buffer length necessary
+/// to compute an id with a max length of `max_id_len` regardless of the alphabet length.
+///
+/// Parameters:
+/// - `max_id_len`: The biggest id length for which the step buffer length needs to be sufficient.
+pub fn computeSufficientRngStepBufferLengthFor(max_id_len: usize) usize {
+    @setEvalBranchQuota(2500);
+    var max_step_buffer_len: usize = 0;
+    var i: u9 = 1;
+    while (i <= max_alphabet_len) : (i += 1) {
+        const alphabet_len: u8 = @truncate(i);
+        const step_buffer_len = computeRngStepBufferLength(max_id_len, alphabet_len);
+
+        if (step_buffer_len > max_step_buffer_len) {
+            max_step_buffer_len = step_buffer_len;
+        }
+    }
+
+    return max_step_buffer_len;
+}
+
+/// Generates a nanoid inside `result_buffer` and returns it back to the caller.
+///
+/// Parameters:
+/// - `rng`: a random number generator.
+///    Provide a secure one such as `std.Random.DefaultCsprng` and seed it properly if you have security concerns.
+///    See `Regarding RNGs` in `readme.md` for more information.
+///
+/// - `alphabet`: an array of the bytes that will be used in the id, its length must be in the range `(0, max_alphabet_len]`.
+///    Consider the options from `nanoid.alphabets`.
+///
+/// - `result_buffer`: is an output buffer that will be filled *completely* with random bytes from `alphabet`, thus generating an id of
+///    length `result_buffer.len`. This buffer will be returned at the end of the function.
+///
+/// - `step_buffer`: The buffer will be filled with random bytes using `rng.bytes()`.
+///    Must be at least `computeRngStepBufferLength(computeMask(@truncate(alphabet.len)), result_buffer.len, alphabet.len)` bytes.
+pub fn generateEx(rng: std.Random, alphabet: []const u8, result_buffer: []u8, step_buffer: []u8) []u8 {
+    std.debug.assert(alphabet.len > 0 and alphabet.len <= max_alphabet_len);
+
+    const alphabet_len: u8 = @truncate(alphabet.len);
+    const mask = computeMask(alphabet_len);
+    const necessary_step_buffer_len = computeRngStepBufferLength(result_buffer.len, alphabet_len);
+    const actual_step_buffer = step_buffer[0..necessary_step_buffer_len];
+
+    var result_iter: usize = 0;
+    while (true) {
+        rng.bytes(actual_step_buffer);
+
+        for (actual_step_buffer) |it| {
+            const alphabet_index = it & mask;
+
+            if (alphabet_index >= alphabet_len) {
+                continue;
+            }
+
+            result_buffer[result_iter] = alphabet[alphabet_index];
+
+            if (result_iter == result_buffer.len - 1) {
+                return result_buffer;
+            } else {
+                result_iter += 1;
+            }
+        }
+    }
+}
+
+/// Generates a nanoid inside `result_buffer` and returns it back to the caller.
+///
+/// This function will use `rng.int` instead of `rng.bytes` thus avoiding the need for a step buffer.
+/// Depending on your choice of rng this can be useful, since you avoid the need for a step buffer,
+/// but repeated calls to `rng.int` might be slower than a single call `rng.bytes`.
+///
+/// Parameters:
+/// - `rng`: a random number generator.
+///    Provide a secure one such as `std.Random.DefaultCsprng` and seed it properly if you have security concerns.
+///    See `Regarding RNGs` in `readme.md` for more information.
+///
+/// - `alphabet`: an array of the bytes that will be used in the id, its length must be in the range `(0, max_alphabet_len]`.
+///    Consider the options from `nanoid.alphabets`.
+///
+/// - `result_buffer` is an output buffer that will be filled *completely* with random bytes from `alphabet`, thus generating an id of
+///    length `result_buffer.len`. This buffer will be returned at the end of the function.
+pub fn generateExWithIterativeRng(rng: std.Random, alphabet: []const u8, result_buffer: []u8) []u8 {
+    std.debug.assert(result_buffer.len > 0);
+    std.debug.assert(alphabet.len > 0 and alphabet.len <= max_alphabet_len);
+
+    const alphabet_len: u8 = @truncate(alphabet.len);
+    const mask = computeMask(alphabet_len);
+
+    var result_iter: usize = 0;
+    while (true) {
+        const random_byte = rng.int(u8);
+
+        const alphabet_index = random_byte & mask;
+
+        if (alphabet_index >= alphabet_len) {
+            continue;
+        }
+
+        result_buffer[result_iter] = alphabet[alphabet_index];
+
+        if (result_iter == result_buffer.len - 1) {
+            return result_buffer;
+        } else {
+            result_iter += 1;
+        }
+    }
+
+    return result_buffer;
+}
+
+/// Generates a nanoid using the provided alphabet.
+///
+/// Parameters:
+///
+/// - `rng`: a random number generator.
+///    Provide a secure one such as `std.Random.DefaultCsprng` and seed it properly if you have security concerns.
+///    See `Regarding RNGs` in `README.md` for more information.
+///
+/// - `alphabet`: an array of the bytes that will be used in the id, its length must be in the range `(0, max_alphabet_len]`.
+pub fn generateWithAlphabet(rng: std.Random, alphabet: []const u8) [default_id_len]u8 {
+    var nanoid: [default_id_len]u8 = undefined;
+    var step_buffer: [rng_step_buffer_len_sufficient_for_default_length_ids]u8 = undefined;
+    _ = generateEx(rng, alphabet, &nanoid, &step_buffer);
+    return nanoid;
+}
+
+/// Generates a nanoid using the default alphabet.
+///
+/// Parameters:
+///
+/// - `rng`: a random number generator.
+///    Provide a secure one such as `std.Random.DefaultCsprng` and seed it properly if you have security concerns.
+///    See `Regarding RNGs` in `README.md` for more information.
+pub fn generate(rng: std.Random) [default_id_len]u8 {
+    const result = generateWithAlphabet(rng, alphabets.default);
+    return result;
+}
+
+/// Non public utility functions used mostly in unit tests.
+const internal_utils = struct {
+    fn makeDefaultCsprng() std.Random.DefaultCsprng {
+        // Generate seed
+        var seed: [std.Random.DefaultCsprng.secret_seed_length]u8 = undefined;
+        std.crypto.random.bytes(&seed);
+
+        // Initialize the rng and allocator
+        const rng = std.Random.DefaultCsprng.init(seed);
+        return rng;
+    }
+
+    fn makeDefaultPrngWithConstantSeed() std.Random.DefaultPrng {
+        const rng = std.Random.DefaultPrng.init(0);
+        return rng;
+    }
+
+    fn makeDefaultCsprngWithConstantSeed() std.Random.DefaultCsprng {
+        // Generate seed
+        const seed: [std.Random.DefaultCsprng.secret_seed_length]u8 = undefined;
+        for (seed) |*it| it.* = 'a';
+
+        // Initialize the rng and allocator
+        const rng = std.Random.DefaultCsprng.init(seed);
+        return rng;
+    }
+
+    /// Taken from https://github.com/codeyu/nanoid-net/blob/445f4d363e0079e151ea414dab1a9f9961679e7e/test/Nanoid.Test/NanoidTest.cs#L145
+    fn toBeCloseTo(actual: f64, expected: f64, precision: f64) bool {
+        const pass = @abs(expected - actual) < std.math.pow(f64, 10, -precision) / 2;
+        return pass;
+    }
+
+    /// Checks if all elements in `array` are present in `includedIn`.
+    fn allIn(comptime T: type, array: []const T, includedIn: []const T) bool {
+        for (array) |it| {
+            if (std.mem.indexOfScalar(u8, includedIn, it) == null) {
+                return false;
+            }
+        }
+
+        return true;
+    }
+};