seqdec_generic.go

Documentation: github.com/klauspost/compress/zstd

     1  //go:build !amd64 || appengine || !gc || noasm
     2  // +build !amd64 appengine !gc noasm
     3  
     4  package zstd
     5  
     6  import (
     7  	"fmt"
     8  	"io"
     9  )
    10  
    11  // decode sequences from the stream with the provided history but without dictionary.
    12  func (s *sequenceDecs) decodeSyncSimple(hist []byte) (bool, error) {
    13  	return false, nil
    14  }
    15  
    16  // decode sequences from the stream without the provided history.
    17  func (s *sequenceDecs) decode(seqs []seqVals) error {
    18  	br := s.br
    19  
    20  	// Grab full sizes tables, to avoid bounds checks.
    21  	llTable, mlTable, ofTable := s.litLengths.fse.dt[:maxTablesize], s.matchLengths.fse.dt[:maxTablesize], s.offsets.fse.dt[:maxTablesize]
    22  	llState, mlState, ofState := s.litLengths.state.state, s.matchLengths.state.state, s.offsets.state.state
    23  	s.seqSize = 0
    24  	litRemain := len(s.literals)
    25  
    26  	maxBlockSize := maxCompressedBlockSize
    27  	if s.windowSize < maxBlockSize {
    28  		maxBlockSize = s.windowSize
    29  	}
    30  	for i := range seqs {
    31  		var ll, mo, ml int
    32  		if len(br.in) > 4+((maxOffsetBits+16+16)>>3) {
    33  			// inlined function:
    34  			// ll, mo, ml = s.nextFast(br, llState, mlState, ofState)
    35  
    36  			// Final will not read from stream.
    37  			var llB, mlB, moB uint8
    38  			ll, llB = llState.final()
    39  			ml, mlB = mlState.final()
    40  			mo, moB = ofState.final()
    41  
    42  			// extra bits are stored in reverse order.
    43  			br.fillFast()
    44  			mo += br.getBits(moB)
    45  			if s.maxBits > 32 {
    46  				br.fillFast()
    47  			}
    48  			ml += br.getBits(mlB)
    49  			ll += br.getBits(llB)
    50  
    51  			if moB > 1 {
    52  				s.prevOffset[2] = s.prevOffset[1]
    53  				s.prevOffset[1] = s.prevOffset[0]
    54  				s.prevOffset[0] = mo
    55  			} else {
    56  				// mo = s.adjustOffset(mo, ll, moB)
    57  				// Inlined for rather big speedup
    58  				if ll == 0 {
    59  					// There is an exception though, when current sequence's literals_length = 0.
    60  					// In this case, repeated offsets are shifted by one, so an offset_value of 1 means Repeated_Offset2,
    61  					// an offset_value of 2 means Repeated_Offset3, and an offset_value of 3 means Repeated_Offset1 - 1_byte.
    62  					mo++
    63  				}
    64  
    65  				if mo == 0 {
    66  					mo = s.prevOffset[0]
    67  				} else {
    68  					var temp int
    69  					if mo == 3 {
    70  						temp = s.prevOffset[0] - 1
    71  					} else {
    72  						temp = s.prevOffset[mo]
    73  					}
    74  
    75  					if temp == 0 {
    76  						// 0 is not valid; input is corrupted; force offset to 1
    77  						println("WARNING: temp was 0")
    78  						temp = 1
    79  					}
    80  
    81  					if mo != 1 {
    82  						s.prevOffset[2] = s.prevOffset[1]
    83  					}
    84  					s.prevOffset[1] = s.prevOffset[0]
    85  					s.prevOffset[0] = temp
    86  					mo = temp
    87  				}
    88  			}
    89  			br.fillFast()
    90  		} else {
    91  			if br.overread() {
    92  				if debugDecoder {
    93  					printf("reading sequence %d, exceeded available data\n", i)
    94  				}
    95  				return io.ErrUnexpectedEOF
    96  			}
    97  			ll, mo, ml = s.next(br, llState, mlState, ofState)
    98  			br.fill()
    99  		}
   100  
   101  		if debugSequences {
   102  			println("Seq", i, "Litlen:", ll, "mo:", mo, "(abs) ml:", ml)
   103  		}
   104  		// Evaluate.
   105  		// We might be doing this async, so do it early.
   106  		if mo == 0 && ml > 0 {
   107  			return fmt.Errorf("zero matchoff and matchlen (%d) > 0", ml)
   108  		}
   109  		if ml > maxMatchLen {
   110  			return fmt.Errorf("match len (%d) bigger than max allowed length", ml)
   111  		}
   112  		s.seqSize += ll + ml
   113  		if s.seqSize > maxBlockSize {
   114  			return fmt.Errorf("output bigger than max block size (%d)", maxBlockSize)
   115  		}
   116  		litRemain -= ll
   117  		if litRemain < 0 {
   118  			return fmt.Errorf("unexpected literal count, want %d bytes, but only %d is available", ll, litRemain+ll)
   119  		}
   120  		seqs[i] = seqVals{
   121  			ll: ll,
   122  			ml: ml,
   123  			mo: mo,
   124  		}
   125  		if i == len(seqs)-1 {
   126  			// This is the last sequence, so we shouldn't update state.
   127  			break
   128  		}
   129  
   130  		// Manually inlined, ~ 5-20% faster
   131  		// Update all 3 states at once. Approx 20% faster.
   132  		nBits := llState.nbBits() + mlState.nbBits() + ofState.nbBits()
   133  		if nBits == 0 {
   134  			llState = llTable[llState.newState()&maxTableMask]
   135  			mlState = mlTable[mlState.newState()&maxTableMask]
   136  			ofState = ofTable[ofState.newState()&maxTableMask]
   137  		} else {
   138  			bits := br.get32BitsFast(nBits)
   139  			lowBits := uint16(bits >> ((ofState.nbBits() + mlState.nbBits()) & 31))
   140  			llState = llTable[(llState.newState()+lowBits)&maxTableMask]
   141  
   142  			lowBits = uint16(bits >> (ofState.nbBits() & 31))
   143  			lowBits &= bitMask[mlState.nbBits()&15]
   144  			mlState = mlTable[(mlState.newState()+lowBits)&maxTableMask]
   145  
   146  			lowBits = uint16(bits) & bitMask[ofState.nbBits()&15]
   147  			ofState = ofTable[(ofState.newState()+lowBits)&maxTableMask]
   148  		}
   149  	}
   150  	s.seqSize += litRemain
   151  	if s.seqSize > maxBlockSize {
   152  		return fmt.Errorf("output bigger than max block size (%d)", maxBlockSize)
   153  	}
   154  	err := br.close()
   155  	if err != nil {
   156  		printf("Closing sequences: %v, %+v\n", err, *br)
   157  	}
   158  	return err
   159  }
   160  
   161  // executeSimple handles cases when a dictionary is not used.
   162  func (s *sequenceDecs) executeSimple(seqs []seqVals, hist []byte) error {
   163  	// Ensure we have enough output size...
   164  	if len(s.out)+s.seqSize > cap(s.out) {
   165  		addBytes := s.seqSize + len(s.out)
   166  		s.out = append(s.out, make([]byte, addBytes)...)
   167  		s.out = s.out[:len(s.out)-addBytes]
   168  	}
   169  
   170  	if debugDecoder {
   171  		printf("Execute %d seqs with literals: %d into %d bytes\n", len(seqs), len(s.literals), s.seqSize)
   172  	}
   173  
   174  	var t = len(s.out)
   175  	out := s.out[:t+s.seqSize]
   176  
   177  	for _, seq := range seqs {
   178  		// Add literals
   179  		copy(out[t:], s.literals[:seq.ll])
   180  		t += seq.ll
   181  		s.literals = s.literals[seq.ll:]
   182  
   183  		// Malformed input
   184  		if seq.mo > t+len(hist) || seq.mo > s.windowSize {
   185  			return fmt.Errorf("match offset (%d) bigger than current history (%d)", seq.mo, t+len(hist))
   186  		}
   187  
   188  		// Copy from history.
   189  		if v := seq.mo - t; v > 0 {
   190  			// v is the start position in history from end.
   191  			start := len(hist) - v
   192  			if seq.ml > v {
   193  				// Some goes into the current block.
   194  				// Copy remainder of history
   195  				copy(out[t:], hist[start:])
   196  				t += v
   197  				seq.ml -= v
   198  			} else {
   199  				copy(out[t:], hist[start:start+seq.ml])
   200  				t += seq.ml
   201  				continue
   202  			}
   203  		}
   204  
   205  		// We must be in the current buffer now
   206  		if seq.ml > 0 {
   207  			start := t - seq.mo
   208  			if seq.ml <= t-start {
   209  				// No overlap
   210  				copy(out[t:], out[start:start+seq.ml])
   211  				t += seq.ml
   212  			} else {
   213  				// Overlapping copy
   214  				// Extend destination slice and copy one byte at the time.
   215  				src := out[start : start+seq.ml]
   216  				dst := out[t:]
   217  				dst = dst[:len(src)]
   218  				t += len(src)
   219  				// Destination is the space we just added.
   220  				for i := range src {
   221  					dst[i] = src[i]
   222  				}
   223  			}
   224  		}
   225  	}
   226  	// Add final literals
   227  	copy(out[t:], s.literals)
   228  	if debugDecoder {
   229  		t += len(s.literals)
   230  		if t != len(out) {
   231  			panic(fmt.Errorf("length mismatch, want %d, got %d, ss: %d", len(out), t, s.seqSize))
   232  		}
   233  	}
   234  	s.out = out
   235  
   236  	return nil
   237  }
   238
View as plain text