Diff

Differences From Artifact [bc261fa076]:

To Artifact [665b1e0b43]:


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)
package fibonacci

import (
	_ "fmt"
	"io"
)

type Numbers []uint64

// Returns a slice with fibonacci numbers up to the given length
func New(size int) Numbers {








|
>

<
<



<







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
}