Unsigned 256-bit integer operations
Module miden::core::math::u256 contains a set of procedures which can be used to perform unsigned 256-bit integer operations. These operations fall into the following categories:
- Arithmetic operations - addition, subtraction, multiplication.
- Comparison operations - equality, ordering, min/max.
- Bitwise operations - AND, OR, XOR, NOT.
- Bit counting - leading/trailing zeros and ones.
- Shifts and rotations - shl, shr, rotl, rotr.
A u256 value is represented as a struct with two u128 components:
pub type u256 = struct { lo: u128, hi: u128 }
When placed on the stack, a 256-bit integer is encoded using eight 32-bit limbs (elements) in little-endian limb order: the least-significant limb is on top of the stack. For example, a u256 value a with limbs a0..a7 would be positioned on the stack like so:
[a0, a1, a2, a3, a4, a5, a6, a7, ...]
where a0 is the least-significant 32-bit limb and a7 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 256-bit integers discarding the overflow. Stack transition: [b0..b7, a0..a7, ...] -> [c0..c7, ...]where c = (a + b) % 2^256 |
| overflowing_add | Performs addition of two unsigned 256-bit integers preserving the overflow. Stack transition: [b0..b7, a0..a7, ...] -> [overflow, c0..c7, ...]where c = (a + b) % 2^256 |
| widening_add | Performs addition of two unsigned 256-bit integers preserving the overflow with sum on top. Stack transition: [b0..b7, a0..a7, ...] -> [c0..c7, overflow, ...]where c = (a + b) % 2^256 |
| wrapping_sub | Performs subtraction of two unsigned 256-bit integers discarding the underflow. Stack transition: [b0..b7, a0..a7, ...] -> [c0..c7, ...]where c = (a - b) % 2^256 |
| overflowing_sub | Performs subtraction of two unsigned 256-bit integers preserving the underflow. Stack transition: [b0..b7, a0..a7, ...] -> [underflow, c0..c7, ...]where c = (a - b) % 2^256 |
| wrapping_mul | Performs multiplication of two unsigned 256-bit integers discarding the overflow. Stack transition: [b0..b7, a0..a7, ...] -> [c0..c7, ...]where c = (a * b) % 2^256 |
| overflowing_mul | Performs multiplication of two unsigned 256-bit integers preserving the overflow flag. Stack transition: [b0..b7, a0..a7, ...] -> [overflow, c0..c7, ...]where c = (a * b) % 2^256 and overflow = 1 iff a * b >= 2^256 |
| widening_mul | Performs multiplication of two unsigned 256-bit integers preserving the full 512-bit product. Stack transition: [b0..b7, a0..a7, ...] -> [c0..c15, ...]where c = a * b is a 512-bit value with c0 the least significant 32-bit limb. |
| div | Performs division of two unsigned 256-bit integers discarding the remainder. Stack transition: [b0..b7, a0..a7, ...] -> [q0..q7, ...]where q = a / b. Panics if b == 0. |
| mod | Performs modulo of two unsigned 256-bit integers. Stack transition: [b0..b7, a0..a7, ...] -> [r0..r7, ...]where r = a mod b. Panics if b == 0. |
| divmod | Performs divmod of two unsigned 256-bit integers. Stack transition: [b0..b7, a0..a7, ...] -> [r0..r7, q0..q7, ...]where q = a / b and r = a mod b. Panics if b == 0. |
Comparison operations
| Procedure | Description |
|---|---|
| eq | Checks equality of two unsigned 256-bit integers. Stack transition: [b0..b7, a0..a7, ...] -> [c, ...]where c = 1 when a == b, and 0 otherwise. |
| neq | Checks inequality of two unsigned 256-bit integers. Stack transition: [b0..b7, a0..a7, ...] -> [c, ...]where c = 1 when a != b, and 0 otherwise. |
| eqz | Checks if an unsigned 256-bit integer equals zero. Stack transition: [a0..a7, ...] -> [c, ...]where c = 1 when a == 0, and 0 otherwise. |
| lt | Less-than comparison of two unsigned 256-bit integers. Stack transition: [b0..b7, a0..a7, ...] -> [c, ...]where c = 1 when a < b, and 0 otherwise. |
| gt | Greater-than comparison of two unsigned 256-bit integers. Stack transition: [b0..b7, a0..a7, ...] -> [c, ...]where c = 1 when a > b, and 0 otherwise. |
| lte | Less-than-or-equal comparison of two unsigned 256-bit integers. Stack transition: [b0..b7, a0..a7, ...] -> [c, ...]where c = 1 when a <= b, and 0 otherwise. |
| gte | Greater-than-or-equal comparison of two unsigned 256-bit integers. Stack transition: [b0..b7, a0..a7, ...] -> [c, ...]where c = 1 when a >= b, and 0 otherwise. |
| min | Minimum of two unsigned 256-bit integers. Stack transition: [b0..b7, a0..a7, ...] -> [c0..c7, ...]where c = min(a, b). |
| max | Maximum of two unsigned 256-bit integers. Stack transition: [b0..b7, a0..a7, ...] -> [c0..c7, ...]where c = max(a, b). |
Bitwise operations
| Procedure | Description |
|---|---|
| and | Performs bitwise AND of two unsigned 256-bit integers. Stack transition: [b0..b7, a0..a7, ...] -> [c0..c7, ...]where c = a AND b |
| or | Performs bitwise OR of two unsigned 256-bit integers. Stack transition: [b0..b7, a0..a7, ...] -> [c0..c7, ...]where c = a OR b |
| xor | Performs bitwise XOR of two unsigned 256-bit integers. Stack transition: [b0..b7, a0..a7, ...] -> [c0..c7, ...]where c = a XOR b |
| not | Performs bitwise NOT of an unsigned 256-bit integer. Stack transition: [a0..a7, ...] -> [c0..c7, ...]where c = !a (i.e., 2^256 - 1 - a) |
Bit counting
| Procedure | Description |
|---|---|
| clz | Counts the leading zeros of an unsigned 256-bit integer. Stack transition: [a0..a7, ...] -> [count, ...]where count is in 0..=256. |
| ctz | Counts the trailing zeros of an unsigned 256-bit integer. Stack transition: [a0..a7, ...] -> [count, ...]where count is in 0..=256. |
| clo | Counts the leading ones of an unsigned 256-bit integer. Stack transition: [a0..a7, ...] -> [count, ...]where count is in 0..=256. |
| cto | Counts the trailing ones of an unsigned 256-bit integer. Stack transition: [a0..a7, ...] -> [count, ...]where count is in 0..=256. |
Shifts and rotations
The shift amount n is a u32 in the range [0, 256). Procedures panic if n is outside this range.
| Procedure | Description |
|---|---|
| shl | Left shift of an unsigned 256-bit integer. Stack transition: [n, a0..a7, ...] -> [c0..c7, ...]where c = (a << n) mod 2^256. |
| shr | Right shift of an unsigned 256-bit integer. Stack transition: [n, a0..a7, ...] -> [c0..c7, ...]where c = a >> n. |
| rotl | Left rotation of an unsigned 256-bit integer. Stack transition: [n, a0..a7, ...] -> [c0..c7, ...]where c = (a << n) | (a >> (256 - n)). |
| rotr | Right rotation of an unsigned 256-bit integer. Stack transition: [n, a0..a7, ...] -> [c0..c7, ...]where c = (a >> n) | (a << (256 - n)). |