Power of two instruction

[bobbinth]

The VM currently does not support dynamic bitwise shifts. One of the reasons for this is that emulating shifts using other operations is relatively easy when we know how many bits to shift by statically. For example, u32shl is actually computed as PUSH(2^x) MUL U32SPLIT DROP where x is the number of bits to shift by and 2^x is computed at compile time.

One way to support dynamic shifts of u32 values (which can be used to support dynamic shifts of u256 values), is to compute 2^x in the VM where x is a value on the stack. The operation could be called U32POW2 (or something similar), and could work as follows:

[x, ... ] -> [2^x, ...]

This, of course, can be computed via repeated multiplication by two, but that would be rather expensive, and we should find a better way of supporting this operation.

One thing to note: even if we do have support for this operation, implementing u256 bitwise shifts is going to be far from trivial. So, other approaches to bitwise shifts may need to be explored.

[bobbinth]

One way to perform U32POW2 operation in a single cycle would be to move the actual computation into a co-processor. Given the current width of our co-processor table, we should be able to compute 2^x for x between 0 and 31 in 4 rows in the table. The constraints for that shouldn't be too complicated.

[grjte]

Reference notes from discussion with Bobbin

Goals:

so, the goal i have in my mind are:

• support for bit shifts and bit rotations for composite values (e.g., u64, u256)
• potential optimization for bit rotations (especially rotate right) - since these are used a lot in BLAKE3
  the secondary goal is a nice to have

Alternative approach:

in my original u32 operations note, i described a different approach: https://hackmd.io/NC-yRmmtRQSvToTHb96e8Q#Bit-shifts

that one had a few disadvantages:

1. we had to have 4 dedicated instructions
2. i assumed there would be a separate table for powers of 2 (kind of like read-only memory)

[bobbinth]

Closed by #161