The Shed
Check-in [f06f8cd058]
Login
HomeTimelineFilesBranchesTagsTicketsWiki
Overview
Comment:Allocate the predictor's decompression buffer per Read call.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: f06f8cd058563e2a8fd404c3d1578857f83a14df
User & Date: spaskalev on 2014-12-25 08:48:58
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
Hide Diffs Side-by-Side Diffs Ignore Whitespace 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

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,
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) 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

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)
		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

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
	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
		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(ctx.input[:1])
	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 = ctx.input[0]
	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(ctx.input[predicted:])
	rc, err = ctx.source.Read(buffer[predicted:])
retryData:
	if rc < int(8-predicted) && err == nil {
	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(ctx.input[int(predicted)+rc:])
		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 += int(predicted)
	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
			ctx.input[i] = ctx.table[ctx.hash]
			buffer[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
			buffer[i], a = buffer[a], a+1
			// Guess failed, update the table
			ctx.table[ctx.hash] = ctx.input[i]
			ctx.table[ctx.hash] = buffer[i]
		}
		// Update the hash
		ctx.update(ctx.input[i])
		ctx.update(buffer[i])
	}

	// Copy the decompressed data to the output and accumulate the count
	copied = copy(output, ctx.input[:rc])
	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