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