Tremor/bitwise.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE.   *
   4  *                                                                  *
   5  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
   6  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
   7  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
   8  *                                                                  *
   9  * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2002    *
  10  * BY THE Xiph.Org FOUNDATION http://www.xiph.org/                  *
  11  *                                                                  *
  12  ********************************************************************
  13
  14   function: packing variable sized words into an octet stream
  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 static unsigned long mask[]=
  26 {0x00000000,0x00000001,0x00000003,0x00000007,0x0000000f,
  27  0x0000001f,0x0000003f,0x0000007f,0x000000ff,0x000001ff,
  28  0x000003ff,0x000007ff,0x00000fff,0x00001fff,0x00003fff,
  29  0x00007fff,0x0000ffff,0x0001ffff,0x0003ffff,0x0007ffff,
  30  0x000fffff,0x001fffff,0x003fffff,0x007fffff,0x00ffffff,
  31  0x01ffffff,0x03ffffff,0x07ffffff,0x0fffffff,0x1fffffff,
  32  0x3fffffff,0x7fffffff,0xffffffff };
  33
  34 /* mark read process as having run off the end */
  35 static void _adv_halt(oggpack_buffer *b){
  36   b->headptr=b->head->buffer->data+b->head->begin+b->head->length;
  37   b->headend=-1;
  38   b->headbit=0;
  39 }
  40
  41 /* spans forward, skipping as many bytes as headend is negative; if
  42    headend is zero, simply finds next byte.  If we're up to the end
  43    of the buffer, leaves headend at zero.  If we've read past the end,
  44    halt the decode process. */
  45 static void _span(oggpack_buffer *b){
  46   while(b->headend<1){
  47     if(b->head->next){
  48       b->count+=b->head->length;
  49       b->head=b->head->next;
  50       b->headptr=b->head->buffer->data+b->head->begin-b->headend;
  51       b->headend+=b->head->length;
  52     }else{
  53       /* we've either met the end of decode, or gone past it. halt
  54          only if we're past */
  55       if(b->headend<0 || b->headbit)
  56         /* read has fallen off the end */
  57         _adv_halt(b);
  58
  59       break;
  60     }
  61   }
  62 }
  63
  64 void oggpack_readinit(oggpack_buffer *b,ogg_reference *r){
  65   memset(b,0,sizeof(*b));
  66
  67   b->tail=b->head=r;
  68   b->count=0;
  69   b->headptr=b->head->buffer->data+b->head->begin;
  70   b->headend=b->head->length;
  71   _span(b);
  72 }
  73
  74 #define _lookspan()   while(!end){\
  75                         head=head->next;\
  76                         if(!head) return -1;\
  77                         ptr=head->buffer->data + head->begin;\
  78                         end=head->length;\
  79                       }
  80
  81 /* Read in bits without advancing the bitptr; bits <= 32 */
  82 long oggpack_look(oggpack_buffer *b,int bits){
  83   unsigned long m=mask[bits];
  84   unsigned long ret=-1;
  85
  86   bits+=b->headbit;
  87
  88   if(bits >= b->headend<<3){
  89     int            end=b->headend;
  90     unsigned char *ptr=b->headptr;
  91     ogg_reference *head=b->head;
  92
  93     if(end<0)return -1;
  94
  95     if(bits){
  96       _lookspan();
  97       ret=*ptr++>>b->headbit;
  98       if(bits>8){
  99         --end;
 100         _lookspan();
 101         ret|=*ptr++<<(8-b->headbit);
 102         if(bits>16){
 103           --end;
 104           _lookspan();
 105           ret|=*ptr++<<(16-b->headbit);
 106           if(bits>24){
 107             --end;
 108             _lookspan();
 109             ret|=*ptr++<<(24-b->headbit);
 110             if(bits>32 && b->headbit){
 111               --end;
 112               _lookspan();
 113               ret|=*ptr<<(32-b->headbit);
 114             }
 115           }
 116         }
 117       }
 118     }
 119
 120   }else{
 121
 122     /* make this a switch jump-table */
 123     ret=b->headptr[0]>>b->headbit;
 124     if(bits>8){
 125       ret|=b->headptr[1]<<(8-b->headbit);
 126       if(bits>16){
 127         ret|=b->headptr[2]<<(16-b->headbit);
 128         if(bits>24){
 129           ret|=b->headptr[3]<<(24-b->headbit);
 130           if(bits>32 && b->headbit)
 131             ret|=b->headptr[4]<<(32-b->headbit);
 132         }
 133       }
 134     }
 135   }
 136
 137   ret&=m;
 138   return ret;
 139 }
 140
 141 /* limited to 32 at a time */
 142 void oggpack_adv(oggpack_buffer *b,int bits){
 143   bits+=b->headbit;
 144   b->headbit=bits&7;
 145   b->headptr+=bits/8;
 146   if((b->headend-=bits/8)<1)_span(b);
 147 }
 148
 149 /* spans forward and finds next byte.  Never halts */
 150 static void _span_one(oggpack_buffer *b){
 151   while(b->headend<1){
 152     if(b->head->next){
 153       b->count+=b->head->length;
 154       b->head=b->head->next;
 155       b->headptr=b->head->buffer->data+b->head->begin;
 156       b->headend=b->head->length;
 157     }else
 158       break;
 159   }
 160 }
 161
 162 static int _halt_one(oggpack_buffer *b){
 163   if(b->headend<1){
 164     _adv_halt(b);
 165     return -1;
 166   }
 167   return 0;
 168 }
 169
 170 int oggpack_eop(oggpack_buffer *b){
 171   if(b->headend<0)return -1;
 172   return 0;
 173 }
 174
 175 /* bits <= 32 */
 176 long oggpack_read(oggpack_buffer *b,int bits){
 177   unsigned long m=mask[bits];
 178   ogg_uint32_t ret=-1;
 179
 180   bits+=b->headbit;
 181
 182   if(bits >= b->headend<<3){
 183
 184     if(b->headend<0)return -1;
 185
 186     if(bits){
 187       if (_halt_one(b)) return -1;
 188       ret=*b->headptr>>b->headbit;
 189
 190       if(bits>=8){
 191         ++b->headptr;
 192         --b->headend;
 193         _span_one(b);
 194         if(bits>8){
 195           if (_halt_one(b)) return -1;
 196           ret|=*b->headptr<<(8-b->headbit);
 197
 198           if(bits>=16){
 199             ++b->headptr;
 200             --b->headend;
 201             _span_one(b);
 202             if(bits>16){
 203               if (_halt_one(b)) return -1;
 204               ret|=*b->headptr<<(16-b->headbit);
 205
 206               if(bits>=24){
 207                 ++b->headptr;
 208                 --b->headend;
 209                 _span_one(b);
 210                 if(bits>24){
 211                   if (_halt_one(b)) return -1;
 212                   ret|=*b->headptr<<(24-b->headbit);
 213
 214                   if(bits>=32){
 215                     ++b->headptr;
 216                     --b->headend;
 217                     _span_one(b);
 218                     if(bits>32){
 219                       if (_halt_one(b)) return -1;
 220                       if(b->headbit)ret|=*b->headptr<<(32-b->headbit);
 221
 222                     }
 223                   }
 224                 }
 225               }
 226             }
 227           }
 228         }
 229       }
 230     }
 231   }else{
 232
 233     ret=b->headptr[0]>>b->headbit;
 234     if(bits>8){
 235       ret|=b->headptr[1]<<(8-b->headbit);
 236       if(bits>16){
 237         ret|=b->headptr[2]<<(16-b->headbit);
 238         if(bits>24){
 239           ret|=b->headptr[3]<<(24-b->headbit);
 240           if(bits>32 && b->headbit){
 241             ret|=b->headptr[4]<<(32-b->headbit);
 242           }
 243         }
 244       }
 245     }
 246
 247     b->headptr+=bits/8;
 248     b->headend-=bits/8;
 249   }
 250
 251   ret&=m;
 252   b->headbit=bits&7;
 253   return ret;
 254 }
 255
 256 long oggpack_bytes(oggpack_buffer *b){
 257   return(b->count+b->headptr-b->head->buffer->data-b->head->begin+
 258          (b->headbit+7)/8);
 259 }
 260
 261 long oggpack_bits(oggpack_buffer *b){
 262   return((b->count+b->headptr-b->head->buffer->data-b->head->begin)*8+
 263          b->headbit);
 264 }
 265