1 files changed, 408 insertions, 0 deletions
diff --git a/libavcodec/opus_rc.c b/libavcodec/opus_rc.c
new file mode 100644
index 0000000000..85268bd284
--- /dev/null
+++ b/libavcodec/opus_rc.c
@@ -0,0 +1,408 @@
+/*
+ * Copyright (c) 2012 Andrew D'Addesio
+ * Copyright (c) 2013-2014 Mozilla Corporation
+ * Copyright (c) 2017 Rostislav Pehlivanov <atomnuker@gmail.com>
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include "opus_rc.h"
+
+#define OPUS_RC_BITS 32
+#define OPUS_RC_SYM  8
+#define OPUS_RC_CEIL ((1 << OPUS_RC_SYM) - 1)
+#define OPUS_RC_TOP (1u << 31)
+#define OPUS_RC_BOT (OPUS_RC_TOP >> OPUS_RC_SYM)
+#define OPUS_RC_SHIFT (OPUS_RC_BITS - OPUS_RC_SYM - 1)
+
+static av_always_inline void opus_rc_enc_carryout(OpusRangeCoder *rc, int cbuf)
+{
+    const int cb = cbuf >> OPUS_RC_SYM, mb = (OPUS_RC_CEIL + cb) & OPUS_RC_CEIL;
+    if (cbuf == OPUS_RC_CEIL) {
+        rc->ext++;
+        return;
+    }
+    rc->rng_cur[0] = rc->rem + cb;
+    rc->rng_cur += (rc->rem >= 0);
+    for (; rc->ext > 0; rc->ext--)
+        *rc->rng_cur++ = mb;
+    av_assert0(rc->rng_cur < rc->rb.position);
+    rc->rem = cbuf & OPUS_RC_CEIL; /* Propagate */
+}
+
+static av_always_inline void opus_rc_dec_normalize(OpusRangeCoder *rc)
+{
+    while (rc->range <= OPUS_RC_BOT) {
+        rc->value = ((rc->value << OPUS_RC_SYM) | (get_bits(&rc->gb, OPUS_RC_SYM) ^ OPUS_RC_CEIL)) & (OPUS_RC_TOP - 1);
+        rc->range     <<= OPUS_RC_SYM;
+        rc->total_bits += OPUS_RC_SYM;
+    }
+}
+
+static av_always_inline void opus_rc_enc_normalize(OpusRangeCoder *rc)
+{
+    while (rc->range <= OPUS_RC_BOT) {
+        opus_rc_enc_carryout(rc, rc->value >> OPUS_RC_SHIFT);
+        rc->value = (rc->value << OPUS_RC_SYM) & (OPUS_RC_TOP - 1);
+        rc->range     <<= OPUS_RC_SYM;
+        rc->total_bits += OPUS_RC_SYM;
+    }
+}
+
+static av_always_inline void opus_rc_dec_update(OpusRangeCoder *rc, uint32_t scale,
+                                                uint32_t low, uint32_t high,
+                                                uint32_t total)
+{
+    rc->value -= scale * (total - high);
+    rc->range  = low ? scale * (high - low)
+                      : rc->range - scale * (total - high);
+    opus_rc_dec_normalize(rc);
+}
+
+/* Main encoding function, this needs to go fast */
+static av_always_inline void opus_rc_enc_update(OpusRangeCoder *rc, uint32_t b, uint32_t p,
+                                                uint32_t p_tot, const int ptwo)
+{
+    uint32_t rscaled, cnd = !!b;
+    if (ptwo) /* Whole function is inlined so hopefully branch is optimized out */
+        rscaled = rc->range >> ff_log2(p_tot);
+    else
+        rscaled = rc->range/p_tot;
+    rc->value +=    cnd*(rc->range - rscaled*(p_tot - b));
+    rc->range  = (!cnd)*(rc->range - rscaled*(p_tot - p)) + cnd*rscaled*(p - b);
+    opus_rc_enc_normalize(rc);
+}
+
+uint32_t ff_opus_rc_dec_cdf(OpusRangeCoder *rc, const uint16_t *cdf)
+{
+    unsigned int k, scale, total, symbol, low, high;
+
+    total = *cdf++;
+
+    scale   = rc->range / total;
+    symbol = rc->value / scale + 1;
+    symbol = total - FFMIN(symbol, total);
+
+    for (k = 0; cdf[k] <= symbol; k++);
+    high = cdf[k];
+    low  = k ? cdf[k-1] : 0;
+
+    opus_rc_dec_update(rc, scale, low, high, total);
+
+    return k;
+}
+
+void ff_opus_rc_enc_cdf(OpusRangeCoder *rc, int val, const uint16_t *cdf)
+{
+    opus_rc_enc_update(rc, cdf[val], cdf[val + 1], cdf[0], 1);
+}
+
+uint32_t ff_opus_rc_dec_log(OpusRangeCoder *rc, uint32_t bits)
+{
+    uint32_t k, scale;
+    scale = rc->range >> bits; // in this case, scale = symbol
+
+    if (rc->value >= scale) {
+        rc->value -= scale;
+        rc->range -= scale;
+        k = 0;
+    } else {
+        rc->range = scale;
+        k = 1;
+    }
+    opus_rc_dec_normalize(rc);
+    return k;
+}
+
+void ff_opus_rc_enc_log(OpusRangeCoder *rc, int val, uint32_t bits)
+{
+    bits = (1 << bits) - 1;
+    opus_rc_enc_update(rc, (!!val)*bits, bits + !!val, bits + 1, 1);
+}
+
+/**
+ * CELT: read 1-25 raw bits at the end of the frame, backwards byte-wise
+ */
+uint32_t ff_opus_rc_get_raw(OpusRangeCoder *rc, uint32_t count)
+{
+    uint32_t value = 0;
+
+    while (rc->rb.bytes && rc->rb.cachelen < count) {
+        rc->rb.cacheval |= *--rc->rb.position << rc->rb.cachelen;
+        rc->rb.cachelen += 8;
+        rc->rb.bytes--;
+    }
+
+    value = av_mod_uintp2(rc->rb.cacheval, count);
+    rc->rb.cacheval    >>= count;
+    rc->rb.cachelen     -= count;
+    rc->total_bits      += count;
+
+    return value;
+}
+
+/**
+ * CELT: write 0 - 31 bits to the rawbits buffer
+ */
+void ff_opus_rc_put_raw(OpusRangeCoder *rc, uint32_t val, uint32_t count)
+{
+    const int to_write = FFMIN(32 - rc->rb.cachelen, count);
+
+    rc->total_bits += count;
+    rc->rb.cacheval |= av_mod_uintp2(val, to_write) << rc->rb.cachelen;
+    rc->rb.cachelen = (rc->rb.cachelen + to_write) % 32;
+
+    if (!rc->rb.cachelen && count) {
+        AV_WB32(rc->rb.position, rc->rb.cacheval);
+        rc->rb.bytes    += 4;
+        rc->rb.position -= 4;
+        rc->rb.cachelen = count - to_write;
+        rc->rb.cacheval = av_mod_uintp2(val >> to_write, rc->rb.cachelen);
+        av_assert0(rc->rng_cur < rc->rb.position);
+    }
+}
+
+/**
+ * CELT: read a uniform distribution
+ */
+uint32_t ff_opus_rc_dec_uint(OpusRangeCoder *rc, uint32_t size)
+{
+    uint32_t bits, k, scale, total;
+
+    bits  = opus_ilog(size - 1);
+    total = (bits > 8) ? ((size - 1) >> (bits - 8)) + 1 : size;
+
+    scale  = rc->range / total;
+    k      = rc->value / scale + 1;
+    k      = total - FFMIN(k, total);
+    opus_rc_dec_update(rc, scale, k, k + 1, total);
+
+    if (bits > 8) {
+        k = k << (bits - 8) | ff_opus_rc_get_raw(rc, bits - 8);
+        return FFMIN(k, size - 1);
+    } else
+        return k;
+}
+
+/**
+ * CELT: write a uniformly distributed integer
+ */
+void ff_opus_rc_enc_uint(OpusRangeCoder *rc, uint32_t val, uint32_t size)
+{
+    const int ps = FFMAX(opus_ilog(size - 1) - 8, 0);
+    opus_rc_enc_update(rc, val >> ps, (val >> ps) + 1, ((size - 1) >> ps) + 1, 0);
+    ff_opus_rc_put_raw(rc, val, ps);
+}
+
+uint32_t ff_opus_rc_dec_uint_step(OpusRangeCoder *rc, int k0)
+{
+    /* Use a probability of 3 up to itheta=8192 and then use 1 after */
+    uint32_t k, scale, symbol, total = (k0+1)*3 + k0;
+    scale  = rc->range / total;
+    symbol = rc->value / scale + 1;
+    symbol = total - FFMIN(symbol, total);
+
+    k = (symbol < (k0+1)*3) ? symbol/3 : symbol - (k0+1)*2;
+
+    opus_rc_dec_update(rc, scale, (k <= k0) ? 3*(k+0) : (k-1-k0) + 3*(k0+1),
+                       (k <= k0) ? 3*(k+1) : (k-0-k0) + 3*(k0+1), total);
+    return k;
+}
+
+void ff_opus_rc_enc_uint_step(OpusRangeCoder *rc, uint32_t val, int k0)
+{
+    const uint32_t a = val <= k0, b = 2*a + 1;
+    k0 = (k0 + 1) << 1;
+    val = b*(val + k0) - 3*a*k0;
+    opus_rc_enc_update(rc, val, val + b, (k0 << 1) - 1, 0);
+}
+
+uint32_t ff_opus_rc_dec_uint_tri(OpusRangeCoder *rc, int qn)
+{
+    uint32_t k, scale, symbol, total, low, center;
+
+    total = ((qn>>1) + 1) * ((qn>>1) + 1);
+    scale   = rc->range / total;
+    center = rc->value / scale + 1;
+    center = total - FFMIN(center, total);
+
+    if (center < total >> 1) {
+        k      = (ff_sqrt(8 * center + 1) - 1) >> 1;
+        low    = k * (k + 1) >> 1;
+        symbol = k + 1;
+    } else {
+        k      = (2*(qn + 1) - ff_sqrt(8*(total - center - 1) + 1)) >> 1;
+        low    = total - ((qn + 1 - k) * (qn + 2 - k) >> 1);
+        symbol = qn + 1 - k;
+    }
+
+    opus_rc_dec_update(rc, scale, low, low + symbol, total);
+
+    return k;
+}
+
+void ff_opus_rc_enc_uint_tri(OpusRangeCoder *rc, uint32_t k, int qn)
+{
+    uint32_t symbol, low, total;
+
+    total = ((qn>>1) + 1) * ((qn>>1) + 1);
+
+    if (k <= qn >> 1) {
+        low    = k * (k + 1) >> 1;
+        symbol = k + 1;
+    } else {
+        low    = total - ((qn + 1 - k) * (qn + 2 - k) >> 1);
+        symbol = qn + 1 - k;
+    }
+
+    opus_rc_enc_update(rc, low, low + symbol, total, 0);
+}
+
+int ff_opus_rc_dec_laplace(OpusRangeCoder *rc, uint32_t symbol, int decay)
+{
+    /* extends the range coder to model a Laplace distribution */
+    int value = 0;
+    uint32_t scale, low = 0, center;
+
+    scale  = rc->range >> 15;
+    center = rc->value / scale + 1;
+    center = (1 << 15) - FFMIN(center, 1 << 15);
+
+    if (center >= symbol) {
+        value++;
+        low = symbol;
+        symbol = 1 + ((32768 - 32 - symbol) * (16384-decay) >> 15);
+
+        while (symbol > 1 && center >= low + 2 * symbol) {
+            value++;
+            symbol *= 2;
+            low    += symbol;
+            symbol  = (((symbol - 2) * decay) >> 15) + 1;
+        }
+
+        if (symbol <= 1) {
+            int distance = (center - low) >> 1;
+            value += distance;
+            low   += 2 * distance;
+        }
+
+        if (center < low + symbol)
+            value *= -1;
+        else
+            low += symbol;
+    }
+
+    opus_rc_dec_update(rc, scale, low, FFMIN(low + symbol, 32768), 32768);
+
+    return value;
+}
+
+void ff_opus_rc_enc_laplace(OpusRangeCoder *rc, int *value, uint32_t symbol, int decay)
+{
+    uint32_t low = symbol;
+    int i = 1, val = FFABS(*value), pos = *value > 0;
+    if (!val) {
+        opus_rc_enc_update(rc, 0, symbol, 1 << 15, 1);
+        return;
+    }
+    symbol = ((32768 - 32 - symbol)*(16384 - decay)) >> 15;
+    for (; i < val && symbol; i++) {
+        low   += (symbol << 1) + 2;
+        symbol = (symbol*decay) >> 14;
+    }
+    if (symbol) {
+        low += (++symbol)*pos;
+    } else {
+        const int distance = FFMIN(val - i, (((32768 - low) - !pos) >> 1) - 1);
+        low   += pos + (distance << 1);
+        symbol = FFMIN(1, 32768 - low);
+        *value = FFSIGN(*value)*(distance + i);
+    }
+    opus_rc_enc_update(rc, low, low + symbol, 1 << 15, 1);
+}
+
+int ff_opus_rc_dec_init(OpusRangeCoder *rc, const uint8_t *data, int size)
+{
+    int ret = init_get_bits8(&rc->gb, data, size);
+    if (ret < 0)
+        return ret;
+
+    rc->range = 128;
+    rc->value = 127 - get_bits(&rc->gb, 7);
+    rc->total_bits = 9;
+    opus_rc_dec_normalize(rc);
+
+    return 0;
+}
+
+void ff_opus_rc_dec_raw_init(OpusRangeCoder *rc, const uint8_t *rightend, uint32_t bytes)
+{
+    rc->rb.position = rightend;
+    rc->rb.bytes    = bytes;
+    rc->rb.cachelen = 0;
+    rc->rb.cacheval = 0;
+}
+
+void ff_opus_rc_enc_end(OpusRangeCoder *rc, uint8_t *dst, int size)
+{
+    int rng_bytes, bits = OPUS_RC_BITS - opus_ilog(rc->range);
+    uint32_t mask = (OPUS_RC_TOP - 1) >> bits;
+    uint32_t end = (rc->value + mask) & ~mask;
+
+    if ((end | mask) >= rc->value + rc->range) {
+        bits++;
+        mask >>= 1;
+        end = (rc->value + mask) & ~mask;
+    }
+
+    /* Finish what's left */
+    while (bits > 0) {
+        opus_rc_enc_carryout(rc, end >> OPUS_RC_SHIFT);
+        end = (end << OPUS_RC_SYM) & (OPUS_RC_TOP - 1);
+        bits -= OPUS_RC_SYM;
+    }
+
+    /* Flush out anything left or marked */
+    if (rc->rem >= 0 || rc->ext > 0)
+        opus_rc_enc_carryout(rc, 0);
+
+    rng_bytes = rc->rng_cur - rc->buf;
+    rc->waste = (size - (rc->rb.bytes + rng_bytes)) << 3;
+    memcpy(dst, rc->buf, rng_bytes);
+    memset(dst + rng_bytes, 0, FFMAX(rc->waste >> 3, 0) + 1);
+
+    /* Put the rawbits part, if any */
+    if (rc->rb.bytes || rc->rb.cachelen) {
+        int rawbytes = FFALIGN(rc->rb.bytes*8 + rc->rb.cachelen, 8) >> 3;
+        int dst_loc = FFMAX(size - rawbytes, 0);
+        uint8_t *src = rc->buf + OPUS_MAX_PACKET_SIZE + 12 - rawbytes;
+        ff_opus_rc_put_raw(rc, 0, 32 - rc->rb.cachelen);
+        dst[dst_loc] |= *src++;
+        memcpy(&dst[dst_loc + 1], src, rawbytes - 1);
+    }
+}
+
+void ff_opus_rc_enc_init(OpusRangeCoder *rc)
+{
+    rc->value = 0;
+    rc->range = OPUS_RC_TOP;
+    rc->total_bits = OPUS_RC_BITS + 1;
+    rc->rem = -1;
+    rc->ext =  0;
+    rc->rng_cur = rc->buf;
+    ff_opus_rc_dec_raw_init(rc, rc->buf + OPUS_MAX_PACKET_SIZE + 8, 0);
+}