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

15033
    if (ctx->err || n >= ELS_EXPGOLOMB_LEN) {
365
        ctx->err = AVERROR_INVALIDDATA;
366
        return 0;
367
    }
368
369
    /* handle the zero case */
370
15033
    if (!n)
371
1916
        return 0;
372
373
    /* initialize probability tree */
374
13117
    if (!ur->rem_rung_list) {
375
136
        ur->rem_rung_list = av_realloc(NULL, RUNG_SPACE);
376
136
        if (!ur->rem_rung_list) {
377
            ctx->err = AVERROR(ENOMEM);
378
            return 0;
379
        }
380
136
        memset(ur->rem_rung_list, 0, RUNG_SPACE);
381
136
        ur->rung_list_size = RUNG_SPACE;
382
136
        ur->avail_index    = ELS_EXPGOLOMB_LEN;
383
    }
384
385
    /* decode the remainder */
386
89095
    for (i = 0, r = 0, bit = 0; i < n; i++) {
387
75978
        if (!i)
388
13117
            rung_node = &ur->rem_rung_list[n];
389
        else {
390
62861
            if (!rung_node->next_index) {
391
6906
                if (ur->rung_list_size <= (ur->avail_index + 2) * sizeof(ElsRungNode)) {
392
                    // remember rung_node position
393
174
                    ptrdiff_t pos     = rung_node - ur->rem_rung_list;
394
348
                    ctx->err = av_reallocp(&ur->rem_rung_list,
395
174
                                                   ur->rung_list_size +
396
                                                   RUNG_SPACE);
397
174
                    if (ctx->err < 0) {
398
                        return 0;
399
                    }
400
174
                    memset((uint8_t *) ur->rem_rung_list + ur->rung_list_size, 0,
401
                           RUNG_SPACE);
402
174
                    ur->rung_list_size += RUNG_SPACE;
403
                    // restore rung_node position in the new list
404
174
                    rung_node = &ur->rem_rung_list[pos];
405
                }
406
6906
                rung_node->next_index = ur->avail_index;
407
6906
                ur->avail_index      += 2;
408
            }
409
62861
            rung_node = &ur->rem_rung_list[rung_node->next_index + bit];
410
        }
411
412
75978
        bit = ff_els_decode_bit(ctx, &rung_node->rung);
413
75978
        if (ctx->err)
414
            return bit;
415
416
75978
        r = (r << 1) + bit;
417
    }
418
419
13117
    return (1 << n) - 1 + r; /* make value from exp golomb code */
420
}