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
ff_els_decoder_init(ElsDecCtx * ctx,const uint8_t * in,size_t data_size)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
ff_els_decoder_uninit(ElsUnsignedRung * rung)272 void ff_els_decoder_uninit(ElsUnsignedRung *rung)
273 {
274 av_freep(&rung->rem_rung_list);
275 }
276
els_import_byte(ElsDecCtx * ctx)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
ff_els_decode_bit(ElsDecCtx * ctx,uint8_t * rung)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
ff_els_decode_unsigned(ElsDecCtx * ctx,ElsUnsignedRung * ur)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 ctx->err = av_reallocp(&ur->rem_rung_list,
395 ur->rung_list_size +
396 RUNG_SPACE);
397 if (ctx->err < 0) {
398 return 0;
399 }
400 memset((uint8_t *) ur->rem_rung_list + ur->rung_list_size, 0,
401 RUNG_SPACE);
402 ur->rung_list_size += RUNG_SPACE;
403 // restore rung_node position in the new list
404 rung_node = &ur->rem_rung_list[pos];
405 }
406 rung_node->next_index = ur->avail_index;
407 ur->avail_index += 2;
408 }
409 rung_node = &ur->rem_rung_list[rung_node->next_index + bit];
410 }
411
412 bit = ff_els_decode_bit(ctx, &rung_node->rung);
413 if (ctx->err)
414 return bit;
415
416 r = (r << 1) + bit;
417 }
418
419 return (1 << n) - 1 + r; /* make value from exp golomb code */
420 }
421