cubefs

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
}
77

78
// initialize all 3 decoders from the stream input.
79
func (s *sequenceDecs) initialize(br *bitReader, hist *history, out []byte) error {
80
	if err := s.litLengths.init(br); err != nil {
81
		return errors.New("litLengths:" + err.Error())
82
	}
83
	if err := s.offsets.init(br); err != nil {
84
		return errors.New("offsets:" + err.Error())
85
	}
86
	if err := s.matchLengths.init(br); err != nil {
87
		return errors.New("matchLengths:" + err.Error())
88
	}
89
	s.br = br
90
	s.prevOffset = hist.recentOffsets
91
	s.maxBits = s.litLengths.fse.maxBits + s.offsets.fse.maxBits + s.matchLengths.fse.maxBits
92
	s.windowSize = hist.windowSize
93
	s.out = out
94
	s.dict = nil
95
	if hist.dict != nil {
96
		s.dict = hist.dict.content
97
	}
98
	return nil
99
}
100

101
// decode sequences from the stream with the provided history.
102
func (s *sequenceDecs) decode(seqs []seqVals) error {
103
	br := s.br
104

105
	// Grab full sizes tables, to avoid bounds checks.
106
	llTable, mlTable, ofTable := s.litLengths.fse.dt[:maxTablesize], s.matchLengths.fse.dt[:maxTablesize], s.offsets.fse.dt[:maxTablesize]
107
	llState, mlState, ofState := s.litLengths.state.state, s.matchLengths.state.state, s.offsets.state.state
108
	s.seqSize = 0
109
	litRemain := len(s.literals)
110

111
	for i := range seqs {
112
		var ll, mo, ml int
113
		if br.off > 4+((maxOffsetBits+16+16)>>3) {
114
			// inlined function:
115
			// ll, mo, ml = s.nextFast(br, llState, mlState, ofState)
116

117
			// Final will not read from stream.
118
			var llB, mlB, moB uint8
119
			ll, llB = llState.final()
120
			ml, mlB = mlState.final()
121
			mo, moB = ofState.final()
122

123
			// extra bits are stored in reverse order.
124
			br.fillFast()
125
			mo += br.getBits(moB)
126
			if s.maxBits > 32 {
127
				br.fillFast()
128
			}
129
			ml += br.getBits(mlB)
130
			ll += br.getBits(llB)
131

132
			if moB > 1 {
133
				s.prevOffset[2] = s.prevOffset[1]
134
				s.prevOffset[1] = s.prevOffset[0]
135
				s.prevOffset[0] = mo
136
			} else {
137
				// mo = s.adjustOffset(mo, ll, moB)
138
				// Inlined for rather big speedup
139
				if ll == 0 {
140
					// There is an exception though, when current sequence's literals_length = 0.
141
					// In this case, repeated offsets are shifted by one, so an offset_value of 1 means Repeated_Offset2,
142
					// an offset_value of 2 means Repeated_Offset3, and an offset_value of 3 means Repeated_Offset1 - 1_byte.
143
					mo++
144
				}
145

146
				if mo == 0 {
147
					mo = s.prevOffset[0]
148
				} else {
149
					var temp int
150
					if mo == 3 {
151
						temp = s.prevOffset[0] - 1
152
					} else {
153
						temp = s.prevOffset[mo]
154
					}
155

156
					if temp == 0 {
157
						// 0 is not valid; input is corrupted; force offset to 1
158
						println("WARNING: temp was 0")
159
						temp = 1
160
					}
161

162
					if mo != 1 {
163
						s.prevOffset[2] = s.prevOffset[1]
164
					}
165
					s.prevOffset[1] = s.prevOffset[0]
166
					s.prevOffset[0] = temp
167
					mo = temp
168
				}
169
			}
170
			br.fillFast()
171
		} else {
172
			if br.overread() {
173
				if debugDecoder {
174
					printf("reading sequence %d, exceeded available data\n", i)
175
				}
176
				return io.ErrUnexpectedEOF
177
			}
178
			ll, mo, ml = s.next(br, llState, mlState, ofState)
179
			br.fill()
180
		}
181

182
		if debugSequences {
183
			println("Seq", i, "Litlen:", ll, "mo:", mo, "(abs) ml:", ml)
184
		}
185
		// Evaluate.
186
		// We might be doing this async, so do it early.
187
		if mo == 0 && ml > 0 {
188
			return fmt.Errorf("zero matchoff and matchlen (%d) > 0", ml)
189
		}
190
		if ml > maxMatchLen {
191
			return fmt.Errorf("match len (%d) bigger than max allowed length", ml)
192
		}
193
		s.seqSize += ll + ml
194
		if s.seqSize > maxBlockSize {
195
			return fmt.Errorf("output (%d) bigger than max block size", s.seqSize)
196
		}
197
		litRemain -= ll
198
		if litRemain < 0 {
199
			return fmt.Errorf("unexpected literal count, want %d bytes, but only %d is available", ll, litRemain+ll)
200
		}
201
		seqs[i] = seqVals{
202
			ll: ll,
203
			ml: ml,
204
			mo: mo,
205
		}
206
		if i == len(seqs)-1 {
207
			// This is the last sequence, so we shouldn't update state.
208
			break
209
		}
210

211
		// Manually inlined, ~ 5-20% faster
212
		// Update all 3 states at once. Approx 20% faster.
213
		nBits := llState.nbBits() + mlState.nbBits() + ofState.nbBits()
214
		if nBits == 0 {
215
			llState = llTable[llState.newState()&maxTableMask]
216
			mlState = mlTable[mlState.newState()&maxTableMask]
217
			ofState = ofTable[ofState.newState()&maxTableMask]
218
		} else {
219
			bits := br.get32BitsFast(nBits)
220
			lowBits := uint16(bits >> ((ofState.nbBits() + mlState.nbBits()) & 31))
221
			llState = llTable[(llState.newState()+lowBits)&maxTableMask]
222

223
			lowBits = uint16(bits >> (ofState.nbBits() & 31))
224
			lowBits &= bitMask[mlState.nbBits()&15]
225
			mlState = mlTable[(mlState.newState()+lowBits)&maxTableMask]
226

227
			lowBits = uint16(bits) & bitMask[ofState.nbBits()&15]
228
			ofState = ofTable[(ofState.newState()+lowBits)&maxTableMask]
229
		}
230
	}
231
	s.seqSize += litRemain
232
	if s.seqSize > maxBlockSize {
233
		return fmt.Errorf("output (%d) bigger than max block size", s.seqSize)
234
	}
235
	err := br.close()
236
	if err != nil {
237
		printf("Closing sequences: %v, %+v\n", err, *br)
238
	}
239
	return err
240
}
241

242
// execute will execute the decoded sequence with the provided history.
243
// The sequence must be evaluated before being sent.
244
func (s *sequenceDecs) execute(seqs []seqVals, hist []byte) error {
245
	// Ensure we have enough output size...
246
	if len(s.out)+s.seqSize > cap(s.out) {
247
		addBytes := s.seqSize + len(s.out)
248
		s.out = append(s.out, make([]byte, addBytes)...)
249
		s.out = s.out[:len(s.out)-addBytes]
250
	}
251

252
	if debugDecoder {
253
		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)
254
	}
255

256
	var t = len(s.out)
257
	out := s.out[:t+s.seqSize]
258

259
	for _, seq := range seqs {
260
		// Add literals
261
		copy(out[t:], s.literals[:seq.ll])
262
		t += seq.ll
263
		s.literals = s.literals[seq.ll:]
264

265
		// Copy from dictionary...
266
		if seq.mo > t+len(hist) || seq.mo > s.windowSize {
267
			if len(s.dict) == 0 {
268
				return fmt.Errorf("match offset (%d) bigger than current history (%d)", seq.mo, t+len(hist))
269
			}
270

271
			// we may be in dictionary.
272
			dictO := len(s.dict) - (seq.mo - (t + len(hist)))
273
			if dictO < 0 || dictO >= len(s.dict) {
274
				return fmt.Errorf("match offset (%d) bigger than current history+dict (%d)", seq.mo, t+len(hist)+len(s.dict))
275
			}
276
			end := dictO + seq.ml
277
			if end > len(s.dict) {
278
				n := len(s.dict) - dictO
279
				copy(out[t:], s.dict[dictO:])
280
				t += n
281
				seq.ml -= n
282
			} else {
283
				copy(out[t:], s.dict[dictO:end])
284
				t += end - dictO
285
				continue
286
			}
287
		}
288

289
		// Copy from history.
290
		if v := seq.mo - t; v > 0 {
291
			// v is the start position in history from end.
292
			start := len(hist) - v
293
			if seq.ml > v {
294
				// Some goes into current block.
295
				// Copy remainder of history
296
				copy(out[t:], hist[start:])
297
				t += v
298
				seq.ml -= v
299
			} else {
300
				copy(out[t:], hist[start:start+seq.ml])
301
				t += seq.ml
302
				continue
303
			}
304
		}
305
		// We must be in current buffer now
306
		if seq.ml > 0 {
307
			start := t - seq.mo
308
			if seq.ml <= t-start {
309
				// No overlap
310
				copy(out[t:], out[start:start+seq.ml])
311
				t += seq.ml
312
				continue
313
			} else {
314
				// Overlapping copy
315
				// Extend destination slice and copy one byte at the time.
316
				src := out[start : start+seq.ml]
317
				dst := out[t:]
318
				dst = dst[:len(src)]
319
				t += len(src)
320
				// Destination is the space we just added.
321
				for i := range src {
322
					dst[i] = src[i]
323
				}
324
			}
325
		}
326
	}
327
	// Add final literals
328
	copy(out[t:], s.literals)
329
	if debugDecoder {
330
		t += len(s.literals)
331
		if t != len(out) {
332
			panic(fmt.Errorf("length mismatch, want %d, got %d, ss: %d", len(out), t, s.seqSize))
333
		}
334
	}
335
	s.out = out
336

337
	return nil
338
}
339

340
// decode sequences from the stream with the provided history.
341
func (s *sequenceDecs) decodeSync(history *history) error {
342
	br := s.br
343
	seqs := s.nSeqs
344
	startSize := len(s.out)
345
	// Grab full sizes tables, to avoid bounds checks.
346
	llTable, mlTable, ofTable := s.litLengths.fse.dt[:maxTablesize], s.matchLengths.fse.dt[:maxTablesize], s.offsets.fse.dt[:maxTablesize]
347
	llState, mlState, ofState := s.litLengths.state.state, s.matchLengths.state.state, s.offsets.state.state
348
	hist := history.b[history.ignoreBuffer:]
349
	out := s.out
350

351
	for i := seqs - 1; i >= 0; i-- {
352
		if br.overread() {
353
			printf("reading sequence %d, exceeded available data\n", seqs-i)
354
			return io.ErrUnexpectedEOF
355
		}
356
		var ll, mo, ml int
357
		if br.off > 4+((maxOffsetBits+16+16)>>3) {
358
			// inlined function:
359
			// ll, mo, ml = s.nextFast(br, llState, mlState, ofState)
360

361
			// Final will not read from stream.
362
			var llB, mlB, moB uint8
363
			ll, llB = llState.final()
364
			ml, mlB = mlState.final()
365
			mo, moB = ofState.final()
366

367
			// extra bits are stored in reverse order.
368
			br.fillFast()
369
			mo += br.getBits(moB)
370
			if s.maxBits > 32 {
371
				br.fillFast()
372
			}
373
			ml += br.getBits(mlB)
374
			ll += br.getBits(llB)
375

376
			if moB > 1 {
377
				s.prevOffset[2] = s.prevOffset[1]
378
				s.prevOffset[1] = s.prevOffset[0]
379
				s.prevOffset[0] = mo
380
			} else {
381
				// mo = s.adjustOffset(mo, ll, moB)
382
				// Inlined for rather big speedup
383
				if ll == 0 {
384
					// There is an exception though, when current sequence's literals_length = 0.
385
					// In this case, repeated offsets are shifted by one, so an offset_value of 1 means Repeated_Offset2,
386
					// an offset_value of 2 means Repeated_Offset3, and an offset_value of 3 means Repeated_Offset1 - 1_byte.
387
					mo++
388
				}
389

390
				if mo == 0 {
391
					mo = s.prevOffset[0]
392
				} else {
393
					var temp int
394
					if mo == 3 {
395
						temp = s.prevOffset[0] - 1
396
					} else {
397
						temp = s.prevOffset[mo]
398
					}
399

400
					if temp == 0 {
401
						// 0 is not valid; input is corrupted; force offset to 1
402
						println("WARNING: temp was 0")
403
						temp = 1
404
					}
405

406
					if mo != 1 {
407
						s.prevOffset[2] = s.prevOffset[1]
408
					}
409
					s.prevOffset[1] = s.prevOffset[0]
410
					s.prevOffset[0] = temp
411
					mo = temp
412
				}
413
			}
414
			br.fillFast()
415
		} else {
416
			ll, mo, ml = s.next(br, llState, mlState, ofState)
417
			br.fill()
418
		}
419

420
		if debugSequences {
421
			println("Seq", seqs-i-1, "Litlen:", ll, "mo:", mo, "(abs) ml:", ml)
422
		}
423

424
		if ll > len(s.literals) {
425
			return fmt.Errorf("unexpected literal count, want %d bytes, but only %d is available", ll, len(s.literals))
426
		}
427
		size := ll + ml + len(out)
428
		if size-startSize > maxBlockSize {
429
			return fmt.Errorf("output (%d) bigger than max block size", size)
430
		}
431
		if size > cap(out) {
432
			// Not enough size, which can happen under high volume block streaming conditions
433
			// but could be if destination slice is too small for sync operations.
434
			// over-allocating here can create a large amount of GC pressure so we try to keep
435
			// it as contained as possible
436
			used := len(out) - startSize
437
			addBytes := 256 + ll + ml + used>>2
438
			// Clamp to max block size.
439
			if used+addBytes > maxBlockSize {
440
				addBytes = maxBlockSize - used
441
			}
442
			out = append(out, make([]byte, addBytes)...)
443
			out = out[:len(out)-addBytes]
444
		}
445
		if ml > maxMatchLen {
446
			return fmt.Errorf("match len (%d) bigger than max allowed length", ml)
447
		}
448

449
		// Add literals
450
		out = append(out, s.literals[:ll]...)
451
		s.literals = s.literals[ll:]
452

453
		if mo == 0 && ml > 0 {
454
			return fmt.Errorf("zero matchoff and matchlen (%d) > 0", ml)
455
		}
456

457
		if mo > len(out)+len(hist) || mo > s.windowSize {
458
			if len(s.dict) == 0 {
459
				return fmt.Errorf("match offset (%d) bigger than current history (%d)", mo, len(out)+len(hist))
460
			}
461

462
			// we may be in dictionary.
463
			dictO := len(s.dict) - (mo - (len(out) + len(hist)))
464
			if dictO < 0 || dictO >= len(s.dict) {
465
				return fmt.Errorf("match offset (%d) bigger than current history (%d)", mo, len(out)+len(hist))
466
			}
467
			end := dictO + ml
468
			if end > len(s.dict) {
469
				out = append(out, s.dict[dictO:]...)
470
				ml -= len(s.dict) - dictO
471
			} else {
472
				out = append(out, s.dict[dictO:end]...)
473
				mo = 0
474
				ml = 0
475
			}
476
		}
477

478
		// Copy from history.
479
		// TODO: Blocks without history could be made to ignore this completely.
480
		if v := mo - len(out); v > 0 {
481
			// v is the start position in history from end.
482
			start := len(hist) - v
483
			if ml > v {
484
				// Some goes into current block.
485
				// Copy remainder of history
486
				out = append(out, hist[start:]...)
487
				ml -= v
488
			} else {
489
				out = append(out, hist[start:start+ml]...)
490
				ml = 0
491
			}
492
		}
493
		// We must be in current buffer now
494
		if ml > 0 {
495
			start := len(out) - mo
496
			if ml <= len(out)-start {
497
				// No overlap
498
				out = append(out, out[start:start+ml]...)
499
			} else {
500
				// Overlapping copy
501
				// Extend destination slice and copy one byte at the time.
502
				out = out[:len(out)+ml]
503
				src := out[start : start+ml]
504
				// Destination is the space we just added.
505
				dst := out[len(out)-ml:]
506
				dst = dst[:len(src)]
507
				for i := range src {
508
					dst[i] = src[i]
509
				}
510
			}
511
		}
512
		if i == 0 {
513
			// This is the last sequence, so we shouldn't update state.
514
			break
515
		}
516

517
		// Manually inlined, ~ 5-20% faster
518
		// Update all 3 states at once. Approx 20% faster.
519
		nBits := llState.nbBits() + mlState.nbBits() + ofState.nbBits()
520
		if nBits == 0 {
521
			llState = llTable[llState.newState()&maxTableMask]
522
			mlState = mlTable[mlState.newState()&maxTableMask]
523
			ofState = ofTable[ofState.newState()&maxTableMask]
524
		} else {
525
			bits := br.get32BitsFast(nBits)
526
			lowBits := uint16(bits >> ((ofState.nbBits() + mlState.nbBits()) & 31))
527
			llState = llTable[(llState.newState()+lowBits)&maxTableMask]
528

529
			lowBits = uint16(bits >> (ofState.nbBits() & 31))
530
			lowBits &= bitMask[mlState.nbBits()&15]
531
			mlState = mlTable[(mlState.newState()+lowBits)&maxTableMask]
532

533
			lowBits = uint16(bits) & bitMask[ofState.nbBits()&15]
534
			ofState = ofTable[(ofState.newState()+lowBits)&maxTableMask]
535
		}
536
	}
537

538
	// Add final literals
539
	s.out = append(out, s.literals...)
540
	return br.close()
541
}
542

543
// update states, at least 27 bits must be available.
544
func (s *sequenceDecs) update(br *bitReader) {
545
	// Max 8 bits
546
	s.litLengths.state.next(br)
547
	// Max 9 bits
548
	s.matchLengths.state.next(br)
549
	// Max 8 bits
550
	s.offsets.state.next(br)
551
}
552

553
var bitMask [16]uint16
554

555
func init() {
556
	for i := range bitMask[:] {
557
		bitMask[i] = uint16((1 << uint(i)) - 1)
558
	}
559
}
560

561
// update states, at least 27 bits must be available.
562
func (s *sequenceDecs) updateAlt(br *bitReader) {
563
	// Update all 3 states at once. Approx 20% faster.
564
	a, b, c := s.litLengths.state.state, s.matchLengths.state.state, s.offsets.state.state
565

566
	nBits := a.nbBits() + b.nbBits() + c.nbBits()
567
	if nBits == 0 {
568
		s.litLengths.state.state = s.litLengths.state.dt[a.newState()]
569
		s.matchLengths.state.state = s.matchLengths.state.dt[b.newState()]
570
		s.offsets.state.state = s.offsets.state.dt[c.newState()]
571
		return
572
	}
573
	bits := br.get32BitsFast(nBits)
574
	lowBits := uint16(bits >> ((c.nbBits() + b.nbBits()) & 31))
575
	s.litLengths.state.state = s.litLengths.state.dt[a.newState()+lowBits]
576

577
	lowBits = uint16(bits >> (c.nbBits() & 31))
578
	lowBits &= bitMask[b.nbBits()&15]
579
	s.matchLengths.state.state = s.matchLengths.state.dt[b.newState()+lowBits]
580

581
	lowBits = uint16(bits) & bitMask[c.nbBits()&15]
582
	s.offsets.state.state = s.offsets.state.dt[c.newState()+lowBits]
583
}
584

585
// nextFast will return new states when there are at least 4 unused bytes left on the stream when done.
586
func (s *sequenceDecs) nextFast(br *bitReader, llState, mlState, ofState decSymbol) (ll, mo, ml int) {
587
	// Final will not read from stream.
588
	ll, llB := llState.final()
589
	ml, mlB := mlState.final()
590
	mo, moB := ofState.final()
591

592
	// extra bits are stored in reverse order.
593
	br.fillFast()
594
	mo += br.getBits(moB)
595
	if s.maxBits > 32 {
596
		br.fillFast()
597
	}
598
	ml += br.getBits(mlB)
599
	ll += br.getBits(llB)
600

601
	if moB > 1 {
602
		s.prevOffset[2] = s.prevOffset[1]
603
		s.prevOffset[1] = s.prevOffset[0]
604
		s.prevOffset[0] = mo
605
		return
606
	}
607
	// mo = s.adjustOffset(mo, ll, moB)
608
	// Inlined for rather big speedup
609
	if ll == 0 {
610
		// There is an exception though, when current sequence's literals_length = 0.
611
		// In this case, repeated offsets are shifted by one, so an offset_value of 1 means Repeated_Offset2,
612
		// an offset_value of 2 means Repeated_Offset3, and an offset_value of 3 means Repeated_Offset1 - 1_byte.
613
		mo++
614
	}
615

616
	if mo == 0 {
617
		mo = s.prevOffset[0]
618
		return
619
	}
620
	var temp int
621
	if mo == 3 {
622
		temp = s.prevOffset[0] - 1
623
	} else {
624
		temp = s.prevOffset[mo]
625
	}
626

627
	if temp == 0 {
628
		// 0 is not valid; input is corrupted; force offset to 1
629
		println("temp was 0")
630
		temp = 1
631
	}
632

633
	if mo != 1 {
634
		s.prevOffset[2] = s.prevOffset[1]
635
	}
636
	s.prevOffset[1] = s.prevOffset[0]
637
	s.prevOffset[0] = temp
638
	mo = temp
639
	return
640
}
641

642
func (s *sequenceDecs) next(br *bitReader, llState, mlState, ofState decSymbol) (ll, mo, ml int) {
643
	// Final will not read from stream.
644
	ll, llB := llState.final()
645
	ml, mlB := mlState.final()
646
	mo, moB := ofState.final()
647

648
	// extra bits are stored in reverse order.
649
	br.fill()
650
	if s.maxBits <= 32 {
651
		mo += br.getBits(moB)
652
		ml += br.getBits(mlB)
653
		ll += br.getBits(llB)
654
	} else {
655
		mo += br.getBits(moB)
656
		br.fill()
657
		// matchlength+literal length, max 32 bits
658
		ml += br.getBits(mlB)
659
		ll += br.getBits(llB)
660

661
	}
662
	mo = s.adjustOffset(mo, ll, moB)
663
	return
664
}
665

666
func (s *sequenceDecs) adjustOffset(offset, litLen int, offsetB uint8) int {
667
	if offsetB > 1 {
668
		s.prevOffset[2] = s.prevOffset[1]
669
		s.prevOffset[1] = s.prevOffset[0]
670
		s.prevOffset[0] = offset
671
		return offset
672
	}
673

674
	if litLen == 0 {
675
		// There is an exception though, when current sequence's literals_length = 0.
676
		// In this case, repeated offsets are shifted by one, so an offset_value of 1 means Repeated_Offset2,
677
		// an offset_value of 2 means Repeated_Offset3, and an offset_value of 3 means Repeated_Offset1 - 1_byte.
678
		offset++
679
	}
680

681
	if offset == 0 {
682
		return s.prevOffset[0]
683
	}
684
	var temp int
685
	if offset == 3 {
686
		temp = s.prevOffset[0] - 1
687
	} else {
688
		temp = s.prevOffset[offset]
689
	}
690

691
	if temp == 0 {
692
		// 0 is not valid; input is corrupted; force offset to 1
693
		println("temp was 0")
694
		temp = 1
695
	}
696

697
	if offset != 1 {
698
		s.prevOffset[2] = s.prevOffset[1]
699
	}
700
	s.prevOffset[1] = s.prevOffset[0]
701
	s.prevOffset[0] = temp
702
	return temp
703
}
704