LCOV - code coverage report
Current view: top level - libavcodec - opus_rc.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 115 235 48.9 %
Date: 2017-12-15 18:13:28 Functions: 11 23 47.8 %

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

Generated by: LCOV version 1.13