158e6d2e69274db25c49b171c7b0ddc4530982ca
[ffmpeg.git] / libavcodec / get_bits.h
1 /*
2  * copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at>
3  *
4  * This file is part of Libav.
5  *
6  * Libav is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2.1 of the License, or (at your option) any later version.
10  *
11  * Libav is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with Libav; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19  */
20
21 /**
22  * @file
23  * bitstream reader API header.
24  */
25
26 #ifndef AVCODEC_GET_BITS_H
27 #define AVCODEC_GET_BITS_H
28
29 #include <stdint.h>
30 #include "libavutil/common.h"
31 #include "libavutil/intreadwrite.h"
32 #include "libavutil/log.h"
33 #include "mathops.h"
34
35 /*
36  * Safe bitstream reading:
37  * optionally, the get_bits API can check to ensure that we
38  * don't read past input buffer boundaries. This is protected
39  * with CONFIG_SAFE_BITSTREAM_READER at the global level, and
40  * then below that with UNCHECKED_BITSTREAM_READER at the per-
41  * decoder level. This means that decoders that check internally
42  * can "#define UNCHECKED_BITSTREAM_READER 1" to disable
43  * overread checks.
44  * Boundary checking causes a minor performance penalty so for
45  * applications that won't want/need this, it can be disabled
46  * globally using "#define CONFIG_SAFE_BITSTREAM_READER 0".
47  */
48 #ifndef UNCHECKED_BITSTREAM_READER
49 #define UNCHECKED_BITSTREAM_READER !CONFIG_SAFE_BITSTREAM_READER
50 #endif
51
52 typedef struct GetBitContext {
53     const uint8_t *buffer, *buffer_end;
54     int index;
55     int size_in_bits;
56 #if !UNCHECKED_BITSTREAM_READER
57     int size_in_bits_plus8;
58 #endif
59 } GetBitContext;
60
61 #define VLC_TYPE int16_t
62
63 typedef struct VLC {
64     int bits;
65     VLC_TYPE (*table)[2]; ///< code, bits
66     int table_size, table_allocated;
67 } VLC;
68
69 typedef struct RL_VLC_ELEM {
70     int16_t level;
71     int8_t len;
72     uint8_t run;
73 } RL_VLC_ELEM;
74
75 /* Bitstream reader API docs:
76 name
77     arbitrary name which is used as prefix for the internal variables
78
79 gb
80     getbitcontext
81
82 OPEN_READER(name, gb)
83     load gb into local variables
84
85 CLOSE_READER(name, gb)
86     store local vars in gb
87
88 UPDATE_CACHE(name, gb)
89     refill the internal cache from the bitstream
90     after this call at least MIN_CACHE_BITS will be available,
91
92 GET_CACHE(name, gb)
93     will output the contents of the internal cache, next bit is MSB of 32 or 64 bit (FIXME 64bit)
94
95 SHOW_UBITS(name, gb, num)
96     will return the next num bits
97
98 SHOW_SBITS(name, gb, num)
99     will return the next num bits and do sign extension
100
101 SKIP_BITS(name, gb, num)
102     will skip over the next num bits
103     note, this is equivalent to SKIP_CACHE; SKIP_COUNTER
104
105 SKIP_CACHE(name, gb, num)
106     will remove the next num bits from the cache (note SKIP_COUNTER MUST be called before UPDATE_CACHE / CLOSE_READER)
107
108 SKIP_COUNTER(name, gb, num)
109     will increment the internal bit counter (see SKIP_CACHE & SKIP_BITS)
110
111 LAST_SKIP_BITS(name, gb, num)
112     like SKIP_BITS, to be used if next call is UPDATE_CACHE or CLOSE_READER
113
114 for examples see get_bits, show_bits, skip_bits, get_vlc
115 */
116
117 #ifdef LONG_BITSTREAM_READER
118 #   define MIN_CACHE_BITS 32
119 #else
120 #   define MIN_CACHE_BITS 25
121 #endif
122
123 #define OPEN_READER(name, gb)                   \
124     unsigned int name##_index = (gb)->index;    \
125     unsigned int av_unused name##_cache = 0
126
127 #define CLOSE_READER(name, gb) (gb)->index = name##_index
128
129 #ifdef BITSTREAM_READER_LE
130
131 # ifdef LONG_BITSTREAM_READER
132 #   define UPDATE_CACHE(name, gb) name##_cache = \
133         AV_RL64((gb)->buffer + (name##_index >> 3)) >> (name##_index & 7)
134 # else
135 #   define UPDATE_CACHE(name, gb) name##_cache = \
136         AV_RL32((gb)->buffer + (name##_index >> 3)) >> (name##_index & 7)
137 # endif
138
139 # define SKIP_CACHE(name, gb, num) name##_cache >>= (num)
140
141 #else
142
143 # ifdef LONG_BITSTREAM_READER
144 #   define UPDATE_CACHE(name, gb) name##_cache = \
145         AV_RB64((gb)->buffer + (name##_index >> 3)) >> (32 - (name##_index & 7))
146 # else
147 #   define UPDATE_CACHE(name, gb) name##_cache = \
148         AV_RB32((gb)->buffer + (name##_index >> 3)) << (name##_index & 7)
149 # endif
150
151 # define SKIP_CACHE(name, gb, num) name##_cache <<= (num)
152
153 #endif
154
155 #if UNCHECKED_BITSTREAM_READER
156 #   define SKIP_COUNTER(name, gb, num) name##_index += (num)
157 #else
158 #   define SKIP_COUNTER(name, gb, num) \
159     name##_index = FFMIN((gb)->size_in_bits_plus8, name##_index + (num))
160 #endif
161
162 #define SKIP_BITS(name, gb, num) do {           \
163         SKIP_CACHE(name, gb, num);              \
164         SKIP_COUNTER(name, gb, num);            \
165     } while (0)
166
167 #define LAST_SKIP_BITS(name, gb, num) SKIP_COUNTER(name, gb, num)
168
169 #ifdef BITSTREAM_READER_LE
170 #   define SHOW_UBITS(name, gb, num) zero_extend(name##_cache, num)
171 #   define SHOW_SBITS(name, gb, num) sign_extend(name##_cache, num)
172 #else
173 #   define SHOW_UBITS(name, gb, num) NEG_USR32(name##_cache, num)
174 #   define SHOW_SBITS(name, gb, num) NEG_SSR32(name##_cache, num)
175 #endif
176
177 #define GET_CACHE(name, gb) ((uint32_t)name##_cache)
178
179 static inline int get_bits_count(const GetBitContext *s)
180 {
181     return s->index;
182 }
183
184 static inline void skip_bits_long(GetBitContext *s, int n){
185 #if UNCHECKED_BITSTREAM_READER
186     s->index += n;
187 #else
188     s->index += av_clip(n, -s->index, s->size_in_bits_plus8 - s->index);
189 #endif
190 }
191
192 /**
193  * read mpeg1 dc style vlc (sign bit + mantisse with no MSB).
194  * if MSB not set it is negative
195  * @param n length in bits
196  */
197 static inline int get_xbits(GetBitContext *s, int n)
198 {
199     register int sign;
200     register int32_t cache;
201     OPEN_READER(re, s);
202     UPDATE_CACHE(re, s);
203     cache = GET_CACHE(re, s);
204     sign = ~cache >> 31;
205     LAST_SKIP_BITS(re, s, n);
206     CLOSE_READER(re, s);
207     return (NEG_USR32(sign ^ cache, n) ^ sign) - sign;
208 }
209
210 static inline int get_sbits(GetBitContext *s, int n)
211 {
212     register int tmp;
213     OPEN_READER(re, s);
214     UPDATE_CACHE(re, s);
215     tmp = SHOW_SBITS(re, s, n);
216     LAST_SKIP_BITS(re, s, n);
217     CLOSE_READER(re, s);
218     return tmp;
219 }
220
221 /**
222  * Read 1-25 bits.
223  */
224 static inline unsigned int get_bits(GetBitContext *s, int n)
225 {
226     register int tmp;
227     OPEN_READER(re, s);
228     UPDATE_CACHE(re, s);
229     tmp = SHOW_UBITS(re, s, n);
230     LAST_SKIP_BITS(re, s, n);
231     CLOSE_READER(re, s);
232     return tmp;
233 }
234
235 /**
236  * Show 1-25 bits.
237  */
238 static inline unsigned int show_bits(GetBitContext *s, int n)
239 {
240     register int tmp;
241     OPEN_READER(re, s);
242     UPDATE_CACHE(re, s);
243     tmp = SHOW_UBITS(re, s, n);
244     return tmp;
245 }
246
247 static inline void skip_bits(GetBitContext *s, int n)
248 {
249     OPEN_READER(re, s);
250     UPDATE_CACHE(re, s);
251     LAST_SKIP_BITS(re, s, n);
252     CLOSE_READER(re, s);
253 }
254
255 static inline unsigned int get_bits1(GetBitContext *s)
256 {
257     unsigned int index = s->index;
258     uint8_t result = s->buffer[index>>3];
259 #ifdef BITSTREAM_READER_LE
260     result >>= index & 7;
261     result &= 1;
262 #else
263     result <<= index & 7;
264     result >>= 8 - 1;
265 #endif
266 #if !UNCHECKED_BITSTREAM_READER
267     if (s->index < s->size_in_bits_plus8)
268 #endif
269         index++;
270     s->index = index;
271
272     return result;
273 }
274
275 static inline unsigned int show_bits1(GetBitContext *s)
276 {
277     return show_bits(s, 1);
278 }
279
280 static inline void skip_bits1(GetBitContext *s)
281 {
282     skip_bits(s, 1);
283 }
284
285 /**
286  * Read 0-32 bits.
287  */
288 static inline unsigned int get_bits_long(GetBitContext *s, int n)
289 {
290     if (n <= MIN_CACHE_BITS)
291         return get_bits(s, n);
292     else {
293 #ifdef BITSTREAM_READER_LE
294         int ret = get_bits(s, 16);
295         return ret | (get_bits(s, n-16) << 16);
296 #else
297         int ret = get_bits(s, 16) << (n-16);
298         return ret | get_bits(s, n-16);
299 #endif
300     }
301 }
302
303 /**
304  * Read 0-32 bits as a signed integer.
305  */
306 static inline int get_sbits_long(GetBitContext *s, int n)
307 {
308     return sign_extend(get_bits_long(s, n), n);
309 }
310
311 /**
312  * Show 0-32 bits.
313  */
314 static inline unsigned int show_bits_long(GetBitContext *s, int n)
315 {
316     if (n <= MIN_CACHE_BITS)
317         return show_bits(s, n);
318     else {
319         GetBitContext gb = *s;
320         return get_bits_long(&gb, n);
321     }
322 }
323
324 static inline int check_marker(GetBitContext *s, const char *msg)
325 {
326     int bit = get_bits1(s);
327     if (!bit)
328         av_log(NULL, AV_LOG_INFO, "Marker bit missing %s\n", msg);
329
330     return bit;
331 }
332
333 /**
334  * Inititalize GetBitContext.
335  * @param buffer bitstream buffer, must be FF_INPUT_BUFFER_PADDING_SIZE bytes larger than the actual read bits
336  * because some optimized bitstream readers read 32 or 64 bit at once and could read over the end
337  * @param bit_size the size of the buffer in bits
338  */
339 static inline void init_get_bits(GetBitContext *s, const uint8_t *buffer,
340                                  int bit_size)
341 {
342     int buffer_size = (bit_size+7)>>3;
343     if (buffer_size < 0 || bit_size < 0) {
344         buffer_size = bit_size = 0;
345         buffer = NULL;
346     }
347
348     s->buffer       = buffer;
349     s->size_in_bits = bit_size;
350 #if !UNCHECKED_BITSTREAM_READER
351     s->size_in_bits_plus8 = bit_size + 8;
352 #endif
353     s->buffer_end   = buffer + buffer_size;
354     s->index        = 0;
355 }
356
357 static inline void align_get_bits(GetBitContext *s)
358 {
359     int n = -get_bits_count(s) & 7;
360     if (n) skip_bits(s, n);
361 }
362
363 #define init_vlc(vlc, nb_bits, nb_codes,                \
364                  bits, bits_wrap, bits_size,            \
365                  codes, codes_wrap, codes_size,         \
366                  flags)                                 \
367         ff_init_vlc_sparse(vlc, nb_bits, nb_codes,         \
368                            bits, bits_wrap, bits_size,     \
369                            codes, codes_wrap, codes_size,  \
370                            NULL, 0, 0, flags)
371
372 int ff_init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes,
373              const void *bits, int bits_wrap, int bits_size,
374              const void *codes, int codes_wrap, int codes_size,
375              const void *symbols, int symbols_wrap, int symbols_size,
376              int flags);
377 #define INIT_VLC_LE         2
378 #define INIT_VLC_USE_NEW_STATIC 4
379 void ff_free_vlc(VLC *vlc);
380
381 #define INIT_VLC_STATIC(vlc, bits, a,b,c,d,e,f,g, static_size) do {     \
382         static VLC_TYPE table[static_size][2];                          \
383         (vlc)->table = table;                                           \
384         (vlc)->table_allocated = static_size;                           \
385         init_vlc(vlc, bits, a,b,c,d,e,f,g, INIT_VLC_USE_NEW_STATIC);    \
386     } while (0)
387
388
389 /**
390  * If the vlc code is invalid and max_depth=1, then no bits will be removed.
391  * If the vlc code is invalid and max_depth>1, then the number of bits removed
392  * is undefined.
393  */
394 #define GET_VLC(code, name, gb, table, bits, max_depth)         \
395     do {                                                        \
396         int n, nb_bits;                                         \
397         unsigned int index;                                     \
398                                                                 \
399         index = SHOW_UBITS(name, gb, bits);                     \
400         code  = table[index][0];                                \
401         n     = table[index][1];                                \
402                                                                 \
403         if (max_depth > 1 && n < 0) {                           \
404             LAST_SKIP_BITS(name, gb, bits);                     \
405             UPDATE_CACHE(name, gb);                             \
406                                                                 \
407             nb_bits = -n;                                       \
408                                                                 \
409             index = SHOW_UBITS(name, gb, nb_bits) + code;       \
410             code  = table[index][0];                            \
411             n     = table[index][1];                            \
412             if (max_depth > 2 && n < 0) {                       \
413                 LAST_SKIP_BITS(name, gb, nb_bits);              \
414                 UPDATE_CACHE(name, gb);                         \
415                                                                 \
416                 nb_bits = -n;                                   \
417                                                                 \
418                 index = SHOW_UBITS(name, gb, nb_bits) + code;   \
419                 code  = table[index][0];                        \
420                 n     = table[index][1];                        \
421             }                                                   \
422         }                                                       \
423         SKIP_BITS(name, gb, n);                                 \
424     } while (0)
425
426 #define GET_RL_VLC(level, run, name, gb, table, bits, max_depth, need_update) \
427     do {                                                                \
428         int n, nb_bits;                                                 \
429         unsigned int index;                                             \
430                                                                         \
431         index = SHOW_UBITS(name, gb, bits);                             \
432         level = table[index].level;                                     \
433         n     = table[index].len;                                       \
434                                                                         \
435         if (max_depth > 1 && n < 0) {                                   \
436             SKIP_BITS(name, gb, bits);                                  \
437             if (need_update) {                                          \
438                 UPDATE_CACHE(name, gb);                                 \
439             }                                                           \
440                                                                         \
441             nb_bits = -n;                                               \
442                                                                         \
443             index = SHOW_UBITS(name, gb, nb_bits) + level;              \
444             level = table[index].level;                                 \
445             n     = table[index].len;                                   \
446         }                                                               \
447         run = table[index].run;                                         \
448         SKIP_BITS(name, gb, n);                                         \
449     } while (0)
450
451
452 /**
453  * Parse a vlc code.
454  * @param bits is the number of bits which will be read at once, must be
455  *             identical to nb_bits in init_vlc()
456  * @param max_depth is the number of times bits bits must be read to completely
457  *                  read the longest vlc code
458  *                  = (max_vlc_length + bits - 1) / bits
459  */
460 static av_always_inline int get_vlc2(GetBitContext *s, VLC_TYPE (*table)[2],
461                                      int bits, int max_depth)
462 {
463     int code;
464
465     OPEN_READER(re, s);
466     UPDATE_CACHE(re, s);
467
468     GET_VLC(code, re, s, table, bits, max_depth);
469
470     CLOSE_READER(re, s);
471     return code;
472 }
473
474 static inline int decode012(GetBitContext *gb)
475 {
476     int n;
477     n = get_bits1(gb);
478     if (n == 0)
479         return 0;
480     else
481         return get_bits1(gb) + 1;
482 }
483
484 static inline int decode210(GetBitContext *gb)
485 {
486     if (get_bits1(gb))
487         return 0;
488     else
489         return 2 - get_bits1(gb);
490 }
491
492 static inline int get_bits_left(GetBitContext *gb)
493 {
494     return gb->size_in_bits - get_bits_count(gb);
495 }
496
497 //#define TRACE
498
499 #ifdef TRACE
500 static inline void print_bin(int bits, int n)
501 {
502     int i;
503
504     for (i = n-1; i >= 0; i--) {
505         av_log(NULL, AV_LOG_DEBUG, "%d", (bits>>i)&1);
506     }
507     for (i = n; i < 24; i++)
508         av_log(NULL, AV_LOG_DEBUG, " ");
509 }
510
511 static inline int get_bits_trace(GetBitContext *s, int n, char *file,
512                                  const char *func, int line)
513 {
514     int r = get_bits(s, n);
515
516     print_bin(r, n);
517     av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d bit @%5d in %s %s:%d\n",
518            r, n, r, get_bits_count(s)-n, file, func, line);
519     return r;
520 }
521 static inline int get_vlc_trace(GetBitContext *s, VLC_TYPE (*table)[2],
522                                 int bits, int max_depth, char *file,
523                                 const char *func, int line)
524 {
525     int show  = show_bits(s, 24);
526     int pos   = get_bits_count(s);
527     int r     = get_vlc2(s, table, bits, max_depth);
528     int len   = get_bits_count(s) - pos;
529     int bits2 = show >> (24-len);
530
531     print_bin(bits2, len);
532
533     av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d vlc @%5d in %s %s:%d\n",
534            bits2, len, r, pos, file, func, line);
535     return r;
536 }
537 static inline int get_xbits_trace(GetBitContext *s, int n, char *file,
538                                   const char *func, int line)
539 {
540     int show = show_bits(s, n);
541     int r    = get_xbits(s, n);
542
543     print_bin(show, n);
544     av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d xbt @%5d in %s %s:%d\n",
545            show, n, r, get_bits_count(s)-n, file, func, line);
546     return r;
547 }
548
549 #define get_bits(s, n)  get_bits_trace(s, n, __FILE__, __PRETTY_FUNCTION__, __LINE__)
550 #define get_bits1(s)    get_bits_trace(s, 1, __FILE__, __PRETTY_FUNCTION__, __LINE__)
551 #define get_xbits(s, n) get_xbits_trace(s, n, __FILE__, __PRETTY_FUNCTION__, __LINE__)
552 #define get_vlc(s, vlc)            get_vlc_trace(s, (vlc)->table, (vlc)->bits, 3, __FILE__, __PRETTY_FUNCTION__, __LINE__)
553 #define get_vlc2(s, tab, bits, max) get_vlc_trace(s, tab, bits, max, __FILE__, __PRETTY_FUNCTION__, __LINE__)
554
555 #define tprintf(p, ...) av_log(p, AV_LOG_DEBUG, __VA_ARGS__)
556
557 #else //TRACE
558 #define tprintf(p, ...) {}
559 #endif
560
561 #endif /* AVCODEC_GET_BITS_H */