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

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