EVM opcodes: bitwise shifting

[axic]

This replaces #105.

Motivation

To provide native bitwise shifting with cost on par with other arithmetic operations.

Specification

The following new EVM opcodes are introduced:

• 1. 0x1b: SHL (logical left shift)
• 2. 0x1c: SHR (logical right shift)
• 3. 0x1d: SAR (arithmetic right shift)
• 4. 0x1e: ROL (rotate left)
• 5. 0x1f: ROR (rotate right)

The gast cost is set at verylow (3 gas)

All shift / rotate instructions take two stack elements (i.e. value << index), with the top element being the index to shift with and the next stack element is the value. Both index and value is considered as unsigned, with the exception of SAR, where value is signed.

All results must be mod 2^256.

For index ≥ 256, the result is 0.

Effect

This effectively reduces the gas cost and number of instructions for the above. A SHL and SHR can be implemented as a * (2 ** b) ( and a / (2 ** b) respectively. The upper gas bound for these is 35 gas.

SAR and the rotation opcodes cost more than 35.

[gcolvin]

I remain in strong support of these, for the reasons you give. (Though I'm tempted to special-case exponentiation for powers of two.)

I think 0x10 is taken by LT. I suggest the range 0x1b through 0x1f.

[gcolvin]

Also, Is the semantics value << index for shifts? And for rotations 0 seems like the wrong answer for rotating more than 256 bits - shouldn't it keep spinning modulo 256?

[axic]

I think 0x10 is taken by LT.

True.

I suggest the range 0x1b through 0x1f.

That seems to be more fitting too (bit ops).

Is the semantics value << index for shifts?

Yes.

for rotations 0 seems like the wrong answer for rotating more than 256 bits - shouldn't it keep spinning modulo 256?

I was considering this too and I have no preference. Not entirely convinced we need rotation as an opcode. It is very useful for hashing functions, but we have them implemented as precompiles already.

[gcolvin]

Rotates can be done with shifts and masks, but it's ugly, error prone, costs more gas, and can be done more efficiently inside the VM. And not all uses of rotate are precompiles.

if you consider rotating by N bits as equivalent to rotating by one bit N number of times you don't end up with 0 unless you started out with 0.

[chfast]

All results must be mod 256.

I guess you mean 2^256 there.

I would suggest to specify the amount of shift/rotate to be N mod 256, where N is the second argument of the instruction. In other words, only 8 least significant bits are taken into account. It is more like hardware works (x86 takes 5 bits for 64-bit registers) and easier to implement.

[gcolvin]

I'm too tired to think, even in circles. But doesn't one (N mod 256)-bit rotation give the same result as N 1-bit rotations of a 256-bit register?

[ethernomad]

If there are EVM opcodes, does it mean the VM can use less time on the hardware processor?

[chfast]

@gcolvin, your are exactly right. But that's not the case for shifts.

[tjade273]

This would be extremely useful. I find an inordinate amount of my time is spent implementing bit shifting in inefficient and inelegant ways. Please do include this in the next hard fork.

[gcolvin]

@chfast Thanks. And yes, for excess shifts all the bits go flying off one end or the other.
@ethernomad Yes, if we do these in opcodes they will use the hardware more efficiently.

[gcolvin]

@axic There are good arguments for not doing SAR at all. It's not really a bitwise operation, and it's a failure as an arithmetic operation. It's not the same as dividing by powers of two, different hardware does it different ways, and the implementation for negative numbers at the C/C++ level remains implementation defined. E.g. the C++14 standard, section 5.8, page 126:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf

[axic]

I don't really like SAR myself and happy to remove it if we can't find a use case where it is really needed.

[gcolvin]

So it's

1. 0x1b: SHL (shift left)
2. 0x1c: SHR (shift right)
3. 0x1d: ROL (rotate left)
4. 0x1e: ROR (rotate right)

And one code left in this column for future use.

[axic]

Do we all agree:

• to remove SAR?
• that for rotations index is mod 256
• and for shifts, index ≥ 256 still means 0?