FFmpeg
Loading...
Searching...
No Matches
elsdec.c
Go to the documentation of this file.
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. */
45static 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
227static 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
249void 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
278
279static 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
293int 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
352unsigned 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}
ctx
static AVFormatContext * ctx
Definition api-movenc-test.c:49
i
#define i(width, name, range_min, range_max)
Definition cbs_h264.c:63
bit
#define bit(string, value)
Definition cbs_mpeg2.c:56
NULL
#define NULL
Definition coverity.c:32
ELS_JOTS_PER_BYTE
#define ELS_JOTS_PER_BYTE
Definition elsdec.c:40
ff_els_decoder_init
void ff_els_decoder_init(ElsDecCtx *ctx, const uint8_t *in, size_t data_size)
Definition elsdec.c:249
ff_els_decode_bit
int ff_els_decode_bit(ElsDecCtx *ctx, uint8_t *rung)
Definition elsdec.c:293
els_exp_tab
static const uint32_t els_exp_tab[ELS_JOTS_PER_BYTE *4+1]
Definition elsdec.c:227
ff_els_decoder_uninit
void ff_els_decoder_uninit(ElsUnsignedRung *rung)
Definition elsdec.c:274
ELS_MAX
#define ELS_MAX
Definition elsdec.c:41
els_import_byte
static int els_import_byte(ElsDecCtx *ctx)
Definition elsdec.c:279
RUNG_SPACE
#define RUNG_SPACE
Definition elsdec.c:42
ff_els_decode_unsigned
unsigned ff_els_decode_unsigned(ElsDecCtx *ctx, ElsUnsignedRung *ur)
Definition elsdec.c:352
elsdec.h
Entropy Logarithmic-Scale binary arithmetic coder.
ELS_EXPGOLOMB_LEN
#define ELS_EXPGOLOMB_LEN
Definition elsdec.h:34
error.h
error code definitions
AVERROR_INVALIDDATA
#define AVERROR_INVALIDDATA
Invalid data found when processing input.
Definition error.h:61
AVERROR_EOF
#define AVERROR_EOF
End of file.
Definition error.h:57
AVERROR
#define AVERROR(e)
Definition error.h:45
av_reallocp
int av_reallocp(void *ptr, size_t size)
Allocate, reallocate, or free a block of memory through a pointer to a pointer.
Definition mem.c:188
r
#define r
Definition input.c:42
AV_RB24
#define AV_RB24(x)
Definition intreadwrite.h:440
AV_RB16
#define AV_RB16(p)
Definition intreadwrite.h:398
macros.h
Utility Preprocessor macros.
FFMIN
#define FFMIN(a, b)
Definition macros.h:49
mem.h
Memory handling functions.
av_realloc
#define av_realloc(p, s)
Definition ops_static.c:54
pos
unsigned int pos
Definition spdifenc.c:431
ElsRungNode::next_index
uint16_t next_index
Definition elsdec.h:45
ElsRungNode::rung
uint8_t rung
Definition elsdec.h:44
ElsUnsignedRung::avail_index
uint16_t avail_index
Definition elsdec.h:52
ElsUnsignedRung::rem_rung_list
ElsRungNode * rem_rung_list
Definition elsdec.h:50
ElsUnsignedRung::prefix_rung
uint8_t prefix_rung[ELS_EXPGOLOMB_LEN+1]
Definition elsdec.h:49
ElsUnsignedRung::rung_list_size
size_t rung_list_size
Definition elsdec.h:51
Ladder::ALps
int8_t ALps
Definition elsdec.c:47
Ladder::next1
uint8_t next1
Definition elsdec.c:49
Ladder::AMps
int8_t AMps
Definition elsdec.c:46
Ladder::next0
uint8_t next0
Definition elsdec.c:48
av_freep
#define av_freep(p)
Definition tableprint_vlc.h:35
Generated on Tue Sep 1 2026 19:20:52 for FFmpeg by doxygen 1.13.2