1 /********************************************************************
3 * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE. *
4 * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
5 * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE. *
6 * PLEASE READ THESE TERMS DISTRIBUTING. *
8 * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-2000 *
9 * by Monty <monty@xiph.org> and The XIPHOPHORUS Company *
10 * http://www.xiph.org/ *
12 ********************************************************************
14 function: packing variable sized words into an octet stream
15 last mod: $Id: bitwise.c,v 1.10 2000/03/10 13:21:18 xiphmont Exp $
17 ********************************************************************/
19 /* We're 'LSb' endian; if we write a word but read individual bits,
20 then we'll read the lsb first */
27 #define BUFFER_INCREMENT 256
29 static unsigned long mask[]=
30 {0x00000000,0x00000001,0x00000003,0x00000007,0x0000000f,
31 0x0000001f,0x0000003f,0x0000007f,0x000000ff,0x000001ff,
32 0x000003ff,0x000007ff,0x00000fff,0x00001fff,0x00003fff,
33 0x00007fff,0x0000ffff,0x0001ffff,0x0003ffff,0x0007ffff,
34 0x000fffff,0x001fffff,0x003fffff,0x007fffff,0x00ffffff,
35 0x01ffffff,0x03ffffff,0x07ffffff,0x0fffffff,0x1fffffff,
36 0x3fffffff,0x7fffffff,0xffffffff };
38 void _oggpack_writeinit(oggpack_buffer *b){
39 memset(b,0,sizeof(oggpack_buffer));
40 b->ptr=b->buffer=malloc(BUFFER_INCREMENT);
42 b->storage=BUFFER_INCREMENT;
45 void _oggpack_reset(oggpack_buffer *b){
48 b->endbit=b->endbyte=0;
51 void _oggpack_writeclear(oggpack_buffer *b){
53 memset(b,0,sizeof(oggpack_buffer));
56 void _oggpack_readinit(oggpack_buffer *b,char *buf,int bytes){
57 memset(b,0,sizeof(oggpack_buffer));
62 /* Takes only up to 32 bits. */
63 void _oggpack_write(oggpack_buffer *b,unsigned long value,int bits){
64 if(b->endbyte+4>=b->storage){
65 b->buffer=realloc(b->buffer,b->storage+BUFFER_INCREMENT);
66 b->storage+=BUFFER_INCREMENT;
67 b->ptr=b->buffer+b->endbyte;
73 b->ptr[0]|=value<<b->endbit;
76 b->ptr[1]=value>>(8-b->endbit);
78 b->ptr[2]=value>>(16-b->endbit);
80 b->ptr[3]=value>>(24-b->endbit);
83 b->ptr[4]=value>>(32-b->endbit);
96 /* Read in bits without advancing the bitptr; bits <= 32 */
97 long _oggpack_look(oggpack_buffer *b,int bits){
99 unsigned long m=mask[bits];
103 if(b->endbyte+4>=b->storage){
104 /* not the main path */
105 if(b->endbyte+(bits-1)/8>=b->storage)return(-1);
108 ret=b->ptr[0]>>b->endbit;
110 ret|=b->ptr[1]<<(8-b->endbit);
112 ret|=b->ptr[2]<<(16-b->endbit);
114 ret|=b->ptr[3]<<(24-b->endbit);
115 if(bits>32 && b->endbit)
116 ret|=b->ptr[4]<<(32-b->endbit);
123 long _oggpack_look1(oggpack_buffer *b){
124 if(b->endbyte>=b->storage)return(-1);
125 return((b->ptr[0]>>b->endbit)&1);
128 void _oggpack_adv(oggpack_buffer *b,int bits){
135 void _oggpack_adv1(oggpack_buffer *b){
144 long _oggpack_read(oggpack_buffer *b,int bits){
146 unsigned long m=mask[bits];
150 if(b->endbyte+4>=b->storage){
151 /* not the main path */
153 if(b->endbyte+(bits-1)/8>=b->storage)goto overflow;
156 ret=b->ptr[0]>>b->endbit;
158 ret|=b->ptr[1]<<(8-b->endbit);
160 ret|=b->ptr[2]<<(16-b->endbit);
162 ret|=b->ptr[3]<<(24-b->endbit);
163 if(bits>32 && b->endbit){
164 ret|=b->ptr[4]<<(32-b->endbit);
179 long _oggpack_read1(oggpack_buffer *b){
182 if(b->endbyte>=b->storage){
183 /* not the main path */
188 ret=(b->ptr[0]>>b->endbit)&1;
201 long _oggpack_bytes(oggpack_buffer *b){
202 return(b->endbyte+(b->endbit+7)/8);
205 long _oggpack_bits(oggpack_buffer *b){
206 return(b->endbyte*8+b->endbit);
209 char *_oggpack_buffer(oggpack_buffer *b){
213 /* Self test of the bitwise routines; everything else is based on
214 them, so they damned well better be solid. */
219 static int ilog(unsigned int v){
231 void report(char *in){
232 fprintf(stderr,"%s",in);
236 void cliptest(unsigned long *b,int vals,int bits,int *comp,int compsize){
238 unsigned char *buffer;
242 _oggpack_write(&o,b[i],bits?bits:ilog(b[i]));
243 buffer=_oggpack_buffer(&o);
244 bytes=_oggpack_bytes(&o);
245 if(bytes!=compsize)report("wrong number of bytes!\n");
246 for(i=0;i<bytes;i++)if(buffer[i]!=comp[i]){
247 for(i=0;i<bytes;i++)fprintf(stderr,"%x %x\n",(int)buffer[i],(int)comp[i]);
248 report("wrote incorrect value!\n");
250 _oggpack_readinit(&r,buffer,bytes);
252 int tbit=bits?bits:ilog(b[i]);
253 if(_oggpack_look(&r,tbit)==-1)
254 report("out of data!\n");
255 if(_oggpack_look(&r,tbit)!=(b[i]&mask[tbit]))
256 report("looked at incorrect value!\n");
258 if(_oggpack_look1(&r)!=(b[i]&mask[tbit]))
259 report("looked at single bit incorrect value!\n");
261 if(_oggpack_read1(&r)!=(b[i]&mask[tbit]))
262 report("read incorrect single bit value!\n");
264 if(_oggpack_read(&r,tbit)!=(b[i]&mask[tbit]))
265 report("read incorrect value!\n");
268 if(_oggpack_bytes(&r)!=bytes)report("leftover bytes after read!\n");
272 unsigned char *buffer;
274 static unsigned long testbuffer1[]=
275 {18,12,103948,4325,543,76,432,52,3,65,4,56,32,42,34,21,1,23,32,546,456,7,
276 567,56,8,8,55,3,52,342,341,4,265,7,67,86,2199,21,7,1,5,1,4};
279 static unsigned long testbuffer2[]=
280 {216531625L,1237861823,56732452,131,3212421,12325343,34547562,12313212,
281 1233432,534,5,346435231,14436467,7869299,76326614,167548585,
282 85525151,0,12321,1,349528352};
285 static unsigned long large[]=
286 {2136531625L,2137861823,56732452,131,3212421,12325343,34547562,12313212,
287 1233432,534,5,2146435231,14436467,7869299,76326614,167548585,
288 85525151,0,12321,1,2146528352};
290 static unsigned long testbuffer3[]=
291 {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,
292 0,1,30,1,1,1,0,0,1,0,0,0,12,0,11,0,1,0,0,1};
296 static int one[]={146,25,44,151,195,15,153,176,233,131,196,65,85,172,47,40,
297 34,242,223,136,35,222,211,86,171,50,225,135,214,75,172,
301 static int two[]={61,255,255,251,231,29};
304 static int three[]={169,2,232,252,91,132,156,36,89,13,123,176,144,32,254,
305 142,224,85,59,121,144,79,124,23,67,90,90,216,79,23,83,
306 58,135,196,61,55,129,183,54,101,100,170,37,127,126,10,
307 100,52,4,14,18,86,77,1};
310 static int four[]={18,6,163,252,97,194,104,131,32,1,7,82,137,42,129,11,72,
311 132,60,220,112,8,196,109,64,179,86,9,137,195,208,122,169,
315 static int five[]={169,2,126,139,144,172,30,4,80,72,240,59,130,218,73,62,
316 241,24,210,44,4,20,0,248,116,49,135,100,110,130,181,169,
317 84,75,159,2,1,0,132,192,8,0,0,18,22};
320 static int six[]={17,177,170,242,169,19,148};
322 /* Test read/write together */
323 /* Later we test against pregenerated bitstreams */
324 _oggpack_writeinit(&o);
326 fprintf(stderr,"\nSmall preclipped packing: ");
327 cliptest(testbuffer1,test1size,0,one,onesize);
328 fprintf(stderr,"ok.");
330 fprintf(stderr,"\nNull bit call: ");
331 cliptest(testbuffer3,test3size,0,two,twosize);
332 fprintf(stderr,"ok.");
334 fprintf(stderr,"\nLarge preclipped packing: ");
335 cliptest(testbuffer2,test2size,0,three,threesize);
336 fprintf(stderr,"ok.");
338 fprintf(stderr,"\n32 bit preclipped packing: ");
340 for(i=0;i<test2size;i++)
341 _oggpack_write(&o,large[i],32);
342 buffer=_oggpack_buffer(&o);
343 bytes=_oggpack_bytes(&o);
344 _oggpack_readinit(&r,buffer,bytes);
345 for(i=0;i<test2size;i++){
346 if(_oggpack_look(&r,32)==-1)report("out of data. failed!");
347 if(_oggpack_look(&r,32)!=large[i]){
348 fprintf(stderr,"%ld != %ld (%lx!=%lx):",_oggpack_look(&r,32),large[i],
349 _oggpack_look(&r,32),large[i]);
350 report("read incorrect value!\n");
354 if(_oggpack_bytes(&r)!=bytes)report("leftover bytes after read!\n");
355 fprintf(stderr,"ok.");
357 fprintf(stderr,"\nSmall unclipped packing: ");
358 cliptest(testbuffer1,test1size,7,four,foursize);
359 fprintf(stderr,"ok.");
361 fprintf(stderr,"\nLarge unclipped packing: ");
362 cliptest(testbuffer2,test2size,17,five,fivesize);
363 fprintf(stderr,"ok.");
365 fprintf(stderr,"\nSingle bit unclicpped packing: ");
366 cliptest(testbuffer3,test3size,1,six,sixsize);
367 fprintf(stderr,"ok.");
369 fprintf(stderr,"\nTesting read past end: ");
370 _oggpack_readinit(&r,"\0\0\0\0\0\0\0\0",8);
372 if(_oggpack_read(&r,1)!=0){
373 fprintf(stderr,"failed; got -1 prematurely.\n");
377 if(_oggpack_look(&r,1)!=-1 ||
378 _oggpack_read(&r,1)!=-1){
379 fprintf(stderr,"failed; read past end without -1.\n");
382 _oggpack_readinit(&r,"\0\0\0\0\0\0\0\0",8);
383 if(_oggpack_read(&r,30)!=0 || _oggpack_read(&r,16)!=0){
384 fprintf(stderr,"failed 2; got -1 prematurely.\n");
388 if(_oggpack_look(&r,18)!=0 ||
389 _oggpack_look(&r,18)!=0){
390 fprintf(stderr,"failed 3; got -1 prematurely.\n");
393 if(_oggpack_look(&r,19)!=-1 ||
394 _oggpack_look(&r,19)!=-1){
395 fprintf(stderr,"failed; read past end without -1.\n");
398 if(_oggpack_look(&r,32)!=-1 ||
399 _oggpack_look(&r,32)!=-1){
400 fprintf(stderr,"failed; read past end without -1.\n");
403 fprintf(stderr,"ok.\n\n");
409 #undef BUFFER_INCREMENT