Unsigned 64-bit integer operations

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

• Arithmetic operations - addition, multiplication, division etc.
• Comparison operations - equality, less than, greater than etc.
• Bitwise operations - binary AND, OR, XOR, bit shifts etc.

All procedures assume that an unsigned 64-bit integer (u64) is encoded using two elements, each containing an unsigned 32-bit integer (u32). When placed on the stack, the least-significant limb is at the top (little-endian convention). For example, a u64 value a consisting of limbs a_hi and a_lo would be positioned on the stack like so:

[a_lo, a_hi, ... ]

Many of the procedures listed below (e.g., overflowing_add, wrapping_add, lt) do not check whether the inputs are encoded using valid u32 values. These procedures do not fail when the inputs are encoded incorrectly, but rather produce undefined results. Thus, it is important to be certain that limbs of input values are valid u32 values prior to calling such procedures.

Arithmetic operations

Procedure	Description
overflowing_add	Performs addition of two unsigned 64-bit integers preserving the overflow. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [overflow, c_lo, c_hi, ...], where c = (a + b) % 2^64. This takes 5 cycles.
widening_add	Performs addition of two unsigned 64-bit integers preserving the overflow, with sum on top. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c_lo, c_hi, overflow, ...], where c = (a + b) % 2^64. This takes 6 cycles.
wrapping_add	Performs addition of two unsigned 64-bit integers discarding the overflow. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c_lo, c_hi, ...], where c = (a + b) % 2^64. This takes 6 cycles.
overflowing_sub	Performs subtraction of two unsigned 64-bit integers preserving the overflow. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [underflow, c_lo, c_hi, ...], where c = (a - b) % 2^64. This takes 15 cycles.
wrapping_sub	Performs subtraction of two unsigned 64-bit integers discarding the overflow. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c_lo, c_hi, ...], where c = (a - b) % 2^64. This takes 11 cycles.
widening_mul	Performs multiplication of two unsigned 64-bit integers preserving the overflow as a 128-bit result. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c_lo, c_mid_lo, c_mid_hi, c_hi, ...], where c = a * b is represented as a 128-bit value split into 4 32-bit limbs. This takes 22 cycles.
wrapping_mul	Performs multiplication of two unsigned 64-bit integers discarding the overflow. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c_lo, c_hi, ...], where c = (a * b) % 2^64. This takes 15 cycles.
div	Performs division of two unsigned 64-bit integers discarding the remainder. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c_lo, c_hi, ...], where c = a // b. This takes 56 cycles.
mod	Performs modulo operation of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c_lo, c_hi, ...], where c = a % b. This takes 58 cycles.
divmod	Performs divmod operation of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [r_lo, r_hi, q_lo, q_hi, ...], where q = a // b, r = a % b. This takes 54 cycles.

Comparison operations

Procedure	Description
lt	Performs less-than comparison of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c, ...], where c = 1 when a < b, and 0 otherwise. This takes 12 cycles.
gt	Performs greater-than comparison of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c, ...], where c = 1 when a > b, and 0 otherwise. This takes 13 cycles.
lte	Performs less-than-or-equal comparison of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c, ...], where c = 1 when a <= b, and 0 otherwise. This takes 14 cycles.
gte	Performs greater-than-or-equal comparison of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c, ...], where c = 1 when a >= b, and 0 otherwise. This takes 13 cycles.
eq	Performs equality comparison of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c, ...], where c = 1 when a == b, and 0 otherwise. This takes 5 cycles.
neq	Performs inequality comparison of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c, ...], where c = 1 when a != b, and 0 otherwise. This takes 5 cycles.
eqz	Performs comparison to zero of an unsigned 64-bit integer. The input value is assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [a_lo, a_hi, ...] -> [c, ...], where c = 1 when a == 0, and 0 otherwise. This takes 4 cycles.
min	Compares two unsigned 64-bit integers and drops the larger one from the stack. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c_lo, c_hi, ...], where c = min(a, b). This takes 23 cycles.
max	Compares two unsigned 64-bit integers and drops the smaller one from the stack. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c_lo, c_hi, ...], where c = max(a, b). This takes 24 cycles.

Bitwise operations

Procedure	Description
and	Performs bitwise AND of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c_lo, c_hi, ...], where c = a AND b. This takes 5 cycles.
or	Performs bitwise OR of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c_lo, c_hi, ...], where c = a OR b. This takes 5 cycles.
xor	Performs bitwise XOR of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_lo, b_hi, a_lo, a_hi, ...] -> [c_lo, c_hi, ...], where c = a XOR b. This takes 5 cycles.
shl	Performs left shift of one unsigned 64-bit integer. The input value to be shifted is assumed to be represented using 32-bit limbs, but this is not checked. The shift value n should be in the range [0, 64), otherwise it will result in an error. The stack transition looks as follows: [n, a_lo, a_hi, ...] -> [c_lo, c_hi, ...], where c = (a << n) mod 2^64. This takes 21 cycles.
shr	Performs right shift of one unsigned 64-bit integer. The input value to be shifted is assumed to be represented using 32-bit limbs, but this is not checked. The shift value n should be in the range [0, 64), otherwise it will result in an error. The stack transition looks as follows: [n, a_lo, a_hi, ...] -> [c_lo, c_hi, ...], where c = a >> n. This takes 44 cycles.
rotl	Performs left rotation of one unsigned 64-bit integer. The input value to be rotated is assumed to be represented using 32-bit limbs, but this is not checked. The rotation amount n should be in the range [0, 64), otherwise it will result in an error. The stack transition looks as follows: [n, a_lo, a_hi, ...] -> [c_lo, c_hi, ...], where c = a <<< n (rotate left). This takes 35 cycles.
rotr	Performs right rotation of one unsigned 64-bit integer. The input value to be rotated is assumed to be represented using 32-bit limbs, but this is not checked. The rotation amount n should be in the range [0, 64), otherwise it will result in an error. The stack transition looks as follows: [n, a_lo, a_hi, ...] -> [c_lo, c_hi, ...], where c = a >>> n (rotate right). This takes 44 cycles.
clz	Counts the number of leading zeros of one unsigned 64-bit integer. The input value is assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [n_lo, n_hi, ...] -> [clz, ...], where clz is the number of leading zeros of value n. This takes 48 cycles.
ctz	Counts the number of trailing zeros of one unsigned 64-bit integer. The input value is assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [n_lo, n_hi, ...] -> [ctz, ...], where ctz is the number of trailing zeros of value n. This takes 41 cycles.
clo	Counts the number of leading ones of one unsigned 64-bit integer. The input value is assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [n_lo, n_hi, ...] -> [clo, ...], where clo is the number of leading ones of value n. This takes 47 cycles.
cto	Counts the number of trailing ones of one unsigned 64-bit integer. The input value is assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [n_lo, n_hi, ...] -> [cto, ...], where cto is the number of trailing ones of value n. This takes 40 cycles.