FFmpeg
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
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 
23 /**
24  * @file
25  * @brief
26  * exp golomb vlc stuff
27  * @author Michael Niedermayer <michaelni@gmx.at> and Alex Beregszaszi
28  */
29 
30 #ifndef AVCODEC_GOLOMB_H
31 #define AVCODEC_GOLOMB_H
32 
33 #include <stdint.h>
34 #include "get_bits.h"
35 #include "put_bits.h"
36 
37 #define INVALID_VLC 0x80000000
38 
39 extern const uint8_t ff_golomb_vlc_len[512];
40 extern const uint8_t ff_ue_golomb_vlc_code[512];
41 extern const int8_t ff_se_golomb_vlc_code[512];
42 extern const uint8_t ff_ue_golomb_len[256];
43 
44 extern const uint8_t ff_interleaved_golomb_vlc_len[256];
46 extern const int8_t ff_interleaved_se_golomb_vlc_code[256];
48 
49 
50  /**
51  * read unsigned exp golomb code.
52  */
53 static inline int get_ue_golomb(GetBitContext *gb){
54  unsigned int buf;
55  int log;
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  log= 2*av_log2(buf) - 31;
69  LAST_SKIP_BITS(re, gb, 32 - log);
70  CLOSE_READER(re, gb);
71  if (CONFIG_FTRAPV && log < 0) {
72  av_log(0, AV_LOG_ERROR, "Invalid UE golomb code\n");
73  return AVERROR_INVALIDDATA;
74  }
75  buf>>= log;
76  buf--;
77 
78  return buf;
79  }
80 }
81 
82 /**
83  * Read an unsigned Exp-Golomb code in the range 0 to UINT32_MAX-1.
84  */
85 static inline unsigned get_ue_golomb_long(GetBitContext *gb)
86 {
87  unsigned buf, log;
88 
89  buf = show_bits_long(gb, 32);
90  log = 31 - av_log2(buf);
91  skip_bits_long(gb, log);
92 
93  return get_bits_long(gb, log + 1) - 1;
94 }
95 
96  /**
97  * read unsigned exp golomb code, constraint to a max of 31.
98  * the return value is undefined if the stored value exceeds 31.
99  */
100 static inline int get_ue_golomb_31(GetBitContext *gb){
101  unsigned int buf;
102 
103  OPEN_READER(re, gb);
104  UPDATE_CACHE(re, gb);
105  buf=GET_CACHE(re, gb);
106 
107  buf >>= 32 - 9;
109  CLOSE_READER(re, gb);
110 
111  return ff_ue_golomb_vlc_code[buf];
112 }
113 
114 static inline unsigned svq3_get_ue_golomb(GetBitContext *gb)
115 {
116  uint32_t buf;
117 
118  OPEN_READER(re, gb);
119  UPDATE_CACHE(re, gb);
120  buf=GET_CACHE(re, gb);
121 
122  if(buf&0xAA800000){
123  buf >>= 32 - 8;
125  CLOSE_READER(re, gb);
126 
128  }else{
129  unsigned ret = 1;
130 
131  do {
132  buf >>= 32 - 8;
134 
135  if (ff_interleaved_golomb_vlc_len[buf] != 9){
136  ret <<= (ff_interleaved_golomb_vlc_len[buf] - 1) >> 1;
138  break;
139  }
140  ret = (ret << 4) | ff_interleaved_dirac_golomb_vlc_code[buf];
141  UPDATE_CACHE(re, gb);
142  buf = GET_CACHE(re, gb);
143  } while (ret<0x8000000U && HAVE_BITS_REMAINING(re, gb));
144 
145  CLOSE_READER(re, gb);
146  return ret - 1;
147  }
148 }
149 
150 /**
151  * read unsigned truncated exp golomb code.
152  */
153 static inline int get_te0_golomb(GetBitContext *gb, int range){
154  av_assert2(range >= 1);
155 
156  if(range==1) return 0;
157  else if(range==2) return get_bits1(gb)^1;
158  else return get_ue_golomb(gb);
159 }
160 
161 /**
162  * read unsigned truncated exp golomb code.
163  */
164 static inline int get_te_golomb(GetBitContext *gb, int range){
165  av_assert2(range >= 1);
166 
167  if(range==2) return get_bits1(gb)^1;
168  else return get_ue_golomb(gb);
169 }
170 
171 
172 /**
173  * read signed exp golomb code.
174  */
175 static inline int get_se_golomb(GetBitContext *gb){
176  unsigned int buf;
177  int log;
178 
179  OPEN_READER(re, gb);
180  UPDATE_CACHE(re, gb);
181  buf=GET_CACHE(re, gb);
182 
183  if(buf >= (1<<27)){
184  buf >>= 32 - 9;
186  CLOSE_READER(re, gb);
187 
188  return ff_se_golomb_vlc_code[buf];
189  }else{
190  log = av_log2(buf);
191  LAST_SKIP_BITS(re, gb, 31 - log);
192  UPDATE_CACHE(re, gb);
193  buf = GET_CACHE(re, gb);
194 
195  buf>>= log;
196 
197  LAST_SKIP_BITS(re, gb, 32 - log);
198  CLOSE_READER(re, gb);
199 
200  if(buf&1) buf= -(buf>>1);
201  else buf= (buf>>1);
202 
203  return buf;
204  }
205 }
206 
207 static inline int svq3_get_se_golomb(GetBitContext *gb){
208  unsigned int buf;
209  int log;
210 
211  OPEN_READER(re, gb);
212  UPDATE_CACHE(re, gb);
213  buf=GET_CACHE(re, gb);
214 
215  if(buf&0xAA800000){
216  buf >>= 32 - 8;
218  CLOSE_READER(re, gb);
219 
221  }else{
222  LAST_SKIP_BITS(re, gb, 8);
223  UPDATE_CACHE(re, gb);
224  buf |= 1 | (GET_CACHE(re, gb) >> 8);
225 
226  if((buf & 0xAAAAAAAA) == 0)
227  return INVALID_VLC;
228 
229  for(log=31; (buf & 0x80000000) == 0; log--){
230  buf = (buf << 2) - ((buf << log) >> (log - 1)) + (buf >> 30);
231  }
232 
233  LAST_SKIP_BITS(re, gb, 63 - 2*log - 8);
234  CLOSE_READER(re, gb);
235 
236  return (signed) (((((buf << log) >> log) - 1) ^ -(buf & 0x1)) + 1) >> 1;
237  }
238 }
239 
240 static inline int dirac_get_se_golomb(GetBitContext *gb){
241  uint32_t buf;
242  uint32_t ret;
243 
244  ret = svq3_get_ue_golomb(gb);
245 
246  if (ret) {
247  OPEN_READER(re, gb);
248  UPDATE_CACHE(re, gb);
249  buf = SHOW_SBITS(re, gb, 1);
250  LAST_SKIP_BITS(re, gb, 1);
251  ret = (ret ^ buf) - buf;
252  CLOSE_READER(re, gb);
253  }
254 
255  return ret;
256 }
257 
258 /**
259  * read unsigned golomb rice code (ffv1).
260  */
261 static inline int get_ur_golomb(GetBitContext *gb, int k, int limit, int esc_len){
262  unsigned int buf;
263  int log;
264 
265  OPEN_READER(re, gb);
266  UPDATE_CACHE(re, gb);
267  buf=GET_CACHE(re, gb);
268 
269  log= av_log2(buf);
270 
271  if(log > 31-limit){
272  buf >>= log - k;
273  buf += (30-log)<<k;
274  LAST_SKIP_BITS(re, gb, 32 + k - log);
275  CLOSE_READER(re, gb);
276 
277  return buf;
278  }else{
279  LAST_SKIP_BITS(re, gb, limit);
280  UPDATE_CACHE(re, gb);
281 
282  buf = SHOW_UBITS(re, gb, esc_len);
283 
284  LAST_SKIP_BITS(re, gb, esc_len);
285  CLOSE_READER(re, gb);
286 
287  return buf + limit - 1;
288  }
289 }
290 
291 /**
292  * read unsigned golomb rice code (jpegls).
293  */
294 static inline int get_ur_golomb_jpegls(GetBitContext *gb, int k, int limit, int esc_len){
295  unsigned int buf;
296  int log;
297 
298  OPEN_READER(re, gb);
299  UPDATE_CACHE(re, gb);
300  buf=GET_CACHE(re, gb);
301 
302  log= av_log2(buf);
303 
304  if(log - k >= 32-MIN_CACHE_BITS+(MIN_CACHE_BITS==32) && 32-log < limit){
305  buf >>= log - k;
306  buf += (30-log)<<k;
307  LAST_SKIP_BITS(re, gb, 32 + k - log);
308  CLOSE_READER(re, gb);
309 
310  return buf;
311  }else{
312  int i;
313  for (i = 0; i < limit && SHOW_UBITS(re, gb, 1) == 0; i++) {
314  if (gb->size_in_bits <= re_index)
315  return -1;
316  LAST_SKIP_BITS(re, gb, 1);
317  UPDATE_CACHE(re, gb);
318  }
319  SKIP_BITS(re, gb, 1);
320 
321  if(i < limit - 1){
322  if(k){
323  buf = SHOW_UBITS(re, gb, k);
324  LAST_SKIP_BITS(re, gb, k);
325  }else{
326  buf=0;
327  }
328 
329  CLOSE_READER(re, gb);
330  return buf + (i<<k);
331  }else if(i == limit - 1){
332  buf = SHOW_UBITS(re, gb, esc_len);
333  LAST_SKIP_BITS(re, gb, esc_len);
334  CLOSE_READER(re, gb);
335 
336  return buf + 1;
337  }else
338  return -1;
339  }
340 }
341 
342 /**
343  * read signed golomb rice code (ffv1).
344  */
345 static inline int get_sr_golomb(GetBitContext *gb, int k, int limit, int esc_len){
346  int v= get_ur_golomb(gb, k, limit, esc_len);
347 
348  v++;
349  if (v&1) return v>>1;
350  else return -(v>>1);
351 
352 // return (v>>1) ^ -(v&1);
353 }
354 
355 /**
356  * read signed golomb rice code (flac).
357  */
358 static inline int get_sr_golomb_flac(GetBitContext *gb, int k, int limit, int esc_len){
359  int v= get_ur_golomb_jpegls(gb, k, limit, esc_len);
360  return (v>>1) ^ -(v&1);
361 }
362 
363 /**
364  * read unsigned golomb rice code (shorten).
365  */
366 static inline unsigned int get_ur_golomb_shorten(GetBitContext *gb, int k){
367  return get_ur_golomb_jpegls(gb, k, INT_MAX, 0);
368 }
369 
370 /**
371  * read signed golomb rice code (shorten).
372  */
373 static inline int get_sr_golomb_shorten(GetBitContext* gb, int k)
374 {
375  int uvar = get_ur_golomb_jpegls(gb, k + 1, INT_MAX, 0);
376  if (uvar & 1)
377  return ~(uvar >> 1);
378  else
379  return uvar >> 1;
380 }
381 
382 
383 
384 #ifdef TRACE
385 
386 static inline int get_ue(GetBitContext *s, const char *file, const char *func,
387  int line)
388 {
389  int show= show_bits(s, 24);
390  int pos= get_bits_count(s);
391  int i= get_ue_golomb(s);
392  int len= get_bits_count(s) - pos;
393  int bits= show>>(24-len);
394 
395  print_bin(bits, len);
396 
397  av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d ue @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
398 
399  return i;
400 }
401 
402 static inline int get_se(GetBitContext *s, const char *file, const char *func,
403  int line)
404 {
405  int show= show_bits(s, 24);
406  int pos= get_bits_count(s);
407  int i= get_se_golomb(s);
408  int len= get_bits_count(s) - pos;
409  int bits= show>>(24-len);
410 
411  print_bin(bits, len);
412 
413  av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d se @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
414 
415  return i;
416 }
417 
418 static inline int get_te(GetBitContext *s, int r, char *file, const char *func, int line){
419  int show= show_bits(s, 24);
420  int pos= get_bits_count(s);
421  int i= get_te0_golomb(s, r);
422  int len= get_bits_count(s) - pos;
423  int bits= show>>(24-len);
424 
425  print_bin(bits, len);
426 
427  av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d te @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
428 
429  return i;
430 }
431 
432 #define get_ue_golomb(a) get_ue(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
433 #define get_se_golomb(a) get_se(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
434 #define get_te_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
435 #define get_te0_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
436 
437 #endif
438 
439 /**
440  * write unsigned exp golomb code.
441  */
442 static inline void set_ue_golomb(PutBitContext *pb, int i){
443  int e;
444 
445  av_assert2(i>=0);
446 
447 #if 0
448  if(i=0){
449  put_bits(pb, 1, 1);
450  return;
451  }
452 #endif
453  if(i<256)
454  put_bits(pb, ff_ue_golomb_len[i], i+1);
455  else{
456  e= av_log2(i+1);
457 
458  put_bits(pb, 2*e+1, i+1);
459  }
460 }
461 
462 /**
463  * write truncated unsigned exp golomb code.
464  */
465 static inline void set_te_golomb(PutBitContext *pb, int i, int range){
466  av_assert2(range >= 1);
467  av_assert2(i<=range);
468 
469  if(range==2) put_bits(pb, 1, i^1);
470  else set_ue_golomb(pb, i);
471 }
472 
473 /**
474  * write signed exp golomb code. 16 bits at most.
475  */
476 static inline void set_se_golomb(PutBitContext *pb, int i){
477 #if 0
478  if(i<=0) i= -2*i;
479  else i= 2*i-1;
480 #elif 1
481  i= 2*i-1;
482  if(i<0) i^= -1; //FIXME check if gcc does the right thing
483 #else
484  i= 2*i-1;
485  i^= (i>>31);
486 #endif
487  set_ue_golomb(pb, i);
488 }
489 
490 /**
491  * write unsigned golomb rice code (ffv1).
492  */
493 static inline void set_ur_golomb(PutBitContext *pb, int i, int k, int limit, int esc_len){
494  int e;
495 
496  av_assert2(i>=0);
497 
498  e= i>>k;
499  if(e<limit){
500  put_bits(pb, e + k + 1, (1<<k) + (i&((1<<k)-1)));
501  }else{
502  put_bits(pb, limit + esc_len, i - limit + 1);
503  }
504 }
505 
506 /**
507  * write unsigned golomb rice code (jpegls).
508  */
509 static inline void set_ur_golomb_jpegls(PutBitContext *pb, int i, int k, int limit, int esc_len){
510  int e;
511 
512  av_assert2(i>=0);
513 
514  e= (i>>k) + 1;
515  if(e<limit){
516  while(e > 31) {
517  put_bits(pb, 31, 0);
518  e -= 31;
519  }
520  put_bits(pb, e, 1);
521  if(k)
522  put_sbits(pb, k, i);
523  }else{
524  while(limit > 31) {
525  put_bits(pb, 31, 0);
526  limit -= 31;
527  }
528  put_bits(pb, limit , 1);
529  put_bits(pb, esc_len, i - 1);
530  }
531 }
532 
533 /**
534  * write signed golomb rice code (ffv1).
535  */
536 static inline void set_sr_golomb(PutBitContext *pb, int i, int k, int limit, int esc_len){
537  int v;
538 
539  v = -2*i-1;
540  v ^= (v>>31);
541 
542  set_ur_golomb(pb, v, k, limit, esc_len);
543 }
544 
545 /**
546  * write signed golomb rice code (flac).
547  */
548 static inline void set_sr_golomb_flac(PutBitContext *pb, int i, int k, int limit, int esc_len){
549  int v;
550 
551  v = -2*i-1;
552  v ^= (v>>31);
553 
554  set_ur_golomb_jpegls(pb, v, k, limit, esc_len);
555 }
556 
557 #endif /* AVCODEC_GOLOMB_H */