1// Copyright 2015, Joe Tsai. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE.md file.
4
5package brotli
6
7// The dictDecoder implements the LZ77 sliding dictionary that is commonly used
8// in various compression formats. For performance reasons, this implementation
9// performs little to no sanity checks about the arguments. As such, the
10// invariants documented for each method call must be respected. Furthermore,
11// to reduce the memory footprint decompressing short streams, the dictionary
12// starts with a relatively small size and then lazily grows.
13
14const (
15	initSize   = 4096 // Initial size allocated for sliding dictionary
16	growFactor = 4    // Rate the dictionary is grown to match expected size
17)
18
19type dictDecoder struct {
20	// Invariant: len(hist) <= size
21	size int    // Sliding window size
22	hist []byte // Sliding window history, dynamically grown to match size
23
24	// Invariant: 0 <= rdPos <= wrPos <= len(hist)
25	wrPos int  // Current output position in buffer
26	rdPos int  // Have emitted hist[:rdPos] already
27	full  bool // Has a full window length been written yet?
28}
29
30func (dd *dictDecoder) Init(size int) {
31	*dd = dictDecoder{hist: dd.hist}
32
33	// Regardless of what size claims, start with a small dictionary to avoid
34	// denial-of-service attacks with large memory allocation.
35	dd.size = size
36	if dd.hist == nil {
37		dd.hist = make([]byte, initSize)
38	}
39	dd.hist = dd.hist[:cap(dd.hist)]
40	if len(dd.hist) > dd.size {
41		dd.hist = dd.hist[:dd.size]
42	}
43	for i := range dd.hist {
44		dd.hist[i] = 0 // Zero out history to make LastBytes logic easier
45	}
46}
47
48// HistSize reports the total amount of historical data in the dictionary.
49func (dd *dictDecoder) HistSize() int {
50	if dd.full {
51		return dd.size
52	}
53	return dd.wrPos
54}
55
56// AvailSize reports the available amount of output buffer space.
57func (dd *dictDecoder) AvailSize() int {
58	return len(dd.hist) - dd.wrPos
59}
60
61// WriteSlice returns a slice of the available buffer to write data to.
62//
63// This invariant will be kept: len(s) <= AvailSize()
64func (dd *dictDecoder) WriteSlice() []byte {
65	return dd.hist[dd.wrPos:]
66}
67
68// WriteMark advances the writer pointer by cnt.
69//
70// This invariant must be kept: 0 <= cnt <= AvailSize()
71func (dd *dictDecoder) WriteMark(cnt int) {
72	dd.wrPos += cnt
73}
74
75// WriteCopy copies a string at a given (distance, length) to the output.
76// This returns the number of bytes copied and may be less than the requested
77// length if the available space in the output buffer is too small.
78//
79// This invariant must be kept: 0 < dist <= HistSize()
80func (dd *dictDecoder) WriteCopy(dist, length int) int {
81	wrBase := dd.wrPos
82	wrEnd := dd.wrPos + length
83	if wrEnd > len(dd.hist) {
84		wrEnd = len(dd.hist)
85	}
86
87	// Copy non-overlapping section after destination.
88	rdPos := dd.wrPos - dist
89	if rdPos < 0 {
90		rdPos += len(dd.hist)
91		dd.wrPos += copy(dd.hist[dd.wrPos:wrEnd], dd.hist[rdPos:])
92		rdPos = 0
93	}
94
95	// Copy overlapping section before destination.
96	for dd.wrPos < wrEnd {
97		dd.wrPos += copy(dd.hist[dd.wrPos:wrEnd], dd.hist[rdPos:dd.wrPos])
98	}
99	return dd.wrPos - wrBase
100}
101
102// ReadFlush returns a slice of the historical buffer that is ready to be
103// emitted to the user. A call to ReadFlush is only valid after all of the data
104// from a previous call to ReadFlush has been consumed.
105func (dd *dictDecoder) ReadFlush() []byte {
106	toRead := dd.hist[dd.rdPos:dd.wrPos]
107	dd.rdPos = dd.wrPos
108	if dd.wrPos == len(dd.hist) {
109		if len(dd.hist) == dd.size {
110			dd.wrPos, dd.rdPos = 0, 0
111			dd.full = true
112		} else {
113			// Allocate a larger history buffer.
114			size := cap(dd.hist) * growFactor
115			if size > dd.size {
116				size = dd.size
117			}
118			hist := make([]byte, size)
119			copy(hist, dd.hist)
120			dd.hist = hist
121		}
122	}
123	return toRead
124}
125
126// LastBytes reports the last 2 bytes in the dictionary. If they do not exist,
127// then zero values are returned.
128func (dd *dictDecoder) LastBytes() (p1, p2 byte) {
129	if dd.wrPos > 1 {
130		return dd.hist[dd.wrPos-1], dd.hist[dd.wrPos-2]
131	} else if dd.wrPos > 0 {
132		return dd.hist[dd.wrPos-1], dd.hist[len(dd.hist)-1]
133	} else {
134		return dd.hist[len(dd.hist)-1], dd.hist[len(dd.hist)-2]
135	}
136}
137