Check-in [93fcb281a1]
Overview
SHA1:93fcb281a19a20c41ebdc26a5db6942198ac1ceb
Date: 2015-01-01 04:58:51
User: spaskalev
Comment:Added fibonacci.Writer(io.Writer) io.Writer that encodes bytes.
Timelines: family | ancestors | descendants | both | trunk
Downloads: Tarball | ZIP archive
Other Links: files | file ages | folders | manifest
Tags And Properties
Context
2015-01-01
05:30
[c7c8d6445f] Added a proper test for fibonacci.Writer that writes 0-255, converts the resulting bits to a string and compares against the result of Numbers.Code for each value. (user: spaskalev, tags: trunk)
04:58
[93fcb281a1] Added fibonacci.Writer(io.Writer) io.Writer that encodes bytes. (user: spaskalev, tags: trunk)
2014-12-30
22:59
[ffb139e305] Dropped the Nth method and return a populated slice by fibonacci.New(size). Changed all access to direct indexing. CC at 100% (user: spaskalev, tags: trunk)
Changes

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

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

     1      1   package fibonacci
     2      2   
     3      3   import (
            4  +	"bytes"
            5  +	"fmt"
            6  +	"io"
     4      7   	"testing"
     5      8   )
     6      9   
     7     10   func TestNumbers(t *testing.T) {
     8     11   	n := New(32)
     9     12   
    10     13   	expected := []uint64{1, 1, 2, 3, 5, 8, 13, 21}
................................................................................
    16     19   		}
    17     20   	}
    18     21   }
    19     22   
    20     23   func TestCoding(t *testing.T) {
    21     24   	n := New(32)
    22     25   
    23         -	for i := uint64(0); i < 1024; i++ {
    24         -		enc := n.Code(i)
    25         -		dec := n.Decode(enc)
           26  +	for i := uint64(0); i < 4096; i++ {
           27  +		enc, _ := n.Code(i)
           28  +		//fmt.Printf("%d - %b, %d\n", i, enc, len)
           29  +		dec, _ := n.Decode(enc)
    26     30   		if i != dec {
    27     31   			t.Errorf("Unexpected value for %d - enc is %b, dec is %d\n", i, enc, dec)
    28     32   		}
    29     33   	}
    30     34   }
           35  +
           36  +func TestWriter0(t *testing.T) {
           37  +	var buf bytes.Buffer
           38  +	var w io.Writer = Writer(&buf)
           39  +
           40  +	w.Write([]byte{0})
           41  +	w.Write(nil)
           42  +	for _, v := range buf.Bytes() {
           43  +		fmt.Printf("%s-", b2s(v))
           44  +	}
           45  +	fmt.Println()
           46  +}
           47  +
           48  +func TestWriter1(t *testing.T) {
           49  +	var buf bytes.Buffer
           50  +	var w io.Writer = Writer(&buf)
           51  +
           52  +	w.Write([]byte{0, 1})
           53  +	w.Write(nil)
           54  +	for _, v := range buf.Bytes() {
           55  +		fmt.Printf("%s-", b2s(v))
           56  +	}
           57  +	fmt.Println()
           58  +}
           59  +
           60  +func TestWriter2(t *testing.T) {
           61  +	var buf bytes.Buffer
           62  +	var w io.Writer = Writer(&buf)
           63  +
           64  +	w.Write([]byte{0, 1, 2})
           65  +	w.Write(nil)
           66  +	for _, v := range buf.Bytes() {
           67  +		fmt.Printf("%s-", b2s(v))
           68  +	}
           69  +	fmt.Println()
           70  +}
           71  +
           72  +func TestWriter3(t *testing.T) {
           73  +	var buf bytes.Buffer
           74  +	var w io.Writer = Writer(&buf)
           75  +
           76  +	var input []byte = make([]byte, 256)
           77  +	for i := 0; i < 256; i++ {
           78  +		input[i] = byte(i)
           79  +	}
           80  +
           81  +	w.Write(input)
           82  +	w.Write(nil)
           83  +	for _, v := range buf.Bytes() {
           84  +		fmt.Printf("%s-", b2s(v))
           85  +	}
           86  +	fmt.Println()
           87  +}
           88  +
           89  +func b2s(b byte) (result string) {
           90  +	for i := 0; i < 8; i++ {
           91  +		if b&1 > 0 {
           92  +			result += "1"
           93  +		} else {
           94  +			result += "0"
           95  +		}
           96  +		b >>= 1
           97  +	}
           98  +	return
           99  +}