Index: src/0dev.org/encoding/fibonacci/fib.go ================================================================== --- src/0dev.org/encoding/fibonacci/fib.go +++ src/0dev.org/encoding/fibonacci/fib.go @@ -1,41 +1,37 @@ -// Package provides a shifted, reversed fibonacci encoding of bytes +// Package provides a shifted, reversed 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 bytes by one to allow for zero gives +// 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 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) +// Returns a slice with fibonacci numbers up to the given length +func New(size int) Numbers { + var fibs Numbers = make(Numbers, size) + copy(fibs, []uint64{1, 1}) + for i := 2; i < size; i++ { + fibs[i] = fibs[i-1] + fibs[i-2] } - return f[index] + return fibs } -// Returns a fibonacci code for an integer as specified in the package doc. +// Returns a fibonacci code for an integer as specified in the package's 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 { + for f[i+1] <= value { i++ } // Leading bit that signals the start of a fibonacci-encoded integer result |= 1 @@ -43,25 +39,26 @@ // 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 { + if f[i] <= value { result |= 1 - value -= f.Nth(i) + value -= f[i] } } return } -// Returns an integer from a fibonacci code as specified in the package doc. +// Returns an integer from a fibonacci code as specified in the package's doc. func (f Numbers) Decode(value uint64) (result uint64) { i := 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.Nth(i) + result += f[i] // We know that the next bit cannot be raised by Zeckendorf's theorem value >>= 2 i += 2 continue @@ -68,8 +65,8 @@ } value >>= 1 i++ } - result += f.Nth(i) - 1 + result += f[i] - 1 return } 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 @@ -3,28 +3,28 @@ import ( "testing" ) func TestNumbers(t *testing.T) { - n := make(Numbers, 32) + n := New(32) expected := []uint64{1, 1, 2, 3, 5, 8, 13, 21} for i, v := range expected { - if f := n.Nth(i); f != v { + if f := n[i]; f != v { t.Error("Unexpected value for", i, f, "expected", v) } } } func TestCoding(t *testing.T) { - n := make(Numbers, 32) + n := New(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) } } }