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