1 /**********************************************************************
2 ga_bitstring.c
3 **********************************************************************
4
5 ga_bitstring - GAUL's low-level bitstring routines.
6 Copyright ©2001-2003, Stewart Adcock <stewart@linux-domain.com>
7 All rights reserved.
8
9 The latest version of this program should be available at:
10 http://gaul.sourceforge.net/
11
12 This program is free software; you can redistribute it and/or modify
13 it under the terms of the GNU General Public License as published by
14 the Free Software Foundation; either version 2 of the License, or
15 (at your option) any later version. Alternatively, if your project
16 is incompatible with the GPL, I will probably agree to requests
17 for permission to use the terms of any other license.
18
19 This program is distributed in the hope that it will be useful, but
20 WITHOUT ANY WARRANTY WHATSOEVER.
21
22 A full copy of the GNU General Public License should be in the file
23 "COPYING" provided with this distribution; if not, see:
24 http://www.gnu.org/
25
26 **********************************************************************
27
28 Synopsis: Low-level bitstring handling functions.
29
30 Note that there is a lack of sanity checking in here
31 for efficiency reasons. Parameter safety should be
32 confirmed in the wrapper functions.
33
34 To do: Mappings.
35
36 FIXME: Performance of gray encoding/decoding is dreadful now
37 that it uses malloc/free. There is also a bug in these
38 routines.
39
40 **********************************************************************/
41
42 #include "gaul/ga_bitstring.h"
43
44 /**********************************************************************
45 ga_bit_new()
46 synopsis: Create a new bitstring.
47 parameters: int length Number of bits.
48 return: byte *ptr Newly allocated bitstring.
49 last updated: 30/06/01
50 **********************************************************************/
51
ga_bit_new(int length)52 byte *ga_bit_new( int length )
53 {
54 byte *ptr;
55
56 if ( !(ptr = (byte *) s_malloc( ga_bit_sizeof( length ) )) )
57 die("Unable to allocate bitstring.");
58
59 return ptr;
60 }
61
62
63 /**********************************************************************
64 ga_bit_free()
65 synopsis: Deallocates a bitstring.
66 parameters: byte *bstr Bitstring to deallocate.
67 return: none
68 last updated: 30/06/01
69 **********************************************************************/
70
ga_bit_free(byte * bstr)71 void ga_bit_free( byte *bstr )
72 {
73 s_free( bstr );
74
75 return;
76 }
77
78
79 /**********************************************************************
80 ga_bit_set()
81 synopsis: Sets a single bit in a bitstring.
82 parameters: byte *bstr Bitstring.
83 int n Bit index.
84 return: none
85 last updated: 30/06/01
86 **********************************************************************/
87
ga_bit_set(byte * bstr,int n)88 void ga_bit_set( byte *bstr, int n )
89 {
90 bstr[n/BYTEBITS] |= 1 << ( n%BYTEBITS );
91
92 return;
93 }
94
95
96 /**********************************************************************
97 ga_bit_clear()
98 synopsis: Unsets a single bit in a bitstring.
99 parameters: byte *bstr Bitstring.
100 int n Bit index.
101 return: none
102 last updated: 07 Sep 2003
103 **********************************************************************/
104
ga_bit_clear(byte * bstr,int n)105 void ga_bit_clear( byte *bstr, int n )
106 {
107 bstr[n/BYTEBITS] &= ~(1 << ( n%BYTEBITS ));
108
109 return;
110 }
111
112
113 /**********************************************************************
114 ga_bit_invert()
115 synopsis: Toggles a single bit in a bitstring.
116 parameters: byte *bstr Bitstring.
117 int n Bit index.
118 return: none
119 last updated: 07 Sep 2003
120 **********************************************************************/
121
ga_bit_invert(byte * bstr,int n)122 void ga_bit_invert( byte *bstr, int n )
123 {
124 bstr[n/BYTEBITS] ^= 1 << (n % BYTEBITS);
125
126 return;
127 }
128
129
130 /**********************************************************************
131 ga_bit_get()
132 synopsis: Returns the state of a single bit in a bitstring.
133 parameters: byte *bstr Bitstring.
134 int n Bit index.
135 return: boolean val The bit's state.
136 last updated: 30/06/01
137 **********************************************************************/
138
ga_bit_get(byte * bstr,int n)139 boolean ga_bit_get( byte *bstr, int n )
140 {
141 return (boolean) ( (bstr[n/BYTEBITS] & (1 << (n % BYTEBITS))) != 0 );
142 }
143
144
145 /**********************************************************************
146 ga_bit_randomize()
147 synopsis: Randomly sets the state of a single bit in a bitstring.
148 parameters: byte *bstr Bitstring.
149 int n Bit index.
150 return: none
151 last updated: 30/06/01
152 **********************************************************************/
153
ga_bit_randomize(byte * bstr,int n)154 void ga_bit_randomize( byte *bstr, int n )
155 {
156 if ( random_boolean() )
157 ga_bit_set( bstr, n );
158 else
159 ga_bit_clear( bstr, n );
160
161 return;
162 }
163
164
165 /**********************************************************************
166 ga_bit_copy()
167 synopsis: Copies a set of bits in a bitstring.
168 If dest and src are the same, overlapping sequences
169 of bits are safely handled.
170
171 FIXME: Should use memcpy, when appropriate.
172 parameters: byte *dest Destination bitstring.
173 byte *src Source bitstring
174 int ndest Initial bit index of destination bits.
175 int nsrc Initial bit index of source bits.
176 int length Number of bits to copy.
177 return: none
178 last updated: 29 Jun 2003
179 **********************************************************************/
180
ga_bit_copy(byte * dest,byte * src,int ndest,int nsrc,int length)181 void ga_bit_copy( byte *dest, byte *src, int ndest, int nsrc, int length )
182 {
183 int i;
184
185 if (dest != src || ndest < nsrc)
186 {
187 for ( i=0; i < length; ++i )
188 {
189 if ( ga_bit_get(src, nsrc+i) )
190 ga_bit_set( dest, ndest+i );
191 else
192 ga_bit_clear( dest, ndest+i );
193 }
194 }
195 else
196 {
197 for ( i = length-1 ; i >= 0; --i )
198 {
199 if ( ga_bit_get(src, nsrc+i) )
200 ga_bit_set( dest, ndest+i );
201 else
202 ga_bit_clear( dest, ndest+i );
203 }
204 }
205
206 return;
207 }
208
209
210 /**********************************************************************
211 ga_bit_sizeof()
212 synopsis: Return the size required for the given number of
213 bits, rounded up if needed.
214 parameters: int length Number of bits.
215 return: none
216 last updated: 30/06/01
217 **********************************************************************/
218
ga_bit_sizeof(int length)219 size_t ga_bit_sizeof( int length )
220 {
221 /* Note that sizeof(byte) should always be 1. */
222 return sizeof(byte) * (length+BYTEBITS-1) / BYTEBITS;
223 }
224
225
226 /**********************************************************************
227 ga_bit_clone()
228 synopsis: Copies a complete bitstring.
229 parameters: byte *dest Destination bitstring.
230 byte *src Source bitstring
231 int length Number of bits in bitstrings.
232 return: none
233 last updated: 30/06/01
234 **********************************************************************/
235
ga_bit_clone(byte * dest,byte * src,int length)236 byte *ga_bit_clone( byte *dest, byte *src, int length )
237 {
238 if (!dest) dest=ga_bit_new( length );
239
240 memcpy( dest, src, ga_bit_sizeof( length ) );
241
242 return dest;
243 }
244
245
246 /**********************************************************************
247 ga_bit_decode_binary_uint()
248 synopsis: Convert a binary-encoded bitstring into an unsigned int
249 starting at a given offset.
250 parameters:
251 return:
252 last updated: 08 Jan 2003
253 **********************************************************************/
254
ga_bit_decode_binary_uint(byte * bstr,int n,int length)255 unsigned int ga_bit_decode_binary_uint( byte *bstr, int n, int length )
256 {
257 int i;
258 unsigned int value=0; /* Decoded value. */
259
260 for ( i=n; i < n+length; i++ )
261 {
262 value <<= 1;
263 value |= ga_bit_get(bstr, i);
264 }
265
266 return value;
267 }
268
269
270 /**********************************************************************
271 ga_bit_encode_binary_uint()
272 synopsis: Convert an unsigned int into a binary-encoded bitstring
273 starting at a given offset.
274 parameters:
275 return:
276 last updated: 08 Jan 2003
277 **********************************************************************/
278
ga_bit_encode_binary_uint(byte * bstr,int n,int length,unsigned int value)279 void ga_bit_encode_binary_uint( byte *bstr, int n, int length, unsigned int value )
280 {
281 int i;
282
283 /* Set bits in _reverse_ order. */
284 for ( i = n+length-1; i >= n; i-- )
285 {
286 if ( value & 1 )
287 ga_bit_set( bstr, i );
288 else
289 ga_bit_clear( bstr, i );
290
291 value >>= 1;
292 }
293
294 return;
295 }
296
297
298 /**********************************************************************
299 ga_bit_decode_binary_int()
300 synopsis: Convert a binary-encoded bitstring into a signed int
301 starting at a given offset.
302 parameters:
303 return:
304 last updated: 08 Jan 2003
305 **********************************************************************/
306
ga_bit_decode_binary_int(byte * bstr,int n,int length)307 int ga_bit_decode_binary_int( byte *bstr, int n, int length )
308 {
309 if ( ga_bit_get( bstr, n ) )
310 return (int) -ga_bit_decode_binary_uint( bstr, n+1, length-1 );
311 else
312 return (int) ga_bit_decode_binary_uint( bstr, n+1, length-1 );
313 }
314
315
316 /**********************************************************************
317 ga_bit_encode_binary_int()
318 synopsis: Convert a signed int into a binary-encoded bitstring
319 starting at a given offset.
320 parameters:
321 return:
322 last updated: 08 Jan 2003
323 **********************************************************************/
324
ga_bit_encode_binary_int(byte * bstr,int n,int length,int value)325 void ga_bit_encode_binary_int( byte *bstr, int n, int length, int value )
326 {
327 if ( value < 0 )
328 {
329 ga_bit_set( bstr, n );
330 value = -value;
331 }
332 else
333 {
334 ga_bit_clear( bstr, n );
335 }
336
337 ga_bit_encode_binary_uint( bstr, n+1, length-1, (unsigned int) value );
338
339 return;
340 }
341
342
343 /**********************************************************************
344 gray_to_binary()
345 synopsis: Convert a Gray-encoded bitstring into a binary-encoded
346 bitstring.
347 parameters:
348 return:
349 last updated: 08 Jan 2003
350 **********************************************************************/
351
gray_to_binary(byte * gray_bstr,int n,byte * int_bstr,int length)352 static void gray_to_binary( byte *gray_bstr, int n, byte *int_bstr, int length )
353 {
354 boolean bit;
355 int i;
356
357 bit = ga_bit_get( gray_bstr, n );
358 if (bit)
359 ga_bit_set( int_bstr, 0 );
360 else
361 ga_bit_clear( int_bstr, 0 );
362
363 for ( i=1; i<length; i++ )
364 {
365 if (bit)
366 bit = !ga_bit_get( gray_bstr, n+i );
367 else
368 bit = ga_bit_get( gray_bstr, n+i );
369
370 if (bit)
371 ga_bit_set( int_bstr, i );
372 else
373 ga_bit_clear( int_bstr, i );
374 }
375
376 return;
377 }
378
379
380 /**********************************************************************
381 binary_to_gray()
382 synopsis: Convert a binary-encoded bitstring into a gray-encoded
383 bitstring.
384 parameters:
385 return:
386 last updated: 08 Jan 2003
387 **********************************************************************/
388
binary_to_gray(byte * gray_bstr,int n,byte * int_bstr,int length)389 static void binary_to_gray( byte *gray_bstr, int n, byte *int_bstr, int length )
390 {
391 boolean bit;
392 int i;
393
394 bit = ga_bit_get( int_bstr, 0 );
395 if (bit)
396 ga_bit_set( gray_bstr, n );
397 else
398 ga_bit_clear( gray_bstr, n );
399
400 for ( i=1; i < length; i++ )
401 {
402
403 if (bit)
404 {
405 bit = ga_bit_get( int_bstr, i );
406 if (bit)
407 ga_bit_clear( gray_bstr, n+i );
408 else
409 ga_bit_set( gray_bstr, n+i );
410 }
411 else
412 {
413 bit = ga_bit_get( int_bstr, i );
414 if (bit)
415 ga_bit_set( gray_bstr, n+i );
416 else
417 ga_bit_clear( gray_bstr, n+i );
418 }
419 }
420
421 return;
422 }
423
424
425 /**********************************************************************
426 ga_bit_decode_gray_int()
427 synopsis: Convert a gray-encoded bitstring into a signed int
428 starting at a given offset.
429 parameters:
430 return:
431 last updated: 08 Jan 2003
432 **********************************************************************/
433
ga_bit_decode_gray_int(byte * bstr,int n,int length)434 int ga_bit_decode_gray_int( byte *bstr, int n, int length )
435 {
436 byte *int_bstr;
437 int val;
438
439 if ( !(int_bstr = (byte *) s_malloc( ga_bit_sizeof( length ) )) )
440 die("Unable to allocate bitstring.");
441
442 gray_to_binary( bstr, n, int_bstr, length );
443
444 val = ga_bit_decode_binary_int( int_bstr, 0, length );
445
446 s_free(int_bstr);
447
448 return val;
449 }
450
451
452 /**********************************************************************
453 ga_bit_decode_gray_uint()
454 synopsis: Convert a gray-encoded bitstring into an unsigned int
455 starting at a given offset.
456 parameters:
457 return:
458 last updated: 08 Jan 2003
459 **********************************************************************/
460
ga_bit_decode_gray_uint(byte * bstr,int n,int length)461 unsigned int ga_bit_decode_gray_uint( byte *bstr, int n, int length )
462 {
463 byte *int_bstr;
464 unsigned int val;
465
466 if ( !(int_bstr = (byte *) s_malloc( ga_bit_sizeof( length ) )) )
467 die("Unable to allocate bitstring.");
468
469 gray_to_binary( bstr, n, int_bstr, length );
470
471 val = ga_bit_decode_binary_uint( int_bstr, 0, length );
472
473 s_free(int_bstr);
474
475 return val;
476 }
477
478
479 /**********************************************************************
480 ga_bit_encode_gray_uint()
481 synopsis: Convert an unsigned int into a gray-encoded bitstring
482 starting at a given offset.
483 parameters:
484 return:
485 last updated: 08 Jan 2003
486 **********************************************************************/
487
ga_bit_encode_gray_uint(byte * bstr,int n,int length,unsigned int value)488 void ga_bit_encode_gray_uint( byte *bstr, int n, int length, unsigned int value )
489 {
490 byte *int_bstr;
491
492 if ( !(int_bstr = (byte *) s_malloc( ga_bit_sizeof( length ) )) )
493 die("Unable to allocate bitstring.");
494
495 ga_bit_encode_binary_uint( int_bstr, 0, length, value );
496 binary_to_gray( bstr, n, int_bstr, length );
497
498 s_free(int_bstr);
499
500 return;
501 }
502
503
504 /**********************************************************************
505 ga_bit_encode_gray_int()
506 synopsis: Convert an unsigned int into a gray-encoded bitstring
507 starting at a given offset.
508 parameters:
509 return:
510 last updated: 08 Jan 2003
511 **********************************************************************/
512
ga_bit_encode_gray_int(byte * bstr,int n,int length,int value)513 void ga_bit_encode_gray_int( byte *bstr, int n, int length, int value )
514 {
515 byte *int_bstr;
516
517 if ( !(int_bstr = (byte *) s_malloc( ga_bit_sizeof( length ) )) )
518 die("Unable to allocate bitstring.");
519
520 ga_bit_encode_binary_int( int_bstr, 0, length, value );
521 binary_to_gray( bstr, n, int_bstr, length );
522
523 s_free(int_bstr);
524
525 return;
526 }
527
528
529 /**********************************************************************
530 ga_bit_decode_binary_real()
531 synopsis: Convert a binary-encoded bitstring at a given offset
532 into a real.
533 parameters:
534 return:
535 last updated: 08 Jan 2003
536 **********************************************************************/
537
ga_bit_decode_binary_real(byte * bstr,int n,int mantissa,int exponent)538 double ga_bit_decode_binary_real( byte *bstr, int n, int mantissa, int exponent )
539 {
540 double value;
541 int int_mantissa, int_exponent;
542
543 int_mantissa = ga_bit_decode_binary_int( bstr, n, mantissa );
544 int_exponent = ga_bit_decode_binary_int( bstr, n+mantissa, exponent );
545
546 value = ((double)int_mantissa) / ((double)(1<<(mantissa-1)))
547 * pow( 2.0, (double) int_exponent );
548
549 return value;
550 }
551
552
553 /**********************************************************************
554 ga_bit_encode_binary_real()
555 synopsis: Convert a real into a binary-encoded bitstring at a
556 given offset.
557 parameters:
558 return:
559 last updated: 08 Jan 2003
560 **********************************************************************/
561
ga_bit_encode_binary_real(byte * bstr,int n,int mantissa,int exponent,double value)562 void ga_bit_encode_binary_real( byte *bstr, int n, int mantissa, int exponent, double value )
563 {
564 int int_mantissa, int_exponent;
565
566 int_mantissa = (int) floor(frexp( value, &int_exponent ) * (double)(1<<(mantissa-1)));
567 ga_bit_encode_binary_int( bstr, n, mantissa, int_mantissa );
568 ga_bit_encode_binary_int( bstr, n+mantissa, exponent, int_exponent );
569
570 return;
571 }
572
573
574 /**********************************************************************
575 ga_bit_decode_gray_real()
576 synopsis: Convert a Gray-encoded bitstring at a given offset
577 into a real.
578 parameters:
579 return:
580 last updated: 25 Jul 2003
581 **********************************************************************/
582
ga_bit_decode_gray_real(byte * bstr,int n,int mantissa,int exponent)583 double ga_bit_decode_gray_real( byte *bstr, int n, int mantissa, int exponent )
584 {
585 double value;
586 int int_mantissa, int_exponent;
587
588 int_mantissa = ga_bit_decode_gray_int( bstr, n, mantissa );
589 int_exponent = ga_bit_decode_gray_int( bstr, n+mantissa, exponent );
590
591 value = pow( 2.0, (double) int_exponent ) *
592 ((double)int_mantissa) / ((double)(1<<(mantissa-1)));
593
594 return value;
595 }
596
597
598 /**********************************************************************
599 ga_bit_encode_gray_real()
600 synopsis: Convert a real into a Gray-encoded bitstring at a
601 given offset.
602 parameters:
603 return:
604 last updated: 25 Jul 2003
605 **********************************************************************/
606
ga_bit_encode_gray_real(byte * bstr,int n,int mantissa,int exponent,double value)607 void ga_bit_encode_gray_real( byte *bstr, int n, int mantissa, int exponent, double value )
608 {
609 int int_mantissa, int_exponent;
610
611 int_mantissa = (int) floor(frexp( value, &int_exponent ) * (double)(1<<(mantissa-1)));
612
613 ga_bit_encode_gray_int( bstr, n, mantissa, int_mantissa );
614 ga_bit_encode_gray_int( bstr, n+mantissa, exponent, int_exponent );
615
616 return;
617 }
618
619
620 /**********************************************************************
621 ga_bit_test()
622 synopsis: Test bitstring conversion routines.
623 parameters: none
624 return: Always TRUE, currently.
625 last updated: 06 Oct 2004
626 **********************************************************************/
627
ga_bit_test(void)628 boolean ga_bit_test( void )
629 {
630 int i; /* Loop variable. */
631 double origval, newval; /* Value before and after encoding+decoding. */
632 int origint, newint; /* Value before and after encoding+decoding. */
633 byte *bstr;
634
635 if ( !(bstr = (byte *) s_malloc( ga_bit_sizeof( 128 ) )) )
636 die("Unable to allocate bitstring.");
637
638 printf("Binary encoding of integers:\n");
639
640 for (i=0; i<10; i++)
641 {
642 origint = 23*i-30;
643 ga_bit_encode_binary_int( bstr, 0, 64, origint );
644 newint = ga_bit_decode_binary_int( bstr, 0, 64 );
645 printf("Orig val = %d new val = %d %s\n",
646 origint, newint, origint==newint?"PASSED":"FAILED");
647 }
648
649 printf("Binary encoding of reals:\n");
650
651 for (i=0; i<10; i++)
652 {
653 origval = -0.3+0.16*i;
654 ga_bit_encode_binary_real( bstr, 0, 64, 64, origval );
655 newval = ga_bit_decode_binary_real( bstr, 0, 64, 64 );
656 printf("Orig val = %f new val = %f %s\n",
657 origval, newval,
658 (origval>newval-TINY&&origval<newval+TINY)?"PASSED":"FAILED");
659 }
660
661 printf("Gray encoding of integers:\n");
662
663 for (i=0; i<10; i++)
664 {
665 origint = 23*i-30;
666 ga_bit_encode_gray_int( bstr, 0, 64, origint );
667 newint = ga_bit_decode_gray_int( bstr, 0, 64 );
668 printf("Orig val = %d new val = %d %s\n",
669 origint, newint, origint==newint?"PASSED":"FAILED");
670 }
671
672 printf("Gray encoding of reals:\n");
673
674 for (i=0; i<10; i++)
675 {
676 origval = -0.3+0.16*i;
677 ga_bit_encode_gray_real( bstr, 0, 64, 64, origval );
678 newval = ga_bit_decode_gray_real( bstr, 0, 64, 64 );
679 printf("Orig val = %f new val = %f %s\n",
680 origval, newval,
681 (origval>newval-TINY&&origval<newval+TINY)?"PASSED":"FAILED");
682 }
683
684 s_free(bstr);
685
686 return TRUE;
687 }
688
689
690