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 "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 
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 
272 void ff_els_decoder_uninit(ElsUnsignedRung *rung)
273 {
274  av_freep(&rung->rem_rung_list);
275 }
276 
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 
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 
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 }
ff_els_decode_unsigned
unsigned ff_els_decode_unsigned(ElsDecCtx *ctx, ElsUnsignedRung *ur)
Definition: elsdec.c:350
ff_els_decode_bit
int ff_els_decode_bit(ElsDecCtx *ctx, uint8_t *rung)
Definition: elsdec.c:291
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:247
AVERROR_EOF
#define AVERROR_EOF
End of file.
Definition: error.h:55
ElsRungNode::rung
uint8_t rung
Definition: elsdec.h:44
ELS_JOTS_PER_BYTE
#define ELS_JOTS_PER_BYTE
Definition: elsdec.c:38
Ladder
Definition: elsdec.c:43
els_exp_tab
static const uint32_t els_exp_tab[ELS_JOTS_PER_BYTE *4+1]
Definition: elsdec.c:225
RUNG_SPACE
#define RUNG_SPACE
Definition: elsdec.c:40
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:45
intreadwrite.h
ctx
AVFormatContext * ctx
Definition: movenc.c:48
Ladder::next0
uint8_t next0
Definition: elsdec.c:46
NULL
#define NULL
Definition: coverity.c:32
ElsRungNode
Definition: elsdec.h:43
Ladder::next1
uint8_t next1
Definition: elsdec.c:47
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:167
ElsUnsignedRung
Definition: elsdec.h:48
ELS_EXPGOLOMB_LEN
#define ELS_EXPGOLOMB_LEN
Definition: elsdec.h:34
FFMIN
#define FFMIN(a, b)
Definition: common.h:105
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:272
av_realloc
void * av_realloc(void *ptr, size_t size)
Allocate, reallocate, or free a block of memory.
Definition: mem.c:134
i
int i
Definition: input.c:407
common.h
ElsUnsignedRung::rung_list_size
size_t rung_list_size
Definition: elsdec.h:51
avcodec.h
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:59
ELS_MAX
#define ELS_MAX
Definition: elsdec.c:39
Ladder::AMps
int8_t AMps
Definition: elsdec.c:44
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:277
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 Thu May 6 2021 19:21:16 for FFmpeg by   doxygen 1.8.17