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
5package zstd
6
7import "math/bits"
8
9type seqCoders struct {
10	llEnc, ofEnc, mlEnc    *fseEncoder
11	llPrev, ofPrev, mlPrev *fseEncoder
12}
13
14// swap coders with another (block).
15func (s *seqCoders) swap(other *seqCoders) {
16	*s, *other = *other, *s
17}
18
19// setPrev will update the previous encoders to the actually used ones
20// and make sure a fresh one is in the main slot.
21func (s *seqCoders) setPrev(ll, ml, of *fseEncoder) {
22	compareSwap := func(used *fseEncoder, current, prev **fseEncoder) {
23		// We used the new one, more current to history and reuse the previous history
24		if *current == used {
25			*prev, *current = *current, *prev
26			c := *current
27			p := *prev
28			c.reUsed = false
29			p.reUsed = true
30			return
31		}
32		if used == *prev {
33			return
34		}
35		// Ensure we cannot reuse by accident
36		prevEnc := *prev
37		prevEnc.symbolLen = 0
38		return
39	}
40	compareSwap(ll, &s.llEnc, &s.llPrev)
41	compareSwap(ml, &s.mlEnc, &s.mlPrev)
42	compareSwap(of, &s.ofEnc, &s.ofPrev)
43}
44
45func highBit(val uint32) (n uint32) {
46	return uint32(bits.Len32(val) - 1)
47}
48
49var llCodeTable = [64]byte{0, 1, 2, 3, 4, 5, 6, 7,
50	8, 9, 10, 11, 12, 13, 14, 15,
51	16, 16, 17, 17, 18, 18, 19, 19,
52	20, 20, 20, 20, 21, 21, 21, 21,
53	22, 22, 22, 22, 22, 22, 22, 22,
54	23, 23, 23, 23, 23, 23, 23, 23,
55	24, 24, 24, 24, 24, 24, 24, 24,
56	24, 24, 24, 24, 24, 24, 24, 24}
57
58// Up to 6 bits
59const maxLLCode = 35
60
61// llBitsTable translates from ll code to number of bits.
62var llBitsTable = [maxLLCode + 1]byte{
63	0, 0, 0, 0, 0, 0, 0, 0,
64	0, 0, 0, 0, 0, 0, 0, 0,
65	1, 1, 1, 1, 2, 2, 3, 3,
66	4, 6, 7, 8, 9, 10, 11, 12,
67	13, 14, 15, 16}
68
69// llCode returns the code that represents the literal length requested.
70func llCode(litLength uint32) uint8 {
71	const llDeltaCode = 19
72	if litLength <= 63 {
73		// Compiler insists on bounds check (Go 1.12)
74		return llCodeTable[litLength&63]
75	}
76	return uint8(highBit(litLength)) + llDeltaCode
77}
78
79var mlCodeTable = [128]byte{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
80	16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
81	32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
82	38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
83	40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
84	41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
85	42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
86	42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42}
87
88// Up to 6 bits
89const maxMLCode = 52
90
91// mlBitsTable translates from ml code to number of bits.
92var mlBitsTable = [maxMLCode + 1]byte{
93	0, 0, 0, 0, 0, 0, 0, 0,
94	0, 0, 0, 0, 0, 0, 0, 0,
95	0, 0, 0, 0, 0, 0, 0, 0,
96	0, 0, 0, 0, 0, 0, 0, 0,
97	1, 1, 1, 1, 2, 2, 3, 3,
98	4, 4, 5, 7, 8, 9, 10, 11,
99	12, 13, 14, 15, 16}
100
101// note : mlBase = matchLength - MINMATCH;
102// because it's the format it's stored in seqStore->sequences
103func mlCode(mlBase uint32) uint8 {
104	const mlDeltaCode = 36
105	if mlBase <= 127 {
106		// Compiler insists on bounds check (Go 1.12)
107		return mlCodeTable[mlBase&127]
108	}
109	return uint8(highBit(mlBase)) + mlDeltaCode
110}
111
112func ofCode(offset uint32) uint8 {
113	// A valid offset will always be > 0.
114	return uint8(bits.Len32(offset) - 1)
115}
116