1 | /* |
2 | Copyright (c) 2015-2016, Apple Inc. All rights reserved. |
3 | |
4 | Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: |
5 | |
6 | 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. |
7 | |
8 | 2. 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 | |
11 | 3. 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 | |
14 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
15 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE |
16 | COPYRIGHT 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) |
18 | HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
19 | ARISING 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. |
31 | void 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. |
57 | int 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. |
109 | void 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. |
150 | static 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]. |
167 | void 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 | |