fib.go at [ffb139e305]

File src/0dev.org/encoding/fibonacci/fib.go artifact 5db8094e9b part of check-in ffb139e305


// 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 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 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 fibs
}

// 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[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[i] <= value {
			result |= 1
			value -= f[i]
		}
	}
	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
	// 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]

			// We know that the next bit cannot be raised by Zeckendorf's theorem
			value >>= 2
			i += 2
			continue
		}

		value >>= 1
		i++
	}
	result += f[i] - 1
	return
}