1 #ifndef MODULE_BIT_VECTOR
2 #define MODULE_BIT_VECTOR
3 /*****************************************************************************/
4 /* MODULE NAME: BitVector.c MODULE TYPE: (adt) */
5 /*****************************************************************************/
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 /*****************************************************************************/
19 ErrCode_Ok = 0, /* everything went allright */
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 */
28 ErrCode_Null, /* unable to allocate memory */
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 */
40 typedef wordptr *listptr;
42 /* ===> MISCELLANEOUS BASIC FUNCTIONS: <=== */
44 charptr BitVector_Error (ErrCode error); /* return string for err code */
46 ErrCode BitVector_Boot (void); /* 0 = ok, 1..7 = error */
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) */
51 /* ===> CLASS METHODS: <=== */
53 charptr BitVector_Version (void); /* return version string */
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 */
58 /* ===> CONSTRUCTOR METHODS: <=== */
60 wordptr BitVector_Create (N_int bits, boolean clear); /* malloc */
61 listptr BitVector_Create_List(N_int bits, boolean clear, N_int count);
63 wordptr BitVector_Resize (wordptr oldaddr, N_int bits); /* realloc */
65 wordptr BitVector_Shadow (wordptr addr); /* make new same size but empty */
66 wordptr BitVector_Clone (wordptr addr); /* make exact duplicate */
68 wordptr BitVector_Concat (wordptr X, wordptr Y); /* return concatenation */
70 /* ===> DESTRUCTOR METHODS: <=== */
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 */
76 /* ===> OBJECT METHODS: <=== */
78 /* ===> bit vector copy function: */
80 void BitVector_Copy (wordptr X, wordptr Y); /* X = Y */
82 /* ===> bit vector initialization: */
84 void BitVector_Empty (wordptr addr); /* X = {} */
85 void BitVector_Fill (wordptr addr); /* X = ~{} */
86 void BitVector_Flip (wordptr addr); /* X = ~X */
88 void BitVector_Primes (wordptr addr);
90 /* ===> miscellaneous functions: */
92 void BitVector_Reverse (wordptr X, wordptr Y);
94 /* ===> bit vector interval operations and functions: */
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);
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);
106 void BitVector_Interval_Copy (wordptr X, wordptr Y, N_int Xoffset,
107 N_int Yoffset, N_int length);
109 wordptr BitVector_Interval_Substitute(wordptr X, wordptr Y,
110 N_int Xoffset, N_int Xlength,
111 N_int Yoffset, N_int Ylength);
113 /* ===> bit vector test functions: */
115 boolean BitVector_is_empty (wordptr addr); /* X == {} ? */
116 boolean BitVector_is_full (wordptr addr); /* X == ~{} ? */
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 ? */
122 /* ===> bit vector string conversion functions: */
124 charptr BitVector_to_Hex (wordptr addr);
125 ErrCode BitVector_from_Hex (wordptr addr, charptr string);
127 charptr BitVector_to_Bin (wordptr addr);
128 ErrCode BitVector_from_Bin (wordptr addr, charptr string);
130 charptr BitVector_to_Dec (wordptr addr);
131 ErrCode BitVector_from_Dec (wordptr addr, charptr string);
133 charptr BitVector_to_Enum (wordptr addr);
134 ErrCode BitVector_from_Enum (wordptr addr, charptr string);
136 /* ===> bit vector bit operations, functions & tests: */
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}) */
142 boolean BitVector_bit_test (wordptr addr, N_int index); /* {x} in X ? */
144 void BitVector_Bit_Copy (wordptr addr, N_int index, boolean bit);
146 /* ===> bit vector bit shift & rotate functions: */
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);
159 /* ===> bit vector insert/delete bits: */
161 void BitVector_Insert (wordptr addr, N_int offset, N_int count,
163 void BitVector_Delete (wordptr addr, N_int offset, N_int count,
166 /* ===> bit vector arithmetic: */
168 boolean BitVector_increment (wordptr addr); /* X++ */
169 boolean BitVector_decrement (wordptr addr); /* X-- */
171 boolean BitVector_compute (wordptr X, wordptr Y, wordptr Z, boolean minus,
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);
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);
190 /* ===> direct memory access functions: */
192 void BitVector_Block_Store(wordptr addr, charptr buffer, N_int length);
193 charptr BitVector_Block_Read (wordptr addr, N_intptr length);
195 /* ===> word array functions: */
197 void BitVector_Word_Store (wordptr addr, N_int offset, N_int value);
198 N_int BitVector_Word_Read (wordptr addr, N_int offset);
200 void BitVector_Word_Insert(wordptr addr, N_int offset, N_int count,
202 void BitVector_Word_Delete(wordptr addr, N_int offset, N_int count,
205 /* ===> arbitrary size chunk functions: */
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,
212 /* ===> set operations: */
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 */
220 /* ===> set functions: */
222 boolean Set_subset (wordptr X, wordptr Y); /* X in Y ? */
224 N_int Set_Norm (wordptr addr); /* = | X | */
225 N_int Set_Norm2 (wordptr addr); /* = | X | */
226 N_int Set_Norm3 (wordptr addr); /* = | X | */
227 Z_long Set_Min (wordptr addr); /* = min(X) */
228 Z_long Set_Max (wordptr addr); /* = max(X) */
230 /* ===> matrix-of-booleans operations: */
232 void Matrix_Multiplication(wordptr X, N_int rowsX, N_int colsX,
233 wordptr Y, N_int rowsY, N_int colsY,
234 wordptr Z, N_int rowsZ, N_int colsZ);
236 void Matrix_Product (wordptr X, N_int rowsX, N_int colsX,
237 wordptr Y, N_int rowsY, N_int colsY,
238 wordptr Z, N_int rowsZ, N_int colsZ);
240 void Matrix_Closure (wordptr addr, N_int rows, N_int cols);
242 void Matrix_Transpose (wordptr X, N_int rowsX, N_int colsX,
243 wordptr Y, N_int rowsY, N_int colsY);
245 /*****************************************************************************/
246 /* MODULE RESOURCES: */
247 /*****************************************************************************/
249 #define bits_(BitVector) *(BitVector-3)
250 #define size_(BitVector) *(BitVector-2)
251 #define mask_(BitVector) *(BitVector-1)
253 #define ERRCODE_TYPE "sizeof(word) > sizeof(size_t)"
254 #define ERRCODE_BITS "bits(word) != sizeof(word)*8"
255 #define ERRCODE_WORD "bits(word) < 16"
256 #define ERRCODE_LONG "bits(word) > bits(long)"
257 #define ERRCODE_POWR "bits(word) != 2^x"
258 #define ERRCODE_LOGA "bits(word) != 2^ld(bits(word))"
259 #define ERRCODE_NULL "unable to allocate memory"
260 #define ERRCODE_INDX "index out of range"
261 #define ERRCODE_ORDR "minimum > maximum index"
262 #define ERRCODE_SIZE "bit vector size mismatch"
263 #define ERRCODE_PARS "input string syntax error"
264 #define ERRCODE_OVFL "numeric overflow error"
265 #define ERRCODE_SAME "result vector(s) must be distinct"
266 #define ERRCODE_EXPO "exponent must be positive"
267 #define ERRCODE_ZERO "division by zero error"
268 #define ERRCODE_OOPS "unexpected internal error - please contact author"
270 const N_int BitVector_BYTENORM[256] =
272 0x00, 0x01, 0x01, 0x02, 0x01, 0x02, 0x02, 0x03,
273 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, /* 0x00 */
274 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
275 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x10 */
276 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
277 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x20 */
278 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
279 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x30 */
280 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
281 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x40 */
282 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
283 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x50 */
284 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
285 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x60 */
286 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
287 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0x70 */
288 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
289 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x80 */
290 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
291 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x90 */
292 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
293 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0xA0 */
294 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
295 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0xB0 */
296 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
297 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0xC0 */
298 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
299 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0xD0 */
300 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
301 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0xE0 */
302 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07,
303 0x05, 0x06, 0x06, 0x07, 0x06, 0x07, 0x07, 0x08 /* 0xF0 */
306 /*****************************************************************************/
307 /* MODULE IMPLEMENTATION: */
308 /*****************************************************************************/
310 /**********************************************/
311 /* global implementation-intrinsic constants: */
312 /**********************************************/
314 #define BIT_VECTOR_HIDDEN_WORDS 3
316 /*****************************************************************/
317 /* global machine-dependent constants (set by "BitVector_Boot"): */
318 /*****************************************************************/
320 static N_word BITS; /* = # of bits in machine word (must be power of 2) */
321 static N_word MODMASK; /* = BITS - 1 (mask for calculating modulo BITS) */
322 static N_word LOGBITS; /* = ld(BITS) (logarithmus dualis) */
323 static N_word FACTOR; /* = ld(BITS / 8) (ld of # of bytes) */
325 static N_word LSB = 1; /* = mask for least significant bit */
326 static N_word MSB; /* = mask for most significant bit */
328 static N_word LONGBITS; /* = # of bits in unsigned long */
330 static N_word LOG10; /* = logarithm to base 10 of BITS - 1 */
331 static N_word EXP10; /* = largest possible power of 10 in signed int */
333 /********************************************************************/
334 /* global bit mask table for fast access (set by "BitVector_Boot"): */
335 /********************************************************************/
337 static wordptr BITMASKTAB;
339 /*****************************/
340 /* global macro definitions: */
341 /*****************************/
343 #define BIT_VECTOR_ZERO_WORDS(target,count) \
344 while (count-- > 0) *target++ = 0;
346 #define BIT_VECTOR_FILL_WORDS(target,fill,count) \
347 while (count-- > 0) *target++ = fill;
349 #define BIT_VECTOR_FLIP_WORDS(target,flip,count) \
350 while (count-- > 0) *target++ ^= flip;
352 #define BIT_VECTOR_COPY_WORDS(target,source,count) \
353 while (count-- > 0) *target++ = *source++;
355 #define BIT_VECTOR_BACK_WORDS(target,source,count) \
356 { target += count; source += count; while (count-- > 0) *--target = *--source; }
358 #define BIT_VECTOR_CLR_BIT(address,index) \
359 *(address+(index>>LOGBITS)) &= NOT BITMASKTAB[index AND MODMASK];
361 #define BIT_VECTOR_SET_BIT(address,index) \
362 *(address+(index>>LOGBITS)) |= BITMASKTAB[index AND MODMASK];
364 #define BIT_VECTOR_TST_BIT(address,index) \
365 ((*(address+(index>>LOGBITS)) AND BITMASKTAB[index AND MODMASK]) != 0)
367 #define BIT_VECTOR_FLP_BIT(address,index,mask) \
368 (mask = BITMASKTAB[index AND MODMASK]), \
369 (((*(addr+(index>>LOGBITS)) ^= mask) AND mask) != 0)
371 #define BIT_VECTOR_DIGITIZE(type,value,digit) \
372 value = (type) ((digit = value) / 10); \
373 digit -= value * 10; \
376 /*********************************************************/
377 /* private low-level functions (potentially dangerous!): */
378 /*********************************************************/
380 static N_word power10(N_word x)
384 while (x-- > 0) y *= 10;
388 static void BIT_VECTOR_zro_words(wordptr addr, N_word count)
390 BIT_VECTOR_ZERO_WORDS(addr,count)
393 static void BIT_VECTOR_cpy_words(wordptr target, wordptr source, N_word count)
395 BIT_VECTOR_COPY_WORDS(target,source,count)
398 static void BIT_VECTOR_mov_words(wordptr target, wordptr source, N_word count)
400 if (target != source)
402 if (target < source) BIT_VECTOR_COPY_WORDS(target,source,count)
403 else BIT_VECTOR_BACK_WORDS(target,source,count)
407 static void BIT_VECTOR_ins_words(wordptr addr, N_word total, N_word count,
412 if ((total > 0) and (count > 0))
414 if (count > total) count = total;
415 length = total - count;
416 if (length > 0) BIT_VECTOR_mov_words(addr+count,addr,length);
417 if (clear) BIT_VECTOR_zro_words(addr,count);
421 static void BIT_VECTOR_del_words(wordptr addr, N_word total, N_word count,
426 if ((total > 0) and (count > 0))
428 if (count > total) count = total;
429 length = total - count;
430 if (length > 0) BIT_VECTOR_mov_words(addr,addr+count,length);
431 if (clear) BIT_VECTOR_zro_words(addr+length,count);
435 static void BIT_VECTOR_reverse(charptr string, N_word length)
442 last = string + length - 1;
443 while (string < last)
454 static N_word BIT_VECTOR_int2str(charptr string, N_word value)
466 BIT_VECTOR_DIGITIZE(N_word,value,digit)
467 *work++ = (N_char) digit;
470 BIT_VECTOR_reverse(string,length);
475 *work++ = (N_char) '0';
480 static N_word BIT_VECTOR_str2int(charptr string, N_word *value)
487 digit = (N_word) *string++;
488 /* separate because isdigit() is likely a macro! */
489 while (isdigit((int)digit) != 0)
492 digit -= (N_word) '0';
493 if (*value) *value *= 10;
495 digit = (N_word) *string++;
500 /********************************************/
501 /* routine to convert error code to string: */
502 /********************************************/
504 charptr BitVector_Error(ErrCode error)
508 case ErrCode_Ok: return( (charptr) NULL ); break;
509 case ErrCode_Type: return( (charptr) ERRCODE_TYPE ); break;
510 case ErrCode_Bits: return( (charptr) ERRCODE_BITS ); break;
511 case ErrCode_Word: return( (charptr) ERRCODE_WORD ); break;
512 case ErrCode_Long: return( (charptr) ERRCODE_LONG ); break;
513 case ErrCode_Powr: return( (charptr) ERRCODE_POWR ); break;
514 case ErrCode_Loga: return( (charptr) ERRCODE_LOGA ); break;
515 case ErrCode_Null: return( (charptr) ERRCODE_NULL ); break;
516 case ErrCode_Indx: return( (charptr) ERRCODE_INDX ); break;
517 case ErrCode_Ordr: return( (charptr) ERRCODE_ORDR ); break;
518 case ErrCode_Size: return( (charptr) ERRCODE_SIZE ); break;
519 case ErrCode_Pars: return( (charptr) ERRCODE_PARS ); break;
520 case ErrCode_Ovfl: return( (charptr) ERRCODE_OVFL ); break;
521 case ErrCode_Same: return( (charptr) ERRCODE_SAME ); break;
522 case ErrCode_Expo: return( (charptr) ERRCODE_EXPO ); break;
523 case ErrCode_Zero: return( (charptr) ERRCODE_ZERO ); break;
524 default: return( (charptr) ERRCODE_OOPS ); break;
528 /*****************************************/
529 /* automatic self-configuration routine: */
530 /*****************************************/
532 /*******************************************************/
534 /* MUST be called once prior to any other function */
535 /* to initialize the machine dependent constants */
536 /* of this package! (But call only ONCE, or you */
537 /* will suffer memory leaks!) */
539 /*******************************************************/
541 ErrCode BitVector_Boot(void)
543 N_long longsample = 1L;
547 if (sizeof(N_word) > sizeof(size_t)) return(ErrCode_Type);
550 while (sample <<= 1) BITS++; /* determine # of bits in a machine word */
552 if (BITS != (sizeof(N_word) << 3)) return(ErrCode_Bits);
554 if (BITS < 16) return(ErrCode_Word);
557 while (longsample <<= 1) LONGBITS++; /* = # of bits in an unsigned long */
559 if (BITS > LONGBITS) return(ErrCode_Long);
563 lsb = (sample AND LSB);
564 while ((sample >>= 1) and (not lsb))
567 lsb = (sample AND LSB);
570 if (sample) return(ErrCode_Powr); /* # of bits is not a power of 2! */
572 if (BITS != (LSB << LOGBITS)) return(ErrCode_Loga);
575 FACTOR = LOGBITS - 3; /* ld(BITS / 8) = ld(BITS) - ld(8) = ld(BITS) - 3 */
576 MSB = (LSB << MODMASK);
578 BITMASKTAB = (wordptr) malloc((size_t) (BITS << FACTOR));
580 if (BITMASKTAB == NULL) return(ErrCode_Null);
582 for ( sample = 0; sample < BITS; sample++ )
584 BITMASKTAB[sample] = (LSB << sample);
587 LOG10 = (N_word) (MODMASK * 0.30103); /* = (BITS - 1) * ( ln 2 / ln 10 ) */
588 EXP10 = power10(LOG10);
593 N_word BitVector_Size(N_int bits) /* bit vector size (# of words) */
597 size = bits >> LOGBITS;
598 if (bits AND MODMASK) size++;
602 N_word BitVector_Mask(N_int bits) /* bit vector mask (unused bits) */
606 mask = bits AND MODMASK;
607 if (mask) mask = (N_word) ~(~0L << mask); else mask = (N_word) ~0L;
611 charptr BitVector_Version(void)
613 return((charptr)"6.4");
616 N_int BitVector_Word_Bits(void)
621 N_int BitVector_Long_Bits(void)
626 /********************************************************************/
628 /* WARNING: Do not "free()" constant character strings, i.e., */
629 /* don't call "BitVector_Dispose()" for strings returned */
630 /* by "BitVector_Error()" or "BitVector_Version()"! */
632 /* ONLY call this function for strings allocated with "malloc()", */
633 /* i.e., the strings returned by the functions "BitVector_to_*()" */
634 /* and "BitVector_Block_Read()"! */
636 /********************************************************************/
638 void BitVector_Dispose(charptr string) /* free string */
640 if (string != NULL) free((voidptr) string);
643 void BitVector_Destroy(wordptr addr) /* free bitvec */
647 addr -= BIT_VECTOR_HIDDEN_WORDS;
648 free((voidptr) addr);
652 void BitVector_Destroy_List(listptr list, N_int count) /* free list */
661 BitVector_Destroy(*slot++);
663 free((voidptr) list);
667 wordptr BitVector_Create(N_int bits, boolean clear) /* malloc */
675 size = BitVector_Size(bits);
676 mask = BitVector_Mask(bits);
677 bytes = (size + BIT_VECTOR_HIDDEN_WORDS) << FACTOR;
678 addr = (wordptr) malloc((size_t) bytes);
687 BIT_VECTOR_ZERO_WORDS(zero,size)
693 listptr BitVector_Create_List(N_int bits, boolean clear, N_int count)
702 list = (listptr) malloc(sizeof(wordptr) * count);
706 for ( i = 0; i < count; i++ )
708 addr = BitVector_Create(bits,clear);
711 BitVector_Destroy_List(list,i);
721 wordptr BitVector_Resize(wordptr oldaddr, N_int bits) /* realloc */
732 oldsize = size_(oldaddr);
733 oldmask = mask_(oldaddr);
734 newsize = BitVector_Size(bits);
735 newmask = BitVector_Mask(bits);
736 if (oldsize > 0) *(oldaddr+oldsize-1) &= oldmask;
737 if (newsize <= oldsize)
740 bits_(newaddr) = bits;
741 size_(newaddr) = newsize;
742 mask_(newaddr) = newmask;
743 if (newsize > 0) *(newaddr+newsize-1) &= newmask;
747 bytes = (newsize + BIT_VECTOR_HIDDEN_WORDS) << FACTOR;
748 newaddr = (wordptr) malloc((size_t) bytes);
752 *newaddr++ = newsize;
753 *newaddr++ = newmask;
757 BIT_VECTOR_COPY_WORDS(target,source,oldsize)
758 BIT_VECTOR_ZERO_WORDS(target,newsize)
760 BitVector_Destroy(oldaddr);
765 wordptr BitVector_Shadow(wordptr addr) /* makes new, same size but empty */
767 return( BitVector_Create(bits_(addr),true) );
770 wordptr BitVector_Clone(wordptr addr) /* makes exact duplicate */
776 twin = BitVector_Create(bits,false);
777 if ((twin != NULL) and (bits > 0))
778 BIT_VECTOR_cpy_words(twin,addr,size_(addr));
782 wordptr BitVector_Concat(wordptr X, wordptr Y) /* returns concatenation */
784 /* BEWARE that X = most significant part, Y = least significant part! */
793 bitsZ = bitsX + bitsY;
794 Z = BitVector_Create(bitsZ,false);
795 if ((Z != NULL) and (bitsZ > 0))
797 BIT_VECTOR_cpy_words(Z,Y,size_(Y));
798 BitVector_Interval_Copy(Z,X,bitsY,0,bitsX);
799 *(Z+size_(Z)-1) &= mask_(Z);
804 void BitVector_Copy(wordptr X, wordptr Y) /* X = Y */
806 N_word sizeX = size_(X);
807 N_word sizeY = size_(Y);
808 N_word maskX = mask_(X);
809 N_word maskY = mask_(Y);
814 if ((X != Y) and (sizeX > 0))
816 lastX = X + sizeX - 1;
819 lastY = Y + sizeY - 1;
820 if ( (*lastY AND (maskY AND NOT (maskY >> 1))) == 0 ) *lastY &= maskY;
826 while ((sizeX > 0) and (sizeY > 0))
834 while (sizeX-- > 0) *X++ = fill;
839 void BitVector_Empty(wordptr addr) /* X = {} clr all */
841 N_word size = size_(addr);
843 BIT_VECTOR_ZERO_WORDS(addr,size)
846 void BitVector_Fill(wordptr addr) /* X = ~{} set all */
848 N_word size = size_(addr);
849 N_word mask = mask_(addr);
850 N_word fill = (N_word) ~0L;
854 BIT_VECTOR_FILL_WORDS(addr,fill,size)
859 void BitVector_Flip(wordptr addr) /* X = ~X flip all */
861 N_word size = size_(addr);
862 N_word mask = mask_(addr);
863 N_word flip = (N_word) ~0L;
867 BIT_VECTOR_FLIP_WORDS(addr,flip,size)
872 void BitVector_Primes(wordptr addr)
874 N_word bits = bits_(addr);
875 N_word size = size_(addr);
891 *work++ = temp XOR 0x0006;
892 while (--i > 0) *work++ = temp;
893 for ( i = 3; (j = i * i) < bits; i += 2 )
895 for ( ; j < bits; j += i ) BIT_VECTOR_CLR_BIT(addr,j)
897 *(addr+size-1) &= mask_(addr);
901 void BitVector_Reverse(wordptr X, wordptr Y)
903 N_word bits = bits_(X);
910 if (X == Y) BitVector_Interval_Reverse(X,0,bits-1);
911 else if (bits == bits_(Y))
913 /* mask = mask_(Y); */
914 /* mask &= NOT (mask >> 1); */
915 mask = BITMASKTAB[(bits-1) AND MODMASK];
921 if ((*Y AND mask) != 0)
925 if (not (mask >>= 1))
937 if (bit > LSB) *X = value;
942 void BitVector_Interval_Empty(wordptr addr, N_int lower, N_int upper)
943 { /* X = X \ [lower..upper] */
944 N_word bits = bits_(addr);
945 N_word size = size_(addr);
954 if ((size > 0) and (lower < bits) and (upper < bits) and (lower <= upper))
956 lobase = lower >> LOGBITS;
957 hibase = upper >> LOGBITS;
958 diff = hibase - lobase;
959 loaddr = addr + lobase;
960 hiaddr = addr + hibase;
962 lomask = (N_word) (~0L << (lower AND MODMASK));
963 himask = (N_word) ~((~0L << (upper AND MODMASK)) << 1);
967 *loaddr &= NOT (lomask AND himask);
971 *loaddr++ &= NOT lomask;
976 *hiaddr &= NOT himask;
981 void BitVector_Interval_Fill(wordptr addr, N_int lower, N_int upper)
982 { /* X = X + [lower..upper] */
983 N_word bits = bits_(addr);
984 N_word size = size_(addr);
985 N_word fill = (N_word) ~0L;
994 if ((size > 0) and (lower < bits) and (upper < bits) and (lower <= upper))
996 lobase = lower >> LOGBITS;
997 hibase = upper >> LOGBITS;
998 diff = hibase - lobase;
999 loaddr = addr + lobase;
1000 hiaddr = addr + hibase;
1002 lomask = (N_word) (~0L << (lower AND MODMASK));
1003 himask = (N_word) ~((~0L << (upper AND MODMASK)) << 1);
1007 *loaddr |= (lomask AND himask);
1011 *loaddr++ |= lomask;
1018 *(addr+size-1) &= mask_(addr);
1022 void BitVector_Interval_Flip(wordptr addr, N_int lower, N_int upper)
1023 { /* X = X ^ [lower..upper] */
1024 N_word bits = bits_(addr);
1025 N_word size = size_(addr);
1026 N_word flip = (N_word) ~0L;
1035 if ((size > 0) and (lower < bits) and (upper < bits) and (lower <= upper))
1037 lobase = lower >> LOGBITS;
1038 hibase = upper >> LOGBITS;
1039 diff = hibase - lobase;
1040 loaddr = addr + lobase;
1041 hiaddr = addr + hibase;
1043 lomask = (N_word) (~0L << (lower AND MODMASK));
1044 himask = (N_word) ~((~0L << (upper AND MODMASK)) << 1);
1048 *loaddr ^= (lomask AND himask);
1052 *loaddr++ ^= lomask;
1059 *(addr+size-1) &= mask_(addr);
1063 void BitVector_Interval_Reverse(wordptr addr, N_int lower, N_int upper)
1065 N_word bits = bits_(addr);
1071 if ((bits > 0) and (lower < bits) and (upper < bits) and (lower < upper))
1073 loaddr = addr + (lower >> LOGBITS);
1074 hiaddr = addr + (upper >> LOGBITS);
1075 lomask = BITMASKTAB[lower AND MODMASK];
1076 himask = BITMASKTAB[upper AND MODMASK];
1077 for ( bits = upper - lower + 1; bits > 1; bits -= 2 )
1079 if (((*loaddr AND lomask) != 0) XOR ((*hiaddr AND himask) != 0))
1081 *loaddr ^= lomask; /* swap bits only if they differ! */
1084 if (not (lomask <<= 1))
1089 if (not (himask >>= 1))
1098 boolean BitVector_interval_scan_inc(wordptr addr, N_int start,
1099 N_intptr min, N_intptr max)
1101 N_word size = size_(addr);
1102 N_word mask = mask_(addr);
1108 if ((size == 0) or (start >= bits_(addr))) return(false);
1113 offset = start >> LOGBITS;
1115 *(addr+size-1) &= mask;
1120 bitmask = BITMASKTAB[start AND MODMASK];
1121 mask = NOT (bitmask OR (bitmask - 1));
1124 if ((value AND bitmask) == 0)
1131 while (empty and (--size > 0))
1133 if ((value = *addr++)) empty = false; else offset++;
1135 if (empty) return(false);
1137 start = offset << LOGBITS;
1140 while (not (mask AND LSB))
1146 mask = NOT (bitmask OR (bitmask - 1));
1156 while (empty and (--size > 0))
1158 if ((value = NOT *addr++)) empty = false; else offset++;
1160 if (empty) value = LSB;
1162 start = offset << LOGBITS;
1163 while (not (value AND LSB))
1172 boolean BitVector_interval_scan_dec(wordptr addr, N_int start,
1173 N_intptr min, N_intptr max)
1175 N_word size = size_(addr);
1176 N_word mask = mask_(addr);
1182 if ((size == 0) or (start >= bits_(addr))) return(false);
1187 offset = start >> LOGBITS;
1189 if (offset >= size) return(false);
1191 *(addr+size-1) &= mask;
1196 bitmask = BITMASKTAB[start AND MODMASK];
1197 mask = (bitmask - 1);
1200 if ((value AND bitmask) == 0)
1207 while (empty and (--size > 0))
1209 if ((value = *addr--)) empty = false; else offset--;
1211 if (empty) return(false);
1213 start = offset << LOGBITS;
1216 while (not (mask AND MSB))
1222 mask = (bitmask - 1);
1232 while (empty and (--size > 0))
1234 if ((value = NOT *addr--)) empty = false; else offset--;
1236 if (empty) value = MSB;
1238 start = offset << LOGBITS;
1239 while (not (value AND MSB))
1248 void BitVector_Interval_Copy(wordptr X, wordptr Y, N_int Xoffset,
1249 N_int Yoffset, N_int length)
1251 N_word bitsX = bits_(X);
1252 N_word bitsY = bits_(Y);
1253 N_word source = 0; /* silence compiler warning */
1254 N_word target = 0; /* silence compiler warning */
1260 N_word s_lower = 0; /* silence compiler warning */
1261 N_word s_upper = 0; /* silence compiler warning */
1270 N_word t_lower = 0; /* silence compiler warning */
1271 N_word t_upper = 0; /* silence compiler warning */
1281 if ((length > 0) and (Xoffset < bitsX) and (Yoffset < bitsY))
1283 if ((Xoffset + length) > bitsX) length = bitsX - Xoffset;
1284 if ((Yoffset + length) > bitsY) length = bitsY - Yoffset;
1286 ascending = (Xoffset <= Yoffset);
1288 s_lo_base = Yoffset >> LOGBITS;
1289 s_lo_bit = Yoffset AND MODMASK;
1290 Yoffset += --length;
1291 s_hi_base = Yoffset >> LOGBITS;
1292 s_hi_bit = Yoffset AND MODMASK;
1294 t_lo_base = Xoffset >> LOGBITS;
1295 t_lo_bit = Xoffset AND MODMASK;
1297 t_hi_base = Xoffset >> LOGBITS;
1298 t_hi_bit = Xoffset AND MODMASK;
1324 if (t_base == t_hi_base) break;
1330 if (t_base == t_lo_base) break;
1335 select = ((t_base == t_hi_base) << 1) OR (t_base == t_lo_base);
1347 t_bits = BITS - t_lo_bit;
1348 mask = (N_word) (~0L << t_lower);
1349 target = *X AND NOT mask;
1354 t_bits = t_hi_bit + 1;
1355 mask = (N_word) ((~0L << t_upper) << 1);
1356 target = *X AND mask;
1361 t_bits = t_hi_bit - t_lo_bit + 1;
1362 mask = (N_word) (~0L << t_lower);
1363 mask &= (N_word) ~((~0L << t_upper) << 1);
1364 target = *X AND NOT mask;
1374 if (s_base == s_hi_base) break;
1380 if (s_base == s_lo_base) break;
1386 select = ((s_base == s_hi_base) << 1) OR (s_base == s_lo_base);
1397 s_bits = BITS - s_lo_bit;
1402 s_bits = s_hi_bit + 1;
1407 s_bits = s_hi_bit - s_lo_bit + 1;
1412 if (s_bits > t_bits)
1418 s_max = s_lower + bits;
1423 s_min = s_upper - bits;
1430 if (ascending) t_min = t_lower;
1431 else t_min = t_upper - bits;
1436 mask = (N_word) (~0L << s_min);
1437 mask &= (N_word) ~((~0L << s_max) << 1);
1438 if (s_min == t_min) target |= (source AND mask);
1441 if (s_min < t_min) target |= (source AND mask) << (t_min-s_min);
1442 else target |= (source AND mask) >> (s_min-t_min);
1457 *(Z+size_(Z)-1) &= mask_(Z);
1462 wordptr BitVector_Interval_Substitute(wordptr X, wordptr Y,
1463 N_int Xoffset, N_int Xlength,
1464 N_int Yoffset, N_int Ylength)
1466 N_word Xbits = bits_(X);
1467 N_word Ybits = bits_(Y);
1471 if ((Xoffset <= Xbits) and (Yoffset <= Ybits))
1473 limit = Xoffset + Xlength;
1477 Xlength = Xbits - Xoffset;
1479 if ((Yoffset + Ylength) > Ybits)
1481 Ylength = Ybits - Yoffset;
1483 if (Xlength == Ylength)
1485 if ((Ylength > 0) and ((X != Y) or (Xoffset != Yoffset)))
1487 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
1490 else /* Xlength != Ylength */
1492 if (Xlength > Ylength)
1494 diff = Xlength - Ylength;
1495 if (Ylength > 0) BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
1496 if (limit < Xbits) BitVector_Delete(X,Xoffset+Ylength,diff,false);
1497 if ((X = BitVector_Resize(X,Xbits-diff)) == NULL) return(NULL);
1499 else /* Ylength > Xlength ==> Ylength > 0 */
1501 diff = Ylength - Xlength;
1504 if ((X = BitVector_Resize(X,Xbits+diff)) == NULL) return(NULL);
1505 if (limit < Xbits) BitVector_Insert(X,limit,diff,false);
1506 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
1510 if ((Y = X = BitVector_Resize(X,Xbits+diff)) == NULL) return(NULL);
1513 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
1515 else /* limit < Xbits */
1517 BitVector_Insert(X,limit,diff,false);
1518 if ((Yoffset+Ylength) <= limit)
1520 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
1522 else /* overlaps or lies above critical area */
1524 if (limit <= Yoffset)
1527 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
1529 else /* Yoffset < limit */
1531 Xlength = limit - Yoffset;
1532 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Xlength);
1533 Yoffset = Xoffset + Ylength; /* = limit + diff */
1536 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
1547 boolean BitVector_is_empty(wordptr addr) /* X == {} ? */
1549 N_word size = size_(addr);
1554 *(addr+size-1) &= mask_(addr);
1555 while (r and (size-- > 0)) r = ( *addr++ == 0 );
1560 boolean BitVector_is_full(wordptr addr) /* X == ~{} ? */
1562 N_word size = size_(addr);
1563 N_word mask = mask_(addr);
1570 last = addr + size - 1;
1572 while (r and (size-- > 0)) r = ( NOT *addr++ == 0 );
1578 boolean BitVector_equal(wordptr X, wordptr Y) /* X == Y ? */
1580 N_word size = size_(X);
1581 N_word mask = mask_(X);
1584 if (bits_(X) == bits_(Y))
1589 *(X+size-1) &= mask;
1590 *(Y+size-1) &= mask;
1591 while (r and (size-- > 0)) r = (*X++ == *Y++);
1597 Z_int BitVector_Lexicompare(wordptr X, wordptr Y) /* X <,=,> Y ? */
1599 N_word bitsX = bits_(X);
1600 N_word bitsY = bits_(Y);
1601 N_word size = size_(X);
1610 while (r and (size-- > 0)) r = (*(--X) == *(--Y));
1612 if (r) return((Z_int) 0);
1615 if (*X < *Y) return((Z_int) -1); else return((Z_int) 1);
1620 if (bitsX < bitsY) return((Z_int) -1); else return((Z_int) 1);
1624 Z_int BitVector_Compare(wordptr X, wordptr Y) /* X <,=,> Y ? */
1626 N_word bitsX = bits_(X);
1627 N_word bitsY = bits_(Y);
1628 N_word size = size_(X);
1629 N_word mask = mask_(X);
1639 mask &= NOT (mask >> 1);
1640 if ((sign = (*(X-1) AND mask)) != (*(Y-1) AND mask))
1642 if (sign) return((Z_int) -1); else return((Z_int) 1);
1644 while (r and (size-- > 0)) r = (*(--X) == *(--Y));
1646 if (r) return((Z_int) 0);
1649 if (*X < *Y) return((Z_int) -1); else return((Z_int) 1);
1654 if (bitsX < bitsY) return((Z_int) -1); else return((Z_int) 1);
1658 charptr BitVector_to_Hex(wordptr addr)
1660 N_word bits = bits_(addr);
1661 N_word size = size_(addr);
1669 if (bits AND 0x0003) length++;
1670 string = (charptr) malloc((size_t) (length+1));
1671 if (string == NULL) return(NULL);
1673 *string = (N_char) '\0';
1676 *(addr+size-1) &= mask_(addr);
1677 while ((size-- > 0) and (length > 0))
1681 while ((count-- > 0) and (length > 0))
1683 digit = value AND 0x000F;
1684 if (digit > 9) digit += (N_word) 'A' - 10;
1685 else digit += (N_word) '0';
1686 *(--string) = (N_char) digit; length--;
1687 if ((count > 0) and (length > 0)) value >>= 4;
1694 ErrCode BitVector_from_Hex(wordptr addr, charptr string)
1696 N_word size = size_(addr);
1697 N_word mask = mask_(addr);
1706 length = strlen((char *) string);
1711 for ( count = 0; (ok and (length > 0) and (count < BITS)); count += 4 )
1713 digit = (int) *(--string); length--;
1714 /* separate because toupper() is likely a macro! */
1715 digit = toupper(digit);
1716 if ((ok = (isxdigit(digit) != 0)))
1718 if (digit >= (int) 'A') digit -= (int) 'A' - 10;
1719 else digit -= (int) '0';
1720 value |= (((N_word) digit) << count);
1727 if (ok) return(ErrCode_Ok);
1728 else return(ErrCode_Pars);
1731 charptr BitVector_to_Bin(wordptr addr)
1733 N_word size = size_(addr);
1740 length = bits_(addr);
1741 string = (charptr) malloc((size_t) (length+1));
1742 if (string == NULL) return(NULL);
1744 *string = (N_char) '\0';
1747 *(addr+size-1) &= mask_(addr);
1752 if (count > length) count = length;
1755 digit = value AND 0x0001;
1756 digit += (N_word) '0';
1757 *(--string) = (N_char) digit; length--;
1758 if (count > 0) value >>= 1;
1765 ErrCode BitVector_from_Bin(wordptr addr, charptr string)
1767 N_word size = size_(addr);
1768 N_word mask = mask_(addr);
1777 length = strlen((char *) string);
1782 for ( count = 0; (ok and (length > 0) and (count < BITS)); count++ )
1784 digit = (int) *(--string); length--;
1790 value |= BITMASKTAB[count];
1801 if (ok) return(ErrCode_Ok);
1802 else return(ErrCode_Pars);
1805 charptr BitVector_to_Dec(wordptr addr)
1807 N_word bits = bits_(addr);
1822 length = (N_word) (bits / 3.3); /* digits = bits * ln(2) / ln(10) */
1823 length += 2; /* compensate for truncating & provide space for minus sign */
1824 result = (charptr) malloc((size_t) (length+1)); /* remember the '\0'! */
1825 if (result == NULL) return(NULL);
1827 sign = BitVector_Sign(addr);
1828 if ((bits < 4) or (sign == 0))
1830 if (bits > 0) digits = *addr; else digits = (N_word) 0;
1831 if (sign < 0) digits = ((N_word)(-((Z_word)digits))) AND mask_(addr);
1832 *string++ = (N_char) digits + (N_char) '0';
1837 quot = BitVector_Create(bits,false);
1840 BitVector_Dispose(result);
1843 rest = BitVector_Create(bits,false);
1846 BitVector_Dispose(result);
1847 BitVector_Destroy(quot);
1850 temp = BitVector_Create(bits,false);
1853 BitVector_Dispose(result);
1854 BitVector_Destroy(quot);
1855 BitVector_Destroy(rest);
1858 base = BitVector_Create(bits,true);
1861 BitVector_Dispose(result);
1862 BitVector_Destroy(quot);
1863 BitVector_Destroy(rest);
1864 BitVector_Destroy(temp);
1867 if (sign < 0) BitVector_Negate(quot,addr);
1868 else BitVector_Copy(quot,addr);
1871 loop = (bits >= BITS);
1876 BitVector_Copy(temp,quot);
1877 if (BitVector_Div_Pos(quot,temp,base,rest))
1879 BitVector_Dispose(result); /* emergency exit */
1880 BitVector_Destroy(quot);
1881 BitVector_Destroy(rest); /* should never occur */
1882 BitVector_Destroy(temp); /* under normal operation */
1883 BitVector_Destroy(base);
1886 loop = not BitVector_is_empty(quot);
1891 while (((loop and (count-- > 0)) or ((not loop) and (q != 0))) and
1896 BIT_VECTOR_DIGITIZE(N_word,q,r)
1898 else r = (N_word) '0';
1899 *string++ = (N_char) r;
1903 while (loop and (digits < length));
1904 BitVector_Destroy(quot);
1905 BitVector_Destroy(rest);
1906 BitVector_Destroy(temp);
1907 BitVector_Destroy(base);
1909 if ((sign < 0) and (digits < length))
1911 *string++ = (N_char) '-';
1914 *string = (N_char) '\0';
1915 BIT_VECTOR_reverse(result,digits);
1919 ErrCode BitVector_from_Dec(wordptr addr, charptr string)
1921 ErrCode error = ErrCode_Ok;
1922 N_word bits = bits_(addr);
1923 N_word mask = mask_(addr);
1924 boolean init = (bits > BITS);
1941 length = strlen((char *) string);
1942 if (length == 0) return(ErrCode_Pars);
1943 digit = (int) *string;
1944 if ((minus = (digit == (int) '-')) or
1945 (digit == (int) '+'))
1948 if (--length == 0) return(ErrCode_Pars);
1951 term = BitVector_Create(BITS,false);
1954 return(ErrCode_Null);
1956 base = BitVector_Create(BITS,false);
1959 BitVector_Destroy(term);
1960 return(ErrCode_Null);
1962 prod = BitVector_Create(bits,init);
1965 BitVector_Destroy(term);
1966 BitVector_Destroy(base);
1967 return(ErrCode_Null);
1969 rank = BitVector_Create(bits,init);
1972 BitVector_Destroy(term);
1973 BitVector_Destroy(base);
1974 BitVector_Destroy(prod);
1975 return(ErrCode_Null);
1977 temp = BitVector_Create(bits,false);
1980 BitVector_Destroy(term);
1981 BitVector_Destroy(base);
1982 BitVector_Destroy(prod);
1983 BitVector_Destroy(rank);
1984 return(ErrCode_Null);
1986 BitVector_Empty(addr);
1989 while ((not error) and (length > 0))
1994 while ((not error) and (length > 0) and (count-- > 0))
1996 digit = (int) *(--string); length--;
1997 /* separate because isdigit() is likely a macro! */
1998 if (isdigit(digit) != 0)
2000 accu += ((N_word) digit - (N_word) '0') * powr;
2003 else error = ErrCode_Pars;
2010 BitVector_Copy(temp,rank);
2011 error = BitVector_Mul_Pos(prod,temp,term,false);
2016 if ((not init) and ((accu AND NOT mask) != 0)) error = ErrCode_Ovfl;
2021 BitVector_compute(addr,addr,prod,false,&carry);
2022 /* ignores sign change (= overflow) but not */
2023 /* numbers too large (= carry) for resulting bit vector */
2024 if (carry) error = ErrCode_Ovfl;
2031 BitVector_Copy(temp,rank);
2032 error = BitVector_Mul_Pos(rank,temp,base,false);
2044 BitVector_Destroy(term);
2045 BitVector_Destroy(base);
2046 BitVector_Destroy(prod);
2047 BitVector_Destroy(rank);
2048 BitVector_Destroy(temp);
2049 if (not error and minus)
2051 BitVector_Negate(addr,addr);
2052 if ((*(addr + size_(addr) - 1) AND mask AND NOT (mask >> 1)) == 0)
2053 error = ErrCode_Ovfl;
2059 charptr BitVector_to_Enum(wordptr addr)
2061 N_word bits = bits_(addr);
2076 sample = bits - 1; /* greatest possible index */
2077 length = 2; /* account for index 0 and terminating '\0' */
2078 digits = 1; /* account for intervening dashes and commas */
2081 while (sample >= (power-1))
2083 length += ++digits * factor * 6; /* 9,90,900,9000,... (9*2/3 = 6) */
2087 if (sample > --factor)
2090 factor = (N_word) ( sample / 3 );
2091 factor = (factor << 1) + (sample - (factor * 3));
2092 length += ++digits * factor;
2096 string = (charptr) malloc((size_t) length);
2097 if (string == NULL) return(NULL);
2101 while ((start < bits) and BitVector_interval_scan_inc(addr,start,&min,&max))
2104 if (comma) *target++ = (N_char) ',';
2107 target += BIT_VECTOR_int2str(target,min);
2113 target += BIT_VECTOR_int2str(target,min);
2114 *target++ = (N_char) ',';
2115 target += BIT_VECTOR_int2str(target,max);
2119 target += BIT_VECTOR_int2str(target,min);
2120 *target++ = (N_char) '-';
2121 target += BIT_VECTOR_int2str(target,max);
2126 *target = (N_char) '\0';
2130 ErrCode BitVector_from_Enum(wordptr addr, charptr string)
2132 ErrCode error = ErrCode_Ok;
2133 N_word bits = bits_(addr);
2137 N_word start = 0; /* silence compiler warning */
2141 BitVector_Empty(addr);
2142 while ((not error) and (state != 0))
2144 token = (N_word) *string;
2145 /* separate because isdigit() is likely a macro! */
2146 if (isdigit((int)token) != 0)
2148 string += BIT_VECTOR_str2int(string,&index);
2149 if (index < bits) token = (N_word) '0';
2150 else error = ErrCode_Indx;
2166 error = ErrCode_Pars;
2178 BIT_VECTOR_SET_BIT(addr,index)
2182 BIT_VECTOR_SET_BIT(addr,index)
2186 error = ErrCode_Pars;
2195 BitVector_Interval_Fill(addr,start,index);
2196 else if (start == index)
2197 BIT_VECTOR_SET_BIT(addr,index)
2198 else error = ErrCode_Ordr;
2202 error = ErrCode_Pars;
2216 error = ErrCode_Pars;
2227 error = ErrCode_Pars;
2237 void BitVector_Bit_Off(wordptr addr, N_int index) /* X = X \ {x} */
2239 if (index < bits_(addr)) BIT_VECTOR_CLR_BIT(addr,index)
2242 void BitVector_Bit_On(wordptr addr, N_int index) /* X = X + {x} */
2244 if (index < bits_(addr)) BIT_VECTOR_SET_BIT(addr,index)
2247 boolean BitVector_bit_flip(wordptr addr, N_int index) /* X=(X+{x})\(X*{x}) */
2251 if (index < bits_(addr)) return( BIT_VECTOR_FLP_BIT(addr,index,mask) );
2252 else return( false );
2255 boolean BitVector_bit_test(wordptr addr, N_int index) /* {x} in X ? */
2257 if (index < bits_(addr)) return( BIT_VECTOR_TST_BIT(addr,index) );
2258 else return( false );
2261 void BitVector_Bit_Copy(wordptr addr, N_int index, boolean bit)
2263 if (index < bits_(addr))
2265 if (bit) BIT_VECTOR_SET_BIT(addr,index)
2266 else BIT_VECTOR_CLR_BIT(addr,index)
2270 void BitVector_LSB(wordptr addr, boolean bit)
2272 if (bits_(addr) > 0)
2274 if (bit) *addr |= LSB;
2275 else *addr &= NOT LSB;
2279 void BitVector_MSB(wordptr addr, boolean bit)
2281 N_word size = size_(addr);
2282 N_word mask = mask_(addr);
2286 if (bit) *(addr+size) |= mask AND NOT (mask >> 1);
2287 else *(addr+size) &= NOT mask OR (mask >> 1);
2291 boolean BitVector_lsb_(wordptr addr)
2293 if (size_(addr) > 0) return( (*addr AND LSB) != 0 );
2294 else return( false );
2297 boolean BitVector_msb_(wordptr addr)
2299 N_word size = size_(addr);
2300 N_word mask = mask_(addr);
2303 return( (*(addr+size) AND (mask AND NOT (mask >> 1))) != 0 );
2308 boolean BitVector_rotate_left(wordptr addr)
2310 N_word size = size_(addr);
2311 N_word mask = mask_(addr);
2314 boolean carry_out = false;
2318 msb = mask AND NOT (mask >> 1);
2319 carry_in = ((*(addr+size-1) AND msb) != 0);
2322 carry_out = ((*addr AND MSB) != 0);
2324 if (carry_in) *addr |= LSB;
2325 carry_in = carry_out;
2328 carry_out = ((*addr AND msb) != 0);
2330 if (carry_in) *addr |= LSB;
2336 boolean BitVector_rotate_right(wordptr addr)
2338 N_word size = size_(addr);
2339 N_word mask = mask_(addr);
2342 boolean carry_out = false;
2346 msb = mask AND NOT (mask >> 1);
2347 carry_in = ((*addr AND LSB) != 0);
2350 carry_out = ((*addr AND LSB) != 0);
2352 if (carry_in) *addr |= msb;
2353 carry_in = carry_out;
2358 carry_out = ((*addr AND LSB) != 0);
2360 if (carry_in) *addr |= MSB;
2361 carry_in = carry_out;
2368 boolean BitVector_shift_left(wordptr addr, boolean carry_in)
2370 N_word size = size_(addr);
2371 N_word mask = mask_(addr);
2373 boolean carry_out = carry_in;
2377 msb = mask AND NOT (mask >> 1);
2380 carry_out = ((*addr AND MSB) != 0);
2382 if (carry_in) *addr |= LSB;
2383 carry_in = carry_out;
2386 carry_out = ((*addr AND msb) != 0);
2388 if (carry_in) *addr |= LSB;
2394 boolean BitVector_shift_right(wordptr addr, boolean carry_in)
2396 N_word size = size_(addr);
2397 N_word mask = mask_(addr);
2399 boolean carry_out = carry_in;
2403 msb = mask AND NOT (mask >> 1);
2406 carry_out = ((*addr AND LSB) != 0);
2408 if (carry_in) *addr |= msb;
2409 carry_in = carry_out;
2414 carry_out = ((*addr AND LSB) != 0);
2416 if (carry_in) *addr |= MSB;
2417 carry_in = carry_out;
2424 void BitVector_Move_Left(wordptr addr, N_int bits)
2431 count = bits AND MODMASK;
2432 words = bits >> LOGBITS;
2433 if (bits >= bits_(addr)) BitVector_Empty(addr);
2436 while (count-- > 0) BitVector_shift_left(addr,0);
2437 BitVector_Word_Insert(addr,0,words,true);
2442 void BitVector_Move_Right(wordptr addr, N_int bits)
2449 count = bits AND MODMASK;
2450 words = bits >> LOGBITS;
2451 if (bits >= bits_(addr)) BitVector_Empty(addr);
2454 while (count-- > 0) BitVector_shift_right(addr,0);
2455 BitVector_Word_Delete(addr,0,words,true);
2460 void BitVector_Insert(wordptr addr, N_int offset, N_int count, boolean clear)
2462 N_word bits = bits_(addr);
2465 if ((count > 0) and (offset < bits))
2467 last = offset + count;
2470 BitVector_Interval_Copy(addr,addr,last,offset,(bits-last));
2473 if (clear) BitVector_Interval_Empty(addr,offset,(last-1));
2477 void BitVector_Delete(wordptr addr, N_int offset, N_int count, boolean clear)
2479 N_word bits = bits_(addr);
2482 if ((count > 0) and (offset < bits))
2484 last = offset + count;
2487 BitVector_Interval_Copy(addr,addr,offset,last,(bits-last));
2489 else count = bits - offset;
2490 if (clear) BitVector_Interval_Empty(addr,(bits-count),(bits-1));
2494 boolean BitVector_increment(wordptr addr) /* X++ */
2496 N_word size = size_(addr);
2497 N_word mask = mask_(addr);
2498 wordptr last = addr + size - 1;
2499 boolean carry = true;
2504 while (carry and (size-- > 0))
2506 carry = (++(*addr++) == 0);
2513 boolean BitVector_decrement(wordptr addr) /* X-- */
2515 N_word size = size_(addr);
2516 N_word mask = mask_(addr);
2517 wordptr last = addr + size - 1;
2518 boolean carry = true;
2523 while (carry and (size-- > 0))
2525 carry = (*addr == 0);
2533 boolean BitVector_compute(wordptr X, wordptr Y, wordptr Z, boolean minus, boolean *carry)
2535 N_word size = size_(X);
2536 N_word mask = mask_(X);
2547 if (minus) cc = (*carry == 0);
2548 else cc = (*carry != 0);
2549 /* deal with (size-1) least significant full words first: */
2553 if (minus) zz = (N_word) NOT ( Z ? *Z++ : 0 );
2554 else zz = (N_word) ( Z ? *Z++ : 0 );
2555 lo = (yy AND LSB) + (zz AND LSB) + cc;
2556 hi = (yy >> 1) + (zz >> 1) + (lo >> 1);
2557 cc = ((hi AND MSB) != 0);
2558 *X++ = (hi << 1) OR (lo AND LSB);
2560 /* deal with most significant word (may be used only partially): */
2562 if (minus) zz = (N_word) NOT ( Z ? *Z : 0 );
2563 else zz = (N_word) ( Z ? *Z : 0 );
2565 if (mask == LSB) /* special case, only one bit used */
2575 if (NOT mask) /* not all bits are used, but more than one */
2578 vv = (yy AND mm) + (zz AND mm) + cc;
2579 mm = mask AND NOT mm;
2587 else /* other special case, all bits are used */
2590 lo = (yy AND mm) + (zz AND mm) + cc;
2592 hi = ((yy AND MSB) >> 1) + ((zz AND MSB) >> 1) + (vv >> 1);
2595 *X = (hi << 1) OR (lo AND mm);
2598 if (minus) *carry = (cc == 0);
2599 else *carry = (cc != 0);
2604 boolean BitVector_add(wordptr X, wordptr Y, wordptr Z, boolean *carry)
2606 return(BitVector_compute(X,Y,Z,false,carry));
2609 boolean BitVector_sub(wordptr X, wordptr Y, wordptr Z, boolean *carry)
2611 return(BitVector_compute(X,Y,Z,true,carry));
2614 boolean BitVector_inc(wordptr X, wordptr Y)
2616 boolean carry = true;
2618 return(BitVector_compute(X,Y,NULL,false,&carry));
2621 boolean BitVector_dec(wordptr X, wordptr Y)
2623 boolean carry = true;
2625 return(BitVector_compute(X,Y,NULL,true,&carry));
2628 void BitVector_Negate(wordptr X, wordptr Y)
2630 N_word size = size_(X);
2631 N_word mask = mask_(X);
2632 boolean carry = true;
2641 carry = (++(*X) == 0);
2649 void BitVector_Absolute(wordptr X, wordptr Y)
2651 N_word size = size_(Y);
2652 N_word mask = mask_(Y);
2656 if (*(Y+size-1) AND (mask AND NOT (mask >> 1))) BitVector_Negate(X,Y);
2657 else BitVector_Copy(X,Y);
2661 Z_int BitVector_Sign(wordptr addr)
2663 N_word size = size_(addr);
2664 N_word mask = mask_(addr);
2665 wordptr last = addr + size - 1;
2671 while (r and (size-- > 0)) r = ( *addr++ == 0 );
2673 if (r) return((Z_int) 0);
2676 if (*last AND (mask AND NOT (mask >> 1))) return((Z_int) -1);
2677 else return((Z_int) 1);
2681 ErrCode BitVector_Mul_Pos(wordptr X, wordptr Y, wordptr Z, boolean strict)
2694 - X, Y and Z must be distinct
2695 - X and Y must have equal sizes (whereas Z may be any size!)
2696 - Z should always contain the SMALLER of the two factors Y and Z
2698 - The contents of Y (and of X, of course) are destroyed
2699 (only Z is preserved!)
2702 if ((X == Y) or (X == Z) or (Y == Z)) return(ErrCode_Same);
2703 if (bits_(X) != bits_(Y)) return(ErrCode_Size);
2705 if (BitVector_is_empty(Y)) return(ErrCode_Ok); /* exit also taken if bits_(Y)==0 */
2706 if ((last = Set_Max(Z)) < 0L) return(ErrCode_Ok);
2707 limit = (N_word) last;
2708 sign = Y + size_(Y) - 1;
2711 mask &= NOT (mask >> 1);
2712 for ( count = 0; (ok and (count <= limit)); count++ )
2714 if ( BIT_VECTOR_TST_BIT(Z,count) )
2717 overflow = BitVector_compute(X,X,Y,false,&carry);
2718 if (strict) ok = not (carry or overflow);
2719 else ok = not carry;
2721 if (ok and (count < limit))
2723 carry = BitVector_shift_left(Y,0);
2726 overflow = ((*sign AND mask) != 0);
2727 ok = not (carry or overflow);
2729 else ok = not carry;
2732 if (ok) return(ErrCode_Ok); else return(ErrCode_Ovfl);
2735 ErrCode BitVector_Multiply(wordptr X, wordptr Y, wordptr Z)
2737 ErrCode error = ErrCode_Ok;
2738 N_word bit_x = bits_(X);
2739 N_word bit_y = bits_(Y);
2740 N_word bit_z = bits_(Z);
2755 - Y and Z must have equal sizes
2756 - X must have at least the same size as Y and Z but may be larger (!)
2758 - The contents of Y and Z are preserved
2759 - X may be identical with Y or Z (or both!)
2760 (in-place multiplication is possible!)
2763 if ((bit_y != bit_z) or (bit_x < bit_y)) return(ErrCode_Size);
2764 if (BitVector_is_empty(Y) or BitVector_is_empty(Z))
2770 A = BitVector_Create(bit_y,false);
2771 if (A == NULL) return(ErrCode_Null);
2772 B = BitVector_Create(bit_z,false);
2773 if (B == NULL) { BitVector_Destroy(A); return(ErrCode_Null); }
2776 msb = (mask AND NOT (mask >> 1));
2777 sgn_y = (((*(Y+size-1) &= mask) AND msb) != 0);
2778 sgn_z = (((*(Z+size-1) &= mask) AND msb) != 0);
2779 sgn_x = sgn_y XOR sgn_z;
2780 if (sgn_y) BitVector_Negate(A,Y); else BitVector_Copy(A,Y);
2781 if (sgn_z) BitVector_Negate(B,Z); else BitVector_Copy(B,Z);
2785 while (zero and (size-- > 0))
2787 zero &= (*(--ptr_y) == 0);
2788 zero &= (*(--ptr_z) == 0);
2790 if (*ptr_y > *ptr_z)
2794 A = BitVector_Resize(A,bit_x);
2795 if (A == NULL) { BitVector_Destroy(B); return(ErrCode_Null); }
2797 error = BitVector_Mul_Pos(X,A,B,true);
2803 B = BitVector_Resize(B,bit_x);
2804 if (B == NULL) { BitVector_Destroy(A); return(ErrCode_Null); }
2806 error = BitVector_Mul_Pos(X,B,A,true);
2808 if ((not error) and sgn_x) BitVector_Negate(X,X);
2809 BitVector_Destroy(A);
2810 BitVector_Destroy(B);
2815 ErrCode BitVector_Div_Pos(wordptr Q, wordptr X, wordptr Y, wordptr R)
2817 N_word bits = bits_(Q);
2822 boolean copy = false; /* flags whether valid rest is in R (0) or X (1) */
2826 - All bit vectors must have equal sizes
2827 - Q, X, Y and R must all be distinct bit vectors
2828 - Y must be non-zero (of course!)
2830 - The contents of X (and Q and R, of course) are destroyed
2831 (only Y is preserved!)
2834 if ((bits != bits_(X)) or (bits != bits_(Y)) or (bits != bits_(R)))
2835 return(ErrCode_Size);
2836 if ((Q == X) or (Q == Y) or (Q == R) or (X == Y) or (X == R) or (Y == R))
2837 return(ErrCode_Same);
2838 if (BitVector_is_empty(Y))
2839 return(ErrCode_Zero);
2842 BitVector_Copy(Q,X);
2843 if ((last = Set_Max(Q)) < 0L) return(ErrCode_Ok);
2844 bits = (N_word) ++last;
2847 addr = Q + (bits >> LOGBITS);
2848 mask = BITMASKTAB[bits AND MODMASK];
2849 flag = ((*addr AND mask) != 0);
2852 BitVector_shift_left(X,flag);
2854 BitVector_compute(R,X,Y,true,&flag);
2858 BitVector_shift_left(R,flag);
2860 BitVector_compute(X,R,Y,true,&flag);
2862 if (flag) *addr &= NOT mask;
2869 if (copy) BitVector_Copy(R,X);
2873 ErrCode BitVector_Divide(wordptr Q, wordptr X, wordptr Y, wordptr R)
2875 ErrCode error = ErrCode_Ok;
2876 N_word bits = bits_(Q);
2877 N_word size = size_(Q);
2878 N_word mask = mask_(Q);
2879 N_word msb = (mask AND NOT (mask >> 1));
2888 - All bit vectors must have equal sizes
2889 - Q and R must be two distinct bit vectors
2890 - Y must be non-zero (of course!)
2892 - The contents of X and Y are preserved
2893 - Q may be identical with X or Y (or both)
2894 (in-place division is possible!)
2895 - R may be identical with X or Y (or both)
2896 (but not identical with Q!)
2899 if ((bits != bits_(X)) or (bits != bits_(Y)) or (bits != bits_(R)))
2900 return(ErrCode_Size);
2902 return(ErrCode_Same);
2903 if (BitVector_is_empty(Y))
2904 return(ErrCode_Zero);
2906 if (BitVector_is_empty(X))
2913 A = BitVector_Create(bits,false);
2914 if (A == NULL) return(ErrCode_Null);
2915 B = BitVector_Create(bits,false);
2916 if (B == NULL) { BitVector_Destroy(A); return(ErrCode_Null); }
2918 sgn_x = (((*(X+size) &= mask) AND msb) != 0);
2919 sgn_y = (((*(Y+size) &= mask) AND msb) != 0);
2920 sgn_q = sgn_x XOR sgn_y;
2921 if (sgn_x) BitVector_Negate(A,X); else BitVector_Copy(A,X);
2922 if (sgn_y) BitVector_Negate(B,Y); else BitVector_Copy(B,Y);
2923 if (not (error = BitVector_Div_Pos(Q,A,B,R)))
2925 if (sgn_q) BitVector_Negate(Q,Q);
2926 if (sgn_x) BitVector_Negate(R,R);
2928 BitVector_Destroy(A);
2929 BitVector_Destroy(B);
2934 ErrCode BitVector_GCD(wordptr X, wordptr Y, wordptr Z)
2936 ErrCode error = ErrCode_Ok;
2937 N_word bits = bits_(X);
2938 N_word size = size_(X);
2939 N_word mask = mask_(X);
2940 N_word msb = (mask AND NOT (mask >> 1));
2952 - All bit vectors must have equal sizes
2954 - The contents of Y and Z are preserved
2955 - X may be identical with Y or Z (or both)
2956 (in-place is possible!)
2957 - GCD(0,z) == GCD(z,0) == z
2958 - negative values are handled correctly
2961 if ((bits != bits_(Y)) or (bits != bits_(Z))) return(ErrCode_Size);
2962 if (BitVector_is_empty(Y))
2964 if (X != Z) BitVector_Copy(X,Z);
2967 if (BitVector_is_empty(Z))
2969 if (X != Y) BitVector_Copy(X,Y);
2972 Q = BitVector_Create(bits,false);
2975 return(ErrCode_Null);
2977 R = BitVector_Create(bits,false);
2980 BitVector_Destroy(Q);
2981 return(ErrCode_Null);
2983 A = BitVector_Create(bits,false);
2986 BitVector_Destroy(Q);
2987 BitVector_Destroy(R);
2988 return(ErrCode_Null);
2990 B = BitVector_Create(bits,false);
2993 BitVector_Destroy(Q);
2994 BitVector_Destroy(R);
2995 BitVector_Destroy(A);
2996 return(ErrCode_Null);
2999 sgn_a = (((*(Y+size) &= mask) AND msb) != 0);
3000 sgn_b = (((*(Z+size) &= mask) AND msb) != 0);
3001 if (sgn_a) BitVector_Negate(A,Y); else BitVector_Copy(A,Y);
3002 if (sgn_b) BitVector_Negate(B,Z); else BitVector_Copy(B,Z);
3005 if (not (error = BitVector_Div_Pos(Q,A,B,R)))
3007 if (BitVector_is_empty(R)) break;
3008 T = A; sgn_r = sgn_a;
3009 A = B; sgn_a = sgn_b;
3010 B = R; sgn_b = sgn_r;
3016 if (sgn_b) BitVector_Negate(X,B); else BitVector_Copy(X,B);
3018 BitVector_Destroy(Q);
3019 BitVector_Destroy(R);
3020 BitVector_Destroy(A);
3021 BitVector_Destroy(B);
3025 ErrCode BitVector_GCD2(wordptr U, wordptr V, wordptr W, wordptr X, wordptr Y)
3027 ErrCode error = ErrCode_Ok;
3028 N_word bits = bits_(U);
3029 N_word size = size_(U);
3030 N_word mask = mask_(U);
3031 N_word msb = (mask AND NOT (mask >> 1));
3056 - All bit vectors must have equal sizes
3057 - U, V, and W must all be distinct bit vectors
3059 - The contents of X and Y are preserved
3060 - U, V and W may be identical with X or Y (or both,
3061 provided that U, V and W are mutually distinct)
3062 (i.e., in-place is possible!)
3063 - GCD(0,z) == GCD(z,0) == z
3064 - negative values are handled correctly
3067 if ((bits != bits_(V)) or
3068 (bits != bits_(W)) or
3069 (bits != bits_(X)) or
3072 return(ErrCode_Size);
3074 if ((U == V) or (U == W) or (V == W))
3076 return(ErrCode_Same);
3078 if (BitVector_is_empty(X))
3080 if (U != Y) BitVector_Copy(U,Y);
3086 if (BitVector_is_empty(Y))
3088 if (U != X) BitVector_Copy(U,X);
3094 if ((L = BitVector_Create_List(bits,false,11)) == NULL)
3096 return(ErrCode_Null);
3110 sgn_a = (((*(X+size) &= mask) AND msb) != 0);
3111 sgn_b = (((*(Y+size) &= mask) AND msb) != 0);
3112 if (sgn_a) BitVector_Negate(A,X); else BitVector_Copy(A,X);
3113 if (sgn_b) BitVector_Negate(B,Y); else BitVector_Copy(B,Y);
3114 BitVector_Empty(X1);
3115 BitVector_Empty(X2);
3117 BitVector_Empty(Y1);
3118 BitVector_Empty(Y2);
3124 if ((error = BitVector_Div_Pos(Q,A,B,R)))
3128 if (BitVector_is_empty(R))
3132 sgn_q = sgn_a XOR sgn_b;
3134 if (sgn_x) BitVector_Negate(Z,X2); else BitVector_Copy(Z,X2);
3135 if ((error = BitVector_Mul_Pos(X3,Z,Q,true)))
3139 minus = not (sgn_x XOR sgn_q);
3141 if (BitVector_compute(X3,X1,X3,minus,&carry))
3143 error = ErrCode_Ovfl;
3146 sgn_x = (((*(X3+size) &= mask) AND msb) != 0);
3148 if (sgn_y) BitVector_Negate(Z,Y2); else BitVector_Copy(Z,Y2);
3149 if ((error = BitVector_Mul_Pos(Y3,Z,Q,true)))
3153 minus = not (sgn_y XOR sgn_q);
3155 if (BitVector_compute(Y3,Y1,Y3,minus,&carry))
3157 error = ErrCode_Ovfl;
3160 sgn_y = (((*(Y3+size) &= mask) AND msb) != 0);
3162 T = A; sgn_r = sgn_a;
3163 A = B; sgn_a = sgn_b;
3164 B = R; sgn_b = sgn_r;
3179 if (sgn_b) BitVector_Negate(U,B); else BitVector_Copy(U,B);
3180 BitVector_Copy(V,X2);
3181 BitVector_Copy(W,Y2);
3183 BitVector_Destroy_List(L,11);
3187 ErrCode BitVector_Power(wordptr X, wordptr Y, wordptr Z)
3189 ErrCode error = ErrCode_Ok;
3190 N_word bits = bits_(X);
3191 boolean first = true;
3199 - X must have at least the same size as Y but may be larger (!)
3200 - X may not be identical with Z
3201 - Z must be positive
3203 - The contents of Y and Z are preserved
3206 if (X == Z) return(ErrCode_Same);
3207 if (bits < bits_(Y)) return(ErrCode_Size);
3208 if (BitVector_msb_(Z)) return(ErrCode_Expo);
3209 if ((last = Set_Max(Z)) < 0L)
3211 if (bits < 2) return(ErrCode_Ovfl);
3214 return(ErrCode_Ok); /* anything ^ 0 == 1 */
3216 if (BitVector_is_empty(Y))
3218 if (X != Y) BitVector_Empty(X);
3219 return(ErrCode_Ok); /* 0 ^ anything not zero == 0 */
3221 T = BitVector_Create(bits,false);
3222 if (T == NULL) return(ErrCode_Null);
3223 limit = (N_word) last;
3224 for ( count = 0; ((!error) and (count <= limit)); count++ )
3226 if ( BIT_VECTOR_TST_BIT(Z,count) )
3231 if (count) { BitVector_Copy(X,T); }
3232 else { if (X != Y) BitVector_Copy(X,Y); }
3234 else error = BitVector_Multiply(X,T,X); /* order important because T > X */
3236 if ((!error) and (count < limit))
3238 if (count) error = BitVector_Multiply(T,T,T);
3239 else error = BitVector_Multiply(T,Y,Y);
3242 BitVector_Destroy(T);
3246 void BitVector_Block_Store(wordptr addr, charptr buffer, N_int length)
3248 N_word size = size_(addr);
3249 N_word mask = mask_(addr);
3253 /* provide translation for independence of endian-ness: */
3259 for ( count = 0; (length > 0) and (count < BITS); count += 8 )
3261 value |= (((N_word) *buffer++) << count); length--;
3269 charptr BitVector_Block_Read(wordptr addr, N_intptr length)
3271 N_word size = size_(addr);
3277 /* provide translation for independence of endian-ness: */
3278 *length = size << FACTOR;
3279 buffer = (charptr) malloc((size_t) ((*length)+1));
3280 if (buffer == NULL) return(NULL);
3284 *(addr+size-1) &= mask_(addr);
3291 *target++ = (N_char) (value AND 0x00FF);
3292 if (count > 0) value >>= 8;
3296 *target = (N_char) '\0';
3300 void BitVector_Word_Store(wordptr addr, N_int offset, N_int value)
3302 N_word size = size_(addr);
3306 if (offset < size) *(addr+offset) = value;
3307 *(addr+size-1) &= mask_(addr);
3311 N_int BitVector_Word_Read(wordptr addr, N_int offset)
3313 N_word size = size_(addr);
3317 *(addr+size-1) &= mask_(addr);
3318 if (offset < size) return( *(addr+offset) );
3320 return( (N_int) 0 );
3323 void BitVector_Word_Insert(wordptr addr, N_int offset, N_int count,
3326 N_word size = size_(addr);
3327 N_word mask = mask_(addr);
3328 wordptr last = addr+size-1;
3333 if (offset > size) offset = size;
3334 BIT_VECTOR_ins_words(addr+offset,size-offset,count,clear);
3339 void BitVector_Word_Delete(wordptr addr, N_int offset, N_int count,
3342 N_word size = size_(addr);
3343 N_word mask = mask_(addr);
3344 wordptr last = addr+size-1;
3349 if (offset > size) offset = size;
3350 BIT_VECTOR_del_words(addr+offset,size-offset,count,clear);
3355 void BitVector_Chunk_Store(wordptr addr, N_int chunksize, N_int offset,
3358 N_word bits = bits_(addr);
3362 if ((chunksize > 0) and (offset < bits))
3364 if (chunksize > LONGBITS) chunksize = LONGBITS;
3365 if ((offset + chunksize) > bits) chunksize = bits - offset;
3366 addr += offset >> LOGBITS;
3368 while (chunksize > 0)
3370 mask = (N_word) (~0L << offset);
3371 bits = offset + chunksize;
3374 mask &= (N_word) ~(~0L << bits);
3377 else bits = BITS - offset;
3378 temp = (N_word) (value << offset);
3389 N_long BitVector_Chunk_Read(wordptr addr, N_int chunksize, N_int offset)
3391 N_word bits = bits_(addr);
3392 N_word chunkbits = 0;
3397 if ((chunksize > 0) and (offset < bits))
3399 if (chunksize > LONGBITS) chunksize = LONGBITS;
3400 if ((offset + chunksize) > bits) chunksize = bits - offset;
3401 addr += offset >> LOGBITS;
3403 while (chunksize > 0)
3405 bits = offset + chunksize;
3408 mask = (N_word) ~(~0L << bits);
3413 mask = (N_word) ~0L;
3414 bits = BITS - offset;
3416 temp = (N_long) ((*addr++ AND mask) >> offset);
3417 value |= temp << chunkbits;
3426 /*******************/
3427 /* set operations: */
3428 /*******************/
3430 void Set_Union(wordptr X, wordptr Y, wordptr Z) /* X = Y + Z */
3432 N_word bits = bits_(X);
3433 N_word size = size_(X);
3434 N_word mask = mask_(X);
3436 if ((size > 0) and (bits == bits_(Y)) and (bits == bits_(Z)))
3438 while (size-- > 0) *X++ = *Y++ OR *Z++;
3443 void Set_Intersection(wordptr X, wordptr Y, wordptr Z) /* X = Y * Z */
3445 N_word bits = bits_(X);
3446 N_word size = size_(X);
3447 N_word mask = mask_(X);
3449 if ((size > 0) and (bits == bits_(Y)) and (bits == bits_(Z)))
3451 while (size-- > 0) *X++ = *Y++ AND *Z++;
3456 void Set_Difference(wordptr X, wordptr Y, wordptr Z) /* X = Y \ Z */
3458 N_word bits = bits_(X);
3459 N_word size = size_(X);
3460 N_word mask = mask_(X);
3462 if ((size > 0) and (bits == bits_(Y)) and (bits == bits_(Z)))
3464 while (size-- > 0) *X++ = *Y++ AND NOT *Z++;
3469 void Set_ExclusiveOr(wordptr X, wordptr Y, wordptr Z) /* X=(Y+Z)\(Y*Z) */
3471 N_word bits = bits_(X);
3472 N_word size = size_(X);
3473 N_word mask = mask_(X);
3475 if ((size > 0) and (bits == bits_(Y)) and (bits == bits_(Z)))
3477 while (size-- > 0) *X++ = *Y++ XOR *Z++;
3482 void Set_Complement(wordptr X, wordptr Y) /* X = ~Y */
3484 N_word size = size_(X);
3485 N_word mask = mask_(X);
3487 if ((size > 0) and (bits_(X) == bits_(Y)))
3489 while (size-- > 0) *X++ = NOT *Y++;
3494 /******************/
3495 /* set functions: */
3496 /******************/
3498 boolean Set_subset(wordptr X, wordptr Y) /* X subset Y ? */
3500 N_word size = size_(X);
3503 if ((size > 0) and (bits_(X) == bits_(Y)))
3506 while (r and (size-- > 0)) r = ((*X++ AND NOT *Y++) == 0);
3511 N_int Set_Norm(wordptr addr) /* = | X | */
3517 byte = (byteptr) addr;
3518 bytes = size_(addr) << FACTOR;
3522 n += BitVector_BYTENORM[*byte++];
3527 N_int Set_Norm2(wordptr addr) /* = | X | */
3529 N_word size = size_(addr);
3537 w1 = NOT (w0 = *addr++);
3544 if (w0 == 0) n += k;
3550 N_int Set_Norm3(wordptr addr) /* = | X | */
3552 N_word size = size_(addr);
3568 Z_long Set_Min(wordptr addr) /* = min(X) */
3570 boolean empty = true;
3571 N_word size = size_(addr);
3573 N_word c = 0; /* silence compiler warning */
3575 while (empty and (size-- > 0))
3577 if ((c = *addr++)) empty = false; else i++;
3579 if (empty) return((Z_long) LONG_MAX); /* plus infinity */
3581 while (not (c AND LSB))
3589 Z_long Set_Max(wordptr addr) /* = max(X) */
3591 boolean empty = true;
3592 N_word size = size_(addr);
3594 N_word c = 0; /* silence compiler warning */
3597 while (empty and (size-- > 0))
3599 if ((c = *addr--)) empty = false; else i--;
3601 if (empty) return((Z_long) LONG_MIN); /* minus infinity */
3603 while (not (c AND MSB))
3608 return((Z_long) --i);
3611 /**********************************/
3612 /* matrix-of-booleans operations: */
3613 /**********************************/
3615 void Matrix_Multiplication(wordptr X, N_int rowsX, N_int colsX,
3616 wordptr Y, N_int rowsY, N_int colsY,
3617 wordptr Z, N_int rowsZ, N_int colsZ)
3629 if ((colsY == rowsZ) and (rowsX == rowsY) and (colsX == colsZ) and
3630 (bits_(X) == rowsX*colsX) and
3631 (bits_(Y) == rowsY*colsY) and
3632 (bits_(Z) == rowsZ*colsZ))
3634 for ( i = 0; i < rowsY; i++ )
3638 for ( j = 0; j < colsZ; j++ )
3642 for ( k = 0; k < colsY; k++ )
3645 indxZ = k * colsZ + j;
3646 if ( BIT_VECTOR_TST_BIT(Y,indxY) &&
3647 BIT_VECTOR_TST_BIT(Z,indxZ) ) sum ^= 1;
3649 if (sum) BIT_VECTOR_SET_BIT(X,indxX)
3650 else BIT_VECTOR_CLR_BIT(X,indxX)
3656 void Matrix_Product(wordptr X, N_int rowsX, N_int colsX,
3657 wordptr Y, N_int rowsY, N_int colsY,
3658 wordptr Z, N_int rowsZ, N_int colsZ)
3670 if ((colsY == rowsZ) and (rowsX == rowsY) and (colsX == colsZ) and
3671 (bits_(X) == rowsX*colsX) and
3672 (bits_(Y) == rowsY*colsY) and
3673 (bits_(Z) == rowsZ*colsZ))
3675 for ( i = 0; i < rowsY; i++ )
3679 for ( j = 0; j < colsZ; j++ )
3683 for ( k = 0; k < colsY; k++ )
3686 indxZ = k * colsZ + j;
3687 if ( BIT_VECTOR_TST_BIT(Y,indxY) &&
3688 BIT_VECTOR_TST_BIT(Z,indxZ) ) sum |= 1;
3690 if (sum) BIT_VECTOR_SET_BIT(X,indxX)
3691 else BIT_VECTOR_CLR_BIT(X,indxX)
3697 void Matrix_Closure(wordptr addr, N_int rows, N_int cols)
3709 if ((rows == cols) and (bits_(addr) == rows*cols))
3711 for ( i = 0; i < rows; i++ )
3714 BIT_VECTOR_SET_BIT(addr,ii)
3716 for ( k = 0; k < rows; k++ )
3719 for ( i = 0; i < rows; i++ )
3723 for ( j = 0; j < rows; j++ )
3727 if ( BIT_VECTOR_TST_BIT(addr,ik) &&
3728 BIT_VECTOR_TST_BIT(addr,kj) )
3729 BIT_VECTOR_SET_BIT(addr,ij)
3736 void Matrix_Transpose(wordptr X, N_int rowsX, N_int colsX,
3737 wordptr Y, N_int rowsY, N_int colsY)
3754 /* BEWARE that "in-place" is ONLY possible if the matrix is quadratic!! */
3756 if ((rowsX == colsY) and (colsX == rowsY) and
3757 (bits_(X) == rowsX*colsX) and
3758 (bits_(Y) == rowsY*colsY))
3760 if (rowsY == colsY) /* in-place is possible! */
3762 for ( i = 0; i < rowsY; i++ )
3765 for ( j = 0; j < i; j++ )
3770 addij = ij >> LOGBITS;
3771 addji = ji >> LOGBITS;
3772 bitij = BITMASKTAB[ij AND MODMASK];
3773 bitji = BITMASKTAB[ji AND MODMASK];
3774 swap = ((*(Y+addij) AND bitij) != 0);
3775 if ((*(Y+addji) AND bitji) != 0)
3776 *(X+addij) |= bitij;
3778 *(X+addij) &= NOT bitij;
3780 *(X+addji) |= bitji;
3782 *(X+addji) &= NOT bitji;
3785 addii = ii >> LOGBITS;
3786 bitii = BITMASKTAB[ii AND MODMASK];
3787 if ((*(Y+addii) AND bitii) != 0)
3788 *(X+addii) |= bitii;
3790 *(X+addii) &= NOT bitii;
3793 else /* rowsX != colsX, in-place is NOT possible! */
3795 for ( i = 0; i < rowsY; i++ )
3798 for ( j = 0; j < colsY; j++ )
3803 addij = ij >> LOGBITS;
3804 addji = ji >> LOGBITS;
3805 bitij = BITMASKTAB[ij AND MODMASK];
3806 bitji = BITMASKTAB[ji AND MODMASK];
3807 if ((*(Y+addij) AND bitij) != 0)
3808 *(X+addji) |= bitji;
3810 *(X+addji) &= NOT bitji;
3817 /*****************************************************************************/
3819 /*****************************************************************************/
3820 /* VERSION HISTORY: */
3821 /*****************************************************************************/
3823 /* Version 6.4 03.10.04 Added C++ comp. directives. Improved "Norm()". */
3824 /* Version 6.3 28.09.02 Added "Create_List()" and "GCD2()". */
3825 /* Version 6.2 15.09.02 Overhauled error handling. Fixed "GCD()". */
3826 /* Version 6.1 08.10.01 Make VMS linker happy: _lsb,_msb => _lsb_,_msb_ */
3827 /* Version 6.0 08.10.00 Corrected overflow handling. */
3828 /* Version 5.8 14.07.00 Added "Power()". Changed "Copy()". */
3829 /* Version 5.7 19.05.99 Quickened "Div_Pos()". Added "Product()". */
3830 /* Version 5.6 02.11.98 Leading zeros eliminated in "to_Hex()". */
3831 /* Version 5.5 21.09.98 Fixed bug of uninitialized "error" in Multiply. */
3832 /* Version 5.4 07.09.98 Fixed bug of uninitialized "error" in Divide. */
3833 /* Version 5.3 12.05.98 Improved Norm. Completed history. */
3834 /* Version 5.2 31.03.98 Improved Norm. */
3835 /* Version 5.1 09.03.98 No changes. */
3836 /* Version 5.0 01.03.98 Major additions and rewrite. */
3837 /* Version 4.2 16.07.97 Added is_empty, is_full. */
3838 /* Version 4.1 30.06.97 Added word-ins/del, move-left/right, inc/dec. */
3839 /* Version 4.0 23.04.97 Rewrite. Added bit shift and bool. matrix ops. */
3840 /* Version 3.2 04.02.97 Added interval methods. */
3841 /* Version 3.1 21.01.97 Fixed bug on 64 bit machines. */
3842 /* Version 3.0 12.01.97 Added flip. */
3843 /* Version 2.0 14.12.96 Efficiency and consistency improvements. */
3844 /* Version 1.1 08.01.96 Added Resize and ExclusiveOr. */
3845 /* Version 1.0 14.12.95 First version under UNIX (with Perl module). */
3846 /* Version 0.9 01.11.93 First version of C library under MS-DOS. */
3847 /* Version 0.1 ??.??.89 First version in Turbo Pascal under CP/M. */
3849 /*****************************************************************************/
3851 /*****************************************************************************/
3854 /* mailto:sb@engelschall.com */
3855 /* http://www.engelschall.com/u/sb/download/ */
3857 /*****************************************************************************/
3859 /*****************************************************************************/
3861 /* Copyright (c) 1995 - 2004 by Steffen Beyer. */
3862 /* All rights reserved. */
3864 /*****************************************************************************/
3866 /*****************************************************************************/
3868 /* This library is free software; you can redistribute it and/or */
3869 /* modify it under the terms of the GNU Library General Public */
3870 /* License as published by the Free Software Foundation; either */
3871 /* version 2 of the License, or (at your option) any later version. */
3873 /* This library is distributed in the hope that it will be useful, */
3874 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
3875 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU */
3876 /* Library General Public License for more details. */
3878 /* You should have received a copy of the GNU Library General Public */
3879 /* License along with this library; if not, write to the */
3880 /* Free Software Foundation, Inc., */
3881 /* 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
3883 /* or download a copy from ftp://ftp.gnu.org/pub/gnu/COPYING.LIB-2.0 */
3885 /*****************************************************************************/