// 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 {
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, length byte) {
// Increment to encode zero as one
value++
// Find the nearest fibonacci number
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 := length - 1; 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, 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[length]
// We know that the next bit cannot be raised by Zeckendorf's theorem
value >>= 2
length += 2
continue
}
value >>= 1
length++
}
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
// }