Libav
|
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