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