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% Tarball | ZIP archive | SQL archive family | ancestors | descendants | both | files | file ages | folders 4b9f9bff3989c6d96534cb07ab4c8d42feec7bca spaskalev on 2015-01-01 14:11:05 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
 ```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 } ```

 ```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 } ```