| /* |
| * 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, (!!val)*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((uint8_t *)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; |
| memcpy(dst, rc->buf, rng_bytes); |
| |
| rc->waste = size*8 - (rc->rb.bytes*8 + rc->rb.cachelen) - rng_bytes*8; |
| |
| /* Put the rawbits part, if any */ |
| if (rc->rb.bytes || rc->rb.cachelen) { |
| int i, lap; |
| uint8_t *rb_src, *rb_dst; |
| ff_opus_rc_put_raw(rc, 0, 32 - rc->rb.cachelen); |
| rb_src = rc->buf + OPUS_MAX_PACKET_SIZE + 12 - rc->rb.bytes; |
| rb_dst = dst + FFMAX(size - rc->rb.bytes, 0); |
| lap = &dst[rng_bytes] - rb_dst; |
| for (i = 0; i < lap; i++) |
| rb_dst[i] |= rb_src[i]; |
| memcpy(&rb_dst[lap], &rb_src[lap], FFMAX(rc->rb.bytes - lap, 0)); |
| } |
| } |
| |
| 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); |
| } |