FFmpeg coverage


Directory: ../../../ffmpeg/
File: src/libavcodec/elsdec.c
Date: 2021-09-24 03:35:22
Exec Total Coverage
Lines: 89 107 83.2%
Branches: 41 56 73.2%

Line Branch Exec Source
1 /*
2 * ELS (Entropy Logarithmic-Scale) decoder
3 *
4 * Copyright (c) 2013 Maxim Poliakovski
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 /**
24 * @file
25 * Entropy Logarithmic-Scale binary arithmetic decoder
26 */
27
28 #include <math.h>
29 #include <stdint.h>
30
31 #include "libavutil/common.h"
32 #include "libavutil/intreadwrite.h"
33
34 #include "elsdec.h"
35
36 /* ELS coder constants and structures. */
37 #define ELS_JOTS_PER_BYTE 36
38 #define ELS_MAX (1 << 24)
39 #define RUNG_SPACE (64 * sizeof(ElsRungNode))
40
41 /* ELS coder tables. */
42 static const struct Ladder {
43 int8_t AMps;
44 int8_t ALps;
45 uint8_t next0;
46 uint8_t next1;
47 } Ladder[174] = {
48 { -6, -5, 2, 1 },
49 { -2, -12, 3, 6 },
50 { -2, -12, 4, 6 },
51 { -1, -16, 7, 5 },
52 { -1, -16, 8, 10 },
53 { -5, -6, 11, 9 },
54 { -6, -5, 10, 5 },
55 { -1, -18, 13, 11 },
56 { -1, -18, 12, 14 },
57 { -6, -5, 15, 18 },
58 { -5, -6, 14, 9 },
59 { -3, -8, 17, 15 },
60 { -1, -20, 20, 16 },
61 { -1, -20, 23, 17 },
62 { -3, -8, 16, 18 },
63 { -5, -6, 19, 26 },
64 { -3, -9, 22, 24 },
65 { -3, -9, 21, 19 },
66 { -5, -6, 24, 26 },
67 { -4, -7, 27, 25 },
68 { -1, -22, 34, 28 },
69 { -2, -11, 29, 27 },
70 { -2, -11, 28, 30 },
71 { -1, -22, 39, 29 },
72 { -4, -7, 30, 32 },
73 { -6, -5, 33, 31 },
74 { -6, -5, 32, 25 },
75 { -3, -8, 35, 33 },
76 { -2, -12, 36, 38 },
77 { -2, -12, 37, 35 },
78 { -3, -8, 38, 40 },
79 { -6, -5, 41, 48 },
80 { -6, -5, 40, 31 },
81 { -5, -6, 43, 41 },
82 { -1, -24, 94, 42 },
83 { -3, -8, 45, 43 },
84 { -2, -12, 42, 44 },
85 { -2, -12, 47, 45 },
86 { -3, -8, 44, 46 },
87 { -1, -24, 125, 47 },
88 { -5, -6, 46, 48 },
89 { -6, -5, 49, 49 },
90 { -2, -13, 152, 164 },
91 { -4, -7, 51, 49 },
92 { -3, -9, 164, 168 },
93 { -3, -9, 55, 51 },
94 { -4, -7, 168, 170 },
95 { -2, -13, 67, 55 },
96 { -6, -5, 170, 49 },
97 { -6, -5, 51, 170 },
98 { -1, -72, 50, 74 },
99 { -4, -7, 53, 49 },
100 { -1, -61, 50, 74 },
101 { -3, -8, 55, 49 },
102 { -1, -51, 52, 76 },
103 { -3, -9, 57, 51 },
104 { -1, -46, 54, 76 },
105 { -2, -10, 59, 53 },
106 { -1, -43, 56, 78 },
107 { -2, -11, 61, 53 },
108 { -1, -41, 58, 80 },
109 { -2, -12, 63, 55 },
110 { -1, -39, 60, 82 },
111 { -2, -12, 65, 55 },
112 { -1, -37, 62, 84 },
113 { -2, -13, 67, 57 },
114 { -1, -36, 64, 86 },
115 { -1, -14, 69, 59 },
116 { -1, -35, 66, 88 },
117 { -1, -14, 71, 59 },
118 { -1, -34, 68, 90 },
119 { -1, -15, 73, 61 },
120 { -1, -33, 70, 92 },
121 { -1, -15, 75, 61 },
122 { -1, -32, 72, 94 },
123 { -1, -15, 77, 63 },
124 { -1, -31, 74, 96 },
125 { -1, -16, 79, 65 },
126 { -1, -31, 76, 98 },
127 { -1, -16, 81, 67 },
128 { -1, -30, 78, 100 },
129 { -1, -17, 83, 67 },
130 { -1, -29, 80, 102 },
131 { -1, -17, 85, 69 },
132 { -1, -29, 82, 104 },
133 { -1, -18, 87, 71 },
134 { -1, -28, 84, 104 },
135 { -1, -18, 89, 73 },
136 { -1, -28, 86, 108 },
137 { -1, -18, 91, 73 },
138 { -1, -27, 88, 108 },
139 { -1, -19, 93, 75 },
140 { -1, -27, 90, 112 },
141 { -1, -19, 95, 77 },
142 { -1, -26, 92, 112 },
143 { -1, -20, 97, 79 },
144 { -1, -26, 94, 114 },
145 { -1, -20, 99, 81 },
146 { -1, -25, 96, 116 },
147 { -1, -20, 101, 83 },
148 { -1, -25, 98, 118 },
149 { -1, -21, 103, 83 },
150 { -1, -24, 100, 120 },
151 { -1, -21, 105, 85 },
152 { -1, -24, 102, 122 },
153 { -1, -22, 107, 87 },
154 { -1, -23, 104, 124 },
155 { -1, -22, 109, 89 },
156 { -1, -23, 106, 126 },
157 { -1, -22, 111, 91 },
158 { -1, -22, 108, 128 },
159 { -1, -23, 113, 93 },
160 { -1, -22, 110, 130 },
161 { -1, -23, 115, 95 },
162 { -1, -22, 112, 132 },
163 { -1, -24, 117, 97 },
164 { -1, -21, 114, 134 },
165 { -1, -24, 119, 99 },
166 { -1, -21, 116, 136 },
167 { -1, -25, 121, 101 },
168 { -1, -20, 118, 136 },
169 { -1, -25, 123, 103 },
170 { -1, -20, 120, 138 },
171 { -1, -26, 125, 105 },
172 { -1, -20, 122, 140 },
173 { -1, -26, 127, 107 },
174 { -1, -19, 124, 142 },
175 { -1, -27, 129, 107 },
176 { -1, -19, 126, 144 },
177 { -1, -27, 131, 111 },
178 { -1, -18, 128, 146 },
179 { -1, -28, 133, 111 },
180 { -1, -18, 130, 146 },
181 { -1, -28, 135, 115 },
182 { -1, -18, 132, 148 },
183 { -1, -29, 137, 115 },
184 { -1, -17, 134, 150 },
185 { -1, -29, 139, 117 },
186 { -1, -17, 136, 152 },
187 { -1, -30, 141, 119 },
188 { -1, -16, 138, 152 },
189 { -1, -31, 143, 121 },
190 { -1, -16, 140, 154 },
191 { -1, -31, 145, 123 },
192 { -1, -15, 142, 156 },
193 { -1, -32, 147, 125 },
194 { -1, -15, 144, 158 },
195 { -1, -33, 149, 127 },
196 { -1, -15, 146, 158 },
197 { -1, -34, 151, 129 },
198 { -1, -14, 148, 160 },
199 { -1, -35, 153, 131 },
200 { -1, -14, 150, 160 },
201 { -1, -36, 155, 133 },
202 { -2, -13, 152, 162 },
203 { -1, -37, 157, 135 },
204 { -2, -12, 154, 164 },
205 { -1, -39, 159, 137 },
206 { -2, -12, 156, 164 },
207 { -1, -41, 161, 139 },
208 { -2, -11, 158, 166 },
209 { -1, -43, 163, 141 },
210 { -2, -10, 160, 166 },
211 { -1, -46, 165, 143 },
212 { -3, -9, 162, 168 },
213 { -1, -51, 167, 143 },
214 { -3, -8, 164, 170 },
215 { -1, -61, 169, 145 },
216 { -4, -7, 166, 170 },
217 { -1, -72, 169, 145 },
218 { -6, -5, 168, 49 },
219 { 0, -108, 171, 171 },
220 { 0, -108, 172, 172 },
221 { -6, -5, 173, 173 },
222 };
223
224 static const uint32_t els_exp_tab[ELS_JOTS_PER_BYTE * 4 + 1] = {
225 0, 0, 0, 0, 0, 0, 0, 0,
226 0, 0, 0, 0, 0, 0, 0, 0,
227 0, 0, 0, 0, 0, 0, 0, 0,
228 0, 0, 0, 0, 0, 0, 0, 0,
229 0, 0, 0, 0, 1, 1, 1, 1,
230 1, 2, 2, 2, 3, 4, 4, 5,
231 6, 7, 8, 10, 11, 13, 16, 18,
232 21, 25, 29, 34, 40, 47, 54, 64,
233 74, 87, 101, 118, 138, 161, 188, 219,
234 256, 298, 348, 406, 474, 552, 645, 752,
235 877, 1024, 1194, 1393, 1625, 1896, 2211, 2580,
236 3010, 3511, 4096, 4778, 5573, 6501, 7584, 8847,
237 10321, 12040, 14045, 16384, 19112, 22295, 26007, 30339,
238 35391, 41285, 48160, 56180, 65536, 76288, 89088, 103936,
239 121344, 141312, 165120, 192512, 224512, 262144, 305664, 356608,
240 416000, 485376, 566016, 660480, 770560, 898816, 1048576, 1223168,
241 1426688, 1664256, 1941504, 2264832, 2642176, 3082240, 3595520, 4194304,
242 4892672, 5707520, 6657792, 7766784, 9060096, 10568960, 12328960, 14382080,
243 16777216,
244 };
245
246 136 void ff_els_decoder_init(ElsDecCtx *ctx, const uint8_t *in, size_t data_size)
247 {
248 int nbytes;
249
250 /* consume up to 3 bytes from the input data */
251
1/2
✓ Branch 0 taken 136 times.
✗ Branch 1 not taken.
136 if (data_size >= 3) {
252 136 ctx->x = AV_RB24(in);
253 136 nbytes = 3;
254 } else if (data_size == 2) {
255 ctx->x = AV_RB16(in);
256 nbytes = 2;
257 } else {
258 ctx->x = *in;
259 nbytes = 1;
260 }
261
262 136 ctx->in_buf = in + nbytes;
263 136 ctx->data_size = data_size - nbytes;
264 136 ctx->err = 0;
265 136 ctx->j = ELS_JOTS_PER_BYTE;
266 136 ctx->t = ELS_MAX;
267 136 ctx->diff = FFMIN(ELS_MAX - ctx->x,
268 ELS_MAX - els_exp_tab[ELS_JOTS_PER_BYTE * 4 - 1]);
269 136 }
270
271 136 void ff_els_decoder_uninit(ElsUnsignedRung *rung)
272 {
273 136 av_freep(&rung->rem_rung_list);
274 136 }
275
276 104553 static int els_import_byte(ElsDecCtx *ctx)
277 {
278
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 104553 times.
104553 if (!ctx->data_size) {
279 ctx->err = AVERROR_EOF;
280 return AVERROR_EOF;
281 }
282 104553 ctx->x = (ctx->x << 8) | *ctx->in_buf++;
283 104553 ctx->data_size--;
284 104553 ctx->j += ELS_JOTS_PER_BYTE;
285 104553 ctx->t <<= 8;
286
287 104553 return 0;
288 }
289
290 1264774 int ff_els_decode_bit(ElsDecCtx *ctx, uint8_t *rung)
291 {
292 int z, bit, ret;
293 1264774 const uint32_t *pAllowable = &els_exp_tab[ELS_JOTS_PER_BYTE * 3];
294
295
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1264774 times.
1264774 if (ctx->err)
296 return 0;
297
298 1264774 z = pAllowable[ctx->j + Ladder[*rung].ALps];
299 1264774 ctx->t -= z;
300 1264774 ctx->diff -= z;
301
2/2
✓ Branch 0 taken 382255 times.
✓ Branch 1 taken 882519 times.
1264774 if (ctx->diff > 0)
302 382255 return *rung & 1; /* shortcut for x < t > pAllowable[j - 1] */
303
304
2/2
✓ Branch 0 taken 600153 times.
✓ Branch 1 taken 282366 times.
882519 if (ctx->t > ctx->x) { /* decode most probable symbol (MPS) */
305 600153 ctx->j += Ladder[*rung].AMps;
306
2/2
✓ Branch 0 taken 525033 times.
✓ Branch 1 taken 600153 times.
1125186 while (ctx->t > pAllowable[ctx->j])
307 525033 ctx->j++;
308
309
2/2
✓ Branch 0 taken 34972 times.
✓ Branch 1 taken 565181 times.
600153 if (ctx->j <= 0) { /* MPS: import one byte from bytestream. */
310 34972 ret = els_import_byte(ctx);
311
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 34972 times.
34972 if (ret < 0)
312 return ret;
313 }
314
315 600153 z = ctx->t;
316 600153 bit = *rung & 1;
317 600153 *rung = Ladder[*rung].next0;
318 } else { /* decode less probable symbol (LPS) */
319 282366 ctx->x -= ctx->t;
320 282366 ctx->t = z;
321
322 282366 ctx->j += Ladder[*rung].ALps;
323
2/2
✓ Branch 0 taken 69563 times.
✓ Branch 1 taken 212803 times.
282366 if (ctx->j <= 0) {
324 /* LPS: import one byte from bytestream. */
325 69563 z <<= 8;
326 69563 ret = els_import_byte(ctx);
327
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 69563 times.
69563 if (ret < 0)
328 return ret;
329
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 69545 times.
69563 if (ctx->j <= 0) {
330 /* LPS: import second byte from bytestream. */
331 18 z <<= 8;
332 18 ret = els_import_byte(ctx);
333
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
18 if (ret < 0)
334 return ret;
335
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 18 times.
20 while (pAllowable[ctx->j - 1] >= z)
336 2 ctx->j--;
337 }
338 }
339
340 282366 bit = !(*rung & 1);
341 282366 *rung = Ladder[*rung].next1;
342 }
343
344 882519 ctx->diff = FFMIN(z - ctx->x, z - pAllowable[ctx->j - 1]);
345
346 882519 return bit;
347 }
348
349 15033 unsigned ff_els_decode_unsigned(ElsDecCtx *ctx, ElsUnsignedRung *ur)
350 {
351 int i, n, r, bit;
352 ElsRungNode *rung_node;
353
354
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15033 times.
15033 if (ctx->err)
355 return 0;
356
357 /* decode unary prefix */
358
1/2
✓ Branch 0 taken 91011 times.
✗ Branch 1 not taken.
91011 for (n = 0; n < ELS_EXPGOLOMB_LEN + 1; n++)
359
2/2
✓ Branch 1 taken 15033 times.
✓ Branch 2 taken 75978 times.
91011 if (ff_els_decode_bit(ctx, &ur->prefix_rung[n]))
360 15033 break;
361
362 /* handle the error/overflow case */
363
2/4
✓ Branch 0 taken 15033 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 15033 times.
15033 if (ctx->err || n >= ELS_EXPGOLOMB_LEN) {
364 ctx->err = AVERROR_INVALIDDATA;
365 return 0;
366 }
367
368 /* handle the zero case */
369
2/2
✓ Branch 0 taken 1916 times.
✓ Branch 1 taken 13117 times.
15033 if (!n)
370 1916 return 0;
371
372 /* initialize probability tree */
373
2/2
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 12981 times.
13117 if (!ur->rem_rung_list) {
374 136 ur->rem_rung_list = av_realloc(NULL, RUNG_SPACE);
375
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 136 times.
136 if (!ur->rem_rung_list) {
376 ctx->err = AVERROR(ENOMEM);
377 return 0;
378 }
379 136 memset(ur->rem_rung_list, 0, RUNG_SPACE);
380 136 ur->rung_list_size = RUNG_SPACE;
381 136 ur->avail_index = ELS_EXPGOLOMB_LEN;
382 }
383
384 /* decode the remainder */
385
2/2
✓ Branch 0 taken 75978 times.
✓ Branch 1 taken 13117 times.
89095 for (i = 0, r = 0, bit = 0; i < n; i++) {
386
2/2
✓ Branch 0 taken 13117 times.
✓ Branch 1 taken 62861 times.
75978 if (!i)
387 13117 rung_node = &ur->rem_rung_list[n];
388 else {
389
2/2
✓ Branch 0 taken 6906 times.
✓ Branch 1 taken 55955 times.
62861 if (!rung_node->next_index) {
390
2/2
✓ Branch 0 taken 174 times.
✓ Branch 1 taken 6732 times.
6906 if (ur->rung_list_size <= (ur->avail_index + 2) * sizeof(ElsRungNode)) {
391 // remember rung_node position
392 174 ptrdiff_t pos = rung_node - ur->rem_rung_list;
393 348 ctx->err = av_reallocp(&ur->rem_rung_list,
394 174 ur->rung_list_size +
395 RUNG_SPACE);
396
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 174 times.
174 if (ctx->err < 0) {
397 return 0;
398 }
399 174 memset((uint8_t *) ur->rem_rung_list + ur->rung_list_size, 0,
400 RUNG_SPACE);
401 174 ur->rung_list_size += RUNG_SPACE;
402 // restore rung_node position in the new list
403 174 rung_node = &ur->rem_rung_list[pos];
404 }
405 6906 rung_node->next_index = ur->avail_index;
406 6906 ur->avail_index += 2;
407 }
408 62861 rung_node = &ur->rem_rung_list[rung_node->next_index + bit];
409 }
410
411 75978 bit = ff_els_decode_bit(ctx, &rung_node->rung);
412
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 75978 times.
75978 if (ctx->err)
413 return bit;
414
415 75978 r = (r << 1) + bit;
416 }
417
418 13117 return (1 << n) - 1 + r; /* make value from exp golomb code */
419 }
420