1 module decimal.integrals; 2 3 private import core.bitop : bsr, bsf; 4 private import std.traits: isUnsigned, isSigned, isSomeChar, Unqual, CommonType, Unsigned, Signed; 5 private import core.checkedint: addu, subu, mulu, adds, subs; 6 7 package: 8 9 10 /* ****************************************************************************************************************** */ 11 /* n BIT UNSIGNED IMPLEMENTATION */ 12 /* ****************************************************************************************************************** */ 13 14 15 template MakeUnsigned(int bits) 16 { 17 static if (bits == 8) 18 alias MakeUnsigned = ubyte; 19 else static if (bits == 16) 20 alias MakeUnsigned = ushort; 21 else static if (bits == 32) 22 alias MakeUnsigned = uint; 23 else static if (bits == 64) 24 alias MakeUnsigned = ulong; 25 else static if (bits >= 128) 26 alias MakeUnsigned = unsigned!bits; 27 else 28 static assert(0); 29 } 30 31 32 33 template isCustomUnsigned(T) 34 { 35 enum isCustomUnsigned = is(T: unsigned!bits, int bits); 36 } 37 38 template isAnyUnsigned(T) 39 { 40 enum isAnyUnsigned = isUnsigned!T || isCustomUnsigned!T; 41 } 42 43 template isUnsignedAssignable(T, U) 44 { 45 enum isUnsignedAssignable = isAnyUnsigned!T && isAnyUnsigned!U && T.sizeof >= U.sizeof; 46 } 47 48 struct unsigned(int bits) if (bits >= 128 && (bits & (bits - 1)) == 0) 49 { 50 alias HALF = MakeUnsigned!(bits / 2); 51 52 alias THIS = typeof(this); 53 54 version (LittleEndian) { HALF lo; HALF hi; } else { HALF hi; HALF lo; } 55 56 enum min = THIS(); 57 enum max = THIS(HALF.max, HALF.max); 58 59 60 this(T, U)(auto const ref T hi, auto const ref U lo) 61 if (isUnsignedAssignable!(HALF, T) && isUnsignedAssignable!(HALF, U)) 62 { 63 this.hi = hi; 64 this.lo = lo; 65 } 66 67 this(T)(auto const ref T x) 68 if (isUnsignedAssignable!(HALF, T)) 69 { 70 this.lo = x; 71 } 72 73 this(string s) 74 { 75 assert (s.length, "Empty string"); 76 size_t i = 0; 77 if (s.length > 2 && s[0] == '0' && (s[1] == 'x' || s[1] == 'X')) 78 { 79 i+=2; 80 assert (i < s.length, "Empty hexadecimal string"); 81 while (i < s.length && (s[i] == '0' || s[i] == '_')) 82 ++i; 83 int width = 0; 84 int maxWidth = THIS.sizeof * 8; 85 while (i < s.length) 86 { 87 assert (width < maxWidth, "Overflow"); 88 char c = s[i++]; 89 if (c >= '0' && c <= '9') 90 { 91 this <<= 4; 92 lo |= cast(uint)(c - '0'); 93 width += 4; 94 } 95 else if (c >= 'A' && c <= 'F') 96 { 97 this <<= 4; 98 lo |= cast(uint)(c - 'A' + 10); 99 width += 4; 100 } 101 else if (c >= 'a' && c <= 'f') 102 { 103 this <<= 4; 104 lo |= cast(uint)(c - 'a' + 10); 105 width += 4; 106 } 107 else 108 assert(c == '_', "Invalid character in input string"); 109 } 110 } 111 else 112 { 113 while (i < s.length) 114 { 115 char c = s[i++]; 116 if (c >= '0' && c <= '9') 117 { 118 bool ovf; 119 auto r = fma(this, 10U, cast(uint)(c - '0'), ovf); 120 assert(!ovf, "Overflow"); 121 this = r; 122 } 123 else 124 assert(c == '_', "Invalid character in input string"); 125 } 126 } 127 } 128 129 130 auto ref opAssign(T)(auto const ref T x) 131 if (isUnsignedAssignable!(HALF, T)) 132 { 133 this.lo = x; 134 this.hi = 0U; 135 return this; 136 } 137 138 auto opUnary(string op: "+")() const 139 { 140 return this; 141 } 142 143 auto opUnary(string op: "-")() const 144 { 145 return ++(~this); 146 } 147 148 149 auto opUnary(string op: "~")() const 150 { 151 return THIS(~hi, ~lo); 152 } 153 154 auto ref opUnary(string op:"++")() 155 { 156 ++lo; 157 if (!lo) 158 ++hi; 159 return this; 160 } 161 162 auto ref opUnary(string op:"--")() 163 { 164 --lo; 165 if (lo == HALF.max) 166 --hi; 167 return this; 168 } 169 170 bool opEquals(T)(const T value) const 171 if (isUnsignedAssignable!(HALF, T)) 172 { 173 return hi == 0U && lo == value; 174 } 175 176 bool opEquals(T: THIS)(auto const ref T value) const 177 { 178 return hi == value.hi && lo == value.lo; 179 } 180 181 int opCmp(T)(const T value) const 182 if (isUnsignedAssignable!(HALF, T)) 183 { 184 if (hi) 185 return 1; 186 else if (lo > value) 187 return 1; 188 else if (lo < value) 189 return -1; 190 else 191 return 0; 192 } 193 194 int opCmp(T: THIS)(auto const ref T value) const 195 { 196 if (hi > value.hi) 197 return 1; 198 else if (hi < value.hi) 199 return -1; 200 else if (lo > value.lo) 201 return 1; 202 else if (lo < value.lo) 203 return -1; 204 else 205 return 0; 206 } 207 208 auto opBinary(string op: "|", T: THIS)(auto const ref T value) const 209 { 210 return THIS(this.hi | value.hi, this.lo | value.lo); 211 } 212 213 auto opBinary(string op: "|", T)(auto const ref T value) const 214 if (isUnsignedAssignable!(HALF, T)) 215 { 216 return THIS(this.hi, this.lo | value); 217 } 218 219 auto ref opOpAssign(string op: "|", T: THIS)(auto const ref T value) 220 { 221 this.hi |= value.hi; 222 this.lo |= value.lo; 223 return this; 224 } 225 226 auto ref opOpAssign(string op: "|", T)(auto const ref T value) 227 if (isUnsignedAssignable!(HALF, T)) 228 { 229 this.lo |= value; 230 return this; 231 } 232 233 auto opBinary(string op: "&", T: THIS)(auto const ref T value) const 234 { 235 return THIS(this.hi & value.hi, this.lo & value.lo); 236 } 237 238 auto opBinary(string op: "&", T)(auto const ref T value) const 239 if (isUnsignedAssignable!(HALF, T)) 240 { 241 return THIS(0U, this.lo & value); 242 } 243 244 auto ref opOpAssign(string op: "&", T: THIS)(auto const ref T value) 245 { 246 this.hi &= value.hi; 247 this.lo &= value.lo; 248 return this; 249 } 250 251 auto ref opOpAssign(string op: "&", T)(auto const ref T value) 252 if (isUnsignedAssignable!(HALF, T)) 253 { 254 this.hi = 0U; 255 this.lo &= value; 256 return this; 257 } 258 259 auto opBinary(string op: "^", T: THIS)(auto const ref T value) const 260 { 261 return THIS(this.hi ^ value.hi, this.lo ^ value.lo); 262 } 263 264 auto opBinary(string op: "^", T)(auto const ref T value) const 265 if (isUnsignedAssignable!(HALF, T)) 266 { 267 return THIS(this.hi ^ 0UL, this.lo ^ value); 268 } 269 270 auto ref opOpAssign(string op: "^", T: THIS)(auto const ref T value) 271 { 272 this.hi ^= value.hi; 273 this.lo ^= value.lo; 274 return this; 275 } 276 277 auto ref opOpAssign(string op: "^", T)(auto const ref T value) 278 if (isUnsignedAssignable!(HALF, T)) 279 { 280 this.hi ^= 0U; 281 this.lo ^= value; 282 return this; 283 } 284 285 auto opBinary(string op)(const int shift) const 286 if (op == ">>" || op == ">>>") 287 in 288 { 289 assert(shift >= 0 && shift < THIS.sizeof * 8); 290 } 291 body 292 { 293 enum int halfBits = HALF.sizeof * 8; 294 THIS ret = void; 295 296 if (shift == halfBits) 297 { 298 ret.lo = this.hi; 299 ret.hi = 0U; 300 } 301 else if (shift > halfBits) 302 { 303 ret.lo = this.hi >>> (shift - halfBits); 304 ret.hi = 0U; 305 } 306 else if (shift != 0) 307 { 308 ret.lo = (this.hi << (halfBits - shift)) | (this.lo >>> shift); 309 ret.hi = this.hi >>> shift; 310 } 311 else 312 ret = this; 313 return ret; 314 } 315 316 auto ref opOpAssign(string op)(const int shift) 317 if (op == ">>" || op == ">>>") 318 in 319 { 320 assert(shift >= 0 && shift < THIS.sizeof * 8); 321 } 322 body 323 { 324 enum int halfBits = HALF.sizeof * 8; 325 if (shift == halfBits) 326 { 327 lo = hi; 328 hi = 0U; 329 } 330 else if (shift > halfBits) 331 { 332 lo = hi >>> (shift - halfBits); 333 hi = 0U; 334 } 335 else if (shift != 0) 336 { 337 lo = (hi << (halfBits - shift)) | (lo >>> shift); 338 hi >>>= shift; 339 } 340 return this; 341 } 342 343 auto opBinary(string op)(const int shift) const 344 if (op == "<<") 345 in 346 { 347 assert(shift >= 0 && shift < THIS.sizeof * 8); 348 } 349 body 350 { 351 THIS ret = void; 352 enum int halfBits = HALF.sizeof * 8; 353 354 if (shift == halfBits) 355 { 356 ret.hi = this.lo; 357 ret.lo = 0U; 358 } 359 else if (shift > halfBits) 360 { 361 ret.hi = this.lo << (shift - halfBits); 362 ret.lo = 0U; 363 } 364 else if (shift != 0) 365 { 366 ret.hi = (this.lo >>> (halfBits - shift)) | (this.hi << shift); 367 ret.lo = this.lo << shift; 368 } 369 else 370 ret = this; 371 return ret; 372 } 373 374 auto ref opOpAssign(string op)(const int shift) 375 if (op == "<<") 376 in 377 { 378 assert(shift >= 0 && shift < THIS.sizeof * 8); 379 } 380 body 381 { 382 enum int halfBits = HALF.sizeof * 8; 383 384 if (shift == halfBits) 385 { 386 hi = lo; 387 lo = 0U; 388 } 389 else if (shift > halfBits) 390 { 391 hi = lo << (shift - halfBits); 392 lo = 0U; 393 } 394 else if (shift != 0) 395 { 396 hi = (lo >>> (halfBits - shift)) | (hi << shift); 397 lo <<= shift; 398 } 399 return this; 400 } 401 402 auto opBinary(string op :"+", T)(const T value) const 403 if (isUnsignedAssignable!(HALF, T)) 404 { 405 THIS ret = this; 406 ret.hi += xadd(ret.lo, value); 407 return ret; 408 } 409 410 auto ref opOpAssign(string op :"+", T)(const T value) 411 if (isUnsignedAssignable!(HALF, T)) 412 { 413 hi += xadd(lo, value); 414 return this; 415 } 416 417 auto opBinary(string op :"+", T: THIS)(const T value) const 418 { 419 THIS ret = this; 420 ret.hi += xadd(ret.lo, value.lo); 421 ret.hi += value.hi; 422 return ret; 423 } 424 425 auto ref opOpAssign(string op :"+", T: THIS)(auto const ref T value) 426 { 427 hi += xadd(this.lo, value.lo); 428 hi += value.hi; 429 return this; 430 } 431 432 auto opBinary(string op :"-", T)(const T value) const 433 if (isUnsignedAssignable!(HALF, T)) 434 { 435 THIS ret = this; 436 ret.hi -= xsub(ret.lo, value); 437 return ret; 438 } 439 440 auto ref opOpAssign(string op :"-", T)(const T value) 441 if (isUnsignedAssignable!(HALF, T)) 442 { 443 hi -= xsub(lo, value); 444 return this; 445 } 446 447 auto opBinary(string op :"-", T: THIS)(const T value) const 448 { 449 THIS ret = this; 450 ret.hi -= xsub(ret.lo, value.lo); 451 ret.hi -= value.hi; 452 return ret; 453 } 454 455 auto ref opOpAssign(string op :"-", T: THIS)(auto const ref T value) 456 { 457 this.hi -= xsub(this.lo, value.lo); 458 this.hi -= value.hi; 459 return this; 460 } 461 462 auto opBinary(string op :"*", T)(const T value) const 463 if (isUnsignedAssignable!(HALF, T)) 464 { 465 THIS ret = xmul(this.lo, value); 466 ret.hi += this.hi * value; 467 return ret; 468 } 469 470 auto ref opOpAssign(string op :"*", T)(const T value) 471 if (isUnsignedAssignable!(HALF, T)) 472 { 473 THIS ret = xmul(this.lo, value); 474 ret.hi += this.hi * value; 475 return this = ret; 476 } 477 478 auto opBinary(string op :"*", T: THIS)(const T value) const 479 { 480 auto ret = xmul(lo, value.lo); 481 ret.hi += this.hi * value.lo + this.lo * value.hi; 482 return ret; 483 } 484 485 auto ref opOpAssign(string op :"*", T: THIS)(const T value) 486 { 487 auto ret = xmul(lo, value.lo); 488 ret.hi += this.hi * value.lo + this.lo * value.hi; 489 return this = ret; 490 } 491 492 auto opBinary(string op :"/", T)(const T value) const 493 if (isUnsignedAssignable!(HALF, T)) 494 { 495 THIS q = this; 496 divrem(q, value); 497 return q; 498 } 499 500 auto ref opOpAssign(string op :"/", T)(const T value) 501 if (isUnsignedAssignable!(HALF, T)) 502 { 503 divrem(this, value); 504 } 505 506 auto opBinary(string op :"/", T: THIS)(const T value) const 507 { 508 THIS q = this; 509 divrem(q, value); 510 return q; 511 } 512 513 auto ref opOpAssign(string op :"/", T: THIS)(const T value) 514 { 515 divrem(this, value); 516 } 517 518 auto opBinary(string op :"%", T)(const T value) const 519 if (isUnsignedAssignable!(HALF, T)) 520 { 521 THIS q = this; 522 return divrem(q, value); 523 } 524 525 auto ref opOpAssign(string op :"%", T)(const T value) 526 if (isUnsignedAssignable!(HALF, T)) 527 { 528 THIS q = this; 529 return this = divrem(q, value); 530 } 531 532 auto opBinary(string op :"%", T: THIS)(const T value) const 533 { 534 THIS q = this; 535 return divrem(q, value); 536 } 537 538 auto ref opOpAssign(string op :"%", T: THIS)(const T value) 539 { 540 THIS q = this; 541 return this = divrem(q, value); 542 } 543 544 auto opCast(T)() const 545 { 546 static if (is(T: bool)) 547 return cast(T)(lo | hi); 548 else static if (isSomeChar!T) 549 return cast(T)lo; 550 else static if (isUnsigned!T) 551 return cast(T)lo; 552 else static if (isUnsignedAssignable!(HALF, T)) 553 return cast(T)lo; 554 else static if (is(T: THIS)) 555 return this; 556 else 557 static assert("Cannot cast '" ~ Unqual!THIS.stringof ~ "' to '" ~ Unqual!T.stringof ~ "'"); 558 } 559 560 string toString() 561 { 562 char[bits / 3 + 1] buffer; 563 size_t i = buffer.length; 564 THIS v = this; 565 do 566 { 567 auto r = divrem(v, 10U); 568 buffer[--i] = cast(char)('0' + cast(uint)r); 569 } while (v != 0U); 570 return buffer[i .. $].dup; 571 } 572 573 } 574 575 alias uint128 = unsigned!128; 576 alias uint256 = unsigned!256; 577 578 unittest 579 { 580 import std.typetuple; 581 import std.random; 582 583 auto gen = Random(); 584 585 T rnd(T)() 586 { 587 static if (is(T == uint)) 588 return uniform(1U, uint.max, gen); 589 else static if (is(T == ulong)) 590 return uniform(1UL, ulong.max, gen); 591 else 592 return T(rnd!(T.HALF)(), rnd!(T.HALF)()); 593 594 } 595 596 597 598 599 foreach (T; TypeTuple!(unsigned!128, unsigned!256, unsigned!512)) 600 { 601 enum zero = T(0U); 602 enum one = T(1U); 603 enum two = T(2U); 604 enum three = T(3U); 605 enum big = T(0x3333333333U, 0x4444444444U); 606 enum next = T(1U, 0U); 607 enum previous = T(0U, T.HALF.max); 608 609 assert (zero == zero); 610 assert (zero <= zero); 611 assert (zero >= zero); 612 assert (zero < one); 613 assert (zero < two); 614 assert (zero < three); 615 assert (zero < big); 616 assert (zero < next); 617 assert (zero < previous); 618 619 assert (one > zero); 620 assert (one >= zero); 621 assert (one >= one); 622 assert (one == one); 623 assert (one < two); 624 assert (one < three); 625 assert (one < big); 626 assert (one < next); 627 assert (one < previous); 628 629 assert (two > zero); 630 assert (two >= zero); 631 assert (two >= one); 632 assert (two > one); 633 assert (two == two); 634 assert (two < three); 635 assert (two < big); 636 assert (two < next); 637 assert (two < previous); 638 639 assert (three > zero); 640 assert (three >= zero); 641 assert (three >= one); 642 assert (three > one); 643 assert (three >= two); 644 assert (three == three); 645 assert (three < big); 646 assert (three < next); 647 assert (three < previous); 648 649 assert (big > zero); 650 assert (big >= zero); 651 assert (big >= one); 652 assert (big > one); 653 assert (big >= two); 654 assert (big >= three); 655 assert (big == big); 656 assert (big > next); 657 assert (big > previous); 658 659 assert (next > zero); 660 assert (next >= zero); 661 assert (next >= one); 662 assert (next > one); 663 assert (next >= two); 664 assert (next >= three); 665 assert (next <= big); 666 assert (next == next); 667 assert (next > previous); 668 669 assert (previous > zero); 670 assert (previous >= zero); 671 assert (previous >= one); 672 assert (previous > one); 673 assert (previous >= two); 674 assert (previous >= three); 675 assert (previous <= big); 676 assert (previous <= next); 677 assert (previous == previous); 678 679 assert (zero == 0U); 680 assert (zero <= 0U); 681 assert (zero >= 0U); 682 assert (zero < 1U); 683 assert (zero < 2U); 684 assert (zero < 3U); 685 assert (zero < ulong.max); 686 687 assert (one > 0U); 688 assert (one >= 0U); 689 assert (one >= 1U); 690 assert (one == 1U); 691 assert (one < 2U); 692 assert (one < 3U); 693 assert (one < ulong.max); 694 695 assert (two > 0U); 696 assert (two >= 0U); 697 assert (two >= 1U); 698 assert (two > 1U); 699 assert (two == 2U); 700 assert (two < 3U); 701 assert (two < ulong.max); 702 703 assert (three > 0U); 704 assert (three >= 0U); 705 assert (three >= 1U); 706 assert (three > 1U); 707 assert (three >= 2U); 708 assert (three == 3U); 709 assert (three < ulong.max); 710 711 assert (big > 0U); 712 assert (big >= 0U); 713 assert (big >= 1U); 714 assert (big > 1U); 715 assert (big >= 2U); 716 assert (big >= 3U); 717 assert (big > ulong.max); 718 719 assert (next > 0U); 720 assert (next >= 0U); 721 assert (next >= 1U); 722 assert (next > 1U); 723 assert (next >= 2U); 724 assert (next >= 3U); 725 assert (next > ulong.max); 726 727 assert (previous > 0U); 728 assert (previous >= 0U); 729 assert (previous >= 1U); 730 assert (previous > 1U); 731 assert (previous >= 2U); 732 assert (previous >= 3U); 733 assert (previous == previous); 734 735 assert (~~zero == zero); 736 assert (~~one == one); 737 assert (~~two == two); 738 assert (~~three == three); 739 assert (~~big == big); 740 assert (~~previous == previous); 741 assert (~~next == next); 742 743 assert ((one | one) == one); 744 assert ((one | zero) == one); 745 assert ((one & one) == one); 746 assert ((one & zero) == zero); 747 assert ((big & ~big) == zero); 748 assert ((one ^ one) == zero); 749 assert ((big ^ big) == zero); 750 assert ((one ^ zero) == one); 751 752 assert(big >> 0 == big); 753 assert(big << 0 == big); 754 755 assert(big << 1 > big); 756 assert(big >> 1 < big); 757 758 auto x = big << 3; 759 auto y = x >> 3; 760 assert((big << 3) >> 3 == big); 761 assert((one << 127) >> 127 == one); 762 assert((one << 64) >> 64 == one); 763 764 assert (zero + zero == zero); 765 assert (zero + one == one); 766 assert (zero + two == two); 767 assert (zero + three == three); 768 assert (zero + big == big); 769 assert (zero + previous == previous); 770 assert (zero + next == next); 771 772 assert (one + zero == one); 773 assert (one + one == two); 774 assert (one + two == three); 775 assert (one + three > three); 776 assert (one + big > big); 777 assert (one + previous == next); 778 assert (one + next > next); 779 780 assert (two + zero == two); 781 assert (two + one == three); 782 assert (two + two > three); 783 assert (two + three > three); 784 assert (two + big > big); 785 assert (two + previous > next); 786 assert (two + next > next); 787 788 assert (three + zero == three); 789 assert (three + one > three); 790 assert (three + two > three); 791 assert (three + three > three); 792 assert (three + big > big); 793 assert (three + previous > next); 794 assert (three + next > next); 795 796 assert (big + zero == big); 797 assert (big + one > big); 798 assert (big + two > big + one); 799 assert (big + three > big + two); 800 assert (big + big > big); 801 assert (big + previous > next); 802 assert (big + next > next); 803 804 assert (previous + zero == previous); 805 assert (previous + one == next); 806 assert (previous + two > next); 807 assert (previous + three == next + two); 808 assert (previous + big > big); 809 assert (previous + previous > previous); 810 assert (previous + next > previous); 811 812 assert (next + zero == next); 813 assert (next + one > next); 814 assert (next + two > next); 815 assert (next + three >= next + two); 816 assert (next + big > big); 817 assert (next + previous > next); 818 assert (next + next > next); 819 820 assert (zero + 0U == zero); 821 assert (zero + 1U == one); 822 assert (zero + 2U == two); 823 assert (zero + 3U == three); 824 825 assert (one + 0U == one); 826 assert (one + 1U == two); 827 assert (one + 2U == three); 828 assert (one + 3U > three); 829 830 assert (two + 0U == two); 831 assert (two + 1U == three); 832 assert (two + 2U > three); 833 assert (two + 3U > three); 834 835 assert (three + 0U == three); 836 assert (three + 1U > three); 837 assert (three + 2U > three); 838 assert (three + 3U > three); 839 840 assert (big + 0U == big); 841 assert (big + 1U > big); 842 assert (big + 2U > big + 1U); 843 assert (big + 3U > big + 2U); 844 845 assert (previous + 0U == previous); 846 assert (previous + 1U == next); 847 assert (previous + 2U > next); 848 assert (previous + 3U == next + 2U); 849 850 assert (next + 0U == next); 851 assert (next + 1U > next); 852 assert (next + 2U > next); 853 assert (next + 3U >= next + two); 854 855 assert (zero - zero == zero); 856 assert (one - zero == one); 857 assert (two - zero == two); 858 assert (three - zero == three); 859 assert (big - zero == big); 860 assert (previous - zero == previous); 861 assert (next - zero == next); 862 863 assert (one - one == zero); 864 assert (two - one == one); 865 assert (three - one == two); 866 assert (big - one < big); 867 assert (previous - one < previous); 868 assert (next - one == previous); 869 870 assert (two - two == zero); 871 assert (three - two == one); 872 assert (big - two < big); 873 assert (previous - two < previous); 874 assert (next - two < previous); 875 876 assert (three - three == zero); 877 assert (big - three < big); 878 assert (previous - three < previous); 879 assert (next - three < previous); 880 881 assert (big - big == zero); 882 assert (next - previous == one); 883 884 assert (one - 1U == zero); 885 assert (two - 1U == one); 886 assert (three - 1U == two); 887 assert (big - 1U < big); 888 assert (previous - 1U < previous); 889 assert (next - 1U == previous); 890 891 assert (two - 2U == zero); 892 assert (three - 2U == one); 893 assert (big - 2U < big); 894 assert (previous - 2U < previous); 895 assert (next - 2U < previous); 896 897 assert (three - 3U == zero); 898 assert (big - 3U < big); 899 assert (previous - 3U < previous); 900 assert (next - 3U < previous); 901 902 T test = zero; 903 assert (++test == one); 904 assert (++test == two); 905 assert (++test == three); 906 test = big; 907 assert (++test > big); 908 test = previous; 909 assert (++test == next); 910 test = three; 911 assert (--test == two); 912 assert (--test == one); 913 assert (--test == zero); 914 test = big; 915 assert (--test < big); 916 test = next; 917 assert (--test == previous); 918 919 assert (-zero == zero); 920 assert (-(-zero) == zero); 921 assert (-(-one) == one); 922 assert (-(-two) == two); 923 assert (-(-three) == three); 924 assert (-(-big) == big); 925 assert (-(-previous) == previous); 926 assert (-(-next) == next); 927 928 929 for(auto i = 0; i < 10; ++i) 930 { 931 T a = rnd!T(); 932 T b = rnd!T(); 933 T.HALF c = rnd!(T.HALF)(); 934 ulong d = rnd!ulong(); 935 uint e = rnd!uint(); 936 937 T result = a / b; 938 T remainder = a % b; 939 940 assert (result * b + remainder == a); 941 942 result = a / c; 943 remainder = a % c; 944 945 assert (result * c + remainder == a); 946 947 result = a / d; 948 remainder = a % d; 949 950 assert (result * d + remainder == a); 951 952 result = a / e; 953 remainder = a % e; 954 955 assert (result * e + remainder == a); 956 } 957 } 958 959 } 960 961 962 963 /* ****************************************************************************************************************** */ 964 /* INTEGRAL UTILITY FUNCTIONS */ 965 /* ****************************************************************************************************************** */ 966 967 @safe pure nothrow @nogc 968 uint xadd(ref uint x, const uint y) 969 { 970 bool ovf; 971 x = addu(x, y, ovf); 972 return ovf ? 1 : 0; 973 } 974 975 @safe pure nothrow @nogc 976 uint xadd(ref ulong x, const ulong y) 977 { 978 bool ovf; 979 x = addu(x, y, ovf); 980 return ovf ? 1 : 0; 981 } 982 983 @safe pure nothrow @nogc 984 uint xadd(ref ulong x, const uint y) 985 { 986 return xadd(x, cast(ulong)y); 987 } 988 989 uint xadd(T)(ref T x, auto const ref T y) 990 if (isCustomUnsigned!T) 991 { 992 auto carry = xadd(x.lo, y.lo); 993 carry = xadd(x.hi, carry); 994 return xadd(x.hi, y.hi) + carry; 995 } 996 997 uint xadd(T, U)(ref T x, auto const ref U y) 998 if (isCustomUnsigned!T && isUnsignedAssignable!(T.HALF, U)) 999 { 1000 auto carry = xadd(x.lo, y); 1001 return xadd(x.hi, carry); 1002 } 1003 1004 @safe pure nothrow @nogc 1005 uint xsub(ref uint x, const uint y) 1006 { 1007 bool ovf; 1008 x = subu(x, y, ovf); 1009 return ovf ? 1 : 0; 1010 } 1011 1012 @safe pure nothrow @nogc 1013 uint xsub(ref ulong x, const ulong y) 1014 { 1015 bool ovf; 1016 x = subu(x, y, ovf); 1017 return ovf ? 1 : 0; 1018 } 1019 1020 @safe pure nothrow @nogc 1021 uint xsub(ref ulong x, const uint y) 1022 { 1023 return xsub(x, cast(ulong)y); 1024 } 1025 1026 @safe pure nothrow @nogc 1027 uint xsub(T)(ref T x, auto const ref T y) 1028 if (isCustomUnsigned!T) 1029 { 1030 auto carry = xsub(x.lo, y.lo); 1031 carry = xsub(x.hi, carry); 1032 return xsub(x.hi, y.hi) + carry; 1033 } 1034 1035 @safe pure nothrow @nogc 1036 uint xsub(T, U)(ref T x, auto const ref U y) 1037 if (isCustomUnsigned!T && isUnsignedAssignable!(T.HALF, U)) 1038 { 1039 auto carry = xsub(x.lo, y); 1040 return xsub(x.hi, carry); 1041 } 1042 1043 @safe pure nothrow @nogc 1044 uint fma(const uint x, const uint y, const uint z, out bool overflow) 1045 { 1046 auto result = mulu(x, y, overflow); 1047 return addu(result, z, overflow); 1048 } 1049 1050 @safe pure nothrow @nogc 1051 ulong fma(const ulong x, const ulong y, const ulong z, ref bool overflow) 1052 { 1053 auto result = mulu(x, y, overflow); 1054 return addu(result, z, overflow); 1055 } 1056 1057 @safe pure nothrow @nogc 1058 ulong fma(const ulong x, const uint y, const uint z, ref bool overflow) 1059 { 1060 auto result = mulu(x, cast(ulong)y, overflow); 1061 return addu(result, cast(ulong)z, overflow); 1062 } 1063 1064 @safe pure nothrow @nogc 1065 T fma(T)(auto const ref T x, auto const ref T y, auto const ref T z, ref bool overflow) 1066 if (isCustomUnsigned!T) 1067 { 1068 auto result = mulu(x, y, overflow); 1069 if (xadd(result, z)) 1070 overflow = true; 1071 return result; 1072 } 1073 1074 @safe pure nothrow @nogc 1075 T fma(T, U)(auto const ref T x, auto const ref U y, auto const ref U z, ref bool overflow) 1076 if (isCustomUnsigned!T && isUnsignedAssignable!(T.HALF, U)) 1077 { 1078 auto result = mulu(x, y, overflow); 1079 if (xadd(result, z)) 1080 overflow = true; 1081 return result; 1082 } 1083 1084 1085 @safe pure nothrow @nogc 1086 ulong xmul(const uint x, const uint y) 1087 { 1088 return cast(ulong)x * y; 1089 } 1090 1091 @safe pure nothrow @nogc 1092 ulong xsqr(const uint x) 1093 { 1094 return cast(ulong)x * x; 1095 } 1096 1097 @safe pure nothrow @nogc 1098 uint128 xmul(const ulong x, const ulong y) 1099 { 1100 if (x == 0 || y == 0) 1101 return uint128.min; 1102 if (x == 1) 1103 return uint128(y); 1104 if (y == 1) 1105 return uint128(x); 1106 if ((x & (x - 1)) == 0) 1107 return uint128(y) << ctz(x); 1108 if ((y & (y - 1)) == 0) 1109 return uint128(x) << ctz(y); 1110 if (x == y) 1111 return xsqr(x); 1112 1113 1114 immutable xlo = cast(uint)x; 1115 immutable xhi = cast(uint)(x >>> 32); 1116 immutable ylo = cast(uint)y; 1117 immutable yhi = cast(uint)(y >>> 32); 1118 1119 ulong t = xmul(xlo, ylo); 1120 ulong w0 = cast(uint)t; 1121 ulong k = t >>> 32; 1122 1123 t = xmul(xhi, ylo) + k; 1124 ulong w1 = cast(uint)t; 1125 ulong w2 = t >>> 32; 1126 1127 t = xmul(xlo, yhi) + w1; 1128 k = t >>> 32; 1129 1130 return uint128(xmul(xhi, yhi) + w2 + k, (t << 32) + w0); 1131 } 1132 1133 @safe pure nothrow @nogc 1134 uint128 xsqr(const ulong x) 1135 { 1136 immutable xlo = cast(uint)x; 1137 immutable xhi = cast(uint)(x >>> 32); 1138 immutable hilo = xmul(xlo, xhi); 1139 1140 ulong t = xsqr(xlo); 1141 ulong w0 = cast(uint)t; 1142 ulong k = t >>> 32; 1143 1144 t = hilo + k; 1145 ulong w1 = cast(uint)t; 1146 ulong w2 = t >>> 32; 1147 1148 t = hilo + w1; 1149 k = t >>> 32; 1150 1151 return uint128(xsqr(xhi) + w2 + k, (t << 32) + w0); 1152 } 1153 1154 @safe pure nothrow @nogc 1155 uint128 xmul(const ulong x, const uint y) 1156 { 1157 if (x == 0 || y == 0) 1158 return uint128.min; 1159 if (x == 1) 1160 return uint128(y); 1161 if (y == 1) 1162 return uint128(x); 1163 if ((x & (x - 1)) == 0) 1164 return uint128(y) << ctz(x); 1165 if ((y & (y - 1)) == 0) 1166 return uint128(x) << ctz(y); 1167 1168 immutable xlo = cast(uint)x; 1169 immutable xhi = cast(uint)(x >>> 32); 1170 1171 ulong t = xmul(xlo, y); 1172 ulong w0 = cast(uint)t; 1173 ulong k = t >>> 32; 1174 1175 t = xmul(xhi, y) + k; 1176 ulong w1 = cast(uint)t; 1177 ulong w2 = t >>> 32; 1178 1179 return uint128(w2, (w1 << 32) + w0); 1180 } 1181 1182 1183 auto xmul(T)(auto const ref T x, auto const ref T y) 1184 if (isCustomUnsigned!T) 1185 { 1186 enum bits = T.sizeof * 8; 1187 enum rbits = bits * 2; 1188 alias R = unsigned!rbits; 1189 1190 if (x == 0U || y == 0U) 1191 return R.min; 1192 if (x == 1U) 1193 return R(y); 1194 if (y == 1U) 1195 return R(x); 1196 if ((x & (x - 1U)) == 0U) 1197 return R(y) << ctz(x); 1198 if ((y & (y - 1U)) == 0U) 1199 return R(x) << ctz(y); 1200 if (x == y) 1201 return xsqr(x); 1202 1203 auto t = xmul(x.lo, y.lo); 1204 auto w0 = t.lo; 1205 auto k = t.hi; 1206 1207 t = xmul(x.hi, y.lo) + k; 1208 auto w2 = t.hi; 1209 1210 t = xmul(x.lo, y.hi) + t.lo; 1211 1212 return R(xmul(x.hi, y.hi) + w2 + t.hi, (t << (bits / 2)) + w0); 1213 } 1214 1215 T mulu(T)(auto const ref T x, auto const ref T y, ref bool overflow) 1216 if (isCustomUnsigned!T) 1217 { 1218 enum bits = T.sizeof * 8; 1219 1220 if (x == 0U || y == 0U) 1221 return T.min; 1222 if (x == 1) 1223 return y; 1224 if (y == 1) 1225 return x; 1226 if ((x & (x - 1)) == 0U) 1227 { 1228 auto lz = clz(y); 1229 auto shift = ctz(x); 1230 if (lz < shift) 1231 overflow = true; 1232 return y << shift; 1233 } 1234 if ((y & (y - 1)) == 0U) 1235 { 1236 auto lz = clz(x); 1237 auto shift = ctz(y); 1238 if (lz < shift) 1239 overflow = true; 1240 return x << shift; 1241 } 1242 if (x == y) 1243 return sqru(x, overflow); 1244 1245 auto t = xmul(x.lo, y.lo); 1246 auto w0 = t.lo; 1247 auto k = t.hi; 1248 1249 t = xmul(x.hi, y.lo) + k; 1250 auto w2 = t.hi; 1251 1252 t = xmul(x.lo, y.hi) + t.lo; 1253 1254 if (w2 || t.hi) 1255 overflow = true; 1256 else if (xmul(x.hi, y.hi)) 1257 overflow = true; 1258 1259 return (t << (bits / 2)) + w0; 1260 } 1261 1262 auto xsqr(T)(auto const ref T x) 1263 if (isCustomUnsigned!T) 1264 { 1265 1266 enum bits = T.sizeof * 8; 1267 enum rbits = bits * 2; 1268 alias R = unsigned!rbits; 1269 1270 immutable hilo = xmul(x.lo, x.hi); 1271 1272 auto t = xsqr(x.lo); 1273 auto w0 = t.lo; 1274 auto k = t.hi; 1275 1276 t = hilo + k; 1277 auto w2 = t.hi; 1278 1279 t = hilo + t.lo; 1280 1281 return R(xsqr(x.hi) + w2 + t.hi, (t << (bits / 2)) + w0); 1282 } 1283 1284 T sqru(T)(auto const ref T x, ref bool overflow) 1285 if (isCustomUnsigned!T) 1286 { 1287 enum bits = T.sizeof * 8; 1288 1289 immutable hilo = xmul(x.lo, x.hi); 1290 auto t = xsqr(x.lo); 1291 auto w0 = t.lo; 1292 auto k = t.hi; 1293 1294 t = hilo + k; 1295 auto w2 = t.hi; 1296 1297 t = hilo + t.lo; 1298 1299 if (w2 || t.hi) 1300 overflow = true; 1301 else if (xhi) 1302 overflow = true; 1303 1304 return (t << (bits / 2)) + w0; 1305 } 1306 1307 auto xmul(T, U)(auto const ref T x, auto const ref U y) 1308 if (isCustomUnsigned!T && isUnsignedAssignable!(T.HALF, U)) 1309 { 1310 1311 enum bits = T.sizeof * 8; 1312 enum rbits = bits * 2; 1313 alias R = unsigned!rbits; 1314 1315 if (x == 0U || y == 0U) 1316 return R.min; 1317 if (x == 1U) 1318 return R(y); 1319 if (y == 1U) 1320 return R(x); 1321 if ((x & (x - 1U)) == 0U) 1322 return R(y) << ctz(x); 1323 if ((y & (y - 1U)) == 0U) 1324 return R(x) << ctz(y); 1325 1326 auto t = xmul(x.lo, y); 1327 auto w0 = t.lo; 1328 auto k = t.hi; 1329 1330 t = xmul(x.hi, y) + k; 1331 auto w2 = t.hi; 1332 1333 t = t.lo; 1334 1335 return R(w2, (t << (bits / 2)) + w0); 1336 } 1337 1338 T mulu(T, U)(auto const ref T x, auto const ref U y, ref bool overflow) 1339 if (isCustomUnsigned!T && isUnsignedAssignable!(T.HALF, U)) 1340 { 1341 1342 enum bits = T.sizeof * 8; 1343 1344 if (x == 0U || y == 0U) 1345 return T.min; 1346 if (x == 1U) 1347 return T(y); 1348 if (y == 1U) 1349 return x; 1350 if ((x & (x - 1U)) == 0U) 1351 { 1352 auto yy = T(y); 1353 auto lz = clz(y); 1354 auto shift = ctz(x); 1355 if (lz < shift) 1356 overflow = true; 1357 return yy << shift; 1358 } 1359 if ((y & (y - 1)) == 0U) 1360 { 1361 auto lz = clz(x); 1362 auto shift = ctz(y); 1363 if (lz < shift) 1364 overflow = true; 1365 return x << shift; 1366 } 1367 1368 auto t = xmul(x.lo, y); 1369 auto w0 = t.lo; 1370 auto k = t.hi; 1371 1372 t = xmul(x.hi, y) + k; 1373 1374 if (t.hi) 1375 overflow = true; 1376 1377 t = t.lo; 1378 1379 return (t << (bits / 2)) + w0; 1380 } 1381 1382 @safe pure nothrow @nogc 1383 auto clz(const uint x) 1384 { 1385 return x ? 31 - bsr(x) : 0; 1386 } 1387 1388 @safe pure nothrow @nogc 1389 auto clz(const ulong x) 1390 { 1391 if (!x) 1392 return 64; 1393 static if (is(size_t == ulong)) 1394 return 63 - bsr(x); 1395 else static if(is(size_t == uint)) 1396 { 1397 immutable hi = cast(uint)(x >> 32); 1398 if (hi) 1399 return 31 - bsr(hi); 1400 else 1401 return 63 - bsr(cast(uint)x); 1402 } 1403 else 1404 static assert(0); 1405 } 1406 1407 auto clz(T)(auto const ref T x) 1408 if (isCustomUnsigned!T) 1409 { 1410 enum bits = T.sizeof * 8; 1411 auto ret = clz(x.hi); 1412 return ret == bits / 2 ? ret + clz(x.lo) : ret; 1413 } 1414 1415 @safe pure nothrow @nogc 1416 auto ctz(const uint x) 1417 { 1418 return x ? bsf(x) : 0; 1419 } 1420 1421 @safe pure nothrow @nogc 1422 auto ctz(const ulong x) 1423 { 1424 if (!x) 1425 return 64; 1426 static if (is(size_t == ulong)) 1427 return bsf(x); 1428 else static if (is(size_t == uint)) 1429 { 1430 immutable lo = cast(uint)x; 1431 if (lo) 1432 return bsf(lo); 1433 else 1434 return bsf(cast(uint)(x >> 32)) + 32; 1435 } 1436 else 1437 static assert(0); 1438 } 1439 1440 auto ctz(T)(auto const ref T x) 1441 if (isCustomUnsigned!T) 1442 { 1443 enum bits = T.sizeof * 8; 1444 auto ret = ctz(x.lo); 1445 return ret == bits / 2 ? ret + ctz(x.hi) : ret; 1446 } 1447 1448 bool ispow2(T)(auto const ref T x) 1449 if (isAnyUnsigned!T) 1450 { 1451 return x != 0U && (x & (x - 1U)) == 0; 1452 } 1453 1454 bool ispow10(T)(auto const ref T x) 1455 if (isAnyUnsigned!T) 1456 { 1457 if (x == 0U) 1458 return false; 1459 1460 for (size_t i = 0; i < pow10!T.length; ++i) 1461 { 1462 if (x == pow10!T[i]) 1463 return true; 1464 else if (x < pow10!T[i]) 1465 return false; 1466 } 1467 return false; 1468 } 1469 1470 1471 1472 1473 @safe pure nothrow @nogc 1474 uint divrem(ref uint x, const uint y) 1475 { 1476 uint ret = x % y; 1477 x /= y; 1478 return ret; 1479 } 1480 1481 @safe pure nothrow @nogc 1482 ulong divrem(ref ulong x, const ulong y) 1483 { 1484 ulong ret = x % y; 1485 x /= y; 1486 return ret; 1487 } 1488 1489 @safe pure nothrow @nogc 1490 ulong divrem(ref ulong x, const uint y) 1491 { 1492 ulong ret = x % y; 1493 x /= y; 1494 return ret; 1495 } 1496 1497 T divrem(T)(ref T x, auto const ref T y) 1498 if (isCustomUnsigned!T) 1499 { 1500 Unqual!T r; 1501 int shift; 1502 1503 if (!x.hi) 1504 { 1505 if (!y.hi) 1506 return Unqual!T(divrem(x.lo, y.lo)); 1507 r.lo = x.lo; 1508 x.lo = 0U; 1509 return r; 1510 } 1511 1512 if (!y.lo) 1513 { 1514 if (!y.hi) 1515 return Unqual!T(divrem(x.hi, y.lo)); 1516 if (!x.lo) 1517 { 1518 r.hi = divrem(x.hi, y.hi); 1519 x.lo = x.hi; 1520 x.hi = 0U; 1521 return r; 1522 } 1523 if ((y.hi & (y.hi - 1U)) == 0U) 1524 { 1525 r.lo = x.lo; 1526 r.hi = x.hi & (y.hi - 1U); 1527 x.lo = x.hi >>> ctz(y.hi); 1528 x.hi = 0U; 1529 return r; 1530 } 1531 shift = clz(y.hi) - clz(x.hi); 1532 if (shift > T.HALF.sizeof * 8 - 2) 1533 { 1534 r = x; 1535 x = 0U; 1536 return r; 1537 } 1538 } 1539 else 1540 { 1541 if (!y.hi) 1542 { 1543 if ((y.lo & (y.lo - 1U)) == 0U) 1544 { 1545 r.lo = x.lo & (y.lo - 1U); 1546 if (y.lo == 1U) 1547 return r; 1548 x >>= ctz(y.lo); 1549 return r; 1550 } 1551 } 1552 else 1553 { 1554 shift = clz(y.hi) - clz(x.hi); 1555 if (shift > T.HALF.sizeof * 8 - 1) 1556 { 1557 r = x; 1558 x = 0U; 1559 return r; 1560 } 1561 } 1562 } 1563 1564 r = x; 1565 T d = y; 1566 T z = 1U; 1567 x = 0U; 1568 1569 shift = clz(d); 1570 1571 z <<= shift; 1572 d <<= shift; 1573 1574 while(z) 1575 { 1576 if (r >= d) 1577 { 1578 r -= d; 1579 x |= z; 1580 } 1581 z >>= 1; 1582 d >>= 1; 1583 } 1584 1585 return r; 1586 } 1587 1588 T divrem(T, U)(ref T x, auto const ref U y) 1589 if (isCustomUnsigned!T && isUnsignedAssignable!(T.HALF, U)) 1590 { 1591 Unqual!T r; 1592 int shift; 1593 1594 if (!x.hi) 1595 return Unqual!T(divrem(x.lo, y)); 1596 1597 if (!y) 1598 return Unqual!T(divrem(x.hi, y)); 1599 1600 if ((y & (y - 1U)) == 0U) 1601 { 1602 r.lo = x.lo & (y - 1U); 1603 if (y == 1U) 1604 return r; 1605 x >>= ctz(y); 1606 return r; 1607 } 1608 1609 1610 r = x; 1611 T d = y; 1612 T z = 1U; 1613 x = 0U; 1614 1615 shift = clz(d); 1616 1617 z <<= shift; 1618 d <<= shift; 1619 1620 while(z) 1621 { 1622 if (r >= d) 1623 { 1624 r -= d; 1625 x |= z; 1626 } 1627 z >>= 1; 1628 d >>= 1; 1629 } 1630 1631 return r; 1632 } 1633 1634 int prec(T)(const T x) 1635 if (isUnsigned!T || is(T : uint128) || is(T : uint256)) 1636 { 1637 static foreach_reverse(i, p; pow10!T) 1638 { 1639 if (x >= p) 1640 return i + 1; 1641 } 1642 return 0; 1643 } 1644 1645 //returns power of 10 if x is power of 10, -1 otherwise 1646 @safe pure nothrow @nogc 1647 int getPow10(T)(auto const ref T x) 1648 if (isUnsigned!T || is(T : uint128) || is(T : uint256)) 1649 { 1650 static foreach_reverse(i, p; pow10!T) 1651 { 1652 if (x == p) 1653 return i + 1; 1654 else if (x < p) 1655 return -1; 1656 } 1657 return 0; 1658 } 1659 1660 T cvt(T, U)(auto const ref U value) 1661 if (isAnyUnsigned!T && isAnyUnsigned!U) 1662 { 1663 static if (T.sizeof > U.sizeof) 1664 return (T(value)); 1665 else static if (T.sizeof < U.sizeof) 1666 return cast(T)(value); 1667 else 1668 return value; 1669 } 1670 1671 auto sign(S, U)(const U u, const bool isNegative) 1672 if (isUnsigned!U && isSigned!S) 1673 { 1674 static if (is(U: ubyte) || is(U: ushort)) 1675 return isNegative ? cast(S)-cast(int)u : cast(S)u; 1676 else static if (is(S: byte) || is(S: short)) 1677 return isNegative ? cast(S)-cast(int)u : cast(S)u; 1678 else 1679 return isNegative ? -cast(S)u : cast(S)u; 1680 } 1681 1682 unittest 1683 { 1684 static assert (sign!byte(ubyte(128), true) == byte.min); 1685 static assert (sign!byte(ushort(128), true) == byte.min); 1686 static assert (sign!byte(uint(128), true) == byte.min); 1687 static assert (sign!byte(ulong(128), true) == byte.min); 1688 1689 static assert (sign!short(ubyte(128), true) == byte.min); 1690 static assert (sign!short(ushort(32768), true) == short.min); 1691 static assert (sign!short(uint(32768), true) == short.min); 1692 static assert (sign!short(ulong(32768), true) == short.min); 1693 1694 1695 static assert (sign!int(ubyte(128), true) == byte.min); 1696 static assert (sign!int(ushort(32768), true) == short.min); 1697 static assert (sign!int(uint(2147483648), true) == int.min); 1698 static assert (sign!int(ulong(2147483648), true) == int.min); 1699 1700 static assert (sign!long(ubyte(128), true) == byte.min); 1701 static assert (sign!long(ushort(32768), true) == short.min); 1702 static assert (sign!long(uint(2147483648), true) == int.min); 1703 static assert (sign!long(ulong(9223372036854775808UL), true) == long.min); 1704 1705 } 1706 1707 auto sign(S, U)(const U u, const bool isNegative) 1708 if (isCustomUnsigned!U && isSigned!S) 1709 { 1710 return isNegative ? cast(S)-cast(ulong)u : cast(S)cast(ulong)u; 1711 } 1712 1713 auto unsign(U, S)(const S s, out bool isNegative) 1714 if (isUnsigned!U && isSigned!S) 1715 { 1716 isNegative = s < 0; 1717 static if (is(S: byte) || is(S: short)) 1718 return isNegative ? cast(U)-cast(int)s : cast(U)s; 1719 else static if (is(U: ubyte) || is(U: ushort)) 1720 return isNegative ? cast(U)-cast(int)s : cast(U)s; 1721 else 1722 return isNegative? -cast(U)s: cast(U)s; 1723 } 1724 1725 unittest 1726 { 1727 1728 static assert (unsign!ubyte(byte.min) == 128); 1729 static assert (unsign!ubyte(short(-128)) == 128); 1730 static assert (unsign!ubyte(int(-128)) == 128); 1731 static assert (unsign!ubyte(long(-128)) == 128); 1732 1733 static assert (unsign!ushort(byte.min) == 128); 1734 static assert (unsign!ushort(short.min) == 32768); 1735 static assert (unsign!ushort(int(short.min)) == 32768); 1736 static assert (unsign!ushort(long(short.min)) == 32768); 1737 1738 static assert (unsign!uint(byte.min) == 128); 1739 static assert (unsign!uint(short.min) == 32768); 1740 static assert (unsign!uint(int.min) == 2147483648); 1741 static assert (unsign!uint(long(int.min)) == 2147483648); 1742 1743 static assert (unsign!ulong(byte.min) == 128); 1744 static assert (unsign!ulong(short.min) == 32768); 1745 static assert (unsign!ulong(int.min) == 2147483648); 1746 static assert (unsign!ulong(long.min) == 9223372036854775808UL); 1747 1748 1749 } 1750 1751 auto unsign(U, V)(const V v, out bool isNegative) 1752 if (isUnsigned!U && isUnsigned!V) 1753 { 1754 isNegative = false; 1755 return cast(U)v; 1756 } 1757 1758 auto unsign(U, V)(const V v, out bool isNegative) 1759 if (isCustomUnsigned!U && isUnsigned!V) 1760 { 1761 isNegative = false; 1762 return U(v); 1763 } 1764 1765 auto unsign(U, S)(const S s) 1766 if (isUnsigned!U && isSigned!S) 1767 { 1768 static if (is(S: byte) || is(S: short)) 1769 return s < 0 ? cast(U)-cast(int)s : cast(U)s; 1770 else static if (is(U: ubyte) || is(U: ushort)) 1771 return s < 0 ? cast(U)-cast(int)s : cast(U)s; 1772 else 1773 return s < 0 ? -cast(U)s: cast(U)s; 1774 } 1775 1776 1777 1778 auto unsign(U, S)(const S s, out bool isNegative) 1779 if (isCustomUnsigned!U && isSigned!S) 1780 { 1781 isNegative = s < 0; 1782 static if (is(S: byte) || is(S: short)) 1783 return isNegative ? U(cast(uint)-cast(int)s) : U(cast(uint)s); 1784 else static if (is(S: int)) 1785 return isNegative ? U(cast(ulong)(-cast(long)s)) : U(cast(uint)s); 1786 else 1787 return isNegative ? U(cast(ulong)-s) : U(cast(ulong)s); 1788 } 1789 1790 auto unsign(U, S)(const S s) 1791 if (isCustomUnsigned!U && isSigned!S) 1792 { 1793 static if (is(S: byte) || is(S: short)) 1794 return s < 0 ? U(cast(uint)-cast(int)s) : U(cast(uint)s); 1795 else static if (is(S: int)) 1796 return s < 0 ? U(cast(ulong)(-cast(long)s)) : U(cast(uint)s); 1797 else 1798 return s < 0 ? U(cast(ulong)-s) : U(cast(ulong)s); 1799 } 1800 1801 1802 1803 1804 1805 1806 pure @safe nothrow @nogc 1807 int cappedSub(ref int target, const int value) 1808 { 1809 bool ovf; 1810 int result = subs(target, value, ovf); 1811 if (ovf) 1812 { 1813 if (value > 0) 1814 { 1815 //target was negative 1816 result = target - int.min; 1817 target = int.min; 1818 } 1819 else 1820 { 1821 //target was positive 1822 result = target - int.max; 1823 target = int.max; 1824 } 1825 return result; 1826 } 1827 else 1828 { 1829 target -= value; 1830 return value; 1831 } 1832 } 1833 1834 pure @safe nothrow @nogc 1835 int cappedAdd(ref int target, const int value) 1836 { 1837 bool ovf; 1838 int result = adds(target, value, ovf); 1839 if (ovf) 1840 { 1841 if (value > 0) 1842 { 1843 //target was positive 1844 result = int.max - target; 1845 target = int.max; 1846 } 1847 else 1848 { 1849 //target was negative 1850 result = int.min - target; 1851 target = int.min; 1852 } 1853 return result; 1854 } 1855 else 1856 { 1857 target += value; 1858 return value; 1859 } 1860 } 1861 1862 unittest 1863 { 1864 int ex = int.min + 1; 1865 int px = cappedSub(ex, 3); 1866 assert (ex == int.min); 1867 assert (px == 1); 1868 1869 ex = int.min + 3; 1870 px = cappedSub(ex, 2); 1871 assert (ex == int.min + 1); 1872 assert (px == 2); 1873 1874 ex = int.max - 1; 1875 px = cappedSub(ex, -2); 1876 assert (ex == int.max); 1877 assert (px == -1); 1878 1879 ex = int.max - 3; 1880 px = cappedSub(ex, -2); 1881 assert (ex == int.max - 1); 1882 assert(px == -2); 1883 1884 1885 } 1886 1887 /* ****************************************************************************************************************** */ 1888 /* 10-POWER CONSTANTS */ 1889 /* ****************************************************************************************************************** */ 1890 1891 immutable ubyte[3] pow10_8 = 1892 [ 1893 1U, 1894 10U, 1895 100U, 1896 ]; 1897 1898 immutable ushort[5] pow10_16 = 1899 [ 1900 1U, 1901 10U, 1902 100U, 1903 1000U, 1904 10000U, 1905 ]; 1906 1907 immutable uint[10] pow10_32 = 1908 [ 1909 1U, 1910 10U, 1911 100U, 1912 1000U, 1913 10000U, 1914 100000U, 1915 1000000U, 1916 10000000U, 1917 100000000U, 1918 1000000000U 1919 ]; 1920 1921 immutable ulong[20] pow10_64 = 1922 [ 1923 1UL, 1924 10UL, 1925 100UL, 1926 1000UL, 1927 10000UL, 1928 100000UL, 1929 1000000UL, 1930 10000000UL, 1931 100000000UL, 1932 1000000000UL, 1933 10000000000UL, 1934 100000000000UL, 1935 1000000000000UL, 1936 10000000000000UL, 1937 100000000000000UL, 1938 1000000000000000UL, 1939 10000000000000000UL, 1940 100000000000000000UL, 1941 1000000000000000000UL, 1942 10000000000000000000UL, 1943 ]; 1944 1945 immutable uint128[39] pow10_128 = 1946 [ 1947 uint128(1UL), 1948 uint128(10UL), 1949 uint128(100UL), 1950 uint128(1000UL), 1951 uint128(10000UL), 1952 uint128(100000UL), 1953 uint128(1000000UL), 1954 uint128(10000000UL), 1955 uint128(100000000UL), 1956 uint128(1000000000UL), 1957 uint128(10000000000UL), 1958 uint128(100000000000UL), 1959 uint128(1000000000000UL), 1960 uint128(10000000000000UL), 1961 uint128(100000000000000UL), 1962 uint128(1000000000000000UL), 1963 uint128(10000000000000000UL), 1964 uint128(100000000000000000UL), 1965 uint128(1000000000000000000UL), 1966 uint128(10000000000000000000UL), 1967 uint128("100000000000000000000"), 1968 uint128("1000000000000000000000"), 1969 uint128("10000000000000000000000"), 1970 uint128("100000000000000000000000"), 1971 uint128("1000000000000000000000000"), 1972 uint128("10000000000000000000000000"), 1973 uint128("100000000000000000000000000"), 1974 uint128("1000000000000000000000000000"), 1975 uint128("10000000000000000000000000000"), 1976 uint128("100000000000000000000000000000"), 1977 uint128("1000000000000000000000000000000"), 1978 uint128("10000000000000000000000000000000"), 1979 uint128("100000000000000000000000000000000"), 1980 uint128("1000000000000000000000000000000000"), 1981 uint128("10000000000000000000000000000000000"), 1982 uint128("100000000000000000000000000000000000"), 1983 uint128("1000000000000000000000000000000000000"), 1984 uint128("10000000000000000000000000000000000000"), 1985 uint128("100000000000000000000000000000000000000"), 1986 ]; 1987 1988 immutable uint256[78] pow10_256 = 1989 [ 1990 uint256(1UL), 1991 uint256(10UL), 1992 uint256(100UL), 1993 uint256(1000UL), 1994 uint256(10000UL), 1995 uint256(100000UL), 1996 uint256(1000000UL), 1997 uint256(10000000UL), 1998 uint256(100000000UL), 1999 uint256(1000000000UL), 2000 uint256(10000000000UL), 2001 uint256(100000000000UL), 2002 uint256(1000000000000UL), 2003 uint256(10000000000000UL), 2004 uint256(100000000000000UL), 2005 uint256(1000000000000000UL), 2006 uint256(10000000000000000UL), 2007 uint256(100000000000000000UL), 2008 uint256(1000000000000000000UL), 2009 uint256(10000000000000000000UL), 2010 uint256("100000000000000000000"), 2011 uint256("1000000000000000000000"), 2012 uint256("10000000000000000000000"), 2013 uint256("100000000000000000000000"), 2014 uint256("1000000000000000000000000"), 2015 uint256("10000000000000000000000000"), 2016 uint256("100000000000000000000000000"), 2017 uint256("1000000000000000000000000000"), 2018 uint256("10000000000000000000000000000"), 2019 uint256("100000000000000000000000000000"), 2020 uint256("1000000000000000000000000000000"), 2021 uint256("10000000000000000000000000000000"), 2022 uint256("100000000000000000000000000000000"), 2023 uint256("1000000000000000000000000000000000"), 2024 uint256("10000000000000000000000000000000000"), 2025 uint256("100000000000000000000000000000000000"), 2026 uint256("1000000000000000000000000000000000000"), 2027 uint256("10000000000000000000000000000000000000"), 2028 uint256("100000000000000000000000000000000000000"), 2029 uint256("1000000000000000000000000000000000000000"), 2030 uint256("10000000000000000000000000000000000000000"), 2031 uint256("100000000000000000000000000000000000000000"), 2032 uint256("1000000000000000000000000000000000000000000"), 2033 uint256("10000000000000000000000000000000000000000000"), 2034 uint256("100000000000000000000000000000000000000000000"), 2035 uint256("1000000000000000000000000000000000000000000000"), 2036 uint256("10000000000000000000000000000000000000000000000"), 2037 uint256("100000000000000000000000000000000000000000000000"), 2038 uint256("1000000000000000000000000000000000000000000000000"), 2039 uint256("10000000000000000000000000000000000000000000000000"), 2040 uint256("100000000000000000000000000000000000000000000000000"), 2041 uint256("1000000000000000000000000000000000000000000000000000"), 2042 uint256("10000000000000000000000000000000000000000000000000000"), 2043 uint256("100000000000000000000000000000000000000000000000000000"), 2044 uint256("1000000000000000000000000000000000000000000000000000000"), 2045 uint256("10000000000000000000000000000000000000000000000000000000"), 2046 uint256("100000000000000000000000000000000000000000000000000000000"), 2047 uint256("1000000000000000000000000000000000000000000000000000000000"), 2048 uint256("10000000000000000000000000000000000000000000000000000000000"), 2049 uint256("100000000000000000000000000000000000000000000000000000000000"), 2050 uint256("1000000000000000000000000000000000000000000000000000000000000"), 2051 uint256("10000000000000000000000000000000000000000000000000000000000000"), 2052 uint256("100000000000000000000000000000000000000000000000000000000000000"), 2053 uint256("1000000000000000000000000000000000000000000000000000000000000000"), 2054 uint256("10000000000000000000000000000000000000000000000000000000000000000"), 2055 uint256("100000000000000000000000000000000000000000000000000000000000000000"), 2056 uint256("1000000000000000000000000000000000000000000000000000000000000000000"), 2057 uint256("10000000000000000000000000000000000000000000000000000000000000000000"), 2058 uint256("100000000000000000000000000000000000000000000000000000000000000000000"), 2059 uint256("1000000000000000000000000000000000000000000000000000000000000000000000"), 2060 uint256("10000000000000000000000000000000000000000000000000000000000000000000000"), 2061 uint256("100000000000000000000000000000000000000000000000000000000000000000000000"), 2062 uint256("1000000000000000000000000000000000000000000000000000000000000000000000000"), 2063 uint256("10000000000000000000000000000000000000000000000000000000000000000000000000"), 2064 uint256("100000000000000000000000000000000000000000000000000000000000000000000000000"), 2065 uint256("1000000000000000000000000000000000000000000000000000000000000000000000000000"), 2066 uint256("10000000000000000000000000000000000000000000000000000000000000000000000000000"), 2067 uint256("100000000000000000000000000000000000000000000000000000000000000000000000000000"), 2068 ]; 2069 2070 template pow10(T) 2071 { 2072 static if (is(Unqual!T == uint)) 2073 alias pow10 = pow10_32; 2074 else static if (is(Unqual!T == ulong)) 2075 alias pow10 = pow10_64; 2076 else static if (is(Unqual!T == uint128)) 2077 alias pow10 = pow10_128; 2078 else static if (is(Unqual!T == uint256)) 2079 alias pow10 = pow10_256; 2080 else static if (is(Unqual!T == ushort)) 2081 alias pow10 = pow10_16; 2082 else static if (is(Unqual!T == ubyte)) 2083 alias pow10 = pow10_8; 2084 else 2085 static assert(0); 2086 } 2087 2088 /* ****************************************************************************************************************** */ 2089 /* MAXIMUM COEFFICIENTS THAT CAN BE MULTIPLIED BY 10-POWERS */ 2090 /* ****************************************************************************************************************** */ 2091 2092 immutable ubyte[3] maxmul10_8 = 2093 [ 2094 255U, 2095 25U, 2096 2U, 2097 ]; 2098 2099 immutable ushort[5] maxmul10_16 = 2100 [ 2101 65535U, 2102 6553U, 2103 655U, 2104 65U, 2105 6U, 2106 ]; 2107 2108 immutable uint[10] maxmul10_32 = 2109 [ 2110 4294967295U, 2111 429496729U, 2112 42949672U, 2113 4294967U, 2114 429496U, 2115 42949U, 2116 4294U, 2117 429U, 2118 42U, 2119 4U, 2120 ]; 2121 2122 immutable ulong[20] maxmul10_64 = 2123 [ 2124 18446744073709551615UL, 2125 1844674407370955161UL, 2126 184467440737095516UL, 2127 18446744073709551UL, 2128 1844674407370955UL, 2129 184467440737095UL, 2130 18446744073709UL, 2131 1844674407370UL, 2132 184467440737UL, 2133 18446744073UL, 2134 1844674407UL, 2135 184467440UL, 2136 18446744UL, 2137 1844674UL, 2138 184467UL, 2139 18446UL, 2140 1844UL, 2141 184UL, 2142 18UL, 2143 1UL, 2144 ]; 2145 2146 immutable uint128[39] maxmul10_128 = 2147 [ 2148 uint128("340282366920938463463374607431768211455"), 2149 uint128("34028236692093846346337460743176821145"), 2150 uint128("3402823669209384634633746074317682114"), 2151 uint128("340282366920938463463374607431768211"), 2152 uint128("34028236692093846346337460743176821"), 2153 uint128("3402823669209384634633746074317682"), 2154 uint128("340282366920938463463374607431768"), 2155 uint128("34028236692093846346337460743176"), 2156 uint128("3402823669209384634633746074317"), 2157 uint128("340282366920938463463374607431"), 2158 uint128("34028236692093846346337460743"), 2159 uint128("3402823669209384634633746074"), 2160 uint128("340282366920938463463374607"), 2161 uint128("34028236692093846346337460"), 2162 uint128("3402823669209384634633746"), 2163 uint128("340282366920938463463374"), 2164 uint128("34028236692093846346337"), 2165 uint128("3402823669209384634633"), 2166 uint128("340282366920938463463"), 2167 uint128("34028236692093846346"), 2168 uint128(3402823669209384634UL), 2169 uint128(340282366920938463UL), 2170 uint128(34028236692093846UL), 2171 uint128(3402823669209384UL), 2172 uint128(340282366920938UL), 2173 uint128(34028236692093UL), 2174 uint128(3402823669209UL), 2175 uint128(340282366920UL), 2176 uint128(34028236692UL), 2177 uint128(3402823669UL), 2178 uint128(340282366UL), 2179 uint128(34028236UL), 2180 uint128(3402823UL), 2181 uint128(340282UL), 2182 uint128(34028UL), 2183 uint128(3402UL), 2184 uint128(340UL), 2185 uint128(34UL), 2186 uint128(3UL), 2187 ]; 2188 2189 immutable uint256[78] maxmul10_256 = 2190 [ 2191 uint256("115792089237316195423570985008687907853269984665640564039457584007913129639935"), 2192 uint256("11579208923731619542357098500868790785326998466564056403945758400791312963993"), 2193 uint256("1157920892373161954235709850086879078532699846656405640394575840079131296399"), 2194 uint256("115792089237316195423570985008687907853269984665640564039457584007913129639"), 2195 uint256("11579208923731619542357098500868790785326998466564056403945758400791312963"), 2196 uint256("1157920892373161954235709850086879078532699846656405640394575840079131296"), 2197 uint256("115792089237316195423570985008687907853269984665640564039457584007913129"), 2198 uint256("11579208923731619542357098500868790785326998466564056403945758400791312"), 2199 uint256("1157920892373161954235709850086879078532699846656405640394575840079131"), 2200 uint256("115792089237316195423570985008687907853269984665640564039457584007913"), 2201 uint256("11579208923731619542357098500868790785326998466564056403945758400791"), 2202 uint256("1157920892373161954235709850086879078532699846656405640394575840079"), 2203 uint256("115792089237316195423570985008687907853269984665640564039457584007"), 2204 uint256("11579208923731619542357098500868790785326998466564056403945758400"), 2205 uint256("1157920892373161954235709850086879078532699846656405640394575840"), 2206 uint256("115792089237316195423570985008687907853269984665640564039457584"), 2207 uint256("11579208923731619542357098500868790785326998466564056403945758"), 2208 uint256("1157920892373161954235709850086879078532699846656405640394575"), 2209 uint256("115792089237316195423570985008687907853269984665640564039457"), 2210 uint256("11579208923731619542357098500868790785326998466564056403945"), 2211 uint256("1157920892373161954235709850086879078532699846656405640394"), 2212 uint256("115792089237316195423570985008687907853269984665640564039"), 2213 uint256("11579208923731619542357098500868790785326998466564056403"), 2214 uint256("1157920892373161954235709850086879078532699846656405640"), 2215 uint256("115792089237316195423570985008687907853269984665640564"), 2216 uint256("11579208923731619542357098500868790785326998466564056"), 2217 uint256("1157920892373161954235709850086879078532699846656405"), 2218 uint256("115792089237316195423570985008687907853269984665640"), 2219 uint256("11579208923731619542357098500868790785326998466564"), 2220 uint256("1157920892373161954235709850086879078532699846656"), 2221 uint256("115792089237316195423570985008687907853269984665"), 2222 uint256("11579208923731619542357098500868790785326998466"), 2223 uint256("1157920892373161954235709850086879078532699846"), 2224 uint256("115792089237316195423570985008687907853269984"), 2225 uint256("11579208923731619542357098500868790785326998"), 2226 uint256("1157920892373161954235709850086879078532699"), 2227 uint256("115792089237316195423570985008687907853269"), 2228 uint256("11579208923731619542357098500868790785326"), 2229 uint256("1157920892373161954235709850086879078532"), 2230 uint256("115792089237316195423570985008687907853"), 2231 uint256("11579208923731619542357098500868790785"), 2232 uint256("1157920892373161954235709850086879078"), 2233 uint256("115792089237316195423570985008687907"), 2234 uint256("11579208923731619542357098500868790"), 2235 uint256("1157920892373161954235709850086879"), 2236 uint256("115792089237316195423570985008687"), 2237 uint256("11579208923731619542357098500868"), 2238 uint256("1157920892373161954235709850086"), 2239 uint256("115792089237316195423570985008"), 2240 uint256("11579208923731619542357098500"), 2241 uint256("1157920892373161954235709850"), 2242 uint256("115792089237316195423570985"), 2243 uint256("11579208923731619542357098"), 2244 uint256("1157920892373161954235709"), 2245 uint256("115792089237316195423570"), 2246 uint256("11579208923731619542357"), 2247 uint256("1157920892373161954235"), 2248 uint256("115792089237316195423"), 2249 uint256("11579208923731619542"), 2250 uint256("1157920892373161954"), 2251 uint256("115792089237316195"), 2252 uint256(11579208923731619UL), 2253 uint256(1157920892373161UL), 2254 uint256(115792089237316UL), 2255 uint256(11579208923731UL), 2256 uint256(1157920892373UL), 2257 uint256(115792089237UL), 2258 uint256(11579208923UL), 2259 uint256(1157920892UL), 2260 uint256(115792089UL), 2261 uint256(11579208UL), 2262 uint256(1157920UL), 2263 uint256(115792UL), 2264 uint256(11579UL), 2265 uint256(1157UL), 2266 uint256(115UL), 2267 uint256(11UL), 2268 uint256(1UL), 2269 ]; 2270 2271 template maxmul10(T) 2272 { 2273 static if (is(Unqual!T == uint)) 2274 alias maxmul10 = maxmul10_32; 2275 else static if (is(Unqual!T == ulong)) 2276 alias maxmul10 = maxmul10_64; 2277 else static if (is(Unqual!T == uint128)) 2278 alias maxmul10 = maxmul10_128; 2279 else static if (is(Unqual!T == uint256)) 2280 alias maxmul10 = maxmul10_256; 2281 else static if (is(Unqual!T == ushort)) 2282 alias maxmul10 = maxmul10_16; 2283 else static if (is(Unqual!T == ubyte)) 2284 alias maxmul10 = maxmul10_8; 2285 else 2286 static assert(0); 2287 } 2288 2289 2290 2291 //true on inexact 2292 bool sqrt(U)(ref U x) 2293 if (isAnyUnsigned!U) 2294 { 2295 // Newton-Raphson: x = (x + n/x) / 2; 2296 //x 2297 if (x <= 1U) 2298 return false; 2299 immutable n = x; 2300 Unqual!U y; 2301 //1 .. 99 1 x 10^0 .. 99 x 10^0 1 .. 2 //0 - 10^0 <10^1 2 x 10^0, 6x10^0 2302 //100 .. 9999 1 x 10^2 ...99.99 x 10^2 3 .. 4 //2 -10^1 <10^3 2 x 10^1, 6x10^1 2303 //10000 .. 999999 1.x 10^4 ...99999.99 x 10^4 5 .. 6 //4 -10^2 <10^5 2 x 10^2, 6x10^2 2304 auto p = prec(x); 2305 int power = p & 1 ? p - 1 : p - 2; 2306 2307 if (power >= pow10!U.length - 1 || x >= pow10!U[power + 1]) 2308 x = pow10!U[power >> 1] * 6U; 2309 else 2310 x = pow10!U[power >> 1] << 1; //* 2U; 2311 2312 do 2313 { 2314 y = x; 2315 x = (x + n / x) >> 1; 2316 } 2317 while (x != y); 2318 return x * x != n; 2319 } 2320 2321 //true on inexact 2322 bool cbrt(U)(ref U x) 2323 if (isAnyUnsigned!U) 2324 { 2325 // Newton-Raphson: x = (2x + N/x2)/3 2326 if (x <= 1U) 2327 return false; 2328 immutable n = x; 2329 Unqual!U y; 2330 //1 .. 99 1 x 10^0 .. 99 x 10^0 1 .. 2 //0 - 10^0 <10^1 2 x 10^0, 6x10^0 2331 //100 .. 9999 1 x 10^2 ...99.99 x 10^2 3 .. 4 //2 -10^1 <10^3 2 x 10^1, 6x10^1 2332 //10000 .. 999999 1.x 10^4 ...99999.99 x 10^4 5 .. 6 //4 -10^2 <10^5 2 x 10^2, 6x10^2 2333 2334 x /= 3U; 2335 if (!x) 2336 return true; 2337 do 2338 { 2339 y = x; 2340 x = ((x << 1) + n / (x * x)) / 3U; 2341 } 2342 while (x != y && x); 2343 return x * x * x != n; 2344 }