Check-in [4b9f9bff39]
Overview
Comment:Initial implementation and test of fibonacci.Reader(io.Reader) io.Reader that decodes bytes encoded from fibonacci.Writer(..). CC at 97.5%
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 4b9f9bff3989c6d96534cb07ab4c8d42feec7bca
User & Date: spaskalev on 2015-01-01 14:11:05
Other Links: manifest | tags
Context
2015-01-01
15:12
Use a common fibonacci number source for each encoder and decoder. Dropped the two-bytes buffer from the encoder struct. check-in: f1a8d5baa9 user: spaskalev tags: trunk
14:11
Initial implementation and test of fibonacci.Reader(io.Reader) io.Reader that decodes bytes encoded from fibonacci.Writer(..). CC at 97.5% check-in: 4b9f9bff39 user: spaskalev tags: trunk
06:34
Fixed Decode's length return and added a test for it. Reduce encoder's buffer to 2 bytes. CC at 98.3% check-in: ea97951fcd user: spaskalev tags: trunk
Changes

Modified src/0dev.org/encoding/fibonacci/fib.go from [bc261fa076] to [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
}

Modified src/0dev.org/encoding/fibonacci/fib_test.go from [0734e0cdf2] to [33c293fd3b].

1
2
3

4
5
6
7
8
9
10
package fibonacci

import (

	"bytes"
	"io"
	"strings"
	"testing"
)

func TestNumbers(t *testing.T) {



>







1
2
3
4
5
6
7
8
9
10
11
package fibonacci

import (
	diff "0dev.org/diff"
	"bytes"
	"io"
	"strings"
	"testing"
)

func TestNumbers(t *testing.T) {
32
33
34
35
36
37
38
39

40
41
42
43

44
45
46
47
48
49
50
		}
		if encLen != decLen {
			t.Errorf("Unexpected difference between encoded and decoded lengths.", encLen, decLen)
		}
	}
}

func TestWriter(t *testing.T) {

	var buf bytes.Buffer
	var w io.Writer = Writer(&buf)
	var input []byte = make([]byte, 256)
	var fib Numbers = New(16)


	for i := uint64(0); i < 256; i++ {
		input[i] = byte(i)
	}

	// Write the input
	count, err := w.Write(input)







|
>
|
|
|
|
>







33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
		}
		if encLen != decLen {
			t.Errorf("Unexpected difference between encoded and decoded lengths.", encLen, decLen)
		}
	}
}

func TestWriterReader(t *testing.T) {
	var (
		buf   bytes.Buffer
		w     io.Writer = Writer(&buf)
		input []byte    = make([]byte, 256)
		fib   Numbers   = New(16)
	)

	for i := uint64(0); i < 256; i++ {
		input[i] = byte(i)
	}

	// Write the input
	count, err := w.Write(input)
73
74
75
76
77
78
79
















80
81
82
83
84
85
86
87
88
89
90
91
92
		c, l := fib.Code(uint64(v))
		vs := u2s(c, l)
		if loc := strings.Index(output, vs); loc != 0 {
			t.Fatal("Unexpected location for", i, "value", vs)
		}
		output = output[len(vs):]
	}
















}

func u2s(b uint64, l byte) (result string) {
	for i := byte(0); i < l; i++ {
		if (b & 1) > 0 {
			result += "1"
		} else {
			result += "0"
		}
		b >>= 1
	}
	return
}







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>













76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
		c, l := fib.Code(uint64(v))
		vs := u2s(c, l)
		if loc := strings.Index(output, vs); loc != 0 {
			t.Fatal("Unexpected location for", i, "value", vs)
		}
		output = output[len(vs):]
	}

	var (
		in  *bytes.Reader = bytes.NewReader(buf.Bytes())
		r   io.Reader     = Reader(in)
		out bytes.Buffer
	)
	io.Copy(&out, r)
	decoded := out.Bytes()

	delta := diff.Diff(diff.D{Len1: len(decoded), Len2: len(input), EqualFunc: func(i, j int) bool {
		return decoded[i] == input[j]
	}})

	if len(delta.Added) > 0 || len(delta.Removed) > 0 {
		t.Error("Differences detected ", delta)
	}
}

func u2s(b uint64, l byte) (result string) {
	for i := byte(0); i < l; i++ {
		if (b & 1) > 0 {
			result += "1"
		} else {
			result += "0"
		}
		b >>= 1
	}
	return
}