Unsigned 128-bit integer operations

Module miden::core::math::u128 contains a set of procedures which can be used to perform unsigned 128-bit integer operations. These operations fall into the following categories:

• Arithmetic operations - addition, subtraction, multiplication, division.
• Comparison operations - equality, less than, greater than etc.
• Bitwise operations - binary AND, OR, XOR, NOT, bit shifts and rotations, leading/trailing zero/one counts.

When placed on the stack, a 128-bit integer is encoded using four 32-bit limbs (elements) in little-endian limb order: the least-significant limb is on top of the stack. For example, a u128 value a with limbs a0..a3 would be positioned on the stack like so:

[a0, a1, a2, a3, ...]

where a0 is the least-significant 32-bit limb and a3 is the most significant.

The procedures in this module assume that the input values are represented using valid 32-bit limbs, but this is not checked. Using invalid inputs may produce undefined results.

Arithmetic operations

Procedure	Description
wrapping_add	Performs addition of two unsigned 128-bit integers discarding the overflow. Stack transition: [b0..b3, a0..a3, ...] -> [c0..c3, ...] where c = (a + b) % 2^128
overflowing_add	Performs addition of two unsigned 128-bit integers preserving the overflow. Stack transition: [b0..b3, a0..a3, ...] -> [overflow, c0..c3, ...] where c = (a + b) % 2^128
widening_add	Performs addition of two unsigned 128-bit integers preserving the overflow with sum on top. Stack transition: [b0..b3, a0..a3, ...] -> [c0..c3, overflow, ...] where c = (a + b) % 2^128
wrapping_sub	Performs subtraction of two unsigned 128-bit integers discarding the underflow. Stack transition: [b0..b3, a0..a3, ...] -> [c0..c3, ...] where c = (a - b) % 2^128
overflowing_sub	Performs subtraction of two unsigned 128-bit integers preserving the underflow. Stack transition: [b0..b3, a0..a3, ...] -> [underflow, c0..c3, ...] where c = (a - b) % 2^128
wrapping_mul	Performs multiplication of two unsigned 128-bit integers discarding the overflow. Stack transition: [b0..b3, a0..a3, ...] -> [c0..c3, ...] where c = (a * b) % 2^128
overflowing_mul	Performs multiplication of two unsigned 128-bit integers preserving the overflow. Stack transition: [b0..b3, a0..a3, ...] -> [overflow, c0..c3, ...] where c = (a * b) % 2^128
widening_mul	Performs multiplication of two unsigned 128-bit integers preserving the overflow with sum on top. Stack transition: [b0..b3, a0..a3, ...] -> [c0..c3, overflow, ...] where c = (a * b) % 2^128
div	Performs division of two unsigned 128-bit integers discarding the remainder. Stack transition: [b0..b3, a0..a3, ...] -> [q0..q3, ...] where q = a / b. Fails if b = 0.
mod	Performs modulo operation of two unsigned 128-bit integers. Stack transition: [b0..b3, a0..a3, ...] -> [r0..r3, ...] where r = a % b. Fails if b = 0.
divmod	Performs divmod operation of two unsigned 128-bit integers. Stack transition: [b0..b3, a0..a3, ...] -> [r0..r3, q0..q3, ...] where q = a / b, r = a % b. Fails if b = 0.

Comparison operations

Procedure	Description
eq	Performs equality comparison of two unsigned 128-bit integers. Stack transition: [b0..b3, a0..a3, ...] -> [c, ...] where c = 1 when a == b, and 0 otherwise.
neq	Performs inequality comparison of two unsigned 128-bit integers. Stack transition: [b0..b3, a0..a3, ...] -> [c, ...] where c = 1 when a != b, and 0 otherwise.
eqz	Checks if an unsigned 128-bit integer equals zero. Stack transition: [a0..a3, ...] -> [c, ...] where c = 1 when a == 0, and 0 otherwise.
lt	Performs less-than comparison of two unsigned 128-bit integers. Stack transition: [b0..b3, a0..a3, ...] -> [c, ...] where c = 1 when a < b, and 0 otherwise.
gt	Performs greater-than comparison of two unsigned 128-bit integers. Stack transition: [b0..b3, a0..a3, ...] -> [c, ...] where c = 1 when a > b, and 0 otherwise.
lte	Performs less-than-or-equal comparison of two unsigned 128-bit integers. Stack transition: [b0..b3, a0..a3, ...] -> [c, ...] where c = 1 when a <= b, and 0 otherwise.
gte	Performs greater-than-or-equal comparison of two unsigned 128-bit integers. Stack transition: [b0..b3, a0..a3, ...] -> [c, ...] where c = 1 when a >= b, and 0 otherwise.
min	Computes the minimum of two unsigned 128-bit integers. Stack transition: [b0..b3, a0..a3, ...] -> [c0..c3, ...] where c = min(a, b).
max	Computes the maximum of two unsigned 128-bit integers. Stack transition: [b0..b3, a0..a3, ...] -> [c0..c3, ...] where c = max(a, b).

Bitwise operations

Procedure	Description
and	Performs bitwise AND of two unsigned 128-bit integers. Stack transition: [b0..b3, a0..a3, ...] -> [c0..c3, ...] where c = a AND b
or	Performs bitwise OR of two unsigned 128-bit integers. Stack transition: [b0..b3, a0..a3, ...] -> [c0..c3, ...] where c = a OR b
xor	Performs bitwise XOR of two unsigned 128-bit integers. Stack transition: [b0..b3, a0..a3, ...] -> [c0..c3, ...] where c = a XOR b
not	Performs bitwise NOT of an unsigned 128-bit integer. Stack transition: [a0..a3, ...] -> [c0..c3, ...] where c = NOT(a)
shl	Performs left shift of one unsigned 128-bit integer. The shift amount n must be in the range [0, 128), otherwise it will result in an error. Stack transition: [n, a0..a3, ...] -> [c0..c3, ...] where c = (a << n) mod 2^128
shr	Performs right shift of one unsigned 128-bit integer. The shift amount n must be in the range [0, 128), otherwise it will result in an error. Stack transition: [n, a0..a3, ...] -> [c0..c3, ...] where c = a >> n
rotl	Performs left rotation of one unsigned 128-bit integer. The rotation amount n must be in the range [0, 128), otherwise it will result in an error. Stack transition: [n, a0..a3, ...] -> [c0..c3, ...] where c = a rotated left by n bits.
rotr	Performs right rotation of one unsigned 128-bit integer. The rotation amount n must be in the range [0, 128), otherwise it will result in an error. Stack transition: [n, a0..a3, ...] -> [c0..c3, ...] where c = a rotated right by n bits.
clz	Counts the number of leading zeros of an unsigned 128-bit integer. Stack transition: [a0..a3, ...] -> [count, ...] where count is the number of leading zero bits in a (0..=128).
ctz	Counts the number of trailing zeros of an unsigned 128-bit integer. Stack transition: [a0..a3, ...] -> [count, ...] where count is the number of trailing zero bits in a (0..=128).
clo	Counts the number of leading ones of an unsigned 128-bit integer. Stack transition: [a0..a3, ...] -> [count, ...] where count is the number of leading one bits in a (0..=128).
cto	Counts the number of trailing ones of an unsigned 128-bit integer. Stack transition: [a0..a3, ...] -> [count, ...] where count is the number of trailing one bits in a (0..=128).