aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMartin Holst Swende <martin@swende.se>2017-06-04 01:01:22 +0800
committerMartin Holst Swende <martin@swende.se>2017-06-05 15:15:46 +0800
commitf4b5f67ee07dabc25b5baab0a94f3420606fd0ea (patch)
tree11b0da74c832879cce602e220e2510fe9e0f8f66
parent6171d01b1195abd7ac75044dcd507d4758d83cde (diff)
downloadgo-tangerine-f4b5f67ee07dabc25b5baab0a94f3420606fd0ea.tar
go-tangerine-f4b5f67ee07dabc25b5baab0a94f3420606fd0ea.tar.gz
go-tangerine-f4b5f67ee07dabc25b5baab0a94f3420606fd0ea.tar.bz2
go-tangerine-f4b5f67ee07dabc25b5baab0a94f3420606fd0ea.tar.lz
go-tangerine-f4b5f67ee07dabc25b5baab0a94f3420606fd0ea.tar.xz
go-tangerine-f4b5f67ee07dabc25b5baab0a94f3420606fd0ea.tar.zst
go-tangerine-f4b5f67ee07dabc25b5baab0a94f3420606fd0ea.zip
core/vm: improved jumpdest analysis
-rw-r--r--core/vm/analysis.go44
-rw-r--r--core/vm/analysis_test.go37
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])
+ }
+ }
+
+}