git.sesse.net Git - ffmpeg/blob - libavcodec/common.c

   1 /*
   2  * Common bit i/o utils
   3  * Copyright (c) 2000, 2001 Gerard Lantau.
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  */
  19 #include <stdlib.h>
  20 #include <stdio.h>
  21 #include <string.h>
  22 #ifdef __FreeBSD__
  23 #include <sys/param.h>
  24 #endif
  25 #include <netinet/in.h>
  26 #include <math.h>
  27 #include "common.h"
  28
  29 #define NDEBUG
  30 #include <assert.h>
  31
  32 void init_put_bits(PutBitContext *s,
  33                    UINT8 *buffer, int buffer_size,
  34                    void *opaque,
  35                    void (*write_data)(void *, UINT8 *, int))
  36 {
  37     s->buf = buffer;
  38     s->buf_ptr = s->buf;
  39     s->buf_end = s->buf + buffer_size;
  40     s->bit_cnt=0;
  41     s->bit_buf=0;
  42     s->data_out_size = 0;
  43     s->write_data = write_data;
  44     s->opaque = opaque;
  45 }
  46
  47 static void flush_buffer(PutBitContext *s)
  48 {
  49     int size;
  50     if (s->write_data) {
  51         size = s->buf_ptr - s->buf;
  52         if (size > 0)
  53             s->write_data(s->opaque, s->buf, size);
  54         s->buf_ptr = s->buf;
  55         s->data_out_size += size;
  56     }
  57 }
  58
  59 void put_bits(PutBitContext *s, int n, unsigned int value)
  60 {
  61     unsigned int bit_buf;
  62     int bit_cnt;
  63
  64 #ifdef STATS
  65     st_out_bit_counts[st_current_index] += n;
  66 #endif
  67     //    printf("put_bits=%d %x\n", n, value);
  68     assert(n == 32 || value < (1U << n));
  69
  70     bit_buf = s->bit_buf;
  71     bit_cnt = s->bit_cnt;
  72
  73     //    printf("n=%d value=%x cnt=%d buf=%x\n", n, value, bit_cnt, bit_buf);
  74     /* XXX: optimize */
  75     if (n < (32-bit_cnt)) {
  76         bit_buf |= value << (32 - n - bit_cnt);
  77         bit_cnt+=n;
  78     } else {
  79         bit_buf |= value >> (n + bit_cnt - 32);
  80         *(UINT32 *)s->buf_ptr = htonl(bit_buf);
  81         //printf("bitbuf = %08x\n", bit_buf);
  82         s->buf_ptr+=4;
  83         if (s->buf_ptr >= s->buf_end)
  84             flush_buffer(s);
  85         bit_cnt=bit_cnt + n - 32;
  86         if (bit_cnt == 0) {
  87             bit_buf = 0;
  88         } else {
  89             bit_buf = value << (32 - bit_cnt);
  90         }
  91     }
  92
  93     s->bit_buf = bit_buf;
  94     s->bit_cnt = bit_cnt;
  95 }
  96
  97 /* return the number of bits output */
  98 long long get_bit_count(PutBitContext *s)
  99 {
 100     return (s->buf_ptr - s->buf + s->data_out_size) * 8 + (long long)s->bit_cnt;
 101 }
 102
 103 void align_put_bits(PutBitContext *s)
 104 {
 105     put_bits(s,(8 - s->bit_cnt) & 7,0);
 106 }
 107
 108 /* pad the end of the output stream with zeros */
 109 void flush_put_bits(PutBitContext *s)
 110 {
 111     while (s->bit_cnt > 0) {
 112         /* XXX: should test end of buffer */
 113         *s->buf_ptr++=s->bit_buf >> 24;
 114         s->bit_buf<<=8;
 115         s->bit_cnt-=8;
 116     }
 117     flush_buffer(s);
 118     s->bit_cnt=0;
 119     s->bit_buf=0;
 120 }
 121
 122 /* for jpeg : espace 0xff with 0x00 after it */
 123 void jput_bits(PutBitContext *s, int n, unsigned int value)
 124 {
 125     unsigned int bit_buf, b;
 126     int bit_cnt, i;
 127
 128     assert(n == 32 || value < (1U << n));
 129
 130     bit_buf = s->bit_buf;
 131     bit_cnt = s->bit_cnt;
 132
 133     //printf("n=%d value=%x cnt=%d buf=%x\n", n, value, bit_cnt, bit_buf);
 134     /* XXX: optimize */
 135     if (n < (32-bit_cnt)) {
 136         bit_buf |= value << (32 - n - bit_cnt);
 137         bit_cnt+=n;
 138     } else {
 139         bit_buf |= value >> (n + bit_cnt - 32);
 140         /* handle escape */
 141         for(i=0;i<4;i++) {
 142             b = (bit_buf >> 24);
 143             *(s->buf_ptr++) = b;
 144             if (b == 0xff)
 145                 *(s->buf_ptr++) = 0;
 146             bit_buf <<= 8;
 147         }
 148         /* we flush the buffer sooner to handle worst case */
 149         if (s->buf_ptr >= (s->buf_end - 8))
 150             flush_buffer(s);
 151
 152         bit_cnt=bit_cnt + n - 32;
 153         if (bit_cnt == 0) {
 154             bit_buf = 0;
 155         } else {
 156             bit_buf = value << (32 - bit_cnt);
 157         }
 158     }
 159
 160     s->bit_buf = bit_buf;
 161     s->bit_cnt = bit_cnt;
 162 }
 163
 164 /* pad the end of the output stream with zeros */
 165 void jflush_put_bits(PutBitContext *s)
 166 {
 167     unsigned int b;
 168
 169     while (s->bit_cnt > 0) {
 170         b = s->bit_buf >> 24;
 171         *s->buf_ptr++ = b;
 172         if (b == 0xff)
 173             *s->buf_ptr++ = 0;
 174         s->bit_buf<<=8;
 175         s->bit_cnt-=8;
 176     }
 177     flush_buffer(s);
 178     s->bit_cnt=0;
 179     s->bit_buf=0;
 180 }
 181
 182 /* bit input functions */
 183
 184 void init_get_bits(GetBitContext *s,
 185                    UINT8 *buffer, int buffer_size)
 186 {
 187     s->buf = buffer;
 188     s->buf_ptr = buffer;
 189     s->buf_end = buffer + buffer_size;
 190     s->bit_cnt = 0;
 191     s->bit_buf = 0;
 192     while (s->buf_ptr < s->buf_end &&
 193            s->bit_cnt < 32) {
 194         s->bit_buf |= (*s->buf_ptr++ << (24 - s->bit_cnt));
 195         s->bit_cnt += 8;
 196     }
 197 }
 198
 199 /* n must be >= 1 and <= 32 */
 200 unsigned int get_bits(GetBitContext *s, int n)
 201 {
 202     unsigned int val;
 203     int bit_cnt;
 204     unsigned int bit_buf;
 205     UINT8 *buf_ptr;
 206
 207 #ifdef STATS
 208     st_bit_counts[st_current_index] += n;
 209 #endif
 210
 211     bit_cnt = s->bit_cnt;
 212     bit_buf = s->bit_buf;
 213
 214     bit_cnt -= n;
 215     if (bit_cnt >= 0) {
 216         /* most common case here */
 217         val = bit_buf >> (32 - n);
 218         bit_buf <<= n;
 219     } else {
 220         val = bit_buf >> (32 - n);
 221         buf_ptr = s->buf_ptr;
 222         buf_ptr += 4;
 223         /* handle common case: we can read everything */
 224         if (buf_ptr <= s->buf_end) {
 225             bit_buf = (buf_ptr[-4] << 24) |
 226                 (buf_ptr[-3] << 16) |
 227                 (buf_ptr[-2] << 8) |
 228                 (buf_ptr[-1]);
 229         } else {
 230             buf_ptr -= 4;
 231             bit_buf = 0;
 232             if (buf_ptr < s->buf_end)
 233                 bit_buf |= *buf_ptr++ << 24;
 234             if (buf_ptr < s->buf_end)
 235                 bit_buf |= *buf_ptr++ << 16;
 236             if (buf_ptr < s->buf_end)
 237                 bit_buf |= *buf_ptr++ << 8;
 238             if (buf_ptr < s->buf_end)
 239                 bit_buf |= *buf_ptr++;
 240         }
 241         s->buf_ptr = buf_ptr;
 242         val |= bit_buf >> (32 + bit_cnt);
 243         bit_buf <<= - bit_cnt;
 244         bit_cnt += 32;
 245     }
 246     s->bit_buf = bit_buf;
 247     s->bit_cnt = bit_cnt;
 248     return val;
 249 }
 250
 251 void align_get_bits(GetBitContext *s)
 252 {
 253     int n;
 254     n = s->bit_cnt & 7;
 255     if (n > 0) {
 256         get_bits(s, n);
 257     }
 258 }
 259
 260 /* VLC decoding */
 261
 262 //#define DEBUG_VLC
 263
 264 #define GET_DATA(v, table, i, wrap, size) \
 265 {\
 266     UINT8 *ptr = (UINT8 *)table + i * wrap;\
 267     switch(size) {\
 268     case 1:\
 269         v = *(UINT8 *)ptr;\
 270         break;\
 271     case 2:\
 272         v = *(UINT16 *)ptr;\
 273         break;\
 274     default:\
 275         v = *(UINT32 *)ptr;\
 276         break;\
 277     }\
 278 }
 279
 280
 281 static int alloc_table(VLC *vlc, int size)
 282 {
 283     int index;
 284     index = vlc->table_size;
 285     vlc->table_size += size;
 286     if (vlc->table_size > vlc->table_allocated) {
 287         vlc->table_allocated += (1 << vlc->bits);
 288         vlc->table_bits = realloc(vlc->table_bits,
 289                                   sizeof(INT8) * vlc->table_allocated);
 290         vlc->table_codes = realloc(vlc->table_codes,
 291                                    sizeof(INT16) * vlc->table_allocated);
 292         if (!vlc->table_bits ||
 293             !vlc->table_codes)
 294             return -1;
 295     }
 296     return index;
 297 }
 298
 299 static int build_table(VLC *vlc, int table_nb_bits,
 300                        int nb_codes,
 301                        const void *bits, int bits_wrap, int bits_size,
 302                        const void *codes, int codes_wrap, int codes_size,
 303                        UINT32 code_prefix, int n_prefix)
 304 {
 305     int i, j, k, n, table_size, table_index, nb, n1, index;
 306     UINT32 code;
 307     INT8 *table_bits;
 308     INT16 *table_codes;
 309
 310     table_size = 1 << table_nb_bits;
 311     table_index = alloc_table(vlc, table_size);
 312 #ifdef DEBUG_VLC
 313     printf("new table index=%d size=%d code_prefix=%x n=%d\n",
 314            table_index, table_size, code_prefix, n_prefix);
 315 #endif
 316     if (table_index < 0)
 317         return -1;
 318     table_bits = &vlc->table_bits[table_index];
 319     table_codes = &vlc->table_codes[table_index];
 320
 321     for(i=0;i<table_size;i++) {
 322         table_bits[i] = 0;
 323         table_codes[i] = -1;
 324     }
 325
 326     /* first pass: map codes and compute auxillary table sizes */
 327     for(i=0;i<nb_codes;i++) {
 328         GET_DATA(n, bits, i, bits_wrap, bits_size);
 329         GET_DATA(code, codes, i, codes_wrap, codes_size);
 330         /* we accept tables with holes */
 331         if (n <= 0)
 332             continue;
 333 #if defined(DEBUG_VLC) && 0
 334         printf("i=%d n=%d code=0x%x\n", i, n, code);
 335 #endif
 336         /* if code matches the prefix, it is in the table */
 337         n -= n_prefix;
 338         if (n > 0 && (code >> n) == code_prefix) {
 339             if (n <= table_nb_bits) {
 340                 /* no need to add another table */
 341                 j = (code << (table_nb_bits - n)) & (table_size - 1);
 342                 nb = 1 << (table_nb_bits - n);
 343                 for(k=0;k<nb;k++) {
 344 #ifdef DEBUG_VLC
 345                     printf("%4x: code=%d n=%d\n",
 346                            j, i, n);
 347 #endif
 348                     if (table_bits[j] != 0) {
 349                         fprintf(stderr, "incorrect codes\n");
 350                         exit(1);
 351                     }
 352                     table_bits[j] = n;
 353                     table_codes[j] = i;
 354                     j++;
 355                 }
 356             } else {
 357                 n -= table_nb_bits;
 358                 j = (code >> n) & ((1 << table_nb_bits) - 1);
 359 #ifdef DEBUG_VLC
 360                 printf("%4x: n=%d (subtable)\n",
 361                        j, n);
 362 #endif
 363                 /* compute table size */
 364                 n1 = -table_bits[j];
 365                 if (n > n1)
 366                     n1 = n;
 367                 table_bits[j] = -n1;
 368             }
 369         }
 370     }
 371
 372     /* second pass : fill auxillary tables recursively */
 373     for(i=0;i<table_size;i++) {
 374         n = table_bits[i];
 375         if (n < 0) {
 376             n = -n;
 377             if (n > table_nb_bits) {
 378                 n = table_nb_bits;
 379                 table_bits[i] = -n;
 380             }
 381             index = build_table(vlc, n, nb_codes,
 382                                 bits, bits_wrap, bits_size,
 383                                 codes, codes_wrap, codes_size,
 384                                 (code_prefix << table_nb_bits) | i,
 385                                 n_prefix + table_nb_bits);
 386             if (index < 0)
 387                 return -1;
 388             /* note: realloc has been done, so reload tables */
 389             table_bits = &vlc->table_bits[table_index];
 390             table_codes = &vlc->table_codes[table_index];
 391             table_codes[i] = index;
 392         }
 393     }
 394     return table_index;
 395 }
 396
 397
 398 /* wrap and size allow to handle most types of storage.  */
 399 int init_vlc(VLC *vlc, int nb_bits, int nb_codes,
 400              const void *bits, int bits_wrap, int bits_size,
 401              const void *codes, int codes_wrap, int codes_size)
 402 {
 403     vlc->bits = nb_bits;
 404     vlc->table_bits = NULL;
 405     vlc->table_codes = NULL;
 406     vlc->table_allocated = 0;
 407     vlc->table_size = 0;
 408 #ifdef DEBUG_VLC
 409     printf("build table nb_codes=%d\n", nb_codes);
 410 #endif
 411
 412     if (build_table(vlc, nb_bits, nb_codes,
 413                     bits, bits_wrap, bits_size,
 414                     codes, codes_wrap, codes_size,
 415                     0, 0) < 0) {
 416         if (vlc->table_bits)
 417             free(vlc->table_bits);
 418         if (vlc->table_codes)
 419             free(vlc->table_codes);
 420         return -1;
 421     }
 422     return 0;
 423 }
 424
 425
 426 void free_vlc(VLC *vlc)
 427 {
 428     free(vlc->table_bits);
 429     free(vlc->table_codes);
 430 }
 431
 432 int get_vlc(GetBitContext *s, VLC *vlc)
 433 {
 434     int bit_cnt, code, n, nb_bits, index;
 435     UINT32 bit_buf;
 436     INT16 *table_codes;
 437     INT8 *table_bits;
 438     UINT8 *buf_ptr;
 439
 440     SAVE_BITS(s);
 441     nb_bits = vlc->bits;
 442     table_codes = vlc->table_codes;
 443     table_bits = vlc->table_bits;
 444     for(;;) {
 445         SHOW_BITS(s, index, nb_bits);
 446         code = table_codes[index];
 447         n = table_bits[index];
 448         if (n > 0) {
 449             /* most common case */
 450             FLUSH_BITS(n);
 451 #ifdef STATS
 452             st_bit_counts[st_current_index] += n;
 453 #endif
 454             break;
 455         } else if (n == 0) {
 456             return -1;
 457         } else {
 458             FLUSH_BITS(nb_bits);
 459 #ifdef STATS
 460             st_bit_counts[st_current_index] += nb_bits;
 461 #endif
 462             nb_bits = -n;
 463             table_codes = vlc->table_codes + code;
 464             table_bits = vlc->table_bits + code;
 465         }
 466     }
 467     RESTORE_BITS(s);
 468     return code;
 469 }