src/bitwise.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE Ogg CONTAINER 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-2014             *
   9  * by the Xiph.Org Foundation http://www.xiph.org/                  *
  10  *                                                                  *
  11  ********************************************************************
  12
  13   function: packing variable sized words into an octet stream
  14
  15  ********************************************************************/
  16
  17 /* We're 'LSb' endian; if we write a word but read individual bits,
  18    then we'll read the lsb first */
  19
  20 #include <string.h>
  21 #include <stdlib.h>
  22 #include <limits.h>
  23 #include <ogg/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 int oggpack_writecheck(oggpack_buffer *b){
  51   if(!b->ptr || !b->storage)return -1;
  52   return 0;
  53 }
  54
  55 int oggpackB_writecheck(oggpack_buffer *b){
  56   return oggpack_writecheck(b);
  57 }
  58
  59 void oggpack_writetrunc(oggpack_buffer *b,long bits){
  60   long bytes=bits>>3;
  61   if(b->ptr){
  62     bits-=bytes*8;
  63     b->ptr=b->buffer+bytes;
  64     b->endbit=bits;
  65     b->endbyte=bytes;
  66     *b->ptr&=mask[bits];
  67   }
  68 }
  69
  70 void oggpackB_writetrunc(oggpack_buffer *b,long bits){
  71   long bytes=bits>>3;
  72   if(b->ptr){
  73     bits-=bytes*8;
  74     b->ptr=b->buffer+bytes;
  75     b->endbit=bits;
  76     b->endbyte=bytes;
  77     *b->ptr&=mask8B[bits];
  78   }
  79 }
  80
  81 /* Takes only up to 32 bits. */
  82 void oggpack_write(oggpack_buffer *b,unsigned long value,int bits){
  83   if(bits<0 || bits>32) goto err;
  84   if(b->endbyte>=b->storage-4){
  85     void *ret;
  86     if(!b->ptr)return;
  87     if(b->storage>LONG_MAX-BUFFER_INCREMENT) goto err;
  88     ret=_ogg_realloc(b->buffer,b->storage+BUFFER_INCREMENT);
  89     if(!ret) goto err;
  90     b->buffer=ret;
  91     b->storage+=BUFFER_INCREMENT;
  92     b->ptr=b->buffer+b->endbyte;
  93   }
  94
  95   value&=mask[bits];
  96   bits+=b->endbit;
  97
  98   b->ptr[0]|=value<<b->endbit;
  99
 100   if(bits>=8){
 101     b->ptr[1]=(unsigned char)(value>>(8-b->endbit));
 102     if(bits>=16){
 103       b->ptr[2]=(unsigned char)(value>>(16-b->endbit));
 104       if(bits>=24){
 105         b->ptr[3]=(unsigned char)(value>>(24-b->endbit));
 106         if(bits>=32){
 107           if(b->endbit)
 108             b->ptr[4]=(unsigned char)(value>>(32-b->endbit));
 109           else
 110             b->ptr[4]=0;
 111         }
 112       }
 113     }
 114   }
 115
 116   b->endbyte+=bits/8;
 117   b->ptr+=bits/8;
 118   b->endbit=bits&7;
 119   return;
 120  err:
 121   oggpack_writeclear(b);
 122 }
 123
 124 /* Takes only up to 32 bits. */
 125 void oggpackB_write(oggpack_buffer *b,unsigned long value,int bits){
 126   if(bits<0 || bits>32) goto err;
 127   if(b->endbyte>=b->storage-4){
 128     void *ret;
 129     if(!b->ptr)return;
 130     if(b->storage>LONG_MAX-BUFFER_INCREMENT) goto err;
 131     ret=_ogg_realloc(b->buffer,b->storage+BUFFER_INCREMENT);
 132     if(!ret) goto err;
 133     b->buffer=ret;
 134     b->storage+=BUFFER_INCREMENT;
 135     b->ptr=b->buffer+b->endbyte;
 136   }
 137
 138   value=(value&mask[bits])<<(32-bits);
 139   bits+=b->endbit;
 140
 141   b->ptr[0]|=value>>(24+b->endbit);
 142
 143   if(bits>=8){
 144     b->ptr[1]=(unsigned char)(value>>(16+b->endbit));
 145     if(bits>=16){
 146       b->ptr[2]=(unsigned char)(value>>(8+b->endbit));
 147       if(bits>=24){
 148         b->ptr[3]=(unsigned char)(value>>(b->endbit));
 149         if(bits>=32){
 150           if(b->endbit)
 151             b->ptr[4]=(unsigned char)(value<<(8-b->endbit));
 152           else
 153             b->ptr[4]=0;
 154         }
 155       }
 156     }
 157   }
 158
 159   b->endbyte+=bits/8;
 160   b->ptr+=bits/8;
 161   b->endbit=bits&7;
 162   return;
 163  err:
 164   oggpack_writeclear(b);
 165 }
 166
 167 void oggpack_writealign(oggpack_buffer *b){
 168   int bits=8-b->endbit;
 169   if(bits<8)
 170     oggpack_write(b,0,bits);
 171 }
 172
 173 void oggpackB_writealign(oggpack_buffer *b){
 174   int bits=8-b->endbit;
 175   if(bits<8)
 176     oggpackB_write(b,0,bits);
 177 }
 178
 179 static void oggpack_writecopy_helper(oggpack_buffer *b,
 180                                      void *source,
 181                                      long bits,
 182                                      void (*w)(oggpack_buffer *,
 183                                                unsigned long,
 184                                                int),
 185                                      int msb){
 186   unsigned char *ptr=(unsigned char *)source;
 187
 188   long bytes=bits/8;
 189   long pbytes=(b->endbit+bits)/8;
 190   bits-=bytes*8;
 191
 192   /* expand storage up-front */
 193   if(b->endbyte+pbytes>=b->storage){
 194     void *ret;
 195     if(!b->ptr) goto err;
 196     if(b->storage>b->endbyte+pbytes+BUFFER_INCREMENT) goto err;
 197     b->storage=b->endbyte+pbytes+BUFFER_INCREMENT;
 198     ret=_ogg_realloc(b->buffer,b->storage);
 199     if(!ret) goto err;
 200     b->buffer=ret;
 201     b->ptr=b->buffer+b->endbyte;
 202   }
 203
 204   /* copy whole octets */
 205   if(b->endbit){
 206     int i;
 207     /* unaligned copy.  Do it the hard way. */
 208     for(i=0;i<bytes;i++)
 209       w(b,(unsigned long)(ptr[i]),8);
 210   }else{
 211     /* aligned block copy */
 212     memmove(b->ptr,source,bytes);
 213     b->ptr+=bytes;
 214     b->endbyte+=bytes;
 215     *b->ptr=0;
 216   }
 217
 218   /* copy trailing bits */
 219   if(bits){
 220     if(msb)
 221       w(b,(unsigned long)(ptr[bytes]>>(8-bits)),bits);
 222     else
 223       w(b,(unsigned long)(ptr[bytes]),bits);
 224   }
 225   return;
 226  err:
 227   oggpack_writeclear(b);
 228 }
 229
 230 void oggpack_writecopy(oggpack_buffer *b,void *source,long bits){
 231   oggpack_writecopy_helper(b,source,bits,oggpack_write,0);
 232 }
 233
 234 void oggpackB_writecopy(oggpack_buffer *b,void *source,long bits){
 235   oggpack_writecopy_helper(b,source,bits,oggpackB_write,1);
 236 }
 237
 238 void oggpack_reset(oggpack_buffer *b){
 239   if(!b->ptr)return;
 240   b->ptr=b->buffer;
 241   b->buffer[0]=0;
 242   b->endbit=b->endbyte=0;
 243 }
 244
 245 void oggpackB_reset(oggpack_buffer *b){
 246   oggpack_reset(b);
 247 }
 248
 249 void oggpack_writeclear(oggpack_buffer *b){
 250   if(b->buffer)_ogg_free(b->buffer);
 251   memset(b,0,sizeof(*b));
 252 }
 253
 254 void oggpackB_writeclear(oggpack_buffer *b){
 255   oggpack_writeclear(b);
 256 }
 257
 258 void oggpack_readinit(oggpack_buffer *b,unsigned char *buf,int bytes){
 259   memset(b,0,sizeof(*b));
 260   b->buffer=b->ptr=buf;
 261   b->storage=bytes;
 262 }
 263
 264 void oggpackB_readinit(oggpack_buffer *b,unsigned char *buf,int bytes){
 265   oggpack_readinit(b,buf,bytes);
 266 }
 267
 268 /* Read in bits without advancing the bitptr; bits <= 32 */
 269 long oggpack_look(oggpack_buffer *b,int bits){
 270   unsigned long ret;
 271   unsigned long m;
 272
 273   if(bits<0 || bits>32) return -1;
 274   m=mask[bits];
 275   bits+=b->endbit;
 276
 277   if(b->endbyte >= b->storage-4){
 278     /* not the main path */
 279     if(b->endbyte > b->storage-((bits+7)>>3)) return -1;
 280     /* special case to avoid reading b->ptr[0], which might be past the end of
 281         the buffer; also skips some useless accounting */
 282     else if(!bits)return(0L);
 283   }
 284
 285   ret=b->ptr[0]>>b->endbit;
 286   if(bits>8){
 287     ret|=b->ptr[1]<<(8-b->endbit);
 288     if(bits>16){
 289       ret|=b->ptr[2]<<(16-b->endbit);
 290       if(bits>24){
 291         ret|=b->ptr[3]<<(24-b->endbit);
 292         if(bits>32 && b->endbit)
 293           ret|=b->ptr[4]<<(32-b->endbit);
 294       }
 295     }
 296   }
 297   return(m&ret);
 298 }
 299
 300 /* Read in bits without advancing the bitptr; bits <= 32 */
 301 long oggpackB_look(oggpack_buffer *b,int bits){
 302   unsigned long ret;
 303   int m=32-bits;
 304
 305   if(m<0 || m>32) return -1;
 306   bits+=b->endbit;
 307
 308   if(b->endbyte >= b->storage-4){
 309     /* not the main path */
 310     if(b->endbyte > b->storage-((bits+7)>>3)) return -1;
 311     /* special case to avoid reading b->ptr[0], which might be past the end of
 312         the buffer; also skips some useless accounting */
 313     else if(!bits)return(0L);
 314   }
 315
 316   ret=b->ptr[0]<<(24+b->endbit);
 317   if(bits>8){
 318     ret|=b->ptr[1]<<(16+b->endbit);
 319     if(bits>16){
 320       ret|=b->ptr[2]<<(8+b->endbit);
 321       if(bits>24){
 322         ret|=b->ptr[3]<<(b->endbit);
 323         if(bits>32 && b->endbit)
 324           ret|=b->ptr[4]>>(8-b->endbit);
 325       }
 326     }
 327   }
 328   return ((ret&0xffffffff)>>(m>>1))>>((m+1)>>1);
 329 }
 330
 331 long oggpack_look1(oggpack_buffer *b){
 332   if(b->endbyte>=b->storage)return(-1);
 333   return((b->ptr[0]>>b->endbit)&1);
 334 }
 335
 336 long oggpackB_look1(oggpack_buffer *b){
 337   if(b->endbyte>=b->storage)return(-1);
 338   return((b->ptr[0]>>(7-b->endbit))&1);
 339 }
 340
 341 void oggpack_adv(oggpack_buffer *b,int bits){
 342   bits+=b->endbit;
 343
 344   if(b->endbyte > b->storage-((bits+7)>>3)) goto overflow;
 345
 346   b->ptr+=bits/8;
 347   b->endbyte+=bits/8;
 348   b->endbit=bits&7;
 349   return;
 350
 351  overflow:
 352   b->ptr=NULL;
 353   b->endbyte=b->storage;
 354   b->endbit=1;
 355 }
 356
 357 void oggpackB_adv(oggpack_buffer *b,int bits){
 358   oggpack_adv(b,bits);
 359 }
 360
 361 void oggpack_adv1(oggpack_buffer *b){
 362   if(++(b->endbit)>7){
 363     b->endbit=0;
 364     b->ptr++;
 365     b->endbyte++;
 366   }
 367 }
 368
 369 void oggpackB_adv1(oggpack_buffer *b){
 370   oggpack_adv1(b);
 371 }
 372
 373 /* bits <= 32 */
 374 long oggpack_read(oggpack_buffer *b,int bits){
 375   long ret;
 376   unsigned long m;
 377
 378   if(bits<0 || bits>32) goto err;
 379   m=mask[bits];
 380   bits+=b->endbit;
 381
 382   if(b->endbyte >= b->storage-4){
 383     /* not the main path */
 384     if(b->endbyte > b->storage-((bits+7)>>3)) goto overflow;
 385     /* special case to avoid reading b->ptr[0], which might be past the end of
 386         the buffer; also skips some useless accounting */
 387     else if(!bits)return(0L);
 388   }
 389
 390   ret=b->ptr[0]>>b->endbit;
 391   if(bits>8){
 392     ret|=b->ptr[1]<<(8-b->endbit);
 393     if(bits>16){
 394       ret|=b->ptr[2]<<(16-b->endbit);
 395       if(bits>24){
 396         ret|=b->ptr[3]<<(24-b->endbit);
 397         if(bits>32 && b->endbit){
 398           ret|=b->ptr[4]<<(32-b->endbit);
 399         }
 400       }
 401     }
 402   }
 403   ret&=m;
 404   b->ptr+=bits/8;
 405   b->endbyte+=bits/8;
 406   b->endbit=bits&7;
 407   return ret;
 408
 409  overflow:
 410  err:
 411   b->ptr=NULL;
 412   b->endbyte=b->storage;
 413   b->endbit=1;
 414   return -1L;
 415 }
 416
 417 /* bits <= 32 */
 418 long oggpackB_read(oggpack_buffer *b,int bits){
 419   long ret;
 420   long m=32-bits;
 421
 422   if(m<0 || m>32) goto err;
 423   bits+=b->endbit;
 424
 425   if(b->endbyte+4>=b->storage){
 426     /* not the main path */
 427     if(b->endbyte > b->storage-((bits+7)>>3)) goto overflow;
 428     /* special case to avoid reading b->ptr[0], which might be past the end of
 429         the buffer; also skips some useless accounting */
 430     else if(!bits)return(0L);
 431   }
 432
 433   ret=b->ptr[0]<<(24+b->endbit);
 434   if(bits>8){
 435     ret|=b->ptr[1]<<(16+b->endbit);
 436     if(bits>16){
 437       ret|=b->ptr[2]<<(8+b->endbit);
 438       if(bits>24){
 439         ret|=b->ptr[3]<<(b->endbit);
 440         if(bits>32 && b->endbit)
 441           ret|=b->ptr[4]>>(8-b->endbit);
 442       }
 443     }
 444   }
 445   ret=((ret&0xffffffffUL)>>(m>>1))>>((m+1)>>1);
 446
 447   b->ptr+=bits/8;
 448   b->endbyte+=bits/8;
 449   b->endbit=bits&7;
 450   return ret;
 451
 452  overflow:
 453  err:
 454   b->ptr=NULL;
 455   b->endbyte=b->storage;
 456   b->endbit=1;
 457   return -1L;
 458 }
 459
 460 long oggpack_read1(oggpack_buffer *b){
 461   long ret;
 462
 463   if(b->endbyte >= b->storage) goto overflow;
 464   ret=(b->ptr[0]>>b->endbit)&1;
 465
 466   b->endbit++;
 467   if(b->endbit>7){
 468     b->endbit=0;
 469     b->ptr++;
 470     b->endbyte++;
 471   }
 472   return ret;
 473
 474  overflow:
 475   b->ptr=NULL;
 476   b->endbyte=b->storage;
 477   b->endbit=1;
 478   return -1L;
 479 }
 480
 481 long oggpackB_read1(oggpack_buffer *b){
 482   long ret;
 483
 484   if(b->endbyte >= b->storage) goto overflow;
 485   ret=(b->ptr[0]>>(7-b->endbit))&1;
 486
 487   b->endbit++;
 488   if(b->endbit>7){
 489     b->endbit=0;
 490     b->ptr++;
 491     b->endbyte++;
 492   }
 493   return ret;
 494
 495  overflow:
 496   b->ptr=NULL;
 497   b->endbyte=b->storage;
 498   b->endbit=1;
 499   return -1L;
 500 }
 501
 502 long oggpack_bytes(oggpack_buffer *b){
 503   return(b->endbyte+(b->endbit+7)/8);
 504 }
 505
 506 long oggpack_bits(oggpack_buffer *b){
 507   return(b->endbyte*8+b->endbit);
 508 }
 509
 510 long oggpackB_bytes(oggpack_buffer *b){
 511   return oggpack_bytes(b);
 512 }
 513
 514 long oggpackB_bits(oggpack_buffer *b){
 515   return oggpack_bits(b);
 516 }
 517
 518 unsigned char *oggpack_get_buffer(oggpack_buffer *b){
 519   return(b->buffer);
 520 }
 521
 522 unsigned char *oggpackB_get_buffer(oggpack_buffer *b){
 523   return oggpack_get_buffer(b);
 524 }
 525
 526 /* Self test of the bitwise routines; everything else is based on
 527    them, so they damned well better be solid. */
 528
 529 #ifdef _V_SELFTEST
 530 #include <stdio.h>
 531
 532 static int ilog(unsigned int v){
 533   int ret=0;
 534   while(v){
 535     ret++;
 536     v>>=1;
 537   }
 538   return(ret);
 539 }
 540
 541 oggpack_buffer o;
 542 oggpack_buffer r;
 543
 544 void report(char *in){
 545   fprintf(stderr,"%s",in);
 546   exit(1);
 547 }
 548
 549 void cliptest(unsigned long *b,int vals,int bits,int *comp,int compsize){
 550   long bytes,i;
 551   unsigned char *buffer;
 552
 553   oggpack_reset(&o);
 554   for(i=0;i<vals;i++)
 555     oggpack_write(&o,b[i],bits?bits:ilog(b[i]));
 556   buffer=oggpack_get_buffer(&o);
 557   bytes=oggpack_bytes(&o);
 558   if(bytes!=compsize)report("wrong number of bytes!\n");
 559   for(i=0;i<bytes;i++)if(buffer[i]!=comp[i]){
 560     for(i=0;i<bytes;i++)fprintf(stderr,"%x %x\n",(int)buffer[i],(int)comp[i]);
 561     report("wrote incorrect value!\n");
 562   }
 563   oggpack_readinit(&r,buffer,bytes);
 564   for(i=0;i<vals;i++){
 565     int tbit=bits?bits:ilog(b[i]);
 566     if(oggpack_look(&r,tbit)==-1)
 567       report("out of data!\n");
 568     if(oggpack_look(&r,tbit)!=(b[i]&mask[tbit]))
 569       report("looked at incorrect value!\n");
 570     if(tbit==1)
 571       if(oggpack_look1(&r)!=(b[i]&mask[tbit]))
 572         report("looked at single bit incorrect value!\n");
 573     if(tbit==1){
 574       if(oggpack_read1(&r)!=(b[i]&mask[tbit]))
 575         report("read incorrect single bit value!\n");
 576     }else{
 577     if(oggpack_read(&r,tbit)!=(b[i]&mask[tbit]))
 578       report("read incorrect value!\n");
 579     }
 580   }
 581   if(oggpack_bytes(&r)!=bytes)report("leftover bytes after read!\n");
 582 }
 583
 584 void cliptestB(unsigned long *b,int vals,int bits,int *comp,int compsize){
 585   long bytes,i;
 586   unsigned char *buffer;
 587
 588   oggpackB_reset(&o);
 589   for(i=0;i<vals;i++)
 590     oggpackB_write(&o,b[i],bits?bits:ilog(b[i]));
 591   buffer=oggpackB_get_buffer(&o);
 592   bytes=oggpackB_bytes(&o);
 593   if(bytes!=compsize)report("wrong number of bytes!\n");
 594   for(i=0;i<bytes;i++)if(buffer[i]!=comp[i]){
 595     for(i=0;i<bytes;i++)fprintf(stderr,"%x %x\n",(int)buffer[i],(int)comp[i]);
 596     report("wrote incorrect value!\n");
 597   }
 598   oggpackB_readinit(&r,buffer,bytes);
 599   for(i=0;i<vals;i++){
 600     int tbit=bits?bits:ilog(b[i]);
 601     if(oggpackB_look(&r,tbit)==-1)
 602       report("out of data!\n");
 603     if(oggpackB_look(&r,tbit)!=(b[i]&mask[tbit]))
 604       report("looked at incorrect value!\n");
 605     if(tbit==1)
 606       if(oggpackB_look1(&r)!=(b[i]&mask[tbit]))
 607         report("looked at single bit incorrect value!\n");
 608     if(tbit==1){
 609       if(oggpackB_read1(&r)!=(b[i]&mask[tbit]))
 610         report("read incorrect single bit value!\n");
 611     }else{
 612     if(oggpackB_read(&r,tbit)!=(b[i]&mask[tbit]))
 613       report("read incorrect value!\n");
 614     }
 615   }
 616   if(oggpackB_bytes(&r)!=bytes)report("leftover bytes after read!\n");
 617 }
 618
 619 void copytest(int prefill, int copy){
 620   oggpack_buffer source_write;
 621   oggpack_buffer dest_write;
 622   oggpack_buffer source_read;
 623   oggpack_buffer dest_read;
 624   unsigned char *source;
 625   unsigned char *dest;
 626   long source_bytes,dest_bytes;
 627   int i;
 628
 629   oggpack_writeinit(&source_write);
 630   oggpack_writeinit(&dest_write);
 631
 632   for(i=0;i<(prefill+copy+7)/8;i++)
 633     oggpack_write(&source_write,(i^0x5a)&0xff,8);
 634   source=oggpack_get_buffer(&source_write);
 635   source_bytes=oggpack_bytes(&source_write);
 636
 637   /* prefill */
 638   oggpack_writecopy(&dest_write,source,prefill);
 639
 640   /* check buffers; verify end byte masking */
 641   dest=oggpack_get_buffer(&dest_write);
 642   dest_bytes=oggpack_bytes(&dest_write);
 643   if(dest_bytes!=(prefill+7)/8){
 644     fprintf(stderr,"wrong number of bytes after prefill! %ld!=%d\n",dest_bytes,(prefill+7)/8);
 645     exit(1);
 646   }
 647   oggpack_readinit(&source_read,source,source_bytes);
 648   oggpack_readinit(&dest_read,dest,dest_bytes);
 649
 650   for(i=0;i<prefill;i+=8){
 651     int s=oggpack_read(&source_read,prefill-i<8?prefill-i:8);
 652     int d=oggpack_read(&dest_read,prefill-i<8?prefill-i:8);
 653     if(s!=d){
 654       fprintf(stderr,"prefill=%d mismatch! byte %d, %x!=%x\n",prefill,i/8,s,d);
 655       exit(1);
 656     }
 657   }
 658   if(prefill<dest_bytes){
 659     if(oggpack_read(&dest_read,dest_bytes-prefill)!=0){
 660       fprintf(stderr,"prefill=%d mismatch! trailing bits not zero\n",prefill);
 661       exit(1);
 662     }
 663   }
 664
 665   /* second copy */
 666   oggpack_writecopy(&dest_write,source,copy);
 667
 668   /* check buffers; verify end byte masking */
 669   dest=oggpack_get_buffer(&dest_write);
 670   dest_bytes=oggpack_bytes(&dest_write);
 671   if(dest_bytes!=(copy+prefill+7)/8){
 672     fprintf(stderr,"wrong number of bytes after prefill+copy! %ld!=%d\n",dest_bytes,(copy+prefill+7)/8);
 673     exit(1);
 674   }
 675   oggpack_readinit(&source_read,source,source_bytes);
 676   oggpack_readinit(&dest_read,dest,dest_bytes);
 677
 678   for(i=0;i<prefill;i+=8){
 679     int s=oggpack_read(&source_read,prefill-i<8?prefill-i:8);
 680     int d=oggpack_read(&dest_read,prefill-i<8?prefill-i:8);
 681     if(s!=d){
 682       fprintf(stderr,"prefill=%d mismatch! byte %d, %x!=%x\n",prefill,i/8,s,d);
 683       exit(1);
 684     }
 685   }
 686
 687   oggpack_readinit(&source_read,source,source_bytes);
 688   for(i=0;i<copy;i+=8){
 689     int s=oggpack_read(&source_read,copy-i<8?copy-i:8);
 690     int d=oggpack_read(&dest_read,copy-i<8?copy-i:8);
 691     if(s!=d){
 692       fprintf(stderr,"prefill=%d copy=%d mismatch! byte %d, %x!=%x\n",prefill,copy,i/8,s,d);
 693       exit(1);
 694     }
 695   }
 696
 697   if(copy+prefill<dest_bytes){
 698     if(oggpack_read(&dest_read,dest_bytes-copy-prefill)!=0){
 699       fprintf(stderr,"prefill=%d copy=%d mismatch! trailing bits not zero\n",prefill,copy);
 700       exit(1);
 701     }
 702   }
 703
 704   oggpack_writeclear(&source_write);
 705   oggpack_writeclear(&dest_write);
 706
 707
 708 }
 709
 710 void copytestB(int prefill, int copy){
 711   oggpack_buffer source_write;
 712   oggpack_buffer dest_write;
 713   oggpack_buffer source_read;
 714   oggpack_buffer dest_read;
 715   unsigned char *source;
 716   unsigned char *dest;
 717   long source_bytes,dest_bytes;
 718   int i;
 719
 720   oggpackB_writeinit(&source_write);
 721   oggpackB_writeinit(&dest_write);
 722
 723   for(i=0;i<(prefill+copy+7)/8;i++)
 724     oggpackB_write(&source_write,(i^0x5a)&0xff,8);
 725   source=oggpackB_get_buffer(&source_write);
 726   source_bytes=oggpackB_bytes(&source_write);
 727
 728   /* prefill */
 729   oggpackB_writecopy(&dest_write,source,prefill);
 730
 731   /* check buffers; verify end byte masking */
 732   dest=oggpackB_get_buffer(&dest_write);
 733   dest_bytes=oggpackB_bytes(&dest_write);
 734   if(dest_bytes!=(prefill+7)/8){
 735     fprintf(stderr,"wrong number of bytes after prefill! %ld!=%d\n",dest_bytes,(prefill+7)/8);
 736     exit(1);
 737   }
 738   oggpackB_readinit(&source_read,source,source_bytes);
 739   oggpackB_readinit(&dest_read,dest,dest_bytes);
 740
 741   for(i=0;i<prefill;i+=8){
 742     int s=oggpackB_read(&source_read,prefill-i<8?prefill-i:8);
 743     int d=oggpackB_read(&dest_read,prefill-i<8?prefill-i:8);
 744     if(s!=d){
 745       fprintf(stderr,"prefill=%d mismatch! byte %d, %x!=%x\n",prefill,i/8,s,d);
 746       exit(1);
 747     }
 748   }
 749   if(prefill<dest_bytes){
 750     if(oggpackB_read(&dest_read,dest_bytes-prefill)!=0){
 751       fprintf(stderr,"prefill=%d mismatch! trailing bits not zero\n",prefill);
 752       exit(1);
 753     }
 754   }
 755
 756   /* second copy */
 757   oggpackB_writecopy(&dest_write,source,copy);
 758
 759   /* check buffers; verify end byte masking */
 760   dest=oggpackB_get_buffer(&dest_write);
 761   dest_bytes=oggpackB_bytes(&dest_write);
 762   if(dest_bytes!=(copy+prefill+7)/8){
 763     fprintf(stderr,"wrong number of bytes after prefill+copy! %ld!=%d\n",dest_bytes,(copy+prefill+7)/8);
 764     exit(1);
 765   }
 766   oggpackB_readinit(&source_read,source,source_bytes);
 767   oggpackB_readinit(&dest_read,dest,dest_bytes);
 768
 769   for(i=0;i<prefill;i+=8){
 770     int s=oggpackB_read(&source_read,prefill-i<8?prefill-i:8);
 771     int d=oggpackB_read(&dest_read,prefill-i<8?prefill-i:8);
 772     if(s!=d){
 773       fprintf(stderr,"prefill=%d mismatch! byte %d, %x!=%x\n",prefill,i/8,s,d);
 774       exit(1);
 775     }
 776   }
 777
 778   oggpackB_readinit(&source_read,source,source_bytes);
 779   for(i=0;i<copy;i+=8){
 780     int s=oggpackB_read(&source_read,copy-i<8?copy-i:8);
 781     int d=oggpackB_read(&dest_read,copy-i<8?copy-i:8);
 782     if(s!=d){
 783       fprintf(stderr,"prefill=%d copy=%d mismatch! byte %d, %x!=%x\n",prefill,copy,i/8,s,d);
 784       exit(1);
 785     }
 786   }
 787
 788   if(copy+prefill<dest_bytes){
 789     if(oggpackB_read(&dest_read,dest_bytes-copy-prefill)!=0){
 790       fprintf(stderr,"prefill=%d copy=%d mismatch! trailing bits not zero\n",prefill,copy);
 791       exit(1);
 792     }
 793   }
 794
 795   oggpackB_writeclear(&source_write);
 796   oggpackB_writeclear(&dest_write);
 797
 798 }
 799
 800 int main(void){
 801   unsigned char *buffer;
 802   long bytes,i,j;
 803   static unsigned long testbuffer1[]=
 804     {18,12,103948,4325,543,76,432,52,3,65,4,56,32,42,34,21,1,23,32,546,456,7,
 805        567,56,8,8,55,3,52,342,341,4,265,7,67,86,2199,21,7,1,5,1,4};
 806   int test1size=43;
 807
 808   static unsigned long testbuffer2[]=
 809     {216531625L,1237861823,56732452,131,3212421,12325343,34547562,12313212,
 810        1233432,534,5,346435231,14436467,7869299,76326614,167548585,
 811        85525151,0,12321,1,349528352};
 812   int test2size=21;
 813
 814   static unsigned long testbuffer3[]=
 815     {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,
 816        0,1,30,1,1,1,0,0,1,0,0,0,12,0,11,0,1,0,0,1};
 817   int test3size=56;
 818
 819   static unsigned long large[]=
 820     {2136531625L,2137861823,56732452,131,3212421,12325343,34547562,12313212,
 821        1233432,534,5,2146435231,14436467,7869299,76326614,167548585,
 822        85525151,0,12321,1,2146528352};
 823
 824   int onesize=33;
 825   static int one[33]={146,25,44,151,195,15,153,176,233,131,196,65,85,172,47,40,
 826                     34,242,223,136,35,222,211,86,171,50,225,135,214,75,172,
 827                     223,4};
 828   static int oneB[33]={150,101,131,33,203,15,204,216,105,193,156,65,84,85,222,
 829                        8,139,145,227,126,34,55,244,171,85,100,39,195,173,18,
 830                        245,251,128};
 831
 832   int twosize=6;
 833   static int two[6]={61,255,255,251,231,29};
 834   static int twoB[6]={247,63,255,253,249,120};
 835
 836   int threesize=54;
 837   static int three[54]={169,2,232,252,91,132,156,36,89,13,123,176,144,32,254,
 838                       142,224,85,59,121,144,79,124,23,67,90,90,216,79,23,83,
 839                       58,135,196,61,55,129,183,54,101,100,170,37,127,126,10,
 840                       100,52,4,14,18,86,77,1};
 841   static int threeB[54]={206,128,42,153,57,8,183,251,13,89,36,30,32,144,183,
 842                          130,59,240,121,59,85,223,19,228,180,134,33,107,74,98,
 843                          233,253,196,135,63,2,110,114,50,155,90,127,37,170,104,
 844                          200,20,254,4,58,106,176,144,0};
 845
 846   int foursize=38;
 847   static int four[38]={18,6,163,252,97,194,104,131,32,1,7,82,137,42,129,11,72,
 848                      132,60,220,112,8,196,109,64,179,86,9,137,195,208,122,169,
 849                      28,2,133,0,1};
 850   static int fourB[38]={36,48,102,83,243,24,52,7,4,35,132,10,145,21,2,93,2,41,
 851                         1,219,184,16,33,184,54,149,170,132,18,30,29,98,229,67,
 852                         129,10,4,32};
 853
 854   int fivesize=45;
 855   static int five[45]={169,2,126,139,144,172,30,4,80,72,240,59,130,218,73,62,
 856                      241,24,210,44,4,20,0,248,116,49,135,100,110,130,181,169,
 857                      84,75,159,2,1,0,132,192,8,0,0,18,22};
 858   static int fiveB[45]={1,84,145,111,245,100,128,8,56,36,40,71,126,78,213,226,
 859                         124,105,12,0,133,128,0,162,233,242,67,152,77,205,77,
 860                         172,150,169,129,79,128,0,6,4,32,0,27,9,0};
 861
 862   int sixsize=7;
 863   static int six[7]={17,177,170,242,169,19,148};
 864   static int sixB[7]={136,141,85,79,149,200,41};
 865
 866   /* Test read/write together */
 867   /* Later we test against pregenerated bitstreams */
 868   oggpack_writeinit(&o);
 869
 870   fprintf(stderr,"\nSmall preclipped packing (LSb): ");
 871   cliptest(testbuffer1,test1size,0,one,onesize);
 872   fprintf(stderr,"ok.");
 873
 874   fprintf(stderr,"\nNull bit call (LSb): ");
 875   cliptest(testbuffer3,test3size,0,two,twosize);
 876   fprintf(stderr,"ok.");
 877
 878   fprintf(stderr,"\nLarge preclipped packing (LSb): ");
 879   cliptest(testbuffer2,test2size,0,three,threesize);
 880   fprintf(stderr,"ok.");
 881
 882   fprintf(stderr,"\n32 bit preclipped packing (LSb): ");
 883   oggpack_reset(&o);
 884   for(i=0;i<test2size;i++)
 885     oggpack_write(&o,large[i],32);
 886   buffer=oggpack_get_buffer(&o);
 887   bytes=oggpack_bytes(&o);
 888   oggpack_readinit(&r,buffer,bytes);
 889   for(i=0;i<test2size;i++){
 890     if(oggpack_look(&r,32)==-1)report("out of data. failed!");
 891     if(oggpack_look(&r,32)!=large[i]){
 892       fprintf(stderr,"%ld != %lu (%lx!=%lx):",oggpack_look(&r,32),large[i],
 893               oggpack_look(&r,32),large[i]);
 894       report("read incorrect value!\n");
 895     }
 896     oggpack_adv(&r,32);
 897   }
 898   if(oggpack_bytes(&r)!=bytes)report("leftover bytes after read!\n");
 899   fprintf(stderr,"ok.");
 900
 901   fprintf(stderr,"\nSmall unclipped packing (LSb): ");
 902   cliptest(testbuffer1,test1size,7,four,foursize);
 903   fprintf(stderr,"ok.");
 904
 905   fprintf(stderr,"\nLarge unclipped packing (LSb): ");
 906   cliptest(testbuffer2,test2size,17,five,fivesize);
 907   fprintf(stderr,"ok.");
 908
 909   fprintf(stderr,"\nSingle bit unclipped packing (LSb): ");
 910   cliptest(testbuffer3,test3size,1,six,sixsize);
 911   fprintf(stderr,"ok.");
 912
 913   fprintf(stderr,"\nTesting read past end (LSb): ");
 914   oggpack_readinit(&r,(unsigned char *)"\0\0\0\0\0\0\0\0",8);
 915   for(i=0;i<64;i++){
 916     if(oggpack_read(&r,1)!=0){
 917       fprintf(stderr,"failed; got -1 prematurely.\n");
 918       exit(1);
 919     }
 920   }
 921   if(oggpack_look(&r,1)!=-1 ||
 922      oggpack_read(&r,1)!=-1){
 923       fprintf(stderr,"failed; read past end without -1.\n");
 924       exit(1);
 925   }
 926   oggpack_readinit(&r,(unsigned char *)"\0\0\0\0\0\0\0\0",8);
 927   if(oggpack_read(&r,30)!=0 || oggpack_read(&r,16)!=0){
 928       fprintf(stderr,"failed 2; got -1 prematurely.\n");
 929       exit(1);
 930   }
 931
 932   if(oggpack_look(&r,18)!=0 ||
 933      oggpack_look(&r,18)!=0){
 934     fprintf(stderr,"failed 3; got -1 prematurely.\n");
 935       exit(1);
 936   }
 937   if(oggpack_look(&r,19)!=-1 ||
 938      oggpack_look(&r,19)!=-1){
 939     fprintf(stderr,"failed; read past end without -1.\n");
 940       exit(1);
 941   }
 942   if(oggpack_look(&r,32)!=-1 ||
 943      oggpack_look(&r,32)!=-1){
 944     fprintf(stderr,"failed; read past end without -1.\n");
 945       exit(1);
 946   }
 947   oggpack_writeclear(&o);
 948   fprintf(stderr,"ok.");
 949
 950   /* this is partly glassbox; we're mostly concerned about the allocation boundaries */
 951
 952   fprintf(stderr,"\nTesting aligned writecopies (LSb): ");
 953   for(i=0;i<71;i++)
 954     for(j=0;j<5;j++)
 955       copytest(j*8,i);
 956   for(i=BUFFER_INCREMENT*8-71;i<BUFFER_INCREMENT*8+71;i++)
 957     for(j=0;j<5;j++)
 958       copytest(j*8,i);
 959   fprintf(stderr,"ok.      ");
 960
 961   fprintf(stderr,"\nTesting unaligned writecopies (LSb): ");
 962   for(i=0;i<71;i++)
 963     for(j=1;j<40;j++)
 964       if(j&0x7)
 965         copytest(j,i);
 966   for(i=BUFFER_INCREMENT*8-71;i<BUFFER_INCREMENT*8+71;i++)
 967     for(j=1;j<40;j++)
 968       if(j&0x7)
 969         copytest(j,i);
 970
 971   fprintf(stderr,"ok.      \n");
 972
 973
 974   /********** lazy, cut-n-paste retest with MSb packing ***********/
 975
 976   /* Test read/write together */
 977   /* Later we test against pregenerated bitstreams */
 978   oggpackB_writeinit(&o);
 979
 980   fprintf(stderr,"\nSmall preclipped packing (MSb): ");
 981   cliptestB(testbuffer1,test1size,0,oneB,onesize);
 982   fprintf(stderr,"ok.");
 983
 984   fprintf(stderr,"\nNull bit call (MSb): ");
 985   cliptestB(testbuffer3,test3size,0,twoB,twosize);
 986   fprintf(stderr,"ok.");
 987
 988   fprintf(stderr,"\nLarge preclipped packing (MSb): ");
 989   cliptestB(testbuffer2,test2size,0,threeB,threesize);
 990   fprintf(stderr,"ok.");
 991
 992   fprintf(stderr,"\n32 bit preclipped packing (MSb): ");
 993   oggpackB_reset(&o);
 994   for(i=0;i<test2size;i++)
 995     oggpackB_write(&o,large[i],32);
 996   buffer=oggpackB_get_buffer(&o);
 997   bytes=oggpackB_bytes(&o);
 998   oggpackB_readinit(&r,buffer,bytes);
 999   for(i=0;i<test2size;i++){
1000     if(oggpackB_look(&r,32)==-1)report("out of data. failed!");
1001     if(oggpackB_look(&r,32)!=large[i]){
1002       fprintf(stderr,"%ld != %lu (%lx!=%lx):",oggpackB_look(&r,32),large[i],
1003               oggpackB_look(&r,32),large[i]);
1004       report("read incorrect value!\n");
1005     }
1006     oggpackB_adv(&r,32);
1007   }
1008   if(oggpackB_bytes(&r)!=bytes)report("leftover bytes after read!\n");
1009   fprintf(stderr,"ok.");
1010
1011   fprintf(stderr,"\nSmall unclipped packing (MSb): ");
1012   cliptestB(testbuffer1,test1size,7,fourB,foursize);
1013   fprintf(stderr,"ok.");
1014
1015   fprintf(stderr,"\nLarge unclipped packing (MSb): ");
1016   cliptestB(testbuffer2,test2size,17,fiveB,fivesize);
1017   fprintf(stderr,"ok.");
1018
1019   fprintf(stderr,"\nSingle bit unclipped packing (MSb): ");
1020   cliptestB(testbuffer3,test3size,1,sixB,sixsize);
1021   fprintf(stderr,"ok.");
1022
1023   fprintf(stderr,"\nTesting read past end (MSb): ");
1024   oggpackB_readinit(&r,(unsigned char *)"\0\0\0\0\0\0\0\0",8);
1025   for(i=0;i<64;i++){
1026     if(oggpackB_read(&r,1)!=0){
1027       fprintf(stderr,"failed; got -1 prematurely.\n");
1028       exit(1);
1029     }
1030   }
1031   if(oggpackB_look(&r,1)!=-1 ||
1032      oggpackB_read(&r,1)!=-1){
1033       fprintf(stderr,"failed; read past end without -1.\n");
1034       exit(1);
1035   }
1036   oggpackB_readinit(&r,(unsigned char *)"\0\0\0\0\0\0\0\0",8);
1037   if(oggpackB_read(&r,30)!=0 || oggpackB_read(&r,16)!=0){
1038       fprintf(stderr,"failed 2; got -1 prematurely.\n");
1039       exit(1);
1040   }
1041
1042   if(oggpackB_look(&r,18)!=0 ||
1043      oggpackB_look(&r,18)!=0){
1044     fprintf(stderr,"failed 3; got -1 prematurely.\n");
1045       exit(1);
1046   }
1047   if(oggpackB_look(&r,19)!=-1 ||
1048      oggpackB_look(&r,19)!=-1){
1049     fprintf(stderr,"failed; read past end without -1.\n");
1050       exit(1);
1051   }
1052   if(oggpackB_look(&r,32)!=-1 ||
1053      oggpackB_look(&r,32)!=-1){
1054     fprintf(stderr,"failed; read past end without -1.\n");
1055       exit(1);
1056   }
1057   fprintf(stderr,"ok.");
1058   oggpackB_writeclear(&o);
1059
1060   /* this is partly glassbox; we're mostly concerned about the allocation boundaries */
1061
1062   fprintf(stderr,"\nTesting aligned writecopies (MSb): ");
1063   for(i=0;i<71;i++)
1064     for(j=0;j<5;j++)
1065       copytestB(j*8,i);
1066   for(i=BUFFER_INCREMENT*8-71;i<BUFFER_INCREMENT*8+71;i++)
1067     for(j=0;j<5;j++)
1068       copytestB(j*8,i);
1069   fprintf(stderr,"ok.      ");
1070
1071   fprintf(stderr,"\nTesting unaligned writecopies (MSb): ");
1072   for(i=0;i<71;i++)
1073     for(j=1;j<40;j++)
1074       if(j&0x7)
1075         copytestB(j,i);
1076   for(i=BUFFER_INCREMENT*8-71;i<BUFFER_INCREMENT*8+71;i++)
1077     for(j=1;j<40;j++)
1078       if(j&0x7)
1079         copytestB(j,i);
1080
1081   fprintf(stderr,"ok.      \n\n");
1082
1083   return(0);
1084 }
1085 #endif  /* _V_SELFTEST */
1086
1087 #undef BUFFER_INCREMENT