git.sesse.net Git - ffmpeg/blob - libavcodec/common.c

   1 /*
   2  * Common bit i/o utils
   3  * Copyright (c) 2000, 2001 Gerard Lantau.
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  *
  19  * alternative bitstream reader & writer by Michael Niedermayer <michaelni@gmx.at>
  20  */
  21 #include "common.h"
  22 #include <math.h>
  23
  24 void init_put_bits(PutBitContext *s,
  25                    UINT8 *buffer, int buffer_size,
  26                    void *opaque,
  27                    void (*write_data)(void *, UINT8 *, int))
  28 {
  29     s->buf = buffer;
  30     s->buf_end = s->buf + buffer_size;
  31     s->data_out_size = 0;
  32     if(write_data!=NULL)
  33     {
  34         fprintf(stderr, "write Data callback is not supported\n");
  35     }
  36 #ifdef ALT_BITSTREAM_WRITER
  37     s->index=0;
  38     ((uint32_t*)(s->buf))[0]=0;
  39 //    memset(buffer, 0, buffer_size);
  40 #else
  41     s->buf_ptr = s->buf;
  42     s->bit_left=32;
  43     s->bit_buf=0;
  44 #endif
  45 }
  46
  47 /* return the number of bits output */
  48 INT64 get_bit_count(PutBitContext *s)
  49 {
  50 #ifdef ALT_BITSTREAM_WRITER
  51     return s->data_out_size * 8 + s->index;
  52 #else
  53     return (s->buf_ptr - s->buf + s->data_out_size) * 8 + 32 - (INT64)s->bit_left;
  54 #endif
  55 }
  56
  57 void align_put_bits(PutBitContext *s)
  58 {
  59 #ifdef ALT_BITSTREAM_WRITER
  60     put_bits(s,(  - s->index) & 7,0);
  61 #else
  62     put_bits(s,s->bit_left & 7,0);
  63 #endif
  64 }
  65
  66 /* pad the end of the output stream with zeros */
  67 void flush_put_bits(PutBitContext *s)
  68 {
  69 #ifdef ALT_BITSTREAM_WRITER
  70     align_put_bits(s);
  71 #else
  72     s->bit_buf<<= s->bit_left;
  73     while (s->bit_left < 32) {
  74         /* XXX: should test end of buffer */
  75         *s->buf_ptr++=s->bit_buf >> 24;
  76         s->bit_buf<<=8;
  77         s->bit_left+=8;
  78     }
  79     s->bit_left=32;
  80     s->bit_buf=0;
  81 #endif
  82 }
  83
  84 /* pad the end of the output stream with zeros */
  85 #ifndef ALT_BITSTREAM_WRITER
  86 void jflush_put_bits(PutBitContext *s)
  87 {
  88     unsigned int b;
  89     s->bit_buf<<= s->bit_left;
  90     s->bit_buf |= ~1U >> (32 - s->bit_left); /* set all the unused bits to one */
  91
  92     while (s->bit_left < 32) {
  93         b = s->bit_buf >> 24;
  94         *s->buf_ptr++ = b;
  95         if (b == 0xff)
  96             *s->buf_ptr++ = 0;
  97         s->bit_buf<<=8;
  98         s->bit_left+=8;
  99     }
 100     s->bit_left=32;
 101     s->bit_buf=0;
 102 }
 103 #else
 104 void jflush_put_bits(PutBitContext *s)
 105 {
 106     int num= (  - s->index) & 7;
 107     jput_bits(s, num,0xFF>>(8-num));
 108 }
 109 #endif
 110
 111 /* bit input functions */
 112
 113 void init_get_bits(GetBitContext *s,
 114                    UINT8 *buffer, int buffer_size)
 115 {
 116 #ifdef ALT_BITSTREAM_READER
 117     s->index=0;
 118     s->buffer= buffer;
 119 #else
 120     s->buf = buffer;
 121     s->buf_ptr = buffer;
 122     s->buf_end = buffer + buffer_size;
 123     s->bit_cnt = 0;
 124     s->bit_buf = 0;
 125     while (s->buf_ptr < s->buf_end &&
 126            s->bit_cnt < 32) {
 127         s->bit_buf |= (*s->buf_ptr++ << (24 - s->bit_cnt));
 128         s->bit_cnt += 8;
 129     }
 130 #endif
 131     s->size= buffer_size;
 132 }
 133
 134 #ifndef ALT_BITSTREAM_READER
 135 /* n must be >= 1 and <= 32 */
 136 /* also true: n > s->bit_cnt */
 137 unsigned int get_bits_long(GetBitContext *s, int n)
 138 {
 139     unsigned int val;
 140     int bit_cnt;
 141     unsigned int bit_buf;
 142
 143 #ifdef STATS
 144     st_bit_counts[st_current_index] += n;
 145 #endif
 146
 147     bit_buf = s->bit_buf;
 148     bit_cnt = s->bit_cnt - n;
 149
 150 //    if (bit_cnt >= 0) {
 151 //        val = bit_buf >> (32 - n);
 152 //        bit_buf <<= n;
 153 //    } else
 154     {
 155         UINT8 *buf_ptr;
 156         val = bit_buf >> (32 - n);
 157         buf_ptr = s->buf_ptr;
 158         buf_ptr += 4;
 159         /* handle common case: we can read everything */
 160         if (buf_ptr <= s->buf_end) {
 161 #if ARCH_X86
 162             bit_buf = bswap_32(*((unsigned long*)(&buf_ptr[-4])));
 163 #else
 164             bit_buf = (buf_ptr[-4] << 24) |
 165                 (buf_ptr[-3] << 16) |
 166                 (buf_ptr[-2] << 8) |
 167                 (buf_ptr[-1]);
 168 #endif
 169         } else {
 170             buf_ptr -= 4;
 171             bit_buf = 0;
 172             if (buf_ptr < s->buf_end)
 173                 bit_buf |= *buf_ptr++ << 24;
 174             if (buf_ptr < s->buf_end)
 175                 bit_buf |= *buf_ptr++ << 16;
 176             if (buf_ptr < s->buf_end)
 177                 bit_buf |= *buf_ptr++ << 8;
 178             if (buf_ptr < s->buf_end)
 179                 bit_buf |= *buf_ptr++;
 180         }
 181         s->buf_ptr = buf_ptr;
 182         val |= bit_buf >> (32 + bit_cnt);
 183         bit_buf <<= - bit_cnt;
 184         bit_cnt += 32;
 185     }
 186     s->bit_buf = bit_buf;
 187     s->bit_cnt = bit_cnt;
 188     return val;
 189 }
 190 #endif
 191
 192 void align_get_bits(GetBitContext *s)
 193 {
 194 #ifdef ALT_BITSTREAM_READER
 195     s->index= (s->index + 7) & (~7);
 196 #else
 197     int n;
 198     n = s->bit_cnt & 7;
 199     if (n > 0) {
 200         get_bits(s, n);
 201     }
 202 #endif
 203 }
 204
 205 int check_marker(GetBitContext *s, char *msg)
 206 {
 207     int bit= get_bits1(s);
 208     if(!bit) printf("Marker bit missing %s\n", msg);
 209
 210     return bit;
 211 }
 212
 213 #ifndef ALT_BITSTREAM_READER
 214 /* This function is identical to get_bits_long(), the */
 215 /* only diference is that it doesn't touch the buffer */
 216 /* it is usefull to see the buffer.                   */
 217
 218 unsigned int show_bits_long(GetBitContext *s, int n)
 219 {
 220     unsigned int val;
 221     int bit_cnt;
 222     unsigned int bit_buf;
 223         UINT8 *buf_ptr;
 224
 225     bit_buf = s->bit_buf;
 226     bit_cnt = s->bit_cnt - n;
 227
 228     val = bit_buf >> (32 - n);
 229     buf_ptr = s->buf_ptr;
 230     buf_ptr += 4;
 231
 232     /* handle common case: we can read everything */
 233     if (buf_ptr <= s->buf_end) {
 234 #ifdef ARCH_X86
 235         bit_buf = bswap_32(*((unsigned long*)(&buf_ptr[-4])));
 236 #else
 237         bit_buf = (buf_ptr[-4] << 24) |
 238             (buf_ptr[-3] << 16) |
 239             (buf_ptr[-2] << 8) |
 240             (buf_ptr[-1]);
 241 #endif
 242     } else {
 243         buf_ptr -= 4;
 244         bit_buf = 0;
 245         if (buf_ptr < s->buf_end)
 246             bit_buf |= *buf_ptr++ << 24;
 247         if (buf_ptr < s->buf_end)
 248             bit_buf |= *buf_ptr++ << 16;
 249         if (buf_ptr < s->buf_end)
 250             bit_buf |= *buf_ptr++ << 8;
 251         if (buf_ptr < s->buf_end)
 252             bit_buf |= *buf_ptr++;
 253     }
 254     val |= bit_buf >> (32 + bit_cnt);
 255     bit_buf <<= - bit_cnt;
 256     bit_cnt += 32;
 257
 258     return val;
 259 }
 260 #endif
 261
 262 /* VLC decoding */
 263
 264 //#define DEBUG_VLC
 265
 266 #define GET_DATA(v, table, i, wrap, size) \
 267 {\
 268     UINT8 *ptr = (UINT8 *)table + i * wrap;\
 269     switch(size) {\
 270     case 1:\
 271         v = *(UINT8 *)ptr;\
 272         break;\
 273     case 2:\
 274         v = *(UINT16 *)ptr;\
 275         break;\
 276     default:\
 277         v = *(UINT32 *)ptr;\
 278         break;\
 279     }\
 280 }
 281
 282
 283 static int alloc_table(VLC *vlc, int size)
 284 {
 285     int index;
 286     index = vlc->table_size;
 287     vlc->table_size += size;
 288     if (vlc->table_size > vlc->table_allocated) {
 289         vlc->table_allocated += (1 << vlc->bits);
 290         vlc->table_bits = realloc(vlc->table_bits,
 291                                   sizeof(INT8) * vlc->table_allocated);
 292         vlc->table_codes = realloc(vlc->table_codes,
 293                                    sizeof(INT16) * vlc->table_allocated);
 294         if (!vlc->table_bits ||
 295             !vlc->table_codes)
 296             return -1;
 297     }
 298     return index;
 299 }
 300
 301 static int build_table(VLC *vlc, int table_nb_bits,
 302                        int nb_codes,
 303                        const void *bits, int bits_wrap, int bits_size,
 304                        const void *codes, int codes_wrap, int codes_size,
 305                        UINT32 code_prefix, int n_prefix)
 306 {
 307     int i, j, k, n, table_size, table_index, nb, n1, index;
 308     UINT32 code;
 309     INT8 *table_bits;
 310     INT16 *table_codes;
 311
 312     table_size = 1 << table_nb_bits;
 313     table_index = alloc_table(vlc, table_size);
 314 #ifdef DEBUG_VLC
 315     printf("new table index=%d size=%d code_prefix=%x n=%d\n",
 316            table_index, table_size, code_prefix, n_prefix);
 317 #endif
 318     if (table_index < 0)
 319         return -1;
 320     table_bits = &vlc->table_bits[table_index];
 321     table_codes = &vlc->table_codes[table_index];
 322
 323     for(i=0;i<table_size;i++) {
 324         table_bits[i] = 0;
 325         table_codes[i] = -1;
 326     }
 327
 328     /* first pass: map codes and compute auxillary table sizes */
 329     for(i=0;i<nb_codes;i++) {
 330         GET_DATA(n, bits, i, bits_wrap, bits_size);
 331         GET_DATA(code, codes, i, codes_wrap, codes_size);
 332         /* we accept tables with holes */
 333         if (n <= 0)
 334             continue;
 335 #if defined(DEBUG_VLC) && 0
 336         printf("i=%d n=%d code=0x%x\n", i, n, code);
 337 #endif
 338         /* if code matches the prefix, it is in the table */
 339         n -= n_prefix;
 340         if (n > 0 && (code >> n) == code_prefix) {
 341             if (n <= table_nb_bits) {
 342                 /* no need to add another table */
 343                 j = (code << (table_nb_bits - n)) & (table_size - 1);
 344                 nb = 1 << (table_nb_bits - n);
 345                 for(k=0;k<nb;k++) {
 346 #ifdef DEBUG_VLC
 347                     printf("%4x: code=%d n=%d\n",
 348                            j, i, n);
 349 #endif
 350                     if (table_bits[j] != 0) {
 351                         fprintf(stderr, "incorrect codes\n");
 352                         exit(1);
 353                     }
 354                     table_bits[j] = n;
 355                     table_codes[j] = i;
 356                     j++;
 357                 }
 358             } else {
 359                 n -= table_nb_bits;
 360                 j = (code >> n) & ((1 << table_nb_bits) - 1);
 361 #ifdef DEBUG_VLC
 362                 printf("%4x: n=%d (subtable)\n",
 363                        j, n);
 364 #endif
 365                 /* compute table size */
 366                 n1 = -table_bits[j];
 367                 if (n > n1)
 368                     n1 = n;
 369                 table_bits[j] = -n1;
 370             }
 371         }
 372     }
 373
 374     /* second pass : fill auxillary tables recursively */
 375     for(i=0;i<table_size;i++) {
 376         n = table_bits[i];
 377         if (n < 0) {
 378             n = -n;
 379             if (n > table_nb_bits) {
 380                 n = table_nb_bits;
 381                 table_bits[i] = -n;
 382             }
 383             index = build_table(vlc, n, nb_codes,
 384                                 bits, bits_wrap, bits_size,
 385                                 codes, codes_wrap, codes_size,
 386                                 (code_prefix << table_nb_bits) | i,
 387                                 n_prefix + table_nb_bits);
 388             if (index < 0)
 389                 return -1;
 390             /* note: realloc has been done, so reload tables */
 391             table_bits = &vlc->table_bits[table_index];
 392             table_codes = &vlc->table_codes[table_index];
 393             table_codes[i] = index;
 394         }
 395     }
 396     return table_index;
 397 }
 398
 399
 400 /* Build VLC decoding tables suitable for use with get_vlc().
 401
 402    'nb_bits' set thee decoding table size (2^nb_bits) entries. The
 403    bigger it is, the faster is the decoding. But it should not be too
 404    big to save memory and L1 cache. '9' is a good compromise.
 405
 406    'nb_codes' : number of vlcs codes
 407
 408    'bits' : table which gives the size (in bits) of each vlc code.
 409
 410    'codes' : table which gives the bit pattern of of each vlc code.
 411
 412    'xxx_wrap' : give the number of bytes between each entry of the
 413    'bits' or 'codes' tables.
 414
 415    'xxx_size' : gives the number of bytes of each entry of the 'bits'
 416    or 'codes' tables.
 417
 418    'wrap' and 'size' allows to use any memory configuration and types
 419    (byte/word/long) to store the 'bits' and 'codes' tables.
 420 */
 421 int init_vlc(VLC *vlc, int nb_bits, int nb_codes,
 422              const void *bits, int bits_wrap, int bits_size,
 423              const void *codes, int codes_wrap, int codes_size)
 424 {
 425     vlc->bits = nb_bits;
 426     vlc->table_bits = NULL;
 427     vlc->table_codes = NULL;
 428     vlc->table_allocated = 0;
 429     vlc->table_size = 0;
 430 #ifdef DEBUG_VLC
 431     printf("build table nb_codes=%d\n", nb_codes);
 432 #endif
 433
 434     if (build_table(vlc, nb_bits, nb_codes,
 435                     bits, bits_wrap, bits_size,
 436                     codes, codes_wrap, codes_size,
 437                     0, 0) < 0) {
 438         if (vlc->table_bits)
 439             free(vlc->table_bits);
 440         if (vlc->table_codes)
 441             free(vlc->table_codes);
 442         return -1;
 443     }
 444     return 0;
 445 }
 446
 447
 448 void free_vlc(VLC *vlc)
 449 {
 450     free(vlc->table_bits);
 451     free(vlc->table_codes);
 452 }
 453
 454 int ff_gcd(int a, int b){
 455     if(b) return ff_gcd(b, a%b);
 456     else  return a;
 457 }