ADDED src/0dev.org/encoding/fibonacci/fib.go Index: src/0dev.org/encoding/fibonacci/fib.go ================================================================== --- /dev/null +++ src/0dev.org/encoding/fibonacci/fib.go @@ -0,0 +1,68 @@ +// Package provides a shifted, reversed fibonacci encoding of bytes +// +// http://en.wikipedia.org/wiki/Fibonacci_coding maps positive integers as +// 1 - 11, 2 - 011, 3 - 0011, 4 - 1011, 5 - 00011 +// +// Incrementing input bytes 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 +package fibonacci + +type Numbers []uint64 + +// Returns the n-th fibonacci number +// The result is stored after calculation +func (f Numbers) Nth(index int) uint64 { + switch { + case index <= 1: + return 1 + case f[index] > 0: + break + default: + f[index] = f.Nth(index-1) + f.Nth(index-2) + } + return f[index] +} + +// Returns a fibonacci code for an integer as specified in the package doc. +func (f Numbers) Code(value uint64) (result uint64) { + // Increment to encode zero as one + value++ + + // Find the nearest fibonacci number + i := 0 + for f.Nth(i+1) <= value { + i++ + } + + // 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-- { + result <<= 1 + if f.Nth(i) <= value { + result |= 1 + value -= f.Nth(i) + } + } + return +} + +// Returns an integer from a fibonacci code as specified in the package doc. +func (f Numbers) Decode(value uint64) (result uint64) { + i := 1 + for (value & 3) != 3 { + if (value & 1) == 1 { + result += f.Nth(i) + } + value >>= 1 + i++ + } + result += f.Nth(i) - 1 + return +} ADDED src/0dev.org/encoding/fibonacci/fib_test.go Index: src/0dev.org/encoding/fibonacci/fib_test.go ================================================================== --- /dev/null +++ src/0dev.org/encoding/fibonacci/fib_test.go @@ -0,0 +1,30 @@ +package fibonacci + +import ( + "testing" +) + +func TestNumbers(t *testing.T) { + n := make(Numbers, 32) + + expected := []uint64{1, 1, 2, 3, 5, 8, 13, 21} + + for i, v := range expected { + + if f := n.Nth(i); f != v { + t.Error("Unexpected value for", i, f, "expected", v) + } + } +} + +func TestCoding(t *testing.T) { + n := make(Numbers, 32) + + for i := uint64(0); i < 1024; i++ { + enc := n.Code(i) + dec := n.Decode(enc) + if i != dec { + t.Errorf("Unexpected value for %d - enc is %b, dec is %d\n", i, enc, dec) + } + } +}