Diff

Differences From Artifact [5db8094e9b]:

To Artifact [fe204fcaf6]:


     1         -// Package provides a shifted, reversed fibonacci encoding of unsigned integers.
            1  +// Package provides a shifted fibonacci encoding of unsigned integers.
     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      9   // The codes are then reversed so that they are easily stored in uints
    10     10   // 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)
    11     13   package fibonacci
           14  +
           15  +import (
           16  +	_ "fmt"
           17  +	"io"
           18  +)
    12     19   
    13     20   type Numbers []uint64
    14     21   
    15     22   // Returns a slice with fibonacci numbers up to the given length
    16     23   func New(size int) Numbers {
    17     24   	var fibs Numbers = make(Numbers, size)
    18     25   	copy(fibs, []uint64{1, 1})
................................................................................
    19     26   	for i := 2; i < size; i++ {
    20     27   		fibs[i] = fibs[i-1] + fibs[i-2]
    21     28   	}
    22     29   	return fibs
    23     30   }
    24     31   
    25     32   // Returns a fibonacci code for an integer as specified in the package's doc.
    26         -func (f Numbers) Code(value uint64) (result uint64) {
           33  +func (f Numbers) Code(value uint64) (result uint64, length byte) {
    27     34   	// Increment to encode zero as one
    28     35   	value++
    29     36   
    30     37   	// Find the nearest fibonacci number
    31         -	i := 0
    32         -	for f[i+1] <= value {
    33         -		i++
           38  +	for f[length] <= value {
           39  +		length++
    34     40   	}
    35     41   
    36     42   	// Leading bit that signals the start of a fibonacci-encoded integer
    37     43   	result |= 1
    38     44   
    39     45   	// Find the Zeckendorf's representation by raising a bit for each
    40     46   	// fibonacci number that is less or equal to the difference
    41     47   	// between the value and the previous such number
    42         -	for ; i >= 1; i-- {
           48  +	for i := length - 1; i >= 1; i-- {
    43     49   		result <<= 1
    44     50   		if f[i] <= value {
    45     51   			result |= 1
    46     52   			value -= f[i]
    47     53   		}
    48     54   	}
    49     55   	return
    50     56   }
    51     57   
    52     58   // Returns an integer from a fibonacci code as specified in the package's doc.
    53         -func (f Numbers) Decode(value uint64) (result uint64) {
    54         -	i := 1
           59  +func (f Numbers) Decode(value uint64) (result uint64, length byte) {
           60  +	length = 1
    55     61   	// Loop until the lowest two bits are both raised
    56     62   	for (value & 3) != 3 {
    57     63   		// Add the fibonacci number for the current bit if it is raised
    58     64   		if (value & 1) == 1 {
    59         -			result += f[i]
           65  +			result += f[length]
    60     66   
    61     67   			// We know that the next bit cannot be raised by Zeckendorf's theorem
    62     68   			value >>= 2
    63         -			i += 2
           69  +			length += 2
    64     70   			continue
    65     71   		}
    66     72   
    67     73   		value >>= 1
    68         -		i++
           74  +		length++
    69     75   	}
    70         -	result += f[i] - 1
           76  +	result += f[length] - 1
    71     77   	return
    72     78   }
           79  +
           80  +func Writer(target io.Writer) io.Writer {
           81  +	var enc encoder
           82  +	enc.Numbers = New(16)
           83  +	enc.target = target
           84  +	enc.buffer = enc.backing[:0:len(enc.backing)]
           85  +	return &enc
           86  +}
           87  +
           88  +type encoder struct {
           89  +	Numbers
           90  +	target    io.Writer
           91  +	backing   [3]byte // TODO - verify that this can be reduced to 2 bytes
           92  +	buffer    []byte
           93  +	remaining byte
           94  +	length    byte
           95  +}
           96  +
           97  +func (e *encoder) Write(input []byte) (int, error) {
           98  +	var (
           99  +		total int
          100  +		err   error
          101  +	)
          102  +
          103  +	// Flush on a nil slice
          104  +	if input == nil {
          105  +		e.backing[0] = byte(e.remaining)
          106  +		_, err = e.target.Write(e.buffer[:1])
          107  +		return 0, err
          108  +	}
          109  +
          110  +	for _, currentByte := range input {
          111  +		// Get the fibonacci code and bit length for the current byte
          112  +		enc, len := e.Code(uint64(currentByte))
          113  +
          114  +		// Add current bits to higher positions
          115  +		e.remaining |= byte(enc << e.length)
          116  +
          117  +		// maximum length of added bits to e.remaining
          118  +		added := 8 - e.length
          119  +
          120  +		// Shift the the encoded value and account for its length
          121  +		enc >>= added
          122  +		e.length += len
          123  +		len -= added
          124  +
          125  +		// Not enough bits to write
          126  +		if e.length < 8 {
          127  +			continue
          128  +		}
          129  +
          130  +		// Clearing e.length is not necessary as it will be overwritten later
          131  +
          132  +		// Stage the complete byte for writing
          133  +		e.buffer = append(e.buffer, byte(e.remaining))
          134  +
          135  +		// Stage every full byte from the encoded value for writing
          136  +		for enc > 128 {
          137  +			e.buffer = append(e.buffer, byte(enc))
          138  +			enc >>= 8
          139  +			len -= 8
          140  +		}
          141  +
          142  +		// Store the remaining bits
          143  +		e.remaining, e.length = byte(enc), len
          144  +
          145  +		// Write the staged bytes
          146  +		_, err = e.target.Write(e.buffer)
          147  +
          148  +		// Abort write on error
          149  +		if err != nil {
          150  +			break
          151  +		}
          152  +
          153  +		// Account for the just-written byte
          154  +		total++
          155  +
          156  +		// Clear the buffer
          157  +		e.buffer = e.buffer[:0]
          158  +	}
          159  +	return total, err
          160  +}
          161  +
          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  +// 	return 0, nil
          178  +// }