src/bitstream.c

   1 /*
   2  * bit stream routine
   3  *                     (C) 2008/03/09- yoya@awm.jp
   4  */
   5
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8 #include <string.h>
   9 #include "bitstream.h"
  10
  11 static void bitstream_clear(bitstream_t *bs);
  12
  13
  14 #ifdef BITSTREAM_DEBUG /* bitstream debug */
  15
  16 #undef bitstream_open
  17 #undef bitstream_close
  18
  19 #define BITSTREAM_DEBUG_TABLE_NUM 0x40000
  20
  21 static struct bitstream_debug_ {
  22     void *ptr;
  23     char *filename;
  24     int  linenum;
  25 } bitstream_debug_table[BITSTREAM_DEBUG_TABLE_NUM];
  26
  27 static int bitstream_debug_stack = 0;
  28
  29 void
  30 bitstream_debug_start(void) {
  31     int i;
  32     bitstream_debug_stack ++;
  33     if (bitstream_debug_stack > 1) {
  34         fprintf(stderr, "bitstream_debug_start: bitstream_debug_stack=%d\n", bitstream_debug_stack);
  35         return ;
  36     }
  37     for (i=0 ; i < BITSTREAM_DEBUG_TABLE_NUM ; i++) {
  38         bitstream_debug_table[i].ptr = NULL;
  39     }
  40     fprintf(stderr, "bitstream_debug_start: 0/n=0/%d\n", BITSTREAM_DEBUG_TABLE_NUM);
  41 }
  42
  43 void
  44 bitstream_debug_end(void) {
  45     int i, j = 0;
  46     bitstream_debug_stack --;
  47     if (bitstream_debug_stack > 0) {
  48         fprintf(stderr, "bitstream_debug_end: bitstream_debug_stack=%d\n", bitstream_debug_stack);
  49         return ;
  50     }
  51     for (i=0 ; i < BITSTREAM_DEBUG_TABLE_NUM ; i++) {
  52         if (bitstream_debug_table[i].ptr) {
  53             fprintf(stderr, "XXX (%d) ptr=%p (%s, %d)\n",
  54                     i, bitstream_debug_table[i].ptr,
  55                     bitstream_debug_table[i].filename,
  56                     bitstream_debug_table[i].linenum);
  57             j = i + 1;
  58         }
  59     }
  60     fprintf(stderr, "bitstream_debug_end: j/n=%d/%d\n", j, BITSTREAM_DEBUG_TABLE_NUM);
  61 }
  62
  63 bitstream_t *
  64 bitstream_open_debug(char *filename, int linenum) {
  65     int i;
  66     void *ptr;
  67     ptr = bitstream_open();
  68     for (i=0 ; i < BITSTREAM_DEBUG_TABLE_NUM ; i++) {
  69         if (bitstream_debug_table[i].ptr == NULL) {
  70             bitstream_debug_table[i].ptr = ptr;
  71             bitstream_debug_table[i].filename = filename;
  72             bitstream_debug_table[i].linenum = linenum;
  73             break;
  74         }
  75     }
  76     return ptr;
  77 }
  78
  79 void
  80 bitstream_close_debug(bitstream_t * bs,  char *filename, int linenum) {
  81     int i;
  82     void *ptr = bs;
  83 //    fprintf(stderr, "free_debug: ptr=%p (%s,%d)\n", ptr, filename, linenum);
  84     for (i=0 ; i < BITSTREAM_DEBUG_TABLE_NUM ; i++) {
  85         if (bitstream_debug_table[i].ptr == ptr) {
  86             bitstream_debug_table[i].ptr = NULL;
  87             break;
  88         }
  89     }
  90     if (i == BITSTREAM_DEBUG_TABLE_NUM) {
  91         char *p;
  92         fprintf(stderr, "free non-allocated memory: ptr=%p (%s,%d)\n", ptr,
  93                 filename, linenum);
  94         bitstream_debug_end();
  95         p = ptr;
  96         p = 0;
  97     }
  98     bitstream_close(bs);
  99 }
 100
 101 #endif // BITSTREAM_DEBUG
 102
 103 bitstream_t *
 104 bitstream_open(void) {
 105     bitstream_t *bs = (bitstream_t *) calloc(sizeof(*bs), 1);
 106
 107     bs->data = NULL;
 108     bs->data_len = 0;
 109     bs->data_alloc_len = 0;
 110     bs->byte_offset = 0;
 111     bs->bit_offset = 0;
 112     return bs;
 113 }
 114
 115 void
 116 bitstream_close(bitstream_t * bs) {
 117     if (bs->data) {
 118         free(bs->data);
 119         bs->data = NULL;
 120     }
 121     free(bs);
 122     return ;
 123 }
 124
 125 static void
 126 bitstream_clear(bitstream_t *bs) {
 127     if (bs->data) {
 128         free(bs->data);
 129         bs->data = NULL;
 130     }
 131     bs->data_len = 0;
 132     bs->data_alloc_len = 0;
 133     bs->byte_offset = 0;
 134     bs->bit_offset = 0;
 135     return ;
 136 }
 137
 138 int
 139 bitstream_realloc(bitstream_t *bs) {
 140     unsigned char *data;
 141     bs->data_alloc_len *= 2;
 142     if (bs->data_alloc_len < BITSTREAM_DATA_LEN_MIN) {
 143         bs->data_alloc_len = BITSTREAM_DATA_LEN_MIN;
 144     }
 145     data = (unsigned char *) realloc(bs->data, bs->data_alloc_len);
 146     if (! data) {
 147         fprintf(stderr, "bitstream_realloc: Can't realloc memory (%p, %lu)\n",
 148                 bs->data, bs->data_alloc_len);
 149         return 1;
 150     }
 151     bs->data = data;
 152     return 0;
 153 }
 154
 155 int
 156 bitstream_input(bitstream_t *bs, unsigned char *data,
 157                    unsigned long data_len) {
 158     bitstream_clear(bs);
 159     bs->data_alloc_len = data_len;
 160     if (bs->data) {
 161         free(bs->data);
 162     }
 163     bs->data = malloc(bs->data_alloc_len);
 164     if (bs->data == NULL) {
 165         fprintf(stderr, "bitstream_input: malloc failed\n");
 166         bs->data_alloc_len = 0;
 167         bs->data_len = 0;
 168         return 1;
 169     }
 170     memcpy(bs->data, data, data_len);
 171     bs->data_len = data_len;
 172     return 0;
 173 }
 174
 175 unsigned char *
 176 bitstream_steal(bitstream_t *bs, unsigned long *length) {
 177     unsigned char *data, *tmp;
 178     *length = 0;
 179     if (bs == NULL) {
 180         fprintf(stderr, "bitstream_steal: bs == NULL\n");
 181         return NULL;
 182     }
 183     data = bs->data;
 184     *length = bs->data_len;
 185     if ((tmp = realloc(data, *length)) == NULL) {
 186         fprintf(stderr, "bitstream_steal: Can't realloc\n");
 187         return NULL;
 188     }
 189     bs->data = NULL;
 190     bs->data_len = 0;
 191     bs->data_alloc_len = 0;
 192     return tmp;
 193 }
 194
 195 unsigned char *
 196 bitstream_output_sub(bitstream_t *bs, unsigned long offset, unsigned long length) {
 197     unsigned char *data;
 198     if (bs == NULL) {
 199         fprintf(stderr, "bitstream_output_sub: bs == NULL\n");
 200         return NULL;
 201     }
 202     if (bs->data_len < offset + length ) {
 203         fprintf(stderr, "bitstream_output_sub: bs->data_len(%lu) < offset(%lu)+length(%lu)\n",
 204                 bs->data_len, offset, length);
 205         return NULL;
 206     }
 207     data = malloc(length);
 208     if (data == NULL) {
 209         fprintf(stderr, "bitstream_output_sub: Can't malloc\n");
 210         return NULL;
 211     }
 212     memcpy(data, bs->data + offset, length);
 213     return data;
 214 }
 215
 216 /*
 217  * byte stream
 218  */
 219
 220 int
 221 bitstream_putbyte(bitstream_t *bs, int byte) {
 222     bitstream_align(bs);
 223     if (bs->data_len < bs->byte_offset ) {
 224         return 1;
 225     }
 226     if (bs->data_len == bs->byte_offset ) {
 227         if (bs->data_alloc_len <= bs->byte_offset ) {
 228             bitstream_realloc(bs);
 229         }
 230         bs->data_len ++;
 231     }
 232     byte &= 0xff;
 233     bs->data[bs->byte_offset++] = (unsigned char) byte ;
 234     return 0;
 235 }
 236
 237 int
 238 bitstream_getbyte(bitstream_t *bs) {
 239     bitstream_align(bs);
 240     if (bs->data_len <= bs->byte_offset) {
 241         return -1; /* End of Stream */
 242     }
 243     return bs->data[bs->byte_offset++] & 0xff;
 244 }
 245
 246 int
 247 bitstream_putstring(bitstream_t *bs,
 248                                unsigned char *data, signed long data_len) {
 249     bitstream_align(bs);
 250     if (bs->data_len < bs->byte_offset ) {
 251         return 1;
 252     }
 253     while(bs->data_alloc_len < bs->byte_offset + data_len) {
 254         bitstream_realloc(bs);
 255     }
 256     bs->data_len = bs->byte_offset + data_len;
 257     memcpy(bs->data + bs->byte_offset, data, data_len);
 258     bs->byte_offset += data_len;
 259     return 0;
 260 }
 261
 262 int
 263 bitstream_getstring(bitstream_t *bs,
 264                                unsigned char *data, signed long data_len) {
 265     bitstream_align(bs);
 266     if (bs->data_len < bs->byte_offset + data_len) {
 267         return -1; /* End of Stream */
 268     }
 269     memcpy(data, bs->data + bs->byte_offset, data_len);
 270     bs->byte_offset += data_len;
 271     return 0;
 272 }
 273
 274 unsigned char *
 275 bitstream_outputstring(bitstream_t *bs) {
 276     unsigned char *data;
 277     register unsigned long data_len;
 278     bitstream_align(bs);
 279     data_len = strlen((char *) bs->data + bs->byte_offset);
 280     data_len += 1; // + '\0'
 281     if (bs->data_len < bs->byte_offset + data_len) {
 282         return NULL; /* End of Stream */
 283     }
 284     data = malloc(data_len);
 285     if (data == NULL) {
 286         fprintf(stderr, "bitstream_outputstring: can't malloc\n");
 287         return NULL;
 288     }
 289     memcpy(data, bs->data + bs->byte_offset, data_len);
 290     bs->byte_offset += data_len;
 291     return data;
 292 }
 293
 294 int
 295 bitstream_putbytesLE(bitstream_t *bs, unsigned long bytes, int byte_width) {
 296     register int i;
 297     register unsigned long tmp_bytes = bytes;
 298     for (i=0 ; i < byte_width ; i++) {
 299         bitstream_putbyte(bs, tmp_bytes & 0xff);
 300         tmp_bytes >>= 8;
 301     }
 302     return 0;
 303 }
 304
 305 int
 306 bitstream_putbytesBE(bitstream_t *bs, unsigned long bytes, int byte_width) {
 307     register int i;
 308     register unsigned long tmp_bytes = bytes;
 309     for (i=0 ; i < byte_width ; i++) {
 310         bitstream_putbyte(bs, (tmp_bytes >> ( 8 * (byte_width - 1 - i))) & 0xff);
 311     }
 312     return 0;
 313 }
 314
 315 unsigned long
 316 bitstream_getbytesLE(bitstream_t *bs, int byte_width) {
 317     register int i;
 318     register int byte;
 319     register unsigned long bytes = 0;
 320     for (i=0 ; i < byte_width ; i++) {
 321         byte = bitstream_getbyte(bs);
 322         if (byte == -1) {
 323             return -1; // End of Stream;
 324         }
 325         byte <<= 8 * i;
 326         bytes |= byte;
 327     }
 328     return bytes;
 329 }
 330
 331 unsigned long
 332 bitstream_getbytesBE(bitstream_t *bs, int byte_width) {
 333     register int i;
 334     register int byte;
 335     register unsigned long bytes = 0;
 336     for (i=0 ; i < byte_width ; i++) {
 337         bytes <<= 8;
 338         byte = bitstream_getbyte(bs);
 339         if (byte == -1) {
 340             return -1; // End of Stream;
 341         }
 342         bytes |= byte;
 343     }
 344     return bytes;
 345 }
 346
 347 /*
 348  * bit stream
 349  */
 350
 351 int
 352 bitstream_putbit(bitstream_t *bs, int bit) {
 353     if (bs->data_len <= bs->byte_offset) {
 354         if (bs->data_alloc_len <= bs->byte_offset) {
 355 //            fprintf(stderr, "bitstream_putbit: alloc_len=%lu\n", bs->data_alloc_len);
 356             bitstream_realloc(bs);
 357         }
 358         bs->data[bs->byte_offset] = 0;
 359         bs->data_len ++;
 360     }
 361     bs->data[bs->byte_offset] |= (bit & 1) << (7 - bs->bit_offset);
 362     bitstream_incrpos(bs, 0, 1);
 363     return 0;
 364 }
 365 int
 366 bitstream_getbit(bitstream_t *bs) {
 367     register int bit;
 368     if (bs->data_len <= bs->byte_offset) {
 369         fprintf(stderr, "bitstream_getbit: bs->data_len(%lu) <= bs->byte_offset(%lu)\n",
 370                 bs->data_len, bs->byte_offset);
 371         return -1; /* End of Stream */
 372     }
 373     bit = bs->data[bs->byte_offset] >> (7 - bs->bit_offset);
 374     bitstream_incrpos(bs, 0, 1);
 375     return bit & 1;
 376 }
 377
 378 int
 379 bitstream_putbits(bitstream_t *bs, unsigned long bits, int bit_width) {
 380     register int i = bit_width;
 381     while (i--) {
 382         bitstream_putbit(bs, (bits >> i) & 1);
 383     }
 384     return 0;
 385 }
 386
 387 int
 388 bitstream_putbits_signed(bitstream_t *bs, signed long bits, int bit_width) {
 389     if (bits < 0) {
 390         register signed long msb = 1 << (bit_width - 1);
 391         register signed long bitmask = (msb << 1) - 1;
 392         bits = (-bits  - 1) ^ bitmask;
 393     }
 394     return bitstream_putbits(bs, bits, bit_width);
 395 }
 396
 397 #if BITOPERATION_OPTIMIZE == 1
 398 unsigned long
 399 bitstream_getbits(bitstream_t *bs, int bit_width) {
 400     register unsigned long bits;
 401     register int byte_offset = bs->byte_offset;
 402     register int bit_offset  = bs->bit_offset;
 403     if (bs->data_len <= byte_offset + (bit_offset + bit_width) >> 3) {
 404         fprintf(stderr, "bitstream_getbits: bs->data_len(%lu) <= byte_offset(%lu) + (bit_offset(%lu) + bit_width(%d)) >> 3\n",
 405                 bs->data_len, bs->byte_offset, bs->bit_offset , bit_width);
 406         return -1; /* End of Stream */
 407     }
 408     if ((bit_offset + bit_width) < 9) {
 409         bits = (bs->data[byte_offset] >> (8 - bit_offset - bit_width)) & bitstream_bitmask_list[bit_width];
 410         bit_offset += bit_width;
 411     } else {
 412         register int len = 8 - bit_offset;
 413         bits = bs->data[byte_offset] & bitstream_bitmask_list[len];
 414         bit_offset += len;
 415         bit_width -= len;
 416         bits <<= bit_width;
 417         while (1) {
 418             if (bit_width < 9) {
 419                 bits |= ((bs->data[++byte_offset] >> (8 - bit_width))) & bitstream_bitmask_list[bit_width];
 420                 bit_offset += bit_width - 8;
 421                 break;
 422             } else {
 423                 bits |= bs->data[++byte_offset];
 424                 bit_width -= 8;
 425                 bits <<= 8;
 426             }
 427         }
 428     }
 429     bitstream_setpos(bs, byte_offset, bit_offset);
 430     return bits;
 431 }
 432 #else // BITOPERATION_OPTIMIZE
 433 unsigned long
 434 bitstream_getbits(bitstream_t *bs, int bit_width) {
 435     register int i, bit;
 436     register unsigned long bits = 0;
 437     for (i=0 ; i < bit_width ; i++) {
 438         bit = bitstream_getbit(bs);
 439         if (bit == -1) {
 440             return -1;
 441         }
 442         bits |= bit << (bit_width - 1 - i);
 443     }
 444     return bits;
 445 }
 446 #endif // BITOPERATION_OPTIMIZE
 447
 448 signed long
 449 bitstream_getbits_signed(bitstream_t *bs, int bit_width) {
 450     register signed long bits = bitstream_getbits(bs, bit_width);
 451     register signed long msb =  bits & (1 << (bit_width - 1));
 452     if (msb) {
 453         register signed long bitmask = (msb << 1) - 1;
 454         bits = - (bits ^ bitmask) - 1;
 455     }
 456     return bits;
 457 }
 458
 459 void
 460 bitstream_align(bitstream_t *bs) {
 461     if (bs->bit_offset > 0) {
 462         bs->byte_offset++;
 463         bs->bit_offset = 0;
 464     }
 465 }
 466
 467 /*
 468  * stream seek
 469  */
 470
 471 int
 472 bitstream_incrpos(bitstream_t *bs, signed long byte_incr,
 473                   signed long bit_incr) {
 474     register signed long byte_offset, bit_offset;
 475     if (bit_incr < 0) {
 476         byte_offset = bs->byte_offset - ((-bit_incr + 7) >> 3);
 477         bit_offset = bs->bit_offset + (bit_incr % 8) + 8;
 478     } else {
 479         byte_offset = bs->byte_offset + byte_incr;
 480         bit_offset = bs->bit_offset + bit_incr;
 481     }
 482     if (bit_offset < 8) {
 483         bs->byte_offset = byte_offset;
 484         bs->bit_offset = bit_offset;
 485     } else {
 486         bs->byte_offset = byte_offset + (bit_offset >> 3);
 487         bs->bit_offset = bit_offset & 7;
 488     }
 489     return 0;
 490 }
 491
 492 int
 493 bitstream_setpos(bitstream_t *bs, unsigned long byte_offset,
 494                      unsigned long bit_offset) {
 495     if (bs->data_len < byte_offset ) {
 496         fprintf(stderr, "bitstream_setpos: bs->data_len(%lu) <= byte_offset(%lu)\n",
 497                 bs->data_len, byte_offset);
 498     }
 499     bs->byte_offset = byte_offset;
 500     bs->bit_offset = bit_offset;
 501     return 0;
 502 }
 503
 504 unsigned long
 505 bitstream_getbytepos(bitstream_t *bs) {
 506     return bs->byte_offset;
 507 }
 508
 509 unsigned long
 510 bitstream_getbitpos(bitstream_t *bs) {
 511     return bs->bit_offset;
 512 }
 513
 514 /*
 515  * stream info
 516  */
 517
 518 unsigned char *
 519 bitstream_buffer(bitstream_t *bs, unsigned long byte_offset) {
 520     return bs->data + byte_offset;
 521 }
 522
 523 unsigned long
 524 bitstream_length(bitstream_t *bs) {
 525     return bs->data_len;
 526 }
 527
 528 /*
 529  * utility
 530  */
 531
 532 signed long
 533 bitstream_unsigned2signed(unsigned long num, int size) {
 534     register unsigned long sig_bit = 1 << (size - 1);
 535     if ((sig_bit & num) == 0) {
 536         return (signed long) num;
 537     } else {
 538         unsigned long mask = sig_bit - 1;
 539         return - ((num^mask) & mask) - 1;
 540     }
 541 }
 542
 543 unsigned long
 544 bitstream_signed2unsigned(signed long num, int size) { // XXX check me!
 545     if (0 <= num){
 546         return (unsigned long) num;
 547     } else {
 548         unsigned long sig_bit = 1 << (size - 1);
 549         unsigned long mask = sig_bit - 1;
 550         return - ((num^mask) & mask) - 1;
 551     }
 552 }
 553
 554 int
 555 bitstream_need_bits_unsigned(unsigned long n) {
 556     register int i;
 557     for (i = 0 ; n ; i++) {
 558         n >>= 1;
 559     }
 560     return i;
 561 }
 562
 563 int
 564 bitstream_need_bits_signed(signed long n) {
 565     register int ret;
 566     if (n < -1) {
 567         n = -1 - n;
 568     }
 569     if (n >= 0) {
 570         register int i;
 571         for (i = 0 ; n ; i++) {
 572             n >>= 1;
 573         }
 574         ret = 1 + i;
 575         ;
 576     } else { // n == -1
 577         ret = 1;
 578     }
 579     return ret;
 580 }
 581
 582 /*
 583  * error handling
 584  */
 585
 586 int
 587 bitstream_iserror(bitstream_t *bs) {
 588     (void) bs;
 589     return 0;
 590 }
 591
 592 void
 593 bitstream_printerror(bitstream_t *bs) {
 594     (void) bs;
 595 }
 596
 597 /*
 598  * for debug
 599  */
 600
 601 void
 602 bitstream_hexdump(bitstream_t *bs, int length) {
 603     register unsigned long i, j;
 604     for ( i = bs->byte_offset ; i < bs->byte_offset + length ; i++) {
 605         if ((i == bs->byte_offset) || (i%16) == 0) {
 606             printf("%08lu: ", i);
 607             if ((i%16) != 0) {
 608                 for( j = 0 ; j < (i%16) ; j++) {
 609                     printf("   ");
 610                 }
 611             }
 612         }
 613         printf("%02x ", bs->data[i] & 0xff);
 614         if ((i%16) == 7) {
 615             printf(" ");
 616         }
 617         if ((i%16) == 15) {
 618             printf("\n");
 619         }
 620     }
 621     if ((i%16) != 0) {
 622         printf("\n");
 623     }
 624 }
 625
 626 void
 627 bitstream_print(bitstream_t *bs) {
 628     printf("data=%p  data_len=%lu data_alloc_len=%lu\n",
 629            bs->data, bs->data_len, bs->data_alloc_len);
 630     printf("byte_offset=%lu  bit_offset=%lu\n",
 631            bs->byte_offset, bs->bit_offset);
 632 }