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 +}