/src/aom/aom_dsp/entenc.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Copyright (c) 2001-2016, Alliance for Open Media. All rights reserved |
3 | | * |
4 | | * This source code is subject to the terms of the BSD 2 Clause License and |
5 | | * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License |
6 | | * was not distributed with this source code in the LICENSE file, you can |
7 | | * obtain it at www.aomedia.org/license/software. If the Alliance for Open |
8 | | * Media Patent License 1.0 was not distributed with this source code in the |
9 | | * PATENTS file, you can obtain it at www.aomedia.org/license/patent. |
10 | | */ |
11 | | |
12 | | #include <stdlib.h> |
13 | | #include <string.h> |
14 | | #include <math.h> |
15 | | #include <assert.h> |
16 | | #include "aom_dsp/entenc.h" |
17 | | #include "aom_dsp/prob.h" |
18 | | |
19 | | #if OD_MEASURE_EC_OVERHEAD |
20 | | #if !defined(M_LOG2E) |
21 | | #define M_LOG2E (1.4426950408889634073599246810019) |
22 | | #endif |
23 | | #define OD_LOG2(x) (M_LOG2E * log(x)) |
24 | | #endif // OD_MEASURE_EC_OVERHEAD |
25 | | |
26 | | /*A range encoder. |
27 | | See entdec.c and the references for implementation details \cite{Mar79,MNW98}. |
28 | | |
29 | | @INPROCEEDINGS{Mar79, |
30 | | author="Martin, G.N.N.", |
31 | | title="Range encoding: an algorithm for removing redundancy from a digitised |
32 | | message", |
33 | | booktitle="Video \& Data Recording Conference", |
34 | | year=1979, |
35 | | address="Southampton", |
36 | | month=Jul, |
37 | | URL="http://www.compressconsult.com/rangecoder/rngcod.pdf.gz" |
38 | | } |
39 | | @ARTICLE{MNW98, |
40 | | author="Alistair Moffat and Radford Neal and Ian H. Witten", |
41 | | title="Arithmetic Coding Revisited", |
42 | | journal="{ACM} Transactions on Information Systems", |
43 | | year=1998, |
44 | | volume=16, |
45 | | number=3, |
46 | | pages="256--294", |
47 | | month=Jul, |
48 | | URL="http://researchcommons.waikato.ac.nz/bitstream/handle/10289/78/content.pdf" |
49 | | }*/ |
50 | | |
51 | | /*Takes updated low and range values, renormalizes them so that |
52 | | 32768 <= rng < 65536 (flushing bytes from low to the pre-carry buffer if |
53 | | necessary), and stores them back in the encoder context. |
54 | | low: The new value of low. |
55 | | rng: The new value of the range.*/ |
56 | | static void od_ec_enc_normalize(od_ec_enc *enc, od_ec_window low, |
57 | 937k | unsigned rng) { |
58 | 937k | int d; |
59 | 937k | int c; |
60 | 937k | int s; |
61 | 937k | c = enc->cnt; |
62 | 937k | assert(rng <= 65535U); |
63 | | /*The number of leading zeros in the 16-bit binary representation of rng.*/ |
64 | 937k | d = 16 - OD_ILOG_NZ(rng); |
65 | 937k | s = c + d; |
66 | | /*TODO: Right now we flush every time we have at least one byte available. |
67 | | Instead we should use an od_ec_window and flush right before we're about to |
68 | | shift bits off the end of the window. |
69 | | For a 32-bit window this is about the same amount of work, but for a 64-bit |
70 | | window it should be a fair win.*/ |
71 | 937k | if (s >= 0) { |
72 | 21.6k | uint16_t *buf; |
73 | 21.6k | uint32_t storage; |
74 | 21.6k | uint32_t offs; |
75 | 21.6k | unsigned m; |
76 | 21.6k | buf = enc->precarry_buf; |
77 | 21.6k | storage = enc->precarry_storage; |
78 | 21.6k | offs = enc->offs; |
79 | 21.6k | if (offs + 2 > storage) { |
80 | 0 | storage = 2 * storage + 2; |
81 | 0 | buf = (uint16_t *)realloc(buf, sizeof(*buf) * storage); |
82 | 0 | if (buf == NULL) { |
83 | 0 | enc->error = -1; |
84 | 0 | enc->offs = 0; |
85 | 0 | return; |
86 | 0 | } |
87 | 0 | enc->precarry_buf = buf; |
88 | 0 | enc->precarry_storage = storage; |
89 | 0 | } |
90 | 21.6k | c += 16; |
91 | 21.6k | m = (1 << c) - 1; |
92 | 21.6k | if (s >= 8) { |
93 | 0 | assert(offs < storage); |
94 | 0 | buf[offs++] = (uint16_t)(low >> c); |
95 | 0 | low &= m; |
96 | 0 | c -= 8; |
97 | 0 | m >>= 8; |
98 | 0 | } |
99 | 21.6k | assert(offs < storage); |
100 | 21.6k | buf[offs++] = (uint16_t)(low >> c); |
101 | 21.6k | s = c + d - 24; |
102 | 21.6k | low &= m; |
103 | 21.6k | enc->offs = offs; |
104 | 21.6k | } |
105 | 937k | enc->low = low << d; |
106 | 937k | enc->rng = rng << d; |
107 | 937k | enc->cnt = s; |
108 | 937k | } |
109 | | |
110 | | /*Initializes the encoder. |
111 | | size: The initial size of the buffer, in bytes.*/ |
112 | 1.26k | void od_ec_enc_init(od_ec_enc *enc, uint32_t size) { |
113 | 1.26k | od_ec_enc_reset(enc); |
114 | 1.26k | enc->buf = (unsigned char *)malloc(sizeof(*enc->buf) * size); |
115 | 1.26k | enc->storage = size; |
116 | 1.26k | if (size > 0 && enc->buf == NULL) { |
117 | 0 | enc->storage = 0; |
118 | 0 | enc->error = -1; |
119 | 0 | } |
120 | 1.26k | enc->precarry_buf = (uint16_t *)malloc(sizeof(*enc->precarry_buf) * size); |
121 | 1.26k | enc->precarry_storage = size; |
122 | 1.26k | if (size > 0 && enc->precarry_buf == NULL) { |
123 | 0 | enc->precarry_storage = 0; |
124 | 0 | enc->error = -1; |
125 | 0 | } |
126 | 1.26k | } |
127 | | |
128 | | /*Reinitializes the encoder.*/ |
129 | 1.26k | void od_ec_enc_reset(od_ec_enc *enc) { |
130 | 1.26k | enc->offs = 0; |
131 | 1.26k | enc->low = 0; |
132 | 1.26k | enc->rng = 0x8000; |
133 | | /*This is initialized to -9 so that it crosses zero after we've accumulated |
134 | | one byte + one carry bit.*/ |
135 | 1.26k | enc->cnt = -9; |
136 | 1.26k | enc->error = 0; |
137 | | #if OD_MEASURE_EC_OVERHEAD |
138 | | enc->entropy = 0; |
139 | | enc->nb_symbols = 0; |
140 | | #endif |
141 | 1.26k | } |
142 | | |
143 | | /*Frees the buffers used by the encoder.*/ |
144 | 1.26k | void od_ec_enc_clear(od_ec_enc *enc) { |
145 | 1.26k | free(enc->precarry_buf); |
146 | 1.26k | free(enc->buf); |
147 | 1.26k | } |
148 | | |
149 | | /*Encodes a symbol given its frequency in Q15. |
150 | | fl: CDF_PROB_TOP minus the cumulative frequency of all symbols that come |
151 | | before the |
152 | | one to be encoded. |
153 | | fh: CDF_PROB_TOP minus the cumulative frequency of all symbols up to and |
154 | | including |
155 | | the one to be encoded.*/ |
156 | | static void od_ec_encode_q15(od_ec_enc *enc, unsigned fl, unsigned fh, int s, |
157 | 882k | int nsyms) { |
158 | 882k | od_ec_window l; |
159 | 882k | unsigned r; |
160 | 882k | unsigned u; |
161 | 882k | unsigned v; |
162 | 882k | l = enc->low; |
163 | 882k | r = enc->rng; |
164 | 882k | assert(32768U <= r); |
165 | 882k | assert(fh <= fl); |
166 | 882k | assert(fl <= 32768U); |
167 | 882k | assert(7 - EC_PROB_SHIFT - CDF_SHIFT >= 0); |
168 | 882k | const int N = nsyms - 1; |
169 | 882k | if (fl < CDF_PROB_TOP) { |
170 | 820k | u = ((r >> 8) * (uint32_t)(fl >> EC_PROB_SHIFT) >> |
171 | 820k | (7 - EC_PROB_SHIFT - CDF_SHIFT)) + |
172 | 820k | EC_MIN_PROB * (N - (s - 1)); |
173 | 820k | v = ((r >> 8) * (uint32_t)(fh >> EC_PROB_SHIFT) >> |
174 | 820k | (7 - EC_PROB_SHIFT - CDF_SHIFT)) + |
175 | 820k | EC_MIN_PROB * (N - (s + 0)); |
176 | 820k | l += r - u; |
177 | 820k | r = u - v; |
178 | 820k | } else { |
179 | 61.9k | r -= ((r >> 8) * (uint32_t)(fh >> EC_PROB_SHIFT) >> |
180 | 61.9k | (7 - EC_PROB_SHIFT - CDF_SHIFT)) + |
181 | 61.9k | EC_MIN_PROB * (N - (s + 0)); |
182 | 61.9k | } |
183 | 882k | od_ec_enc_normalize(enc, l, r); |
184 | | #if OD_MEASURE_EC_OVERHEAD |
185 | | enc->entropy -= OD_LOG2((double)(OD_ICDF(fh) - OD_ICDF(fl)) / CDF_PROB_TOP.); |
186 | | enc->nb_symbols++; |
187 | | #endif |
188 | 882k | } |
189 | | |
190 | | /*Encode a single binary value. |
191 | | val: The value to encode (0 or 1). |
192 | | f: The probability that the val is one, scaled by 32768.*/ |
193 | 54.4k | void od_ec_encode_bool_q15(od_ec_enc *enc, int val, unsigned f) { |
194 | 54.4k | od_ec_window l; |
195 | 54.4k | unsigned r; |
196 | 54.4k | unsigned v; |
197 | 54.4k | assert(0 < f); |
198 | 54.4k | assert(f < 32768U); |
199 | 54.4k | l = enc->low; |
200 | 54.4k | r = enc->rng; |
201 | 54.4k | assert(32768U <= r); |
202 | 54.4k | v = ((r >> 8) * (uint32_t)(f >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT)); |
203 | 54.4k | v += EC_MIN_PROB; |
204 | 54.4k | if (val) l += r - v; |
205 | 54.4k | r = val ? v : r - v; |
206 | 54.4k | od_ec_enc_normalize(enc, l, r); |
207 | | #if OD_MEASURE_EC_OVERHEAD |
208 | | enc->entropy -= OD_LOG2((double)(val ? f : (32768 - f)) / 32768.); |
209 | | enc->nb_symbols++; |
210 | | #endif |
211 | 54.4k | } |
212 | | |
213 | | /*Encodes a symbol given a cumulative distribution function (CDF) table in Q15. |
214 | | s: The index of the symbol to encode. |
215 | | icdf: 32768 minus the CDF, such that symbol s falls in the range |
216 | | [s > 0 ? (32768 - icdf[s - 1]) : 0, 32768 - icdf[s]). |
217 | | The values must be monotonically decreasing, and icdf[nsyms - 1] must |
218 | | be 0. |
219 | | nsyms: The number of symbols in the alphabet. |
220 | | This should be at most 16.*/ |
221 | | void od_ec_encode_cdf_q15(od_ec_enc *enc, int s, const uint16_t *icdf, |
222 | 882k | int nsyms) { |
223 | 882k | (void)nsyms; |
224 | 882k | assert(s >= 0); |
225 | 882k | assert(s < nsyms); |
226 | 882k | assert(icdf[nsyms - 1] == OD_ICDF(CDF_PROB_TOP)); |
227 | 882k | od_ec_encode_q15(enc, s > 0 ? icdf[s - 1] : OD_ICDF(0), icdf[s], s, nsyms); |
228 | 882k | } |
229 | | |
230 | | /*Overwrites a few bits at the very start of an existing stream, after they |
231 | | have already been encoded. |
232 | | This makes it possible to have a few flags up front, where it is easy for |
233 | | decoders to access them without parsing the whole stream, even if their |
234 | | values are not determined until late in the encoding process, without having |
235 | | to buffer all the intermediate symbols in the encoder. |
236 | | In order for this to work, at least nbits bits must have already been encoded |
237 | | using probabilities that are an exact power of two. |
238 | | The encoder can verify the number of encoded bits is sufficient, but cannot |
239 | | check this latter condition. |
240 | | val: The bits to encode (in the least nbits significant bits). |
241 | | They will be decoded in order from most-significant to least. |
242 | | nbits: The number of bits to overwrite. |
243 | | This must be no more than 8.*/ |
244 | 0 | void od_ec_enc_patch_initial_bits(od_ec_enc *enc, unsigned val, int nbits) { |
245 | 0 | int shift; |
246 | 0 | unsigned mask; |
247 | 0 | assert(nbits >= 0); |
248 | 0 | assert(nbits <= 8); |
249 | 0 | assert(val < 1U << nbits); |
250 | 0 | shift = 8 - nbits; |
251 | 0 | mask = ((1U << nbits) - 1) << shift; |
252 | 0 | if (enc->offs > 0) { |
253 | | /*The first byte has been finalized.*/ |
254 | 0 | enc->precarry_buf[0] = |
255 | 0 | (uint16_t)((enc->precarry_buf[0] & ~mask) | val << shift); |
256 | 0 | } else if (9 + enc->cnt + (enc->rng == 0x8000) > nbits) { |
257 | | /*The first byte has yet to be output.*/ |
258 | 0 | enc->low = (enc->low & ~((od_ec_window)mask << (16 + enc->cnt))) | |
259 | 0 | (od_ec_window)val << (16 + enc->cnt + shift); |
260 | 0 | } else { |
261 | | /*The encoder hasn't even encoded _nbits of data yet.*/ |
262 | 0 | enc->error = -1; |
263 | 0 | } |
264 | 0 | } |
265 | | |
266 | | #if OD_MEASURE_EC_OVERHEAD |
267 | | #include <stdio.h> |
268 | | #endif |
269 | | |
270 | | /*Indicates that there are no more symbols to encode. |
271 | | All remaining output bytes are flushed to the output buffer. |
272 | | od_ec_enc_reset() should be called before using the encoder again. |
273 | | bytes: Returns the size of the encoded data in the returned buffer. |
274 | | Return: A pointer to the start of the final buffer, or NULL if there was an |
275 | | encoding error.*/ |
276 | 1.26k | unsigned char *od_ec_enc_done(od_ec_enc *enc, uint32_t *nbytes) { |
277 | 1.26k | unsigned char *out; |
278 | 1.26k | uint32_t storage; |
279 | 1.26k | uint16_t *buf; |
280 | 1.26k | uint32_t offs; |
281 | 1.26k | od_ec_window m; |
282 | 1.26k | od_ec_window e; |
283 | 1.26k | od_ec_window l; |
284 | 1.26k | int c; |
285 | 1.26k | int s; |
286 | 1.26k | if (enc->error) return NULL; |
287 | | #if OD_MEASURE_EC_OVERHEAD |
288 | | { |
289 | | uint32_t tell; |
290 | | /* Don't count the 1 bit we lose to raw bits as overhead. */ |
291 | | tell = od_ec_enc_tell(enc) - 1; |
292 | | fprintf(stderr, "overhead: %f%%\n", |
293 | | 100 * (tell - enc->entropy) / enc->entropy); |
294 | | fprintf(stderr, "efficiency: %f bits/symbol\n", |
295 | | (double)tell / enc->nb_symbols); |
296 | | } |
297 | | #endif |
298 | | /*We output the minimum number of bits that ensures that the symbols encoded |
299 | | thus far will be decoded correctly regardless of the bits that follow.*/ |
300 | 1.26k | l = enc->low; |
301 | 1.26k | c = enc->cnt; |
302 | 1.26k | s = 10; |
303 | 1.26k | m = 0x3FFF; |
304 | 1.26k | e = ((l + m) & ~m) | (m + 1); |
305 | 1.26k | s += c; |
306 | 1.26k | offs = enc->offs; |
307 | 1.26k | buf = enc->precarry_buf; |
308 | 1.26k | if (s > 0) { |
309 | 1.26k | unsigned n; |
310 | 1.26k | storage = enc->precarry_storage; |
311 | 1.26k | if (offs + ((s + 7) >> 3) > storage) { |
312 | 0 | storage = storage * 2 + ((s + 7) >> 3); |
313 | 0 | buf = (uint16_t *)realloc(buf, sizeof(*buf) * storage); |
314 | 0 | if (buf == NULL) { |
315 | 0 | enc->error = -1; |
316 | 0 | return NULL; |
317 | 0 | } |
318 | 0 | enc->precarry_buf = buf; |
319 | 0 | enc->precarry_storage = storage; |
320 | 0 | } |
321 | 1.26k | n = (1 << (c + 16)) - 1; |
322 | 1.43k | do { |
323 | 1.43k | assert(offs < storage); |
324 | 1.43k | buf[offs++] = (uint16_t)(e >> (c + 16)); |
325 | 1.43k | e &= n; |
326 | 1.43k | s -= 8; |
327 | 1.43k | c -= 8; |
328 | 1.43k | n >>= 8; |
329 | 1.43k | } while (s > 0); |
330 | 1.26k | } |
331 | | /*Make sure there's enough room for the entropy-coded bits.*/ |
332 | 1.26k | out = enc->buf; |
333 | 1.26k | storage = enc->storage; |
334 | 1.26k | c = OD_MAXI((s + 7) >> 3, 0); |
335 | 1.26k | if (offs + c > storage) { |
336 | 0 | storage = offs + c; |
337 | 0 | out = (unsigned char *)realloc(out, sizeof(*out) * storage); |
338 | 0 | if (out == NULL) { |
339 | 0 | enc->error = -1; |
340 | 0 | return NULL; |
341 | 0 | } |
342 | 0 | enc->buf = out; |
343 | 0 | enc->storage = storage; |
344 | 0 | } |
345 | 1.26k | *nbytes = offs; |
346 | | /*Perform carry propagation.*/ |
347 | 1.26k | assert(offs <= storage); |
348 | 1.26k | out = out + storage - offs; |
349 | 1.26k | c = 0; |
350 | 24.3k | while (offs > 0) { |
351 | 23.1k | offs--; |
352 | 23.1k | c = buf[offs] + c; |
353 | 23.1k | out[offs] = (unsigned char)c; |
354 | 23.1k | c >>= 8; |
355 | 23.1k | } |
356 | | /*Note: Unless there's an allocation error, if you keep encoding into the |
357 | | current buffer and call this function again later, everything will work |
358 | | just fine (you won't get a new packet out, but you will get a single |
359 | | buffer with the new data appended to the old). |
360 | | However, this function is O(N) where N is the amount of data coded so far, |
361 | | so calling it more than once for a given packet is a bad idea.*/ |
362 | 1.26k | return out; |
363 | 1.26k | } |
364 | | |
365 | | /*Returns the number of bits "used" by the encoded symbols so far. |
366 | | This same number can be computed in either the encoder or the decoder, and is |
367 | | suitable for making coding decisions. |
368 | | Warning: The value returned by this function can decrease compared to an |
369 | | earlier call, even after encoding more data, if there is an encoding error |
370 | | (i.e., a failure to allocate enough space for the output buffer). |
371 | | Return: The number of bits. |
372 | | This will always be slightly larger than the exact value (e.g., all |
373 | | rounding error is in the positive direction).*/ |
374 | 24.8k | int od_ec_enc_tell(const od_ec_enc *enc) { |
375 | | /*The 10 here counteracts the offset of -9 baked into cnt, and adds 1 extra |
376 | | bit, which we reserve for terminating the stream.*/ |
377 | 24.8k | return (enc->cnt + 10) + enc->offs * 8; |
378 | 24.8k | } |
379 | | |
380 | | /*Returns the number of bits "used" by the encoded symbols so far. |
381 | | This same number can be computed in either the encoder or the decoder, and is |
382 | | suitable for making coding decisions. |
383 | | Warning: The value returned by this function can decrease compared to an |
384 | | earlier call, even after encoding more data, if there is an encoding error |
385 | | (i.e., a failure to allocate enough space for the output buffer). |
386 | | Return: The number of bits scaled by 2**OD_BITRES. |
387 | | This will always be slightly larger than the exact value (e.g., all |
388 | | rounding error is in the positive direction).*/ |
389 | 0 | uint32_t od_ec_enc_tell_frac(const od_ec_enc *enc) { |
390 | 0 | return od_ec_tell_frac(od_ec_enc_tell(enc), enc->rng); |
391 | 0 | } |
392 | | |
393 | | /*Saves a entropy coder checkpoint to dst. |
394 | | This allows an encoder to reverse a series of entropy coder |
395 | | decisions if it decides that the information would have been |
396 | | better coded some other way.*/ |
397 | 0 | void od_ec_enc_checkpoint(od_ec_enc *dst, const od_ec_enc *src) { |
398 | 0 | OD_COPY(dst, src, 1); |
399 | 0 | } |
400 | | |
401 | | /*Restores an entropy coder checkpoint saved by od_ec_enc_checkpoint. |
402 | | This can only be used to restore from checkpoints earlier in the target |
403 | | state's history: you can not switch backwards and forwards or otherwise |
404 | | switch to a state which isn't a casual ancestor of the current state. |
405 | | Restore is also incompatible with patching the initial bits, as the |
406 | | changes will remain in the restored version.*/ |
407 | 0 | void od_ec_enc_rollback(od_ec_enc *dst, const od_ec_enc *src) { |
408 | 0 | unsigned char *buf; |
409 | 0 | uint32_t storage; |
410 | 0 | uint16_t *precarry_buf; |
411 | 0 | uint32_t precarry_storage; |
412 | 0 | assert(dst->storage >= src->storage); |
413 | 0 | assert(dst->precarry_storage >= src->precarry_storage); |
414 | 0 | buf = dst->buf; |
415 | 0 | storage = dst->storage; |
416 | 0 | precarry_buf = dst->precarry_buf; |
417 | 0 | precarry_storage = dst->precarry_storage; |
418 | 0 | OD_COPY(dst, src, 1); |
419 | 0 | dst->buf = buf; |
420 | 0 | dst->storage = storage; |
421 | 0 | dst->precarry_buf = precarry_buf; |
422 | 0 | dst->precarry_storage = precarry_storage; |
423 | 0 | } |