Uint
An unsigned big integer with a fixed maximum size (max_bits), suitable for cryptographic operations.
Unless side-channels mitigations are explicitly disabled, operations are designed to be constant-time.
Fields of this type
Fields
- limbs_buffer:[max_limbs_count]Limb
- limbs_len:usize
- The number of active limbs.
Creates a new big integer from a primitive type.
Functions
- fromPrimitive
- Creates a new big integer from a primitive type.
- toPrimitive
- Converts a big integer to a primitive type.
- toBytes
- Encodes a big integer into a byte array.
- fromBytes
- Creates a new big integer from a byte array.
- eql
- Returns `true` if both integers are equal.
- compare
- Compares two integers.
- isZero
- Returns `true` if the integer is zero.
- isOdd
- Returns `true` if the integer is odd.
- addWithOverflow
- Adds `y` to `x`, and returns `true` if the operation overflowed.
- subWithOverflow
- Subtracts `y` from `x`, and returns `true` if the operation overflowed.
Number of bytes required to serialize an integer.
Values
- encoded_bytes
- Number of bytes required to serialize an integer.
- zero
- The zero integer.
Source
Implementation
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 = math.divCeil(usize, max_bits, t_bits) catch unreachable;
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 = math.divCeil(usize, max_bits, 8) catch unreachable;
/// 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 = [1]Limb{0} ** max_limbs_count,
.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;
}
};
}