aboutsummaryrefslogtreecommitdiffstats
path: root/compression
diff options
context:
space:
mode:
authorobscuren <geffobscura@gmail.com>2014-11-03 06:33:06 +0800
committerobscuren <geffobscura@gmail.com>2014-11-03 06:33:06 +0800
commit9f8bcf3abca8c6c32efc384f6c6eda1677b769c5 (patch)
tree081d285f1ba5a38bf3708c53094f0966e11eee93 /compression
parent1bb398f4e22feef8f83fedd8a525e4da5b627773 (diff)
downloadgo-tangerine-9f8bcf3abca8c6c32efc384f6c6eda1677b769c5.tar
go-tangerine-9f8bcf3abca8c6c32efc384f6c6eda1677b769c5.tar.gz
go-tangerine-9f8bcf3abca8c6c32efc384f6c6eda1677b769c5.tar.bz2
go-tangerine-9f8bcf3abca8c6c32efc384f6c6eda1677b769c5.tar.lz
go-tangerine-9f8bcf3abca8c6c32efc384f6c6eda1677b769c5.tar.xz
go-tangerine-9f8bcf3abca8c6c32efc384f6c6eda1677b769c5.tar.zst
go-tangerine-9f8bcf3abca8c6c32efc384f6c6eda1677b769c5.zip
Added RLE compression. Closes #171
Diffstat (limited to 'compression')
-rw-r--r--compression/rle/read_write.go82
-rw-r--r--compression/rle/read_write_test.go93
2 files changed, 175 insertions, 0 deletions
diff --git a/compression/rle/read_write.go b/compression/rle/read_write.go
new file mode 100644
index 000000000..e6f78e372
--- /dev/null
+++ b/compression/rle/read_write.go
@@ -0,0 +1,82 @@
+package rle
+
+import (
+ "bytes"
+ "errors"
+
+ "github.com/ethereum/go-ethereum/crypto"
+)
+
+const (
+ token byte = 0xfe
+ emptyShaToken = 0xfd
+ emptyListShaToken = 0xfe
+ tokenToken = 0xff
+)
+
+var empty = crypto.Sha3([]byte(""))
+var emptyList = crypto.Sha3([]byte{0x80})
+
+func Decompress(dat []byte) ([]byte, error) {
+ buf := new(bytes.Buffer)
+
+ for i := 0; i < len(dat); i++ {
+ if dat[i] == token {
+ if i+1 < len(dat) {
+ switch dat[i+1] {
+ case emptyShaToken:
+ buf.Write(empty)
+ case emptyListShaToken:
+ buf.Write(emptyList)
+ case tokenToken:
+ buf.WriteByte(token)
+ default:
+ buf.Write(make([]byte, int(dat[i+1]-2)))
+ }
+ i++
+ } else {
+ return nil, errors.New("error reading bytes. token encountered without proceeding bytes")
+ }
+ }
+ }
+
+ return buf.Bytes(), nil
+}
+
+func Compress(dat []byte) []byte {
+ buf := new(bytes.Buffer)
+
+ for i := 0; i < len(dat); i++ {
+ if dat[i] == token {
+ buf.Write([]byte{token, tokenToken})
+ } else if i+1 < len(dat) {
+ if dat[i] == 0x0 && dat[i+1] == 0x0 {
+ j := 0
+ for j <= 254 && i+j < len(dat) {
+ if dat[i+j] != 0 {
+ break
+ }
+ j++
+ }
+ buf.Write([]byte{token, byte(j + 2)})
+ i += (j - 1)
+ } else if len(dat[i:]) >= 32 {
+ if dat[i] == empty[0] && bytes.Compare(dat[i:i+32], empty) == 0 {
+ buf.Write([]byte{token, emptyShaToken})
+ i += 31
+ } else if dat[i] == emptyList[0] && bytes.Compare(dat[i:i+32], emptyList) == 0 {
+ buf.Write([]byte{token, emptyListShaToken})
+ i += 31
+ } else {
+ buf.WriteByte(dat[i])
+ }
+ } else {
+ buf.WriteByte(dat[i])
+ }
+ } else {
+ buf.WriteByte(dat[i])
+ }
+ }
+
+ return buf.Bytes()
+}
diff --git a/compression/rle/read_write_test.go b/compression/rle/read_write_test.go
new file mode 100644
index 000000000..944822a47
--- /dev/null
+++ b/compression/rle/read_write_test.go
@@ -0,0 +1,93 @@
+package rle
+
+import (
+ "bytes"
+ "testing"
+
+ "github.com/ethereum/go-ethereum/crypto"
+)
+
+func TestDecompressSimple(t *testing.T) {
+ res, err := Decompress([]byte{token, 0xfd})
+ if err != nil {
+ t.Error(err)
+ }
+ if bytes.Compare(res, crypto.Sha3([]byte(""))) != 0 {
+ t.Error("empty sha3", res)
+ }
+
+ res, err = Decompress([]byte{token, 0xfe})
+ if err != nil {
+ t.Error(err)
+ }
+ if bytes.Compare(res, crypto.Sha3([]byte{0x80})) != 0 {
+ t.Error("0x80 sha3", res)
+ }
+
+ res, err = Decompress([]byte{token, 0xff})
+ if err != nil {
+ t.Error(err)
+ }
+ if bytes.Compare(res, []byte{token}) != 0 {
+ t.Error("token", res)
+ }
+
+ res, err = Decompress([]byte{token, 12})
+ if err != nil {
+ t.Error(err)
+ }
+ if bytes.Compare(res, make([]byte, 10)) != 0 {
+ t.Error("10 * zero", res)
+ }
+}
+
+func TestDecompressMulti(t *testing.T) {
+ res, err := Decompress([]byte{token, 0xfd, token, 0xfe, token, 12})
+ if err != nil {
+ t.Error(err)
+ }
+
+ var exp []byte
+ exp = append(exp, crypto.Sha3([]byte(""))...)
+ exp = append(exp, crypto.Sha3([]byte{0x80})...)
+ exp = append(exp, make([]byte, 10)...)
+
+ if bytes.Compare(res, res) != 0 {
+ t.Error("Expected", exp, "result", res)
+ }
+}
+
+func TestCompressSimple(t *testing.T) {
+ res := Compress([]byte{0, 0, 0, 0, 0})
+ if bytes.Compare(res, []byte{token, 7}) != 0 {
+ t.Error("5 * zero", res)
+ }
+
+ res = Compress(crypto.Sha3([]byte("")))
+ if bytes.Compare(res, []byte{token, emptyShaToken}) != 0 {
+ t.Error("empty sha", res)
+ }
+
+ res = Compress(crypto.Sha3([]byte{0x80}))
+ if bytes.Compare(res, []byte{token, emptyListShaToken}) != 0 {
+ t.Error("empty list sha", res)
+ }
+
+ res = Compress([]byte{token})
+ if bytes.Compare(res, []byte{token, tokenToken}) != 0 {
+ t.Error("token", res)
+ }
+}
+
+func TestCompressMulti(t *testing.T) {
+ in := []byte{0, 0, 0, 0, 0}
+ in = append(in, crypto.Sha3([]byte(""))...)
+ in = append(in, crypto.Sha3([]byte{0x80})...)
+ in = append(in, token)
+ res := Compress(in)
+
+ exp := []byte{token, 7, token, emptyShaToken, token, emptyListShaToken, token, tokenToken}
+ if bytes.Compare(res, exp) != 0 {
+ t.Error("expected", exp, "got", res)
+ }
+}