FFmpeg coverage

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