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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
// Copyright 2015, Joe Tsai. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE.md file.
package brotli
// The dictDecoder implements the LZ77 sliding dictionary that is commonly used
// in various compression formats. For performance reasons, this implementation
// performs little to no sanity checks about the arguments. As such, the
// invariants documented for each method call must be respected. Furthermore,
// to reduce the memory footprint decompressing short streams, the dictionary
// starts with a relatively small size and then lazily grows.
const (
initSize = 4096 // Initial size allocated for sliding dictionary
growFactor = 4 // Rate the dictionary is grown to match expected size
)
type dictDecoder struct {
// Invariant: len(hist) <= size
size int // Sliding window size
hist []byte // Sliding window history, dynamically grown to match size
// Invariant: 0 <= rdPos <= wrPos <= len(hist)
wrPos int // Current output position in buffer
rdPos int // Have emitted hist[:rdPos] already
full bool // Has a full window length been written yet?
}
func (dd *dictDecoder) Init(size int) {
*dd = dictDecoder{hist: dd.hist}
// Regardless of what size claims, start with a small dictionary to avoid
// denial-of-service attacks with large memory allocation.
dd.size = size
if dd.hist == nil {
dd.hist = make([]byte, initSize)
}
dd.hist = dd.hist[:cap(dd.hist)]
if len(dd.hist) > dd.size {
dd.hist = dd.hist[:dd.size]
}
for i := range dd.hist {
dd.hist[i] = 0 // Zero out history to make LastBytes logic easier
}
}
// HistSize reports the total amount of historical data in the dictionary.
func (dd *dictDecoder) HistSize() int {
if dd.full {
return dd.size
}
return dd.wrPos
}
// AvailSize reports the available amount of output buffer space.
func (dd *dictDecoder) AvailSize() int {
return len(dd.hist) - dd.wrPos
}
// WriteSlice returns a slice of the available buffer to write data to.
//
// This invariant will be kept: len(s) <= AvailSize()
func (dd *dictDecoder) WriteSlice() []byte {
return dd.hist[dd.wrPos:]
}
// WriteMark advances the writer pointer by cnt.
//
// This invariant must be kept: 0 <= cnt <= AvailSize()
func (dd *dictDecoder) WriteMark(cnt int) {
dd.wrPos += cnt
}
// WriteCopy copies a string at a given (distance, length) to the output.
// This returns the number of bytes copied and may be less than the requested
// length if the available space in the output buffer is too small.
//
// This invariant must be kept: 0 < dist <= HistSize()
func (dd *dictDecoder) WriteCopy(dist, length int) int {
wrBase := dd.wrPos
wrEnd := dd.wrPos + length
if wrEnd > len(dd.hist) {
wrEnd = len(dd.hist)
}
// Copy non-overlapping section after destination.
rdPos := dd.wrPos - dist
if rdPos < 0 {
rdPos += len(dd.hist)
dd.wrPos += copy(dd.hist[dd.wrPos:wrEnd], dd.hist[rdPos:])
rdPos = 0
}
// Copy overlapping section before destination.
for dd.wrPos < wrEnd {
dd.wrPos += copy(dd.hist[dd.wrPos:wrEnd], dd.hist[rdPos:dd.wrPos])
}
return dd.wrPos - wrBase
}
// ReadFlush returns a slice of the historical buffer that is ready to be
// emitted to the user. A call to ReadFlush is only valid after all of the data
// from a previous call to ReadFlush has been consumed.
func (dd *dictDecoder) ReadFlush() []byte {
toRead := dd.hist[dd.rdPos:dd.wrPos]
dd.rdPos = dd.wrPos
if dd.wrPos == len(dd.hist) {
if len(dd.hist) == dd.size {
dd.wrPos, dd.rdPos = 0, 0
dd.full = true
} else {
// Allocate a larger history buffer.
size := cap(dd.hist) * growFactor
if size > dd.size {
size = dd.size
}
hist := make([]byte, size)
copy(hist, dd.hist)
dd.hist = hist
}
}
return toRead
}
// LastBytes reports the last 2 bytes in the dictionary. If they do not exist,
// then zero values are returned.
func (dd *dictDecoder) LastBytes() (p1, p2 byte) {
if dd.wrPos > 1 {
return dd.hist[dd.wrPos-1], dd.hist[dd.wrPos-2]
} else if dd.wrPos > 0 {
return dd.hist[dd.wrPos-1], dd.hist[len(dd.hist)-1]
} else {
return dd.hist[len(dd.hist)-1], dd.hist[len(dd.hist)-2]
}
}
|
