• 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  *
00006  * alternative bitstream reader & writer by Michael Niedermayer <michaelni@gmx.at>
00007  *
00008  * This file is part of FFmpeg.
00009  *
00010  * FFmpeg is free software; you can redistribute it and/or
00011  * modify it under the terms of the GNU Lesser General Public
00012  * License as published by the Free Software Foundation; either
00013  * version 2.1 of the License, or (at your option) any later version.
00014  *
00015  * FFmpeg is distributed in the hope that it will be useful,
00016  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018  * Lesser General Public License for more details.
00019  *
00020  * You should have received a copy of the GNU Lesser General Public
00021  * License along with FFmpeg; if not, write to the Free Software
00022  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
00023  */
00024 
00030 #include "avcodec.h"
00031 #include "bitstream.h"
00032 
00033 const uint8_t ff_log2_run[32]={
00034  0, 0, 0, 0, 1, 1, 1, 1,
00035  2, 2, 2, 2, 3, 3, 3, 3,
00036  4, 4, 5, 5, 6, 6, 7, 7,
00037  8, 9,10,11,12,13,14,15
00038 };
00039 
00049 attribute_deprecated av_alloc_size(2)
00050 static void *ff_realloc_static(void *ptr, unsigned int size);
00051 
00052 static void *ff_realloc_static(void *ptr, unsigned int size)
00053 {
00054     return av_realloc(ptr, size);
00055 }
00056 
00057 void align_put_bits(PutBitContext *s)
00058 {
00059 #ifdef ALT_BITSTREAM_WRITER
00060     put_bits(s,(  - s->index) & 7,0);
00061 #else
00062     put_bits(s,s->bit_left & 7,0);
00063 #endif
00064 }
00065 
00066 void ff_put_string(PutBitContext * pbc, const char *s, int put_zero)
00067 {
00068     while(*s){
00069         put_bits(pbc, 8, *s);
00070         s++;
00071     }
00072     if(put_zero)
00073         put_bits(pbc, 8, 0);
00074 }
00075 
00076 void ff_copy_bits(PutBitContext *pb, const uint8_t *src, int length)
00077 {
00078     const uint16_t *srcw= (const uint16_t*)src;
00079     int words= length>>4;
00080     int bits= length&15;
00081     int i;
00082 
00083     if(length==0) return;
00084 
00085     if(CONFIG_SMALL || words < 16 || put_bits_count(pb)&7){
00086         for(i=0; i<words; i++) put_bits(pb, 16, be2me_16(srcw[i]));
00087     }else{
00088         for(i=0; put_bits_count(pb)&31; i++)
00089             put_bits(pb, 8, src[i]);
00090         flush_put_bits(pb);
00091         memcpy(pbBufPtr(pb), src+i, 2*words-i);
00092         skip_put_bytes(pb, 2*words-i);
00093     }
00094 
00095     put_bits(pb, bits, be2me_16(srcw[words])>>(16-bits));
00096 }
00097 
00098 /* VLC decoding */
00099 
00100 //#define DEBUG_VLC
00101 
00102 #define GET_DATA(v, table, i, wrap, size) \
00103 {\
00104     const uint8_t *ptr = (const uint8_t *)table + i * wrap;\
00105     switch(size) {\
00106     case 1:\
00107         v = *(const uint8_t *)ptr;\
00108         break;\
00109     case 2:\
00110         v = *(const uint16_t *)ptr;\
00111         break;\
00112     default:\
00113         v = *(const uint32_t *)ptr;\
00114         break;\
00115     }\
00116 }
00117 
00118 
00119 static int alloc_table(VLC *vlc, int size, int use_static)
00120 {
00121     int index;
00122     index = vlc->table_size;
00123     vlc->table_size += size;
00124     if (vlc->table_size > vlc->table_allocated) {
00125         if(use_static>1)
00126             abort(); //cant do anything, init_vlc() is used with too little memory
00127         vlc->table_allocated += (1 << vlc->bits);
00128         if(use_static)
00129             vlc->table = ff_realloc_static(vlc->table,
00130                                            sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
00131         else
00132             vlc->table = av_realloc(vlc->table,
00133                                     sizeof(VLC_TYPE) * 2 * vlc->table_allocated);
00134         if (!vlc->table)
00135             return -1;
00136     }
00137     return index;
00138 }
00139 
00140 static int build_table(VLC *vlc, int table_nb_bits,
00141                        int nb_codes,
00142                        const void *bits, int bits_wrap, int bits_size,
00143                        const void *codes, int codes_wrap, int codes_size,
00144                        const void *symbols, int symbols_wrap, int symbols_size,
00145                        uint32_t code_prefix, int n_prefix, int flags)
00146 {
00147     int i, j, k, n, table_size, table_index, nb, n1, index, code_prefix2, symbol;
00148     uint32_t code;
00149     VLC_TYPE (*table)[2];
00150 
00151     table_size = 1 << table_nb_bits;
00152     table_index = alloc_table(vlc, table_size, flags & (INIT_VLC_USE_STATIC|INIT_VLC_USE_NEW_STATIC));
00153 #ifdef DEBUG_VLC
00154     av_log(NULL,AV_LOG_DEBUG,"new table index=%d size=%d code_prefix=%x n=%d\n",
00155            table_index, table_size, code_prefix, n_prefix);
00156 #endif
00157     if (table_index < 0)
00158         return -1;
00159     table = &vlc->table[table_index];
00160 
00161     for(i=0;i<table_size;i++) {
00162         table[i][1] = 0; //bits
00163         table[i][0] = -1; //codes
00164     }
00165 
00166     /* first pass: map codes and compute auxillary table sizes */
00167     for(i=0;i<nb_codes;i++) {
00168         GET_DATA(n, bits, i, bits_wrap, bits_size);
00169         GET_DATA(code, codes, i, codes_wrap, codes_size);
00170         /* we accept tables with holes */
00171         if (n <= 0)
00172             continue;
00173         if (!symbols)
00174             symbol = i;
00175         else
00176             GET_DATA(symbol, symbols, i, symbols_wrap, symbols_size);
00177 #if defined(DEBUG_VLC) && 0
00178         av_log(NULL,AV_LOG_DEBUG,"i=%d n=%d code=0x%x\n", i, n, code);
00179 #endif
00180         /* if code matches the prefix, it is in the table */
00181         n -= n_prefix;
00182         if(flags & INIT_VLC_LE)
00183             code_prefix2= code & (n_prefix>=32 ? 0xffffffff : (1 << n_prefix)-1);
00184         else
00185             code_prefix2= code >> n;
00186         if (n > 0 && code_prefix2 == code_prefix) {
00187             if (n <= table_nb_bits) {
00188                 /* no need to add another table */
00189                 j = (code << (table_nb_bits - n)) & (table_size - 1);
00190                 nb = 1 << (table_nb_bits - n);
00191                 for(k=0;k<nb;k++) {
00192                     if(flags & INIT_VLC_LE)
00193                         j = (code >> n_prefix) + (k<<n);
00194 #ifdef DEBUG_VLC
00195                     av_log(NULL, AV_LOG_DEBUG, "%4x: code=%d n=%d\n",
00196                            j, i, n);
00197 #endif
00198                     if (table[j][1] /*bits*/ != 0) {
00199                         av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");
00200                         return -1;
00201                     }
00202                     table[j][1] = n; //bits
00203                     table[j][0] = symbol;
00204                     j++;
00205                 }
00206             } else {
00207                 n -= table_nb_bits;
00208                 j = (code >> ((flags & INIT_VLC_LE) ? n_prefix : n)) & ((1 << table_nb_bits) - 1);
00209 #ifdef DEBUG_VLC
00210                 av_log(NULL,AV_LOG_DEBUG,"%4x: n=%d (subtable)\n",
00211                        j, n);
00212 #endif
00213                 /* compute table size */
00214                 n1 = -table[j][1]; //bits
00215                 if (n > n1)
00216                     n1 = n;
00217                 table[j][1] = -n1; //bits
00218             }
00219         }
00220     }
00221 
00222     /* second pass : fill auxillary tables recursively */
00223     for(i=0;i<table_size;i++) {
00224         n = table[i][1]; //bits
00225         if (n < 0) {
00226             n = -n;
00227             if (n > table_nb_bits) {
00228                 n = table_nb_bits;
00229                 table[i][1] = -n; //bits
00230             }
00231             index = build_table(vlc, n, nb_codes,
00232                                 bits, bits_wrap, bits_size,
00233                                 codes, codes_wrap, codes_size,
00234                                 symbols, symbols_wrap, symbols_size,
00235                                 (flags & INIT_VLC_LE) ? (code_prefix | (i << n_prefix)) : ((code_prefix << table_nb_bits) | i),
00236                                 n_prefix + table_nb_bits, flags);
00237             if (index < 0)
00238                 return -1;
00239             /* note: realloc has been done, so reload tables */
00240             table = &vlc->table[table_index];
00241             table[i][0] = index; //code
00242         }
00243     }
00244     return table_index;
00245 }
00246 
00247 
00248 /* Build VLC decoding tables suitable for use with get_vlc().
00249 
00250    'nb_bits' set thee decoding table size (2^nb_bits) entries. The
00251    bigger it is, the faster is the decoding. But it should not be too
00252    big to save memory and L1 cache. '9' is a good compromise.
00253 
00254    'nb_codes' : number of vlcs codes
00255 
00256    'bits' : table which gives the size (in bits) of each vlc code.
00257 
00258    'codes' : table which gives the bit pattern of of each vlc code.
00259 
00260    'symbols' : table which gives the values to be returned from get_vlc().
00261 
00262    'xxx_wrap' : give the number of bytes between each entry of the
00263    'bits' or 'codes' tables.
00264 
00265    'xxx_size' : gives the number of bytes of each entry of the 'bits'
00266    or 'codes' tables.
00267 
00268    'wrap' and 'size' allows to use any memory configuration and types
00269    (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.
00270 
00271    'use_static' should be set to 1 for tables, which should be freed
00272    with av_free_static(), 0 if free_vlc() will be used.
00273 */
00274 int init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes,
00275              const void *bits, int bits_wrap, int bits_size,
00276              const void *codes, int codes_wrap, int codes_size,
00277              const void *symbols, int symbols_wrap, int symbols_size,
00278              int flags)
00279 {
00280     vlc->bits = nb_bits;
00281     if(flags & INIT_VLC_USE_NEW_STATIC){
00282         if(vlc->table_size && vlc->table_size == vlc->table_allocated){
00283             return 0;
00284         }else if(vlc->table_size){
00285             abort(); // fatal error, we are called on a partially initialized table
00286         }
00287     }else if(!(flags & INIT_VLC_USE_STATIC)) {
00288         vlc->table = NULL;
00289         vlc->table_allocated = 0;
00290         vlc->table_size = 0;
00291     } else {
00292         /* Static tables are initially always NULL, return
00293            if vlc->table != NULL to avoid double allocation */
00294         if(vlc->table)
00295             return 0;
00296     }
00297 
00298 #ifdef DEBUG_VLC
00299     av_log(NULL,AV_LOG_DEBUG,"build table nb_codes=%d\n", nb_codes);
00300 #endif
00301 
00302     if (build_table(vlc, nb_bits, nb_codes,
00303                     bits, bits_wrap, bits_size,
00304                     codes, codes_wrap, codes_size,
00305                     symbols, symbols_wrap, symbols_size,
00306                     0, 0, flags) < 0) {
00307         av_freep(&vlc->table);
00308         return -1;
00309     }
00310     if((flags & INIT_VLC_USE_NEW_STATIC) && vlc->table_size != vlc->table_allocated)
00311         av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);
00312     return 0;
00313 }
00314 
00315 
00316 void free_vlc(VLC *vlc)
00317 {
00318     av_freep(&vlc->table);
00319 }
00320 

Generated on Sat Feb 16 2013 09:23:11 for ffmpeg by  doxygen 1.7.1