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