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
16
17
18
19
20
21
22
23




24









25
26
27
28
29
30
31
...
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
...
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
	"io"
)

// Alias type with methods for encoding and decoding integers
type Numbers []uint64

var (
	// Used for encoding and decoding byte values
	bytesCodec = New(14)




)










// Returns a slice with fibonacci numbers up to the given length
func New(size int) Numbers {
	var fibs Numbers = make(Numbers, size)
	copy(fibs, []uint64{1, 1})
	for i := 2; i < size; i++ {
		fibs[i] = fibs[i-1] + fibs[i-2]
................................................................................
	if input == nil {
		_, err = e.target.Write([]byte{byte(e.remaining)})
		return 0, err
	}

	for _, currentByte := range input {
		// Get the fibonacci code and bit length for the current byte
		enc, len := bytesCodec.Code(uint64(currentByte))

		// Add current bits to higher positions
		e.remaining |= byte(enc << e.length)

		// maximum length of added bits to e.remaining
		added := 8 - e.length

................................................................................
		total int
		err   error
	)

start:
	// While we have suitable buffered data and enough output space
	for (len(output) > 0) && ((d.buffer & (d.buffer >> 1)) > 0) {
		val, len := bytesCodec.Decode(d.buffer)

		// Store the decoded byte
		output[0] = byte(val)

		// Advance the internal and output buffers
		output = output[1:]
		d.buffer >>= len







|
|
>
>
>
>

>
>
>
>
>
>
>
>
>







 







|







 







|







15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
...
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
...
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
	"io"
)

// Alias type with methods for encoding and decoding integers
type Numbers []uint64

var (
	// Used for decoding byte values
	codec Numbers
	// Used for encoding byte values
	// The lower 16 bits store the encoded value itself
	// while the remaining upper ones store its length
	lookup [256]uint32
)

func init() {
	codec = New(16)
	for i := uint64(0); i < 256; i++ {
		val, len := codec.Code(i)
		lookup[i] |= uint32(val)
		lookup[i] |= uint32(len) << 16
	}
}

// Returns a slice with fibonacci numbers up to the given length
func New(size int) Numbers {
	var fibs Numbers = make(Numbers, size)
	copy(fibs, []uint64{1, 1})
	for i := 2; i < size; i++ {
		fibs[i] = fibs[i-1] + fibs[i-2]
................................................................................
	if input == nil {
		_, err = e.target.Write([]byte{byte(e.remaining)})
		return 0, err
	}

	for _, currentByte := range input {
		// Get the fibonacci code and bit length for the current byte
		enc, len := uint16(lookup[currentByte]), byte(lookup[currentByte]>>16)

		// Add current bits to higher positions
		e.remaining |= byte(enc << e.length)

		// maximum length of added bits to e.remaining
		added := 8 - e.length

................................................................................
		total int
		err   error
	)

start:
	// While we have suitable buffered data and enough output space
	for (len(output) > 0) && ((d.buffer & (d.buffer >> 1)) > 0) {
		val, len := codec.Decode(d.buffer)

		// Store the decoded byte
		output[0] = byte(val)

		// Advance the internal and output buffers
		output = output[1:]
		d.buffer >>= len