Uint

pub fn Uint(comptime max_bits: comptime_int) type {
    comptime assert(@bitSizeOf(Limb) % 8 == 0); // Limb size must be a multiple of 8

    return struct {
        const Self = @This();
        const max_limbs_count = @divCeil(max_bits, t_bits);

        limbs_buffer: [max_limbs_count]Limb,
        /// The number of active limbs.
        limbs_len: usize,

        /// Number of bytes required to serialize an integer.
        pub const encoded_bytes = @divCeil(max_bits, 8);

        /// Constant slice of active limbs.
        fn limbsConst(self: *const Self) []const Limb {
            return self.limbs_buffer[0..self.limbs_len];
        }

        /// Mutable slice of active limbs.
        fn limbs(self: *Self) []Limb {
            return self.limbs_buffer[0..self.limbs_len];
        }

        // Removes limbs whose value is zero from the active limbs.
        fn normalize(self: Self) Self {
            var res = self;
            if (self.limbs_len < 2) {
                return res;
            }
            var i = self.limbs_len - 1;
            while (i > 0 and res.limbsConst()[i] == 0) : (i -= 1) {}
            res.limbs_len = i + 1;
            assert(res.limbs_len <= res.limbs_buffer.len);
            return res;
        }

        /// The zero integer.
        pub const zero: Self = .{
            .limbs_buffer = @splat(0),
            .limbs_len = max_limbs_count,
        };

        /// Creates a new big integer from a primitive type.
        /// This function may not run in constant time.
        pub fn fromPrimitive(comptime T: type, init_value: T) OverflowError!Self {
            var x = init_value;
            var out: Self = .{
                .limbs_buffer = undefined,
                .limbs_len = max_limbs_count,
            };
            for (&out.limbs_buffer) |*limb| {
                limb.* = if (@bitSizeOf(T) > t_bits) @as(TLimb, @truncate(x)) else x;
                x = math.shr(T, x, t_bits);
            }
            if (x != 0) {
                return error.Overflow;
            }
            return out;
        }

        /// Converts a big integer to a primitive type.
        /// This function may not run in constant time.
        pub fn toPrimitive(self: Self, comptime T: type) OverflowError!T {
            var x: T = 0;
            var i = self.limbs_len - 1;
            while (true) : (i -= 1) {
                if (@bitSizeOf(T) >= t_bits and math.shr(T, x, @bitSizeOf(T) - t_bits) != 0) {
                    return error.Overflow;
                }
                x = math.shl(T, x, t_bits);
                const v = math.cast(T, self.limbsConst()[i]) orelse return error.Overflow;
                x |= v;
                if (i == 0) break;
            }
            return x;
        }

        /// Encodes a big integer into a byte array.
        pub fn toBytes(self: Self, bytes: []u8, comptime endian: Endian) OverflowError!void {
            if (bytes.len == 0) {
                if (self.isZero()) return;
                return error.Overflow;
            }
            @memset(bytes, 0);
            var shift: usize = 0;
            var out_i: usize = switch (endian) {
                .big => bytes.len - 1,
                .little => 0,
            };
            for (0..self.limbs_len) |i| {
                var remaining_bits = t_bits;
                var limb = self.limbsConst()[i];
                while (remaining_bits >= 8) {
                    bytes[out_i] |= math.shl(u8, @as(u8, @truncate(limb)), shift);
                    const consumed = 8 - shift;
                    limb >>= @as(u4, @truncate(consumed));
                    remaining_bits -= consumed;
                    shift = 0;
                    switch (endian) {
                        .big => {
                            if (out_i == 0) {
                                if (i != self.limbs_len - 1 or limb != 0) {
                                    return error.Overflow;
                                }
                                return;
                            }
                            out_i -= 1;
                        },
                        .little => {
                            out_i += 1;
                            if (out_i == bytes.len) {
                                if (i != self.limbs_len - 1 or limb != 0) {
                                    return error.Overflow;
                                }
                                return;
                            }
                        },
                    }
                }
                bytes[out_i] |= @as(u8, @truncate(limb));
                shift = remaining_bits;
            }
        }

        /// Creates a new big integer from a byte array.
        pub fn fromBytes(bytes: []const u8, comptime endian: Endian) OverflowError!Self {
            if (bytes.len == 0) return Self.zero;
            var shift: usize = 0;
            var out = Self.zero;
            var out_i: usize = 0;
            var i: usize = switch (endian) {
                .big => bytes.len - 1,
                .little => 0,
            };
            while (true) {
                const bi = bytes[i];
                out.limbs()[out_i] |= math.shl(Limb, bi, shift);
                shift += 8;
                if (shift >= t_bits) {
                    shift -= t_bits;
                    out.limbs()[out_i] = @as(TLimb, @truncate(out.limbs()[out_i]));
                    const overflow = math.shr(Limb, bi, 8 - shift);
                    out_i += 1;
                    if (out_i >= out.limbs_len) {
                        if (overflow != 0 or i != 0) {
                            return error.Overflow;
                        }
                        break;
                    }
                    out.limbs()[out_i] = overflow;
                }
                switch (endian) {
                    .big => {
                        if (i == 0) break;
                        i -= 1;
                    },
                    .little => {
                        i += 1;
                        if (i == bytes.len) break;
                    },
                }
            }
            return out;
        }

        /// Returns `true` if both integers are equal.
        pub fn eql(x: Self, y: Self) bool {
            return crypto.timing_safe.eql([max_limbs_count]Limb, x.limbs_buffer, y.limbs_buffer);
        }

        /// Compares two integers.
        pub fn compare(x: Self, y: Self) math.Order {
            return crypto.timing_safe.compare(
                Limb,
                x.limbsConst(),
                y.limbsConst(),
                .little,
            );
        }

        /// Returns `true` if the integer is zero.
        pub fn isZero(x: Self) bool {
            var t: Limb = 0;
            for (x.limbsConst()) |elem| {
                t |= elem;
            }
            return ct.eql(t, 0);
        }

        /// Returns `true` if the integer is odd.
        pub fn isOdd(x: Self) bool {
            return @as(u1, @truncate(x.limbsConst()[0])) != 0;
        }

        /// Adds `y` to `x`, and returns `true` if the operation overflowed.
        pub fn addWithOverflow(x: *Self, y: Self) u1 {
            return x.conditionalAddWithOverflow(true, y);
        }

        /// Subtracts `y` from `x`, and returns `true` if the operation overflowed.
        pub fn subWithOverflow(x: *Self, y: Self) u1 {
            return x.conditionalSubWithOverflow(true, y);
        }

        // Replaces the limbs of `x` with the limbs of `y` if `on` is `true`.
        fn cmov(x: *Self, on: bool, y: Self) void {
            for (x.limbs(), y.limbsConst()) |*x_limb, y_limb| {
                x_limb.* = ct.select(on, y_limb, x_limb.*);
            }
        }

        // Adds `y` to `x` if `on` is `true`, and returns `true` if the
        // operation overflowed.
        fn conditionalAddWithOverflow(x: *Self, on: bool, y: Self) u1 {
            var carry: u1 = 0;
            for (x.limbs(), y.limbsConst()) |*x_limb, y_limb| {
                const res = x_limb.* + y_limb + carry;
                x_limb.* = ct.select(on, @as(TLimb, @truncate(res)), x_limb.*);
                carry = @truncate(res >> t_bits);
            }
            return carry;
        }

        // Subtracts `y` from `x` if `on` is `true`, and returns `true` if the
        // operation overflowed.
        fn conditionalSubWithOverflow(x: *Self, on: bool, y: Self) u1 {
            var borrow: u1 = 0;
            for (x.limbs(), y.limbsConst()) |*x_limb, y_limb| {
                const res = x_limb.* -% y_limb -% borrow;
                x_limb.* = ct.select(on, @as(TLimb, @truncate(res)), x_limb.*);
                borrow = @truncate(res >> t_bits);
            }
            return borrow;
        }
    };
}