1 /++ 2 Note: 3 The module doesn't provide full arithmetic API for now. 4 +/ 5 module mir.bignum.fixed; 6 7 import std.traits; 8 import mir.bitop; 9 import mir.utility; 10 11 /++ 12 Fixed-length unsigned integer. 13 14 Params: 15 size = size in bits 16 +/ 17 struct UInt(size_t size) 18 if (size % (size_t.sizeof * 8) == 0 && size >= (size_t.sizeof * 8)) 19 { 20 import mir.bignum.fixed: UInt; 21 /++ 22 Payload. The data is located in the target endianness. 23 +/ 24 size_t[size / (size_t.sizeof * 8)] data; 25 26 /// 27 this(size_t N)(auto ref const size_t[N] data) 28 if (N <= this.data.length) 29 { 30 version(LittleEndian) 31 this.data[0 .. N] = data; 32 else 33 this.data[$ - N .. $] = data; 34 } 35 36 /// 37 this(size_t argSize)(auto ref const UInt!argSize arg) 38 if (argSize <= size) 39 { 40 this(arg.data); 41 } 42 43 static if (size_t.sizeof == uint.sizeof && data.length % 2 == 0) 44 /// 45 this()(auto ref const ulong[data.length / 2] data) 46 { 47 if (!__ctfe) 48 { 49 this.data = cast(typeof(this.data)) data; 50 } 51 else 52 { 53 version(LittleEndian) 54 { 55 static foreach (i; 0 .. data.length) 56 { 57 this.data[i * 2 + 0] = cast(uint) data[i]; 58 this.data[i * 2 + 1] = cast(uint) (data[i] >> 32); 59 } 60 } 61 else 62 { 63 static foreach (i; 0 .. data.length) 64 { 65 this.data[i * 2 + 1] = cast(uint) data[i]; 66 this.data[i * 2 + 0] = cast(uint) (data[i] >> 32); 67 } 68 } 69 } 70 } 71 72 /// 73 this(ulong data) 74 { 75 auto d = view.leastSignificantFirst; 76 static if (size_t.sizeof == ulong.sizeof) 77 { 78 d.front = data; 79 } 80 else 81 { 82 d.front = cast(uint) data; 83 d[1] = cast(uint) (data >> 32); 84 } 85 } 86 87 static if (size < 64) 88 /// 89 this(uint data) 90 { 91 view.leastSignificant = data; 92 } 93 94 /// 95 this(C)(scope const(C)[] str) @safe pure @nogc 96 if (isSomeChar!C) 97 { 98 if (fromStringImpl(str)) 99 return; 100 static if (__traits(compiles, () @nogc { throw new Exception("Can't parse UInt."); })) 101 { 102 import mir.exception: MirException; 103 throw new MirException("Can't parse UInt!" ~ size.stringof ~ " from string `", str , "`."); 104 } 105 else 106 { 107 static immutable exception = new Exception("Can't parse UInt!" ~ size.stringof ~ "."); 108 throw exception; 109 } 110 } 111 112 static if (size == 128) 113 /// 114 version(mir_bignum_test) @safe pure @nogc unittest 115 { 116 import mir.math.constant: PI; 117 UInt!256 integer = "34010447314490204552169750449563978034784726557588085989975288830070948234680"; // constructor 118 assert(integer == UInt!256.fromHexString("4b313b23aa560e1b0985f89cbe6df5460860e39a64ba92b4abdd3ee77e4e05b8")); 119 } 120 121 /++ 122 Returns: false in case of overflow or incorrect string. 123 Precondition: non-empty coefficients. 124 +/ 125 bool fromStringImpl(C)(scope const(C)[] str) 126 scope @trusted pure @nogc nothrow 127 if (isSomeChar!C) 128 { 129 import mir.bignum.low_level_view: BigUIntView; 130 return BigUIntView!size_t(data[]).fromStringImpl(str); 131 } 132 133 /// 134 immutable(C)[] toString(C = char)() const @safe pure nothrow 135 if(isSomeChar!C && isMutable!C) 136 { 137 UInt!size copy = this; 138 auto work = copy.view.normalized; 139 import mir.bignum.low_level_view: ceilLog10Exp2; 140 C[ceilLog10Exp2(data.length * (size_t.sizeof * 8))] buffer = void; 141 return buffer[$ - work.toStringImpl(buffer) .. $].idup; 142 } 143 144 static if (size == 128) 145 /// 146 version(mir_bignum_test) @safe pure unittest 147 { 148 auto str = "34010447314490204552169750449563978034784726557588085989975288830070948234680"; 149 auto integer = UInt!256(str); 150 assert(integer.toString == str); 151 152 integer = UInt!256.init; 153 assert(integer.toString == "0"); 154 } 155 156 /// 157 void toString(C = char, W)(scope ref W w) const 158 if(isSomeChar!C && isMutable!C) 159 { 160 UInt!size copy = this; 161 auto work = copy.view.normalized; 162 import mir.bignum.low_level_view: ceilLog10Exp2; 163 C[ceilLog10Exp2(data.length * (size_t.sizeof * 8))] buffer = void; 164 w.put(buffer[$ - work.toStringImpl(buffer) .. $]); 165 } 166 167 static if (size == 128) 168 /// Check @nogc toString impl 169 version(mir_bignum_test) @safe pure @nogc unittest 170 { 171 import mir.format: stringBuf; 172 auto str = "34010447314490204552169750449563978034784726557588085989975288830070948234680"; 173 auto integer = UInt!256(str); 174 stringBuf buffer; 175 buffer << integer; 176 assert(buffer.data == str, buffer.data); 177 } 178 179 /// 180 enum UInt!size max = ((){UInt!size ret; ret.data = size_t.max; return ret;})(); 181 182 /// 183 enum UInt!size min = UInt!size.init; 184 185 import mir.bignum.low_level_view: BigUIntView; 186 187 /// 188 BigUIntView!size_t view()() @property pure nothrow @nogc scope @safe 189 { 190 return BigUIntView!size_t(data); 191 } 192 193 /// 194 BigUIntView!(const size_t) view()() const @property pure nothrow @nogc scope @safe 195 { 196 return BigUIntView!(const size_t)(data); 197 } 198 199 /// 200 static UInt!size fromHexString(bool allowUnderscores = false)(scope const(char)[] str) 201 { 202 typeof(return) ret; 203 if (ret.fromHexStringImpl!(char, allowUnderscores)(str)) 204 return ret; 205 version(D_Exceptions) 206 { 207 import mir.bignum.low_level_view: hexStringException; 208 throw hexStringException; 209 } 210 else 211 { 212 import mir.bignum.low_level_view: hexStringErrorMsg; 213 assert(0, hexStringErrorMsg); 214 } 215 } 216 217 /++ 218 +/ 219 bool fromHexStringImpl(C, bool allowUnderscores = false)(scope const(C)[] str) 220 @safe pure @nogc nothrow 221 if (isSomeChar!C) 222 { 223 return view.fromHexStringImpl!(C, allowUnderscores)(str); 224 } 225 226 /++ 227 +/ 228 auto opEquals(size_t rhsSize)(auto ref const UInt!rhsSize rhs) const 229 { 230 static if (rhsSize == size) 231 return this.data == rhs.data; 232 else 233 static if (rhsSize > size) 234 return this.toSize!rhsSize.data == rhs.data; 235 else 236 return this.data == rhs.toSize!size.data; 237 } 238 239 /// ditto 240 auto opEquals(ulong rhs) const 241 { 242 return opEquals(UInt!size(rhs)); 243 } 244 245 /++ 246 +/ 247 auto opCmp(UInt!size rhs) const 248 { 249 version (LittleEndian) // workaround for CTFE bug 250 { 251 foreach_reverse(i; 0 .. data.length) 252 { 253 if (this.data[i] < rhs.data[i]) 254 return -1; 255 if (this.data[i] > rhs.data[i]) 256 return +1; 257 } 258 return 0; 259 } 260 else 261 { 262 import mir.algorithm.iteration: cmp; 263 return cmp(this.view.mostSignificantFirst, rhs.view.mostSignificantFirst); 264 } 265 } 266 267 /// ditto 268 auto opCmp(ulong rhs) const scope 269 { 270 return opCmp(UInt!size(rhs)); 271 } 272 273 /++ 274 +/ 275 ref UInt!size opAssign(ulong rhs) scope return 276 @safe pure nothrow @nogc 277 { 278 this.data = UInt!size(rhs).data; 279 return this; 280 } 281 282 /++ 283 `bool overflow = a += b ` and `bool overflow = a -= b` operations. 284 +/ 285 bool opOpAssign(string op)(UInt!size rhs, bool overflow = false) 286 @safe pure nothrow @nogc scope 287 if (op == "+" || op == "-") 288 { 289 return view.opOpAssign!op(rhs.view, overflow); 290 } 291 292 /// ditto 293 bool opOpAssign(string op)(size_t rhs) 294 @safe pure nothrow @nogc scope 295 if (op == "+" || op == "-") 296 { 297 return view.opOpAssign!op(rhs); 298 } 299 300 static if (size_t.sizeof < ulong.sizeof) 301 /// ditto 302 bool opOpAssign(string op)(ulong rhs) 303 @safe pure nothrow @nogc scope 304 if (op == "+" || op == "-") 305 { 306 return opOpAssign!op(UInt!size(rhs)); 307 } 308 309 /// ditto 310 bool opOpAssign(string op, size_t rsize)(UInt!rsize rhs, bool overflow = false) 311 @safe pure nothrow @nogc scope 312 if ((op == "+" || op == "-") && rsize < size) 313 { 314 return opOpAssign!op(rhs.toSize!size, overflow); 315 } 316 317 /++ 318 Returns: overflow value of multiplication 319 +/ 320 size_t opOpAssign(string op : "*")(size_t rhs, size_t carry = 0) 321 @safe pure nothrow @nogc scope 322 { 323 return view.opOpAssign!op(rhs, carry); 324 } 325 326 static if (size_t.sizeof == 4) 327 /// ditto 328 auto opOpAssign(string op : "*")(ulong rhs) 329 @safe pure nothrow @nogc scope 330 { 331 return opOpAssign!op(UInt!64(rhs)); 332 } 333 334 335 /++ 336 Returns: overflow value of multiplication 337 +/ 338 void opOpAssign(string op : "*", size_t rhsSize)(UInt!rhsSize rhs) 339 @safe pure nothrow @nogc scope 340 if (rhsSize <= size) 341 { 342 this = extendedMul(this, rhs).toSize!size; 343 } 344 345 /++ 346 Performs `uint remainder = (overflow$big) /= scalar` operatrion, where `$` denotes big-endian concatenation. 347 Precondition: `overflow < rhs` 348 Params: 349 rhs = unsigned value to devide by 350 overflow = initial unsigned overflow 351 Returns: 352 unsigned remainder value (evaluated overflow) 353 +/ 354 uint opOpAssign(string op : "/")(uint rhs, uint overflow = 0) 355 @safe pure nothrow @nogc scope 356 { 357 assert(overflow < rhs); 358 auto work = view.normalized; 359 if (worl.coefficients.length) 360 return work.opOpAssign!op(rhs, overflow); 361 return overflow; 362 } 363 364 /// 365 ref UInt!size opOpAssign(string op)(UInt!size rhs) nothrow return 366 if (op == "^" || op == "|" || op == "&") 367 { 368 static foreach (i; 0 .. data.length) 369 mixin(`data[i] ` ~ op ~ `= rhs.data[i];`); 370 return this; 371 } 372 373 static if (size == 128) 374 /// 375 version(mir_bignum_test) 376 @safe pure @nogc 377 unittest 378 { 379 auto a = UInt!128.fromHexString("dfbbfae3cd0aff2714a1de7022b0029d"); 380 auto b = UInt!128.fromHexString("e3251bacb112c88b71ad3f85a970a314"); 381 assert((a.opBinary!"|"(b)) == UInt!128.fromHexString("ffbffbeffd1affaf75adfff5abf0a39d")); 382 } 383 384 /// 385 ref UInt!size opOpAssign(string op)(size_t rhs) nothrow return scope 386 if (op == "^" || op == "|" || op == "&") 387 { 388 mixin(`view.leastSignificantFirst[0] ` ~ op ~ `= rhs;`); 389 return this; 390 } 391 392 static if (size_t.sizeof < ulong.sizeof) 393 /// ditto 394 ref opOpAssign(string op)(ulong rhs) return 395 @safe pure nothrow @nogc scope 396 if (op == "^" || op == "|" || op == "&") 397 { 398 return opOpAssign!op(UInt!size(rhs)); 399 } 400 401 /// 402 ref UInt!size opOpAssign(string op)(size_t shift) 403 @safe pure nothrow @nogc return 404 if (op == "<<" || op == ">>") 405 { 406 auto d = view.leastSignificantFirst; 407 assert(shift < size); 408 auto index = shift / (size_t.sizeof * 8); 409 auto bs = shift % (size_t.sizeof * 8); 410 auto ss = size_t.sizeof * 8 - bs; 411 static if (op == ">>") 412 { 413 if (bs) 414 { 415 foreach (j; 0 .. data.length - (index + 1)) 416 { 417 d[j] = (d[j + index] >>> bs) | (d[j + (index + 1)] << ss); 418 } 419 } 420 else 421 { 422 foreach (j; 0 .. data.length - (index + 1)) 423 { 424 d[j] = d[j + index]; 425 } 426 } 427 d[$ - (index + 1)] = d.back >>> bs; 428 foreach (j; data.length - index .. data.length) 429 { 430 d[j] = 0; 431 } 432 } 433 else 434 { 435 if (bs) 436 { 437 foreach_reverse (j; index + 1 .. data.length) 438 { 439 d[j] = (d[j - index] << bs) | (d[j - (index + 1)] >> ss); 440 } 441 } 442 else 443 { 444 foreach_reverse (j; index + 1 .. data.length) 445 { 446 d[j] = d[j - index]; 447 } 448 } 449 d[index] = d.front << bs; 450 foreach_reverse (j; 0 .. index) 451 { 452 d[j] = 0; 453 } 454 } 455 return this; 456 } 457 458 /++ 459 `auto c = a << b` operation. 460 +/ 461 UInt!size opBinary(string op)(size_t rhs) 462 const @safe pure nothrow @nogc 463 if (op == "<<" || op == ">>>" || op == ">>") 464 { 465 UInt!size ret = this; 466 ret.opOpAssign!op(rhs); 467 return ret; 468 } 469 470 static if (size == 128) 471 /// 472 version(mir_bignum_test) 473 @safe pure @nogc 474 unittest 475 { 476 auto a = UInt!128.fromHexString("afbbfae3cd0aff2714a1de7022b0029d"); 477 assert(a << 0 == a); 478 assert(a << 4 == UInt!128.fromHexString("fbbfae3cd0aff2714a1de7022b0029d0")); 479 assert(a << 68 == UInt!128.fromHexString("4a1de7022b0029d00000000000000000")); 480 assert(a << 127 == UInt!128.fromHexString("80000000000000000000000000000000")); 481 assert(a >> 0 == a); 482 assert(a >> 4 == UInt!128.fromHexString("afbbfae3cd0aff2714a1de7022b0029")); 483 assert(a >> 68 == UInt!128.fromHexString("afbbfae3cd0aff2")); 484 assert(a >> 127 == UInt!128(1)); 485 } 486 487 /++ 488 Binary operations 489 +/ 490 template opBinary(string op) 491 if (op == "^" || op == "|" || op == "&" || op == "+" || op == "-" || op == "*") // || op == "/" || op == "%" 492 { 493 /// 494 UInt!size opBinary(size_t rsize)(UInt!rsize rhs) 495 const @safe pure nothrow @nogc 496 if (rsize <= size) 497 { 498 UInt!size ret = this; 499 ret.opOpAssign!op(rhs); 500 return ret; 501 } 502 503 /// ditto 504 UInt!size opBinary(ulong rhs) 505 const @safe pure nothrow @nogc 506 { 507 UInt!size ret = this; 508 ret.opOpAssign!op(rhs); 509 return ret; 510 } 511 } 512 513 /// ditto 514 template opBinaryRight(string op) 515 if (op == "^" || op == "|" || op == "&" || op == "+" || op == "*") 516 { 517 /// 518 UInt!size opBinaryRight(size_t lsize)(UInt!lsize lhs) 519 const @safe pure nothrow @nogc 520 if (lsize < size) 521 { 522 UInt!size ret = this; 523 ret.opOpAssign!op(lhs); 524 return ret; 525 } 526 527 /// ditto 528 UInt!size opBinaryRight(ulong lhs) 529 const @safe pure nothrow @nogc 530 { 531 UInt!size ret = this; 532 ret.opOpAssign!op(lhs); 533 return ret; 534 } 535 } 536 537 /++ 538 Shifts left using at most `size_t.sizeof * 8 - 1` bits 539 +/ 540 UInt!size smallLeftShift()(uint shift) const 541 { 542 assert(shift < size_t.sizeof * 8); 543 UInt!size ret = this; 544 if (shift) 545 { 546 auto csh = size_t.sizeof * 8 - shift; 547 version (LittleEndian) 548 { 549 static foreach_reverse (i; 1 .. data.length) 550 { 551 ret.data[i] = (ret.data[i] << shift) | (ret.data[i - 1] >>> csh); 552 } 553 ret.data[0] = ret.data[0] << shift; 554 } 555 else 556 { 557 static foreach (i; 0 .. data.length - 1) 558 { 559 ret.data[i] = (ret.data[i] << shift) | (ret.data[i + 1] >>> csh); 560 } 561 ret.data[$ - 1] = ret.data[$ - 1] << shift; 562 } 563 } 564 return ret; 565 } 566 567 static if (size == 128) 568 /// 569 version(mir_bignum_test) 570 @safe pure @nogc 571 unittest 572 { 573 auto a = UInt!128.fromHexString("afbbfae3cd0aff2714a1de7022b0029d"); 574 assert(a.smallLeftShift(4) == UInt!128.fromHexString("fbbfae3cd0aff2714a1de7022b0029d0")); 575 } 576 577 /++ 578 Shifts right using at most `size_t.sizeof * 8 - 1` bits 579 +/ 580 UInt!size smallRightShift()(uint shift) const 581 { 582 assert(shift < size_t.sizeof * 8); 583 UInt!size ret = this; 584 if (shift) 585 { 586 auto csh = size_t.sizeof * 8 - shift; 587 version (LittleEndian) 588 { 589 static foreach (i; 0 .. data.length - 1) 590 { 591 ret.data[i] = (ret.data[i] >>> shift) | (ret.data[i + 1] << csh); 592 } 593 ret.data[$ - 1] = ret.data[$ - 1] >>> shift; 594 } 595 else 596 { 597 static foreach_reverse (i; 1 .. data.length) 598 { 599 ret.data[i] = (ret.data[i] >>> shift) | (ret.data[i - 1] << csh); 600 } 601 ret.data[0] = ret.data[0] >>> shift; 602 } 603 } 604 return ret; 605 } 606 607 static if (size == 128) 608 /// 609 version(mir_bignum_test) 610 @safe pure @nogc 611 unittest 612 { 613 auto a = UInt!128.fromHexString("afbbfae3cd0aff2714a1de7022b0029d"); 614 assert(a.smallRightShift(4) == UInt!128.fromHexString("afbbfae3cd0aff2714a1de7022b0029")); 615 } 616 617 /++ 618 +/ 619 T opCast(T)() const 620 if (is(Unqual!T == bool)) 621 { 622 static foreach (i; 0 .. data.length) 623 { 624 if (data[i]) 625 return true; 626 } 627 return false; 628 } 629 630 /++ 631 +/ 632 T opCast(T)() const 633 if (is(Unqual!T == ulong)) 634 { 635 auto d = view.leastSignificantFirst; 636 static if (size_t.sizeof == ulong.sizeof) 637 { 638 return d.front; 639 } 640 else 641 { 642 return d.front | (ulong(d[1]) << 32); 643 } 644 } 645 646 /++ 647 +/ 648 T opCast(T)() const 649 if (is(Unqual!T == uint)) 650 { 651 auto d = view.leastSignificantFirst; 652 return cast(uint) d.front; 653 } 654 655 /++ 656 Returns: 657 the number with shrinked or extended size. 658 +/ 659 UInt!newSize toSize(size_t newSize, bool lowerBits = true)() 660 const @safe pure @nogc nothrow 661 { 662 typeof(return) ret; 663 import mir.utility: min; 664 enum N = min(ret.data.length, data.length); 665 static if (lowerBits) 666 { 667 version (LittleEndian) 668 ret.data[0 .. N] = data[0 .. N]; 669 else 670 ret.data[$ - N .. $] = data[$ - N .. $]; 671 } 672 else 673 { 674 version (LittleEndian) 675 ret.data[0 .. N] = data[$ - N .. $]; 676 else 677 ret.data[$ - N .. $] = data[0 .. N]; 678 } 679 return ret; 680 } 681 682 /// 683 UInt!(size + additionalRightBits) rightExtend(size_t additionalRightBits)() 684 const @safe pure @nogc nothrow 685 if (additionalRightBits) 686 { 687 typeof(return) ret; 688 version (BigEndian) 689 ret.data[0 .. data.length] = data; 690 else 691 ret.data[$ - data.length .. $] = data; 692 return ret; 693 } 694 695 /++ 696 +/ 697 bool bt()(size_t position) const 698 @safe pure nothrow @nogc 699 { 700 assert(position < data.sizeof * 8); 701 return view.bt(position); 702 } 703 704 static if (size == 128) 705 /// 706 version(mir_bignum_test) 707 @safe pure @nogc 708 unittest 709 { 710 auto a = UInt!128.fromHexString("afbbfae3cd0aff2714a1de7022b0029d"); 711 assert(a.bt(127) == 1); 712 assert(a.bt(126) == 0); 713 assert(a.bt(125) == 1); 714 assert(a.bt(124) == 0); 715 assert(a.bt(0) == 1); 716 assert(a.bt(1) == 0); 717 assert(a.bt(2) == 1); 718 assert(a.bt(3) == 1); 719 } 720 721 /++ 722 +/ 723 size_t ctlz()() const @property 724 @safe pure nothrow @nogc 725 { 726 return view.ctlz; 727 } 728 729 static if (size == 128) 730 /// 731 version(mir_bignum_test) 732 @safe pure @nogc 733 unittest 734 { 735 auto a = UInt!128.fromHexString("dfbbfae3cd0aff2714a1de7022b0029d"); 736 assert (a.ctlz == 0); 737 a = UInt!128.init; 738 assert (a.ctlz == 128); 739 a = UInt!128.fromHexString("3"); 740 assert (a.ctlz == 126); 741 } 742 743 /++ 744 +/ 745 size_t cttz()() const @property 746 @safe pure nothrow @nogc 747 { 748 return view.cttz; 749 } 750 751 static if (size == 128) 752 /// 753 version(mir_bignum_test) 754 @safe pure @nogc 755 unittest 756 { 757 auto a = UInt!128.fromHexString("d"); 758 assert (a.cttz == 0); 759 a = UInt!128.init; 760 assert (a.cttz == 128); 761 a = UInt!128.fromHexString("300000000000000000"); 762 assert (a.cttz == 68); 763 } 764 765 /++ 766 +/ 767 bool signBit()() const @property 768 { 769 version (LittleEndian) 770 return data[$ - 1] >> (size_t.sizeof * 8 - 1); 771 else 772 return data[0] >> (size_t.sizeof * 8 - 1); 773 } 774 775 /// ditto 776 void signBit()(bool value) @property 777 { 778 enum signMask = ptrdiff_t.max; 779 version (LittleEndian) 780 data[$ - 1] = (data[$ - 1] & ptrdiff_t.max) | (size_t(value) << (size_t.sizeof * 8 - 1)); 781 else 782 data[ 0] = (data[ 0] & ptrdiff_t.max) | (size_t(value) << (size_t.sizeof * 8 - 1)); 783 } 784 785 /// 786 version(mir_bignum_test) 787 unittest 788 { 789 auto a = UInt!128.fromHexString("dfbbfae3cd0aff2714a1de7022b0029d"); 790 assert(a.signBit); 791 a.signBit = false; 792 assert(a == UInt!128.fromHexString("5fbbfae3cd0aff2714a1de7022b0029d")); 793 assert(!a.signBit); 794 a.signBit = true; 795 assert(a == UInt!128.fromHexString("dfbbfae3cd0aff2714a1de7022b0029d")); 796 } 797 } 798 799 /++ 800 +/ 801 UInt!sizeB extendedMulHigh(size_t sizeA, size_t sizeB)(UInt!sizeA a, UInt!sizeB b) 802 { 803 return (extendedMul(a, b) >> sizeA).toSize!sizeB; 804 } 805 806 /++ 807 +/ 808 UInt!(sizeA + sizeB) extendedMul(size_t sizeA, size_t sizeB)(UInt!sizeA a, UInt!sizeB b) @safe 809 { 810 UInt!(sizeA + sizeB) ret; 811 enum al = a.data.length; 812 enum alp1 = a.data.length + 1; 813 version (LittleEndian) 814 { 815 ret.data[0 .. alp1] = extendedMul(a, b.data[0]).data; 816 static foreach ( i; 1 .. b.data.length) 817 ret.data[i .. i + alp1] = extendedMulAdd(a, b.data[i], UInt!sizeA(ret.data[i .. i + al])).data; 818 } 819 else 820 { 821 ret.data[$ - alp1 .. $] = extendedMul(a, b.data[$ - 1]).data; 822 static foreach_reverse ( i; 0 .. b.data.length - 1) 823 ret.data[i .. i + alp1] = extendedMulAdd(a, b.data[i], UInt!sizeA(ret.data[i .. i + al])).data; 824 } 825 return ret; 826 } 827 828 /// ditto 829 UInt!(size + size_t.sizeof * 8) 830 extendedMul(size_t size)(UInt!size a, size_t b) @safe 831 { 832 size_t overflow = a.view *= b; 833 auto ret = a.toSize!(size + size_t.sizeof * 8); 834 ret.view.mostSignificant = overflow; 835 return ret; 836 } 837 838 /// ditto 839 UInt!128 extendedMul()(ulong a, ulong b) 840 { 841 static if (size_t.sizeof == ulong.sizeof) 842 { 843 import mir.utility: extMul; 844 auto e = extMul(a, b); 845 version(LittleEndian) 846 return typeof(return)([e.low, e.high]); 847 else 848 return typeof(return)([e.high, e.low]); 849 } 850 else 851 { 852 return extendedMul(UInt!64(a), UInt!64(b)); 853 } 854 } 855 856 /// ditto 857 UInt!64 extendedMul()(uint a, uint b) 858 { 859 static if (size_t.sizeof == uint.sizeof) 860 { 861 import mir.utility: extMul; 862 auto e = extMul(a, b); 863 version(LittleEndian) 864 return typeof(return)([e.low, e.high]); 865 else 866 return typeof(return)([e.high, e.low]); 867 } 868 else 869 { 870 return typeof(return)([ulong(a) * b]); 871 } 872 } 873 874 /// 875 version(mir_bignum_test) 876 @safe pure @nogc 877 unittest 878 { 879 auto a = UInt!128.max; 880 auto b = UInt!256.max; 881 auto c = UInt!384.max; 882 assert(extendedMul(a, a) == UInt!256.max - UInt!128.max - UInt!128.max); 883 assert(extendedMul(a, b) == UInt!384.max - UInt!128.max - UInt!256.max); 884 assert(extendedMul(b, a) == UInt!384.max - UInt!128.max - UInt!256.max); 885 886 a = UInt!128.fromHexString("dfbbfae3cd0aff2714a1de7022b0029d"); 887 b = UInt!256.fromHexString("3fe48f2dc8aad570d037bc9b323fc0cfa312fcc2f63cb521bd8a4ca6157ef619"); 888 c = UInt!384.fromHexString("37d7034b86e8d58a9fc564463fcedef9e2ad1126dd2c0f803e61c72852a9917ef74fa749e7936a9e4e224aeeaff91f55"); 889 assert(extendedMul(a, b) == c); 890 assert(extendedMul(b, a) == c); 891 892 a = UInt!128.fromHexString("23edf5ff44ee3a4feafc652607aa1eb9"); 893 b = UInt!256.fromHexString("d3d79144b8941fb50c9102e3251bacb112c88b71ad3f85a970a31458ce24297b"); 894 c = UInt!384.fromHexString("1dbb62fe6ca5fed101068eda7222d6a9857633ecdfed37a2d156ff6309065ecc633f31465727677a93a7acbd1dac63e3"); 895 assert(extendedMul(a, b) == c); 896 assert(extendedMul(b, a) == c); 897 } 898 899 /// ulong 900 version(mir_bignum_test) 901 @safe pure @nogc 902 unittest 903 { 904 ulong a = 0xdfbbfae3cd0aff27; 905 ulong b = 0x14a1de7022b0029d; 906 auto c = UInt!128.fromHexString("120827399968ea2a2db185d16e8cc8eb"); 907 assert(extendedMul(a, b) == c); 908 assert(extendedMul(b, a) == c); 909 } 910 911 /// uint 912 version(mir_bignum_test) 913 @safe pure @nogc 914 unittest 915 { 916 uint a = 0xdfbbfae3; 917 uint b = 0xcd0aff27; 918 auto c = UInt!64.fromHexString("b333243de8695595"); 919 assert(extendedMul(a, b) == c); 920 assert(extendedMul(b, a) == c); 921 } 922 923 /++ 924 +/ 925 UInt!(size + size_t.sizeof * 8) 926 extendedMulAdd(size_t size)(UInt!size a, size_t b, UInt!size c) 927 { 928 auto ret = extendedMul(a, b); 929 auto view = ret.view; 930 view.mostSignificant += view.topLeastSignificantPart(a.data.length) += c.view; 931 return ret; 932 }