1/*
2Copyright (c) 2015-2016, Apple Inc. All rights reserved.
3
4Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
5
61. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
7
82. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer
9 in the documentation and/or other materials provided with the distribution.
10
113. Neither the name of the copyright holder(s) nor the names of any contributors may be used to endorse or promote products derived
12 from this software without specific prior written permission.
13
14THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
15LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
16COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
17(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
18HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
19ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
20*/
21
22#include "lzfse_internal.h"
23
24// Initialize encoder table T[NSYMBOLS].
25// NSTATES = sum FREQ[i] is the number of states (a power of 2)
26// NSYMBOLS is the number of symbols.
27// FREQ[NSYMBOLS] is a normalized histogram of symbol frequencies, with FREQ[i]
28// >= 0.
29// Some symbols may have a 0 frequency. In that case, they should not be
30// present in the data.
31void fse_init_encoder_table(int nstates, int nsymbols,
32 const uint16_t *__restrict freq,
33 fse_encoder_entry *__restrict t) {
34 int offset = 0; // current offset
35 int n_clz = __builtin_clz(nstates);
36 for (int i = 0; i < nsymbols; i++) {
37 int f = (int)freq[i];
38 if (f == 0)
39 continue; // skip this symbol, no occurrences
40 int k =
41 __builtin_clz(f) - n_clz; // shift needed to ensure N <= (F<<K) < 2*N
42 t[i].s0 = (int16_t)((f << k) - nstates);
43 t[i].k = (int16_t)k;
44 t[i].delta0 = (int16_t)(offset - f + (nstates >> k));
45 t[i].delta1 = (int16_t)(offset - f + (nstates >> (k - 1)));
46 offset += f;
47 }
48}
49
50// Initialize decoder table T[NSTATES].
51// NSTATES = sum FREQ[i] is the number of states (a power of 2)
52// NSYMBOLS is the number of symbols.
53// FREQ[NSYMBOLS] is a normalized histogram of symbol frequencies, with FREQ[i]
54// >= 0.
55// Some symbols may have a 0 frequency. In that case, they should not be
56// present in the data.
57int fse_init_decoder_table(int nstates, int nsymbols,
58 const uint16_t *__restrict freq,
59 int32_t *__restrict t) {
60 assert(nsymbols <= 256);
61 assert(fse_check_freq(freq, nsymbols, nstates) == 0);
62 int n_clz = __builtin_clz(nstates);
63 int sum_of_freq = 0;
64 for (int i = 0; i < nsymbols; i++) {
65 int f = (int)freq[i];
66 if (f == 0)
67 continue; // skip this symbol, no occurrences
68
69 sum_of_freq += f;
70
71 if (sum_of_freq > nstates) {
72 return -1;
73 }
74
75 int k =
76 __builtin_clz(f) - n_clz; // shift needed to ensure N <= (F<<K) < 2*N
77 int j0 = ((2 * nstates) >> k) - f;
78
79 // Initialize all states S reached by this symbol: OFFSET <= S < OFFSET + F
80 for (int j = 0; j < f; j++) {
81 fse_decoder_entry e;
82
83 e.symbol = (uint8_t)i;
84 if (j < j0) {
85 e.k = (int8_t)k;
86 e.delta = (int16_t)(((f + j) << k) - nstates);
87 } else {
88 e.k = (int8_t)(k - 1);
89 e.delta = (int16_t)((j - j0) << (k - 1));
90 }
91
92 memcpy(t, &e, sizeof(e));
93 t++;
94 }
95 }
96
97 return 0; // OK
98}
99
100// Initialize value decoder table T[NSTATES].
101// NSTATES = sum FREQ[i] is the number of states (a power of 2)
102// NSYMBOLS is the number of symbols.
103// FREQ[NSYMBOLS] is a normalized histogram of symbol frequencies, with FREQ[i]
104// >= 0.
105// SYMBOL_VBITS[NSYMBOLS] and SYMBOLS_VBASE[NSYMBOLS] are the number of value
106// bits to read and the base value for each symbol.
107// Some symbols may have a 0 frequency. In that case, they should not be
108// present in the data.
109void fse_init_value_decoder_table(int nstates, int nsymbols,
110 const uint16_t *__restrict freq,
111 const uint8_t *__restrict symbol_vbits,
112 const int32_t *__restrict symbol_vbase,
113 fse_value_decoder_entry *__restrict t) {
114 assert(nsymbols <= 256);
115 assert(fse_check_freq(freq, nsymbols, nstates) == 0);
116
117 int n_clz = __builtin_clz(nstates);
118 for (int i = 0; i < nsymbols; i++) {
119 int f = (int)freq[i];
120 if (f == 0)
121 continue; // skip this symbol, no occurrences
122
123 int k =
124 __builtin_clz(f) - n_clz; // shift needed to ensure N <= (F<<K) < 2*N
125 int j0 = ((2 * nstates) >> k) - f;
126
127 fse_value_decoder_entry ei = {0};
128 ei.value_bits = symbol_vbits[i];
129 ei.vbase = symbol_vbase[i];
130
131 // Initialize all states S reached by this symbol: OFFSET <= S < OFFSET + F
132 for (int j = 0; j < f; j++) {
133 fse_value_decoder_entry e = ei;
134
135 if (j < j0) {
136 e.total_bits = (uint8_t)k + e.value_bits;
137 e.delta = (int16_t)(((f + j) << k) - nstates);
138 } else {
139 e.total_bits = (uint8_t)(k - 1) + e.value_bits;
140 e.delta = (int16_t)((j - j0) << (k - 1));
141 }
142
143 memcpy(t, &e, 8);
144 t++;
145 }
146 }
147}
148
149// Remove states from symbols until the correct number of states is used.
150static void fse_adjust_freqs(uint16_t *freq, int overrun, int nsymbols) {
151 for (int shift = 3; overrun != 0; shift--) {
152 for (int sym = 0; sym < nsymbols; sym++) {
153 if (freq[sym] > 1) {
154 int n = (freq[sym] - 1) >> shift;
155 if (n > overrun)
156 n = overrun;
157 freq[sym] -= n;
158 overrun -= n;
159 if (overrun == 0)
160 break;
161 }
162 }
163 }
164}
165
166// Normalize a table T[NSYMBOLS] of occurrences to FREQ[NSYMBOLS].
167void fse_normalize_freq(int nstates, int nsymbols, const uint32_t *__restrict t,
168 uint16_t *__restrict freq) {
169 uint32_t s_count = 0;
170 int remaining = nstates; // must be signed; this may become < 0
171 int max_freq = 0;
172 int max_freq_sym = 0;
173 int shift = __builtin_clz(nstates) - 1;
174 uint32_t highprec_step;
175
176 // Compute the total number of symbol occurrences
177 for (int i = 0; i < nsymbols; i++)
178 s_count += t[i];
179
180 if (s_count == 0)
181 highprec_step = 0; // no symbols used
182 else
183 highprec_step = ((uint32_t)1 << 31) / s_count;
184
185 for (int i = 0; i < nsymbols; i++) {
186
187 // Rescale the occurrence count to get the normalized frequency.
188 // Round up if the fractional part is >= 0.5; otherwise round down.
189 // For efficiency, we do this calculation using integer arithmetic.
190 int f = (((t[i] * highprec_step) >> shift) + 1) >> 1;
191
192 // If a symbol was used, it must be given a nonzero normalized frequency.
193 if (f == 0 && t[i] != 0)
194 f = 1;
195
196 freq[i] = f;
197 remaining -= f;
198
199 // Remember the maximum frequency and which symbol had it.
200 if (f > max_freq) {
201 max_freq = f;
202 max_freq_sym = i;
203 }
204 }
205
206 // If there remain states to be assigned, then just assign them to the most
207 // frequent symbol. Alternatively, if we assigned more states than were
208 // actually available, then either remove states from the most frequent symbol
209 // (for minor overruns) or use the slower adjustment algorithm (for major
210 // overruns).
211 if (-remaining < (max_freq >> 2)) {
212 freq[max_freq_sym] += remaining;
213 } else {
214 fse_adjust_freqs(freq, -remaining, nsymbols);
215 }
216}
217