Skip to content

Commit

Permalink
Wideint instructions (FuelLabs#483)
Browse files Browse the repository at this point in the history
Progress towards FuelLabs#478.
Implementation PR: FuelLabs/fuel-vm#424

This PR adds instructions for handling wideint types, specifically
memory-stored 128- and 256-bit unsigned integers. The following opcodes
are added:

* MLDV - Fused multiply-add of 64bit register values
* WDCM - Compare 128bit integers
* WQCM - Compare 256bit integers
* WDOP - Cheap 128bit operations (add,, sub, shr, shl, not, and, or,
xor)
* WQOP - Cheap 256bit operations (add,, sub, shr, shl, not, and, or,
xor)
* WDML - Multiply 128bit
* WQML - Multiply 256bit
* WDDV - Divide 128bit
* WQDV - Divide 256bit
* WDMD - Fused multiply-divide 128bit
* WQMD - Fused multiply-divide 256bit
* WDAM - AddMod 128bit
* WQAM - AddMod 256bit
* WDMM - MulMod 128bit
* WQMM - MulMod 256bit

The naming convention is to prefix the operations with their size: `WD`
for double-word-sized (128 bit) operations, and `WQ` for quad-word-sized
(256 bit) operations.

### Grouped by cost

The operations are grouped to these opcodes so that cost of a signle
opcode can be a constant. To avoid polluting the opcode space, several
operations are grouped together: W*CM for compare operations and W*OP
for arithmetic operations. The actual operation is then selected using
the immediate part of the instruction.

Since multiplication and especially division are more expensive than
cheap operations behind these groups, they have their own, separate
opcodes. Similarly AddMod and MulMod, which require larger precision
than the input operations, are grouped separately. A separate modulus
instruction is not provided, but AddMod with addition of zero will
perform this function with minimal overhead.

### Direct/Indirect arguments

Some of the operations also allow users to select between direct and
indirect operands. When a direct operand is selected, instead of reading
the wide integer pointed by the register value, the register value
itself is zero-extended to full-width value and used as an operand. This
reduces the size of many common operations by a couple of instructions.
Also, this means that u64 * u64 -> u128 can be done directly.

### What's missing?

Astute reviewers might have already noticed that some operations are
missing.

* exponentation - Can be added if needed, also ExpMod could be added
* logarithm - This can be added if any use cases are found
* nth root (or even square root) - The roots are rather slow to compute,
and hopefully never needed. Even the 64bit version was tricky
* Fused opcodes like multiply-add and multiply-divide

### Hopes and dreams

We could support these operations for 64-bit integers as well, and
remove current ALU instructions completely. However, I think that we are
too committed to backwards compatibility of the current ops even now.

---------

Co-authored-by: Mitch Martin <111294749 [email protected]>
Co-authored-by: Tom <[email protected]>
  • Loading branch information
3 people authored Apr 28, 2023
1 parent 5c78c43 commit 9784735
Showing 1 changed file with 389 additions and 0 deletions.
Loading

0 comments on commit 9784735

Please sign in to comment.