/********************************************************************
* *
* 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