1 /********************************************************************
2 * This file was modified from the libogg distribution for *
3 * inclusion into libkate *
4 ********************************************************************/
5
6 /********************************************************************
7 * *
8 * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE. *
9 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS *
10 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
11 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. *
12 * *
13 * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2002 *
14 * by the Xiph.Org Foundation http://www.xiph.org/ *
15 * *
16 ********************************************************************
17
18 function: packing variable sized words into an octet stream
19 last mod: $Id: kate_bitwise.c,v 1.3 2008/08/05 20:14:21 lyrian Exp $
20
21 ********************************************************************/
22
23 /* We're 'LSb' endian; if we write a word but read individual bits,
24 then we'll read the lsb first */
25
26 #define KATE_INTERNAL
27 #include "kate_internal.h"
28
29 #ifdef HAVE_STRING_H
30 #include <string.h>
31 #endif
32 #ifdef HAVE_STDLIB_H
33 #include <stdlib.h>
34 #endif
35 #include "kate_bitwise.h"
36
37 #define BUFFER_INCREMENT 256
38
39 static const unsigned long mask[]=
40 {0x00000000,0x00000001,0x00000003,0x00000007,0x0000000f,
41 0x0000001f,0x0000003f,0x0000007f,0x000000ff,0x000001ff,
42 0x000003ff,0x000007ff,0x00000fff,0x00001fff,0x00003fff,
43 0x00007fff,0x0000ffff,0x0001ffff,0x0003ffff,0x0007ffff,
44 0x000fffff,0x001fffff,0x003fffff,0x007fffff,0x00ffffff,
45 0x01ffffff,0x03ffffff,0x07ffffff,0x0fffffff,0x1fffffff,
46 0x3fffffff,0x7fffffff,0xffffffff };
47
kate_pack_writeinit(kate_pack_buffer * b)48 void kate_pack_writeinit(kate_pack_buffer *b){
49 memset(b,0,sizeof(*b));
50 b->ptr=b->buffer=kate_malloc(BUFFER_INCREMENT);
51 b->buffer[0]='\0';
52 b->storage=BUFFER_INCREMENT;
53 }
54
kate_pack_writetrunc(kate_pack_buffer * b,long bits)55 void kate_pack_writetrunc(kate_pack_buffer *b,long bits){
56 long bytes=bits>>3;
57 bits-=bytes*8;
58 b->ptr=b->buffer+bytes;
59 b->endbit=bits;
60 b->endbyte=bytes;
61 *b->ptr&=mask[bits];
62 }
63
64 /* Takes only up to 32 bits. */
kate_pack_write(kate_pack_buffer * b,unsigned long value,int bits)65 void kate_pack_write(kate_pack_buffer *b,unsigned long value,int bits){
66 if(b->endbyte+4>=b->storage){
67 b->buffer=kate_realloc(b->buffer,b->storage+BUFFER_INCREMENT);
68 b->storage+=BUFFER_INCREMENT;
69 b->ptr=b->buffer+b->endbyte;
70 }
71
72 value&=mask[bits];
73 bits+=b->endbit;
74
75 b->ptr[0]|=value<<b->endbit;
76
77 if(bits>=8){
78 b->ptr[1]=(unsigned char)(value>>(8-b->endbit));
79 if(bits>=16){
80 b->ptr[2]=(unsigned char)(value>>(16-b->endbit));
81 if(bits>=24){
82 b->ptr[3]=(unsigned char)(value>>(24-b->endbit));
83 if(bits>=32){
84 if(b->endbit)
85 b->ptr[4]=(unsigned char)(value>>(32-b->endbit));
86 else
87 b->ptr[4]=0;
88 }
89 }
90 }
91 }
92
93 b->endbyte+=bits/8;
94 b->ptr+=bits/8;
95 b->endbit=bits&7;
96 }
97
kate_pack_writealign(kate_pack_buffer * b)98 void kate_pack_writealign(kate_pack_buffer *b){
99 int bits=8-b->endbit;
100 if(bits<8)
101 kate_pack_write(b,0,bits);
102 }
103
kate_pack_writecopy_helper(kate_pack_buffer * b,void * source,long bits,void (* w)(kate_pack_buffer *,unsigned long,int),int msb)104 static void kate_pack_writecopy_helper(kate_pack_buffer *b,
105 void *source,
106 long bits,
107 void (*w)(kate_pack_buffer *,
108 unsigned long,
109 int),
110 int msb){
111 unsigned char *ptr=(unsigned char *)source;
112
113 long bytes=bits/8;
114 bits-=bytes*8;
115
116 if(b->endbit){
117 int i;
118 /* unaligned copy. Do it the hard way. */
119 for(i=0;i<bytes;i++)
120 w(b,(unsigned long)(ptr[i]),8);
121 }else{
122 /* aligned block copy */
123 if(b->endbyte+bytes+1>=b->storage){
124 b->storage=b->endbyte+bytes+BUFFER_INCREMENT;
125 b->buffer=kate_realloc(b->buffer,b->storage);
126 b->ptr=b->buffer+b->endbyte;
127 }
128
129 memmove(b->ptr,source,bytes);
130 b->ptr+=bytes;
131 b->endbyte+=bytes;
132 *b->ptr=0;
133
134 }
135 if(bits){
136 if(msb)
137 w(b,(unsigned long)(ptr[bytes]>>(8-bits)),bits);
138 else
139 w(b,(unsigned long)(ptr[bytes]),bits);
140 }
141 }
142
kate_pack_writecopy(kate_pack_buffer * b,void * source,long bits)143 void kate_pack_writecopy(kate_pack_buffer *b,void *source,long bits){
144 kate_pack_writecopy_helper(b,source,bits,kate_pack_write,0);
145 }
146
kate_pack_reset(kate_pack_buffer * b)147 void kate_pack_reset(kate_pack_buffer *b){
148 b->ptr=b->buffer;
149 b->buffer[0]=0;
150 b->endbit=b->endbyte=0;
151 }
152
kate_pack_writeclear(kate_pack_buffer * b)153 void kate_pack_writeclear(kate_pack_buffer *b){
154 kate_free(b->buffer);
155 memset(b,0,sizeof(*b));
156 }
157
kate_pack_readinit(kate_pack_buffer * b,unsigned char * buf,int bytes)158 void kate_pack_readinit(kate_pack_buffer *b,unsigned char *buf,int bytes){
159 memset(b,0,sizeof(*b));
160 b->buffer=b->ptr=buf;
161 b->storage=bytes;
162 }
163
164 /* Read in bits without advancing the bitptr; bits <= 32 */
kate_pack_look(kate_pack_buffer * b,int bits)165 long kate_pack_look(kate_pack_buffer *b,int bits){
166 unsigned long ret;
167 unsigned long m=mask[bits];
168
169 bits+=b->endbit;
170
171 if(b->endbyte+4>=b->storage){
172 /* not the main path */
173 if(b->endbyte*8+bits>b->storage*8)return(-1);
174 }
175
176 ret=b->ptr[0]>>b->endbit;
177 if(bits>8){
178 ret|=b->ptr[1]<<(8-b->endbit);
179 if(bits>16){
180 ret|=b->ptr[2]<<(16-b->endbit);
181 if(bits>24){
182 ret|=b->ptr[3]<<(24-b->endbit);
183 if(bits>32 && b->endbit)
184 ret|=b->ptr[4]<<(32-b->endbit);
185 }
186 }
187 }
188 return(m&ret);
189 }
190
kate_pack_look1(kate_pack_buffer * b)191 long kate_pack_look1(kate_pack_buffer *b){
192 if(b->endbyte>=b->storage)return(-1);
193 return((b->ptr[0]>>b->endbit)&1);
194 }
195
kate_pack_adv(kate_pack_buffer * b,int bits)196 void kate_pack_adv(kate_pack_buffer *b,int bits){
197 bits+=b->endbit;
198 b->ptr+=bits/8;
199 b->endbyte+=bits/8;
200 b->endbit=bits&7;
201 }
202
kate_pack_adv1(kate_pack_buffer * b)203 void kate_pack_adv1(kate_pack_buffer *b){
204 if(++(b->endbit)>7){
205 b->endbit=0;
206 b->ptr++;
207 b->endbyte++;
208 }
209 }
210
211 /* bits <= 32 */
kate_pack_read(kate_pack_buffer * b,int bits)212 long kate_pack_read(kate_pack_buffer *b,int bits){
213 long ret;
214 unsigned long m=mask[bits];
215
216 bits+=b->endbit;
217
218 if(b->endbyte+4>=b->storage){
219 /* not the main path */
220 ret=-1L;
221 if(b->endbyte*8+bits>b->storage*8)goto overflow;
222 }
223
224 ret=b->ptr[0]>>b->endbit;
225 if(bits>8){
226 ret|=b->ptr[1]<<(8-b->endbit);
227 if(bits>16){
228 ret|=b->ptr[2]<<(16-b->endbit);
229 if(bits>24){
230 ret|=b->ptr[3]<<(24-b->endbit);
231 if(bits>32 && b->endbit){
232 ret|=b->ptr[4]<<(32-b->endbit);
233 }
234 }
235 }
236 }
237 ret&=m;
238
239 overflow:
240
241 b->ptr+=bits/8;
242 b->endbyte+=bits/8;
243 b->endbit=bits&7;
244 return(ret);
245 }
246
kate_pack_read1(kate_pack_buffer * b)247 long kate_pack_read1(kate_pack_buffer *b){
248 long ret;
249
250 if(b->endbyte>=b->storage){
251 /* not the main path */
252 ret=-1L;
253 goto overflow;
254 }
255
256 ret=(b->ptr[0]>>b->endbit)&1;
257
258 overflow:
259
260 b->endbit++;
261 if(b->endbit>7){
262 b->endbit=0;
263 b->ptr++;
264 b->endbyte++;
265 }
266 return(ret);
267 }
268
kate_pack_bytes(kate_pack_buffer * b)269 long kate_pack_bytes(kate_pack_buffer *b){
270 return(b->endbyte+(b->endbit+7)/8);
271 }
272
kate_pack_bits(kate_pack_buffer * b)273 long kate_pack_bits(kate_pack_buffer *b){
274 return(b->endbyte*8+b->endbit);
275 }
276
kate_pack_get_buffer(kate_pack_buffer * b)277 unsigned char *kate_pack_get_buffer(kate_pack_buffer *b){
278 return(b->buffer);
279 }
280
kate_pack_readable_bits(kate_pack_buffer * b)281 long kate_pack_readable_bits(kate_pack_buffer *b){
282 return b->storage*8-kate_pack_bits(b);
283 }
284
285 #undef BUFFER_INCREMENT
286