snappy: initial check-in of package snappy.
R=bradfitz, adg
CC=golang-dev
http://codereview.appspot.com/4958041
diff --git a/.hgignore b/.hgignore
index af8f845..055f43c 100644
--- a/.hgignore
+++ b/.hgignore
@@ -11,9 +11,19 @@
[568a].out
*~
*.orig
+*.rej
+*.exe
+.*.swp
core
+*.cgo*.go
+*.cgo*.c
+_cgo_*
_obj
_test
+_testmain.go
+build.out
+test.out
+y.tab.[ch]
syntax:regexp
^.*/core.[0-9]*$
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..dae304b
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,18 @@
+# Copyright 2011 The Snappy-Go Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style
+# license that can be found in the LICENSE file.
+
+include $(GOROOT)/src/Make.inc
+
+all: install
+
+# The order matters: earlier packages may not depend on later ones.
+DIRS=\
+ varint/zigzag\
+ varint\
+ snappy\
+
+install clean nuke:
+ for dir in $(DIRS); do \
+ $(MAKE) -C $$dir $@ || exit 1; \
+ done
diff --git a/snappy/Makefile b/snappy/Makefile
new file mode 100644
index 0000000..707afc8
--- /dev/null
+++ b/snappy/Makefile
@@ -0,0 +1,14 @@
+# Copyright 2011 The Snappy-Go Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style
+# license that can be found in the LICENSE file.
+
+include $(GOROOT)/src/Make.inc
+
+TARG=snappy-go.googlecode.com/hg/snappy
+GOFILES=\
+ decode.go\
+ encode.go\
+ snappy.go\
+
+include $(GOROOT)/src/Make.pkg
+
diff --git a/snappy/decode.go b/snappy/decode.go
new file mode 100644
index 0000000..1749280
--- /dev/null
+++ b/snappy/decode.go
@@ -0,0 +1,122 @@
+// Copyright 2011 The Snappy-Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package snappy
+
+import (
+ "os"
+
+ "snappy-go.googlecode.com/hg/varint"
+)
+
+// ErrCorrupt reports that the input is invalid.
+var ErrCorrupt = os.NewError("snappy: corrupt input")
+
+// DecodedLen returns the length of the decoded block.
+func DecodedLen(src []byte) (int, os.Error) {
+ v, _, err := decodedLen(src)
+ return v, err
+}
+
+// decodedLen returns the length of the decoded block and the number of bytes
+// that the length header occupied.
+func decodedLen(src []byte) (blockLen, headerLen int, err os.Error) {
+ v, n := varint.Decode(src)
+ if n == 0 {
+ return 0, 0, ErrCorrupt
+ }
+ if uint64(int(v)) != v {
+ return 0, 0, os.NewError("snappy: decoded block is too large")
+ }
+ return int(v), n, nil
+}
+
+// Decode returns the decoded form of src. The returned slice may be a sub-
+// slice of dst if dst was large enough to hold the entire decoded block.
+// Otherwise, a newly allocated slice will be returned.
+// It is valid to pass a nil dst.
+func Decode(dst, src []byte) ([]byte, os.Error) {
+ dLen, s, err := decodedLen(src)
+ if err != nil {
+ return nil, err
+ }
+ if len(dst) < dLen {
+ dst = make([]byte, dLen)
+ }
+
+ var d, offset, length int
+ for s < len(src) {
+ switch src[s] & 0x03 {
+ case tagLiteral:
+ x := uint(src[s] >> 2)
+ switch {
+ case x < 60:
+ s += 1
+ case x == 60:
+ s += 2
+ if s > len(src) {
+ return nil, ErrCorrupt
+ }
+ x = uint(src[s-1])
+ case x == 61:
+ s += 3
+ if s > len(src) {
+ return nil, ErrCorrupt
+ }
+ x = uint(src[s-2]) | uint(src[s-1])<<8
+ case x == 62:
+ s += 4
+ if s > len(src) {
+ return nil, ErrCorrupt
+ }
+ x = uint(src[s-3]) | uint(src[s-2])<<8 | uint(src[s-1])<<16
+ case x == 63:
+ s += 5
+ if s > len(src) {
+ return nil, ErrCorrupt
+ }
+ x = uint(src[s-4]) | uint(src[s-3])<<8 | uint(src[s-2])<<16 | uint(src[s-1])<<24
+ }
+ length = int(x + 1)
+ if length <= 0 {
+ return nil, os.NewError("snappy: unsupported literal length")
+ }
+ if length > len(dst)-d || length > len(src)-s {
+ return nil, ErrCorrupt
+ }
+ copy(dst[d:], src[s:s+length])
+ d += length
+ s += length
+ continue
+
+ case tagCopy1:
+ s += 2
+ if s > len(src) {
+ return nil, ErrCorrupt
+ }
+ length = 4 + int(src[s-2])>>2&0x7
+ offset = int(src[s-2])&0xe0<<3 | int(src[s-1])
+
+ case tagCopy2:
+ s += 3
+ if s > len(src) {
+ return nil, ErrCorrupt
+ }
+ length = 1 + int(src[s-3])>>2
+ offset = int(src[s-2]) | int(src[s-1])<<8
+
+ case tagCopy4:
+ return nil, os.NewError("snappy: unsupported COPY_4 tag")
+ }
+
+ end := d + length
+ if offset > d || end > len(dst) {
+ return nil, ErrCorrupt
+ }
+ for ; d < end; d++ {
+ dst[d] = dst[d-offset]
+ }
+ }
+ return dst, nil
+}
diff --git a/snappy/encode.go b/snappy/encode.go
new file mode 100644
index 0000000..3d1fa20
--- /dev/null
+++ b/snappy/encode.go
@@ -0,0 +1,180 @@
+// Copyright 2011 The Snappy-Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package snappy
+
+import (
+ "os"
+
+ "snappy-go.googlecode.com/hg/varint"
+)
+
+// We limit how far copy back-references can go, the same as the C++ code.
+const maxOffset = 1 << 15
+
+// equal4 returns whether b[i:i+4] equals b[j:j+4].
+func equal4(b []byte, i, j int) bool {
+ return b[i] == b[j] &&
+ b[i+1] == b[j+1] &&
+ b[i+2] == b[j+2] &&
+ b[i+3] == b[j+3]
+}
+
+// emitLiteral writes a literal chunk and returns the number of bytes written.
+func emitLiteral(dst, lit []byte) int {
+ i, n := 0, uint(len(lit)-1)
+ switch {
+ case n < 60:
+ dst[0] = uint8(n)<<2 | tagLiteral
+ i = 1
+ case n < 1<<8:
+ dst[0] = 60<<2 | tagLiteral
+ dst[1] = uint8(n)
+ i = 2
+ case n < 1<<16:
+ dst[0] = 61<<2 | tagLiteral
+ dst[1] = uint8(n)
+ dst[2] = uint8(n >> 8)
+ i = 3
+ case n < 1<<24:
+ dst[0] = 62<<2 | tagLiteral
+ dst[1] = uint8(n)
+ dst[2] = uint8(n >> 8)
+ dst[3] = uint8(n >> 16)
+ i = 4
+ case int64(n) < 1<<32:
+ dst[0] = 63<<2 | tagLiteral
+ dst[1] = uint8(n)
+ dst[2] = uint8(n >> 8)
+ dst[3] = uint8(n >> 16)
+ dst[4] = uint8(n >> 24)
+ i = 5
+ default:
+ panic("snappy: source buffer is too long")
+ }
+ if copy(dst[i:], lit) != len(lit) {
+ panic("snappy: destination buffer is too short")
+ }
+ return i + len(lit)
+}
+
+// emitCopy writes a copy chunk and returns the number of bytes written.
+func emitCopy(dst []byte, offset, length int) int {
+ i := 0
+ for length > 0 {
+ x := length - 4
+ if 0 <= x && x < 1<<3 && offset < 1<<11 {
+ dst[i+0] = uint8(offset>>8)&0x07<<5 | uint8(x)<<2 | tagCopy1
+ dst[i+1] = uint8(offset)
+ i += 2
+ break
+ }
+
+ x = length
+ if x > 1<<6 {
+ x = 1 << 6
+ }
+ dst[i+0] = uint8(x-1)<<2 | tagCopy2
+ dst[i+1] = uint8(offset)
+ dst[i+2] = uint8(offset >> 8)
+ i += 3
+ length -= x
+ }
+ return i
+}
+
+// Encode returns the encoded form of src. The returned slice may be a sub-
+// slice of dst if dst was large enough to hold the entire encoded block.
+// Otherwise, a newly allocated slice will be returned.
+// It is valid to pass a nil dst.
+func Encode(dst, src []byte) ([]byte, os.Error) {
+ if n := MaxEncodedLen(len(src)); len(dst) < n {
+ dst = make([]byte, n)
+ }
+
+ // The block starts with the varint-encoded length of the decompressed bytes.
+ d := varint.Encode(dst, uint64(len(src)))
+
+ // Return early if src is short.
+ if len(src) <= 4 {
+ d += emitLiteral(dst[d:], src)
+ return dst[:d], nil
+ }
+
+ // Initialize the hash table. Its size ranges from 1<<8 to 1<<14 inclusive.
+ const maxTableSize = 1 << 14
+ shift, tableSize := uint(32-8), 1<<8
+ for tableSize < maxTableSize && tableSize < len(src) {
+ shift--
+ tableSize *= 2
+ }
+ var table [maxTableSize]int
+ for i := 0; i < tableSize; i++ {
+ table[i] = -1
+ }
+
+ // Iterate over the source bytes.
+ var (
+ s int // The iterator position.
+ t int // The last position with the same hash as s.
+ lit int // The start position of any pending literal bytes.
+ )
+ for s+3 < len(src) {
+ // Update the hash table.
+ h := uint32(src[s]) | uint32(src[s+1])<<8 | uint32(src[s+2])<<16 | uint32(src[s+3])<<24
+ h = (h * 0x1e35a7bd) >> shift
+ t, table[h] = table[h], s
+ // If t is invalid or src[s:s+4] differs from src[t:t+4], accumulate a literal byte.
+ if t < 0 || s-t >= maxOffset || !equal4(src, t, s) {
+ s++
+ continue
+ }
+ // Otherwise, we have a match. First, emit any pending literal bytes.
+ if lit != s {
+ d += emitLiteral(dst[d:], src[lit:s])
+ }
+ // Extend the match to be as long as possible.
+ s0 := s
+ s, t = s+4, t+4
+ for s < len(src) && src[s] == src[t] {
+ s++
+ t++
+ }
+ // Emit the copied bytes.
+ d += emitCopy(dst[d:], s-t, s-s0)
+ lit = s
+ }
+
+ // Emit any final pending literal bytes and return.
+ if lit != len(src) {
+ d += emitLiteral(dst[d:], src[lit:])
+ }
+ return dst[:d], nil
+}
+
+// MaxEncodedLen returns the maximum length of a snappy block, given its
+// uncompressed length.
+func MaxEncodedLen(srcLen int) int {
+ // Compressed data can be defined as:
+ // compressed := item* literal*
+ // item := literal* copy
+ //
+ // The trailing literal sequence has a space blowup of at most 62/60
+ // since a literal of length 60 needs one tag byte + one extra byte
+ // for length information.
+ //
+ // Item blowup is trickier to measure. Suppose the "copy" op copies
+ // 4 bytes of data. Because of a special check in the encoding code,
+ // we produce a 4-byte copy only if the offset is < 65536. Therefore
+ // the copy op takes 3 bytes to encode, and this type of item leads
+ // to at most the 62/60 blowup for representing literals.
+ //
+ // Suppose the "copy" op copies 5 bytes of data. If the offset is big
+ // enough, it will take 5 bytes to encode the copy op. Therefore the
+ // worst case here is a one-byte literal followed by a five-byte copy.
+ // That is, 6 bytes of input turn into 7 bytes of "compressed" data.
+ //
+ // This last factor dominates the blowup, so the final estimate is:
+ return 32 + srcLen + srcLen/6
+}
diff --git a/snappy/snappy.go b/snappy/snappy.go
new file mode 100644
index 0000000..2f1b790
--- /dev/null
+++ b/snappy/snappy.go
@@ -0,0 +1,38 @@
+// Copyright 2011 The Snappy-Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package snappy implements the snappy block-based compression format.
+// It aims for very high speeds and reasonable compression.
+//
+// The C++ snappy implementation is at http://code.google.com/p/snappy/
+package snappy
+
+/*
+Each encoded block begins with the varint-encoded length of the decoded data,
+followed by a sequence of chunks. Chunks begin and end on byte boundaries. The
+first byte of each chunk is broken into its 2 least and 6 most significant bits
+called l and m: l ranges in [0, 4) and m ranges in [0, 64). l is the chunk tag.
+Zero means a literal tag. All other values mean a copy tag.
+
+For literal tags:
+ - If m < 60, the next 1 + m bytes are literal bytes.
+ - Otherwise, let n be the little-endian unsigned integer denoted by the next
+ m - 59 bytes. The next 1 + n bytes after that are literal bytes.
+
+For copy tags, length bytes are copied from offset bytes ago, in the style of
+Lempel-Ziv compression algorithms. In particular:
+ - For l == 1, the offset ranges in [0, 1<<11) and the length in [4, 12).
+ The length is 4 + the low 3 bits of m. The high 3 bits of m form bits 8-10
+ of the offset. The next byte is bits 0-7 of the offset.
+ - For l == 2, the offset ranges in [0, 1<<16) and the length in [1, 65).
+ The length is 1 + m. The offset is the little-endian unsigned integer
+ denoted by the next 2 bytes.
+ - For l == 3, this tag is a legacy format that is no longer supported.
+*/
+const (
+ tagLiteral = 0x00
+ tagCopy1 = 0x01
+ tagCopy2 = 0x02
+ tagCopy4 = 0x03
+)
diff --git a/snappy/snappy_test.go b/snappy/snappy_test.go
new file mode 100644
index 0000000..bb266e9
--- /dev/null
+++ b/snappy/snappy_test.go
@@ -0,0 +1,118 @@
+// Copyright 2011 The Snappy-Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package snappy
+
+import (
+ "bytes"
+ "fmt"
+ "io/ioutil"
+ "os"
+ "rand"
+ "strings"
+ "testing"
+)
+
+func roundtrip(b []byte) os.Error {
+ e, err := Encode(nil, b)
+ if err != nil {
+ return fmt.Errorf("encoding error: %v", err)
+ }
+ d, err := Decode(nil, e)
+ if err != nil {
+ return fmt.Errorf("decoding error: %v", err)
+ }
+ if !bytes.Equal(b, d) {
+ return fmt.Errorf("roundtrip mismatch:\n\twant %v\n\tgot %v", b, d)
+ }
+ return nil
+}
+
+func TestSmallCopy(t *testing.T) {
+ for i := 0; i < 32; i++ {
+ s := "aaaa" + strings.Repeat("b", i) + "aaaabbbb"
+ if err := roundtrip([]byte(s)); err != nil {
+ t.Fatalf("i=%d: %v", i, err)
+ }
+ }
+}
+
+func TestSmallRand(t *testing.T) {
+ rand.Seed(27354294)
+ for n := 1; n < 20000; n += 23 {
+ b := make([]byte, n)
+ for i, _ := range b {
+ b[i] = uint8(rand.Uint32())
+ }
+ if err := roundtrip(b); err != nil {
+ t.Fatal(err)
+ }
+ }
+}
+
+func TestSmallRegular(t *testing.T) {
+ for n := 1; n < 20000; n += 23 {
+ b := make([]byte, n)
+ for i, _ := range b {
+ b[i] = uint8(i%10 + 'a')
+ }
+ if err := roundtrip(b); err != nil {
+ t.Fatal(err)
+ }
+ }
+}
+
+func benchWords(b *testing.B, n int, decode bool) {
+ b.StopTimer()
+
+ // Make src, a []byte of length n containing copies of the words file.
+ words, err := ioutil.ReadFile("/usr/share/dict/words")
+ if err != nil {
+ panic(err)
+ }
+ if len(words) == 0 {
+ panic("/usr/share/dict/words has zero length")
+ }
+ src := make([]byte, n)
+ for x := src; len(x) > 0; {
+ n := copy(x, words)
+ x = x[n:]
+ }
+
+ // If benchmarking decoding, encode the src.
+ if decode {
+ src, err = Encode(nil, src)
+ if err != nil {
+ panic(err)
+ }
+ }
+ b.SetBytes(int64(len(src)))
+
+ // Allocate a sufficiently large dst buffer.
+ var dst []byte
+ if decode {
+ dst = make([]byte, n)
+ } else {
+ dst = make([]byte, MaxEncodedLen(n))
+ }
+
+ // Run the loop.
+ b.StartTimer()
+ for i := 0; i < b.N; i++ {
+ if decode {
+ Decode(dst, src)
+ } else {
+ Encode(dst, src)
+ }
+ }
+}
+
+func BenchmarkDecodeWords1e3(b *testing.B) { benchWords(b, 1e3, true) }
+func BenchmarkDecodeWords1e4(b *testing.B) { benchWords(b, 1e4, true) }
+func BenchmarkDecodeWords1e5(b *testing.B) { benchWords(b, 1e5, true) }
+func BenchmarkDecodeWords1e6(b *testing.B) { benchWords(b, 1e6, true) }
+func BenchmarkEncodeWords1e3(b *testing.B) { benchWords(b, 1e3, false) }
+func BenchmarkEncodeWords1e4(b *testing.B) { benchWords(b, 1e4, false) }
+func BenchmarkEncodeWords1e5(b *testing.B) { benchWords(b, 1e5, false) }
+func BenchmarkEncodeWords1e6(b *testing.B) { benchWords(b, 1e6, false) }
