Libav
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 Libav.
7  *
8  * Libav 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  * Libav 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 Libav; 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];
47 extern const int8_t ff_interleaved_se_golomb_vlc_code[256];
49 
53 static inline int get_ue_golomb(GetBitContext *gb)
54 {
55  unsigned int buf;
56 
57  OPEN_READER(re, gb);
58  UPDATE_CACHE(re, gb);
59  buf = GET_CACHE(re, gb);
60 
61  if (buf >= (1 << 27)) {
62  buf >>= 32 - 9;
64  CLOSE_READER(re, gb);
65 
66  return ff_ue_golomb_vlc_code[buf];
67  } else {
68  int log = 2 * av_log2(buf) - 31;
69  buf >>= log;
70  buf--;
71  LAST_SKIP_BITS(re, gb, 32 - log);
72  CLOSE_READER(re, gb);
73 
74  return buf;
75  }
76 }
77 
81 static inline unsigned get_ue_golomb_long(GetBitContext *gb)
82 {
83  unsigned buf, log;
84 
85  buf = show_bits_long(gb, 32);
86  log = 31 - av_log2(buf);
87  skip_bits_long(gb, log);
88 
89  return get_bits_long(gb, log + 1) - 1;
90 }
91 
96 static inline int get_ue_golomb_31(GetBitContext *gb)
97 {
98  unsigned int buf;
99 
100  OPEN_READER(re, gb);
101  UPDATE_CACHE(re, gb);
102  buf = GET_CACHE(re, gb);
103 
104  buf >>= 32 - 9;
106  CLOSE_READER(re, gb);
107 
108  return ff_ue_golomb_vlc_code[buf];
109 }
110 
111 static inline unsigned svq3_get_ue_golomb(GetBitContext *gb)
112 {
113  uint32_t buf;
114 
115  OPEN_READER(re, gb);
116  UPDATE_CACHE(re, gb);
117  buf = GET_CACHE(re, gb);
118 
119  if (buf & 0xAA800000) {
120  buf >>= 32 - 8;
122  CLOSE_READER(re, gb);
123 
125  } else {
126  unsigned ret = 1;
127 
128  do {
129  buf >>= 32 - 8;
130  LAST_SKIP_BITS(re, gb,
132 
133  if (ff_interleaved_golomb_vlc_len[buf] != 9) {
134  ret <<= (ff_interleaved_golomb_vlc_len[buf] - 1) >> 1;
136  break;
137  }
138  ret = (ret << 4) | ff_interleaved_dirac_golomb_vlc_code[buf];
139  UPDATE_CACHE(re, gb);
140  buf = GET_CACHE(re, gb);
141  } while (HAVE_BITS_REMAINING(re, gb));
142 
143  CLOSE_READER(re, gb);
144  return ret - 1;
145  }
146 }
147 
151 static inline int get_te0_golomb(GetBitContext *gb, int range)
152 {
153  assert(range >= 1);
154 
155  if (range == 1)
156  return 0;
157  else if (range == 2)
158  return get_bits1(gb) ^ 1;
159  else
160  return get_ue_golomb(gb);
161 }
162 
166 static inline int get_te_golomb(GetBitContext *gb, int range)
167 {
168  assert(range >= 1);
169 
170  if (range == 2)
171  return get_bits1(gb) ^ 1;
172  else
173  return get_ue_golomb(gb);
174 }
175 
179 static inline int get_se_golomb(GetBitContext *gb)
180 {
181  unsigned int buf;
182 
183  OPEN_READER(re, gb);
184  UPDATE_CACHE(re, gb);
185  buf = GET_CACHE(re, gb);
186 
187  if (buf >= (1 << 27)) {
188  buf >>= 32 - 9;
190  CLOSE_READER(re, gb);
191 
192  return ff_se_golomb_vlc_code[buf];
193  } else {
194  int log = 2 * av_log2(buf) - 31;
195  buf >>= log;
196 
197  LAST_SKIP_BITS(re, gb, 32 - log);
198  CLOSE_READER(re, gb);
199 
200  if (buf & 1)
201  buf = -(buf >> 1);
202  else
203  buf = (buf >> 1);
204 
205  return buf;
206  }
207 }
208 
209 static inline int get_se_golomb_long(GetBitContext *gb)
210 {
211  unsigned int buf = get_ue_golomb_long(gb);
212 
213  if (buf & 1)
214  buf = (buf + 1) >> 1;
215  else
216  buf = -(buf >> 1);
217 
218  return buf;
219 }
220 
221 static inline int svq3_get_se_golomb(GetBitContext *gb)
222 {
223  unsigned int buf;
224 
225  OPEN_READER(re, gb);
226  UPDATE_CACHE(re, gb);
227  buf = GET_CACHE(re, gb);
228 
229  if (buf & 0xAA800000) {
230  buf >>= 32 - 8;
232  CLOSE_READER(re, gb);
233 
235  } else {
236  int log;
237  LAST_SKIP_BITS(re, gb, 8);
238  UPDATE_CACHE(re, gb);
239  buf |= 1 | (GET_CACHE(re, gb) >> 8);
240 
241  if ((buf & 0xAAAAAAAA) == 0)
242  return INVALID_VLC;
243 
244  for (log = 31; (buf & 0x80000000) == 0; log--)
245  buf = (buf << 2) - ((buf << log) >> (log - 1)) + (buf >> 30);
246 
247  LAST_SKIP_BITS(re, gb, 63 - 2 * log - 8);
248  CLOSE_READER(re, gb);
249 
250  return (signed) (((((buf << log) >> log) - 1) ^ -(buf & 0x1)) + 1) >> 1;
251  }
252 }
253 
254 static inline int dirac_get_se_golomb(GetBitContext *gb)
255 {
256  uint32_t ret = svq3_get_ue_golomb(gb);
257 
258  if (ret) {
259  uint32_t buf;
260  OPEN_READER(re, gb);
261  UPDATE_CACHE(re, gb);
262  buf = SHOW_SBITS(re, gb, 1);
263  LAST_SKIP_BITS(re, gb, 1);
264  ret = (ret ^ buf) - buf;
265  CLOSE_READER(re, gb);
266  }
267 
268  return ret;
269 }
270 
274 static inline int get_ur_golomb(GetBitContext *gb, int k, int limit,
275  int esc_len)
276 {
277  unsigned int buf;
278  int log;
279 
280  OPEN_READER(re, gb);
281  UPDATE_CACHE(re, gb);
282  buf = GET_CACHE(re, gb);
283 
284  log = av_log2(buf);
285 
286  if (log > 31 - limit) {
287  buf >>= log - k;
288  buf += (30 - log) << k;
289  LAST_SKIP_BITS(re, gb, 32 + k - log);
290  CLOSE_READER(re, gb);
291 
292  return buf;
293  } else {
294  LAST_SKIP_BITS(re, gb, limit);
295  UPDATE_CACHE(re, gb);
296 
297  buf = SHOW_UBITS(re, gb, esc_len);
298 
299  LAST_SKIP_BITS(re, gb, esc_len);
300  CLOSE_READER(re, gb);
301 
302  return buf + limit - 1;
303  }
304 }
305 
309 static inline int get_ur_golomb_jpegls(GetBitContext *gb, int k, int limit,
310  int esc_len)
311 {
312  unsigned int buf;
313  int log;
314 
315  OPEN_READER(re, gb);
316  UPDATE_CACHE(re, gb);
317  buf = GET_CACHE(re, gb);
318 
319  log = av_log2(buf);
320 
321  if (log - k >= 32 - MIN_CACHE_BITS + (MIN_CACHE_BITS == 32) &&
322  32 - log < limit) {
323  buf >>= log - k;
324  buf += (30 - log) << k;
325  LAST_SKIP_BITS(re, gb, 32 + k - log);
326  CLOSE_READER(re, gb);
327 
328  return buf;
329  } else {
330  int i;
331  for (i = 0; i < limit && SHOW_UBITS(re, gb, 1) == 0 && HAVE_BITS_REMAINING(re, gb); i++) {
332  LAST_SKIP_BITS(re, gb, 1);
333  UPDATE_CACHE(re, gb);
334  }
335  SKIP_BITS(re, gb, 1);
336 
337  if (i < limit - 1) {
338  if (k) {
339  buf = SHOW_UBITS(re, gb, k);
340  LAST_SKIP_BITS(re, gb, k);
341  } else {
342  buf = 0;
343  }
344 
345  CLOSE_READER(re, gb);
346  return buf + (i << k);
347  } else if (i == limit - 1) {
348  buf = SHOW_UBITS(re, gb, esc_len);
349  LAST_SKIP_BITS(re, gb, esc_len);
350  CLOSE_READER(re, gb);
351 
352  return buf + 1;
353  } else
354  return -1;
355  }
356 }
357 
361 static inline int get_sr_golomb(GetBitContext *gb, int k, int limit,
362  int esc_len)
363 {
364  int v = get_ur_golomb(gb, k, limit, esc_len);
365 
366  v++;
367  if (v & 1)
368  return v >> 1;
369  else
370  return -(v >> 1);
371 
372 // return (v>>1) ^ -(v&1);
373 }
374 
378 static inline int get_sr_golomb_flac(GetBitContext *gb, int k, int limit,
379  int esc_len)
380 {
381  int v = get_ur_golomb_jpegls(gb, k, limit, esc_len);
382  return (v >> 1) ^ -(v & 1);
383 }
384 
388 static inline unsigned int get_ur_golomb_shorten(GetBitContext *gb, int k)
389 {
390  return get_ur_golomb_jpegls(gb, k, INT_MAX, 0);
391 }
392 
396 static inline int get_sr_golomb_shorten(GetBitContext *gb, int k)
397 {
398  int uvar = get_ur_golomb_jpegls(gb, k + 1, INT_MAX, 0);
399  if (uvar & 1)
400  return ~(uvar >> 1);
401  else
402  return uvar >> 1;
403 }
404 
405 #ifdef TRACE
406 
407 static inline int get_ue(GetBitContext *s, const char *file, const char *func,
408  int line)
409 {
410  int show = show_bits(s, 24);
411  int pos = get_bits_count(s);
412  int i = get_ue_golomb(s);
413  int len = get_bits_count(s) - pos;
414  int bits = show >> (24 - len);
415 
416  print_bin(bits, len);
417 
418  av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d ue @%5d in %s %s:%d\n",
419  bits, len, i, pos, file, func, line);
420 
421  return i;
422 }
423 
424 static inline int get_se(GetBitContext *s, const char *file, const char *func,
425  int line)
426 {
427  int show = show_bits(s, 24);
428  int pos = get_bits_count(s);
429  int i = get_se_golomb(s);
430  int len = get_bits_count(s) - pos;
431  int bits = show >> (24 - len);
432 
433  print_bin(bits, len);
434 
435  av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d se @%5d in %s %s:%d\n",
436  bits, len, i, pos, file, func, line);
437 
438  return i;
439 }
440 
441 static inline int get_te(GetBitContext *s, int r, char *file, const char *func,
442  int line)
443 {
444  int show = show_bits(s, 24);
445  int pos = get_bits_count(s);
446  int i = get_te0_golomb(s, r);
447  int len = get_bits_count(s) - pos;
448  int bits = show >> (24 - len);
449 
450  print_bin(bits, len);
451 
452  av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d te @%5d in %s %s:%d\n",
453  bits, len, i, pos, file, func, line);
454 
455  return i;
456 }
457 
458 #define get_ue_golomb(a) get_ue(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
459 #define get_se_golomb(a) get_se(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
460 #define get_te_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
461 #define get_te0_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
462 
463 #endif /* TRACE */
464 
468 static inline void set_ue_golomb(PutBitContext *pb, int i)
469 {
470  assert(i >= 0);
471 
472 #if 0
473  if (i = 0) {
474  put_bits(pb, 1, 1);
475  return;
476  }
477 #endif
478  if (i < 256)
479  put_bits(pb, ff_ue_golomb_len[i], i + 1);
480  else {
481  int e = av_log2(i + 1);
482  put_bits(pb, 2 * e + 1, i + 1);
483  }
484 }
485 
489 static inline void set_te_golomb(PutBitContext *pb, int i, int range)
490 {
491  assert(range >= 1);
492  assert(i <= range);
493 
494  if (range == 2)
495  put_bits(pb, 1, i ^ 1);
496  else
497  set_ue_golomb(pb, i);
498 }
499 
503 static inline void set_se_golomb(PutBitContext *pb, int i)
504 {
505 #if 0
506  if (i <= 0)
507  i = -2 * i;
508  else
509  i = 2 * i - 1;
510 #elif 1
511  i = 2 * i - 1;
512  if (i < 0)
513  i ^= -1; //FIXME check if gcc does the right thing
514 #else
515  i = 2 * i - 1;
516  i ^= (i >> 31);
517 #endif
518  set_ue_golomb(pb, i);
519 }
520 
524 static inline void set_ur_golomb(PutBitContext *pb, int i, int k, int limit,
525  int esc_len)
526 {
527  int e;
528 
529  assert(i >= 0);
530 
531  e = i >> k;
532  if (e < limit)
533  put_bits(pb, e + k + 1, (1 << k) + (i & ((1 << k) - 1)));
534  else
535  put_bits(pb, limit + esc_len, i - limit + 1);
536 }
537 
541 static inline void set_ur_golomb_jpegls(PutBitContext *pb, int i, int k,
542  int limit, int esc_len)
543 {
544  int e;
545 
546  assert(i >= 0);
547 
548  e = (i >> k) + 1;
549  if (e < limit) {
550  while (e > 31) {
551  put_bits(pb, 31, 0);
552  e -= 31;
553  }
554  put_bits(pb, e, 1);
555  if (k)
556  put_sbits(pb, k, i);
557  } else {
558  while (limit > 31) {
559  put_bits(pb, 31, 0);
560  limit -= 31;
561  }
562  put_bits(pb, limit, 1);
563  put_bits(pb, esc_len, i - 1);
564  }
565 }
566 
570 static inline void set_sr_golomb(PutBitContext *pb, int i, int k, int limit,
571  int esc_len)
572 {
573  int v;
574 
575  v = -2 * i - 1;
576  v ^= (v >> 31);
577 
578  set_ur_golomb(pb, v, k, limit, esc_len);
579 }
580 
584 static inline void set_sr_golomb_flac(PutBitContext *pb, int i, int k,
585  int limit, int esc_len)
586 {
587  int v;
588 
589  v = -2 * i - 1;
590  v ^= (v >> 31);
591 
592  set_ur_golomb_jpegls(pb, v, k, limit, esc_len);
593 }
594 
595 #endif /* AVCODEC_GOLOMB_H */