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