@@ -1,5 +1,5 @@ -// 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 // @@ -7,9 +7,16 @@ // 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 @@ -22,16 +29,15 @@ 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 @@ -38,9 +44,9 @@ // 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] @@ -49,24 +55,124 @@ 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 +// }