libavcodec/opus_rc.c

   1 /*
   2  * Copyright (c) 2012 Andrew D'Addesio
   3  * Copyright (c) 2013-2014 Mozilla Corporation
   4  * Copyright (c) 2017 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_enc_carryout(OpusRangeCoder *rc, int cbuf)
  33 {
  34     const int cb = cbuf >> OPUS_RC_SYM, mb = (OPUS_RC_CEIL + cb) & OPUS_RC_CEIL;
  35     if (cbuf == OPUS_RC_CEIL) {
  36         rc->ext++;
  37         return;
  38     }
  39     rc->rng_cur[0] = rc->rem + cb;
  40     rc->rng_cur += (rc->rem >= 0);
  41     for (; rc->ext > 0; rc->ext--)
  42         *rc->rng_cur++ = mb;
  43     av_assert0(rc->rng_cur < rc->rb.position);
  44     rc->rem = cbuf & OPUS_RC_CEIL; /* Propagate */
  45 }
  46
  47 static av_always_inline void opus_rc_dec_normalize(OpusRangeCoder *rc)
  48 {
  49     while (rc->range <= OPUS_RC_BOT) {
  50         rc->value = ((rc->value << OPUS_RC_SYM) | (get_bits(&rc->gb, OPUS_RC_SYM) ^ OPUS_RC_CEIL)) & (OPUS_RC_TOP - 1);
  51         rc->range     <<= OPUS_RC_SYM;
  52         rc->total_bits += OPUS_RC_SYM;
  53     }
  54 }
  55
  56 static av_always_inline void opus_rc_enc_normalize(OpusRangeCoder *rc)
  57 {
  58     while (rc->range <= OPUS_RC_BOT) {
  59         opus_rc_enc_carryout(rc, rc->value >> OPUS_RC_SHIFT);
  60         rc->value = (rc->value << OPUS_RC_SYM) & (OPUS_RC_TOP - 1);
  61         rc->range     <<= OPUS_RC_SYM;
  62         rc->total_bits += OPUS_RC_SYM;
  63     }
  64 }
  65
  66 static av_always_inline void opus_rc_dec_update(OpusRangeCoder *rc, uint32_t scale,
  67                                                 uint32_t low, uint32_t high,
  68                                                 uint32_t total)
  69 {
  70     rc->value -= scale * (total - high);
  71     rc->range  = low ? scale * (high - low)
  72                       : rc->range - scale * (total - high);
  73     opus_rc_dec_normalize(rc);
  74 }
  75
  76 /* Main encoding function, this needs to go fast */
  77 static av_always_inline void opus_rc_enc_update(OpusRangeCoder *rc, uint32_t b, uint32_t p,
  78                                                 uint32_t p_tot, const int ptwo)
  79 {
  80     uint32_t rscaled, cnd = !!b;
  81     if (ptwo) /* Whole function is inlined so hopefully branch is optimized out */
  82         rscaled = rc->range >> ff_log2(p_tot);
  83     else
  84         rscaled = rc->range/p_tot;
  85     rc->value +=    cnd*(rc->range - rscaled*(p_tot - b));
  86     rc->range  = (!cnd)*(rc->range - rscaled*(p_tot - p)) + cnd*rscaled*(p - b);
  87     opus_rc_enc_normalize(rc);
  88 }
  89
  90 uint32_t ff_opus_rc_dec_cdf(OpusRangeCoder *rc, const uint16_t *cdf)
  91 {
  92     unsigned int k, scale, total, symbol, low, high;
  93
  94     total = *cdf++;
  95
  96     scale   = rc->range / total;
  97     symbol = rc->value / scale + 1;
  98     symbol = total - FFMIN(symbol, total);
  99
 100     for (k = 0; cdf[k] <= symbol; k++);
 101     high = cdf[k];
 102     low  = k ? cdf[k-1] : 0;
 103
 104     opus_rc_dec_update(rc, scale, low, high, total);
 105
 106     return k;
 107 }
 108
 109 void ff_opus_rc_enc_cdf(OpusRangeCoder *rc, int val, const uint16_t *cdf)
 110 {
 111     opus_rc_enc_update(rc, cdf[val], cdf[val + 1], cdf[0], 1);
 112 }
 113
 114 uint32_t ff_opus_rc_dec_log(OpusRangeCoder *rc, uint32_t bits)
 115 {
 116     uint32_t k, scale;
 117     scale = rc->range >> bits; // in this case, scale = symbol
 118
 119     if (rc->value >= scale) {
 120         rc->value -= scale;
 121         rc->range -= scale;
 122         k = 0;
 123     } else {
 124         rc->range = scale;
 125         k = 1;
 126     }
 127     opus_rc_dec_normalize(rc);
 128     return k;
 129 }
 130
 131 void ff_opus_rc_enc_log(OpusRangeCoder *rc, int val, uint32_t bits)
 132 {
 133     bits = (1 << bits) - 1;
 134     opus_rc_enc_update(rc, (!!val)*bits, bits + !!val, bits + 1, 1);
 135 }
 136
 137 /**
 138  * CELT: read 1-25 raw bits at the end of the frame, backwards byte-wise
 139  */
 140 uint32_t ff_opus_rc_get_raw(OpusRangeCoder *rc, uint32_t count)
 141 {
 142     uint32_t value = 0;
 143
 144     while (rc->rb.bytes && rc->rb.cachelen < count) {
 145         rc->rb.cacheval |= *--rc->rb.position << rc->rb.cachelen;
 146         rc->rb.cachelen += 8;
 147         rc->rb.bytes--;
 148     }
 149
 150     value = av_mod_uintp2(rc->rb.cacheval, count);
 151     rc->rb.cacheval    >>= count;
 152     rc->rb.cachelen     -= count;
 153     rc->total_bits      += count;
 154
 155     return value;
 156 }
 157
 158 /**
 159  * CELT: write 0 - 31 bits to the rawbits buffer
 160  */
 161 void ff_opus_rc_put_raw(OpusRangeCoder *rc, uint32_t val, uint32_t count)
 162 {
 163     const int to_write = FFMIN(32 - rc->rb.cachelen, count);
 164
 165     rc->total_bits += count;
 166     rc->rb.cacheval |= av_mod_uintp2(val, to_write) << rc->rb.cachelen;
 167     rc->rb.cachelen = (rc->rb.cachelen + to_write) % 32;
 168
 169     if (!rc->rb.cachelen && count) {
 170         AV_WB32(rc->rb.position, rc->rb.cacheval);
 171         rc->rb.bytes    += 4;
 172         rc->rb.position -= 4;
 173         rc->rb.cachelen = count - to_write;
 174         rc->rb.cacheval = av_mod_uintp2(val >> to_write, rc->rb.cachelen);
 175         av_assert0(rc->rng_cur < rc->rb.position);
 176     }
 177 }
 178
 179 /**
 180  * CELT: read a uniform distribution
 181  */
 182 uint32_t ff_opus_rc_dec_uint(OpusRangeCoder *rc, uint32_t size)
 183 {
 184     uint32_t bits, k, scale, total;
 185
 186     bits  = opus_ilog(size - 1);
 187     total = (bits > 8) ? ((size - 1) >> (bits - 8)) + 1 : size;
 188
 189     scale  = rc->range / total;
 190     k      = rc->value / scale + 1;
 191     k      = total - FFMIN(k, total);
 192     opus_rc_dec_update(rc, scale, k, k + 1, total);
 193
 194     if (bits > 8) {
 195         k = k << (bits - 8) | ff_opus_rc_get_raw(rc, bits - 8);
 196         return FFMIN(k, size - 1);
 197     } else
 198         return k;
 199 }
 200
 201 /**
 202  * CELT: write a uniformly distributed integer
 203  */
 204 void ff_opus_rc_enc_uint(OpusRangeCoder *rc, uint32_t val, uint32_t size)
 205 {
 206     const int ps = FFMAX(opus_ilog(size - 1) - 8, 0);
 207     opus_rc_enc_update(rc, val >> ps, (val >> ps) + 1, ((size - 1) >> ps) + 1, 0);
 208     ff_opus_rc_put_raw(rc, val, ps);
 209 }
 210
 211 uint32_t ff_opus_rc_dec_uint_step(OpusRangeCoder *rc, int k0)
 212 {
 213     /* Use a probability of 3 up to itheta=8192 and then use 1 after */
 214     uint32_t k, scale, symbol, total = (k0+1)*3 + k0;
 215     scale  = rc->range / total;
 216     symbol = rc->value / scale + 1;
 217     symbol = total - FFMIN(symbol, total);
 218
 219     k = (symbol < (k0+1)*3) ? symbol/3 : symbol - (k0+1)*2;
 220
 221     opus_rc_dec_update(rc, scale, (k <= k0) ? 3*(k+0) : (k-1-k0) + 3*(k0+1),
 222                        (k <= k0) ? 3*(k+1) : (k-0-k0) + 3*(k0+1), total);
 223     return k;
 224 }
 225
 226 void ff_opus_rc_enc_uint_step(OpusRangeCoder *rc, uint32_t val, int k0)
 227 {
 228     const uint32_t a = val <= k0, b = 2*a + 1;
 229     k0 = (k0 + 1) << 1;
 230     val = b*(val + k0) - 3*a*k0;
 231     opus_rc_enc_update(rc, val, val + b, (k0 << 1) - 1, 0);
 232 }
 233
 234 uint32_t ff_opus_rc_dec_uint_tri(OpusRangeCoder *rc, int qn)
 235 {
 236     uint32_t k, scale, symbol, total, low, center;
 237
 238     total = ((qn>>1) + 1) * ((qn>>1) + 1);
 239     scale   = rc->range / total;
 240     center = rc->value / scale + 1;
 241     center = total - FFMIN(center, total);
 242
 243     if (center < total >> 1) {
 244         k      = (ff_sqrt(8 * center + 1) - 1) >> 1;
 245         low    = k * (k + 1) >> 1;
 246         symbol = k + 1;
 247     } else {
 248         k      = (2*(qn + 1) - ff_sqrt(8*(total - center - 1) + 1)) >> 1;
 249         low    = total - ((qn + 1 - k) * (qn + 2 - k) >> 1);
 250         symbol = qn + 1 - k;
 251     }
 252
 253     opus_rc_dec_update(rc, scale, low, low + symbol, total);
 254
 255     return k;
 256 }
 257
 258 void ff_opus_rc_enc_uint_tri(OpusRangeCoder *rc, uint32_t k, int qn)
 259 {
 260     uint32_t symbol, low, total;
 261
 262     total = ((qn>>1) + 1) * ((qn>>1) + 1);
 263
 264     if (k <= qn >> 1) {
 265         low    = k * (k + 1) >> 1;
 266         symbol = k + 1;
 267     } else {
 268         low    = total - ((qn + 1 - k) * (qn + 2 - k) >> 1);
 269         symbol = qn + 1 - k;
 270     }
 271
 272     opus_rc_enc_update(rc, low, low + symbol, total, 0);
 273 }
 274
 275 int ff_opus_rc_dec_laplace(OpusRangeCoder *rc, uint32_t symbol, int decay)
 276 {
 277     /* extends the range coder to model a Laplace distribution */
 278     int value = 0;
 279     uint32_t scale, low = 0, center;
 280
 281     scale  = rc->range >> 15;
 282     center = rc->value / scale + 1;
 283     center = (1 << 15) - FFMIN(center, 1 << 15);
 284
 285     if (center >= symbol) {
 286         value++;
 287         low = symbol;
 288         symbol = 1 + ((32768 - 32 - symbol) * (16384-decay) >> 15);
 289
 290         while (symbol > 1 && center >= low + 2 * symbol) {
 291             value++;
 292             symbol *= 2;
 293             low    += symbol;
 294             symbol  = (((symbol - 2) * decay) >> 15) + 1;
 295         }
 296
 297         if (symbol <= 1) {
 298             int distance = (center - low) >> 1;
 299             value += distance;
 300             low   += 2 * distance;
 301         }
 302
 303         if (center < low + symbol)
 304             value *= -1;
 305         else
 306             low += symbol;
 307     }
 308
 309     opus_rc_dec_update(rc, scale, low, FFMIN(low + symbol, 32768), 32768);
 310
 311     return value;
 312 }
 313
 314 void ff_opus_rc_enc_laplace(OpusRangeCoder *rc, int *value, uint32_t symbol, int decay)
 315 {
 316     uint32_t low = symbol;
 317     int i = 1, val = FFABS(*value), pos = *value > 0;
 318     if (!val) {
 319         opus_rc_enc_update(rc, 0, symbol, 1 << 15, 1);
 320         return;
 321     }
 322     symbol = ((32768 - 32 - symbol)*(16384 - decay)) >> 15;
 323     for (; i < val && symbol; i++) {
 324         low   += (symbol << 1) + 2;
 325         symbol = (symbol*decay) >> 14;
 326     }
 327     if (symbol) {
 328         low += (++symbol)*pos;
 329     } else {
 330         const int distance = FFMIN(val - i, (((32768 - low) - !pos) >> 1) - 1);
 331         low   += pos + (distance << 1);
 332         symbol = FFMIN(1, 32768 - low);
 333         *value = FFSIGN(*value)*(distance + i);
 334     }
 335     opus_rc_enc_update(rc, low, low + symbol, 1 << 15, 1);
 336 }
 337
 338 int ff_opus_rc_dec_init(OpusRangeCoder *rc, const uint8_t *data, int size)
 339 {
 340     int ret = init_get_bits8(&rc->gb, data, size);
 341     if (ret < 0)
 342         return ret;
 343
 344     rc->range = 128;
 345     rc->value = 127 - get_bits(&rc->gb, 7);
 346     rc->total_bits = 9;
 347     opus_rc_dec_normalize(rc);
 348
 349     return 0;
 350 }
 351
 352 void ff_opus_rc_dec_raw_init(OpusRangeCoder *rc, const uint8_t *rightend, uint32_t bytes)
 353 {
 354     rc->rb.position = rightend;
 355     rc->rb.bytes    = bytes;
 356     rc->rb.cachelen = 0;
 357     rc->rb.cacheval = 0;
 358 }
 359
 360 void ff_opus_rc_enc_end(OpusRangeCoder *rc, uint8_t *dst, int size)
 361 {
 362     int rng_bytes, bits = OPUS_RC_BITS - opus_ilog(rc->range);
 363     uint32_t mask = (OPUS_RC_TOP - 1) >> bits;
 364     uint32_t end = (rc->value + mask) & ~mask;
 365
 366     if ((end | mask) >= rc->value + rc->range) {
 367         bits++;
 368         mask >>= 1;
 369         end = (rc->value + mask) & ~mask;
 370     }
 371
 372     /* Finish what's left */
 373     while (bits > 0) {
 374         opus_rc_enc_carryout(rc, end >> OPUS_RC_SHIFT);
 375         end = (end << OPUS_RC_SYM) & (OPUS_RC_TOP - 1);
 376         bits -= OPUS_RC_SYM;
 377     }
 378
 379     /* Flush out anything left or marked */
 380     if (rc->rem >= 0 || rc->ext > 0)
 381         opus_rc_enc_carryout(rc, 0);
 382
 383     rng_bytes = rc->rng_cur - rc->buf;
 384     rc->waste = (size - (rc->rb.bytes + rng_bytes)) << 3;
 385     memcpy(dst, rc->buf, rng_bytes);
 386     memset(dst + rng_bytes, 0, FFMAX(rc->waste >> 3, 0) + 1);
 387
 388     /* Put the rawbits part, if any */
 389     if (rc->rb.bytes || rc->rb.cachelen) {
 390         int rawbytes = FFALIGN(rc->rb.bytes*8 + rc->rb.cachelen, 8) >> 3;
 391         int dst_loc = FFMAX(size - rawbytes, 0);
 392         uint8_t *src = rc->buf + OPUS_MAX_PACKET_SIZE + 12 - rawbytes;
 393         ff_opus_rc_put_raw(rc, 0, 32 - rc->rb.cachelen);
 394         dst[dst_loc] |= *src++;
 395         memcpy(&dst[dst_loc + 1], src, rawbytes - 1);
 396     }
 397 }
 398
 399 void ff_opus_rc_enc_init(OpusRangeCoder *rc)
 400 {
 401     rc->value = 0;
 402     rc->range = OPUS_RC_TOP;
 403     rc->total_bits = OPUS_RC_BITS + 1;
 404     rc->rem = -1;
 405     rc->ext =  0;
 406     rc->rng_cur = rc->buf;
 407     ff_opus_rc_dec_raw_init(rc, rc->buf + OPUS_MAX_PACKET_SIZE + 8, 0);
 408 }