EVM opcodes: bitwise shifting

Question

EVM opcodes: bitwise shifting

axic opened this issue 8 years ago · 30 comments

axic commented 8 years ago

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)
1. 0x1c: SHR (logical right shift)
1. 0x1d: SAR (arithmetic right shift)
1. 0x1e: ROL (rotate left)
1. 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.

Answer 1 · 2016-09-08T15:19:33.000Z

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.

Answer 2 · 2016-09-08T18:05:39.000Z

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?

Answer 3 · 2016-09-08T19:23:42.000Z

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.

Answer 4 · 2016-09-08T21:55:45.000Z

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.

Answer 5 · 2016-09-08T22:36:02.000Z

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.

Answer 6 · 2016-09-08T23:45:07.000Z

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?

Answer 7 · 2016-09-09T08:12:49.000Z

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

Answer 8 · 2016-09-09T09:14:14.000Z

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

Answer 9 · 2016-09-09T15:09:30.000Z

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.

Answer 10 · 2016-09-09T15:36:43.000Z

@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.

Answer 11 · 2016-09-09T16:18:05.000Z

@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

Answer 12 · 2016-09-09T17:46:16.000Z

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.

Answer 13 · 2016-09-09T22:57:22.000Z

So it's

0x1b: SHL (shift left)
0x1c: SHR (shift right)
0x1d: ROL (rotate left)
0x1e: ROR (rotate right)

And one code left in this column for future use.

Answer 14 · 2016-09-13T00:00:30.000Z

Do we all agree:

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

Answer 15 · 2016-09-13T09:21:17.000Z

SAR is used to optimize SDIV.

Answer 16 · 2016-09-13T09:41:35.000Z

But we have SDIV already, so users don't need to implement it.


On 9/13/16 3:21 AM, Paweł Bylica wrote:


  SAR is used to optimized SDIV.
  —
    You are receiving this because you were mentioned.
    Reply to this email directly, view
      it on GitHub, or mute
      the thread.







  {"api_version":"1.0","publisher":{"api_key":"05dde50f1d1a384dd78767c55493e4bb","name":"GitHub"},"entity":{"external_key":"github/ethereum/EIPs","title":"ethereum/EIPs","subtitle":"GitHub repository","main_image_url":"https://cloud.githubusercontent.com/assets/143418/17495839/a5054eac-5d88-11e6-95fc-7290892c7bb5.png","avatar_image_url":"https://cloud.githubusercontent.com/assets/143418/15842166/7c72db34-2c0b-11e6-9aed-b52498112777.png","action":{"name":"Open in GitHub","url":"https://github.com/ethereum/EIPs"}},"updates":{"snippets":[{"icon":"PERSON","message":"@chfast in #145: `SAR` is used to optimized `SDIV`."}],"action":{"name":"View Issue","url":"https://github.com/ethereum/EIPs/issues/145#issuecomment-246624541"}}}

Answer 17 · 2016-09-13T09:43:20.000Z

SAR is used to optimize SDIV.

You mean SAR can serve a purpose as an optimised SDIV in certain cases? True, but the gas cost is the same so end users wouldn't care.

Answer 18 · 2016-09-13T11:03:07.000Z

0x1b: SHL (shift left)
The SHL instruction (shift left) pops 2 values from the stack, arg1 and arg2, and pushes on the stack the second popped value arg2 shifted to the left by the number of bits in the first popped value arg1. The result is equal to
```
(arg2 * 2^arg1) mod 2²⁵⁶
```
Notes:
- If the shift amount is greater or equal 256 the result is 0.
0x1c: SHR (logical shift right)
The SHR instruction (logical shift right) pops 2 values from the stack, arg1 and arg2, and pushes on the stack the second popped value arg2 shifted to the right by the number of bits in the first popped value arg1 with zero fill. The result is equal to
```
arg2 udiv 2^arg1
```
Notes:
- If the shift amount is greater or equal 256 the result is 0.
0x1d: SAR (arithmetic shift right)
The SAR instruction (arithmetic shift right) pops 2 values from the stack, arg1 and arg2, and pushes on the stack the second popped value arg2 shifted to the right by the number of bits in the first popped value arg1 with sign extension. The result is equal to
```
arg2 sdiv 2^arg1
```
Notes:
- arg1 is interpreted as unsigned number.
- If the shift amount is greater or equal 256 the result is 0 if arg2 is non-negative or -1 if arg2 is negative.
0x1e: ROL (rotate left)
The ROL instruction (rotate left) pops 2 values from the stack, arg1 and arg2, and pushes on the stack the second popped value arg2 circular shifted to the left by the number of bits in the first popped value arg1.

Notes:
- arg2 rol arg1 is equivalent of arg2 rol (arg1 mod 2^256)
0x1f: ROR (rotate right)
The ROL instruction (rotate right) pops 2 values from the stack, arg1 and arg2, and pushes on the stack the second popped value arg2 circular shifted to the right by the number of bits in the first popped value arg1.

Notes:
- arg2 rorl arg1 is equivalent of arg2 ror (arg1 mod 2^256)

Answer 19 · 2017-02-06T22:03:41.000Z

@axic @chfast Is it time to get a trial implementation going and write the EIP? We can hack the Solidity assembler, not the compiler, if that helps. I need to hack the assembler anyway to put in JUMPSUB and its friends. And I really need shifts and rotates for porting crypto code into the EVM.

Answer 20 · 2017-02-06T22:06:44.000Z

Thanks for the heads up @gcolvin, I'm in the process of writing proper draft of many of my submissions.

Answer 21 · 2017-02-06T22:30:49.000Z

Available here in Solidity: https://github.com/ethereum/solidity/tree/asm-bitshift

The following example code should work:

library Bitwise {
  function shr(uint v, uint n) internal returns (uint r) {
    assembly {
      r := shr(v, n)
    }
  }
}

contract A {
  using Bitwise for uint;
  function f() returns (uint) {
    uint a = 0x1234;
    return a.shr(8); // => 0x12
  }
}

Answer 22 · 2017-02-07T01:14:09.000Z

Thanks @axic !

Answer 23 · 2017-02-13T16:07:42.000Z

Replaced by #215.

Answer 24 · 2017-02-13T16:12:02.000Z

@chfast @gcolvin moved the description into the current format required by EIPs, please review.

Answer 25 · 2017-02-13T22:09:06.000Z

This looks very good. Thanks! Seems most every cipher and hash I want to use for testing involves lots of shifts or rotates.

Answer 26 · 2017-04-29T19:36:59.000Z

Bit rotation has some uses in cryptography when the word it is either 32-bit or 64-bit.
I don't know many use cases for 256-bit bit rotation, except maybe for PRNG (taking the upper bits of a number after multiplication).
Is there any other?
Maybe it would be better to provide 32-bit rotation and 64-bit rotation only?

Answer 27 · 2017-04-29T20:43:36.000Z

That is being considered as part of this proposal:
#616

Answer 28 · 2017-04-29T20:45:44.000Z

@SergioDemianLerner where are you seeing rotations in #215?

Answer 29 · 2018-04-23T09:48:38.000Z

Just learnt of this EIP (had been wondering why EVM doesn't have bitwise shifting).

The issue seems to have gone quiet and missed the Byzantium fork. I'd like to express interest in it being included for Constantinople.

Answer 30 · 2019-03-01T19:24:47.000Z

Is it present on the Constantinople release?
Which pragma solidity version do i need to make use of it?