?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Nothing to see here.
[xiph/unicode.git] / tarkin / bitwise.c
blobc318c45159eae2b4860cc743acb6ed7621feddae
1 /********************************************************************
2 * *
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. *
7 * *
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/ *
11 * *
12 ********************************************************************
13
14 function: packing variable sized words into an octet stream
15 last mod: $Id: bitwise.c,v 1.1 2001/02/13 01:06:24 giles Exp $
16
17 ********************************************************************/
18
19 /* We're 'LSb' endian; if we write a word but read individual bits,
20 then we'll read the lsb first */
21
22 #include <string.h>
23 #include <stdlib.h>
24 #include "bitwise.h"
25
26 #define BUFFER_INCREMENT 256
27
28 static unsigned long mask[]=
29 {0x00000000,0x00000001,0x00000003,0x00000007,0x0000000f,
30 0x0000001f,0x0000003f,0x0000007f,0x000000ff,0x000001ff,
31 0x000003ff,0x000007ff,0x00000fff,0x00001fff,0x00003fff,
32 0x00007fff,0x0000ffff,0x0001ffff,0x0003ffff,0x0007ffff,
33 0x000fffff,0x001fffff,0x003fffff,0x007fffff,0x00ffffff,
34 0x01ffffff,0x03ffffff,0x07ffffff,0x0fffffff,0x1fffffff,
35 0x3fffffff,0x7fffffff,0xffffffff };
36
37 void _oggpack_writeinit(oggpack_buffer *b){
38 memset(b,0,sizeof(oggpack_buffer));
39 b->ptr=b->buffer=malloc(BUFFER_INCREMENT);
40 b->buffer[0]='\0';
41 b->storage=BUFFER_INCREMENT;
42 }
43
44 void _oggpack_reset(oggpack_buffer *b){
45 b->ptr=b->buffer;
46 b->buffer[0]=0;
47 b->endbit=b->endbyte=0;
48 }
49
50 void _oggpack_writeclear(oggpack_buffer *b){
51 free(b->buffer);
52 memset(b,0,sizeof(oggpack_buffer));
53 }
54
55 void _oggpack_readinit(oggpack_buffer *b,char *buf,int bytes){
56 memset(b,0,sizeof(oggpack_buffer));
57 b->buffer=b->ptr=buf;
58 b->storage=bytes;
59 }
60
61 /* Takes only up to 32 bits. */
62 void _oggpack_write(oggpack_buffer *b,unsigned long value,int bits){
63 if(b->endbyte+4>=b->storage){
64 b->buffer=realloc(b->buffer,b->storage+BUFFER_INCREMENT);
65 b->storage+=BUFFER_INCREMENT;
66 b->ptr=b->buffer+b->endbyte;
67 }
68
69 value&=mask[bits];
70 bits+=b->endbit;
71
72 b->ptr[0]|=value<<b->endbit;
73
74 if(bits>=8){
75 b->ptr[1]=value>>(8-b->endbit);
76 if(bits>=16){
77 b->ptr[2]=value>>(16-b->endbit);
78 if(bits>=24){
79 b->ptr[3]=value>>(24-b->endbit);
80 if(bits>=32){
81 if(b->endbit)
82 b->ptr[4]=value>>(32-b->endbit);
83 else
84 b->ptr[4]=0;
85 }
86 }
87 }
88 }
89
90 b->endbyte+=bits/8;
91 b->ptr+=bits/8;
92 b->endbit=bits&7;
93 }
94
95 /* Read in bits without advancing the bitptr; bits <= 32 */
96 long _oggpack_look(oggpack_buffer *b,int bits){
97 unsigned long ret;
98 unsigned long m=mask[bits];
99
100 bits+=b->endbit;
101
102 if(b->endbyte+4>=b->storage){
103 /* not the main path */
104 if(b->endbyte+(bits-1)/8>=b->storage)return(-1);
105 }
106
107 ret=b->ptr[0]>>b->endbit;
108 if(bits>8){
109 ret|=b->ptr[1]<<(8-b->endbit);
110 if(bits>16){
111 ret|=b->ptr[2]<<(16-b->endbit);
112 if(bits>24){
113 ret|=b->ptr[3]<<(24-b->endbit);
114 if(bits>32 && b->endbit)
115 ret|=b->ptr[4]<<(32-b->endbit);
116 }
117 }
118 }
119 return(m&ret);
120 }
121
122 long _oggpack_look1(oggpack_buffer *b){
123 if(b->endbyte>=b->storage)return(-1);
124 return((b->ptr[0]>>b->endbit)&1);
125 }
126
127 void _oggpack_adv(oggpack_buffer *b,int bits){
128 bits+=b->endbit;
129 b->ptr+=bits/8;
130 b->endbyte+=bits/8;
131 b->endbit=bits&7;
132 }
133
134 void _oggpack_adv1(oggpack_buffer *b){
135 if(++(b->endbit)>7){
136 b->endbit=0;
137 b->ptr++;
138 b->endbyte++;
139 }
140 }
141
142 /* bits <= 32 */
143 long _oggpack_read(oggpack_buffer *b,int bits){
144 unsigned long ret;
145 unsigned long m=mask[bits];
146
147 bits+=b->endbit;
148
149 if(b->endbyte+4>=b->storage){
150 /* not the main path */
151 ret=-1;
152 if(b->endbyte+(bits-1)/8>=b->storage)goto overflow;
153 }
154
155 ret=b->ptr[0]>>b->endbit;
156 if(bits>8){
157 ret|=b->ptr[1]<<(8-b->endbit);
158 if(bits>16){
159 ret|=b->ptr[2]<<(16-b->endbit);
160 if(bits>24){
161 ret|=b->ptr[3]<<(24-b->endbit);
162 if(bits>32 && b->endbit){
163 ret|=b->ptr[4]<<(32-b->endbit);
164 }
165 }
166 }
167 }
168 ret&=m;
169
170 overflow:
171
172 b->ptr+=bits/8;
173 b->endbyte+=bits/8;
174 b->endbit=bits&7;
175 return(ret);
176 }
177
178 long _oggpack_read1(oggpack_buffer *b){
179 unsigned long ret;
180
181 if(b->endbyte>=b->storage){
182 /* not the main path */
183 ret=-1;
184 goto overflow;
185 }
186
187 ret=(b->ptr[0]>>b->endbit)&1;
188
189 overflow:
190
191 b->endbit++;
192 if(b->endbit>7){
193 b->endbit=0;
194 b->ptr++;
195 b->endbyte++;
196 }
197 return(ret);
198 }
199
200 long _oggpack_bytes(oggpack_buffer *b){
201 return(b->endbyte+(b->endbit+7)/8);
202 }
203
204 long _oggpack_bits(oggpack_buffer *b){
205 return(b->endbyte*8+b->endbit);
206 }
207
208 char *_oggpack_buffer(oggpack_buffer *b){
209 return(b->buffer);
210 }
211
212 /* Self test of the bitwise routines; everything else is based on
213 them, so they damned well better be solid. */
214
215 #ifdef _V_SELFTEST
216 #include <stdio.h>
217
218 static int ilog(unsigned int v){
219 int ret=0;
220 while(v){
221 ret++;
222 v>>=1;
223 }
224 return(ret);
225 }
226
227 oggpack_buffer o;
228 oggpack_buffer r;
229
230 void report(char *in){
231 fprintf(stderr,in);
232 exit(1);
233 }
234
235 void cliptest(unsigned long *b,int vals,int bits,int *comp,int compsize){
236 long bytes,i;
237 unsigned char *buffer;
238
239 _oggpack_reset(&o);
240 for(i=0;i<vals;i++)
241 _oggpack_write(&o,b[i],bits?bits:ilog(b[i]));
242 buffer=_oggpack_buffer(&o);
243 bytes=_oggpack_bytes(&o);
244 if(bytes!=compsize)report("wrong number of bytes!\n");
245 for(i=0;i<bytes;i++)if(buffer[i]!=comp[i]){
246 for(i=0;i<bytes;i++)fprintf(stderr,"%x %x\n",(int)buffer[i],(int)comp[i]);
247 report("wrote incorrect value!\n");
248 }
249 _oggpack_readinit(&r,buffer,bytes);
250 for(i=0;i<vals;i++){
251 int tbit=bits?bits:ilog(b[i]);
252 if(_oggpack_look(&r,tbit)==-1)
253 report("out of data!\n");
254 if(_oggpack_look(&r,tbit)!=(b[i]&mask[tbit]))
255 report("looked at incorrect value!\n");
256 if(tbit==1)
257 if(_oggpack_look1(&r)!=(b[i]&mask[tbit]))
258 report("looked at single bit incorrect value!\n");
259 if(tbit==1){
260 if(_oggpack_read1(&r)!=(b[i]&mask[tbit]))
261 report("read incorrect single bit value!\n");
262 }else{
263 if(_oggpack_read(&r,tbit)!=(b[i]&mask[tbit]))
264 report("read incorrect value!\n");
265 }
266 }
267 if(_oggpack_bytes(&r)!=bytes)report("leftover bytes after read!\n");
268 }
269
270 int main(void){
271 unsigned char *buffer;
272 long bytes,i;
273 static unsigned long testbuffer1[]=
274 {18,12,103948,4325,543,76,432,52,3,65,4,56,32,42,34,21,1,23,32,546,456,7,
275 567,56,8,8,55,3,52,342,341,4,265,7,67,86,2199,21,7,1,5,1,4};
276 int test1size=43;
277
278 static unsigned long testbuffer2[]=
279 {216531625L,1237861823,56732452,131,3212421,12325343,34547562,12313212,
280 1233432,534,5,346435231,14436467,7869299,76326614,167548585,
281 85525151,0,12321,1,349528352};
282 int test2size=21;
283
284 static unsigned long large[]=
285 {2136531625L,2137861823,56732452,131,3212421,12325343,34547562,12313212,
286 1233432,534,5,2146435231,14436467,7869299,76326614,167548585,
287 85525151,0,12321,1,2146528352};
288
289 static unsigned long testbuffer3[]=
290 {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,
291 0,1,30,1,1,1,0,0,1,0,0,0,12,0,11,0,1,0,0,1};
292 int test3size=56;
293
294 int onesize=33;
295 static int one[]={146,25,44,151,195,15,153,176,233,131,196,65,85,172,47,40,
296 34,242,223,136,35,222,211,86,171,50,225,135,214,75,172,
297 223,4};
298
299 int twosize=6;
300 static int two[]={61,255,255,251,231,29};
301
302 int threesize=54;
303 static int three[]={169,2,232,252,91,132,156,36,89,13,123,176,144,32,254,
304 142,224,85,59,121,144,79,124,23,67,90,90,216,79,23,83,
305 58,135,196,61,55,129,183,54,101,100,170,37,127,126,10,
306 100,52,4,14,18,86,77,1};
307
308 int foursize=38;
309 static int four[]={18,6,163,252,97,194,104,131,32,1,7,82,137,42,129,11,72,
310 132,60,220,112,8,196,109,64,179,86,9,137,195,208,122,169,
311 28,2,133,0,1};
312
313 int fivesize=45;
314 static int five[]={169,2,126,139,144,172,30,4,80,72,240,59,130,218,73,62,
315 241,24,210,44,4,20,0,248,116,49,135,100,110,130,181,169,
316 84,75,159,2,1,0,132,192,8,0,0,18,22};
317
318 int sixsize=7;
319 static int six[]={17,177,170,242,169,19,148};
320
321 /* Test read/write together */
322 /* Later we test against pregenerated bitstreams */
323 _oggpack_writeinit(&o);
324
325 fprintf(stderr,"\nSmall preclipped packing: ");
326 cliptest(testbuffer1,test1size,0,one,onesize);
327 fprintf(stderr,"ok.");
328
329 fprintf(stderr,"\nNull bit call: ");
330 cliptest(testbuffer3,test3size,0,two,twosize);
331 fprintf(stderr,"ok.");
332
333 fprintf(stderr,"\nLarge preclipped packing: ");
334 cliptest(testbuffer2,test2size,0,three,threesize);
335 fprintf(stderr,"ok.");
336
337 fprintf(stderr,"\n32 bit preclipped packing: ");
338 _oggpack_reset(&o);
339 for(i=0;i<test2size;i++)
340 _oggpack_write(&o,large[i],32);
341 buffer=_oggpack_buffer(&o);
342 bytes=_oggpack_bytes(&o);
343 _oggpack_readinit(&r,buffer,bytes);
344 for(i=0;i<test2size;i++){
345 if(_oggpack_look(&r,32)==-1)report("out of data. failed!");
346 if(_oggpack_look(&r,32)!=large[i]){
347 fprintf(stderr,"%ld != %ld (%lx!=%lx):",_oggpack_look(&r,32),large[i],
348 _oggpack_look(&r,32),large[i]);
349 report("read incorrect value!\n");
350 }
351 _oggpack_adv(&r,32);
352 }
353 if(_oggpack_bytes(&r)!=bytes)report("leftover bytes after read!\n");
354 fprintf(stderr,"ok.");
355
356 fprintf(stderr,"\nSmall unclipped packing: ");
357 cliptest(testbuffer1,test1size,7,four,foursize);
358 fprintf(stderr,"ok.");
359
360 fprintf(stderr,"\nLarge unclipped packing: ");
361 cliptest(testbuffer2,test2size,17,five,fivesize);
362 fprintf(stderr,"ok.");
363
364 fprintf(stderr,"\nSingle bit unclicpped packing: ");
365 cliptest(testbuffer3,test3size,1,six,sixsize);
366 fprintf(stderr,"ok.");
367
368 fprintf(stderr,"\nTesting read past end: ");
369 _oggpack_readinit(&r,"\0\0\0\0\0\0\0\0",8);
370 for(i=0;i<64;i++){
371 if(_oggpack_read(&r,1)!=0){
372 fprintf(stderr,"failed; got -1 prematurely.\n");
373 exit(1);
374 }
375 }
376 if(_oggpack_look(&r,1)!=-1 ||
377 _oggpack_read(&r,1)!=-1){
378 fprintf(stderr,"failed; read past end without -1.\n");
379 exit(1);
380 }
381 _oggpack_readinit(&r,"\0\0\0\0\0\0\0\0",8);
382 if(_oggpack_read(&r,30)!=0 || _oggpack_read(&r,16)!=0){
383 fprintf(stderr,"failed 2; got -1 prematurely.\n");
384 exit(1);
385 }
386
387 if(_oggpack_look(&r,18)!=0 ||
388 _oggpack_look(&r,18)!=0){
389 fprintf(stderr,"failed 3; got -1 prematurely.\n");
390 exit(1);
391 }
392 if(_oggpack_look(&r,19)!=-1 ||
393 _oggpack_look(&r,19)!=-1){
394 fprintf(stderr,"failed; read past end without -1.\n");
395 exit(1);
396 }
397 if(_oggpack_look(&r,32)!=-1 ||
398 _oggpack_look(&r,32)!=-1){
399 fprintf(stderr,"failed; read past end without -1.\n");
400 exit(1);
401 }
402 fprintf(stderr,"ok.\n\n");
403
404
405 return(0);
406 }
407 #endif
408 #undef BUFFER_INCREMENT
Unicode patches for Win32