root/psad/tags/psad-2.1.2/Bit-Vector/BitVector.c

Revision 1175, 109.8 kB (checked in by mbr, 4 years ago)

Initial revision

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
Line 
1 #ifndef MODULE_BIT_VECTOR
2 #define MODULE_BIT_VECTOR
3 /*****************************************************************************/
4 /*  MODULE NAME:  BitVector.c                           MODULE TYPE:  (adt)  */
5 /*****************************************************************************/
6 /*  MODULE IMPORTS:                                                          */
7 /*****************************************************************************/
8 #include <stdlib.h>                                 /*  MODULE TYPE:  (sys)  */
9 #include <limits.h>                                 /*  MODULE TYPE:  (sys)  */
10 #include <string.h>                                 /*  MODULE TYPE:  (sys)  */
11 #include <ctype.h>                                  /*  MODULE TYPE:  (sys)  */
12 #include "ToolBox.h"                                /*  MODULE TYPE:  (dat)  */
13 /*****************************************************************************/
14 /*  MODULE INTERFACE:                                                        */
15 /*****************************************************************************/
16
17 typedef enum
18     {
19         ErrCode_Ok = 0,    /* everything went allright                       */
20
21         ErrCode_Type,      /* types word and size_t have incompatible sizes  */
22         ErrCode_Bits,      /* bits of word and sizeof(word) are inconsistent */
23         ErrCode_Word,      /* size of word is less than 16 bits              */
24         ErrCode_Long,      /* size of word is greater than size of long      */
25         ErrCode_Powr,      /* number of bits of word is not a power of two   */
26         ErrCode_Loga,      /* error in calculation of logarithm              */
27
28         ErrCode_Null,      /* unable to allocate memory                      */
29
30         ErrCode_Indx,      /* index out of range                             */
31         ErrCode_Ordr,      /* minimum > maximum index                        */
32         ErrCode_Size,      /* bit vector size mismatch                       */
33         ErrCode_Pars,      /* input string syntax error                      */
34         ErrCode_Ovfl,      /* numeric overflow error                         */
35         ErrCode_Same,      /* operands must be distinct                      */
36         ErrCode_Expo,      /* exponent must be positive                      */
37         ErrCode_Zero       /* division by zero error                         */
38     } ErrCode;
39
40 typedef wordptr *listptr;
41
42 /* ===> MISCELLANEOUS BASIC FUNCTIONS: <=== */
43
44 charptr BitVector_Error      (ErrCode error);  /* return string for err code */
45
46 ErrCode BitVector_Boot       (void);                 /* 0 = ok, 1..7 = error */
47
48 N_word  BitVector_Size       (N_int bits);  /* bit vector size (# of words)  */
49 N_word  BitVector_Mask       (N_int bits);  /* bit vector mask (unused bits) */
50
51 /* ===> CLASS METHODS: <=== */
52
53 charptr BitVector_Version    (void);                /* return version string */
54
55 N_int   BitVector_Word_Bits  (void);     /* return # of bits in machine word */
56 N_int   BitVector_Long_Bits  (void);    /* return # of bits in unsigned long */
57
58 /* ===> CONSTRUCTOR METHODS: <=== */
59
60 wordptr BitVector_Create     (N_int bits, boolean clear);          /* malloc */
61 listptr BitVector_Create_List(N_int bits, boolean clear, N_int count);
62
63 wordptr BitVector_Resize     (wordptr oldaddr, N_int bits);       /* realloc */
64
65 wordptr BitVector_Shadow     (wordptr addr); /* make new same size but empty */
66 wordptr BitVector_Clone      (wordptr addr);         /* make exact duplicate */
67
68 wordptr BitVector_Concat     (wordptr X, wordptr Y); /* return concatenation */
69
70 /* ===> DESTRUCTOR METHODS: <=== */
71
72 void    BitVector_Dispose            (charptr string);             /* string */
73 void    BitVector_Destroy            (wordptr addr);               /* bitvec */
74 void    BitVector_Destroy_List       (listptr list, N_int count);  /* list   */
75
76 /* ===> OBJECT METHODS: <=== */
77
78 /* ===> bit vector copy function: */
79
80 void    BitVector_Copy       (wordptr X, wordptr Y);              /* X = Y   */
81
82 /* ===> bit vector initialization: */
83
84 void    BitVector_Empty      (wordptr addr);                      /* X = {}  */
85 void    BitVector_Fill       (wordptr addr);                      /* X = ~{} */
86 void    BitVector_Flip       (wordptr addr);                      /* X = ~X  */
87
88 void    BitVector_Primes     (wordptr addr);
89
90 /* ===> miscellaneous functions: */
91
92 void    BitVector_Reverse    (wordptr X, wordptr Y);
93
94 /* ===> bit vector interval operations and functions: */
95
96 void    BitVector_Interval_Empty     (wordptr addr, N_int lower, N_int upper);
97 void    BitVector_Interval_Fill      (wordptr addr, N_int lower, N_int upper);
98 void    BitVector_Interval_Flip      (wordptr addr, N_int lower, N_int upper);
99 void    BitVector_Interval_Reverse   (wordptr addr, N_int lower, N_int upper);
100
101 boolean BitVector_interval_scan_inc  (wordptr addr, N_int start,
102                                       N_intptr min, N_intptr max);
103 boolean BitVector_interval_scan_dec  (wordptr addr, N_int start,
104                                       N_intptr min, N_intptr max);
105
106 void    BitVector_Interval_Copy      (wordptr X, wordptr Y, N_int Xoffset,
107                                       N_int Yoffset, N_int length);
108
109 wordptr BitVector_Interval_Substitute(wordptr X, wordptr Y,
110                                       N_int Xoffset, N_int Xlength,
111                                       N_int Yoffset, N_int Ylength);
112
113 /* ===> bit vector test functions: */
114
115 boolean BitVector_is_empty   (wordptr addr);                  /* X == {} ?   */
116 boolean BitVector_is_full    (wordptr addr);                  /* X == ~{} ?  */
117
118 boolean BitVector_equal      (wordptr X, wordptr Y);          /* X == Y ?    */
119 Z_int   BitVector_Lexicompare(wordptr X, wordptr Y);          /* X <,=,> Y ? */
120 Z_int   BitVector_Compare    (wordptr X, wordptr Y);          /* X <,=,> Y ? */
121
122 /* ===> bit vector string conversion functions: */
123
124 charptr BitVector_to_Hex     (wordptr addr);
125 ErrCode BitVector_from_Hex   (wordptr addr, charptr string);
126
127 charptr BitVector_to_Bin     (wordptr addr);
128 ErrCode BitVector_from_Bin   (wordptr addr, charptr string);
129
130 charptr BitVector_to_Dec     (wordptr addr);
131 ErrCode BitVector_from_Dec   (wordptr addr, charptr string);
132
133 charptr BitVector_to_Enum    (wordptr addr);
134 ErrCode BitVector_from_Enum  (wordptr addr, charptr string);
135
136 /* ===> bit vector bit operations, functions & tests: */
137
138 void    BitVector_Bit_Off    (wordptr addr, N_int index); /*  X = X \ {x}    */
139 void    BitVector_Bit_On     (wordptr addr, N_int index); /*  X = X + {x}    */
140 boolean BitVector_bit_flip   (wordptr addr, N_int index); /* (X+{x})\(X*{x}) */
141
142 boolean BitVector_bit_test   (wordptr addr, N_int index); /*  {x} in X ?     */
143
144 void    BitVector_Bit_Copy   (wordptr addr, N_int index, boolean bit);
145
146 /* ===> bit vector bit shift & rotate functions: */
147
148 void    BitVector_LSB                (wordptr addr, boolean bit);
149 void    BitVector_MSB                (wordptr addr, boolean bit);
150 boolean BitVector_lsb_               (wordptr addr);
151 boolean BitVector_msb_               (wordptr addr);
152 boolean BitVector_rotate_left        (wordptr addr);
153 boolean BitVector_rotate_right       (wordptr addr);
154 boolean BitVector_shift_left         (wordptr addr, boolean carry_in);
155 boolean BitVector_shift_right        (wordptr addr, boolean carry_in);
156 void    BitVector_Move_Left          (wordptr addr, N_int bits);
157 void    BitVector_Move_Right         (wordptr addr, N_int bits);
158
159 /* ===> bit vector insert/delete bits: */
160
161 void    BitVector_Insert     (wordptr addr, N_int offset, N_int count,
162                               boolean clear);
163 void    BitVector_Delete     (wordptr addr, N_int offset, N_int count,
164                               boolean clear);
165
166 /* ===> bit vector arithmetic: */
167
168 boolean BitVector_increment  (wordptr addr);                        /*  X++  */
169 boolean BitVector_decrement  (wordptr addr);                        /*  X--  */
170
171 boolean BitVector_compute    (wordptr X, wordptr Y, wordptr Z, boolean minus,
172                                                                boolean *carry);
173 boolean BitVector_add        (wordptr X, wordptr Y, wordptr Z, boolean *carry);
174 boolean BitVector_sub        (wordptr X, wordptr Y, wordptr Z, boolean *carry);
175 boolean BitVector_inc        (wordptr X, wordptr Y);
176 boolean BitVector_dec        (wordptr X, wordptr Y);
177
178 void    BitVector_Negate     (wordptr X, wordptr Y);
179 void    BitVector_Absolute   (wordptr X, wordptr Y);
180 Z_int   BitVector_Sign       (wordptr addr);
181 ErrCode BitVector_Mul_Pos    (wordptr X, wordptr Y, wordptr Z, boolean strict);
182 ErrCode BitVector_Multiply   (wordptr X, wordptr Y, wordptr Z);
183 ErrCode BitVector_Div_Pos    (wordptr Q, wordptr X, wordptr Y, wordptr R);
184 ErrCode BitVector_Divide     (wordptr Q, wordptr X, wordptr Y, wordptr R);
185 ErrCode BitVector_GCD        (wordptr X, wordptr Y, wordptr Z);
186 ErrCode BitVector_GCD2       (wordptr U, wordptr V, wordptr W,      /*   O   */
187                                          wordptr X, wordptr Y);     /*   I   */
188 ErrCode BitVector_Power      (wordptr X, wordptr Y, wordptr Z);
189
190 /* ===> direct memory access functions: */
191
192 void    BitVector_Block_Store(wordptr addr, charptr buffer, N_int length);
193 charptr BitVector_Block_Read (wordptr addr, N_intptr length);
194
195 /* ===> word array functions: */
196
197 void    BitVector_Word_Store (wordptr addr, N_int offset, N_int value);
198 N_int   BitVector_Word_Read  (wordptr addr, N_int offset);
199
200 void    BitVector_Word_Insert(wordptr addr, N_int offset, N_int count,
201                               boolean clear);
202 void    BitVector_Word_Delete(wordptr addr, N_int offset, N_int count,
203                               boolean clear);
204
205 /* ===> arbitrary size chunk functions: */
206
207 void    BitVector_Chunk_Store(wordptr addr, N_int chunksize,
208                               N_int offset, N_long value);
209 N_long  BitVector_Chunk_Read (wordptr addr, N_int chunksize,
210                               N_int offset);
211
212 /* ===> set operations: */
213
214 void    Set_Union            (wordptr X, wordptr Y, wordptr Z); /* X = Y + Z */
215 void    Set_Intersection     (wordptr X, wordptr Y, wordptr Z); /* X = Y * Z */
216 void    Set_Difference       (wordptr X, wordptr Y, wordptr Z); /* X = Y \ Z */
217 void    Set_ExclusiveOr      (wordptr X, wordptr Y, wordptr Z); /*(Y+Z)\(Y*Z)*/
218 void    Set_Complement       (wordptr X, wordptr Y);            /* X = ~Y    */
219
220 /* ===> set functions: */
221
222 boolean Set_subset           (wordptr X, wordptr Y);            /* X in Y ?  */
223
224 N_int   Set_Norm             (wordptr addr);                    /* = | X |   */
225 Z_long  Set_Min              (wordptr addr);                    /* = min(X)  */
226 Z_long  Set_Max              (wordptr addr);                    /* = max(X)  */
227
228 /* ===> matrix-of-booleans operations: */
229
230 void    Matrix_Multiplication(wordptr X, N_int rowsX, N_int colsX,
231                               wordptr Y, N_int rowsY, N_int colsY,
232                               wordptr Z, N_int rowsZ, N_int colsZ);
233
234 void    Matrix_Product       (wordptr X, N_int rowsX, N_int colsX,
235                               wordptr Y, N_int rowsY, N_int colsY,
236                               wordptr Z, N_int rowsZ, N_int colsZ);
237
238 void    Matrix_Closure       (wordptr addr, N_int rows, N_int cols);
239
240 void    Matrix_Transpose     (wordptr X, N_int rowsX, N_int colsX,
241                               wordptr Y, N_int rowsY, N_int colsY);
242
243 /*****************************************************************************/
244 /*  MODULE RESOURCES:                                                        */
245 /*****************************************************************************/
246
247 #define bits_(BitVector) *(BitVector-3)
248 #define size_(BitVector) *(BitVector-2)
249 #define mask_(BitVector) *(BitVector-1)
250
251 #define  ERRCODE_TYPE  "sizeof(word) > sizeof(size_t)"
252 #define  ERRCODE_BITS  "bits(word) != sizeof(word)*8"
253 #define  ERRCODE_WORD  "bits(word) < 16"
254 #define  ERRCODE_LONG  "bits(word) > bits(long)"
255 #define  ERRCODE_POWR  "bits(word) != 2^x"
256 #define  ERRCODE_LOGA  "bits(word) != 2^ld(bits(word))"
257 #define  ERRCODE_NULL  "unable to allocate memory"
258 #define  ERRCODE_INDX  "index out of range"
259 #define  ERRCODE_ORDR  "minimum > maximum index"
260 #define  ERRCODE_SIZE  "bit vector size mismatch"
261 #define  ERRCODE_PARS  "input string syntax error"
262 #define  ERRCODE_OVFL  "numeric overflow error"
263 #define  ERRCODE_SAME  "result vector(s) must be distinct"
264 #define  ERRCODE_EXPO  "exponent must be positive"
265 #define  ERRCODE_ZERO  "division by zero error"
266 #define  ERRCODE_OOPS  "unexpected internal error - please contact author"
267
268 /*****************************************************************************/
269 /*  MODULE IMPLEMENTATION:                                                   */
270 /*****************************************************************************/
271
272     /**********************************************/
273     /* global implementation-intrinsic constants: */
274     /**********************************************/
275
276 #define BIT_VECTOR_HIDDEN_WORDS 3
277
278     /*****************************************************************/
279     /* global machine-dependent constants (set by "BitVector_Boot"): */
280     /*****************************************************************/
281
282 static N_word BITS;     /* = # of bits in machine word (must be power of 2)  */
283 static N_word MODMASK;  /* = BITS - 1 (mask for calculating modulo BITS)     */
284 static N_word LOGBITS;  /* = ld(BITS) (logarithmus dualis)                   */
285 static N_word FACTOR;   /* = ld(BITS / 8) (ld of # of bytes)                 */
286
287 static N_word LSB = 1;  /* = mask for least significant bit                  */
288 static N_word MSB;      /* = mask for most significant bit                   */
289
290 static N_word LONGBITS; /* = # of bits in unsigned long                      */
291
292 static N_word LOG10;    /* = logarithm to base 10 of BITS - 1                */
293 static N_word EXP10;    /* = largest possible power of 10 in signed int      */
294
295     /********************************************************************/
296     /* global bit mask table for fast access (set by "BitVector_Boot"): */
297     /********************************************************************/
298
299 static wordptr BITMASKTAB;
300
301     /*****************************/
302     /* global macro definitions: */
303     /*****************************/
304
305 #define BIT_VECTOR_ZERO_WORDS(target,count) \
306     while (count-- > 0) *target++ = 0;
307
308 #define BIT_VECTOR_FILL_WORDS(target,fill,count) \
309     while (count-- > 0) *target++ = fill;
310
311 #define BIT_VECTOR_FLIP_WORDS(target,flip,count) \
312     while (count-- > 0) *target++ ^= flip;
313
314 #define BIT_VECTOR_COPY_WORDS(target,source,count) \
315     while (count-- > 0) *target++ = *source++;
316
317 #define BIT_VECTOR_BACK_WORDS(target,source,count) \
318     { target += count; source += count; while (count-- > 0) *--target = *--source; }
319
320 #define BIT_VECTOR_CLR_BIT(address,index) \
321     *(address+(index>>LOGBITS)) &= NOT BITMASKTAB[index AND MODMASK];
322
323 #define BIT_VECTOR_SET_BIT(address,index) \
324     *(address+(index>>LOGBITS)) |= BITMASKTAB[index AND MODMASK];
325
326 #define BIT_VECTOR_TST_BIT(address,index) \
327     ((*(address+(index>>LOGBITS)) AND BITMASKTAB[index AND MODMASK]) != 0)
328
329 #define BIT_VECTOR_FLP_BIT(address,index,mask) \
330     (mask = BITMASKTAB[index AND MODMASK]), \
331     (((*(addr+(index>>LOGBITS)) ^= mask) AND mask) != 0)
332
333 #define BIT_VECTOR_DIGITIZE(type,value,digit) \
334     value = (type) ((digit = value) / 10); \
335     digit -= value * 10; \
336     digit += (type) '0';
337
338     /*********************************************************/
339     /* private low-level functions (potentially dangerous!): */
340     /*********************************************************/
341
342 static N_word power10(N_word x)
343 {
344     N_word y = 1;
345
346     while (x-- > 0) y *= 10;
347     return(y);
348 }
349
350 static void BIT_VECTOR_zro_words(wordptr addr, N_word count)
351 {
352     BIT_VECTOR_ZERO_WORDS(addr,count)
353 }
354
355 static void BIT_VECTOR_cpy_words(wordptr target, wordptr source, N_word count)
356 {
357     BIT_VECTOR_COPY_WORDS(target,source,count)
358 }
359
360 static void BIT_VECTOR_mov_words(wordptr target, wordptr source, N_word count)
361 {
362     if (target != source)
363     {
364         if (target < source) BIT_VECTOR_COPY_WORDS(target,source,count)
365         else                 BIT_VECTOR_BACK_WORDS(target,source,count)
366     }
367 }
368
369 static void BIT_VECTOR_ins_words(wordptr addr, N_word total, N_word count,
370                                  boolean clear)
371 {
372     N_word length;
373
374     if ((total > 0) and (count > 0))
375     {
376         if (count > total) count = total;
377         length = total - count;
378         if (length > 0) BIT_VECTOR_mov_words(addr+count,addr,length);
379         if (clear)      BIT_VECTOR_zro_words(addr,count);
380     }
381 }
382
383 static void BIT_VECTOR_del_words(wordptr addr, N_word total, N_word count,
384                                  boolean clear)
385 {
386     N_word length;
387
388     if ((total > 0) and (count > 0))
389     {
390         if (count > total) count = total;
391         length = total - count;
392         if (length > 0) BIT_VECTOR_mov_words(addr,addr+count,length);
393         if (clear)      BIT_VECTOR_zro_words(addr+length,count);
394     }
395 }
396
397 static void BIT_VECTOR_reverse(charptr string, N_word length)
398 {
399     charptr last;
400     N_char  temp;
401
402     if (length > 1)
403     {
404         last = string + length - 1;
405         while (string < last)
406         {
407             temp = *string;
408             *string = *last;
409             *last = temp;
410             string++;
411             last--;
412         }
413     }
414 }
415
416 static N_word BIT_VECTOR_int2str(charptr string, N_word value)
417 {
418     N_word  length;
419     N_word  digit;
420     charptr work;
421
422     work = string;
423     if (value > 0)
424     {
425         length = 0;
426         while (value > 0)
427         {
428             BIT_VECTOR_DIGITIZE(N_word,value,digit)
429             *work++ = (N_char) digit;
430             length++;
431         }
432         BIT_VECTOR_reverse(string,length);
433     }
434     else
435     {
436         length = 1;
437         *work++ = (N_char) '0';
438     }
439     return(length);
440 }
441
442 static N_word BIT_VECTOR_str2int(charptr string, N_word *value)
443 {
444     N_word  length;
445     N_word  digit;
446
447     *value = 0;
448     length = 0;
449     digit = (N_word) *string++;
450     /* separate because isdigit() is likely a macro! */
451     while (isdigit((int)digit) != 0)
452     {
453         length++;
454         digit -= (N_word) '0';
455         if (*value) *value *= 10;
456         *value += digit;
457         digit = (N_word) *string++;
458     }
459     return(length);
460 }
461
462     /********************************************/
463     /* routine to convert error code to string: */
464     /********************************************/
465
466 charptr BitVector_Error(ErrCode error)
467 {
468     switch (error)
469     {
470         case ErrCode_Ok:   return( (charptr)     NULL     ); break;
471         case ErrCode_Type: return( (charptr) ERRCODE_TYPE ); break;
472         case ErrCode_Bits: return( (charptr) ERRCODE_BITS ); break;
473         case ErrCode_Word: return( (charptr) ERRCODE_WORD ); break;
474         case ErrCode_Long: return( (charptr) ERRCODE_LONG ); break;
475         case ErrCode_Powr: return( (charptr) ERRCODE_POWR ); break;
476         case ErrCode_Loga: return( (charptr) ERRCODE_LOGA ); break;
477         case ErrCode_Null: return( (charptr) ERRCODE_NULL ); break;
478         case ErrCode_Indx: return( (charptr) ERRCODE_INDX ); break;
479         case ErrCode_Ordr: return( (charptr) ERRCODE_ORDR ); break;
480         case ErrCode_Size: return( (charptr) ERRCODE_SIZE ); break;
481         case ErrCode_Pars: return( (charptr) ERRCODE_PARS ); break;
482         case ErrCode_Ovfl: return( (charptr) ERRCODE_OVFL ); break;
483         case ErrCode_Same: return( (charptr) ERRCODE_SAME ); break;
484         case ErrCode_Expo: return( (charptr) ERRCODE_EXPO ); break;
485         case ErrCode_Zero: return( (charptr) ERRCODE_ZERO ); break;
486         default:           return( (charptr) ERRCODE_OOPS ); break;
487     }
488 }
489
490     /*****************************************/
491     /* automatic self-configuration routine: */
492     /*****************************************/
493
494     /*******************************************************/
495     /*                                                     */
496     /*   MUST be called once prior to any other function   */
497     /*   to initialize the machine dependent constants     */
498     /*   of this package! (But call only ONCE, or you      */
499     /*   will suffer memory leaks!)                        */
500     /*                                                     */
501     /*******************************************************/
502
503 ErrCode BitVector_Boot(void)
504 {
505     N_long longsample = 1L;
506     N_word sample = LSB;
507     N_word lsb;
508
509     if (sizeof(N_word) > sizeof(size_t)) return(ErrCode_Type);
510
511     BITS = 1;
512     while (sample <<= 1) BITS++;    /* determine # of bits in a machine word */
513
514     if (BITS != (sizeof(N_word) << 3)) return(ErrCode_Bits);
515
516     if (BITS < 16) return(ErrCode_Word);
517
518     LONGBITS = 1;
519     while (longsample <<= 1) LONGBITS++;  /* = # of bits in an unsigned long */
520
521     if (BITS > LONGBITS) return(ErrCode_Long);
522
523     LOGBITS = 0;
524     sample = BITS;
525     lsb = (sample AND LSB);
526     while ((sample >>= 1) and (not lsb))
527     {
528         LOGBITS++;
529         lsb = (sample AND LSB);
530     }
531
532     if (sample) return(ErrCode_Powr);      /* # of bits is not a power of 2! */
533
534     if (BITS != (LSB << LOGBITS)) return(ErrCode_Loga);
535
536     MODMASK = BITS - 1;
537     FACTOR = LOGBITS - 3;  /* ld(BITS / 8) = ld(BITS) - ld(8) = ld(BITS) - 3 */
538     MSB = (LSB << MODMASK);
539
540     BITMASKTAB = (wordptr) malloc((size_t) (BITS << FACTOR));
541
542     if (BITMASKTAB == NULL) return(ErrCode_Null);
543
544     for ( sample = 0; sample < BITS; sample++ )
545     {
546         BITMASKTAB[sample] = (LSB << sample);
547     }
548
549     LOG10 = (N_word) (MODMASK * 0.30103); /* = (BITS - 1) * ( ln 2 / ln 10 ) */
550     EXP10 = power10(LOG10);
551
552     return(ErrCode_Ok);
553 }
554
555 N_word BitVector_Size(N_int bits)           /* bit vector size (# of words)  */
556 {
557     N_word size;
558
559     size = bits >> LOGBITS;
560     if (bits AND MODMASK) size++;
561     return(size);
562 }
563
564 N_word BitVector_Mask(N_int bits)           /* bit vector mask (unused bits) */
565 {
566     N_word mask;
567
568     mask = bits AND MODMASK;
569     if (mask) mask = (N_word) ~(~0L << mask); else mask = (N_word) ~0L;
570     return(mask);
571 }
572
573 charptr BitVector_Version(void)
574 {
575     return((charptr)"6.3");
576 }
577
578 N_int BitVector_Word_Bits(void)
579 {
580     return(BITS);
581 }
582
583 N_int BitVector_Long_Bits(void)
584 {
585     return(LONGBITS);
586 }
587
588 /********************************************************************/
589 /*                                                                  */
590 /*  WARNING: Do not "free()" constant character strings, i.e.,      */
591 /*           don't call "BitVector_Dispose()" for strings returned  */
592 /*           by "BitVector_Error()" or "BitVector_Version()"!       */
593 /*                                                                  */
594 /*  ONLY call this function for strings allocated with "malloc()",  */
595 /*  i.e., the strings returned by the functions "BitVector_to_*()"  */
596 /*  and "BitVector_Block_Read()"!                                   */
597 /*                                                                  */
598 /********************************************************************/
599
600 void BitVector_Dispose(charptr string)                      /* free string   */
601 {
602     if (string != NULL) free((voidptr) string);
603 }
604
605 void BitVector_Destroy(wordptr addr)                        /* free bitvec   */
606 {
607     if (addr != NULL)
608     {
609         addr -= BIT_VECTOR_HIDDEN_WORDS;
610         free((voidptr) addr);
611     }
612 }
613
614 void BitVector_Destroy_List(listptr list, N_int count)      /* free list     */
615 {
616     listptr slot;
617
618     if (list != NULL)
619     {
620         slot = list;
621         while (count-- > 0)
622         {
623             BitVector_Destroy(*slot++);
624         }
625         free((voidptr) list);
626     }
627 }
628
629 wordptr BitVector_Create(N_int bits, boolean clear)         /* malloc        */
630 {
631     N_word  size;
632     N_word  mask;
633     N_word  bytes;
634     wordptr addr;
635     wordptr zero;
636
637     size = BitVector_Size(bits);
638     mask = BitVector_Mask(bits);
639     bytes = (size + BIT_VECTOR_HIDDEN_WORDS) << FACTOR;
640     addr = (wordptr) malloc((size_t) bytes);
641     if (addr != NULL)
642     {
643         *addr++ = bits;
644         *addr++ = size;
645         *addr++ = mask;
646         if (clear)
647         {
648             zero = addr;
649             BIT_VECTOR_ZERO_WORDS(zero,size)
650         }
651     }
652     return(addr);
653 }
654
655 listptr BitVector_Create_List(N_int bits, boolean clear, N_int count)
656 {
657     listptr list = NULL;
658     listptr slot;
659     wordptr addr;
660     N_int   i;
661
662     if (count > 0)
663     {
664         list = (listptr) malloc(sizeof(wordptr) * count);
665         if (list != NULL)
666         {
667             slot = list;
668             for ( i = 0; i < count; i++ )
669             {
670                 addr = BitVector_Create(bits,clear);
671                 if (addr == NULL)
672                 {
673                     BitVector_Destroy_List(list,i);
674                     return(NULL);
675                 }
676                 *slot++ = addr;
677             }
678         }
679     }
680     return(list);
681 }
682
683 wordptr BitVector_Resize(wordptr oldaddr, N_int bits)       /* realloc       */
684 {
685     N_word  bytes;
686     N_word  oldsize;
687     N_word  oldmask;
688     N_word  newsize;
689     N_word  newmask;
690     wordptr newaddr;
691     wordptr source;
692     wordptr target;
693
694     oldsize = size_(oldaddr);
695     oldmask = mask_(oldaddr);
696     newsize = BitVector_Size(bits);
697     newmask = BitVector_Mask(bits);
698     if (oldsize > 0) *(oldaddr+oldsize-1) &= oldmask;
699     if (newsize <= oldsize)
700     {
701         newaddr = oldaddr;
702         bits_(newaddr) = bits;
703         size_(newaddr) = newsize;
704         mask_(newaddr) = newmask;
705         if (newsize > 0) *(newaddr+newsize-1) &= newmask;
706     }
707     else
708     {
709         bytes = (newsize + BIT_VECTOR_HIDDEN_WORDS) << FACTOR;
710         newaddr = (wordptr) malloc((size_t) bytes);
711         if (newaddr != NULL)
712         {
713             *newaddr++ = bits;
714             *newaddr++ = newsize;
715             *newaddr++ = newmask;
716             target = newaddr;
717             source = oldaddr;
718             newsize -= oldsize;
719             BIT_VECTOR_COPY_WORDS(target,source,oldsize)
720             BIT_VECTOR_ZERO_WORDS(target,newsize)
721         }
722         BitVector_Destroy(oldaddr);
723     }
724     return(newaddr);
725 }
726
727 wordptr BitVector_Shadow(wordptr addr)     /* makes new, same size but empty */
728 {
729     return( BitVector_Create(bits_(addr),true) );
730 }
731
732 wordptr BitVector_Clone(wordptr addr)               /* makes exact duplicate */
733 {
734     N_word  bits;
735     wordptr twin;
736
737     bits = bits_(addr);
738     twin = BitVector_Create(bits,false);
739     if ((twin != NULL) and (bits > 0))
740         BIT_VECTOR_cpy_words(twin,addr,size_(addr));
741     return(twin);
742 }
743
744 wordptr BitVector_Concat(wordptr X, wordptr Y)      /* returns concatenation */
745 {
746     /* BEWARE that X = most significant part, Y = least significant part! */
747
748     N_word  bitsX;
749     N_word  bitsY;
750     N_word  bitsZ;
751     wordptr Z;
752
753     bitsX = bits_(X);
754     bitsY = bits_(Y);
755     bitsZ = bitsX + bitsY;
756     Z = BitVector_Create(bitsZ,false);
757     if ((Z != NULL) and (bitsZ > 0))
758     {
759         BIT_VECTOR_cpy_words(Z,Y,size_(Y));
760         BitVector_Interval_Copy(Z,X,bitsY,0,bitsX);
761         *(Z+size_(Z)-1) &= mask_(Z);
762     }
763     return(Z);
764 }
765
766 void BitVector_Copy(wordptr X, wordptr Y)                           /* X = Y */
767 {
768     N_word  sizeX = size_(X);
769     N_word  sizeY = size_(Y);
770     N_word  maskX = mask_(X);
771     N_word  maskY = mask_(Y);
772     N_word  fill  = 0;
773     wordptr lastX;
774     wordptr lastY;
775
776     if ((X != Y) and (sizeX > 0))
777     {
778         lastX = X + sizeX - 1;
779         if (sizeY > 0)
780         {
781             lastY = Y + sizeY - 1;
782             *lastY &= maskY;
783             while ((sizeX > 0) and (sizeY > 0))
784             {
785                 *X++ = *Y++;
786                 sizeX--;
787                 sizeY--;
788             }
789             if ( (*lastY AND (maskY AND NOT (maskY >> 1))) != 0 )
790             {
791                 fill = (N_word) ~0L;
792                 *(X-1) |= NOT maskY;
793             }
794         }
795         while (sizeX-- > 0) *X++ = fill;
796         *lastX &= maskX;
797     }
798 }
799
800 void BitVector_Empty(wordptr addr)                        /* X = {}  clr all */
801 {
802     N_word size = size_(addr);
803
804     BIT_VECTOR_ZERO_WORDS(addr,size)
805 }
806
807 void BitVector_Fill(wordptr addr)                         /* X = ~{} set all */
808 {
809     N_word size = size_(addr);
810     N_word mask = mask_(addr);
811     N_word fill = (N_word) ~0L;
812
813     if (size > 0)
814     {
815         BIT_VECTOR_FILL_WORDS(addr,fill,size)
816         *(--addr) &= mask;
817     }
818 }
819
820 void BitVector_Flip(wordptr addr)                         /* X = ~X flip all */
821 {
822     N_word size = size_(addr);
823     N_word mask = mask_(addr);
824     N_word flip = (N_word) ~0L;
825
826     if (size > 0)
827     {
828         BIT_VECTOR_FLIP_WORDS(addr,flip,size)
829         *(--addr) &= mask;
830     }
831 }
832
833 void BitVector_Primes(wordptr addr)
834 {
835     N_word  bits = bits_(addr);
836     N_word  size = size_(addr);
837     wordptr work;
838     N_word  temp;
839     N_word  i,j;
840
841     if (size > 0)
842     {
843         temp = 0xAAAA;
844         i = BITS >> 4;
845         while (--i > 0)
846         {
847             temp <<= 16;
848             temp |= 0xAAAA;
849         }
850         i = size;
851         work = addr;
852         *work++ = temp XOR 0x0006;
853         while (--i > 0) *work++ = temp;
854         for ( i = 3; (j = i * i) < bits; i += 2 )
855         {
856             for ( ; j < bits; j += i ) BIT_VECTOR_CLR_BIT(addr,j)
857         }
858         *(addr+size-1) &= mask_(addr);
859     }
860 }
861
862 void BitVector_Reverse(wordptr X, wordptr Y)
863 {
864     N_word bits = bits_(X);
865     N_word mask;
866     N_word bit;
867     N_word value;
868
869     if (bits > 0)
870     {
871         if (X == Y) BitVector_Interval_Reverse(X,0,bits-1);
872         else if (bits == bits_(Y))
873         {
874 /*          mask = mask_(Y);  */
875 /*          mask &= NOT (mask >> 1);  */
876             mask = BITMASKTAB[(bits-1) AND MODMASK];
877             Y += size_(Y) - 1;
878             value = 0;
879             bit = LSB;
880             while (bits-- > 0)
881             {
882                 if ((*Y AND mask) != 0)
883                 {
884                     value |= bit;
885                 }
886                 if (not (mask >>= 1))
887                 {
888                     Y--;
889