ogg2/src/bytewise.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE Ogg Reference Library 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 Ogg Reference Library SOURCE CODE IS (C) COPYRIGHT 1994-2004 *
   9  * by the Xiph.Org Foundation http://www.xiph.org/                  *
  10  *                                                                  *
  11  ********************************************************************
  12
  13   function: byte-aligned access; array-like abstraction over buffers
  14   last mod: $Id$
  15
  16  ********************************************************************/
  17
  18 #include <string.h>
  19 #include <stdlib.h>
  20 #include "ogginternal.h"
  21
  22 /* this is an internal abstraction, and it is not guarded from misuse
  23    or botching a fencepost. */
  24
  25 static void _positionB(ogg2byte_buffer *b,int pos){
  26   if(pos<b->pos){
  27     /* start at beginning, scan forward */
  28     b->ref=b->baseref;
  29     b->pos=0;
  30     b->end=b->pos+b->ref->length;
  31     b->ptr=b->ref->buffer->data+b->ref->begin;
  32   }
  33 }
  34
  35 static void _positionF(ogg2byte_buffer *b,int pos){
  36   /* scan forward for position */
  37   while(pos>=b->end){
  38     /* just seek forward */
  39     b->pos+=b->ref->length;
  40     b->ref=b->ref->next;
  41     b->end=b->ref->length+b->pos;
  42     b->ptr=b->ref->buffer->data+b->ref->begin;
  43   }
  44 }
  45
  46 static void _positionFE(ogg2byte_buffer *b,int pos){
  47   /* scan forward for position */
  48   while(pos>=b->end){
  49     if(!b->ref->next){
  50       /* perhaps just need to extend length field... */
  51       if(pos-b->pos < b->ref->buffer->size-b->ref->begin){
  52
  53         /* yes, there's space here */
  54         b->ref->length=pos-b->pos+1;
  55         b->end=b->pos+b->ref->length;
  56
  57       }else{
  58         b->ref->length=b->ref->buffer->size-b->ref->begin;
  59         /* extend the array and span */
  60         b->pos+=b->ref->length;
  61         b->ref=ogg2_buffer_extend(b->ref,OGG2PACK_CHUNKSIZE);
  62         b->end=b->pos;
  63         b->ptr=b->ref->buffer->data+b->ref->begin;
  64       }
  65
  66     }else{
  67
  68       /* just seek forward */
  69       b->pos+=b->ref->length;
  70       b->ref=b->ref->next;
  71       b->end=b->ref->length+b->pos;
  72       b->ptr=b->ref->buffer->data+b->ref->begin;
  73     }
  74   }
  75 }
  76
  77 int ogg2byte_init(ogg2byte_buffer *b,ogg2_reference *or,ogg2_buffer_state *bs){
  78   memset(b,0,sizeof(*b));
  79
  80   if(!or){
  81     if(!bs)return -1;
  82     or=ogg2_buffer_alloc(bs,OGG2PACK_CHUNKSIZE);
  83   }else{
  84     b->external=1;
  85   }
  86
  87   b->owner=bs;
  88   b->ref=b->baseref=or;
  89   b->pos=0;
  90   b->end=b->ref->length;
  91   b->ptr=b->ref->buffer->data+b->ref->begin;
  92
  93   return(0);
  94 }
  95
  96 ogg2_reference *ogg2byte_return_and_reset(ogg2byte_buffer *b){
  97   if(!b->external){
  98     ogg2_reference *ret=b->baseref;
  99     memset(b,0,sizeof(*b));
 100     return(ret);
 101   }
 102   return(NULL);
 103 }
 104
 105 void ogg2byte_clear(ogg2byte_buffer *b){
 106   if(!b->external)ogg2_buffer_release(b->baseref);
 107   memset(b,0,sizeof(*b));
 108 }
 109
 110 void ogg2byte_set1(ogg2byte_buffer *b,unsigned char val,int pos){
 111   _positionB(b,pos);
 112   _positionFE(b,pos);
 113   b->ptr[pos-b->pos]=val;
 114 }
 115
 116 void ogg2byte_set2(ogg2byte_buffer *b,int val,int pos){
 117   _positionB(b,pos);
 118   _positionFE(b,pos);
 119   b->ptr[pos-b->pos]=val;
 120   _positionFE(b,++pos);
 121   b->ptr[pos-b->pos]=val>>8;
 122 }
 123
 124 void ogg2byte_set4(ogg2byte_buffer *b,ogg_uint32_t val,int pos){
 125   int i;
 126   _positionB(b,pos);
 127   for(i=0;i<4;i++){
 128     _positionFE(b,pos);
 129     b->ptr[pos-b->pos]=val;
 130     val>>=8;
 131     ++pos;
 132   }
 133 }
 134
 135 void ogg2byte_set8(ogg2byte_buffer *b,ogg_int64_t val,int pos){
 136   int i;
 137   _positionB(b,pos);
 138   for(i=0;i<8;i++){
 139     _positionFE(b,pos);
 140     b->ptr[pos-b->pos]=val;
 141     val>>=8;
 142     ++pos;
 143   }
 144 }
 145
 146 unsigned char ogg2byte_read1(ogg2byte_buffer *b,int pos){
 147   _positionB(b,pos);
 148   _positionF(b,pos);
 149   return b->ptr[pos-b->pos];
 150 }
 151
 152 int ogg2byte_read2(ogg2byte_buffer *b,int pos){
 153   int ret;
 154   _positionB(b,pos);
 155   _positionF(b,pos);
 156   ret=b->ptr[pos-b->pos];
 157   _positionF(b,++pos);
 158   return ret|b->ptr[pos-b->pos]<<8;
 159 }
 160
 161 ogg_uint32_t ogg2byte_read4(ogg2byte_buffer *b,int pos){
 162   ogg_uint32_t ret;
 163   _positionB(b,pos);
 164   _positionF(b,pos);
 165   ret=b->ptr[pos-b->pos];
 166   _positionF(b,++pos);
 167   ret|=b->ptr[pos-b->pos]<<8;
 168   _positionF(b,++pos);
 169   ret|=b->ptr[pos-b->pos]<<16;
 170   _positionF(b,++pos);
 171   ret|=b->ptr[pos-b->pos]<<24;
 172   return ret;
 173 }
 174
 175 ogg_int64_t ogg2byte_read8(ogg2byte_buffer *b,int pos){
 176   ogg_int64_t ret;
 177   unsigned char t[7];
 178   int i;
 179   _positionB(b,pos);
 180   for(i=0;i<7;i++){
 181     _positionF(b,pos);
 182     t[i]=b->ptr[pos++ -b->pos];
 183   }
 184
 185   _positionF(b,pos);
 186   ret=b->ptr[pos-b->pos];
 187
 188   for(i=6;i>=0;--i)
 189     ret= ret<<8 | t[i];
 190
 191   return ret;
 192 }
 193
 194
 195 #ifdef _V_SELFTEST
 196
 197 #include <stdio.h>
 198 #define TESTBYTES 4096
 199
 200 unsigned char ref[TESTBYTES];
 201 unsigned char work[TESTBYTES];
 202 ogg2_buffer_state *bs;
 203
 204 void _read_linear_test1(ogg2_reference *or){
 205   ogg2byte_buffer obb;
 206   int j;
 207
 208   ogg2byte_init(&obb,or,0);
 209   for(j=0;j<TESTBYTES;j++){
 210     unsigned char ret=ogg2byte_read1(&obb,j);
 211     if(ref[j]!=ret){
 212       fprintf(stderr,"\nERROR:  %02x != %02x, position %d\n\n",
 213               ref[j],ret,j);
 214       exit(1);
 215     }
 216   }
 217 }
 218
 219 void _read_linear_test1b(ogg2_reference *or){
 220   ogg2byte_buffer obb;
 221   int j;
 222
 223   ogg2byte_init(&obb,or,0);
 224   for(j=0;j<TESTBYTES;j++){
 225     if(work[j]){
 226       unsigned char ret=ogg2byte_read1(&obb,j);
 227       if(ref[j]!=ret){
 228         fprintf(stderr,"\nERROR:  %02x != %02x, position %d\n\n",
 229                 ref[j],ret,j);
 230         exit(1);
 231       }
 232     }
 233   }
 234 }
 235
 236 void _read_linear_test2(ogg2_reference *or){
 237   ogg2byte_buffer obb;
 238   int j;
 239
 240   ogg2byte_init(&obb,or,0);
 241   for(j=0;j+1<TESTBYTES;j++){
 242     int ret=ogg2byte_read2(&obb,j);
 243     if(ref[j]!=(ret&0xff) || ref[j+1]!=((ret>>8)&0xff)){
 244       fprintf(stderr,"\nERROR:  %02x%02x != %04x, position %d\n\n",
 245               ref[j+1],ref[j],ret,j);
 246       exit(1);
 247     }
 248   }
 249 }
 250
 251 void _read_linear_test4(ogg2_reference *or){
 252   ogg2byte_buffer obb;
 253   int j;
 254
 255   ogg2byte_init(&obb,or,0);
 256
 257   for(j=0;j+3<TESTBYTES;j++){
 258     ogg_uint32_t ret=ogg2byte_read4(&obb,j);
 259     if(ref[j]!=(ret&0xff) ||
 260        ref[j+1]!=((ret>>8)&0xff) ||
 261        ref[j+2]!=((ret>>16)&0xff) ||
 262        ref[j+3]!=((ret>>24)&0xff)    ){
 263       fprintf(stderr,"\nERROR:  %02x%02x%02x%02x != %08lx, position %d\n\n",
 264               ref[j+3],ref[j+2],ref[j+1],ref[j],
 265               (unsigned long)ret,j);
 266       exit(1);
 267     }
 268   }
 269 }
 270
 271 void _read_linear_test8(ogg2_reference *or){
 272   ogg2byte_buffer obb;
 273   int j;
 274
 275   ogg2byte_init(&obb,or,0);
 276
 277   for(j=0;j+7<TESTBYTES;j++){
 278     ogg_int64_t ret=ref[j+7];
 279     ret=(ret<<8)|ref[j+6];
 280     ret=(ret<<8)|ref[j+5];
 281     ret=(ret<<8)|ref[j+4];
 282     ret=(ret<<8)|ref[j+3];
 283     ret=(ret<<8)|ref[j+2];
 284     ret=(ret<<8)|ref[j+1];
 285     ret=(ret<<8)|ref[j];
 286
 287     if(ret!=ogg2byte_read8(&obb,j)){
 288       int i;
 289       ret=ogg2byte_read8(&obb,j);
 290       fprintf(stderr,"\nERROR:  %02x%02x%02x%02x%02x%02x%02x%02x != ",
 291               ref[j+7],ref[j+6],ref[j+5],ref[j+4],
 292               ref[j+3],ref[j+2],ref[j+1],ref[j]);
 293       for(i=0;i<8;i++){
 294         ref[j+i]=ret&0xff;
 295         ret>>=8;
 296       }
 297       fprintf(stderr,"%02x%02x%02x%02x%02x%02x%02x%02x, position %d\n\n",
 298               ref[j+7],ref[j+6],ref[j+5],ref[j+4],
 299               ref[j+3],ref[j+2],ref[j+1],ref[j],
 300               j);
 301       exit(1);
 302     }
 303   }
 304 }
 305
 306 void _read_seek_test(ogg2_reference *or){
 307   ogg2byte_buffer obb;
 308   int i,j;
 309   int length=TESTBYTES;
 310   unsigned char *lref=ref;
 311
 312   ogg2byte_init(&obb,or,0);
 313
 314   for(i=0;i<TESTBYTES;i++){
 315     unsigned char ret;
 316     j=rand()%length;
 317     ret=ogg2byte_read1(&obb,j);
 318     if(lref[j]!=ret){
 319       fprintf(stderr,"\nERROR:  %02x != %02x, position %d\n\n",
 320               lref[j],ret,j);
 321       exit(1);
 322     }
 323   }
 324
 325   for(i=0;i<TESTBYTES;i++){
 326     int ret;
 327     j=rand()%(length-1);
 328     ret=ogg2byte_read2(&obb,j);
 329     if(lref[j]!=(ret&0xff) || lref[j+1]!=((ret>>8)&0xff)){
 330       fprintf(stderr,"\nERROR:  %02x%02x != %04x, position %d\n\n",
 331               lref[j+1],lref[j],ret,j);
 332       exit(1);
 333     }
 334   }
 335
 336   for(i=0;i<TESTBYTES;i++){
 337     ogg_uint32_t ret;
 338     j=rand()%(length-3);
 339     ret=ogg2byte_read4(&obb,j);
 340     if(lref[j]!=(ret&0xff) ||
 341        lref[j+1]!=((ret>>8)&0xff) ||
 342        lref[j+2]!=((ret>>16)&0xff) ||
 343        lref[j+3]!=((ret>>24)&0xff)    ){
 344       fprintf(stderr,"\nERROR:  %02x%02x%02x%02x != %08lx, position %d\n\n",
 345               lref[j+3],lref[j+2],lref[j+1],lref[j],
 346               (unsigned long)ret,j);
 347       exit(1);
 348     }
 349   }
 350
 351   for(i=0;i<TESTBYTES;i++){
 352     ogg_int64_t ret;
 353     j=rand()%(length-7);
 354     ret=lref[j+7];
 355     ret=(ret<<8)|lref[j+6];
 356     ret=(ret<<8)|lref[j+5];
 357     ret=(ret<<8)|lref[j+4];
 358     ret=(ret<<8)|lref[j+3];
 359     ret=(ret<<8)|lref[j+2];
 360     ret=(ret<<8)|lref[j+1];
 361     ret=(ret<<8)|lref[j];
 362
 363     if(ret!=ogg2byte_read8(&obb,j)){
 364       int i;
 365       ret=ogg2byte_read8(&obb,j);
 366       fprintf(stderr,"\nERROR:  %02x%02x%02x%02x%02x%02x%02x%02x != ",
 367               lref[j+7],lref[j+6],lref[j+5],lref[j+4],
 368               lref[j+3],lref[j+2],lref[j+1],lref[j]);
 369       for(i=0;i<8;i++){
 370         lref[j+i]=ret&0xff;
 371         ret>>=8;
 372       }
 373       fprintf(stderr,"%02x%02x%02x%02x%02x%02x%02x%02x, position %d\n\n",
 374               lref[j+7],lref[j+6],lref[j+5],lref[j+4],
 375               lref[j+3],lref[j+2],lref[j+1],lref[j],
 376               j);
 377       exit(1);
 378     }
 379   }
 380 }
 381
 382 void _head_prep(ogg2_reference *head){
 383   int count=0;
 384   while(head){
 385     memset(head->buffer->data,0,head->buffer->size);
 386     count+=head->length;
 387
 388     if(count>TESTBYTES/2+rand()%(TESTBYTES/4)){
 389       ogg2_buffer_release(head->next);
 390       head->next=0;
 391       break;
 392     }else{
 393       head=head->next;
 394     }
 395   }
 396 }
 397
 398 void _write_linear_test(ogg2_reference *tail){
 399   ogg2byte_buffer ob;
 400   int i;
 401
 402   _head_prep(tail);
 403   ogg2byte_init(&ob,tail,0);
 404   for(i=0;i<TESTBYTES;i++)
 405     ogg2byte_set1(&ob,ref[i],i);
 406   _read_linear_test1(tail);
 407   if(ogg2_buffer_length(tail)!=TESTBYTES){
 408     fprintf(stderr,"\nERROR: ogg2byte_set1 extended incorrectly.\n\n");
 409     exit(1);
 410   }
 411
 412   _head_prep(tail);
 413
 414   ogg2byte_init(&ob,tail,0);
 415   for(i=0;i<TESTBYTES;i+=2){
 416     unsigned int val=ref[i]|(ref[i+1]<<8);
 417     ogg2byte_set2(&ob,val,i);
 418   }
 419   _read_linear_test1(tail);
 420   if(ogg2_buffer_length(tail)>TESTBYTES){
 421     fprintf(stderr,"\nERROR: ogg2byte_set2 extended incorrectly.\n\n");
 422     exit(1);
 423   }
 424
 425   _head_prep(tail);
 426
 427   ogg2byte_init(&ob,tail,0);
 428   for(i=0;i<TESTBYTES;i+=4){
 429     unsigned long val=ref[i+2]|(ref[i+3]<<8);
 430     val=(val<<16)|ref[i]|(ref[i+1]<<8);
 431     ogg2byte_set4(&ob,val,i);
 432   }
 433   _read_linear_test1(tail);
 434   if(ogg2_buffer_length(tail)>TESTBYTES){
 435     fprintf(stderr,"\nERROR: ogg2byte_set4 extended incorrectly.\n\n");
 436     exit(1);
 437   }
 438
 439   _head_prep(tail);
 440
 441   ogg2byte_init(&ob,tail,0);
 442   for(i=0;i<TESTBYTES;i+=8){
 443     ogg_int64_t val=ref[i+6]|(ref[i+7]<<8);
 444     val=(val<<16)|ref[i+4]|(ref[i+5]<<8);
 445     val=(val<<16)|ref[i+2]|(ref[i+3]<<8);
 446     val=(val<<16)|ref[i]|(ref[i+1]<<8);
 447     ogg2byte_set8(&ob,val,i);
 448   }
 449   _read_linear_test1(tail);
 450   if(ogg2_buffer_length(tail)>TESTBYTES){
 451     fprintf(stderr,"\nERROR: ogg2byte_set8 extended incorrectly.\n\n");
 452     exit(1);
 453   }
 454
 455 }
 456
 457 void _write_zero_test(void){
 458   ogg2byte_buffer ob;
 459   int i;
 460
 461   ogg2byte_init(&ob,0,bs);
 462   for(i=0;i<TESTBYTES;i++)
 463     ogg2byte_set1(&ob,ref[i],i);
 464   _read_linear_test1(ob.baseref);
 465   if(ogg2_buffer_length(ob.baseref)!=TESTBYTES){
 466     fprintf(stderr,"\nERROR: ogg2byte_set1 extended incorrectly.\n\n");
 467     exit(1);
 468   }
 469 }
 470
 471 void _write_seek_test(void){
 472   ogg2byte_buffer ob;
 473   int i;
 474
 475   memset(work,0,TESTBYTES);
 476
 477   ogg2byte_init(&ob,0,bs);
 478
 479   for(i=0;i<TESTBYTES;i++){
 480     int j=rand()%TESTBYTES;
 481     ogg2byte_set1(&ob,ref[j],j);
 482     work[j]=1;
 483   }
 484
 485   _read_linear_test1b(ob.baseref);
 486 }
 487
 488 int main(void){
 489   int i,j;
 490   bs=ogg2_buffer_create();
 491
 492   /* test all codepaths through randomly generated data set */
 493   fprintf(stderr,"\nRandomized testing of byte aligned access abstraction: \n");
 494
 495   for(i=0;i<1000;i++){
 496
 497     /* fill reference array */
 498     for(j=0;j<TESTBYTES;j++)
 499       ref[j]=rand()%TESTBYTES;
 500
 501     /* test basic reading using single synthetic reference 1,2,4,8 */
 502     fprintf(stderr,"\r\t loops left (%d),  basic read test... ",1000-i);
 503     {
 504       ogg2_buffer ob;
 505       ogg2_reference or;
 506
 507       ob.data=ref;
 508       ob.size=TESTBYTES;
 509       or.buffer=&ob;
 510       or.begin=0;
 511       or.length=TESTBYTES;
 512
 513       _read_linear_test1(&or);
 514       _read_linear_test2(&or);
 515       _read_linear_test4(&or);
 516       _read_linear_test8(&or);
 517     }
 518
 519     /* test basic reading using multiple synthetic refs 1,2,4,8 */
 520     fprintf(stderr,"\r\t loops left (%d),  fragmented read test... ",1000-i);
 521     {
 522       ogg2_reference *tail=0;
 523       ogg2_reference *head=0;
 524       long count=0;
 525
 526
 527       while(count<TESTBYTES){
 528         int begin=rand()%32;
 529         int length=rand()%32;
 530         int pad=rand()%32;
 531
 532         if(length>TESTBYTES-count)length=TESTBYTES-count;
 533
 534         if(tail)
 535           head=ogg2_buffer_extend(head,begin+length+pad);
 536         else
 537           tail=head=ogg2_buffer_alloc(bs,begin+length+pad);
 538
 539         memcpy(head->buffer->data+begin,ref+count,length);
 540         head->begin=begin;
 541         head->length=length;
 542
 543         count+=length;
 544       }
 545
 546       _read_linear_test1(tail);
 547       _read_linear_test2(tail);
 548       _read_linear_test4(tail);
 549       _read_linear_test8(tail);
 550       /* test reading with random seek using multiple synthetic refs */
 551       fprintf(stderr,"\r\t loops left (%d),  nonsequential read test... ",1000-i);
 552       _read_seek_test(tail);
 553
 554       /* test writing, starting at offset zero in already built reference */
 555       fprintf(stderr,"\r\t loops left (%d),  linear write test...       ",1000-i);
 556       _write_linear_test(tail);
 557
 558       ogg2_buffer_release(tail);
 559     }
 560
 561     /* test writing, init blank reference */
 562     fprintf(stderr,"\r\t loops left (%d),  zero-start write test...   ",1000-i);
 563     _write_zero_test();
 564
 565     /* random writing, init blank ref */
 566     fprintf(stderr,"\r\t loops left (%d),  random-offset write test...   ",1000-i);
 567
 568     _write_seek_test();
 569
 570
 571   }
 572   fprintf(stderr,"\r\t all tests ok.                                              \n\n");
 573   ogg2_buffer_destroy(bs);
 574   return 0;
 575 }
 576
 577 #endif