1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
// 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)
_ "fmt"
|
|
>
<
<
<
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
// 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 reversed so that they are easily stored in uints,
// effectively avoiding the need to store the number of leading zeroes
// 0 - 11, 1 - 110, 2 - 1100, 3 - 1101, 4 - 11000
package fibonacci
import (
"io"
)
type Numbers []uint64
// Returns a slice with fibonacci numbers up to the given length
func New(size int) Numbers {
|
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
|
// 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) {
// var (
// total int
// err error
// )
// // While we have suitable buffered data and enough output space
// for (len(output) > 0) && ((d.buffer & (d.buffer >> 1)) > 0) {
// val, len := d.Decode(d.buffer)
// // Store the decoded byte
// output[0] = byte(val)
// // Advance the internal and output buffers
// output = output[1:]
// d.buffer >>= len
// // TODO - decrease d.at as well ?
// total++
// }
// // Termination condition
// if len(output) == 0 {
// return total, nil
// }
// // count, err := d.source.Read(output)
// return total, err
// }
|
|
|
|
|
|
<
|
>
|
|
|
|
|
<
|
>
|
|
|
|
<
|
>
>
|
|
|
|
|
|
|
|
|
<
|
<
|
>
|
|
|
>
|
>
>
>
>
>
|
>
>
|
>
>
>
|
|
|
>
|
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
|
// 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) {
var (
total int
err error
)
start:
// While we have suitable buffered data and enough output space
for (len(output) > 0) && ((d.buffer & (d.buffer >> 1)) > 0) {
val, len := d.Decode(d.buffer)
// Store the decoded byte
output[0] = byte(val)
// Advance the internal and output buffers
output = output[1:]
d.buffer >>= len
d.at -= len
total++
}
// Termination condition
if len(output) == 0 || err != nil {
return total, err
}
// We need to limit the output's size else we could end up with a lot of small values
// that fit neither in the output slice nor in the internal buffer
free := int((63 ^ d.at) >> 3)
if free > len(output) {
free = len(output)
}
// Read data and transfer to the internal buffer
count, err := d.source.Read(output[:free])
for _, v := range output[:count] {
d.buffer |= uint64(v) << d.at
d.at += 8
}
goto start
}
|