diff options
| -rw-r--r-- | core/vm/analysis.go | 44 | ||||
| -rw-r--r-- | core/vm/analysis_test.go | 37 |
2 files changed, 72 insertions, 9 deletions
diff --git a/core/vm/analysis.go b/core/vm/analysis.go index d5f048d1d..b27dee8dc 100644 --- a/core/vm/analysis.go +++ b/core/vm/analysis.go @@ -41,21 +41,47 @@ func (d destinations) has(codehash common.Hash, code []byte, dest *big.Int) bool m = jumpdests(code) d[codehash] = m } - return (m[udest/8] & (1 << (udest % 8))) != 0 + return OpCode(code[udest]) == JUMPDEST && (m[udest/8]&(0x80>>(udest%8))) == 0 + // return (m[udest/8] & (1 << (udest % 8))) != 0 +} + +type bitvec struct { + m []byte +} + +func (bits *bitvec) addone(pos uint64) { + bits.m[pos/8] |= 0x80 >> (pos % 8) +} +func (bits *bitvec) addOneByte(pos uint64) { + bits.m[pos/8] |= 0xFF >> (pos % 8) + bits.m[pos/8+1] |= ^(0xFF >> (pos % 8)) } // jumpdests creates a map that contains an entry for each // PC location that is a JUMPDEST instruction. func jumpdests(code []byte) []byte { - m := make([]byte, len(code)/8+1) - for pc := uint64(0); pc < uint64(len(code)); pc++ { + //The map is 4 bytes longer than necessary, in case the code + // ends with a PUSH32, the algorithm will push zeroes onto the + // bitvector outside the bounds of the actual code. + m := make([]byte, len(code)/8+1+4) + bits := &bitvec{m} + for pc := uint64(0); pc < uint64(len(code)); { op := OpCode(code[pc]) - if op == JUMPDEST { - m[pc/8] |= 1 << (pc % 8) - } else if op >= PUSH1 && op <= PUSH32 { - a := uint64(op) - uint64(PUSH1) + 1 - pc += a + + if op >= PUSH1 && op <= PUSH32 { + numbits := op - PUSH1 + 1 + pc++ + for ; numbits >= 8; numbits -= 8 { + bits.addOneByte(pc) // 8 + pc += 8 + } + for ; numbits > 0; numbits-- { + bits.addone(pc) + pc++ + } + } else { + pc++ } } - return m + return bits.m } diff --git a/core/vm/analysis_test.go b/core/vm/analysis_test.go new file mode 100644 index 000000000..17c578e95 --- /dev/null +++ b/core/vm/analysis_test.go @@ -0,0 +1,37 @@ +package vm + +import "testing" + +func TestJumpDestAnalysis(t *testing.T) { + tests := []struct { + code []byte + exp byte + which int + }{ + {[]byte{byte(PUSH1), 0x01, 0x01, 0x01}, 0x40, 0}, + {[]byte{byte(PUSH1), byte(PUSH1), byte(PUSH1), byte(PUSH1)}, 0x50, 0}, + {[]byte{byte(PUSH8), byte(PUSH8), byte(PUSH8), byte(PUSH8), byte(PUSH8), byte(PUSH8), byte(PUSH8), byte(PUSH8), 0x01, 0x01, 0x01}, 0x7F, 0}, + {[]byte{byte(PUSH8), 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01}, 0x80, 1}, + {[]byte{0x01, 0x01, 0x01, 0x01, 0x01, byte(PUSH2), byte(PUSH2), byte(PUSH2), 0x01, 0x01, 0x01}, 0x03, 0}, + {[]byte{0x01, 0x01, 0x01, 0x01, 0x01, byte(PUSH2), 0x01, 0x01, 0x01, 0x01, 0x01}, 0x00, 1}, + {[]byte{byte(PUSH3), 0x01, 0x01, 0x01, byte(PUSH1), 0x01, 0x01, 0x01, 0x01, 0x01, 0x01}, 0x74, 0}, + {[]byte{byte(PUSH3), 0x01, 0x01, 0x01, byte(PUSH1), 0x01, 0x01, 0x01, 0x01, 0x01, 0x01}, 0x00, 1}, + {[]byte{0x01, byte(PUSH8), 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01}, 0x3F, 0}, + {[]byte{0x01, byte(PUSH8), 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01}, 0xC0, 1}, + {[]byte{byte(PUSH16), 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01}, 0x7F, 0}, + {[]byte{byte(PUSH16), 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01}, 0xFF, 1}, + {[]byte{byte(PUSH16), 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01}, 0x80, 2}, + {[]byte{byte(PUSH8), 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, byte(PUSH1), 0x01}, 0x7f, 0}, + {[]byte{byte(PUSH8), 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, byte(PUSH1), 0x01}, 0xA0, 1}, + {[]byte{byte(PUSH32)}, 0x7F, 0}, + {[]byte{byte(PUSH32)}, 0xFF, 1}, + {[]byte{byte(PUSH32)}, 0xFF, 2}, + } + for _, test := range tests { + ret := jumpdests(test.code) + if ret[test.which] != test.exp { + t.Fatalf("expected %x, got %02x", test.exp, ret[test.which]) + } + } + +} |