libgo/go/compress/flate/dict_decoder.go

   1 // Copyright 2016 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package flate
   6
   7 // dictDecoder implements the LZ77 sliding dictionary as used in decompression.
   8 // LZ77 decompresses data through sequences of two forms of commands:
   9 //
  10 //      * Literal insertions: Runs of one or more symbols are inserted into the data
  11 //      stream as is. This is accomplished through the writeByte method for a
  12 //      single symbol, or combinations of writeSlice/writeMark for multiple symbols.
  13 //      Any valid stream must start with a literal insertion if no preset dictionary
  14 //      is used.
  15 //
  16 //      * Backward copies: Runs of one or more symbols are copied from previously
  17 //      emitted data. Backward copies come as the tuple (dist, length) where dist
  18 //      determines how far back in the stream to copy from and length determines how
  19 //      many bytes to copy. Note that it is valid for the length to be greater than
  20 //      the distance. Since LZ77 uses forward copies, that situation is used to
  21 //      perform a form of run-length encoding on repeated runs of symbols.
  22 //      The writeCopy and tryWriteCopy are used to implement this command.
  23 //
  24 // For performance reasons, this implementation performs little to no sanity
  25 // checks about the arguments. As such, the invariants documented for each
  26 // method call must be respected.
  27 type dictDecoder struct {
  28         hist []byte // Sliding window history
  29
  30         // Invariant: 0 <= rdPos <= wrPos <= len(hist)
  31         wrPos int  // Current output position in buffer
  32         rdPos int  // Have emitted hist[:rdPos] already
  33         full  bool // Has a full window length been written yet?
  34 }
  35
  36 // init initializes dictDecoder to have a sliding window dictionary of the given
  37 // size. If a preset dict is provided, it will initialize the dictionary with
  38 // the contents of dict.
  39 func (dd *dictDecoder) init(size int, dict []byte) {
  40         *dd = dictDecoder{hist: dd.hist}
  41
  42         if cap(dd.hist) < size {
  43                 dd.hist = make([]byte, size)
  44         }
  45         dd.hist = dd.hist[:size]
  46
  47         if len(dict) > len(dd.hist) {
  48                 dict = dict[len(dict)-len(dd.hist):]
  49         }
  50         dd.wrPos = copy(dd.hist, dict)
  51         if dd.wrPos == len(dd.hist) {
  52                 dd.wrPos = 0
  53                 dd.full = true
  54         }
  55         dd.rdPos = dd.wrPos
  56 }
  57
  58 // histSize reports the total amount of historical data in the dictionary.
  59 func (dd *dictDecoder) histSize() int {
  60         if dd.full {
  61                 return len(dd.hist)
  62         }
  63         return dd.wrPos
  64 }
  65
  66 // availRead reports the number of bytes that can be flushed by readFlush.
  67 func (dd *dictDecoder) availRead() int {
  68         return dd.wrPos - dd.rdPos
  69 }
  70
  71 // availWrite reports the available amount of output buffer space.
  72 func (dd *dictDecoder) availWrite() int {
  73         return len(dd.hist) - dd.wrPos
  74 }
  75
  76 // writeSlice returns a slice of the available buffer to write data to.
  77 //
  78 // This invariant will be kept: len(s) <= availWrite()
  79 func (dd *dictDecoder) writeSlice() []byte {
  80         return dd.hist[dd.wrPos:]
  81 }
  82
  83 // writeMark advances the writer pointer by cnt.
  84 //
  85 // This invariant must be kept: 0 <= cnt <= availWrite()
  86 func (dd *dictDecoder) writeMark(cnt int) {
  87         dd.wrPos += cnt
  88 }
  89
  90 // writeByte writes a single byte to the dictionary.
  91 //
  92 // This invariant must be kept: 0 < availWrite()
  93 func (dd *dictDecoder) writeByte(c byte) {
  94         dd.hist[dd.wrPos] = c
  95         dd.wrPos++
  96 }
  97
  98 // writeCopy copies a string at a given (dist, length) to the output.
  99 // This returns the number of bytes copied and may be less than the requested
 100 // length if the available space in the output buffer is too small.
 101 //
 102 // This invariant must be kept: 0 < dist <= histSize()
 103 func (dd *dictDecoder) writeCopy(dist, length int) int {
 104         dstBase := dd.wrPos
 105         dstPos := dstBase
 106         srcPos := dstPos - dist
 107         endPos := dstPos + length
 108         if endPos > len(dd.hist) {
 109                 endPos = len(dd.hist)
 110         }
 111
 112         // Copy non-overlapping section after destination position.
 113         //
 114         // This section is non-overlapping in that the copy length for this section
 115         // is always less than or equal to the backwards distance. This can occur
 116         // if a distance refers to data that wraps-around in the buffer.
 117         // Thus, a backwards copy is performed here; that is, the exact bytes in
 118         // the source prior to the copy is placed in the destination.
 119         if srcPos < 0 {
 120                 srcPos += len(dd.hist)
 121                 dstPos += copy(dd.hist[dstPos:endPos], dd.hist[srcPos:])
 122                 srcPos = 0
 123         }
 124
 125         // Copy possibly overlapping section before destination position.
 126         //
 127         // This section can overlap if the copy length for this section is larger
 128         // than the backwards distance. This is allowed by LZ77 so that repeated
 129         // strings can be succinctly represented using (dist, length) pairs.
 130         // Thus, a forwards copy is performed here; that is, the bytes copied is
 131         // possibly dependent on the resulting bytes in the destination as the copy
 132         // progresses along. This is functionally equivalent to the following:
 133         //
 134         //      for i := 0; i < endPos-dstPos; i++ {
 135         //              dd.hist[dstPos+i] = dd.hist[srcPos+i]
 136         //      }
 137         //      dstPos = endPos
 138         //
 139         for dstPos < endPos {
 140                 dstPos += copy(dd.hist[dstPos:endPos], dd.hist[srcPos:dstPos])
 141         }
 142
 143         dd.wrPos = dstPos
 144         return dstPos - dstBase
 145 }
 146
 147 // tryWriteCopy tries to copy a string at a given (distance, length) to the
 148 // output. This specialized version is optimized for short distances.
 149 //
 150 // This method is designed to be inlined for performance reasons.
 151 //
 152 // This invariant must be kept: 0 < dist <= histSize()
 153 func (dd *dictDecoder) tryWriteCopy(dist, length int) int {
 154         dstPos := dd.wrPos
 155         endPos := dstPos + length
 156         if dstPos < dist || endPos > len(dd.hist) {
 157                 return 0
 158         }
 159         dstBase := dstPos
 160         srcPos := dstPos - dist
 161
 162         // Copy possibly overlapping section before destination position.
 163 loop:
 164         dstPos += copy(dd.hist[dstPos:endPos], dd.hist[srcPos:dstPos])
 165         if dstPos < endPos {
 166                 goto loop // Avoid for-loop so that this function can be inlined
 167         }
 168
 169         dd.wrPos = dstPos
 170         return dstPos - dstBase
 171 }
 172
 173 // readFlush returns a slice of the historical buffer that is ready to be
 174 // emitted to the user. The data returned by readFlush must be fully consumed
 175 // before calling any other dictDecoder methods.
 176 func (dd *dictDecoder) readFlush() []byte {
 177         toRead := dd.hist[dd.rdPos:dd.wrPos]
 178         dd.rdPos = dd.wrPos
 179         if dd.wrPos == len(dd.hist) {
 180                 dd.wrPos, dd.rdPos = 0, 0
 181                 dd.full = true
 182         }
 183         return toRead
 184 }