seqdec.go

Documentation: github.com/klauspost/compress/zstd

     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  	"errors"
     9  	"fmt"
    10  	"io"
    11  )
    12  
    13  type seq struct {
    14  	litLen   uint32
    15  	matchLen uint32
    16  	offset   uint32
    17  
    18  	// Codes are stored here for the encoder
    19  	// so they only have to be looked up once.
    20  	llCode, mlCode, ofCode uint8
    21  }
    22  
    23  type seqVals struct {
    24  	ll, ml, mo int
    25  }
    26  
    27  func (s seq) String() string {
    28  	if s.offset <= 3 {
    29  		if s.offset == 0 {
    30  			return fmt.Sprint("litLen:", s.litLen, ", matchLen:", s.matchLen+zstdMinMatch, ", offset: INVALID (0)")
    31  		}
    32  		return fmt.Sprint("litLen:", s.litLen, ", matchLen:", s.matchLen+zstdMinMatch, ", offset:", s.offset, " (repeat)")
    33  	}
    34  	return fmt.Sprint("litLen:", s.litLen, ", matchLen:", s.matchLen+zstdMinMatch, ", offset:", s.offset-3, " (new)")
    35  }
    36  
    37  type seqCompMode uint8
    38  
    39  const (
    40  	compModePredefined seqCompMode = iota
    41  	compModeRLE
    42  	compModeFSE
    43  	compModeRepeat
    44  )
    45  
    46  type sequenceDec struct {
    47  	// decoder keeps track of the current state and updates it from the bitstream.
    48  	fse    *fseDecoder
    49  	state  fseState
    50  	repeat bool
    51  }
    52  
    53  // init the state of the decoder with input from stream.
    54  func (s *sequenceDec) init(br *bitReader) error {
    55  	if s.fse == nil {
    56  		return errors.New("sequence decoder not defined")
    57  	}
    58  	s.state.init(br, s.fse.actualTableLog, s.fse.dt[:1<<s.fse.actualTableLog])
    59  	return nil
    60  }
    61  
    62  // sequenceDecs contains all 3 sequence decoders and their state.
    63  type sequenceDecs struct {
    64  	litLengths   sequenceDec
    65  	offsets      sequenceDec
    66  	matchLengths sequenceDec
    67  	prevOffset   [3]int
    68  	dict         []byte
    69  	literals     []byte
    70  	out          []byte
    71  	nSeqs        int
    72  	br           *bitReader
    73  	seqSize      int
    74  	windowSize   int
    75  	maxBits      uint8
    76  	maxSyncLen   uint64
    77  }
    78  
    79  // initialize all 3 decoders from the stream input.
    80  func (s *sequenceDecs) initialize(br *bitReader, hist *history, out []byte) error {
    81  	if err := s.litLengths.init(br); err != nil {
    82  		return errors.New("litLengths:" + err.Error())
    83  	}
    84  	if err := s.offsets.init(br); err != nil {
    85  		return errors.New("offsets:" + err.Error())
    86  	}
    87  	if err := s.matchLengths.init(br); err != nil {
    88  		return errors.New("matchLengths:" + err.Error())
    89  	}
    90  	s.br = br
    91  	s.prevOffset = hist.recentOffsets
    92  	s.maxBits = s.litLengths.fse.maxBits + s.offsets.fse.maxBits + s.matchLengths.fse.maxBits
    93  	s.windowSize = hist.windowSize
    94  	s.out = out
    95  	s.dict = nil
    96  	if hist.dict != nil {
    97  		s.dict = hist.dict.content
    98  	}
    99  	return nil
   100  }
   101  
   102  func (s *sequenceDecs) freeDecoders() {
   103  	if f := s.litLengths.fse; f != nil && !f.preDefined {
   104  		fseDecoderPool.Put(f)
   105  		s.litLengths.fse = nil
   106  	}
   107  	if f := s.offsets.fse; f != nil && !f.preDefined {
   108  		fseDecoderPool.Put(f)
   109  		s.offsets.fse = nil
   110  	}
   111  	if f := s.matchLengths.fse; f != nil && !f.preDefined {
   112  		fseDecoderPool.Put(f)
   113  		s.matchLengths.fse = nil
   114  	}
   115  }
   116  
   117  // execute will execute the decoded sequence with the provided history.
   118  // The sequence must be evaluated before being sent.
   119  func (s *sequenceDecs) execute(seqs []seqVals, hist []byte) error {
   120  	if len(s.dict) == 0 {
   121  		return s.executeSimple(seqs, hist)
   122  	}
   123  
   124  	// Ensure we have enough output size...
   125  	if len(s.out)+s.seqSize > cap(s.out) {
   126  		addBytes := s.seqSize + len(s.out)
   127  		s.out = append(s.out, make([]byte, addBytes)...)
   128  		s.out = s.out[:len(s.out)-addBytes]
   129  	}
   130  
   131  	if debugDecoder {
   132  		printf("Execute %d seqs with hist %d, dict %d, literals: %d into %d bytes\n", len(seqs), len(hist), len(s.dict), len(s.literals), s.seqSize)
   133  	}
   134  
   135  	var t = len(s.out)
   136  	out := s.out[:t+s.seqSize]
   137  
   138  	for _, seq := range seqs {
   139  		// Add literals
   140  		copy(out[t:], s.literals[:seq.ll])
   141  		t += seq.ll
   142  		s.literals = s.literals[seq.ll:]
   143  
   144  		// Copy from dictionary...
   145  		if seq.mo > t+len(hist) || seq.mo > s.windowSize {
   146  			if len(s.dict) == 0 {
   147  				return fmt.Errorf("match offset (%d) bigger than current history (%d)", seq.mo, t+len(hist))
   148  			}
   149  
   150  			// we may be in dictionary.
   151  			dictO := len(s.dict) - (seq.mo - (t + len(hist)))
   152  			if dictO < 0 || dictO >= len(s.dict) {
   153  				return fmt.Errorf("match offset (%d) bigger than current history+dict (%d)", seq.mo, t+len(hist)+len(s.dict))
   154  			}
   155  			end := dictO + seq.ml
   156  			if end > len(s.dict) {
   157  				n := len(s.dict) - dictO
   158  				copy(out[t:], s.dict[dictO:])
   159  				t += n
   160  				seq.ml -= n
   161  			} else {
   162  				copy(out[t:], s.dict[dictO:end])
   163  				t += end - dictO
   164  				continue
   165  			}
   166  		}
   167  
   168  		// Copy from history.
   169  		if v := seq.mo - t; v > 0 {
   170  			// v is the start position in history from end.
   171  			start := len(hist) - v
   172  			if seq.ml > v {
   173  				// Some goes into current block.
   174  				// Copy remainder of history
   175  				copy(out[t:], hist[start:])
   176  				t += v
   177  				seq.ml -= v
   178  			} else {
   179  				copy(out[t:], hist[start:start+seq.ml])
   180  				t += seq.ml
   181  				continue
   182  			}
   183  		}
   184  		// We must be in current buffer now
   185  		if seq.ml > 0 {
   186  			start := t - seq.mo
   187  			if seq.ml <= t-start {
   188  				// No overlap
   189  				copy(out[t:], out[start:start+seq.ml])
   190  				t += seq.ml
   191  				continue
   192  			} else {
   193  				// Overlapping copy
   194  				// Extend destination slice and copy one byte at the time.
   195  				src := out[start : start+seq.ml]
   196  				dst := out[t:]
   197  				dst = dst[:len(src)]
   198  				t += len(src)
   199  				// Destination is the space we just added.
   200  				for i := range src {
   201  					dst[i] = src[i]
   202  				}
   203  			}
   204  		}
   205  	}
   206  
   207  	// Add final literals
   208  	copy(out[t:], s.literals)
   209  	if debugDecoder {
   210  		t += len(s.literals)
   211  		if t != len(out) {
   212  			panic(fmt.Errorf("length mismatch, want %d, got %d, ss: %d", len(out), t, s.seqSize))
   213  		}
   214  	}
   215  	s.out = out
   216  
   217  	return nil
   218  }
   219  
   220  // decode sequences from the stream with the provided history.
   221  func (s *sequenceDecs) decodeSync(hist []byte) error {
   222  	supported, err := s.decodeSyncSimple(hist)
   223  	if supported {
   224  		return err
   225  	}
   226  
   227  	br := s.br
   228  	seqs := s.nSeqs
   229  	startSize := len(s.out)
   230  	// Grab full sizes tables, to avoid bounds checks.
   231  	llTable, mlTable, ofTable := s.litLengths.fse.dt[:maxTablesize], s.matchLengths.fse.dt[:maxTablesize], s.offsets.fse.dt[:maxTablesize]
   232  	llState, mlState, ofState := s.litLengths.state.state, s.matchLengths.state.state, s.offsets.state.state
   233  	out := s.out
   234  	maxBlockSize := maxCompressedBlockSize
   235  	if s.windowSize < maxBlockSize {
   236  		maxBlockSize = s.windowSize
   237  	}
   238  
   239  	if debugDecoder {
   240  		println("decodeSync: decoding", seqs, "sequences", br.remain(), "bits remain on stream")
   241  	}
   242  	for i := seqs - 1; i >= 0; i-- {
   243  		if br.overread() {
   244  			printf("reading sequence %d, exceeded available data. Overread by %d\n", seqs-i, -br.remain())
   245  			return io.ErrUnexpectedEOF
   246  		}
   247  		var ll, mo, ml int
   248  		if len(br.in) > 4+((maxOffsetBits+16+16)>>3) {
   249  			// inlined function:
   250  			// ll, mo, ml = s.nextFast(br, llState, mlState, ofState)
   251  
   252  			// Final will not read from stream.
   253  			var llB, mlB, moB uint8
   254  			ll, llB = llState.final()
   255  			ml, mlB = mlState.final()
   256  			mo, moB = ofState.final()
   257  
   258  			// extra bits are stored in reverse order.
   259  			br.fillFast()
   260  			mo += br.getBits(moB)
   261  			if s.maxBits > 32 {
   262  				br.fillFast()
   263  			}
   264  			ml += br.getBits(mlB)
   265  			ll += br.getBits(llB)
   266  
   267  			if moB > 1 {
   268  				s.prevOffset[2] = s.prevOffset[1]
   269  				s.prevOffset[1] = s.prevOffset[0]
   270  				s.prevOffset[0] = mo
   271  			} else {
   272  				// mo = s.adjustOffset(mo, ll, moB)
   273  				// Inlined for rather big speedup
   274  				if ll == 0 {
   275  					// There is an exception though, when current sequence's literals_length = 0.
   276  					// In this case, repeated offsets are shifted by one, so an offset_value of 1 means Repeated_Offset2,
   277  					// an offset_value of 2 means Repeated_Offset3, and an offset_value of 3 means Repeated_Offset1 - 1_byte.
   278  					mo++
   279  				}
   280  
   281  				if mo == 0 {
   282  					mo = s.prevOffset[0]
   283  				} else {
   284  					var temp int
   285  					if mo == 3 {
   286  						temp = s.prevOffset[0] - 1
   287  					} else {
   288  						temp = s.prevOffset[mo]
   289  					}
   290  
   291  					if temp == 0 {
   292  						// 0 is not valid; input is corrupted; force offset to 1
   293  						println("WARNING: temp was 0")
   294  						temp = 1
   295  					}
   296  
   297  					if mo != 1 {
   298  						s.prevOffset[2] = s.prevOffset[1]
   299  					}
   300  					s.prevOffset[1] = s.prevOffset[0]
   301  					s.prevOffset[0] = temp
   302  					mo = temp
   303  				}
   304  			}
   305  			br.fillFast()
   306  		} else {
   307  			ll, mo, ml = s.next(br, llState, mlState, ofState)
   308  			br.fill()
   309  		}
   310  
   311  		if debugSequences {
   312  			println("Seq", seqs-i-1, "Litlen:", ll, "mo:", mo, "(abs) ml:", ml)
   313  		}
   314  
   315  		if ll > len(s.literals) {
   316  			return fmt.Errorf("unexpected literal count, want %d bytes, but only %d is available", ll, len(s.literals))
   317  		}
   318  		size := ll + ml + len(out)
   319  		if size-startSize > maxBlockSize {
   320  			return fmt.Errorf("output bigger than max block size (%d)", maxBlockSize)
   321  		}
   322  		if size > cap(out) {
   323  			// Not enough size, which can happen under high volume block streaming conditions
   324  			// but could be if destination slice is too small for sync operations.
   325  			// over-allocating here can create a large amount of GC pressure so we try to keep
   326  			// it as contained as possible
   327  			used := len(out) - startSize
   328  			addBytes := 256 + ll + ml + used>>2
   329  			// Clamp to max block size.
   330  			if used+addBytes > maxBlockSize {
   331  				addBytes = maxBlockSize - used
   332  			}
   333  			out = append(out, make([]byte, addBytes)...)
   334  			out = out[:len(out)-addBytes]
   335  		}
   336  		if ml > maxMatchLen {
   337  			return fmt.Errorf("match len (%d) bigger than max allowed length", ml)
   338  		}
   339  
   340  		// Add literals
   341  		out = append(out, s.literals[:ll]...)
   342  		s.literals = s.literals[ll:]
   343  
   344  		if mo == 0 && ml > 0 {
   345  			return fmt.Errorf("zero matchoff and matchlen (%d) > 0", ml)
   346  		}
   347  
   348  		if mo > len(out)+len(hist) || mo > s.windowSize {
   349  			if len(s.dict) == 0 {
   350  				return fmt.Errorf("match offset (%d) bigger than current history (%d)", mo, len(out)+len(hist)-startSize)
   351  			}
   352  
   353  			// we may be in dictionary.
   354  			dictO := len(s.dict) - (mo - (len(out) + len(hist)))
   355  			if dictO < 0 || dictO >= len(s.dict) {
   356  				return fmt.Errorf("match offset (%d) bigger than current history (%d)", mo, len(out)+len(hist)-startSize)
   357  			}
   358  			end := dictO + ml
   359  			if end > len(s.dict) {
   360  				out = append(out, s.dict[dictO:]...)
   361  				ml -= len(s.dict) - dictO
   362  			} else {
   363  				out = append(out, s.dict[dictO:end]...)
   364  				mo = 0
   365  				ml = 0
   366  			}
   367  		}
   368  
   369  		// Copy from history.
   370  		// TODO: Blocks without history could be made to ignore this completely.
   371  		if v := mo - len(out); v > 0 {
   372  			// v is the start position in history from end.
   373  			start := len(hist) - v
   374  			if ml > v {
   375  				// Some goes into current block.
   376  				// Copy remainder of history
   377  				out = append(out, hist[start:]...)
   378  				ml -= v
   379  			} else {
   380  				out = append(out, hist[start:start+ml]...)
   381  				ml = 0
   382  			}
   383  		}
   384  		// We must be in current buffer now
   385  		if ml > 0 {
   386  			start := len(out) - mo
   387  			if ml <= len(out)-start {
   388  				// No overlap
   389  				out = append(out, out[start:start+ml]...)
   390  			} else {
   391  				// Overlapping copy
   392  				// Extend destination slice and copy one byte at the time.
   393  				out = out[:len(out)+ml]
   394  				src := out[start : start+ml]
   395  				// Destination is the space we just added.
   396  				dst := out[len(out)-ml:]
   397  				dst = dst[:len(src)]
   398  				for i := range src {
   399  					dst[i] = src[i]
   400  				}
   401  			}
   402  		}
   403  		if i == 0 {
   404  			// This is the last sequence, so we shouldn't update state.
   405  			break
   406  		}
   407  
   408  		// Manually inlined, ~ 5-20% faster
   409  		// Update all 3 states at once. Approx 20% faster.
   410  		nBits := llState.nbBits() + mlState.nbBits() + ofState.nbBits()
   411  		if nBits == 0 {
   412  			llState = llTable[llState.newState()&maxTableMask]
   413  			mlState = mlTable[mlState.newState()&maxTableMask]
   414  			ofState = ofTable[ofState.newState()&maxTableMask]
   415  		} else {
   416  			bits := br.get32BitsFast(nBits)
   417  
   418  			lowBits := uint16(bits >> ((ofState.nbBits() + mlState.nbBits()) & 31))
   419  			llState = llTable[(llState.newState()+lowBits)&maxTableMask]
   420  
   421  			lowBits = uint16(bits >> (ofState.nbBits() & 31))
   422  			lowBits &= bitMask[mlState.nbBits()&15]
   423  			mlState = mlTable[(mlState.newState()+lowBits)&maxTableMask]
   424  
   425  			lowBits = uint16(bits) & bitMask[ofState.nbBits()&15]
   426  			ofState = ofTable[(ofState.newState()+lowBits)&maxTableMask]
   427  		}
   428  	}
   429  
   430  	if size := len(s.literals) + len(out) - startSize; size > maxBlockSize {
   431  		return fmt.Errorf("output bigger than max block size (%d)", maxBlockSize)
   432  	}
   433  
   434  	// Add final literals
   435  	s.out = append(out, s.literals...)
   436  	return br.close()
   437  }
   438  
   439  var bitMask [16]uint16
   440  
   441  func init() {
   442  	for i := range bitMask[:] {
   443  		bitMask[i] = uint16((1 << uint(i)) - 1)
   444  	}
   445  }
   446  
   447  func (s *sequenceDecs) next(br *bitReader, llState, mlState, ofState decSymbol) (ll, mo, ml int) {
   448  	// Final will not read from stream.
   449  	ll, llB := llState.final()
   450  	ml, mlB := mlState.final()
   451  	mo, moB := ofState.final()
   452  
   453  	// extra bits are stored in reverse order.
   454  	br.fill()
   455  	mo += br.getBits(moB)
   456  	if s.maxBits > 32 {
   457  		br.fill()
   458  	}
   459  	// matchlength+literal length, max 32 bits
   460  	ml += br.getBits(mlB)
   461  	ll += br.getBits(llB)
   462  	mo = s.adjustOffset(mo, ll, moB)
   463  	return
   464  }
   465  
   466  func (s *sequenceDecs) adjustOffset(offset, litLen int, offsetB uint8) int {
   467  	if offsetB > 1 {
   468  		s.prevOffset[2] = s.prevOffset[1]
   469  		s.prevOffset[1] = s.prevOffset[0]
   470  		s.prevOffset[0] = offset
   471  		return offset
   472  	}
   473  
   474  	if litLen == 0 {
   475  		// There is an exception though, when current sequence's literals_length = 0.
   476  		// In this case, repeated offsets are shifted by one, so an offset_value of 1 means Repeated_Offset2,
   477  		// an offset_value of 2 means Repeated_Offset3, and an offset_value of 3 means Repeated_Offset1 - 1_byte.
   478  		offset++
   479  	}
   480  
   481  	if offset == 0 {
   482  		return s.prevOffset[0]
   483  	}
   484  	var temp int
   485  	if offset == 3 {
   486  		temp = s.prevOffset[0] - 1
   487  	} else {
   488  		temp = s.prevOffset[offset]
   489  	}
   490  
   491  	if temp == 0 {
   492  		// 0 is not valid; input is corrupted; force offset to 1
   493  		println("temp was 0")
   494  		temp = 1
   495  	}
   496  
   497  	if offset != 1 {
   498  		s.prevOffset[2] = s.prevOffset[1]
   499  	}
   500  	s.prevOffset[1] = s.prevOffset[0]
   501  	s.prevOffset[0] = temp
   502  	return temp
   503  }
   504
View as plain text