Check-in [4b9f9bff39]
Overview
SHA1:4b9f9bff3989c6d96534cb07ab4c8d42feec7bca
Date: 2015-01-01 14:11:05
User: spaskalev
Comment:Initial implementation and test of fibonacci.Reader(io.Reader) io.Reader that decodes bytes encoded from fibonacci.Writer(..). CC at 97.5%
Timelines: family | ancestors | descendants | both | trunk
Downloads: Tarball | ZIP archive
Other Links: 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

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

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

     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)
           40  +func TestWriterReader(t *testing.T) {
           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 (
           85  +		in  *bytes.Reader = bytes.NewReader(buf.Bytes())
           86  +		r   io.Reader     = Reader(in)
           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   }