Index: src/0dev.org/encoding/fibonacci/fib.go
==================================================================
--- src/0dev.org/encoding/fibonacci/fib.go
+++ src/0dev.org/encoding/fibonacci/fib.go
@@ -1,16 +1,23 @@
-// Package provides a shifted, reversed fibonacci encoding of unsigned integers.
+// Package provides a shifted fibonacci encoding of unsigned integers.
//
// http://en.wikipedia.org/wiki/Fibonacci_coding maps positive integers as
// 1 - 11, 2 - 011, 3 - 0011, 4 - 1011, 5 - 00011
//
// Incrementing input by one to allow for zero gives
// 0 - 11, 1 - 011, 2 - 0011, 3 - 1011, 4 - 00011
//
// The codes are then reversed so that they are easily stored in uints
// 0 - 11, 1 - 110, 2 - 1100, 3 - 1101, 4 - 11000
+// (so that they are always comparable with each other as there is no need to
+// store the leading number of zeroes which are otherwise required)
package fibonacci
+
+import (
+ _ "fmt"
+ "io"
+)
type Numbers []uint64
// Returns a slice with fibonacci numbers up to the given length
func New(size int) Numbers {
@@ -21,27 +28,26 @@
}
return fibs
}
// Returns a fibonacci code for an integer as specified in the package's doc.
-func (f Numbers) Code(value uint64) (result uint64) {
+func (f Numbers) Code(value uint64) (result uint64, length byte) {
// Increment to encode zero as one
value++
// Find the nearest fibonacci number
- i := 0
- for f[i+1] <= value {
- i++
+ for f[length] <= value {
+ length++
}
// Leading bit that signals the start of a fibonacci-encoded integer
result |= 1
// Find the Zeckendorf's representation by raising a bit for each
// fibonacci number that is less or equal to the difference
// between the value and the previous such number
- for ; i >= 1; i-- {
+ for i := length - 1; i >= 1; i-- {
result <<= 1
if f[i] <= value {
result |= 1
value -= f[i]
}
@@ -48,25 +54,125 @@
}
return
}
// Returns an integer from a fibonacci code as specified in the package's doc.
-func (f Numbers) Decode(value uint64) (result uint64) {
- i := 1
+func (f Numbers) Decode(value uint64) (result uint64, length byte) {
+ length = 1
// Loop until the lowest two bits are both raised
for (value & 3) != 3 {
// Add the fibonacci number for the current bit if it is raised
if (value & 1) == 1 {
- result += f[i]
+ result += f[length]
// We know that the next bit cannot be raised by Zeckendorf's theorem
value >>= 2
- i += 2
+ length += 2
continue
}
value >>= 1
- i++
+ length++
}
- result += f[i] - 1
+ result += f[length] - 1
return
}
+
+func Writer(target io.Writer) io.Writer {
+ var enc encoder
+ enc.Numbers = New(16)
+ enc.target = target
+ enc.buffer = enc.backing[:0:len(enc.backing)]
+ return &enc
+}
+
+type encoder struct {
+ Numbers
+ target io.Writer
+ backing [3]byte // TODO - verify that this can be reduced to 2 bytes
+ buffer []byte
+ remaining byte
+ length byte
+}
+
+func (e *encoder) Write(input []byte) (int, error) {
+ var (
+ total int
+ err error
+ )
+
+ // Flush on a nil slice
+ if input == nil {
+ e.backing[0] = byte(e.remaining)
+ _, err = e.target.Write(e.buffer[:1])
+ return 0, err
+ }
+
+ for _, currentByte := range input {
+ // Get the fibonacci code and bit length for the current byte
+ enc, len := e.Code(uint64(currentByte))
+
+ // Add current bits to higher positions
+ e.remaining |= byte(enc << e.length)
+
+ // maximum length of added bits to e.remaining
+ added := 8 - e.length
+
+ // Shift the the encoded value and account for its length
+ enc >>= added
+ e.length += len
+ len -= added
+
+ // Not enough bits to write
+ if e.length < 8 {
+ continue
+ }
+
+ // Clearing e.length is not necessary as it will be overwritten later
+
+ // Stage the complete byte for writing
+ e.buffer = append(e.buffer, byte(e.remaining))
+
+ // Stage every full byte from the encoded value for writing
+ for enc > 128 {
+ e.buffer = append(e.buffer, byte(enc))
+ enc >>= 8
+ len -= 8
+ }
+
+ // Store the remaining bits
+ e.remaining, e.length = byte(enc), len
+
+ // Write the staged bytes
+ _, err = e.target.Write(e.buffer)
+
+ // Abort write on error
+ if err != nil {
+ break
+ }
+
+ // Account for the just-written byte
+ total++
+
+ // Clear the buffer
+ e.buffer = e.buffer[:0]
+ }
+ return total, err
+}
+
+// func Reader(source io.Reader) io.Reader {
+// var dec decoder
+// dec.Numbers = New(16)
+// dec.source = source
+// return &dec
+// }
+
+// type decoder struct {
+// Numbers
+// source io.Reader
+// buffer uint64
+// at byte
+// }
+
+// func (d *decoder) Read(output []byte) (int, error) {
+// return 0, nil
+// }
Index: src/0dev.org/encoding/fibonacci/fib_test.go
==================================================================
--- src/0dev.org/encoding/fibonacci/fib_test.go
+++ src/0dev.org/encoding/fibonacci/fib_test.go
@@ -1,8 +1,11 @@
package fibonacci
import (
+ "bytes"
+ "fmt"
+ "io"
"testing"
)
func TestNumbers(t *testing.T) {
n := New(32)
@@ -18,13 +21,79 @@
}
func TestCoding(t *testing.T) {
n := New(32)
- for i := uint64(0); i < 1024; i++ {
- enc := n.Code(i)
- dec := n.Decode(enc)
+ for i := uint64(0); i < 4096; i++ {
+ enc, _ := n.Code(i)
+ //fmt.Printf("%d - %b, %d\n", i, enc, len)
+ dec, _ := n.Decode(enc)
if i != dec {
t.Errorf("Unexpected value for %d - enc is %b, dec is %d\n", i, enc, dec)
}
}
}
+
+func TestWriter0(t *testing.T) {
+ var buf bytes.Buffer
+ var w io.Writer = Writer(&buf)
+
+ w.Write([]byte{0})
+ w.Write(nil)
+ for _, v := range buf.Bytes() {
+ fmt.Printf("%s-", b2s(v))
+ }
+ fmt.Println()
+}
+
+func TestWriter1(t *testing.T) {
+ var buf bytes.Buffer
+ var w io.Writer = Writer(&buf)
+
+ w.Write([]byte{0, 1})
+ w.Write(nil)
+ for _, v := range buf.Bytes() {
+ fmt.Printf("%s-", b2s(v))
+ }
+ fmt.Println()
+}
+
+func TestWriter2(t *testing.T) {
+ var buf bytes.Buffer
+ var w io.Writer = Writer(&buf)
+
+ w.Write([]byte{0, 1, 2})
+ w.Write(nil)
+ for _, v := range buf.Bytes() {
+ fmt.Printf("%s-", b2s(v))
+ }
+ fmt.Println()
+}
+
+func TestWriter3(t *testing.T) {
+ var buf bytes.Buffer
+ var w io.Writer = Writer(&buf)
+
+ var input []byte = make([]byte, 256)
+ for i := 0; i < 256; i++ {
+ input[i] = byte(i)
+ }
+
+ w.Write(input)
+ w.Write(nil)
+ for _, v := range buf.Bytes() {
+ fmt.Printf("%s-", b2s(v))
+ }
+ fmt.Println()
+}
+
+func b2s(b byte) (result string) {
+ for i := 0; i < 8; i++ {
+ if b&1 > 0 {
+ result += "1"
+ } else {
+ result += "0"
+ }
+ b >>= 1
+ }
+ return
+}