Add get_ue_golomb_31()
[libav.git] / libavcodec / golomb.h
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 golomb.h
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 "bitstream.h"
35
36 #define INVALID_VLC 0x80000000
37
38 extern const uint8_t ff_golomb_vlc_len[512];
39 extern const uint8_t ff_ue_golomb_vlc_code[512];
40 extern const int8_t ff_se_golomb_vlc_code[512];
41 extern const uint8_t ff_ue_golomb_len[256];
42
43 extern const uint8_t ff_interleaved_golomb_vlc_len[256];
44 extern const uint8_t ff_interleaved_ue_golomb_vlc_code[256];
45 extern const int8_t ff_interleaved_se_golomb_vlc_code[256];
46 extern const uint8_t ff_interleaved_dirac_golomb_vlc_code[256];
47
48
49 /**
50 * read unsigned exp golomb code.
51 */
52 static inline int get_ue_golomb(GetBitContext *gb){
53 unsigned int buf;
54 int log;
55
56 OPEN_READER(re, gb);
57 UPDATE_CACHE(re, gb);
58 buf=GET_CACHE(re, gb);
59
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);
64
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);
72
73 return buf;
74 }
75 }
76
77 /**
78 * read unsigned exp golomb code, constraint to a max of 31
79 */
80 static 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
94 static inline int svq3_get_ue_golomb(GetBitContext *gb){
95 uint32_t buf;
96
97 OPEN_READER(re, gb);
98 UPDATE_CACHE(re, gb);
99 buf=GET_CACHE(re, gb);
100
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);
105
106 return ff_interleaved_ue_golomb_vlc_code[buf];
107 }else{
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);
122 }
123
124 CLOSE_READER(re, gb);
125 return ret - 1;
126 }
127 }
128
129 /**
130 * read unsigned truncated exp golomb code.
131 */
132 static inline int get_te0_golomb(GetBitContext *gb, int range){
133 assert(range >= 1);
134
135 if(range==1) return 0;
136 else if(range==2) return get_bits1(gb)^1;
137 else return get_ue_golomb(gb);
138 }
139
140 /**
141 * read unsigned truncated exp golomb code.
142 */
143 static inline int get_te_golomb(GetBitContext *gb, int range){
144 assert(range >= 1);
145
146 if(range==2) return get_bits1(gb)^1;
147 else return get_ue_golomb(gb);
148 }
149
150
151 /**
152 * read signed exp golomb code.
153 */
154 static inline int get_se_golomb(GetBitContext *gb){
155 unsigned int buf;
156 int log;
157
158 OPEN_READER(re, gb);
159 UPDATE_CACHE(re, gb);
160 buf=GET_CACHE(re, gb);
161
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);
166
167 return ff_se_golomb_vlc_code[buf];
168 }else{
169 log= 2*av_log2(buf) - 31;
170 buf>>= log;
171
172 LAST_SKIP_BITS(re, gb, 32 - log);
173 CLOSE_READER(re, gb);
174
175 if(buf&1) buf= -(buf>>1);
176 else buf= (buf>>1);
177
178 return buf;
179 }
180 }
181
182 static 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);
188 buf=GET_CACHE(re, gb);
189
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);
194
195 return ff_interleaved_se_golomb_vlc_code[buf];
196 }else{
197 LAST_SKIP_BITS(re, gb, 8);
198 UPDATE_CACHE(re, gb);
199 buf |= 1 | (GET_CACHE(re, gb) >> 8);
200
201 if((buf & 0xAAAAAAAA) == 0)
202 return INVALID_VLC;
203
204 for(log=31; (buf & 0x80000000) == 0; log--){
205 buf = (buf << 2) - ((buf << log) >> (log - 1)) + (buf >> 30);
206 }
207
208 LAST_SKIP_BITS(re, gb, 63 - 2*log - 8);
209 CLOSE_READER(re, gb);
210
211 return (signed) (((((buf << log) >> log) - 1) ^ -(buf & 0x1)) + 1) >> 1;
212 }
213 }
214
215 static 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
233 /**
234 * read unsigned golomb rice code (ffv1).
235 */
236 static inline int get_ur_golomb(GetBitContext *gb, int k, int limit, int esc_len){
237 unsigned int buf;
238 int log;
239
240 OPEN_READER(re, gb);
241 UPDATE_CACHE(re, gb);
242 buf=GET_CACHE(re, gb);
243
244 log= av_log2(buf);
245
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);
251
252 return buf;
253 }else{
254 buf >>= 32 - limit - esc_len;
255 LAST_SKIP_BITS(re, gb, esc_len + limit);
256 CLOSE_READER(re, gb);
257
258 return buf + limit - 1;
259 }
260 }
261
262 /**
263 * read unsigned golomb rice code (jpegls).
264 */
265 static inline int get_ur_golomb_jpegls(GetBitContext *gb, int k, int limit, int esc_len){
266 unsigned int buf;
267 int log;
268
269 OPEN_READER(re, gb);
270 UPDATE_CACHE(re, gb);
271 buf=GET_CACHE(re, gb);
272
273 log= av_log2(buf);
274
275 if(log - k >= 32-MIN_CACHE_BITS && 32-log < limit){
276 buf >>= log - k;
277 buf += (30-log)<<k;
278 LAST_SKIP_BITS(re, gb, 32 + k - log);
279 CLOSE_READER(re, gb);
280
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);
304
305 return buf + 1;
306 }else
307 return -1;
308 }
309 }
310
311 /**
312 * read signed golomb rice code (ffv1).
313 */
314 static inline int get_sr_golomb(GetBitContext *gb, int k, int limit, int esc_len){
315 int v= get_ur_golomb(gb, k, limit, esc_len);
316
317 v++;
318 if (v&1) return v>>1;
319 else return -(v>>1);
320
321 // return (v>>1) ^ -(v&1);
322 }
323
324 /**
325 * read signed golomb rice code (flac).
326 */
327 static 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
332 /**
333 * read unsigned golomb rice code (shorten).
334 */
335 static inline unsigned int get_ur_golomb_shorten(GetBitContext *gb, int k){
336 return get_ur_golomb_jpegls(gb, k, INT_MAX, 0);
337 }
338
339 /**
340 * read signed golomb rice code (shorten).
341 */
342 static 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
353 #ifdef TRACE
354
355 static inline int get_ue(GetBitContext *s, char *file, const char *func, int line){
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);
361
362 print_bin(bits, len);
363
364 av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d ue @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
365
366 return i;
367 }
368
369 static inline int get_se(GetBitContext *s, char *file, const char *func, int line){
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);
375
376 print_bin(bits, len);
377
378 av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d se @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
379
380 return i;
381 }
382
383 static inline int get_te(GetBitContext *s, int r, char *file, const char *func, int line){
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);
389
390 print_bin(bits, len);
391
392 av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d te @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
393
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 */
407 static inline void set_ue_golomb(PutBitContext *pb, int i){
408 int e;
409
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);
422
423 put_bits(pb, 2*e+1, i+1);
424 }
425 }
426
427 /**
428 * write truncated unsigned exp golomb code.
429 */
430 static inline void set_te_golomb(PutBitContext *pb, int i, int range){
431 assert(range >= 1);
432 assert(i<=range);
433
434 if(range==2) put_bits(pb, 1, i^1);
435 else set_ue_golomb(pb, i);
436 }
437
438 /**
439 * write signed exp golomb code. 16 bits at most.
440 */
441 static inline void set_se_golomb(PutBitContext *pb, int i){
442 // if (i>32767 || i<-32767)
443 // av_log(NULL,AV_LOG_ERROR,"value out of range %d\n", i);
444 #if 0
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 }
456
457 /**
458 * write unsigned golomb rice code (ffv1).
459 */
460 static inline void set_ur_golomb(PutBitContext *pb, int i, int k, int limit, int esc_len){
461 int e;
462
463 assert(i>=0);
464
465 e= i>>k;
466 if(e<limit){
467 put_bits(pb, e + k + 1, (1<<k) + (i&((1<<k)-1)));
468 }else{
469 put_bits(pb, limit + esc_len, i - limit + 1);
470 }
471 }
472
473 /**
474 * write unsigned golomb rice code (jpegls).
475 */
476 static inline void set_ur_golomb_jpegls(PutBitContext *pb, int i, int k, int limit, int esc_len){
477 int e;
478
479 assert(i>=0);
480
481 e= (i>>k) + 1;
482 if(e<limit){
483 while(e > 31) {
484 put_bits(pb, 31, 0);
485 e -= 31;
486 }
487 put_bits(pb, e, 1);
488 if(k)
489 put_sbits(pb, k, i);
490 }else{
491 while(limit > 31) {
492 put_bits(pb, 31, 0);
493 limit -= 31;
494 }
495 put_bits(pb, limit , 1);
496 put_bits(pb, esc_len, i - 1);
497 }
498 }
499
500 /**
501 * write signed golomb rice code (ffv1).
502 */
503 static inline void set_sr_golomb(PutBitContext *pb, int i, int k, int limit, int esc_len){
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 */
515 static 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 }
523
524 #endif /* AVCODEC_GOLOMB_H */