aboutsummaryrefslogtreecommitdiffstats
path: root/trie
diff options
context:
space:
mode:
authorEthan Buchman <ethan@coinculture.info>2015-08-07 00:39:07 +0800
committerEthan Buchman <ethan@coinculture.info>2015-08-07 02:04:16 +0800
commit46c95940812ccd3f474dc5fab7a5351351e8f105 (patch)
tree8e240a6caecd342d4298e16856753690c5291b18 /trie
parent7baa5977c8c4b1608c2a23615143da414a638b5c (diff)
downloaddexon-46c95940812ccd3f474dc5fab7a5351351e8f105.tar.gz
dexon-46c95940812ccd3f474dc5fab7a5351351e8f105.tar.zst
dexon-46c95940812ccd3f474dc5fab7a5351351e8f105.zip
trie: run codec tests, add benchmarks, faster
Diffstat (limited to 'trie')
-rw-r--r--trie/encoding.go36
-rw-r--r--trie/encoding_test.go58
2 files changed, 70 insertions, 24 deletions
diff --git a/trie/encoding.go b/trie/encoding.go
index 8daf503a3..9c862d78f 100644
--- a/trie/encoding.go
+++ b/trie/encoding.go
@@ -16,10 +16,6 @@
package trie
-import (
- "bytes"
-)
-
func CompactEncode(hexSlice []byte) []byte {
terminator := 0
if hexSlice[len(hexSlice)-1] == 16 {
@@ -38,12 +34,12 @@ func CompactEncode(hexSlice []byte) []byte {
hexSlice = append([]byte{flags, 0}, hexSlice...)
}
- var buff bytes.Buffer
- for i := 0; i < len(hexSlice); i += 2 {
- buff.WriteByte(byte(16*hexSlice[i] + hexSlice[i+1]))
+ l := len(hexSlice) / 2
+ var buf = make([]byte, l)
+ for i := 0; i < l; i++ {
+ buf[i] = 16*hexSlice[2*i] + hexSlice[2*i+1]
}
-
- return buff.Bytes()
+ return buf
}
func CompactDecode(str []byte) []byte {
@@ -62,22 +58,22 @@ func CompactDecode(str []byte) []byte {
}
func CompactHexDecode(str []byte) []byte {
- var nibbles []byte
-
- for _, b := range str {
- nibbles = append(nibbles, b/16)
- nibbles = append(nibbles, b%16)
+ l := len(str)*2 + 1
+ var nibbles = make([]byte, l)
+ for i, b := range str {
+ nibbles[i*2] = b / 16
+ nibbles[i*2+1] = b % 16
}
- nibbles = append(nibbles, 16)
+ nibbles[l-1] = 16
return nibbles
}
-// assumes key is odd length
func DecodeCompact(key []byte) []byte {
- var res []byte
- for i := 0; i < len(key)-1; i += 2 {
- v1, v0 := key[i], key[i+1]
- res = append(res, v1*16+v0)
+ l := len(key) / 2
+ var res = make([]byte, l)
+ for i := 0; i < l; i++ {
+ v1, v0 := key[2*i], key[2*i+1]
+ res[i] = v1*16 + v0
}
return res
}
diff --git a/trie/encoding_test.go b/trie/encoding_test.go
index faaa7f583..e49b57ef0 100644
--- a/trie/encoding_test.go
+++ b/trie/encoding_test.go
@@ -17,9 +17,14 @@
package trie
import (
+ "encoding/hex"
+ "testing"
+
checker "gopkg.in/check.v1"
)
+func Test(t *testing.T) { checker.TestingT(t) }
+
type TrieEncodingSuite struct{}
var _ = checker.Suite(&TrieEncodingSuite{})
@@ -28,22 +33,22 @@ func (s *TrieEncodingSuite) TestCompactEncode(c *checker.C) {
// even compact encode
test1 := []byte{1, 2, 3, 4, 5}
res1 := CompactEncode(test1)
- c.Assert(res1, checker.Equals, "\x11\x23\x45")
+ c.Assert(res1, checker.DeepEquals, []byte("\x11\x23\x45"))
// odd compact encode
test2 := []byte{0, 1, 2, 3, 4, 5}
res2 := CompactEncode(test2)
- c.Assert(res2, checker.Equals, "\x00\x01\x23\x45")
+ c.Assert(res2, checker.DeepEquals, []byte("\x00\x01\x23\x45"))
//odd terminated compact encode
test3 := []byte{0, 15, 1, 12, 11, 8 /*term*/, 16}
res3 := CompactEncode(test3)
- c.Assert(res3, checker.Equals, "\x20\x0f\x1c\xb8")
+ c.Assert(res3, checker.DeepEquals, []byte("\x20\x0f\x1c\xb8"))
// even terminated compact encode
test4 := []byte{15, 1, 12, 11, 8 /*term*/, 16}
res4 := CompactEncode(test4)
- c.Assert(res4, checker.Equals, "\x3f\x1c\xb8")
+ c.Assert(res4, checker.DeepEquals, []byte("\x3f\x1c\xb8"))
}
func (s *TrieEncodingSuite) TestCompactHexDecode(c *checker.C) {
@@ -73,3 +78,48 @@ func (s *TrieEncodingSuite) TestCompactDecode(c *checker.C) {
res = CompactDecode([]byte("\x3f\x1c\xb8"))
c.Assert(res, checker.DeepEquals, exp)
}
+
+func (s *TrieEncodingSuite) TestDecodeCompact(c *checker.C) {
+ exp, _ := hex.DecodeString("012345")
+ res := DecodeCompact([]byte{0, 1, 2, 3, 4, 5})
+ c.Assert(res, checker.DeepEquals, exp)
+
+ exp, _ = hex.DecodeString("012345")
+ res = DecodeCompact([]byte{0, 1, 2, 3, 4, 5, 16})
+ c.Assert(res, checker.DeepEquals, exp)
+
+ exp, _ = hex.DecodeString("abcdef")
+ res = DecodeCompact([]byte{10, 11, 12, 13, 14, 15})
+ c.Assert(res, checker.DeepEquals, exp)
+}
+
+func BenchmarkCompactEncode(b *testing.B) {
+
+ testBytes := []byte{0, 15, 1, 12, 11, 8 /*term*/, 16}
+ for i := 0; i < b.N; i++ {
+ CompactEncode(testBytes)
+ }
+}
+
+func BenchmarkCompactDecode(b *testing.B) {
+ testBytes := []byte{0, 15, 1, 12, 11, 8 /*term*/, 16}
+ for i := 0; i < b.N; i++ {
+ CompactDecode(testBytes)
+ }
+}
+
+func BenchmarkCompactHexDecode(b *testing.B) {
+ testBytes := []byte{7, 6, 6, 5, 7, 2, 6, 2, 16}
+ for i := 0; i < b.N; i++ {
+ CompactHexDecode(testBytes)
+ }
+
+}
+
+func BenchmarkDecodeCompact(b *testing.B) {
+ testBytes := []byte{7, 6, 6, 5, 7, 2, 6, 2, 16}
+ for i := 0; i < b.N; i++ {
+ DecodeCompact(testBytes)
+ }
+
+}