1const std = @import("../../std.zig"); 2const mem = std.mem; 3const testing = std.testing; 4const Managed = std.math.big.int.Managed; 5const Mutable = std.math.big.int.Mutable; 6const Limb = std.math.big.Limb; 7const SignedLimb = std.math.big.SignedLimb; 8const DoubleLimb = std.math.big.DoubleLimb; 9const SignedDoubleLimb = std.math.big.SignedDoubleLimb; 10const maxInt = std.math.maxInt; 11const minInt = std.math.minInt; 12 13// NOTE: All the following tests assume the max machine-word will be 64-bit. 14// 15// They will still run on larger than this and should pass, but the multi-limb code-paths 16// may be untested in some cases. 17 18test "big.int comptime_int set" { 19 comptime var s = 0xefffffff00000001eeeeeeefaaaaaaab; 20 var a = try Managed.initSet(testing.allocator, s); 21 defer a.deinit(); 22 23 const s_limb_count = 128 / @typeInfo(Limb).Int.bits; 24 25 comptime var i: usize = 0; 26 inline while (i < s_limb_count) : (i += 1) { 27 const result = @as(Limb, s & maxInt(Limb)); 28 s >>= @typeInfo(Limb).Int.bits / 2; 29 s >>= @typeInfo(Limb).Int.bits / 2; 30 try testing.expect(a.limbs[i] == result); 31 } 32} 33 34test "big.int comptime_int set negative" { 35 var a = try Managed.initSet(testing.allocator, -10); 36 defer a.deinit(); 37 38 try testing.expect(a.limbs[0] == 10); 39 try testing.expect(a.isPositive() == false); 40} 41 42test "big.int int set unaligned small" { 43 var a = try Managed.initSet(testing.allocator, @as(u7, 45)); 44 defer a.deinit(); 45 46 try testing.expect(a.limbs[0] == 45); 47 try testing.expect(a.isPositive() == true); 48} 49 50test "big.int comptime_int to" { 51 var a = try Managed.initSet(testing.allocator, 0xefffffff00000001eeeeeeefaaaaaaab); 52 defer a.deinit(); 53 54 try testing.expect((try a.to(u128)) == 0xefffffff00000001eeeeeeefaaaaaaab); 55} 56 57test "big.int sub-limb to" { 58 var a = try Managed.initSet(testing.allocator, 10); 59 defer a.deinit(); 60 61 try testing.expect((try a.to(u8)) == 10); 62} 63 64test "big.int set negative minimum" { 65 var a = try Managed.initSet(testing.allocator, @as(i64, minInt(i64))); 66 defer a.deinit(); 67 68 try testing.expect((try a.to(i64)) == minInt(i64)); 69} 70 71test "big.int to target too small error" { 72 var a = try Managed.initSet(testing.allocator, 0xffffffff); 73 defer a.deinit(); 74 75 try testing.expectError(error.TargetTooSmall, a.to(u8)); 76} 77 78test "big.int normalize" { 79 var a = try Managed.init(testing.allocator); 80 defer a.deinit(); 81 try a.ensureCapacity(8); 82 83 a.limbs[0] = 1; 84 a.limbs[1] = 2; 85 a.limbs[2] = 3; 86 a.limbs[3] = 0; 87 a.normalize(4); 88 try testing.expect(a.len() == 3); 89 90 a.limbs[0] = 1; 91 a.limbs[1] = 2; 92 a.limbs[2] = 3; 93 a.normalize(3); 94 try testing.expect(a.len() == 3); 95 96 a.limbs[0] = 0; 97 a.limbs[1] = 0; 98 a.normalize(2); 99 try testing.expect(a.len() == 1); 100 101 a.limbs[0] = 0; 102 a.normalize(1); 103 try testing.expect(a.len() == 1); 104} 105 106test "big.int normalize multi" { 107 var a = try Managed.init(testing.allocator); 108 defer a.deinit(); 109 try a.ensureCapacity(8); 110 111 a.limbs[0] = 1; 112 a.limbs[1] = 2; 113 a.limbs[2] = 0; 114 a.limbs[3] = 0; 115 a.normalize(4); 116 try testing.expect(a.len() == 2); 117 118 a.limbs[0] = 1; 119 a.limbs[1] = 2; 120 a.limbs[2] = 3; 121 a.normalize(3); 122 try testing.expect(a.len() == 3); 123 124 a.limbs[0] = 0; 125 a.limbs[1] = 0; 126 a.limbs[2] = 0; 127 a.limbs[3] = 0; 128 a.normalize(4); 129 try testing.expect(a.len() == 1); 130 131 a.limbs[0] = 0; 132 a.normalize(1); 133 try testing.expect(a.len() == 1); 134} 135 136test "big.int parity" { 137 var a = try Managed.init(testing.allocator); 138 defer a.deinit(); 139 140 try a.set(0); 141 try testing.expect(a.isEven()); 142 try testing.expect(!a.isOdd()); 143 144 try a.set(7); 145 try testing.expect(!a.isEven()); 146 try testing.expect(a.isOdd()); 147} 148 149test "big.int bitcount + sizeInBaseUpperBound" { 150 var a = try Managed.init(testing.allocator); 151 defer a.deinit(); 152 153 try a.set(0b100); 154 try testing.expect(a.bitCountAbs() == 3); 155 try testing.expect(a.sizeInBaseUpperBound(2) >= 3); 156 try testing.expect(a.sizeInBaseUpperBound(10) >= 1); 157 158 a.negate(); 159 try testing.expect(a.bitCountAbs() == 3); 160 try testing.expect(a.sizeInBaseUpperBound(2) >= 4); 161 try testing.expect(a.sizeInBaseUpperBound(10) >= 2); 162 163 try a.set(0xffffffff); 164 try testing.expect(a.bitCountAbs() == 32); 165 try testing.expect(a.sizeInBaseUpperBound(2) >= 32); 166 try testing.expect(a.sizeInBaseUpperBound(10) >= 10); 167 168 try a.shiftLeft(a, 5000); 169 try testing.expect(a.bitCountAbs() == 5032); 170 try testing.expect(a.sizeInBaseUpperBound(2) >= 5032); 171 a.setSign(false); 172 173 try testing.expect(a.bitCountAbs() == 5032); 174 try testing.expect(a.sizeInBaseUpperBound(2) >= 5033); 175} 176 177test "big.int bitcount/to" { 178 var a = try Managed.init(testing.allocator); 179 defer a.deinit(); 180 181 try a.set(0); 182 try testing.expect(a.bitCountTwosComp() == 0); 183 184 try testing.expect((try a.to(u0)) == 0); 185 try testing.expect((try a.to(i0)) == 0); 186 187 try a.set(-1); 188 try testing.expect(a.bitCountTwosComp() == 1); 189 try testing.expect((try a.to(i1)) == -1); 190 191 try a.set(-8); 192 try testing.expect(a.bitCountTwosComp() == 4); 193 try testing.expect((try a.to(i4)) == -8); 194 195 try a.set(127); 196 try testing.expect(a.bitCountTwosComp() == 7); 197 try testing.expect((try a.to(u7)) == 127); 198 199 try a.set(-128); 200 try testing.expect(a.bitCountTwosComp() == 8); 201 try testing.expect((try a.to(i8)) == -128); 202 203 try a.set(-129); 204 try testing.expect(a.bitCountTwosComp() == 9); 205 try testing.expect((try a.to(i9)) == -129); 206} 207 208test "big.int fits" { 209 var a = try Managed.init(testing.allocator); 210 defer a.deinit(); 211 212 try a.set(0); 213 try testing.expect(a.fits(u0)); 214 try testing.expect(a.fits(i0)); 215 216 try a.set(255); 217 try testing.expect(!a.fits(u0)); 218 try testing.expect(!a.fits(u1)); 219 try testing.expect(!a.fits(i8)); 220 try testing.expect(a.fits(u8)); 221 try testing.expect(a.fits(u9)); 222 try testing.expect(a.fits(i9)); 223 224 try a.set(-128); 225 try testing.expect(!a.fits(i7)); 226 try testing.expect(a.fits(i8)); 227 try testing.expect(a.fits(i9)); 228 try testing.expect(!a.fits(u9)); 229 230 try a.set(0x1ffffffffeeeeeeee); 231 try testing.expect(!a.fits(u32)); 232 try testing.expect(!a.fits(u64)); 233 try testing.expect(a.fits(u65)); 234} 235 236test "big.int string set" { 237 var a = try Managed.init(testing.allocator); 238 defer a.deinit(); 239 240 try a.setString(10, "120317241209124781241290847124"); 241 try testing.expect((try a.to(u128)) == 120317241209124781241290847124); 242} 243 244test "big.int string negative" { 245 var a = try Managed.init(testing.allocator); 246 defer a.deinit(); 247 248 try a.setString(10, "-1023"); 249 try testing.expect((try a.to(i32)) == -1023); 250} 251 252test "big.int string set number with underscores" { 253 var a = try Managed.init(testing.allocator); 254 defer a.deinit(); 255 256 try a.setString(10, "__1_2_0_3_1_7_2_4_1_2_0_____9_1__2__4_7_8_1_2_4_1_2_9_0_8_4_7_1_2_4___"); 257 try testing.expect((try a.to(u128)) == 120317241209124781241290847124); 258} 259 260test "big.int string set case insensitive number" { 261 var a = try Managed.init(testing.allocator); 262 defer a.deinit(); 263 264 try a.setString(16, "aB_cD_eF"); 265 try testing.expect((try a.to(u32)) == 0xabcdef); 266} 267 268test "big.int string set bad char error" { 269 var a = try Managed.init(testing.allocator); 270 defer a.deinit(); 271 try testing.expectError(error.InvalidCharacter, a.setString(10, "x")); 272} 273 274test "big.int string set bad base error" { 275 var a = try Managed.init(testing.allocator); 276 defer a.deinit(); 277 try testing.expectError(error.InvalidBase, a.setString(45, "10")); 278} 279 280test "big.int twos complement limit set" { 281 const test_types = [_]type{ 282 u64, 283 i64, 284 u1, 285 i1, 286 u0, 287 i0, 288 u65, 289 i65, 290 }; 291 292 inline for (test_types) |T| { 293 // To work around 'control flow attempts to use compile-time variable at runtime' 294 const U = T; 295 const int_info = @typeInfo(U).Int; 296 297 var a = try Managed.init(testing.allocator); 298 defer a.deinit(); 299 300 try a.setTwosCompIntLimit(.max, int_info.signedness, int_info.bits); 301 var max: U = maxInt(U); 302 try testing.expect(max == try a.to(U)); 303 304 try a.setTwosCompIntLimit(.min, int_info.signedness, int_info.bits); 305 var min: U = minInt(U); 306 try testing.expect(min == try a.to(U)); 307 } 308} 309 310test "big.int string to" { 311 var a = try Managed.initSet(testing.allocator, 120317241209124781241290847124); 312 defer a.deinit(); 313 314 const as = try a.toString(testing.allocator, 10, .lower); 315 defer testing.allocator.free(as); 316 const es = "120317241209124781241290847124"; 317 318 try testing.expect(mem.eql(u8, as, es)); 319} 320 321test "big.int string to base base error" { 322 var a = try Managed.initSet(testing.allocator, 0xffffffff); 323 defer a.deinit(); 324 325 try testing.expectError(error.InvalidBase, a.toString(testing.allocator, 45, .lower)); 326} 327 328test "big.int string to base 2" { 329 var a = try Managed.initSet(testing.allocator, -0b1011); 330 defer a.deinit(); 331 332 const as = try a.toString(testing.allocator, 2, .lower); 333 defer testing.allocator.free(as); 334 const es = "-1011"; 335 336 try testing.expect(mem.eql(u8, as, es)); 337} 338 339test "big.int string to base 16" { 340 var a = try Managed.initSet(testing.allocator, 0xefffffff00000001eeeeeeefaaaaaaab); 341 defer a.deinit(); 342 343 const as = try a.toString(testing.allocator, 16, .lower); 344 defer testing.allocator.free(as); 345 const es = "efffffff00000001eeeeeeefaaaaaaab"; 346 347 try testing.expect(mem.eql(u8, as, es)); 348} 349 350test "big.int neg string to" { 351 var a = try Managed.initSet(testing.allocator, -123907434); 352 defer a.deinit(); 353 354 const as = try a.toString(testing.allocator, 10, .lower); 355 defer testing.allocator.free(as); 356 const es = "-123907434"; 357 358 try testing.expect(mem.eql(u8, as, es)); 359} 360 361test "big.int zero string to" { 362 var a = try Managed.initSet(testing.allocator, 0); 363 defer a.deinit(); 364 365 const as = try a.toString(testing.allocator, 10, .lower); 366 defer testing.allocator.free(as); 367 const es = "0"; 368 369 try testing.expect(mem.eql(u8, as, es)); 370} 371 372test "big.int clone" { 373 var a = try Managed.initSet(testing.allocator, 1234); 374 defer a.deinit(); 375 var b = try a.clone(); 376 defer b.deinit(); 377 378 try testing.expect((try a.to(u32)) == 1234); 379 try testing.expect((try b.to(u32)) == 1234); 380 381 try a.set(77); 382 try testing.expect((try a.to(u32)) == 77); 383 try testing.expect((try b.to(u32)) == 1234); 384} 385 386test "big.int swap" { 387 var a = try Managed.initSet(testing.allocator, 1234); 388 defer a.deinit(); 389 var b = try Managed.initSet(testing.allocator, 5678); 390 defer b.deinit(); 391 392 try testing.expect((try a.to(u32)) == 1234); 393 try testing.expect((try b.to(u32)) == 5678); 394 395 a.swap(&b); 396 397 try testing.expect((try a.to(u32)) == 5678); 398 try testing.expect((try b.to(u32)) == 1234); 399} 400 401test "big.int to negative" { 402 var a = try Managed.initSet(testing.allocator, -10); 403 defer a.deinit(); 404 405 try testing.expect((try a.to(i32)) == -10); 406} 407 408test "big.int compare" { 409 var a = try Managed.initSet(testing.allocator, -11); 410 defer a.deinit(); 411 var b = try Managed.initSet(testing.allocator, 10); 412 defer b.deinit(); 413 414 try testing.expect(a.orderAbs(b) == .gt); 415 try testing.expect(a.order(b) == .lt); 416} 417 418test "big.int compare similar" { 419 var a = try Managed.initSet(testing.allocator, 0xffffffffeeeeeeeeffffffffeeeeeeee); 420 defer a.deinit(); 421 var b = try Managed.initSet(testing.allocator, 0xffffffffeeeeeeeeffffffffeeeeeeef); 422 defer b.deinit(); 423 424 try testing.expect(a.orderAbs(b) == .lt); 425 try testing.expect(b.orderAbs(a) == .gt); 426} 427 428test "big.int compare different limb size" { 429 var a = try Managed.initSet(testing.allocator, maxInt(Limb) + 1); 430 defer a.deinit(); 431 var b = try Managed.initSet(testing.allocator, 1); 432 defer b.deinit(); 433 434 try testing.expect(a.orderAbs(b) == .gt); 435 try testing.expect(b.orderAbs(a) == .lt); 436} 437 438test "big.int compare multi-limb" { 439 var a = try Managed.initSet(testing.allocator, -0x7777777799999999ffffeeeeffffeeeeffffeeeef); 440 defer a.deinit(); 441 var b = try Managed.initSet(testing.allocator, 0x7777777799999999ffffeeeeffffeeeeffffeeeee); 442 defer b.deinit(); 443 444 try testing.expect(a.orderAbs(b) == .gt); 445 try testing.expect(a.order(b) == .lt); 446} 447 448test "big.int equality" { 449 var a = try Managed.initSet(testing.allocator, 0xffffffff1); 450 defer a.deinit(); 451 var b = try Managed.initSet(testing.allocator, -0xffffffff1); 452 defer b.deinit(); 453 454 try testing.expect(a.eqAbs(b)); 455 try testing.expect(!a.eq(b)); 456} 457 458test "big.int abs" { 459 var a = try Managed.initSet(testing.allocator, -5); 460 defer a.deinit(); 461 462 a.abs(); 463 try testing.expect((try a.to(u32)) == 5); 464 465 a.abs(); 466 try testing.expect((try a.to(u32)) == 5); 467} 468 469test "big.int negate" { 470 var a = try Managed.initSet(testing.allocator, 5); 471 defer a.deinit(); 472 473 a.negate(); 474 try testing.expect((try a.to(i32)) == -5); 475 476 a.negate(); 477 try testing.expect((try a.to(i32)) == 5); 478} 479 480test "big.int add single-single" { 481 var a = try Managed.initSet(testing.allocator, 50); 482 defer a.deinit(); 483 var b = try Managed.initSet(testing.allocator, 5); 484 defer b.deinit(); 485 486 var c = try Managed.init(testing.allocator); 487 defer c.deinit(); 488 try c.add(a.toConst(), b.toConst()); 489 490 try testing.expect((try c.to(u32)) == 55); 491} 492 493test "big.int add multi-single" { 494 var a = try Managed.initSet(testing.allocator, maxInt(Limb) + 1); 495 defer a.deinit(); 496 var b = try Managed.initSet(testing.allocator, 1); 497 defer b.deinit(); 498 499 var c = try Managed.init(testing.allocator); 500 defer c.deinit(); 501 502 try c.add(a.toConst(), b.toConst()); 503 try testing.expect((try c.to(DoubleLimb)) == maxInt(Limb) + 2); 504 505 try c.add(b.toConst(), a.toConst()); 506 try testing.expect((try c.to(DoubleLimb)) == maxInt(Limb) + 2); 507} 508 509test "big.int add multi-multi" { 510 const op1 = 0xefefefef7f7f7f7f; 511 const op2 = 0xfefefefe9f9f9f9f; 512 var a = try Managed.initSet(testing.allocator, op1); 513 defer a.deinit(); 514 var b = try Managed.initSet(testing.allocator, op2); 515 defer b.deinit(); 516 517 var c = try Managed.init(testing.allocator); 518 defer c.deinit(); 519 try c.add(a.toConst(), b.toConst()); 520 521 try testing.expect((try c.to(u128)) == op1 + op2); 522} 523 524test "big.int add zero-zero" { 525 var a = try Managed.initSet(testing.allocator, 0); 526 defer a.deinit(); 527 var b = try Managed.initSet(testing.allocator, 0); 528 defer b.deinit(); 529 530 var c = try Managed.init(testing.allocator); 531 defer c.deinit(); 532 try c.add(a.toConst(), b.toConst()); 533 534 try testing.expect((try c.to(u32)) == 0); 535} 536 537test "big.int add alias multi-limb nonzero-zero" { 538 const op1 = 0xffffffff777777771; 539 var a = try Managed.initSet(testing.allocator, op1); 540 defer a.deinit(); 541 var b = try Managed.initSet(testing.allocator, 0); 542 defer b.deinit(); 543 544 try a.add(a.toConst(), b.toConst()); 545 546 try testing.expect((try a.to(u128)) == op1); 547} 548 549test "big.int add sign" { 550 var a = try Managed.init(testing.allocator); 551 defer a.deinit(); 552 553 var one = try Managed.initSet(testing.allocator, 1); 554 defer one.deinit(); 555 var two = try Managed.initSet(testing.allocator, 2); 556 defer two.deinit(); 557 var neg_one = try Managed.initSet(testing.allocator, -1); 558 defer neg_one.deinit(); 559 var neg_two = try Managed.initSet(testing.allocator, -2); 560 defer neg_two.deinit(); 561 562 try a.add(one.toConst(), two.toConst()); 563 try testing.expect((try a.to(i32)) == 3); 564 565 try a.add(neg_one.toConst(), two.toConst()); 566 try testing.expect((try a.to(i32)) == 1); 567 568 try a.add(one.toConst(), neg_two.toConst()); 569 try testing.expect((try a.to(i32)) == -1); 570 571 try a.add(neg_one.toConst(), neg_two.toConst()); 572 try testing.expect((try a.to(i32)) == -3); 573} 574 575test "big.int add scalar" { 576 var a = try Managed.initSet(testing.allocator, 50); 577 defer a.deinit(); 578 579 var b = try Managed.init(testing.allocator); 580 defer b.deinit(); 581 try b.addScalar(a.toConst(), 5); 582 583 try testing.expect((try b.to(u32)) == 55); 584} 585 586test "big.int addWrap single-single, unsigned" { 587 var a = try Managed.initSet(testing.allocator, maxInt(u17)); 588 defer a.deinit(); 589 590 var b = try Managed.initSet(testing.allocator, 10); 591 defer b.deinit(); 592 593 try a.addWrap(a.toConst(), b.toConst(), .unsigned, 17); 594 595 try testing.expect((try a.to(u17)) == 9); 596} 597 598test "big.int subWrap single-single, unsigned" { 599 var a = try Managed.initSet(testing.allocator, 0); 600 defer a.deinit(); 601 602 var b = try Managed.initSet(testing.allocator, maxInt(u17)); 603 defer b.deinit(); 604 605 try a.subWrap(a.toConst(), b.toConst(), .unsigned, 17); 606 607 try testing.expect((try a.to(u17)) == 1); 608} 609 610test "big.int addWrap multi-multi, unsigned, limb aligned" { 611 var a = try Managed.initSet(testing.allocator, maxInt(DoubleLimb)); 612 defer a.deinit(); 613 614 var b = try Managed.initSet(testing.allocator, maxInt(DoubleLimb)); 615 defer b.deinit(); 616 617 try a.addWrap(a.toConst(), b.toConst(), .unsigned, @bitSizeOf(DoubleLimb)); 618 619 try testing.expect((try a.to(DoubleLimb)) == maxInt(DoubleLimb) - 1); 620} 621 622test "big.int subWrap single-multi, unsigned, limb aligned" { 623 var a = try Managed.initSet(testing.allocator, 10); 624 defer a.deinit(); 625 626 var b = try Managed.initSet(testing.allocator, maxInt(DoubleLimb) + 100); 627 defer b.deinit(); 628 629 try a.subWrap(a.toConst(), b.toConst(), .unsigned, @bitSizeOf(DoubleLimb)); 630 631 try testing.expect((try a.to(DoubleLimb)) == maxInt(DoubleLimb) - 88); 632} 633 634test "big.int addWrap single-single, signed" { 635 var a = try Managed.initSet(testing.allocator, maxInt(i21)); 636 defer a.deinit(); 637 638 var b = try Managed.initSet(testing.allocator, 1 + 1 + maxInt(u21)); 639 defer b.deinit(); 640 641 try a.addWrap(a.toConst(), b.toConst(), .signed, @bitSizeOf(i21)); 642 643 try testing.expect((try a.to(i21)) == minInt(i21)); 644} 645 646test "big.int subWrap single-single, signed" { 647 var a = try Managed.initSet(testing.allocator, minInt(i21)); 648 defer a.deinit(); 649 650 var b = try Managed.initSet(testing.allocator, 1); 651 defer b.deinit(); 652 653 try a.subWrap(a.toConst(), b.toConst(), .signed, @bitSizeOf(i21)); 654 655 try testing.expect((try a.to(i21)) == maxInt(i21)); 656} 657 658test "big.int addWrap multi-multi, signed, limb aligned" { 659 var a = try Managed.initSet(testing.allocator, maxInt(SignedDoubleLimb)); 660 defer a.deinit(); 661 662 var b = try Managed.initSet(testing.allocator, maxInt(SignedDoubleLimb)); 663 defer b.deinit(); 664 665 try a.addWrap(a.toConst(), b.toConst(), .signed, @bitSizeOf(SignedDoubleLimb)); 666 667 try testing.expect((try a.to(SignedDoubleLimb)) == -2); 668} 669 670test "big.int subWrap single-multi, signed, limb aligned" { 671 var a = try Managed.initSet(testing.allocator, minInt(SignedDoubleLimb)); 672 defer a.deinit(); 673 674 var b = try Managed.initSet(testing.allocator, 1); 675 defer b.deinit(); 676 677 try a.subWrap(a.toConst(), b.toConst(), .signed, @bitSizeOf(SignedDoubleLimb)); 678 679 try testing.expect((try a.to(SignedDoubleLimb)) == maxInt(SignedDoubleLimb)); 680} 681 682test "big.int addSat single-single, unsigned" { 683 var a = try Managed.initSet(testing.allocator, maxInt(u17) - 5); 684 defer a.deinit(); 685 686 var b = try Managed.initSet(testing.allocator, 10); 687 defer b.deinit(); 688 689 try a.addSat(a.toConst(), b.toConst(), .unsigned, 17); 690 691 try testing.expect((try a.to(u17)) == maxInt(u17)); 692} 693 694test "big.int subSat single-single, unsigned" { 695 var a = try Managed.initSet(testing.allocator, 123); 696 defer a.deinit(); 697 698 var b = try Managed.initSet(testing.allocator, 4000); 699 defer b.deinit(); 700 701 try a.subSat(a.toConst(), b.toConst(), .unsigned, 17); 702 703 try testing.expect((try a.to(u17)) == 0); 704} 705 706test "big.int addSat multi-multi, unsigned, limb aligned" { 707 var a = try Managed.initSet(testing.allocator, maxInt(DoubleLimb)); 708 defer a.deinit(); 709 710 var b = try Managed.initSet(testing.allocator, maxInt(DoubleLimb)); 711 defer b.deinit(); 712 713 try a.addSat(a.toConst(), b.toConst(), .unsigned, @bitSizeOf(DoubleLimb)); 714 715 try testing.expect((try a.to(DoubleLimb)) == maxInt(DoubleLimb)); 716} 717 718test "big.int subSat single-multi, unsigned, limb aligned" { 719 var a = try Managed.initSet(testing.allocator, 10); 720 defer a.deinit(); 721 722 var b = try Managed.initSet(testing.allocator, maxInt(DoubleLimb) + 100); 723 defer b.deinit(); 724 725 try a.subSat(a.toConst(), b.toConst(), .unsigned, @bitSizeOf(DoubleLimb)); 726 727 try testing.expect((try a.to(DoubleLimb)) == 0); 728} 729 730test "big.int addSat single-single, signed" { 731 var a = try Managed.initSet(testing.allocator, maxInt(i14)); 732 defer a.deinit(); 733 734 var b = try Managed.initSet(testing.allocator, 1); 735 defer b.deinit(); 736 737 try a.addSat(a.toConst(), b.toConst(), .signed, @bitSizeOf(i14)); 738 739 try testing.expect((try a.to(i14)) == maxInt(i14)); 740} 741 742test "big.int subSat single-single, signed" { 743 var a = try Managed.initSet(testing.allocator, minInt(i21)); 744 defer a.deinit(); 745 746 var b = try Managed.initSet(testing.allocator, 1); 747 defer b.deinit(); 748 749 try a.subSat(a.toConst(), b.toConst(), .signed, @bitSizeOf(i21)); 750 751 try testing.expect((try a.to(i21)) == minInt(i21)); 752} 753 754test "big.int addSat multi-multi, signed, limb aligned" { 755 var a = try Managed.initSet(testing.allocator, maxInt(SignedDoubleLimb)); 756 defer a.deinit(); 757 758 var b = try Managed.initSet(testing.allocator, maxInt(SignedDoubleLimb)); 759 defer b.deinit(); 760 761 try a.addSat(a.toConst(), b.toConst(), .signed, @bitSizeOf(SignedDoubleLimb)); 762 763 try testing.expect((try a.to(SignedDoubleLimb)) == maxInt(SignedDoubleLimb)); 764} 765 766test "big.int subSat single-multi, signed, limb aligned" { 767 var a = try Managed.initSet(testing.allocator, minInt(SignedDoubleLimb)); 768 defer a.deinit(); 769 770 var b = try Managed.initSet(testing.allocator, 1); 771 defer b.deinit(); 772 773 try a.subSat(a.toConst(), b.toConst(), .signed, @bitSizeOf(SignedDoubleLimb)); 774 775 try testing.expect((try a.to(SignedDoubleLimb)) == minInt(SignedDoubleLimb)); 776} 777 778test "big.int sub single-single" { 779 var a = try Managed.initSet(testing.allocator, 50); 780 defer a.deinit(); 781 var b = try Managed.initSet(testing.allocator, 5); 782 defer b.deinit(); 783 784 var c = try Managed.init(testing.allocator); 785 defer c.deinit(); 786 try c.sub(a.toConst(), b.toConst()); 787 788 try testing.expect((try c.to(u32)) == 45); 789} 790 791test "big.int sub multi-single" { 792 var a = try Managed.initSet(testing.allocator, maxInt(Limb) + 1); 793 defer a.deinit(); 794 var b = try Managed.initSet(testing.allocator, 1); 795 defer b.deinit(); 796 797 var c = try Managed.init(testing.allocator); 798 defer c.deinit(); 799 try c.sub(a.toConst(), b.toConst()); 800 801 try testing.expect((try c.to(Limb)) == maxInt(Limb)); 802} 803 804test "big.int sub multi-multi" { 805 const op1 = 0xefefefefefefefefefefefef; 806 const op2 = 0xabababababababababababab; 807 808 var a = try Managed.initSet(testing.allocator, op1); 809 defer a.deinit(); 810 var b = try Managed.initSet(testing.allocator, op2); 811 defer b.deinit(); 812 813 var c = try Managed.init(testing.allocator); 814 defer c.deinit(); 815 try c.sub(a.toConst(), b.toConst()); 816 817 try testing.expect((try c.to(u128)) == op1 - op2); 818} 819 820test "big.int sub equal" { 821 var a = try Managed.initSet(testing.allocator, 0x11efefefefefefefefefefefef); 822 defer a.deinit(); 823 var b = try Managed.initSet(testing.allocator, 0x11efefefefefefefefefefefef); 824 defer b.deinit(); 825 826 var c = try Managed.init(testing.allocator); 827 defer c.deinit(); 828 try c.sub(a.toConst(), b.toConst()); 829 830 try testing.expect((try c.to(u32)) == 0); 831} 832 833test "big.int sub sign" { 834 var a = try Managed.init(testing.allocator); 835 defer a.deinit(); 836 837 var one = try Managed.initSet(testing.allocator, 1); 838 defer one.deinit(); 839 var two = try Managed.initSet(testing.allocator, 2); 840 defer two.deinit(); 841 var neg_one = try Managed.initSet(testing.allocator, -1); 842 defer neg_one.deinit(); 843 var neg_two = try Managed.initSet(testing.allocator, -2); 844 defer neg_two.deinit(); 845 846 try a.sub(one.toConst(), two.toConst()); 847 try testing.expect((try a.to(i32)) == -1); 848 849 try a.sub(neg_one.toConst(), two.toConst()); 850 try testing.expect((try a.to(i32)) == -3); 851 852 try a.sub(one.toConst(), neg_two.toConst()); 853 try testing.expect((try a.to(i32)) == 3); 854 855 try a.sub(neg_one.toConst(), neg_two.toConst()); 856 try testing.expect((try a.to(i32)) == 1); 857 858 try a.sub(neg_two.toConst(), neg_one.toConst()); 859 try testing.expect((try a.to(i32)) == -1); 860} 861 862test "big.int mul single-single" { 863 var a = try Managed.initSet(testing.allocator, 50); 864 defer a.deinit(); 865 var b = try Managed.initSet(testing.allocator, 5); 866 defer b.deinit(); 867 868 var c = try Managed.init(testing.allocator); 869 defer c.deinit(); 870 try c.mul(a.toConst(), b.toConst()); 871 872 try testing.expect((try c.to(u64)) == 250); 873} 874 875test "big.int mul multi-single" { 876 var a = try Managed.initSet(testing.allocator, maxInt(Limb)); 877 defer a.deinit(); 878 var b = try Managed.initSet(testing.allocator, 2); 879 defer b.deinit(); 880 881 var c = try Managed.init(testing.allocator); 882 defer c.deinit(); 883 try c.mul(a.toConst(), b.toConst()); 884 885 try testing.expect((try c.to(DoubleLimb)) == 2 * maxInt(Limb)); 886} 887 888test "big.int mul multi-multi" { 889 const op1 = 0x998888efefefefefefefef; 890 const op2 = 0x333000abababababababab; 891 var a = try Managed.initSet(testing.allocator, op1); 892 defer a.deinit(); 893 var b = try Managed.initSet(testing.allocator, op2); 894 defer b.deinit(); 895 896 var c = try Managed.init(testing.allocator); 897 defer c.deinit(); 898 try c.mul(a.toConst(), b.toConst()); 899 900 try testing.expect((try c.to(u256)) == op1 * op2); 901} 902 903test "big.int mul alias r with a" { 904 var a = try Managed.initSet(testing.allocator, maxInt(Limb)); 905 defer a.deinit(); 906 var b = try Managed.initSet(testing.allocator, 2); 907 defer b.deinit(); 908 909 try a.mul(a.toConst(), b.toConst()); 910 911 try testing.expect((try a.to(DoubleLimb)) == 2 * maxInt(Limb)); 912} 913 914test "big.int mul alias r with b" { 915 var a = try Managed.initSet(testing.allocator, maxInt(Limb)); 916 defer a.deinit(); 917 var b = try Managed.initSet(testing.allocator, 2); 918 defer b.deinit(); 919 920 try a.mul(b.toConst(), a.toConst()); 921 922 try testing.expect((try a.to(DoubleLimb)) == 2 * maxInt(Limb)); 923} 924 925test "big.int mul alias r with a and b" { 926 var a = try Managed.initSet(testing.allocator, maxInt(Limb)); 927 defer a.deinit(); 928 929 try a.mul(a.toConst(), a.toConst()); 930 931 try testing.expect((try a.to(DoubleLimb)) == maxInt(Limb) * maxInt(Limb)); 932} 933 934test "big.int mul a*0" { 935 var a = try Managed.initSet(testing.allocator, 0xefefefefefefefef); 936 defer a.deinit(); 937 var b = try Managed.initSet(testing.allocator, 0); 938 defer b.deinit(); 939 940 var c = try Managed.init(testing.allocator); 941 defer c.deinit(); 942 try c.mul(a.toConst(), b.toConst()); 943 944 try testing.expect((try c.to(u32)) == 0); 945} 946 947test "big.int mul 0*0" { 948 var a = try Managed.initSet(testing.allocator, 0); 949 defer a.deinit(); 950 var b = try Managed.initSet(testing.allocator, 0); 951 defer b.deinit(); 952 953 var c = try Managed.init(testing.allocator); 954 defer c.deinit(); 955 try c.mul(a.toConst(), b.toConst()); 956 957 try testing.expect((try c.to(u32)) == 0); 958} 959 960test "big.int mul large" { 961 var a = try Managed.initCapacity(testing.allocator, 50); 962 defer a.deinit(); 963 var b = try Managed.initCapacity(testing.allocator, 100); 964 defer b.deinit(); 965 var c = try Managed.initCapacity(testing.allocator, 100); 966 defer c.deinit(); 967 968 // Generate a number that's large enough to cross the thresholds for the use 969 // of subquadratic algorithms 970 for (a.limbs) |*p| { 971 p.* = std.math.maxInt(Limb); 972 } 973 a.setMetadata(true, 50); 974 975 try b.mul(a.toConst(), a.toConst()); 976 try c.sqr(a.toConst()); 977 978 try testing.expect(b.eq(c)); 979} 980 981test "big.int mulWrap single-single unsigned" { 982 var a = try Managed.initSet(testing.allocator, 1234); 983 defer a.deinit(); 984 var b = try Managed.initSet(testing.allocator, 5678); 985 defer b.deinit(); 986 987 var c = try Managed.init(testing.allocator); 988 defer c.deinit(); 989 try c.mulWrap(a.toConst(), b.toConst(), .unsigned, 17); 990 991 try testing.expect((try c.to(u17)) == 59836); 992} 993 994test "big.int mulWrap single-single signed" { 995 var a = try Managed.initSet(testing.allocator, 1234); 996 defer a.deinit(); 997 var b = try Managed.initSet(testing.allocator, -5678); 998 defer b.deinit(); 999 1000 var c = try Managed.init(testing.allocator); 1001 defer c.deinit(); 1002 try c.mulWrap(a.toConst(), b.toConst(), .signed, 17); 1003 1004 try testing.expect((try c.to(i17)) == -59836); 1005} 1006 1007test "big.int mulWrap multi-multi unsigned" { 1008 const op1 = 0x998888efefefefefefefef; 1009 const op2 = 0x333000abababababababab; 1010 var a = try Managed.initSet(testing.allocator, op1); 1011 defer a.deinit(); 1012 var b = try Managed.initSet(testing.allocator, op2); 1013 defer b.deinit(); 1014 1015 var c = try Managed.init(testing.allocator); 1016 defer c.deinit(); 1017 try c.mulWrap(a.toConst(), b.toConst(), .unsigned, 65); 1018 1019 try testing.expect((try c.to(u128)) == (op1 * op2) & ((1 << 65) - 1)); 1020} 1021 1022test "big.int mulWrap multi-multi signed" { 1023 var a = try Managed.initSet(testing.allocator, maxInt(SignedDoubleLimb) - 1); 1024 defer a.deinit(); 1025 var b = try Managed.initSet(testing.allocator, maxInt(SignedDoubleLimb)); 1026 defer b.deinit(); 1027 1028 var c = try Managed.init(testing.allocator); 1029 defer c.deinit(); 1030 try c.mulWrap(a.toConst(), b.toConst(), .signed, @bitSizeOf(SignedDoubleLimb)); 1031 1032 try testing.expect((try c.to(SignedDoubleLimb)) == minInt(SignedDoubleLimb) + 2); 1033} 1034 1035test "big.int mulWrap large" { 1036 var a = try Managed.initCapacity(testing.allocator, 50); 1037 defer a.deinit(); 1038 var b = try Managed.initCapacity(testing.allocator, 100); 1039 defer b.deinit(); 1040 var c = try Managed.initCapacity(testing.allocator, 100); 1041 defer c.deinit(); 1042 1043 // Generate a number that's large enough to cross the thresholds for the use 1044 // of subquadratic algorithms 1045 for (a.limbs) |*p| { 1046 p.* = std.math.maxInt(Limb); 1047 } 1048 a.setMetadata(true, 50); 1049 1050 const testbits = @bitSizeOf(Limb) * 64 + 45; 1051 1052 try b.mulWrap(a.toConst(), a.toConst(), .signed, testbits); 1053 try c.sqr(a.toConst()); 1054 try c.truncate(c.toConst(), .signed, testbits); 1055 1056 try testing.expect(b.eq(c)); 1057} 1058 1059test "big.int div single-single no rem" { 1060 var a = try Managed.initSet(testing.allocator, 50); 1061 defer a.deinit(); 1062 var b = try Managed.initSet(testing.allocator, 5); 1063 defer b.deinit(); 1064 1065 var q = try Managed.init(testing.allocator); 1066 defer q.deinit(); 1067 var r = try Managed.init(testing.allocator); 1068 defer r.deinit(); 1069 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1070 1071 try testing.expect((try q.to(u32)) == 10); 1072 try testing.expect((try r.to(u32)) == 0); 1073} 1074 1075test "big.int div single-single with rem" { 1076 var a = try Managed.initSet(testing.allocator, 49); 1077 defer a.deinit(); 1078 var b = try Managed.initSet(testing.allocator, 5); 1079 defer b.deinit(); 1080 1081 var q = try Managed.init(testing.allocator); 1082 defer q.deinit(); 1083 var r = try Managed.init(testing.allocator); 1084 defer r.deinit(); 1085 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1086 1087 try testing.expect((try q.to(u32)) == 9); 1088 try testing.expect((try r.to(u32)) == 4); 1089} 1090 1091test "big.int div multi-single no rem" { 1092 const op1 = 0xffffeeeeddddcccc; 1093 const op2 = 34; 1094 1095 var a = try Managed.initSet(testing.allocator, op1); 1096 defer a.deinit(); 1097 var b = try Managed.initSet(testing.allocator, op2); 1098 defer b.deinit(); 1099 1100 var q = try Managed.init(testing.allocator); 1101 defer q.deinit(); 1102 var r = try Managed.init(testing.allocator); 1103 defer r.deinit(); 1104 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1105 1106 try testing.expect((try q.to(u64)) == op1 / op2); 1107 try testing.expect((try r.to(u64)) == 0); 1108} 1109 1110test "big.int div multi-single with rem" { 1111 const op1 = 0xffffeeeeddddcccf; 1112 const op2 = 34; 1113 1114 var a = try Managed.initSet(testing.allocator, op1); 1115 defer a.deinit(); 1116 var b = try Managed.initSet(testing.allocator, op2); 1117 defer b.deinit(); 1118 1119 var q = try Managed.init(testing.allocator); 1120 defer q.deinit(); 1121 var r = try Managed.init(testing.allocator); 1122 defer r.deinit(); 1123 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1124 1125 try testing.expect((try q.to(u64)) == op1 / op2); 1126 try testing.expect((try r.to(u64)) == 3); 1127} 1128 1129test "big.int div multi>2-single" { 1130 const op1 = 0xfefefefefefefefefefefefefefefefe; 1131 const op2 = 0xefab8; 1132 1133 var a = try Managed.initSet(testing.allocator, op1); 1134 defer a.deinit(); 1135 var b = try Managed.initSet(testing.allocator, op2); 1136 defer b.deinit(); 1137 1138 var q = try Managed.init(testing.allocator); 1139 defer q.deinit(); 1140 var r = try Managed.init(testing.allocator); 1141 defer r.deinit(); 1142 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1143 1144 try testing.expect((try q.to(u128)) == op1 / op2); 1145 try testing.expect((try r.to(u32)) == 0x3e4e); 1146} 1147 1148test "big.int div single-single q < r" { 1149 var a = try Managed.initSet(testing.allocator, 0x0078f432); 1150 defer a.deinit(); 1151 var b = try Managed.initSet(testing.allocator, 0x01000000); 1152 defer b.deinit(); 1153 1154 var q = try Managed.init(testing.allocator); 1155 defer q.deinit(); 1156 var r = try Managed.init(testing.allocator); 1157 defer r.deinit(); 1158 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1159 1160 try testing.expect((try q.to(u64)) == 0); 1161 try testing.expect((try r.to(u64)) == 0x0078f432); 1162} 1163 1164test "big.int div single-single q == r" { 1165 var a = try Managed.initSet(testing.allocator, 10); 1166 defer a.deinit(); 1167 var b = try Managed.initSet(testing.allocator, 10); 1168 defer b.deinit(); 1169 1170 var q = try Managed.init(testing.allocator); 1171 defer q.deinit(); 1172 var r = try Managed.init(testing.allocator); 1173 defer r.deinit(); 1174 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1175 1176 try testing.expect((try q.to(u64)) == 1); 1177 try testing.expect((try r.to(u64)) == 0); 1178} 1179 1180test "big.int div q=0 alias" { 1181 var a = try Managed.initSet(testing.allocator, 3); 1182 defer a.deinit(); 1183 var b = try Managed.initSet(testing.allocator, 10); 1184 defer b.deinit(); 1185 1186 try Managed.divTrunc(&a, &b, a.toConst(), b.toConst()); 1187 1188 try testing.expect((try a.to(u64)) == 0); 1189 try testing.expect((try b.to(u64)) == 3); 1190} 1191 1192test "big.int div multi-multi q < r" { 1193 const op1 = 0x1ffffffff0078f432; 1194 const op2 = 0x1ffffffff01000000; 1195 var a = try Managed.initSet(testing.allocator, op1); 1196 defer a.deinit(); 1197 var b = try Managed.initSet(testing.allocator, op2); 1198 defer b.deinit(); 1199 1200 var q = try Managed.init(testing.allocator); 1201 defer q.deinit(); 1202 var r = try Managed.init(testing.allocator); 1203 defer r.deinit(); 1204 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1205 1206 try testing.expect((try q.to(u128)) == 0); 1207 try testing.expect((try r.to(u128)) == op1); 1208} 1209 1210test "big.int div trunc single-single +/+" { 1211 const u: i32 = 5; 1212 const v: i32 = 3; 1213 1214 var a = try Managed.initSet(testing.allocator, u); 1215 defer a.deinit(); 1216 var b = try Managed.initSet(testing.allocator, v); 1217 defer b.deinit(); 1218 1219 var q = try Managed.init(testing.allocator); 1220 defer q.deinit(); 1221 var r = try Managed.init(testing.allocator); 1222 defer r.deinit(); 1223 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1224 1225 // n = q * d + r 1226 // 5 = 1 * 3 + 2 1227 const eq = @divTrunc(u, v); 1228 const er = @mod(u, v); 1229 1230 try testing.expect((try q.to(i32)) == eq); 1231 try testing.expect((try r.to(i32)) == er); 1232} 1233 1234test "big.int div trunc single-single -/+" { 1235 const u: i32 = -5; 1236 const v: i32 = 3; 1237 1238 var a = try Managed.initSet(testing.allocator, u); 1239 defer a.deinit(); 1240 var b = try Managed.initSet(testing.allocator, v); 1241 defer b.deinit(); 1242 1243 var q = try Managed.init(testing.allocator); 1244 defer q.deinit(); 1245 var r = try Managed.init(testing.allocator); 1246 defer r.deinit(); 1247 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1248 1249 // n = q * d + r 1250 // -5 = 1 * -3 - 2 1251 const eq = -1; 1252 const er = -2; 1253 1254 try testing.expect((try q.to(i32)) == eq); 1255 try testing.expect((try r.to(i32)) == er); 1256} 1257 1258test "big.int div trunc single-single +/-" { 1259 const u: i32 = 5; 1260 const v: i32 = -3; 1261 1262 var a = try Managed.initSet(testing.allocator, u); 1263 defer a.deinit(); 1264 var b = try Managed.initSet(testing.allocator, v); 1265 defer b.deinit(); 1266 1267 var q = try Managed.init(testing.allocator); 1268 defer q.deinit(); 1269 var r = try Managed.init(testing.allocator); 1270 defer r.deinit(); 1271 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1272 1273 // n = q * d + r 1274 // 5 = -1 * -3 + 2 1275 const eq = -1; 1276 const er = 2; 1277 1278 try testing.expect((try q.to(i32)) == eq); 1279 try testing.expect((try r.to(i32)) == er); 1280} 1281 1282test "big.int div trunc single-single -/-" { 1283 const u: i32 = -5; 1284 const v: i32 = -3; 1285 1286 var a = try Managed.initSet(testing.allocator, u); 1287 defer a.deinit(); 1288 var b = try Managed.initSet(testing.allocator, v); 1289 defer b.deinit(); 1290 1291 var q = try Managed.init(testing.allocator); 1292 defer q.deinit(); 1293 var r = try Managed.init(testing.allocator); 1294 defer r.deinit(); 1295 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1296 1297 // n = q * d + r 1298 // -5 = 1 * -3 - 2 1299 const eq = 1; 1300 const er = -2; 1301 1302 try testing.expect((try q.to(i32)) == eq); 1303 try testing.expect((try r.to(i32)) == er); 1304} 1305 1306test "big.int div floor single-single +/+" { 1307 const u: i32 = 5; 1308 const v: i32 = 3; 1309 1310 var a = try Managed.initSet(testing.allocator, u); 1311 defer a.deinit(); 1312 var b = try Managed.initSet(testing.allocator, v); 1313 defer b.deinit(); 1314 1315 var q = try Managed.init(testing.allocator); 1316 defer q.deinit(); 1317 var r = try Managed.init(testing.allocator); 1318 defer r.deinit(); 1319 try Managed.divFloor(&q, &r, a.toConst(), b.toConst()); 1320 1321 // n = q * d + r 1322 // 5 = 1 * 3 + 2 1323 const eq = 1; 1324 const er = 2; 1325 1326 try testing.expect((try q.to(i32)) == eq); 1327 try testing.expect((try r.to(i32)) == er); 1328} 1329 1330test "big.int div floor single-single -/+" { 1331 const u: i32 = -5; 1332 const v: i32 = 3; 1333 1334 var a = try Managed.initSet(testing.allocator, u); 1335 defer a.deinit(); 1336 var b = try Managed.initSet(testing.allocator, v); 1337 defer b.deinit(); 1338 1339 var q = try Managed.init(testing.allocator); 1340 defer q.deinit(); 1341 var r = try Managed.init(testing.allocator); 1342 defer r.deinit(); 1343 try Managed.divFloor(&q, &r, a.toConst(), b.toConst()); 1344 1345 // n = q * d + r 1346 // -5 = -2 * 3 + 1 1347 const eq = -2; 1348 const er = 1; 1349 1350 try testing.expect((try q.to(i32)) == eq); 1351 try testing.expect((try r.to(i32)) == er); 1352} 1353 1354test "big.int div floor single-single +/-" { 1355 const u: i32 = 5; 1356 const v: i32 = -3; 1357 1358 var a = try Managed.initSet(testing.allocator, u); 1359 defer a.deinit(); 1360 var b = try Managed.initSet(testing.allocator, v); 1361 defer b.deinit(); 1362 1363 var q = try Managed.init(testing.allocator); 1364 defer q.deinit(); 1365 var r = try Managed.init(testing.allocator); 1366 defer r.deinit(); 1367 try Managed.divFloor(&q, &r, a.toConst(), b.toConst()); 1368 1369 // n = q * d + r 1370 // 5 = -2 * -3 - 1 1371 const eq = -2; 1372 const er = -1; 1373 1374 try testing.expect((try q.to(i32)) == eq); 1375 try testing.expect((try r.to(i32)) == er); 1376} 1377 1378test "big.int div floor single-single -/-" { 1379 const u: i32 = -5; 1380 const v: i32 = -3; 1381 1382 var a = try Managed.initSet(testing.allocator, u); 1383 defer a.deinit(); 1384 var b = try Managed.initSet(testing.allocator, v); 1385 defer b.deinit(); 1386 1387 var q = try Managed.init(testing.allocator); 1388 defer q.deinit(); 1389 var r = try Managed.init(testing.allocator); 1390 defer r.deinit(); 1391 try Managed.divFloor(&q, &r, a.toConst(), b.toConst()); 1392 1393 // n = q * d + r 1394 // -5 = 2 * -3 + 1 1395 const eq = 1; 1396 const er = -2; 1397 1398 try testing.expect((try q.to(i32)) == eq); 1399 try testing.expect((try r.to(i32)) == er); 1400} 1401 1402test "big.int div floor no remainder negative quotient" { 1403 const u: i32 = -0x80000000; 1404 const v: i32 = 1; 1405 1406 var a = try Managed.initSet(testing.allocator, u); 1407 defer a.deinit(); 1408 var b = try Managed.initSet(testing.allocator, v); 1409 defer b.deinit(); 1410 1411 var q = try Managed.init(testing.allocator); 1412 defer q.deinit(); 1413 var r = try Managed.init(testing.allocator); 1414 defer r.deinit(); 1415 try Managed.divFloor(&q, &r, a.toConst(), b.toConst()); 1416 1417 try testing.expect((try q.to(i32)) == -0x80000000); 1418 try testing.expect((try r.to(i32)) == 0); 1419} 1420 1421test "big.int div floor negative close to zero" { 1422 const u: i32 = -2; 1423 const v: i32 = 12; 1424 1425 var a = try Managed.initSet(testing.allocator, u); 1426 defer a.deinit(); 1427 var b = try Managed.initSet(testing.allocator, v); 1428 defer b.deinit(); 1429 1430 var q = try Managed.init(testing.allocator); 1431 defer q.deinit(); 1432 var r = try Managed.init(testing.allocator); 1433 defer r.deinit(); 1434 try Managed.divFloor(&q, &r, a.toConst(), b.toConst()); 1435 1436 try testing.expect((try q.to(i32)) == -1); 1437 try testing.expect((try r.to(i32)) == 10); 1438} 1439 1440test "big.int div floor positive close to zero" { 1441 const u: i32 = 10; 1442 const v: i32 = 12; 1443 1444 var a = try Managed.initSet(testing.allocator, u); 1445 defer a.deinit(); 1446 var b = try Managed.initSet(testing.allocator, v); 1447 defer b.deinit(); 1448 1449 var q = try Managed.init(testing.allocator); 1450 defer q.deinit(); 1451 var r = try Managed.init(testing.allocator); 1452 defer r.deinit(); 1453 try Managed.divFloor(&q, &r, a.toConst(), b.toConst()); 1454 1455 try testing.expect((try q.to(i32)) == 0); 1456 try testing.expect((try r.to(i32)) == 10); 1457} 1458 1459test "big.int div multi-multi with rem" { 1460 var a = try Managed.initSet(testing.allocator, 0x8888999911110000ffffeeeeddddccccbbbbaaaa9999); 1461 defer a.deinit(); 1462 var b = try Managed.initSet(testing.allocator, 0x99990000111122223333); 1463 defer b.deinit(); 1464 1465 var q = try Managed.init(testing.allocator); 1466 defer q.deinit(); 1467 var r = try Managed.init(testing.allocator); 1468 defer r.deinit(); 1469 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1470 1471 try testing.expect((try q.to(u128)) == 0xe38f38e39161aaabd03f0f1b); 1472 try testing.expect((try r.to(u128)) == 0x28de0acacd806823638); 1473} 1474 1475test "big.int div multi-multi no rem" { 1476 var a = try Managed.initSet(testing.allocator, 0x8888999911110000ffffeeeedb4fec200ee3a4286361); 1477 defer a.deinit(); 1478 var b = try Managed.initSet(testing.allocator, 0x99990000111122223333); 1479 defer b.deinit(); 1480 1481 var q = try Managed.init(testing.allocator); 1482 defer q.deinit(); 1483 var r = try Managed.init(testing.allocator); 1484 defer r.deinit(); 1485 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1486 1487 try testing.expect((try q.to(u128)) == 0xe38f38e39161aaabd03f0f1b); 1488 try testing.expect((try r.to(u128)) == 0); 1489} 1490 1491test "big.int div multi-multi (2 branch)" { 1492 var a = try Managed.initSet(testing.allocator, 0x866666665555555588888887777777761111111111111111); 1493 defer a.deinit(); 1494 var b = try Managed.initSet(testing.allocator, 0x86666666555555554444444433333333); 1495 defer b.deinit(); 1496 1497 var q = try Managed.init(testing.allocator); 1498 defer q.deinit(); 1499 var r = try Managed.init(testing.allocator); 1500 defer r.deinit(); 1501 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1502 1503 try testing.expect((try q.to(u128)) == 0x10000000000000000); 1504 try testing.expect((try r.to(u128)) == 0x44444443444444431111111111111111); 1505} 1506 1507test "big.int div multi-multi (3.1/3.3 branch)" { 1508 var a = try Managed.initSet(testing.allocator, 0x11111111111111111111111111111111111111111111111111111111111111); 1509 defer a.deinit(); 1510 var b = try Managed.initSet(testing.allocator, 0x1111111111111111111111111111111111111111171); 1511 defer b.deinit(); 1512 1513 var q = try Managed.init(testing.allocator); 1514 defer q.deinit(); 1515 var r = try Managed.init(testing.allocator); 1516 defer r.deinit(); 1517 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1518 1519 try testing.expect((try q.to(u128)) == 0xfffffffffffffffffff); 1520 try testing.expect((try r.to(u256)) == 0x1111111111111111111110b12222222222222222282); 1521} 1522 1523test "big.int div multi-single zero-limb trailing" { 1524 var a = try Managed.initSet(testing.allocator, 0x60000000000000000000000000000000000000000000000000000000000000000); 1525 defer a.deinit(); 1526 var b = try Managed.initSet(testing.allocator, 0x10000000000000000); 1527 defer b.deinit(); 1528 1529 var q = try Managed.init(testing.allocator); 1530 defer q.deinit(); 1531 var r = try Managed.init(testing.allocator); 1532 defer r.deinit(); 1533 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1534 1535 var expected = try Managed.initSet(testing.allocator, 0x6000000000000000000000000000000000000000000000000); 1536 defer expected.deinit(); 1537 try testing.expect(q.eq(expected)); 1538 try testing.expect(r.eqZero()); 1539} 1540 1541test "big.int div multi-multi zero-limb trailing (with rem)" { 1542 var a = try Managed.initSet(testing.allocator, 0x86666666555555558888888777777776111111111111111100000000000000000000000000000000); 1543 defer a.deinit(); 1544 var b = try Managed.initSet(testing.allocator, 0x8666666655555555444444443333333300000000000000000000000000000000); 1545 defer b.deinit(); 1546 1547 var q = try Managed.init(testing.allocator); 1548 defer q.deinit(); 1549 var r = try Managed.init(testing.allocator); 1550 defer r.deinit(); 1551 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1552 1553 try testing.expect((try q.to(u128)) == 0x10000000000000000); 1554 1555 const rs = try r.toString(testing.allocator, 16, .lower); 1556 defer testing.allocator.free(rs); 1557 try testing.expect(std.mem.eql(u8, rs, "4444444344444443111111111111111100000000000000000000000000000000")); 1558} 1559 1560test "big.int div multi-multi zero-limb trailing (with rem) and dividend zero-limb count > divisor zero-limb count" { 1561 var a = try Managed.initSet(testing.allocator, 0x8666666655555555888888877777777611111111111111110000000000000000); 1562 defer a.deinit(); 1563 var b = try Managed.initSet(testing.allocator, 0x8666666655555555444444443333333300000000000000000000000000000000); 1564 defer b.deinit(); 1565 1566 var q = try Managed.init(testing.allocator); 1567 defer q.deinit(); 1568 var r = try Managed.init(testing.allocator); 1569 defer r.deinit(); 1570 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1571 1572 try testing.expect((try q.to(u128)) == 0x1); 1573 1574 const rs = try r.toString(testing.allocator, 16, .lower); 1575 defer testing.allocator.free(rs); 1576 try testing.expect(std.mem.eql(u8, rs, "444444434444444311111111111111110000000000000000")); 1577} 1578 1579test "big.int div multi-multi zero-limb trailing (with rem) and dividend zero-limb count < divisor zero-limb count" { 1580 var a = try Managed.initSet(testing.allocator, 0x86666666555555558888888777777776111111111111111100000000000000000000000000000000); 1581 defer a.deinit(); 1582 var b = try Managed.initSet(testing.allocator, 0x866666665555555544444444333333330000000000000000); 1583 defer b.deinit(); 1584 1585 var q = try Managed.init(testing.allocator); 1586 defer q.deinit(); 1587 var r = try Managed.init(testing.allocator); 1588 defer r.deinit(); 1589 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1590 1591 const qs = try q.toString(testing.allocator, 16, .lower); 1592 defer testing.allocator.free(qs); 1593 try testing.expect(std.mem.eql(u8, qs, "10000000000000000820820803105186f")); 1594 1595 const rs = try r.toString(testing.allocator, 16, .lower); 1596 defer testing.allocator.free(rs); 1597 try testing.expect(std.mem.eql(u8, rs, "4e11f2baa5896a321d463b543d0104e30000000000000000")); 1598} 1599 1600test "big.int div multi-multi fuzz case #1" { 1601 var a = try Managed.init(testing.allocator); 1602 defer a.deinit(); 1603 var b = try Managed.init(testing.allocator); 1604 defer b.deinit(); 1605 1606 try a.setString(16, "ffffffffffffffffffffffffffffc00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"); 1607 try b.setString(16, "3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0000000000000000000000000000000000001ffffffffffffffffffffffffffffffffffffffffffffffffffc000000000000000000000000000000007fffffffffff"); 1608 1609 var q = try Managed.init(testing.allocator); 1610 defer q.deinit(); 1611 var r = try Managed.init(testing.allocator); 1612 defer r.deinit(); 1613 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1614 1615 const qs = try q.toString(testing.allocator, 16, .lower); 1616 defer testing.allocator.free(qs); 1617 try testing.expect(std.mem.eql(u8, qs, "3ffffffffffffffffffffffffffff0000000000000000000000000000000000001ffffffffffffffffffffffffffff7fffffffe000000000000000000000000000180000000000000000000003fffffbfffffffdfffffffffffffeffff800000100101000000100000000020003fffffdfbfffffe3ffffffffffffeffff7fffc00800a100000017ffe000002000400007efbfff7fe9f00000037ffff3fff7fffa004006100000009ffe00000190038200bf7d2ff7fefe80400060000f7d7f8fbf9401fe38e0403ffc0bdffffa51102c300d7be5ef9df4e5060007b0127ad3fa69f97d0f820b6605ff617ddf7f32ad7a05c0d03f2e7bc78a6000e087a8bbcdc59e07a5a079128a7861f553ddebed7e8e56701756f9ead39b48cd1b0831889ea6ec1fddf643d0565b075ff07e6caea4e2854ec9227fd635ed60a2f5eef2893052ffd54718fa08604acbf6a15e78a467c4a3c53c0278af06c4416573f925491b195e8fd79302cb1aaf7caf4ecfc9aec1254cc969786363ac729f914c6ddcc26738d6b0facd54eba026580aba2eb6482a088b0d224a8852420b91ec1")); 1618 1619 const rs = try r.toString(testing.allocator, 16, .lower); 1620 defer testing.allocator.free(rs); 1621 try testing.expect(std.mem.eql(u8, rs, "310d1d4c414426b4836c2635bad1df3a424e50cbdd167ffccb4dfff57d36b4aae0d6ca0910698220171a0f3373c1060a046c2812f0027e321f72979daa5e7973214170d49e885de0c0ecc167837d44502430674a82522e5df6a0759548052420b91ec1")); 1622} 1623 1624test "big.int div multi-multi fuzz case #2" { 1625 var a = try Managed.init(testing.allocator); 1626 defer a.deinit(); 1627 var b = try Managed.init(testing.allocator); 1628 defer b.deinit(); 1629 1630 try a.setString(16, "3ffffffffe00000000000000000000000000fffffffffffffffffffffffffffffffffffffffffffffffffffffffffe000000000000000000000000000000000000000000000000000000000000001fffffffffffffffff800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffc000000000000000000000000000000000000000000000000000000000000000"); 1631 try b.setString(16, "ffc0000000000000000000000000000000000000000000000000"); 1632 1633 var q = try Managed.init(testing.allocator); 1634 defer q.deinit(); 1635 var r = try Managed.init(testing.allocator); 1636 defer r.deinit(); 1637 try Managed.divTrunc(&q, &r, a.toConst(), b.toConst()); 1638 1639 const qs = try q.toString(testing.allocator, 16, .lower); 1640 defer testing.allocator.free(qs); 1641 try testing.expect(std.mem.eql(u8, qs, "40100400fe3f8fe3f8fe3f8fe3f8fe3f8fe4f93e4f93e4f93e4f93e4f93e4f93e4f93e4f93e4f93e4f93e4f93e4f91e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4992649926499264991e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4792e4b92e4b92e4b92e4b92a4a92a4a92a4")); 1642 1643 const rs = try r.toString(testing.allocator, 16, .lower); 1644 defer testing.allocator.free(rs); 1645 try testing.expect(std.mem.eql(u8, rs, "a900000000000000000000000000000000000000000000000000")); 1646} 1647 1648test "big.int truncate single unsigned" { 1649 var a = try Managed.initSet(testing.allocator, maxInt(u47)); 1650 defer a.deinit(); 1651 1652 try a.truncate(a.toConst(), .unsigned, 17); 1653 1654 try testing.expect((try a.to(u17)) == maxInt(u17)); 1655} 1656 1657test "big.int truncate single signed" { 1658 var a = try Managed.initSet(testing.allocator, 0x1_0000); 1659 defer a.deinit(); 1660 1661 try a.truncate(a.toConst(), .signed, 17); 1662 1663 try testing.expect((try a.to(i17)) == minInt(i17)); 1664} 1665 1666test "big.int truncate multi to single unsigned" { 1667 var a = try Managed.initSet(testing.allocator, (maxInt(Limb) + 1) | 0x1234_5678_9ABC_DEF0); 1668 defer a.deinit(); 1669 1670 try a.truncate(a.toConst(), .unsigned, 27); 1671 1672 try testing.expect((try a.to(u27)) == 0x2BC_DEF0); 1673} 1674 1675test "big.int truncate multi to single signed" { 1676 var a = try Managed.initSet(testing.allocator, maxInt(Limb) << 10); 1677 defer a.deinit(); 1678 1679 try a.truncate(a.toConst(), .signed, @bitSizeOf(i11)); 1680 1681 try testing.expect((try a.to(i11)) == minInt(i11)); 1682} 1683 1684test "big.int truncate multi to multi unsigned" { 1685 const bits = @typeInfo(SignedDoubleLimb).Int.bits; 1686 const Int = std.meta.Int(.unsigned, bits - 1); 1687 1688 var a = try Managed.initSet(testing.allocator, maxInt(SignedDoubleLimb)); 1689 defer a.deinit(); 1690 1691 try a.truncate(a.toConst(), .unsigned, bits - 1); 1692 1693 try testing.expect((try a.to(Int)) == maxInt(Int)); 1694} 1695 1696test "big.int truncate multi to multi signed" { 1697 var a = try Managed.initSet(testing.allocator, 3 << @bitSizeOf(Limb)); 1698 defer a.deinit(); 1699 1700 try a.truncate(a.toConst(), .signed, @bitSizeOf(Limb) + 1); 1701 1702 try testing.expect((try a.to(std.meta.Int(.signed, @bitSizeOf(Limb) + 1))) == -1 << @bitSizeOf(Limb)); 1703} 1704 1705test "big.int truncate negative multi to single" { 1706 var a = try Managed.initSet(testing.allocator, -@as(SignedDoubleLimb, maxInt(Limb) + 1)); 1707 defer a.deinit(); 1708 1709 try a.truncate(a.toConst(), .signed, @bitSizeOf(i17)); 1710 1711 try testing.expect((try a.to(i17)) == 0); 1712} 1713 1714test "big.int truncate multi unsigned many" { 1715 var a = try Managed.initSet(testing.allocator, 1); 1716 defer a.deinit(); 1717 try a.shiftLeft(a, 1023); 1718 1719 var b = try Managed.init(testing.allocator); 1720 defer b.deinit(); 1721 try b.truncate(a.toConst(), .signed, @bitSizeOf(i1)); 1722 1723 try testing.expect((try b.to(i1)) == 0); 1724} 1725 1726test "big.int saturate single signed positive" { 1727 var a = try Managed.initSet(testing.allocator, 0xBBBB_BBBB); 1728 defer a.deinit(); 1729 1730 try a.saturate(a.toConst(), .signed, 17); 1731 1732 try testing.expect((try a.to(i17)) == maxInt(i17)); 1733} 1734 1735test "big.int saturate single signed negative" { 1736 var a = try Managed.initSet(testing.allocator, -1_234_567); 1737 defer a.deinit(); 1738 1739 try a.saturate(a.toConst(), .signed, 17); 1740 1741 try testing.expect((try a.to(i17)) == minInt(i17)); 1742} 1743 1744test "big.int saturate single signed" { 1745 var a = try Managed.initSet(testing.allocator, maxInt(i17) - 1); 1746 defer a.deinit(); 1747 1748 try a.saturate(a.toConst(), .signed, 17); 1749 1750 try testing.expect((try a.to(i17)) == maxInt(i17) - 1); 1751} 1752 1753test "big.int saturate multi signed" { 1754 var a = try Managed.initSet(testing.allocator, maxInt(Limb) << @bitSizeOf(SignedDoubleLimb)); 1755 defer a.deinit(); 1756 1757 try a.saturate(a.toConst(), .signed, @bitSizeOf(SignedDoubleLimb)); 1758 1759 try testing.expect((try a.to(SignedDoubleLimb)) == maxInt(SignedDoubleLimb)); 1760} 1761 1762test "big.int saturate single unsigned" { 1763 var a = try Managed.initSet(testing.allocator, 0xFEFE_FEFE); 1764 defer a.deinit(); 1765 1766 try a.saturate(a.toConst(), .unsigned, 23); 1767 1768 try testing.expect((try a.to(u23)) == maxInt(u23)); 1769} 1770 1771test "big.int saturate multi unsigned zero" { 1772 var a = try Managed.initSet(testing.allocator, -1); 1773 defer a.deinit(); 1774 1775 try a.saturate(a.toConst(), .unsigned, @bitSizeOf(DoubleLimb)); 1776 1777 try testing.expect(a.eqZero()); 1778} 1779 1780test "big.int saturate multi unsigned" { 1781 var a = try Managed.initSet(testing.allocator, maxInt(Limb) << @bitSizeOf(DoubleLimb)); 1782 defer a.deinit(); 1783 1784 try a.saturate(a.toConst(), .unsigned, @bitSizeOf(DoubleLimb)); 1785 1786 try testing.expect((try a.to(DoubleLimb)) == maxInt(DoubleLimb)); 1787} 1788 1789test "big.int shift-right single" { 1790 var a = try Managed.initSet(testing.allocator, 0xffff0000); 1791 defer a.deinit(); 1792 try a.shiftRight(a, 16); 1793 1794 try testing.expect((try a.to(u32)) == 0xffff); 1795} 1796 1797test "big.int shift-right multi" { 1798 var a = try Managed.initSet(testing.allocator, 0xffff0000eeee1111dddd2222cccc3333); 1799 defer a.deinit(); 1800 try a.shiftRight(a, 67); 1801 1802 try testing.expect((try a.to(u64)) == 0x1fffe0001dddc222); 1803 1804 try a.set(0xffff0000eeee1111dddd2222cccc3333); 1805 try a.shiftRight(a, 63); 1806 try a.shiftRight(a, 63); 1807 try a.shiftRight(a, 2); 1808 try testing.expect(a.eqZero()); 1809} 1810 1811test "big.int shift-left single" { 1812 var a = try Managed.initSet(testing.allocator, 0xffff); 1813 defer a.deinit(); 1814 try a.shiftLeft(a, 16); 1815 1816 try testing.expect((try a.to(u64)) == 0xffff0000); 1817} 1818 1819test "big.int shift-left multi" { 1820 var a = try Managed.initSet(testing.allocator, 0x1fffe0001dddc222); 1821 defer a.deinit(); 1822 try a.shiftLeft(a, 67); 1823 1824 try testing.expect((try a.to(u128)) == 0xffff0000eeee11100000000000000000); 1825} 1826 1827test "big.int shift-right negative" { 1828 var a = try Managed.init(testing.allocator); 1829 defer a.deinit(); 1830 1831 var arg = try Managed.initSet(testing.allocator, -20); 1832 defer arg.deinit(); 1833 try a.shiftRight(arg, 2); 1834 try testing.expect((try a.to(i32)) == -20 >> 2); 1835 1836 var arg2 = try Managed.initSet(testing.allocator, -5); 1837 defer arg2.deinit(); 1838 try a.shiftRight(arg2, 10); 1839 try testing.expect((try a.to(i32)) == -5 >> 10); 1840} 1841 1842test "big.int shift-left negative" { 1843 var a = try Managed.init(testing.allocator); 1844 defer a.deinit(); 1845 1846 var arg = try Managed.initSet(testing.allocator, -10); 1847 defer arg.deinit(); 1848 try a.shiftRight(arg, 1232); 1849 try testing.expect((try a.to(i32)) == -10 >> 1232); 1850} 1851 1852test "big.int sat shift-left simple unsigned" { 1853 var a = try Managed.initSet(testing.allocator, 0xffff); 1854 defer a.deinit(); 1855 try a.shiftLeftSat(a, 16, .unsigned, 21); 1856 1857 try testing.expect((try a.to(u64)) == 0x1fffff); 1858} 1859 1860test "big.int sat shift-left simple unsigned no sat" { 1861 var a = try Managed.initSet(testing.allocator, 1); 1862 defer a.deinit(); 1863 try a.shiftLeftSat(a, 16, .unsigned, 21); 1864 1865 try testing.expect((try a.to(u64)) == 0x10000); 1866} 1867 1868test "big.int sat shift-left multi unsigned" { 1869 var a = try Managed.initSet(testing.allocator, 16); 1870 defer a.deinit(); 1871 try a.shiftLeftSat(a, @bitSizeOf(DoubleLimb) - 3, .unsigned, @bitSizeOf(DoubleLimb) - 1); 1872 1873 try testing.expect((try a.to(DoubleLimb)) == maxInt(DoubleLimb) >> 1); 1874} 1875 1876test "big.int sat shift-left unsigned shift > bitcount" { 1877 var a = try Managed.initSet(testing.allocator, 1); 1878 defer a.deinit(); 1879 try a.shiftLeftSat(a, 10, .unsigned, 10); 1880 1881 try testing.expect((try a.to(u10)) == maxInt(u10)); 1882} 1883 1884test "big.int sat shift-left unsigned zero" { 1885 var a = try Managed.initSet(testing.allocator, 0); 1886 defer a.deinit(); 1887 try a.shiftLeftSat(a, 1, .unsigned, 0); 1888 1889 try testing.expect((try a.to(u64)) == 0); 1890} 1891 1892test "big.int sat shift-left unsigned negative" { 1893 var a = try Managed.initSet(testing.allocator, -100); 1894 defer a.deinit(); 1895 try a.shiftLeftSat(a, 0, .unsigned, 0); 1896 1897 try testing.expect((try a.to(u64)) == 0); 1898} 1899 1900test "big.int sat shift-left signed simple negative" { 1901 var a = try Managed.initSet(testing.allocator, -100); 1902 defer a.deinit(); 1903 try a.shiftLeftSat(a, 3, .signed, 10); 1904 1905 try testing.expect((try a.to(i10)) == minInt(i10)); 1906} 1907 1908test "big.int sat shift-left signed simple positive" { 1909 var a = try Managed.initSet(testing.allocator, 100); 1910 defer a.deinit(); 1911 try a.shiftLeftSat(a, 3, .signed, 10); 1912 1913 try testing.expect((try a.to(i10)) == maxInt(i10)); 1914} 1915 1916test "big.int sat shift-left signed multi positive" { 1917 const x = 1; 1918 const shift = @bitSizeOf(SignedDoubleLimb) - 1; 1919 1920 var a = try Managed.initSet(testing.allocator, x); 1921 defer a.deinit(); 1922 try a.shiftLeftSat(a, shift, .signed, @bitSizeOf(SignedDoubleLimb)); 1923 1924 try testing.expect((try a.to(SignedDoubleLimb)) == @as(SignedDoubleLimb, x) <<| shift); 1925} 1926 1927test "big.int sat shift-left signed multi negative" { 1928 const x = -1; 1929 const shift = @bitSizeOf(SignedDoubleLimb) - 1; 1930 1931 var a = try Managed.initSet(testing.allocator, x); 1932 defer a.deinit(); 1933 try a.shiftLeftSat(a, shift, .signed, @bitSizeOf(SignedDoubleLimb)); 1934 1935 try testing.expect((try a.to(SignedDoubleLimb)) == @as(SignedDoubleLimb, x) <<| shift); 1936} 1937 1938test "big.int bitNotWrap unsigned simple" { 1939 var a = try Managed.initSet(testing.allocator, 123); 1940 defer a.deinit(); 1941 1942 try a.bitNotWrap(a, .unsigned, 10); 1943 1944 try testing.expect((try a.to(u10)) == ~@as(u10, 123)); 1945} 1946 1947test "big.int bitNotWrap unsigned multi" { 1948 var a = try Managed.initSet(testing.allocator, 0); 1949 defer a.deinit(); 1950 1951 try a.bitNotWrap(a, .unsigned, @bitSizeOf(DoubleLimb)); 1952 1953 try testing.expect((try a.to(DoubleLimb)) == maxInt(DoubleLimb)); 1954} 1955 1956test "big.int bitNotWrap signed simple" { 1957 var a = try Managed.initSet(testing.allocator, -456); 1958 defer a.deinit(); 1959 1960 try a.bitNotWrap(a, .signed, 11); 1961 1962 try testing.expect((try a.to(i11)) == ~@as(i11, -456)); 1963} 1964 1965test "big.int bitNotWrap signed multi" { 1966 var a = try Managed.initSet(testing.allocator, 0); 1967 defer a.deinit(); 1968 1969 try a.bitNotWrap(a, .signed, @bitSizeOf(SignedDoubleLimb)); 1970 1971 try testing.expect((try a.to(SignedDoubleLimb)) == -1); 1972} 1973 1974test "big.int bitwise and simple" { 1975 var a = try Managed.initSet(testing.allocator, 0xffffffff11111111); 1976 defer a.deinit(); 1977 var b = try Managed.initSet(testing.allocator, 0xeeeeeeee22222222); 1978 defer b.deinit(); 1979 1980 try a.bitAnd(a, b); 1981 1982 try testing.expect((try a.to(u64)) == 0xeeeeeeee00000000); 1983} 1984 1985test "big.int bitwise and multi-limb" { 1986 var a = try Managed.initSet(testing.allocator, maxInt(Limb) + 1); 1987 defer a.deinit(); 1988 var b = try Managed.initSet(testing.allocator, maxInt(Limb)); 1989 defer b.deinit(); 1990 1991 try a.bitAnd(a, b); 1992 1993 try testing.expect((try a.to(u128)) == 0); 1994} 1995 1996test "big.int bitwise and negative-positive simple" { 1997 var a = try Managed.initSet(testing.allocator, -0xffffffff11111111); 1998 defer a.deinit(); 1999 var b = try Managed.initSet(testing.allocator, 0xeeeeeeee22222222); 2000 defer b.deinit(); 2001 2002 try a.bitAnd(a, b); 2003 2004 try testing.expect((try a.to(u64)) == 0x22222222); 2005} 2006 2007test "big.int bitwise and negative-positive multi-limb" { 2008 var a = try Managed.initSet(testing.allocator, -maxInt(Limb) - 1); 2009 defer a.deinit(); 2010 var b = try Managed.initSet(testing.allocator, maxInt(Limb)); 2011 defer b.deinit(); 2012 2013 try a.bitAnd(a, b); 2014 2015 try testing.expect(a.eqZero()); 2016} 2017 2018test "big.int bitwise and positive-negative simple" { 2019 var a = try Managed.initSet(testing.allocator, 0xffffffff11111111); 2020 defer a.deinit(); 2021 var b = try Managed.initSet(testing.allocator, -0xeeeeeeee22222222); 2022 defer b.deinit(); 2023 2024 try a.bitAnd(a, b); 2025 2026 try testing.expect((try a.to(u64)) == 0x1111111111111110); 2027} 2028 2029test "big.int bitwise and positive-negative multi-limb" { 2030 var a = try Managed.initSet(testing.allocator, maxInt(Limb)); 2031 defer a.deinit(); 2032 var b = try Managed.initSet(testing.allocator, -maxInt(Limb) - 1); 2033 defer b.deinit(); 2034 2035 try a.bitAnd(a, b); 2036 2037 try testing.expect(a.eqZero()); 2038} 2039 2040test "big.int bitwise and negative-negative simple" { 2041 var a = try Managed.initSet(testing.allocator, -0xffffffff11111111); 2042 defer a.deinit(); 2043 var b = try Managed.initSet(testing.allocator, -0xeeeeeeee22222222); 2044 defer b.deinit(); 2045 2046 try a.bitAnd(a, b); 2047 2048 try testing.expect((try a.to(i128)) == -0xffffffff33333332); 2049} 2050 2051test "big.int bitwise and negative-negative multi-limb" { 2052 var a = try Managed.initSet(testing.allocator, -maxInt(Limb) - 1); 2053 defer a.deinit(); 2054 var b = try Managed.initSet(testing.allocator, -maxInt(Limb) - 2); 2055 defer b.deinit(); 2056 2057 try a.bitAnd(a, b); 2058 2059 try testing.expect((try a.to(i128)) == -maxInt(Limb) * 2 - 2); 2060} 2061 2062test "big.int bitwise and negative overflow" { 2063 var a = try Managed.initSet(testing.allocator, -maxInt(Limb)); 2064 defer a.deinit(); 2065 var b = try Managed.initSet(testing.allocator, -2); 2066 defer b.deinit(); 2067 2068 try a.bitAnd(a, b); 2069 2070 try testing.expect((try a.to(SignedDoubleLimb)) == -maxInt(Limb) - 1); 2071} 2072 2073test "big.int bitwise xor simple" { 2074 var a = try Managed.initSet(testing.allocator, 0xffffffff11111111); 2075 defer a.deinit(); 2076 var b = try Managed.initSet(testing.allocator, 0xeeeeeeee22222222); 2077 defer b.deinit(); 2078 2079 try a.bitXor(a, b); 2080 2081 try testing.expect((try a.to(u64)) == 0x1111111133333333); 2082} 2083 2084test "big.int bitwise xor multi-limb" { 2085 var a = try Managed.initSet(testing.allocator, maxInt(Limb) + 1); 2086 defer a.deinit(); 2087 var b = try Managed.initSet(testing.allocator, maxInt(Limb)); 2088 defer b.deinit(); 2089 2090 try a.bitXor(a, b); 2091 2092 try testing.expect((try a.to(DoubleLimb)) == (maxInt(Limb) + 1) ^ maxInt(Limb)); 2093} 2094 2095test "big.int bitwise xor single negative simple" { 2096 var a = try Managed.initSet(testing.allocator, 0x6b03e381328a3154); 2097 defer a.deinit(); 2098 var b = try Managed.initSet(testing.allocator, -0x45fd3acef9191fad); 2099 defer b.deinit(); 2100 2101 try a.bitXor(a, b); 2102 2103 try testing.expect((try a.to(i64)) == -0x2efed94fcb932ef9); 2104} 2105 2106test "big.int bitwise xor single negative zero" { 2107 var a = try Managed.initSet(testing.allocator, 0); 2108 defer a.deinit(); 2109 var b = try Managed.initSet(testing.allocator, -0); 2110 defer b.deinit(); 2111 2112 try a.bitXor(a, b); 2113 2114 try testing.expect(a.eqZero()); 2115} 2116 2117test "big.int bitwise xor single negative multi-limb" { 2118 var a = try Managed.initSet(testing.allocator, -0x9849c6e7a10d66d0e4260d4846254c32); 2119 defer a.deinit(); 2120 var b = try Managed.initSet(testing.allocator, 0xf2194e7d1c855272a997fcde16f6d5a8); 2121 defer b.deinit(); 2122 2123 try a.bitXor(a, b); 2124 2125 try testing.expect((try a.to(i128)) == -0x6a50889abd8834a24db1f19650d3999a); 2126} 2127 2128test "big.int bitwise xor single negative overflow" { 2129 var a = try Managed.initSet(testing.allocator, maxInt(Limb)); 2130 defer a.deinit(); 2131 var b = try Managed.initSet(testing.allocator, -1); 2132 defer b.deinit(); 2133 2134 try a.bitXor(a, b); 2135 2136 try testing.expect((try a.to(SignedDoubleLimb)) == -(maxInt(Limb) + 1)); 2137} 2138 2139test "big.int bitwise xor double negative simple" { 2140 var a = try Managed.initSet(testing.allocator, -0x8e48bd5f755ef1f3); 2141 defer a.deinit(); 2142 var b = try Managed.initSet(testing.allocator, -0x4dd4fa576f3046ac); 2143 defer b.deinit(); 2144 2145 try a.bitXor(a, b); 2146 2147 try testing.expect((try a.to(u64)) == 0xc39c47081a6eb759); 2148} 2149 2150test "big.int bitwise xor double negative multi-limb" { 2151 var a = try Managed.initSet(testing.allocator, -0x684e5da8f500ec8ca7204c33ccc51c9c); 2152 defer a.deinit(); 2153 var b = try Managed.initSet(testing.allocator, -0xcb07736a7b62289c78d967c3985eebeb); 2154 defer b.deinit(); 2155 2156 try a.bitXor(a, b); 2157 2158 try testing.expect((try a.to(u128)) == 0xa3492ec28e62c410dff92bf0549bf771); 2159} 2160 2161test "big.int bitwise or simple" { 2162 var a = try Managed.initSet(testing.allocator, 0xffffffff11111111); 2163 defer a.deinit(); 2164 var b = try Managed.initSet(testing.allocator, 0xeeeeeeee22222222); 2165 defer b.deinit(); 2166 2167 try a.bitOr(a, b); 2168 2169 try testing.expect((try a.to(u64)) == 0xffffffff33333333); 2170} 2171 2172test "big.int bitwise or multi-limb" { 2173 var a = try Managed.initSet(testing.allocator, maxInt(Limb) + 1); 2174 defer a.deinit(); 2175 var b = try Managed.initSet(testing.allocator, maxInt(Limb)); 2176 defer b.deinit(); 2177 2178 try a.bitOr(a, b); 2179 2180 // TODO: big.int.cpp or is wrong on multi-limb. 2181 try testing.expect((try a.to(DoubleLimb)) == (maxInt(Limb) + 1) + maxInt(Limb)); 2182} 2183 2184test "big.int bitwise or negative-positive simple" { 2185 var a = try Managed.initSet(testing.allocator, -0xffffffff11111111); 2186 defer a.deinit(); 2187 var b = try Managed.initSet(testing.allocator, 0xeeeeeeee22222222); 2188 defer b.deinit(); 2189 2190 try a.bitOr(a, b); 2191 2192 try testing.expect((try a.to(i64)) == -0x1111111111111111); 2193} 2194 2195test "big.int bitwise or negative-positive multi-limb" { 2196 var a = try Managed.initSet(testing.allocator, -maxInt(Limb) - 1); 2197 defer a.deinit(); 2198 var b = try Managed.initSet(testing.allocator, 1); 2199 defer b.deinit(); 2200 2201 try a.bitOr(a, b); 2202 2203 try testing.expect((try a.to(SignedDoubleLimb)) == -maxInt(Limb)); 2204} 2205 2206test "big.int bitwise or positive-negative simple" { 2207 var a = try Managed.initSet(testing.allocator, 0xffffffff11111111); 2208 defer a.deinit(); 2209 var b = try Managed.initSet(testing.allocator, -0xeeeeeeee22222222); 2210 defer b.deinit(); 2211 2212 try a.bitOr(a, b); 2213 2214 try testing.expect((try a.to(i64)) == -0x22222221); 2215} 2216 2217test "big.int bitwise or positive-negative multi-limb" { 2218 var a = try Managed.initSet(testing.allocator, maxInt(Limb) + 1); 2219 defer a.deinit(); 2220 var b = try Managed.initSet(testing.allocator, -1); 2221 defer b.deinit(); 2222 2223 try a.bitOr(a, b); 2224 2225 try testing.expect((try a.to(SignedDoubleLimb)) == -1); 2226} 2227 2228test "big.int bitwise or negative-negative simple" { 2229 var a = try Managed.initSet(testing.allocator, -0xffffffff11111111); 2230 defer a.deinit(); 2231 var b = try Managed.initSet(testing.allocator, -0xeeeeeeee22222222); 2232 defer b.deinit(); 2233 2234 try a.bitOr(a, b); 2235 2236 try testing.expect((try a.to(i128)) == -0xeeeeeeee00000001); 2237} 2238 2239test "big.int bitwise or negative-negative multi-limb" { 2240 var a = try Managed.initSet(testing.allocator, -maxInt(Limb) - 1); 2241 defer a.deinit(); 2242 var b = try Managed.initSet(testing.allocator, -maxInt(Limb)); 2243 defer b.deinit(); 2244 2245 try a.bitOr(a, b); 2246 2247 try testing.expect((try a.to(SignedDoubleLimb)) == -maxInt(Limb)); 2248} 2249 2250test "big.int var args" { 2251 var a = try Managed.initSet(testing.allocator, 5); 2252 defer a.deinit(); 2253 2254 var b = try Managed.initSet(testing.allocator, 6); 2255 defer b.deinit(); 2256 try a.add(a.toConst(), b.toConst()); 2257 try testing.expect((try a.to(u64)) == 11); 2258 2259 var c = try Managed.initSet(testing.allocator, 11); 2260 defer c.deinit(); 2261 try testing.expect(a.order(c) == .eq); 2262 2263 var d = try Managed.initSet(testing.allocator, 14); 2264 defer d.deinit(); 2265 try testing.expect(a.order(d) != .gt); 2266} 2267 2268test "big.int gcd non-one small" { 2269 var a = try Managed.initSet(testing.allocator, 17); 2270 defer a.deinit(); 2271 var b = try Managed.initSet(testing.allocator, 97); 2272 defer b.deinit(); 2273 var r = try Managed.init(testing.allocator); 2274 defer r.deinit(); 2275 2276 try r.gcd(a, b); 2277 2278 try testing.expect((try r.to(u32)) == 1); 2279} 2280 2281test "big.int gcd non-one small" { 2282 var a = try Managed.initSet(testing.allocator, 4864); 2283 defer a.deinit(); 2284 var b = try Managed.initSet(testing.allocator, 3458); 2285 defer b.deinit(); 2286 var r = try Managed.init(testing.allocator); 2287 defer r.deinit(); 2288 2289 try r.gcd(a, b); 2290 2291 try testing.expect((try r.to(u32)) == 38); 2292} 2293 2294test "big.int gcd non-one large" { 2295 var a = try Managed.initSet(testing.allocator, 0xffffffffffffffff); 2296 defer a.deinit(); 2297 var b = try Managed.initSet(testing.allocator, 0xffffffffffffffff7777); 2298 defer b.deinit(); 2299 var r = try Managed.init(testing.allocator); 2300 defer r.deinit(); 2301 2302 try r.gcd(a, b); 2303 2304 try testing.expect((try r.to(u32)) == 4369); 2305} 2306 2307test "big.int gcd large multi-limb result" { 2308 var a = try Managed.initSet(testing.allocator, 0x12345678123456781234567812345678123456781234567812345678); 2309 defer a.deinit(); 2310 var b = try Managed.initSet(testing.allocator, 0x12345671234567123456712345671234567123456712345671234567); 2311 defer b.deinit(); 2312 var r = try Managed.init(testing.allocator); 2313 defer r.deinit(); 2314 2315 try r.gcd(a, b); 2316 2317 const answer = (try r.to(u256)); 2318 try testing.expect(answer == 0xf000000ff00000fff0000ffff000fffff00ffffff1); 2319} 2320 2321test "big.int gcd one large" { 2322 var a = try Managed.initSet(testing.allocator, 1897056385327307); 2323 defer a.deinit(); 2324 var b = try Managed.initSet(testing.allocator, 2251799813685248); 2325 defer b.deinit(); 2326 var r = try Managed.init(testing.allocator); 2327 defer r.deinit(); 2328 2329 try r.gcd(a, b); 2330 2331 try testing.expect((try r.to(u64)) == 1); 2332} 2333 2334test "big.int mutable to managed" { 2335 const allocator = testing.allocator; 2336 var limbs_buf = try allocator.alloc(Limb, 8); 2337 defer allocator.free(limbs_buf); 2338 2339 var a = Mutable.init(limbs_buf, 0xdeadbeef); 2340 var a_managed = a.toManaged(allocator); 2341 2342 try testing.expect(a.toConst().eq(a_managed.toConst())); 2343} 2344 2345test "big.int const to managed" { 2346 var a = try Managed.initSet(testing.allocator, 123423453456); 2347 defer a.deinit(); 2348 2349 var b = try a.toConst().toManaged(testing.allocator); 2350 defer b.deinit(); 2351 2352 try testing.expect(a.toConst().eq(b.toConst())); 2353} 2354 2355test "big.int pow" { 2356 { 2357 var a = try Managed.initSet(testing.allocator, -3); 2358 defer a.deinit(); 2359 2360 try a.pow(a.toConst(), 3); 2361 try testing.expectEqual(@as(i32, -27), try a.to(i32)); 2362 2363 try a.pow(a.toConst(), 4); 2364 try testing.expectEqual(@as(i32, 531441), try a.to(i32)); 2365 } 2366 { 2367 var a = try Managed.initSet(testing.allocator, 10); 2368 defer a.deinit(); 2369 2370 var y = try Managed.init(testing.allocator); 2371 defer y.deinit(); 2372 2373 // y and a are not aliased 2374 try y.pow(a.toConst(), 123); 2375 // y and a are aliased 2376 try a.pow(a.toConst(), 123); 2377 2378 try testing.expect(a.eq(y)); 2379 2380 const ys = try y.toString(testing.allocator, 16, .lower); 2381 defer testing.allocator.free(ys); 2382 try testing.expectEqualSlices( 2383 u8, 2384 "183425a5f872f126e00a5ad62c839075cd6846c6fb0230887c7ad7a9dc530fcb" ++ 2385 "4933f60e8000000000000000000000000000000", 2386 ys, 2387 ); 2388 } 2389 // Special cases 2390 { 2391 var a = try Managed.initSet(testing.allocator, 0); 2392 defer a.deinit(); 2393 2394 try a.pow(a.toConst(), 100); 2395 try testing.expectEqual(@as(i32, 0), try a.to(i32)); 2396 2397 try a.set(1); 2398 try a.pow(a.toConst(), 0); 2399 try testing.expectEqual(@as(i32, 1), try a.to(i32)); 2400 try a.pow(a.toConst(), 100); 2401 try testing.expectEqual(@as(i32, 1), try a.to(i32)); 2402 try a.set(-1); 2403 try a.pow(a.toConst(), 15); 2404 try testing.expectEqual(@as(i32, -1), try a.to(i32)); 2405 try a.pow(a.toConst(), 16); 2406 try testing.expectEqual(@as(i32, 1), try a.to(i32)); 2407 } 2408} 2409 2410test "big.int regression test for 1 limb overflow with alias" { 2411 // Note these happen to be two consecutive Fibonacci sequence numbers, the 2412 // first two whose sum exceeds 2**64. 2413 var a = try Managed.initSet(testing.allocator, 7540113804746346429); 2414 defer a.deinit(); 2415 var b = try Managed.initSet(testing.allocator, 12200160415121876738); 2416 defer b.deinit(); 2417 2418 try a.ensureAddCapacity(a.toConst(), b.toConst()); 2419 try a.add(a.toConst(), b.toConst()); 2420 2421 try testing.expect(a.toConst().orderAgainstScalar(19740274219868223167) == .eq); 2422} 2423 2424test "big.int regression test for realloc with alias" { 2425 // Note these happen to be two consecutive Fibonacci sequence numbers, the 2426 // second of which is the first such number to exceed 2**192. 2427 var a = try Managed.initSet(testing.allocator, 5611500259351924431073312796924978741056961814867751431689); 2428 defer a.deinit(); 2429 var b = try Managed.initSet(testing.allocator, 9079598147510263717870894449029933369491131786514446266146); 2430 defer b.deinit(); 2431 2432 try a.ensureAddCapacity(a.toConst(), b.toConst()); 2433 try a.add(a.toConst(), b.toConst()); 2434 2435 try testing.expect(a.toConst().orderAgainstScalar(14691098406862188148944207245954912110548093601382197697835) == .eq); 2436} 2437 2438test "big int popcount" { 2439 var a = try Managed.initSet(testing.allocator, -1); 2440 defer a.deinit(); 2441 var b = try Managed.initSet(testing.allocator, -1); 2442 defer b.deinit(); 2443 2444 try a.popCount(b.toConst(), 16); 2445 2446 try testing.expect(a.toConst().orderAgainstScalar(16) == .eq); 2447} 2448