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
ff_els_decoder_init(ElsDecCtx * ctx,const uint8_t * in,size_t data_size)249 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 if (data_size >= 3) {
255 ctx->x = AV_RB24(in);
256 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 ctx->in_buf = in + nbytes;
266 ctx->data_size = data_size - nbytes;
267 ctx->err = 0;
268 ctx->j = ELS_JOTS_PER_BYTE;
269 ctx->t = ELS_MAX;
270 ctx->diff = FFMIN(ELS_MAX - ctx->x,
271 ELS_MAX - els_exp_tab[ELS_JOTS_PER_BYTE * 4 - 1]);
272 }
273
ff_els_decoder_uninit(ElsUnsignedRung * rung)274 void ff_els_decoder_uninit(ElsUnsignedRung *rung)
275 {
276 av_freep(&rung->rem_rung_list);
277 }
278
els_import_byte(ElsDecCtx * ctx)279 static int els_import_byte(ElsDecCtx *ctx)
280 {
281 if (!ctx->data_size) {
282 ctx->err = AVERROR_EOF;
283 return AVERROR_EOF;
284 }
285 ctx->x = (ctx->x << 8) | *ctx->in_buf++;
286 ctx->data_size--;
287 ctx->j += ELS_JOTS_PER_BYTE;
288 ctx->t <<= 8;
289
290 return 0;
291 }
292
ff_els_decode_bit(ElsDecCtx * ctx,uint8_t * rung)293 int ff_els_decode_bit(ElsDecCtx *ctx, uint8_t *rung)
294 {
295 int z, bit, ret;
296 const uint32_t *pAllowable = &els_exp_tab[ELS_JOTS_PER_BYTE * 3];
297
298 if (ctx->err)
299 return 0;
300
301 z = pAllowable[ctx->j + Ladder[*rung].ALps];
302 ctx->t -= z;
303 ctx->diff -= z;
304 if (ctx->diff > 0)
305 return *rung & 1; /* shortcut for x < t > pAllowable[j - 1] */
306
307 if (ctx->t > ctx->x) { /* decode most probable symbol (MPS) */
308 ctx->j += Ladder[*rung].AMps;
309 while (ctx->t > pAllowable[ctx->j])
310 ctx->j++;
311
312 if (ctx->j <= 0) { /* MPS: import one byte from bytestream. */
313 ret = els_import_byte(ctx);
314 if (ret < 0)
315 return ret;
316 }
317
318 z = ctx->t;
319 bit = *rung & 1;
320 *rung = Ladder[*rung].next0;
321 } else { /* decode less probable symbol (LPS) */
322 ctx->x -= ctx->t;
323 ctx->t = z;
324
325 ctx->j += Ladder[*rung].ALps;
326 if (ctx->j <= 0) {
327 /* LPS: import one byte from bytestream. */
328 z <<= 8;
329 ret = els_import_byte(ctx);
330 if (ret < 0)
331 return ret;
332 if (ctx->j <= 0) {
333 /* LPS: import second byte from bytestream. */
334 z <<= 8;
335 ret = els_import_byte(ctx);
336 if (ret < 0)
337 return ret;
338 while (pAllowable[ctx->j - 1] >= z)
339 ctx->j--;
340 }
341 }
342
343 bit = !(*rung & 1);
344 *rung = Ladder[*rung].next1;
345 }
346
347 ctx->diff = FFMIN(z - ctx->x, z - pAllowable[ctx->j - 1]);
348
349 return bit;
350 }
351
ff_els_decode_unsigned(ElsDecCtx * ctx,ElsUnsignedRung * ur)352 unsigned ff_els_decode_unsigned(ElsDecCtx *ctx, ElsUnsignedRung *ur)
353 {
354 int i, n, r, bit;
355 ElsRungNode *rung_node;
356
357 if (ctx->err)
358 return 0;
359
360 /* decode unary prefix */
361 for (n = 0; n < ELS_EXPGOLOMB_LEN + 1; n++)
362 if (ff_els_decode_bit(ctx, &ur->prefix_rung[n]))
363 break;
364
365 /* handle the error/overflow case */
366 if (ctx->err || n >= ELS_EXPGOLOMB_LEN) {
367 ctx->err = AVERROR_INVALIDDATA;
368 return 0;
369 }
370
371 /* handle the zero case */
372 if (!n)
373 return 0;
374
375 /* initialize probability tree */
376 if (!ur->rem_rung_list) {
377 ur->rem_rung_list = av_realloc(NULL, RUNG_SPACE);
378 if (!ur->rem_rung_list) {
379 ctx->err = AVERROR(ENOMEM);
380 return 0;
381 }
382 memset(ur->rem_rung_list, 0, RUNG_SPACE);
383 ur->rung_list_size = RUNG_SPACE;
384 ur->avail_index = ELS_EXPGOLOMB_LEN;
385 }
386
387 /* decode the remainder */
388 for (i = 0, r = 0, bit = 0; i < n; i++) {
389 if (!i)
390 rung_node = &ur->rem_rung_list[n];
391 else {
392 if (!rung_node->next_index) {
393 if (ur->rung_list_size <= (ur->avail_index + 2) * sizeof(ElsRungNode)) {
394 // remember rung_node position
395 ptrdiff_t pos = rung_node - ur->rem_rung_list;
396 ctx->err = av_reallocp(&ur->rem_rung_list,
397 ur->rung_list_size +
398 RUNG_SPACE);
399 if (ctx->err < 0) {
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 }
423