Diff

Differences From Artifact [bc261fa076]:

To Artifact [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  +}