OpenFFmpeg
golomb.h
Go to the documentation of this file.
1 /*
2  * exp golomb vlc stuff
3  * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at>
4  * Copyright (c) 2004 Alex Beregszaszi
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 
30 #ifndef AVCODEC_GOLOMB_H
31 #define AVCODEC_GOLOMB_H
32 
33 #include <stdint.h>
34 
35 #include "get_bits.h"
36 #include "put_bits.h"
37 
38 #define INVALID_VLC 0x80000000
39 
40 extern const uint8_t ff_golomb_vlc_len[512];
41 extern const uint8_t ff_ue_golomb_vlc_code[512];
42 extern const int8_t ff_se_golomb_vlc_code[512];
43 extern const uint8_t ff_ue_golomb_len[256];
44 
45 extern const uint8_t ff_interleaved_golomb_vlc_len[256];
46 extern const uint8_t ff_interleaved_ue_golomb_vlc_code[256];
47 extern const int8_t ff_interleaved_se_golomb_vlc_code[256];
48 extern const uint8_t ff_interleaved_dirac_golomb_vlc_code[256];
49 
53 static inline int get_ue_golomb(GetBitContext *gb)
54 {
55  unsigned int buf;
56 
57 #if CACHED_BITSTREAM_READER
58  buf = show_bits_long(gb, 32);
59 
60  if (buf >= (1 << 27)) {
61  buf >>= 32 - 9;
62  skip_bits_long(gb, ff_golomb_vlc_len[buf]);
63 
64  return ff_ue_golomb_vlc_code[buf];
65  } else {
66  int log = 2 * av_log2(buf) - 31;
67  buf >>= log;
68  buf--;
69  skip_bits_long(gb, 32 - log);
70 
71  return buf;
72  }
73 #else
74  OPEN_READER(re, gb);
75  UPDATE_CACHE(re, gb);
76  buf = GET_CACHE(re, gb);
77 
78  if (buf >= (1 << 27)) {
79  buf >>= 32 - 9;
80  LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]);
81  CLOSE_READER(re, gb);
82 
83  return ff_ue_golomb_vlc_code[buf];
84  } else {
85  int log = 2 * av_log2(buf) - 31;
86  LAST_SKIP_BITS(re, gb, 32 - log);
87  CLOSE_READER(re, gb);
88  if (log < 7) {
89  av_log(NULL, AV_LOG_ERROR, "Invalid UE golomb code\n");
90  return AVERROR_INVALIDDATA;
91  }
92  buf >>= log;
93  buf--;
94 
95  return buf;
96  }
97 #endif
98 }
99 
103 static inline unsigned get_ue_golomb_long(GetBitContext *gb)
104 {
105  unsigned buf, log;
106 
107  buf = show_bits_long(gb, 32);
108  log = 31 - av_log2(buf);
109  skip_bits_long(gb, log);
110 
111  return get_bits_long(gb, log + 1) - 1;
112 }
113 
118 static inline int get_ue_golomb_31(GetBitContext *gb)
119 {
120  unsigned int buf;
121 
122 #if CACHED_BITSTREAM_READER
123  buf = show_bits_long(gb, 32);
124 
125  buf >>= 32 - 9;
126  skip_bits_long(gb, ff_golomb_vlc_len[buf]);
127 #else
128 
129  OPEN_READER(re, gb);
130  UPDATE_CACHE(re, gb);
131  buf = GET_CACHE(re, gb);
132 
133  buf >>= 32 - 9;
134  LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]);
135  CLOSE_READER(re, gb);
136 #endif
137 
138  return ff_ue_golomb_vlc_code[buf];
139 }
140 
141 static inline unsigned get_interleaved_ue_golomb(GetBitContext *gb)
142 {
143  uint32_t buf;
144 
145 #if CACHED_BITSTREAM_READER
146  buf = show_bits_long(gb, 32);
147 
148  if (buf & 0xAA800000) {
149  buf >>= 32 - 8;
150  skip_bits_long(gb, ff_interleaved_golomb_vlc_len[buf]);
151 
152  return ff_interleaved_ue_golomb_vlc_code[buf];
153  } else {
154  unsigned ret = 1;
155 
156  do {
157  buf >>= 32 - 8;
158  skip_bits_long(gb, FFMIN(ff_interleaved_golomb_vlc_len[buf], 8));
159 
160  if (ff_interleaved_golomb_vlc_len[buf] != 9) {
161  ret <<= (ff_interleaved_golomb_vlc_len[buf] - 1) >> 1;
162  ret |= ff_interleaved_dirac_golomb_vlc_code[buf];
163  break;
164  }
165  ret = (ret << 4) | ff_interleaved_dirac_golomb_vlc_code[buf];
166  buf = show_bits_long(gb, 32);
167  } while (get_bits_left(gb) > 0);
168 
169  return ret - 1;
170  }
171 #else
172  OPEN_READER(re, gb);
173  UPDATE_CACHE(re, gb);
174  buf = GET_CACHE(re, gb);
175 
176  if (buf & 0xAA800000) {
177  buf >>= 32 - 8;
178  LAST_SKIP_BITS(re, gb, ff_interleaved_golomb_vlc_len[buf]);
179  CLOSE_READER(re, gb);
180 
181  return ff_interleaved_ue_golomb_vlc_code[buf];
182  } else {
183  unsigned ret = 1;
184 
185  do {
186  buf >>= 32 - 8;
187  LAST_SKIP_BITS(re, gb,
188  FFMIN(ff_interleaved_golomb_vlc_len[buf], 8));
189 
190  if (ff_interleaved_golomb_vlc_len[buf] != 9) {
191  ret <<= (ff_interleaved_golomb_vlc_len[buf] - 1) >> 1;
192  ret |= ff_interleaved_dirac_golomb_vlc_code[buf];
193  break;
194  }
195  ret = (ret << 4) | ff_interleaved_dirac_golomb_vlc_code[buf];
196  UPDATE_CACHE(re, gb);
197  buf = GET_CACHE(re, gb);
198  } while (ret<0x8000000U && BITS_AVAILABLE(re, gb));
199 
200  CLOSE_READER(re, gb);
201  return ret - 1;
202  }
203 #endif
204 }
205 
209 static inline int get_te0_golomb(GetBitContext *gb, int range)
210 {
211  av_assert2(range >= 1);
212 
213  if (range == 1)
214  return 0;
215  else if (range == 2)
216  return get_bits1(gb) ^ 1;
217  else
218  return get_ue_golomb(gb);
219 }
220 
224 static inline int get_te_golomb(GetBitContext *gb, int range)
225 {
226  av_assert2(range >= 1);
227 
228  if (range == 2)
229  return get_bits1(gb) ^ 1;
230  else
231  return get_ue_golomb(gb);
232 }
233 
237 static inline int get_se_golomb(GetBitContext *gb)
238 {
239  unsigned int buf;
240 
241 #if CACHED_BITSTREAM_READER
242  buf = show_bits_long(gb, 32);
243 
244  if (buf >= (1 << 27)) {
245  buf >>= 32 - 9;
246  skip_bits_long(gb, ff_golomb_vlc_len[buf]);
247 
248  return ff_se_golomb_vlc_code[buf];
249  } else {
250  int log = 2 * av_log2(buf) - 31;
251  buf >>= log;
252 
253  skip_bits_long(gb, 32 - log);
254 
255  if (buf & 1)
256  buf = -(buf >> 1);
257  else
258  buf = (buf >> 1);
259 
260  return buf;
261  }
262 #else
263  OPEN_READER(re, gb);
264  UPDATE_CACHE(re, gb);
265  buf = GET_CACHE(re, gb);
266 
267  if (buf >= (1 << 27)) {
268  buf >>= 32 - 9;
269  LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]);
270  CLOSE_READER(re, gb);
271 
272  return ff_se_golomb_vlc_code[buf];
273  } else {
274  int log = av_log2(buf), sign;
275  LAST_SKIP_BITS(re, gb, 31 - log);
276  UPDATE_CACHE(re, gb);
277  buf = GET_CACHE(re, gb);
278 
279  buf >>= log;
280 
281  LAST_SKIP_BITS(re, gb, 32 - log);
282  CLOSE_READER(re, gb);
283 
284  sign = -(buf & 1);
285  buf = ((buf >> 1) ^ sign) - sign;
286 
287  return buf;
288  }
289 #endif
290 }
291 
292 static inline int get_se_golomb_long(GetBitContext *gb)
293 {
294  unsigned int buf = get_ue_golomb_long(gb);
295  int sign = (buf & 1) - 1;
296  return ((buf >> 1) ^ sign) + 1;
297 }
298 
299 static inline int get_interleaved_se_golomb(GetBitContext *gb)
300 {
301  unsigned int buf;
302 
303 #if CACHED_BITSTREAM_READER
304  buf = show_bits_long(gb, 32);
305 
306  if (buf & 0xAA800000) {
307  buf >>= 32 - 8;
308  skip_bits_long(gb, ff_interleaved_golomb_vlc_len[buf]);
309 
310  return ff_interleaved_se_golomb_vlc_code[buf];
311  } else {
312  int log;
313  skip_bits(gb, 8);
314  buf |= 1 | show_bits_long(gb, 24);
315 
316  if ((buf & 0xAAAAAAAA) == 0)
317  return INVALID_VLC;
318 
319  for (log = 31; (buf & 0x80000000) == 0; log--)
320  buf = (buf << 2) - ((buf << log) >> (log - 1)) + (buf >> 30);
321 
322  skip_bits_long(gb, 63 - 2 * log - 8);
323 
324  return (signed) (((((buf << log) >> log) - 1) ^ -(buf & 0x1)) + 1) >> 1;
325  }
326 #else
327  OPEN_READER(re, gb);
328  UPDATE_CACHE(re, gb);
329  buf = GET_CACHE(re, gb);
330 
331  if (buf & 0xAA800000) {
332  buf >>= 32 - 8;
333  LAST_SKIP_BITS(re, gb, ff_interleaved_golomb_vlc_len[buf]);
334  CLOSE_READER(re, gb);
335 
336  return ff_interleaved_se_golomb_vlc_code[buf];
337  } else {
338  int log;
339  LAST_SKIP_BITS(re, gb, 8);
340  UPDATE_CACHE(re, gb);
341  buf |= 1 | (GET_CACHE(re, gb) >> 8);
342 
343  if ((buf & 0xAAAAAAAA) == 0)
344  return INVALID_VLC;
345 
346  for (log = 31; (buf & 0x80000000) == 0; log--)
347  buf = (buf << 2) - ((buf << log) >> (log - 1)) + (buf >> 30);
348 
349  LAST_SKIP_BITS(re, gb, 63 - 2 * log - 8);
350  CLOSE_READER(re, gb);
351 
352  return (signed) (((((buf << log) >> log) - 1) ^ -(buf & 0x1)) + 1) >> 1;
353  }
354 #endif
355 }
356 
357 static inline int dirac_get_se_golomb(GetBitContext *gb)
358 {
359  uint32_t ret = get_interleaved_ue_golomb(gb);
360 
361  if (ret) {
362  int sign = -get_bits1(gb);
363  ret = (ret ^ sign) - sign;
364  }
365 
366  return ret;
367 }
368 
372 static inline int get_ur_golomb(GetBitContext *gb, int k, int limit,
373  int esc_len)
374 {
375  unsigned int buf;
376  int log;
377 
378 #if CACHED_BITSTREAM_READER
379  buf = show_bits_long(gb, 32);
380 
381  log = av_log2(buf);
382 
383  if (log > 31 - limit) {
384  buf >>= log - k;
385  buf += (30 - log) << k;
386  skip_bits_long(gb, 32 + k - log);
387 
388  return buf;
389  } else {
390  skip_bits_long(gb, limit);
391  buf = get_bits_long(gb, esc_len);
392 
393  return buf + limit - 1;
394  }
395 #else
396  OPEN_READER(re, gb);
397  UPDATE_CACHE(re, gb);
398  buf = GET_CACHE(re, gb);
399 
400  log = av_log2(buf);
401 
402  if (log > 31 - limit) {
403  buf >>= log - k;
404  buf += (30U - log) << k;
405  LAST_SKIP_BITS(re, gb, 32 + k - log);
406  CLOSE_READER(re, gb);
407 
408  return buf;
409  } else {
410  LAST_SKIP_BITS(re, gb, limit);
411  UPDATE_CACHE(re, gb);
412 
413  buf = SHOW_UBITS(re, gb, esc_len);
414 
415  LAST_SKIP_BITS(re, gb, esc_len);
416  CLOSE_READER(re, gb);
417 
418  return buf + limit - 1;
419  }
420 #endif
421 }
422 
426 static inline int get_ur_golomb_jpegls(GetBitContext *gb, int k, int limit,
427  int esc_len)
428 {
429  unsigned int buf;
430  int log;
431 
432 #if CACHED_BITSTREAM_READER
433  buf = show_bits_long(gb, 32);
434 
435  log = av_log2(buf);
436 
437  if (log - k >= 1 && 32 - log < limit) {
438  buf >>= log - k;
439  buf += (30 - log) << k;
440  skip_bits_long(gb, 32 + k - log);
441 
442  return buf;
443  } else {
444  int i;
445  for (i = 0;
446  i < limit && get_bits1(gb) == 0 && get_bits_left(gb) > 0;
447  i++);
448 
449  if (i < limit - 1) {
450  buf = get_bits_long(gb, k);
451 
452  return buf + (i << k);
453  } else if (i == limit - 1) {
454  buf = get_bits_long(gb, esc_len);
455 
456  return buf + 1;
457  } else
458  return -1;
459  }
460 #else
461  OPEN_READER(re, gb);
462  UPDATE_CACHE(re, gb);
463  buf = GET_CACHE(re, gb);
464 
465  log = av_log2(buf);
466 
467  av_assert2(k <= 31);
468 
469  if (log - k >= 32 - MIN_CACHE_BITS + (MIN_CACHE_BITS == 32) &&
470  32 - log < limit) {
471  buf >>= log - k;
472  buf += (30U - log) << k;
473  LAST_SKIP_BITS(re, gb, 32 + k - log);
474  CLOSE_READER(re, gb);
475 
476  return buf;
477  } else {
478  int i;
479  for (i = 0; i + MIN_CACHE_BITS <= limit && SHOW_UBITS(re, gb, MIN_CACHE_BITS) == 0; i += MIN_CACHE_BITS) {
480  if (gb->size_in_bits <= re_index) {
481  CLOSE_READER(re, gb);
482  return -1;
483  }
484  LAST_SKIP_BITS(re, gb, MIN_CACHE_BITS);
485  UPDATE_CACHE(re, gb);
486  }
487  for (; i < limit && SHOW_UBITS(re, gb, 1) == 0; i++) {
488  SKIP_BITS(re, gb, 1);
489  }
490  LAST_SKIP_BITS(re, gb, 1);
491  UPDATE_CACHE(re, gb);
492 
493  if (i < limit - 1) {
494  if (k) {
495  if (k > MIN_CACHE_BITS - 1) {
496  buf = SHOW_UBITS(re, gb, 16) << (k-16);
497  LAST_SKIP_BITS(re, gb, 16);
498  UPDATE_CACHE(re, gb);
499  buf |= SHOW_UBITS(re, gb, k-16);
500  LAST_SKIP_BITS(re, gb, k-16);
501  } else {
502  buf = SHOW_UBITS(re, gb, k);
503  LAST_SKIP_BITS(re, gb, k);
504  }
505  } else {
506  buf = 0;
507  }
508 
509  buf += ((SUINT)i << k);
510  } else if (i == limit - 1) {
511  buf = SHOW_UBITS(re, gb, esc_len);
512  LAST_SKIP_BITS(re, gb, esc_len);
513 
514  buf ++;
515  } else {
516  buf = -1;
517  }
518  CLOSE_READER(re, gb);
519  return buf;
520  }
521 #endif
522 }
523 
527 static inline int get_sr_golomb(GetBitContext *gb, int k, int limit,
528  int esc_len)
529 {
530  unsigned v = get_ur_golomb(gb, k, limit, esc_len);
531  return (v >> 1) ^ -(v & 1);
532 }
533 
537 static inline int get_sr_golomb_flac(GetBitContext *gb, int k, int limit,
538  int esc_len)
539 {
540  unsigned v = get_ur_golomb_jpegls(gb, k, limit, esc_len);
541  return (v >> 1) ^ -(v & 1);
542 }
543 
547 static inline unsigned int get_ur_golomb_shorten(GetBitContext *gb, int k)
548 {
549  return get_ur_golomb_jpegls(gb, k, INT_MAX, 0);
550 }
551 
555 static inline int get_sr_golomb_shorten(GetBitContext *gb, int k)
556 {
557  int uvar = get_ur_golomb_jpegls(gb, k + 1, INT_MAX, 0);
558  return (uvar >> 1) ^ -(uvar & 1);
559 }
560 
561 #ifdef TRACE
562 
563 static inline int get_ue(GetBitContext *s, const char *file, const char *func,
564  int line)
565 {
566  int show = show_bits(s, 24);
567  int pos = get_bits_count(s);
568  int i = get_ue_golomb(s);
569  int len = get_bits_count(s) - pos;
570  int bits = show >> (24 - len);
571 
572  av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d ue @%5d in %s %s:%d\n",
573  bits, len, i, pos, file, func, line);
574 
575  return i;
576 }
577 
578 static inline int get_se(GetBitContext *s, const char *file, const char *func,
579  int line)
580 {
581  int show = show_bits(s, 24);
582  int pos = get_bits_count(s);
583  int i = get_se_golomb(s);
584  int len = get_bits_count(s) - pos;
585  int bits = show >> (24 - len);
586 
587  av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d se @%5d in %s %s:%d\n",
588  bits, len, i, pos, file, func, line);
589 
590  return i;
591 }
592 
593 static inline int get_te(GetBitContext *s, int r, char *file, const char *func,
594  int line)
595 {
596  int show = show_bits(s, 24);
597  int pos = get_bits_count(s);
598  int i = get_te0_golomb(s, r);
599  int len = get_bits_count(s) - pos;
600  int bits = show >> (24 - len);
601 
602  av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d te @%5d in %s %s:%d\n",
603  bits, len, i, pos, file, func, line);
604 
605  return i;
606 }
607 
608 #define get_ue_golomb(a) get_ue(a, __FILE__, __func__, __LINE__)
609 #define get_se_golomb(a) get_se(a, __FILE__, __func__, __LINE__)
610 #define get_te_golomb(a, r) get_te(a, r, __FILE__, __func__, __LINE__)
611 #define get_te0_golomb(a, r) get_te(a, r, __FILE__, __func__, __LINE__)
612 
613 #endif /* TRACE */
614 
618 static inline void set_ue_golomb(PutBitContext *pb, int i)
619 {
620  av_assert2(i >= 0);
621  av_assert2(i <= 0xFFFE);
622 
623  if (i < 256)
624  put_bits(pb, ff_ue_golomb_len[i], i + 1);
625  else {
626  int e = av_log2(i + 1);
627  put_bits(pb, 2 * e + 1, i + 1);
628  }
629 }
630 
634 static inline void set_ue_golomb_long(PutBitContext *pb, uint32_t i)
635 {
636  av_assert2(i <= (UINT32_MAX - 1));
637 
638  if (i < 256)
639  put_bits(pb, ff_ue_golomb_len[i], i + 1);
640  else {
641  int e = av_log2(i + 1);
642  put_bits64(pb, 2 * e + 1, i + 1);
643  }
644 }
645 
649 static inline void set_te_golomb(PutBitContext *pb, int i, int range)
650 {
651  av_assert2(range >= 1);
652  av_assert2(i <= range);
653 
654  if (range == 2)
655  put_bits(pb, 1, i ^ 1);
656  else
657  set_ue_golomb(pb, i);
658 }
659 
663 static inline void set_se_golomb(PutBitContext *pb, int i)
664 {
665  i = 2 * i - 1;
666  if (i < 0)
667  i ^= -1; //FIXME check if gcc does the right thing
668  set_ue_golomb(pb, i);
669 }
670 
674 static inline void set_ur_golomb(PutBitContext *pb, int i, int k, int limit,
675  int esc_len)
676 {
677  int e;
678 
679  av_assert2(i >= 0);
680 
681  e = i >> k;
682  if (e < limit)
683  put_bits(pb, e + k + 1, (1 << k) + av_mod_uintp2(i, k));
684  else
685  put_bits(pb, limit + esc_len, i - limit + 1);
686 }
687 
691 static inline void set_ur_golomb_jpegls(PutBitContext *pb, int i, int k,
692  int limit, int esc_len)
693 {
694  int e;
695 
696  av_assert2(i >= 0);
697 
698  e = (i >> k) + 1;
699  if (e < limit) {
700  while (e > 31) {
701  put_bits(pb, 31, 0);
702  e -= 31;
703  }
704  put_bits(pb, e, 1);
705  if (k)
706  put_sbits(pb, k, i);
707  } else {
708  while (limit > 31) {
709  put_bits(pb, 31, 0);
710  limit -= 31;
711  }
712  put_bits(pb, limit, 1);
713  put_bits(pb, esc_len, i - 1);
714  }
715 }
716 
720 static inline void set_sr_golomb(PutBitContext *pb, int i, int k, int limit,
721  int esc_len)
722 {
723  int v;
724 
725  v = -2 * i - 1;
726  v ^= (v >> 31);
727 
728  set_ur_golomb(pb, v, k, limit, esc_len);
729 }
730 
734 static inline void set_sr_golomb_flac(PutBitContext *pb, int i, int k,
735  int limit, int esc_len)
736 {
737  int v;
738 
739  v = -2 * i - 1;
740  v ^= (v >> 31);
741 
742  set_ur_golomb_jpegls(pb, v, k, limit, esc_len);
743 }
744 
745 #endif /* AVCODEC_GOLOMB_H */
AVERROR_INVALIDDATA
#define AVERROR_INVALIDDATA
Invalid data found when processing input.
Definition: error.h:59
PutBitContext
Definition: put_bits.h:35
av_log
void av_log(void *avcl, int level, const char *fmt,...) av_printf_format(3
Send the specified message to the log if the level is less than or equal to the current av_log_level...
av_assert2
#define av_assert2(cond)
assert() equivalent, that does lie in speed critical code.
Definition: avassert.h:64
get_bits.h
bitstream reader API header.
AV_LOG_ERROR
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:176
AV_LOG_DEBUG
#define AV_LOG_DEBUG
Stuff which is only useful for libav* developers.
Definition: log.h:197
line
Definition: graph2dot.c:48
GetBitContext
Definition: get_bits.h:61
put_bits.h
bitstream writer API
Generated by   doxygen 1.8.12