FFmpeg
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. */
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 
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 
274 void ff_els_decoder_uninit(ElsUnsignedRung *rung)
275 {
276  av_freep(&rung->rem_rung_list);
277 }
278 
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 
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 
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 }
ff_els_decode_unsigned
unsigned ff_els_decode_unsigned(ElsDecCtx *ctx, ElsUnsignedRung *ur)
Definition: elsdec.c:352
ff_els_decode_bit
int ff_els_decode_bit(ElsDecCtx *ctx, uint8_t *rung)
Definition: elsdec.c:293
r
const char * r
Definition: vf_curves.c:126
AVERROR
Filter the word “frame” indicates either a video frame or a group of audio as stored in an AVFrame structure Format for each input and each output the list of supported formats For video that means pixel format For audio that means channel sample they are references to shared objects When the negotiation mechanism computes the intersection of the formats supported at each end of a all references to both lists are replaced with a reference to the intersection And when a single format is eventually chosen for a link amongst the remaining all references to the list are updated That means that if a filter requires that its input and output have the same format amongst a supported all it has to do is use a reference to the same list of formats query_formats can leave some formats unset and return AVERROR(EAGAIN) to cause the negotiation mechanism toagain later. That can be used by filters with complex requirements to use the format negotiated on one link to set the formats supported on another. Frame references ownership and permissions
ff_els_decoder_init
void ff_els_decoder_init(ElsDecCtx *ctx, const uint8_t *in, size_t data_size)
Definition: elsdec.c:249
AVERROR_EOF
#define AVERROR_EOF
End of file.
Definition: error.h:57
ElsRungNode::rung
uint8_t rung
Definition: elsdec.h:44
ELS_JOTS_PER_BYTE
#define ELS_JOTS_PER_BYTE
Definition: elsdec.c:40
Ladder
Definition: elsdec.c:45
els_exp_tab
static const uint32_t els_exp_tab[ELS_JOTS_PER_BYTE *4+1]
Definition: elsdec.c:227
RUNG_SPACE
#define RUNG_SPACE
Definition: elsdec.c:42
ElsRungNode::next_index
uint16_t next_index
Definition: elsdec.h:45
bit
#define bit(string, value)
Definition: cbs_mpeg2.c:58
ElsUnsignedRung::avail_index
uint16_t avail_index
Definition: elsdec.h:52
macros.h
Ladder::ALps
int8_t ALps
Definition: elsdec.c:47
intreadwrite.h
ctx
AVFormatContext * ctx
Definition: movenc.c:48
Ladder::next0
uint8_t next0
Definition: elsdec.c:48
NULL
#define NULL
Definition: coverity.c:32
av_realloc
void * av_realloc(void *ptr, size_t size)
Allocate, reallocate, or free a block of memory.
Definition: mem.c:153
error.h
ElsRungNode
Definition: elsdec.h:43
Ladder::next1
uint8_t next1
Definition: elsdec.c:49
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:186
ElsUnsignedRung
Definition: elsdec.h:48
ELS_EXPGOLOMB_LEN
#define ELS_EXPGOLOMB_LEN
Definition: elsdec.h:34
ElsDecCtx
Definition: elsdec.h:36
ElsUnsignedRung::rem_rung_list
ElsRungNode * rem_rung_list
Definition: elsdec.h:50
ff_els_decoder_uninit
void ff_els_decoder_uninit(ElsUnsignedRung *rung)
Definition: elsdec.c:274
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:269
ElsUnsignedRung::rung_list_size
size_t rung_list_size
Definition: elsdec.h:51
FFMIN
#define FFMIN(a, b)
Definition: macros.h:49
ret
ret
Definition: filter_design.txt:187
pos
unsigned int pos
Definition: spdifenc.c:412
mem.h
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:34
AVERROR_INVALIDDATA
#define AVERROR_INVALIDDATA
Invalid data found when processing input.
Definition: error.h:61
ELS_MAX
#define ELS_MAX
Definition: elsdec.c:41
Ladder::AMps
int8_t AMps
Definition: elsdec.c:46
AV_RB24
uint64_t_TMPL AV_WL64 unsigned int_TMPL AV_WL32 unsigned int_TMPL AV_WL24 unsigned int_TMPL AV_WL16 uint64_t_TMPL AV_WB64 unsigned int_TMPL AV_WB32 unsigned int_TMPL AV_RB24
Definition: bytestream.h:97
els_import_byte
static int els_import_byte(ElsDecCtx *ctx)
Definition: elsdec.c:279
AV_RB16
uint64_t_TMPL AV_WL64 unsigned int_TMPL AV_WL32 unsigned int_TMPL AV_WL24 unsigned int_TMPL AV_WL16 uint64_t_TMPL AV_WB64 unsigned int_TMPL AV_WB32 unsigned int_TMPL AV_WB24 unsigned int_TMPL AV_RB16
Definition: bytestream.h:98
ElsUnsignedRung::prefix_rung
uint8_t prefix_rung[ELS_EXPGOLOMB_LEN+1]
Definition: elsdec.h:49
elsdec.h
Generated on Sat Dec 3 2022 19:21:15 for FFmpeg by   doxygen 1.8.17