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

Generated on Wed Apr 11 2012 07:31:32 for FFmpeg by  doxygen 1.7.1