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 := min(dstPos+length, len(dd.hist))
   108  
   109  	// Copy non-overlapping section after destination position.
   110  	//
   111  	// This section is non-overlapping in that the copy length for this section
   112  	// is always less than or equal to the backwards distance. This can occur
   113  	// if a distance refers to data that wraps-around in the buffer.
   114  	// Thus, a backwards copy is performed here; that is, the exact bytes in
   115  	// the source prior to the copy is placed in the destination.
   116  	if srcPos < 0 {
   117  		srcPos += len(dd.hist)
   118  		dstPos += copy(dd.hist[dstPos:endPos], dd.hist[srcPos:])
   119  		srcPos = 0
   120  	}
   121  
   122  	// Copy possibly overlapping section before destination position.
   123  	//
   124  	// This section can overlap if the copy length for this section is larger
   125  	// than the backwards distance. This is allowed by LZ77 so that repeated
   126  	// strings can be succinctly represented using (dist, length) pairs.
   127  	// Thus, a forwards copy is performed here; that is, the bytes copied is
   128  	// possibly dependent on the resulting bytes in the destination as the copy
   129  	// progresses along. This is functionally equivalent to the following:
   130  	//
   131  	//	for i := 0; i < endPos-dstPos; i++ {
   132  	//		dd.hist[dstPos+i] = dd.hist[srcPos+i]
   133  	//	}
   134  	//	dstPos = endPos
   135  	//
   136  	for dstPos < endPos {
   137  		dstPos += copy(dd.hist[dstPos:endPos], dd.hist[srcPos:dstPos])
   138  	}
   139  
   140  	dd.wrPos = dstPos
   141  	return dstPos - dstBase
   142  }
   143  
   144  // tryWriteCopy tries to copy a string at a given (distance, length) to the
   145  // output. This specialized version is optimized for short distances.
   146  //
   147  // This method is designed to be inlined for performance reasons.
   148  //
   149  // This invariant must be kept: 0 < dist <= histSize()
   150  func (dd *dictDecoder) tryWriteCopy(dist, length int) int {
   151  	dstPos := dd.wrPos
   152  	endPos := dstPos + length
   153  	if dstPos < dist || endPos > len(dd.hist) {
   154  		return 0
   155  	}
   156  	dstBase := dstPos
   157  	srcPos := dstPos - dist
   158  
   159  	// Copy possibly overlapping section before destination position.
   160  	for dstPos < endPos {
   161  		dstPos += copy(dd.hist[dstPos:endPos], dd.hist[srcPos:dstPos])
   162  	}
   163  
   164  	dd.wrPos = dstPos
   165  	return dstPos - dstBase
   166  }
   167  
   168  // readFlush returns a slice of the historical buffer that is ready to be
   169  // emitted to the user. The data returned by readFlush must be fully consumed
   170  // before calling any other dictDecoder methods.
   171  func (dd *dictDecoder) readFlush() []byte {
   172  	toRead := dd.hist[dd.rdPos:dd.wrPos]
   173  	dd.rdPos = dd.wrPos
   174  	if dd.wrPos == len(dd.hist) {
   175  		dd.wrPos, dd.rdPos = 0, 0
   176  		dd.full = true
   177  	}
   178  	return toRead
   179  }
   180
View as plain text