Import aom library

This is the reference implementation for the Alliance for Open Media's av1 video code.

The commit used was 4d668d7feb1f8abd809d1bca0418570a7f142a36.

1 files changed, 300 insertions, 0 deletions

diff --git a/third_party/aom/aom_dsp/entdec.c b/third_party/aom/aom_dsp/entdec.c
new file mode 100644
index 000000000..49b176cd8
--- /dev/null
+++ b/third_party/aom/aom_dsp/entdec.c
@@ -0,0 +1,300 @@
+/*
+ * 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.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "./config.h"
+#endif
+
+#include "aom_dsp/entdec.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)
+
+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++) {
+    OD_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;
+  OD_ASSERT(rng <= 65535U);
+  d = 16 - OD_ILOG_NZ(rng);
+  dec->cnt -= d;
+#if CONFIG_EC_SMALLMUL
+  /*This is equivalent to shifting in 1's instead of 0's.*/
+  dec->dif = ((dif + 1) << d) - 1;
+#else
+  dec->dif = dif << d;
+#endif
+  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->eptr = buf + storage;
+  dec->end_window = 0;
+  dec->nend_bits = 0;
+  dec->tell_offs = 10 - (OD_EC_WINDOW_SIZE - 8);
+  dec->end = buf + storage;
+  dec->bptr = buf;
+#if CONFIG_EC_SMALLMUL
+  dec->dif = ((od_ec_window)1 << (OD_EC_WINDOW_SIZE - 1)) - 1;
+#else
+  dec->dif = 0;
+#endif
+  dec->rng = 0x8000;
+  dec->cnt = -15;
+  dec->error = 0;
+  od_ec_dec_refill(dec);
+}
+
+/*Decode a single binary value.
+  {EC_SMALLMUL} f: The probability that the bit is one, scaled by 32768.
+  {else} f: The probability that the bit is zero, 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;
+  OD_ASSERT(0 < f);
+  OD_ASSERT(f < 32768U);
+  dif = dec->dif;
+  r = dec->rng;
+  OD_ASSERT(dif >> (OD_EC_WINDOW_SIZE - 16) < r);
+  OD_ASSERT(32768U <= r);
+#if CONFIG_EC_SMALLMUL
+  v = (r >> 8) * (uint32_t)f >> 7;
+  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;
+  }
+#else
+  v = f * (uint32_t)r >> 15;
+  vw = (od_ec_window)v << (OD_EC_WINDOW_SIZE - 16);
+  ret = 0;
+  r_new = v;
+  if (dif >= vw) {
+    r_new = r - v;
+    dif -= vw;
+    ret = 1;
+  }
+#endif
+  return od_ec_dec_normalize(dec, dif, r_new, ret);
+}
+
+/*Decodes a symbol given a cumulative distribution function (CDF) table in Q15.
+  cdf: The CDF, such that symbol s falls in the range
+        [s > 0 ? cdf[s - 1] : 0, cdf[s]).
+       The values must be monotonically non-increasing, and cdf[nsyms - 1]
+        must be 32768.
+       {EC_SMALLMUL}: The CDF contains 32768 minus those values.
+  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 *cdf, int nsyms) {
+  od_ec_window dif;
+  unsigned r;
+  unsigned c;
+  unsigned u;
+  unsigned v;
+  int ret;
+  (void)nsyms;
+  dif = dec->dif;
+  r = dec->rng;
+  OD_ASSERT(dif >> (OD_EC_WINDOW_SIZE - 16) < r);
+  OD_ASSERT(cdf[nsyms - 1] == OD_ICDF(32768U));
+  OD_ASSERT(32768U <= r);
+#if CONFIG_EC_SMALLMUL
+  c = (unsigned)(dif >> (OD_EC_WINDOW_SIZE - 16));
+  v = r;
+  ret = -1;
+  do {
+    u = v;
+    v = (r >> 8) * (uint32_t)cdf[++ret] >> 7;
+  } while (c < v);
+  OD_ASSERT(v < u);
+  OD_ASSERT(u <= r);
+  r = u - v;
+  dif -= (od_ec_window)v << (OD_EC_WINDOW_SIZE - 16);
+#else
+  c = (unsigned)(dif >> (OD_EC_WINDOW_SIZE - 16));
+  v = 0;
+  ret = -1;
+  do {
+    u = v;
+    v = cdf[++ret] * (uint32_t)r >> 15;
+  } while (v <= c);
+  OD_ASSERT(u < v);
+  OD_ASSERT(v <= r);
+  r = v - u;
+  dif -= (od_ec_window)u << (OD_EC_WINDOW_SIZE - 16);
+#endif
+  return od_ec_dec_normalize(dec, dif, r, ret);
+}
+
+#if CONFIG_RAWBITS
+/*Extracts a sequence of raw bits from the stream.
+  The bits must have been encoded with od_ec_enc_bits().
+  ftb: The number of bits to extract.
+       This must be between 0 and 25, inclusive.
+  Return: The decoded bits.*/
+uint32_t od_ec_dec_bits_(od_ec_dec *dec, unsigned ftb) {
+  od_ec_window window;
+  int available;
+  uint32_t ret;
+  OD_ASSERT(ftb <= 25);
+  window = dec->end_window;
+  available = dec->nend_bits;
+  if ((unsigned)available < ftb) {
+    const unsigned char *buf;
+    const unsigned char *eptr;
+    buf = dec->buf;
+    eptr = dec->eptr;
+    OD_ASSERT(available <= OD_EC_WINDOW_SIZE - 8);
+    do {
+      if (eptr <= buf) {
+        dec->tell_offs += OD_EC_LOTS_OF_BITS - available;
+        available = OD_EC_LOTS_OF_BITS;
+        break;
+      }
+      window |= (od_ec_window) * --eptr << available;
+      available += 8;
+    } while (available <= OD_EC_WINDOW_SIZE - 8);
+    dec->eptr = eptr;
+  }
+  ret = (uint32_t)window & (((uint32_t)1 << ftb) - 1);
+  window >>= ftb;
+  available -= ftb;
+  dec->end_window = window;
+  dec->nend_bits = available;
+  return ret;
+}
+#endif
+
+/*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->end - dec->eptr) + (dec->bptr - dec->buf)) * 8 -
+               dec->cnt - dec->nend_bits + 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);
+}