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 }