lib/bitwise.c

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