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 #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 
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 
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  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 (HAVE_BITS_REMAINING(re, gb));
140 
141  CLOSE_READER(re, gb);
142  return ret - 1;
143  }
144 }
145 
149 static inline int get_te0_golomb(GetBitContext *gb, int range){
150  assert(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 
160 static inline int get_te_golomb(GetBitContext *gb, int range){
161  assert(range >= 1);
162 
163  if(range==2) return get_bits1(gb)^1;
164  else return get_ue_golomb(gb);
165 }
166 
167 
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 
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 
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 && HAVE_BITS_REMAINING(re, gb); i++) {
306  LAST_SKIP_BITS(re, gb, 1);
307  UPDATE_CACHE(re, gb);
308  }
309  SKIP_BITS(re, gb, 1);
310 
311  if(i < limit - 1){
312  if(k){
313  buf = SHOW_UBITS(re, gb, k);
314  LAST_SKIP_BITS(re, gb, k);
315  }else{
316  buf=0;
317  }
318 
319  CLOSE_READER(re, gb);
320  return buf + (i<<k);
321  }else if(i == limit - 1){
322  buf = SHOW_UBITS(re, gb, esc_len);
323  LAST_SKIP_BITS(re, gb, esc_len);
324  CLOSE_READER(re, gb);
325 
326  return buf + 1;
327  }else
328  return -1;
329  }
330 }
331 
335 static inline int get_sr_golomb(GetBitContext *gb, int k, int limit, int esc_len){
336  int v= get_ur_golomb(gb, k, limit, esc_len);
337 
338  v++;
339  if (v&1) return v>>1;
340  else return -(v>>1);
341 
342 // return (v>>1) ^ -(v&1);
343 }
344 
348 static inline int get_sr_golomb_flac(GetBitContext *gb, int k, int limit, int esc_len){
349  int v= get_ur_golomb_jpegls(gb, k, limit, esc_len);
350  return (v>>1) ^ -(v&1);
351 }
352 
356 static inline unsigned int get_ur_golomb_shorten(GetBitContext *gb, int k){
357  return get_ur_golomb_jpegls(gb, k, INT_MAX, 0);
358 }
359 
363 static inline int get_sr_golomb_shorten(GetBitContext* gb, int k)
364 {
365  int uvar = get_ur_golomb_jpegls(gb, k + 1, INT_MAX, 0);
366  if (uvar & 1)
367  return ~(uvar >> 1);
368  else
369  return uvar >> 1;
370 }
371 
372 
373 
374 #ifdef TRACE
375 
376 static inline int get_ue(GetBitContext *s, const char *file, const char *func,
377  int line)
378 {
379  int show= show_bits(s, 24);
380  int pos= get_bits_count(s);
381  int i= get_ue_golomb(s);
382  int len= get_bits_count(s) - pos;
383  int bits= show>>(24-len);
384 
385  print_bin(bits, len);
386 
387  av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d ue @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
388 
389  return i;
390 }
391 
392 static inline int get_se(GetBitContext *s, const char *file, const char *func,
393  int line)
394 {
395  int show= show_bits(s, 24);
396  int pos= get_bits_count(s);
397  int i= get_se_golomb(s);
398  int len= get_bits_count(s) - pos;
399  int bits= show>>(24-len);
400 
401  print_bin(bits, len);
402 
403  av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d se @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
404 
405  return i;
406 }
407 
408 static inline int get_te(GetBitContext *s, int r, char *file, const char *func, int line){
409  int show= show_bits(s, 24);
410  int pos= get_bits_count(s);
411  int i= get_te0_golomb(s, r);
412  int len= get_bits_count(s) - pos;
413  int bits= show>>(24-len);
414 
415  print_bin(bits, len);
416 
417  av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d te @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
418 
419  return i;
420 }
421 
422 #define get_ue_golomb(a) get_ue(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
423 #define get_se_golomb(a) get_se(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
424 #define get_te_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
425 #define get_te0_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
426 
427 #endif
428 
432 static inline void set_ue_golomb(PutBitContext *pb, int i){
433  int e;
434 
435  assert(i>=0);
436 
437 #if 0
438  if(i=0){
439  put_bits(pb, 1, 1);
440  return;
441  }
442 #endif
443  if(i<256)
444  put_bits(pb, ff_ue_golomb_len[i], i+1);
445  else{
446  e= av_log2(i+1);
447 
448  put_bits(pb, 2*e+1, i+1);
449  }
450 }
451 
455 static inline void set_te_golomb(PutBitContext *pb, int i, int range){
456  assert(range >= 1);
457  assert(i<=range);
458 
459  if(range==2) put_bits(pb, 1, i^1);
460  else set_ue_golomb(pb, i);
461 }
462 
466 static inline void set_se_golomb(PutBitContext *pb, int i){
467 #if 0
468  if(i<=0) i= -2*i;
469  else i= 2*i-1;
470 #elif 1
471  i= 2*i-1;
472  if(i<0) i^= -1; //FIXME check if gcc does the right thing
473 #else
474  i= 2*i-1;
475  i^= (i>>31);
476 #endif
477  set_ue_golomb(pb, i);
478 }
479 
483 static inline void set_ur_golomb(PutBitContext *pb, int i, int k, int limit, int esc_len){
484  int e;
485 
486  assert(i>=0);
487 
488  e= i>>k;
489  if(e<limit){
490  put_bits(pb, e + k + 1, (1<<k) + (i&((1<<k)-1)));
491  }else{
492  put_bits(pb, limit + esc_len, i - limit + 1);
493  }
494 }
495 
499 static inline void set_ur_golomb_jpegls(PutBitContext *pb, int i, int k, int limit, int esc_len){
500  int e;
501 
502  assert(i>=0);
503 
504  e= (i>>k) + 1;
505  if(e<limit){
506  while(e > 31) {
507  put_bits(pb, 31, 0);
508  e -= 31;
509  }
510  put_bits(pb, e, 1);
511  if(k)
512  put_sbits(pb, k, i);
513  }else{
514  while(limit > 31) {
515  put_bits(pb, 31, 0);
516  limit -= 31;
517  }
518  put_bits(pb, limit , 1);
519  put_bits(pb, esc_len, i - 1);
520  }
521 }
522 
526 static inline void set_sr_golomb(PutBitContext *pb, int i, int k, int limit, int esc_len){
527  int v;
528 
529  v = -2*i-1;
530  v ^= (v>>31);
531 
532  set_ur_golomb(pb, v, k, limit, esc_len);
533 }
534 
538 static inline void set_sr_golomb_flac(PutBitContext *pb, int i, int k, int limit, int esc_len){
539  int v;
540 
541  v = -2*i-1;
542  v ^= (v>>31);
543 
544  set_ur_golomb_jpegls(pb, v, k, limit, esc_len);
545 }
546 
547 #endif /* AVCODEC_GOLOMB_H */