Modified src/0dev.org/encoding/fibonacci/fib.go from [36b31aa589] to [5db8094e9b].

     1         -// Package provides a shifted, reversed fibonacci encoding of bytes
            1  +// Package provides a shifted, reversed 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         -// Incrementing input bytes by one to allow for zero gives
            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     11   package fibonacci
    12     12   
    13     13   type Numbers []uint64
    14     14   
    15         -// Returns the n-th fibonacci number
    16         -// The result is stored after calculation
    17         -func (f Numbers) Nth(index int) uint64 {
    18         -	switch {
    19         -	case index <= 1:
    20         -		return 1
    21         -	case f[index] > 0:
    22         -		break
    23         -	default:
    24         -		f[index] = f.Nth(index-1) + f.Nth(index-2)
           15  +// Returns a slice with fibonacci numbers up to the given length
           16  +func New(size int) Numbers {
           17  +	var fibs Numbers = make(Numbers, size)
           18  +	copy(fibs, []uint64{1, 1})
           19  +	for i := 2; i < size; i++ {
           20  +		fibs[i] = fibs[i-1] + fibs[i-2]
    25     21   	}
    26         -	return f[index]
           22  +	return fibs
    27     23   }
    28     24   
    29         -// Returns a fibonacci code for an integer as specified in the package doc.
           25  +// Returns a fibonacci code for an integer as specified in the package's doc.
    30     26   func (f Numbers) Code(value uint64) (result uint64) {
    31     27   	// Increment to encode zero as one
    32     28   	value++
    33     29   
    34     30   	// Find the nearest fibonacci number
    35     31   	i := 0
    36         -	for f.Nth(i+1) <= value {
           32  +	for f[i+1] <= value {
    37     33   		i++
    38     34   	}
    39     35   
    40     36   	// Leading bit that signals the start of a fibonacci-encoded integer
    41     37   	result |= 1
    42     38   
    43     39   	// Find the Zeckendorf's representation by raising a bit for each
    44     40   	// fibonacci number that is less or equal to the difference
    45     41   	// between the value and the previous such number
    46     42   	for ; i >= 1; i-- {
    47     43   		result <<= 1
    48         -		if f.Nth(i) <= value {
           44  +		if f[i] <= value {
    49     45   			result |= 1
    50         -			value -= f.Nth(i)
           46  +			value -= f[i]
    51     47   		}
    52     48   	}
    53     49   	return
    54     50   }
    55     51   
    56         -// Returns an integer from a fibonacci code as specified in the package doc.
           52  +// Returns an integer from a fibonacci code as specified in the package's doc.
    57     53   func (f Numbers) Decode(value uint64) (result uint64) {
    58     54   	i := 1
           55  +	// Loop until the lowest two bits are both raised
    59     56   	for (value & 3) != 3 {
    60     57   		// Add the fibonacci number for the current bit if it is raised
    61     58   		if (value & 1) == 1 {
    62         -			result += f.Nth(i)
           59  +			result += f[i]
    63     60   
    64     61   			// We know that the next bit cannot be raised by Zeckendorf's theorem
    65     62   			value >>= 2
    66     63   			i += 2
    67     64   			continue
    68     65   		}
    69     66   
    70     67   		value >>= 1
    71     68   		i++
    72     69   	}
    73         -	result += f.Nth(i) - 1
           70  +	result += f[i] - 1
    74     71   	return
    75     72   }

Modified src/0dev.org/encoding/fibonacci/fib_test.go from [5949178ed8] to [ecd601a44e].

     1      1   package fibonacci
     2      2   
     3      3   import (
     4      4   	"testing"
     5      5   )
     6      6   
     7      7   func TestNumbers(t *testing.T) {
     8         -	n := make(Numbers, 32)
            8  +	n := New(32)
     9      9   
    10     10   	expected := []uint64{1, 1, 2, 3, 5, 8, 13, 21}
    11     11   
    12     12   	for i, v := range expected {
    13     13   
    14         -		if f := n.Nth(i); f != v {
           14  +		if f := n[i]; f != v {
    15     15   			t.Error("Unexpected value for", i, f, "expected", v)
    16     16   		}
    17     17   	}
    18     18   }
    19     19   
    20     20   func TestCoding(t *testing.T) {
    21         -	n := make(Numbers, 32)
           21  +	n := New(32)
    22     22   
    23     23   	for i := uint64(0); i < 1024; i++ {
    24     24   		enc := n.Code(i)
    25     25   		dec := n.Decode(enc)
    26     26   		if i != dec {
    27     27   			t.Errorf("Unexpected value for %d - enc is %b, dec is %d\n", i, enc, dec)
    28     28   		}
    29     29   	}
    30     30   }