Add get_ue_golomb_31()
[libav.git] / libavcodec / golomb.h
CommitLineData
0da71265
MN
1/*
2 * exp golomb vlc stuff
3 * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at>
4579adb0 4 * Copyright (c) 2004 Alex Beregszaszi
0da71265 5 *
b78e7197
DB
6 * This file is part of FFmpeg.
7 *
8 * FFmpeg is free software; you can redistribute it and/or
0da71265
MN
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
b78e7197 11 * version 2.1 of the License, or (at your option) any later version.
0da71265 12 *
b78e7197 13 * FFmpeg is distributed in the hope that it will be useful,
0da71265
MN
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
b78e7197 19 * License along with FFmpeg; if not, write to the Free Software
5509bffa 20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
0da71265 21 */
115329f1 22
0da71265
MN
23/**
24 * @file golomb.h
115329f1 25 * @brief
0da71265 26 * exp golomb vlc stuff
4579adb0 27 * @author Michael Niedermayer <michaelni@gmx.at> and Alex Beregszaszi
0da71265
MN
28 */
29
98790382
SS
30#ifndef AVCODEC_GOLOMB_H
31#define AVCODEC_GOLOMB_H
699b3f99 32
99545457
MR
33#include <stdint.h>
34#include "bitstream.h"
35
8b82a956
MN
36#define INVALID_VLC 0x80000000
37
0da71265
MN
38extern const uint8_t ff_golomb_vlc_len[512];
39extern const uint8_t ff_ue_golomb_vlc_code[512];
40extern const int8_t ff_se_golomb_vlc_code[512];
41extern const uint8_t ff_ue_golomb_len[256];
42
4704097a
MN
43extern const uint8_t ff_interleaved_golomb_vlc_len[256];
44extern const uint8_t ff_interleaved_ue_golomb_vlc_code[256];
45extern const int8_t ff_interleaved_se_golomb_vlc_code[256];
9df4ce5e 46extern const uint8_t ff_interleaved_dirac_golomb_vlc_code[256];
4704097a 47
115329f1 48
0da71265
MN
49 /**
50 * read unsigned exp golomb code.
51 */
52static inline int get_ue_golomb(GetBitContext *gb){
53 unsigned int buf;
54 int log;
115329f1 55
0da71265
MN
56 OPEN_READER(re, gb);
57 UPDATE_CACHE(re, gb);
58 buf=GET_CACHE(re, gb);
115329f1 59
0da71265
MN
60 if(buf >= (1<<27)){
61 buf >>= 32 - 9;
62 LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]);
63 CLOSE_READER(re, gb);
115329f1 64
0da71265
MN
65 return ff_ue_golomb_vlc_code[buf];
66 }else{
67 log= 2*av_log2(buf) - 31;
68 buf>>= log;
69 buf--;
70 LAST_SKIP_BITS(re, gb, 32 - log);
71 CLOSE_READER(re, gb);
115329f1 72
0da71265
MN
73 return buf;
74 }
75}
76
0e921e97
MN
77 /**
78 * read unsigned exp golomb code, constraint to a max of 31
79 */
80static inline int get_ue_golomb_31(GetBitContext *gb){
81 unsigned int buf;
82
83 OPEN_READER(re, gb);
84 UPDATE_CACHE(re, gb);
85 buf=GET_CACHE(re, gb);
86
87 buf >>= 32 - 9;
88 LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]);
89 CLOSE_READER(re, gb);
90
91 return ff_ue_golomb_vlc_code[buf];
92}
93
8b82a956 94static inline int svq3_get_ue_golomb(GetBitContext *gb){
4704097a 95 uint32_t buf;
8b82a956
MN
96
97 OPEN_READER(re, gb);
98 UPDATE_CACHE(re, gb);
4704097a 99 buf=GET_CACHE(re, gb);
115329f1 100
4704097a
MN
101 if(buf&0xAA800000){
102 buf >>= 32 - 8;
103 LAST_SKIP_BITS(re, gb, ff_interleaved_golomb_vlc_len[buf]);
104 CLOSE_READER(re, gb);
115329f1 105
4704097a
MN
106 return ff_interleaved_ue_golomb_vlc_code[buf];
107 }else{
9df4ce5e
MG
108 int ret = 1;
109
110 while (1) {
111 buf >>= 32 - 8;
112 LAST_SKIP_BITS(re, gb, FFMIN(ff_interleaved_golomb_vlc_len[buf], 8));
113
114 if (ff_interleaved_golomb_vlc_len[buf] != 9){
115 ret <<= (ff_interleaved_golomb_vlc_len[buf] - 1) >> 1;
116 ret |= ff_interleaved_dirac_golomb_vlc_code[buf];
117 break;
118 }
119 ret = (ret << 4) | ff_interleaved_dirac_golomb_vlc_code[buf];
120 UPDATE_CACHE(re, gb);
121 buf = GET_CACHE(re, gb);
4704097a 122 }
8b82a956 123
4704097a 124 CLOSE_READER(re, gb);
9df4ce5e 125 return ret - 1;
4704097a 126 }
8b82a956
MN
127}
128
0da71265
MN
129/**
130 * read unsigned truncated exp golomb code.
131 */
132static inline int get_te0_golomb(GetBitContext *gb, int range){
133 assert(range >= 1);
115329f1 134
0da71265 135 if(range==1) return 0;
1924f3ce 136 else if(range==2) return get_bits1(gb)^1;
0da71265
MN
137 else return get_ue_golomb(gb);
138}
139
140/**
141 * read unsigned truncated exp golomb code.
142 */
143static inline int get_te_golomb(GetBitContext *gb, int range){
144 assert(range >= 1);
115329f1 145
1924f3ce 146 if(range==2) return get_bits1(gb)^1;
0da71265
MN
147 else return get_ue_golomb(gb);
148}
149
150
151/**
152 * read signed exp golomb code.
153 */
154static inline int get_se_golomb(GetBitContext *gb){
155 unsigned int buf;
156 int log;
115329f1 157
0da71265
MN
158 OPEN_READER(re, gb);
159 UPDATE_CACHE(re, gb);
160 buf=GET_CACHE(re, gb);
115329f1 161
0da71265
MN
162 if(buf >= (1<<27)){
163 buf >>= 32 - 9;
164 LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]);
165 CLOSE_READER(re, gb);
115329f1 166
0da71265
MN
167 return ff_se_golomb_vlc_code[buf];
168 }else{
169 log= 2*av_log2(buf) - 31;
170 buf>>= log;
115329f1 171
0da71265
MN
172 LAST_SKIP_BITS(re, gb, 32 - log);
173 CLOSE_READER(re, gb);
115329f1 174
0da71265
MN
175 if(buf&1) buf= -(buf>>1);
176 else buf= (buf>>1);
177
178 return buf;
179 }
180}
181
8b82a956
MN
182static inline int svq3_get_se_golomb(GetBitContext *gb){
183 unsigned int buf;
184 int log;
185
186 OPEN_READER(re, gb);
187 UPDATE_CACHE(re, gb);
4704097a 188 buf=GET_CACHE(re, gb);
8b82a956 189
4704097a
MN
190 if(buf&0xAA800000){
191 buf >>= 32 - 8;
192 LAST_SKIP_BITS(re, gb, ff_interleaved_golomb_vlc_len[buf]);
193 CLOSE_READER(re, gb);
115329f1 194
4704097a
MN
195 return ff_interleaved_se_golomb_vlc_code[buf];
196 }else{
895345da
MN
197 LAST_SKIP_BITS(re, gb, 8);
198 UPDATE_CACHE(re, gb);
199 buf |= 1 | (GET_CACHE(re, gb) >> 8);
200
4704097a
MN
201 if((buf & 0xAAAAAAAA) == 0)
202 return INVALID_VLC;
8b82a956 203
4704097a
MN
204 for(log=31; (buf & 0x80000000) == 0; log--){
205 buf = (buf << 2) - ((buf << log) >> (log - 1)) + (buf >> 30);
206 }
8b82a956 207
895345da 208 LAST_SKIP_BITS(re, gb, 63 - 2*log - 8);
4704097a 209 CLOSE_READER(re, gb);
8b82a956 210
4704097a
MN
211 return (signed) (((((buf << log) >> log) - 1) ^ -(buf & 0x1)) + 1) >> 1;
212 }
8b82a956
MN
213}
214
9df4ce5e
MG
215static inline int dirac_get_se_golomb(GetBitContext *gb){
216 uint32_t buf;
217 uint32_t ret;
218
219 ret = svq3_get_ue_golomb(gb);
220
221 if (ret) {
222 OPEN_READER(re, gb);
223 UPDATE_CACHE(re, gb);
224 buf = SHOW_SBITS(re, gb, 1);
225 LAST_SKIP_BITS(re, gb, 1);
226 ret = (ret ^ buf) - buf;
227 CLOSE_READER(re, gb);
228 }
229
230 return ret;
231}
232
11e659c2 233/**
d9e6a6c6 234 * read unsigned golomb rice code (ffv1).
11e659c2
MN
235 */
236static inline int get_ur_golomb(GetBitContext *gb, int k, int limit, int esc_len){
237 unsigned int buf;
238 int log;
115329f1 239
11e659c2
MN
240 OPEN_READER(re, gb);
241 UPDATE_CACHE(re, gb);
242 buf=GET_CACHE(re, gb);
243
244 log= av_log2(buf);
d9e6a6c6 245
11e659c2
MN
246 if(log > 31-limit){
247 buf >>= log - k;
248 buf += (30-log)<<k;
249 LAST_SKIP_BITS(re, gb, 32 + k - log);
250 CLOSE_READER(re, gb);
115329f1 251
11e659c2 252 return buf;
d9e6a6c6
MN
253 }else{
254 buf >>= 32 - limit - esc_len;
255 LAST_SKIP_BITS(re, gb, esc_len + limit);
11e659c2 256 CLOSE_READER(re, gb);
115329f1 257
d9e6a6c6
MN
258 return buf + limit - 1;
259 }
260}
261
262/**
263 * read unsigned golomb rice code (jpegls).
264 */
265static inline int get_ur_golomb_jpegls(GetBitContext *gb, int k, int limit, int esc_len){
266 unsigned int buf;
267 int log;
115329f1 268
d9e6a6c6
MN
269 OPEN_READER(re, gb);
270 UPDATE_CACHE(re, gb);
271 buf=GET_CACHE(re, gb);
272
273 log= av_log2(buf);
115329f1 274
740c14db 275 if(log - k >= 32-MIN_CACHE_BITS && 32-log < limit){
d9e6a6c6
MN
276 buf >>= log - k;
277 buf += (30-log)<<k;
278 LAST_SKIP_BITS(re, gb, 32 + k - log);
279 CLOSE_READER(re, gb);
115329f1 280
d9e6a6c6
MN
281 return buf;
282 }else{
283 int i;
284 for(i=0; SHOW_UBITS(re, gb, 1) == 0; i++){
285 LAST_SKIP_BITS(re, gb, 1);
286 UPDATE_CACHE(re, gb);
287 }
288 SKIP_BITS(re, gb, 1);
289
290 if(i < limit - 1){
291 if(k){
292 buf = SHOW_UBITS(re, gb, k);
293 LAST_SKIP_BITS(re, gb, k);
294 }else{
295 buf=0;
296 }
297
298 CLOSE_READER(re, gb);
299 return buf + (i<<k);
300 }else if(i == limit - 1){
301 buf = SHOW_UBITS(re, gb, esc_len);
302 LAST_SKIP_BITS(re, gb, esc_len);
303 CLOSE_READER(re, gb);
115329f1 304
d9e6a6c6
MN
305 return buf + 1;
306 }else
307 return -1;
308 }
11e659c2
MN
309}
310
ac2570a8 311/**
4579adb0
AB
312 * read signed golomb rice code (ffv1).
313 */
a6c01275 314static inline int get_sr_golomb(GetBitContext *gb, int k, int limit, int esc_len){
4579adb0 315 int v= get_ur_golomb(gb, k, limit, esc_len);
115329f1 316
4579adb0
AB
317 v++;
318 if (v&1) return v>>1;
319 else return -(v>>1);
115329f1 320
4579adb0
AB
321// return (v>>1) ^ -(v&1);
322}
4579adb0 323
a6c01275 324/**
4579adb0 325 * read signed golomb rice code (flac).
ac2570a8
MN
326 */
327static inline int get_sr_golomb_flac(GetBitContext *gb, int k, int limit, int esc_len){
328 int v= get_ur_golomb_jpegls(gb, k, limit, esc_len);
329 return (v>>1) ^ -(v&1);
330}
331
85ad5695
MN
332/**
333 * read unsigned golomb rice code (shorten).
334 */
335static inline unsigned int get_ur_golomb_shorten(GetBitContext *gb, int k){
bb270c08 336 return get_ur_golomb_jpegls(gb, k, INT_MAX, 0);
85ad5695
MN
337}
338
339/**
340 * read signed golomb rice code (shorten).
341 */
342static inline int get_sr_golomb_shorten(GetBitContext* gb, int k)
343{
344 int uvar = get_ur_golomb_jpegls(gb, k + 1, INT_MAX, 0);
345 if (uvar & 1)
346 return ~(uvar >> 1);
347 else
348 return uvar >> 1;
349}
350
351
352
0da71265
MN
353#ifdef TRACE
354
61f040dd 355static inline int get_ue(GetBitContext *s, char *file, const char *func, int line){
0da71265
MN
356 int show= show_bits(s, 24);
357 int pos= get_bits_count(s);
358 int i= get_ue_golomb(s);
359 int len= get_bits_count(s) - pos;
360 int bits= show>>(24-len);
115329f1 361
0da71265 362 print_bin(bits, len);
115329f1 363
4579adb0 364 av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d ue @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
115329f1 365
0da71265
MN
366 return i;
367}
368
61f040dd 369static inline int get_se(GetBitContext *s, char *file, const char *func, int line){
0da71265
MN
370 int show= show_bits(s, 24);
371 int pos= get_bits_count(s);
372 int i= get_se_golomb(s);
373 int len= get_bits_count(s) - pos;
374 int bits= show>>(24-len);
115329f1 375
0da71265 376 print_bin(bits, len);
115329f1 377
4579adb0 378 av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d se @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
115329f1 379
0da71265
MN
380 return i;
381}
382
61f040dd 383static inline int get_te(GetBitContext *s, int r, char *file, const char *func, int line){
0da71265
MN
384 int show= show_bits(s, 24);
385 int pos= get_bits_count(s);
386 int i= get_te0_golomb(s, r);
387 int len= get_bits_count(s) - pos;
388 int bits= show>>(24-len);
115329f1 389
0da71265 390 print_bin(bits, len);
115329f1 391
4579adb0 392 av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d te @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
115329f1 393
0da71265
MN
394 return i;
395}
396
397#define get_ue_golomb(a) get_ue(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
398#define get_se_golomb(a) get_se(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
399#define get_te_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
400#define get_te0_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
401
402#endif
403
404/**
405 * write unsigned exp golomb code.
406 */
407static inline void set_ue_golomb(PutBitContext *pb, int i){
408 int e;
115329f1 409
0da71265
MN
410 assert(i>=0);
411
412#if 0
413 if(i=0){
414 put_bits(pb, 1, 1);
415 return;
416 }
417#endif
418 if(i<256)
419 put_bits(pb, ff_ue_golomb_len[i], i+1);
420 else{
421 e= av_log2(i+1);
115329f1 422
0da71265
MN
423 put_bits(pb, 2*e+1, i+1);
424 }
425}
426
427/**
428 * write truncated unsigned exp golomb code.
429 */
430static inline void set_te_golomb(PutBitContext *pb, int i, int range){
431 assert(range >= 1);
432 assert(i<=range);
433
1924f3ce 434 if(range==2) put_bits(pb, 1, i^1);
0da71265
MN
435 else set_ue_golomb(pb, i);
436}
437
438/**
e134e10f 439 * write signed exp golomb code. 16 bits at most.
0da71265
MN
440 */
441static inline void set_se_golomb(PutBitContext *pb, int i){
e134e10f 442// if (i>32767 || i<-32767)
bb270c08 443// av_log(NULL,AV_LOG_ERROR,"value out of range %d\n", i);
115329f1 444#if 0
0da71265
MN
445 if(i<=0) i= -2*i;
446 else i= 2*i-1;
447#elif 1
448 i= 2*i-1;
449 if(i<0) i^= -1; //FIXME check if gcc does the right thing
450#else
451 i= 2*i-1;
452 i^= (i>>31);
453#endif
454 set_ue_golomb(pb, i);
455}
11e659c2
MN
456
457/**
d9e6a6c6 458 * write unsigned golomb rice code (ffv1).
11e659c2
MN
459 */
460static inline void set_ur_golomb(PutBitContext *pb, int i, int k, int limit, int esc_len){
461 int e;
115329f1 462
11e659c2 463 assert(i>=0);
115329f1 464
11e659c2
MN
465 e= i>>k;
466 if(e<limit){
467 put_bits(pb, e + k + 1, (1<<k) + (i&((1<<k)-1)));
468 }else{
d9e6a6c6
MN
469 put_bits(pb, limit + esc_len, i - limit + 1);
470 }
471}
472
473/**
474 * write unsigned golomb rice code (jpegls).
475 */
476static inline void set_ur_golomb_jpegls(PutBitContext *pb, int i, int k, int limit, int esc_len){
477 int e;
115329f1 478
d9e6a6c6 479 assert(i>=0);
115329f1 480
d9e6a6c6
MN
481 e= (i>>k) + 1;
482 if(e<limit){
9e96ab03
MN
483 while(e > 31) {
484 put_bits(pb, 31, 0);
485 e -= 31;
486 }
d9e6a6c6 487 put_bits(pb, e, 1);
ce329952 488 if(k)
6647ab80 489 put_sbits(pb, k, i);
d9e6a6c6 490 }else{
76aca7a8
KS
491 while(limit > 31) {
492 put_bits(pb, 31, 0);
493 limit -= 31;
494 }
d9e6a6c6
MN
495 put_bits(pb, limit , 1);
496 put_bits(pb, esc_len, i - 1);
11e659c2
MN
497 }
498}
4579adb0
AB
499
500/**
501 * write signed golomb rice code (ffv1).
502 */
a6c01275 503static inline void set_sr_golomb(PutBitContext *pb, int i, int k, int limit, int esc_len){
4579adb0
AB
504 int v;
505
506 v = -2*i-1;
507 v ^= (v>>31);
508
509 set_ur_golomb(pb, v, k, limit, esc_len);
510}
511
512/**
513 * write signed golomb rice code (flac).
514 */
515static inline void set_sr_golomb_flac(PutBitContext *pb, int i, int k, int limit, int esc_len){
516 int v;
517
518 v = -2*i-1;
519 v ^= (v>>31);
520
521 set_ur_golomb_jpegls(pb, v, k, limit, esc_len);
522}
699b3f99 523
98790382 524#endif /* AVCODEC_GOLOMB_H */