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