tremor/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$
  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.h"
  24
  25 #define BUFFER_INCREMENT 256
  26
  27 static const 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 static const unsigned int mask8B[]=
  37 {0x00,0x80,0xc0,0xe0,0xf0,0xf8,0xfc,0xfe,0xff};
  38
  39 void oggpack_writeinit(oggpack_buffer *b){
  40   memset(b,0,sizeof(*b));
  41   b->ptr=b->buffer=_ogg_malloc(BUFFER_INCREMENT);
  42   b->buffer[0]='\0';
  43   b->storage=BUFFER_INCREMENT;
  44 }
  45
  46 void oggpackB_writeinit(oggpack_buffer *b){
  47   oggpack_writeinit(b);
  48 }
  49
  50 void oggpack_writetrunc(oggpack_buffer *b,long bits){
  51   long bytes=bits>>3;
  52   bits-=bytes*8;
  53   b->ptr=b->buffer+bytes;
  54   b->endbit=bits;
  55   b->endbyte=bytes;
  56   *b->ptr&=mask[bits];
  57 }
  58
  59 void oggpackB_writetrunc(oggpack_buffer *b,long bits){
  60   long bytes=bits>>3;
  61   bits-=bytes*8;
  62   b->ptr=b->buffer+bytes;
  63   b->endbit=bits;
  64   b->endbyte=bytes;
  65   *b->ptr&=mask8B[bits];
  66 }
  67
  68 /* Takes only up to 32 bits. */
  69 void oggpack_write(oggpack_buffer *b,unsigned long value,int bits){
  70   if(b->endbyte+4>=b->storage){
  71     b->buffer=_ogg_realloc(b->buffer,b->storage+BUFFER_INCREMENT);
  72     b->storage+=BUFFER_INCREMENT;
  73     b->ptr=b->buffer+b->endbyte;
  74   }
  75
  76   value&=mask[bits];
  77   bits+=b->endbit;
  78
  79   b->ptr[0]|=value<<b->endbit;
  80
  81   if(bits>=8){
  82     b->ptr[1]=(unsigned char)(value>>(8-b->endbit));
  83     if(bits>=16){
  84       b->ptr[2]=(unsigned char)(value>>(16-b->endbit));
  85       if(bits>=24){
  86         b->ptr[3]=(unsigned char)(value>>(24-b->endbit));
  87         if(bits>=32){
  88           if(b->endbit)
  89             b->ptr[4]=(unsigned char)(value>>(32-b->endbit));
  90           else
  91             b->ptr[4]=0;
  92         }
  93       }
  94     }
  95   }
  96
  97   b->endbyte+=bits/8;
  98   b->ptr+=bits/8;
  99   b->endbit=bits&7;
 100 }
 101
 102 /* Takes only up to 32 bits. */
 103 void oggpackB_write(oggpack_buffer *b,unsigned long value,int bits){
 104   if(b->endbyte+4>=b->storage){
 105     b->buffer=_ogg_realloc(b->buffer,b->storage+BUFFER_INCREMENT);
 106     b->storage+=BUFFER_INCREMENT;
 107     b->ptr=b->buffer+b->endbyte;
 108   }
 109
 110   value=(value&mask[bits])<<(32-bits);
 111   bits+=b->endbit;
 112
 113   b->ptr[0]|=value>>(24+b->endbit);
 114
 115   if(bits>=8){
 116     b->ptr[1]=(unsigned char)(value>>(16+b->endbit));
 117     if(bits>=16){
 118       b->ptr[2]=(unsigned char)(value>>(8+b->endbit));
 119       if(bits>=24){
 120         b->ptr[3]=(unsigned char)(value>>(b->endbit));
 121         if(bits>=32){
 122           if(b->endbit)
 123             b->ptr[4]=(unsigned char)(value<<(8-b->endbit));
 124           else
 125             b->ptr[4]=0;
 126         }
 127       }
 128     }
 129   }
 130
 131   b->endbyte+=bits/8;
 132   b->ptr+=bits/8;
 133   b->endbit=bits&7;
 134 }
 135
 136 void oggpack_writealign(oggpack_buffer *b){
 137   int bits=8-b->endbit;
 138   if(bits<8)
 139     oggpack_write(b,0,bits);
 140 }
 141
 142 void oggpackB_writealign(oggpack_buffer *b){
 143   int bits=8-b->endbit;
 144   if(bits<8)
 145     oggpackB_write(b,0,bits);
 146 }
 147
 148 static void oggpack_writecopy_helper(oggpack_buffer *b,
 149                                      void *source,
 150                                      long bits,
 151                                      void (*w)(oggpack_buffer *,
 152                                                unsigned long,
 153                                                int),
 154                                      int msb){
 155   unsigned char *ptr=(unsigned char *)source;
 156
 157   long bytes=bits/8;
 158   bits-=bytes*8;
 159
 160   if(b->endbit){
 161     int i;
 162     /* unaligned copy.  Do it the hard way. */
 163     for(i=0;i<bytes;i++)
 164       w(b,(unsigned long)(ptr[i]),8);
 165   }else{
 166     /* aligned block copy */
 167     if(b->endbyte+bytes+1>=b->storage){
 168       b->storage=b->endbyte+bytes+BUFFER_INCREMENT;
 169       b->buffer=_ogg_realloc(b->buffer,b->storage);
 170       b->ptr=b->buffer+b->endbyte;
 171     }
 172
 173     memmove(b->ptr,source,bytes);
 174     b->ptr+=bytes;
 175     b->endbyte+=bytes;
 176     *b->ptr=0;
 177
 178   }
 179   if(bits){
 180     if(msb)
 181       w(b,(unsigned long)(ptr[bytes]>>(8-bits)),bits);
 182     else
 183       w(b,(unsigned long)(ptr[bytes]),bits);
 184   }
 185 }
 186
 187 void oggpack_writecopy(oggpack_buffer *b,void *source,long bits){
 188   oggpack_writecopy_helper(b,source,bits,oggpack_write,0);
 189 }
 190
 191 void oggpackB_writecopy(oggpack_buffer *b,void *source,long bits){
 192   oggpack_writecopy_helper(b,source,bits,oggpackB_write,1);
 193 }
 194
 195 void oggpack_reset(oggpack_buffer *b){
 196   b->ptr=b->buffer;
 197   b->buffer[0]=0;
 198   b->endbit=b->endbyte=0;
 199 }
 200
 201 void oggpackB_reset(oggpack_buffer *b){
 202   oggpack_reset(b);
 203 }
 204
 205 void oggpack_writeclear(oggpack_buffer *b){
 206   _ogg_free(b->buffer);
 207   memset(b,0,sizeof(*b));
 208 }
 209
 210 void oggpackB_writeclear(oggpack_buffer *b){
 211   oggpack_writeclear(b);
 212 }
 213
 214 void oggpack_readinit(oggpack_buffer *b,unsigned char *buf,int bytes){
 215   memset(b,0,sizeof(*b));
 216   b->buffer=b->ptr=buf;
 217   b->storage=bytes;
 218 }
 219
 220 void oggpackB_readinit(oggpack_buffer *b,unsigned char *buf,int bytes){
 221   oggpack_readinit(b,buf,bytes);
 222 }
 223
 224 /* Read in bits without advancing the bitptr; bits <= 32 */
 225 long oggpack_look(oggpack_buffer *b,int bits){
 226   unsigned long ret;
 227   unsigned long m=mask[bits];
 228
 229   bits+=b->endbit;
 230
 231   if(b->endbyte+4>=b->storage){
 232     /* not the main path */
 233     if(b->endbyte*8+bits>b->storage*8)return(-1);
 234   }
 235
 236   ret=b->ptr[0]>>b->endbit;
 237   if(bits>8){
 238     ret|=b->ptr[1]<<(8-b->endbit);
 239     if(bits>16){
 240       ret|=b->ptr[2]<<(16-b->endbit);
 241       if(bits>24){
 242         ret|=b->ptr[3]<<(24-b->endbit);
 243         if(bits>32 && b->endbit)
 244           ret|=b->ptr[4]<<(32-b->endbit);
 245       }
 246     }
 247   }
 248   return(m&ret);
 249 }
 250
 251 /* Read in bits without advancing the bitptr; bits <= 32 */
 252 long oggpackB_look(oggpack_buffer *b,int bits){
 253   unsigned long ret;
 254   int m=32-bits;
 255
 256   bits+=b->endbit;
 257
 258   if(b->endbyte+4>=b->storage){
 259     /* not the main path */
 260     if(b->endbyte*8+bits>b->storage*8)return(-1);
 261   }
 262
 263   ret=b->ptr[0]<<(24+b->endbit);
 264   if(bits>8){
 265     ret|=b->ptr[1]<<(16+b->endbit);
 266     if(bits>16){
 267       ret|=b->ptr[2]<<(8+b->endbit);
 268       if(bits>24){
 269         ret|=b->ptr[3]<<(b->endbit);
 270         if(bits>32 && b->endbit)
 271           ret|=b->ptr[4]>>(8-b->endbit);
 272       }
 273     }
 274   }
 275   return ((ret&0xffffffff)>>(m>>1))>>((m+1)>>1);
 276 }
 277
 278 long oggpack_look1(oggpack_buffer *b){
 279   if(b->endbyte>=b->storage)return(-1);
 280   return((b->ptr[0]>>b->endbit)&1);
 281 }
 282
 283 long oggpackB_look1(oggpack_buffer *b){
 284   if(b->endbyte>=b->storage)return(-1);
 285   return((b->ptr[0]>>(7-b->endbit))&1);
 286 }
 287
 288 void oggpack_adv(oggpack_buffer *b,int bits){
 289   bits+=b->endbit;
 290   b->ptr+=bits/8;
 291   b->endbyte+=bits/8;
 292   b->endbit=bits&7;
 293 }
 294
 295 void oggpackB_adv(oggpack_buffer *b,int bits){
 296   oggpack_adv(b,bits);
 297 }
 298
 299 void oggpack_adv1(oggpack_buffer *b){
 300   if(++(b->endbit)>7){
 301     b->endbit=0;
 302     b->ptr++;
 303     b->endbyte++;
 304   }
 305 }
 306
 307 void oggpackB_adv1(oggpack_buffer *b){
 308   oggpack_adv1(b);
 309 }
 310
 311 /* bits <= 32 */
 312 long oggpack_read(oggpack_buffer *b,int bits){
 313   long ret;
 314   unsigned long m=mask[bits];
 315
 316   bits+=b->endbit;
 317
 318   if(b->endbyte+4>=b->storage){
 319     /* not the main path */
 320     ret=-1L;
 321     if(b->endbyte*8+bits>b->storage*8)goto overflow;
 322   }
 323
 324   ret=b->ptr[0]>>b->endbit;
 325   if(bits>8){
 326     ret|=b->ptr[1]<<(8-b->endbit);
 327     if(bits>16){
 328       ret|=b->ptr[2]<<(16-b->endbit);
 329       if(bits>24){
 330         ret|=b->ptr[3]<<(24-b->endbit);
 331         if(bits>32 && b->endbit){
 332           ret|=b->ptr[4]<<(32-b->endbit);
 333         }
 334       }
 335     }
 336   }
 337   ret&=m;
 338
 339  overflow:
 340
 341   b->ptr+=bits/8;
 342   b->endbyte+=bits/8;
 343   b->endbit=bits&7;
 344   return(ret);
 345 }
 346
 347 /* bits <= 32 */
 348 long oggpackB_read(oggpack_buffer *b,int bits){
 349   long ret;
 350   long m=32-bits;
 351
 352   bits+=b->endbit;
 353
 354   if(b->endbyte+4>=b->storage){
 355     /* not the main path */
 356     ret=-1L;
 357     if(b->endbyte*8+bits>b->storage*8)goto overflow;
 358   }
 359
 360   ret=b->ptr[0]<<(24+b->endbit);
 361   if(bits>8){
 362     ret|=b->ptr[1]<<(16+b->endbit);
 363     if(bits>16){
 364       ret|=b->ptr[2]<<(8+b->endbit);
 365       if(bits>24){
 366         ret|=b->ptr[3]<<(b->endbit);
 367         if(bits>32 && b->endbit)
 368           ret|=b->ptr[4]>>(8-b->endbit);
 369       }
 370     }
 371   }
 372   ret=((ret&0xffffffffUL)>>(m>>1))>>((m+1)>>1);
 373
 374  overflow:
 375
 376   b->ptr+=bits/8;
 377   b->endbyte+=bits/8;
 378   b->endbit=bits&7;
 379   return(ret);
 380 }
 381
 382 long oggpack_read1(oggpack_buffer *b){
 383   long ret;
 384
 385   if(b->endbyte>=b->storage){
 386     /* not the main path */
 387     ret=-1L;
 388     goto overflow;
 389   }
 390
 391   ret=(b->ptr[0]>>b->endbit)&1;
 392
 393  overflow:
 394
 395   b->endbit++;
 396   if(b->endbit>7){
 397     b->endbit=0;
 398     b->ptr++;
 399     b->endbyte++;
 400   }
 401   return(ret);
 402 }
 403
 404 long oggpackB_read1(oggpack_buffer *b){
 405   long ret;
 406
 407   if(b->endbyte>=b->storage){
 408     /* not the main path */
 409     ret=-1L;
 410     goto overflow;
 411   }
 412
 413   ret=(b->ptr[0]>>(7-b->endbit))&1;
 414
 415  overflow:
 416
 417   b->endbit++;
 418   if(b->endbit>7){
 419     b->endbit=0;
 420     b->ptr++;
 421     b->endbyte++;
 422   }
 423   return(ret);
 424 }
 425
 426 long oggpack_bytes(oggpack_buffer *b){
 427   return(b->endbyte+(b->endbit+7)/8);
 428 }
 429
 430 long oggpack_bits(oggpack_buffer *b){
 431   return(b->endbyte*8+b->endbit);
 432 }
 433
 434 long oggpackB_bytes(oggpack_buffer *b){
 435   return oggpack_bytes(b);
 436 }
 437
 438 long oggpackB_bits(oggpack_buffer *b){
 439   return oggpack_bits(b);
 440 }
 441
 442 unsigned char *oggpack_get_buffer(oggpack_buffer *b){
 443   return(b->buffer);
 444 }
 445
 446 unsigned char *oggpackB_get_buffer(oggpack_buffer *b){
 447   return oggpack_get_buffer(b);
 448 }
 449
 450 #undef BUFFER_INCREMENT