FFmpeg coverage

Directory: ../../../ffmpeg/
File: src/libavcodec/opus/rc.c
Date: 2024-11-20 23:03:26
Exec Total Coverage
Lines: 115 235 48.9%
Functions: 11 23 47.8%
Branches: 36 84 42.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 "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 6431149 static av_always_inline void opus_rc_dec_normalize(OpusRangeCoder *rc)
48 {
49
2/2
✓ Branch 0 taken 2020540 times.
✓ Branch 1 taken 6431149 times.
 8451689 while (rc->range <= OPUS_RC_BOT) {
50 2020540 rc->value = ((rc->value << OPUS_RC_SYM) | (get_bits(&rc->gb, OPUS_RC_SYM) ^ OPUS_RC_CEIL)) & (OPUS_RC_TOP - 1);
51 2020540 rc->range <<= OPUS_RC_SYM;
52 2020540 rc->total_bits += OPUS_RC_SYM;
53 }
54 6431149 }
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 5155560 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 5155560 rc->value -= scale * (total - high);
71 8843583 rc->range = low ? scale * (high - low)
72
2/2
✓ Branch 0 taken 3688023 times.
✓ Branch 1 taken 1467537 times.
 5155560 : rc->range - scale * (total - high);
73 5155560 opus_rc_dec_normalize(rc);
74 5155560 }
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 2830955 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 2830955 total = *cdf++;
95
96 2830955 scale = rc->range / total;
97 2830955 symbol = rc->value / scale + 1;
98 2830955 symbol = total - FFMIN(symbol, total);
99
100
2/2
✓ Branch 0 taken 4302718 times.
✓ Branch 1 taken 2830955 times.
 7133673 for (k = 0; cdf[k] <= symbol; k++);
101 2830955 high = cdf[k];
102
2/2
✓ Branch 0 taken 1776696 times.
✓ Branch 1 taken 1054259 times.
 2830955 low = k ? cdf[k-1] : 0;
103
104 2830955 opus_rc_dec_update(rc, scale, low, high, total);
105
106 2830955 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 1241108 uint32_t ff_opus_rc_dec_log(OpusRangeCoder *rc, uint32_t bits)
115 {
116 uint32_t k, scale;
117 1241108 scale = rc->range >> bits; // in this case, scale = symbol
118
119
2/2
✓ Branch 0 taken 1132440 times.
✓ Branch 1 taken 108668 times.
 1241108 if (rc->value >= scale) {
120 1132440 rc->value -= scale;
121 1132440 rc->range -= scale;
122 1132440 k = 0;
123 } else {
124 108668 rc->range = scale;
125 108668 k = 1;
126 }
127 1241108 opus_rc_dec_normalize(rc);
128 1241108 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 1756685 uint32_t ff_opus_rc_get_raw(OpusRangeCoder *rc, uint32_t count)
141 {
142 1756685 uint32_t value = 0;
143
144
3/4
✓ Branch 0 taken 3064414 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1307729 times.
✓ Branch 3 taken 1756685 times.
 3064414 while (rc->rb.bytes && rc->rb.cachelen < count) {
145 1307729 rc->rb.cacheval |= *--rc->rb.position << rc->rb.cachelen;
146 1307729 rc->rb.cachelen += 8;
147 1307729 rc->rb.bytes--;
148 }
149
150 1756685 value = av_zero_extend(rc->rb.cacheval, count);
151 1756685 rc->rb.cacheval >>= count;
152 1756685 rc->rb.cachelen -= count;
153 1756685 rc->total_bits += count;
154
155 1756685 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_zero_extend(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_zero_extend(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 1092994 uint32_t ff_opus_rc_dec_uint(OpusRangeCoder *rc, uint32_t size)
183 {
184 uint32_t bits, k, scale, total;
185
186 1092994 bits = opus_ilog(size - 1);
187
2/2
✓ Branch 0 taken 782533 times.
✓ Branch 1 taken 310461 times.
 1092994 total = (bits > 8) ? ((size - 1) >> (bits - 8)) + 1 : size;
188
189 1092994 scale = rc->range / total;
190 1092994 k = rc->value / scale + 1;
191 1092994 k = total - FFMIN(k, total);
192 1092994 opus_rc_dec_update(rc, scale, k, k + 1, total);
193
194
2/2
✓ Branch 0 taken 782533 times.
✓ Branch 1 taken 310461 times.
 1092994 if (bits > 8) {
195 782533 k = k << (bits - 8) | ff_opus_rc_get_raw(rc, bits - 8);
196 782533 return FFMIN(k, size - 1);
197 } else
198 310461 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 138861 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 138861 uint32_t k, scale, symbol, total = (k0+1)*3 + k0;
215 138861 scale = rc->range / total;
216 138861 symbol = rc->value / scale + 1;
217 138861 symbol = total - FFMIN(symbol, total);
218
219
2/2
✓ Branch 0 taken 113202 times.
✓ Branch 1 taken 25659 times.
 138861 k = (symbol < (k0+1)*3) ? symbol/3 : symbol - (k0+1)*2;
220
221
2/2
✓ Branch 0 taken 113202 times.
✓ Branch 1 taken 25659 times.
 138861 opus_rc_dec_update(rc, scale, (k <= k0) ? 3*(k+0) : (k-1-k0) + 3*(k0+1),
222
2/2
✓ Branch 0 taken 113202 times.
✓ Branch 1 taken 25659 times.
 138861 (k <= k0) ? 3*(k+1) : (k-0-k0) + 3*(k0+1), total);
223 138861 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 245873 uint32_t ff_opus_rc_dec_uint_tri(OpusRangeCoder *rc, int qn)
235 {
236 uint32_t k, scale, symbol, total, low, center;
237
238 245873 total = ((qn>>1) + 1) * ((qn>>1) + 1);
239 245873 scale = rc->range / total;
240 245873 center = rc->value / scale + 1;
241 245873 center = total - FFMIN(center, total);
242
243
2/2
✓ Branch 0 taken 130144 times.
✓ Branch 1 taken 115729 times.
 245873 if (center < total >> 1) {
244 130144 k = (ff_sqrt(8 * center + 1) - 1) >> 1;
245 130144 low = k * (k + 1) >> 1;
246 130144 symbol = k + 1;
247 } else {
248 115729 k = (2*(qn + 1) - ff_sqrt(8*(total - center - 1) + 1)) >> 1;
249 115729 low = total - ((qn + 1 - k) * (qn + 2 - k) >> 1);
250 115729 symbol = qn + 1 - k;
251 }
252
253 245873 opus_rc_dec_update(rc, scale, low, low + symbol, total);
254
255 245873 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 846877 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 846877 int value = 0;
279 846877 uint32_t scale, low = 0, center;
280
281 846877 scale = rc->range >> 15;
282 846877 center = rc->value / scale + 1;
283 846877 center = (1 << 15) - FFMIN(center, 1 << 15);
284
285
2/2
✓ Branch 0 taken 498766 times.
✓ Branch 1 taken 348111 times.
 846877 if (center >= symbol) {
286 498766 value++;
287 498766 low = symbol;
288 498766 symbol = 1 + ((32768 - 32 - symbol) * (16384-decay) >> 15);
289
290
4/4
✓ Branch 0 taken 818969 times.
✓ Branch 1 taken 240 times.
✓ Branch 2 taken 320443 times.
✓ Branch 3 taken 498526 times.
 819209 while (symbol > 1 && center >= low + 2 * symbol) {
291 320443 value++;
292 320443 symbol *= 2;
293 320443 low += symbol;
294 320443 symbol = (((symbol - 2) * decay) >> 15) + 1;
295 }
296
297
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 498526 times.
 498766 if (symbol <= 1) {
298 240 int distance = (center - low) >> 1;
299 240 value += distance;
300 240 low += 2 * distance;
301 }
302
303
2/2
✓ Branch 0 taken 271153 times.
✓ Branch 1 taken 227613 times.
 498766 if (center < low + symbol)
304 271153 value *= -1;
305 else
306 227613 low += symbol;
307 }
308
309 846877 opus_rc_dec_update(rc, scale, low, FFMIN(low + symbol, 32768), 32768);
310
311 846877 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 34481 int ff_opus_rc_dec_init(OpusRangeCoder *rc, const uint8_t *data, int size)
339 {
340 34481 int ret = init_get_bits8(&rc->gb, data, size);
341
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 34481 times.
 34481 if (ret < 0)
342 ✗ return ret;
343
344 34481 rc->range = 128;
345 34481 rc->value = 127 - get_bits(&rc->gb, 7);
346 34481 rc->total_bits = 9;
347 34481 opus_rc_dec_normalize(rc);
348
349 34481 return 0;
350 }
351
352 29947 void ff_opus_rc_dec_raw_init(OpusRangeCoder *rc, const uint8_t *rightend, uint32_t bytes)
353 {
354 29947 rc->rb.position = rightend;
355 29947 rc->rb.bytes = bytes;
356 29947 rc->rb.cachelen = 0;
357 29947 rc->rb.cacheval = 0;
358 29947 }
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_FRAME_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_FRAME_SIZE + 8, 0);
411 ✗ }
412