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 //for debugging purposes 561 string toString() const 562 { 563 char[bits / 3 + 1] buffer; 564 size_t i = buffer.length; 565 THIS v = this; 566 do 567 { 568 auto r = divrem(v, 10U); 569 buffer[--i] = cast(char)('0' + cast(uint)r); 570 } while (v != 0U); 571 return buffer[i .. $].dup; 572 } 573 574 } 575 576 alias uint128 = unsigned!128; 577 alias uint256 = unsigned!256; 578 alias uint512 = unsigned!512; 579 580 unittest 581 { 582 import std.typetuple; 583 import std.random; 584 585 auto gen = Random(); 586 587 T rnd(T)() 588 { 589 static if (is(T == uint)) 590 return uniform(1U, uint.max, gen); 591 else static if (is(T == ulong)) 592 return uniform(1UL, ulong.max, gen); 593 else 594 return T(rnd!(T.HALF)(), rnd!(T.HALF)()); 595 596 } 597 598 599 600 601 foreach (T; TypeTuple!(unsigned!128, unsigned!256, unsigned!512)) 602 { 603 enum zero = T(0U); 604 enum one = T(1U); 605 enum two = T(2U); 606 enum three = T(3U); 607 enum big = T(0x3333333333U, 0x4444444444U); 608 enum next = T(1U, 0U); 609 enum previous = T(0U, T.HALF.max); 610 611 assert (zero == zero); 612 assert (zero <= zero); 613 assert (zero >= zero); 614 assert (zero < one); 615 assert (zero < two); 616 assert (zero < three); 617 assert (zero < big); 618 assert (zero < next); 619 assert (zero < previous); 620 621 assert (one > zero); 622 assert (one >= zero); 623 assert (one >= one); 624 assert (one == one); 625 assert (one < two); 626 assert (one < three); 627 assert (one < big); 628 assert (one < next); 629 assert (one < previous); 630 631 assert (two > zero); 632 assert (two >= zero); 633 assert (two >= one); 634 assert (two > one); 635 assert (two == two); 636 assert (two < three); 637 assert (two < big); 638 assert (two < next); 639 assert (two < previous); 640 641 assert (three > zero); 642 assert (three >= zero); 643 assert (three >= one); 644 assert (three > one); 645 assert (three >= two); 646 assert (three == three); 647 assert (three < big); 648 assert (three < next); 649 assert (three < previous); 650 651 assert (big > zero); 652 assert (big >= zero); 653 assert (big >= one); 654 assert (big > one); 655 assert (big >= two); 656 assert (big >= three); 657 assert (big == big); 658 assert (big > next); 659 assert (big > previous); 660 661 assert (next > zero); 662 assert (next >= zero); 663 assert (next >= one); 664 assert (next > one); 665 assert (next >= two); 666 assert (next >= three); 667 assert (next <= big); 668 assert (next == next); 669 assert (next > previous); 670 671 assert (previous > zero); 672 assert (previous >= zero); 673 assert (previous >= one); 674 assert (previous > one); 675 assert (previous >= two); 676 assert (previous >= three); 677 assert (previous <= big); 678 assert (previous <= next); 679 assert (previous == previous); 680 681 assert (zero == 0U); 682 assert (zero <= 0U); 683 assert (zero >= 0U); 684 assert (zero < 1U); 685 assert (zero < 2U); 686 assert (zero < 3U); 687 assert (zero < ulong.max); 688 689 assert (one > 0U); 690 assert (one >= 0U); 691 assert (one >= 1U); 692 assert (one == 1U); 693 assert (one < 2U); 694 assert (one < 3U); 695 assert (one < ulong.max); 696 697 assert (two > 0U); 698 assert (two >= 0U); 699 assert (two >= 1U); 700 assert (two > 1U); 701 assert (two == 2U); 702 assert (two < 3U); 703 assert (two < ulong.max); 704 705 assert (three > 0U); 706 assert (three >= 0U); 707 assert (three >= 1U); 708 assert (three > 1U); 709 assert (three >= 2U); 710 assert (three == 3U); 711 assert (three < ulong.max); 712 713 assert (big > 0U); 714 assert (big >= 0U); 715 assert (big >= 1U); 716 assert (big > 1U); 717 assert (big >= 2U); 718 assert (big >= 3U); 719 assert (big > ulong.max); 720 721 assert (next > 0U); 722 assert (next >= 0U); 723 assert (next >= 1U); 724 assert (next > 1U); 725 assert (next >= 2U); 726 assert (next >= 3U); 727 assert (next > ulong.max); 728 729 assert (previous > 0U); 730 assert (previous >= 0U); 731 assert (previous >= 1U); 732 assert (previous > 1U); 733 assert (previous >= 2U); 734 assert (previous >= 3U); 735 assert (previous == previous); 736 737 assert (~~zero == zero); 738 assert (~~one == one); 739 assert (~~two == two); 740 assert (~~three == three); 741 assert (~~big == big); 742 assert (~~previous == previous); 743 assert (~~next == next); 744 745 assert ((one | one) == one); 746 assert ((one | zero) == one); 747 assert ((one & one) == one); 748 assert ((one & zero) == zero); 749 assert ((big & ~big) == zero); 750 assert ((one ^ one) == zero); 751 assert ((big ^ big) == zero); 752 assert ((one ^ zero) == one); 753 754 assert(big >> 0 == big); 755 assert(big << 0 == big); 756 757 assert(big << 1 > big); 758 assert(big >> 1 < big); 759 760 auto x = big << 3; 761 auto y = x >> 3; 762 assert((big << 3) >> 3 == big); 763 assert((one << 127) >> 127 == one); 764 assert((one << 64) >> 64 == one); 765 766 assert (zero + zero == zero); 767 assert (zero + one == one); 768 assert (zero + two == two); 769 assert (zero + three == three); 770 assert (zero + big == big); 771 assert (zero + previous == previous); 772 assert (zero + next == next); 773 774 assert (one + zero == one); 775 assert (one + one == two); 776 assert (one + two == three); 777 assert (one + three > three); 778 assert (one + big > big); 779 assert (one + previous == next); 780 assert (one + next > next); 781 782 assert (two + zero == two); 783 assert (two + one == three); 784 assert (two + two > three); 785 assert (two + three > three); 786 assert (two + big > big); 787 assert (two + previous > next); 788 assert (two + next > next); 789 790 assert (three + zero == three); 791 assert (three + one > three); 792 assert (three + two > three); 793 assert (three + three > three); 794 assert (three + big > big); 795 assert (three + previous > next); 796 assert (three + next > next); 797 798 assert (big + zero == big); 799 assert (big + one > big); 800 assert (big + two > big + one); 801 assert (big + three > big + two); 802 assert (big + big > big); 803 assert (big + previous > next); 804 assert (big + next > next); 805 806 assert (previous + zero == previous); 807 assert (previous + one == next); 808 assert (previous + two > next); 809 assert (previous + three == next + two); 810 assert (previous + big > big); 811 assert (previous + previous > previous); 812 assert (previous + next > previous); 813 814 assert (next + zero == next); 815 assert (next + one > next); 816 assert (next + two > next); 817 assert (next + three >= next + two); 818 assert (next + big > big); 819 assert (next + previous > next); 820 assert (next + next > next); 821 822 assert (zero + 0U == zero); 823 assert (zero + 1U == one); 824 assert (zero + 2U == two); 825 assert (zero + 3U == three); 826 827 assert (one + 0U == one); 828 assert (one + 1U == two); 829 assert (one + 2U == three); 830 assert (one + 3U > three); 831 832 assert (two + 0U == two); 833 assert (two + 1U == three); 834 assert (two + 2U > three); 835 assert (two + 3U > three); 836 837 assert (three + 0U == three); 838 assert (three + 1U > three); 839 assert (three + 2U > three); 840 assert (three + 3U > three); 841 842 assert (big + 0U == big); 843 assert (big + 1U > big); 844 assert (big + 2U > big + 1U); 845 assert (big + 3U > big + 2U); 846 847 assert (previous + 0U == previous); 848 assert (previous + 1U == next); 849 assert (previous + 2U > next); 850 assert (previous + 3U == next + 2U); 851 852 assert (next + 0U == next); 853 assert (next + 1U > next); 854 assert (next + 2U > next); 855 assert (next + 3U >= next + two); 856 857 assert (zero - zero == zero); 858 assert (one - zero == one); 859 assert (two - zero == two); 860 assert (three - zero == three); 861 assert (big - zero == big); 862 assert (previous - zero == previous); 863 assert (next - zero == next); 864 865 assert (one - one == zero); 866 assert (two - one == one); 867 assert (three - one == two); 868 assert (big - one < big); 869 assert (previous - one < previous); 870 assert (next - one == previous); 871 872 assert (two - two == zero); 873 assert (three - two == one); 874 assert (big - two < big); 875 assert (previous - two < previous); 876 assert (next - two < previous); 877 878 assert (three - three == zero); 879 assert (big - three < big); 880 assert (previous - three < previous); 881 assert (next - three < previous); 882 883 assert (big - big == zero); 884 assert (next - previous == one); 885 886 assert (one - 1U == zero); 887 assert (two - 1U == one); 888 assert (three - 1U == two); 889 assert (big - 1U < big); 890 assert (previous - 1U < previous); 891 assert (next - 1U == previous); 892 893 assert (two - 2U == zero); 894 assert (three - 2U == one); 895 assert (big - 2U < big); 896 assert (previous - 2U < previous); 897 assert (next - 2U < previous); 898 899 assert (three - 3U == zero); 900 assert (big - 3U < big); 901 assert (previous - 3U < previous); 902 assert (next - 3U < previous); 903 904 T test = zero; 905 assert (++test == one); 906 assert (++test == two); 907 assert (++test == three); 908 test = big; 909 assert (++test > big); 910 test = previous; 911 assert (++test == next); 912 test = three; 913 assert (--test == two); 914 assert (--test == one); 915 assert (--test == zero); 916 test = big; 917 assert (--test < big); 918 test = next; 919 assert (--test == previous); 920 921 assert (-zero == zero); 922 assert (-(-zero) == zero); 923 assert (-(-one) == one); 924 assert (-(-two) == two); 925 assert (-(-three) == three); 926 assert (-(-big) == big); 927 assert (-(-previous) == previous); 928 assert (-(-next) == next); 929 930 931 for(auto i = 0; i < 10; ++i) 932 { 933 T a = rnd!T(); 934 T b = rnd!T(); 935 T.HALF c = rnd!(T.HALF)(); 936 ulong d = rnd!ulong(); 937 uint e = rnd!uint(); 938 939 T result = a / b; 940 T remainder = a % b; 941 942 assert (result * b + remainder == a); 943 944 result = a / c; 945 remainder = a % c; 946 947 assert (result * c + remainder == a); 948 949 result = a / d; 950 remainder = a % d; 951 952 assert (result * d + remainder == a); 953 954 result = a / e; 955 remainder = a % e; 956 957 assert (result * e + remainder == a); 958 } 959 } 960 961 } 962 963 964 965 /* ****************************************************************************************************************** */ 966 /* INTEGRAL UTILITY FUNCTIONS */ 967 /* ****************************************************************************************************************** */ 968 969 @safe pure nothrow @nogc 970 uint xadd(ref uint x, const uint y) 971 { 972 bool ovf; 973 x = addu(x, y, ovf); 974 return ovf ? 1 : 0; 975 } 976 977 @safe pure nothrow @nogc 978 uint xadd(ref ulong x, const ulong y) 979 { 980 bool ovf; 981 x = addu(x, y, ovf); 982 return ovf ? 1 : 0; 983 } 984 985 @safe pure nothrow @nogc 986 uint xadd(ref ulong x, const uint y) 987 { 988 return xadd(x, cast(ulong)y); 989 } 990 991 uint xadd(T)(ref T x, auto const ref T y) 992 if (isCustomUnsigned!T) 993 { 994 auto carry = xadd(x.lo, y.lo); 995 carry = xadd(x.hi, carry); 996 return xadd(x.hi, y.hi) + carry; 997 } 998 999 uint xadd(T, U)(ref T x, auto const ref U y) 1000 if (isCustomUnsigned!T && isUnsignedAssignable!(T.HALF, U)) 1001 { 1002 auto carry = xadd(x.lo, y); 1003 return xadd(x.hi, carry); 1004 } 1005 1006 @safe pure nothrow @nogc 1007 uint xsub(ref uint x, const uint y) 1008 { 1009 bool ovf; 1010 x = subu(x, y, ovf); 1011 return ovf ? 1 : 0; 1012 } 1013 1014 @safe pure nothrow @nogc 1015 uint xsub(ref ulong x, const ulong y) 1016 { 1017 bool ovf; 1018 x = subu(x, y, ovf); 1019 return ovf ? 1 : 0; 1020 } 1021 1022 @safe pure nothrow @nogc 1023 uint xsub(ref ulong x, const uint y) 1024 { 1025 return xsub(x, cast(ulong)y); 1026 } 1027 1028 @safe pure nothrow @nogc 1029 uint xsub(T)(ref T x, auto const ref T y) 1030 if (isCustomUnsigned!T) 1031 { 1032 auto carry = xsub(x.lo, y.lo); 1033 carry = xsub(x.hi, carry); 1034 return xsub(x.hi, y.hi) + carry; 1035 } 1036 1037 @safe pure nothrow @nogc 1038 uint xsub(T, U)(ref T x, auto const ref U y) 1039 if (isCustomUnsigned!T && isUnsignedAssignable!(T.HALF, U)) 1040 { 1041 auto carry = xsub(x.lo, y); 1042 return xsub(x.hi, carry); 1043 } 1044 1045 @safe pure nothrow @nogc 1046 uint fma(const uint x, const uint y, const uint z, out bool overflow) 1047 { 1048 auto result = mulu(x, y, overflow); 1049 return addu(result, z, overflow); 1050 } 1051 1052 @safe pure nothrow @nogc 1053 ulong fma(const ulong x, const ulong y, const ulong z, ref bool overflow) 1054 { 1055 auto result = mulu(x, y, overflow); 1056 return addu(result, z, overflow); 1057 } 1058 1059 @safe pure nothrow @nogc 1060 ulong fma(const ulong x, const uint y, const uint z, ref bool overflow) 1061 { 1062 auto result = mulu(x, cast(ulong)y, overflow); 1063 return addu(result, cast(ulong)z, overflow); 1064 } 1065 1066 @safe pure nothrow @nogc 1067 T fma(T)(auto const ref T x, auto const ref T y, auto const ref T z, ref bool overflow) 1068 if (isCustomUnsigned!T) 1069 { 1070 auto result = mulu(x, y, overflow); 1071 if (xadd(result, z)) 1072 overflow = true; 1073 return result; 1074 } 1075 1076 @safe pure nothrow @nogc 1077 T fma(T, U)(auto const ref T x, auto const ref U y, auto const ref U z, ref bool overflow) 1078 if (isCustomUnsigned!T && isUnsignedAssignable!(T.HALF, U)) 1079 { 1080 auto result = mulu(x, y, overflow); 1081 if (xadd(result, z)) 1082 overflow = true; 1083 return result; 1084 } 1085 1086 1087 @safe pure nothrow @nogc 1088 ulong xmul(const uint x, const uint y) 1089 { 1090 return cast(ulong)x * y; 1091 } 1092 1093 @safe pure nothrow @nogc 1094 ulong xsqr(const uint x) 1095 { 1096 return cast(ulong)x * x; 1097 } 1098 1099 @safe pure nothrow @nogc 1100 uint128 xmul(const ulong x, const ulong y) 1101 { 1102 if (x == 0 || y == 0) 1103 return uint128.min; 1104 if (x == 1) 1105 return uint128(y); 1106 if (y == 1) 1107 return uint128(x); 1108 if ((x & (x - 1)) == 0) 1109 return uint128(y) << ctz(x); 1110 if ((y & (y - 1)) == 0) 1111 return uint128(x) << ctz(y); 1112 if (x == y) 1113 return xsqr(x); 1114 1115 1116 immutable xlo = cast(uint)x; 1117 immutable xhi = cast(uint)(x >>> 32); 1118 immutable ylo = cast(uint)y; 1119 immutable yhi = cast(uint)(y >>> 32); 1120 1121 ulong t = xmul(xlo, ylo); 1122 ulong w0 = cast(uint)t; 1123 ulong k = t >>> 32; 1124 1125 t = xmul(xhi, ylo) + k; 1126 ulong w1 = cast(uint)t; 1127 ulong w2 = t >>> 32; 1128 1129 t = xmul(xlo, yhi) + w1; 1130 k = t >>> 32; 1131 1132 return uint128(xmul(xhi, yhi) + w2 + k, (t << 32) + w0); 1133 } 1134 1135 @safe pure nothrow @nogc 1136 uint128 xsqr(const ulong x) 1137 { 1138 immutable xlo = cast(uint)x; 1139 immutable xhi = cast(uint)(x >>> 32); 1140 immutable hilo = xmul(xlo, xhi); 1141 1142 ulong t = xsqr(xlo); 1143 ulong w0 = cast(uint)t; 1144 ulong k = t >>> 32; 1145 1146 t = hilo + k; 1147 ulong w1 = cast(uint)t; 1148 ulong w2 = t >>> 32; 1149 1150 t = hilo + w1; 1151 k = t >>> 32; 1152 1153 return uint128(xsqr(xhi) + w2 + k, (t << 32) + w0); 1154 } 1155 1156 @safe pure nothrow @nogc 1157 uint128 xmul(const ulong x, const uint y) 1158 { 1159 if (x == 0 || y == 0) 1160 return uint128.min; 1161 if (x == 1) 1162 return uint128(y); 1163 if (y == 1) 1164 return uint128(x); 1165 if ((x & (x - 1)) == 0) 1166 return uint128(y) << ctz(x); 1167 if ((y & (y - 1)) == 0) 1168 return uint128(x) << ctz(y); 1169 1170 immutable xlo = cast(uint)x; 1171 immutable xhi = cast(uint)(x >>> 32); 1172 1173 ulong t = xmul(xlo, y); 1174 ulong w0 = cast(uint)t; 1175 ulong k = t >>> 32; 1176 1177 t = xmul(xhi, y) + k; 1178 ulong w1 = cast(uint)t; 1179 ulong w2 = t >>> 32; 1180 1181 return uint128(w2, (w1 << 32) + w0); 1182 } 1183 1184 1185 auto xmul(T)(auto const ref T x, auto const ref T y) 1186 if (isCustomUnsigned!T) 1187 { 1188 enum bits = T.sizeof * 8; 1189 enum rbits = bits * 2; 1190 alias R = unsigned!rbits; 1191 1192 if (x == 0U || y == 0U) 1193 return R.min; 1194 if (x == 1U) 1195 return R(y); 1196 if (y == 1U) 1197 return R(x); 1198 if ((x & (x - 1U)) == 0U) 1199 return R(y) << ctz(x); 1200 if ((y & (y - 1U)) == 0U) 1201 return R(x) << ctz(y); 1202 if (x == y) 1203 return xsqr(x); 1204 1205 auto t = xmul(x.lo, y.lo); 1206 auto w0 = t.lo; 1207 auto k = t.hi; 1208 1209 t = xmul(x.hi, y.lo) + k; 1210 auto w2 = t.hi; 1211 1212 t = xmul(x.lo, y.hi) + t.lo; 1213 1214 return R(xmul(x.hi, y.hi) + w2 + t.hi, (t << (bits / 2)) + w0); 1215 } 1216 1217 T mulu(T)(auto const ref T x, auto const ref T y, ref bool overflow) 1218 if (isCustomUnsigned!T) 1219 { 1220 enum bits = T.sizeof * 8; 1221 1222 if (x == 0U || y == 0U) 1223 return T.min; 1224 if (x == 1) 1225 return y; 1226 if (y == 1) 1227 return x; 1228 if ((x & (x - 1)) == 0U) 1229 { 1230 auto lz = clz(y); 1231 auto shift = ctz(x); 1232 if (lz < shift) 1233 overflow = true; 1234 return y << shift; 1235 } 1236 if ((y & (y - 1)) == 0U) 1237 { 1238 auto lz = clz(x); 1239 auto shift = ctz(y); 1240 if (lz < shift) 1241 overflow = true; 1242 return x << shift; 1243 } 1244 if (x == y) 1245 return sqru(x, overflow); 1246 1247 auto t = xmul(x.lo, y.lo); 1248 auto w0 = t.lo; 1249 auto k = t.hi; 1250 1251 t = xmul(x.hi, y.lo) + k; 1252 auto w2 = t.hi; 1253 1254 t = xmul(x.lo, y.hi) + t.lo; 1255 1256 if (w2 || t.hi) 1257 overflow = true; 1258 else if (xmul(x.hi, y.hi)) 1259 overflow = true; 1260 1261 return (t << (bits / 2)) + w0; 1262 } 1263 1264 auto xsqr(T)(auto const ref T x) 1265 if (isCustomUnsigned!T) 1266 { 1267 1268 enum bits = T.sizeof * 8; 1269 enum rbits = bits * 2; 1270 alias R = unsigned!rbits; 1271 1272 immutable hilo = xmul(x.lo, x.hi); 1273 1274 auto t = xsqr(x.lo); 1275 auto w0 = t.lo; 1276 auto k = t.hi; 1277 1278 t = hilo + k; 1279 auto w2 = t.hi; 1280 1281 t = hilo + t.lo; 1282 1283 return R(xsqr(x.hi) + w2 + t.hi, (t << (bits / 2)) + w0); 1284 } 1285 1286 T sqru(T)(auto const ref T x, ref bool overflow) 1287 if (isCustomUnsigned!T) 1288 { 1289 enum bits = T.sizeof * 8; 1290 1291 immutable hilo = xmul(x.lo, x.hi); 1292 auto t = xsqr(x.lo); 1293 auto w0 = t.lo; 1294 auto k = t.hi; 1295 1296 t = hilo + k; 1297 auto w2 = t.hi; 1298 1299 t = hilo + t.lo; 1300 1301 if (w2 || t.hi) 1302 overflow = true; 1303 else if (xhi) 1304 overflow = true; 1305 1306 return (t << (bits / 2)) + w0; 1307 } 1308 1309 auto xmul(T, U)(auto const ref T x, auto const ref U y) 1310 if (isCustomUnsigned!T && isUnsignedAssignable!(T.HALF, U)) 1311 { 1312 1313 enum bits = T.sizeof * 8; 1314 enum rbits = bits * 2; 1315 alias R = unsigned!rbits; 1316 1317 if (x == 0U || y == 0U) 1318 return R.min; 1319 if (x == 1U) 1320 return R(y); 1321 if (y == 1U) 1322 return R(x); 1323 if ((x & (x - 1U)) == 0U) 1324 return R(y) << ctz(x); 1325 if ((y & (y - 1U)) == 0U) 1326 return R(x) << ctz(y); 1327 1328 auto t = xmul(x.lo, y); 1329 auto w0 = t.lo; 1330 auto k = t.hi; 1331 1332 t = xmul(x.hi, y) + k; 1333 auto w2 = t.hi; 1334 1335 t = t.lo; 1336 1337 return R(w2, (t << (bits / 2)) + w0); 1338 } 1339 1340 T mulu(T, U)(auto const ref T x, auto const ref U y, ref bool overflow) 1341 if (isCustomUnsigned!T && isUnsignedAssignable!(T.HALF, U)) 1342 { 1343 1344 enum bits = T.sizeof * 8; 1345 1346 if (x == 0U || y == 0U) 1347 return T.min; 1348 if (x == 1U) 1349 return T(y); 1350 if (y == 1U) 1351 return x; 1352 if ((x & (x - 1U)) == 0U) 1353 { 1354 auto yy = T(y); 1355 auto lz = clz(y); 1356 auto shift = ctz(x); 1357 if (lz < shift) 1358 overflow = true; 1359 return yy << shift; 1360 } 1361 if ((y & (y - 1)) == 0U) 1362 { 1363 auto lz = clz(x); 1364 auto shift = ctz(y); 1365 if (lz < shift) 1366 overflow = true; 1367 return x << shift; 1368 } 1369 1370 auto t = xmul(x.lo, y); 1371 auto w0 = t.lo; 1372 auto k = t.hi; 1373 1374 t = xmul(x.hi, y) + k; 1375 1376 if (t.hi) 1377 overflow = true; 1378 1379 t = t.lo; 1380 1381 return (t << (bits / 2)) + w0; 1382 } 1383 1384 @safe pure nothrow @nogc 1385 auto clz(const uint x) 1386 { 1387 return x ? 31 - bsr(x) : 0; 1388 } 1389 1390 @safe pure nothrow @nogc 1391 auto clz(const ulong x) 1392 { 1393 if (!x) 1394 return 64; 1395 static if (is(size_t == ulong)) 1396 return 63 - bsr(x); 1397 else static if(is(size_t == uint)) 1398 { 1399 immutable hi = cast(uint)(x >> 32); 1400 if (hi) 1401 return 31 - bsr(hi); 1402 else 1403 return 63 - bsr(cast(uint)x); 1404 } 1405 else 1406 static assert(0); 1407 } 1408 1409 auto clz(T)(auto const ref T x) 1410 if (isCustomUnsigned!T) 1411 { 1412 enum bits = T.sizeof * 8; 1413 auto ret = clz(x.hi); 1414 return ret == bits / 2 ? ret + clz(x.lo) : ret; 1415 } 1416 1417 @safe pure nothrow @nogc 1418 auto ctz(const uint x) 1419 { 1420 return x ? bsf(x) : 0; 1421 } 1422 1423 @safe pure nothrow @nogc 1424 auto ctz(const ulong x) 1425 { 1426 if (!x) 1427 return 64; 1428 static if (is(size_t == ulong)) 1429 return bsf(x); 1430 else static if (is(size_t == uint)) 1431 { 1432 immutable lo = cast(uint)x; 1433 if (lo) 1434 return bsf(lo); 1435 else 1436 return bsf(cast(uint)(x >> 32)) + 32; 1437 } 1438 else 1439 static assert(0); 1440 } 1441 1442 auto ctz(T)(auto const ref T x) 1443 if (isCustomUnsigned!T) 1444 { 1445 enum bits = T.sizeof * 8; 1446 auto ret = ctz(x.lo); 1447 return ret == bits / 2 ? ret + ctz(x.hi) : ret; 1448 } 1449 1450 bool ispow2(T)(auto const ref T x) 1451 if (isAnyUnsigned!T) 1452 { 1453 return x != 0U && (x & (x - 1U)) == 0; 1454 } 1455 1456 bool ispow10(T)(auto const ref T x) 1457 if (isAnyUnsigned!T) 1458 { 1459 if (x == 0U) 1460 return false; 1461 1462 for (size_t i = 0; i < pow10!T.length; ++i) 1463 { 1464 if (x == pow10!T[i]) 1465 return true; 1466 else if (x < pow10!T[i]) 1467 return false; 1468 } 1469 return false; 1470 } 1471 1472 1473 1474 1475 @safe pure nothrow @nogc 1476 uint divrem(ref uint x, const uint y) 1477 { 1478 uint ret = x % y; 1479 x /= y; 1480 return ret; 1481 } 1482 1483 @safe pure nothrow @nogc 1484 ulong divrem(ref ulong x, const ulong y) 1485 { 1486 ulong ret = x % y; 1487 x /= y; 1488 return ret; 1489 } 1490 1491 @safe pure nothrow @nogc 1492 ulong divrem(ref ulong x, const uint y) 1493 { 1494 ulong ret = x % y; 1495 x /= y; 1496 return ret; 1497 } 1498 1499 T divrem(T)(ref T x, auto const ref T y) 1500 if (isCustomUnsigned!T) 1501 { 1502 Unqual!T r; 1503 int shift; 1504 1505 if (!x.hi) 1506 { 1507 if (!y.hi) 1508 return Unqual!T(divrem(x.lo, y.lo)); 1509 r.lo = x.lo; 1510 x.lo = 0U; 1511 return r; 1512 } 1513 1514 if (!y.lo) 1515 { 1516 if (!y.hi) 1517 return Unqual!T(divrem(x.hi, y.lo)); 1518 if (!x.lo) 1519 { 1520 r.hi = divrem(x.hi, y.hi); 1521 x.lo = x.hi; 1522 x.hi = 0U; 1523 return r; 1524 } 1525 if ((y.hi & (y.hi - 1U)) == 0U) 1526 { 1527 r.lo = x.lo; 1528 r.hi = x.hi & (y.hi - 1U); 1529 x.lo = x.hi >>> ctz(y.hi); 1530 x.hi = 0U; 1531 return r; 1532 } 1533 shift = clz(y.hi) - clz(x.hi); 1534 if (shift > T.HALF.sizeof * 8 - 2) 1535 { 1536 r = x; 1537 x = 0U; 1538 return r; 1539 } 1540 } 1541 else 1542 { 1543 if (!y.hi) 1544 { 1545 if ((y.lo & (y.lo - 1U)) == 0U) 1546 { 1547 r.lo = x.lo & (y.lo - 1U); 1548 if (y.lo == 1U) 1549 return r; 1550 x >>= ctz(y.lo); 1551 return r; 1552 } 1553 } 1554 else 1555 { 1556 shift = clz(y.hi) - clz(x.hi); 1557 if (shift > T.HALF.sizeof * 8 - 1) 1558 { 1559 r = x; 1560 x = 0U; 1561 return r; 1562 } 1563 } 1564 } 1565 1566 r = x; 1567 T d = y; 1568 T z = 1U; 1569 x = 0U; 1570 1571 shift = clz(d); 1572 1573 z <<= shift; 1574 d <<= shift; 1575 1576 while(z) 1577 { 1578 if (r >= d) 1579 { 1580 r -= d; 1581 x |= z; 1582 } 1583 z >>= 1; 1584 d >>= 1; 1585 } 1586 1587 return r; 1588 } 1589 1590 T divrem(T, U)(ref T x, auto const ref U y) 1591 if (isCustomUnsigned!T && isUnsignedAssignable!(T.HALF, U)) 1592 { 1593 Unqual!T r; 1594 int shift; 1595 1596 if (!x.hi) 1597 return Unqual!T(divrem(x.lo, y)); 1598 1599 if (!y) 1600 return Unqual!T(divrem(x.hi, y)); 1601 1602 if ((y & (y - 1U)) == 0U) 1603 { 1604 r.lo = x.lo & (y - 1U); 1605 if (y == 1U) 1606 return r; 1607 x >>= ctz(y); 1608 return r; 1609 } 1610 1611 1612 r = x; 1613 T d = y; 1614 T z = 1U; 1615 x = 0U; 1616 1617 shift = clz(d); 1618 1619 z <<= shift; 1620 d <<= shift; 1621 1622 while(z) 1623 { 1624 if (r >= d) 1625 { 1626 r -= d; 1627 x |= z; 1628 } 1629 z >>= 1; 1630 d >>= 1; 1631 } 1632 1633 return r; 1634 } 1635 1636 int prec(T)(const T x) 1637 if (isUnsigned!T || is(T : uint128) || is(T : uint256) || is(T : uint512)) 1638 { 1639 static foreach_reverse(i, p; pow10!T) 1640 { 1641 if (x >= p) 1642 return i + 1; 1643 } 1644 return 0; 1645 } 1646 1647 //returns power of 10 if x is power of 10, -1 otherwise 1648 @safe pure nothrow @nogc 1649 int getPow10(T)(auto const ref T x) 1650 if (isUnsigned!T || is(T : uint128) || is(T : uint256)) 1651 { 1652 static foreach_reverse(i, p; pow10!T) 1653 { 1654 if (x == p) 1655 return i + 1; 1656 else if (x < p) 1657 return -1; 1658 } 1659 return 0; 1660 } 1661 1662 T cvt(T, U)(auto const ref U value) 1663 if (isAnyUnsigned!T && isAnyUnsigned!U) 1664 { 1665 static if (T.sizeof > U.sizeof) 1666 return (T(value)); 1667 else static if (T.sizeof < U.sizeof) 1668 return cast(T)(value); 1669 else 1670 return value; 1671 } 1672 1673 auto sign(S, U)(const U u, const bool isNegative) 1674 if (isUnsigned!U && isSigned!S) 1675 { 1676 static if (is(U: ubyte) || is(U: ushort)) 1677 return isNegative ? cast(S)-cast(int)u : cast(S)u; 1678 else static if (is(S: byte) || is(S: short)) 1679 return isNegative ? cast(S)-cast(int)u : cast(S)u; 1680 else 1681 return isNegative ? -cast(S)u : cast(S)u; 1682 } 1683 1684 unittest 1685 { 1686 static assert (sign!byte(ubyte(128), true) == byte.min); 1687 static assert (sign!byte(ushort(128), true) == byte.min); 1688 static assert (sign!byte(uint(128), true) == byte.min); 1689 static assert (sign!byte(ulong(128), true) == byte.min); 1690 1691 static assert (sign!short(ubyte(128), true) == byte.min); 1692 static assert (sign!short(ushort(32768), true) == short.min); 1693 static assert (sign!short(uint(32768), true) == short.min); 1694 static assert (sign!short(ulong(32768), true) == short.min); 1695 1696 1697 static assert (sign!int(ubyte(128), true) == byte.min); 1698 static assert (sign!int(ushort(32768), true) == short.min); 1699 static assert (sign!int(uint(2147483648), true) == int.min); 1700 static assert (sign!int(ulong(2147483648), true) == int.min); 1701 1702 static assert (sign!long(ubyte(128), true) == byte.min); 1703 static assert (sign!long(ushort(32768), true) == short.min); 1704 static assert (sign!long(uint(2147483648), true) == int.min); 1705 static assert (sign!long(ulong(9223372036854775808UL), true) == long.min); 1706 1707 } 1708 1709 auto sign(S, U)(const U u, const bool isNegative) 1710 if (isCustomUnsigned!U && isSigned!S) 1711 { 1712 return isNegative ? cast(S)-cast(ulong)u : cast(S)cast(ulong)u; 1713 } 1714 1715 auto unsign(U, S)(const S s, out bool isNegative) 1716 if (isUnsigned!U && isSigned!S) 1717 { 1718 isNegative = s < 0; 1719 static if (is(S: byte) || is(S: short)) 1720 return isNegative ? cast(U)-cast(int)s : cast(U)s; 1721 else static if (is(U: ubyte) || is(U: ushort)) 1722 return isNegative ? cast(U)-cast(int)s : cast(U)s; 1723 else 1724 return isNegative? -cast(U)s: cast(U)s; 1725 } 1726 1727 unittest 1728 { 1729 1730 static assert (unsign!ubyte(byte.min) == 128); 1731 static assert (unsign!ubyte(short(-128)) == 128); 1732 static assert (unsign!ubyte(int(-128)) == 128); 1733 static assert (unsign!ubyte(long(-128)) == 128); 1734 1735 static assert (unsign!ushort(byte.min) == 128); 1736 static assert (unsign!ushort(short.min) == 32768); 1737 static assert (unsign!ushort(int(short.min)) == 32768); 1738 static assert (unsign!ushort(long(short.min)) == 32768); 1739 1740 static assert (unsign!uint(byte.min) == 128); 1741 static assert (unsign!uint(short.min) == 32768); 1742 static assert (unsign!uint(int.min) == 2147483648); 1743 static assert (unsign!uint(long(int.min)) == 2147483648); 1744 1745 static assert (unsign!ulong(byte.min) == 128); 1746 static assert (unsign!ulong(short.min) == 32768); 1747 static assert (unsign!ulong(int.min) == 2147483648); 1748 static assert (unsign!ulong(long.min) == 9223372036854775808UL); 1749 1750 1751 } 1752 1753 auto unsign(U, V)(const V v, out bool isNegative) 1754 if (isUnsigned!U && isUnsigned!V) 1755 { 1756 isNegative = false; 1757 return cast(U)v; 1758 } 1759 1760 auto unsign(U, V)(const V v, out bool isNegative) 1761 if (isCustomUnsigned!U && isUnsigned!V) 1762 { 1763 isNegative = false; 1764 return U(v); 1765 } 1766 1767 auto unsign(U, S)(const S s) 1768 if (isUnsigned!U && isSigned!S) 1769 { 1770 static if (is(S: byte) || is(S: short)) 1771 return s < 0 ? cast(U)-cast(int)s : cast(U)s; 1772 else static if (is(U: ubyte) || is(U: ushort)) 1773 return s < 0 ? cast(U)-cast(int)s : cast(U)s; 1774 else 1775 return s < 0 ? -cast(U)s: cast(U)s; 1776 } 1777 1778 1779 1780 auto unsign(U, S)(const S s, out bool isNegative) 1781 if (isCustomUnsigned!U && isSigned!S) 1782 { 1783 isNegative = s < 0; 1784 static if (is(S: byte) || is(S: short)) 1785 return isNegative ? U(cast(uint)-cast(int)s) : U(cast(uint)s); 1786 else static if (is(S: int)) 1787 return isNegative ? U(cast(ulong)(-cast(long)s)) : U(cast(uint)s); 1788 else 1789 return isNegative ? U(cast(ulong)-s) : U(cast(ulong)s); 1790 } 1791 1792 auto unsign(U, S)(const S s) 1793 if (isCustomUnsigned!U && isSigned!S) 1794 { 1795 static if (is(S: byte) || is(S: short)) 1796 return s < 0 ? U(cast(uint)-cast(int)s) : U(cast(uint)s); 1797 else static if (is(S: int)) 1798 return s < 0 ? U(cast(ulong)(-cast(long)s)) : U(cast(uint)s); 1799 else 1800 return s < 0 ? U(cast(ulong)-s) : U(cast(ulong)s); 1801 } 1802 1803 1804 1805 1806 1807 1808 pure @safe nothrow @nogc 1809 int cappedSub(ref int target, const int value) 1810 { 1811 bool ovf; 1812 int result = subs(target, value, ovf); 1813 if (ovf) 1814 { 1815 if (value > 0) 1816 { 1817 //target was negative 1818 result = target - int.min; 1819 target = int.min; 1820 } 1821 else 1822 { 1823 //target was positive 1824 result = target - int.max; 1825 target = int.max; 1826 } 1827 return result; 1828 } 1829 else 1830 { 1831 target -= value; 1832 return value; 1833 } 1834 } 1835 1836 pure @safe nothrow @nogc 1837 int cappedAdd(ref int target, const int value) 1838 { 1839 bool ovf; 1840 int result = adds(target, value, ovf); 1841 if (ovf) 1842 { 1843 if (value > 0) 1844 { 1845 //target was positive 1846 result = int.max - target; 1847 target = int.max; 1848 } 1849 else 1850 { 1851 //target was negative 1852 result = int.min - target; 1853 target = int.min; 1854 } 1855 return result; 1856 } 1857 else 1858 { 1859 target += value; 1860 return value; 1861 } 1862 } 1863 1864 unittest 1865 { 1866 int ex = int.min + 1; 1867 int px = cappedSub(ex, 3); 1868 assert (ex == int.min); 1869 assert (px == 1); 1870 1871 ex = int.min + 3; 1872 px = cappedSub(ex, 2); 1873 assert (ex == int.min + 1); 1874 assert (px == 2); 1875 1876 ex = int.max - 1; 1877 px = cappedSub(ex, -2); 1878 assert (ex == int.max); 1879 assert (px == -1); 1880 1881 ex = int.max - 3; 1882 px = cappedSub(ex, -2); 1883 assert (ex == int.max - 1); 1884 assert(px == -2); 1885 1886 1887 } 1888 1889 /* ****************************************************************************************************************** */ 1890 /* 10-POWER CONSTANTS */ 1891 /* ****************************************************************************************************************** */ 1892 1893 immutable ubyte[3] pow10_8 = 1894 [ 1895 1U, 1896 10U, 1897 100U, 1898 ]; 1899 1900 immutable ushort[5] pow10_16 = 1901 [ 1902 1U, 1903 10U, 1904 100U, 1905 1000U, 1906 10000U, 1907 ]; 1908 1909 immutable uint[10] pow10_32 = 1910 [ 1911 1U, 1912 10U, 1913 100U, 1914 1000U, 1915 10000U, 1916 100000U, 1917 1000000U, 1918 10000000U, 1919 100000000U, 1920 1000000000U 1921 ]; 1922 1923 immutable ulong[20] pow10_64 = 1924 [ 1925 1UL, 1926 10UL, 1927 100UL, 1928 1000UL, 1929 10000UL, 1930 100000UL, 1931 1000000UL, 1932 10000000UL, 1933 100000000UL, 1934 1000000000UL, 1935 10000000000UL, 1936 100000000000UL, 1937 1000000000000UL, 1938 10000000000000UL, 1939 100000000000000UL, 1940 1000000000000000UL, 1941 10000000000000000UL, 1942 100000000000000000UL, 1943 1000000000000000000UL, 1944 10000000000000000000UL, 1945 ]; 1946 1947 immutable uint128[39] pow10_128 = 1948 [ 1949 uint128(1UL), 1950 uint128(10UL), 1951 uint128(100UL), 1952 uint128(1000UL), 1953 uint128(10000UL), 1954 uint128(100000UL), 1955 uint128(1000000UL), 1956 uint128(10000000UL), 1957 uint128(100000000UL), 1958 uint128(1000000000UL), 1959 uint128(10000000000UL), 1960 uint128(100000000000UL), 1961 uint128(1000000000000UL), 1962 uint128(10000000000000UL), 1963 uint128(100000000000000UL), 1964 uint128(1000000000000000UL), 1965 uint128(10000000000000000UL), 1966 uint128(100000000000000000UL), 1967 uint128(1000000000000000000UL), 1968 uint128(10000000000000000000UL), 1969 uint128("100000000000000000000"), 1970 uint128("1000000000000000000000"), 1971 uint128("10000000000000000000000"), 1972 uint128("100000000000000000000000"), 1973 uint128("1000000000000000000000000"), 1974 uint128("10000000000000000000000000"), 1975 uint128("100000000000000000000000000"), 1976 uint128("1000000000000000000000000000"), 1977 uint128("10000000000000000000000000000"), 1978 uint128("100000000000000000000000000000"), 1979 uint128("1000000000000000000000000000000"), 1980 uint128("10000000000000000000000000000000"), 1981 uint128("100000000000000000000000000000000"), 1982 uint128("1000000000000000000000000000000000"), 1983 uint128("10000000000000000000000000000000000"), 1984 uint128("100000000000000000000000000000000000"), 1985 uint128("1000000000000000000000000000000000000"), 1986 uint128("10000000000000000000000000000000000000"), 1987 uint128("100000000000000000000000000000000000000"), 1988 ]; 1989 1990 immutable uint256[78] pow10_256 = 1991 [ 1992 uint256(1UL), 1993 uint256(10UL), 1994 uint256(100UL), 1995 uint256(1000UL), 1996 uint256(10000UL), 1997 uint256(100000UL), 1998 uint256(1000000UL), 1999 uint256(10000000UL), 2000 uint256(100000000UL), 2001 uint256(1000000000UL), 2002 uint256(10000000000UL), 2003 uint256(100000000000UL), 2004 uint256(1000000000000UL), 2005 uint256(10000000000000UL), 2006 uint256(100000000000000UL), 2007 uint256(1000000000000000UL), 2008 uint256(10000000000000000UL), 2009 uint256(100000000000000000UL), 2010 uint256(1000000000000000000UL), 2011 uint256(10000000000000000000UL), 2012 uint256("100000000000000000000"), 2013 uint256("1000000000000000000000"), 2014 uint256("10000000000000000000000"), 2015 uint256("100000000000000000000000"), 2016 uint256("1000000000000000000000000"), 2017 uint256("10000000000000000000000000"), 2018 uint256("100000000000000000000000000"), 2019 uint256("1000000000000000000000000000"), 2020 uint256("10000000000000000000000000000"), 2021 uint256("100000000000000000000000000000"), 2022 uint256("1000000000000000000000000000000"), 2023 uint256("10000000000000000000000000000000"), 2024 uint256("100000000000000000000000000000000"), 2025 uint256("1000000000000000000000000000000000"), 2026 uint256("10000000000000000000000000000000000"), 2027 uint256("100000000000000000000000000000000000"), 2028 uint256("1000000000000000000000000000000000000"), 2029 uint256("10000000000000000000000000000000000000"), 2030 uint256("100000000000000000000000000000000000000"), 2031 uint256("1000000000000000000000000000000000000000"), 2032 uint256("10000000000000000000000000000000000000000"), 2033 uint256("100000000000000000000000000000000000000000"), 2034 uint256("1000000000000000000000000000000000000000000"), 2035 uint256("10000000000000000000000000000000000000000000"), 2036 uint256("100000000000000000000000000000000000000000000"), 2037 uint256("1000000000000000000000000000000000000000000000"), 2038 uint256("10000000000000000000000000000000000000000000000"), 2039 uint256("100000000000000000000000000000000000000000000000"), 2040 uint256("1000000000000000000000000000000000000000000000000"), 2041 uint256("10000000000000000000000000000000000000000000000000"), 2042 uint256("100000000000000000000000000000000000000000000000000"), 2043 uint256("1000000000000000000000000000000000000000000000000000"), 2044 uint256("10000000000000000000000000000000000000000000000000000"), 2045 uint256("100000000000000000000000000000000000000000000000000000"), 2046 uint256("1000000000000000000000000000000000000000000000000000000"), 2047 uint256("10000000000000000000000000000000000000000000000000000000"), 2048 uint256("100000000000000000000000000000000000000000000000000000000"), 2049 uint256("1000000000000000000000000000000000000000000000000000000000"), 2050 uint256("10000000000000000000000000000000000000000000000000000000000"), 2051 uint256("100000000000000000000000000000000000000000000000000000000000"), 2052 uint256("1000000000000000000000000000000000000000000000000000000000000"), 2053 uint256("10000000000000000000000000000000000000000000000000000000000000"), 2054 uint256("100000000000000000000000000000000000000000000000000000000000000"), 2055 uint256("1000000000000000000000000000000000000000000000000000000000000000"), 2056 uint256("10000000000000000000000000000000000000000000000000000000000000000"), 2057 uint256("100000000000000000000000000000000000000000000000000000000000000000"), 2058 uint256("1000000000000000000000000000000000000000000000000000000000000000000"), 2059 uint256("10000000000000000000000000000000000000000000000000000000000000000000"), 2060 uint256("100000000000000000000000000000000000000000000000000000000000000000000"), 2061 uint256("1000000000000000000000000000000000000000000000000000000000000000000000"), 2062 uint256("10000000000000000000000000000000000000000000000000000000000000000000000"), 2063 uint256("100000000000000000000000000000000000000000000000000000000000000000000000"), 2064 uint256("1000000000000000000000000000000000000000000000000000000000000000000000000"), 2065 uint256("10000000000000000000000000000000000000000000000000000000000000000000000000"), 2066 uint256("100000000000000000000000000000000000000000000000000000000000000000000000000"), 2067 uint256("1000000000000000000000000000000000000000000000000000000000000000000000000000"), 2068 uint256("10000000000000000000000000000000000000000000000000000000000000000000000000000"), 2069 uint256("100000000000000000000000000000000000000000000000000000000000000000000000000000"), 2070 ]; 2071 2072 immutable uint512[155] pow10_512 = 2073 [ 2074 uint512(1UL), //0 - 2074 2075 uint512(10UL), //1 - 2075 2076 uint512(100UL), 2077 uint512(1000UL), 2078 uint512(10000UL), 2079 uint512(100000UL), 2080 uint512(1000000UL), 2081 uint512(10000000UL), 2082 uint512(100000000UL), 2083 uint512(1000000000UL), 2084 uint512(10000000000UL), 2085 uint512(100000000000UL), 2086 uint512(1000000000000UL), 2087 uint512(10000000000000UL), 2088 uint512(100000000000000UL), 2089 uint512(1000000000000000UL), 2090 uint512(10000000000000000UL), 2091 uint512(100000000000000000UL), 2092 uint512(1000000000000000000UL), 2093 uint512(10000000000000000000UL), 2094 uint512("100000000000000000000"), 2095 uint512("1000000000000000000000"), 2096 uint512("10000000000000000000000"), 2097 uint512("100000000000000000000000"), 2098 uint512("1000000000000000000000000"), 2099 uint512("10000000000000000000000000"), 2100 uint512("100000000000000000000000000"), 2101 uint512("1000000000000000000000000000"), 2102 uint512("10000000000000000000000000000"), 2103 uint512("100000000000000000000000000000"), 2104 uint512("1000000000000000000000000000000"), 2105 uint512("10000000000000000000000000000000"), 2106 uint512("100000000000000000000000000000000"), 2107 uint512("1000000000000000000000000000000000"), 2108 uint512("10000000000000000000000000000000000"), 2109 uint512("100000000000000000000000000000000000"), 2110 uint512("1000000000000000000000000000000000000"), 2111 uint512("10000000000000000000000000000000000000"), 2112 uint512("100000000000000000000000000000000000000"), 2113 uint512("1000000000000000000000000000000000000000"), 2114 uint512("10000000000000000000000000000000000000000"), 2115 uint512("100000000000000000000000000000000000000000"), 2116 uint512("1000000000000000000000000000000000000000000"), 2117 uint512("10000000000000000000000000000000000000000000"), 2118 uint512("100000000000000000000000000000000000000000000"), 2119 uint512("1000000000000000000000000000000000000000000000"), 2120 uint512("10000000000000000000000000000000000000000000000"), 2121 uint512("100000000000000000000000000000000000000000000000"), 2122 uint512("1000000000000000000000000000000000000000000000000"), 2123 uint512("10000000000000000000000000000000000000000000000000"), 2124 uint512("100000000000000000000000000000000000000000000000000"), 2125 uint512("1000000000000000000000000000000000000000000000000000"), 2126 uint512("10000000000000000000000000000000000000000000000000000"), 2127 uint512("100000000000000000000000000000000000000000000000000000"), 2128 uint512("1000000000000000000000000000000000000000000000000000000"), 2129 uint512("10000000000000000000000000000000000000000000000000000000"), 2130 uint512("100000000000000000000000000000000000000000000000000000000"), 2131 uint512("1000000000000000000000000000000000000000000000000000000000"), 2132 uint512("10000000000000000000000000000000000000000000000000000000000"), 2133 uint512("100000000000000000000000000000000000000000000000000000000000"), 2134 uint512("1000000000000000000000000000000000000000000000000000000000000"), 2135 uint512("10000000000000000000000000000000000000000000000000000000000000"), 2136 uint512("100000000000000000000000000000000000000000000000000000000000000"), 2137 uint512("1000000000000000000000000000000000000000000000000000000000000000"), 2138 uint512("10000000000000000000000000000000000000000000000000000000000000000"), 2139 uint512("100000000000000000000000000000000000000000000000000000000000000000"), 2140 uint512("1000000000000000000000000000000000000000000000000000000000000000000"), 2141 uint512("10000000000000000000000000000000000000000000000000000000000000000000"), 2142 uint512("100000000000000000000000000000000000000000000000000000000000000000000"), 2143 uint512("1000000000000000000000000000000000000000000000000000000000000000000000"), 2144 uint512("10000000000000000000000000000000000000000000000000000000000000000000000"), 2145 uint512("100000000000000000000000000000000000000000000000000000000000000000000000"), 2146 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000"), 2147 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000"), 2148 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000"), 2149 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000"), 2150 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000"), 2151 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000"), 2152 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2153 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2154 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2155 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2156 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2157 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2158 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2159 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2160 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2161 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2162 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2163 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2164 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2165 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2166 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2167 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2168 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2169 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2170 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2171 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2172 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2173 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2174 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2175 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2176 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2177 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2178 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2179 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2180 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2181 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2182 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2183 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2184 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2185 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2186 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2187 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2188 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2189 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2190 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2191 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2192 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2193 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2194 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2195 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2196 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2197 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2198 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2199 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2200 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2201 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2202 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2203 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2204 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2205 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2206 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2207 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2208 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2209 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2210 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2211 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2212 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2213 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2214 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2215 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2216 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2217 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2218 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2219 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2220 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2221 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2222 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2223 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2224 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2225 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2226 uint512("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2227 uint512("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2228 uint512("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"), 2229 ]; 2230 2231 2232 template pow10(T) 2233 { 2234 static if (is(Unqual!T == uint)) 2235 alias pow10 = pow10_32; 2236 else static if (is(Unqual!T == ulong)) 2237 alias pow10 = pow10_64; 2238 else static if (is(Unqual!T == uint128)) 2239 alias pow10 = pow10_128; 2240 else static if (is(Unqual!T == uint256)) 2241 alias pow10 = pow10_256; 2242 else static if (is(Unqual!T == uint512)) 2243 alias pow10 = pow10_512; 2244 else static if (is(Unqual!T == ushort)) 2245 alias pow10 = pow10_16; 2246 else static if (is(Unqual!T == ubyte)) 2247 alias pow10 = pow10_8; 2248 else 2249 static assert(0); 2250 } 2251 2252 /* ****************************************************************************************************************** */ 2253 /* MAXIMUM COEFFICIENTS THAT CAN BE MULTIPLIED BY 10-POWERS */ 2254 /* ****************************************************************************************************************** */ 2255 2256 immutable ubyte[3] maxmul10_8 = 2257 [ 2258 255U, 2259 25U, 2260 2U, 2261 ]; 2262 2263 immutable ushort[5] maxmul10_16 = 2264 [ 2265 65535U, 2266 6553U, 2267 655U, 2268 65U, 2269 6U, 2270 ]; 2271 2272 immutable uint[10] maxmul10_32 = 2273 [ 2274 4294967295U, 2275 429496729U, 2276 42949672U, 2277 4294967U, 2278 429496U, 2279 42949U, 2280 4294U, 2281 429U, 2282 42U, 2283 4U, 2284 ]; 2285 2286 immutable ulong[20] maxmul10_64 = 2287 [ 2288 18446744073709551615UL, 2289 1844674407370955161UL, 2290 184467440737095516UL, 2291 18446744073709551UL, 2292 1844674407370955UL, 2293 184467440737095UL, 2294 18446744073709UL, 2295 1844674407370UL, 2296 184467440737UL, 2297 18446744073UL, 2298 1844674407UL, 2299 184467440UL, 2300 18446744UL, 2301 1844674UL, 2302 184467UL, 2303 18446UL, 2304 1844UL, 2305 184UL, 2306 18UL, 2307 1UL, 2308 ]; 2309 2310 immutable uint128[39] maxmul10_128 = 2311 [ 2312 uint128("340282366920938463463374607431768211455"), 2313 uint128("34028236692093846346337460743176821145"), 2314 uint128("3402823669209384634633746074317682114"), 2315 uint128("340282366920938463463374607431768211"), 2316 uint128("34028236692093846346337460743176821"), 2317 uint128("3402823669209384634633746074317682"), 2318 uint128("340282366920938463463374607431768"), 2319 uint128("34028236692093846346337460743176"), 2320 uint128("3402823669209384634633746074317"), 2321 uint128("340282366920938463463374607431"), 2322 uint128("34028236692093846346337460743"), 2323 uint128("3402823669209384634633746074"), 2324 uint128("340282366920938463463374607"), 2325 uint128("34028236692093846346337460"), 2326 uint128("3402823669209384634633746"), 2327 uint128("340282366920938463463374"), 2328 uint128("34028236692093846346337"), 2329 uint128("3402823669209384634633"), 2330 uint128("340282366920938463463"), 2331 uint128("34028236692093846346"), 2332 uint128(3402823669209384634UL), 2333 uint128(340282366920938463UL), 2334 uint128(34028236692093846UL), 2335 uint128(3402823669209384UL), 2336 uint128(340282366920938UL), 2337 uint128(34028236692093UL), 2338 uint128(3402823669209UL), 2339 uint128(340282366920UL), 2340 uint128(34028236692UL), 2341 uint128(3402823669UL), 2342 uint128(340282366UL), 2343 uint128(34028236UL), 2344 uint128(3402823UL), 2345 uint128(340282UL), 2346 uint128(34028UL), 2347 uint128(3402UL), 2348 uint128(340UL), 2349 uint128(34UL), 2350 uint128(3UL), 2351 ]; 2352 2353 immutable uint256[78] maxmul10_256 = 2354 [ 2355 uint256("115792089237316195423570985008687907853269984665640564039457584007913129639935"), 2356 uint256("11579208923731619542357098500868790785326998466564056403945758400791312963993"), 2357 uint256("1157920892373161954235709850086879078532699846656405640394575840079131296399"), 2358 uint256("115792089237316195423570985008687907853269984665640564039457584007913129639"), 2359 uint256("11579208923731619542357098500868790785326998466564056403945758400791312963"), 2360 uint256("1157920892373161954235709850086879078532699846656405640394575840079131296"), 2361 uint256("115792089237316195423570985008687907853269984665640564039457584007913129"), 2362 uint256("11579208923731619542357098500868790785326998466564056403945758400791312"), 2363 uint256("1157920892373161954235709850086879078532699846656405640394575840079131"), 2364 uint256("115792089237316195423570985008687907853269984665640564039457584007913"), 2365 uint256("11579208923731619542357098500868790785326998466564056403945758400791"), 2366 uint256("1157920892373161954235709850086879078532699846656405640394575840079"), 2367 uint256("115792089237316195423570985008687907853269984665640564039457584007"), 2368 uint256("11579208923731619542357098500868790785326998466564056403945758400"), 2369 uint256("1157920892373161954235709850086879078532699846656405640394575840"), 2370 uint256("115792089237316195423570985008687907853269984665640564039457584"), 2371 uint256("11579208923731619542357098500868790785326998466564056403945758"), 2372 uint256("1157920892373161954235709850086879078532699846656405640394575"), 2373 uint256("115792089237316195423570985008687907853269984665640564039457"), 2374 uint256("11579208923731619542357098500868790785326998466564056403945"), 2375 uint256("1157920892373161954235709850086879078532699846656405640394"), 2376 uint256("115792089237316195423570985008687907853269984665640564039"), 2377 uint256("11579208923731619542357098500868790785326998466564056403"), 2378 uint256("1157920892373161954235709850086879078532699846656405640"), 2379 uint256("115792089237316195423570985008687907853269984665640564"), 2380 uint256("11579208923731619542357098500868790785326998466564056"), 2381 uint256("1157920892373161954235709850086879078532699846656405"), 2382 uint256("115792089237316195423570985008687907853269984665640"), 2383 uint256("11579208923731619542357098500868790785326998466564"), 2384 uint256("1157920892373161954235709850086879078532699846656"), 2385 uint256("115792089237316195423570985008687907853269984665"), 2386 uint256("11579208923731619542357098500868790785326998466"), 2387 uint256("1157920892373161954235709850086879078532699846"), 2388 uint256("115792089237316195423570985008687907853269984"), 2389 uint256("11579208923731619542357098500868790785326998"), 2390 uint256("1157920892373161954235709850086879078532699"), 2391 uint256("115792089237316195423570985008687907853269"), 2392 uint256("11579208923731619542357098500868790785326"), 2393 uint256("1157920892373161954235709850086879078532"), 2394 uint256("115792089237316195423570985008687907853"), 2395 uint256("11579208923731619542357098500868790785"), 2396 uint256("1157920892373161954235709850086879078"), 2397 uint256("115792089237316195423570985008687907"), 2398 uint256("11579208923731619542357098500868790"), 2399 uint256("1157920892373161954235709850086879"), 2400 uint256("115792089237316195423570985008687"), 2401 uint256("11579208923731619542357098500868"), 2402 uint256("1157920892373161954235709850086"), 2403 uint256("115792089237316195423570985008"), 2404 uint256("11579208923731619542357098500"), 2405 uint256("1157920892373161954235709850"), 2406 uint256("115792089237316195423570985"), 2407 uint256("11579208923731619542357098"), 2408 uint256("1157920892373161954235709"), 2409 uint256("115792089237316195423570"), 2410 uint256("11579208923731619542357"), 2411 uint256("1157920892373161954235"), 2412 uint256("115792089237316195423"), 2413 uint256("11579208923731619542"), 2414 uint256("1157920892373161954"), 2415 uint256("115792089237316195"), 2416 uint256(11579208923731619UL), 2417 uint256(1157920892373161UL), 2418 uint256(115792089237316UL), 2419 uint256(11579208923731UL), 2420 uint256(1157920892373UL), 2421 uint256(115792089237UL), 2422 uint256(11579208923UL), 2423 uint256(1157920892UL), 2424 uint256(115792089UL), 2425 uint256(11579208UL), 2426 uint256(1157920UL), 2427 uint256(115792UL), 2428 uint256(11579UL), 2429 uint256(1157UL), 2430 uint256(115UL), 2431 uint256(11UL), 2432 uint256(1UL), 2433 ]; 2434 2435 template maxmul10(T) 2436 { 2437 static if (is(Unqual!T == uint)) 2438 alias maxmul10 = maxmul10_32; 2439 else static if (is(Unqual!T == ulong)) 2440 alias maxmul10 = maxmul10_64; 2441 else static if (is(Unqual!T == uint128)) 2442 alias maxmul10 = maxmul10_128; 2443 else static if (is(Unqual!T == uint256)) 2444 alias maxmul10 = maxmul10_256; 2445 else static if (is(Unqual!T == ushort)) 2446 alias maxmul10 = maxmul10_16; 2447 else static if (is(Unqual!T == ubyte)) 2448 alias maxmul10 = maxmul10_8; 2449 else 2450 static assert(0); 2451 } 2452 2453 2454 2455 //true on inexact 2456 bool sqrt(U)(ref U x) 2457 if (isAnyUnsigned!U) 2458 { 2459 // Newton-Raphson: x = (x + n/x) / 2; 2460 //x 2461 if (x <= 1U) 2462 return false; 2463 immutable n = x; 2464 Unqual!U y; 2465 //1 .. 99 1 x 10^0 .. 99 x 10^0 1 .. 2 //0 - 10^0 <10^1 2 x 10^0, 6x10^0 2466 //100 .. 9999 1 x 10^2 ...99.99 x 10^2 3 .. 4 //2 -10^1 <10^3 2 x 10^1, 6x10^1 2467 //10000 .. 999999 1.x 10^4 ...99999.99 x 10^4 5 .. 6 //4 -10^2 <10^5 2 x 10^2, 6x10^2 2468 auto p = prec(x); 2469 int power = p & 1 ? p - 1 : p - 2; 2470 2471 if (power >= pow10!U.length - 1 || x >= pow10!U[power + 1]) 2472 x = pow10!U[power >> 1] * 6U; 2473 else 2474 x = pow10!U[power >> 1] << 1; //* 2U; 2475 2476 do 2477 { 2478 y = x; 2479 x = (x + n / x) >> 1; 2480 } 2481 while (x != y); 2482 return x * x != n; 2483 } 2484 2485 //true on inexact 2486 bool cbrt(U)(ref U x) 2487 if (isAnyUnsigned!U) 2488 { 2489 // Newton-Raphson: x = (2x + N/x2)/3 2490 if (x <= 1U) 2491 return false; 2492 immutable n = x; 2493 Unqual!U y; 2494 //1 .. 99 1 x 10^0 .. 99 x 10^0 1 .. 2 //0 - 10^0 <10^1 2 x 10^0, 6x10^0 2495 //100 .. 9999 1 x 10^2 ...99.99 x 10^2 3 .. 4 //2 -10^1 <10^3 2 x 10^1, 6x10^1 2496 //10000 .. 999999 1.x 10^4 ...99999.99 x 10^4 5 .. 6 //4 -10^2 <10^5 2 x 10^2, 6x10^2 2497 2498 x /= 3U; 2499 if (!x) 2500 return true; 2501 do 2502 { 2503 y = x; 2504 x = ((x << 1) + n / (x * x)) / 3U; 2505 } 2506 while (x != y && x); 2507 return x * x * x != n; 2508 } 2509 2510 U uparse(U)(string s) 2511 { 2512 Unqual!U result; 2513 assert (s.length, "Empty string"); 2514 size_t i = 0; 2515 if (s.length > 2 && s[0] == '0' && (s[1] == 'x' || s[1] == 'X')) 2516 { 2517 i+=2; 2518 assert (i < s.length, "Empty hexadecimal string"); 2519 while (i < s.length && (s[i] == '0' || s[i] == '_')) 2520 ++i; 2521 int width = 0; 2522 int maxWidth = U.sizeof * 8; 2523 while (i < s.length) 2524 { 2525 assert (width < maxWidth, "Overflow"); 2526 char c = s[i++]; 2527 if (c >= '0' && c <= '9') 2528 { 2529 result <<= 4; 2530 result |= cast(uint)(c - '0'); 2531 width += 4; 2532 } 2533 else if (c >= 'A' && c <= 'F') 2534 { 2535 result <<= 4; 2536 result |= cast(uint)(c - 'A' + 10); 2537 width += 4; 2538 } 2539 else if (c >= 'a' && c <= 'f') 2540 { 2541 result <<= 4; 2542 result |= cast(uint)(c - 'a' + 10); 2543 width += 4; 2544 } 2545 else 2546 assert(c == '_', "Invalid character in input string"); 2547 } 2548 } 2549 else 2550 { 2551 while (i < s.length) 2552 { 2553 char c = s[i++]; 2554 if (c >= '0' && c <= '9') 2555 { 2556 bool ovf; 2557 auto r = fma(result, 10U, cast(uint)(c - '0'), ovf); 2558 assert(!ovf, "Overflow"); 2559 result = r; 2560 } 2561 else 2562 assert(c == '_', "Invalid character in input string"); 2563 } 2564 } 2565 2566 return result; 2567 } 2568 2569 unittest 2570 { 2571 uint512 x = uparse!uint512("1234567890123456789012345678901234567890"); 2572 }