u32 operations
Miden assembly provides a set of instructions which can perform operations on regular two-complement 32-bit integers. These instructions are described in the tables below.
Most instructions have checked variants. These variants ensure that input values are 32-bit integers, and fail if that’s not the case. All other variants do not perform these checks, and thus, should be used only if the inputs are known to be 32-bit integers. Supplying inputs which are greater than or equal to \(2^{32}\) to unchecked operations results in undefined behavior.
The primary benefit of using unchecked operations is performance: they can frequently be executed \(2\) or \(3\) times faster than their checked counterparts. In general, vast majority of the unchecked operations listed below can be executed in a single VM cycle.
For instructions where one or more operands can be provided as immediate parameters (e.g., u32checked_add and u32checked_add.b), we provide stack transition diagrams only for the non-immediate version. For the immediate version, it can be assumed that the operand with the specified name is not present on the stack.
In all the table below, the number of cycles it takes for the VM to execute each instruction is listed beneath the instruction.
Conversions and tests¶
| Instruction | Stack input | Stack output | Notes |
|---|---|---|---|
| u32test - (5 cycles) |
[a, …] | [b, a, …] | \(b \leftarrow \begin{cases} 1, & \text{if}\ a < 2^{32} \\ 0, & \text{otherwise}\ \end{cases}\) |
| u32testw - (23 cycles) |
[A, …] | [b, A, …] | \(b \leftarrow \begin{cases} 1, & \text{if}\ \forall\ i \in \{0, 1, 2, 3\}\ a_i < 2^{32} \\ 0, & \text{otherwise}\ \end{cases}\) |
| u32assert - (3 cycles) |
[a, …] | [a, …] | Fails if \(a \ge 2^{32}\) |
| u32assert2 - (1 cycle) |
[b, a,…] | [b, a,…] | Fails if \(a \ge 2^{32}\) or \(b \ge 2^{32}\) |
| u32assertw - (6 cycles) |
[A, …] | [A, …] | Fails if \(\exists\ i \in \{0, 1, 2, 3\} : a_i \ge 2^{32}\) |
| u32cast - (2 cycles) |
[a, …] | [b, …] | \(b \leftarrow a \mod 2^{32}\) |
| u32split - (1 cycle) |
[a, …] | [c, b, …] | \(b \leftarrow a \mod 2^{32}\), \(c \leftarrow \lfloor{a / 2^{32}}\rfloor\) |
The instructions u32assert, u32assert2 and u32assertw can also be parametrized with an error code which can be any 32-bit value specified either directly or via a named constant. For example:
u32assert.err=123
u32assert.err=MY_CONSTANT
If the error code is omitted, the default value of \(0\) is assumed.
Arithmetic operations¶
| Instruction | Stack input | Stack output | Notes |
|---|---|---|---|
| u32checked_add - (4 cycles) u32checked_add.b - (5-6 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow a + b\) Fails if \(max(a, b, c) \ge 2^{32}\) |
| u32overflowing_add - (1 cycle) u32overflowing_add.b - (2-3 cycles) |
[b, a, …] | [d, c, …] | \(c \leftarrow (a + b) \mod 2^{32}\) \(d \leftarrow \begin{cases} 1, & \text{if}\ (a + b) \ge 2^{32} \\ 0, & \text{otherwise}\ \end{cases}\) Undefined if \(max(a, b) \ge 2^{32}\) |
| u32wrapping_add - (2 cycles) u32wrapping_add.b - (3-4 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow (a + b) \mod 2^{32}\) Undefined if \(max(a, b) \ge 2^{32}\) |
| u32overflowing_add3 - (1 cycle) |
[c, b, a, …] | [e, d, …] | \(d \leftarrow (a + b + c) \mod 2^{32}\), \(e \leftarrow \lfloor (a + b + c) / 2^{32}\rfloor\) Undefined if \(max(a, b, c) \ge 2^{32}\) |
| u32wrapping_add3 - (2 cycles) |
[c, b, a, …] | [d, …] | \(d \leftarrow (a + b + c) \mod 2^{32}\), Undefined if \(max(a, b, c) \ge 2^{32}\) |
| u32checked_sub - (4 cycles) u32checked_sub.b - (5-6 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow (a - b)\) Fails if \(max(a, b) \ge 2^{32}\) or \(a < b\) |
| u32overflowing_sub - (1 cycle) u32overflowing_sub.b - (2-3 cycles) |
[b, a, …] | [d, c, …] | \(c \leftarrow (a - b) \mod 2^{32}\) \(d \leftarrow \begin{cases} 1, & \text{if}\ a < b \\ 0, & \text{otherwise}\ \end{cases}\) Undefined if \(max(a, b) \ge 2^{32}\) |
| u32wrapping_sub - (2 cycles) u32wrapping_sub.b - (3-4 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow (a - b) \mod 2^{32}\) Undefined if \(max(a, b) \ge 2^{32}\) |
| u32checked_mul - (4 cycles) u32checked_mul.b - (5-6 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow a \cdot b\) Fails if \(max(a, b, c) \ge 2^{32}\) |
| u32overflowing_mul - (1 cycle) u32overflowing_mul.b - (2-3 cycles) |
[b, a, …] | [d, c, …] | \(c \leftarrow (a \cdot b) \mod 2^{32}\) \(d \leftarrow \lfloor(a \cdot b) / 2^{32}\rfloor\) Undefined if \(max(a, b) \ge 2^{32}\) |
| u32wrapping_mul - (2 cycles) u32wrapping_mul.b - (3-4 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow (a \cdot b) \mod 2^{32}\) Undefined if \(max(a, b) \ge 2^{32}\) |
| u32overflowing_madd - (1 cycle) |
[b, a, c, …] | [e, d, …] | \(d \leftarrow (a \cdot b + c) \mod 2^{32}\) \(e \leftarrow \lfloor(a \cdot b + c) / 2^{32}\rfloor\) Undefined if \(max(a, b, c) \ge 2^{32}\) |
| u32wrapping_madd - (2 cycles) |
[b, a, c, …] | [d, …] | \(d \leftarrow (a \cdot b + c) \mod 2^{32}\) Undefined if \(max(a, b, c) \ge 2^{32}\) |
| u32checked_div - (3 cycles) u32checked_div.b - (4-5 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \lfloor a / b\rfloor\) Fails if \(max(a, b) \ge 2^{32}\) or \(b = 0\) |
| u32unchecked_div - (2 cycles) u32unchecked_div.b - (3-4 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \lfloor a / b\rfloor\) Fails if \(b = 0\) Undefined if \(max(a, b) \ge 2^{32}\) |
| u32checked_mod - (4 cycles) u32checked_mod.b - (5-6 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow a \mod b\) Fails if \(max(a, b) \ge 2^{32}\) or \(b = 0\) |
| u32unchecked_mod - (3 cycles) u32unchecked_mod.b - (4-5 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow a \mod b\) Fails if \(b = 0\) Undefined if \(max(a, b) \ge 2^{32}\) |
| u32checked_divmod - (2 cycles) u32checked_divmod.b - (3-4 cycles) |
[b, a, …] | [d, c, …] | \(c \leftarrow \lfloor a / b\rfloor\) \(d \leftarrow a \mod b\) Fails if \(max(a, b) \ge 2^{32}\) or \(b = 0\) |
| u32unchecked_divmod - (1 cycle) u32unchecked_divmod.b - (2-3 cycles) |
[b, a, …] | [d, c, …] | \(c \leftarrow \lfloor a / b\rfloor\) \(d \leftarrow a \mod b\) Fails if \(b = 0\) Undefined if \(max(a, b) \ge 2^{32}\) |
Bitwise operations¶
| Instruction | Stack input | Stack output | Notes |
|---|---|---|---|
| u32checked_and - (1 cycle) |
[b, a, …] | [c, …] | Computes \(c\) as a bitwise AND of binary representations of \(a\) and \(b\). Fails if \(max(a,b) \ge 2^{32}\) |
| u32checked_or - (6 cycle)s |
[b, a, …] | [c, …] | Computes \(c\) as a bitwise OR of binary representations of \(a\) and \(b\). Fails if \(max(a,b) \ge 2^{32}\) |
| u32checked_xor - (1 cycle) |
[b, a, …] | [c, …] | Computes \(c\) as a bitwise XOR of binary representations of \(a\) and \(b\). Fails if \(max(a,b) \ge 2^{32}\) |
| u32checked_not - (5 cycles) |
[a, …] | [b, …] | Computes \(b\) as a bitwise NOT of binary representation of \(a\). Fails if \(a \ge 2^{32}\) |
| u32checked_shl - (47 cycles) u32checked_shl.b - (4 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow (a \cdot 2^b) \mod 2^{32}\) Fails if \(a \ge 2^{32}\) or \(b > 31\) |
| u32unchecked_shl - (40 cycles) u32unchecked_shl.b - (3 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow (a \cdot 2^b) \mod 2^{32}\) Undefined if \(a \ge 2^{32}\) or \(b > 31\) |
| u32checked_shr - (47 cycles) u32checked_shr.b - (4 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \lfloor a/2^b \rfloor\) Fails if \(a \ge 2^{32}\) or \(b > 31\) |
| u32unchecked_shr - (40 cycles) u32unchecked_shr.b - (3 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \lfloor a/2^b \rfloor\) Undefined if \(a \ge 2^{32}\) or \(b > 31\) |
| u32checked_rotl - (47 cycles) u32checked_rotl.b - (4 cycles) |
[b, a, …] | [c, …] | Computes \(c\) by rotating a 32-bit representation of \(a\) to the left by \(b\) bits. Fails if \(a \ge 2^{32}\) or \(b > 31\) |
| u32unchecked_rotl - (40 cycles) u32unchecked_rotl.b - (3 cycles) |
[b, a, …] | [c, …] | Computes \(c\) by rotating a 32-bit representation of \(a\) to the left by \(b\) bits. Undefined if \(a \ge 2^{32}\) or \(b > 31\) |
| u32checked_rotr - (59 cycles) u32checked_rotr.b - (6 cycles) |
[b, a, …] | [c, …] | Computes \(c\) by rotating a 32-bit representation of \(a\) to the right by \(b\) bits. Fails if \(a \ge 2^{32}\) or \(b > 31\) |
| u32unchecked_rotr - (44 cycles) u32unchecked_rotr.b - (3 cycles) |
[b, a, …] | [c, …] | Computes \(c\) by rotating a 32-bit representation of \(a\) to the right by \(b\) bits. Undefined if \(a \ge 2^{32}\) or \(b > 31\) |
| u32checked_popcnt - (36 cycles) |
[a, …] | [b, …] | Computes \(b\) by counting the number of set bits in \(a\) (hamming weight of \(a\)). Fails if \(a \ge 2^{32}\) |
| u32unchecked_popcnt - (33 cycles) |
[a, …] | [b, …] | Computes \(b\) by counting the number of set bits in \(a\) (hamming weight of \(a\)). Undefined if \(a \ge 2^{32}\) |
Comparison operations¶
| Instruction | Stack input | Stack output | Notes |
|---|---|---|---|
| u32checked_eq - (2 cycles) u32checked_eq.b - (3-4 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \begin{cases} 1, & \text{if}\ a=b \\ 0, & \text{otherwise}\ \end{cases}\) Fails if \(max(a, b) \ge 2^{32}\) Note: unchecked version is not provided because it is equivalent to simple eq. |
| u32checked_neq - (3 cycles) u32checked_neq.b - (4-5 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \begin{cases} 1, & \text{if}\ a \ne b \\ 0, & \text{otherwise}\ \end{cases}\) Fails if \(max(a, b) \ge 2^{32}\) Note: unchecked version is not provided because it is equivalent to simple neq. |
| u32checked_lt - (6 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \begin{cases} 1, & \text{if}\ a < b \\ 0, & \text{otherwise}\ \end{cases}\) Fails if \(max(a, b) \ge 2^{32}\) |
| u32unchecked_lt - (5 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \begin{cases} 1, & \text{if}\ a < b \\ 0, & \text{otherwise}\ \end{cases}\) Undefined if \(max(a, b) \ge 2^{32}\) |
| u32checked_lte - (8 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \begin{cases} 1, & \text{if}\ a \le b \\ 0, & \text{otherwise}\ \end{cases}\) Fails if \(max(a, b) \ge 2^{32}\) |
| u32unchecked_lte - (7 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \begin{cases} 1, & \text{if}\ a \le b \\ 0, & \text{otherwise}\ \end{cases}\) Undefined if \(max(a, b) \ge 2^{32}\) |
| u32checked_gt - (7 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \begin{cases} 1, & \text{if}\ a > b \\ 0, & \text{otherwise}\ \end{cases}\) Fails if \(max(a, b) \ge 2^{32}\) |
| u32unchecked_gt - (6 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \begin{cases} 1, & \text{if}\ a > b \\ 0, & \text{otherwise}\ \end{cases}\) Undefined if \(max(a, b) \ge 2^{32}\) |
| u32checked_gte - (7 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \begin{cases} 1, & \text{if}\ a \ge b \\ 0, & \text{otherwise}\ \end{cases}\) Fails if \(max(a, b) \ge 2^{32}\) |
| u32unchecked_gte - (6 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \begin{cases} 1, & \text{if}\ a \ge b \\ 0, & \text{otherwise}\ \end{cases}\) Undefined if \(max(a, b) \ge 2^{32}\) |
| u32checked_min - (9 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \begin{cases} a, & \text{if}\ a < b \\ b, & \text{otherwise}\ \end{cases}\) Fails if \(max(a, b) \ge 2^{32}\) |
| u32unchecked_min - (8 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \begin{cases} a, & \text{if}\ a < b \\ b, & \text{otherwise}\ \end{cases}\) Undefined if \(max(a, b) \ge 2^{32}\) |
| u32checked_max - (10 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \begin{cases} a, & \text{if}\ a > b \\ b, & \text{otherwise}\ \end{cases}\) Fails if \(max(a, b) \ge 2^{32}\) |
| u32unchecked_max - (9 cycles) |
[b, a, …] | [c, …] | \(c \leftarrow \begin{cases} a, & \text{if}\ a > b \\ b, & \text{otherwise}\ \end{cases}\) Undefined if \(max(a, b) \ge 2^{32}\) |
Last update:
January 17, 2024
Authors: