Check-in [4b9f9bff39]
Overview
SHA1: 4b9f9bff3989c6d96534cb07ab4c8d42feec7bca 2015-01-01 14:11:05 spaskalev Initial implementation and test of fibonacci.Reader(io.Reader) io.Reader that decodes bytes encoded from fibonacci.Writer(..). CC at 97.5% family | ancestors | descendants | both | trunk Tarball | ZIP archive files | file ages | folders | manifest
Tags And Properties
Context
 2015-01-01 15:12 [f1a8d5baa9] Use a common fibonacci number source for each encoder and decoder. Dropped the two-bytes buffer from the encoder struct. (user: spaskalev, tags: trunk) 14:11 [4b9f9bff39] Initial implementation and test of fibonacci.Reader(io.Reader) io.Reader that decodes bytes encoded from fibonacci.Writer(..). CC at 97.5% (user: spaskalev, tags: trunk) 06:34 [ea97951fcd] Fixed Decode's length return and added a test for it. Reduce encoder's buffer to 2 bytes. CC at 98.3% (user: spaskalev, tags: trunk)
Changes
```     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   	}
162    160   }
163    161
165         -// 	var dec decoder
166         -// 	dec.Numbers = New(16)
167         -// 	dec.source = source
168         -// 	return &dec
169         -// }
163  +	var dec decoder
164  +	dec.Numbers = New(16)
165  +	dec.source = source
166  +	return &dec
167  +}
168  +
169  +type decoder struct {
170  +	Numbers
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 {
201  +	}
170    202
171         -// type decoder struct {
172         -// 	Numbers
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 {
203         -// 	}
204         -
205         -// 	// count, err := d.source.Read(output)
206         -
208         -// }
217  +	goto start
218  +}

```

```     1      1   package fibonacci
2      2
3      3   import (
4  +	diff "0dev.org/diff"
4      5   	"bytes"
5      6   	"io"
6      7   	"strings"
7      8   	"testing"
8      9   )
9     10
10     11   func TestNumbers(t *testing.T) {
................................................................................
32     33   		}
33     34   		if encLen != decLen {
34     35   			t.Errorf("Unexpected difference between encoded and decoded lengths.", encLen, decLen)
35     36   		}
36     37   	}
37     38   }
38     39
39         -func TestWriter(t *testing.T) {
40         -	var buf bytes.Buffer
41         -	var w io.Writer = Writer(&buf)
42         -	var input []byte = make([]byte, 256)
43         -	var fib Numbers = New(16)
41  +	var (
42  +		buf   bytes.Buffer
43  +		w     io.Writer = Writer(&buf)
44  +		input []byte    = make([]byte, 256)
45  +		fib   Numbers   = New(16)
46  +	)
44     47
45     48   	for i := uint64(0); i < 256; i++ {
46     49   		input[i] = byte(i)
47     50   	}
48     51
49     52   	// Write the input
50     53   	count, err := w.Write(input)
................................................................................
73     76   		c, l := fib.Code(uint64(v))
74     77   		vs := u2s(c, l)
75     78   		if loc := strings.Index(output, vs); loc != 0 {
76     79   			t.Fatal("Unexpected location for", i, "value", vs)
77     80   		}
78     81   		output = output[len(vs):]
79     82   	}
83  +
84  +	var (
87  +		out bytes.Buffer
88  +	)
89  +	io.Copy(&out, r)
90  +	decoded := out.Bytes()
91  +
92  +	delta := diff.Diff(diff.D{Len1: len(decoded), Len2: len(input), EqualFunc: func(i, j int) bool {
93  +		return decoded[i] == input[j]
94  +	}})
95  +
96  +	if len(delta.Added) > 0 || len(delta.Removed) > 0 {
97  +		t.Error("Differences detected ", delta)
98  +	}
80     99   }
81    100
82    101   func u2s(b uint64, l byte) (result string) {
83    102   	for i := byte(0); i < l; i++ {
84    103   		if (b & 1) > 0 {
85    104   			result += "1"
86    105   		} else {
87    106   			result += "0"
88    107   		}
89    108   		b >>= 1
90    109   	}
91    110   	return
92    111   }

```