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 <math.h>
29 #include <stdint.h>
30 
31 #include "libavutil/common.h"
32 #include "libavutil/intreadwrite.h"
33 
34 #include "elsdec.h"
35 
36 /* ELS coder constants and structures. */
37 #define ELS_JOTS_PER_BYTE 36
38 #define ELS_MAX (1 << 24)
39 #define RUNG_SPACE (64 * sizeof(ElsRungNode))
40 
41 /* ELS coder tables. */
42 static const struct Ladder {
43  int8_t AMps;
44  int8_t ALps;
45  uint8_t next0;
46  uint8_t next1;
47 } Ladder[174] = {
48  { -6, -5, 2, 1 },
49  { -2, -12, 3, 6 },
50  { -2, -12, 4, 6 },
51  { -1, -16, 7, 5 },
52  { -1, -16, 8, 10 },
53  { -5, -6, 11, 9 },
54  { -6, -5, 10, 5 },
55  { -1, -18, 13, 11 },
56  { -1, -18, 12, 14 },
57  { -6, -5, 15, 18 },
58  { -5, -6, 14, 9 },
59  { -3, -8, 17, 15 },
60  { -1, -20, 20, 16 },
61  { -1, -20, 23, 17 },
62  { -3, -8, 16, 18 },
63  { -5, -6, 19, 26 },
64  { -3, -9, 22, 24 },
65  { -3, -9, 21, 19 },
66  { -5, -6, 24, 26 },
67  { -4, -7, 27, 25 },
68  { -1, -22, 34, 28 },
69  { -2, -11, 29, 27 },
70  { -2, -11, 28, 30 },
71  { -1, -22, 39, 29 },
72  { -4, -7, 30, 32 },
73  { -6, -5, 33, 31 },
74  { -6, -5, 32, 25 },
75  { -3, -8, 35, 33 },
76  { -2, -12, 36, 38 },
77  { -2, -12, 37, 35 },
78  { -3, -8, 38, 40 },
79  { -6, -5, 41, 48 },
80  { -6, -5, 40, 31 },
81  { -5, -6, 43, 41 },
82  { -1, -24, 94, 42 },
83  { -3, -8, 45, 43 },
84  { -2, -12, 42, 44 },
85  { -2, -12, 47, 45 },
86  { -3, -8, 44, 46 },
87  { -1, -24, 125, 47 },
88  { -5, -6, 46, 48 },
89  { -6, -5, 49, 49 },
90  { -2, -13, 152, 164 },
91  { -4, -7, 51, 49 },
92  { -3, -9, 164, 168 },
93  { -3, -9, 55, 51 },
94  { -4, -7, 168, 170 },
95  { -2, -13, 67, 55 },
96  { -6, -5, 170, 49 },
97  { -6, -5, 51, 170 },
98  { -1, -72, 50, 74 },
99  { -4, -7, 53, 49 },
100  { -1, -61, 50, 74 },
101  { -3, -8, 55, 49 },
102  { -1, -51, 52, 76 },
103  { -3, -9, 57, 51 },
104  { -1, -46, 54, 76 },
105  { -2, -10, 59, 53 },
106  { -1, -43, 56, 78 },
107  { -2, -11, 61, 53 },
108  { -1, -41, 58, 80 },
109  { -2, -12, 63, 55 },
110  { -1, -39, 60, 82 },
111  { -2, -12, 65, 55 },
112  { -1, -37, 62, 84 },
113  { -2, -13, 67, 57 },
114  { -1, -36, 64, 86 },
115  { -1, -14, 69, 59 },
116  { -1, -35, 66, 88 },
117  { -1, -14, 71, 59 },
118  { -1, -34, 68, 90 },
119  { -1, -15, 73, 61 },
120  { -1, -33, 70, 92 },
121  { -1, -15, 75, 61 },
122  { -1, -32, 72, 94 },
123  { -1, -15, 77, 63 },
124  { -1, -31, 74, 96 },
125  { -1, -16, 79, 65 },
126  { -1, -31, 76, 98 },
127  { -1, -16, 81, 67 },
128  { -1, -30, 78, 100 },
129  { -1, -17, 83, 67 },
130  { -1, -29, 80, 102 },
131  { -1, -17, 85, 69 },
132  { -1, -29, 82, 104 },
133  { -1, -18, 87, 71 },
134  { -1, -28, 84, 104 },
135  { -1, -18, 89, 73 },
136  { -1, -28, 86, 108 },
137  { -1, -18, 91, 73 },
138  { -1, -27, 88, 108 },
139  { -1, -19, 93, 75 },
140  { -1, -27, 90, 112 },
141  { -1, -19, 95, 77 },
142  { -1, -26, 92, 112 },
143  { -1, -20, 97, 79 },
144  { -1, -26, 94, 114 },
145  { -1, -20, 99, 81 },
146  { -1, -25, 96, 116 },
147  { -1, -20, 101, 83 },
148  { -1, -25, 98, 118 },
149  { -1, -21, 103, 83 },
150  { -1, -24, 100, 120 },
151  { -1, -21, 105, 85 },
152  { -1, -24, 102, 122 },
153  { -1, -22, 107, 87 },
154  { -1, -23, 104, 124 },
155  { -1, -22, 109, 89 },
156  { -1, -23, 106, 126 },
157  { -1, -22, 111, 91 },
158  { -1, -22, 108, 128 },
159  { -1, -23, 113, 93 },
160  { -1, -22, 110, 130 },
161  { -1, -23, 115, 95 },
162  { -1, -22, 112, 132 },
163  { -1, -24, 117, 97 },
164  { -1, -21, 114, 134 },
165  { -1, -24, 119, 99 },
166  { -1, -21, 116, 136 },
167  { -1, -25, 121, 101 },
168  { -1, -20, 118, 136 },
169  { -1, -25, 123, 103 },
170  { -1, -20, 120, 138 },
171  { -1, -26, 125, 105 },
172  { -1, -20, 122, 140 },
173  { -1, -26, 127, 107 },
174  { -1, -19, 124, 142 },
175  { -1, -27, 129, 107 },
176  { -1, -19, 126, 144 },
177  { -1, -27, 131, 111 },
178  { -1, -18, 128, 146 },
179  { -1, -28, 133, 111 },
180  { -1, -18, 130, 146 },
181  { -1, -28, 135, 115 },
182  { -1, -18, 132, 148 },
183  { -1, -29, 137, 115 },
184  { -1, -17, 134, 150 },
185  { -1, -29, 139, 117 },
186  { -1, -17, 136, 152 },
187  { -1, -30, 141, 119 },
188  { -1, -16, 138, 152 },
189  { -1, -31, 143, 121 },
190  { -1, -16, 140, 154 },
191  { -1, -31, 145, 123 },
192  { -1, -15, 142, 156 },
193  { -1, -32, 147, 125 },
194  { -1, -15, 144, 158 },
195  { -1, -33, 149, 127 },
196  { -1, -15, 146, 158 },
197  { -1, -34, 151, 129 },
198  { -1, -14, 148, 160 },
199  { -1, -35, 153, 131 },
200  { -1, -14, 150, 160 },
201  { -1, -36, 155, 133 },
202  { -2, -13, 152, 162 },
203  { -1, -37, 157, 135 },
204  { -2, -12, 154, 164 },
205  { -1, -39, 159, 137 },
206  { -2, -12, 156, 164 },
207  { -1, -41, 161, 139 },
208  { -2, -11, 158, 166 },
209  { -1, -43, 163, 141 },
210  { -2, -10, 160, 166 },
211  { -1, -46, 165, 143 },
212  { -3, -9, 162, 168 },
213  { -1, -51, 167, 143 },
214  { -3, -8, 164, 170 },
215  { -1, -61, 169, 145 },
216  { -4, -7, 166, 170 },
217  { -1, -72, 169, 145 },
218  { -6, -5, 168, 49 },
219  { 0, -108, 171, 171 },
220  { 0, -108, 172, 172 },
221  { -6, -5, 173, 173 },
222 };
223 
224 static const uint32_t els_exp_tab[ELS_JOTS_PER_BYTE * 4 + 1] = {
225  0, 0, 0, 0, 0, 0, 0, 0,
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, 1, 1, 1, 1,
230  1, 2, 2, 2, 3, 4, 4, 5,
231  6, 7, 8, 10, 11, 13, 16, 18,
232  21, 25, 29, 34, 40, 47, 54, 64,
233  74, 87, 101, 118, 138, 161, 188, 219,
234  256, 298, 348, 406, 474, 552, 645, 752,
235  877, 1024, 1194, 1393, 1625, 1896, 2211, 2580,
236  3010, 3511, 4096, 4778, 5573, 6501, 7584, 8847,
237  10321, 12040, 14045, 16384, 19112, 22295, 26007, 30339,
238  35391, 41285, 48160, 56180, 65536, 76288, 89088, 103936,
239  121344, 141312, 165120, 192512, 224512, 262144, 305664, 356608,
240  416000, 485376, 566016, 660480, 770560, 898816, 1048576, 1223168,
241  1426688, 1664256, 1941504, 2264832, 2642176, 3082240, 3595520, 4194304,
242  4892672, 5707520, 6657792, 7766784, 9060096, 10568960, 12328960, 14382080,
243  16777216,
244 };
245 
246 void ff_els_decoder_init(ElsDecCtx *ctx, const uint8_t *in, size_t data_size)
247 {
248  int nbytes;
249 
250  /* consume up to 3 bytes from the input data */
251  if (data_size >= 3) {
252  ctx->x = AV_RB24(in);
253  nbytes = 3;
254  } else if (data_size == 2) {
255  ctx->x = AV_RB16(in);
256  nbytes = 2;
257  } else {
258  ctx->x = *in;
259  nbytes = 1;
260  }
261 
262  ctx->in_buf = in + nbytes;
263  ctx->data_size = data_size - nbytes;
264  ctx->err = 0;
265  ctx->j = ELS_JOTS_PER_BYTE;
266  ctx->t = ELS_MAX;
267  ctx->diff = FFMIN(ELS_MAX - ctx->x,
268  ELS_MAX - els_exp_tab[ELS_JOTS_PER_BYTE * 4 - 1]);
269 }
270 
271 void ff_els_decoder_uninit(ElsUnsignedRung *rung)
272 {
273  av_freep(&rung->rem_rung_list);
274 }
275 
276 static int els_import_byte(ElsDecCtx *ctx)
277 {
278  if (!ctx->data_size) {
279  ctx->err = AVERROR_EOF;
280  return AVERROR_EOF;
281  }
282  ctx->x = (ctx->x << 8) | *ctx->in_buf++;
283  ctx->data_size--;
284  ctx->j += ELS_JOTS_PER_BYTE;
285  ctx->t <<= 8;
286 
287  return 0;
288 }
289 
290 int ff_els_decode_bit(ElsDecCtx *ctx, uint8_t *rung)
291 {
292  int z, bit, ret;
293  const uint32_t *pAllowable = &els_exp_tab[ELS_JOTS_PER_BYTE * 3];
294 
295  if (ctx->err)
296  return 0;
297 
298  z = pAllowable[ctx->j + Ladder[*rung].ALps];
299  ctx->t -= z;
300  ctx->diff -= z;
301  if (ctx->diff > 0)
302  return *rung & 1; /* shortcut for x < t > pAllowable[j - 1] */
303 
304  if (ctx->t > ctx->x) { /* decode most probable symbol (MPS) */
305  ctx->j += Ladder[*rung].AMps;
306  while (ctx->t > pAllowable[ctx->j])
307  ctx->j++;
308 
309  if (ctx->j <= 0) { /* MPS: import one byte from bytestream. */
310  ret = els_import_byte(ctx);
311  if (ret < 0)
312  return ret;
313  }
314 
315  z = ctx->t;
316  bit = *rung & 1;
317  *rung = Ladder[*rung].next0;
318  } else { /* decode less probable symbol (LPS) */
319  ctx->x -= ctx->t;
320  ctx->t = z;
321 
322  ctx->j += Ladder[*rung].ALps;
323  if (ctx->j <= 0) {
324  /* LPS: import one byte from bytestream. */
325  z <<= 8;
326  ret = els_import_byte(ctx);
327  if (ret < 0)
328  return ret;
329  if (ctx->j <= 0) {
330  /* LPS: import second byte from bytestream. */
331  z <<= 8;
332  ret = els_import_byte(ctx);
333  if (ret < 0)
334  return ret;
335  while (pAllowable[ctx->j - 1] >= z)
336  ctx->j--;
337  }
338  }
339 
340  bit = !(*rung & 1);
341  *rung = Ladder[*rung].next1;
342  }
343 
344  ctx->diff = FFMIN(z - ctx->x, z - pAllowable[ctx->j - 1]);
345 
346  return bit;
347 }
348 
349 unsigned ff_els_decode_unsigned(ElsDecCtx *ctx, ElsUnsignedRung *ur)
350 {
351  int i, n, r, bit;
352  ElsRungNode *rung_node;
353 
354  if (ctx->err)
355  return 0;
356 
357  /* decode unary prefix */
358  for (n = 0; n < ELS_EXPGOLOMB_LEN + 1; n++)
359  if (ff_els_decode_bit(ctx, &ur->prefix_rung[n]))
360  break;
361 
362  /* handle the error/overflow case */
363  if (ctx->err || n >= ELS_EXPGOLOMB_LEN) {
364  ctx->err = AVERROR_INVALIDDATA;
365  return 0;
366  }
367 
368  /* handle the zero case */
369  if (!n)
370  return 0;
371 
372  /* initialize probability tree */
373  if (!ur->rem_rung_list) {
374  ur->rem_rung_list = av_realloc(NULL, RUNG_SPACE);
375  if (!ur->rem_rung_list) {
376  ctx->err = AVERROR(ENOMEM);
377  return 0;
378  }
379  memset(ur->rem_rung_list, 0, RUNG_SPACE);
380  ur->rung_list_size = RUNG_SPACE;
381  ur->avail_index = ELS_EXPGOLOMB_LEN;
382  }
383 
384  /* decode the remainder */
385  for (i = 0, r = 0, bit = 0; i < n; i++) {
386  if (!i)
387  rung_node = &ur->rem_rung_list[n];
388  else {
389  if (!rung_node->next_index) {
390  if (ur->rung_list_size <= (ur->avail_index + 2) * sizeof(ElsRungNode)) {
391  // remember rung_node position
392  ptrdiff_t pos = rung_node - ur->rem_rung_list;
393  ctx->err = av_reallocp(&ur->rem_rung_list,
394  ur->rung_list_size +
395  RUNG_SPACE);
396  if (ctx->err < 0) {
397  return 0;
398  }
399  memset((uint8_t *) ur->rem_rung_list + ur->rung_list_size, 0,
400  RUNG_SPACE);
401  ur->rung_list_size += RUNG_SPACE;
402  // restore rung_node position in the new list
403  rung_node = &ur->rem_rung_list[pos];
404  }
405  rung_node->next_index = ur->avail_index;
406  ur->avail_index += 2;
407  }
408  rung_node = &ur->rem_rung_list[rung_node->next_index + bit];
409  }
410 
411  bit = ff_els_decode_bit(ctx, &rung_node->rung);
412  if (ctx->err)
413  return bit;
414 
415  r = (r << 1) + bit;
416  }
417 
418  return (1 << n) - 1 + r; /* make value from exp golomb code */
419 }
ff_els_decode_unsigned
unsigned ff_els_decode_unsigned(ElsDecCtx *ctx, ElsUnsignedRung *ur)
Definition: elsdec.c:349
ff_els_decode_bit
int ff_els_decode_bit(ElsDecCtx *ctx, uint8_t *rung)
Definition: elsdec.c:290
r
const char * r
Definition: vf_curves.c:116
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:246
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:37
Ladder
Definition: elsdec.c:42
els_exp_tab
static const uint32_t els_exp_tab[ELS_JOTS_PER_BYTE *4+1]
Definition: elsdec.c:224
RUNG_SPACE
#define RUNG_SPACE
Definition: elsdec.c:39
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
Ladder::ALps
int8_t ALps
Definition: elsdec.c:44
intreadwrite.h
ctx
AVFormatContext * ctx
Definition: movenc.c:48
Ladder::next0
uint8_t next0
Definition: elsdec.c:45
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:152
ElsRungNode
Definition: elsdec.h:43
Ladder::next1
uint8_t next1
Definition: elsdec.c:46
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:185
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:271
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:271
common.h
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
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:35
AVERROR_INVALIDDATA
#define AVERROR_INVALIDDATA
Invalid data found when processing input.
Definition: error.h:61
ELS_MAX
#define ELS_MAX
Definition: elsdec.c:38
Ladder::AMps
int8_t AMps
Definition: elsdec.c:43
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:276
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 Wed Aug 24 2022 21:37:33 for FFmpeg by   doxygen 1.8.17