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