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 }