1 // Written in the D programming language 2 /** 3 * Implements a signed 128 bit integer type. 4 * 5 Author: Walter Bright 6 Copyright: Copyright (c) 2022, D Language Foundation 7 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0) 8 Source: $(PHOBOSSRC std/int128.d) 9 */ 10 module std.int128; 11 12 private import core.int128; 13 14 15 /*********************************** 16 * 128 bit signed integer type. 17 */ 18 19 public struct Int128 20 { 21 @safe pure nothrow @nogc 22 { 23 Cent data; /// core.int128.Cent 24 25 /**************** 26 * Construct an `Int128` from a `long` value. 27 * The upper 64 bits are formed by sign extension. 28 * Params: 29 * lo = signed lower 64 bits 30 */ 31 this(long lo) 32 { 33 data.lo = lo; 34 data.hi = lo < 0 ? ~0L : 0; 35 } 36 37 /**************** 38 * Construct an `Int128` from a `ulong` value. 39 * The upper 64 bits are set to zero. 40 * Params: 41 * lo = unsigned lower 64 bits 42 */ 43 this(ulong lo) 44 { 45 data.lo = lo; 46 data.hi = 0; 47 } 48 49 /**************** 50 * Construct an `Int128` from a `long` value. 51 * Params: 52 * hi = upper 64 bits 53 * lo = lower 64 bits 54 */ 55 this(long hi, long lo) 56 { 57 data.hi = hi; 58 data.lo = lo; 59 } 60 61 /******************** 62 * Construct an `Int128` from a `Cent`. 63 * Params: 64 * data = Cent data 65 */ 66 this(Cent data) 67 { 68 this.data = data; 69 } 70 71 /******************** 72 * Returns: hash value for Int128 73 */ 74 size_t toHash() const 75 { 76 return cast(size_t)((data.lo & 0xFFFF_FFFF) + (data.hi & 0xFFFF_FFFF) + (data.lo >> 32) + (data.hi >> 32)); 77 } 78 79 /************************ 80 * Compare for equality 81 * Params: lo = signed value to compare with 82 * Returns: true if Int128 equals value 83 */ 84 bool opEquals(long lo) const 85 { 86 return data.lo == lo && data.hi == (lo >> 63); 87 } 88 89 /************************ 90 * Compare for equality 91 * Params: lo = unsigned value to compare with 92 * Returns: true if Int128 equals value 93 */ 94 bool opEquals(ulong lo) const 95 { 96 return data.hi == 0 && data.lo == lo; 97 } 98 99 /************************ 100 * Compare for equality 101 * Params: op2 = value to compare with 102 * Returns: true if Int128 equals value 103 */ 104 bool opEquals(Int128 op2) const 105 { 106 return data.hi == op2.data.hi && data.lo == op2.data.lo; 107 } 108 109 /** Support unary arithmentic operator + 110 * Params: op = "+" 111 * Returns: lvalue of result 112 */ 113 Int128 opUnary(string op)() const 114 if (op == "+") 115 { 116 return this; 117 } 118 119 /** Support unary arithmentic operator - ~ 120 * Params: op = "-", "~" 121 * Returns: lvalue of result 122 */ 123 Int128 opUnary(string op)() const 124 if (op == "-" || op == "~") 125 { 126 static if (op == "-") 127 return Int128(neg(this.data)); 128 else static if (op == "~") 129 return Int128(com(this.data)); 130 } 131 132 /** Support unary arithmentic operator ++ -- 133 * Params: op = "++", "--" 134 * Returns: lvalue of result 135 */ 136 Int128 opUnary(string op)() 137 if (op == "++" || op == "--") 138 { 139 static if (op == "++") 140 this.data = inc(this.data); 141 else static if (op == "--") 142 this.data = dec(this.data); 143 else 144 static assert(0, op); 145 return this; 146 } 147 148 /** Support casting to a bool 149 * Params: T = bool 150 * Returns: true if value is not zero 151 */ 152 bool opCast(T : bool)() const 153 { 154 return tst(this.data); 155 } 156 } // @safe pure nothrow @nogc 157 158 /** Support casting to an integral type 159 * Params: T = integral type 160 * Returns: low bits of value reinterpreted as T 161 */ 162 T opCast(T : long)() const 163 if (is(byte : T)) 164 { 165 return cast(T) this.data.lo; 166 } 167 168 /// 169 @safe unittest 170 { 171 const Int128 a = Int128(0xffff_ffff_ffff_ffffL, 0x0123_4567_89ab_cdefL); 172 assert(cast(long) a == 0x0123_4567_89ab_cdefL); 173 assert(cast(int) a == 0x89ab_cdef); 174 assert(cast(byte) a == cast(byte) 0xef); 175 } 176 177 /** Support casting to floating point type 178 * Params: T = floating point type 179 * Returns: value cast to floating point with environment-dependent 180 * rounding if the value is not exactly representable 181 */ 182 T opCast(T : real)() const 183 { 184 import core.math : ldexp; 185 if (cast(long) this.data.hi >= 0) 186 return ldexp(cast(T) this.data.hi, 64) + this.data.lo; 187 else 188 { 189 const absData = neg(this.data); 190 return -ldexp(cast(T) absData.hi, 64) - absData.lo; 191 } 192 } 193 194 /// 195 @safe unittest 196 { 197 const Int128 a = Int128(-1L << 60); 198 assert(cast(double) a == -(2.0 ^^ 60)); 199 assert(cast(double) (a * a) == 2.0 ^^ 120); 200 } 201 202 /** Support binary arithmetic operators + - * / % & | ^ << >> >>> 203 * Params: 204 * op = one of the arithmetic binary operators 205 * op2 = second operand 206 * Returns: value after the operation is applied 207 */ 208 Int128 opBinary(string op)(Int128 op2) const 209 if (op == "+" || op == "-" || 210 op == "*" || op == "/" || op == "%" || 211 op == "&" || op == "|" || op == "^") 212 { 213 static if (op == "+") 214 return Int128(add(this.data, op2.data)); 215 else static if (op == "-") 216 return Int128(sub(this.data, op2.data)); 217 else static if (op == "*") 218 return Int128(mul(this.data, op2.data)); 219 else static if (op == "/") 220 return Int128(div(this.data, op2.data)); 221 else static if (op == "%") 222 { 223 Cent modulus; 224 divmod(this.data, op2.data, modulus); 225 return Int128(modulus); 226 } 227 else static if (op == "&") 228 return Int128(and(this.data, op2.data)); 229 else static if (op == "|") 230 return Int128(or(this.data, op2.data)); 231 else static if (op == "^") 232 return Int128(xor(this.data, op2.data)); 233 else 234 static assert(0, "wrong op value"); 235 } 236 237 /// ditto 238 Int128 opBinary(string op, Int)(const Int op2) const 239 if ((op == "+" || op == "-" || 240 op == "*" || op == "/" || op == "%" || 241 op == "&" || op == "|" || op == "^") && 242 is(Int : long) && __traits(isIntegral, Int)) 243 { 244 static if (__traits(isUnsigned, Int)) 245 return mixin("this " ~ op ~ " Int128(0, op2)"); 246 else 247 return mixin("this " ~ op ~ " Int128((cast(long) op2) >> 63 , op2)"); 248 } 249 250 /// ditto 251 Int128 opBinary(string op, IntLike)(auto ref IntLike op2) const 252 if ((op == "+" || op == "-" || 253 op == "*" || op == "/" || op == "%" || 254 op == "&" || op == "|" || op == "^") && 255 is(IntLike : long) && !__traits(isIntegral, IntLike)) 256 { 257 return opBinary!(op)(__traits(getMember, op2, __traits(getAliasThis, IntLike)[0])); 258 } 259 260 /// ditto 261 Int128 opBinaryRight(string op, Int)(const Int op2) const 262 if ((op == "+" || op == "-" || 263 op == "*" || op == "/" || op == "%" || 264 op == "&" || op == "|" || op == "^") && 265 is(Int : long) && __traits(isIntegral, Int)) 266 { 267 static if (__traits(isUnsigned, Int)) 268 mixin("return Int128(0, op2) " ~ op ~ " this;"); 269 else 270 mixin("return Int128((cast(long) op2) >> 63, op2) " ~ op ~ " this;"); 271 } 272 273 /// ditto 274 Int128 opBinaryRight(string op, IntLike)(auto ref IntLike op2) const 275 if ((op == "+" || op == "-" || 276 op == "*" || op == "/" || op == "%" || 277 op == "&" || op == "|" || op == "^") && 278 is(IntLike : long) && !__traits(isIntegral, IntLike)) 279 { 280 return opBinaryRight!(op)(__traits(getMember, op2, __traits(getAliasThis, IntLike)[0])); 281 } 282 283 /// ditto 284 Int128 opBinary(string op)(long op2) const 285 if (op == "<<") 286 { 287 return Int128(shl(this.data, cast(uint) op2)); 288 } 289 290 /// ditto 291 Int128 opBinary(string op)(long op2) const 292 if (op == ">>") 293 { 294 return Int128(sar(this.data, cast(uint) op2)); 295 } 296 297 /// ditto 298 Int128 opBinary(string op)(long op2) const 299 if (op == ">>>") 300 { 301 return Int128(shr(this.data, cast(uint) op2)); 302 } 303 304 /** arithmetic assignment operators += -= *= /= %= &= |= ^= <<= >>= >>>= 305 * Params: op = one of +, -, etc. 306 * op2 = second operand 307 * Returns: lvalue of updated left operand 308 */ 309 ref Int128 opOpAssign(string op)(Int128 op2) 310 if (op == "+" || op == "-" || 311 op == "*" || op == "/" || op == "%" || 312 op == "&" || op == "|" || op == "^" || 313 op == "<<" || op == ">>" || op == ">>>") 314 { 315 mixin("this = this " ~ op ~ " op2;"); 316 return this; 317 } 318 319 /// ditto 320 ref Int128 opOpAssign(string op, Int)(auto ref Int op2) 321 if ((op == "+" || op == "-" || 322 op == "*" || op == "/" || op == "%" || 323 op == "&" || op == "|" || op == "^" || 324 op == "<<" || op == ">>" || op == ">>>") 325 && is(Int : long)) 326 { 327 mixin("this = this " ~ op ~ " op2;"); 328 return this; 329 } 330 331 /** support arithmentic comparison operators < <= > >= 332 * Params: op2 = right hand operand 333 * Returns: -1 for less than, 0 for equals, 1 for greater than 334 */ 335 int opCmp(Int128 op2) const @nogc nothrow pure @safe 336 { 337 return this == op2 ? 0 : gt(this.data, op2.data) * 2 - 1; 338 } 339 340 /// ditto 341 int opCmp(Int)(const Int op2) const @nogc nothrow pure @safe 342 if (is(Int : long) && __traits(isIntegral, Int)) 343 { 344 static if (__traits(isUnsigned, Int)) 345 return opCmp(Int128(0, op2)); 346 else 347 return opCmp(Int128((cast(long) op2) >> 63, op2)); 348 } 349 350 /// ditto 351 int opCmp(IntLike)(auto ref IntLike op2) const 352 if (is(IntLike : long) && !__traits(isIntegral, IntLike)) 353 { 354 return opCmp(__traits(getMember, op2, __traits(getAliasThis, IntLike)[0])); 355 } 356 357 /** 358 * Formats `Int128` with either `%d`, `%x`, `%X`, or `%s` (same as `%d`). 359 * 360 * Params: 361 * sink = $(REF_ALTTEXT Output range, isOutputRange, std, range, primitives) 362 * to write to. 363 * fmt = A $(REF FormatSpec, std,format) which controls how the number 364 * is displayed. 365 * 366 * Throws: 367 * $(REF FormatException, std,format) if the format specifier is 368 * not one of 'd', 'x', 'X', 's'. 369 * 370 * See_Also: $(REF formatValue, std,format) 371 */ 372 void toString(Writer, FormatSpec)(scope ref Writer sink, scope const ref FormatSpec fmt) const 373 { 374 import std.range.primitives : put; 375 import std.format : FormatException, Fmt = FormatSpec; 376 377 static if (is(FormatSpec == Fmt!Char, Char)) 378 { 379 // Puts "Char" into scope if the pattern matches. 380 } 381 static assert(is(Char), 382 "Expecting `FormatSpec` to be instantiation of `std.format.FormatSpec`"); 383 384 Char[39] buf = void; 385 size_t bufStart = void; 386 Char signChar = 0; 387 if (fmt.spec == 'd' || fmt.spec == 's') 388 { 389 const bool isNeg = 0 > cast(long) this.data.hi; 390 Cent val = isNeg ? neg(this.data) : this.data; 391 immutable Cent radix = { lo: 10, hi: 0 }; 392 Cent modulus; 393 bufStart = buf.length; 394 do 395 { 396 uint x = void; 397 if (ugt(radix, val)) 398 { 399 x = cast(uint) val.lo; 400 val = Cent(0, 0); 401 } 402 else 403 { 404 val = udivmod(val, radix, modulus); 405 x = cast(uint) modulus.lo; 406 } 407 buf[--bufStart] = cast(Char) ('0' + x); 408 } while (tst(val)); 409 if (isNeg) 410 signChar = '-'; 411 else if (fmt.flPlus) 412 signChar = '+'; 413 else if (fmt.flSpace) 414 signChar = ' '; 415 } 416 else if (fmt.spec == 'x' || fmt.spec == 'X') 417 { 418 immutable hexDigits = fmt.spec == 'X' ? "0123456789ABCDEF" : "0123456789abcdef"; 419 ulong a = data.lo; 420 bufStart = buf.length - 1; 421 size_t penPos = buf.length - 1; 422 do 423 { 424 if ((buf[penPos] = hexDigits[0xF & cast(uint) a]) != '0') 425 bufStart = penPos; 426 a >>>= 4; 427 } while (--penPos >= buf.length - 16); 428 a = data.hi; 429 do 430 { 431 if ((buf[penPos] = hexDigits[0xF & cast(uint) a]) != '0') 432 bufStart = penPos; 433 a >>>= 4; 434 } while (--penPos >= buf.length - 32); 435 } 436 else 437 { 438 throw new FormatException("Format specifier not understood: %" ~ fmt.spec); 439 } 440 441 const minw = (buf.length - bufStart) + int(signChar != 0); 442 const maxw = minw < fmt.width ? fmt.width : minw; 443 const difw = maxw - minw; 444 445 static void putRepeatedChars(Char c)(scope ref Writer sink, size_t n) 446 { 447 static immutable Char[8] array = [c, c, c, c, c, c, c, c]; 448 foreach (_; 0 .. n / 8) 449 put(sink, array[0 .. 8]); 450 if (n & 7) 451 put(sink, array[0 .. n & 7]); 452 } 453 454 if (!fmt.flDash && !fmt.flZero && difw) 455 putRepeatedChars!' '(sink, difw); 456 457 if (signChar) 458 { 459 Char[1] signCharBuf = signChar; 460 put(sink, signCharBuf[0 .. 1]); 461 } 462 463 if (!fmt.flDash && fmt.flZero && difw) 464 putRepeatedChars!'0'(sink, difw); 465 466 put(sink, buf[bufStart .. $]); 467 468 if (fmt.flDash && difw) 469 putRepeatedChars!' '(sink, difw); 470 } 471 472 /** 473 `toString` is rarely directly invoked; the usual way of using it is via 474 $(REF format, std, format): 475 */ 476 @safe unittest 477 { 478 import std.format : format; 479 480 assert(format("%s", Int128.max) == "170141183460469231731687303715884105727"); 481 assert(format("%s", Int128.min) == "-170141183460469231731687303715884105728"); 482 assert(format("%x", Int128.max) == "7fffffffffffffffffffffffffffffff"); 483 assert(format("%X", Int128.max) == "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"); 484 assert(format("%032X", Int128(123L)) == "0000000000000000000000000000007B"); 485 assert(format("%+ 40d", Int128(123L)) == " +123"); 486 assert(format("%+-40d", Int128(123L)) == "+123 "); 487 } 488 489 /// Also can format as `wchar` or `dchar`. 490 @safe unittest 491 { 492 import std.conv : to; 493 494 assert(to!wstring(Int128.max) == "170141183460469231731687303715884105727"w); 495 assert(to!dstring(Int128.max) == "170141183460469231731687303715884105727"d); 496 } 497 498 enum min = Int128(long.min, 0); /// minimum value 499 enum max = Int128(long.max, ulong.max); /// maximum value 500 } 501 502 /********************************************* Tests ************************************/ 503 504 version (unittest) 505 { 506 import core.stdc.stdio; 507 508 @trusted void print(Int128 c) 509 { 510 printf("%lld, %lld\n", c.data.hi, c.data.lo); 511 } 512 513 @trusted void printx(Int128 c) 514 { 515 printf("%llx, %llx\n", c.data.hi, c.data.lo); 516 } 517 } 518 519 /// Int128 tests 520 @safe pure nothrow @nogc 521 unittest 522 { 523 Int128 c = Int128(5, 6); 524 assert(c == c); 525 assert(c == +c); 526 assert(c == - -c); 527 assert(~c == Int128(~5, ~6)); 528 ++c; 529 assert(c == Int128(5, 7)); 530 assert(--c == Int128(5, 6)); 531 assert(!!c); 532 assert(!Int128()); 533 534 assert(c + Int128(10, 20) == Int128(15, 26)); 535 assert(c - Int128(1, 2) == Int128(4, 4)); 536 assert(c * Int128(100, 2) == Int128(610, 12)); 537 assert(c / Int128(3, 2) == Int128(0, 1)); 538 assert(c % Int128(3, 2) == Int128(2, 4)); 539 assert((c & Int128(3, 2)) == Int128(1, 2)); 540 assert((c | Int128(3, 2)) == Int128(7, 6)); 541 assert((c ^ Int128(3, 2)) == Int128(6, 4)); 542 543 assert(c + 15 == Int128(5, 21)); 544 assert(c - 15 == Int128(4, -9)); 545 assert(c * 15 == Int128(75, 90)); 546 assert(c / 15 == Int128(0, 6148914691236517205)); 547 assert(c % 15 == Int128(0, 11)); 548 assert((c & 15) == Int128(0, 6)); 549 assert((c | 15) == Int128(5, 15)); 550 assert((c ^ 15) == Int128(5, 9)); 551 552 assert(15 + c == Int128(5, 21)); 553 assert(15 - c == Int128(-5, 9)); 554 assert(15 * c == Int128(75, 90)); 555 assert(15 / c == Int128(0, 0)); 556 assert(15 % c == Int128(0, 15)); 557 assert((15 & c) == Int128(0, 6)); 558 assert((15 | c) == Int128(5, 15)); 559 assert((15 ^ c) == Int128(5, 9)); 560 561 assert(c << 1 == Int128(10, 12)); 562 assert(-c >> 1 == Int128(-3, 9223372036854775805)); 563 assert(-c >>> 1 == Int128(9223372036854775805, 9223372036854775805)); 564 565 assert((c += 1) == Int128(5, 7)); 566 assert((c -= 1) == Int128(5, 6)); 567 assert((c += Int128(0, 1)) == Int128(5, 7)); 568 assert((c -= Int128(0, 1)) == Int128(5, 6)); 569 assert((c *= 2) == Int128(10, 12)); 570 assert((c /= 2) == Int128(5, 6)); 571 assert((c %= 2) == Int128()); 572 c += Int128(5, 6); 573 assert((c *= Int128(10, 20)) == Int128(160, 120)); 574 assert((c /= Int128(10, 20)) == Int128(0, 15)); 575 c += Int128(72, 0); 576 assert((c %= Int128(10, 20)) == Int128(1, -125)); 577 assert((c &= Int128(3, 20)) == Int128(1, 0)); 578 assert((c |= Int128(8, 2)) == Int128(9, 2)); 579 assert((c ^= Int128(8, 2)) == Int128(1, 0)); 580 c |= Int128(10, 5); 581 assert((c <<= 1) == Int128(11 * 2, 5 * 2)); 582 assert((c >>>= 1) == Int128(11, 5)); 583 c = Int128(long.min, long.min); 584 assert((c >>= 1) == Int128(long.min >> 1, cast(ulong) long.min >> 1)); 585 586 assert(-Int128.min == Int128.min); 587 assert(Int128.max + 1 == Int128.min); 588 589 c = Int128(5, 6); 590 assert(c < Int128(6, 5)); 591 assert(c > 10); 592 593 c = Int128(-1UL); 594 assert(c == -1UL); 595 c = Int128(-1L); 596 assert(c == -1L); 597 } 598 599 @system unittest 600 { 601 alias Seq(T...) = T; 602 Int128 c = Int128(-1L); 603 assert(c.opCmp(-1L) == 0); 604 // To avoid regression calling opCmp with any integral type needs to 605 // work without the compiler complaining "opCmp called with argument 606 // X matches both <...>". 607 static foreach (Int; Seq!(long, int, short, byte, ulong, uint, ushort, ubyte, dchar, wchar, char)) 608 assert(c < Int.max); 609 static foreach (Int; Seq!(int, short, byte)) 610 assert(c.opCmp(Int(-1)) == 0); 611 assert(c < true); 612 // To avoid regression calling opCmp with any type that converts to an 613 // integral type through alias this needs to work regardless of whether 614 // the alias is safe/pure/nothrow/nogc and regardless of whether the 615 // type has a disabled postblit. 616 static struct Wrapped(T) 617 { 618 T value; 619 uint count; 620 T get() @system { ++count; return value; } // not const 621 alias get this; 622 @disable this(this); // no implicit copies 623 } 624 assert(c.opCmp(Wrapped!long(-1)) == 0); 625 auto w = Wrapped!ulong(ulong.max); 626 w.count++; // avoid invalid D-Scanner message that w could have been declared const 627 assert(c < w); 628 629 const zero = Int128(0L); 630 const one = Int128(1L); 631 const neg_one = Int128(-1L); 632 const neg_two = Int128(-2L); 633 // Correct result with ulong.max: 634 assert(zero + ulong.max == ulong.max); 635 assert(one * ulong.max == ulong.max); 636 assert((neg_one & ulong.max) == ulong.max); 637 assert((zero | ulong.max) == ulong.max); 638 assert((zero ^ ulong.max) == ulong.max); 639 // Correct result with negative arguments: 640 assert(zero + -1L == -1L); 641 assert(neg_two * -3L == 6L); 642 assert(neg_two / -2L == 1L); 643 assert(neg_two % -2L == 0L); 644 assert((neg_one & -1L) == -1L); 645 assert((zero | -1L) == -1L); 646 assert((zero ^ -1L) == -1L); 647 // Ensure alias this still works. 648 { 649 Int128 a = zero; 650 assert((a ^= w) == ulong.max); 651 } 652 assert((Wrapped!long(-1L) + zero) == -1L); 653 }