diff options
Diffstat (limited to 'third_party/aom/aom_dsp/entdec.c')
| -rw-r--r-- | third_party/aom/aom_dsp/entdec.c | 229 |
1 files changed, 0 insertions, 229 deletions
diff --git a/third_party/aom/aom_dsp/entdec.c b/third_party/aom/aom_dsp/entdec.c deleted file mode 100644 index d1764c47b..000000000 --- a/third_party/aom/aom_dsp/entdec.c +++ /dev/null @@ -1,229 +0,0 @@ -/* - * Copyright (c) 2001-2016, Alliance for Open Media. All rights reserved - * - * This source code is subject to the terms of the BSD 2 Clause License and - * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License - * was not distributed with this source code in the LICENSE file, you can - * obtain it at www.aomedia.org/license/software. If the Alliance for Open - * Media Patent License 1.0 was not distributed with this source code in the - * PATENTS file, you can obtain it at www.aomedia.org/license/patent. - */ - -#include <assert.h> -#include "aom_dsp/entdec.h" -#include "aom_dsp/prob.h" - -/*A range decoder. - This is an entropy decoder based upon \cite{Mar79}, which is itself a - rediscovery of the FIFO arithmetic code introduced by \cite{Pas76}. - It is very similar to arithmetic encoding, except that encoding is done with - digits in any base, instead of with bits, and so it is faster when using - larger bases (i.e.: a byte). - The author claims an average waste of $\frac{1}{2}\log_b(2b)$ bits, where $b$ - is the base, longer than the theoretical optimum, but to my knowledge there - is no published justification for this claim. - This only seems true when using near-infinite precision arithmetic so that - the process is carried out with no rounding errors. - - An excellent description of implementation details is available at - http://www.arturocampos.com/ac_range.html - A recent work \cite{MNW98} which proposes several changes to arithmetic - encoding for efficiency actually re-discovers many of the principles - behind range encoding, and presents a good theoretical analysis of them. - - End of stream is handled by writing out the smallest number of bits that - ensures that the stream will be correctly decoded regardless of the value of - any subsequent bits. - od_ec_dec_tell() can be used to determine how many bits were needed to decode - all the symbols thus far; other data can be packed in the remaining bits of - the input buffer. - @PHDTHESIS{Pas76, - author="Richard Clark Pasco", - title="Source coding algorithms for fast data compression", - school="Dept. of Electrical Engineering, Stanford University", - address="Stanford, CA", - month=May, - year=1976, - URL="http://www.richpasco.org/scaffdc.pdf" - } - @INPROCEEDINGS{Mar79, - author="Martin, G.N.N.", - title="Range encoding: an algorithm for removing redundancy from a digitised - message", - booktitle="Video & Data Recording Conference", - year=1979, - address="Southampton", - month=Jul, - URL="http://www.compressconsult.com/rangecoder/rngcod.pdf.gz" - } - @ARTICLE{MNW98, - author="Alistair Moffat and Radford Neal and Ian H. Witten", - title="Arithmetic Coding Revisited", - journal="{ACM} Transactions on Information Systems", - year=1998, - volume=16, - number=3, - pages="256--294", - month=Jul, - URL="http://researchcommons.waikato.ac.nz/bitstream/handle/10289/78/content.pdf" - }*/ - -/*This is meant to be a large, positive constant that can still be efficiently - loaded as an immediate (on platforms like ARM, for example). - Even relatively modest values like 100 would work fine.*/ -#define OD_EC_LOTS_OF_BITS (0x4000) - -/*The return value of od_ec_dec_tell does not change across an od_ec_dec_refill - call.*/ -static void od_ec_dec_refill(od_ec_dec *dec) { - int s; - od_ec_window dif; - int16_t cnt; - const unsigned char *bptr; - const unsigned char *end; - dif = dec->dif; - cnt = dec->cnt; - bptr = dec->bptr; - end = dec->end; - s = OD_EC_WINDOW_SIZE - 9 - (cnt + 15); - for (; s >= 0 && bptr < end; s -= 8, bptr++) { - assert(s <= OD_EC_WINDOW_SIZE - 8); - dif ^= (od_ec_window)bptr[0] << s; - cnt += 8; - } - if (bptr >= end) { - dec->tell_offs += OD_EC_LOTS_OF_BITS - cnt; - cnt = OD_EC_LOTS_OF_BITS; - } - dec->dif = dif; - dec->cnt = cnt; - dec->bptr = bptr; -} - -/*Takes updated dif and range values, renormalizes them so that - 32768 <= rng < 65536 (reading more bytes from the stream into dif if - necessary), and stores them back in the decoder context. - dif: The new value of dif. - rng: The new value of the range. - ret: The value to return. - Return: ret. - This allows the compiler to jump to this function via a tail-call.*/ -static int od_ec_dec_normalize(od_ec_dec *dec, od_ec_window dif, unsigned rng, - int ret) { - int d; - assert(rng <= 65535U); - // The number of leading zeros in the 16-bit binary representation of rng. - d = 16 - OD_ILOG_NZ(rng); - dec->cnt -= d; - /*This is equivalent to shifting in 1's instead of 0's.*/ - dec->dif = ((dif + 1) << d) - 1; - dec->rng = rng << d; - if (dec->cnt < 0) od_ec_dec_refill(dec); - return ret; -} - -/*Initializes the decoder. - buf: The input buffer to use. - Return: 0 on success, or a negative value on error.*/ -void od_ec_dec_init(od_ec_dec *dec, const unsigned char *buf, - uint32_t storage) { - dec->buf = buf; - dec->tell_offs = 10 - (OD_EC_WINDOW_SIZE - 8); - dec->end = buf + storage; - dec->bptr = buf; - dec->dif = ((od_ec_window)1 << (OD_EC_WINDOW_SIZE - 1)) - 1; - dec->rng = 0x8000; - dec->cnt = -15; - dec->error = 0; - od_ec_dec_refill(dec); -} - -/*Decode a single binary value. - f: The probability that the bit is one, scaled by 32768. - Return: The value decoded (0 or 1).*/ -int od_ec_decode_bool_q15(od_ec_dec *dec, unsigned f) { - od_ec_window dif; - od_ec_window vw; - unsigned r; - unsigned r_new; - unsigned v; - int ret; - assert(0 < f); - assert(f < 32768U); - dif = dec->dif; - r = dec->rng; - assert(dif >> (OD_EC_WINDOW_SIZE - 16) < r); - assert(32768U <= r); - v = ((r >> 8) * (uint32_t)(f >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT)); - v += EC_MIN_PROB; - vw = (od_ec_window)v << (OD_EC_WINDOW_SIZE - 16); - ret = 1; - r_new = v; - if (dif >= vw) { - r_new = r - v; - dif -= vw; - ret = 0; - } - return od_ec_dec_normalize(dec, dif, r_new, ret); -} - -/*Decodes a symbol given an inverse cumulative distribution function (CDF) - table in Q15. - icdf: CDF_PROB_TOP minus the CDF, such that symbol s falls in the range - [s > 0 ? (CDF_PROB_TOP - icdf[s - 1]) : 0, CDF_PROB_TOP - icdf[s]). - The values must be monotonically non-increasing, and icdf[nsyms - 1] - must be 0. - nsyms: The number of symbols in the alphabet. - This should be at most 16. - Return: The decoded symbol s.*/ -int od_ec_decode_cdf_q15(od_ec_dec *dec, const uint16_t *icdf, int nsyms) { - od_ec_window dif; - unsigned r; - unsigned c; - unsigned u; - unsigned v; - int ret; - (void)nsyms; - dif = dec->dif; - r = dec->rng; - const int N = nsyms - 1; - - assert(dif >> (OD_EC_WINDOW_SIZE - 16) < r); - assert(icdf[nsyms - 1] == OD_ICDF(CDF_PROB_TOP)); - assert(32768U <= r); - assert(7 - EC_PROB_SHIFT - CDF_SHIFT >= 0); - c = (unsigned)(dif >> (OD_EC_WINDOW_SIZE - 16)); - v = r; - ret = -1; - do { - u = v; - v = ((r >> 8) * (uint32_t)(icdf[++ret] >> EC_PROB_SHIFT) >> - (7 - EC_PROB_SHIFT - CDF_SHIFT)); - v += EC_MIN_PROB * (N - ret); - } while (c < v); - assert(v < u); - assert(u <= r); - r = u - v; - dif -= (od_ec_window)v << (OD_EC_WINDOW_SIZE - 16); - return od_ec_dec_normalize(dec, dif, r, ret); -} - -/*Returns the number of bits "used" by the decoded symbols so far. - This same number can be computed in either the encoder or the decoder, and is - suitable for making coding decisions. - Return: The number of bits. - This will always be slightly larger than the exact value (e.g., all - rounding error is in the positive direction).*/ -int od_ec_dec_tell(const od_ec_dec *dec) { - return (int)((dec->bptr - dec->buf) * 8 - dec->cnt + dec->tell_offs); -} - -/*Returns the number of bits "used" by the decoded symbols so far. - This same number can be computed in either the encoder or the decoder, and is - suitable for making coding decisions. - Return: The number of bits scaled by 2**OD_BITRES. - This will always be slightly larger than the exact value (e.g., all - rounding error is in the positive direction).*/ -uint32_t od_ec_dec_tell_frac(const od_ec_dec *dec) { - return od_ec_tell_frac(od_ec_dec_tell(dec), dec->rng); -} |