tremor/tremor/bitwise.c

/********************************************************************
 *                                                                  *
 * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE.   *
 *                                                                  *
 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
 *                                                                  *
 * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2003    *
 * BY THE Xiph.Org FOUNDATION http://www.xiph.org/                  *
 *                                                                  *
 ********************************************************************

  function: packing variable sized words into an octet stream

 ********************************************************************/

/* We're 'LSb' endian; if we write a word but read individual bits,
   then we'll read the lsb first */

#include <string.h>
#include <stdlib.h>
#include "misc.h"
#include "ogg.h"

static unsigned long mask[]=
{0x00000000,0x00000001,0x00000003,0x00000007,0x0000000f,
 0x0000001f,0x0000003f,0x0000007f,0x000000ff,0x000001ff,
 0x000003ff,0x000007ff,0x00000fff,0x00001fff,0x00003fff,
 0x00007fff,0x0000ffff,0x0001ffff,0x0003ffff,0x0007ffff,
 0x000fffff,0x001fffff,0x003fffff,0x007fffff,0x00ffffff,
 0x01ffffff,0x03ffffff,0x07ffffff,0x0fffffff,0x1fffffff,
 0x3fffffff,0x7fffffff,0xffffffff };

/* spans forward, skipping as many bytes as headend is negative; if
   headend is zero, simply finds next byte.  If we're up to the end
   of the buffer, leaves headend at zero.  If we've read past the end,
   halt the decode process. */

static void _span(oggpack_buffer *b){
  while(b->headend-(b->headbit>>3)<1){
    b->headend-=b->headbit>>3;
    b->headbit&=0x7;

    if(b->head && b->head->next){
      b->count+=b->head->length;
      b->head=b->head->next;

      if(b->headend+b->head->length>0)
 b->headptr=b->head->buffer->data+b->head->begin-b->headend;

      b->headend+=b->head->length;
    }else{
      /* we've either met the end of decode, or gone past it. halt
  only if we're past */
      if(b->headend*8<b->headbit)
 /* read has fallen off the end */
 b->headend=-1;
        break;
    }
  }
}

void oggpack_readinit(oggpack_buffer *b,ogg_reference *r){
  memset(b,0,sizeof(*b));

  b->tail=b->head=r;
  b->count=0;
  if (b->head) {
    b->headptr=b->head->buffer->data+b->head->begin;
    b->headend=b->head->length;
  } else {
    b->headptr=0;
    b->headend=0;
  }
  _span(b);
}

#define _lookspan()   while(!end){\
                        head=head->next;\
                        if(!head) return -1;\
                        ptr=head->buffer->data + head->begin;\
                        end=head->length;\
                      }

/* Read in bits without advancing the bitptr; bits <= 32 */
long oggpack_look(oggpack_buffer *b,int bits){
  unsigned long m=mask[bits];
  unsigned long ret;

  bits+=b->headbit;

  if(bits >= b->headend<<3){
    int            end=b->headend;
    unsigned char *ptr=b->headptr;
    ogg_reference *head=b->head;

    if(end<0)return -1;
    if (!head || !end)return -1;

    if(bits){
      _lookspan();
      ret=*ptr++>>b->headbit;
      if(bits>8){
        --end;
        _lookspan();
        ret|=*ptr++<<(8-b->headbit);
        if(bits>16){
          --end;
          _lookspan();
          ret|=*ptr++<<(16-b->headbit);
          if(bits>24){
            --end;
            _lookspan();
            ret|=*ptr++<<(24-b->headbit);
            if(bits>32 && b->headbit){
              --end;
              _lookspan();
              ret|=*ptr<<(32-b->headbit);
            }
          }
        }
      }
    }

  }else{

    /* make this a switch jump-table */
    ret=b->headptr[0]>>b->headbit;
    if(bits>8){
      ret|=b->headptr[1]<<(8-b->headbit);
      if(bits>16){
        ret|=b->headptr[2]<<(16-b->headbit);
        if(bits>24){
          ret|=b->headptr[3]<<(24-b->headbit);
          if(bits>32 && b->headbit)
            ret|=b->headptr[4]<<(32-b->headbit);
        }
      }
    }
  }

  ret&=m;
  return ret;
}

/* limited to 32 at a time */
void oggpack_adv(oggpack_buffer *b,int bits){
  bits+=b->headbit;
  b->headbit=bits&7;
  b->headend-=(bits>>3);
  b->headptr+=(bits>>3);
  if(b->headend<1)_span(b);
}

int oggpack_eop(oggpack_buffer *b){
  if(b->headend<0)return -1;
  return 0;
}

/* bits <= 32 */
long oggpack_read(oggpack_buffer *b,int bits){
  long ret=oggpack_look(b,bits);
  oggpack_adv(b,bits);
  return(ret);
}

long oggpack_bytes(oggpack_buffer *b){
  if(b->headend<0)return b->count+b->head->length;
  return b->count + b->head->length-b->headend +
    (b->headbit+7)/8;
}

long oggpack_bits(oggpack_buffer *b){
  if(b->headend<0)return (b->count+b->head->length)*8;
  return (b->count + b->head->length-b->headend)*8 +
    b->headbit;
}

/* Self test of the bitwise routines; everything else is based on
   them, so they damned well better be solid. */

#ifdef _V_BIT_TEST
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include "framing.c"

static int ilog(unsigned long v){
  int ret=0;
  while(v){
    ret++;
    v>>=1;
  }
  return(ret);
}

oggpack_buffer r;
oggpack_buffer o;
ogg_buffer_state *bs;
ogg_reference *or;
#define TESTWORDS 256

void report(char *in){
  fprintf(stderr,"%s",in);
  exit(1);
}

int getbyte(ogg_reference *or,int position){
  while(or && position>=or->length){
    position-=or->length;
    or=or->next;
    if(or==NULL){
      fprintf(stderr,"\n\tERROR: getbyte ran off end of buffer.\n");
      exit(1);
    }
  }

  if((position+or->begin)&1)
    return (or->buffer->data[(position+or->begin)>>1])&0xff;
  else
    return (or->buffer->data[(position+or->begin)>>1]>>8)&0xff;
}

void cliptest(unsigned long *b,int vals,int bits,int *comp,int compsize){
  long i,bitcount=0;
  ogg_reference *or=ogg_buffer_alloc(bs,64);
  for(i=0;i<compsize;i++)
    or->buffer->data[i]= comp[i];
  or->length=i;

  oggpack_readinit(&r,or);
  for(i=0;i<vals;i++){
    unsigned long test;
    int tbit=bits?bits:ilog(b[i]);
    if((test=oggpack_look(&r,tbit))==0xffffffff)
      report("out of data!\n");
    if(test!=(b[i]&mask[tbit])){
      fprintf(stderr,"%ld) %lx %lx\n",i,(b[i]&mask[tbit]),test);
      report("looked at incorrect value!\n");
    }
    if((test=oggpack_read(&r,tbit))==0xffffffff){
      report("premature end of data when reading!\n");
    }
    if(test!=(b[i]&mask[tbit])){
      fprintf(stderr,"%ld) %lx %lx\n",i,(b[i]&mask[tbit]),test);
      report("read incorrect value!\n");
    }
    bitcount+=tbit;

    if(bitcount!=oggpack_bits(&r))
      report("wrong number of bits while reading!\n");
    if((bitcount+7)/8!=oggpack_bytes(&r))
      report("wrong number of bytes while reading!\n");

  }
  if(oggpack_bytes(&r)!=(bitcount+7)/8)report("leftover bytes after read!\n");
  ogg_buffer_release(or);
}

void _end_verify(int count){
  int i;

  /* are the proper number of bits left over? */
  int leftover=count*8-oggpack_bits(&o);
  if(leftover>7)
    report("\nERROR: too many bits reported left over.\n");

  /* does reading to exactly byte alignment *not* trip EOF? */
  if(oggpack_read(&o,leftover)==-1)
    report("\nERROR: read to but not past exact end tripped EOF.\n");
  if(oggpack_bits(&o)!=count*8)
    report("\nERROR: read to but not past exact end reported bad bitcount.\n");

  /* does EOF trip properly after a single additional bit? */
  if(oggpack_read(&o,1)!=-1)
    report("\nERROR: read past exact end did not trip EOF.\n");
  if(oggpack_bits(&o)!=count*8)
    report("\nERROR: read past exact end reported bad bitcount.\n");

  /* does EOF stay set over additional bit reads? */
  for(i=0;i<=32;i++){
    if(oggpack_read(&o,i)!=-1)
      report("\nERROR: EOF did not stay set on stream.\n");
    if(oggpack_bits(&o)!=count*8)
      report("\nERROR: read past exact end reported bad bitcount.\n");
  }
}

void _end_verify2(int count){
  int i;

  /* are the proper number of bits left over? */
  int leftover=count*8-oggpack_bits(&o);
  if(leftover>7)
    report("\nERROR: too many bits reported left over.\n");

  /* does reading to exactly byte alignment *not* trip EOF? */
  oggpack_adv(&o,leftover);
  if(o.headend!=0)
    report("\nERROR: read to but not past exact end tripped EOF.\n");
  if(oggpack_bits(&o)!=count*8)
    report("\nERROR: read to but not past exact end reported bad bitcount.\n");

  /* does EOF trip properly after a single additional bit? */
  oggpack_adv(&o,1);
  if(o.headend>=0)
    report("\nERROR: read past exact end did not trip EOF.\n");
  if(oggpack_bits(&o)!=count*8)
    report("\nERROR: read past exact end reported bad bitcount.\n");

  /* does EOF stay set over additional bit reads? */
  for(i=0;i<=32;i++){
    oggpack_adv(&o,i);
    if(o.headend>=0)
      report("\nERROR: EOF did not stay set on stream.\n");
    if(oggpack_bits(&o)!=count*8)
      report("\nERROR: read past exact end reported bad bitcount.\n");
  }
}

long ogg_buffer_length(ogg_reference *or){
  int count=0;
  while(or){
    count+=or->length;
    or=or->next;
  }
  return count;
}

ogg_reference *ogg_buffer_extend(ogg_reference *or,long bytes){
  if(or){
    while(or->next){
      or=or->next;
    }
    or->next=ogg_buffer_alloc(or->buffer->ptr.owner,bytes);
    return(or->next);
  }
  return 0;
}

void ogg_buffer_posttruncate(ogg_reference *or,long pos){
  /* walk to the point where we want to begin truncate */
  while(or && pos>or->length){
    pos-=or->length;
    or=or->next;
  }
  if(or){
    ogg_buffer_release(or->next);
    or->next=0;
    or->length=pos;
  }
}

int main(void){
  long i;
  static unsigned long testbuffer1[]=
    {18,12,103948,4325,543,76,432,52,3,65,4,56,32,42,34,21,1,23,32,546,456,7,
       567,56,8,8,55,3,52,342,341,4,265,7,67,86,2199,21,7,1,5,1,4};
  int test1size=43;

  static unsigned long testbuffer2[]=
    {216531625L,1237861823,56732452,131,3212421,12325343,34547562,12313212,
       1233432,534,5,346435231,14436467,7869299,76326614,167548585,
       85525151,0,12321,1,349528352};
  int test2size=21;

  static unsigned long testbuffer3[]=
    {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,
       0,1,30,1,1,1,0,0,1,0,0,0,12,0,11,0,1,0,0,1};
  int test3size=56;

  static unsigned long large[]=
    {2136531625L,2137861823,56732452,131,3212421,12325343,34547562,12313212,
       1233432,534,5,2146435231,14436467,7869299,76326614,167548585,
       85525151,0,12321,1,2146528352};

  int onesize=33;
  static int one[33]={146,25,44,151,195,15,153,176,233,131,196,65,85,172,47,40,
                    34,242,223,136,35,222,211,86,171,50,225,135,214,75,172,
                    223,4};

  int twosize=6;
  static int two[6]={61,255,255,251,231,29};

  int threesize=54;
  static int three[54]={169,2,232,252,91,132,156,36,89,13,123,176,144,32,254,
                      142,224,85,59,121,144,79,124,23,67,90,90,216,79,23,83,
                      58,135,196,61,55,129,183,54,101,100,170,37,127,126,10,
                      100,52,4,14,18,86,77,1};

  int foursize=38;
  static int four[38]={18,6,163,252,97,194,104,131,32,1,7,82,137,42,129,11,72,
                     132,60,220,112,8,196,109,64,179,86,9,137,195,208,122,169,
                     28,2,133,0,1};

  int fivesize=45;
  static int five[45]={169,2,126,139,144,172,30,4,80,72,240,59,130,218,73,62,
                     241,24,210,44,4,20,0,248,116,49,135,100,110,130,181,169,
                     84,75,159,2,1,0,132,192,8,0,0,18,22};

  int sixsize=7;
  static int six[7]={17,177,170,242,169,19,148};

  /* Test read/write together */
  /* Later we test against pregenerated bitstreams */
  bs=ogg_buffer_create();

  fprintf(stderr,"\nSmall preclipped packing (LSb): ");
  cliptest(testbuffer1,test1size,0,one,onesize);
  fprintf(stderr,"ok.");

  fprintf(stderr,"\nNull bit call (LSb): ");
  cliptest(testbuffer3,test3size,0,two,twosize);
  fprintf(stderr,"ok.");

  fprintf(stderr,"\nLarge preclipped packing (LSb): ");
  cliptest(testbuffer2,test2size,0,three,threesize);
  fprintf(stderr,"ok.");

  fprintf(stderr,"\n32 bit preclipped packing (LSb): ");

  or=ogg_buffer_alloc(bs,128);
  for(i=0;i<test2size;i++){
    or->buffer->data[i*4]  = large[i]&0xff;
    or->buffer->data[i*4+1]  = (large[i]>>8)&0xff;
    or->buffer->data[i*4+2]  = (large[i]>>16)&0xff;
    or->buffer->data[i*4+3]  = (large[i]>>24)&0xff;
  }
  or->length=test2size*4;
  oggpack_readinit(&r,or);
  for(i=0;i<test2size;i++){
    unsigned long test;
    if((test=oggpack_look(&r,32))==0xffffffffUL)report("out of data. failed!");
    if(test!=large[i]){
      fprintf(stderr,"%ld != %ld (%lx!=%lx):",test,large[i],
              test,large[i]);
      report("read incorrect value!\n");
    }
    oggpack_adv(&r,32);
  }
  ogg_buffer_release(or);
  if(oggpack_bytes(&r)!=test2size*4)report("leftover bytes after read!\n");
  fprintf(stderr,"ok.");

  fprintf(stderr,"\nSmall unclipped packing (LSb): ");
  cliptest(testbuffer1,test1size,7,four,foursize);
  fprintf(stderr,"ok.");

  fprintf(stderr,"\nLarge unclipped packing (LSb): ");
  cliptest(testbuffer2,test2size,17,five,fivesize);
  fprintf(stderr,"ok.");

  fprintf(stderr,"\nSingle bit unclipped packing (LSb): ");
  cliptest(testbuffer3,test3size,1,six,sixsize);
  fprintf(stderr,"ok.");

  fprintf(stderr,"\nTesting read past end (LSb): ");
  {
    unsigned char dda[]={0,0,0,0};
    ogg_buffer lob={dda,8,0,{0}};
    ogg_reference lor={&lob,0,8,0};

    oggpack_readinit(&r,&lor);
    for(i=0;i<64;i++){
      if(oggpack_read(&r,1)<0){
        fprintf(stderr,"failed; got -1 prematurely.\n");
        exit(1);
      }
    }
    if(oggpack_look(&r,1)!=-1 ||
       oggpack_read(&r,1)!=-1){
      fprintf(stderr,"failed; read past end without -1.\n");
      exit(1);
    }
  }
  {
    unsigned char dda[]={0,0,0,0};
    ogg_buffer lob={dda,8,0,{0}};
    ogg_reference lor={&lob,0,8,0};
    unsigned long test;

    oggpack_readinit(&r,&lor);
    if((test=oggpack_read(&r,30))==0xffffffffUL ||
       (test=oggpack_read(&r,16))==0xffffffffUL){
      fprintf(stderr,"failed 2; got -1 prematurely.\n");
      exit(1);
    }

    if((test=oggpack_look(&r,18))==0xffffffffUL){
      fprintf(stderr,"failed 3; got -1 prematurely.\n");
      exit(1);
    }
    if((test=oggpack_look(&r,19))!=0xffffffffUL){
      fprintf(stderr,"failed; read past end without -1.\n");
      exit(1);
    }
    if((test=oggpack_look(&r,32))!=0xffffffffUL){
      fprintf(stderr,"failed; read past end without -1.\n");
      exit(1);
    }
  }
  fprintf(stderr,"ok.\n");

  /* now the scary shit: randomized testing */

  for(i=0;i<10000;i++){
    long j,count=0,count2=0,bitcount=0;
    unsigned long values[TESTWORDS];
    int len[TESTWORDS];
    unsigned char flat[4*TESTWORDS]; /* max possible needed size */

    memset(flat,0,sizeof(flat));
    fprintf(stderr,"\rRandomized testing (LSb)... (%ld)   ",10000-i);

    /* generate a list of words and lengths */
    /* write the required number of bits out to packbuffer */
    {
      long word=0;
      long bit=0;
      int k;

      for(j=0;j<TESTWORDS;j++){
 values[j]=rand();
 len[j]=(rand()%33);

 for(k=0;k<len[j];k++){
   flat[word] |= ((values[j]>>k)&0x1)<<bit;
   bit++;
   bitcount++;
   if(bit>7){
     bit=0;
     word++;
   }
 }
      }
    }
    count2=(bitcount+7)>>3;

    /* construct random-length buffer chain from flat vector; random
       byte starting offset within the length of the vector */
    {
      ogg_reference *or=NULL,*orl=NULL;
      long pos=0;

      /* build buffer chain */
      while(count2){
        int ilen=(rand()%32),k;
        int ibegin=(rand()%32);


        if(ilen>count2)ilen=count2;

        if(or)
          orl=ogg_buffer_extend(orl,64);
        else
          or=orl=ogg_buffer_alloc(bs,64);

        orl->length=ilen;
        orl->begin=ibegin;

 for(k=0;k<ilen;k++)
   orl->buffer->data[ibegin++]= flat[pos++];

        count2-=ilen;
      }

      if(ogg_buffer_length(or)!=(bitcount+7)/8){
        fprintf(stderr,"\nERROR: buffer length incorrect after build.\n");
        exit(1);
      }


      {
        int begin=0; //=(rand()%TESTWORDS);
        int ilen=(rand()%(TESTWORDS-begin));
        int bitoffset,bitcount=0;
        unsigned long temp;

        for(j=0;j<begin;j++)
          bitcount+=len[j];
        or=ogg_buffer_pretruncate(or,bitcount/8);
        bitoffset=bitcount%=8;
        for(;j<begin+ilen;j++)
          bitcount+=len[j];
        ogg_buffer_posttruncate(or,((bitcount+7)/8));

        if((count=ogg_buffer_length(or))!=(bitcount+7)/8){
          fprintf(stderr,"\nERROR: buffer length incorrect after truncate.\n");
          exit(1);
        }

        oggpack_readinit(&o,or);

        /* verify bit count */
        if(oggpack_bits(&o)!=0){
          fprintf(stderr,"\nERROR: Read bitcounter not zero!\n");
          exit(1);
        }
        if(oggpack_bytes(&o)!=0){
          fprintf(stderr,"\nERROR: Read bytecounter not zero!\n");
          exit(1);
        }

        bitcount=bitoffset;
        oggpack_read(&o,bitoffset);

        /* read and compare to original list */
        for(j=begin;j<begin+ilen;j++){
   temp=oggpack_read(&o,len[j]);
          if(temp==0xffffffffUL){
            fprintf(stderr,"\nERROR: End of stream too soon! word: %ld,%d\n",
                    j-begin,ilen);
            exit(1);
          }
          if(temp!=(values[j]&mask[len[j]])){
            fprintf(stderr,"\nERROR: Incorrect read %lx != %lx, word %ld, len %d\n"
,
                    values[j]&mask[len[j]],temp,j-begin,len[j]);
            exit(1);
          }
          bitcount+=len[j];
          if(oggpack_bits(&o)!=bitcount){
            fprintf(stderr,"\nERROR: Read bitcounter %d != %ld!\n",
                    bitcount,oggpack_bits(&o));
            exit(1);
          }
          if(oggpack_bytes(&o)!=(bitcount+7)/8){
            fprintf(stderr,"\nERROR: Read bytecounter %d != %ld!\n",
                    (bitcount+7)/8,oggpack_bytes(&o));
            exit(1);
          }

        }
        _end_verify(count);

        /* look/adv version */
        oggpack_readinit(&o,or);
        bitcount=bitoffset;
        oggpack_adv(&o,bitoffset);

        /* read and compare to original list */
        for(j=begin;j<begin+ilen;j++){
   temp=oggpack_look(&o,len[j]);

          if(temp==0xffffffffUL){
            fprintf(stderr,"\nERROR: End of stream too soon! word: %ld\n",
                    j-begin);
            exit(1);
          }
          if(temp!=(values[j]&mask[len[j]])){
            fprintf(stderr,"\nERROR: Incorrect look %lx != %lx, word %ld, len %d\n"
,
                    values[j]&mask[len[j]],temp,j-begin,len[j]);
            exit(1);
          }
   oggpack_adv(&o,len[j]);
          bitcount+=len[j];
          if(oggpack_bits(&o)!=bitcount){
            fprintf(stderr,"\nERROR: Look/Adv bitcounter %d != %ld!\n",
                    bitcount,oggpack_bits(&o));
            exit(1);
          }
          if(oggpack_bytes(&o)!=(bitcount+7)/8){
            fprintf(stderr,"\nERROR: Look/Adv bytecounter %d != %ld!\n",
                    (bitcount+7)/8,oggpack_bytes(&o));
            exit(1);
          }

        }
        _end_verify2(count);

      }
      ogg_buffer_release(or);
    }
  }
  fprintf(stderr,"\rRandomized testing (LSb)... ok.   \n");

  return(0);
}
#endif