Check-in [9ded78a659]
Overview
Comment:Use a lookup table for fibonacci's encoding of bytes.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 9ded78a6597b6db8e07d755976eac3768c77c3b6
User & Date: spaskalev on 2015-01-04 16:45:56
Other Links: manifest | tags
Context
2015-01-10
21:28
encoding/mtf optimizations check-in: 5c9c0a2164 user: spaskalev tags: trunk
2015-01-04
16:45
Use a lookup table for fibonacci's encoding of bytes. check-in: 9ded78a659 user: spaskalev tags: trunk
12:52
commands/mtf now uses fibonacci representation when encoding check-in: 6bd6e6d5c7 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
	"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]







>
>
|
<
>
>
>

>
>
>
>
>
>
>
>
>







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
	"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]
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
	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








|







117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
	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

185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
		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







|







198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
		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