Deprecate avctx.coded_frame
[ffmpeg.git] / libavcodec / elsdec.c
1 /*
2  * ELS (Entropy Logarithmic-Scale) decoder
3  *
4  * Copyright (c) 2013 Maxim Poliakovski
5  *
6  * This file is part of Libav.
7  *
8  * Libav 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  * Libav 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 Libav; 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 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     if (data_size >= 3) {
253         ctx->x = AV_RB24(in);
254         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     ctx->in_buf    = in + nbytes;
264     ctx->data_size = data_size - nbytes;
265     ctx->err       = 0;
266     ctx->j         = ELS_JOTS_PER_BYTE;
267     ctx->t         = ELS_MAX;
268     ctx->diff      = FFMIN(ELS_MAX - ctx->x,
269                            ELS_MAX - els_exp_tab[ELS_JOTS_PER_BYTE * 4 - 1]);
270 }
271
272 void ff_els_decoder_uninit(ElsUnsignedRung *rung)
273 {
274     av_free(rung->rem_rung_list);
275 }
276
277 static int els_import_byte(ElsDecCtx *ctx)
278 {
279     if (!ctx->data_size) {
280         ctx->err = AVERROR_EOF;
281         return AVERROR_EOF;
282     }
283     ctx->x   = (ctx->x << 8) | *ctx->in_buf++;
284     ctx->data_size--;
285     ctx->j  += ELS_JOTS_PER_BYTE;
286     ctx->t <<= 8;
287
288     return 0;
289 }
290
291 int ff_els_decode_bit(ElsDecCtx *ctx, uint8_t *rung)
292 {
293     int z, bit, ret;
294     const uint32_t *pAllowable = &els_exp_tab[ELS_JOTS_PER_BYTE * 3];
295
296     if (ctx->err)
297         return 0;
298
299     z          = pAllowable[ctx->j + Ladder[*rung].ALps];
300     ctx->t    -= z;
301     ctx->diff -= z;
302     if (ctx->diff > 0)
303         return *rung & 1;   /* shortcut for x < t > pAllowable[j - 1] */
304
305     if (ctx->t > ctx->x) {  /* decode most probable symbol (MPS) */
306         ctx->j += Ladder[*rung].AMps;
307         while (ctx->t > pAllowable[ctx->j])
308             ctx->j++;
309
310         if (ctx->j <= 0) { /* MPS: import one byte from bytestream. */
311             ret = els_import_byte(ctx);
312             if (ret < 0)
313                 return ret;
314         }
315
316         z     = ctx->t;
317         bit   = *rung & 1;
318         *rung = Ladder[*rung].next0;
319     } else { /* decode less probable symbol (LPS) */
320         ctx->x -= ctx->t;
321         ctx->t  = z;
322
323         ctx->j += Ladder[*rung].ALps;
324         if (ctx->j <= 0) {
325             /* LPS: import one byte from bytestream. */
326             z <<= 8;
327             ret = els_import_byte(ctx);
328             if (ret < 0)
329                 return ret;
330             if (ctx->j <= 0) {
331                 /* LPS: import second byte from bytestream. */
332                 z <<= 8;
333                 ret = els_import_byte(ctx);
334                 if (ret < 0)
335                     return ret;
336                 while (pAllowable[ctx->j - 1] >= z)
337                     ctx->j--;
338             }
339         }
340
341         bit   = !(*rung & 1);
342         *rung = Ladder[*rung].next1;
343     }
344
345     ctx->diff = FFMIN(z - ctx->x, z - pAllowable[ctx->j - 1]);
346
347     return bit;
348 }
349
350 unsigned ff_els_decode_unsigned(ElsDecCtx *ctx, ElsUnsignedRung *ur)
351 {
352     int i, n, r, bit;
353     ElsRungNode *rung_node;
354
355     if (ctx->err)
356         return 0;
357
358     /* decode unary prefix */
359     for (n = 0; n < ELS_EXPGOLOMB_LEN + 1; n++)
360         if (ff_els_decode_bit(ctx, &ur->prefix_rung[n]))
361             break;
362
363     /* handle the error/overflow case */
364     if (ctx->err || n >= ELS_EXPGOLOMB_LEN) {
365         ctx->err = AVERROR_INVALIDDATA;
366         return 0;
367     }
368
369     /* handle the zero case */
370     if (!n)
371         return 0;
372
373     /* initialize probability tree */
374     if (!ur->rem_rung_list) {
375         ur->rem_rung_list = av_realloc(NULL, RUNG_SPACE);
376         if (!ur->rem_rung_list) {
377             ctx->err = AVERROR(ENOMEM);
378             return 0;
379         }
380         memset(ur->rem_rung_list, 0, RUNG_SPACE);
381         ur->rung_list_size = RUNG_SPACE;
382         ur->avail_index    = ELS_EXPGOLOMB_LEN;
383     }
384
385     /* decode the remainder */
386     for (i = 0, r = 0, bit = 0; i < n; i++) {
387         if (!i)
388             rung_node = &ur->rem_rung_list[n];
389         else {
390             if (!rung_node->next_index) {
391                 if (ur->rung_list_size <= (ur->avail_index + 2) * sizeof(ElsRungNode)) {
392                     // remember rung_node position
393                     ptrdiff_t pos     = rung_node - ur->rem_rung_list;
394                     ur->rem_rung_list = av_realloc(ur->rem_rung_list,
395                                                    ur->rung_list_size +
396                                                    RUNG_SPACE);
397                     if (!ur->rem_rung_list) {
398                         av_free(ur->rem_rung_list);
399                         ctx->err = AVERROR(ENOMEM);
400                         return 0;
401                     }
402                     memset((uint8_t *) ur->rem_rung_list + ur->rung_list_size, 0,
403                            RUNG_SPACE);
404                     ur->rung_list_size += RUNG_SPACE;
405                     // restore rung_node position in the new list
406                     rung_node = &ur->rem_rung_list[pos];
407                 }
408                 rung_node->next_index = ur->avail_index;
409                 ur->avail_index      += 2;
410             }
411             rung_node = &ur->rem_rung_list[rung_node->next_index + bit];
412         }
413
414         bit = ff_els_decode_bit(ctx, &rung_node->rung);
415         if (ctx->err)
416             return bit;
417
418         r = (r << 1) + bit;
419     }
420
421     return (1 << n) - 1 + r; /* make value from exp golomb code */
422 }