history.go raw

   1  // Copyright 2019+ Klaus Post. All rights reserved.
   2  // License information can be found in the LICENSE file.
   3  // Based on work by Yann Collet, released under BSD License.
   4  
   5  package zstd
   6  
   7  import (
   8  	"github.com/klauspost/compress/huff0"
   9  )
  10  
  11  // history contains the information transferred between blocks.
  12  type history struct {
  13  	// Literal decompression
  14  	huffTree *huff0.Scratch
  15  
  16  	// Sequence decompression
  17  	decoders      sequenceDecs
  18  	recentOffsets [3]int
  19  
  20  	// History buffer...
  21  	b []byte
  22  
  23  	// ignoreBuffer is meant to ignore a number of bytes
  24  	// when checking for matches in history
  25  	ignoreBuffer int
  26  
  27  	windowSize       int
  28  	allocFrameBuffer int // needed?
  29  	error            bool
  30  	dict             *dict
  31  }
  32  
  33  // reset will reset the history to initial state of a frame.
  34  // The history must already have been initialized to the desired size.
  35  func (h *history) reset() {
  36  	h.b = h.b[:0]
  37  	h.ignoreBuffer = 0
  38  	h.error = false
  39  	h.recentOffsets = [3]int{1, 4, 8}
  40  	h.decoders.freeDecoders()
  41  	h.decoders = sequenceDecs{br: h.decoders.br}
  42  	h.freeHuffDecoder()
  43  	h.huffTree = nil
  44  	h.dict = nil
  45  	//printf("history created: %+v (l: %d, c: %d)", *h, len(h.b), cap(h.b))
  46  }
  47  
  48  func (h *history) freeHuffDecoder() {
  49  	if h.huffTree != nil {
  50  		if h.dict == nil || h.dict.litEnc != h.huffTree {
  51  			huffDecoderPool.Put(h.huffTree)
  52  			h.huffTree = nil
  53  		}
  54  	}
  55  }
  56  
  57  func (h *history) setDict(dict *dict) {
  58  	if dict == nil {
  59  		return
  60  	}
  61  	h.dict = dict
  62  	h.decoders.litLengths = dict.llDec
  63  	h.decoders.offsets = dict.ofDec
  64  	h.decoders.matchLengths = dict.mlDec
  65  	h.decoders.dict = dict.content
  66  	h.recentOffsets = dict.offsets
  67  	h.huffTree = dict.litEnc
  68  }
  69  
  70  // append bytes to history.
  71  // This function will make sure there is space for it,
  72  // if the buffer has been allocated with enough extra space.
  73  func (h *history) append(b []byte) {
  74  	if len(b) >= h.windowSize {
  75  		// Discard all history by simply overwriting
  76  		h.b = h.b[:h.windowSize]
  77  		copy(h.b, b[len(b)-h.windowSize:])
  78  		return
  79  	}
  80  
  81  	// If there is space, append it.
  82  	if len(b) < cap(h.b)-len(h.b) {
  83  		h.b = append(h.b, b...)
  84  		return
  85  	}
  86  
  87  	// Move data down so we only have window size left.
  88  	// We know we have less than window size in b at this point.
  89  	discard := len(b) + len(h.b) - h.windowSize
  90  	copy(h.b, h.b[discard:])
  91  	h.b = h.b[:h.windowSize]
  92  	copy(h.b[h.windowSize-len(b):], b)
  93  }
  94  
  95  // ensureBlock will ensure there is space for at least one block...
  96  func (h *history) ensureBlock() {
  97  	if cap(h.b) < h.allocFrameBuffer {
  98  		h.b = make([]byte, 0, h.allocFrameBuffer)
  99  		return
 100  	}
 101  
 102  	avail := cap(h.b) - len(h.b)
 103  	if avail >= h.windowSize || avail > maxCompressedBlockSize {
 104  		return
 105  	}
 106  	// Move data down so we only have window size left.
 107  	// We know we have less than window size in b at this point.
 108  	discard := len(h.b) - h.windowSize
 109  	copy(h.b, h.b[discard:])
 110  	h.b = h.b[:h.windowSize]
 111  }
 112  
 113  // append bytes to history without ever discarding anything.
 114  func (h *history) appendKeep(b []byte) {
 115  	h.b = append(h.b, b...)
 116  }
 117