• Main Page
  • Related Pages
  • Modules
  • Data Structures
  • Files
  • 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 FFmpeg.
00010  *
00011  * FFmpeg 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  * FFmpeg 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 FFmpeg; 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[32]={
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 };
00041 
00042 void align_put_bits(PutBitContext *s)
00043 {
00044 #ifdef ALT_BITSTREAM_WRITER
00045     put_bits(s,(  - s->index) & 7,0);
00046 #else
00047     put_bits(s,s->bit_left & 7,0);
00048 #endif
00049 }
00050 
00051 void ff_put_string(PutBitContext *pb, const char *string, int terminate_string)
00052 {
00053     while(*string){
00054         put_bits(pb, 8, *string);
00055         string++;
00056     }
00057     if(terminate_string)
00058         put_bits(pb, 8, 0);
00059 }
00060 
00061 void ff_copy_bits(PutBitContext *pb, const uint8_t *src, int length)
00062 {
00063     int words= length>>4;
00064     int bits= length&15;
00065     int i;
00066 
00067     if(length==0) return;
00068 
00069     if(CONFIG_SMALL || words < 16 || put_bits_count(pb)&7){
00070         for(i=0; i<words; i++) put_bits(pb, 16, AV_RB16(src + 2*i));
00071     }else{
00072         for(i=0; put_bits_count(pb)&31; i++)
00073             put_bits(pb, 8, src[i]);
00074         flush_put_bits(pb);
00075         memcpy(put_bits_ptr(pb), src+i, 2*words-i);
00076         skip_put_bytes(pb, 2*words-i);
00077     }
00078 
00079     put_bits(pb, bits, AV_RB16(src + 2*words)>>(16-bits));
00080 }
00081 
00082 /* VLC decoding */
00083 
00084 //#define DEBUG_VLC
00085 
00086 #define GET_DATA(v, table, i, wrap, size) \
00087 {\
00088     const uint8_t *ptr = (const uint8_t *)table + i * wrap;\
00089     switch(size) {\
00090     case 1:\
00091         v = *(const uint8_t *)ptr;\
00092         break;\
00093     case 2:\
00094         v = *(const uint16_t *)ptr;\
00095         break;\
00096     default:\
00097         v = *(const uint32_t *)ptr;\
00098         break;\
00099     }\
00100 }
00101 
00102 
00103 static int alloc_table(VLC *vlc, int size, int use_static)
00104 {
00105     int index;
00106     index = vlc->table_size;
00107     vlc->table_size += size;
00108     if (vlc->table_size > vlc->table_allocated) {
00109         if(use_static)
00110             abort(); //cant do anything, init_vlc() is used with too little memory
00111         vlc->table_allocated += (1 << vlc->bits);
00112         vlc->table = av_realloc(vlc->table,
00113                                 sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
00114         if (!vlc->table)
00115             return -1;
00116     }
00117     return index;
00118 }
00119 
00120 static av_always_inline uint32_t bitswap_32(uint32_t x) {
00121     return av_reverse[x&0xFF]<<24
00122          | av_reverse[(x>>8)&0xFF]<<16
00123          | av_reverse[(x>>16)&0xFF]<<8
00124          | av_reverse[x>>24];
00125 }
00126 
00127 typedef struct {
00128     uint8_t bits;
00129     uint16_t symbol;
00132     uint32_t code;
00133 } VLCcode;
00134 
00135 static int compare_vlcspec(const void *a, const void *b)
00136 {
00137     const VLCcode *sa=a, *sb=b;
00138     return (sa->code >> 1) - (sb->code >> 1);
00139 }
00140 
00155 static int build_table(VLC *vlc, int table_nb_bits, int nb_codes,
00156                        VLCcode *codes, int flags)
00157 {
00158     int table_size, table_index, index, code_prefix, symbol, subtable_bits;
00159     int i, j, k, n, nb, inc;
00160     uint32_t code;
00161     VLC_TYPE (*table)[2];
00162 
00163     table_size = 1 << table_nb_bits;
00164     table_index = alloc_table(vlc, table_size, flags & INIT_VLC_USE_NEW_STATIC);
00165 #ifdef DEBUG_VLC
00166     av_log(NULL,AV_LOG_DEBUG,"new table index=%d size=%d\n",
00167            table_index, table_size);
00168 #endif
00169     if (table_index < 0)
00170         return -1;
00171     table = &vlc->table[table_index];
00172 
00173     for (i = 0; i < table_size; i++) {
00174         table[i][1] = 0; //bits
00175         table[i][0] = -1; //codes
00176     }
00177 
00178     /* first pass: map codes and compute auxillary table sizes */
00179     for (i = 0; i < nb_codes; i++) {
00180         n = codes[i].bits;
00181         code = codes[i].code;
00182         symbol = codes[i].symbol;
00183 #if defined(DEBUG_VLC) && 0
00184         av_log(NULL,AV_LOG_DEBUG,"i=%d n=%d code=0x%x\n", i, n, code);
00185 #endif
00186         if (n <= table_nb_bits) {
00187             /* no need to add another table */
00188             j = code >> (32 - table_nb_bits);
00189             nb = 1 << (table_nb_bits - n);
00190             inc = 1;
00191             if (flags & INIT_VLC_LE) {
00192                 j = bitswap_32(code);
00193                 inc = 1 << n;
00194             }
00195             for (k = 0; k < nb; k++) {
00196 #ifdef DEBUG_VLC
00197                 av_log(NULL, AV_LOG_DEBUG, "%4x: code=%d n=%d\n",
00198                        j, i, n);
00199 #endif
00200                 if (table[j][1] /*bits*/ != 0) {
00201                     av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
00202                     return -1;
00203                 }
00204                 table[j][1] = n; //bits
00205                 table[j][0] = symbol;
00206                 j += inc;
00207             }
00208         } else {
00209             /* fill auxiliary table recursively */
00210             n -= table_nb_bits;
00211             code_prefix = code >> (32 - table_nb_bits);
00212             subtable_bits = n;
00213             codes[i].bits = n;
00214             codes[i].code = code << table_nb_bits;
00215             for (k = i+1; k < nb_codes; k++) {
00216                 n = codes[k].bits - table_nb_bits;
00217                 if (n <= 0)
00218                     break;
00219                 code = codes[k].code;
00220                 if (code >> (32 - table_nb_bits) != code_prefix)
00221                     break;
00222                 codes[k].bits = n;
00223                 codes[k].code = code << table_nb_bits;
00224                 subtable_bits = FFMAX(subtable_bits, n);
00225             }
00226             subtable_bits = FFMIN(subtable_bits, table_nb_bits);
00227             j = (flags & INIT_VLC_LE) ? bitswap_32(code_prefix) >> (32 - table_nb_bits) : code_prefix;
00228             table[j][1] = -subtable_bits;
00229 #ifdef DEBUG_VLC
00230             av_log(NULL,AV_LOG_DEBUG,"%4x: n=%d (subtable)\n",
00231                    j, codes[i].bits + table_nb_bits);
00232 #endif
00233             index = build_table(vlc, subtable_bits, k-i, codes+i, flags);
00234             if (index < 0)
00235                 return -1;
00236             /* note: realloc has been done, so reload tables */
00237             table = &vlc->table[table_index];
00238             table[j][0] = index; //code
00239             i = k-1;
00240         }
00241     }
00242     return table_index;
00243 }
00244 
00245 
00246 /* Build VLC decoding tables suitable for use with get_vlc().
00247 
00248    'nb_bits' set thee decoding table size (2^nb_bits) entries. The
00249    bigger it is, the faster is the decoding. But it should not be too
00250    big to save memory and L1 cache. '9' is a good compromise.
00251 
00252    'nb_codes' : number of vlcs codes
00253 
00254    'bits' : table which gives the size (in bits) of each vlc code.
00255 
00256    'codes' : table which gives the bit pattern of of each vlc code.
00257 
00258    'symbols' : table which gives the values to be returned from get_vlc().
00259 
00260    'xxx_wrap' : give the number of bytes between each entry of the
00261    'bits' or 'codes' tables.
00262 
00263    'xxx_size' : gives the number of bytes of each entry of the 'bits'
00264    or 'codes' tables.
00265 
00266    'wrap' and 'size' allows to use any memory configuration and types
00267    (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
00268 
00269    'use_static' should be set to 1 for tables, which should be freed
00270    with av_free_static(), 0 if free_vlc() will be used.
00271 */
00272 int init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes,
00273              const void *bits, int bits_wrap, int bits_size,
00274              const void *codes, int codes_wrap, int codes_size,
00275              const void *symbols, int symbols_wrap, int symbols_size,
00276              int flags)
00277 {
00278     VLCcode buf[nb_codes];
00279     int i, j;
00280 
00281     vlc->bits = nb_bits;
00282     if(flags & INIT_VLC_USE_NEW_STATIC){
00283         if(vlc->table_size && vlc->table_size == vlc->table_allocated){
00284             return 0;
00285         }else if(vlc->table_size){
00286             abort(); // fatal error, we are called on a partially initialized table
00287         }
00288     }else {
00289         vlc->table = NULL;
00290         vlc->table_allocated = 0;
00291         vlc->table_size = 0;
00292     }
00293 
00294 #ifdef DEBUG_VLC
00295     av_log(NULL,AV_LOG_DEBUG,"build table nb_codes=%d\n", nb_codes);
00296 #endif
00297 
00298     assert(symbols_size <= 2 || !symbols);
00299     j = 0;
00300 #define COPY(condition)\
00301     for (i = 0; i < nb_codes; i++) {\
00302         GET_DATA(buf[j].bits, bits, i, bits_wrap, bits_size);\
00303         if (!(condition))\
00304             continue;\
00305         GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size);\
00306         if (flags & INIT_VLC_LE)\
00307             buf[j].code = bitswap_32(buf[j].code);\
00308         else\
00309             buf[j].code <<= 32 - buf[j].bits;\
00310         if (symbols)\
00311             GET_DATA(buf[j].symbol, symbols, i, symbols_wrap, symbols_size)\
00312         else\
00313             buf[j].symbol = i;\
00314         j++;\
00315     }
00316     COPY(buf[j].bits > nb_bits);
00317     // qsort is the slowest part of init_vlc, and could probably be improved or avoided
00318     qsort(buf, j, sizeof(VLCcode), compare_vlcspec);
00319     COPY(buf[j].bits && buf[j].bits <= nb_bits);
00320     nb_codes = j;
00321 
00322     if (build_table(vlc, nb_bits, nb_codes, buf, flags) < 0) {
00323         av_freep(&vlc->table);
00324         return -1;
00325     }
00326     if((flags & INIT_VLC_USE_NEW_STATIC) && vlc->table_size != vlc->table_allocated)
00327         av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);
00328     return 0;
00329 }
00330 
00331 
00332 void free_vlc(VLC *vlc)
00333 {
00334     av_freep(&vlc->table);
00335 }
00336 

Generated on Fri Sep 16 2011 17:17:34 for FFmpeg by  doxygen 1.7.1