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