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];
45 extern const uint8_t ff_interleaved_ue_golomb_vlc_code[256];
46 extern const int8_t ff_interleaved_se_golomb_vlc_code[256];
47 extern const uint8_t ff_interleaved_dirac_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 int svq3_get_ue_golomb(GetBitContext *gb){
111  uint32_t buf;
112 
113  OPEN_READER(re, gb);
114  UPDATE_CACHE(re, gb);
115  buf=GET_CACHE(re, gb);
116 
117  if(buf&0xAA800000){
118  buf >>= 32 - 8;
120  CLOSE_READER(re, gb);
121 
123  }else{
124  int ret = 1;
125 
126  do {
127  buf >>= 32 - 8;
129 
130  if (ff_interleaved_golomb_vlc_len[buf] != 9){
131  ret <<= (ff_interleaved_golomb_vlc_len[buf] - 1) >> 1;
133  break;
134  }
135  ret = (ret << 4) | ff_interleaved_dirac_golomb_vlc_code[buf];
136  UPDATE_CACHE(re, gb);
137  buf = GET_CACHE(re, gb);
138  } while (HAVE_BITS_REMAINING(re, gb));
139 
140  CLOSE_READER(re, gb);
141  return ret - 1;
142  }
143 }
144 
148 static inline int get_te0_golomb(GetBitContext *gb, int range){
149  assert(range >= 1);
150 
151  if(range==1) return 0;
152  else if(range==2) return get_bits1(gb)^1;
153  else return get_ue_golomb(gb);
154 }
155 
159 static inline int get_te_golomb(GetBitContext *gb, int range){
160  assert(range >= 1);
161 
162  if(range==2) return get_bits1(gb)^1;
163  else return get_ue_golomb(gb);
164 }
165 
166 
170 static inline int get_se_golomb(GetBitContext *gb){
171  unsigned int buf;
172  int log;
173 
174  OPEN_READER(re, gb);
175  UPDATE_CACHE(re, gb);
176  buf=GET_CACHE(re, gb);
177 
178  if(buf >= (1<<27)){
179  buf >>= 32 - 9;
181  CLOSE_READER(re, gb);
182 
183  return ff_se_golomb_vlc_code[buf];
184  }else{
185  log= 2*av_log2(buf) - 31;
186  buf>>= log;
187 
188  LAST_SKIP_BITS(re, gb, 32 - log);
189  CLOSE_READER(re, gb);
190 
191  if(buf&1) buf= -(buf>>1);
192  else buf= (buf>>1);
193 
194  return buf;
195  }
196 }
197 
198 static inline int svq3_get_se_golomb(GetBitContext *gb){
199  unsigned int buf;
200  int log;
201 
202  OPEN_READER(re, gb);
203  UPDATE_CACHE(re, gb);
204  buf=GET_CACHE(re, gb);
205 
206  if(buf&0xAA800000){
207  buf >>= 32 - 8;
209  CLOSE_READER(re, gb);
210 
212  }else{
213  LAST_SKIP_BITS(re, gb, 8);
214  UPDATE_CACHE(re, gb);
215  buf |= 1 | (GET_CACHE(re, gb) >> 8);
216 
217  if((buf & 0xAAAAAAAA) == 0)
218  return INVALID_VLC;
219 
220  for(log=31; (buf & 0x80000000) == 0; log--){
221  buf = (buf << 2) - ((buf << log) >> (log - 1)) + (buf >> 30);
222  }
223 
224  LAST_SKIP_BITS(re, gb, 63 - 2*log - 8);
225  CLOSE_READER(re, gb);
226 
227  return (signed) (((((buf << log) >> log) - 1) ^ -(buf & 0x1)) + 1) >> 1;
228  }
229 }
230 
231 static inline int dirac_get_se_golomb(GetBitContext *gb){
232  uint32_t buf;
233  uint32_t ret;
234 
235  ret = svq3_get_ue_golomb(gb);
236 
237  if (ret) {
238  OPEN_READER(re, gb);
239  UPDATE_CACHE(re, gb);
240  buf = SHOW_SBITS(re, gb, 1);
241  LAST_SKIP_BITS(re, gb, 1);
242  ret = (ret ^ buf) - buf;
243  CLOSE_READER(re, gb);
244  }
245 
246  return ret;
247 }
248 
252 static inline int get_ur_golomb(GetBitContext *gb, int k, int limit, int esc_len){
253  unsigned int buf;
254  int log;
255 
256  OPEN_READER(re, gb);
257  UPDATE_CACHE(re, gb);
258  buf=GET_CACHE(re, gb);
259 
260  log= av_log2(buf);
261 
262  if(log > 31-limit){
263  buf >>= log - k;
264  buf += (30-log)<<k;
265  LAST_SKIP_BITS(re, gb, 32 + k - log);
266  CLOSE_READER(re, gb);
267 
268  return buf;
269  }else{
270  LAST_SKIP_BITS(re, gb, limit);
271  UPDATE_CACHE(re, gb);
272 
273  buf = SHOW_UBITS(re, gb, esc_len);
274 
275  LAST_SKIP_BITS(re, gb, esc_len);
276  CLOSE_READER(re, gb);
277 
278  return buf + limit - 1;
279  }
280 }
281 
285 static inline int get_ur_golomb_jpegls(GetBitContext *gb, int k, int limit, int esc_len){
286  unsigned int buf;
287  int log;
288 
289  OPEN_READER(re, gb);
290  UPDATE_CACHE(re, gb);
291  buf=GET_CACHE(re, gb);
292 
293  log= av_log2(buf);
294 
295  if(log - k >= 32-MIN_CACHE_BITS+(MIN_CACHE_BITS==32) && 32-log < limit){
296  buf >>= log - k;
297  buf += (30-log)<<k;
298  LAST_SKIP_BITS(re, gb, 32 + k - log);
299  CLOSE_READER(re, gb);
300 
301  return buf;
302  }else{
303  int i;
304  for (i = 0; i < limit && SHOW_UBITS(re, gb, 1) == 0 && HAVE_BITS_REMAINING(re, gb); i++) {
305  LAST_SKIP_BITS(re, gb, 1);
306  UPDATE_CACHE(re, gb);
307  }
308  SKIP_BITS(re, gb, 1);
309 
310  if(i < limit - 1){
311  if(k){
312  buf = SHOW_UBITS(re, gb, k);
313  LAST_SKIP_BITS(re, gb, k);
314  }else{
315  buf=0;
316  }
317 
318  CLOSE_READER(re, gb);
319  return buf + (i<<k);
320  }else if(i == limit - 1){
321  buf = SHOW_UBITS(re, gb, esc_len);
322  LAST_SKIP_BITS(re, gb, esc_len);
323  CLOSE_READER(re, gb);
324 
325  return buf + 1;
326  }else
327  return -1;
328  }
329 }
330 
334 static inline int get_sr_golomb(GetBitContext *gb, int k, int limit, int esc_len){
335  int v= get_ur_golomb(gb, k, limit, esc_len);
336 
337  v++;
338  if (v&1) return v>>1;
339  else return -(v>>1);
340 
341 // return (v>>1) ^ -(v&1);
342 }
343 
347 static inline int get_sr_golomb_flac(GetBitContext *gb, int k, int limit, int esc_len){
348  int v= get_ur_golomb_jpegls(gb, k, limit, esc_len);
349  return (v>>1) ^ -(v&1);
350 }
351 
355 static inline unsigned int get_ur_golomb_shorten(GetBitContext *gb, int k){
356  return get_ur_golomb_jpegls(gb, k, INT_MAX, 0);
357 }
358 
362 static inline int get_sr_golomb_shorten(GetBitContext* gb, int k)
363 {
364  int uvar = get_ur_golomb_jpegls(gb, k + 1, INT_MAX, 0);
365  if (uvar & 1)
366  return ~(uvar >> 1);
367  else
368  return uvar >> 1;
369 }
370 
371 
372 
373 #ifdef TRACE
374 
375 static inline int get_ue(GetBitContext *s, char *file, const char *func, int line){
376  int show= show_bits(s, 24);
377  int pos= get_bits_count(s);
378  int i= get_ue_golomb(s);
379  int len= get_bits_count(s) - pos;
380  int bits= show>>(24-len);
381 
382  print_bin(bits, len);
383 
384  av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d ue @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
385 
386  return i;
387 }
388 
389 static inline int get_se(GetBitContext *s, char *file, const char *func, int line){
390  int show= show_bits(s, 24);
391  int pos= get_bits_count(s);
392  int i= get_se_golomb(s);
393  int len= get_bits_count(s) - pos;
394  int bits= show>>(24-len);
395 
396  print_bin(bits, len);
397 
398  av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d se @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
399 
400  return i;
401 }
402 
403 static inline int get_te(GetBitContext *s, int r, char *file, const char *func, int line){
404  int show= show_bits(s, 24);
405  int pos= get_bits_count(s);
406  int i= get_te0_golomb(s, r);
407  int len= get_bits_count(s) - pos;
408  int bits= show>>(24-len);
409 
410  print_bin(bits, len);
411 
412  av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d te @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
413 
414  return i;
415 }
416 
417 #define get_ue_golomb(a) get_ue(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
418 #define get_se_golomb(a) get_se(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
419 #define get_te_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
420 #define get_te0_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
421 
422 #endif
423 
427 static inline void set_ue_golomb(PutBitContext *pb, int i){
428  int e;
429 
430  assert(i>=0);
431 
432 #if 0
433  if(i=0){
434  put_bits(pb, 1, 1);
435  return;
436  }
437 #endif
438  if(i<256)
439  put_bits(pb, ff_ue_golomb_len[i], i+1);
440  else{
441  e= av_log2(i+1);
442 
443  put_bits(pb, 2*e+1, i+1);
444  }
445 }
446 
450 static inline void set_te_golomb(PutBitContext *pb, int i, int range){
451  assert(range >= 1);
452  assert(i<=range);
453 
454  if(range==2) put_bits(pb, 1, i^1);
455  else set_ue_golomb(pb, i);
456 }
457 
461 static inline void set_se_golomb(PutBitContext *pb, int i){
462 // if (i>32767 || i<-32767)
463 // av_log(NULL,AV_LOG_ERROR,"value out of range %d\n", i);
464 #if 0
465  if(i<=0) i= -2*i;
466  else i= 2*i-1;
467 #elif 1
468  i= 2*i-1;
469  if(i<0) i^= -1; //FIXME check if gcc does the right thing
470 #else
471  i= 2*i-1;
472  i^= (i>>31);
473 #endif
474  set_ue_golomb(pb, i);
475 }
476 
480 static inline void set_ur_golomb(PutBitContext *pb, int i, int k, int limit, int esc_len){
481  int e;
482 
483  assert(i>=0);
484 
485  e= i>>k;
486  if(e<limit){
487  put_bits(pb, e + k + 1, (1<<k) + (i&((1<<k)-1)));
488  }else{
489  put_bits(pb, limit + esc_len, i - limit + 1);
490  }
491 }
492 
496 static inline void set_ur_golomb_jpegls(PutBitContext *pb, int i, int k, int limit, int esc_len){
497  int e;
498 
499  assert(i>=0);
500 
501  e= (i>>k) + 1;
502  if(e<limit){
503  while(e > 31) {
504  put_bits(pb, 31, 0);
505  e -= 31;
506  }
507  put_bits(pb, e, 1);
508  if(k)
509  put_sbits(pb, k, i);
510  }else{
511  while(limit > 31) {
512  put_bits(pb, 31, 0);
513  limit -= 31;
514  }
515  put_bits(pb, limit , 1);
516  put_bits(pb, esc_len, i - 1);
517  }
518 }
519 
523 static inline void set_sr_golomb(PutBitContext *pb, int i, int k, int limit, int esc_len){
524  int v;
525 
526  v = -2*i-1;
527  v ^= (v>>31);
528 
529  set_ur_golomb(pb, v, k, limit, esc_len);
530 }
531 
535 static inline void set_sr_golomb_flac(PutBitContext *pb, int i, int k, int limit, int esc_len){
536  int v;
537 
538  v = -2*i-1;
539  v ^= (v>>31);
540 
541  set_ur_golomb_jpegls(pb, v, k, limit, esc_len);
542 }
543 
544 #endif /* AVCODEC_GOLOMB_H */