1 #include "util.h" 2 3 #include "coretype.h" 4 5 /*****************************************************************************/ 6 /* MODULE NAME: BitVector.c MODULE TYPE: (adt) */ 7 /*****************************************************************************/ 8 /* MODULE IMPORTS: */ 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 /*****************************************************************************/ 16 #include "bitvect.h" 17 18 /* ToolBox.h */ 19 #define and && /* logical (boolean) operators: lower case */ 20 #define or || 21 #define not ! 22 23 #define AND & /* binary (bitwise) operators: UPPER CASE */ 24 #define OR | 25 #define XOR ^ 26 #define NOT ~ 27 #define SHL << 28 #define SHR >> 29 30 #ifdef ENABLE_MODULO 31 #define mod % /* arithmetic operators */ 32 #endif 33 34 #define blockdef(name,size) unsigned char name[size] 35 #define blocktypedef(name,size) typedef unsigned char name[size] 36 37 /*****************************************************************************/ 38 /* MODULE RESOURCES: */ 39 /*****************************************************************************/ 40 41 #define bits_(BitVector) *(BitVector-3) 42 #define size_(BitVector) *(BitVector-2) 43 #define mask_(BitVector) *(BitVector-1) 44 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" 61 62 const N_int BitVector_BYTENORM[256] = 63 { 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 */ 96 }; 97 98 /*****************************************************************************/ 99 /* MODULE IMPLEMENTATION: */ 100 /*****************************************************************************/ 101 102 /**********************************************/ 103 /* global implementation-intrinsic constants: */ 104 /**********************************************/ 105 106 #define BIT_VECTOR_HIDDEN_WORDS 3 107 108 /*****************************************************************/ 109 /* global machine-dependent constants (set by "BitVector_Boot"): */ 110 /*****************************************************************/ 111 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) */ 116 117 static N_word LSB = 1; /* = mask for least significant bit */ 118 static N_word MSB; /* = mask for most significant bit */ 119 120 static N_word LONGBITS; /* = # of bits in unsigned long */ 121 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 */ 124 125 /********************************************************************/ 126 /* global bit mask table for fast access (set by "BitVector_Boot"): */ 127 /********************************************************************/ 128 129 static wordptr BITMASKTAB; 130 131 /*****************************/ 132 /* global macro definitions: */ 133 /*****************************/ 134 135 #define BIT_VECTOR_ZERO_WORDS(target,count) \ 136 while (count-- > 0) *target++ = 0; 137 138 #define BIT_VECTOR_FILL_WORDS(target,fill,count) \ 139 while (count-- > 0) *target++ = fill; 140 141 #define BIT_VECTOR_FLIP_WORDS(target,flip,count) \ 142 while (count-- > 0) *target++ ^= flip; 143 144 #define BIT_VECTOR_COPY_WORDS(target,source,count) \ 145 while (count-- > 0) *target++ = *source++; 146 147 #define BIT_VECTOR_BACK_WORDS(target,source,count) \ 148 { target += count; source += count; while (count-- > 0) *--target = *--source; } 149 150 #define BIT_VECTOR_CLR_BIT(address,index) \ 151 *(address+(index>>LOGBITS)) &= NOT BITMASKTAB[index AND MODMASK]; 152 153 #define BIT_VECTOR_SET_BIT(address,index) \ 154 *(address+(index>>LOGBITS)) |= BITMASKTAB[index AND MODMASK]; 155 156 #define BIT_VECTOR_TST_BIT(address,index) \ 157 ((*(address+(index>>LOGBITS)) AND BITMASKTAB[index AND MODMASK]) != 0) 158 159 #define BIT_VECTOR_FLP_BIT(address,index,mask) \ 160 (mask = BITMASKTAB[index AND MODMASK]), \ 161 (((*(addr+(index>>LOGBITS)) ^= mask) AND mask) != 0) 162 163 #define BIT_VECTOR_DIGITIZE(type,value,digit) \ 164 value = (type) ((digit = value) / 10); \ 165 digit -= value * 10; \ 166 digit += (type) '0'; 167 168 /*********************************************************/ 169 /* private low-level functions (potentially dangerous!): */ 170 /*********************************************************/ 171 172 static N_word power10(N_word x) 173 { 174 N_word y = 1; 175 176 while (x-- > 0) y *= 10; 177 return(y); 178 } 179 180 static void BIT_VECTOR_zro_words(wordptr addr, N_word count) 181 { 182 BIT_VECTOR_ZERO_WORDS(addr,count) 183 } 184 185 static void BIT_VECTOR_cpy_words(wordptr target, wordptr source, N_word count) 186 { 187 BIT_VECTOR_COPY_WORDS(target,source,count) 188 } 189 190 static void BIT_VECTOR_mov_words(wordptr target, wordptr source, N_word count) 191 { 192 if (target != source) 193 { 194 if (target < source) BIT_VECTOR_COPY_WORDS(target,source,count) 195 else BIT_VECTOR_BACK_WORDS(target,source,count) 196 } 197 } 198 199 static void BIT_VECTOR_ins_words(wordptr addr, N_word total, N_word count, 200 boolean clear) 201 { 202 N_word length; 203 204 if ((total > 0) and (count > 0)) 205 { 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); 210 } 211 } 212 213 static void BIT_VECTOR_del_words(wordptr addr, N_word total, N_word count, 214 boolean clear) 215 { 216 N_word length; 217 218 if ((total > 0) and (count > 0)) 219 { 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); 224 } 225 } 226 227 static void BIT_VECTOR_reverse(charptr string, N_word length) 228 { 229 charptr last; 230 N_char temp; 231 232 if (length > 1) 233 { 234 last = string + length - 1; 235 while (string < last) 236 { 237 temp = *string; 238 *string = *last; 239 *last = temp; 240 string++; 241 last--; 242 } 243 } 244 } 245 246 static N_word BIT_VECTOR_int2str(charptr string, N_word value) 247 { 248 N_word length; 249 N_word digit; 250 charptr work; 251 252 work = string; 253 if (value > 0) 254 { 255 length = 0; 256 while (value > 0) 257 { 258 BIT_VECTOR_DIGITIZE(N_word,value,digit) 259 *work++ = (N_char) digit; 260 length++; 261 } 262 BIT_VECTOR_reverse(string,length); 263 } 264 else 265 { 266 length = 1; 267 *work++ = (N_char) '0'; 268 } 269 return(length); 270 } 271 272 static N_word BIT_VECTOR_str2int(charptr string, N_word *value) 273 { 274 N_word length; 275 N_word digit; 276 277 *value = 0; 278 length = 0; 279 digit = (N_word) *string++; 280 /* separate because isdigit() is likely a macro! */ 281 while (isdigit((int)digit) != 0) 282 { 283 length++; 284 digit -= (N_word) '0'; 285 if (*value) *value *= 10; 286 *value += digit; 287 digit = (N_word) *string++; 288 } 289 return(length); 290 } 291 292 /********************************************/ 293 /* routine to convert error code to string: */ 294 /********************************************/ 295 296 const char * BitVector_Error(ErrCode error) 297 { 298 switch (error) 299 { 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; 317 } 318 } 319 320 /*****************************************/ 321 /* automatic self-configuration routine: */ 322 /*****************************************/ 323 324 /*******************************************************/ 325 /* */ 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!) */ 330 /* */ 331 /*******************************************************/ 332 333 ErrCode BitVector_Boot(void) 334 { 335 N_long longsample = 1L; 336 N_word sample = LSB; 337 N_word lsb; 338 339 if (sizeof(N_word) > sizeof(size_t)) return(ErrCode_Type); 340 341 BITS = 1; 342 while (sample <<= 1) BITS++; /* determine # of bits in a machine word */ 343 344 if (BITS != (sizeof(N_word) << 3)) return(ErrCode_Bits); 345 346 if (BITS < 16) return(ErrCode_Word); 347 348 LONGBITS = 1; 349 while (longsample <<= 1) LONGBITS++; /* = # of bits in an unsigned long */ 350 351 if (BITS > LONGBITS) return(ErrCode_Long); 352 353 LOGBITS = 0; 354 sample = BITS; 355 lsb = (sample AND LSB); 356 while ((sample >>= 1) and (not lsb)) 357 { 358 LOGBITS++; 359 lsb = (sample AND LSB); 360 } 361 362 if (sample) return(ErrCode_Powr); /* # of bits is not a power of 2! */ 363 364 if (BITS != (LSB << LOGBITS)) return(ErrCode_Loga); 365 366 MODMASK = BITS - 1; 367 FACTOR = LOGBITS - 3; /* ld(BITS / 8) = ld(BITS) - ld(8) = ld(BITS) - 3 */ 368 MSB = (LSB << MODMASK); 369 370 BITMASKTAB = (wordptr) yasm_xmalloc((size_t) (BITS << FACTOR)); 371 372 if (BITMASKTAB == NULL) return(ErrCode_Null); 373 374 for ( sample = 0; sample < BITS; sample++ ) 375 { 376 BITMASKTAB[sample] = (LSB << sample); 377 } 378 379 LOG10 = (N_word) (MODMASK * 0.30103); /* = (BITS - 1) * ( ln 2 / ln 10 ) */ 380 EXP10 = power10(LOG10); 381 382 return(ErrCode_Ok); 383 } 384 385 void BitVector_Shutdown(void) 386 { 387 if (BITMASKTAB) yasm_xfree(BITMASKTAB); 388 } 389 390 N_word BitVector_Size(N_int bits) /* bit vector size (# of words) */ 391 { 392 N_word size; 393 394 size = bits >> LOGBITS; 395 if (bits AND MODMASK) size++; 396 return(size); 397 } 398 399 N_word BitVector_Mask(N_int bits) /* bit vector mask (unused bits) */ 400 { 401 N_word mask; 402 403 mask = bits AND MODMASK; 404 if (mask) mask = (N_word) ~(~0L << mask); else mask = (N_word) ~0L; 405 return(mask); 406 } 407 408 const char * BitVector_Version(void) 409 { 410 return("6.4"); 411 } 412 413 N_int BitVector_Word_Bits(void) 414 { 415 return(BITS); 416 } 417 418 N_int BitVector_Long_Bits(void) 419 { 420 return(LONGBITS); 421 } 422 423 /********************************************************************/ 424 /* */ 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()"! */ 428 /* */ 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()"! */ 432 /* */ 433 /********************************************************************/ 434 435 void BitVector_Dispose(charptr string) /* free string */ 436 { 437 if (string != NULL) yasm_xfree((voidptr) string); 438 } 439 440 void BitVector_Destroy(wordptr addr) /* free bitvec */ 441 { 442 if (addr != NULL) 443 { 444 addr -= BIT_VECTOR_HIDDEN_WORDS; 445 yasm_xfree((voidptr) addr); 446 } 447 } 448 449 void BitVector_Destroy_List(listptr list, N_int count) /* free list */ 450 { 451 listptr slot; 452 453 if (list != NULL) 454 { 455 slot = list; 456 while (count-- > 0) 457 { 458 BitVector_Destroy(*slot++); 459 } 460 free((voidptr) list); 461 } 462 } 463 464 wordptr BitVector_Create(N_int bits, boolean clear) /* malloc */ 465 { 466 N_word size; 467 N_word mask; 468 N_word bytes; 469 wordptr addr; 470 wordptr zero; 471 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); 476 if (addr != NULL) 477 { 478 *addr++ = bits; 479 *addr++ = size; 480 *addr++ = mask; 481 if (clear) 482 { 483 zero = addr; 484 BIT_VECTOR_ZERO_WORDS(zero,size) 485 } 486 } 487 return(addr); 488 } 489 490 listptr BitVector_Create_List(N_int bits, boolean clear, N_int count) 491 { 492 listptr list = NULL; 493 listptr slot; 494 wordptr addr; 495 N_int i; 496 497 if (count > 0) 498 { 499 list = (listptr) malloc(sizeof(wordptr) * count); 500 if (list != NULL) 501 { 502 slot = list; 503 for ( i = 0; i < count; i++ ) 504 { 505 addr = BitVector_Create(bits,clear); 506 if (addr == NULL) 507 { 508 BitVector_Destroy_List(list,i); 509 return(NULL); 510 } 511 *slot++ = addr; 512 } 513 } 514 } 515 return(list); 516 } 517 518 wordptr BitVector_Resize(wordptr oldaddr, N_int bits) /* realloc */ 519 { 520 N_word bytes; 521 N_word oldsize; 522 N_word oldmask; 523 N_word newsize; 524 N_word newmask; 525 wordptr newaddr; 526 wordptr source; 527 wordptr target; 528 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) 535 { 536 newaddr = oldaddr; 537 bits_(newaddr) = bits; 538 size_(newaddr) = newsize; 539 mask_(newaddr) = newmask; 540 if (newsize > 0) *(newaddr+newsize-1) &= newmask; 541 } 542 else 543 { 544 bytes = (newsize + BIT_VECTOR_HIDDEN_WORDS) << FACTOR; 545 newaddr = (wordptr) yasm_xmalloc((size_t) bytes); 546 if (newaddr != NULL) 547 { 548 *newaddr++ = bits; 549 *newaddr++ = newsize; 550 *newaddr++ = newmask; 551 target = newaddr; 552 source = oldaddr; 553 newsize -= oldsize; 554 BIT_VECTOR_COPY_WORDS(target,source,oldsize) 555 BIT_VECTOR_ZERO_WORDS(target,newsize) 556 } 557 BitVector_Destroy(oldaddr); 558 } 559 return(newaddr); 560 } 561 562 wordptr BitVector_Shadow(wordptr addr) /* makes new, same size but empty */ 563 { 564 return( BitVector_Create(bits_(addr),true) ); 565 } 566 567 wordptr BitVector_Clone(wordptr addr) /* makes exact duplicate */ 568 { 569 N_word bits; 570 wordptr twin; 571 572 bits = bits_(addr); 573 twin = BitVector_Create(bits,false); 574 if ((twin != NULL) and (bits > 0)) 575 BIT_VECTOR_cpy_words(twin,addr,size_(addr)); 576 return(twin); 577 } 578 579 wordptr BitVector_Concat(wordptr X, wordptr Y) /* returns concatenation */ 580 { 581 /* BEWARE that X = most significant part, Y = least significant part! */ 582 583 N_word bitsX; 584 N_word bitsY; 585 N_word bitsZ; 586 wordptr Z; 587 588 bitsX = bits_(X); 589 bitsY = bits_(Y); 590 bitsZ = bitsX + bitsY; 591 Z = BitVector_Create(bitsZ,false); 592 if ((Z != NULL) and (bitsZ > 0)) 593 { 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); 597 } 598 return(Z); 599 } 600 601 void BitVector_Copy(wordptr X, wordptr Y) /* X = Y */ 602 { 603 N_word sizeX = size_(X); 604 N_word sizeY = size_(Y); 605 N_word maskX = mask_(X); 606 N_word maskY = mask_(Y); 607 N_word fill = 0; 608 wordptr lastX; 609 wordptr lastY; 610 611 if ((X != Y) and (sizeX > 0)) 612 { 613 lastX = X + sizeX - 1; 614 if (sizeY > 0) 615 { 616 lastY = Y + sizeY - 1; 617 if ( (*lastY AND (maskY AND NOT (maskY >> 1))) == 0 ) *lastY &= maskY; 618 else 619 { 620 fill = (N_word) ~0L; 621 *lastY |= NOT maskY; 622 } 623 while ((sizeX > 0) and (sizeY > 0)) 624 { 625 *X++ = *Y++; 626 sizeX--; 627 sizeY--; 628 } 629 *lastY &= maskY; 630 } 631 while (sizeX-- > 0) *X++ = fill; 632 *lastX &= maskX; 633 } 634 } 635 636 void BitVector_Empty(wordptr addr) /* X = {} clr all */ 637 { 638 N_word size = size_(addr); 639 640 BIT_VECTOR_ZERO_WORDS(addr,size) 641 } 642 643 void BitVector_Fill(wordptr addr) /* X = ~{} set all */ 644 { 645 N_word size = size_(addr); 646 N_word mask = mask_(addr); 647 N_word fill = (N_word) ~0L; 648 649 if (size > 0) 650 { 651 BIT_VECTOR_FILL_WORDS(addr,fill,size) 652 *(--addr) &= mask; 653 } 654 } 655 656 void BitVector_Flip(wordptr addr) /* X = ~X flip all */ 657 { 658 N_word size = size_(addr); 659 N_word mask = mask_(addr); 660 N_word flip = (N_word) ~0L; 661 662 if (size > 0) 663 { 664 BIT_VECTOR_FLIP_WORDS(addr,flip,size) 665 *(--addr) &= mask; 666 } 667 } 668 669 void BitVector_Primes(wordptr addr) 670 { 671 N_word bits = bits_(addr); 672 N_word size = size_(addr); 673 wordptr work; 674 N_word temp; 675 N_word i,j; 676 677 if (size > 0) 678 { 679 temp = 0xAAAA; 680 i = BITS >> 4; 681 while (--i > 0) 682 { 683 temp <<= 16; 684 temp |= 0xAAAA; 685 } 686 i = size; 687 work = addr; 688 *work++ = temp XOR 0x0006; 689 while (--i > 0) *work++ = temp; 690 for ( i = 3; (j = i * i) < bits; i += 2 ) 691 { 692 for ( ; j < bits; j += i ) BIT_VECTOR_CLR_BIT(addr,j) 693 } 694 *(addr+size-1) &= mask_(addr); 695 } 696 } 697 698 void BitVector_Reverse(wordptr X, wordptr Y) 699 { 700 N_word bits = bits_(X); 701 N_word mask; 702 N_word bit; 703 N_word value; 704 705 if (bits > 0) 706 { 707 if (X == Y) BitVector_Interval_Reverse(X,0,bits-1); 708 else if (bits == bits_(Y)) 709 { 710 /* mask = mask_(Y); */ 711 /* mask &= NOT (mask >> 1); */ 712 mask = BITMASKTAB[(bits-1) AND MODMASK]; 713 Y += size_(Y) - 1; 714 value = 0; 715 bit = LSB; 716 while (bits-- > 0) 717 { 718 if ((*Y AND mask) != 0) 719 { 720 value |= bit; 721 } 722 if (not (mask >>= 1)) 723 { 724 Y--; 725 mask = MSB; 726 } 727 if (not (bit <<= 1)) 728 { 729 *X++ = value; 730 value = 0; 731 bit = LSB; 732 } 733 } 734 if (bit > LSB) *X = value; 735 } 736 } 737 } 738 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); 743 wordptr loaddr; 744 wordptr hiaddr; 745 N_word lobase; 746 N_word hibase; 747 N_word lomask; 748 N_word himask; 749 N_word diff; 750 751 if ((size > 0) and (lower < bits) and (upper < bits) and (lower <= upper)) 752 { 753 lobase = lower >> LOGBITS; 754 hibase = upper >> LOGBITS; 755 diff = hibase - lobase; 756 loaddr = addr + lobase; 757 hiaddr = addr + hibase; 758 759 lomask = (N_word) (~0L << (lower AND MODMASK)); 760 himask = (N_word) ~((~0L << (upper AND MODMASK)) << 1); 761 762 if (diff == 0) 763 { 764 *loaddr &= NOT (lomask AND himask); 765 } 766 else 767 { 768 *loaddr++ &= NOT lomask; 769 while (--diff > 0) 770 { 771 *loaddr++ = 0; 772 } 773 *hiaddr &= NOT himask; 774 } 775 } 776 } 777 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; 783 wordptr loaddr; 784 wordptr hiaddr; 785 N_word lobase; 786 N_word hibase; 787 N_word lomask; 788 N_word himask; 789 N_word diff; 790 791 if ((size > 0) and (lower < bits) and (upper < bits) and (lower <= upper)) 792 { 793 lobase = lower >> LOGBITS; 794 hibase = upper >> LOGBITS; 795 diff = hibase - lobase; 796 loaddr = addr + lobase; 797 hiaddr = addr + hibase; 798 799 lomask = (N_word) (~0L << (lower AND MODMASK)); 800 himask = (N_word) ~((~0L << (upper AND MODMASK)) << 1); 801 802 if (diff == 0) 803 { 804 *loaddr |= (lomask AND himask); 805 } 806 else 807 { 808 *loaddr++ |= lomask; 809 while (--diff > 0) 810 { 811 *loaddr++ = fill; 812 } 813 *hiaddr |= himask; 814 } 815 *(addr+size-1) &= mask_(addr); 816 } 817 } 818 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; 824 wordptr loaddr; 825 wordptr hiaddr; 826 N_word lobase; 827 N_word hibase; 828 N_word lomask; 829 N_word himask; 830 N_word diff; 831 832 if ((size > 0) and (lower < bits) and (upper < bits) and (lower <= upper)) 833 { 834 lobase = lower >> LOGBITS; 835 hibase = upper >> LOGBITS; 836 diff = hibase - lobase; 837 loaddr = addr + lobase; 838 hiaddr = addr + hibase; 839 840 lomask = (N_word) (~0L << (lower AND MODMASK)); 841 himask = (N_word) ~((~0L << (upper AND MODMASK)) << 1); 842 843 if (diff == 0) 844 { 845 *loaddr ^= (lomask AND himask); 846 } 847 else 848 { 849 *loaddr++ ^= lomask; 850 while (--diff > 0) 851 { 852 *loaddr++ ^= flip; 853 } 854 *hiaddr ^= himask; 855 } 856 *(addr+size-1) &= mask_(addr); 857 } 858 } 859 860 void BitVector_Interval_Reverse(wordptr addr, N_int lower, N_int upper) 861 { 862 N_word bits = bits_(addr); 863 wordptr loaddr; 864 wordptr hiaddr; 865 N_word lomask; 866 N_word himask; 867 868 if ((bits > 0) and (lower < bits) and (upper < bits) and (lower < upper)) 869 { 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 ) 875 { 876 if (((*loaddr AND lomask) != 0) XOR ((*hiaddr AND himask) != 0)) 877 { 878 *loaddr ^= lomask; /* swap bits only if they differ! */ 879 *hiaddr ^= himask; 880 } 881 if (not (lomask <<= 1)) 882 { 883 lomask = LSB; 884 loaddr++; 885 } 886 if (not (himask >>= 1)) 887 { 888 himask = MSB; 889 hiaddr--; 890 } 891 } 892 } 893 } 894 895 boolean BitVector_interval_scan_inc(wordptr addr, N_int start, 896 N_intptr min, N_intptr max) 897 { 898 N_word size = size_(addr); 899 N_word mask = mask_(addr); 900 N_word offset; 901 N_word bitmask; 902 N_word value; 903 boolean empty; 904 905 if ((size == 0) or (start >= bits_(addr))) return(FALSE); 906 907 *min = start; 908 *max = start; 909 910 offset = start >> LOGBITS; 911 912 *(addr+size-1) &= mask; 913 914 addr += offset; 915 size -= offset; 916 917 bitmask = BITMASKTAB[start AND MODMASK]; 918 mask = NOT (bitmask OR (bitmask - 1)); 919 920 value = *addr++; 921 if ((value AND bitmask) == 0) 922 { 923 value &= mask; 924 if (value == 0) 925 { 926 offset++; 927 empty = TRUE; 928 while (empty and (--size > 0)) 929 { 930 if ((value = *addr++)) empty = false; else offset++; 931 } 932 if (empty) return(FALSE); 933 } 934 start = offset << LOGBITS; 935 bitmask = LSB; 936 mask = value; 937 while (not (mask AND LSB)) 938 { 939 bitmask <<= 1; 940 mask >>= 1; 941 start++; 942 } 943 mask = NOT (bitmask OR (bitmask - 1)); 944 *min = start; 945 *max = start; 946 } 947 value = NOT value; 948 value &= mask; 949 if (value == 0) 950 { 951 offset++; 952 empty = TRUE; 953 while (empty and (--size > 0)) 954 { 955 if ((value = NOT *addr++)) empty = false; else offset++; 956 } 957 if (empty) value = LSB; 958 } 959 start = offset << LOGBITS; 960 while (not (value AND LSB)) 961 { 962 value >>= 1; 963 start++; 964 } 965 *max = --start; 966 return(TRUE); 967 } 968 969 boolean BitVector_interval_scan_dec(wordptr addr, N_int start, 970 N_intptr min, N_intptr max) 971 { 972 N_word size = size_(addr); 973 N_word mask = mask_(addr); 974 N_word offset; 975 N_word bitmask; 976 N_word value; 977 boolean empty; 978 979 if ((size == 0) or (start >= bits_(addr))) return(FALSE); 980 981 *min = start; 982 *max = start; 983 984 offset = start >> LOGBITS; 985 986 if (offset >= size) return(FALSE); 987 988 *(addr+size-1) &= mask; 989 990 addr += offset; 991 size = ++offset; 992 993 bitmask = BITMASKTAB[start AND MODMASK]; 994 mask = (bitmask - 1); 995 996 value = *addr--; 997 if ((value AND bitmask) == 0) 998 { 999 value &= mask; 1000 if (value == 0) 1001 { 1002 offset--; 1003 empty = TRUE; 1004 while (empty and (--size > 0)) 1005 { 1006 if ((value = *addr--)) empty = false; else offset--; 1007 } 1008 if (empty) return(FALSE); 1009 } 1010 start = offset << LOGBITS; 1011 bitmask = MSB; 1012 mask = value; 1013 while (not (mask AND MSB)) 1014 { 1015 bitmask >>= 1; 1016 mask <<= 1; 1017 start--; 1018 } 1019 mask = (bitmask - 1); 1020 *max = --start; 1021 *min = start; 1022 } 1023 value = NOT value; 1024 value &= mask; 1025 if (value == 0) 1026 { 1027 offset--; 1028 empty = TRUE; 1029 while (empty and (--size > 0)) 1030 { 1031 if ((value = NOT *addr--)) empty = false; else offset--; 1032 } 1033 if (empty) value = MSB; 1034 } 1035 start = offset << LOGBITS; 1036 while (not (value AND MSB)) 1037 { 1038 value <<= 1; 1039 start--; 1040 } 1041 *min = start; 1042 return(TRUE); 1043 } 1044 1045 void BitVector_Interval_Copy(wordptr X, wordptr Y, N_int Xoffset, 1046 N_int Yoffset, N_int length) 1047 { 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 */ 1052 N_word s_lo_base; 1053 N_word s_hi_base; 1054 N_word s_lo_bit; 1055 N_word s_hi_bit; 1056 N_word s_base; 1057 N_word s_lower = 0; /* silence compiler warning */ 1058 N_word s_upper = 0; /* silence compiler warning */ 1059 N_word s_bits; 1060 N_word s_min; 1061 N_word s_max; 1062 N_word t_lo_base; 1063 N_word t_hi_base; 1064 N_word t_lo_bit; 1065 N_word t_hi_bit; 1066 N_word t_base; 1067 N_word t_lower = 0; /* silence compiler warning */ 1068 N_word t_upper = 0; /* silence compiler warning */ 1069 N_word t_bits; 1070 N_word t_min; 1071 N_word mask; 1072 N_word bits; 1073 N_word sel; 1074 boolean ascending; 1075 boolean notfirst; 1076 wordptr Z = X; 1077 1078 if ((length > 0) and (Xoffset < bitsX) and (Yoffset < bitsY)) 1079 { 1080 if ((Xoffset + length) > bitsX) length = bitsX - Xoffset; 1081 if ((Yoffset + length) > bitsY) length = bitsY - Yoffset; 1082 1083 ascending = (Xoffset <= Yoffset); 1084 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; 1090 1091 t_lo_base = Xoffset >> LOGBITS; 1092 t_lo_bit = Xoffset AND MODMASK; 1093 Xoffset += length; 1094 t_hi_base = Xoffset >> LOGBITS; 1095 t_hi_bit = Xoffset AND MODMASK; 1096 1097 if (ascending) 1098 { 1099 s_base = s_lo_base; 1100 t_base = t_lo_base; 1101 } 1102 else 1103 { 1104 s_base = s_hi_base; 1105 t_base = t_hi_base; 1106 } 1107 s_bits = 0; 1108 t_bits = 0; 1109 Y += s_base; 1110 X += t_base; 1111 notfirst = FALSE; 1112 while (TRUE) 1113 { 1114 if (t_bits == 0) 1115 { 1116 if (notfirst) 1117 { 1118 *X = target; 1119 if (ascending) 1120 { 1121 if (t_base == t_hi_base) break; 1122 t_base++; 1123 X++; 1124 } 1125 else 1126 { 1127 if (t_base == t_lo_base) break; 1128 t_base--; 1129 X--; 1130 } 1131 } 1132 sel = ((t_base == t_hi_base) << 1) OR (t_base == t_lo_base); 1133 switch (sel) 1134 { 1135 case 0: 1136 t_lower = 0; 1137 t_upper = BITS - 1; 1138 t_bits = BITS; 1139 target = 0; 1140 break; 1141 case 1: 1142 t_lower = t_lo_bit; 1143 t_upper = BITS - 1; 1144 t_bits = BITS - t_lo_bit; 1145 mask = (N_word) (~0L << t_lower); 1146 target = *X AND NOT mask; 1147 break; 1148 case 2: 1149 t_lower = 0; 1150 t_upper = t_hi_bit; 1151 t_bits = t_hi_bit + 1; 1152 mask = (N_word) ((~0L << t_upper) << 1); 1153 target = *X AND mask; 1154 break; 1155 case 3: 1156 t_lower = t_lo_bit; 1157 t_upper = t_hi_bit; 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; 1162 break; 1163 } 1164 } 1165 if (s_bits == 0) 1166 { 1167 if (notfirst) 1168 { 1169 if (ascending) 1170 { 1171 if (s_base == s_hi_base) break; 1172 s_base++; 1173 Y++; 1174 } 1175 else 1176 { 1177 if (s_base == s_lo_base) break; 1178 s_base--; 1179 Y--; 1180 } 1181 } 1182 source = *Y; 1183 sel = ((s_base == s_hi_base) << 1) OR (s_base == s_lo_base); 1184 switch (sel) 1185 { 1186 case 0: 1187 s_lower = 0; 1188 s_upper = BITS - 1; 1189 s_bits = BITS; 1190 break; 1191 case 1: 1192 s_lower = s_lo_bit; 1193 s_upper = BITS - 1; 1194 s_bits = BITS - s_lo_bit; 1195 break; 1196 case 2: 1197 s_lower = 0; 1198 s_upper = s_hi_bit; 1199 s_bits = s_hi_bit + 1; 1200 break; 1201 case 3: 1202 s_lower = s_lo_bit; 1203 s_upper = s_hi_bit; 1204 s_bits = s_hi_bit - s_lo_bit + 1; 1205 break; 1206 } 1207 } 1208 notfirst = TRUE; 1209 if (s_bits > t_bits) 1210 { 1211 bits = t_bits - 1; 1212 if (ascending) 1213 { 1214 s_min = s_lower; 1215 s_max = s_lower + bits; 1216 } 1217 else 1218 { 1219 s_max = s_upper; 1220 s_min = s_upper - bits; 1221 } 1222 t_min = t_lower; 1223 } 1224 else 1225 { 1226 bits = s_bits - 1; 1227 if (ascending) t_min = t_lower; 1228 else t_min = t_upper - bits; 1229 s_min = s_lower; 1230 s_max = s_upper; 1231 } 1232 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); 1236 else 1237 { 1238 if (s_min < t_min) target |= (source AND mask) << (t_min-s_min); 1239 else target |= (source AND mask) >> (s_min-t_min); 1240 } 1241 if (ascending) 1242 { 1243 s_lower += bits; 1244 t_lower += bits; 1245 } 1246 else 1247 { 1248 s_upper -= bits; 1249 t_upper -= bits; 1250 } 1251 s_bits -= bits; 1252 t_bits -= bits; 1253 } 1254 *(Z+size_(Z)-1) &= mask_(Z); 1255 } 1256 } 1257 1258 1259 wordptr BitVector_Interval_Substitute(wordptr X, wordptr Y, 1260 N_int Xoffset, N_int Xlength, 1261 N_int Yoffset, N_int Ylength) 1262 { 1263 N_word Xbits = bits_(X); 1264 N_word Ybits = bits_(Y); 1265 N_word limit; 1266 N_word diff; 1267 1268 if ((Xoffset <= Xbits) and (Yoffset <= Ybits)) 1269 { 1270 limit = Xoffset + Xlength; 1271 if (limit > Xbits) 1272 { 1273 limit = Xbits; 1274 Xlength = Xbits - Xoffset; 1275 } 1276 if ((Yoffset + Ylength) > Ybits) 1277 { 1278 Ylength = Ybits - Yoffset; 1279 } 1280 if (Xlength == Ylength) 1281 { 1282 if ((Ylength > 0) and ((X != Y) or (Xoffset != Yoffset))) 1283 { 1284 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength); 1285 } 1286 } 1287 else /* Xlength != Ylength */ 1288 { 1289 if (Xlength > Ylength) 1290 { 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); 1295 } 1296 else /* Ylength > Xlength ==> Ylength > 0 */ 1297 { 1298 diff = Ylength - Xlength; 1299 if (X != Y) 1300 { 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); 1304 } 1305 else /* in-place */ 1306 { 1307 if ((Y = X = BitVector_Resize(X,Xbits+diff)) == NULL) return(NULL); 1308 if (limit >= Xbits) 1309 { 1310 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength); 1311 } 1312 else /* limit < Xbits */ 1313 { 1314 BitVector_Insert(X,limit,diff,FALSE); 1315 if ((Yoffset+Ylength) <= limit) 1316 { 1317 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength); 1318 } 1319 else /* overlaps or lies above critical area */ 1320 { 1321 if (limit <= Yoffset) 1322 { 1323 Yoffset += diff; 1324 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength); 1325 } 1326 else /* Yoffset < limit */ 1327 { 1328 Xlength = limit - Yoffset; 1329 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Xlength); 1330 Yoffset = Xoffset + Ylength; /* = limit + diff */ 1331 Xoffset += Xlength; 1332 Ylength -= Xlength; 1333 BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength); 1334 } 1335 } 1336 } 1337 } 1338 } 1339 } 1340 } 1341 return(X); 1342 } 1343 1344 boolean BitVector_is_empty(wordptr addr) /* X == {} ? */ 1345 { 1346 N_word size = size_(addr); 1347 boolean r = TRUE; 1348 1349 if (size > 0) 1350 { 1351 *(addr+size-1) &= mask_(addr); 1352 while (r and (size-- > 0)) r = ( *addr++ == 0 ); 1353 } 1354 return(r); 1355 } 1356 1357 boolean BitVector_is_full(wordptr addr) /* X == ~{} ? */ 1358 { 1359 N_word size = size_(addr); 1360 N_word mask = mask_(addr); 1361 boolean r = FALSE; 1362 wordptr last; 1363 1364 if (size > 0) 1365 { 1366 r = TRUE; 1367 last = addr + size - 1; 1368 *last |= NOT mask; 1369 while (r and (size-- > 0)) r = ( NOT *addr++ == 0 ); 1370 *last &= mask; 1371 } 1372 return(r); 1373 } 1374 1375 boolean BitVector_equal(wordptr X, wordptr Y) /* X == Y ? */ 1376 { 1377 N_word size = size_(X); 1378 N_word mask = mask_(X); 1379 boolean r = FALSE; 1380 1381 if (bits_(X) == bits_(Y)) 1382 { 1383 r = TRUE; 1384 if (size > 0) 1385 { 1386 *(X+size-1) &= mask; 1387 *(Y+size-1) &= mask; 1388 while (r and (size-- > 0)) r = (*X++ == *Y++); 1389 } 1390 } 1391 return(r); 1392 } 1393 1394 Z_int BitVector_Lexicompare(wordptr X, wordptr Y) /* X <,=,> Y ? */ 1395 { /* unsigned */ 1396 N_word bitsX = bits_(X); 1397 N_word bitsY = bits_(Y); 1398 N_word size = size_(X); 1399 boolean r = TRUE; 1400 1401 if (bitsX == bitsY) 1402 { 1403 if (size > 0) 1404 { 1405 X += size; 1406 Y += size; 1407 while (r and (size-- > 0)) r = (*(--X) == *(--Y)); 1408 } 1409 if (r) return((Z_int) 0); 1410 else 1411 { 1412 if (*X < *Y) return((Z_int) -1); else return((Z_int) 1); 1413 } 1414 } 1415 else 1416 { 1417 if (bitsX < bitsY) return((Z_int) -1); else return((Z_int) 1); 1418 } 1419 } 1420 1421 Z_int BitVector_Compare(wordptr X, wordptr Y) /* X <,=,> Y ? */ 1422 { /* signed */ 1423 N_word bitsX = bits_(X); 1424 N_word bitsY = bits_(Y); 1425 N_word size = size_(X); 1426 N_word mask = mask_(X); 1427 N_word sign; 1428 boolean r = TRUE; 1429 1430 if (bitsX == bitsY) 1431 { 1432 if (size > 0) 1433 { 1434 X += size; 1435 Y += size; 1436 mask &= NOT (mask >> 1); 1437 if ((sign = (*(X-1) AND mask)) != (*(Y-1) AND mask)) 1438 { 1439 if (sign) return((Z_int) -1); else return((Z_int) 1); 1440 } 1441 while (r and (size-- > 0)) r = (*(--X) == *(--Y)); 1442 } 1443 if (r) return((Z_int) 0); 1444 else 1445 { 1446 if (*X < *Y) return((Z_int) -1); else return((Z_int) 1); 1447 } 1448 } 1449 else 1450 { 1451 if (bitsX < bitsY) return((Z_int) -1); else return((Z_int) 1); 1452 } 1453 } 1454 1455 charptr BitVector_to_Hex(wordptr addr) 1456 { 1457 N_word bits = bits_(addr); 1458 N_word size = size_(addr); 1459 N_word value; 1460 N_word count; 1461 N_word digit; 1462 N_word length; 1463 charptr string; 1464 1465 length = bits >> 2; 1466 if (bits AND 0x0003) length++; 1467 string = (charptr) yasm_xmalloc((size_t) (length+1)); 1468 if (string == NULL) return(NULL); 1469 string += length; 1470 *string = (N_char) '\0'; 1471 if (size > 0) 1472 { 1473 *(addr+size-1) &= mask_(addr); 1474 while ((size-- > 0) and (length > 0)) 1475 { 1476 value = *addr++; 1477 count = BITS >> 2; 1478 while ((count-- > 0) and (length > 0)) 1479 { 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; 1485 } 1486 } 1487 } 1488 return(string); 1489 } 1490 1491 ErrCode BitVector_from_Hex(wordptr addr, charptr string) 1492 { 1493 N_word size = size_(addr); 1494 N_word mask = mask_(addr); 1495 boolean ok = TRUE; 1496 size_t length; 1497 N_word value; 1498 N_word count; 1499 int digit; 1500 1501 if (size > 0) 1502 { 1503 length = strlen((char *) string); 1504 string += length; 1505 while (size-- > 0) 1506 { 1507 value = 0; 1508 for ( count = 0; (ok and (length > 0) and (count < BITS)); count += 4 ) 1509 { 1510 digit = (int) *(--string); length--; 1511 /* separate because toupper() is likely a macro! */ 1512 digit = toupper(digit); 1513 if (digit == '_') 1514 count -= 4; 1515 else if ((ok = (isxdigit(digit) != 0))) 1516 { 1517 if (digit >= (int) 'A') digit -= (int) 'A' - 10; 1518 else digit -= (int) '0'; 1519 value |= (((N_word) digit) << count); 1520 } 1521 } 1522 *addr++ = value; 1523 } 1524 *(--addr) &= mask; 1525 } 1526 if (ok) return(ErrCode_Ok); 1527 else return(ErrCode_Pars); 1528 } 1529 1530 ErrCode BitVector_from_Oct(wordptr addr, charptr string) 1531 { 1532 N_word size = size_(addr); 1533 N_word mask = mask_(addr); 1534 boolean ok = TRUE; 1535 size_t length; 1536 N_word value; 1537 N_word value_fill = 0; 1538 N_word count; 1539 Z_word count_fill = 0; 1540 int digit = 0; 1541 1542 if (size > 0) 1543 { 1544 length = strlen((char *) string); 1545 string += length; 1546 while (size-- > 0) 1547 { 1548 value = value_fill; 1549 for ( count = count_fill; (ok and (length > 0) and (count < BITS)); count += 3 ) 1550 { 1551 digit = (int) *(--string); length--; 1552 if (digit == '_') 1553 count -= 3; 1554 else if ((ok = (isdigit(digit) && digit != '8' && digit != '9')) != 0) 1555 { 1556 digit -= (int) '0'; 1557 value |= (((N_word) digit) << count); 1558 } 1559 } 1560 count_fill = (Z_word)count-(Z_word)BITS; 1561 if (count_fill > 0) 1562 value_fill = (((N_word) digit) >> (3-count_fill)); 1563 else 1564 value_fill = 0; 1565 *addr++ = value; 1566 } 1567 *(--addr) &= mask; 1568 } 1569 if (ok) return(ErrCode_Ok); 1570 else return(ErrCode_Pars); 1571 } 1572 1573 charptr BitVector_to_Bin(wordptr addr) 1574 { 1575 N_word size = size_(addr); 1576 N_word value; 1577 N_word count; 1578 N_word digit; 1579 N_word length; 1580 charptr string; 1581 1582 length = bits_(addr); 1583 string = (charptr) yasm_xmalloc((size_t) (length+1)); 1584 if (string == NULL) return(NULL); 1585 string += length; 1586 *string = (N_char) '\0'; 1587 if (size > 0) 1588 { 1589 *(addr+size-1) &= mask_(addr); 1590 while (size-- > 0) 1591 { 1592 value = *addr++; 1593 count = BITS; 1594 if (count > length) count = length; 1595 while (count-- > 0) 1596 { 1597 digit = value AND 0x0001; 1598 digit += (N_word) '0'; 1599 *(--string) = (N_char) digit; length--; 1600 if (count > 0) value >>= 1; 1601 } 1602 } 1603 } 1604 return(string); 1605 } 1606 1607 ErrCode BitVector_from_Bin(wordptr addr, charptr string) 1608 { 1609 N_word size = size_(addr); 1610 N_word mask = mask_(addr); 1611 boolean ok = TRUE; 1612 size_t length; 1613 N_word value; 1614 N_word count; 1615 int digit; 1616 1617 if (size > 0) 1618 { 1619 length = strlen((char *) string); 1620 string += length; 1621 while (size-- > 0) 1622 { 1623 value = 0; 1624 for ( count = 0; (ok and (length > 0) and (count < BITS)); count++ ) 1625 { 1626 digit = (int) *(--string); length--; 1627 switch (digit) 1628 { 1629 case (int) '0': 1630 break; 1631 case (int) '1': 1632 value |= BITMASKTAB[count]; 1633 break; 1634 case (int) '_': 1635 count--; 1636 break; 1637 default: 1638 ok = FALSE; 1639 break; 1640 } 1641 } 1642 *addr++ = value; 1643 } 1644 *(--addr) &= mask; 1645 } 1646 if (ok) return(ErrCode_Ok); 1647 else return(ErrCode_Pars); 1648 } 1649 1650 charptr BitVector_to_Dec(wordptr addr) 1651 { 1652 N_word bits = bits_(addr); 1653 N_word length; 1654 N_word digits; 1655 N_word count; 1656 N_word q; 1657 N_word r; 1658 boolean loop; 1659 charptr result; 1660 charptr string; 1661 wordptr quot; 1662 wordptr rest; 1663 wordptr temp; 1664 wordptr base; 1665 Z_int sign; 1666 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); 1671 string = result; 1672 sign = BitVector_Sign(addr); 1673 if ((bits < 4) or (sign == 0)) 1674 { 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'; 1678 digits = 1; 1679 } 1680 else 1681 { 1682 quot = BitVector_Create(bits,FALSE); 1683 if (quot == NULL) 1684 { 1685 BitVector_Dispose(result); 1686 return(NULL); 1687 } 1688 rest = BitVector_Create(bits,FALSE); 1689 if (rest == NULL) 1690 { 1691 BitVector_Dispose(result); 1692 BitVector_Destroy(quot); 1693 return(NULL); 1694 } 1695 temp = BitVector_Create(bits,FALSE); 1696 if (temp == NULL) 1697 { 1698 BitVector_Dispose(result); 1699 BitVector_Destroy(quot); 1700 BitVector_Destroy(rest); 1701 return(NULL); 1702 } 1703 base = BitVector_Create(bits,TRUE); 1704 if (base == NULL) 1705 { 1706 BitVector_Dispose(result); 1707 BitVector_Destroy(quot); 1708 BitVector_Destroy(rest); 1709 BitVector_Destroy(temp); 1710 return(NULL); 1711 } 1712 if (sign < 0) BitVector_Negate(quot,addr); 1713 else BitVector_Copy(quot,addr); 1714 digits = 0; 1715 *base = EXP10; 1716 loop = (bits >= BITS); 1717 do 1718 { 1719 if (loop) 1720 { 1721 BitVector_Copy(temp,quot); 1722 if (BitVector_Div_Pos(quot,temp,base,rest)) 1723 { 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); 1729 return(NULL); 1730 } 1731 loop = not BitVector_is_empty(quot); 1732 q = *rest; 1733 } 1734 else q = *quot; 1735 count = LOG10; 1736 while (((loop and (count-- > 0)) or ((not loop) and (q != 0))) and 1737 (digits < length)) 1738 { 1739 if (q != 0) 1740 { 1741 BIT_VECTOR_DIGITIZE(N_word,q,r) 1742 } 1743 else r = (N_word) '0'; 1744 *string++ = (N_char) r; 1745 digits++; 1746 } 1747 } 1748 while (loop and (digits < length)); 1749 BitVector_Destroy(quot); 1750 BitVector_Destroy(rest); 1751 BitVector_Destroy(temp); 1752 BitVector_Destroy(base); 1753 } 1754 if ((sign < 0) and (digits < length)) 1755 { 1756 *string++ = (N_char) '-'; 1757 digits++; 1758 } 1759 *string = (N_char) '\0'; 1760 BIT_VECTOR_reverse(result,digits); 1761 return(result); 1762 } 1763 1764 struct BitVector_from_Dec_static_data { 1765 wordptr term; 1766 wordptr base; 1767 wordptr prod; 1768 wordptr rank; 1769 wordptr temp; 1770 }; 1771 1772 BitVector_from_Dec_static_data *BitVector_from_Dec_static_Boot(N_word bits) 1773 { 1774 BitVector_from_Dec_static_data *data; 1775 1776 data = yasm_xmalloc(sizeof(BitVector_from_Dec_static_data)); 1777 1778 if (bits > 0) 1779 { 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); 1785 } else { 1786 data->term = NULL; 1787 data->base = NULL; 1788 data->prod = NULL; 1789 data->rank = NULL; 1790 data->temp = NULL; 1791 } 1792 return data; 1793 } 1794 1795 void BitVector_from_Dec_static_Shutdown(BitVector_from_Dec_static_data *data) 1796 { 1797 if (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); 1803 } 1804 yasm_xfree(data); 1805 } 1806 1807 ErrCode BitVector_from_Dec_static(BitVector_from_Dec_static_data *data, 1808 wordptr addr, charptr string) 1809 { 1810 ErrCode error = ErrCode_Ok; 1811 N_word bits = bits_(addr); 1812 N_word mask = mask_(addr); 1813 boolean init = (bits > BITS); 1814 boolean minus; 1815 boolean shift; 1816 boolean carry; 1817 wordptr term; 1818 wordptr base; 1819 wordptr prod; 1820 wordptr rank; 1821 wordptr temp; 1822 N_word accu; 1823 N_word powr; 1824 N_word count; 1825 size_t length; 1826 int digit; 1827 1828 if (bits > 0) 1829 { 1830 term = data->term; 1831 base = data->base; 1832 prod = data->prod; 1833 rank = data->rank; 1834 temp = data->temp; 1835 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) '+')) 1841 { 1842 string++; 1843 if (--length == 0) return(ErrCode_Pars); 1844 } 1845 string += length; 1846 if (init) 1847 { 1848 BitVector_Empty(prod); 1849 BitVector_Empty(rank); 1850 } 1851 BitVector_Empty(addr); 1852 *base = EXP10; 1853 shift = FALSE; 1854 while ((not error) and (length > 0)) 1855 { 1856 accu = 0; 1857 powr = 1; 1858 count = LOG10; 1859 while ((not error) and (length > 0) and (count-- > 0)) 1860 { 1861 digit = (int) *(--string); length--; 1862 /* separate because isdigit() is likely a macro! */ 1863 if (isdigit(digit) != 0) 1864 { 1865 accu += ((N_word) digit - (N_word) '0') * powr; 1866 powr *= 10; 1867 } 1868 else error = ErrCode_Pars; 1869 } 1870 if (not error) 1871 { 1872 if (shift) 1873 { 1874 *term = accu; 1875 BitVector_Copy(temp,rank); 1876 error = BitVector_Mul_Pos(prod,temp,term,FALSE); 1877 } 1878 else 1879 { 1880 *prod = accu; 1881 if ((not init) and ((accu AND NOT mask) != 0)) error = ErrCode_Ovfl; 1882 } 1883 if (not error) 1884 { 1885 carry = FALSE; 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; 1890 else 1891 { 1892 if (length > 0) 1893 { 1894 if (shift) 1895 { 1896 BitVector_Copy(temp,rank); 1897 error = BitVector_Mul_Pos(rank,temp,base,FALSE); 1898 } 1899 else 1900 { 1901 *rank = *base; 1902 shift = TRUE; 1903 } 1904 } 1905 } 1906 } 1907 } 1908 } 1909 if (not error and minus) 1910 { 1911 BitVector_Negate(addr,addr); 1912 if ((*(addr + size_(addr) - 1) AND mask AND NOT (mask >> 1)) == 0) 1913 error = ErrCode_Ovfl; 1914 } 1915 } 1916 return(error); 1917 } 1918 1919 ErrCode BitVector_from_Dec(wordptr addr, charptr string) 1920 { 1921 ErrCode error = ErrCode_Ok; 1922 N_word bits = bits_(addr); 1923 N_word mask = mask_(addr); 1924 boolean init = (bits > BITS); 1925 boolean minus; 1926 boolean shift; 1927 boolean carry; 1928 wordptr term; 1929 wordptr base; 1930 wordptr prod; 1931 wordptr rank; 1932 wordptr temp; 1933 N_word accu; 1934 N_word powr; 1935 N_word count; 1936 size_t length; 1937 int digit; 1938 1939 if (bits > 0) 1940 { 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) '+')) 1946 { 1947 string++; 1948 if (--length == 0) return(ErrCode_Pars); 1949 } 1950 string += length; 1951 term = BitVector_Create(BITS,FALSE); 1952 if (term == NULL) 1953 { 1954 return(ErrCode_Null); 1955 } 1956 base = BitVector_Create(BITS,FALSE); 1957 if (base == NULL) 1958 { 1959 BitVector_Destroy(term); 1960 return(ErrCode_Null); 1961 } 1962 prod = BitVector_Create(bits,init); 1963 if (prod == NULL) 1964 { 1965 BitVector_Destroy(term); 1966 BitVector_Destroy(base); 1967 return(ErrCode_Null); 1968 } 1969 rank = BitVector_Create(bits,init); 1970 if (rank == NULL) 1971 { 1972 BitVector_Destroy(term); 1973 BitVector_Destroy(base); 1974 BitVector_Destroy(prod); 1975 return(ErrCode_Null); 1976 } 1977 temp = BitVector_Create(bits,FALSE); 1978 if (temp == NULL) 1979 { 1980 BitVector_Destroy(term); 1981 BitVector_Destroy(base); 1982 BitVector_Destroy(prod); 1983 BitVector_Destroy(rank); 1984 return(ErrCode_Null); 1985 } 1986 BitVector_Empty(addr); 1987 *base = EXP10; 1988 shift = FALSE; 1989 while ((not error) and (length > 0)) 1990 { 1991 accu = 0; 1992 powr = 1; 1993 count = LOG10; 1994 while ((not error) and (length > 0) and (count-- > 0)) 1995 { 1996 digit = (int) *(--string); length--; 1997 /* separate because isdigit() is likely a macro! */ 1998 if (isdigit(digit) != 0) 1999 { 2000 accu += ((N_word) digit - (N_word) '0') * powr; 2001 powr *= 10; 2002 } 2003 else error = ErrCode_Pars; 2004 } 2005 if (not error) 2006 { 2007 if (shift) 2008 { 2009 *term = accu; 2010 BitVector_Copy(temp,rank); 2011 error = BitVector_Mul_Pos(prod,temp,term,FALSE); 2012 } 2013 else 2014 { 2015 *prod = accu; 2016 if ((not init) and ((accu AND NOT mask) != 0)) error = ErrCode_Ovfl; 2017 } 2018 if (not error) 2019 { 2020 carry = FALSE; 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; 2025 else 2026 { 2027 if (length > 0) 2028 { 2029 if (shift) 2030 { 2031 BitVector_Copy(temp,rank); 2032 error = BitVector_Mul_Pos(rank,temp,base,FALSE); 2033 } 2034 else 2035 { 2036 *rank = *base; 2037 shift = TRUE; 2038 } 2039 } 2040 } 2041 } 2042 } 2043 } 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) 2050 { 2051 BitVector_Negate(addr,addr); 2052 if ((*(addr + size_(addr) - 1) AND mask AND NOT (mask >> 1)) == 0) 2053 error = ErrCode_Ovfl; 2054 } 2055 } 2056 return(error); 2057 } 2058 2059 charptr BitVector_to_Enum(wordptr addr) 2060 { 2061 N_word bits = bits_(addr); 2062 N_word sample; 2063 N_word length; 2064 N_word digits; 2065 N_word factor; 2066 N_word power; 2067 N_word start; 2068 N_word min; 2069 N_word max; 2070 charptr string; 2071 charptr target; 2072 boolean comma; 2073 2074 if (bits > 0) 2075 { 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 */ 2079 factor = 1; 2080 power = 10; 2081 while (sample >= (power-1)) 2082 { 2083 length += ++digits * factor * 6; /* 9,90,900,9000,... (9*2/3 = 6) */ 2084 factor = power; 2085 power *= 10; 2086 } 2087 if (sample > --factor) 2088 { 2089 sample -= factor; 2090 factor = (N_word) ( sample / 3 ); 2091 factor = (factor << 1) + (sample - (factor * 3)); 2092 length += ++digits * factor; 2093 } 2094 } 2095 else length = 1; 2096 string = (charptr) yasm_xmalloc((size_t) length); 2097 if (string == NULL) return(NULL); 2098 start = 0; 2099 comma = FALSE; 2100 target = string; 2101 while ((start < bits) and BitVector_interval_scan_inc(addr,start,&min,&max)) 2102 { 2103 start = max + 2; 2104 if (comma) *target++ = (N_char) ','; 2105 if (min == max) 2106 { 2107 target += BIT_VECTOR_int2str(target,min); 2108 } 2109 else 2110 { 2111 if (min+1 == max) 2112 { 2113 target += BIT_VECTOR_int2str(target,min); 2114 *target++ = (N_char) ','; 2115 target += BIT_VECTOR_int2str(target,max); 2116 } 2117 else 2118 { 2119 target += BIT_VECTOR_int2str(target,min); 2120 *target++ = (N_char) '-'; 2121 target += BIT_VECTOR_int2str(target,max); 2122 } 2123 } 2124 comma = TRUE; 2125 } 2126 *target = (N_char) '\0'; 2127 return(string); 2128 } 2129 2130 ErrCode BitVector_from_Enum(wordptr addr, charptr string) 2131 { 2132 ErrCode error = ErrCode_Ok; 2133 N_word bits = bits_(addr); 2134 N_word state = 1; 2135 N_word token; 2136 N_word indx = 0; /* silence compiler warning */ 2137 N_word start = 0; /* silence compiler warning */ 2138 2139 if (bits > 0) 2140 { 2141 BitVector_Empty(addr); 2142 while ((not error) and (state != 0)) 2143 { 2144 token = (N_word) *string; 2145 /* separate because isdigit() is likely a macro! */ 2146 if (isdigit((int)token) != 0) 2147 { 2148 string += BIT_VECTOR_str2int(string,&indx); 2149 if (indx < bits) token = (N_word) '0'; 2150 else error = ErrCode_Indx; 2151 } 2152 else string++; 2153 if (not error) 2154 switch (state) 2155 { 2156 case 1: 2157 switch (token) 2158 { 2159 case (N_word) '0': 2160 state = 2; 2161 break; 2162 case (N_word) '\0': 2163 state = 0; 2164 break; 2165 default: 2166 error = ErrCode_Pars; 2167 break; 2168 } 2169 break; 2170 case 2: 2171 switch (token) 2172 { 2173 case (N_word) '-': 2174 start = indx; 2175 state = 3; 2176 break; 2177 case (N_word) ',': 2178 BIT_VECTOR_SET_BIT(addr,indx) 2179 state = 5; 2180 break; 2181 case (N_word) '\0': 2182 BIT_VECTOR_SET_BIT(addr,indx) 2183 state = 0; 2184 break; 2185 default: 2186 error = ErrCode_Pars; 2187 break; 2188 } 2189 break; 2190 case 3: 2191 switch (token) 2192 { 2193 case (N_word) '0': 2194 if (start < indx) 2195 BitVector_Interval_Fill(addr,start,indx); 2196 else if (start == indx) 2197 BIT_VECTOR_SET_BIT(addr,indx) 2198 else error = ErrCode_Ordr; 2199 state = 4; 2200 break; 2201 default: 2202 error = ErrCode_Pars; 2203 break; 2204 } 2205 break; 2206 case 4: 2207 switch (token) 2208 { 2209 case (N_word) ',': 2210 state = 5; 2211 break; 2212 case (N_word) '\0': 2213 state = 0; 2214 break; 2215 default: 2216 error = ErrCode_Pars; 2217 break; 2218 } 2219 break; 2220 case 5: 2221 switch (token) 2222 { 2223 case (N_word) '0': 2224 state = 2; 2225 break; 2226 default: 2227 error = ErrCode_Pars; 2228 break; 2229 } 2230 break; 2231 } 2232 } 2233 } 2234 return(error); 2235 } 2236 2237 void BitVector_Bit_Off(wordptr addr, N_int indx) /* X = X \ {x} */ 2238 { 2239 if (indx < bits_(addr)) BIT_VECTOR_CLR_BIT(addr,indx) 2240 } 2241 2242 void BitVector_Bit_On(wordptr addr, N_int indx) /* X = X + {x} */ 2243 { 2244 if (indx < bits_(addr)) BIT_VECTOR_SET_BIT(addr,indx) 2245 } 2246 2247 boolean BitVector_bit_flip(wordptr addr, N_int indx) /* X=(X+{x})\(X*{x}) */ 2248 { 2249 N_word mask; 2250 2251 if (indx < bits_(addr)) return( BIT_VECTOR_FLP_BIT(addr,indx,mask) ); 2252 else return( FALSE ); 2253 } 2254 2255 boolean BitVector_bit_test(wordptr addr, N_int indx) /* {x} in X ? */ 2256 { 2257 if (indx < bits_(addr)) return( BIT_VECTOR_TST_BIT(addr,indx) ); 2258 else return( FALSE ); 2259 } 2260 2261 void BitVector_Bit_Copy(wordptr addr, N_int indx, boolean bit) 2262 { 2263 if (indx < bits_(addr)) 2264 { 2265 if (bit) BIT_VECTOR_SET_BIT(addr,indx) 2266 else BIT_VECTOR_CLR_BIT(addr,indx) 2267 } 2268 } 2269 2270 void BitVector_LSB(wordptr addr, boolean bit) 2271 { 2272 if (bits_(addr) > 0) 2273 { 2274 if (bit) *addr |= LSB; 2275 else *addr &= NOT LSB; 2276 } 2277 } 2278 2279 void BitVector_MSB(wordptr addr, boolean bit) 2280 { 2281 N_word size = size_(addr); 2282 N_word mask = mask_(addr); 2283 2284 if (size-- > 0) 2285 { 2286 if (bit) *(addr+size) |= mask AND NOT (mask >> 1); 2287 else *(addr+size) &= NOT mask OR (mask >> 1); 2288 } 2289 } 2290 2291 boolean BitVector_lsb_(wordptr addr) 2292 { 2293 if (size_(addr) > 0) return( (*addr AND LSB) != 0 ); 2294 else return( FALSE ); 2295 } 2296 2297 boolean BitVector_msb_(wordptr addr) 2298 { 2299 N_word size = size_(addr); 2300 N_word mask = mask_(addr); 2301 2302 if (size-- > 0) 2303 return( (*(addr+size) AND (mask AND NOT (mask >> 1))) != 0 ); 2304 else 2305 return( FALSE ); 2306 } 2307 2308 boolean BitVector_rotate_left(wordptr addr) 2309 { 2310 N_word size = size_(addr); 2311 N_word mask = mask_(addr); 2312 N_word msb; 2313 boolean carry_in; 2314 boolean carry_out = FALSE; 2315 2316 if (size > 0) 2317 { 2318 msb = mask AND NOT (mask >> 1); 2319 carry_in = ((*(addr+size-1) AND msb) != 0); 2320 while (size-- > 1) 2321 { 2322 carry_out = ((*addr AND MSB) != 0); 2323 *addr <<= 1; 2324 if (carry_in) *addr |= LSB; 2325 carry_in = carry_out; 2326 addr++; 2327 } 2328 carry_out = ((*addr AND msb) != 0); 2329 *addr <<= 1; 2330 if (carry_in) *addr |= LSB; 2331 *addr &= mask; 2332 } 2333 return(carry_out); 2334 } 2335 2336 boolean BitVector_rotate_right(wordptr addr) 2337 { 2338 N_word size = size_(addr); 2339 N_word mask = mask_(addr); 2340 N_word msb; 2341 boolean carry_in; 2342 boolean carry_out = FALSE; 2343 2344 if (size > 0) 2345 { 2346 msb = mask AND NOT (mask >> 1); 2347 carry_in = ((*addr AND LSB) != 0); 2348 addr += size-1; 2349 *addr &= mask; 2350 carry_out = ((*addr AND LSB) != 0); 2351 *addr >>= 1; 2352 if (carry_in) *addr |= msb; 2353 carry_in = carry_out; 2354 addr--; 2355 size--; 2356 while (size-- > 0) 2357 { 2358 carry_out = ((*addr AND LSB) != 0); 2359 *addr >>= 1; 2360 if (carry_in) *addr |= MSB; 2361 carry_in = carry_out; 2362 addr--; 2363 } 2364 } 2365 return(carry_out); 2366 } 2367 2368 boolean BitVector_shift_left(wordptr addr, boolean carry_in) 2369 { 2370 N_word size = size_(addr); 2371 N_word mask = mask_(addr); 2372 N_word msb; 2373 boolean carry_out = carry_in; 2374 2375 if (size > 0) 2376 { 2377 msb = mask AND NOT (mask >> 1); 2378 while (size-- > 1) 2379 { 2380 carry_out = ((*addr AND MSB) != 0); 2381 *addr <<= 1; 2382 if (carry_in) *addr |= LSB; 2383 carry_in = carry_out; 2384 addr++; 2385 } 2386 carry_out = ((*addr AND msb) != 0); 2387 *addr <<= 1; 2388 if (carry_in) *addr |= LSB; 2389 *addr &= mask; 2390 } 2391 return(carry_out); 2392 } 2393 2394 boolean BitVector_shift_right(wordptr addr, boolean carry_in) 2395 { 2396 N_word size = size_(addr); 2397 N_word mask = mask_(addr); 2398 N_word msb; 2399 boolean carry_out = carry_in; 2400 2401 if (size > 0) 2402 { 2403 msb = mask AND NOT (mask >> 1); 2404 addr += size-1; 2405 *addr &= mask; 2406 carry_out = ((*addr AND LSB) != 0); 2407 *addr >>= 1; 2408 if (carry_in) *addr |= msb; 2409 carry_in = carry_out; 2410 addr--; 2411 size--; 2412 while (size-- > 0) 2413 { 2414 carry_out = ((*addr AND LSB) != 0); 2415 *addr >>= 1; 2416 if (carry_in) *addr |= MSB; 2417 carry_in = carry_out; 2418 addr--; 2419 } 2420 } 2421 return(carry_out); 2422 } 2423 2424 void BitVector_Move_Left(wordptr addr, N_int bits) 2425 { 2426 N_word count; 2427 N_word words; 2428 2429 if (bits > 0) 2430 { 2431 count = bits AND MODMASK; 2432 words = bits >> LOGBITS; 2433 if (bits >= bits_(addr)) BitVector_Empty(addr); 2434 else 2435 { 2436 while (count-- > 0) BitVector_shift_left(addr,0); 2437 BitVector_Word_Insert(addr,0,words,TRUE); 2438 } 2439 } 2440 } 2441 2442 void BitVector_Move_Right(wordptr addr, N_int bits) 2443 { 2444 N_word count; 2445 N_word words; 2446 2447 if (bits > 0) 2448 { 2449 count = bits AND MODMASK; 2450 words = bits >> LOGBITS; 2451 if (bits >= bits_(addr)) BitVector_Empty(addr); 2452 else 2453 { 2454 while (count-- > 0) BitVector_shift_right(addr,0); 2455 BitVector_Word_Delete(addr,0,words,TRUE); 2456 } 2457 } 2458 } 2459 2460 void BitVector_Insert(wordptr addr, N_int offset, N_int count, boolean clear) 2461 { 2462 N_word bits = bits_(addr); 2463 N_word last; 2464 2465 if ((count > 0) and (offset < bits)) 2466 { 2467 last = offset + count; 2468 if (last < bits) 2469 { 2470 BitVector_Interval_Copy(addr,addr,last,offset,(bits-last)); 2471 } 2472 else last = bits; 2473 if (clear) BitVector_Interval_Empty(addr,offset,(last-1)); 2474 } 2475 } 2476 2477 void BitVector_Delete(wordptr addr, N_int offset, N_int count, boolean clear) 2478 { 2479 N_word bits = bits_(addr); 2480 N_word last; 2481 2482 if ((count > 0) and (offset < bits)) 2483 { 2484 last = offset + count; 2485 if (last < bits) 2486 { 2487 BitVector_Interval_Copy(addr,addr,offset,last,(bits-last)); 2488 } 2489 else count = bits - offset; 2490 if (clear) BitVector_Interval_Empty(addr,(bits-count),(bits-1)); 2491 } 2492 } 2493 2494 boolean BitVector_increment(wordptr addr) /* X++ */ 2495 { 2496 N_word size = size_(addr); 2497 N_word mask = mask_(addr); 2498 wordptr last = addr + size - 1; 2499 boolean carry = TRUE; 2500 2501 if (size > 0) 2502 { 2503 *last |= NOT mask; 2504 while (carry and (size-- > 0)) 2505 { 2506 carry = (++(*addr++) == 0); 2507 } 2508 *last &= mask; 2509 } 2510 return(carry); 2511 } 2512 2513 boolean BitVector_decrement(wordptr addr) /* X-- */ 2514 { 2515 N_word size = size_(addr); 2516 N_word mask = mask_(addr); 2517 wordptr last = addr + size - 1; 2518 boolean carry = TRUE; 2519 2520 if (size > 0) 2521 { 2522 *last &= mask; 2523 while (carry and (size-- > 0)) 2524 { 2525 carry = (*addr == 0); 2526 --(*addr++); 2527 } 2528 *last &= mask; 2529 } 2530 return(carry); 2531 } 2532 2533 boolean BitVector_compute(wordptr X, wordptr Y, wordptr Z, boolean minus, boolean *carry) 2534 { 2535 N_word size = size_(X); 2536 N_word mask = mask_(X); 2537 N_word vv = 0; 2538 N_word cc; 2539 N_word mm; 2540 N_word yy; 2541 N_word zz; 2542 N_word lo; 2543 N_word hi; 2544 2545 if (size > 0) 2546 { 2547 if (minus) cc = (*carry == 0); 2548 else cc = (*carry != 0); 2549 /* deal with (size-1) least significant full words first: */ 2550 while (--size > 0) 2551 { 2552 yy = *Y++; 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); 2559 } 2560 /* deal with most significant word (may be used only partially): */ 2561 yy = *Y AND mask; 2562 if (minus) zz = (N_word) NOT ( Z ? *Z : 0 ); 2563 else zz = (N_word) ( Z ? *Z : 0 ); 2564 zz &= mask; 2565 if (mask == LSB) /* special case, only one bit used */ 2566 { 2567 vv = cc; 2568 lo = yy + zz + cc; 2569 cc = (lo >> 1); 2570 vv ^= cc; 2571 *X = lo AND LSB; 2572 } 2573 else 2574 { 2575 if (NOT mask) /* not all bits are used, but more than one */ 2576 { 2577 mm = (mask >> 1); 2578 vv = (yy AND mm) + (zz AND mm) + cc; 2579 mm = mask AND NOT mm; 2580 lo = yy + zz + cc; 2581 cc = (lo >> 1); 2582 vv ^= cc; 2583 vv &= mm; 2584 cc &= mm; 2585 *X = lo AND mask; 2586 } 2587 else /* other special case, all bits are used */ 2588 { 2589 mm = NOT MSB; 2590 lo = (yy AND mm) + (zz AND mm) + cc; 2591 vv = lo AND MSB; 2592 hi = ((yy AND MSB) >> 1) + ((zz AND MSB) >> 1) + (vv >> 1); 2593 cc = hi AND MSB; 2594 vv ^= cc; 2595 *X = (hi << 1) OR (lo AND mm); 2596 } 2597 } 2598 if (minus) *carry = (cc == 0); 2599 else *carry = (cc != 0); 2600 } 2601 return(vv != 0); 2602 } 2603 2604 boolean BitVector_add(wordptr X, wordptr Y, wordptr Z, boolean *carry) 2605 { 2606 return(BitVector_compute(X,Y,Z,FALSE,carry)); 2607 } 2608 2609 boolean BitVector_sub(wordptr X, wordptr Y, wordptr Z, boolean *carry) 2610 { 2611 return(BitVector_compute(X,Y,Z,TRUE,carry)); 2612 } 2613 2614 boolean BitVector_inc(wordptr X, wordptr Y) 2615 { 2616 boolean carry = TRUE; 2617 2618 return(BitVector_compute(X,Y,NULL,FALSE,&carry)); 2619 } 2620 2621 boolean BitVector_dec(wordptr X, wordptr Y) 2622 { 2623 boolean carry = TRUE; 2624 2625 return(BitVector_compute(X,Y,NULL,TRUE,&carry)); 2626 } 2627 2628 void BitVector_Negate(wordptr X, wordptr Y) 2629 { 2630 N_word size = size_(X); 2631 N_word mask = mask_(X); 2632 boolean carry = TRUE; 2633 2634 if (size > 0) 2635 { 2636 while (size-- > 0) 2637 { 2638 *X = NOT *Y++; 2639 if (carry) 2640 { 2641 carry = (++(*X) == 0); 2642 } 2643 X++; 2644 } 2645 *(--X) &= mask; 2646 } 2647 } 2648 2649 void BitVector_Absolute(wordptr X, wordptr Y) 2650 { 2651 N_word size = size_(Y); 2652 N_word mask = mask_(Y); 2653 2654 if (size > 0) 2655 { 2656 if (*(Y+size-1) AND (mask AND NOT (mask >> 1))) BitVector_Negate(X,Y); 2657 else BitVector_Copy(X,Y); 2658 } 2659 } 2660 2661 Z_int BitVector_Sign(wordptr addr) 2662 { 2663 N_word size = size_(addr); 2664 N_word mask = mask_(addr); 2665 wordptr last = addr + size - 1; 2666 boolean r = TRUE; 2667 2668 if (size > 0) 2669 { 2670 *last &= mask; 2671 while (r and (size-- > 0)) r = ( *addr++ == 0 ); 2672 } 2673 if (r) return((Z_int) 0); 2674 else 2675 { 2676 if (*last AND (mask AND NOT (mask >> 1))) return((Z_int) -1); 2677 else return((Z_int) 1); 2678 } 2679 } 2680 2681 ErrCode BitVector_Mul_Pos(wordptr X, wordptr Y, wordptr Z, boolean strict) 2682 { 2683 N_word mask; 2684 N_word limit; 2685 N_word count; 2686 Z_long last; 2687 wordptr sign; 2688 boolean carry; 2689 boolean overflow; 2690 boolean ok = TRUE; 2691 2692 /* 2693 Requirements: 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 2697 Constraints: 2698 - The contents of Y (and of X, of course) are destroyed 2699 (only Z is preserved!) 2700 */ 2701 2702 if ((X == Y) or (X == Z) or (Y == Z)) return(ErrCode_Same); 2703 if (bits_(X) != bits_(Y)) return(ErrCode_Size); 2704 BitVector_Empty(X); 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; 2709 mask = mask_(Y); 2710 *sign &= mask; 2711 mask &= NOT (mask >> 1); 2712 for ( count = 0; (ok and (count <= limit)); count++ ) 2713 { 2714 if ( BIT_VECTOR_TST_BIT(Z,count) ) 2715 { 2716 carry = false; 2717 overflow = BitVector_compute(X,X,Y,false,&carry); 2718 if (strict) ok = not (carry or overflow); 2719 else ok = not carry; 2720 } 2721 if (ok and (count < limit)) 2722 { 2723 carry = BitVector_shift_left(Y,0); 2724 if (strict) 2725 { 2726 overflow = ((*sign AND mask) != 0); 2727 ok = not (carry or overflow); 2728 } 2729 else ok = not carry; 2730 } 2731 } 2732 if (ok) return(ErrCode_Ok); else return(ErrCode_Ovfl); 2733 } 2734 2735 ErrCode BitVector_Multiply(wordptr X, wordptr Y, wordptr Z) 2736 { 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); 2741 N_word size; 2742 N_word mask; 2743 N_word msb; 2744 wordptr ptr_y; 2745 wordptr ptr_z; 2746 boolean sgn_x; 2747 boolean sgn_y; 2748 boolean sgn_z; 2749 boolean zero; 2750 wordptr A; 2751 wordptr B; 2752 2753 /* 2754 Requirements: 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 (!) 2757 Features: 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!) 2761 */ 2762 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)) 2765 { 2766 BitVector_Empty(X); 2767 } 2768 else 2769 { 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); } 2774 size = size_(Y); 2775 mask = mask_(Y); 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); 2782 ptr_y = A + size; 2783 ptr_z = B + size; 2784 zero = TRUE; 2785 while (zero and (size-- > 0)) 2786 { 2787 zero &= (*(--ptr_y) == 0); 2788 zero &= (*(--ptr_z) == 0); 2789 } 2790 if (*ptr_y > *ptr_z) 2791 { 2792 if (bit_x > bit_y) 2793 { 2794 A = BitVector_Resize(A,bit_x); 2795 if (A == NULL) { BitVector_Destroy(B); return(ErrCode_Null); } 2796 } 2797 error = BitVector_Mul_Pos(X,A,B,TRUE); 2798 } 2799 else 2800 { 2801 if (bit_x > bit_z) 2802 { 2803 B = BitVector_Resize(B,bit_x); 2804 if (B == NULL) { BitVector_Destroy(A); return(ErrCode_Null); } 2805 } 2806 error = BitVector_Mul_Pos(X,B,A,TRUE); 2807 } 2808 if ((not error) and sgn_x) BitVector_Negate(X,X); 2809 BitVector_Destroy(A); 2810 BitVector_Destroy(B); 2811 } 2812 return(error); 2813 } 2814 2815 ErrCode BitVector_Div_Pos(wordptr Q, wordptr X, wordptr Y, wordptr R) 2816 { 2817 N_word bits = bits_(Q); 2818 N_word mask; 2819 wordptr addr; 2820 Z_long last; 2821 boolean flag; 2822 boolean copy = FALSE; /* flags whether valid rest is in R (0) or X (1) */ 2823 2824 /* 2825 Requirements: 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!) 2829 Constraints: 2830 - The contents of X (and Q and R, of course) are destroyed 2831 (only Y is preserved!) 2832 */ 2833 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); 2840 2841 BitVector_Empty(R); 2842 BitVector_Copy(Q,X); 2843 if ((last = Set_Max(Q)) < 0L) return(ErrCode_Ok); 2844 bits = (N_word) ++last; 2845 while (bits-- > 0) 2846 { 2847 addr = Q + (bits >> LOGBITS); 2848 mask = BITMASKTAB[bits AND MODMASK]; 2849 flag = ((*addr AND mask) != 0); 2850 if (copy) 2851 { 2852 BitVector_shift_left(X,flag); 2853 flag = FALSE; 2854 BitVector_compute(R,X,Y,TRUE,&flag); 2855 } 2856 else 2857 { 2858 BitVector_shift_left(R,flag); 2859 flag = FALSE; 2860 BitVector_compute(X,R,Y,TRUE,&flag); 2861 } 2862 if (flag) *addr &= NOT mask; 2863 else 2864 { 2865 *addr |= mask; 2866 copy = not copy; 2867 } 2868 } 2869 if (copy) BitVector_Copy(R,X); 2870 return(ErrCode_Ok); 2871 } 2872 2873 ErrCode BitVector_Divide(wordptr Q, wordptr X, wordptr Y, wordptr R) 2874 { 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)); 2880 boolean sgn_q; 2881 boolean sgn_x; 2882 boolean sgn_y; 2883 wordptr A; 2884 wordptr B; 2885 2886 /* 2887 Requirements: 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!) 2891 Features: 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!) 2897 */ 2898 2899 if ((bits != bits_(X)) or (bits != bits_(Y)) or (bits != bits_(R))) 2900 return(ErrCode_Size); 2901 if (Q == R) 2902 return(ErrCode_Same); 2903 if (BitVector_is_empty(Y)) 2904 return(ErrCode_Zero); 2905 2906 if (BitVector_is_empty(X)) 2907 { 2908 BitVector_Empty(Q); 2909 BitVector_Empty(R); 2910 } 2911 else 2912 { 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); } 2917 size--; 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))) 2924 { 2925 if (sgn_q) BitVector_Negate(Q,Q); 2926 if (sgn_x) BitVector_Negate(R,R); 2927 } 2928 BitVector_Destroy(A); 2929 BitVector_Destroy(B); 2930 } 2931 return(error); 2932 } 2933 2934 ErrCode BitVector_GCD(wordptr X, wordptr Y, wordptr Z) 2935 { 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)); 2941 boolean sgn_a; 2942 boolean sgn_b; 2943 boolean sgn_r; 2944 wordptr Q; 2945 wordptr R; 2946 wordptr A; 2947 wordptr B; 2948 wordptr T; 2949 2950 /* 2951 Requirements: 2952 - All bit vectors must have equal sizes 2953 Features: 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 2959 */ 2960 2961 if ((bits != bits_(Y)) or (bits != bits_(Z))) return(ErrCode_Size); 2962 if (BitVector_is_empty(Y)) 2963 { 2964 if (X != Z) BitVector_Copy(X,Z); 2965 return(ErrCode_Ok); 2966 } 2967 if (BitVector_is_empty(Z)) 2968 { 2969 if (X != Y) BitVector_Copy(X,Y); 2970 return(ErrCode_Ok); 2971 } 2972 Q = BitVector_Create(bits,false); 2973 if (Q == NULL) 2974 { 2975 return(ErrCode_Null); 2976 } 2977 R = BitVector_Create(bits,FALSE); 2978 if (R == NULL) 2979 { 2980 BitVector_Destroy(Q); 2981 return(ErrCode_Null); 2982 } 2983 A = BitVector_Create(bits,FALSE); 2984 if (A == NULL) 2985 { 2986 BitVector_Destroy(Q); 2987 BitVector_Destroy(R); 2988 return(ErrCode_Null); 2989 } 2990 B = BitVector_Create(bits,FALSE); 2991 if (B == NULL) 2992 { 2993 BitVector_Destroy(Q); 2994 BitVector_Destroy(R); 2995 BitVector_Destroy(A); 2996 return(ErrCode_Null); 2997 } 2998 size--; 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); 3003 while (not error) 3004 { 3005 if (not (error = BitVector_Div_Pos(Q,A,B,R))) 3006 { 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; 3011 R = T; 3012 } 3013 } 3014 if (not error) 3015 { 3016 if (sgn_b) BitVector_Negate(X,B); else BitVector_Copy(X,B); 3017 } 3018 BitVector_Destroy(Q); 3019 BitVector_Destroy(R); 3020 BitVector_Destroy(A); 3021 BitVector_Destroy(B); 3022 return(error); 3023 } 3024 3025 ErrCode BitVector_GCD2(wordptr U, wordptr V, wordptr W, wordptr X, wordptr Y) 3026 { 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)); 3032 boolean minus; 3033 boolean carry; 3034 boolean sgn_q; 3035 boolean sgn_r; 3036 boolean sgn_a; 3037 boolean sgn_b; 3038 boolean sgn_x; 3039 boolean sgn_y; 3040 listptr L; 3041 wordptr Q; 3042 wordptr R; 3043 wordptr A; 3044 wordptr B; 3045 wordptr T; 3046 wordptr X1; 3047 wordptr X2; 3048 wordptr X3; 3049 wordptr Y1; 3050 wordptr Y2; 3051 wordptr Y3; 3052 wordptr Z; 3053 3054 /* 3055 Requirements: 3056 - All bit vectors must have equal sizes 3057 - U, V, and W must all be distinct bit vectors 3058 Features: 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 3065 */ 3066 3067 if ((bits != bits_(V)) or 3068 (bits != bits_(W)) or 3069 (bits != bits_(X)) or 3070 (bits != bits_(Y))) 3071 { 3072 return(ErrCode_Size); 3073 } 3074 if ((U == V) or (U == W) or (V == W)) 3075 { 3076 return(ErrCode_Same); 3077 } 3078 if (BitVector_is_empty(X)) 3079 { 3080 if (U != Y) BitVector_Copy(U,Y); 3081 BitVector_Empty(V); 3082 BitVector_Empty(W); 3083 *W = 1; 3084 return(ErrCode_Ok); 3085 } 3086 if (BitVector_is_empty(Y)) 3087 { 3088 if (U != X) BitVector_Copy(U,X); 3089 BitVector_Empty(V); 3090 BitVector_Empty(W); 3091 *V = 1; 3092 return(ErrCode_Ok); 3093 } 3094 if ((L = BitVector_Create_List(bits,false,11)) == NULL) 3095 { 3096 return(ErrCode_Null); 3097 } 3098 Q = L[0]; 3099 R = L[1]; 3100 A = L[2]; 3101 B = L[3]; 3102 X1 = L[4]; 3103 X2 = L[5]; 3104 X3 = L[6]; 3105 Y1 = L[7]; 3106 Y2 = L[8]; 3107 Y3 = L[9]; 3108 Z = L[10]; 3109 size--; 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); 3116 *X1 = 1; 3117 BitVector_Empty(Y1); 3118 BitVector_Empty(Y2); 3119 *Y2 = 1; 3120 sgn_x = false; 3121 sgn_y = false; 3122 while (not error) 3123 { 3124 if ((error = BitVector_Div_Pos(Q,A,B,R))) 3125 { 3126 break; 3127 } 3128 if (BitVector_is_empty(R)) 3129 { 3130 break; 3131 } 3132 sgn_q = sgn_a XOR sgn_b; 3133 3134 if (sgn_x) BitVector_Negate(Z,X2); else BitVector_Copy(Z,X2); 3135 if ((error = BitVector_Mul_Pos(X3,Z,Q,true))) 3136 { 3137 break; 3138 } 3139 minus = not (sgn_x XOR sgn_q); 3140 carry = 0; 3141 if (BitVector_compute(X3,X1,X3,minus,&carry)) 3142 { 3143 error = ErrCode_Ovfl; 3144 break; 3145 } 3146 sgn_x = (((*(X3+size) &= mask) AND msb) != 0); 3147 3148 if (sgn_y) BitVector_Negate(Z,Y2); else BitVector_Copy(Z,Y2); 3149 if ((error = BitVector_Mul_Pos(Y3,Z,Q,true))) 3150 { 3151 break; 3152 } 3153 minus = not (sgn_y XOR sgn_q); 3154 carry = 0; 3155 if (BitVector_compute(Y3,Y1,Y3,minus,&carry)) 3156 { 3157 error = ErrCode_Ovfl; 3158 break; 3159 } 3160 sgn_y = (((*(Y3+size) &= mask) AND msb) != 0); 3161 3162 T = A; sgn_r = sgn_a; 3163 A = B; sgn_a = sgn_b; 3164 B = R; sgn_b = sgn_r; 3165 R = T; 3166 3167 T = X1; 3168 X1 = X2; 3169 X2 = X3; 3170 X3 = T; 3171 3172 T = Y1; 3173 Y1 = Y2; 3174 Y2 = Y3; 3175 Y3 = T; 3176 } 3177 if (not error) 3178 { 3179 if (sgn_b) BitVector_Negate(U,B); else BitVector_Copy(U,B); 3180 BitVector_Copy(V,X2); 3181 BitVector_Copy(W,Y2); 3182 } 3183 BitVector_Destroy_List(L,11); 3184 return(error); 3185 } 3186 3187 ErrCode BitVector_Power(wordptr X, wordptr Y, wordptr Z) 3188 { 3189 ErrCode error = ErrCode_Ok; 3190 N_word bits = bits_(X); 3191 boolean first = TRUE; 3192 Z_long last; 3193 N_word limit; 3194 N_word count; 3195 wordptr T; 3196 3197 /* 3198 Requirements: 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 3202 Features: 3203 - The contents of Y and Z are preserved 3204 */ 3205 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) 3210 { 3211 if (bits < 2) return(ErrCode_Ovfl); 3212 BitVector_Empty(X); 3213 *X |= LSB; 3214 return(ErrCode_Ok); /* anything ^ 0 == 1 */ 3215 } 3216 if (BitVector_is_empty(Y)) 3217 { 3218 if (X != Y) BitVector_Empty(X); 3219 return(ErrCode_Ok); /* 0 ^ anything not zero == 0 */ 3220 } 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++ ) 3225 { 3226 if ( BIT_VECTOR_TST_BIT(Z,count) ) 3227 { 3228 if (first) 3229 { 3230 first = FALSE; 3231 if (count) { BitVector_Copy(X,T); } 3232 else { if (X != Y) BitVector_Copy(X,Y); } 3233 } 3234 else error = BitVector_Multiply(X,T,X); /* order important because T > X */ 3235 } 3236 if ((!error) and (count < limit)) 3237 { 3238 if (count) error = BitVector_Multiply(T,T,T); 3239 else error = BitVector_Multiply(T,Y,Y); 3240 } 3241 } 3242 BitVector_Destroy(T); 3243 return(error); 3244 } 3245 3246 void BitVector_Block_Store(wordptr addr, charptr buffer, N_int length) 3247 { 3248 N_word size = size_(addr); 3249 N_word mask = mask_(addr); 3250 N_word value; 3251 N_word count; 3252 3253 /* provide translation for independence of endian-ness: */ 3254 if (size > 0) 3255 { 3256 while (size-- > 0) 3257 { 3258 value = 0; 3259 for ( count = 0; (length > 0) and (count < BITS); count += 8 ) 3260 { 3261 value |= (((N_word) *buffer++) << count); length--; 3262 } 3263 *addr++ = value; 3264 } 3265 *(--addr) &= mask; 3266 } 3267 } 3268 3269 charptr BitVector_Block_Read(wordptr addr, N_intptr length) 3270 { 3271 N_word size = size_(addr); 3272 N_word value; 3273 N_word count; 3274 charptr buffer; 3275 charptr target; 3276 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); 3281 target = buffer; 3282 if (size > 0) 3283 { 3284 *(addr+size-1) &= mask_(addr); 3285 while (size-- > 0) 3286 { 3287 value = *addr++; 3288 count = BITS >> 3; 3289 while (count-- > 0) 3290 { 3291 *target++ = (N_char) (value AND 0x00FF); 3292 if (count > 0) value >>= 8; 3293 } 3294 } 3295 } 3296 *target = (N_char) '\0'; 3297 return(buffer); 3298 } 3299 3300 void BitVector_Word_Store(wordptr addr, N_int offset, N_int value) 3301 { 3302 N_word size = size_(addr); 3303 3304 if (size > 0) 3305 { 3306 if (offset < size) *(addr+offset) = value; 3307 *(addr+size-1) &= mask_(addr); 3308 } 3309 } 3310 3311 N_int BitVector_Word_Read(wordptr addr, N_int offset) 3312 { 3313 N_word size = size_(addr); 3314 3315 if (size > 0) 3316 { 3317 *(addr+size-1) &= mask_(addr); 3318 if (offset < size) return( *(addr+offset) ); 3319 } 3320 return( (N_int) 0 ); 3321 } 3322 3323 void BitVector_Word_Insert(wordptr addr, N_int offset, N_int count, 3324 boolean clear) 3325 { 3326 N_word size = size_(addr); 3327 N_word mask = mask_(addr); 3328 wordptr last = addr+size-1; 3329 3330 if (size > 0) 3331 { 3332 *last &= mask; 3333 if (offset > size) offset = size; 3334 BIT_VECTOR_ins_words(addr+offset,size-offset,count,clear); 3335 *last &= mask; 3336 } 3337 } 3338 3339 void BitVector_Word_Delete(wordptr addr, N_int offset, N_int count, 3340 boolean clear) 3341 { 3342 N_word size = size_(addr); 3343 N_word mask = mask_(addr); 3344 wordptr last = addr+size-1; 3345 3346 if (size > 0) 3347 { 3348 *last &= mask; 3349 if (offset > size) offset = size; 3350 BIT_VECTOR_del_words(addr+offset,size-offset,count,clear); 3351 *last &= mask; 3352 } 3353 } 3354 3355 void BitVector_Chunk_Store(wordptr addr, N_int chunksize, N_int offset, 3356 N_long value) 3357 { 3358 N_word bits = bits_(addr); 3359 N_word mask; 3360 N_word temp; 3361 3362 if ((chunksize > 0) and (offset < bits)) 3363 { 3364 if (chunksize > LONGBITS) chunksize = LONGBITS; 3365 if ((offset + chunksize) > bits) chunksize = bits - offset; 3366 addr += offset >> LOGBITS; 3367 offset &= MODMASK; 3368 while (chunksize > 0) 3369 { 3370 mask = (N_word) (~0L << offset); 3371 bits = offset + chunksize; 3372 if (bits < BITS) 3373 { 3374 mask &= (N_word) ~(~0L << bits); 3375 bits = chunksize; 3376 } 3377 else bits = BITS - offset; 3378 temp = (N_word) (value << offset); 3379 temp &= mask; 3380 *addr &= NOT mask; 3381 *addr++ |= temp; 3382 value >>= bits; 3383 chunksize -= bits; 3384 offset = 0; 3385 } 3386 } 3387 } 3388 3389 N_long BitVector_Chunk_Read(wordptr addr, N_int chunksize, N_int offset) 3390 { 3391 N_word bits = bits_(addr); 3392 N_word chunkbits = 0; 3393 N_long value = 0L; 3394 N_long temp; 3395 N_word mask; 3396 3397 if ((chunksize > 0) and (offset < bits)) 3398 { 3399 if (chunksize > LONGBITS) chunksize = LONGBITS; 3400 if ((offset + chunksize) > bits) chunksize = bits - offset; 3401 addr += offset >> LOGBITS; 3402 offset &= MODMASK; 3403 while (chunksize > 0) 3404 { 3405 bits = offset + chunksize; 3406 if (bits < BITS) 3407 { 3408 mask = (N_word) ~(~0L << bits); 3409 bits = chunksize; 3410 } 3411 else 3412 { 3413 mask = (N_word) ~0L; 3414 bits = BITS - offset; 3415 } 3416 temp = (N_long) ((*addr++ AND mask) >> offset); 3417 value |= temp << chunkbits; 3418 chunkbits += bits; 3419 chunksize -= bits; 3420 offset = 0; 3421 } 3422 } 3423 return(value); 3424 } 3425 3426 /*******************/ 3427 /* set operations: */ 3428 /*******************/ 3429 3430 void Set_Union(wordptr X, wordptr Y, wordptr Z) /* X = Y + Z */ 3431 { 3432 N_word bits = bits_(X); 3433 N_word size = size_(X); 3434 N_word mask = mask_(X); 3435 3436 if ((size > 0) and (bits == bits_(Y)) and (bits == bits_(Z))) 3437 { 3438 while (size-- > 0) *X++ = *Y++ OR *Z++; 3439 *(--X) &= mask; 3440 } 3441 } 3442 3443 void Set_Intersection(wordptr X, wordptr Y, wordptr Z) /* X = Y * Z */ 3444 { 3445 N_word bits = bits_(X); 3446 N_word size = size_(X); 3447 N_word mask = mask_(X); 3448 3449 if ((size > 0) and (bits == bits_(Y)) and (bits == bits_(Z))) 3450 { 3451 while (size-- > 0) *X++ = *Y++ AND *Z++; 3452 *(--X) &= mask; 3453 } 3454 } 3455 3456 void Set_Difference(wordptr X, wordptr Y, wordptr Z) /* X = Y \ Z */ 3457 { 3458 N_word bits = bits_(X); 3459 N_word size = size_(X); 3460 N_word mask = mask_(X); 3461 3462 if ((size > 0) and (bits == bits_(Y)) and (bits == bits_(Z))) 3463 { 3464 while (size-- > 0) *X++ = *Y++ AND NOT *Z++; 3465 *(--X) &= mask; 3466 } 3467 } 3468 3469 void Set_ExclusiveOr(wordptr X, wordptr Y, wordptr Z) /* X=(Y+Z)\(Y*Z) */ 3470 { 3471 N_word bits = bits_(X); 3472 N_word size = size_(X); 3473 N_word mask = mask_(X); 3474 3475 if ((size > 0) and (bits == bits_(Y)) and (bits == bits_(Z))) 3476 { 3477 while (size-- > 0) *X++ = *Y++ XOR *Z++; 3478 *(--X) &= mask; 3479 } 3480 } 3481 3482 void Set_Complement(wordptr X, wordptr Y) /* X = ~Y */ 3483 { 3484 N_word size = size_(X); 3485 N_word mask = mask_(X); 3486 3487 if ((size > 0) and (bits_(X) == bits_(Y))) 3488 { 3489 while (size-- > 0) *X++ = NOT *Y++; 3490 *(--X) &= mask; 3491 } 3492 } 3493 3494 /******************/ 3495 /* set functions: */ 3496 /******************/ 3497 3498 boolean Set_subset(wordptr X, wordptr Y) /* X subset Y ? */ 3499 { 3500 N_word size = size_(X); 3501 boolean r = FALSE; 3502 3503 if ((size > 0) and (bits_(X) == bits_(Y))) 3504 { 3505 r = TRUE; 3506 while (r and (size-- > 0)) r = ((*X++ AND NOT *Y++) == 0); 3507 } 3508 return(r); 3509 } 3510 3511 N_int Set_Norm(wordptr addr) /* = | X | */ 3512 { 3513 byteptr byte; 3514 N_word bytes; 3515 N_int n; 3516 3517 byte = (byteptr) addr; 3518 bytes = size_(addr) << FACTOR; 3519 n = 0; 3520 while (bytes-- > 0) 3521 { 3522 n += BitVector_BYTENORM[*byte++]; 3523 } 3524 return(n); 3525 } 3526 3527 N_int Set_Norm2(wordptr addr) /* = | X | */ 3528 { 3529 N_word size = size_(addr); 3530 N_word w0,w1; 3531 N_int n,k; 3532 3533 n = 0; 3534 while (size-- > 0) 3535 { 3536 k = 0; 3537 w1 = NOT (w0 = *addr++); 3538 while (w0 and w1) 3539 { 3540 w0 &= w0 - 1; 3541 w1 &= w1 - 1; 3542 k++; 3543 } 3544 if (w0 == 0) n += k; 3545 else n += BITS - k; 3546 } 3547 return(n); 3548 } 3549 3550 N_int Set_Norm3(wordptr addr) /* = | X | */ 3551 { 3552 N_word size = size_(addr); 3553 N_int count = 0; 3554 N_word c; 3555 3556 while (size-- > 0) 3557 { 3558 c = *addr++; 3559 while (c) 3560 { 3561 c &= c - 1; 3562 count++; 3563 } 3564 } 3565 return(count); 3566 } 3567 3568 Z_long Set_Min(wordptr addr) /* = min(X) */ 3569 { 3570 boolean empty = TRUE; 3571 N_word size = size_(addr); 3572 N_word i = 0; 3573 N_word c = 0; /* silence compiler warning */ 3574 3575 while (empty and (size-- > 0)) 3576 { 3577 if ((c = *addr++)) empty = false; else i++; 3578 } 3579 if (empty) return((Z_long) LONG_MAX); /* plus infinity */ 3580 i <<= LOGBITS; 3581 while (not (c AND LSB)) 3582 { 3583 c >>= 1; 3584 i++; 3585 } 3586 return((Z_long) i); 3587 } 3588 3589 Z_long Set_Max(wordptr addr) /* = max(X) */ 3590 { 3591 boolean empty = TRUE; 3592 N_word size = size_(addr); 3593 N_word i = size; 3594 N_word c = 0; /* silence compiler warning */ 3595 3596 addr += size-1; 3597 while (empty and (size-- > 0)) 3598 { 3599 if ((c = *addr--)) empty = false; else i--; 3600 } 3601 if (empty) return((Z_long) LONG_MIN); /* minus infinity */ 3602 i <<= LOGBITS; 3603 while (not (c AND MSB)) 3604 { 3605 c <<= 1; 3606 i--; 3607 } 3608 return((Z_long) --i); 3609 } 3610 3611 /**********************************/ 3612 /* matrix-of-booleans operations: */ 3613 /**********************************/ 3614 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) 3618 { 3619 N_word i; 3620 N_word j; 3621 N_word k; 3622 N_word indxX; 3623 N_word indxY; 3624 N_word indxZ; 3625 N_word termX; 3626 N_word termY; 3627 N_word sum; 3628 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)) 3633 { 3634 for ( i = 0; i < rowsY; i++ ) 3635 { 3636 termX = i * colsX; 3637 termY = i * colsY; 3638 for ( j = 0; j < colsZ; j++ ) 3639 { 3640 indxX = termX + j; 3641 sum = 0; 3642 for ( k = 0; k < colsY; k++ ) 3643 { 3644 indxY = termY + k; 3645 indxZ = k * colsZ + j; 3646 if ( BIT_VECTOR_TST_BIT(Y,indxY) && 3647 BIT_VECTOR_TST_BIT(Z,indxZ) ) sum ^= 1; 3648 } 3649 if (sum) BIT_VECTOR_SET_BIT(X,indxX) 3650 else BIT_VECTOR_CLR_BIT(X,indxX) 3651 } 3652 } 3653 } 3654 } 3655 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) 3659 { 3660 N_word i; 3661 N_word j; 3662 N_word k; 3663 N_word indxX; 3664 N_word indxY; 3665 N_word indxZ; 3666 N_word termX; 3667 N_word termY; 3668 N_word sum; 3669 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)) 3674 { 3675 for ( i = 0; i < rowsY; i++ ) 3676 { 3677 termX = i * colsX; 3678 termY = i * colsY; 3679 for ( j = 0; j < colsZ; j++ ) 3680 { 3681 indxX = termX + j; 3682 sum = 0; 3683 for ( k = 0; k < colsY; k++ ) 3684 { 3685 indxY = termY + k; 3686 indxZ = k * colsZ + j; 3687 if ( BIT_VECTOR_TST_BIT(Y,indxY) && 3688 BIT_VECTOR_TST_BIT(Z,indxZ) ) sum |= 1; 3689 } 3690 if (sum) BIT_VECTOR_SET_BIT(X,indxX) 3691 else BIT_VECTOR_CLR_BIT(X,indxX) 3692 } 3693 } 3694 } 3695 } 3696 3697 void Matrix_Closure(wordptr addr, N_int rows, N_int cols) 3698 { 3699 N_word i; 3700 N_word j; 3701 N_word k; 3702 N_word ii; 3703 N_word ij; 3704 N_word ik; 3705 N_word kj; 3706 N_word termi; 3707 N_word termk; 3708 3709 if ((rows == cols) and (bits_(addr) == rows*cols)) 3710 { 3711 for ( i = 0; i < rows; i++ ) 3712 { 3713 ii = i * cols + i; 3714 BIT_VECTOR_SET_BIT(addr,ii) 3715 } 3716 for ( k = 0; k < rows; k++ ) 3717 { 3718 termk = k * cols; 3719 for ( i = 0; i < rows; i++ ) 3720 { 3721 termi = i * cols; 3722 ik = termi + k; 3723 for ( j = 0; j < rows; j++ ) 3724 { 3725 ij = termi + j; 3726 kj = termk + j; 3727 if ( BIT_VECTOR_TST_BIT(addr,ik) && 3728 BIT_VECTOR_TST_BIT(addr,kj) ) 3729 BIT_VECTOR_SET_BIT(addr,ij) 3730 } 3731 } 3732 } 3733 } 3734 } 3735 3736 void Matrix_Transpose(wordptr X, N_int rowsX, N_int colsX, 3737 wordptr Y, N_int rowsY, N_int colsY) 3738 { 3739 N_word i; 3740 N_word j; 3741 N_word ii; 3742 N_word ij; 3743 N_word ji; 3744 N_word addii; 3745 N_word addij; 3746 N_word addji; 3747 N_word bitii; 3748 N_word bitij; 3749 N_word bitji; 3750 N_word termi; 3751 N_word termj; 3752 boolean swap; 3753 3754 /* BEWARE that "in-place" is ONLY possible if the matrix is quadratic!! */ 3755 3756 if ((rowsX == colsY) and (colsX == rowsY) and 3757 (bits_(X) == rowsX*colsX) and 3758 (bits_(Y) == rowsY*colsY)) 3759 { 3760 if (rowsY == colsY) /* in-place is possible! */ 3761 { 3762 for ( i = 0; i < rowsY; i++ ) 3763 { 3764 termi = i * colsY; 3765 for ( j = 0; j < i; j++ ) 3766 { 3767 termj = j * colsX; 3768 ij = termi + j; 3769 ji = termj + i; 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; 3777 else 3778 *(X+addij) &= NOT bitij; 3779 if (swap) 3780 *(X+addji) |= bitji; 3781 else 3782 *(X+addji) &= NOT bitji; 3783 } 3784 ii = termi + i; 3785 addii = ii >> LOGBITS; 3786 bitii = BITMASKTAB[ii AND MODMASK]; 3787 if ((*(Y+addii) AND bitii) != 0) 3788 *(X+addii) |= bitii; 3789 else 3790 *(X+addii) &= NOT bitii; 3791 } 3792 } 3793 else /* rowsX != colsX, in-place is NOT possible! */ 3794 { 3795 for ( i = 0; i < rowsY; i++ ) 3796 { 3797 termi = i * colsY; 3798 for ( j = 0; j < colsY; j++ ) 3799 { 3800 termj = j * colsX; 3801 ij = termi + j; 3802 ji = termj + i; 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; 3809 else 3810 *(X+addji) &= NOT bitji; 3811 } 3812 } 3813 } 3814 } 3815 } 3816 3817 /*****************************************************************************/ 3818 /* VERSION: 6.4 */ 3819 /*****************************************************************************/ 3820 /* VERSION HISTORY: */ 3821 /*****************************************************************************/ 3822 /* */ 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. */ 3848 /* */ 3849 /*****************************************************************************/ 3850 /* AUTHOR: */ 3851 /*****************************************************************************/ 3852 /* */ 3853 /* Steffen Beyer */ 3854 /* mailto:sb (at) engelschall.com */ 3855 /* http://www.engelschall.com/u/sb/download/ */ 3856 /* */ 3857 /*****************************************************************************/ 3858 /* COPYRIGHT: */ 3859 /*****************************************************************************/ 3860 /* */ 3861 /* Copyright (c) 1995 - 2004 by Steffen Beyer. */ 3862 /* All rights reserved. */ 3863 /* */ 3864 /*****************************************************************************/ 3865 /* LICENSE: */ 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". */ 3870 /* */ 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". */ 3874 /* */ 3875 /*****************************************************************************/ 3876 /* ARTISTIC LICENSE: */ 3877 /*****************************************************************************/ 3878 /* 3879 The "Artistic License" 3880 3881 Preamble 3882 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. 3889 3890 Definitions: 3891 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. 3895 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. 3899 3900 "Copyright Holder" is whoever is named in the copyright or 3901 copyrights for the package. 3902 3903 "You" is you, if you're thinking about copying or distributing 3904 this Package. 3905 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.) 3911 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. 3916 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. 3920 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. 3924 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 3928 following: 3929 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. 3935 3936 b) use the modified Package only within your corporation or organization. 3937 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. 3942 3943 d) make other distribution arrangements with the Copyright Holder. 3944 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: 3947 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. 3951 3952 b) accompany the distribution with the machine-readable source of 3953 the Package with your modifications. 3954 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. 3958 3959 d) make other distribution arrangements with the Copyright Holder. 3960 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. 3971 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 3982 Package. 3983 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. 3991 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. 3997 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. 4000 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. 4004 4005 The End 4006 */ 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. */ 4014 /* */ 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. */ 4019 /* */ 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. */ 4024 /* */ 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. */ 4032 /* */ 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. */ 4037 /* */ 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 */ 4042 /* */ 4043 /* or download a copy from ftp://ftp.gnu.org/pub/gnu/COPYING.LIB-2.0 */ 4044 /* */ 4045 /*****************************************************************************/ 4046
