Diff

To Artifact [665b1e0b43]:

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

```