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 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_ptr = s->buf;
  31     s->buf_end = s->buf + buffer_size;
  32     s->bit_cnt=0;
  33     s->bit_buf=0;
  34     s->data_out_size = 0;
  35     s->write_data = write_data;
  36     s->opaque = opaque;
  37 }
  38
  39 static void flush_buffer(PutBitContext *s)
  40 {
  41     int size;
  42     if (s->write_data) {
  43         size = s->buf_ptr - s->buf;
  44         if (size > 0)
  45             s->write_data(s->opaque, s->buf, size);
  46         s->buf_ptr = s->buf;
  47         s->data_out_size += size;
  48     }
  49 }
  50
  51 void put_bits(PutBitContext *s, int n, unsigned int value)
  52 {
  53     unsigned int bit_buf;
  54     int bit_cnt;
  55
  56 #ifdef STATS
  57     st_out_bit_counts[st_current_index] += n;
  58 #endif
  59     //    printf("put_bits=%d %x\n", n, value);
  60     assert(n == 32 || value < (1U << n));
  61
  62     bit_buf = s->bit_buf;
  63     bit_cnt = s->bit_cnt;
  64
  65     //    printf("n=%d value=%x cnt=%d buf=%x\n", n, value, bit_cnt, bit_buf);
  66     /* XXX: optimize */
  67     if (n < (32-bit_cnt)) {
  68         bit_buf |= value << (32 - n - bit_cnt);
  69         bit_cnt+=n;
  70     } else {
  71         bit_buf |= value >> (n + bit_cnt - 32);
  72         *(UINT32 *)s->buf_ptr = be2me_32(bit_buf);
  73         //printf("bitbuf = %08x\n", bit_buf);
  74         s->buf_ptr+=4;
  75         if (s->buf_ptr >= s->buf_end)
  76             flush_buffer(s);
  77         bit_cnt=bit_cnt + n - 32;
  78         if (bit_cnt == 0) {
  79             bit_buf = 0;
  80         } else {
  81             bit_buf = value << (32 - bit_cnt);
  82         }
  83     }
  84
  85     s->bit_buf = bit_buf;
  86     s->bit_cnt = bit_cnt;
  87 }
  88
  89 /* return the number of bits output */
  90 INT64 get_bit_count(PutBitContext *s)
  91 {
  92     return (s->buf_ptr - s->buf + s->data_out_size) * 8 + (INT64)s->bit_cnt;
  93 }
  94
  95 void align_put_bits(PutBitContext *s)
  96 {
  97     put_bits(s,(8 - s->bit_cnt) & 7,0);
  98 }
  99
 100 /* pad the end of the output stream with zeros */
 101 void flush_put_bits(PutBitContext *s)
 102 {
 103     while (s->bit_cnt > 0) {
 104         /* XXX: should test end of buffer */
 105         *s->buf_ptr++=s->bit_buf >> 24;
 106         s->bit_buf<<=8;
 107         s->bit_cnt-=8;
 108     }
 109     flush_buffer(s);
 110     s->bit_cnt=0;
 111     s->bit_buf=0;
 112 }
 113
 114 /* for jpeg : escape 0xff with 0x00 after it */
 115 void jput_bits(PutBitContext *s, int n, unsigned int value)
 116 {
 117     unsigned int bit_buf, b;
 118     int bit_cnt, i;
 119
 120     assert(n == 32 || value < (1U << n));
 121
 122     bit_buf = s->bit_buf;
 123     bit_cnt = s->bit_cnt;
 124
 125     //printf("n=%d value=%x cnt=%d buf=%x\n", n, value, bit_cnt, bit_buf);
 126     /* XXX: optimize */
 127     if (n < (32-bit_cnt)) {
 128         bit_buf |= value << (32 - n - bit_cnt);
 129         bit_cnt+=n;
 130     } else {
 131         bit_buf |= value >> (n + bit_cnt - 32);
 132         /* handle escape */
 133         for(i=0;i<4;i++) {
 134             b = (bit_buf >> 24);
 135             *(s->buf_ptr++) = b;
 136             if (b == 0xff)
 137                 *(s->buf_ptr++) = 0;
 138             bit_buf <<= 8;
 139         }
 140         /* we flush the buffer sooner to handle worst case */
 141         if (s->buf_ptr >= (s->buf_end - 8))
 142             flush_buffer(s);
 143
 144         bit_cnt=bit_cnt + n - 32;
 145         if (bit_cnt == 0) {
 146             bit_buf = 0;
 147         } else {
 148             bit_buf = value << (32 - bit_cnt);
 149         }
 150     }
 151
 152     s->bit_buf = bit_buf;
 153     s->bit_cnt = bit_cnt;
 154 }
 155
 156 /* pad the end of the output stream with zeros */
 157 void jflush_put_bits(PutBitContext *s)
 158 {
 159     unsigned int b;
 160
 161     while (s->bit_cnt > 0) {
 162         b = s->bit_buf >> 24;
 163         *s->buf_ptr++ = b;
 164         if (b == 0xff)
 165             *s->buf_ptr++ = 0;
 166         s->bit_buf<<=8;
 167         s->bit_cnt-=8;
 168     }
 169     flush_buffer(s);
 170     s->bit_cnt=0;
 171     s->bit_buf=0;
 172 }
 173
 174 /* bit input functions */
 175
 176 void init_get_bits(GetBitContext *s,
 177                    UINT8 *buffer, int buffer_size)
 178 {
 179 #ifdef ALT_BITSTREAM_READER
 180     s->index=0;
 181     s->buffer= buffer;
 182 #else
 183     s->buf = buffer;
 184     s->buf_ptr = buffer;
 185     s->buf_end = buffer + buffer_size;
 186     s->bit_cnt = 0;
 187     s->bit_buf = 0;
 188     while (s->buf_ptr < s->buf_end &&
 189            s->bit_cnt < 32) {
 190         s->bit_buf |= (*s->buf_ptr++ << (24 - s->bit_cnt));
 191         s->bit_cnt += 8;
 192     }
 193 #endif
 194 }
 195
 196 #ifndef ALT_BITSTREAM_READER
 197 /* n must be >= 1 and <= 32 */
 198 /* also true: n > s->bit_cnt */
 199 unsigned int get_bits_long(GetBitContext *s, int n)
 200 {
 201     unsigned int val;
 202     int bit_cnt;
 203     unsigned int bit_buf;
 204
 205 #ifdef STATS
 206     st_bit_counts[st_current_index] += n;
 207 #endif
 208
 209     bit_buf = s->bit_buf;
 210     bit_cnt = s->bit_cnt - n;
 211
 212 //    if (bit_cnt >= 0) {
 213 //        val = bit_buf >> (32 - n);
 214 //        bit_buf <<= n;
 215 //    } else
 216     {
 217         UINT8 *buf_ptr;
 218         val = bit_buf >> (32 - n);
 219         buf_ptr = s->buf_ptr;
 220         buf_ptr += 4;
 221         /* handle common case: we can read everything */
 222         if (buf_ptr <= s->buf_end) {
 223 #if ARCH_X86
 224             bit_buf = bswap_32(*((unsigned long*)(&buf_ptr[-4])));
 225 #else
 226             bit_buf = (buf_ptr[-4] << 24) |
 227                 (buf_ptr[-3] << 16) |
 228                 (buf_ptr[-2] << 8) |
 229                 (buf_ptr[-1]);
 230 #endif
 231         } else {
 232             buf_ptr -= 4;
 233             bit_buf = 0;
 234             if (buf_ptr < s->buf_end)
 235                 bit_buf |= *buf_ptr++ << 24;
 236             if (buf_ptr < s->buf_end)
 237                 bit_buf |= *buf_ptr++ << 16;
 238             if (buf_ptr < s->buf_end)
 239                 bit_buf |= *buf_ptr++ << 8;
 240             if (buf_ptr < s->buf_end)
 241                 bit_buf |= *buf_ptr++;
 242         }
 243         s->buf_ptr = buf_ptr;
 244         val |= bit_buf >> (32 + bit_cnt);
 245         bit_buf <<= - bit_cnt;
 246         bit_cnt += 32;
 247     }
 248     s->bit_buf = bit_buf;
 249     s->bit_cnt = bit_cnt;
 250     return val;
 251 }
 252 #endif
 253
 254 void align_get_bits(GetBitContext *s)
 255 {
 256 #ifdef ALT_BITSTREAM_READER
 257     s->index= (s->index + 7) & (~7);
 258 #else
 259     int n;
 260     n = s->bit_cnt & 7;
 261     if (n > 0) {
 262         get_bits(s, n);
 263     }
 264 #endif
 265 }
 266
 267 #ifndef ALT_BITSTREAM_READER
 268 /* This function is identical to get_bits_long(), the */
 269 /* only diference is that it doesn't touch the buffer */
 270 /* it is usefull to see the buffer.                   */
 271
 272 unsigned int show_bits_long(GetBitContext *s, int n)
 273 {
 274     unsigned int val;
 275     int bit_cnt;
 276     unsigned int bit_buf;
 277         UINT8 *buf_ptr;
 278
 279     bit_buf = s->bit_buf;
 280     bit_cnt = s->bit_cnt - n;
 281
 282     val = bit_buf >> (32 - n);
 283     buf_ptr = s->buf_ptr;
 284     buf_ptr += 4;
 285
 286     /* handle common case: we can read everything */
 287     if (buf_ptr <= s->buf_end) {
 288 #ifdef ARCH_X86
 289         bit_buf = bswap_32(*((unsigned long*)(&buf_ptr[-4])));
 290 #else
 291         bit_buf = (buf_ptr[-4] << 24) |
 292             (buf_ptr[-3] << 16) |
 293             (buf_ptr[-2] << 8) |
 294             (buf_ptr[-1]);
 295 #endif
 296     } else {
 297         buf_ptr -= 4;
 298         bit_buf = 0;
 299         if (buf_ptr < s->buf_end)
 300             bit_buf |= *buf_ptr++ << 24;
 301         if (buf_ptr < s->buf_end)
 302             bit_buf |= *buf_ptr++ << 16;
 303         if (buf_ptr < s->buf_end)
 304             bit_buf |= *buf_ptr++ << 8;
 305         if (buf_ptr < s->buf_end)
 306             bit_buf |= *buf_ptr++;
 307     }
 308     val |= bit_buf >> (32 + bit_cnt);
 309     bit_buf <<= - bit_cnt;
 310     bit_cnt += 32;
 311
 312     return val;
 313 }
 314 #endif
 315
 316 /* VLC decoding */
 317
 318 //#define DEBUG_VLC
 319
 320 #define GET_DATA(v, table, i, wrap, size) \
 321 {\
 322     UINT8 *ptr = (UINT8 *)table + i * wrap;\
 323     switch(size) {\
 324     case 1:\
 325         v = *(UINT8 *)ptr;\
 326         break;\
 327     case 2:\
 328         v = *(UINT16 *)ptr;\
 329         break;\
 330     default:\
 331         v = *(UINT32 *)ptr;\
 332         break;\
 333     }\
 334 }
 335
 336
 337 static int alloc_table(VLC *vlc, int size)
 338 {
 339     int index;
 340     index = vlc->table_size;
 341     vlc->table_size += size;
 342     if (vlc->table_size > vlc->table_allocated) {
 343         vlc->table_allocated += (1 << vlc->bits);
 344         vlc->table_bits = realloc(vlc->table_bits,
 345                                   sizeof(INT8) * vlc->table_allocated);
 346         vlc->table_codes = realloc(vlc->table_codes,
 347                                    sizeof(INT16) * vlc->table_allocated);
 348         if (!vlc->table_bits ||
 349             !vlc->table_codes)
 350             return -1;
 351     }
 352     return index;
 353 }
 354
 355 static int build_table(VLC *vlc, int table_nb_bits,
 356                        int nb_codes,
 357                        const void *bits, int bits_wrap, int bits_size,
 358                        const void *codes, int codes_wrap, int codes_size,
 359                        UINT32 code_prefix, int n_prefix)
 360 {
 361     int i, j, k, n, table_size, table_index, nb, n1, index;
 362     UINT32 code;
 363     INT8 *table_bits;
 364     INT16 *table_codes;
 365
 366     table_size = 1 << table_nb_bits;
 367     table_index = alloc_table(vlc, table_size);
 368 #ifdef DEBUG_VLC
 369     printf("new table index=%d size=%d code_prefix=%x n=%d\n",
 370            table_index, table_size, code_prefix, n_prefix);
 371 #endif
 372     if (table_index < 0)
 373         return -1;
 374     table_bits = &vlc->table_bits[table_index];
 375     table_codes = &vlc->table_codes[table_index];
 376
 377     for(i=0;i<table_size;i++) {
 378         table_bits[i] = 0;
 379         table_codes[i] = -1;
 380     }
 381
 382     /* first pass: map codes and compute auxillary table sizes */
 383     for(i=0;i<nb_codes;i++) {
 384         GET_DATA(n, bits, i, bits_wrap, bits_size);
 385         GET_DATA(code, codes, i, codes_wrap, codes_size);
 386         /* we accept tables with holes */
 387         if (n <= 0)
 388             continue;
 389 #if defined(DEBUG_VLC) && 0
 390         printf("i=%d n=%d code=0x%x\n", i, n, code);
 391 #endif
 392         /* if code matches the prefix, it is in the table */
 393         n -= n_prefix;
 394         if (n > 0 && (code >> n) == code_prefix) {
 395             if (n <= table_nb_bits) {
 396                 /* no need to add another table */
 397                 j = (code << (table_nb_bits - n)) & (table_size - 1);
 398                 nb = 1 << (table_nb_bits - n);
 399                 for(k=0;k<nb;k++) {
 400 #ifdef DEBUG_VLC
 401                     printf("%4x: code=%d n=%d\n",
 402                            j, i, n);
 403 #endif
 404                     if (table_bits[j] != 0) {
 405                         fprintf(stderr, "incorrect codes\n");
 406                         exit(1);
 407                     }
 408                     table_bits[j] = n;
 409                     table_codes[j] = i;
 410                     j++;
 411                 }
 412             } else {
 413                 n -= table_nb_bits;
 414                 j = (code >> n) & ((1 << table_nb_bits) - 1);
 415 #ifdef DEBUG_VLC
 416                 printf("%4x: n=%d (subtable)\n",
 417                        j, n);
 418 #endif
 419                 /* compute table size */
 420                 n1 = -table_bits[j];
 421                 if (n > n1)
 422                     n1 = n;
 423                 table_bits[j] = -n1;
 424             }
 425         }
 426     }
 427
 428     /* second pass : fill auxillary tables recursively */
 429     for(i=0;i<table_size;i++) {
 430         n = table_bits[i];
 431         if (n < 0) {
 432             n = -n;
 433             if (n > table_nb_bits) {
 434                 n = table_nb_bits;
 435                 table_bits[i] = -n;
 436             }
 437             index = build_table(vlc, n, nb_codes,
 438                                 bits, bits_wrap, bits_size,
 439                                 codes, codes_wrap, codes_size,
 440                                 (code_prefix << table_nb_bits) | i,
 441                                 n_prefix + table_nb_bits);
 442             if (index < 0)
 443                 return -1;
 444             /* note: realloc has been done, so reload tables */
 445             table_bits = &vlc->table_bits[table_index];
 446             table_codes = &vlc->table_codes[table_index];
 447             table_codes[i] = index;
 448         }
 449     }
 450     return table_index;
 451 }
 452
 453
 454 /* Build VLC decoding tables suitable for use with get_vlc().
 455
 456    'nb_bits' set thee decoding table size (2^nb_bits) entries. The
 457    bigger it is, the faster is the decoding. But it should not be too
 458    big to save memory and L1 cache. '9' is a good compromise.
 459
 460    'nb_codes' : number of vlcs codes
 461
 462    'bits' : table which gives the size (in bits) of each vlc code.
 463
 464    'codes' : table which gives the bit pattern of of each vlc code.
 465
 466    'xxx_wrap' : give the number of bytes between each entry of the
 467    'bits' or 'codes' tables.
 468
 469    'xxx_size' : gives the number of bytes of each entry of the 'bits'
 470    or 'codes' tables.
 471
 472    'wrap' and 'size' allows to use any memory configuration and types
 473    (byte/word/long) to store the 'bits' and 'codes' tables.
 474 */
 475 int init_vlc(VLC *vlc, int nb_bits, int nb_codes,
 476              const void *bits, int bits_wrap, int bits_size,
 477              const void *codes, int codes_wrap, int codes_size)
 478 {
 479     vlc->bits = nb_bits;
 480     vlc->table_bits = NULL;
 481     vlc->table_codes = NULL;
 482     vlc->table_allocated = 0;
 483     vlc->table_size = 0;
 484 #ifdef DEBUG_VLC
 485     printf("build table nb_codes=%d\n", nb_codes);
 486 #endif
 487
 488     if (build_table(vlc, nb_bits, nb_codes,
 489                     bits, bits_wrap, bits_size,
 490                     codes, codes_wrap, codes_size,
 491                     0, 0) < 0) {
 492         if (vlc->table_bits)
 493             free(vlc->table_bits);
 494         if (vlc->table_codes)
 495             free(vlc->table_codes);
 496         return -1;
 497     }
 498     return 0;
 499 }
 500
 501
 502 void free_vlc(VLC *vlc)
 503 {
 504     free(vlc->table_bits);
 505     free(vlc->table_codes);
 506 }
 507
 508 int get_vlc(GetBitContext *s, VLC *vlc)
 509 {
 510     int bit_cnt, code, n, nb_bits, index;
 511     UINT32 bit_buf;
 512     INT16 *table_codes;
 513     INT8 *table_bits;
 514     UINT8 *buf_ptr;
 515
 516     SAVE_BITS(s);
 517     nb_bits = vlc->bits;
 518     table_codes = vlc->table_codes;
 519     table_bits = vlc->table_bits;
 520     for(;;) {
 521         SHOW_BITS(s, index, nb_bits);
 522         code = table_codes[index];
 523         n = table_bits[index];
 524         if (n > 0) {
 525             /* most common case */
 526             FLUSH_BITS(n);
 527 #ifdef STATS
 528             st_bit_counts[st_current_index] += n;
 529 #endif
 530             break;
 531         } else if (n == 0) {
 532             return -1;
 533         } else {
 534             FLUSH_BITS(nb_bits);
 535 #ifdef STATS
 536             st_bit_counts[st_current_index] += nb_bits;
 537 #endif
 538             nb_bits = -n;
 539             table_codes = vlc->table_codes + code;
 540             table_bits = vlc->table_bits + code;
 541         }
 542     }
 543     RESTORE_BITS(s);
 544     return code;
 545 }