From 44d40ffce1200ce8875e187b57ac17e4901db32a Mon Sep 17 00:00:00 2001 From: Martin Holst Swende Date: Fri, 23 Feb 2018 11:32:57 +0100 Subject: core, vm, common: define constantinople fork + shift (#16045) * core, vm, common: define constantinople fork, start implementation of shift instructions * vm: more testcases * vm: add tests for intpool erroneous intpool handling * core, vm, common: fix constantinople review concerns * vm: add string<->op definitions for new opcodes --- core/vm/instructions.go | 60 +++++++++++++++++ core/vm/instructions_test.go | 153 +++++++++++++++++++++++++++++++++++++++++++ core/vm/interpreter.go | 2 + core/vm/jump_table.go | 33 +++++++++- core/vm/opcodes.go | 9 +++ 5 files changed, 254 insertions(+), 3 deletions(-) (limited to 'core/vm') diff --git a/core/vm/instructions.go b/core/vm/instructions.go index 766172501..6daf4e10d 100644 --- a/core/vm/instructions.go +++ b/core/vm/instructions.go @@ -302,6 +302,66 @@ func opMulmod(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *S return nil, nil } +// opSHL implements 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. +func opSHL(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) { + // Note, second operand is left in the stack; accumulate result into it, and no need to push it afterwards + shift, value := math.U256(stack.pop()), math.U256(stack.peek()) + defer evm.interpreter.intPool.put(shift) // First operand back into the pool + + if shift.Cmp(common.Big256) >= 0 { + value.SetUint64(0) + return nil, nil + } + n := uint(shift.Uint64()) + math.U256(value.Lsh(value, n)) + + return nil, nil +} + +// opSHR implements 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. +func opSHR(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) { + // Note, second operand is left in the stack; accumulate result into it, and no need to push it afterwards + shift, value := math.U256(stack.pop()), math.U256(stack.peek()) + defer evm.interpreter.intPool.put(shift) // First operand back into the pool + + if shift.Cmp(common.Big256) >= 0 { + value.SetUint64(0) + return nil, nil + } + n := uint(shift.Uint64()) + math.U256(value.Rsh(value, n)) + + return nil, nil +} + +// opSAR implements 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. +func opSAR(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) { + // Note, S256 returns (potentially) a new bigint, so we're popping, not peeking this one + shift, value := math.U256(stack.pop()), math.S256(stack.pop()) + defer evm.interpreter.intPool.put(shift) // First operand back into the pool + + if shift.Cmp(common.Big256) >= 0 { + if value.Sign() > 0 { + value.SetUint64(0) + } else { + value.SetInt64(-1) + } + stack.push(math.U256(value)) + return nil, nil + } + n := uint(shift.Uint64()) + value.Rsh(value, n) + stack.push(math.U256(value)) + + return nil, nil +} + func opSha3(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) { offset, size := stack.pop(), stack.pop() data := memory.Get(offset.Int64(), size.Int64()) diff --git a/core/vm/instructions_test.go b/core/vm/instructions_test.go index 180433ea8..eef4328bd 100644 --- a/core/vm/instructions_test.go +++ b/core/vm/instructions_test.go @@ -24,6 +24,48 @@ import ( "github.com/ethereum/go-ethereum/params" ) +type twoOperandTest struct { + x string + y string + expected string +} + +func testTwoOperandOp(t *testing.T, tests []twoOperandTest, opFn func(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Stack) ([]byte, error)) { + var ( + env = NewEVM(Context{}, nil, params.TestChainConfig, Config{EnableJit: false, ForceJit: false}) + stack = newstack() + pc = uint64(0) + ) + for i, test := range tests { + x := new(big.Int).SetBytes(common.Hex2Bytes(test.x)) + shift := new(big.Int).SetBytes(common.Hex2Bytes(test.y)) + expected := new(big.Int).SetBytes(common.Hex2Bytes(test.expected)) + stack.push(x) + stack.push(shift) + opFn(&pc, env, nil, nil, stack) + actual := stack.pop() + if actual.Cmp(expected) != 0 { + t.Errorf("Testcase %d, expected %v, got %v", i, expected, actual) + } + // Check pool usage + // 1.pool is not allowed to contain anything on the stack + // 2.pool is not allowed to contain the same pointers twice + if env.interpreter.intPool.pool.len() > 0 { + + poolvals := make(map[*big.Int]struct{}) + poolvals[actual] = struct{}{} + + for env.interpreter.intPool.pool.len() > 0 { + key := env.interpreter.intPool.get() + if _, exist := poolvals[key]; exist { + t.Errorf("Testcase %d, pool contains double-entry", i) + } + poolvals[key] = struct{}{} + } + } + } +} + func TestByteOp(t *testing.T) { var ( env = NewEVM(Context{}, nil, params.TestChainConfig, Config{EnableJit: false, ForceJit: false}) @@ -57,6 +99,98 @@ func TestByteOp(t *testing.T) { } } +func TestSHL(t *testing.T) { + // Testcases from https://github.com/ethereum/EIPs/blob/master/EIPS/eip-145.md#shl-shift-left + tests := []twoOperandTest{ + {"0000000000000000000000000000000000000000000000000000000000000001", "00", "0000000000000000000000000000000000000000000000000000000000000001"}, + {"0000000000000000000000000000000000000000000000000000000000000001", "01", "0000000000000000000000000000000000000000000000000000000000000002"}, + {"0000000000000000000000000000000000000000000000000000000000000001", "ff", "8000000000000000000000000000000000000000000000000000000000000000"}, + {"0000000000000000000000000000000000000000000000000000000000000001", "0100", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"0000000000000000000000000000000000000000000000000000000000000001", "0101", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "00", "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "01", "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "ff", "8000000000000000000000000000000000000000000000000000000000000000"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0100", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"0000000000000000000000000000000000000000000000000000000000000000", "01", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "01", "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"}, + } + testTwoOperandOp(t, tests, opSHL) +} + +func TestSHR(t *testing.T) { + // Testcases from https://github.com/ethereum/EIPs/blob/master/EIPS/eip-145.md#shr-logical-shift-right + tests := []twoOperandTest{ + {"0000000000000000000000000000000000000000000000000000000000000001", "00", "0000000000000000000000000000000000000000000000000000000000000001"}, + {"0000000000000000000000000000000000000000000000000000000000000001", "01", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"8000000000000000000000000000000000000000000000000000000000000000", "01", "4000000000000000000000000000000000000000000000000000000000000000"}, + {"8000000000000000000000000000000000000000000000000000000000000000", "ff", "0000000000000000000000000000000000000000000000000000000000000001"}, + {"8000000000000000000000000000000000000000000000000000000000000000", "0100", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"8000000000000000000000000000000000000000000000000000000000000000", "0101", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "00", "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "01", "7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "ff", "0000000000000000000000000000000000000000000000000000000000000001"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0100", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"0000000000000000000000000000000000000000000000000000000000000000", "01", "0000000000000000000000000000000000000000000000000000000000000000"}, + } + testTwoOperandOp(t, tests, opSHR) +} + +func TestSAR(t *testing.T) { + // Testcases from https://github.com/ethereum/EIPs/blob/master/EIPS/eip-145.md#sar-arithmetic-shift-right + tests := []twoOperandTest{ + {"0000000000000000000000000000000000000000000000000000000000000001", "00", "0000000000000000000000000000000000000000000000000000000000000001"}, + {"0000000000000000000000000000000000000000000000000000000000000001", "01", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"8000000000000000000000000000000000000000000000000000000000000000", "01", "c000000000000000000000000000000000000000000000000000000000000000"}, + {"8000000000000000000000000000000000000000000000000000000000000000", "ff", "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"}, + {"8000000000000000000000000000000000000000000000000000000000000000", "0100", "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"}, + {"8000000000000000000000000000000000000000000000000000000000000000", "0101", "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "00", "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "01", "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "ff", "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0100", "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"}, + {"0000000000000000000000000000000000000000000000000000000000000000", "01", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"4000000000000000000000000000000000000000000000000000000000000000", "fe", "0000000000000000000000000000000000000000000000000000000000000001"}, + {"7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "f8", "000000000000000000000000000000000000000000000000000000000000007f"}, + {"7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "fe", "0000000000000000000000000000000000000000000000000000000000000001"}, + {"7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "ff", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0100", "0000000000000000000000000000000000000000000000000000000000000000"}, + } + + testTwoOperandOp(t, tests, opSAR) +} + +func TestSGT(t *testing.T) { + tests := []twoOperandTest{ + {"0000000000000000000000000000000000000000000000000000000000000001", "0000000000000000000000000000000000000000000000000000000000000001", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"0000000000000000000000000000000000000000000000000000000000000001", "7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0000000000000000000000000000000000000000000000000000000000000001"}, + {"7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0000000000000000000000000000000000000000000000000000000000000001", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0000000000000000000000000000000000000000000000000000000000000001", "0000000000000000000000000000000000000000000000000000000000000001"}, + {"0000000000000000000000000000000000000000000000000000000000000001", "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"8000000000000000000000000000000000000000000000000000000000000001", "8000000000000000000000000000000000000000000000000000000000000001", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"8000000000000000000000000000000000000000000000000000000000000001", "7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0000000000000000000000000000000000000000000000000000000000000001"}, + {"7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "8000000000000000000000000000000000000000000000000000000000000001", "0000000000000000000000000000000000000000000000000000000000000000"}, + } + testTwoOperandOp(t, tests, opSgt) +} + +func TestSLT(t *testing.T) { + tests := []twoOperandTest{ + {"0000000000000000000000000000000000000000000000000000000000000001", "0000000000000000000000000000000000000000000000000000000000000001", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"0000000000000000000000000000000000000000000000000000000000000001", "7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0000000000000000000000000000000000000000000000000000000000000001", "0000000000000000000000000000000000000000000000000000000000000001"}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0000000000000000000000000000000000000000000000000000000000000001", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"0000000000000000000000000000000000000000000000000000000000000001", "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0000000000000000000000000000000000000000000000000000000000000001"}, + {"8000000000000000000000000000000000000000000000000000000000000001", "8000000000000000000000000000000000000000000000000000000000000001", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"8000000000000000000000000000000000000000000000000000000000000001", "7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0000000000000000000000000000000000000000000000000000000000000000"}, + {"7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "8000000000000000000000000000000000000000000000000000000000000001", "0000000000000000000000000000000000000000000000000000000000000001"}, + } + testTwoOperandOp(t, tests, opSlt) +} + func opBenchmark(bench *testing.B, op func(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Stack) ([]byte, error), args ...string) { var ( env = NewEVM(Context{}, nil, params.TestChainConfig, Config{EnableJit: false, ForceJit: false}) @@ -259,3 +393,22 @@ func BenchmarkOpMulmod(b *testing.B) { opBenchmark(b, opMulmod, x, y, z) } + +func BenchmarkOpSHL(b *testing.B) { + x := "FBCDEF090807060504030201ffffffffFBCDEF090807060504030201ffffffff" + y := "ff" + + opBenchmark(b, opSHL, x, y) +} +func BenchmarkOpSHR(b *testing.B) { + x := "FBCDEF090807060504030201ffffffffFBCDEF090807060504030201ffffffff" + y := "ff" + + opBenchmark(b, opSHR, x, y) +} +func BenchmarkOpSAR(b *testing.B) { + x := "FBCDEF090807060504030201ffffffffFBCDEF090807060504030201ffffffff" + y := "ff" + + opBenchmark(b, opSAR, x, y) +} diff --git a/core/vm/interpreter.go b/core/vm/interpreter.go index 82a6d3de6..e12dd7e5a 100644 --- a/core/vm/interpreter.go +++ b/core/vm/interpreter.go @@ -68,6 +68,8 @@ func NewInterpreter(evm *EVM, cfg Config) *Interpreter { // we'll set the default jump table. if !cfg.JumpTable[STOP].valid { switch { + case evm.ChainConfig().IsConstantinople(evm.BlockNumber): + cfg.JumpTable = constantinopleInstructionSet case evm.ChainConfig().IsByzantium(evm.BlockNumber): cfg.JumpTable = byzantiumInstructionSet case evm.ChainConfig().IsHomestead(evm.BlockNumber): diff --git a/core/vm/jump_table.go b/core/vm/jump_table.go index a1c5ad9c6..338994135 100644 --- a/core/vm/jump_table.go +++ b/core/vm/jump_table.go @@ -51,11 +51,38 @@ type operation struct { } var ( - frontierInstructionSet = NewFrontierInstructionSet() - homesteadInstructionSet = NewHomesteadInstructionSet() - byzantiumInstructionSet = NewByzantiumInstructionSet() + frontierInstructionSet = NewFrontierInstructionSet() + homesteadInstructionSet = NewHomesteadInstructionSet() + byzantiumInstructionSet = NewByzantiumInstructionSet() + constantinopleInstructionSet = NewConstantinopleInstructionSet() ) +// NewConstantinopleInstructionSet returns the frontier, homestead +// byzantium and contantinople instructions. +func NewConstantinopleInstructionSet() [256]operation { + // instructions that can be executed during the byzantium phase. + instructionSet := NewByzantiumInstructionSet() + instructionSet[SHL] = operation{ + execute: opSHL, + gasCost: constGasFunc(GasFastestStep), + validateStack: makeStackFunc(2, 1), + valid: true, + } + instructionSet[SHR] = operation{ + execute: opSHR, + gasCost: constGasFunc(GasFastestStep), + validateStack: makeStackFunc(2, 1), + valid: true, + } + instructionSet[SAR] = operation{ + execute: opSAR, + gasCost: constGasFunc(GasFastestStep), + validateStack: makeStackFunc(2, 1), + valid: true, + } + return instructionSet +} + // NewByzantiumInstructionSet returns the frontier, homestead and // byzantium instructions. func NewByzantiumInstructionSet() [256]operation { diff --git a/core/vm/opcodes.go b/core/vm/opcodes.go index 0c6550735..7fe55b72f 100644 --- a/core/vm/opcodes.go +++ b/core/vm/opcodes.go @@ -63,6 +63,9 @@ const ( XOR NOT BYTE + SHL + SHR + SAR SHA3 = 0x20 ) @@ -234,6 +237,9 @@ var opCodeToString = map[OpCode]string{ OR: "OR", XOR: "XOR", BYTE: "BYTE", + SHL: "SHL", + SHR: "SHR", + SAR: "SAR", ADDMOD: "ADDMOD", MULMOD: "MULMOD", @@ -400,6 +406,9 @@ var stringToOp = map[string]OpCode{ "OR": OR, "XOR": XOR, "BYTE": BYTE, + "SHL": SHL, + "SHR": SHR, + "SAR": SAR, "ADDMOD": ADDMOD, "MULMOD": MULMOD, "SHA3": SHA3, -- cgit v1.2.3