以太坊改进提案 EIPs

# EIP 145: EVM 按位移位指令

作者 状态 类型 分类 创建时间
Alex Beregszaszi (@axic), Paweł Bylica (@chfast) 最终 Standards Track Core 2017-02-13

# 简要说明

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

# 摘要

Native bitwise shifting instructions are introduced, which are more efficient processing wise on the host and are cheaper to use by a contract.

# 动机

EVM is lacking bitwise shifting operators, but supports other logical and arithmetic operators. Shift operations can be implemented via arithmetic operators, but that has a higher cost and requires more processing time from the host. Implementing SHL and SHR using arithmetic cost each 35 gas, while the proposed instructions take 3 gas.

# 规范

The following instructions are introduced:

# 0x1b: SHL (shift left)

The SHL instruction (shift left) pops 2 values from the stack, first arg1 and then arg2, and pushes on the stack arg2 shifted to the left by arg1 number of bits. The result is equal to

(arg2 * 2^arg1) mod 2^256
1

Notes:

  • The value (arg2) is interpreted as an unsigned number.
  • The shift amount (arg1) is interpreted as an unsigned number.
  • If the shift amount (arg1) is greater or equal 256 the result is 0.
  • This is equivalent to PUSH1 2 EXP MUL.

# 0x1c: SHR (logical shift right)

The SHR instruction (logical shift right) pops 2 values from the stack, first arg1 and then arg2, and pushes on the stack arg2 shifted to the right by arg1 number of bits with zero fill. The result is equal to

floor(arg2 / 2^arg1)
1

Notes:

  • The value (arg2) is interpreted as an unsigned number.
  • The shift amount (arg1) is interpreted as an unsigned number.
  • If the shift amount (arg1) is greater or equal 256 the result is 0.
  • This is equivalent to PUSH1 2 EXP DIV.

# 0x1d: SAR (arithmetic shift right)

The SAR instruction (arithmetic shift right) pops 2 values from the stack, first arg1 and then arg2, and pushes on the stack arg2 shifted to the right by arg1 number of bits with sign extension. The result is equal to

floor(arg2 / 2^arg1)
1

Notes:

  • The value (arg2) is interpreted as a signed number.
  • The shift amount (arg1) is interpreted as an unsigned number.
  • If the shift amount (arg1) is greater or equal 256 the result is 0 if arg2 is non-negative or -1 if arg2 is negative.
  • This is not equivalent to PUSH1 2 EXP SDIV, since it rounds differently. See SDIV(-1, 2) == 0, while SAR(-1, 1) == -1.

The cost of the shift instructions is set at verylow tier (3 gas).

# 原理阐述

Instruction operands were chosen to fit the more natural use case of shifting a value already on the stack. This means the operand order is swapped compared to most arithmetic insturctions.

# 向后兼容

The newly introduced instructions have no effect on bytecode created in the past.

# 测试用例

# SHL (shift left)

  1. PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x00
SHL
---
0x0000000000000000000000000000000000000000000000000000000000000001
    1
    2
    3
    4
    5
  2. PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x01
SHL
---
0x0000000000000000000000000000000000000000000000000000000000000002
    1
    2
    3
    4
    5
  3. PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0xff
SHL
---
0x8000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5
  4. PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x0100
SHL
---
0x0000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5
  5. PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x0101
SHL
---
0x0000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5
  6. PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x00
SHL
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    1
    2
    3
    4
    5
  7. PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x01
SHL
---
0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe
    1
    2
    3
    4
    5
  8. PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0xff
SHL
---
0x8000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5
  9. PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x0100
SHL
---
0x0000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5
  10. PUSH 0x0000000000000000000000000000000000000000000000000000000000000000
PUSH 0x01
SHL
---
0x0000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5
  11. PUSH 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x01
SHL
---
0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe
    1
    2
    3
    4
    5

# SHR (logical shift right)

  1. PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x00
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000001
    1
    2
    3
    4
    5
  2. PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x01
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5
  3. PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0x01
SHR
---
0x4000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5
  4. PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0xff
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000001
    1
    2
    3
    4
    5
  5. PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0x0100
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5
  6. PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0x0101
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5
  7. PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x00
SHR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    1
    2
    3
    4
    5
  8. PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x01
SHR
---
0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    1
    2
    3
    4
    5
  9. PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0xff
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000001
    1
    2
    3
    4
    5
  10. PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x0100
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5
  11. PUSH 0x0000000000000000000000000000000000000000000000000000000000000000
PUSH 0x01
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5

# SAR (arithmetic shift right)

  1. PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x00
SAR
---
0x0000000000000000000000000000000000000000000000000000000000000001
    1
    2
    3
    4
    5
  2. PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x01
SAR
---
0x0000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5
  3. PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0x01
SAR
---
0xc000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5
  4. PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0xff
SAR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    1
    2
    3
    4
    5
  5. PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0x0100
SAR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    1
    2
    3
    4
    5
  6. PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0x0101
SAR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    1
    2
    3
    4
    5
  7. PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x00
SAR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    1
    2
    3
    4
    5
  8. PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x01
SAR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    1
    2
    3
    4
    5
  9. PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0xff
SAR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    1
    2
    3
    4
    5
  10. PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x0100
SAR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    1
    2
    3
    4
    5
  11. PUSH 0x0000000000000000000000000000000000000000000000000000000000000000
PUSH 0x01
SAR
---
0x0000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5
  12. PUSH 0x4000000000000000000000000000000000000000000000000000000000000000
PUSH 0xfe
SAR
---
0x0000000000000000000000000000000000000000000000000000000000000001
    1
    2
    3
    4
    5
  13. PUSH 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0xf8
SAR
---
0x000000000000000000000000000000000000000000000000000000000000007f
    1
    2
    3
    4
    5
  14. PUSH 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0xfe
SAR
---
0x0000000000000000000000000000000000000000000000000000000000000001
    1
    2
    3
    4
    5
  15. PUSH 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0xff
SAR
---
0x0000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5
  16. PUSH 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x0100
SAR
---
0x0000000000000000000000000000000000000000000000000000000000000000
    1
    2
    3
    4
    5

# 实现

Client support:

  • cpp-ethereum: https://github.com/ethereum/cpp-ethereum/pull/4054

Compiler support:

  • Solidity/LLL: https://github.com/ethereum/solidity/pull/2541

# 测试

Sources:

  • https://github.com/ethereum/tests/tree/develop/src/GeneralStateTestsFiller/stShift

Filled Tests:

  • https://github.com/ethereum/tests/tree/develop/GeneralStateTests/stShift
  • https://github.com/ethereum/tests/tree/develop/BlockchainTests/GeneralStateTests/stShift

# 版权

Copyright and related rights waived via CC0.

← EIP 150 : 调整重IO操作的Gas 消耗 →