FFmpeg
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
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;
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,
270 }
271 
273 {
274  av_freep(&rung->rem_rung_list);
275 }
276 
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 
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 
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) {
376  if (!ur->rem_rung_list) {
377  ctx->err = AVERROR(ENOMEM);
378  return 0;
379  }
380  memset(ur->rem_rung_list, 0, RUNG_SPACE);
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 }
#define NULL
Definition: coverity.c:32
#define AVERROR_INVALIDDATA
Invalid data found when processing input.
Definition: error.h:59
void * av_realloc(void *ptr, size_t size)
Allocate, reallocate, or free a block of memory.
Definition: mem.c:135
Entropy Logarithmic-Scale binary arithmetic coder.
#define RUNG_SPACE
Definition: elsdec.c:40
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:87
uint8_t
#define ELS_EXPGOLOMB_LEN
Definition: elsdec.h:34
uint8_t next1
Definition: elsdec.c:47
static const uint32_t els_exp_tab[ELS_JOTS_PER_BYTE *4+1]
Definition: elsdec.c:225
#define ELS_MAX
Definition: elsdec.c:39
#define AVERROR_EOF
End of file.
Definition: error.h:55
int err
Definition: elsdec.h:40
#define ELS_JOTS_PER_BYTE
Definition: elsdec.c:38
#define AVERROR(e)
Definition: error.h:43
const char * r
Definition: vf_curves.c:111
void ff_els_decoder_init(ElsDecCtx *ctx, const uint8_t *in, size_t data_size)
Definition: elsdec.c:247
uint8_t next0
Definition: elsdec.c:46
int t
Definition: elsdec.h:40
int diff
Definition: elsdec.h:40
#define FFMIN(a, b)
Definition: common.h:96
int j
Definition: elsdec.h:40
const uint8_t * in_buf
Definition: elsdec.h:37
AVFormatContext * ctx
Definition: movenc.c:48
int n
Definition: avisynth_c.h:684
size_t rung_list_size
Definition: elsdec.h:51
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:163
Libavcodec external API header.
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:87
uint8_t pi<< 24) CONV_FUNC_GROUP(AV_SAMPLE_FMT_FLT, float, AV_SAMPLE_FMT_U8, uint8_t,(*(constuint8_t *) pi-0x80)*(1.0f/(1<< 7))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_DBL, double, AV_SAMPLE_FMT_U8, uint8_t,(*(constuint8_t *) pi-0x80)*(1.0/(1<< 7))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_S16, int16_t,(*(constint16_t *) pi >>8)+0x80) CONV_FUNC_GROUP(AV_SAMPLE_FMT_FLT, float, AV_SAMPLE_FMT_S16, int16_t,*(constint16_t *) pi *(1.0f/(1<< 15))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_DBL, double, AV_SAMPLE_FMT_S16, int16_t,*(constint16_t *) pi *(1.0/(1<< 15))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_S32, int32_t,(*(constint32_t *) pi >>24)+0x80) CONV_FUNC_GROUP(AV_SAMPLE_FMT_FLT, float, AV_SAMPLE_FMT_S32, int32_t,*(constint32_t *) pi *(1.0f/(1U<< 31))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_DBL, double, AV_SAMPLE_FMT_S32, int32_t,*(constint32_t *) pi *(1.0/(1U<< 31))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_FLT, float, av_clip_uint8(lrintf(*(constfloat *) pi *(1<< 7))+0x80)) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S16, int16_t, AV_SAMPLE_FMT_FLT, float, av_clip_int16(lrintf(*(constfloat *) pi *(1<< 15)))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S32, int32_t, AV_SAMPLE_FMT_FLT, float, av_clipl_int32(llrintf(*(constfloat *) pi *(1U<< 31)))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_DBL, double, av_clip_uint8(lrint(*(constdouble *) pi *(1<< 7))+0x80)) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S16, int16_t, AV_SAMPLE_FMT_DBL, double, av_clip_int16(lrint(*(constdouble *) pi *(1<< 15)))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S32, int32_t, AV_SAMPLE_FMT_DBL, double, av_clipl_int32(llrint(*(constdouble *) pi *(1U<< 31))))#defineSET_CONV_FUNC_GROUP(ofmt, ifmt) staticvoidset_generic_function(AudioConvert *ac){}voidff_audio_convert_free(AudioConvert **ac){if(!*ac) return;ff_dither_free(&(*ac) ->dc);av_freep(ac);}AudioConvert *ff_audio_convert_alloc(AVAudioResampleContext *avr, enumAVSampleFormatout_fmt, enumAVSampleFormatin_fmt, intchannels, intsample_rate, intapply_map){AudioConvert *ac;intin_planar, out_planar;ac=av_mallocz(sizeof(*ac));if(!ac) returnNULL;ac->avr=avr;ac->out_fmt=out_fmt;ac->in_fmt=in_fmt;ac->channels=channels;ac->apply_map=apply_map;if(avr->dither_method!=AV_RESAMPLE_DITHER_NONE &&av_get_packed_sample_fmt(out_fmt)==AV_SAMPLE_FMT_S16 &&av_get_bytes_per_sample(in_fmt)>2){ac->dc=ff_dither_alloc(avr, out_fmt, in_fmt, channels, sample_rate, apply_map);if(!ac->dc){av_free(ac);returnNULL;}returnac;}in_planar=ff_sample_fmt_is_planar(in_fmt, channels);out_planar=ff_sample_fmt_is_planar(out_fmt, channels);if(in_planar==out_planar){ac->func_type=CONV_FUNC_TYPE_FLAT;ac->planes=in_planar?ac->channels:1;}elseif(in_planar) ac->func_type=CONV_FUNC_TYPE_INTERLEAVE;elseac->func_type=CONV_FUNC_TYPE_DEINTERLEAVE;set_generic_function(ac);if(ARCH_AARCH64) ff_audio_convert_init_aarch64(ac);if(ARCH_ARM) ff_audio_convert_init_arm(ac);if(ARCH_X86) ff_audio_convert_init_x86(ac);returnac;}intff_audio_convert(AudioConvert *ac, AudioData *out, AudioData *in){intuse_generic=1;intlen=in->nb_samples;intp;if(ac->dc){av_log(ac->avr, AV_LOG_TRACE,"%dsamples-audio_convert:%sto%s(dithered)\n", len, av_get_sample_fmt_name(ac->in_fmt), av_get_sample_fmt_name(ac->out_fmt));returnff_convert_dither(ac-> in
ElsRungNode * rem_rung_list
Definition: elsdec.h:50
uint16_t next_index
Definition: elsdec.h:45
static int els_import_byte(ElsDecCtx *ctx)
Definition: elsdec.c:277
Definition: elsdec.c:43
int8_t ALps
Definition: elsdec.c:45
int8_t AMps
Definition: elsdec.c:44
unsigned ff_els_decode_unsigned(ElsDecCtx *ctx, ElsUnsignedRung *ur)
Definition: elsdec.c:350
common internal and external API header
unsigned x
Definition: elsdec.h:38
size_t data_size
Definition: elsdec.h:39
uint16_t avail_index
Definition: elsdec.h:52
void ff_els_decoder_uninit(ElsUnsignedRung *rung)
Definition: elsdec.c:272
int ff_els_decode_bit(ElsDecCtx *ctx, uint8_t *rung)
Definition: elsdec.c:291
#define av_freep(p)
uint8_t rung
Definition: elsdec.h:44
uint8_t prefix_rung[ELS_EXPGOLOMB_LEN+1]
Definition: elsdec.h:49