git.sesse.net Git - ffmpeg/blob - libavcodec/opus_rc.c

   1 /*
   2  * Copyright (c) 2012 Andrew D'Addesio
   3  * Copyright (c) 2013-2014 Mozilla Corporation
   4  * Copyright (c) 2016 Rostislav Pehlivanov <atomnuker@gmail.com>
   5  *
   6  * This file is part of FFmpeg.
   7  *
   8  * FFmpeg is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * FFmpeg is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with FFmpeg; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  21  */
  22
  23 #include "opus_rc.h"
  24
  25 #define OPUS_RC_BITS 32
  26 #define OPUS_RC_SYM  8
  27 #define OPUS_RC_CEIL ((1 << OPUS_RC_SYM) - 1)
  28 #define OPUS_RC_TOP (1u << 31)
  29 #define OPUS_RC_BOT (OPUS_RC_TOP >> OPUS_RC_SYM)
  30 #define OPUS_RC_SHIFT (OPUS_RC_BITS - OPUS_RC_SYM - 1)
  31
  32 static av_always_inline void opus_rc_dec_normalize(OpusRangeCoder *rc)
  33 {
  34     while (rc->range <= OPUS_RC_BOT) {
  35         rc->value = ((rc->value << OPUS_RC_SYM) | (get_bits(&rc->gb, OPUS_RC_SYM) ^ OPUS_RC_CEIL)) & (OPUS_RC_TOP - 1);
  36         rc->range     <<= OPUS_RC_SYM;
  37         rc->total_bits += OPUS_RC_SYM;
  38     }
  39 }
  40
  41 static av_always_inline void opus_rc_dec_update(OpusRangeCoder *rc, uint32_t scale,
  42                                                 uint32_t low, uint32_t high,
  43                                                 uint32_t total)
  44 {
  45     rc->value -= scale * (total - high);
  46     rc->range  = low ? scale * (high - low)
  47                       : rc->range - scale * (total - high);
  48     opus_rc_dec_normalize(rc);
  49 }
  50
  51 uint32_t ff_opus_rc_dec_cdf(OpusRangeCoder *rc, const uint16_t *cdf)
  52 {
  53     unsigned int k, scale, total, symbol, low, high;
  54
  55     total = *cdf++;
  56
  57     scale   = rc->range / total;
  58     symbol = rc->value / scale + 1;
  59     symbol = total - FFMIN(symbol, total);
  60
  61     for (k = 0; cdf[k] <= symbol; k++);
  62     high = cdf[k];
  63     low  = k ? cdf[k-1] : 0;
  64
  65     opus_rc_dec_update(rc, scale, low, high, total);
  66
  67     return k;
  68 }
  69
  70 uint32_t ff_opus_rc_dec_log(OpusRangeCoder *rc, uint32_t bits)
  71 {
  72     uint32_t k, scale;
  73     scale = rc->range >> bits; // in this case, scale = symbol
  74
  75     if (rc->value >= scale) {
  76         rc->value -= scale;
  77         rc->range -= scale;
  78         k = 0;
  79     } else {
  80         rc->range = scale;
  81         k = 1;
  82     }
  83     opus_rc_dec_normalize(rc);
  84     return k;
  85 }
  86
  87 /**
  88  * CELT: read 1-25 raw bits at the end of the frame, backwards byte-wise
  89  */
  90 uint32_t ff_opus_rc_get_raw(OpusRangeCoder *rc, uint32_t count)
  91 {
  92     uint32_t value = 0;
  93
  94     while (rc->rb.bytes && rc->rb.cachelen < count) {
  95         rc->rb.cacheval |= *--rc->rb.position << rc->rb.cachelen;
  96         rc->rb.cachelen += 8;
  97         rc->rb.bytes--;
  98     }
  99
 100     value = av_mod_uintp2(rc->rb.cacheval, count);
 101     rc->rb.cacheval    >>= count;
 102     rc->rb.cachelen     -= count;
 103     rc->total_bits      += count;
 104
 105     return value;
 106 }
 107
 108 /**
 109  * CELT: read a uniform distribution
 110  */
 111 uint32_t ff_opus_rc_dec_uint(OpusRangeCoder *rc, uint32_t size)
 112 {
 113     uint32_t bits, k, scale, total;
 114
 115     bits  = opus_ilog(size - 1);
 116     total = (bits > 8) ? ((size - 1) >> (bits - 8)) + 1 : size;
 117
 118     scale  = rc->range / total;
 119     k      = rc->value / scale + 1;
 120     k      = total - FFMIN(k, total);
 121     opus_rc_dec_update(rc, scale, k, k + 1, total);
 122
 123     if (bits > 8) {
 124         k = k << (bits - 8) | ff_opus_rc_get_raw(rc, bits - 8);
 125         return FFMIN(k, size - 1);
 126     } else
 127         return k;
 128 }
 129
 130 uint32_t ff_opus_rc_dec_uint_step(OpusRangeCoder *rc, int k0)
 131 {
 132     /* Use a probability of 3 up to itheta=8192 and then use 1 after */
 133     uint32_t k, scale, symbol, total = (k0+1)*3 + k0;
 134     scale  = rc->range / total;
 135     symbol = rc->value / scale + 1;
 136     symbol = total - FFMIN(symbol, total);
 137
 138     k = (symbol < (k0+1)*3) ? symbol/3 : symbol - (k0+1)*2;
 139
 140     opus_rc_dec_update(rc, scale, (k <= k0) ? 3*(k+0) : (k-1-k0) + 3*(k0+1),
 141                        (k <= k0) ? 3*(k+1) : (k-0-k0) + 3*(k0+1), total);
 142     return k;
 143 }
 144
 145 uint32_t ff_opus_rc_dec_uint_tri(OpusRangeCoder *rc, int qn)
 146 {
 147     uint32_t k, scale, symbol, total, low, center;
 148
 149     total = ((qn>>1) + 1) * ((qn>>1) + 1);
 150     scale   = rc->range / total;
 151     center = rc->value / scale + 1;
 152     center = total - FFMIN(center, total);
 153
 154     if (center < total >> 1) {
 155         k      = (ff_sqrt(8 * center + 1) - 1) >> 1;
 156         low    = k * (k + 1) >> 1;
 157         symbol = k + 1;
 158     } else {
 159         k      = (2*(qn + 1) - ff_sqrt(8*(total - center - 1) + 1)) >> 1;
 160         low    = total - ((qn + 1 - k) * (qn + 2 - k) >> 1);
 161         symbol = qn + 1 - k;
 162     }
 163
 164     opus_rc_dec_update(rc, scale, low, low + symbol, total);
 165
 166     return k;
 167 }
 168
 169 int ff_opus_rc_dec_laplace(OpusRangeCoder *rc, uint32_t symbol, int decay)
 170 {
 171     /* extends the range coder to model a Laplace distribution */
 172     int value = 0;
 173     uint32_t scale, low = 0, center;
 174
 175     scale  = rc->range >> 15;
 176     center = rc->value / scale + 1;
 177     center = (1 << 15) - FFMIN(center, 1 << 15);
 178
 179     if (center >= symbol) {
 180         value++;
 181         low = symbol;
 182         symbol = 1 + ((32768 - 32 - symbol) * (16384-decay) >> 15);
 183
 184         while (symbol > 1 && center >= low + 2 * symbol) {
 185             value++;
 186             symbol *= 2;
 187             low    += symbol;
 188             symbol  = (((symbol - 2) * decay) >> 15) + 1;
 189         }
 190
 191         if (symbol <= 1) {
 192             int distance = (center - low) >> 1;
 193             value += distance;
 194             low   += 2 * distance;
 195         }
 196
 197         if (center < low + symbol)
 198             value *= -1;
 199         else
 200             low += symbol;
 201     }
 202
 203     opus_rc_dec_update(rc, scale, low, FFMIN(low + symbol, 32768), 32768);
 204
 205     return value;
 206 }
 207
 208 int ff_opus_rc_dec_init(OpusRangeCoder *rc, const uint8_t *data, int size)
 209 {
 210     int ret = init_get_bits8(&rc->gb, data, size);
 211     if (ret < 0)
 212         return ret;
 213
 214     rc->range = 128;
 215     rc->value = 127 - get_bits(&rc->gb, 7);
 216     rc->total_bits = 9;
 217     opus_rc_dec_normalize(rc);
 218
 219     return 0;
 220 }
 221
 222 void ff_opus_rc_dec_raw_init(OpusRangeCoder *rc, const uint8_t *rightend, uint32_t bytes)
 223 {
 224     rc->rb.position = rightend;
 225     rc->rb.bytes    = bytes;
 226     rc->rb.cachelen = 0;
 227     rc->rb.cacheval = 0;
 228 }