#ifndef MODULE_BIT_VECTOR #define MODULE_BIT_VECTOR /*****************************************************************************/ /* MODULE NAME: BitVector.c MODULE TYPE: (adt) */ /*****************************************************************************/ /* MODULE IMPORTS: */ /*****************************************************************************/ #include /* MODULE TYPE: (sys) */ #include /* MODULE TYPE: (sys) */ #include /* MODULE TYPE: (sys) */ #include /* MODULE TYPE: (sys) */ #include "ToolBox.h" /* MODULE TYPE: (dat) */ /*****************************************************************************/ /* MODULE INTERFACE: */ /*****************************************************************************/ typedef enum { BV_ErrCode_Ok = 0, /* everything went allright */ BV_ErrCode_Type, /* types word and size_t have incompatible sizes */ BV_ErrCode_Bits, /* bits of word and sizeof(word) are inconsistent */ BV_ErrCode_Word, /* size of word is less than 16 bits */ BV_ErrCode_Powr, /* number of bits of word is not a power of two */ BV_ErrCode_Loga, /* error in calculation of logarithm */ BV_ErrCode_Lpwr, /* number of bits of long is not a power of two */ BV_ErrCode_WgtL, /* size of word is greater than size of long */ BV_ErrCode_Null, /* unable to allocate memory */ BV_ErrCode_Indx, /* index out of range */ BV_ErrCode_Ordr, /* minimum > maximum index */ BV_ErrCode_Size, /* bit vector size mismatch */ BV_ErrCode_Pars, /* input string syntax error */ BV_ErrCode_Ovfl, /* numeric overflow error */ BV_ErrCode_Same, /* operands must be distinct */ BV_ErrCode_Expo, /* exponent must be positive */ BV_ErrCode_Zero, /* division by zero error */ BV_ErrCode_Oops /* unexpected error (contact author) */ } BV_ErrCode; typedef wordptr *bv_listptr; /* ===> MISCELLANEOUS BASIC FUNCTIONS: <=== */ charptr BitVector_Error (BV_ErrCode error); /* map errcode to string */ BV_ErrCode BitVector_Boot (void); /* 0 = ok, 1..17 = error */ N_word BitVector_Size (N_int bits); /* bit vec. size (# of words) */ N_word BitVector_Mask (N_int bits); /* bit vec. mask (unused bits) */ /* ===> CLASS METHODS: <=== */ charptr BitVector_Version (void); /* return version string */ N_int BitVector_Word_Bits (void); /* return # of bits in machine word */ N_int BitVector_Long_Bits (void); /* return # of bits in unsigned long */ /* ===> CONSTRUCTOR METHODS: <=== */ wordptr BitVector_Create (N_int bits, boolean clear); /* malloc */ bv_listptr BitVector_Create_List(N_int bits, boolean clear, N_int count); wordptr BitVector_Resize (wordptr oldaddr, N_int bits); /* realloc */ wordptr BitVector_Shadow (wordptr addr); /* make same size but empty */ wordptr BitVector_Clone (wordptr addr); /* make exact duplicate */ wordptr BitVector_Concat (wordptr X, wordptr Y); /* return concat'd */ /* ===> DESTRUCTOR METHODS: <=== */ void BitVector_Dispose (charptr string); /* string */ void BitVector_Destroy (wordptr addr); /* bitvec */ void BitVector_Destroy_List (bv_listptr list, N_int count); /* list */ /* ===> OBJECT METHODS: <=== */ /* ===> bit vector copy function: */ void BitVector_Copy (wordptr X, wordptr Y); /* X = Y */ /* ===> bit vector initialization: */ void BitVector_Empty (wordptr addr); /* X = {} */ void BitVector_Fill (wordptr addr); /* X = ~{} */ void BitVector_Flip (wordptr addr); /* X = ~X */ void BitVector_Primes (wordptr addr); /* ===> miscellaneous functions: */ void BitVector_Reverse (wordptr X, wordptr Y); /* ===> bit vector interval operations and functions: */ void BitVector_Interval_Empty (wordptr addr, N_int lower, N_int upper); void BitVector_Interval_Fill (wordptr addr, N_int lower, N_int upper); void BitVector_Interval_Flip (wordptr addr, N_int lower, N_int upper); void BitVector_Interval_Reverse (wordptr addr, N_int lower, N_int upper); boolean BitVector_interval_scan_inc (wordptr addr, N_int start, N_intptr min, N_intptr max); boolean BitVector_interval_scan_dec (wordptr addr, N_int start, N_intptr min, N_intptr max); void BitVector_Interval_Copy (wordptr X, wordptr Y, N_int Xoffset, N_int Yoffset, N_int length); wordptr BitVector_Interval_Substitute(wordptr X, wordptr Y, N_int Xoffset, N_int Xlength, N_int Yoffset, N_int Ylength); /* ===> bit vector test functions: */ boolean BitVector_is_empty (wordptr addr); /* X == {} ? */ boolean BitVector_is_full (wordptr addr); /* X == ~{} ? */ boolean BitVector_equal (wordptr X, wordptr Y); /* X == Y ? */ Z_int BitVector_Lexicompare(wordptr X, wordptr Y); /* X <,=,> Y ? */ Z_int BitVector_Compare (wordptr X, wordptr Y); /* X <,=,> Y ? */ /* ===> bit vector string conversion functions: */ charptr BitVector_to_Hex (wordptr addr); BV_ErrCode BitVector_from_Hex (wordptr addr, charptr string); charptr BitVector_to_Bin (wordptr addr); BV_ErrCode BitVector_from_Bin (wordptr addr, charptr string); charptr BitVector_to_Dec (wordptr addr); BV_ErrCode BitVector_from_Dec (wordptr addr, charptr string); charptr BitVector_to_Enum (wordptr addr); BV_ErrCode BitVector_from_Enum (wordptr addr, charptr string); /* ===> bit vector bit operations, functions & tests: */ void BitVector_Bit_Off (wordptr addr, N_int index); /* X = X \ {x} */ void BitVector_Bit_On (wordptr addr, N_int index); /* X = X + {x} */ boolean BitVector_bit_flip (wordptr addr, N_int index); /* (X+{x})\(X*{x}) */ boolean BitVector_bit_test (wordptr addr, N_int index); /* {x} in X ? */ void BitVector_Bit_Copy (wordptr addr, N_int index, boolean bit); /* ===> bit vector bit shift & rotate functions: */ void BitVector_LSB (wordptr addr, boolean bit); void BitVector_MSB (wordptr addr, boolean bit); boolean BitVector_lsb_ (wordptr addr); boolean BitVector_msb_ (wordptr addr); boolean BitVector_rotate_left (wordptr addr); boolean BitVector_rotate_right (wordptr addr); boolean BitVector_shift_left (wordptr addr, boolean carry_in); boolean BitVector_shift_right (wordptr addr, boolean carry_in); void BitVector_Move_Left (wordptr addr, N_int bits); void BitVector_Move_Right (wordptr addr, N_int bits); /* ===> bit vector insert/delete bits: */ void BitVector_Insert (wordptr addr, N_int offset, N_int count, boolean clear); void BitVector_Delete (wordptr addr, N_int offset, N_int count, boolean clear); /* ===> bit vector arithmetic: */ boolean BitVector_increment (wordptr addr); /* X++ */ boolean BitVector_decrement (wordptr addr); /* X-- */ boolean BitVector_compute (wordptr X, wordptr Y, wordptr Z, boolean minus, boolean *carry); boolean BitVector_add (wordptr X, wordptr Y, wordptr Z, boolean *carry); boolean BitVector_sub (wordptr X, wordptr Y, wordptr Z, boolean *carry); boolean BitVector_inc (wordptr X, wordptr Y); boolean BitVector_dec (wordptr X, wordptr Y); void BitVector_Negate (wordptr X, wordptr Y); void BitVector_Absolute (wordptr X, wordptr Y); Z_int BitVector_Sign (wordptr addr); BV_ErrCode BitVector_Mul_Pos (wordptr X, wordptr Y, wordptr Z, boolean strict); BV_ErrCode BitVector_Multiply (wordptr X, wordptr Y, wordptr Z); BV_ErrCode BitVector_Div_Pos (wordptr Q, wordptr X, wordptr Y, wordptr R); BV_ErrCode BitVector_Divide (wordptr Q, wordptr X, wordptr Y, wordptr R); BV_ErrCode BitVector_GCD (wordptr X, wordptr Y, wordptr Z); BV_ErrCode BitVector_GCD2 (wordptr U, wordptr V, wordptr W, /* O */ wordptr X, wordptr Y); /* I */ BV_ErrCode BitVector_Power (wordptr X, wordptr Y, wordptr Z); /* ===> direct memory access functions: */ void BitVector_Block_Store(wordptr addr, charptr buffer, N_int length); charptr BitVector_Block_Read (wordptr addr, N_intptr length); /* ===> word array functions: */ void BitVector_Word_Store (wordptr addr, N_int offset, N_int value); N_int BitVector_Word_Read (wordptr addr, N_int offset); void BitVector_Word_Insert(wordptr addr, N_int offset, N_int count, boolean clear); void BitVector_Word_Delete(wordptr addr, N_int offset, N_int count, boolean clear); /* ===> arbitrary size chunk functions: */ void BitVector_Chunk_Store(wordptr addr, N_int chunksize, N_int offset, N_long value); N_long BitVector_Chunk_Read (wordptr addr, N_int chunksize, N_int offset); /* ===> set operations: */ void Set_Union (wordptr X, wordptr Y, wordptr Z); /* X = Y + Z */ void Set_Intersection (wordptr X, wordptr Y, wordptr Z); /* X = Y * Z */ void Set_Difference (wordptr X, wordptr Y, wordptr Z); /* X = Y \ Z */ void Set_ExclusiveOr (wordptr X, wordptr Y, wordptr Z); /*(Y+Z)\(Y*Z)*/ void Set_Complement (wordptr X, wordptr Y); /* X = ~Y */ /* ===> set functions: */ boolean Set_subset (wordptr X, wordptr Y); /* X in Y */ N_int Set_Norm (wordptr addr); /* = |X| */ N_int Set_Norm2 (wordptr addr); /* = |X| */ N_int Set_Norm3 (wordptr addr); /* = |X| */ Z_long Set_Min (wordptr addr); /* = min(X) */ Z_long Set_Max (wordptr addr); /* = max(X) */ /* ===> matrix-of-booleans operations: */ void Matrix_Multiplication(wordptr X, N_int rowsX, N_int colsX, wordptr Y, N_int rowsY, N_int colsY, wordptr Z, N_int rowsZ, N_int colsZ); void Matrix_Product (wordptr X, N_int rowsX, N_int colsX, wordptr Y, N_int rowsY, N_int colsY, wordptr Z, N_int rowsZ, N_int colsZ); void Matrix_Closure (wordptr addr, N_int rows, N_int cols); void Matrix_Transpose (wordptr X, N_int rowsX, N_int colsX, wordptr Y, N_int rowsY, N_int colsY); /*****************************************************************************/ /* MODULE RESOURCES: */ /*****************************************************************************/ #define BV_BITS_(BitVector) *(BitVector-3) #define BV_SIZE_(BitVector) *(BitVector-2) #define BV_MASK_(BitVector) *(BitVector-1) #define BV_ERRCODE_TYPE "sizeof(word) > sizeof(size_t)" #define BV_ERRCODE_BITS "bits(word) != sizeof(word)*8" #define BV_ERRCODE_WORD "bits(word) < 16" #define BV_ERRCODE_POWR "bits(word) is not a power of two" #define BV_ERRCODE_LOGA "bits(word) != 2^ld(bits(word))" #define BV_ERRCODE_LPWR "bits(long) is not a power of two" #define BV_ERRCODE_WGTL "bits(word) > bits(long)" #define BV_ERRCODE_NULL "unable to allocate memory" #define BV_ERRCODE_INDX "index out of range" #define BV_ERRCODE_ORDR "minimum > maximum index" #define BV_ERRCODE_SIZE "bit vector size mismatch" #define BV_ERRCODE_PARS "input string syntax error" #define BV_ERRCODE_OVFL "numeric overflow error" #define BV_ERRCODE_SAME "result vector(s) must be distinct" #define BV_ERRCODE_EXPO "exponent must be positive" #define BV_ERRCODE_ZERO "division by zero error" #define BV_ERRCODE_OOPS "unexpected internal error - please contact author" const N_int BV_ByteNorm[256] = { 0x00, 0x01, 0x01, 0x02, 0x01, 0x02, 0x02, 0x03, 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, /* 0x00 */ 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x10 */ 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x20 */ 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x30 */ 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x40 */ 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x50 */ 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x60 */ 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0x70 */ 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x80 */ 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x90 */ 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0xA0 */ 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0xB0 */ 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0xC0 */ 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0xD0 */ 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0xE0 */ 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, 0x05, 0x06, 0x06, 0x07, 0x06, 0x07, 0x07, 0x08 /* 0xF0 */ }; /*****************************************************************************/ /* MODULE IMPLEMENTATION: */ /*****************************************************************************/ /**********************************************/ /* global implementation-intrinsic constants: */ /**********************************************/ #define BV_HIDDENWORDS 3 /*****************************************************************/ /* global machine-dependent constants (set by "BitVector_Boot"): */ /*****************************************************************/ static N_word BV_WordBits; /* = # of bits in a machine word (power of 2) */ static N_word BV_ModMask; /* = BV_WordBits-1 (for "modulo BV_WordBits") */ static N_word BV_LogBits; /* = ld(BV_WordBits) (logarithmus dualis) */ static N_word BV_Factor; /* = ld(BV_WordBits / 8) (ld of # of bytes) */ static N_word BV_LSB = 1; /* = mask for least significant bit */ static N_word BV_MSB; /* = mask for most significant bit */ static N_word BV_LongBits; /* = # of bits in unsigned long */ static N_word BV_Log10; /* = logarithm to base 10 of BV_WordBits - 1 */ static N_word BV_Exp10; /* = largest possible power of 10 in signed int */ /********************************************************************/ /* global bit mask table for fast access (set by "BitVector_Boot"): */ /********************************************************************/ #define BV_MASKTABSIZE (sizeof(N_word) << 3) static N_word BV_BitMaskTab[BV_MASKTABSIZE]; /*****************************/ /* global macro definitions: */ /*****************************/ #define BIT_VECTOR_ZERO_WORDS(target,count) \ while (count-- > 0) *target++ = 0; #define BIT_VECTOR_FILL_WORDS(target,fill,count) \ while (count-- > 0) *target++ = fill; #define BIT_VECTOR_FLIP_WORDS(target,flip,count) \ while (count-- > 0) *target++ ^= flip; #define BIT_VECTOR_COPY_WORDS(target,source,count) \ while (count-- > 0) *target++ = *source++; #define BIT_VECTOR_BACK_WORDS(target,source,count) \ { target += count; source += count; while (count-- > 0) *--target = *--source; } #define BIT_VECTOR_CLR_BIT(address,index) \ *(address+(index>>BV_LogBits)) &= NOT BV_BitMaskTab[index AND BV_ModMask]; #define BIT_VECTOR_SET_BIT(address,index) \ *(address+(index>>BV_LogBits)) |= BV_BitMaskTab[index AND BV_ModMask]; #define BIT_VECTOR_TST_BIT(address,index) \ ((*(address+(index>>BV_LogBits)) AND BV_BitMaskTab[index AND BV_ModMask]) != 0) #define BIT_VECTOR_FLP_BIT(address,index,mask) \ (mask = BV_BitMaskTab[index AND BV_ModMask]), \ (((*(addr+(index>>BV_LogBits)) ^= mask) AND mask) != 0) #define BIT_VECTOR_DIGITIZE(type,value,digit) \ value = (type) ((digit = value) / 10); \ digit -= value * 10; \ digit += (type) '0'; /*********************************************************/ /* private low-level functions (potentially dangerous!): */ /*********************************************************/ static N_word BIT_VECTOR_power10(N_word x) { N_word y = 1; while (x-- > 0) y *= 10; return(y); } static void BIT_VECTOR_zro_words(wordptr addr, N_word count) { BIT_VECTOR_ZERO_WORDS(addr,count) } static void BIT_VECTOR_cpy_words(wordptr target, wordptr source, N_word count) { BIT_VECTOR_COPY_WORDS(target,source,count) } static void BIT_VECTOR_mov_words(wordptr target, wordptr source, N_word count) { if (target != source) { if (target < source) BIT_VECTOR_COPY_WORDS(target,source,count) else BIT_VECTOR_BACK_WORDS(target,source,count) } } static void BIT_VECTOR_ins_words(wordptr addr, N_word total, N_word count, boolean clear) { N_word length; if ((total > 0) and (count > 0)) { if (count > total) count = total; length = total - count; if (length > 0) BIT_VECTOR_mov_words(addr+count,addr,length); if (clear) BIT_VECTOR_zro_words(addr,count); } } static void BIT_VECTOR_del_words(wordptr addr, N_word total, N_word count, boolean clear) { N_word length; if ((total > 0) and (count > 0)) { if (count > total) count = total; length = total - count; if (length > 0) BIT_VECTOR_mov_words(addr,addr+count,length); if (clear) BIT_VECTOR_zro_words(addr+length,count); } } static void BIT_VECTOR_reverse(charptr string, N_word length) { charptr last; N_char temp; if (length > 1) { last = string + length - 1; while (string < last) { temp = *string; *string = *last; *last = temp; string++; last--; } } } static N_word BIT_VECTOR_int2str(charptr string, N_word value) { N_word length; N_word digit; charptr work; work = string; if (value > 0) { length = 0; while (value > 0) { BIT_VECTOR_DIGITIZE(N_word,value,digit) *work++ = (N_char) digit; length++; } BIT_VECTOR_reverse(string,length); } else { length = 1; *work++ = (N_char) '0'; } return(length); } static N_word BIT_VECTOR_str2int(charptr string, N_word *value) { N_word length; N_word digit; *value = 0; length = 0; digit = (N_word) *string++; /* separate because isdigit() is likely a macro! */ while (isdigit((int)digit) != 0) { length++; digit -= (N_word) '0'; if (*value) *value *= 10; *value += digit; digit = (N_word) *string++; } return(length); } /********************************************/ /* routine to convert error code to string: */ /********************************************/ charptr BitVector_Error(BV_ErrCode error) { switch (error) { case BV_ErrCode_Ok: return( (charptr) NULL ); break; case BV_ErrCode_Type: return( (charptr) BV_ERRCODE_TYPE ); break; case BV_ErrCode_Bits: return( (charptr) BV_ERRCODE_BITS ); break; case BV_ErrCode_Word: return( (charptr) BV_ERRCODE_WORD ); break; case BV_ErrCode_Powr: return( (charptr) BV_ERRCODE_POWR ); break; case BV_ErrCode_Loga: return( (charptr) BV_ERRCODE_LOGA ); break; case BV_ErrCode_Lpwr: return( (charptr) BV_ERRCODE_LPWR ); break; case BV_ErrCode_WgtL: return( (charptr) BV_ERRCODE_WGTL ); break; case BV_ErrCode_Null: return( (charptr) BV_ERRCODE_NULL ); break; case BV_ErrCode_Indx: return( (charptr) BV_ERRCODE_INDX ); break; case BV_ErrCode_Ordr: return( (charptr) BV_ERRCODE_ORDR ); break; case BV_ErrCode_Size: return( (charptr) BV_ERRCODE_SIZE ); break; case BV_ErrCode_Pars: return( (charptr) BV_ERRCODE_PARS ); break; case BV_ErrCode_Ovfl: return( (charptr) BV_ERRCODE_OVFL ); break; case BV_ErrCode_Same: return( (charptr) BV_ERRCODE_SAME ); break; case BV_ErrCode_Expo: return( (charptr) BV_ERRCODE_EXPO ); break; case BV_ErrCode_Zero: return( (charptr) BV_ERRCODE_ZERO ); break; default: return( (charptr) BV_ERRCODE_OOPS ); break; } } /*****************************************/ /* automatic self-configuration routine: */ /*****************************************/ /*******************************************************/ /* */ /* MUST be called once prior to any other function */ /* to initialize the machine dependent constants */ /* of this package! */ /* */ /*******************************************************/ BV_ErrCode BitVector_Boot(void) { N_word sample; N_long longsample; if (sizeof(N_word) > sizeof(size_t)) return(BV_ErrCode_Type); BV_WordBits = 0; sample = ~0; while (sample) /* determine # of bits in a machine word */ { sample &= sample - 1; BV_WordBits++; } if (BV_WordBits != (sizeof(N_word) << 3)) return(BV_ErrCode_Bits); if (BV_WordBits < 16) return(BV_ErrCode_Word); BV_LongBits = 0; longsample = ~0L; while (longsample) /* determine # of bits in an unsigned long */ { longsample &= longsample - 1L; BV_LongBits++; } BV_LogBits = 0; sample = BV_ModMask = BV_WordBits - 1; if (sample AND BV_WordBits) return(BV_ErrCode_Powr); /* not a power of 2 */ while (sample) { sample &= sample - 1; BV_LogBits++; } if (BV_WordBits != (BV_LSB << BV_LogBits)) return(BV_ErrCode_Loga); /* ld wrong */ longsample = BV_LongBits - 1; if ((longsample AND BV_LongBits) or (BV_LongBits != (sizeof(N_long) << 3))) { BV_LongBits = (sizeof(N_long) << 3); longsample = BV_LongBits - 1; if (longsample AND BV_LongBits) return(BV_ErrCode_Lpwr); } if (BV_WordBits > BV_LongBits) return(BV_ErrCode_WgtL); if (BV_WordBits > BV_MASKTABSIZE) return(BV_ErrCode_Oops); for ( sample = 0; sample < BV_WordBits; sample++ ) { BV_BitMaskTab[sample] = (BV_LSB << sample); } BV_Factor = BV_LogBits - 3; /* ld(Bits/8) = ld(Bits)-ld(8) = ld(Bits)-3 */ BV_MSB = (BV_LSB << BV_ModMask); BV_Log10 = (N_word) (BV_ModMask * 0.30103); /* (Bits-1) * ln(2) / ln(10) */ BV_Exp10 = BIT_VECTOR_power10(BV_Log10); return(BV_ErrCode_Ok); } N_word BitVector_Size(N_int bits) /* bit vector size (# of words) */ { N_word size; size = bits >> BV_LogBits; if (bits AND BV_ModMask) size++; return(size); } N_word BitVector_Mask(N_int bits) /* bit vector mask (unused bits) */ { N_word mask; mask = bits AND BV_ModMask; if (mask) mask = (N_word) ~(~0L << mask); else mask = (N_word) ~0L; return(mask); } charptr BitVector_Version(void) { return((charptr)"7.4"); } N_int BitVector_Word_Bits(void) { return(BV_WordBits); } N_int BitVector_Long_Bits(void) { return(BV_LongBits); } /********************************************************************/ /* */ /* WARNING: Do not "free()" constant character strings, i.e., */ /* don't call "BitVector_Dispose()" for strings returned */ /* by "BitVector_Error()" or "BitVector_Version()"! */ /* */ /* ONLY call this function for strings allocated with "malloc()", */ /* i.e., the strings returned by the functions "BitVector_to_*()" */ /* and "BitVector_Block_Read()"! */ /* */ /********************************************************************/ void BitVector_Dispose(charptr string) /* free string */ { if (string != NULL) free((voidptr) string); } void BitVector_Destroy(wordptr addr) /* free bitvec */ { if (addr != NULL) { addr -= BV_HIDDENWORDS; free((voidptr) addr); } } void BitVector_Destroy_List(bv_listptr list, N_int count) /* free list */ { bv_listptr slot; if (list != NULL) { slot = list; while (count-- > 0) { BitVector_Destroy(*slot++); } free((voidptr) list); } } wordptr BitVector_Create(N_int bits, boolean clear) /* malloc */ { N_word size; N_word mask; N_word bytes; wordptr addr; wordptr zero; size = BitVector_Size(bits); mask = BitVector_Mask(bits); bytes = (size + BV_HIDDENWORDS) << BV_Factor; addr = (wordptr) malloc((size_t) bytes); if (addr != NULL) { *addr++ = bits; *addr++ = size; *addr++ = mask; if (clear) { zero = addr; BIT_VECTOR_ZERO_WORDS(zero,size) } } return(addr); } bv_listptr BitVector_Create_List(N_int bits, boolean clear, N_int count) { bv_listptr list = NULL; bv_listptr slot; wordptr addr; N_int i; if (count > 0) { list = (bv_listptr) malloc(sizeof(wordptr) * count); if (list != NULL) { slot = list; for ( i = 0; i < count; i++ ) { addr = BitVector_Create(bits,clear); if (addr == NULL) { BitVector_Destroy_List(list,i); return(NULL); } *slot++ = addr; } } } return(list); } wordptr BitVector_Resize(wordptr oldaddr, N_int bits) /* realloc */ { N_word bytes; N_word oldsize; N_word oldmask; N_word newsize; N_word newmask; wordptr newaddr; wordptr source; wordptr target; oldsize = BV_SIZE_(oldaddr); oldmask = BV_MASK_(oldaddr); newsize = BitVector_Size(bits); newmask = BitVector_Mask(bits); if (oldsize > 0) *(oldaddr+oldsize-1) &= oldmask; if (newsize <= oldsize) { newaddr = oldaddr; BV_BITS_(newaddr) = bits; BV_SIZE_(newaddr) = newsize; BV_MASK_(newaddr) = newmask; if (newsize > 0) *(newaddr+newsize-1) &= newmask; } else { bytes = (newsize + BV_HIDDENWORDS) << BV_Factor; newaddr = (wordptr) malloc((size_t) bytes); if (newaddr != NULL) { *newaddr++ = bits; *newaddr++ = newsize; *newaddr++ = newmask; target = newaddr; source = oldaddr; newsize -= oldsize; BIT_VECTOR_COPY_WORDS(target,source,oldsize) BIT_VECTOR_ZERO_WORDS(target,newsize) } BitVector_Destroy(oldaddr); } return(newaddr); } wordptr BitVector_Shadow(wordptr addr) /* makes new, same size but empty */ { return( BitVector_Create(BV_BITS_(addr),true) ); } wordptr BitVector_Clone(wordptr addr) /* makes exact duplicate */ { N_word bits; wordptr twin; bits = BV_BITS_(addr); twin = BitVector_Create(bits,false); if ((twin != NULL) and (bits > 0)) BIT_VECTOR_cpy_words(twin,addr,BV_SIZE_(addr)); return(twin); } wordptr BitVector_Concat(wordptr X, wordptr Y) /* returns concatenation */ { /* BEWARE that X = most significant part, Y = least significant part! */ N_word bitsX; N_word bitsY; N_word bitsZ; wordptr Z; bitsX = BV_BITS_(X); bitsY = BV_BITS_(Y); bitsZ = bitsX + bitsY; Z = BitVector_Create(bitsZ,false); if ((Z != NULL) and (bitsZ > 0)) { BIT_VECTOR_cpy_words(Z,Y,BV_SIZE_(Y)); BitVector_Interval_Copy(Z,X,bitsY,0,bitsX); *(Z+BV_SIZE_(Z)-1) &= BV_MASK_(Z); } return(Z); } void BitVector_Copy(wordptr X, wordptr Y) /* X = Y */ { N_word sizeX = BV_SIZE_(X); N_word sizeY = BV_SIZE_(Y); N_word maskX = BV_MASK_(X); N_word maskY = BV_MASK_(Y); N_word fill = 0; wordptr lastX; wordptr lastY; if ((X != Y) and (sizeX > 0)) { lastX = X + sizeX - 1; if (sizeY > 0) { lastY = Y + sizeY - 1; if ( (*lastY AND (maskY AND NOT (maskY >> 1))) == 0 ) *lastY &= maskY; else { fill = (N_word) ~0L; *lastY |= NOT maskY; } while ((sizeX > 0) and (sizeY > 0)) { *X++ = *Y++; sizeX--; sizeY--; } *lastY &= maskY; } while (sizeX-- > 0) *X++ = fill; *lastX &= maskX; } } void BitVector_Empty(wordptr addr) /* X = {} clr all */ { N_word size = BV_SIZE_(addr); BIT_VECTOR_ZERO_WORDS(addr,size) } void BitVector_Fill(wordptr addr) /* X = ~{} set all */ { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); N_word fill = (N_word) ~0L; if (size > 0) { BIT_VECTOR_FILL_WORDS(addr,fill,size) *(--addr) &= mask; } } void BitVector_Flip(wordptr addr) /* X = ~X flip all */ { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); N_word flip = (N_word) ~0L; if (size > 0) { BIT_VECTOR_FLIP_WORDS(addr,flip,size) *(--addr) &= mask; } } void BitVector_Primes(wordptr addr) { N_word bits = BV_BITS_(addr); N_word size = BV_SIZE_(addr); wordptr work; N_word temp; N_word i,j; if (size > 0) { temp = 0xAAAA; i = BV_WordBits >> 4; while (--i > 0) { temp <<= 16; temp |= 0xAAAA; } i = size; work = addr; *work++ = temp XOR 0x0006; while (--i > 0) *work++ = temp; for ( i = 3; (j = i * i) < bits; i += 2 ) { for ( ; j < bits; j += i ) BIT_VECTOR_CLR_BIT(addr,j) } *(addr+size-1) &= BV_MASK_(addr); } } void BitVector_Reverse(wordptr X, wordptr Y) { N_word bits = BV_BITS_(X); N_word mask; N_word bit; N_word value; if (bits > 0) { if (X == Y) BitVector_Interval_Reverse(X,0,bits-1); else if (bits == BV_BITS_(Y)) { /* mask = BV_MASK_(Y); */ /* mask &= NOT (mask >> 1); */ mask = BV_BitMaskTab[(bits-1) AND BV_ModMask]; Y += BV_SIZE_(Y) - 1; value = 0; bit = BV_LSB; while (bits-- > 0) { if ((*Y AND mask) != 0) { value |= bit; } if (not (mask >>= 1)) { Y--; mask = BV_MSB; } if (not (bit <<= 1)) { *X++ = value; value = 0; bit = BV_LSB; } } if (bit > BV_LSB) *X = value; } } } void BitVector_Interval_Empty(wordptr addr, N_int lower, N_int upper) { /* X = X \ [lower..upper] */ N_word bits = BV_BITS_(addr); N_word size = BV_SIZE_(addr); wordptr loaddr; wordptr hiaddr; N_word lobase; N_word hibase; N_word lomask; N_word himask; N_word diff; if ((size > 0) and (lower < bits) and (upper < bits) and (lower <= upper)) { lobase = lower >> BV_LogBits; hibase = upper >> BV_LogBits; diff = hibase - lobase; loaddr = addr + lobase; hiaddr = addr + hibase; lomask = (N_word) (~0L << (lower AND BV_ModMask)); himask = (N_word) ~((~0L << (upper AND BV_ModMask)) << 1); if (diff == 0) { *loaddr &= NOT (lomask AND himask); } else { *loaddr++ &= NOT lomask; while (--diff > 0) { *loaddr++ = 0; } *hiaddr &= NOT himask; } } } void BitVector_Interval_Fill(wordptr addr, N_int lower, N_int upper) { /* X = X + [lower..upper] */ N_word bits = BV_BITS_(addr); N_word size = BV_SIZE_(addr); N_word fill = (N_word) ~0L; wordptr loaddr; wordptr hiaddr; N_word lobase; N_word hibase; N_word lomask; N_word himask; N_word diff; if ((size > 0) and (lower < bits) and (upper < bits) and (lower <= upper)) { lobase = lower >> BV_LogBits; hibase = upper >> BV_LogBits; diff = hibase - lobase; loaddr = addr + lobase; hiaddr = addr + hibase; lomask = (N_word) (~0L << (lower AND BV_ModMask)); himask = (N_word) ~((~0L << (upper AND BV_ModMask)) << 1); if (diff == 0) { *loaddr |= (lomask AND himask); } else { *loaddr++ |= lomask; while (--diff > 0) { *loaddr++ = fill; } *hiaddr |= himask; } *(addr+size-1) &= BV_MASK_(addr); } } void BitVector_Interval_Flip(wordptr addr, N_int lower, N_int upper) { /* X = X ^ [lower..upper] */ N_word bits = BV_BITS_(addr); N_word size = BV_SIZE_(addr); N_word flip = (N_word) ~0L; wordptr loaddr; wordptr hiaddr; N_word lobase; N_word hibase; N_word lomask; N_word himask; N_word diff; if ((size > 0) and (lower < bits) and (upper < bits) and (lower <= upper)) { lobase = lower >> BV_LogBits; hibase = upper >> BV_LogBits; diff = hibase - lobase; loaddr = addr + lobase; hiaddr = addr + hibase; lomask = (N_word) (~0L << (lower AND BV_ModMask)); himask = (N_word) ~((~0L << (upper AND BV_ModMask)) << 1); if (diff == 0) { *loaddr ^= (lomask AND himask); } else { *loaddr++ ^= lomask; while (--diff > 0) { *loaddr++ ^= flip; } *hiaddr ^= himask; } *(addr+size-1) &= BV_MASK_(addr); } } void BitVector_Interval_Reverse(wordptr addr, N_int lower, N_int upper) { N_word bits = BV_BITS_(addr); wordptr loaddr; wordptr hiaddr; N_word lomask; N_word himask; if ((bits > 0) and (lower < bits) and (upper < bits) and (lower < upper)) { loaddr = addr + (lower >> BV_LogBits); hiaddr = addr + (upper >> BV_LogBits); lomask = BV_BitMaskTab[lower AND BV_ModMask]; himask = BV_BitMaskTab[upper AND BV_ModMask]; for ( bits = upper - lower + 1; bits > 1; bits -= 2 ) { if (((*loaddr AND lomask) != 0) XOR ((*hiaddr AND himask) != 0)) { *loaddr ^= lomask; /* swap bits only if they differ! */ *hiaddr ^= himask; } if (not (lomask <<= 1)) { lomask = BV_LSB; loaddr++; } if (not (himask >>= 1)) { himask = BV_MSB; hiaddr--; } } } } boolean BitVector_interval_scan_inc(wordptr addr, N_int start, N_intptr min, N_intptr max) { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); N_word offset; N_word bitmask; N_word value; boolean empty; if ((size == 0) or (start >= BV_BITS_(addr))) return(false); *min = start; *max = start; offset = start >> BV_LogBits; *(addr+size-1) &= mask; addr += offset; size -= offset; bitmask = BV_BitMaskTab[start AND BV_ModMask]; mask = NOT (bitmask OR (bitmask - 1)); value = *addr++; if ((value AND bitmask) == 0) { value &= mask; if (value == 0) { offset++; empty = true; while (empty and (--size > 0)) { if ((value = *addr++)) empty = false; else offset++; } if (empty) return(false); } start = offset << BV_LogBits; bitmask = BV_LSB; mask = value; while (not (mask AND BV_LSB)) { bitmask <<= 1; mask >>= 1; start++; } mask = NOT (bitmask OR (bitmask - 1)); *min = start; *max = start; } value = NOT value; value &= mask; if (value == 0) { offset++; empty = true; while (empty and (--size > 0)) { if ((value = NOT *addr++)) empty = false; else offset++; } if (empty) value = BV_LSB; } start = offset << BV_LogBits; while (not (value AND BV_LSB)) { value >>= 1; start++; } *max = --start; return(true); } boolean BitVector_interval_scan_dec(wordptr addr, N_int start, N_intptr min, N_intptr max) { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); N_word offset; N_word bitmask; N_word value; boolean empty; if ((size == 0) or (start >= BV_BITS_(addr))) return(false); *min = start; *max = start; offset = start >> BV_LogBits; if (offset >= size) return(false); *(addr+size-1) &= mask; addr += offset; size = ++offset; bitmask = BV_BitMaskTab[start AND BV_ModMask]; mask = (bitmask - 1); value = *addr--; if ((value AND bitmask) == 0) { value &= mask; if (value == 0) { offset--; empty = true; while (empty and (--size > 0)) { if ((value = *addr--)) empty = false; else offset--; } if (empty) return(false); } start = offset << BV_LogBits; bitmask = BV_MSB; mask = value; while (not (mask AND BV_MSB)) { bitmask >>= 1; mask <<= 1; start--; } mask = (bitmask - 1); *max = --start; *min = start; } value = NOT value; value &= mask; if (value == 0) { offset--; empty = true; while (empty and (--size > 0)) { if ((value = NOT *addr--)) empty = false; else offset--; } if (empty) value = BV_MSB; } start = offset << BV_LogBits; while (not (value AND BV_MSB)) { value <<= 1; start--; } *min = start; return(true); } void BitVector_Interval_Copy(wordptr X, wordptr Y, N_int Xoffset, N_int Yoffset, N_int length) { N_word bitsX = BV_BITS_(X); N_word bitsY = BV_BITS_(Y); N_word source = 0; /* silence compiler warning */ N_word target = 0; /* silence compiler warning */ N_word s_lo_base; N_word s_hi_base; N_word s_lo_bit; N_word s_hi_bit; N_word s_base; N_word s_lower = 0; /* silence compiler warning */ N_word s_upper = 0; /* silence compiler warning */ N_word s_bits; N_word s_min; N_word s_max; N_word t_lo_base; N_word t_hi_base; N_word t_lo_bit; N_word t_hi_bit; N_word t_base; N_word t_lower = 0; /* silence compiler warning */ N_word t_upper = 0; /* silence compiler warning */ N_word t_bits; N_word t_min; N_word mask; N_word bits; N_word select; boolean ascending; boolean notfirst; wordptr Z = X; if ((length > 0) and (Xoffset < bitsX) and (Yoffset < bitsY)) { if ((Xoffset + length) > bitsX) length = bitsX - Xoffset; if ((Yoffset + length) > bitsY) length = bitsY - Yoffset; ascending = (Xoffset <= Yoffset); s_lo_base = Yoffset >> BV_LogBits; s_lo_bit = Yoffset AND BV_ModMask; Yoffset += --length; s_hi_base = Yoffset >> BV_LogBits; s_hi_bit = Yoffset AND BV_ModMask; t_lo_base = Xoffset >> BV_LogBits; t_lo_bit = Xoffset AND BV_ModMask; Xoffset += length; t_hi_base = Xoffset >> BV_LogBits; t_hi_bit = Xoffset AND BV_ModMask; if (ascending) { s_base = s_lo_base; t_base = t_lo_base; } else { s_base = s_hi_base; t_base = t_hi_base; } s_bits = 0; t_bits = 0; Y += s_base; X += t_base; notfirst = false; while (true) { if (t_bits == 0) { if (notfirst) { *X = target; if (ascending) { if (t_base == t_hi_base) break; t_base++; X++; } else { if (t_base == t_lo_base) break; t_base--; X--; } } select = ((t_base == t_hi_base) << 1) OR (t_base == t_lo_base); switch (select) { case 0: t_lower = 0; t_upper = BV_WordBits - 1; t_bits = BV_WordBits; target = 0; break; case 1: t_lower = t_lo_bit; t_upper = BV_WordBits - 1; t_bits = BV_WordBits - t_lo_bit; mask = (N_word) (~0L << t_lower); target = *X AND NOT mask; break; case 2: t_lower = 0; t_upper = t_hi_bit; t_bits = t_hi_bit + 1; mask = (N_word) ((~0L << t_upper) << 1); target = *X AND mask; break; case 3: t_lower = t_lo_bit; t_upper = t_hi_bit; t_bits = t_hi_bit - t_lo_bit + 1; mask = (N_word) (~0L << t_lower); mask &= (N_word) ~((~0L << t_upper) << 1); target = *X AND NOT mask; break; } } if (s_bits == 0) { if (notfirst) { if (ascending) { if (s_base == s_hi_base) break; s_base++; Y++; } else { if (s_base == s_lo_base) break; s_base--; Y--; } } source = *Y; select = ((s_base == s_hi_base) << 1) OR (s_base == s_lo_base); switch (select) { case 0: s_lower = 0; s_upper = BV_WordBits - 1; s_bits = BV_WordBits; break; case 1: s_lower = s_lo_bit; s_upper = BV_WordBits - 1; s_bits = BV_WordBits - s_lo_bit; break; case 2: s_lower = 0; s_upper = s_hi_bit; s_bits = s_hi_bit + 1; break; case 3: s_lower = s_lo_bit; s_upper = s_hi_bit; s_bits = s_hi_bit - s_lo_bit + 1; break; } } notfirst = true; if (s_bits > t_bits) { bits = t_bits - 1; if (ascending) { s_min = s_lower; s_max = s_lower + bits; } else { s_max = s_upper; s_min = s_upper - bits; } t_min = t_lower; } else { bits = s_bits - 1; if (ascending) t_min = t_lower; else t_min = t_upper - bits; s_min = s_lower; s_max = s_upper; } bits++; mask = (N_word) (~0L << s_min); mask &= (N_word) ~((~0L << s_max) << 1); if (s_min == t_min) target |= (source AND mask); else { if (s_min < t_min) target |= (source AND mask) << (t_min-s_min); else target |= (source AND mask) >> (s_min-t_min); } if (ascending) { s_lower += bits; t_lower += bits; } else { s_upper -= bits; t_upper -= bits; } s_bits -= bits; t_bits -= bits; } *(Z+BV_SIZE_(Z)-1) &= BV_MASK_(Z); } } wordptr BitVector_Interval_Substitute(wordptr X, wordptr Y, N_int Xoffset, N_int Xlength, N_int Yoffset, N_int Ylength) { N_word Xbits = BV_BITS_(X); N_word Ybits = BV_BITS_(Y); N_word limit; N_word diff; if ((Xoffset <= Xbits) and (Yoffset <= Ybits)) { limit = Xoffset + Xlength; if (limit > Xbits) { limit = Xbits; Xlength = Xbits - Xoffset; } if ((Yoffset + Ylength) > Ybits) { Ylength = Ybits - Yoffset; } if (Xlength == Ylength) { if ((Ylength > 0) and ((X != Y) or (Xoffset != Yoffset))) { BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength); } } else /* Xlength != Ylength */ { if (Xlength > Ylength) { diff = Xlength - Ylength; if (Ylength > 0) BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength); if (limit < Xbits) BitVector_Delete(X,Xoffset+Ylength,diff,false); if ((X = BitVector_Resize(X,Xbits-diff)) == NULL) return(NULL); } else /* Ylength > Xlength ==> Ylength > 0 */ { diff = Ylength - Xlength; if (X != Y) { if ((X = BitVector_Resize(X,Xbits+diff)) == NULL) return(NULL); if (limit < Xbits) BitVector_Insert(X,limit,diff,false); BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength); } else /* in-place */ { if ((Y = X = BitVector_Resize(X,Xbits+diff)) == NULL) return(NULL); if (limit >= Xbits) { BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength); } else /* limit < Xbits */ { BitVector_Insert(X,limit,diff,false); if ((Yoffset+Ylength) <= limit) { BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength); } else /* overlaps or lies above critical area */ { if (limit <= Yoffset) { Yoffset += diff; BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength); } else /* Yoffset < limit */ { Xlength = limit - Yoffset; BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Xlength); Yoffset = Xoffset + Ylength; /* = limit + diff */ Xoffset += Xlength; Ylength -= Xlength; BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength); } } } } } } } return(X); } boolean BitVector_is_empty(wordptr addr) /* X == {} ? */ { N_word size = BV_SIZE_(addr); boolean r = true; if (size > 0) { *(addr+size-1) &= BV_MASK_(addr); while (r and (size-- > 0)) r = ( *addr++ == 0 ); } return(r); } boolean BitVector_is_full(wordptr addr) /* X == ~{} ? */ { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); boolean r = false; wordptr last; if (size > 0) { r = true; last = addr + size - 1; *last |= NOT mask; while (r and (size-- > 0)) r = ( NOT *addr++ == 0 ); *last &= mask; } return(r); } boolean BitVector_equal(wordptr X, wordptr Y) /* X == Y ? */ { N_word size = BV_SIZE_(X); N_word mask = BV_MASK_(X); boolean r = false; if (BV_BITS_(X) == BV_BITS_(Y)) { r = true; if (size > 0) { *(X+size-1) &= mask; *(Y+size-1) &= mask; while (r and (size-- > 0)) r = (*X++ == *Y++); } } return(r); } Z_int BitVector_Lexicompare(wordptr X, wordptr Y) /* X <,=,> Y ? */ { /* unsigned */ N_word bitsX = BV_BITS_(X); N_word bitsY = BV_BITS_(Y); N_word size = BV_SIZE_(X); boolean r = true; if (bitsX == bitsY) { if (size > 0) { X += size; Y += size; while (r and (size-- > 0)) r = (*(--X) == *(--Y)); } if (r) return((Z_int) 0); else { if (*X < *Y) return((Z_int) -1); else return((Z_int) 1); } } else { if (bitsX < bitsY) return((Z_int) -1); else return((Z_int) 1); } } Z_int BitVector_Compare(wordptr X, wordptr Y) /* X <,=,> Y ? */ { /* signed */ N_word bitsX = BV_BITS_(X); N_word bitsY = BV_BITS_(Y); N_word size = BV_SIZE_(X); N_word mask = BV_MASK_(X); N_word sign; boolean r = true; if (bitsX == bitsY) { if (size > 0) { X += size; Y += size; mask &= NOT (mask >> 1); if ((sign = (*(X-1) AND mask)) != (*(Y-1) AND mask)) { if (sign) return((Z_int) -1); else return((Z_int) 1); } while (r and (size-- > 0)) r = (*(--X) == *(--Y)); } if (r) return((Z_int) 0); else { if (*X < *Y) return((Z_int) -1); else return((Z_int) 1); } } else { if (bitsX < bitsY) return((Z_int) -1); else return((Z_int) 1); } } charptr BitVector_to_Hex(wordptr addr) { N_word bits = BV_BITS_(addr); N_word size = BV_SIZE_(addr); N_word value; N_word count; N_word digit; N_word length; charptr string; length = bits >> 2; if (bits AND 0x0003) length++; string = (charptr) malloc((size_t) (length+1)); if (string == NULL) return(NULL); string += length; *string = (N_char) '\0'; if (size > 0) { *(addr+size-1) &= BV_MASK_(addr); while ((size-- > 0) and (length > 0)) { value = *addr++; count = BV_WordBits >> 2; while ((count-- > 0) and (length > 0)) { digit = value AND 0x000F; if (digit > 9) digit += (N_word) 'A' - 10; else digit += (N_word) '0'; *(--string) = (N_char) digit; length--; if ((count > 0) and (length > 0)) value >>= 4; } } } return(string); } BV_ErrCode BitVector_from_Hex(wordptr addr, charptr string) { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); boolean ok = true; N_word length; N_word value; N_word count; int digit; if (size > 0) { length = strlen((char *) string); string += length; while (size-- > 0) { value = 0; for ( count = 0; (ok and (length > 0) and (count < BV_WordBits)); count += 4 ) { digit = (int) *(--string); length--; /* separate because toupper() is likely a macro! */ digit = toupper(digit); if ((ok = (isxdigit(digit) != 0))) { if (digit >= (int) 'A') digit -= (int) 'A' - 10; else digit -= (int) '0'; value |= (((N_word) digit) << count); } } *addr++ = value; } *(--addr) &= mask; } if (ok) return(BV_ErrCode_Ok); else return(BV_ErrCode_Pars); } charptr BitVector_to_Bin(wordptr addr) { N_word size = BV_SIZE_(addr); N_word value; N_word count; N_word digit; N_word length; charptr string; length = BV_BITS_(addr); string = (charptr) malloc((size_t) (length+1)); if (string == NULL) return(NULL); string += length; *string = (N_char) '\0'; if (size > 0) { *(addr+size-1) &= BV_MASK_(addr); while (size-- > 0) { value = *addr++; count = BV_WordBits; if (count > length) count = length; while (count-- > 0) { digit = value AND 0x0001; digit += (N_word) '0'; *(--string) = (N_char) digit; length--; if (count > 0) value >>= 1; } } } return(string); } BV_ErrCode BitVector_from_Bin(wordptr addr, charptr string) { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); boolean ok = true; N_word length; N_word value; N_word count; int digit; if (size > 0) { length = strlen((char *) string); string += length; while (size-- > 0) { value = 0; for ( count = 0; (ok and (length > 0) and (count < BV_WordBits)); count++ ) { digit = (int) *(--string); length--; switch (digit) { case (int) '0': break; case (int) '1': value |= BV_BitMaskTab[count]; break; default: ok = false; break; } } *addr++ = value; } *(--addr) &= mask; } if (ok) return(BV_ErrCode_Ok); else return(BV_ErrCode_Pars); } charptr BitVector_to_Dec(wordptr addr) { N_word bits = BV_BITS_(addr); N_word length; N_word digits; N_word count; N_word q; N_word r; boolean loop; charptr result; charptr string; wordptr quot; wordptr rest; wordptr temp; wordptr base; Z_int sign; length = (N_word) (bits / 3.3); /* digits = bits * ln(2) / ln(10) */ length += 2; /* compensate for truncating & provide space for minus sign */ result = (charptr) malloc((size_t) (length+1)); /* remember the '\0'! */ if (result == NULL) return(NULL); string = result; sign = BitVector_Sign(addr); if ((bits < 4) or (sign == 0)) { if (bits > 0) digits = *addr; else digits = (N_word) 0; if (sign < 0) digits = ((N_word)(-((Z_word)digits))) AND BV_MASK_(addr); *string++ = (N_char) digits + (N_char) '0'; digits = 1; } else { quot = BitVector_Create(bits,false); if (quot == NULL) { BitVector_Dispose(result); return(NULL); } rest = BitVector_Create(bits,false); if (rest == NULL) { BitVector_Dispose(result); BitVector_Destroy(quot); return(NULL); } temp = BitVector_Create(bits,false); if (temp == NULL) { BitVector_Dispose(result); BitVector_Destroy(quot); BitVector_Destroy(rest); return(NULL); } base = BitVector_Create(bits,true); if (base == NULL) { BitVector_Dispose(result); BitVector_Destroy(quot); BitVector_Destroy(rest); BitVector_Destroy(temp); return(NULL); } if (sign < 0) BitVector_Negate(quot,addr); else BitVector_Copy(quot,addr); digits = 0; *base = BV_Exp10; loop = (bits >= BV_WordBits); do { if (loop) { BitVector_Copy(temp,quot); if (BitVector_Div_Pos(quot,temp,base,rest)) { BitVector_Dispose(result); /* emergency exit */ BitVector_Destroy(quot); BitVector_Destroy(rest); /* should never occur */ BitVector_Destroy(temp); /* under normal operation */ BitVector_Destroy(base); return(NULL); } loop = not BitVector_is_empty(quot); q = *rest; } else q = *quot; count = BV_Log10; while (((loop and (count-- > 0)) or ((not loop) and (q != 0))) and (digits < length)) { if (q != 0) { BIT_VECTOR_DIGITIZE(N_word,q,r) } else r = (N_word) '0'; *string++ = (N_char) r; digits++; } } while (loop and (digits < length)); BitVector_Destroy(quot); BitVector_Destroy(rest); BitVector_Destroy(temp); BitVector_Destroy(base); } if ((sign < 0) and (digits < length)) { *string++ = (N_char) '-'; digits++; } *string = (N_char) '\0'; BIT_VECTOR_reverse(result,digits); return(result); } BV_ErrCode BitVector_from_Dec(wordptr addr, charptr string) { BV_ErrCode error = BV_ErrCode_Ok; N_word bits = BV_BITS_(addr); N_word mask = BV_MASK_(addr); boolean init = (bits > BV_WordBits); boolean minus; boolean shift; boolean carry; wordptr term; wordptr base; wordptr prod; wordptr rank; wordptr temp; N_word accu; N_word powr; N_word count; N_word length; int digit; if (bits > 0) { length = strlen((char *) string); if (length == 0) return(BV_ErrCode_Pars); digit = (int) *string; if ((minus = (digit == (int) '-')) or (digit == (int) '+')) { string++; if (--length == 0) return(BV_ErrCode_Pars); } string += length; term = BitVector_Create(BV_WordBits,false); if (term == NULL) { return(BV_ErrCode_Null); } base = BitVector_Create(BV_WordBits,false); if (base == NULL) { BitVector_Destroy(term); return(BV_ErrCode_Null); } prod = BitVector_Create(bits,init); if (prod == NULL) { BitVector_Destroy(term); BitVector_Destroy(base); return(BV_ErrCode_Null); } rank = BitVector_Create(bits,init); if (rank == NULL) { BitVector_Destroy(term); BitVector_Destroy(base); BitVector_Destroy(prod); return(BV_ErrCode_Null); } temp = BitVector_Create(bits,false); if (temp == NULL) { BitVector_Destroy(term); BitVector_Destroy(base); BitVector_Destroy(prod); BitVector_Destroy(rank); return(BV_ErrCode_Null); } BitVector_Empty(addr); *base = BV_Exp10; shift = false; while ((not error) and (length > 0)) { accu = 0; powr = 1; count = BV_Log10; while ((not error) and (length > 0) and (count-- > 0)) { digit = (int) *(--string); length--; /* separate because isdigit() is likely a macro! */ if (isdigit(digit) != 0) { accu += ((N_word) digit - (N_word) '0') * powr; powr *= 10; } else error = BV_ErrCode_Pars; } if (not error) { if (shift) { *term = accu; BitVector_Copy(temp,rank); error = BitVector_Mul_Pos(prod,temp,term,false); } else { *prod = accu; if ((not init) and ((accu AND NOT mask) != 0)) error = BV_ErrCode_Ovfl; } if (not error) { carry = false; BitVector_compute(addr,addr,prod,false,&carry); /* ignores sign change (= overflow) but not */ /* numbers too large (= carry) for resulting bit vector */ if (carry) error = BV_ErrCode_Ovfl; else { if (length > 0) { if (shift) { BitVector_Copy(temp,rank); error = BitVector_Mul_Pos(rank,temp,base,false); } else { *rank = *base; shift = true; } } } } } } BitVector_Destroy(term); BitVector_Destroy(base); BitVector_Destroy(prod); BitVector_Destroy(rank); BitVector_Destroy(temp); if (not error and minus) { BitVector_Negate(addr,addr); if ((*(addr + BV_SIZE_(addr) - 1) AND mask AND NOT (mask >> 1)) == 0) error = BV_ErrCode_Ovfl; } } return(error); } charptr BitVector_to_Enum(wordptr addr) { N_word bits = BV_BITS_(addr); N_word sample; N_word length; N_word digits; N_word factor; N_word power; N_word start; N_word min; N_word max; charptr string; charptr target; boolean comma; if (bits > 0) { sample = bits - 1; /* greatest possible index */ length = 2; /* account for index 0 and terminating '\0' */ digits = 1; /* account for intervening dashes and commas */ factor = 1; power = 10; while (sample >= (power-1)) { length += ++digits * factor * 6; /* 9,90,900,9000,... (9*2/3 = 6) */ factor = power; power *= 10; } if (sample > --factor) { sample -= factor; factor = (N_word) ( sample / 3 ); factor = (factor << 1) + (sample - (factor * 3)); length += ++digits * factor; } } else length = 1; string = (charptr) malloc((size_t) length); if (string == NULL) return(NULL); start = 0; comma = false; target = string; while ((start < bits) and BitVector_interval_scan_inc(addr,start,&min,&max)) { start = max + 2; if (comma) *target++ = (N_char) ','; if (min == max) { target += BIT_VECTOR_int2str(target,min); } else { if (min+1 == max) { target += BIT_VECTOR_int2str(target,min); *target++ = (N_char) ','; target += BIT_VECTOR_int2str(target,max); } else { target += BIT_VECTOR_int2str(target,min); *target++ = (N_char) '-'; target += BIT_VECTOR_int2str(target,max); } } comma = true; } *target = (N_char) '\0'; return(string); } BV_ErrCode BitVector_from_Enum(wordptr addr, charptr string) { BV_ErrCode error = BV_ErrCode_Ok; N_word bits = BV_BITS_(addr); N_word state = 1; N_word start = 0; /* silence compiler warning */ N_word token; N_word index; if (bits > 0) { BitVector_Empty(addr); while ((not error) and (state != 0)) { token = (N_word) *string; /* separate because isdigit() is likely a macro! */ if (isdigit((int)token) != 0) { string += BIT_VECTOR_str2int(string,&index); if (index < bits) token = (N_word) '0'; else error = BV_ErrCode_Indx; } else string++; if (not error) switch (state) { case 1: switch (token) { case (N_word) '0': state = 2; break; case (N_word) '\0': state = 0; break; default: error = BV_ErrCode_Pars; break; } break; case 2: switch (token) { case (N_word) '-': start = index; state = 3; break; case (N_word) ',': BIT_VECTOR_SET_BIT(addr,index) state = 5; break; case (N_word) '\0': BIT_VECTOR_SET_BIT(addr,index) state = 0; break; default: error = BV_ErrCode_Pars; break; } break; case 3: switch (token) { case (N_word) '0': if (start < index) BitVector_Interval_Fill(addr,start,index); else if (start == index) BIT_VECTOR_SET_BIT(addr,index) else error = BV_ErrCode_Ordr; state = 4; break; default: error = BV_ErrCode_Pars; break; } break; case 4: switch (token) { case (N_word) ',': state = 5; break; case (N_word) '\0': state = 0; break; default: error = BV_ErrCode_Pars; break; } break; case 5: switch (token) { case (N_word) '0': state = 2; break; default: error = BV_ErrCode_Pars; break; } break; } } } return(error); } void BitVector_Bit_Off(wordptr addr, N_int index) /* X = X \ {x} */ { if (index < BV_BITS_(addr)) BIT_VECTOR_CLR_BIT(addr,index) } void BitVector_Bit_On(wordptr addr, N_int index) /* X = X + {x} */ { if (index < BV_BITS_(addr)) BIT_VECTOR_SET_BIT(addr,index) } boolean BitVector_bit_flip(wordptr addr, N_int index) /* X=(X+{x})\(X*{x}) */ { N_word mask; if (index < BV_BITS_(addr)) return( BIT_VECTOR_FLP_BIT(addr,index,mask) ); else return( false ); } boolean BitVector_bit_test(wordptr addr, N_int index) /* {x} in X ? */ { if (index < BV_BITS_(addr)) return( BIT_VECTOR_TST_BIT(addr,index) ); else return( false ); } void BitVector_Bit_Copy(wordptr addr, N_int index, boolean bit) { if (index < BV_BITS_(addr)) { if (bit) BIT_VECTOR_SET_BIT(addr,index) else BIT_VECTOR_CLR_BIT(addr,index) } } void BitVector_LSB(wordptr addr, boolean bit) { if (BV_BITS_(addr) > 0) { if (bit) *addr |= BV_LSB; else *addr &= NOT BV_LSB; } } void BitVector_MSB(wordptr addr, boolean bit) { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); if (size-- > 0) { if (bit) *(addr+size) |= mask AND NOT (mask >> 1); else *(addr+size) &= NOT mask OR (mask >> 1); } } boolean BitVector_lsb_(wordptr addr) { if (BV_SIZE_(addr) > 0) return( (*addr AND BV_LSB) != 0 ); else return( false ); } boolean BitVector_msb_(wordptr addr) { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); if (size-- > 0) return( (*(addr+size) AND (mask AND NOT (mask >> 1))) != 0 ); else return( false ); } boolean BitVector_rotate_left(wordptr addr) { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); N_word msb; boolean carry_in; boolean carry_out = false; if (size > 0) { msb = mask AND NOT (mask >> 1); carry_in = ((*(addr+size-1) AND msb) != 0); while (size-- > 1) { carry_out = ((*addr AND BV_MSB) != 0); *addr <<= 1; if (carry_in) *addr |= BV_LSB; carry_in = carry_out; addr++; } carry_out = ((*addr AND msb) != 0); *addr <<= 1; if (carry_in) *addr |= BV_LSB; *addr &= mask; } return(carry_out); } boolean BitVector_rotate_right(wordptr addr) { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); N_word msb; boolean carry_in; boolean carry_out = false; if (size > 0) { msb = mask AND NOT (mask >> 1); carry_in = ((*addr AND BV_LSB) != 0); addr += size-1; *addr &= mask; carry_out = ((*addr AND BV_LSB) != 0); *addr >>= 1; if (carry_in) *addr |= msb; carry_in = carry_out; addr--; size--; while (size-- > 0) { carry_out = ((*addr AND BV_LSB) != 0); *addr >>= 1; if (carry_in) *addr |= BV_MSB; carry_in = carry_out; addr--; } } return(carry_out); } boolean BitVector_shift_left(wordptr addr, boolean carry_in) { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); N_word msb; boolean carry_out = carry_in; if (size > 0) { msb = mask AND NOT (mask >> 1); while (size-- > 1) { carry_out = ((*addr AND BV_MSB) != 0); *addr <<= 1; if (carry_in) *addr |= BV_LSB; carry_in = carry_out; addr++; } carry_out = ((*addr AND msb) != 0); *addr <<= 1; if (carry_in) *addr |= BV_LSB; *addr &= mask; } return(carry_out); } boolean BitVector_shift_right(wordptr addr, boolean carry_in) { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); N_word msb; boolean carry_out = carry_in; if (size > 0) { msb = mask AND NOT (mask >> 1); addr += size-1; *addr &= mask; carry_out = ((*addr AND BV_LSB) != 0); *addr >>= 1; if (carry_in) *addr |= msb; carry_in = carry_out; addr--; size--; while (size-- > 0) { carry_out = ((*addr AND BV_LSB) != 0); *addr >>= 1; if (carry_in) *addr |= BV_MSB; carry_in = carry_out; addr--; } } return(carry_out); } void BitVector_Move_Left(wordptr addr, N_int bits) { N_word count; N_word words; if (bits > 0) { count = bits AND BV_ModMask; words = bits >> BV_LogBits; if (bits >= BV_BITS_(addr)) BitVector_Empty(addr); else { while (count-- > 0) BitVector_shift_left(addr,0); BitVector_Word_Insert(addr,0,words,true); } } } void BitVector_Move_Right(wordptr addr, N_int bits) { N_word count; N_word words; if (bits > 0) { count = bits AND BV_ModMask; words = bits >> BV_LogBits; if (bits >= BV_BITS_(addr)) BitVector_Empty(addr); else { while (count-- > 0) BitVector_shift_right(addr,0); BitVector_Word_Delete(addr,0,words,true); } } } void BitVector_Insert(wordptr addr, N_int offset, N_int count, boolean clear) { N_word bits = BV_BITS_(addr); N_word last; if ((count > 0) and (offset < bits)) { last = offset + count; if (last < bits) { BitVector_Interval_Copy(addr,addr,last,offset,(bits-last)); } else last = bits; if (clear) BitVector_Interval_Empty(addr,offset,(last-1)); } } void BitVector_Delete(wordptr addr, N_int offset, N_int count, boolean clear) { N_word bits = BV_BITS_(addr); N_word last; if ((count > 0) and (offset < bits)) { last = offset + count; if (last < bits) { BitVector_Interval_Copy(addr,addr,offset,last,(bits-last)); } else count = bits - offset; if (clear) BitVector_Interval_Empty(addr,(bits-count),(bits-1)); } } boolean BitVector_increment(wordptr addr) /* X++ */ { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); wordptr last = addr + size - 1; boolean carry = true; if (size > 0) { *last |= NOT mask; while (carry and (size-- > 0)) { carry = (++(*addr++) == 0); } *last &= mask; } return(carry); } boolean BitVector_decrement(wordptr addr) /* X-- */ { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); wordptr last = addr + size - 1; boolean carry = true; if (size > 0) { *last &= mask; while (carry and (size-- > 0)) { carry = (*addr == 0); --(*addr++); } *last &= mask; } return(carry); } boolean BitVector_compute(wordptr X, wordptr Y, wordptr Z, boolean minus, boolean *carry) { N_word size = BV_SIZE_(X); N_word mask = BV_MASK_(X); N_word vv = 0; N_word cc; N_word mm; N_word yy; N_word zz; N_word lo; N_word hi; if (size > 0) { if (minus) cc = (*carry == 0); else cc = (*carry != 0); /* deal with (size-1) least significant full words first: */ while (--size > 0) { yy = *Y++; if (minus) zz = (N_word) NOT ( Z ? *Z++ : 0 ); else zz = (N_word) ( Z ? *Z++ : 0 ); lo = (yy AND BV_LSB) + (zz AND BV_LSB) + cc; hi = (yy >> 1) + (zz >> 1) + (lo >> 1); cc = ((hi AND BV_MSB) != 0); *X++ = (hi << 1) OR (lo AND BV_LSB); } /* deal with most significant word (may be used only partially): */ yy = *Y AND mask; if (minus) zz = (N_word) NOT ( Z ? *Z : 0 ); else zz = (N_word) ( Z ? *Z : 0 ); zz &= mask; if (mask == BV_LSB) /* special case, only one bit used */ { vv = cc; lo = yy + zz + cc; cc = (lo >> 1); vv ^= cc; *X = lo AND BV_LSB; } else { if (NOT mask) /* not all bits are used, but more than one */ { mm = (mask >> 1); vv = (yy AND mm) + (zz AND mm) + cc; mm = mask AND NOT mm; lo = yy + zz + cc; cc = (lo >> 1); vv ^= cc; vv &= mm; cc &= mm; *X = lo AND mask; } else /* other special case, all bits are used */ { mm = NOT BV_MSB; lo = (yy AND mm) + (zz AND mm) + cc; vv = lo AND BV_MSB; hi = ((yy AND BV_MSB) >> 1) + ((zz AND BV_MSB) >> 1) + (vv >> 1); cc = hi AND BV_MSB; vv ^= cc; *X = (hi << 1) OR (lo AND mm); } } if (minus) *carry = (cc == 0); else *carry = (cc != 0); } return(vv != 0); } boolean BitVector_add(wordptr X, wordptr Y, wordptr Z, boolean *carry) { return(BitVector_compute(X,Y,Z,false,carry)); } boolean BitVector_sub(wordptr X, wordptr Y, wordptr Z, boolean *carry) { return(BitVector_compute(X,Y,Z,true,carry)); } boolean BitVector_inc(wordptr X, wordptr Y) { boolean carry = true; return(BitVector_compute(X,Y,NULL,false,&carry)); } boolean BitVector_dec(wordptr X, wordptr Y) { boolean carry = true; return(BitVector_compute(X,Y,NULL,true,&carry)); } void BitVector_Negate(wordptr X, wordptr Y) { N_word size = BV_SIZE_(X); N_word mask = BV_MASK_(X); boolean carry = true; if (size > 0) { while (size-- > 0) { *X = NOT *Y++; if (carry) { carry = (++(*X) == 0); } X++; } *(--X) &= mask; } } void BitVector_Absolute(wordptr X, wordptr Y) { N_word size = BV_SIZE_(Y); N_word mask = BV_MASK_(Y); if (size > 0) { if (*(Y+size-1) AND (mask AND NOT (mask >> 1))) BitVector_Negate(X,Y); else BitVector_Copy(X,Y); } } Z_int BitVector_Sign(wordptr addr) { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); wordptr last = addr + size - 1; boolean r = true; if (size > 0) { *last &= mask; while (r and (size-- > 0)) r = ( *addr++ == 0 ); } if (r) return((Z_int) 0); else { if (*last AND (mask AND NOT (mask >> 1))) return((Z_int) -1); else return((Z_int) 1); } } BV_ErrCode BitVector_Mul_Pos(wordptr X, wordptr Y, wordptr Z, boolean strict) { N_word mask; N_word limit; N_word count; Z_long last; wordptr sign; boolean carry; boolean overflow; boolean ok = true; /* Requirements: - X, Y and Z must be distinct - X and Y must have equal sizes (whereas Z may be any size!) - Z should always contain the SMALLER of the two factors Y and Z Constraints: - The contents of Y (and of X, of course) are destroyed (only Z is preserved!) */ if ((X == Y) or (X == Z) or (Y == Z)) return(BV_ErrCode_Same); if (BV_BITS_(X) != BV_BITS_(Y)) return(BV_ErrCode_Size); BitVector_Empty(X); if (BitVector_is_empty(Y)) return(BV_ErrCode_Ok); /* also if BV_BITS_(Y)==0 */ if ((last = Set_Max(Z)) < 0L) return(BV_ErrCode_Ok); limit = (N_word) last; sign = Y + BV_SIZE_(Y) - 1; mask = BV_MASK_(Y); *sign &= mask; mask &= NOT (mask >> 1); for ( count = 0; (ok and (count <= limit)); count++ ) { if ( BIT_VECTOR_TST_BIT(Z,count) ) { carry = false; overflow = BitVector_compute(X,X,Y,false,&carry); if (strict) ok = not (carry or overflow); else ok = not carry; } if (ok and (count < limit)) { carry = BitVector_shift_left(Y,0); if (strict) { overflow = ((*sign AND mask) != 0); ok = not (carry or overflow); } else ok = not carry; } } if (ok) return(BV_ErrCode_Ok); else return(BV_ErrCode_Ovfl); } BV_ErrCode BitVector_Multiply(wordptr X, wordptr Y, wordptr Z) { BV_ErrCode error = BV_ErrCode_Ok; N_word bit_x = BV_BITS_(X); N_word bit_y = BV_BITS_(Y); N_word bit_z = BV_BITS_(Z); N_word size; N_word mask; N_word msb; wordptr ptr_y; wordptr ptr_z; boolean sgn_x; boolean sgn_y; boolean sgn_z; boolean zero; wordptr A; wordptr B; /* Requirements: - Y and Z must have equal sizes - X must have at least the same size as Y and Z but may be larger (!) Features: - The contents of Y and Z are preserved - X may be identical with Y or Z (or both!) (in-place multiplication is possible!) */ if ((bit_y != bit_z) or (bit_x < bit_y)) return(BV_ErrCode_Size); if (BitVector_is_empty(Y) or BitVector_is_empty(Z)) { BitVector_Empty(X); } else { A = BitVector_Create(bit_y,false); if (A == NULL) return(BV_ErrCode_Null); B = BitVector_Create(bit_z,false); if (B == NULL) { BitVector_Destroy(A); return(BV_ErrCode_Null); } size = BV_SIZE_(Y); mask = BV_MASK_(Y); msb = (mask AND NOT (mask >> 1)); sgn_y = (((*(Y+size-1) &= mask) AND msb) != 0); sgn_z = (((*(Z+size-1) &= mask) AND msb) != 0); sgn_x = sgn_y XOR sgn_z; if (sgn_y) BitVector_Negate(A,Y); else BitVector_Copy(A,Y); if (sgn_z) BitVector_Negate(B,Z); else BitVector_Copy(B,Z); ptr_y = A + size; ptr_z = B + size; zero = true; while (zero and (size-- > 0)) { zero &= (*(--ptr_y) == 0); zero &= (*(--ptr_z) == 0); } if (*ptr_y > *ptr_z) { if (bit_x > bit_y) { A = BitVector_Resize(A,bit_x); if (A == NULL) { BitVector_Destroy(B); return(BV_ErrCode_Null); } } error = BitVector_Mul_Pos(X,A,B,true); } else { if (bit_x > bit_z) { B = BitVector_Resize(B,bit_x); if (B == NULL) { BitVector_Destroy(A); return(BV_ErrCode_Null); } } error = BitVector_Mul_Pos(X,B,A,true); } if ((not error) and sgn_x) BitVector_Negate(X,X); BitVector_Destroy(A); BitVector_Destroy(B); } return(error); } BV_ErrCode BitVector_Div_Pos(wordptr Q, wordptr X, wordptr Y, wordptr R) { N_word bits = BV_BITS_(Q); N_word mask; wordptr addr; Z_long last; boolean flag; boolean copy = false; /* flags whether valid rest is in R (0) or X (1) */ /* Requirements: - All bit vectors must have equal sizes - Q, X, Y and R must all be distinct bit vectors - Y must be non-zero (of course!) Constraints: - The contents of X (and Q and R, of course) are destroyed (only Y is preserved!) */ if ((bits != BV_BITS_(X)) or (bits != BV_BITS_(Y)) or (bits != BV_BITS_(R))) return(BV_ErrCode_Size); if ((Q == X) or (Q == Y) or (Q == R) or (X == Y) or (X == R) or (Y == R)) return(BV_ErrCode_Same); if (BitVector_is_empty(Y)) return(BV_ErrCode_Zero); BitVector_Empty(R); BitVector_Copy(Q,X); if ((last = Set_Max(Q)) < 0L) return(BV_ErrCode_Ok); bits = (N_word) ++last; while (bits-- > 0) { addr = Q + (bits >> BV_LogBits); mask = BV_BitMaskTab[bits AND BV_ModMask]; flag = ((*addr AND mask) != 0); if (copy) { BitVector_shift_left(X,flag); flag = false; BitVector_compute(R,X,Y,true,&flag); } else { BitVector_shift_left(R,flag); flag = false; BitVector_compute(X,R,Y,true,&flag); } if (flag) *addr &= NOT mask; else { *addr |= mask; copy = not copy; } } if (copy) BitVector_Copy(R,X); return(BV_ErrCode_Ok); } BV_ErrCode BitVector_Divide(wordptr Q, wordptr X, wordptr Y, wordptr R) { BV_ErrCode error = BV_ErrCode_Ok; N_word bits = BV_BITS_(Q); N_word size = BV_SIZE_(Q); N_word mask = BV_MASK_(Q); N_word msb = (mask AND NOT (mask >> 1)); boolean sgn_q; boolean sgn_x; boolean sgn_y; wordptr A; wordptr B; /* Requirements: - All bit vectors must have equal sizes - Q and R must be two distinct bit vectors - Y must be non-zero (of course!) Features: - The contents of X and Y are preserved - Q may be identical with X or Y (or both) (in-place division is possible!) - R may be identical with X or Y (or both) (but not identical with Q!) */ if ((bits != BV_BITS_(X)) or (bits != BV_BITS_(Y)) or (bits != BV_BITS_(R))) return(BV_ErrCode_Size); if (Q == R) return(BV_ErrCode_Same); if (BitVector_is_empty(Y)) return(BV_ErrCode_Zero); if (BitVector_is_empty(X)) { BitVector_Empty(Q); BitVector_Empty(R); } else { A = BitVector_Create(bits,false); if (A == NULL) return(BV_ErrCode_Null); B = BitVector_Create(bits,false); if (B == NULL) { BitVector_Destroy(A); return(BV_ErrCode_Null); } size--; sgn_x = (((*(X+size) &= mask) AND msb) != 0); sgn_y = (((*(Y+size) &= mask) AND msb) != 0); sgn_q = sgn_x XOR sgn_y; if (sgn_x) BitVector_Negate(A,X); else BitVector_Copy(A,X); if (sgn_y) BitVector_Negate(B,Y); else BitVector_Copy(B,Y); if (not (error = BitVector_Div_Pos(Q,A,B,R))) { if (sgn_q) BitVector_Negate(Q,Q); if (sgn_x) BitVector_Negate(R,R); } BitVector_Destroy(A); BitVector_Destroy(B); } return(error); } BV_ErrCode BitVector_GCD(wordptr X, wordptr Y, wordptr Z) { BV_ErrCode error = BV_ErrCode_Ok; N_word bits = BV_BITS_(X); N_word size = BV_SIZE_(X); N_word mask = BV_MASK_(X); N_word msb = (mask AND NOT (mask >> 1)); boolean sgn_a; boolean sgn_b; boolean sgn_r; wordptr Q; wordptr R; wordptr A; wordptr B; wordptr T; /* Requirements: - All bit vectors must have equal sizes Features: - The contents of Y and Z are preserved - X may be identical with Y or Z (or both) (in-place is possible!) - GCD(0,z) == GCD(z,0) == z - negative values are handled correctly */ if ((bits != BV_BITS_(Y)) or (bits != BV_BITS_(Z))) return(BV_ErrCode_Size); if (BitVector_is_empty(Y)) { if (X != Z) BitVector_Copy(X,Z); return(BV_ErrCode_Ok); } if (BitVector_is_empty(Z)) { if (X != Y) BitVector_Copy(X,Y); return(BV_ErrCode_Ok); } Q = BitVector_Create(bits,false); if (Q == NULL) { return(BV_ErrCode_Null); } R = BitVector_Create(bits,false); if (R == NULL) { BitVector_Destroy(Q); return(BV_ErrCode_Null); } A = BitVector_Create(bits,false); if (A == NULL) { BitVector_Destroy(Q); BitVector_Destroy(R); return(BV_ErrCode_Null); } B = BitVector_Create(bits,false); if (B == NULL) { BitVector_Destroy(Q); BitVector_Destroy(R); BitVector_Destroy(A); return(BV_ErrCode_Null); } size--; sgn_a = (((*(Y+size) &= mask) AND msb) != 0); sgn_b = (((*(Z+size) &= mask) AND msb) != 0); if (sgn_a) BitVector_Negate(A,Y); else BitVector_Copy(A,Y); if (sgn_b) BitVector_Negate(B,Z); else BitVector_Copy(B,Z); while (not error) { if (not (error = BitVector_Div_Pos(Q,A,B,R))) { if (BitVector_is_empty(R)) break; T = A; sgn_r = sgn_a; A = B; sgn_a = sgn_b; B = R; sgn_b = sgn_r; R = T; } } if (not error) { if (sgn_b) BitVector_Negate(X,B); else BitVector_Copy(X,B); } BitVector_Destroy(Q); BitVector_Destroy(R); BitVector_Destroy(A); BitVector_Destroy(B); return(error); } BV_ErrCode BitVector_GCD2(wordptr U, wordptr V, wordptr W, wordptr X, wordptr Y) { BV_ErrCode error = BV_ErrCode_Ok; N_word bits = BV_BITS_(U); N_word size = BV_SIZE_(U); N_word mask = BV_MASK_(U); N_word msb = (mask AND NOT (mask >> 1)); bv_listptr L; boolean minus; boolean carry; boolean sgn_q; boolean sgn_r; boolean sgn_a; boolean sgn_b; boolean sgn_x; boolean sgn_y; wordptr Q; wordptr R; wordptr A; wordptr B; wordptr T; wordptr X1; wordptr X2; wordptr X3; wordptr Y1; wordptr Y2; wordptr Y3; wordptr Z; /* Requirements: - All bit vectors must have equal sizes - U, V, and W must all be distinct bit vectors Features: - The contents of X and Y are preserved - U, V and W may be identical with X or Y (or both, provided that U, V and W are mutually distinct) (i.e., in-place is possible!) - GCD(0,z) == GCD(z,0) == z - negative values are handled correctly */ if ((bits != BV_BITS_(V)) or (bits != BV_BITS_(W)) or (bits != BV_BITS_(X)) or (bits != BV_BITS_(Y))) { return(BV_ErrCode_Size); } if ((U == V) or (U == W) or (V == W)) { return(BV_ErrCode_Same); } if ((bits == 0) or (size == 0)) { return(BV_ErrCode_Ok); } if (BitVector_is_empty(X)) { if (U != Y) BitVector_Copy(U,Y); BitVector_Empty(V); BitVector_Empty(W); if (BV_SIZE_(W)) *W = 1; return(BV_ErrCode_Ok); } if (BitVector_is_empty(Y)) { if (U != X) BitVector_Copy(U,X); BitVector_Empty(V); BitVector_Empty(W); if (BV_SIZE_(V)) *V = 1; return(BV_ErrCode_Ok); } if ((L = BitVector_Create_List(bits,false,11)) == NULL) { return(BV_ErrCode_Null); } Q = L[0]; R = L[1]; A = L[2]; B = L[3]; X1 = L[4]; X2 = L[5]; X3 = L[6]; Y1 = L[7]; Y2 = L[8]; Y3 = L[9]; Z = L[10]; size--; sgn_a = (((*(X+size) &= mask) AND msb) != 0); sgn_b = (((*(Y+size) &= mask) AND msb) != 0); if (sgn_a) BitVector_Negate(A,X); else BitVector_Copy(A,X); if (sgn_b) BitVector_Negate(B,Y); else BitVector_Copy(B,Y); BitVector_Empty(X1); BitVector_Empty(X2); *X1 = 1; BitVector_Empty(Y1); BitVector_Empty(Y2); *Y2 = 1; sgn_x = false; sgn_y = false; while (not error) { if ((error = BitVector_Div_Pos(Q,A,B,R))) { break; } if (BitVector_is_empty(R)) { break; } sgn_q = sgn_a XOR sgn_b; if (sgn_x) BitVector_Negate(Z,X2); else BitVector_Copy(Z,X2); if ((error = BitVector_Mul_Pos(X3,Z,Q,true))) { break; } minus = not (sgn_x XOR sgn_q); carry = 0; if (BitVector_compute(X3,X1,X3,minus,&carry)) { error = BV_ErrCode_Ovfl; break; } sgn_x = (((*(X3+size) &= mask) AND msb) != 0); if (sgn_y) BitVector_Negate(Z,Y2); else BitVector_Copy(Z,Y2); if ((error = BitVector_Mul_Pos(Y3,Z,Q,true))) { break; } minus = not (sgn_y XOR sgn_q); carry = 0; if (BitVector_compute(Y3,Y1,Y3,minus,&carry)) { error = BV_ErrCode_Ovfl; break; } sgn_y = (((*(Y3+size) &= mask) AND msb) != 0); T = A; sgn_r = sgn_a; A = B; sgn_a = sgn_b; B = R; sgn_b = sgn_r; R = T; T = X1; X1 = X2; X2 = X3; X3 = T; T = Y1; Y1 = Y2; Y2 = Y3; Y3 = T; } if (not error) { if (sgn_b) BitVector_Negate(U,B); else BitVector_Copy(U,B); BitVector_Copy(V,X2); BitVector_Copy(W,Y2); } BitVector_Destroy_List(L,11); return(error); } BV_ErrCode BitVector_Power(wordptr X, wordptr Y, wordptr Z) { BV_ErrCode error = BV_ErrCode_Ok; N_word bits = BV_BITS_(X); boolean first = true; Z_long last; N_word limit; N_word count; wordptr T; /* Requirements: - X must have at least the same size as Y but may be larger (!) - X may not be identical with Z - Z must be positive Features: - The contents of Y and Z are preserved */ if (X == Z) return(BV_ErrCode_Same); if (bits < BV_BITS_(Y)) return(BV_ErrCode_Size); if (BitVector_msb_(Z)) return(BV_ErrCode_Expo); if ((last = Set_Max(Z)) < 0L) { if (bits < 2) return(BV_ErrCode_Ovfl); BitVector_Empty(X); *X |= BV_LSB; return(BV_ErrCode_Ok); /* anything ^ 0 == 1 */ } if (BitVector_is_empty(Y)) { if (X != Y) BitVector_Empty(X); return(BV_ErrCode_Ok); /* 0 ^ anything not zero == 0 */ } T = BitVector_Create(bits,false); if (T == NULL) return(BV_ErrCode_Null); limit = (N_word) last; for ( count = 0; ((!error) and (count <= limit)); count++ ) { if ( BIT_VECTOR_TST_BIT(Z,count) ) { if (first) { first = false; if (count) { BitVector_Copy(X,T); } else { if (X != Y) BitVector_Copy(X,Y); } } else error = BitVector_Multiply(X,T,X); /* order important because T > X */ } if ((!error) and (count < limit)) { if (count) error = BitVector_Multiply(T,T,T); else error = BitVector_Multiply(T,Y,Y); } } BitVector_Destroy(T); return(error); } void BitVector_Block_Store(wordptr addr, charptr buffer, N_int length) { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); N_word value; N_word count; /* provide translation for independence of endian-ness: */ if (size > 0) { while (size-- > 0) { value = 0; for ( count = 0; (length > 0) and (count < BV_WordBits); count += 8 ) { value |= (((N_word) *buffer++) << count); length--; } *addr++ = value; } *(--addr) &= mask; } } charptr BitVector_Block_Read(wordptr addr, N_intptr length) { N_word size = BV_SIZE_(addr); N_word value; N_word count; charptr buffer; charptr target; /* provide translation for independence of endian-ness: */ *length = size << BV_Factor; buffer = (charptr) malloc((size_t) ((*length)+1)); if (buffer == NULL) return(NULL); target = buffer; if (size > 0) { *(addr+size-1) &= BV_MASK_(addr); while (size-- > 0) { value = *addr++; count = BV_WordBits >> 3; while (count-- > 0) { *target++ = (N_char) (value AND 0x00FF); if (count > 0) value >>= 8; } } } *target = (N_char) '\0'; return(buffer); } void BitVector_Word_Store(wordptr addr, N_int offset, N_int value) { N_word size = BV_SIZE_(addr); if (size > 0) { if (offset < size) *(addr+offset) = value; *(addr+size-1) &= BV_MASK_(addr); } } N_int BitVector_Word_Read(wordptr addr, N_int offset) { N_word size = BV_SIZE_(addr); if (size > 0) { *(addr+size-1) &= BV_MASK_(addr); if (offset < size) return( *(addr+offset) ); } return( (N_int) 0 ); } void BitVector_Word_Insert(wordptr addr, N_int offset, N_int count, boolean clear) { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); wordptr last = addr+size-1; if (size > 0) { *last &= mask; if (offset > size) offset = size; BIT_VECTOR_ins_words(addr+offset,size-offset,count,clear); *last &= mask; } } void BitVector_Word_Delete(wordptr addr, N_int offset, N_int count, boolean clear) { N_word size = BV_SIZE_(addr); N_word mask = BV_MASK_(addr); wordptr last = addr+size-1; if (size > 0) { *last &= mask; if (offset > size) offset = size; BIT_VECTOR_del_words(addr+offset,size-offset,count,clear); *last &= mask; } } void BitVector_Chunk_Store(wordptr addr, N_int chunksize, N_int offset, N_long value) { N_word bits = BV_BITS_(addr); N_word mask; N_word temp; if ((chunksize > 0) and (offset < bits)) { if (chunksize > BV_LongBits) chunksize = BV_LongBits; if ((offset + chunksize) > bits) chunksize = bits - offset; addr += offset >> BV_LogBits; offset &= BV_ModMask; while (chunksize > 0) { mask = (N_word) (~0L << offset); bits = offset + chunksize; if (bits < BV_WordBits) { mask &= (N_word) ~(~0L << bits); bits = chunksize; } else bits = BV_WordBits - offset; temp = (N_word) (value << offset); temp &= mask; *addr &= NOT mask; *addr++ |= temp; value >>= bits; chunksize -= bits; offset = 0; } } } N_long BitVector_Chunk_Read(wordptr addr, N_int chunksize, N_int offset) { N_word bits = BV_BITS_(addr); N_word chunkbits = 0; N_long value = 0L; N_long temp; N_word mask; if ((chunksize > 0) and (offset < bits)) { if (chunksize > BV_LongBits) chunksize = BV_LongBits; if ((offset + chunksize) > bits) chunksize = bits - offset; addr += offset >> BV_LogBits; offset &= BV_ModMask; while (chunksize > 0) { bits = offset + chunksize; if (bits < BV_WordBits) { mask = (N_word) ~(~0L << bits); bits = chunksize; } else { mask = (N_word) ~0L; bits = BV_WordBits - offset; } temp = (N_long) ((*addr++ AND mask) >> offset); value |= temp << chunkbits; chunkbits += bits; chunksize -= bits; offset = 0; } } return(value); } /*******************/ /* set operations: */ /*******************/ void Set_Union(wordptr X, wordptr Y, wordptr Z) /* X = Y + Z */ { N_word bits = BV_BITS_(X); N_word size = BV_SIZE_(X); N_word mask = BV_MASK_(X); if ((size > 0) and (bits == BV_BITS_(Y)) and (bits == BV_BITS_(Z))) { while (size-- > 0) *X++ = *Y++ OR *Z++; *(--X) &= mask; } } void Set_Intersection(wordptr X, wordptr Y, wordptr Z) /* X = Y * Z */ { N_word bits = BV_BITS_(X); N_word size = BV_SIZE_(X); N_word mask = BV_MASK_(X); if ((size > 0) and (bits == BV_BITS_(Y)) and (bits == BV_BITS_(Z))) { while (size-- > 0) *X++ = *Y++ AND *Z++; *(--X) &= mask; } } void Set_Difference(wordptr X, wordptr Y, wordptr Z) /* X = Y \ Z */ { N_word bits = BV_BITS_(X); N_word size = BV_SIZE_(X); N_word mask = BV_MASK_(X); if ((size > 0) and (bits == BV_BITS_(Y)) and (bits == BV_BITS_(Z))) { while (size-- > 0) *X++ = *Y++ AND NOT *Z++; *(--X) &= mask; } } void Set_ExclusiveOr(wordptr X, wordptr Y, wordptr Z) /* X=(Y+Z)\(Y*Z) */ { N_word bits = BV_BITS_(X); N_word size = BV_SIZE_(X); N_word mask = BV_MASK_(X); if ((size > 0) and (bits == BV_BITS_(Y)) and (bits == BV_BITS_(Z))) { while (size-- > 0) *X++ = *Y++ XOR *Z++; *(--X) &= mask; } } void Set_Complement(wordptr X, wordptr Y) /* X = ~Y */ { N_word size = BV_SIZE_(X); N_word mask = BV_MASK_(X); if ((size > 0) and (BV_BITS_(X) == BV_BITS_(Y))) { while (size-- > 0) *X++ = NOT *Y++; *(--X) &= mask; } } /******************/ /* set functions: */ /******************/ boolean Set_subset(wordptr X, wordptr Y) /* X subset Y ? */ { N_word size = BV_SIZE_(X); boolean r = false; if ((size > 0) and (BV_BITS_(X) == BV_BITS_(Y))) { r = true; while (r and (size-- > 0)) r = ((*X++ AND NOT *Y++) == 0); } return(r); } N_int Set_Norm(wordptr addr) /* = | X | */ { byteptr byte; N_word bytes; N_int n; byte = (byteptr) addr; bytes = BV_SIZE_(addr) << BV_Factor; n = 0; while (bytes-- > 0) { n += BV_ByteNorm[*byte++]; } return(n); } N_int Set_Norm2(wordptr addr) /* = | X | */ { N_word size = BV_SIZE_(addr); N_word w0,w1; N_int n,k; n = 0; while (size-- > 0) { k = 0; w1 = NOT (w0 = *addr++); while (w0 and w1) { w0 &= w0 - 1; w1 &= w1 - 1; k++; } if (w0 == 0) n += k; else n += BV_WordBits - k; } return(n); } N_int Set_Norm3(wordptr addr) /* = | X | */ { N_word size = BV_SIZE_(addr); N_int count = 0; N_word c; while (size-- > 0) { c = *addr++; while (c) { c &= c - 1; count++; } } return(count); } Z_long Set_Min(wordptr addr) /* = min(X) */ { boolean empty = true; N_word size = BV_SIZE_(addr); N_word i = 0; N_word c = 0; /* silence compiler warning */ while (empty and (size-- > 0)) { if ((c = *addr++)) empty = false; else i++; } if (empty) return((Z_long) LONG_MAX); /* plus infinity */ i <<= BV_LogBits; while (not (c AND BV_LSB)) { c >>= 1; i++; } return((Z_long) i); } Z_long Set_Max(wordptr addr) /* = max(X) */ { boolean empty = true; N_word size = BV_SIZE_(addr); N_word i = size; N_word c = 0; /* silence compiler warning */ addr += size-1; while (empty and (size-- > 0)) { if ((c = *addr--)) empty = false; else i--; } if (empty) return((Z_long) LONG_MIN); /* minus infinity */ i <<= BV_LogBits; while (not (c AND BV_MSB)) { c <<= 1; i--; } return((Z_long) --i); } /**********************************/ /* matrix-of-booleans operations: */ /**********************************/ void Matrix_Multiplication(wordptr X, N_int rowsX, N_int colsX, wordptr Y, N_int rowsY, N_int colsY, wordptr Z, N_int rowsZ, N_int colsZ) { N_word i; N_word j; N_word k; N_word indxX; N_word indxY; N_word indxZ; N_word termX; N_word termY; N_word sum; if ((colsY == rowsZ) and (rowsX == rowsY) and (colsX == colsZ) and (BV_BITS_(X) == rowsX*colsX) and (BV_BITS_(Y) == rowsY*colsY) and (BV_BITS_(Z) == rowsZ*colsZ)) { for ( i = 0; i < rowsY; i++ ) { termX = i * colsX; termY = i * colsY; for ( j = 0; j < colsZ; j++ ) { indxX = termX + j; sum = 0; for ( k = 0; k < colsY; k++ ) { indxY = termY + k; indxZ = k * colsZ + j; if ( BIT_VECTOR_TST_BIT(Y,indxY) && BIT_VECTOR_TST_BIT(Z,indxZ) ) sum ^= 1; } if (sum) BIT_VECTOR_SET_BIT(X,indxX) else BIT_VECTOR_CLR_BIT(X,indxX) } } } } void Matrix_Product(wordptr X, N_int rowsX, N_int colsX, wordptr Y, N_int rowsY, N_int colsY, wordptr Z, N_int rowsZ, N_int colsZ) { N_word i; N_word j; N_word k; N_word indxX; N_word indxY; N_word indxZ; N_word termX; N_word termY; N_word sum; if ((colsY == rowsZ) and (rowsX == rowsY) and (colsX == colsZ) and (BV_BITS_(X) == rowsX*colsX) and (BV_BITS_(Y) == rowsY*colsY) and (BV_BITS_(Z) == rowsZ*colsZ)) { for ( i = 0; i < rowsY; i++ ) { termX = i * colsX; termY = i * colsY; for ( j = 0; j < colsZ; j++ ) { indxX = termX + j; sum = 0; for ( k = 0; k < colsY; k++ ) { indxY = termY + k; indxZ = k * colsZ + j; if ( BIT_VECTOR_TST_BIT(Y,indxY) && BIT_VECTOR_TST_BIT(Z,indxZ) ) sum |= 1; } if (sum) BIT_VECTOR_SET_BIT(X,indxX) else BIT_VECTOR_CLR_BIT(X,indxX) } } } } void Matrix_Closure(wordptr addr, N_int rows, N_int cols) { N_word i; N_word j; N_word k; N_word ii; N_word ij; N_word ik; N_word kj; N_word termi; N_word termk; if ((rows == cols) and (BV_BITS_(addr) == rows*cols)) { for ( i = 0; i < rows; i++ ) { ii = i * cols + i; BIT_VECTOR_SET_BIT(addr,ii) } for ( k = 0; k < rows; k++ ) { termk = k * cols; for ( i = 0; i < rows; i++ ) { termi = i * cols; ik = termi + k; for ( j = 0; j < rows; j++ ) { ij = termi + j; kj = termk + j; if ( BIT_VECTOR_TST_BIT(addr,ik) && BIT_VECTOR_TST_BIT(addr,kj) ) BIT_VECTOR_SET_BIT(addr,ij) } } } } } void Matrix_Transpose(wordptr X, N_int rowsX, N_int colsX, wordptr Y, N_int rowsY, N_int colsY) { N_word i; N_word j; N_word ii; N_word ij; N_word ji; N_word addii; N_word addij; N_word addji; N_word bitii; N_word bitij; N_word bitji; N_word termi; N_word termj; boolean swap; /* BEWARE that "in-place" is ONLY possible if the matrix is quadratic!! */ if ((rowsX == colsY) and (colsX == rowsY) and (BV_BITS_(X) == rowsX*colsX) and (BV_BITS_(Y) == rowsY*colsY)) { if (rowsY == colsY) /* in-place is possible! */ { for ( i = 0; i < rowsY; i++ ) { termi = i * colsY; for ( j = 0; j < i; j++ ) { termj = j * colsX; ij = termi + j; ji = termj + i; addij = ij >> BV_LogBits; addji = ji >> BV_LogBits; bitij = BV_BitMaskTab[ij AND BV_ModMask]; bitji = BV_BitMaskTab[ji AND BV_ModMask]; swap = ((*(Y+addij) AND bitij) != 0); if ((*(Y+addji) AND bitji) != 0) *(X+addij) |= bitij; else *(X+addij) &= NOT bitij; if (swap) *(X+addji) |= bitji; else *(X+addji) &= NOT bitji; } ii = termi + i; addii = ii >> BV_LogBits; bitii = BV_BitMaskTab[ii AND BV_ModMask]; if ((*(Y+addii) AND bitii) != 0) *(X+addii) |= bitii; else *(X+addii) &= NOT bitii; } } else /* rowsX != colsX, in-place is NOT possible! */ { for ( i = 0; i < rowsY; i++ ) { termi = i * colsY; for ( j = 0; j < colsY; j++ ) { termj = j * colsX; ij = termi + j; ji = termj + i; addij = ij >> BV_LogBits; addji = ji >> BV_LogBits; bitij = BV_BitMaskTab[ij AND BV_ModMask]; bitji = BV_BitMaskTab[ji AND BV_ModMask]; if ((*(Y+addij) AND bitij) != 0) *(X+addji) |= bitji; else *(X+addji) &= NOT bitji; } } } } } /*****************************************************************************/ /* VERSION: 7.4 */ /*****************************************************************************/ /* VERSION HISTORY: */ /*****************************************************************************/ /* */ /* Version 7.4 03.09.13 No changes. */ /* Version 7.3 01.06.13 No changes. */ /* Version 7.2 17.05.12 No changes. */ /* Version 7.1 29.09.09 Added prefix "BV_" to all global identifiers. */ /* Version 7.0 22.08.09 Fixed bugs in "GCD2()" and "Boot()". */ /* Version 6.9 12.08.09 Removed an obsolete warning (memory leak). */ /* Version 6.8 10.08.09 Fixed hard-coded table size BV_MASKTABSIZE. */ /* Version 6.7 08.08.09 No changes. */ /* Version 6.6 27.07.09 Made it thread-safe and MacOS X compatible. */ /* Version 6.5 27.07.09 Added automatic support for module "Storable". */ /* Version 6.4 03.10.04 Added C++ comp. directives. Improved "Norm()". */ /* Version 6.3 28.09.02 Added "Create_List()" and "GCD2()". */ /* Version 6.2 15.09.02 Overhauled error handling. Fixed "GCD()". */ /* Version 6.1 08.10.01 Make VMS linker happy: _lsb,_msb => _lsb_,_msb_ */ /* Version 6.0 08.10.00 Corrected overflow handling. */ /* Version 5.8 14.07.00 Added "Power()". Changed "Copy()". */ /* Version 5.7 19.05.99 Quickened "Div_Pos()". Added "Product()". */ /* Version 5.6 02.11.98 Leading zeros eliminated in "to_Hex()". */ /* Version 5.5 21.09.98 Fixed bug of uninitialized "error" in Multiply. */ /* Version 5.4 07.09.98 Fixed bug of uninitialized "error" in Divide. */ /* Version 5.3 12.05.98 Improved Norm. Completed history. */ /* Version 5.2 31.03.98 Improved Norm. */ /* Version 5.1 09.03.98 No changes. */ /* Version 5.0 01.03.98 Major additions and rewrite. */ /* Version 4.2 16.07.97 Added is_empty, is_full. */ /* Version 4.1 30.06.97 Added word-ins/del, move-left/right, inc/dec. */ /* Version 4.0 23.04.97 Rewrite. Added bit shift and bool. matrix ops. */ /* Version 3.2 04.02.97 Added interval methods. */ /* Version 3.1 21.01.97 Fixed bug on 64 bit machines. */ /* Version 3.0 12.01.97 Added flip. */ /* Version 2.0 14.12.96 Efficiency and consistency improvements. */ /* Version 1.1 08.01.96 Added Resize and ExclusiveOr. */ /* Version 1.0 14.12.95 First version under UNIX (with Perl module). */ /* Version 0.9 01.11.93 First version of C library under MS-DOS. */ /* Version 0.1 ??.??.89 First version in Turbo Pascal under CP/M. */ /* */ /*****************************************************************************/ /* AUTHOR: */ /*****************************************************************************/ /* */ /* Steffen Beyer */ /* mailto:STBEY@cpan.org */ /* http://www.engelschall.com/u/sb/download/ */ /* */ /*****************************************************************************/ /* COPYRIGHT: */ /*****************************************************************************/ /* */ /* Copyright (c) 1995 - 2013 by Steffen Beyer. */ /* All rights reserved. */ /* */ /*****************************************************************************/ /* LICENSE: */ /*****************************************************************************/ /* */ /* This library is free software; you can redistribute it and/or */ /* modify it under the terms of the GNU Library General Public */ /* License as published by the Free Software Foundation; either */ /* version 2 of the License, or (at your option) any later version. */ /* */ /* This library is distributed in the hope that it will be useful, */ /* but WITHOUT ANY WARRANTY; without even the implied warranty of */ /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU */ /* Library General Public License for more details. */ /* */ /* You should have received a copy of the GNU Library General Public */ /* License along with this library; if not, write to the */ /* Free Software Foundation, Inc., */ /* 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ /* */ /* or download a copy from ftp://ftp.gnu.org/pub/gnu/COPYING.LIB-2.0 */ /* */ /*****************************************************************************/ #endif