1/* 2 * Common bit i/o utils 3 * Copyright (c) 2000, 2001 Fabrice Bellard 4 * Copyright (c) 2002-2004 Michael Niedermayer <michaelni@gmx.at> 5 * 6 * alternative bitstream reader & writer by Michael Niedermayer <michaelni@gmx.at> 7 * 8 * This file is part of FFmpeg. 9 * 10 * FFmpeg is free software; you can redistribute it and/or 11 * modify it under the terms of the GNU Lesser General Public 12 * License as published by the Free Software Foundation; either 13 * version 2.1 of the License, or (at your option) any later version. 14 * 15 * FFmpeg is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 18 * Lesser General Public License for more details. 19 * 20 * You should have received a copy of the GNU Lesser General Public 21 * License along with FFmpeg; if not, write to the Free Software 22 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 23 */ 24 25/** 26 * @file libavcodec/bitstream.c 27 * bitstream api. 28 */ 29 30#include "avcodec.h" 31#include "bitstream.h" 32 33const uint8_t ff_log2_run[32]={ 34 0, 0, 0, 0, 1, 1, 1, 1, 35 2, 2, 2, 2, 3, 3, 3, 3, 36 4, 4, 5, 5, 6, 6, 7, 7, 37 8, 9,10,11,12,13,14,15 38}; 39 40/** 41 * Same as av_mallocz_static(), but does a realloc. 42 * 43 * @param[in] ptr The block of memory to reallocate. 44 * @param[in] size The requested size. 45 * @return Block of memory of requested size. 46 * @deprecated. Code which uses ff_realloc_static is broken/misdesigned 47 * and should correctly use static arrays 48 */ 49attribute_deprecated av_alloc_size(2) 50static void *ff_realloc_static(void *ptr, unsigned int size); 51 52static void *ff_realloc_static(void *ptr, unsigned int size) 53{ 54 return av_realloc(ptr, size); 55} 56 57void align_put_bits(PutBitContext *s) 58{ 59#ifdef ALT_BITSTREAM_WRITER 60 put_bits(s,( - s->index) & 7,0); 61#else 62 put_bits(s,s->bit_left & 7,0); 63#endif 64} 65 66void ff_put_string(PutBitContext * pbc, const char *s, int put_zero) 67{ 68 while(*s){ 69 put_bits(pbc, 8, *s); 70 s++; 71 } 72 if(put_zero) 73 put_bits(pbc, 8, 0); 74} 75 76void ff_copy_bits(PutBitContext *pb, const uint8_t *src, int length) 77{ 78 const uint16_t *srcw= (const uint16_t*)src; 79 int words= length>>4; 80 int bits= length&15; 81 int i; 82 83 if(length==0) return; 84 85 if(CONFIG_SMALL || words < 16 || put_bits_count(pb)&7){ 86 for(i=0; i<words; i++) put_bits(pb, 16, be2me_16(srcw[i])); 87 }else{ 88 for(i=0; put_bits_count(pb)&31; i++) 89 put_bits(pb, 8, src[i]); 90 flush_put_bits(pb); 91 memcpy(pbBufPtr(pb), src+i, 2*words-i); 92 skip_put_bytes(pb, 2*words-i); 93 } 94 95 put_bits(pb, bits, be2me_16(srcw[words])>>(16-bits)); 96} 97 98/* VLC decoding */ 99 100//#define DEBUG_VLC 101 102#define GET_DATA(v, table, i, wrap, size) \ 103{\ 104 const uint8_t *ptr = (const uint8_t *)table + i * wrap;\ 105 switch(size) {\ 106 case 1:\ 107 v = *(const uint8_t *)ptr;\ 108 break;\ 109 case 2:\ 110 v = *(const uint16_t *)ptr;\ 111 break;\ 112 default:\ 113 v = *(const uint32_t *)ptr;\ 114 break;\ 115 }\ 116} 117 118 119static int alloc_table(VLC *vlc, int size, int use_static) 120{ 121 int index; 122 index = vlc->table_size; 123 vlc->table_size += size; 124 if (vlc->table_size > vlc->table_allocated) { 125 if(use_static>1) 126 abort(); //cant do anything, init_vlc() is used with too little memory 127 vlc->table_allocated += (1 << vlc->bits); 128 if(use_static) 129 vlc->table = ff_realloc_static(vlc->table, 130 sizeof(VLC_TYPE) * 2 * vlc->table_allocated); 131 else 132 vlc->table = av_realloc(vlc->table, 133 sizeof(VLC_TYPE) * 2 * vlc->table_allocated); 134 if (!vlc->table) 135 return -1; 136 } 137 return index; 138} 139 140static int build_table(VLC *vlc, int table_nb_bits, 141 int nb_codes, 142 const void *bits, int bits_wrap, int bits_size, 143 const void *codes, int codes_wrap, int codes_size, 144 const void *symbols, int symbols_wrap, int symbols_size, 145 uint32_t code_prefix, int n_prefix, int flags) 146{ 147 int i, j, k, n, table_size, table_index, nb, n1, index, code_prefix2, symbol; 148 uint32_t code; 149 VLC_TYPE (*table)[2]; 150 151 table_size = 1 << table_nb_bits; 152 table_index = alloc_table(vlc, table_size, flags & (INIT_VLC_USE_STATIC|INIT_VLC_USE_NEW_STATIC)); 153#ifdef DEBUG_VLC 154 av_log(NULL,AV_LOG_DEBUG,"new table index=%d size=%d code_prefix=%x n=%d\n", 155 table_index, table_size, code_prefix, n_prefix); 156#endif 157 if (table_index < 0) 158 return -1; 159 table = &vlc->table[table_index]; 160 161 for(i=0;i<table_size;i++) { 162 table[i][1] = 0; //bits 163 table[i][0] = -1; //codes 164 } 165 166 /* first pass: map codes and compute auxillary table sizes */ 167 for(i=0;i<nb_codes;i++) { 168 GET_DATA(n, bits, i, bits_wrap, bits_size); 169 GET_DATA(code, codes, i, codes_wrap, codes_size); 170 /* we accept tables with holes */ 171 if (n <= 0) 172 continue; 173 if (!symbols) 174 symbol = i; 175 else 176 GET_DATA(symbol, symbols, i, symbols_wrap, symbols_size); 177#if defined(DEBUG_VLC) && 0 178 av_log(NULL,AV_LOG_DEBUG,"i=%d n=%d code=0x%x\n", i, n, code); 179#endif 180 /* if code matches the prefix, it is in the table */ 181 n -= n_prefix; 182 if(flags & INIT_VLC_LE) 183 code_prefix2= code & (n_prefix>=32 ? 0xffffffff : (1 << n_prefix)-1); 184 else 185 code_prefix2= code >> n; 186 if (n > 0 && code_prefix2 == code_prefix) { 187 if (n <= table_nb_bits) { 188 /* no need to add another table */ 189 j = (code << (table_nb_bits - n)) & (table_size - 1); 190 nb = 1 << (table_nb_bits - n); 191 for(k=0;k<nb;k++) { 192 if(flags & INIT_VLC_LE) 193 j = (code >> n_prefix) + (k<<n); 194#ifdef DEBUG_VLC 195 av_log(NULL, AV_LOG_DEBUG, "%4x: code=%d n=%d\n", 196 j, i, n); 197#endif 198 if (table[j][1] /*bits*/ != 0) { 199 av_log(NULL, AV_LOG_ERROR, "incorrect codes\n"); 200 return -1; 201 } 202 table[j][1] = n; //bits 203 table[j][0] = symbol; 204 j++; 205 } 206 } else { 207 n -= table_nb_bits; 208 j = (code >> ((flags & INIT_VLC_LE) ? n_prefix : n)) & ((1 << table_nb_bits) - 1); 209#ifdef DEBUG_VLC 210 av_log(NULL,AV_LOG_DEBUG,"%4x: n=%d (subtable)\n", 211 j, n); 212#endif 213 /* compute table size */ 214 n1 = -table[j][1]; //bits 215 if (n > n1) 216 n1 = n; 217 table[j][1] = -n1; //bits 218 } 219 } 220 } 221 222 /* second pass : fill auxillary tables recursively */ 223 for(i=0;i<table_size;i++) { 224 n = table[i][1]; //bits 225 if (n < 0) { 226 n = -n; 227 if (n > table_nb_bits) { 228 n = table_nb_bits; 229 table[i][1] = -n; //bits 230 } 231 index = build_table(vlc, n, nb_codes, 232 bits, bits_wrap, bits_size, 233 codes, codes_wrap, codes_size, 234 symbols, symbols_wrap, symbols_size, 235 (flags & INIT_VLC_LE) ? (code_prefix | (i << n_prefix)) : ((code_prefix << table_nb_bits) | i), 236 n_prefix + table_nb_bits, flags); 237 if (index < 0) 238 return -1; 239 /* note: realloc has been done, so reload tables */ 240 table = &vlc->table[table_index]; 241 table[i][0] = index; //code 242 } 243 } 244 return table_index; 245} 246 247 248/* Build VLC decoding tables suitable for use with get_vlc(). 249 250 'nb_bits' set thee decoding table size (2^nb_bits) entries. The 251 bigger it is, the faster is the decoding. But it should not be too 252 big to save memory and L1 cache. '9' is a good compromise. 253 254 'nb_codes' : number of vlcs codes 255 256 'bits' : table which gives the size (in bits) of each vlc code. 257 258 'codes' : table which gives the bit pattern of of each vlc code. 259 260 'symbols' : table which gives the values to be returned from get_vlc(). 261 262 'xxx_wrap' : give the number of bytes between each entry of the 263 'bits' or 'codes' tables. 264 265 'xxx_size' : gives the number of bytes of each entry of the 'bits' 266 or 'codes' tables. 267 268 'wrap' and 'size' allows to use any memory configuration and types 269 (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables. 270 271 'use_static' should be set to 1 for tables, which should be freed 272 with av_free_static(), 0 if free_vlc() will be used. 273*/ 274int init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes, 275 const void *bits, int bits_wrap, int bits_size, 276 const void *codes, int codes_wrap, int codes_size, 277 const void *symbols, int symbols_wrap, int symbols_size, 278 int flags) 279{ 280 vlc->bits = nb_bits; 281 if(flags & INIT_VLC_USE_NEW_STATIC){ 282 if(vlc->table_size && vlc->table_size == vlc->table_allocated){ 283 return 0; 284 }else if(vlc->table_size){ 285 abort(); // fatal error, we are called on a partially initialized table 286 } 287 }else if(!(flags & INIT_VLC_USE_STATIC)) { 288 vlc->table = NULL; 289 vlc->table_allocated = 0; 290 vlc->table_size = 0; 291 } else { 292 /* Static tables are initially always NULL, return 293 if vlc->table != NULL to avoid double allocation */ 294 if(vlc->table) 295 return 0; 296 } 297 298#ifdef DEBUG_VLC 299 av_log(NULL,AV_LOG_DEBUG,"build table nb_codes=%d\n", nb_codes); 300#endif 301 302 if (build_table(vlc, nb_bits, nb_codes, 303 bits, bits_wrap, bits_size, 304 codes, codes_wrap, codes_size, 305 symbols, symbols_wrap, symbols_size, 306 0, 0, flags) < 0) { 307 av_freep(&vlc->table); 308 return -1; 309 } 310 if((flags & INIT_VLC_USE_NEW_STATIC) && vlc->table_size != vlc->table_allocated) 311 av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated); 312 return 0; 313} 314 315 316void free_vlc(VLC *vlc) 317{ 318 av_freep(&vlc->table); 319} 320 321