Check-in [9ded78a659]
Overview
SHA1:9ded78a6597b6db8e07d755976eac3768c77c3b6
Date: 2015-01-04 16:45:56
User: spaskalev
Comment:Use a lookup table for fibonacci's encoding of bytes.
Timelines: family | ancestors | descendants | both | trunk
Downloads: Tarball | ZIP archive
Other Links: files | file ages | folders | manifest
Tags And Properties
Context
2015-01-10
21:28
[5c9c0a2164] encoding/mtf optimizations (user: spaskalev, tags: trunk)
2015-01-04
16:45
[9ded78a659] Use a lookup table for fibonacci's encoding of bytes. (user: spaskalev, tags: trunk)
12:52
[6bd6e6d5c7] commands/mtf now uses fibonacci representation when encoding (user: spaskalev, tags: trunk)
Changes

Modified src/0dev.org/encoding/fibonacci/fib.go from [4b4dfe919b] to [32c0b16287].

    15     15   	"io"
    16     16   )
    17     17   
    18     18   // Alias type with methods for encoding and decoding integers
    19     19   type Numbers []uint64
    20     20   
    21     21   var (
    22         -	// Used for encoding and decoding byte values
    23         -	bytesCodec = New(14)
           22  +	// Used for decoding byte values
           23  +	codec Numbers
           24  +	// Used for encoding byte values
           25  +	// The lower 16 bits store the encoded value itself
           26  +	// while the remaining upper ones store its length
           27  +	lookup [256]uint32
    24     28   )
           29  +
           30  +func init() {
           31  +	codec = New(16)
           32  +	for i := uint64(0); i < 256; i++ {
           33  +		val, len := codec.Code(i)
           34  +		lookup[i] |= uint32(val)
           35  +		lookup[i] |= uint32(len) << 16
           36  +	}
           37  +}
    25     38   
    26     39   // Returns a slice with fibonacci numbers up to the given length
    27     40   func New(size int) Numbers {
    28     41   	var fibs Numbers = make(Numbers, size)
    29     42   	copy(fibs, []uint64{1, 1})
    30     43   	for i := 2; i < size; i++ {
    31     44   		fibs[i] = fibs[i-1] + fibs[i-2]
................................................................................
   104    117   	if input == nil {
   105    118   		_, err = e.target.Write([]byte{byte(e.remaining)})
   106    119   		return 0, err
   107    120   	}
   108    121   
   109    122   	for _, currentByte := range input {
   110    123   		// Get the fibonacci code and bit length for the current byte
   111         -		enc, len := bytesCodec.Code(uint64(currentByte))
          124  +		enc, len := uint16(lookup[currentByte]), byte(lookup[currentByte]>>16)
   112    125   
   113    126   		// Add current bits to higher positions
   114    127   		e.remaining |= byte(enc << e.length)
   115    128   
   116    129   		// maximum length of added bits to e.remaining
   117    130   		added := 8 - e.length
   118    131   
................................................................................
   185    198   		total int
   186    199   		err   error
   187    200   	)
   188    201   
   189    202   start:
   190    203   	// While we have suitable buffered data and enough output space
   191    204   	for (len(output) > 0) && ((d.buffer & (d.buffer >> 1)) > 0) {
   192         -		val, len := bytesCodec.Decode(d.buffer)
          205  +		val, len := codec.Decode(d.buffer)
   193    206   
   194    207   		// Store the decoded byte
   195    208   		output[0] = byte(val)
   196    209   
   197    210   		// Advance the internal and output buffers
   198    211   		output = output[1:]
   199    212   		d.buffer >>= len