Line data Source code
1 : /*
2 : * Copyright(c) 2019 Intel Corporation
3 : * SPDX - License - Identifier: BSD - 2 - Clause - Patent
4 : */
5 :
6 : /*
7 : * Copyright (c) 2016, Alliance for Open Media. All rights reserved
8 : *
9 : * This source code is subject to the terms of the BSD 2 Clause License and
10 : * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
11 : * was not distributed with this source code in the LICENSE file, you can
12 : * obtain it at www.aomedia.org/license/software. If the Alliance for Open
13 : * Media Patent License 1.0 was not distributed with this source code in the
14 : * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
15 : */
16 :
17 : #include <stdlib.h>
18 :
19 : #include "EbDefinitions.h"
20 : #include "EbBitstreamUnit.h"
21 : #if OD_MEASURE_EC_OVERHEAD
22 : #include <stdio.h>
23 : #endif
24 :
25 30 : static void output_bitstream_unit_dctor(EbPtr p)
26 : {
27 30 : OutputBitstreamUnit *obj = (OutputBitstreamUnit*)p;
28 30 : EB_FREE_ARRAY(obj->buffer_begin_av1);
29 30 : }
30 :
31 : /**********************************
32 : * Constructor
33 : **********************************/
34 30 : EbErrorType output_bitstream_unit_ctor(
35 : OutputBitstreamUnit *bitstream_ptr,
36 : uint32_t buffer_size){
37 30 : bitstream_ptr->dctor = output_bitstream_unit_dctor;
38 30 : if (buffer_size) {
39 30 : bitstream_ptr->size = buffer_size / sizeof(uint32_t);
40 30 : EB_MALLOC_ARRAY(bitstream_ptr->buffer_begin_av1, bitstream_ptr->size);
41 30 : bitstream_ptr->buffer_av1 = bitstream_ptr->buffer_begin_av1;
42 : }
43 : else {
44 0 : bitstream_ptr->size = 0;
45 0 : bitstream_ptr->buffer_begin_av1 = 0;
46 0 : bitstream_ptr->buffer_av1 = 0;
47 : }
48 30 : bitstream_ptr->written_bits_count = 0;
49 :
50 30 : return EB_ErrorNone;
51 : }
52 :
53 : /**********************************
54 : * Reset Bitstream
55 : **********************************/
56 296 : EbErrorType output_bitstream_reset(
57 : OutputBitstreamUnit *bitstream_ptr)
58 : {
59 296 : EbErrorType return_error = EB_ErrorNone;
60 :
61 296 : bitstream_ptr->written_bits_count = 0;
62 : // Reset the write ptr to the beginning of the buffer
63 296 : bitstream_ptr->buffer_av1 = bitstream_ptr->buffer_begin_av1;
64 :
65 296 : return return_error;
66 : }
67 :
68 : /**********************************
69 : * Output RBSP to payload
70 : * Intended to be used in CABAC
71 : **********************************/
72 176 : EbErrorType output_bitstream_rbsp_to_payload(
73 : OutputBitstreamUnit *bitstream_ptr,
74 : EbByte output_buffer,
75 : uint32_t *output_buffer_index,
76 : uint32_t *output_buffer_size,
77 : uint32_t start_location)
78 : {
79 176 : EbErrorType return_error = EB_ErrorNone;
80 176 : uint32_t buffer_written_bytes_count = (uint32_t)(bitstream_ptr->buffer_av1 - bitstream_ptr->buffer_begin_av1);
81 176 : uint32_t write_location = start_location;
82 176 : uint32_t read_location = start_location;
83 : EbByte read_byte_ptr;
84 : EbByte write_byte_ptr;
85 : #if IVF_FRAME_HEADER_IN_LIB
86 : static uint64_t frame_count = 0;
87 :
88 : #endif
89 : // IVF data
90 176 : read_byte_ptr = (EbByte)bitstream_ptr->buffer_begin_av1;
91 176 : write_byte_ptr = &output_buffer[*output_buffer_index];
92 : #if IVF_FRAME_HEADER_IN_LIB
93 : mem_put_le32(&write_byte_ptr[write_location], (int32_t)buffer_written_bytes_count);
94 : write_location = write_location + 4;
95 : mem_put_le32(&write_byte_ptr[write_location], (int32_t)(frame_count & 0xFFFFFFFF));
96 : write_location = write_location + 4;
97 : mem_put_le32(&write_byte_ptr[write_location], (int32_t)(frame_count >> 32));
98 : write_location = write_location + 4;
99 : *output_buffer_index += 12;
100 : #endif
101 : //frame_count++;
102 126774 : while ((read_location < buffer_written_bytes_count)) {
103 126598 : if ((*output_buffer_index) < (*output_buffer_size)) {
104 126598 : write_byte_ptr[write_location++] = read_byte_ptr[read_location];
105 126598 : *output_buffer_index += 1;
106 : }
107 126598 : read_location++;
108 : }
109 :
110 176 : return return_error;
111 : }
112 : /********************************************************************************************************************************/
113 : /********************************************************************************************************************************/
114 : /********************************************************************************************************************************/
115 : /********************************************************************************************************************************/
116 : // daalaboolwriter.c
117 120 : void eb_aom_daala_start_encode(DaalaWriter *br, uint8_t *source) {
118 120 : br->buffer = source;
119 120 : br->pos = 0;
120 120 : eb_od_ec_enc_init(&br->ec, 62025);
121 120 : }
122 :
123 120 : int32_t eb_aom_daala_stop_encode(DaalaWriter *br) {
124 : int32_t nb_bits;
125 : uint32_t daala_bytes;
126 : uint8_t *daala_data;
127 120 : daala_data = eb_od_ec_enc_done(&br->ec, &daala_bytes);
128 120 : nb_bits = eb_od_ec_enc_tell(&br->ec);
129 120 : memcpy(br->buffer, daala_data, daala_bytes);
130 120 : br->pos = daala_bytes;
131 120 : eb_od_ec_enc_clear(&br->ec);
132 120 : return nb_bits;
133 : }
134 :
135 : /********************************************************************************************************************************/
136 : // entcode.c
137 : /*Given the current total integer number of bits used and the current value of
138 : rng, computes the fraction number of bits used to OD_BITRES precision.
139 : This is used by od_ec_enc_tell_frac() and od_ec_dec_tell_frac().
140 : nbits_total: The number of whole bits currently used, i.e., the value
141 : returned by eb_od_ec_enc_tell() or od_ec_dec_tell().
142 : rng: The current value of rng from either the encoder or decoder state.
143 : Return: The number of bits scaled by 2**OD_BITRES.
144 : This will always be slightly larger than the exact value (e.g., all
145 : rounding error is in the positive direction).*/
146 0 : uint32_t eb_od_ec_tell_frac(uint32_t nbits_total, uint32_t rng) {
147 : uint32_t nbits;
148 : int32_t l;
149 : int32_t i;
150 : /*To handle the non-integral number of bits still left in the encoder/decoder
151 : state, we compute the worst-case number of bits of val that must be
152 : encoded to ensure that the value is inside the range for any possible
153 : subsequent bits.
154 : The computation here is independent of val itself (the decoder does not
155 : even track that value), even though the real number of bits used after
156 : eb_od_ec_enc_done() may be 1 smaller if rng is a power of two and the
157 : corresponding trailing bits of val are all zeros.
158 : If we did try to track that special case, then coding a value with a
159 : probability of 1/(1 << n) might sometimes appear to use more than n bits.
160 : This may help explain the surprising result that a newly initialized
161 : encoder or decoder claims to have used 1 bit.*/
162 0 : nbits = nbits_total << OD_BITRES;
163 0 : l = 0;
164 0 : for (i = OD_BITRES; i-- > 0;) {
165 : int32_t b;
166 0 : rng = rng * rng >> 15;
167 0 : b = (int32_t)(rng >> 16);
168 0 : l = l << 1 | b;
169 0 : rng >>= b;
170 : }
171 0 : return nbits - l;
172 : }
173 : /********************************************************************************************************************************/
174 : // entenc.c
175 :
176 : /*A range encoder.
177 : See entdec.c and the references for implementation details \cite{Mar79,MNW98}.
178 :
179 : @INPROCEEDINGS{Mar79,
180 : author="Martin, G.N.N.",
181 : title="Range encoding: an algorithm for removing redundancy from a digitised
182 : message",
183 : booktitle="Video \& Data Recording Conference",
184 : year=1979,
185 : address="Southampton",
186 : month=Jul,
187 : URL="http://www.compressconsult.com/rangecoder/rngcod.pdf.gz"
188 : }
189 : @ARTICLE{MNW98,
190 : author="Alistair Moffat and Radford Neal and Ian H. Witten",
191 : title="Arithmetic Coding Revisited",
192 : journal="{ACM} Transactions on Information Systems",
193 : year=1998,
194 : volume=16,
195 : number=3,
196 : pages="256--294",
197 : month=Jul,
198 : URL="http://researchcommons.waikato.ac.nz/bitstream/handle/10289/78/content.pdf"
199 : }*/
200 :
201 : /*Takes updated low and range values, renormalizes them so that
202 : 32768 <= rng < 65536 (flushing bytes from low to the pre-carry buffer if
203 : necessary), and stores them back in the encoder context.
204 : low: The new value of low.
205 : rng: The new value of the range.*/
206 1131860 : static void od_ec_enc_normalize(OdEcEnc *enc, od_ec_window low,
207 : unsigned rng) {
208 : int32_t d;
209 : int32_t c;
210 : int32_t s;
211 1131860 : c = enc->cnt;
212 : assert(rng <= 65535U);
213 1131860 : d = 16 - OD_ILOG_NZ(rng);
214 1131890 : s = c + d;
215 : /*TODO: Right now we flush every time we have at least one byte available.
216 : Instead we should use an od_ec_window and flush right before we're about to
217 : shift bits off the end of the window.
218 : For a 32-bit window this is about the same amount of work, but for a 64-bit
219 : window it should be a fair win.*/
220 1131890 : if (s >= 0) {
221 : uint16_t *buf;
222 : uint32_t storage;
223 : uint32_t offs;
224 : unsigned m;
225 123159 : buf = enc->precarry_buf;
226 123159 : storage = enc->precarry_storage;
227 123159 : offs = enc->offs;
228 123159 : if (offs + 2 > storage) {
229 0 : storage = 2 * storage + 2;
230 0 : buf = (uint16_t *)realloc(buf, sizeof(*buf) * storage);
231 0 : if (buf == NULL) {
232 0 : enc->error = -1;
233 0 : enc->offs = 0;
234 0 : return;
235 : }
236 0 : enc->precarry_buf = buf;
237 0 : enc->precarry_storage = storage;
238 : }
239 123159 : c += 16;
240 123159 : m = (1 << c) - 1;
241 123159 : if (s >= 8) {
242 : assert(offs < storage);
243 242 : buf[offs++] = (uint16_t)(low >> c);
244 242 : low &= m;
245 242 : c -= 8;
246 242 : m >>= 8;
247 : }
248 : assert(offs < storage);
249 123159 : buf[offs++] = (uint16_t)(low >> c);
250 123159 : s = c + d - 24;
251 123159 : low &= m;
252 123159 : enc->offs = offs;
253 : }
254 1131890 : enc->low = low << d;
255 1131890 : enc->rng = (int16_t)(rng << d);
256 1131890 : enc->cnt = (int16_t)s;
257 : }
258 :
259 : /*Initializes the encoder.
260 : size: The initial size of the buffer, in bytes.*/
261 120 : void eb_od_ec_enc_init(OdEcEnc *enc, uint32_t size) {
262 120 : eb_od_ec_enc_reset(enc);
263 120 : enc->buf = (uint8_t *)malloc(sizeof(*enc->buf) * size);
264 120 : enc->storage = size;
265 120 : if (size > 0 && enc->buf == NULL) {
266 0 : enc->storage = 0;
267 0 : enc->error = -1;
268 : }
269 120 : enc->precarry_buf = (uint16_t *)malloc(sizeof(*enc->precarry_buf) * size);
270 120 : enc->precarry_storage = size;
271 120 : if (size > 0 && enc->precarry_buf == NULL) {
272 0 : enc->precarry_storage = 0;
273 0 : enc->error = -1;
274 : }
275 120 : }
276 :
277 : /*Reinitializes the encoder.*/
278 120 : void eb_od_ec_enc_reset(OdEcEnc *enc) {
279 120 : enc->offs = 0;
280 120 : enc->low = 0;
281 120 : enc->rng = 0x8000;
282 : /*This is initialized to -9 so that it crosses zero after we've accumulated
283 : one byte + one carry bit.*/
284 120 : enc->cnt = -9;
285 120 : enc->error = 0;
286 : #if OD_MEASURE_EC_OVERHEAD
287 : enc->entropy = 0;
288 : enc->nb_symbols = 0;
289 : #endif
290 120 : }
291 :
292 : /*Frees the buffers used by the encoder.*/
293 120 : void eb_od_ec_enc_clear(OdEcEnc *enc) {
294 120 : free(enc->precarry_buf);
295 120 : free(enc->buf);
296 120 : }
297 :
298 : /*Encodes a symbol given its frequency in Q15.
299 : fl: CDF_PROB_TOP minus the cumulative frequency of all symbols that come
300 : before the
301 : one to be encoded.
302 : fh: CDF_PROB_TOP minus the cumulative frequency of all symbols up to and
303 : including
304 : the one to be encoded.*/
305 962430 : static void od_ec_encode_q15(OdEcEnc *enc, unsigned fl, unsigned fh, int32_t s,
306 : int32_t nsyms) {
307 : od_ec_window l;
308 : unsigned r;
309 : unsigned u;
310 : unsigned v;
311 962430 : l = enc->low;
312 962430 : r = enc->rng;
313 : assert(32768U <= r);
314 : assert(fh <= fl);
315 : assert(fl <= 32768U);
316 : assert(7 - EC_PROB_SHIFT - CDF_SHIFT >= 0);
317 962430 : const int32_t N = nsyms - 1;
318 962430 : if (fl < CDF_PROB_TOP) {
319 352524 : u = ((r >> 8) * (uint32_t)(fl >> EC_PROB_SHIFT) >>
320 : (7 - EC_PROB_SHIFT - CDF_SHIFT)) +
321 352524 : EC_MIN_PROB * (N - (s - 1));
322 352524 : v = ((r >> 8) * (uint32_t)(fh >> EC_PROB_SHIFT) >>
323 : (7 - EC_PROB_SHIFT - CDF_SHIFT)) +
324 352524 : EC_MIN_PROB * (N - (s + 0));
325 352524 : l += r - u;
326 352524 : r = u - v;
327 : }
328 : else {
329 609906 : r -= ((r >> 8) * (uint32_t)(fh >> EC_PROB_SHIFT) >>
330 609906 : (7 - EC_PROB_SHIFT - CDF_SHIFT)) +
331 609906 : EC_MIN_PROB * (N - (s + 0));
332 : }
333 962430 : od_ec_enc_normalize(enc, l, r);
334 : #if OD_MEASURE_EC_OVERHEAD
335 : enc->entropy -= OD_LOG2((double)(OD_ICDF(fh) - OD_ICDF(fl)) / CDF_PROB_TOP.);
336 : enc->nb_symbols++;
337 : #endif
338 962488 : }
339 :
340 : /*Encode a single binary value.
341 : val: The value to encode (0 or 1).
342 : f: The probability that the val is one, scaled by 32768.*/
343 169400 : void eb_od_ec_encode_bool_q15(OdEcEnc *enc, int32_t val, unsigned f) {
344 : od_ec_window l;
345 : unsigned r;
346 : unsigned v;
347 : assert(0 < f);
348 : assert(f < 32768U);
349 169400 : l = enc->low;
350 169400 : r = enc->rng;
351 : assert(32768U <= r);
352 169400 : v = ((r >> 8) * (uint32_t)(f >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT));
353 169400 : v += EC_MIN_PROB;
354 169400 : if (val) l += r - v;
355 169400 : r = val ? v : r - v;
356 169400 : od_ec_enc_normalize(enc, l, r);
357 : #if OD_MEASURE_EC_OVERHEAD
358 : enc->entropy -= OD_LOG2((double)(val ? f : (32768 - f)) / 32768.);
359 : enc->nb_symbols++;
360 : #endif
361 169400 : }
362 :
363 : /*Encodes a symbol given a cumulative distribution function (CDF) table in Q15.
364 : s: The index of the symbol to encode.
365 : icdf: 32768 minus the CDF, such that symbol s falls in the range
366 : [s > 0 ? (32768 - icdf[s - 1]) : 0, 32768 - icdf[s]).
367 : The values must be monotonically decreasing, and icdf[nsyms - 1] must
368 : be 0.
369 : nsyms: The number of symbols in the alphabet.
370 : This should be at most 16.*/
371 962413 : void eb_od_ec_encode_cdf_q15(OdEcEnc *enc, int32_t s, const uint16_t *icdf,
372 : int32_t nsyms) {
373 : (void)nsyms;
374 : assert(s >= 0);
375 : assert(s < nsyms);
376 : assert(icdf[nsyms - 1] == OD_ICDF(CDF_PROB_TOP));
377 962413 : od_ec_encode_q15(enc, s > 0 ? icdf[s - 1] : OD_ICDF(0), icdf[s], s, nsyms);
378 962488 : }
379 :
380 120 : uint8_t *eb_od_ec_enc_done(OdEcEnc *enc, uint32_t *nbytes) {
381 : uint8_t *out;
382 : uint32_t storage;
383 : uint16_t *buf;
384 : uint32_t offs;
385 : od_ec_window m;
386 : od_ec_window e;
387 : od_ec_window l;
388 : int32_t c;
389 : int32_t s;
390 120 : if (enc->error) return NULL;
391 : #if OD_MEASURE_EC_OVERHEAD
392 : {
393 : uint32_t tell;
394 : /* Don't count the 1 bit we lose to raw bits as overhead. */
395 : tell = eb_od_ec_enc_tell(enc) - 1;
396 : fprintf(stderr, "overhead: %f%%\n",
397 : 100 * (tell - enc->entropy) / enc->entropy);
398 : fprintf(stderr, "efficiency: %f bits/symbol\n",
399 : (double)tell / enc->nb_symbols);
400 : }
401 : #endif
402 : /*We output the minimum number of bits that ensures that the symbols encoded
403 : thus far will be decoded correctly regardless of the bits that follow.*/
404 120 : l = enc->low;
405 120 : c = enc->cnt;
406 120 : s = 10;
407 120 : m = 0x3FFF;
408 120 : e = ((l + m) & ~m) | (m + 1);
409 120 : s += c;
410 120 : offs = enc->offs;
411 120 : buf = enc->precarry_buf;
412 120 : if (s > 0) {
413 : unsigned n;
414 120 : storage = enc->precarry_storage;
415 120 : if (offs + ((s + 7) >> 3) > storage) {
416 0 : storage = storage * 2 + ((s + 7) >> 3);
417 0 : buf = (uint16_t *)realloc(buf, sizeof(*buf) * storage);
418 0 : if (buf == NULL) {
419 0 : enc->error = -1;
420 0 : return NULL;
421 : }
422 0 : enc->precarry_buf = buf;
423 0 : enc->precarry_storage = storage;
424 : }
425 120 : n = (1 << (c + 16)) - 1;
426 : do {
427 : assert(offs < storage);
428 134 : buf[offs++] = (uint16_t)(e >> (c + 16));
429 134 : e &= n;
430 134 : s -= 8;
431 134 : c -= 8;
432 134 : n >>= 8;
433 134 : } while (s > 0);
434 : }
435 : /*Make sure there's enough room for the entropy-coded bits.*/
436 120 : out = enc->buf;
437 120 : storage = enc->storage;
438 120 : c = OD_MAXI((s + 7) >> 3, 0);
439 120 : if (offs + c > storage) {
440 0 : storage = offs + c;
441 0 : out = (uint8_t *)realloc(out, sizeof(*out) * storage);
442 0 : if (out == NULL) {
443 0 : enc->error = -1;
444 0 : return NULL;
445 : }
446 0 : enc->buf = out;
447 0 : enc->storage = storage;
448 : }
449 120 : *nbytes = offs;
450 : /*Perform carry propagation.*/
451 : assert(offs <= storage);
452 120 : out = out + storage - offs;
453 120 : c = 0;
454 123657 : while (offs > 0) {
455 123537 : offs--;
456 123537 : c = buf[offs] + c;
457 123537 : out[offs] = (uint8_t)c;
458 123537 : c >>= 8;
459 : }
460 : /*Note: Unless there's an allocation error, if you keep encoding into the
461 : current buffer and call this function again later, everything will work
462 : just fine (you won't get a new packet out, but you will get a single
463 : buffer with the new data appended to the old).
464 : However, this function is O(N) where N is the amount of data coded so far,
465 : so calling it more than once for a given packet is a bad idea.*/
466 120 : return out;
467 : }
468 :
469 : /*Returns the number of bits "used" by the encoded symbols so far.
470 : This same number can be computed in either the encoder or the decoder, and is
471 : suitable for making coding decisions.
472 : Warning: The value returned by this function can decrease compared to an
473 : earlier call, even after encoding more data, if there is an encoding error
474 : (i.e., a failure to allocate enough space for the output buffer).
475 : Return: The number of bits.
476 : This will always be slightly larger than the exact value (e.g., all
477 : rounding error is in the positive direction).*/
478 120 : int32_t eb_od_ec_enc_tell(const OdEcEnc *enc) {
479 : /*The 10 here counteracts the offset of -9 baked into cnt, and adds 1 extra
480 : bit, which we reserve for terminating the stream.*/
481 120 : return (enc->cnt + 10) + enc->offs * 8;
482 : }
483 :
484 : /*Saves a entropy coder checkpoint to dst.
485 : This allows an encoder to reverse a series of entropy coder
486 : decisions if it decides that the information would have been
487 : better coded some other way.*/
488 0 : void eb_od_ec_enc_checkpoint(OdEcEnc *dst, const OdEcEnc *src) {
489 0 : OD_COPY(dst, src, 1);
490 0 : }
491 :
492 : /*Restores an entropy coder checkpoint saved by eb_od_ec_enc_checkpoint.
493 : This can only be used to restore from checkpoints earlier in the target
494 : state's history: you can not switch backwards and forwards or otherwise
495 : switch to a state which isn't a casual ancestor of the current state.
496 : Restore is also incompatible with patching the initial bits, as the
497 : changes will remain in the restored version.*/
498 0 : void eb_od_ec_enc_rollback(OdEcEnc *dst, const OdEcEnc *src) {
499 : uint8_t *buf;
500 : uint32_t storage;
501 : uint16_t *precarry_buf;
502 : uint32_t precarry_storage;
503 : assert(dst->storage >= src->storage);
504 : assert(dst->precarry_storage >= src->precarry_storage);
505 0 : buf = dst->buf;
506 0 : storage = dst->storage;
507 0 : precarry_buf = dst->precarry_buf;
508 0 : precarry_storage = dst->precarry_storage;
509 0 : OD_COPY(dst, src, 1);
510 0 : dst->buf = buf;
511 0 : dst->storage = storage;
512 0 : dst->precarry_buf = precarry_buf;
513 0 : dst->precarry_storage = precarry_storage;
514 0 : }
515 : /********************************************************************************************************************************/
516 : /********************************************************************************************************************************/
517 : /********************************************************************************************************************************/
|
