1 /* Copyright 1994 NEC Corporation, Tokyo, Japan.
2 *
3 * Permission to use, copy, modify, distribute and sell this software
4 * and its documentation for any purpose is hereby granted without
5 * fee, provided that the above copyright notice appear in all copies
6 * and that both that copyright notice and this permission notice
7 * appear in supporting documentation, and that the name of NEC
8 * Corporation not be used in advertising or publicity pertaining to
9 * distribution of the software without specific, written prior
10 * permission. NEC Corporation makes no representations about the
11 * suitability of this software for any purpose. It is provided "as
12 * is" without express or implied warranty.
13 *
14 * NEC CORPORATION DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
15 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
16 * NO EVENT SHALL NEC CORPORATION BE LIABLE FOR ANY SPECIAL, INDIRECT OR
17 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
18 * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
19 * OTHER TORTUOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
20 * PERFORMANCE OF THIS SOFTWARE.
21 */
22
23 #if !defined(lint) && !defined(__CODECENTER__)
24 static char rcsid[]="$Id: bits.c,v 1.2 2003/09/17 08:50:52 aida_s Exp $";
25 #endif
26 /* LINTLIBRARY */
27
28 #include "RKintern.h"
29
30 /*
31 * PackBits
32 */
33 #define BIT_UNIT 8
34
35 /*
36 �ؽ��ե������ѥӥå�������
37
38 �ؽ����ե��åȤξ���Ǥ�������������ӥåȤ�����Ȥ����ݻ����롣
39
40 ����� 1 2 3 4 5 6 7 8 9 ... n
41 �ӥå��� 2 3 3 4 4 4 4 5 5 log(n) + 1
42
43 RkPackBits �� unsigned ������ο��� dst_bits �� dst_offset(�ӥåȤ�
44 �������)���褫���Ǽ���롣ü�����Ф����ϲ��̥ӥåȤ���Ȥ��롣
45
46 ����
47 dst_bits -- �ӥå�����ؤΥݥ���
48 dst_offset -- �ºݤ˥�����������Ȥ���ޤǤΥ��ե��å�(�ӥåȤǥ������)
49 bit_size -- �ӥå�����Σ��Ĥ����ǤΥӥå���
50 src_ints -- ��Ǽ���������ͤ�����
51 count -- ��Ǽ��������
52
53 �����
54
55 */
56
57 long
_RkPackBits(dst_bits,dst_offset,bit_size,src_ints,count)58 _RkPackBits(dst_bits, dst_offset, bit_size, src_ints, count)
59 unsigned char *dst_bits;
60 long dst_offset;
61 int bit_size;
62 unsigned *src_ints;
63 int count;
64 {
65 unsigned char *dstB;
66 unsigned dstQ;
67 unsigned dstCount;
68 unsigned bitMask;
69
70 dstB = dst_bits + dst_offset / BIT_UNIT;
71 dstCount = (dst_offset % BIT_UNIT);
72
73 /* ����ʤΤǡ�����դ��ʤ���ʬ�����뤳�Ȥ���� */
74 dstQ = *dstB & ((1 << dstCount) - 1);
75 bitMask = (1 << bit_size) - 1;
76 while (count-- > 0) {
77 dstQ |= (*src_ints++ & bitMask) << dstCount;
78 dstCount += bit_size;
79 dst_offset += bit_size;
80 while (dstCount >= BIT_UNIT) {
81 *dstB++ = dstQ & ((1 << BIT_UNIT) - 1);
82 dstQ >>= BIT_UNIT;
83 dstCount -= BIT_UNIT;
84 }
85 }
86 if (dstCount) {
87 *dstB = (*dstB & ~((1 << dstCount) - 1)) | (dstQ & ((1 << dstCount) - 1));
88 }
89 return dst_offset;
90 }
91
92 /*
93 UnpackBits
94
95 RkUnpackBits �� dst_bits �� dst_offset(�ӥåȤǥ������)�˳�Ǽ�����
96 ����ӥåȤ������ unsigned ������˼��Ф���offset ��ü�����Ф���
97 ��ϲ��̥ӥåȤ���Ȥ��롣
98
99 ����
100 dst_ints -- ���Ф������ͤ��Ǽ��������ؤΥݥ���
101 src_bits -- �ӥå�����ؤΥݥ���
102 src_offset -- �ºݤ˳�Ǽ����Ȥ���ޤǤΥ��ե��å�(�ӥåȤǥ������)
103 bit_size -- �ӥå�����Σ��Ĥ����ǤΥӥå���
104 count -- ����������
105
106 �����
107
108 */
109
110 long
_RkUnpackBits(dst_ints,src_bits,src_offset,bit_size,count)111 _RkUnpackBits(dst_ints, src_bits, src_offset, bit_size, count)
112 unsigned *dst_ints;
113 unsigned char *src_bits;
114 long src_offset;
115 int bit_size;
116 int count;
117 {
118 unsigned char *srcB;
119 unsigned srcQ;
120 unsigned srcCount;
121 unsigned bitMask;
122
123 srcB = src_bits + src_offset / BIT_UNIT;
124 srcCount = BIT_UNIT - (src_offset % BIT_UNIT);
125 srcQ = *srcB++ >> (src_offset % BIT_UNIT);
126 bitMask = (1 << bit_size) - 1;
127 while (count-- > 0) {
128 while (srcCount < (unsigned)bit_size) {
129 srcQ |= (*srcB++ << srcCount);
130 srcCount += BIT_UNIT;
131 }
132 *dst_ints++ = srcQ & bitMask;
133 srcQ >>= bit_size;
134 srcCount -= bit_size;
135 src_offset += bit_size;
136 }
137 return src_offset;
138 }
139
140 /*
141 CopyBits
142
143 RkCopyBits �� src_bits �� src_offset �˳�Ǽ����Ƥ���ӥå������
144 count �Ĥ��� dst_bits �� dst_offset�˰�ư�����롣
145
146 ����
147 dst_bits -- ��ư��ӥå�����ؤΥݥ���
148 dst_offset -- �ºݤ˳�Ǽ����Ȥ���ޤǤΥ��ե��å�(�ӥåȤǥ������)
149 bit_size -- �ӥå�����Σ��Ĥ����ǤΥӥå���
150 src_bits -- ��ư���ӥå�����ؤΥݥ���
151 src_offset -- ���Ф��Ȥ���ޤǤΥ��ե��å�(�ӥåȤǥ������)
152 count -- ��ư��������
153
154 �����
155
156 */
157
158 long
_RkCopyBits(dst_bits,dst_offset,bit_size,src_bits,src_offset,count)159 _RkCopyBits(dst_bits, dst_offset, bit_size, src_bits, src_offset, count)
160 unsigned char *dst_bits;
161 long dst_offset;
162 int bit_size;
163 unsigned char *src_bits;
164 long src_offset;
165 int count;
166 {
167 unsigned char *dstB;
168 unsigned dstQ;
169 unsigned dstCount;
170 unsigned char *srcB;
171 unsigned srcQ;
172 unsigned srcCount;
173 unsigned bitMask;
174 unsigned bits;
175
176 dstB = dst_bits + dst_offset / BIT_UNIT;
177 dstCount = (dst_offset % BIT_UNIT);
178 dstQ = *dstB & ((1 << dstCount) - 1);
179 srcB = src_bits + src_offset / BIT_UNIT;
180 srcCount = BIT_UNIT - (src_offset % BIT_UNIT);
181 srcQ = *srcB++ >> (src_offset % BIT_UNIT);
182 bitMask = (1 << bit_size) - 1;
183 while (count-- > 0) {
184 /* unpack */
185 while (srcCount < (unsigned)bit_size) {
186 srcQ |= (*srcB++ << srcCount);
187 srcCount += BIT_UNIT;
188 }
189 bits = srcQ & bitMask;
190 srcQ >>= bit_size;
191 srcCount -= bit_size;
192 src_offset += bit_size;
193 /* pack */
194 dstQ |= bits << dstCount;
195 dstCount += bit_size;
196 dst_offset += bit_size;
197 while (dstCount >= BIT_UNIT) {
198 *dstB++ = dstQ & ((1 << BIT_UNIT) - 1);
199 dstQ >>= BIT_UNIT;
200 dstCount -= BIT_UNIT;
201 }
202 }
203 if (dstCount) {
204 *dstB = (*dstB & ~((1 << dstCount) - 1)) | (dstQ & ((1 << dstCount) - 1));
205 }
206 return dst_offset;
207 }
208
209 /*
210 _RkSetBitNum
211
212 _RkSetBitNum �� bit ����� offset ���֤��� n ���ܤ��ͤȤ��� val ���
213 Ǽ����ؿ��Ǥ��롣
214
215 ����
216 dst_bits -- �ӥå�����ؤΥݥ���
217 dst_offset -- �ºݤ˳�Ǽ����Ȥ���ޤǤΥ��ե��å�(�ӥåȤǥ������)
218 bit_size -- �ӥå�����Σ��Ĥ����ǤΥӥå���
219 n -- ��Ƭ���鲿���ܤ����Ǥ���Ϳ���롣
220 val -- ��Ǽ�����ͤ�Ϳ���롣
221
222 �����
223
224 */
225
226 int
_RkSetBitNum(dst_bits,dst_offset,bit_size,n,val)227 _RkSetBitNum(dst_bits, dst_offset, bit_size, n, val)
228 unsigned char *dst_bits;
229 unsigned long dst_offset;
230 int bit_size, n, val;
231 {
232 unsigned char *dstB;
233 unsigned dstQ, dstCount, bitMask;
234
235 dst_offset += bit_size * n;
236
237 dstB = dst_bits + dst_offset / BIT_UNIT;
238 dstCount = (dst_offset % BIT_UNIT);
239
240 /* ����ʤΤǡ�����դ��ʤ���ʬ�����뤳�Ȥ���� */
241 dstQ = *dstB & ((1 << dstCount) - 1);
242 bitMask = (1 << bit_size) - 1;
243
244 dstQ |= (val & bitMask) << dstCount;
245 dstCount += bit_size;
246 dst_offset += bit_size;
247 while (dstCount >= BIT_UNIT) {
248 *dstB++ = dstQ & ((1 << BIT_UNIT) - 1);
249 dstQ >>= BIT_UNIT;
250 dstCount -= BIT_UNIT;
251 }
252 if (dstCount) {
253 *dstB = (*dstB & ~((1 << dstCount) - 1)) | (dstQ & ((1 << dstCount) - 1));
254 }
255 return dst_offset;
256 }
257
258 int
_RkCalcFqSize(n)259 _RkCalcFqSize(n)
260 int n;
261 {
262 return n*(_RkCalcLog2(n) + 1);
263 }
264
265 #ifdef __BITS_DEBUG__
266 #include <stdio.h>
_RkPrintPackedBits(bits,offset,bit_size,count)267 _RkPrintPackedBits(bits, offset, bit_size, count)
268 unsigned char *bits;
269 int offset;
270 int bit_size;
271 int count;
272 {
273 fprintf(stderr, "%d <", count);
274 while ( count-- > 0 ) {
275 unsigned w;
276
277 offset = _RkUnpackBits(&w, bits, offset, bit_size, 1);
278 fprintf(stderr, " %d", w/2);
279 };
280 fprintf(stderr, ">\n");
281 }
282
283 int
_RkCalcLog2(n)284 _RkCalcLog2(n)
285 int n;
286 {
287 int lg2;
288
289 n--;
290 for (lg2 = 0; n > 0; lg2++)
291 n >>= 1;
292 return(lg2);
293 }
294
main()295 main()
296 {
297 int offset;
298 int bit_size;
299 int size;
300 unsigned char bits[1024*8];
301 unsigned char Bits[1024*8];
302 int c, i;
303 int ec;
304 int o;
305
306 /* create test run */
307 for ( size = 1; size <= 32; size++ ) {
308 bit_size = _RkCalcLog2(size) + 1;
309 printf("#%4d/%2d\t", size, bit_size);
310 /* pack 'em all */
311 o = 0;
312 for ( i = 0; i < size; i++ )
313 o = _RkPackBits(Bits, o, bit_size, &i, 1);
314 printf("PK ");
315 for ( i = 0; i < (bit_size*size+7)/8; i++ )
316 printf(" %02x", Bits[i]);
317 printf("\n");
318
319
320 for ( offset = 0; offset < 16; offset++ ) {
321 /* copybits */
322 o = _RkCopyBits(bits, offset, bit_size, Bits, 0, size);
323 printf("%d ", offset);
324 for ( i = 0; i < (o + 7)/8; i++ )
325 printf(" %02x", bits[i]);
326 printf("\n");
327
328 /* unpack 'em again */
329 ec = 0;
330 o = offset;
331 for ( i = 0; i < size; i++ ) {
332 unsigned w;
333
334 o = _RkUnpackBits(&w, bits, o, bit_size, 1);
335 if ( w != i )
336 ec++;
337 };
338 if ( ec )
339 printf(" %d", offset);
340 else
341 printf(".");
342 };
343 printf("\n");
344 };
345 }
346 #endif
347