libogg-1.0/src/bitwise.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
   4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
   5  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
   6  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
   7  *                                                                  *
   8  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2002             *
   9  * by the Xiph.Org Foundation http://www.xiph.org/                  *
  10  *                                                                  *
  11  ********************************************************************
  12
  13   function: packing variable sized words into an octet stream
  14   last mod: $Id: bitwise.c,v 1.13 2002/07/11 09:09:08 xiphmont Exp $
  15
  16  ********************************************************************/
  17
  18 /* We're 'LSb' endian; if we write a word but read individual bits,
  19    then we'll read the lsb first */
  20
  21 #include <string.h>
  22 #include <stdlib.h>
  23 #include <ogg/ogg.h>
  24
  25 #define BUFFER_INCREMENT 256
  26
  27 static unsigned long mask[]=
  28 {0x00000000,0x00000001,0x00000003,0x00000007,0x0000000f,
  29  0x0000001f,0x0000003f,0x0000007f,0x000000ff,0x000001ff,
  30  0x000003ff,0x000007ff,0x00000fff,0x00001fff,0x00003fff,
  31  0x00007fff,0x0000ffff,0x0001ffff,0x0003ffff,0x0007ffff,
  32  0x000fffff,0x001fffff,0x003fffff,0x007fffff,0x00ffffff,
  33  0x01ffffff,0x03ffffff,0x07ffffff,0x0fffffff,0x1fffffff,
  34  0x3fffffff,0x7fffffff,0xffffffff };
  35
  36 void oggpack_writeinit(oggpack_buffer *b){
  37   memset(b,0,sizeof(*b));
  38   b->ptr=b->buffer=_ogg_malloc(BUFFER_INCREMENT);
  39   b->buffer[0]='\0';
  40   b->storage=BUFFER_INCREMENT;
  41 }
  42
  43 void oggpack_writetrunc(oggpack_buffer *b,long bits){
  44   long bytes=bits>>3;
  45   bits-=bytes*8;
  46   b->ptr=b->buffer+bytes;
  47   b->endbit=bits;
  48   b->endbyte=bytes;
  49   *b->ptr|=mask[bits];
  50 }
  51
  52 void oggpack_writealign(oggpack_buffer *b){
  53   int bits=8-b->endbit;
  54   if(bits<8)
  55     oggpack_write(b,0,bits);
  56 }
  57
  58 void oggpack_writecopy(oggpack_buffer *b,void *source,long bits){
  59   unsigned char *ptr=(unsigned char *)source;
  60
  61   long bytes=bits/8;
  62   bits-=bytes*8;
  63
  64   if(b->endbit){
  65     int i;
  66     /* unaligned copy.  Do it the hard way. */
  67     for(i=0;i<bytes;i++)
  68       oggpack_write(b,(long)(ptr[i]),8);
  69   }else{
  70     /* aligned block copy */
  71     if(b->endbyte+bytes+1>=b->storage){
  72       b->storage=b->endbyte+bytes+BUFFER_INCREMENT;
  73       b->buffer=_ogg_realloc(b->buffer,b->storage);
  74       b->ptr=b->buffer+b->endbyte;
  75     }
  76
  77     memmove(b->ptr,source,bytes);
  78     b->ptr+=bytes;
  79     b->buffer+=bytes;
  80     *b->ptr=0;
  81
  82   }
  83   if(bits)
  84     oggpack_write(b,(long)(ptr[bytes]),bits);
  85 }
  86
  87 void oggpack_reset(oggpack_buffer *b){
  88   b->ptr=b->buffer;
  89   b->buffer[0]=0;
  90   b->endbit=b->endbyte=0;
  91 }
  92
  93 void oggpack_writeclear(oggpack_buffer *b){
  94   _ogg_free(b->buffer);
  95   memset(b,0,sizeof(*b));
  96 }
  97
  98 void oggpack_readinit(oggpack_buffer *b,unsigned char *buf,int bytes){
  99   memset(b,0,sizeof(*b));
 100   b->buffer=b->ptr=buf;
 101   b->storage=bytes;
 102 }
 103
 104 /* Takes only up to 32 bits. */
 105 void oggpack_write(oggpack_buffer *b,unsigned long value,int bits){
 106   if(b->endbyte+4>=b->storage){
 107     b->buffer=_ogg_realloc(b->buffer,b->storage+BUFFER_INCREMENT);
 108     b->storage+=BUFFER_INCREMENT;
 109     b->ptr=b->buffer+b->endbyte;
 110   }
 111
 112   value&=mask[bits];
 113   bits+=b->endbit;
 114
 115   b->ptr[0]|=value<<b->endbit;
 116
 117   if(bits>=8){
 118     b->ptr[1]=value>>(8-b->endbit);
 119     if(bits>=16){
 120       b->ptr[2]=value>>(16-b->endbit);
 121       if(bits>=24){
 122         b->ptr[3]=value>>(24-b->endbit);
 123         if(bits>=32){
 124           if(b->endbit)
 125             b->ptr[4]=value>>(32-b->endbit);
 126           else
 127             b->ptr[4]=0;
 128         }
 129       }
 130     }
 131   }
 132
 133   b->endbyte+=bits/8;
 134   b->ptr+=bits/8;
 135   b->endbit=bits&7;
 136 }
 137
 138 /* Read in bits without advancing the bitptr; bits <= 32 */
 139 long oggpack_look(oggpack_buffer *b,int bits){
 140   unsigned long ret;
 141   unsigned long m=mask[bits];
 142
 143   bits+=b->endbit;
 144
 145   if(b->endbyte+4>=b->storage){
 146     /* not the main path */
 147     if(b->endbyte*8+bits>b->storage*8)return(-1);
 148   }
 149
 150   ret=b->ptr[0]>>b->endbit;
 151   if(bits>8){
 152     ret|=b->ptr[1]<<(8-b->endbit);
 153     if(bits>16){
 154       ret|=b->ptr[2]<<(16-b->endbit);
 155       if(bits>24){
 156         ret|=b->ptr[3]<<(24-b->endbit);
 157         if(bits>32 && b->endbit)
 158           ret|=b->ptr[4]<<(32-b->endbit);
 159       }
 160     }
 161   }
 162   return(m&ret);
 163 }
 164
 165 long oggpack_look1(oggpack_buffer *b){
 166   if(b->endbyte>=b->storage)return(-1);
 167   return((b->ptr[0]>>b->endbit)&1);
 168 }
 169
 170 void oggpack_adv(oggpack_buffer *b,int bits){
 171   bits+=b->endbit;
 172   b->ptr+=bits/8;
 173   b->endbyte+=bits/8;
 174   b->endbit=bits&7;
 175 }
 176
 177 void oggpack_adv1(oggpack_buffer *b){
 178   if(++(b->endbit)>7){
 179     b->endbit=0;
 180     b->ptr++;
 181     b->endbyte++;
 182   }
 183 }
 184
 185 /* bits <= 32 */
 186 long oggpack_read(oggpack_buffer *b,int bits){
 187   unsigned long ret;
 188   unsigned long m=mask[bits];
 189
 190   bits+=b->endbit;
 191
 192   if(b->endbyte+4>=b->storage){
 193     /* not the main path */
 194     ret=-1UL;
 195     if(b->endbyte*8+bits>b->storage*8)goto overflow;
 196   }
 197
 198   ret=b->ptr[0]>>b->endbit;
 199   if(bits>8){
 200     ret|=b->ptr[1]<<(8-b->endbit);
 201     if(bits>16){
 202       ret|=b->ptr[2]<<(16-b->endbit);
 203       if(bits>24){
 204         ret|=b->ptr[3]<<(24-b->endbit);
 205         if(bits>32 && b->endbit){
 206           ret|=b->ptr[4]<<(32-b->endbit);
 207         }
 208       }
 209     }
 210   }
 211   ret&=m;
 212
 213  overflow:
 214
 215   b->ptr+=bits/8;
 216   b->endbyte+=bits/8;
 217   b->endbit=bits&7;
 218   return(ret);
 219 }
 220
 221 long oggpack_read1(oggpack_buffer *b){
 222   unsigned long ret;
 223
 224   if(b->endbyte>=b->storage){
 225     /* not the main path */
 226     ret=-1UL;
 227     goto overflow;
 228   }
 229
 230   ret=(b->ptr[0]>>b->endbit)&1;
 231
 232  overflow:
 233
 234   b->endbit++;
 235   if(b->endbit>7){
 236     b->endbit=0;
 237     b->ptr++;
 238     b->endbyte++;
 239   }
 240   return(ret);
 241 }
 242
 243 long oggpack_bytes(oggpack_buffer *b){
 244   return(b->endbyte+(b->endbit+7)/8);
 245 }
 246
 247 long oggpack_bits(oggpack_buffer *b){
 248   return(b->endbyte*8+b->endbit);
 249 }
 250
 251 unsigned char *oggpack_get_buffer(oggpack_buffer *b){
 252   return(b->buffer);
 253 }
 254
 255 /* Self test of the bitwise routines; everything else is based on
 256    them, so they damned well better be solid. */
 257
 258 #ifdef _V_SELFTEST
 259 #include <stdio.h>
 260
 261 static int ilog(unsigned int v){
 262   int ret=0;
 263   while(v){
 264     ret++;
 265     v>>=1;
 266   }
 267   return(ret);
 268 }
 269
 270 oggpack_buffer o;
 271 oggpack_buffer r;
 272
 273 void report(char *in){
 274   fprintf(stderr,"%s",in);
 275   exit(1);
 276 }
 277
 278 void cliptest(unsigned long *b,int vals,int bits,int *comp,int compsize){
 279   long bytes,i;
 280   unsigned char *buffer;
 281
 282   oggpack_reset(&o);
 283   for(i=0;i<vals;i++)
 284     oggpack_write(&o,b[i],bits?bits:ilog(b[i]));
 285   buffer=oggpack_get_buffer(&o);
 286   bytes=oggpack_bytes(&o);
 287   if(bytes!=compsize)report("wrong number of bytes!\n");
 288   for(i=0;i<bytes;i++)if(buffer[i]!=comp[i]){
 289     for(i=0;i<bytes;i++)fprintf(stderr,"%x %x\n",(int)buffer[i],(int)comp[i]);
 290     report("wrote incorrect value!\n");
 291   }
 292   oggpack_readinit(&r,buffer,bytes);
 293   for(i=0;i<vals;i++){
 294     int tbit=bits?bits:ilog(b[i]);
 295     if(oggpack_look(&r,tbit)==-1)
 296       report("out of data!\n");
 297     if(oggpack_look(&r,tbit)!=(b[i]&mask[tbit]))
 298       report("looked at incorrect value!\n");
 299     if(tbit==1)
 300       if(oggpack_look1(&r)!=(b[i]&mask[tbit]))
 301         report("looked at single bit incorrect value!\n");
 302     if(tbit==1){
 303       if(oggpack_read1(&r)!=(b[i]&mask[tbit]))
 304         report("read incorrect single bit value!\n");
 305     }else{
 306     if(oggpack_read(&r,tbit)!=(b[i]&mask[tbit]))
 307       report("read incorrect value!\n");
 308     }
 309   }
 310   if(oggpack_bytes(&r)!=bytes)report("leftover bytes after read!\n");
 311 }
 312
 313 int main(void){
 314   unsigned char *buffer;
 315   long bytes,i;
 316   static unsigned long testbuffer1[]=
 317     {18,12,103948,4325,543,76,432,52,3,65,4,56,32,42,34,21,1,23,32,546,456,7,
 318        567,56,8,8,55,3,52,342,341,4,265,7,67,86,2199,21,7,1,5,1,4};
 319   int test1size=43;
 320
 321   static unsigned long testbuffer2[]=
 322     {216531625L,1237861823,56732452,131,3212421,12325343,34547562,12313212,
 323        1233432,534,5,346435231,14436467,7869299,76326614,167548585,
 324        85525151,0,12321,1,349528352};
 325   int test2size=21;
 326
 327   static unsigned long large[]=
 328     {2136531625L,2137861823,56732452,131,3212421,12325343,34547562,12313212,
 329        1233432,534,5,2146435231,14436467,7869299,76326614,167548585,
 330        85525151,0,12321,1,2146528352};
 331
 332   static unsigned long testbuffer3[]=
 333     {1,0,14,0,1,0,12,0,1,0,0,0,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,1,1,1,1,0,0,1,
 334        0,1,30,1,1,1,0,0,1,0,0,0,12,0,11,0,1,0,0,1};
 335   int test3size=56;
 336
 337   int onesize=33;
 338   static int one[]={146,25,44,151,195,15,153,176,233,131,196,65,85,172,47,40,
 339                     34,242,223,136,35,222,211,86,171,50,225,135,214,75,172,
 340                     223,4};
 341
 342   int twosize=6;
 343   static int two[]={61,255,255,251,231,29};
 344
 345   int threesize=54;
 346   static int three[]={169,2,232,252,91,132,156,36,89,13,123,176,144,32,254,
 347                       142,224,85,59,121,144,79,124,23,67,90,90,216,79,23,83,
 348                       58,135,196,61,55,129,183,54,101,100,170,37,127,126,10,
 349                       100,52,4,14,18,86,77,1};
 350
 351   int foursize=38;
 352   static int four[]={18,6,163,252,97,194,104,131,32,1,7,82,137,42,129,11,72,
 353                      132,60,220,112,8,196,109,64,179,86,9,137,195,208,122,169,
 354                      28,2,133,0,1};
 355
 356   int fivesize=45;
 357   static int five[]={169,2,126,139,144,172,30,4,80,72,240,59,130,218,73,62,
 358                      241,24,210,44,4,20,0,248,116,49,135,100,110,130,181,169,
 359                      84,75,159,2,1,0,132,192,8,0,0,18,22};
 360
 361   int sixsize=7;
 362   static int six[]={17,177,170,242,169,19,148};
 363
 364   /* Test read/write together */
 365   /* Later we test against pregenerated bitstreams */
 366   oggpack_writeinit(&o);
 367
 368   fprintf(stderr,"\nSmall preclipped packing: ");
 369   cliptest(testbuffer1,test1size,0,one,onesize);
 370   fprintf(stderr,"ok.");
 371
 372   fprintf(stderr,"\nNull bit call: ");
 373   cliptest(testbuffer3,test3size,0,two,twosize);
 374   fprintf(stderr,"ok.");
 375
 376   fprintf(stderr,"\nLarge preclipped packing: ");
 377   cliptest(testbuffer2,test2size,0,three,threesize);
 378   fprintf(stderr,"ok.");
 379
 380   fprintf(stderr,"\n32 bit preclipped packing: ");
 381   oggpack_reset(&o);
 382   for(i=0;i<test2size;i++)
 383     oggpack_write(&o,large[i],32);
 384   buffer=oggpack_get_buffer(&o);
 385   bytes=oggpack_bytes(&o);
 386   oggpack_readinit(&r,buffer,bytes);
 387   for(i=0;i<test2size;i++){
 388     if(oggpack_look(&r,32)==-1)report("out of data. failed!");
 389     if(oggpack_look(&r,32)!=large[i]){
 390       fprintf(stderr,"%ld != %ld (%lx!=%lx):",oggpack_look(&r,32),large[i],
 391               oggpack_look(&r,32),large[i]);
 392       report("read incorrect value!\n");
 393     }
 394     oggpack_adv(&r,32);
 395   }
 396   if(oggpack_bytes(&r)!=bytes)report("leftover bytes after read!\n");
 397   fprintf(stderr,"ok.");
 398
 399   fprintf(stderr,"\nSmall unclipped packing: ");
 400   cliptest(testbuffer1,test1size,7,four,foursize);
 401   fprintf(stderr,"ok.");
 402
 403   fprintf(stderr,"\nLarge unclipped packing: ");
 404   cliptest(testbuffer2,test2size,17,five,fivesize);
 405   fprintf(stderr,"ok.");
 406
 407   fprintf(stderr,"\nSingle bit unclipped packing: ");
 408   cliptest(testbuffer3,test3size,1,six,sixsize);
 409   fprintf(stderr,"ok.");
 410
 411   fprintf(stderr,"\nTesting read past end: ");
 412   oggpack_readinit(&r,"\0\0\0\0\0\0\0\0",8);
 413   for(i=0;i<64;i++){
 414     if(oggpack_read(&r,1)!=0){
 415       fprintf(stderr,"failed; got -1 prematurely.\n");
 416       exit(1);
 417     }
 418   }
 419   if(oggpack_look(&r,1)!=-1 ||
 420      oggpack_read(&r,1)!=-1){
 421       fprintf(stderr,"failed; read past end without -1.\n");
 422       exit(1);
 423   }
 424   oggpack_readinit(&r,"\0\0\0\0\0\0\0\0",8);
 425   if(oggpack_read(&r,30)!=0 || oggpack_read(&r,16)!=0){
 426       fprintf(stderr,"failed 2; got -1 prematurely.\n");
 427       exit(1);
 428   }
 429
 430   if(oggpack_look(&r,18)!=0 ||
 431      oggpack_look(&r,18)!=0){
 432     fprintf(stderr,"failed 3; got -1 prematurely.\n");
 433       exit(1);
 434   }
 435   if(oggpack_look(&r,19)!=-1 ||
 436      oggpack_look(&r,19)!=-1){
 437     fprintf(stderr,"failed; read past end without -1.\n");
 438       exit(1);
 439   }
 440   if(oggpack_look(&r,32)!=-1 ||
 441      oggpack_look(&r,32)!=-1){
 442     fprintf(stderr,"failed; read past end without -1.\n");
 443       exit(1);
 444   }
 445   fprintf(stderr,"ok.\n\n");
 446
 447
 448   return(0);
 449 }
 450 #endif  /* _V_SELFTEST */
 451
 452 #undef BUFFER_INCREMENT