1 typedef unsigned long ulong; 2 typedef unsigned int uint; 3 typedef unsigned short ushort; 4 typedef unsigned char uchar; 5 typedef signed char schar; 6 7 #define SIGN(n) (1UL<<(n-1)) 8 9 typedef struct Vlong Vlong; 10 struct Vlong 11 { 12 union 13 { 14 struct 15 { 16 ulong hi; 17 ulong lo; 18 }; 19 struct 20 { 21 ushort hims; 22 ushort hils; 23 ushort loms; 24 ushort lols; 25 }; 26 }; 27 }; 28 29 void abort(void); 30 31 void 32 _addv(Vlong *r, Vlong a, Vlong b) 33 { 34 ulong lo, hi; 35 36 lo = a.lo + b.lo; 37 hi = a.hi + b.hi; 38 if(lo < a.lo) 39 hi++; 40 r->lo = lo; 41 r->hi = hi; 42 } 43 44 void 45 _subv(Vlong *r, Vlong a, Vlong b) 46 { 47 ulong lo, hi; 48 49 lo = a.lo - b.lo; 50 hi = a.hi - b.hi; 51 if(lo > a.lo) 52 hi--; 53 r->lo = lo; 54 r->hi = hi; 55 } 56 57 void 58 _d2v(Vlong *y, double d) 59 { 60 union { double d; struct Vlong; } x; 61 ulong xhi, xlo, ylo, yhi; 62 int sh; 63 64 x.d = d; 65 66 xhi = (x.hi & 0xfffff) | 0x100000; 67 xlo = x.lo; 68 sh = 1075 - ((x.hi >> 20) & 0x7ff); 69 70 ylo = 0; 71 yhi = 0; 72 if(sh >= 0) { 73 /* v = (hi||lo) >> sh */ 74 if(sh < 32) { 75 if(sh == 0) { 76 ylo = xlo; 77 yhi = xhi; 78 } else { 79 ylo = (xlo >> sh) | (xhi << (32-sh)); 80 yhi = xhi >> sh; 81 } 82 } else { 83 if(sh == 32) { 84 ylo = xhi; 85 } else 86 if(sh < 64) { 87 ylo = xhi >> (sh-32); 88 } 89 } 90 } else { 91 /* v = (hi||lo) << -sh */ 92 sh = -sh; 93 if(sh <= 10) { 94 ylo = xlo << sh; 95 yhi = (xhi << sh) | (xlo >> (32-sh)); 96 } else { 97 /* overflow */ 98 yhi = d; /* causes something awful */ 99 } 100 } 101 if(x.hi & SIGN(32)) { 102 if(ylo != 0) { 103 ylo = -ylo; 104 yhi = ~yhi; 105 } else 106 yhi = -yhi; 107 } 108 109 y->hi = yhi; 110 y->lo = ylo; 111 } 112 113 void 114 _f2v(Vlong *y, float f) 115 { 116 117 _d2v(y, f); 118 } 119 120 double 121 _v2d(Vlong x) 122 { 123 if(x.hi & SIGN(32)) { 124 if(x.lo) { 125 x.lo = -x.lo; 126 x.hi = ~x.hi; 127 } else 128 x.hi = -x.hi; 129 return -((long)x.hi*4294967296. + x.lo); 130 } 131 return (long)x.hi*4294967296. + x.lo; 132 } 133 134 float 135 _v2f(Vlong x) 136 { 137 return _v2d(x); 138 } 139 140 static void 141 dodiv(Vlong num, Vlong den, Vlong *q, Vlong *r) 142 { 143 ulong numlo, numhi, denhi, denlo, quohi, quolo, t; 144 int i; 145 146 numhi = num.hi; 147 numlo = num.lo; 148 denhi = den.hi; 149 denlo = den.lo; 150 151 /* 152 * get a divide by zero 153 */ 154 if(denlo==0 && denhi==0) { 155 numlo = numlo / denlo; 156 } 157 158 /* 159 * set up the divisor and find the number of iterations needed 160 */ 161 if(numhi >= SIGN(32)) { 162 quohi = SIGN(32); 163 quolo = 0; 164 } else { 165 quohi = numhi; 166 quolo = numlo; 167 } 168 i = 0; 169 while(denhi < quohi || (denhi == quohi && denlo < quolo)) { 170 denhi = (denhi<<1) | (denlo>>31); 171 denlo <<= 1; 172 i++; 173 } 174 175 quohi = 0; 176 quolo = 0; 177 for(; i >= 0; i--) { 178 quohi = (quohi<<1) | (quolo>>31); 179 quolo <<= 1; 180 if(numhi > denhi || (numhi == denhi && numlo >= denlo)) { 181 t = numlo; 182 numlo -= denlo; 183 if(numlo > t) 184 numhi--; 185 numhi -= denhi; 186 quolo |= 1; 187 } 188 denlo = (denlo>>1) | (denhi<<31); 189 denhi >>= 1; 190 } 191 192 if(q) { 193 q->lo = quolo; 194 q->hi = quohi; 195 } 196 if(r) { 197 r->lo = numlo; 198 r->hi = numhi; 199 } 200 } 201 202 void 203 _divvu(Vlong *q, Vlong n, Vlong d) 204 { 205 206 if(n.hi == 0 && d.hi == 0) { 207 q->hi = 0; 208 q->lo = n.lo / d.lo; 209 return; 210 } 211 dodiv(n, d, q, 0); 212 } 213 214 void 215 _modvu(Vlong *r, Vlong n, Vlong d) 216 { 217 218 if(n.hi == 0 && d.hi == 0) { 219 r->hi = 0; 220 r->lo = n.lo % d.lo; 221 return; 222 } 223 dodiv(n, d, 0, r); 224 } 225 226 static void 227 vneg(Vlong *v) 228 { 229 230 if(v->lo == 0) { 231 v->hi = -v->hi; 232 return; 233 } 234 v->lo = -v->lo; 235 v->hi = ~v->hi; 236 } 237 238 void 239 _divv(Vlong *q, Vlong n, Vlong d) 240 { 241 long nneg, dneg; 242 243 if(n.hi == (((long)n.lo)>>31) && d.hi == (((long)d.lo)>>31)) { 244 q->lo = (long)n.lo / (long)d.lo; 245 q->hi = ((long)q->lo) >> 31; 246 return; 247 } 248 nneg = n.hi >> 31; 249 if(nneg) 250 vneg(&n); 251 dneg = d.hi >> 31; 252 if(dneg) 253 vneg(&d); 254 dodiv(n, d, q, 0); 255 if(nneg != dneg) 256 vneg(q); 257 } 258 259 void 260 _modv(Vlong *r, Vlong n, Vlong d) 261 { 262 long nneg, dneg; 263 264 if(n.hi == (((long)n.lo)>>31) && d.hi == (((long)d.lo)>>31)) { 265 r->lo = (long)n.lo % (long)d.lo; 266 r->hi = ((long)r->lo) >> 31; 267 return; 268 } 269 nneg = n.hi >> 31; 270 if(nneg) 271 vneg(&n); 272 dneg = d.hi >> 31; 273 if(dneg) 274 vneg(&d); 275 dodiv(n, d, 0, r); 276 if(nneg) 277 vneg(r); 278 } 279 280 void 281 _rshav(Vlong *r, Vlong a, int b) 282 { 283 long t; 284 285 t = a.hi; 286 if(b >= 32) { 287 r->hi = t>>31; 288 if(b >= 64) { 289 /* this is illegal re C standard */ 290 r->lo = t>>31; 291 return; 292 } 293 r->lo = t >> (b-32); 294 return; 295 } 296 if(b <= 0) { 297 r->hi = t; 298 r->lo = a.lo; 299 return; 300 } 301 r->hi = t >> b; 302 r->lo = (t << (32-b)) | (a.lo >> b); 303 } 304 305 void 306 _rshlv(Vlong *r, Vlong a, int b) 307 { 308 ulong t; 309 310 t = a.hi; 311 if(b >= 32) { 312 r->hi = 0; 313 if(b >= 64) { 314 /* this is illegal re C standard */ 315 r->lo = 0; 316 return; 317 } 318 r->lo = t >> (b-32); 319 return; 320 } 321 if(b <= 0) { 322 r->hi = t; 323 r->lo = a.lo; 324 return; 325 } 326 r->hi = t >> b; 327 r->lo = (t << (32-b)) | (a.lo >> b); 328 } 329 330 void 331 _lshv(Vlong *r, Vlong a, int b) 332 { 333 ulong t; 334 335 t = a.lo; 336 if(b >= 32) { 337 r->lo = 0; 338 if(b >= 64) { 339 /* this is illegal re C standard */ 340 r->hi = 0; 341 return; 342 } 343 r->hi = t << (b-32); 344 return; 345 } 346 if(b <= 0) { 347 r->lo = t; 348 r->hi = a.hi; 349 return; 350 } 351 r->lo = t << b; 352 r->hi = (t >> (32-b)) | (a.hi << b); 353 } 354 355 void 356 _andv(Vlong *r, Vlong a, Vlong b) 357 { 358 r->hi = a.hi & b.hi; 359 r->lo = a.lo & b.lo; 360 } 361 362 void 363 _orv(Vlong *r, Vlong a, Vlong b) 364 { 365 r->hi = a.hi | b.hi; 366 r->lo = a.lo | b.lo; 367 } 368 369 void 370 _xorv(Vlong *r, Vlong a, Vlong b) 371 { 372 r->hi = a.hi ^ b.hi; 373 r->lo = a.lo ^ b.lo; 374 } 375 376 void 377 _vpp(Vlong *l, Vlong *r) 378 { 379 380 l->hi = r->hi; 381 l->lo = r->lo; 382 r->lo++; 383 if(r->lo == 0) 384 r->hi++; 385 } 386 387 void 388 _vmm(Vlong *l, Vlong *r) 389 { 390 391 l->hi = r->hi; 392 l->lo = r->lo; 393 if(r->lo == 0) 394 r->hi--; 395 r->lo--; 396 } 397 398 void 399 _ppv(Vlong *l, Vlong *r) 400 { 401 402 r->lo++; 403 if(r->lo == 0) 404 r->hi++; 405 l->hi = r->hi; 406 l->lo = r->lo; 407 } 408 409 void 410 _mmv(Vlong *l, Vlong *r) 411 { 412 413 if(r->lo == 0) 414 r->hi--; 415 r->lo--; 416 l->hi = r->hi; 417 l->lo = r->lo; 418 } 419 420 void 421 _vasop(Vlong *ret, void *lv, void fn(Vlong*, Vlong, Vlong), int type, Vlong rv) 422 { 423 Vlong t, u; 424 425 u = *ret; 426 switch(type) { 427 default: 428 abort(); 429 break; 430 431 case 1: /* schar */ 432 t.lo = *(schar*)lv; 433 t.hi = t.lo >> 31; 434 fn(&u, t, rv); 435 *(schar*)lv = u.lo; 436 break; 437 438 case 2: /* uchar */ 439 t.lo = *(uchar*)lv; 440 t.hi = 0; 441 fn(&u, t, rv); 442 *(uchar*)lv = u.lo; 443 break; 444 445 case 3: /* short */ 446 t.lo = *(short*)lv; 447 t.hi = t.lo >> 31; 448 fn(&u, t, rv); 449 *(short*)lv = u.lo; 450 break; 451 452 case 4: /* ushort */ 453 t.lo = *(ushort*)lv; 454 t.hi = 0; 455 fn(&u, t, rv); 456 *(ushort*)lv = u.lo; 457 break; 458 459 case 9: /* int */ 460 t.lo = *(int*)lv; 461 t.hi = t.lo >> 31; 462 fn(&u, t, rv); 463 *(int*)lv = u.lo; 464 break; 465 466 case 10: /* uint */ 467 t.lo = *(uint*)lv; 468 t.hi = 0; 469 fn(&u, t, rv); 470 *(uint*)lv = u.lo; 471 break; 472 473 case 5: /* long */ 474 t.lo = *(long*)lv; 475 t.hi = t.lo >> 31; 476 fn(&u, t, rv); 477 *(long*)lv = u.lo; 478 break; 479 480 case 6: /* ulong */ 481 t.lo = *(ulong*)lv; 482 t.hi = 0; 483 fn(&u, t, rv); 484 *(ulong*)lv = u.lo; 485 break; 486 487 case 7: /* vlong */ 488 case 8: /* uvlong */ 489 fn(&u, *(Vlong*)lv, rv); 490 *(Vlong*)lv = u; 491 break; 492 } 493 *ret = u; 494 } 495 496 void 497 _p2v(Vlong *ret, void *p) 498 { 499 long t; 500 501 t = (ulong)p; 502 ret->lo = t; 503 ret->hi = 0; 504 } 505 506 void 507 _sl2v(Vlong *ret, long sl) 508 { 509 long t; 510 511 t = sl; 512 ret->lo = t; 513 ret->hi = t >> 31; 514 } 515 516 void 517 _ul2v(Vlong *ret, ulong ul) 518 { 519 long t; 520 521 t = ul; 522 ret->lo = t; 523 ret->hi = 0; 524 } 525 526 void 527 _si2v(Vlong *ret, int si) 528 { 529 long t; 530 531 t = si; 532 ret->lo = t; 533 ret->hi = t >> 31; 534 } 535 536 void 537 _ui2v(Vlong *ret, uint ui) 538 { 539 long t; 540 541 t = ui; 542 ret->lo = t; 543 ret->hi = 0; 544 } 545 546 void 547 _sh2v(Vlong *ret, long sh) 548 { 549 long t; 550 551 t = (sh << 16) >> 16; 552 ret->lo = t; 553 ret->hi = t >> 31; 554 } 555 556 void 557 _uh2v(Vlong *ret, ulong ul) 558 { 559 long t; 560 561 t = ul & 0xffff; 562 ret->lo = t; 563 ret->hi = 0; 564 } 565 566 void 567 _sc2v(Vlong *ret, long uc) 568 { 569 long t; 570 571 t = (uc << 24) >> 24; 572 ret->lo = t; 573 ret->hi = t >> 31; 574 } 575 576 void 577 _uc2v(Vlong *ret, ulong ul) 578 { 579 long t; 580 581 t = ul & 0xff; 582 ret->lo = t; 583 ret->hi = 0; 584 } 585 586 long 587 _v2sc(Vlong rv) 588 { 589 long t; 590 591 t = rv.lo & 0xff; 592 return (t << 24) >> 24; 593 } 594 595 long 596 _v2uc(Vlong rv) 597 { 598 599 return rv.lo & 0xff; 600 } 601 602 long 603 _v2sh(Vlong rv) 604 { 605 long t; 606 607 t = rv.lo & 0xffff; 608 return (t << 16) >> 16; 609 } 610 611 long 612 _v2uh(Vlong rv) 613 { 614 615 return rv.lo & 0xffff; 616 } 617 618 long 619 _v2sl(Vlong rv) 620 { 621 622 return rv.lo; 623 } 624 625 long 626 _v2ul(Vlong rv) 627 { 628 629 return rv.lo; 630 } 631 632 long 633 _v2si(Vlong rv) 634 { 635 636 return rv.lo; 637 } 638 639 long 640 _v2ui(Vlong rv) 641 { 642 643 return rv.lo; 644 } 645 646 int 647 _testv(Vlong rv) 648 { 649 return rv.lo || rv.hi; 650 } 651 652 int 653 _eqv(Vlong lv, Vlong rv) 654 { 655 return lv.lo == rv.lo && lv.hi == rv.hi; 656 } 657 658 int 659 _nev(Vlong lv, Vlong rv) 660 { 661 return lv.lo != rv.lo || lv.hi != rv.hi; 662 } 663 664 int 665 _ltv(Vlong lv, Vlong rv) 666 { 667 return (long)lv.hi < (long)rv.hi || 668 (lv.hi == rv.hi && lv.lo < rv.lo); 669 } 670 671 int 672 _lev(Vlong lv, Vlong rv) 673 { 674 return (long)lv.hi < (long)rv.hi || 675 (lv.hi == rv.hi && lv.lo <= rv.lo); 676 } 677 678 int 679 _gtv(Vlong lv, Vlong rv) 680 { 681 return (long)lv.hi > (long)rv.hi || 682 (lv.hi == rv.hi && lv.lo > rv.lo); 683 } 684 685 int 686 _gev(Vlong lv, Vlong rv) 687 { 688 return (long)lv.hi > (long)rv.hi || 689 (lv.hi == rv.hi && lv.lo >= rv.lo); 690 } 691 692 int 693 _lov(Vlong lv, Vlong rv) 694 { 695 return lv.hi < rv.hi || 696 (lv.hi == rv.hi && lv.lo < rv.lo); 697 } 698 699 int 700 _lsv(Vlong lv, Vlong rv) 701 { 702 return lv.hi < rv.hi || 703 (lv.hi == rv.hi && lv.lo <= rv.lo); 704 } 705 706 int 707 _hiv(Vlong lv, Vlong rv) 708 { 709 return lv.hi > rv.hi || 710 (lv.hi == rv.hi && lv.lo > rv.lo); 711 } 712 713 int 714 _hsv(Vlong lv, Vlong rv) 715 { 716 return lv.hi > rv.hi || 717 (lv.hi == rv.hi && lv.lo >= rv.lo); 718 } 719