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?

[chfast]

SAR is used to optimize SDIV.

[gcolvin]

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"}}}

[axic]

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.

[chfast]

1. 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 * 2arg1) mod 2256

   Notes:

   • If the shift amount is greater or equal 256 the result is 0.

2. 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 2arg1

   Notes:

   • If the shift amount is greater or equal 256 the result is 0.

3. 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 2arg1

   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.

4. 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)

5. 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)

[gcolvin]

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

[axic]

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

[axic]

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
  }
}

[gcolvin]

Thanks @axic !

[axic]

Replaced by #215.

[axic]

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

[gcolvin]

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

[SergioDemianLerner]

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?

[gcolvin]

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

[chfast]

@SergioDemianLerner where are you seeing rotations in #215?

[o0ragman0o]

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.

[flockonus]

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