5 /*****************************************************************************/
6 /* MODULE NAME: BitVector.c MODULE TYPE: (adt) */
7 /*****************************************************************************/
9 /*****************************************************************************/
10 #include <ctype.h> /* MODULE TYPE: (sys) */
11 #include <limits.h> /* MODULE TYPE: (sys) */
12 #include <string.h> /* MODULE TYPE: (sys) */
13 /*****************************************************************************/
14 /* MODULE INTERFACE: */
15 /*****************************************************************************/
19 #define and && /* logical (boolean) operators: lower case */
23 #define AND & /* binary (bitwise) operators: UPPER CASE */
31 #define mod % /* arithmetic operators */
34 #define blockdef(name,size) unsigned char name[size]
35 #define blocktypedef(name,size) typedef unsigned char name[size]
37 /*****************************************************************************/
38 /* MODULE RESOURCES: */
39 /*****************************************************************************/
41 #define bits_(BitVector) *(BitVector-3)
42 #define size_(BitVector) *(BitVector-2)
43 #define mask_(BitVector) *(BitVector-1)
45 #define ERRCODE_TYPE "sizeof(word) > sizeof(size_t)"
46 #define ERRCODE_BITS "bits(word) != sizeof(word)*8"
47 #define ERRCODE_WORD "bits(word) < 16"
48 #define ERRCODE_LONG "bits(word) > bits(long)"
49 #define ERRCODE_POWR "bits(word) != 2^x"
50 #define ERRCODE_LOGA "bits(word) != 2^ld(bits(word))"
51 #define ERRCODE_NULL "unable to allocate memory"
52 #define ERRCODE_INDX "index out of range"
53 #define ERRCODE_ORDR "minimum > maximum index"
54 #define ERRCODE_SIZE "bit vector size mismatch"
55 #define ERRCODE_PARS "input string syntax error"
56 #define ERRCODE_OVFL "numeric overflow error"
57 #define ERRCODE_SAME "result vector(s) must be distinct"
58 #define ERRCODE_EXPO "exponent must be positive"
59 #define ERRCODE_ZERO "division by zero error"
60 #define ERRCODE_OOPS "unexpected internal error - please contact author"
62 const N_int BitVector_BYTENORM[256] =
64 0x00, 0x01, 0x01, 0x02, 0x01, 0x02, 0x02, 0x03,
65 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, /* 0x00 */
66 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
67 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x10 */
68 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
69 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x20 */
70 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
71 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x30 */
72 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
73 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x40 */
74 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
75 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x50 */
76 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
77 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x60 */
78 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
79 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0x70 */
80 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
81 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x80 */
82 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
83 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x90 */
84 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
85 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0xA0 */
86 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
87 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0xB0 */
88 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
89 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0xC0 */
90 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
91 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0xD0 */
92 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
93 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0xE0 */
94 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07,
95 0x05, 0x06, 0x06, 0x07, 0x06, 0x07, 0x07, 0x08 /* 0xF0 */
98 /*****************************************************************************/
99 /* MODULE IMPLEMENTATION: */
100 /*****************************************************************************/
102 /**********************************************/
103 /* global implementation-intrinsic constants: */
104 /**********************************************/
106 #define BIT_VECTOR_HIDDEN_WORDS 3
108 /*****************************************************************/
109 /* global machine-dependent constants (set by "BitVector_Boot"): */
110 /*****************************************************************/
112 static N_word BITS; /* = # of bits in machine word (must be power of 2) */
113 static N_word MODMASK; /* = BITS - 1 (mask for calculating modulo BITS) */
114 static N_word LOGBITS; /* = ld(BITS) (logarithmus dualis) */
115 static N_word FACTOR; /* = ld(BITS / 8) (ld of # of bytes) */
117 static N_word LSB = 1; /* = mask for least significant bit */
118 static N_word MSB; /* = mask for most significant bit */
120 static N_word LONGBITS; /* = # of bits in unsigned long */
122 static N_word LOG10; /* = logarithm to base 10 of BITS - 1 */
123 static N_word EXP10; /* = largest possible power of 10 in signed int */
125 /********************************************************************/
126 /* global bit mask table for fast access (set by "BitVector_Boot"): */
127 /********************************************************************/
129 static wordptr BITMASKTAB;
131 /*****************************/
132 /* global macro definitions: */
133 /*****************************/
135 #define BIT_VECTOR_ZERO_WORDS(target,count) \
136 while (count-- > 0) *target++ = 0;
138 #define BIT_VECTOR_FILL_WORDS(target,fill,count) \
139 while (count-- > 0) *target++ = fill;
141 #define BIT_VECTOR_FLIP_WORDS(target,flip,count) \
142 while (count-- > 0) *target++ ^= flip;
144 #define BIT_VECTOR_COPY_WORDS(target,source,count) \
145 while (count-- > 0) *target++ = *source++;
147 #define BIT_VECTOR_BACK_WORDS(target,source,count) \
148 { target += count; source += count; while (count-- > 0) *--target = *--source; }
150 #define BIT_VECTOR_CLR_BIT(address,index) \
151 *(address+(index>>LOGBITS)) &= NOT BITMASKTAB[index AND MODMASK];
153 #define BIT_VECTOR_SET_BIT(address,index) \
154 *(address+(index>>LOGBITS)) |= BITMASKTAB[index AND MODMASK];
156 #define BIT_VECTOR_TST_BIT(address,index) \
157 ((*(address+(index>>LOGBITS)) AND BITMASKTAB[index AND MODMASK]) != 0)
159 #define BIT_VECTOR_FLP_BIT(address,index,mask) \
160 (mask = BITMASKTAB[index AND MODMASK]), \
161 (((*(addr+(index>>LOGBITS)) ^= mask) AND mask) != 0)
163 #define BIT_VECTOR_DIGITIZE(type,value,digit) \
164 value = (type) ((digit = value) / 10); \
165 digit -= value * 10; \
168 /*********************************************************/
169 /* private low-level functions (potentially dangerous!): */
170 /*********************************************************/
172 static N_word power10(N_word x)
176 while (x-- > 0) y *= 10;
180 static void BIT_VECTOR_zro_words(wordptr addr, N_word count)
182 BIT_VECTOR_ZERO_WORDS(addr,count)
185 static void BIT_VECTOR_cpy_words(wordptr target, wordptr source, N_word count)
187 BIT_VECTOR_COPY_WORDS(target,source,count)
190 static void BIT_VECTOR_mov_words(wordptr target, wordptr source, N_word count)
192 if (target != source)
194 if (target < source) BIT_VECTOR_COPY_WORDS(target,source,count)
195 else BIT_VECTOR_BACK_WORDS(target,source,count)
199 static void BIT_VECTOR_ins_words(wordptr addr, N_word total, N_word count,
204 if ((total > 0) and (count > 0))
206 if (count > total) count = total;
207 length = total - count;
208 if (length > 0) BIT_VECTOR_mov_words(addr+count,addr,length);
209 if (clear) BIT_VECTOR_zro_words(addr,count);
213 static void BIT_VECTOR_del_words(wordptr addr, N_word total, N_word count,
218 if ((total > 0) and (count > 0))
220 if (count > total) count = total;
221 length = total - count;
222 if (length > 0) BIT_VECTOR_mov_words(addr,addr+count,length);
223 if (clear) BIT_VECTOR_zro_words(addr+length,count);
227 static void BIT_VECTOR_reverse(charptr string, N_word length)
234 last = string + length - 1;
235 while (string < last)
246 static N_word BIT_VECTOR_int2str(charptr string, N_word value)
258 BIT_VECTOR_DIGITIZE(N_word,value,digit)
259 *work++ = (N_char) digit;
262 BIT_VECTOR_reverse(string,length);
267 *work++ = (N_char) '0';
272 static N_word BIT_VECTOR_str2int(charptr string, N_word *value)
279 digit = (N_word) *string++;
280 /* separate because isdigit() is likely a macro! */
281 while (isdigit((int)digit) != 0)
284 digit -= (N_word) '0';
285 if (*value) *value *= 10;
287 digit = (N_word) *string++;
292 /********************************************/
293 /* routine to convert error code to string: */
294 /********************************************/
296 const char * BitVector_Error(ErrCode error)
300 case ErrCode_Ok: return( NULL ); break;
301 case ErrCode_Type: return( ERRCODE_TYPE ); break;
302 case ErrCode_Bits: return( ERRCODE_BITS ); break;
303 case ErrCode_Word: return( ERRCODE_WORD ); break;
304 case ErrCode_Long: return( ERRCODE_LONG ); break;
305 case ErrCode_Powr: return( ERRCODE_POWR ); break;
306 case ErrCode_Loga: return( ERRCODE_LOGA ); break;
307 case ErrCode_Null: return( ERRCODE_NULL ); break;
308 case ErrCode_Indx: return( ERRCODE_INDX ); break;
309 case ErrCode_Ordr: return( ERRCODE_ORDR ); break;
310 case ErrCode_Size: return( ERRCODE_SIZE ); break;
311 case ErrCode_Pars: return( ERRCODE_PARS ); break;
312 case ErrCode_Ovfl: return( ERRCODE_OVFL ); break;
313 case ErrCode_Same: return( ERRCODE_SAME ); break;
314 case ErrCode_Expo: return( ERRCODE_EXPO ); break;
315 case ErrCode_Zero: return( ERRCODE_ZERO ); break;
316 default: return( ERRCODE_OOPS ); break;
320 /*****************************************/
321 /* automatic self-configuration routine: */
322 /*****************************************/
324 /*******************************************************/
326 /* MUST be called once prior to any other function */
327 /* to initialize the machine dependent constants */
328 /* of this package! (But call only ONCE, or you */
329 /* will suffer memory leaks!) */
331 /*******************************************************/
333 ErrCode BitVector_Boot(void)
335 N_long longsample = 1L;
339 if (sizeof(N_word) > sizeof(size_t)) return(ErrCode_Type);
342 while (sample <<= 1) BITS++; /* determine # of bits in a machine word */
344 if (BITS != (sizeof(N_word) << 3)) return(ErrCode_Bits);
346 if (BITS < 16) return(ErrCode_Word);
349 while (longsample <<= 1) LONGBITS++; /* = # of bits in an unsigned long */
351 if (BITS > LONGBITS) return(ErrCode_Long);
355 lsb = (sample AND LSB);
356 while ((sample >>= 1) and (not lsb))
359 lsb = (sample AND LSB);
362 if (sample) return(ErrCode_Powr); /* # of bits is not a power of 2! */
364 if (BITS != (LSB << LOGBITS)) return(ErrCode_Loga);
367 FACTOR = LOGBITS - 3; /* ld(BITS / 8) = ld(BITS) - ld(8) = ld(BITS) - 3 */
368 MSB = (LSB << MODMASK);
370 BITMASKTAB = (wordptr) yasm_xmalloc((size_t) (BITS << FACTOR));
372 if (BITMASKTAB == NULL) return(ErrCode_Null);
374 for ( sample = 0; sample < BITS; sample++ )
376 BITMASKTAB[sample] = (LSB << sample);
379 LOG10 = (N_word) (MODMASK * 0.30103); /* = (BITS - 1) * ( ln 2 / ln 10 ) */
380 EXP10 = power10(LOG10);
385 void BitVector_Shutdown(void)
387 if (BITMASKTAB) yasm_xfree(BITMASKTAB);
390 N_word BitVector_Size(N_int bits) /* bit vector size (# of words) */
394 size = bits >> LOGBITS;
395 if (bits AND MODMASK) size++;
399 N_word BitVector_Mask(N_int bits) /* bit vector mask (unused bits) */
403 mask = bits AND MODMASK;
404 if (mask) mask = (N_word) ~(~0L << mask); else mask = (N_word) ~0L;
408 const char * BitVector_Version(void)
413 N_int BitVector_Word_Bits(void)
418 N_int BitVector_Long_Bits(void)
423 /********************************************************************/
425 /* WARNING: Do not "free()" constant character strings, i.e., */
426 /* don't call "BitVector_Dispose()" for strings returned */
427 /* by "BitVector_Error()" or "BitVector_Version()"! */
429 /* ONLY call this function for strings allocated with "malloc()", */
430 /* i.e., the strings returned by the functions "BitVector_to_*()" */
431 /* and "BitVector_Block_Read()"! */
433 /********************************************************************/
435 void BitVector_Dispose(charptr string) /* free string */
437 if (string != NULL) yasm_xfree((voidptr) string);
440 void BitVector_Destroy(wordptr addr) /* free bitvec */
444 addr -= BIT_VECTOR_HIDDEN_WORDS;
445 yasm_xfree((voidptr) addr);
449 void BitVector_Destroy_List(listptr list, N_int count) /* free list */
458 BitVector_Destroy(*slot++);
460 free((voidptr) list);
464 wordptr BitVector_Create(N_int bits, boolean clear) /* malloc */
472 size = BitVector_Size(bits);
473 mask = BitVector_Mask(bits);
474 bytes = (size + BIT_VECTOR_HIDDEN_WORDS) << FACTOR;
475 addr = (wordptr) yasm_xmalloc((size_t) bytes);
484 BIT_VECTOR_ZERO_WORDS(zero,size)
490 listptr BitVector_Create_List(N_int bits, boolean clear, N_int count)
499 list = (listptr) malloc(sizeof(wordptr) * count);
503 for ( i = 0; i < count; i++ )
505 addr = BitVector_Create(bits,clear);
508 BitVector_Destroy_List(list,i);
518 wordptr BitVector_Resize(wordptr oldaddr, N_int bits) /* realloc */
529 oldsize = size_(oldaddr);
530 oldmask = mask_(oldaddr);
531 newsize = BitVector_Size(bits);
532 newmask = BitVector_Mask(bits);
533 if (oldsize > 0) *(oldaddr+oldsize-1) &= oldmask;
534 if (newsize <= oldsize)
537 bits_(newaddr) = bits;
538 size_(newaddr) = newsize;
539 mask_(newaddr) = newmask;
540 if (newsize > 0) *(newaddr+newsize-1) &= newmask;
544 bytes = (newsize + BIT_VECTOR_HIDDEN_WORDS) << FACTOR;
545 newaddr = (wordptr) yasm_xmalloc((size_t) bytes);
549 *newaddr++ = newsize;
550 *newaddr++ = newmask;
554 BIT_VECTOR_COPY_WORDS(target,source,oldsize)
555 BIT_VECTOR_ZERO_WORDS(target,newsize)
557 BitVector_Destroy(oldaddr);
562 wordptr BitVector_Shadow(wordptr addr) /* makes new, same size but empty */
564 return( BitVector_Create(bits_(addr),true) );
567 wordptr BitVector_Clone(wordptr addr) /* makes exact duplicate */
573 twin = BitVector_Create(bits,false);
574 if ((twin != NULL) and (bits > 0))
575 BIT_VECTOR_cpy_words(twin,addr,size_(addr));
579 wordptr BitVector_Concat(wordptr X, wordptr Y) /* returns concatenation */
581 /* BEWARE that X = most significant part, Y = least significant part! */
590 bitsZ = bitsX + bitsY;
591 Z = BitVector_Create(bitsZ,false);
592 if ((Z != NULL) and (bitsZ > 0))
594 BIT_VECTOR_cpy_words(Z,Y,size_(Y));
595 BitVector_Interval_Copy(Z,X,bitsY,0,bitsX);
596 *(Z+size_(Z)-1) &= mask_(Z);
601 void BitVector_Copy(wordptr X, wordptr Y) /* X = Y */
603 N_word sizeX = size_(X);
604 N_word sizeY = size_(Y);
605 N_word maskX = mask_(X);
606 N_word maskY = mask_(Y);
611 if ((X != Y) and (sizeX > 0))
613 lastX = X + sizeX - 1;
616 lastY = Y + sizeY - 1;
617 if ( (*lastY AND (maskY AND NOT (maskY >> 1))) == 0 ) *lastY &= maskY;
623 while ((sizeX > 0) and (sizeY > 0))
631 while (sizeX-- > 0) *X++ = fill;
636 void BitVector_Empty(wordptr addr) /* X = {} clr all */
638 N_word size = size_(addr);
640 BIT_VECTOR_ZERO_WORDS(addr,size)
643 void BitVector_Fill(wordptr addr) /* X = ~{} set all */
645 N_word size = size_(addr);
646 N_word mask = mask_(addr);
647 N_word fill = (N_word) ~0L;
651 BIT_VECTOR_FILL_WORDS(addr,fill,size)
656 void BitVector_Flip(wordptr addr) /* X = ~X flip all */
658 N_word size = size_(addr);
659 N_word mask = mask_(addr);
660 N_word flip = (N_word) ~0L;
664 BIT_VECTOR_FLIP_WORDS(addr,flip,size)
669 void BitVector_Primes(wordptr addr)
671 N_word bits = bits_(addr);
672 N_word size = size_(addr);
688 *work++ = temp XOR 0x0006;
689 while (--i > 0) *work++ = temp;
690 for ( i = 3; (j = i * i) < bits; i += 2 )
692 for ( ; j < bits; j += i ) BIT_VECTOR_CLR_BIT(addr,j)
694 *(addr+size-1) &= mask_(addr);
698 void BitVector_Reverse(wordptr X, wordptr Y)
700 N_word bits = bits_(X);
707 if (X == Y) BitVector_Interval_Reverse(X,0,bits-1);
708 else if (bits == bits_(Y))
710 /* mask = mask_(Y); */
711 /* mask &= NOT (mask >> 1); */
712 mask = BITMASKTAB[(bits-1) AND MODMASK];
718 if ((*Y AND mask) != 0)
722 if (not (mask >>= 1))
734 if (bit > LSB) *X = value;
739 void BitVector_Interval_Empty(wordptr addr, N_int lower, N_int upper)
740 { /* X = X \ [lower..upper] */
741 N_word bits = bits_(addr);
742 N_word size = size_(addr);
751 if ((size > 0) and (lower < bits) and (upper < bits) and (lower <= upper))
753 lobase = lower >> LOGBITS;
754 hibase = upper >> LOGBITS;
755 diff = hibase - lobase;
756 loaddr = addr + lobase;
757 hiaddr = addr + hibase;
759 lomask = (N_word) (~0L << (lower AND MODMASK));
760 himask = (N_word) ~((~0L << (upper AND MODMASK)) << 1);
764 *loaddr &= NOT (lomask AND himask);
768 *loaddr++ &= NOT lomask;
773 *hiaddr &= NOT himask;
778 void BitVector_Interval_Fill(wordptr addr, N_int lower, N_int upper)
779 { /* X = X + [lower..upper] */
780 N_word bits = bits_(addr);
781 N_word size = size_(addr);
782 N_word fill = (N_word) ~0L;
791 if ((size > 0) and (lower < bits) and (upper < bits) and (lower <= upper))
793 lobase = lower >> LOGBITS;
794 hibase = upper >> LOGBITS;
795 diff = hibase - lobase;
796 loaddr = addr + lobase;
797 hiaddr = addr + hibase;
799 lomask = (N_word) (~0L << (lower AND MODMASK));
800 himask = (N_word) ~((~0L << (upper AND MODMASK)) << 1);
804 *loaddr |= (lomask AND himask);
815 *(addr+size-1) &= mask_(addr);
819 void BitVector_Interval_Flip(wordptr addr, N_int lower, N_int upper)
820 { /* X = X ^ [lower..upper] */
821 N_word bits = bits_(addr);
822 N_word size = size_(addr);
823 N_word flip = (N_word) ~0L;
832 if ((size > 0) and (lower < bits) and (upper < bits) and (lower <= upper))
834 lobase = lower >> LOGBITS;
835 hibase = upper >> LOGBITS;
836 diff = hibase - lobase;
837 loaddr = addr + lobase;
838 hiaddr = addr + hibase;
840 lomask = (N_word) (~0L << (lower AND MODMASK));
841 himask = (N_word) ~((~0L << (upper AND MODMASK)) << 1);
845 *loaddr ^= (lomask AND himask);
856 *(addr+size-1) &= mask_(addr);
860 void BitVector_Interval_Reverse(wordptr addr, N_int lower, N_int upper)
862 N_word bits = bits_(addr);
868 if ((bits > 0) and (lower < bits) and (upper < bits) and (lower < upper))
870 loaddr = addr + (lower >> LOGBITS);
871 hiaddr = addr + (upper >> LOGBITS);
872 lomask = BITMASKTAB[lower AND MODMASK];
873 himask = BITMASKTAB[upper AND MODMASK];
874 for ( bits = upper - lower + 1; bits > 1; bits -= 2 )
876 if (((*loaddr AND lomask) != 0) XOR ((*hiaddr AND himask) != 0))
878 *loaddr ^= lomask; /* swap bits only if they differ! */
881 if (not (lomask <<= 1))
886 if (not (himask >>= 1))
895 boolean BitVector_interval_scan_inc(wordptr addr, N_int start,
896 N_intptr min, N_intptr max)
898 N_word size = size_(addr);
899 N_word mask = mask_(addr);
905 if ((size == 0) or (start >= bits_(addr))) return(FALSE);
910 offset = start >> LOGBITS;
912 *(addr+size-1) &= mask;
917 bitmask = BITMASKTAB[start AND MODMASK];
918 mask = NOT (bitmask OR (bitmask - 1));
921 if ((value AND bitmask) == 0)
928 while (empty and (--size > 0))
930 if ((value = *addr++)) empty = false; else offset++;
932 if (empty) return(FALSE);
934 start = offset << LOGBITS;
937 while (not (mask AND LSB))
943 mask = NOT (bitmask OR (bitmask - 1));
953 while (empty and (--size > 0))
955 if ((value = NOT *addr++)) empty = false; else offset++;
957 if (empty) value = LSB;
959 start = offset << LOGBITS;
960 while (not (value AND LSB))
969 boolean BitVector_interval_scan_dec(wordptr addr, N_int start,
970 N_intptr min, N_intptr max)
972 N_word size = size_(addr);
973 N_word mask = mask_(addr);
979 if ((size == 0) or (start >= bits_(addr))) return(FALSE);
984 offset = start >> LOGBITS;
986 if (offset >= size) return(FALSE);
988 *(addr+size-1) &= mask;
993 bitmask = BITMASKTAB[start AND MODMASK];
994 mask = (bitmask - 1);
997 if ((value AND bitmask) == 0)
1004 while (empty and (--size > 0))
1006 if ((value = *addr--)) empty = false; else offset--;
1008 if (empty) return(FALSE);
1010 start = offset << LOGBITS;
1013 while (not (mask AND MSB))
1019 mask = (bitmask - 1);
1029 while (empty and (--size > 0))
1031 if ((value = NOT *addr--)) empty = false; else offset--;
1033 if (empty) value = MSB;
1035 start = offset << LOGBITS;
1036 while (not (value AND MSB))
1045 void BitVector_Interval_Copy(wordptr X, wordptr Y, N_int Xoffset,
1046 N_int Yoffset, N_int length)
1048 N_word bitsX = bits_(X);
1049 N_word bitsY = bits_(Y);
1050 N_word source = 0; /* silence compiler warning */
1051 N_word target = 0; /* silence compiler warning */
1057 N_word s_lower = 0; /* silence compiler warning */
1058 N_word s_upper = 0; /* silence compiler warning */
1067 N_word t_lower = 0; /* silence compiler warning */
1068 N_word t_upper = 0; /* silence compiler warning */
1078 if ((length > 0) and (Xoffset < bitsX) and (Yoffset < bitsY))
1080 if ((Xoffset + length) > bitsX) length = bitsX - Xoffset;
1081 if ((Yoffset + length) > bitsY) length = bitsY - Yoffset;
1083 ascending = (Xoffset <= Yoffset);
1085 s_lo_base = Yoffset >> LOGBITS;
1086 s_lo_bit = Yoffset AND MODMASK;
1087 Yoffset += --length;
1088 s_hi_base = Yoffset >> LOGBITS;
1089 s_hi_bit = Yoffset AND MODMASK;
1091 t_lo_base = Xoffset >> LOGBITS;
1092 t_lo_bit = Xoffset AND MODMASK;
1094 t_hi_base = Xoffset >> LOGBITS;
1095 t_hi_bit = Xoffset AND MODMASK;
1121 if (t_base == t_hi_base) break;
1127 if (t_base == t_lo_base) break;
1132 sel = ((t_base == t_hi_base) << 1) OR (t_base == t_lo_base);
1144 t_bits = BITS - t_lo_bit;
1145 mask = (N_word) (~0L << t_lower);
1146 target = *X AND NOT mask;
1151 t_bits = t_hi_bit + 1;
1152 mask = (N_word) ((~0L << t_upper) << 1);
1153 target = *X AND mask;
1158 t_bits = t_hi_bit - t_lo_bit + 1;
1159 mask = (N_word) (~0L << t_lower);
1160 mask &= (N_word) ~((~0L << t_upper) << 1);
1161 target = *X AND NOT mask;
1171 if (s_base == s_hi_base) break;
1177 if (s_base == s_lo_base) break;
1183 sel = ((s_base == s_hi_base) << 1) OR (s_base == s_lo_base);
1194 s_bits = BITS - s_lo_bit;
1199 s_bits = s_hi_bit + 1;
1204 s_bits = s_hi_bit - s_lo_bit + 1;
1209 if (s_bits > t_bits)
1215 s_max = s_lower + bits;
1220 s_min = s_upper - bits;
1227 if (ascending) t_min = t_lower;
1228 else t_min = t_upper - bits;
1233 mask = (N_word) (~0L << s_min);
1234 mask &= (N_word) ~((~0L << s_max) << 1);
1235 if (s_min == t_min) target |= (source AND mask);
1238 if (s_min < t_min) target |= (source AND mask) << (t_min-s_min);
1239 else target |= (source AND mask) >> (s_min-t_min);
1254 *(Z+size_(Z)-1) &= mask_(Z);
1259 wordptr BitVector_Interval_Substitute(wordptr X, wordptr Y,
1260 N_int Xoffset, N_int Xlength,
1261 N_int Yoffset, N_int Ylength)
1263 N_word Xbits = bits_(X);
1264 N_word Ybits = bits_(Y);
1268 if ((Xoffset <= Xbits) and (Yoffset <= Ybits))
1270 limit = Xoffset + Xlength;
1274 Xlength = Xbits - Xoffset;
1276 if ((Yoffset + Ylength) > Ybits)
1278 Ylength = Ybits - Yoffset;
1280 if (Xlength == Ylength)
1282 if ((Ylength > 0) and ((X != Y) or (Xoffset != Yoffset)))
1284 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
1287 else /* Xlength != Ylength */
1289 if (Xlength > Ylength)
1291 diff = Xlength - Ylength;
1292 if (Ylength > 0) BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
1293 if (limit < Xbits) BitVector_Delete(X,Xoffset+Ylength,diff,FALSE);
1294 if ((X = BitVector_Resize(X,Xbits-diff)) == NULL) return(NULL);
1296 else /* Ylength > Xlength ==> Ylength > 0 */
1298 diff = Ylength - Xlength;
1301 if ((X = BitVector_Resize(X,Xbits+diff)) == NULL) return(NULL);
1302 if (limit < Xbits) BitVector_Insert(X,limit,diff,FALSE);
1303 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
1307 if ((Y = X = BitVector_Resize(X,Xbits+diff)) == NULL) return(NULL);
1310 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
1312 else /* limit < Xbits */
1314 BitVector_Insert(X,limit,diff,FALSE);
1315 if ((Yoffset+Ylength) <= limit)
1317 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
1319 else /* overlaps or lies above critical area */
1321 if (limit <= Yoffset)
1324 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
1326 else /* Yoffset < limit */
1328 Xlength = limit - Yoffset;
1329 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Xlength);
1330 Yoffset = Xoffset + Ylength; /* = limit + diff */
1333 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
1344 boolean BitVector_is_empty(wordptr addr) /* X == {} ? */
1346 N_word size = size_(addr);
1351 *(addr+size-1) &= mask_(addr);
1352 while (r and (size-- > 0)) r = ( *addr++ == 0 );
1357 boolean BitVector_is_full(wordptr addr) /* X == ~{} ? */
1359 N_word size = size_(addr);
1360 N_word mask = mask_(addr);
1367 last = addr + size - 1;
1369 while (r and (size-- > 0)) r = ( NOT *addr++ == 0 );
1375 boolean BitVector_equal(wordptr X, wordptr Y) /* X == Y ? */
1377 N_word size = size_(X);
1378 N_word mask = mask_(X);
1381 if (bits_(X) == bits_(Y))
1386 *(X+size-1) &= mask;
1387 *(Y+size-1) &= mask;
1388 while (r and (size-- > 0)) r = (*X++ == *Y++);
1394 Z_int BitVector_Lexicompare(wordptr X, wordptr Y) /* X <,=,> Y ? */
1396 N_word bitsX = bits_(X);
1397 N_word bitsY = bits_(Y);
1398 N_word size = size_(X);
1407 while (r and (size-- > 0)) r = (*(--X) == *(--Y));
1409 if (r) return((Z_int) 0);
1412 if (*X < *Y) return((Z_int) -1); else return((Z_int) 1);
1417 if (bitsX < bitsY) return((Z_int) -1); else return((Z_int) 1);
1421 Z_int BitVector_Compare(wordptr X, wordptr Y) /* X <,=,> Y ? */
1423 N_word bitsX = bits_(X);
1424 N_word bitsY = bits_(Y);
1425 N_word size = size_(X);
1426 N_word mask = mask_(X);
1436 mask &= NOT (mask >> 1);
1437 if ((sign = (*(X-1) AND mask)) != (*(Y-1) AND mask))
1439 if (sign) return((Z_int) -1); else return((Z_int) 1);
1441 while (r and (size-- > 0)) r = (*(--X) == *(--Y));
1443 if (r) return((Z_int) 0);
1446 if (*X < *Y) return((Z_int) -1); else return((Z_int) 1);
1451 if (bitsX < bitsY) return((Z_int) -1); else return((Z_int) 1);
1455 charptr BitVector_to_Hex(wordptr addr)
1457 N_word bits = bits_(addr);
1458 N_word size = size_(addr);
1466 if (bits AND 0x0003) length++;
1467 string = (charptr) yasm_xmalloc((size_t) (length+1));
1468 if (string == NULL) return(NULL);
1470 *string = (N_char) '\0';
1473 *(addr+size-1) &= mask_(addr);
1474 while ((size-- > 0) and (length > 0))
1478 while ((count-- > 0) and (length > 0))
1480 digit = value AND 0x000F;
1481 if (digit > 9) digit += (N_word) 'A' - 10;
1482 else digit += (N_word) '0';
1483 *(--string) = (N_char) digit; length--;
1484 if ((count > 0) and (length > 0)) value >>= 4;
1491 ErrCode BitVector_from_Hex(wordptr addr, charptr string)
1493 N_word size = size_(addr);
1494 N_word mask = mask_(addr);
1503 length = strlen((char *) string);
1508 for ( count = 0; (ok and (length > 0) and (count < BITS)); count += 4 )
1510 digit = (int) *(--string); length--;
1511 /* separate because toupper() is likely a macro! */
1512 digit = toupper(digit);
1515 else if ((ok = (isxdigit(digit) != 0)))
1517 if (digit >= (int) 'A') digit -= (int) 'A' - 10;
1518 else digit -= (int) '0';
1519 value |= (((N_word) digit) << count);
1526 if (ok) return(ErrCode_Ok);
1527 else return(ErrCode_Pars);
1530 ErrCode BitVector_from_Oct(wordptr addr, charptr string)
1532 N_word size = size_(addr);
1533 N_word mask = mask_(addr);
1537 N_word value_fill = 0;
1539 Z_word count_fill = 0;
1544 length = strlen((char *) string);
1549 for ( count = count_fill; (ok and (length > 0) and (count < BITS)); count += 3 )
1551 digit = (int) *(--string); length--;
1554 else if ((ok = (isdigit(digit) && digit != '8' && digit != '9')) != 0)
1557 value |= (((N_word) digit) << count);
1560 count_fill = (Z_word)count-(Z_word)BITS;
1562 value_fill = (((N_word) digit) >> (3-count_fill));
1569 if (ok) return(ErrCode_Ok);
1570 else return(ErrCode_Pars);
1573 charptr BitVector_to_Bin(wordptr addr)
1575 N_word size = size_(addr);
1582 length = bits_(addr);
1583 string = (charptr) yasm_xmalloc((size_t) (length+1));
1584 if (string == NULL) return(NULL);
1586 *string = (N_char) '\0';
1589 *(addr+size-1) &= mask_(addr);
1594 if (count > length) count = length;
1597 digit = value AND 0x0001;
1598 digit += (N_word) '0';
1599 *(--string) = (N_char) digit; length--;
1600 if (count > 0) value >>= 1;
1607 ErrCode BitVector_from_Bin(wordptr addr, charptr string)
1609 N_word size = size_(addr);
1610 N_word mask = mask_(addr);
1619 length = strlen((char *) string);
1624 for ( count = 0; (ok and (length > 0) and (count < BITS)); count++ )
1626 digit = (int) *(--string); length--;
1632 value |= BITMASKTAB[count];
1646 if (ok) return(ErrCode_Ok);
1647 else return(ErrCode_Pars);
1650 charptr BitVector_to_Dec(wordptr addr)
1652 N_word bits = bits_(addr);
1667 length = (N_word) (bits / 3.3); /* digits = bits * ln(2) / ln(10) */
1668 length += 2; /* compensate for truncating & provide space for minus sign */
1669 result = (charptr) yasm_xmalloc((size_t) (length+1)); /* remember the '\0'! */
1670 if (result == NULL) return(NULL);
1672 sign = BitVector_Sign(addr);
1673 if ((bits < 4) or (sign == 0))
1675 if (bits > 0) digits = *addr; else digits = (N_word) 0;
1676 if (sign < 0) digits = ((N_word)(-((Z_word)digits))) AND mask_(addr);
1677 *string++ = (N_char) digits + (N_char) '0';
1682 quot = BitVector_Create(bits,FALSE);
1685 BitVector_Dispose(result);
1688 rest = BitVector_Create(bits,FALSE);
1691 BitVector_Dispose(result);
1692 BitVector_Destroy(quot);
1695 temp = BitVector_Create(bits,FALSE);
1698 BitVector_Dispose(result);
1699 BitVector_Destroy(quot);
1700 BitVector_Destroy(rest);
1703 base = BitVector_Create(bits,TRUE);
1706 BitVector_Dispose(result);
1707 BitVector_Destroy(quot);
1708 BitVector_Destroy(rest);
1709 BitVector_Destroy(temp);
1712 if (sign < 0) BitVector_Negate(quot,addr);
1713 else BitVector_Copy(quot,addr);
1716 loop = (bits >= BITS);
1721 BitVector_Copy(temp,quot);
1722 if (BitVector_Div_Pos(quot,temp,base,rest))
1724 BitVector_Dispose(result); /* emergency exit */
1725 BitVector_Destroy(quot);
1726 BitVector_Destroy(rest); /* should never occur */
1727 BitVector_Destroy(temp); /* under normal operation */
1728 BitVector_Destroy(base);
1731 loop = not BitVector_is_empty(quot);
1736 while (((loop and (count-- > 0)) or ((not loop) and (q != 0))) and
1741 BIT_VECTOR_DIGITIZE(N_word,q,r)
1743 else r = (N_word) '0';
1744 *string++ = (N_char) r;
1748 while (loop and (digits < length));
1749 BitVector_Destroy(quot);
1750 BitVector_Destroy(rest);
1751 BitVector_Destroy(temp);
1752 BitVector_Destroy(base);
1754 if ((sign < 0) and (digits < length))
1756 *string++ = (N_char) '-';
1759 *string = (N_char) '\0';
1760 BIT_VECTOR_reverse(result,digits);
1764 struct BitVector_from_Dec_static_data {
1772 BitVector_from_Dec_static_data *BitVector_from_Dec_static_Boot(N_word bits)
1774 BitVector_from_Dec_static_data *data;
1776 data = yasm_xmalloc(sizeof(BitVector_from_Dec_static_data));
1780 data->term = BitVector_Create(BITS,FALSE);
1781 data->base = BitVector_Create(BITS,FALSE);
1782 data->prod = BitVector_Create(bits,FALSE);
1783 data->rank = BitVector_Create(bits,FALSE);
1784 data->temp = BitVector_Create(bits,FALSE);
1795 void BitVector_from_Dec_static_Shutdown(BitVector_from_Dec_static_data *data)
1798 BitVector_Destroy(data->term);
1799 BitVector_Destroy(data->base);
1800 BitVector_Destroy(data->prod);
1801 BitVector_Destroy(data->rank);
1802 BitVector_Destroy(data->temp);
1807 ErrCode BitVector_from_Dec_static(BitVector_from_Dec_static_data *data,
1808 wordptr addr, charptr string)
1810 ErrCode error = ErrCode_Ok;
1811 N_word bits = bits_(addr);
1812 N_word mask = mask_(addr);
1813 boolean init = (bits > BITS);
1836 length = strlen((char *) string);
1837 if (length == 0) return(ErrCode_Pars);
1838 digit = (int) *string;
1839 if ((minus = (digit == (int) '-')) or
1840 (digit == (int) '+'))
1843 if (--length == 0) return(ErrCode_Pars);
1848 BitVector_Empty(prod);
1849 BitVector_Empty(rank);
1851 BitVector_Empty(addr);
1854 while ((not error) and (length > 0))
1859 while ((not error) and (length > 0) and (count-- > 0))
1861 digit = (int) *(--string); length--;
1862 /* separate because isdigit() is likely a macro! */
1863 if (isdigit(digit) != 0)
1865 accu += ((N_word) digit - (N_word) '0') * powr;
1868 else error = ErrCode_Pars;
1875 BitVector_Copy(temp,rank);
1876 error = BitVector_Mul_Pos(prod,temp,term,FALSE);
1881 if ((not init) and ((accu AND NOT mask) != 0)) error = ErrCode_Ovfl;
1886 BitVector_compute(addr,addr,prod,FALSE,&carry);
1887 /* ignores sign change (= overflow) but not */
1888 /* numbers too large (= carry) for resulting bit vector */
1889 if (carry) error = ErrCode_Ovfl;
1896 BitVector_Copy(temp,rank);
1897 error = BitVector_Mul_Pos(rank,temp,base,FALSE);
1909 if (not error and minus)
1911 BitVector_Negate(addr,addr);
1912 if ((*(addr + size_(addr) - 1) AND mask AND NOT (mask >> 1)) == 0)
1913 error = ErrCode_Ovfl;
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) yasm_xmalloc((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);
2136 N_word indx = 0; /* silence compiler warning */
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,&indx);
2149 if (indx < bits) token = (N_word) '0';
2150 else error = ErrCode_Indx;
2166 error = ErrCode_Pars;
2178 BIT_VECTOR_SET_BIT(addr,indx)
2182 BIT_VECTOR_SET_BIT(addr,indx)
2186 error = ErrCode_Pars;
2195 BitVector_Interval_Fill(addr,start,indx);
2196 else if (start == indx)
2197 BIT_VECTOR_SET_BIT(addr,indx)
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 indx) /* X = X \ {x} */
2239 if (indx < bits_(addr)) BIT_VECTOR_CLR_BIT(addr,indx)
2242 void BitVector_Bit_On(wordptr addr, N_int indx) /* X = X + {x} */
2244 if (indx < bits_(addr)) BIT_VECTOR_SET_BIT(addr,indx)
2247 boolean BitVector_bit_flip(wordptr addr, N_int indx) /* X=(X+{x})\(X*{x}) */
2251 if (indx < bits_(addr)) return( BIT_VECTOR_FLP_BIT(addr,indx,mask) );
2252 else return( FALSE );
2255 boolean BitVector_bit_test(wordptr addr, N_int indx) /* {x} in X ? */
2257 if (indx < bits_(addr)) return( BIT_VECTOR_TST_BIT(addr,indx) );
2258 else return( FALSE );
2261 void BitVector_Bit_Copy(wordptr addr, N_int indx, boolean bit)
2263 if (indx < bits_(addr))
2265 if (bit) BIT_VECTOR_SET_BIT(addr,indx)
2266 else BIT_VECTOR_CLR_BIT(addr,indx)
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) yasm_xmalloc((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 /*****************************************************************************/
3867 /* This package is free software; you can use, modify and redistribute */
3868 /* it under the same terms as Perl itself, i.e., under the terms of */
3869 /* the "Artistic License" or the "GNU General Public License". */
3871 /* The C library at the core of this Perl module can additionally */
3872 /* be used, modified and redistributed under the terms of the */
3873 /* "GNU Library General Public License". */
3875 /*****************************************************************************/
3876 /* ARTISTIC LICENSE: */
3877 /*****************************************************************************/
3879 The "Artistic License"
3883 The intent of this document is to state the conditions under which a
3884 Package may be copied, such that the Copyright Holder maintains some
3885 semblance of artistic control over the development of the package,
3886 while giving the users of the package the right to use and distribute
3887 the Package in a more-or-less customary fashion, plus the right to make
3888 reasonable modifications.
3892 "Package" refers to the collection of files distributed by the
3893 Copyright Holder, and derivatives of that collection of files
3894 created through textual modification.
3896 "Standard Version" refers to such a Package if it has not been
3897 modified, or has been modified in accordance with the wishes
3898 of the Copyright Holder as specified below.
3900 "Copyright Holder" is whoever is named in the copyright or
3901 copyrights for the package.
3903 "You" is you, if you're thinking about copying or distributing
3906 "Reasonable copying fee" is whatever you can justify on the
3907 basis of media cost, duplication charges, time of people involved,
3908 and so on. (You will not be required to justify it to the
3909 Copyright Holder, but only to the computing community at large
3910 as a market that must bear the fee.)
3912 "Freely Available" means that no fee is charged for the item
3913 itself, though there may be fees involved in handling the item.
3914 It also means that recipients of the item may redistribute it
3915 under the same conditions they received it.
3917 1. You may make and give away verbatim copies of the source form of the
3918 Standard Version of this Package without restriction, provided that you
3919 duplicate all of the original copyright notices and associated disclaimers.
3921 2. You may apply bug fixes, portability fixes and other modifications
3922 derived from the Public Domain or from the Copyright Holder. A Package
3923 modified in such a way shall still be considered the Standard Version.
3925 3. You may otherwise modify your copy of this Package in any way, provided
3926 that you insert a prominent notice in each changed file stating how and
3927 when you changed that file, and provided that you do at least ONE of the
3930 a) place your modifications in the Public Domain or otherwise make them
3931 Freely Available, such as by posting said modifications to Usenet or
3932 an equivalent medium, or placing the modifications on a major archive
3933 site such as uunet.uu.net, or by allowing the Copyright Holder to include
3934 your modifications in the Standard Version of the Package.
3936 b) use the modified Package only within your corporation or organization.
3938 c) rename any non-standard executables so the names do not conflict
3939 with standard executables, which must also be provided, and provide
3940 a separate manual page for each non-standard executable that clearly
3941 documents how it differs from the Standard Version.
3943 d) make other distribution arrangements with the Copyright Holder.
3945 4. You may distribute the programs of this Package in object code or
3946 executable form, provided that you do at least ONE of the following:
3948 a) distribute a Standard Version of the executables and library files,
3949 together with instructions (in the manual page or equivalent) on where
3950 to get the Standard Version.
3952 b) accompany the distribution with the machine-readable source of
3953 the Package with your modifications.
3955 c) give non-standard executables non-standard names, and clearly
3956 document the differences in manual pages (or equivalent), together
3957 with instructions on where to get the Standard Version.
3959 d) make other distribution arrangements with the Copyright Holder.
3961 5. You may charge a reasonable copying fee for any distribution of this
3962 Package. You may charge any fee you choose for support of this
3963 Package. You may not charge a fee for this Package itself. However,
3964 you may distribute this Package in aggregate with other (possibly
3965 commercial) programs as part of a larger (possibly commercial) software
3966 distribution provided that you do not advertise this Package as a
3967 product of your own. You may embed this Package's interpreter within
3968 an executable of yours (by linking); this shall be construed as a mere
3969 form of aggregation, provided that the complete Standard Version of the
3970 interpreter is so embedded.
3972 6. The scripts and library files supplied as input to or produced as
3973 output from the programs of this Package do not automatically fall
3974 under the copyright of this Package, but belong to whoever generated
3975 them, and may be sold commercially, and may be aggregated with this
3976 Package. If such scripts or library files are aggregated with this
3977 Package via the so-called "undump" or "unexec" methods of producing a
3978 binary executable image, then distribution of such an image shall
3979 neither be construed as a distribution of this Package nor shall it
3980 fall under the restrictions of Paragraphs 3 and 4, provided that you do
3981 not represent such an executable image as a Standard Version of this
3984 7. C subroutines (or comparably compiled subroutines in other
3985 languages) supplied by you and linked into this Package in order to
3986 emulate subroutines and variables of the language defined by this
3987 Package shall not be considered part of this Package, but are the
3988 equivalent of input as in Paragraph 6, provided these subroutines do
3989 not change the language in any way that would cause it to fail the
3990 regression tests for the language.
3992 8. Aggregation of this Package with a commercial distribution is always
3993 permitted provided that the use of this Package is embedded; that is,
3994 when no overt attempt is made to make this Package's interfaces visible
3995 to the end user of the commercial distribution. Such use shall not be
3996 construed as a distribution of this Package.
3998 9. The name of the Copyright Holder may not be used to endorse or promote
3999 products derived from this software without specific prior written permission.
4001 10. THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR
4002 IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
4003 WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
4007 /*****************************************************************************/
4008 /* GNU GENERAL PUBLIC LICENSE: */
4009 /*****************************************************************************/
4010 /* This program is free software; you can redistribute it and/or */
4011 /* modify it under the terms of the GNU General Public License */
4012 /* as published by the Free Software Foundation; either version 2 */
4013 /* of the License, or (at your option) any later version. */
4015 /* This program is distributed in the hope that it will be useful, */
4016 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
4017 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
4018 /* GNU General Public License for more details. */
4020 /* You should have received a copy of the GNU General Public License */
4021 /* along with this program; if not, write to the */
4022 /* Free Software Foundation, Inc., */
4023 /* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
4025 /*****************************************************************************/
4026 /* GNU LIBRARY GENERAL PUBLIC LICENSE: */
4027 /*****************************************************************************/
4028 /* This library is free software; you can redistribute it and/or */
4029 /* modify it under the terms of the GNU Library General Public */
4030 /* License as published by the Free Software Foundation; either */
4031 /* version 2 of the License, or (at your option) any later version. */
4033 /* This library is distributed in the hope that it will be useful, */
4034 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
4035 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU */
4036 /* Library General Public License for more details. */
4038 /* You should have received a copy of the GNU Library General Public */
4039 /* License along with this library; if not, write to the */
4040 /* Free Software Foundation, Inc., */
4041 /* 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
4043 /* or download a copy from ftp://ftp.gnu.org/pub/gnu/COPYING.LIB-2.0 */
4045 /*****************************************************************************/