Basic varint and zigzag packages.
diff --git a/varint/Makefile b/varint/Makefile
new file mode 100644
index 0000000..5979656
--- /dev/null
+++ b/varint/Makefile
@@ -0,0 +1,12 @@
+# 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/varint
+GOFILES=\
+ varint.go\
+
+include $(GOROOT)/src/Make.pkg
+
diff --git a/varint/varint.go b/varint/varint.go
new file mode 100644
index 0000000..a52628b
--- /dev/null
+++ b/varint/varint.go
@@ -0,0 +1,50 @@
+// 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 varint implements a variable-width byte encoding of integers.
+//
+// It is the same format used by protocol buffers. The format is described at
+// http://code.google.com/apis/protocolbuffers/docs/encoding.html
+package varint
+
+// MaxLen is the maximum encoded length of a uint64.
+const MaxLen = 10
+
+// Len returns the number of bytes used to represent v.
+func Len(v uint64) (n int) {
+ for v > 0x7f {
+ v >>= 7
+ n++
+ }
+ return n + 1
+}
+
+// Decode returns the value encoded at the start of src, as well as the number
+// of bytes it occupies. It returns n == 0 if given invalid input.
+func Decode(src []byte) (v uint64, n int) {
+ for shift := uint(0); ; shift += 7 {
+ if n >= len(src) {
+ return 0, 0
+ }
+ b := src[n]
+ n++
+ v |= uint64(b&0x7f) << shift
+ if b&0x80 == 0 {
+ break
+ }
+ }
+ return v, n
+}
+
+// Encode writes the value to the start of dst, and returns the number of bytes
+// written. It panics if len(dst) < Len(v).
+func Encode(dst []byte, v uint64) (n int) {
+ for v > 0x7f {
+ dst[n] = 0x80 | uint8(v&0x7f)
+ v >>= 7
+ n++
+ }
+ dst[n] = uint8(v)
+ return n + 1
+}
diff --git a/varint/varint_test.go b/varint/varint_test.go
new file mode 100644
index 0000000..2587c68
--- /dev/null
+++ b/varint/varint_test.go
@@ -0,0 +1,70 @@
+// 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 varint
+
+import (
+ "testing"
+)
+
+var testCases = []struct {
+ valid bool
+ s string
+ v uint64
+}{
+ // Valid encodings.
+ {true, "\x00", 0},
+ {true, "\x01", 1},
+ {true, "\x7f", 127},
+ {true, "\x80\x01", 128},
+ {true, "\xff\x02", 383},
+ {true, "\x9e\xa7\x05", 86942}, // 86942 = 0x1e + 0x27<<7 + 0x05<<14
+ {true, "\xff\xff\xff\xff\xff\xff\xff\xff\xff\x01", 0xffffffffffffffff},
+ {
+ true,
+ "\x8a\x89\x88\x87\x86\x85\x84\x83\x82\x01",
+ 10 + 9<<7 + 8<<14 + 7<<21 + 6<<28 + 5<<35 + 4<<42 + 3<<49 + 2<<56 + 1<<63,
+ },
+ // Invalid encodings.
+ {false, "", 0},
+ {false, "\x80", 0},
+ {false, "\xff", 0},
+ {false, "\x9e\xa7", 0},
+}
+
+func TestDecode(t *testing.T) {
+ for _, tc := range testCases {
+ v, n := Decode([]byte(tc.s))
+ if v != tc.v {
+ t.Errorf("decode %q: want value %d got %d", tc.s, tc.v, v)
+ continue
+ }
+ m := 0
+ if tc.valid {
+ m = len(tc.s)
+ }
+ if n != m {
+ t.Errorf("decode %q: want length %d got %d", tc.s, m, n)
+ continue
+ }
+ }
+}
+
+func TestEncode(t *testing.T) {
+ for _, tc := range testCases {
+ if !tc.valid {
+ continue
+ }
+ var b [MaxLen]byte
+ n := Encode(b[:], tc.v)
+ if s := string(b[:n]); s != tc.s {
+ t.Errorf("encode %d: want bytes %q got %q", tc.v, tc.s, s)
+ continue
+ }
+ if n != Len(tc.v) {
+ t.Errorf("encode %d: Encode length %d != Len length %d", tc.v, n, Len(tc.v))
+ continue
+ }
+ }
+}
diff --git a/zigzag/Makefile b/zigzag/Makefile
new file mode 100644
index 0000000..f12b3ec
--- /dev/null
+++ b/zigzag/Makefile
@@ -0,0 +1,12 @@
+# 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/zigzag
+GOFILES=\
+ zigzag.go\
+
+include $(GOROOT)/src/Make.pkg
+
diff --git a/zigzag/zigzag.go b/zigzag/zigzag.go
new file mode 100644
index 0000000..a0c1cf4
--- /dev/null
+++ b/zigzag/zigzag.go
@@ -0,0 +1,23 @@
+// 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 zigzag implements the zigzag mapping between signed and unsigned
+// integers:
+// +0 <--> 0
+// -1 <--> 1
+// +1 <--> 2
+// -2 <--> 3
+// +2 <--> 4
+//
+// It is the same format used by protocol buffers. The format is described at
+// http://code.google.com/apis/protocolbuffers/docs/encoding.html
+package zigzag
+
+func Itou64(i int64) uint64 {
+ return uint64(i<<1 ^ i>>63)
+}
+
+func Utoi64(u uint64) int64 {
+ return int64(u>>1) ^ -int64(u&1)
+}
diff --git a/zigzag/zigzag_test.go b/zigzag/zigzag_test.go
new file mode 100644
index 0000000..397fe4a
--- /dev/null
+++ b/zigzag/zigzag_test.go
@@ -0,0 +1,42 @@
+// 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 zigzag
+
+import (
+ "testing"
+)
+
+var testCases = []struct {
+ u uint64
+ i int64
+}{
+ {0, +0},
+ {1, -1},
+ {2, +1},
+ {3, -2},
+ {4, +2},
+ {5, -3},
+ {6, +3},
+ {199, -100},
+ {200, +100},
+ {1<<32 - 2, +1<<31 - 1},
+ {1<<32 - 1, -1<<31 - 0},
+ {1<<32 + 0, +1<<31 + 0},
+ {1<<32 + 1, -1<<31 - 1},
+ {1<<32 + 2, +1<<31 + 1},
+ {1<<64 - 2, +1<<63 - 1},
+ {1<<64 - 1, -1<<63 + 0},
+}
+
+func TestZigzag(t *testing.T) {
+ for _, tc := range testCases {
+ if i := Utoi64(tc.u); i != tc.i {
+ t.Errorf("uint64 %d to int64: want %d got %d", tc.u, tc.i, i)
+ }
+ if u := Itou64(tc.i); u != tc.u {
+ t.Errorf("int64 %d to uint64: want %d got %d", tc.i, tc.u, u)
+ }
+ }
+}
