GCC Code Coverage Report
Directory: ../../../ffmpeg/ Exec Total Coverage
File: src/libavcodec/opus_rc.c Lines: 115 225 51.1 %
Date: 2019-11-18 18:00:01 Branches: 36 86 41.9 %

Line Branch Exec Source
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
6396408
static av_always_inline void opus_rc_dec_normalize(OpusRangeCoder *rc)
48
{
49
8408650
    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
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
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
5122912
                      : 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
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
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
7063788
    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
void ff_opus_rc_enc_cdf(OpusRangeCoder *rc, int val, const uint16_t *cdf)
110
{
111
    opus_rc_enc_update(rc, (!!val)*cdf[val], cdf[val + 1], cdf[0], 1);
112
}
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
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
1753519
uint32_t ff_opus_rc_get_raw(OpusRangeCoder *rc, uint32_t count)
141
{
142
1753519
    uint32_t value = 0;
143
144

3057726
    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
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((uint8_t *)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
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
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
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
138754
    opus_rc_dec_update(rc, scale, (k <= k0) ? 3*(k+0) : (k-1-k0) + 3*(k0+1),
222
138754
                       (k <= k0) ? 3*(k+1) : (k-0-k0) + 3*(k0+1), total);
223
138754
    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
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
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
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

818173
        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
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
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
        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
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
    memcpy(dst, rc->buf, rng_bytes);
385
386
    rc->waste = size*8 - (rc->rb.bytes*8 + rc->rb.cachelen) - rng_bytes*8;
387
388
    /* Put the rawbits part, if any */
389
    if (rc->rb.bytes || rc->rb.cachelen) {
390
        int i, lap;
391
        uint8_t *rb_src, *rb_dst;
392
        ff_opus_rc_put_raw(rc, 0, 32 - rc->rb.cachelen);
393
        rb_src = rc->buf + OPUS_MAX_PACKET_SIZE + 12 - rc->rb.bytes;
394
        rb_dst = dst + FFMAX(size - rc->rb.bytes, 0);
395
        lap = &dst[rng_bytes] - rb_dst;
396
        for (i = 0; i < lap; i++)
397
            rb_dst[i] |= rb_src[i];
398
        memcpy(&rb_dst[lap], &rb_src[lap], FFMAX(rc->rb.bytes - lap, 0));
399
    }
400
}
401
402
void ff_opus_rc_enc_init(OpusRangeCoder *rc)
403
{
404
    rc->value = 0;
405
    rc->range = OPUS_RC_TOP;
406
    rc->total_bits = OPUS_RC_BITS + 1;
407
    rc->rem = -1;
408
    rc->ext =  0;
409
    rc->rng_cur = rc->buf;
410
    ff_opus_rc_dec_raw_init(rc, rc->buf + OPUS_MAX_PACKET_SIZE + 8, 0);
411
}