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