diff options
author | obscuren <geffobscura@gmail.com> | 2014-11-03 06:33:06 +0800 |
---|---|---|
committer | obscuren <geffobscura@gmail.com> | 2014-11-03 06:33:06 +0800 |
commit | 9f8bcf3abca8c6c32efc384f6c6eda1677b769c5 (patch) | |
tree | 081d285f1ba5a38bf3708c53094f0966e11eee93 /compression | |
parent | 1bb398f4e22feef8f83fedd8a525e4da5b627773 (diff) | |
download | dexon-9f8bcf3abca8c6c32efc384f6c6eda1677b769c5.tar dexon-9f8bcf3abca8c6c32efc384f6c6eda1677b769c5.tar.gz dexon-9f8bcf3abca8c6c32efc384f6c6eda1677b769c5.tar.bz2 dexon-9f8bcf3abca8c6c32efc384f6c6eda1677b769c5.tar.lz dexon-9f8bcf3abca8c6c32efc384f6c6eda1677b769c5.tar.xz dexon-9f8bcf3abca8c6c32efc384f6c6eda1677b769c5.tar.zst dexon-9f8bcf3abca8c6c32efc384f6c6eda1677b769c5.zip |
Added RLE compression. Closes #171
Diffstat (limited to 'compression')
-rw-r--r-- | compression/rle/read_write.go | 82 | ||||
-rw-r--r-- | compression/rle/read_write_test.go | 93 |
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) + } +} |