Check-in [f1a8d5baa9]
Overview
Comment:Use a common fibonacci number source for each encoder and decoder. Dropped the two-bytes buffer from the encoder struct.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: f1a8d5baa914eb4073c9ff4da03ea5e893854cde
User & Date: spaskalev on 2015-01-01 15:12:44
Other Links: manifest | tags
Context
2015-01-01
15:19
[fibonacci] renamed Writer->Encoder, Reader->Decoder. [mtf] moved package mtf to encoding\mtf check-in: cb736e7ad3 user: spaskalev tags: trunk
15:12
Use a common fibonacci number source for each encoder and decoder. Dropped the two-bytes buffer from the encoder struct. check-in: f1a8d5baa9 user: spaskalev tags: trunk
14:11
Initial implementation and test of fibonacci.Reader(io.Reader) io.Reader that decodes bytes encoded from fibonacci.Writer(..). CC at 97.5% check-in: 4b9f9bff39 user: spaskalev tags: trunk
Changes

Modified src/0dev.org/encoding/fibonacci/fib.go from [665b1e0b43] to [5685c81b13].

12
13
14
15
16
17
18





19
20
21
22
23
24
25
package fibonacci

import (
	"io"
)

type Numbers []uint64






// 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]







>
>
>
>
>







12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package fibonacci

import (
	"io"
)

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]
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
		length++
	}
	return result + f[length] - 1, length + 1
}

func Writer(target io.Writer) io.Writer {
	var enc encoder
	enc.Numbers = New(14)
	enc.target = target
	enc.buffer = enc.backing[:0:len(enc.backing)]
	return &enc
}

type encoder struct {
	Numbers
	target    io.Writer
	backing   [2]byte
	buffer    []byte
	remaining byte
	length    byte
}

func (e *encoder) Write(input []byte) (int, error) {
	var (
		total int
		err   error
	)

	// Flush on a nil slice
	if input == nil {
		e.backing[0] = byte(e.remaining)
		_, err = e.target.Write(e.buffer[:1])
		return 0, err
	}

	for _, currentByte := range input {
		// Get the fibonacci code and bit length for the current byte
		enc, len := e.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








<

<




<

<
<












<
|





|







77
78
79
80
81
82
83

84

85
86
87
88

89


90
91
92
93
94
95
96
97
98
99
100
101

102
103
104
105
106
107
108
109
110
111
112
113
114
115
		length++
	}
	return result + f[length] - 1, length + 1
}

func Writer(target io.Writer) io.Writer {
	var enc encoder

	enc.target = target

	return &enc
}

type encoder struct {

	target    io.Writer


	remaining byte
	length    byte
}

func (e *encoder) Write(input []byte) (int, error) {
	var (
		total int
		err   error
	)

	// Flush on a nil slice
	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

126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192

			continue
		}

		// Clearing e.length is not necessary as it will be overwritten later

		// Stage the complete byte for writing
		e.buffer = append(e.buffer, byte(e.remaining))

		// Stage every full byte from the encoded value for writing
		for enc > 128 {
			e.buffer = append(e.buffer, byte(enc))
			enc >>= 8
			len -= 8
		}

		// Store the remaining bits
		e.remaining, e.length = byte(enc), len

		// Write the staged bytes
		_, err = e.target.Write(e.buffer)

		// Abort write on error
		if err != nil {
			break
		}

		// Account for the processed input byte
		total++

		// Clear the buffer
		e.buffer = e.buffer[:0]
	}
	return total, err
}

func Reader(source io.Reader) io.Reader {
	var dec decoder
	dec.Numbers = New(16)
	dec.source = source
	return &dec
}

type decoder struct {
	Numbers
	source io.Reader
	buffer uint64
	at     byte
}

func (d *decoder) Read(output []byte) (int, error) {
	var (
		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 := d.Decode(d.buffer)

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

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







|



|








|








<
<
<






<





<














|







125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153



154
155
156
157
158
159

160
161
162
163
164

165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

			continue
		}

		// Clearing e.length is not necessary as it will be overwritten later

		// Stage the complete byte for writing
		buffer := []byte{byte(e.remaining)}

		// Stage every full byte from the encoded value for writing
		for enc > 128 {
			buffer = append(buffer, byte(enc))
			enc >>= 8
			len -= 8
		}

		// Store the remaining bits
		e.remaining, e.length = byte(enc), len

		// Write the staged bytes
		_, err = e.target.Write(buffer)

		// Abort write on error
		if err != nil {
			break
		}

		// Account for the processed input byte
		total++



	}
	return total, err
}

func Reader(source io.Reader) io.Reader {
	var dec decoder

	dec.source = source
	return &dec
}

type decoder struct {

	source io.Reader
	buffer uint64
	at     byte
}

func (d *decoder) Read(output []byte) (int, error) {
	var (
		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
210
211
212
213
214
215
216

217
218
	// Read data and transfer to the internal buffer
	count, err := d.source.Read(output[:free])
	for _, v := range output[:count] {
		d.buffer |= uint64(v) << d.at
		d.at += 8
	}


	goto start
}







>


204
205
206
207
208
209
210
211
212
213
	// Read data and transfer to the internal buffer
	count, err := d.source.Read(output[:free])
	for _, v := range output[:count] {
		d.buffer |= uint64(v) << d.at
		d.at += 8
	}

	// To ensure a tail call :)
	goto start
}