The Shed
Check-in [f06f8cd058]
Login
HomeTimelineFilesBranchesTagsTicketsWiki
Overview
Comment:Allocate the predictor's decompression buffer per Read call.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: f06f8cd058563e2a8fd404c3d1578857f83a14df
User & Date: spaskalev on 2014-12-25 08:48:58.742
Other Links: manifest | tags
Context
2014-12-26
15:50
Initial implementation of package mtf - a move-to-front transform. check-in: ad5c25d9ab user: spaskalev tags: trunk
2014-12-25
08:48
Allocate the predictor's decompression buffer per Read call. check-in: f06f8cd058 user: spaskalev tags: trunk
01:25
Removed pdc's output buffer when decompressing as io.Copy uses a sufficiently-large buffer internally. check-in: 2b1ed8e45e user: spaskalev tags: trunk
Changes
Unified Diff Show Whitespace Changes Patch
Modified src/0dev.org/bits/bits.go from [7a154cae58] to [16bc764710]. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

// Package bits provides various constructs that work with bits
package bits

import (
	"strconv"
)

var hamming = [256]byte{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
}

// Returns the number of raised bits in the given byte
func Hamming(b byte) byte {
	return hamming[b]
}

var reversed = [256]byte{
	0, 128, 64, 192, 32, 160, 96, 224, 16, 144, 80, 208, 48, 176, 112, 240,
	8, 136, 72, 200, 40, 168, 104, 232, 24, 152, 88, 216, 56, 184, 120, 248,
	4, 132, 68, 196, 36, 164, 100, 228, 20, 148, 84, 212, 52, 180, 116, 244,








|


















|








1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

// Package bits provides various constructs that work with bits
package bits

import (
	"strconv"
)

var hamming = [256]int{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
}

// Returns the number of raised bits in the given byte
func Hamming(b byte) int {
	return hamming[b]
}

var reversed = [256]byte{
	0, 128, 64, 192, 32, 160, 96, 224, 16, 144, 80, 208, 48, 176, 112, 240,
	8, 136, 72, 200, 40, 168, 104, 232, 24, 152, 88, 216, 56, 184, 120, 248,
	4, 132, 68, 196, 36, 164, 100, 228, 20, 148, 84, 212, 52, 180, 116, 244,
︙︙
Modified src/0dev.org/bits/bits_test.go from [255f42be62] to [ed7ac493ff]. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

package bits

import (
	"strconv"
	"testing"
)

func TestHamming(t *testing.T) {
	for i := 0; i < 256; i++ {
		b, result := i, byte(0)
		for b > 0 {
			if (b & 1) > 0 {
				result++
			}
			b = b >> 1
		}
		if result != Hamming(byte(i)) {










|








1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

package bits

import (
	"strconv"
	"testing"
)

func TestHamming(t *testing.T) {
	for i := 0; i < 256; i++ {
		b, result := i, 0
		for b > 0 {
			if (b & 1) > 0 {
				result++
			}
			b = b >> 1
		}
		if result != Hamming(byte(i)) {
︙︙
Modified src/0dev.org/predictor/predictor.go from [3161320c11] to [4f6ff0f55a].
︙︙
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
117
118
119
120
121
122
123
124
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

}

// Returns an io.Reader implementation that wraps the provided io.Reader
// and decompresses data according to the predictor algorithm
func Decompressor(reader io.Reader) io.Reader {
	var dcmp decompressor
	dcmp.source = reader
	dcmp.input = make([]byte, 8)
	return iou.SizedReader(&dcmp, 8)
}

type decompressor struct {
	context
	source io.Reader
	input  []byte
}

// Note: this method does not implement the full io.Reader's Read() semantics
func (ctx *decompressor) Read(output []byte) (int, error) {
	var (
		err               error

		flags, predicted  byte
		rc, total, copied int
	)

	// Read the next prediction header
readHeader:
	rc, err = ctx.source.Read(ctx.input[:1])
	// Fail on error unless it is EOF
	if err != nil && err != io.EOF {
		return total, err
	} else if rc == 0 {
		return total, err
	}

	// Copy the prediction header and calculate the number of subsequent bytes to read
	flags = ctx.input[0]
	predicted = bits.Hamming(flags)

	// Read the non-predicted bytes and place them in the end of the buffer
	rc, err = ctx.source.Read(ctx.input[predicted:])
retryData:
	if rc < int(8-predicted) && err == nil {
		// Retry the read if we have fewer bytes than what the prediction header indicates
		var r int
		r, err = ctx.source.Read(ctx.input[int(predicted)+rc:])
		rc += r
		goto retryData
	} // Continue on any error, try to decompress and return it along the result

	// rc now contains the amount of actual bytes in this cycle (usually 8)
	rc += int(predicted)

	// Walk the buffer, filling in the predicted blanks,
	// relocating read bytes and and updating the guess table
	for i, a := 0, predicted; i < rc; i++ {
		if (flags & (1 << uint(i))) > 0 {
			// Guess succeeded, fill in from the table
			ctx.input[i] = ctx.table[ctx.hash]
		} else {
			// Relocate a read byte and advance the read byte index
			ctx.input[i], a = ctx.input[a], a+1
			// Guess failed, update the table
			ctx.table[ctx.hash] = ctx.input[i]
		}
		// Update the hash
		ctx.update(ctx.input[i])
	}

	// Copy the decompressed data to the output and accumulate the count
	copied = copy(output, ctx.input[:rc])
	total += copied

	// Loop for another pass if there is available space in the output
	output = output[copied:]
	if len(output) > 0 && err == nil {
		goto readHeader
	}








<






<






>
|
|




|








|



|

|


|





|






|


|

|


|



|








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
117
118
119
120
121
122
123
124
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

}

// Returns an io.Reader implementation that wraps the provided io.Reader
// and decompresses data according to the predictor algorithm
func Decompressor(reader io.Reader) io.Reader {
	var dcmp decompressor
	dcmp.source = reader

	return iou.SizedReader(&dcmp, 8)
}

type decompressor struct {
	context
	source io.Reader

}

// Note: this method does not implement the full io.Reader's Read() semantics
func (ctx *decompressor) Read(output []byte) (int, error) {
	var (
		err               error
		buffer                       []byte = make([]byte, 8)
		flags                        byte
		predicted, rc, total, copied int
	)

	// Read the next prediction header
readHeader:
	rc, err = ctx.source.Read(buffer[:1])
	// Fail on error unless it is EOF
	if err != nil && err != io.EOF {
		return total, err
	} else if rc == 0 {
		return total, err
	}

	// Copy the prediction header and calculate the number of subsequent bytes to read
	flags = buffer[0]
	predicted = bits.Hamming(flags)

	// Read the non-predicted bytes and place them in the end of the buffer
	rc, err = ctx.source.Read(buffer[predicted:])
retryData:
	if (rc < (8 - predicted)) && err == nil {
		// Retry the read if we have fewer bytes than what the prediction header indicates
		var r int
		r, err = ctx.source.Read(buffer[predicted+rc:])
		rc += r
		goto retryData
	} // Continue on any error, try to decompress and return it along the result

	// rc now contains the amount of actual bytes in this cycle (usually 8)
	rc += predicted

	// Walk the buffer, filling in the predicted blanks,
	// relocating read bytes and and updating the guess table
	for i, a := 0, predicted; i < rc; i++ {
		if (flags & (1 << uint(i))) > 0 {
			// Guess succeeded, fill in from the table
			buffer[i] = ctx.table[ctx.hash]
		} else {
			// Relocate a read byte and advance the read byte index
			buffer[i], a = buffer[a], a+1
			// Guess failed, update the table
			ctx.table[ctx.hash] = buffer[i]
		}
		// Update the hash
		ctx.update(buffer[i])
	}

	// Copy the decompressed data to the output and accumulate the count
	copied = copy(output, buffer[:rc])
	total += copied

	// Loop for another pass if there is available space in the output
	output = output[copied:]
	if len(output) > 0 && err == nil {
		goto readHeader
	}
︙︙
Powered by Fossil · RSS