• Main Page
  • Related Pages
  • Modules
  • Data Structures
  • Files
  • Examples
  • File List
  • Globals

libavcodec/bitstream.c

Go to the documentation of this file.
00001 /*
00002  * Common bit i/o utils
00003  * Copyright (c) 2000, 2001 Fabrice Bellard
00004  * Copyright (c) 2002-2004 Michael Niedermayer <michaelni@gmx.at>
00005  * Copyright (c) 2010 Loren Merritt
00006  *
00007  * alternative bitstream reader & writer by Michael Niedermayer <michaelni@gmx.at>
00008  *
00009  * This file is part of Libav.
00010  *
00011  * Libav is free software; you can redistribute it and/or
00012  * modify it under the terms of the GNU Lesser General Public
00013  * License as published by the Free Software Foundation; either
00014  * version 2.1 of the License, or (at your option) any later version.
00015  *
00016  * Libav is distributed in the hope that it will be useful,
00017  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00018  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00019  * Lesser General Public License for more details.
00020  *
00021  * You should have received a copy of the GNU Lesser General Public
00022  * License along with Libav; if not, write to the Free Software
00023  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
00024  */
00025 
00031 #include "avcodec.h"
00032 #include "get_bits.h"
00033 #include "put_bits.h"
00034 
00035 const uint8_t ff_log2_run[41]={
00036  0, 0, 0, 0, 1, 1, 1, 1,
00037  2, 2, 2, 2, 3, 3, 3, 3,
00038  4, 4, 5, 5, 6, 6, 7, 7,
00039  8, 9,10,11,12,13,14,15,
00040 16,17,18,19,20,21,22,23,
00041 24,
00042 };
00043 
00044 void avpriv_align_put_bits(PutBitContext *s)
00045 {
00046     put_bits(s,s->bit_left & 7,0);
00047 }
00048 
00049 void ff_put_string(PutBitContext *pb, const char *string, int terminate_string)
00050 {
00051     while(*string){
00052         put_bits(pb, 8, *string);
00053         string++;
00054     }
00055     if(terminate_string)
00056         put_bits(pb, 8, 0);
00057 }
00058 
00059 void avpriv_copy_bits(PutBitContext *pb, const uint8_t *src, int length)
00060 {
00061     int words= length>>4;
00062     int bits= length&15;
00063     int i;
00064 
00065     if(length==0) return;
00066 
00067     if(CONFIG_SMALL || words < 16 || put_bits_count(pb)&7){
00068         for(i=0; i<words; i++) put_bits(pb, 16, AV_RB16(src + 2*i));
00069     }else{
00070         for(i=0; put_bits_count(pb)&31; i++)
00071             put_bits(pb, 8, src[i]);
00072         flush_put_bits(pb);
00073         memcpy(put_bits_ptr(pb), src+i, 2*words-i);
00074         skip_put_bytes(pb, 2*words-i);
00075     }
00076 
00077     put_bits(pb, bits, AV_RB16(src + 2*words)>>(16-bits));
00078 }
00079 
00080 /* VLC decoding */
00081 
00082 #define GET_DATA(v, table, i, wrap, size) \
00083 {\
00084     const uint8_t *ptr = (const uint8_t *)table + i * wrap;\
00085     switch(size) {\
00086     case 1:\
00087         v = *(const uint8_t *)ptr;\
00088         break;\
00089     case 2:\
00090         v = *(const uint16_t *)ptr;\
00091         break;\
00092     default:\
00093         v = *(const uint32_t *)ptr;\
00094         break;\
00095     }\
00096 }
00097 
00098 
00099 static int alloc_table(VLC *vlc, int size, int use_static)
00100 {
00101     int index;
00102     index = vlc->table_size;
00103     vlc->table_size += size;
00104     if (vlc->table_size > vlc->table_allocated) {
00105         if(use_static)
00106             abort(); // cannot do anything, init_vlc() is used with too little memory
00107         vlc->table_allocated += (1 << vlc->bits);
00108         vlc->table = av_realloc(vlc->table,
00109                                 sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
00110         if (!vlc->table)
00111             return -1;
00112     }
00113     return index;
00114 }
00115 
00116 static av_always_inline uint32_t bitswap_32(uint32_t x) {
00117     return (uint32_t)av_reverse[x&0xFF]<<24
00118          | (uint32_t)av_reverse[(x>>8)&0xFF]<<16
00119          | (uint32_t)av_reverse[(x>>16)&0xFF]<<8
00120          | (uint32_t)av_reverse[x>>24];
00121 }
00122 
00123 typedef struct {
00124     uint8_t bits;
00125     uint16_t symbol;
00128     uint32_t code;
00129 } VLCcode;
00130 
00131 static int compare_vlcspec(const void *a, const void *b)
00132 {
00133     const VLCcode *sa=a, *sb=b;
00134     return (sa->code >> 1) - (sb->code >> 1);
00135 }
00136 
00151 static int build_table(VLC *vlc, int table_nb_bits, int nb_codes,
00152                        VLCcode *codes, int flags)
00153 {
00154     int table_size, table_index, index, code_prefix, symbol, subtable_bits;
00155     int i, j, k, n, nb, inc;
00156     uint32_t code;
00157     VLC_TYPE (*table)[2];
00158 
00159     table_size = 1 << table_nb_bits;
00160     table_index = alloc_table(vlc, table_size, flags & INIT_VLC_USE_NEW_STATIC);
00161     av_dlog(NULL, "new table index=%d size=%d\n", table_index, table_size);
00162     if (table_index < 0)
00163         return -1;
00164     table = &vlc->table[table_index];
00165 
00166     for (i = 0; i < table_size; i++) {
00167         table[i][1] = 0; //bits
00168         table[i][0] = -1; //codes
00169     }
00170 
00171     /* first pass: map codes and compute auxillary table sizes */
00172     for (i = 0; i < nb_codes; i++) {
00173         n = codes[i].bits;
00174         code = codes[i].code;
00175         symbol = codes[i].symbol;
00176         av_dlog(NULL, "i=%d n=%d code=0x%x\n", i, n, code);
00177         if (n <= table_nb_bits) {
00178             /* no need to add another table */
00179             j = code >> (32 - table_nb_bits);
00180             nb = 1 << (table_nb_bits - n);
00181             inc = 1;
00182             if (flags & INIT_VLC_LE) {
00183                 j = bitswap_32(code);
00184                 inc = 1 << n;
00185             }
00186             for (k = 0; k < nb; k++) {
00187                 av_dlog(NULL, "%4x: code=%d n=%d\n", j, i, n);
00188                 if (table[j][1] /*bits*/ != 0) {
00189                     av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
00190                     return -1;
00191                 }
00192                 table[j][1] = n; //bits
00193                 table[j][0] = symbol;
00194                 j += inc;
00195             }
00196         } else {
00197             /* fill auxiliary table recursively */
00198             n -= table_nb_bits;
00199             code_prefix = code >> (32 - table_nb_bits);
00200             subtable_bits = n;
00201             codes[i].bits = n;
00202             codes[i].code = code << table_nb_bits;
00203             for (k = i+1; k < nb_codes; k++) {
00204                 n = codes[k].bits - table_nb_bits;
00205                 if (n <= 0)
00206                     break;
00207                 code = codes[k].code;
00208                 if (code >> (32 - table_nb_bits) != code_prefix)
00209                     break;
00210                 codes[k].bits = n;
00211                 codes[k].code = code << table_nb_bits;
00212                 subtable_bits = FFMAX(subtable_bits, n);
00213             }
00214             subtable_bits = FFMIN(subtable_bits, table_nb_bits);
00215             j = (flags & INIT_VLC_LE) ? bitswap_32(code_prefix) >> (32 - table_nb_bits) : code_prefix;
00216             table[j][1] = -subtable_bits;
00217             av_dlog(NULL, "%4x: n=%d (subtable)\n",
00218                     j, codes[i].bits + table_nb_bits);
00219             index = build_table(vlc, subtable_bits, k-i, codes+i, flags);
00220             if (index < 0)
00221                 return -1;
00222             /* note: realloc has been done, so reload tables */
00223             table = &vlc->table[table_index];
00224             table[j][0] = index; //code
00225             i = k-1;
00226         }
00227     }
00228     return table_index;
00229 }
00230 
00231 
00232 /* Build VLC decoding tables suitable for use with get_vlc().
00233 
00234    'nb_bits' set thee decoding table size (2^nb_bits) entries. The
00235    bigger it is, the faster is the decoding. But it should not be too
00236    big to save memory and L1 cache. '9' is a good compromise.
00237 
00238    'nb_codes' : number of vlcs codes
00239 
00240    'bits' : table which gives the size (in bits) of each vlc code.
00241 
00242    'codes' : table which gives the bit pattern of of each vlc code.
00243 
00244    'symbols' : table which gives the values to be returned from get_vlc().
00245 
00246    'xxx_wrap' : give the number of bytes between each entry of the
00247    'bits' or 'codes' tables.
00248 
00249    'xxx_size' : gives the number of bytes of each entry of the 'bits'
00250    or 'codes' tables.
00251 
00252    'wrap' and 'size' allows to use any memory configuration and types
00253    (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
00254 
00255    'use_static' should be set to 1 for tables, which should be freed
00256    with av_free_static(), 0 if free_vlc() will be used.
00257 */
00258 int init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes,
00259              const void *bits, int bits_wrap, int bits_size,
00260              const void *codes, int codes_wrap, int codes_size,
00261              const void *symbols, int symbols_wrap, int symbols_size,
00262              int flags)
00263 {
00264     VLCcode *buf;
00265     int i, j, ret;
00266 
00267     vlc->bits = nb_bits;
00268     if(flags & INIT_VLC_USE_NEW_STATIC){
00269         if(vlc->table_size && vlc->table_size == vlc->table_allocated){
00270             return 0;
00271         }else if(vlc->table_size){
00272             abort(); // fatal error, we are called on a partially initialized table
00273         }
00274     }else {
00275         vlc->table = NULL;
00276         vlc->table_allocated = 0;
00277         vlc->table_size = 0;
00278     }
00279 
00280     av_dlog(NULL, "build table nb_codes=%d\n", nb_codes);
00281 
00282     buf = av_malloc((nb_codes+1)*sizeof(VLCcode));
00283 
00284     assert(symbols_size <= 2 || !symbols);
00285     j = 0;
00286 #define COPY(condition)\
00287     for (i = 0; i < nb_codes; i++) {\
00288         GET_DATA(buf[j].bits, bits, i, bits_wrap, bits_size);\
00289         if (!(condition))\
00290             continue;\
00291         GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size);\
00292         if (flags & INIT_VLC_LE)\
00293             buf[j].code = bitswap_32(buf[j].code);\
00294         else\
00295             buf[j].code <<= 32 - buf[j].bits;\
00296         if (symbols)\
00297             GET_DATA(buf[j].symbol, symbols, i, symbols_wrap, symbols_size)\
00298         else\
00299             buf[j].symbol = i;\
00300         j++;\
00301     }
00302     COPY(buf[j].bits > nb_bits);
00303     // qsort is the slowest part of init_vlc, and could probably be improved or avoided
00304     qsort(buf, j, sizeof(VLCcode), compare_vlcspec);
00305     COPY(buf[j].bits && buf[j].bits <= nb_bits);
00306     nb_codes = j;
00307 
00308     ret = build_table(vlc, nb_bits, nb_codes, buf, flags);
00309 
00310     av_free(buf);
00311     if (ret < 0) {
00312         av_freep(&vlc->table);
00313         return -1;
00314     }
00315     if((flags & INIT_VLC_USE_NEW_STATIC) && vlc->table_size != vlc->table_allocated)
00316         av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);
00317     return 0;
00318 }
00319 
00320 
00321 void free_vlc(VLC *vlc)
00322 {
00323     av_freep(&vlc->table);
00324 }
00325 
Generated on Sun Apr 22 2012 21:53:59 for Libav by doxygen 1.7.1