1 /**
2   Provide a 2^N-bit integer type.
3   Guaranteed to never allocate and expected binary layout
4   Recursive implementation with very slow division.
5 
6   <b>Supports all operations that builtin integers support.</b>
7 
8   Bugs: it's not sure if the unsigned operand would take precedence in a comparison/division.
9           - a < b should be an unsigned comparison if at least one operand is unsigned
10           - a / b should be an unsigned division   if at least one operand is unsigned
11  */
12 module gfm.integers.wideint;
13 
14 import std.traits,
15        std.ascii;
16 import std.format : FormatSpec;
17 
18 /// Wide signed integer.
19 /// Params:
20 ///    bits = number of bits, must be a power of 2.
21 template wideint(int bits)
22 {
23     alias integer!(true, bits) wideint;
24 }
25 
26 /// Wide unsigned integer.
27 /// Params:
28 ///    bits = number of bits, must be a power of 2.
29 template uwideint(int bits)
30 {
31     alias integer!(false, bits) uwideint;
32 }
33 
34 // Some predefined integers (any power of 2 greater than 128 would work)
35 
36 alias wideint!128 int128; // cent and ucent!
37 alias uwideint!128 uint128;
38 
39 alias wideint!256 int256;
40 alias uwideint!256 uint256;
41 
42 /// Use this template to get an arbitrary sized integer type.
43 private template integer(bool signed, int bits)
44     if ((bits & (bits - 1)) == 0)
45 {
46 
47     // forward to native type for lower numbers of bits
48     static if (bits == 8)
49     {
50         static if (signed)
51             alias byte integer;
52         else
53             alias ubyte integer;
54     }
55     else static if (bits == 16)
56     {
57         static if (signed)
58             alias short integer;
59         else
60             alias ushort integer;
61     }
62     else static if (bits == 32)
63     {
64         static if (signed)
65             alias int integer;
66         else
67             alias uint integer;
68     }
69     else static if (bits == 64)
70     {
71         static if (signed)
72             alias long integer;
73         else
74             alias ulong integer;
75     }
76     else
77     {
78         alias wideIntImpl!(signed, bits) integer;
79     }
80 }
81 
82 private template integer(bool signed, int bits)
83     if ((bits & (bits - 1)) != 0)
84 {
85     static assert(0, "wide integer bits must be a power of 2");
86 }
87 
88 /// Recursive 2^n integer implementation.
89 struct wideIntImpl(bool signed, int bits)
90 {
91     static assert(bits >= 128);
92     private
93     {
94         alias wideIntImpl self;
95 
96         template isSelf(T)
97         {
98             enum bool isSelf = is(Unqual!T == self);
99         }
100 
101         alias integer!(true, bits/2) sub_int_t;   // signed bits/2 integer
102         alias integer!(false, bits/2) sub_uint_t; // unsigned bits/2 integer
103 
104         alias integer!(true, bits/4) sub_sub_int_t;   // signed bits/4 integer
105         alias integer!(false, bits/4) sub_sub_uint_t; // unsigned bits/4 integer
106 
107         static if(signed)
108             alias sub_int_t hi_t; // hi_t has same signedness as the whole struct
109         else
110             alias sub_uint_t hi_t;
111 
112         alias sub_uint_t low_t;   // low_t is always unsigned
113 
114         enum _bits = bits,
115              _signed = signed;
116     }
117 
118     /// Construct from a value.
119     @nogc this(T)(T x) pure nothrow
120     {
121         opAssign!T(x);
122     }
123 
124     // Private functions used by the `literal` template.
125     private static bool isValidDigitString(string digits)
126     {
127         import std.algorithm : startsWith;
128         import std.ascii : isDigit;
129 
130         if (digits.startsWith("0x"))
131         {
132             foreach (d; digits[2 .. $])
133             {
134                 if (!isHexDigit(d) && d != '_')
135                     return false;
136             }
137         }
138         else // decimal
139         {
140             static if (signed)
141                 if (digits.startsWith("-"))
142                     digits = digits[1 .. $];
143             if (digits.length < 1)
144                 return false;   // at least 1 digit required
145             foreach (d; digits)
146             {
147                 if (!isDigit(d) && d != '_')
148                     return false;
149             }
150         }
151         return true;
152     }
153 
154     private static typeof(this) literalImpl(string digits)
155     {
156         import std.algorithm : startsWith;
157         import std.ascii : isDigit;
158 
159         typeof(this) value = 0;
160         if (digits.startsWith("0x"))
161         {
162             foreach (d; digits[2 .. $])
163             {
164                 if (d == '_')
165                     continue;
166                 value <<= 4;
167                 if (isDigit(d))
168                     value += d - '0';
169                 else
170                     value += 10 + toUpper(d) - 'A';
171             }
172         }
173         else
174         {
175             static if (signed)
176             {
177                 bool negative = false;
178                 if (digits.startsWith("-"))
179                 {
180                     negative = true;
181                     digits = digits[1 .. $];
182                 }
183             }
184             foreach (d; digits)
185             {
186                 if (d == '_')
187                     continue;
188                 value *= 10;
189                 value += d - '0';
190             }
191             static if (signed)
192                 if (negative)
193                     value = -value;
194         }
195         return value;
196     }
197 
198     /// Construct from compile-time digit string.
199     ///
200     /// Both decimal and hex digit strings are supported.
201     ///
202     /// Example:
203     /// ----
204     /// auto x = int128.literal!"20_000_000_000_000_000_001";
205     /// assert((x >>> 1) == 0x8AC7_2304_89E8_0000);
206     ///
207     /// auto y = int126.literal!"0x1_158E_4609_13D0_0001";
208     /// assert(y == x);
209     /// ----
210     template literal(string digits)
211     {
212         static assert(isValidDigitString(digits),
213                       "invalid digits in literal: " ~ digits);
214         enum literal = literalImpl(digits);
215     }
216 
217     /// Assign with a smaller unsigned type.
218     @nogc ref self opAssign(T)(T n) pure nothrow if (isIntegral!T && isUnsigned!T)
219     {
220         hi = 0;
221         lo = n;
222         return this;
223     }
224 
225     /// Assign with a smaller signed type (sign is extended).
226     @nogc ref self opAssign(T)(T n) pure nothrow if (isIntegral!T && isSigned!T)
227     {
228         // shorter int always gets sign-extended,
229         // regardless of the larger int being signed or not
230         hi = (n < 0) ? cast(hi_t)(-1) : cast(hi_t)0;
231 
232         // will also sign extend as well if needed
233         lo = cast(sub_int_t)n;
234         return this;
235     }
236 
237     /// Assign with a wide integer of the same size (sign is lost).
238     @nogc ref self opAssign(T)(T n) pure nothrow if (isWideIntInstantiation!T && T._bits == bits)
239     {
240         hi = n.hi;
241         lo = n.lo;
242         return this;
243     }
244 
245     /// Assign with a smaller wide integer (sign is extended accordingly).
246     @nogc ref self opAssign(T)(T n) pure nothrow if (isWideIntInstantiation!T && T._bits < bits)
247     {
248         static if (T._signed)
249         {
250             // shorter int always gets sign-extended,
251             // regardless of the larger int being signed or not
252             hi = cast(hi_t)((n < 0) ? -1 : 0);
253 
254             // will also sign extend as well if needed
255             lo = cast(sub_int_t)n;
256             return this;
257         }
258         else
259         {
260             hi = 0;
261             lo = n;
262             return this;
263         }
264     }
265 
266     /// Cast to a smaller integer type (truncation).
267     @nogc T opCast(T)() pure const nothrow if (isIntegral!T)
268     {
269         return cast(T)lo;
270     }
271 
272     /// Cast to bool.
273     @nogc T opCast(T)() pure const nothrow if (is(T == bool))
274     {
275         return this != 0;
276     }
277 
278     /// Cast to wide integer of any size.
279     @nogc T opCast(T)() pure const nothrow if (isWideIntInstantiation!T)
280     {
281         static if (T._bits < bits)
282             return cast(T)lo;
283         else
284             return T(this);
285     }
286 
287     /// Converts to a string. Supports format specifiers %d, %s (both decimal)
288     /// and %x (hex).
289     void toString(DG, Char)(DG sink, FormatSpec!Char fmt) const
290         if (is(typeof(sink((const(Char)[]).init))))
291     {
292         if (fmt.spec == 'x')
293         {
294             if (this == 0)
295             {
296                 sink("0");
297                 return;
298             }
299 
300             enum maxDigits = bits / 4;
301             Char[maxDigits] buf;
302             wideIntImpl tmp = this;
303             size_t i;
304 
305             for (i = maxDigits-1; tmp != 0 && i < buf.length; i--)
306             {
307                 buf[i] = hexDigits[cast(int)tmp & 0b00001111];
308                 tmp >>= 4;
309             }
310             assert(i+1 < buf.length);
311             sink(buf[i+1 .. $]);
312         }
313         else // default to decimal
314         {
315             import std.algorithm : reverse;
316 
317             if (this == 0)
318             {
319                 sink("0");
320                 return;
321             }
322 
323             // The maximum number of decimal digits is basically
324             // ceil(log_10(2^^bits - 1)), which is slightly below
325             // ceil(bits * log(2)/log(10)). The value 0.30103 is a slight
326             // overestimate of log(2)/log(10), to be sure we never
327             // underestimate. We add 1 to account for rounding up.
328             enum maxDigits = cast(ulong)(0.30103 * bits) + 1;
329             Char[maxDigits] buf;
330             size_t i;
331             self q = void, r = void;
332 
333             wideIntImpl tmp = this;
334             if (tmp < 0)
335             {
336                 sink("-");
337                 tmp = -tmp;
338             }
339             for (i = maxDigits-1; tmp > 0; i--)
340             {
341                 assert(i < buf.length);
342                 static if (signed)
343                     Internals!bits.signedDivide(tmp, self.literal!"10", q, r);
344                 else
345                     Internals!bits.unsignedDivide(tmp, self.literal!"10", q, r);
346 
347                 buf[i] = digits[cast(int)(r)];
348                 tmp = q;
349             }
350             assert(i+1 < buf.length);
351             sink(buf[i+1 .. $]);
352         }
353     }
354 
355     @nogc self opBinary(string op, T)(T o) pure const nothrow if (!isSelf!T)
356     {
357         self r = this;
358         self y = o;
359         return r.opOpAssign!(op)(y);
360     }
361 
362     @nogc self opBinary(string op, T)(T y) pure const nothrow if (isSelf!T)
363     {
364         self r = this; // copy
365         self o = y;
366         return r.opOpAssign!(op)(o);
367     }
368 
369     @nogc ref self opOpAssign(string op, T)(T y) pure nothrow if (!isSelf!T)
370     {
371         const(self) o = y;
372         return opOpAssign!(op)(o);
373     }
374 
375     @nogc ref self opOpAssign(string op, T)(T y) pure nothrow if (isSelf!T)
376     {
377         static if (op == "+")
378         {
379             hi += y.hi;
380             if (lo + y.lo < lo) // deal with overflow
381                 ++hi;
382             lo += y.lo;
383         }
384         else static if (op == "-")
385         {
386             opOpAssign!"+"(-y);
387         }
388         else static if (op == "<<")
389         {
390             if (y >= bits)
391             {
392                 hi = 0;
393                 lo = 0;
394             }
395             else if (y >= bits / 2)
396             {
397                 hi = lo << (y.lo - bits / 2);
398                 lo = 0;
399             }
400             else if (y > 0)
401             {
402                 hi = (lo >>> (-y.lo + bits / 2)) | (hi << y.lo);
403                 lo = lo << y.lo;
404             }
405         }
406         else static if (op == ">>" || op == ">>>")
407         {
408             assert(y >= 0);
409             static if (!signed || op == ">>>")
410                 immutable(sub_int_t) signFill = 0;
411             else
412                 immutable(sub_int_t) signFill = cast(sub_int_t)(isNegative() ? -1 : 0);
413 
414             if (y >= bits)
415             {
416                 hi = signFill;
417                 lo = signFill;
418             }
419             else if (y >= bits/2)
420             {
421                 lo = hi >> (y.lo - bits/2);
422                 hi = signFill;
423             }
424             else if (y > 0)
425             {
426                 lo = (hi << (-y.lo + bits/2)) | (lo >> y.lo);
427                 hi = hi >> y.lo;
428             }
429         }
430         else static if (op == "*")
431         {
432             sub_sub_uint_t[4] a = toParts();
433             sub_sub_uint_t[4] b = y.toParts();
434 
435             this = 0;
436             for(int i = 0; i < 4; ++i)
437                 for(int j = 0; j < 4 - i; ++j)
438                     this += self(cast(sub_uint_t)(a[i]) * b[j]) << ((bits/4) * (i + j));
439         }
440         else static if (op == "&")
441         {
442             hi &= y.hi;
443             lo &= y.lo;
444         }
445         else static if (op == "|")
446         {
447             hi |= y.hi;
448             lo |= y.lo;
449         }
450         else static if (op == "^")
451         {
452             hi ^= y.hi;
453             lo ^= y.lo;
454         }
455         else static if (op == "/" || op == "%")
456         {
457             self q = void, r = void;
458             static if(signed)
459                 Internals!bits.signedDivide(this, y, q, r);
460             else
461                 Internals!bits.unsignedDivide(this, y, q, r);
462             static if (op == "/")
463                 this = q;
464             else
465                 this = r;
466         }
467         else
468         {
469             static assert(false, "unsupported operation '" ~ op ~ "'");
470         }
471         return this;
472     }
473 
474     // const unary operations
475     @nogc self opUnary(string op)() pure const nothrow if (op == "+" || op == "-" || op == "~")
476     {
477         static if (op == "-")
478         {
479             self r = this;
480             r.not();
481             r.increment();
482             return r;
483         }
484         else static if (op == "+")
485            return this;
486         else static if (op == "~")
487         {
488             self r = this;
489             r.not();
490             return r;
491         }
492     }
493 
494     // non-const unary operations
495     @nogc self opUnary(string op)() pure nothrow if (op == "++" || op == "--")
496     {
497         static if (op == "++")
498             increment();
499         else static if (op == "--")
500             decrement();
501         return this;
502     }
503 
504     @nogc bool opEquals(T)(T y) pure const if (!isSelf!T)
505     {
506         return this == self(y);
507     }
508 
509     @nogc bool opEquals(T)(T y) pure const if (isSelf!T)
510     {
511        return lo == y.lo && y.hi == hi;
512     }
513 
514     @nogc int opCmp(T)(T y) pure const if (!isSelf!T)
515     {
516         return opCmp(self(y));
517     }
518 
519     @nogc int opCmp(T)(T y) pure const if (isSelf!T)
520     {
521         if (hi < y.hi) return -1;
522         if (hi > y.hi) return 1;
523         if (lo < y.lo) return -1;
524         if (lo > y.lo) return 1;
525         return 0;
526     }
527 
528     // binary layout should be what is expected on this platform
529     version (LittleEndian)
530     {
531         low_t lo;
532         hi_t hi;
533     }
534     else
535     {
536         hi_t hi;
537         low_t lo;
538     }
539 
540     private
541     {
542         static if (signed)
543         {
544             @nogc bool isNegative() pure nothrow const
545             {
546                 return signBit();
547             }
548         }
549         else
550         {
551             @nogc bool isNegative() pure nothrow const
552             {
553                 return false;
554             }
555         }
556 
557         @nogc void not() pure nothrow
558         {
559             hi = ~hi;
560             lo = ~lo;
561         }
562 
563         @nogc void increment() pure nothrow
564         {
565             ++lo;
566             if (lo == 0) ++hi;
567         }
568 
569         @nogc void decrement() pure nothrow
570         {
571             if (lo == 0) --hi;
572             --lo;
573         }
574 
575         @nogc bool signBit() pure const nothrow
576         {
577             enum SIGN_SHIFT = bits / 2 - 1;
578             return ((hi >> SIGN_SHIFT) & 1) != 0;
579         }
580 
581         @nogc sub_sub_uint_t[4] toParts() pure const nothrow
582         {
583             sub_sub_uint_t[4] p = void;
584             enum SHIFT = bits / 4;
585             immutable lomask = cast(sub_uint_t)(cast(sub_sub_int_t)(-1));
586             p[3] = cast(sub_sub_uint_t)(hi >> SHIFT);
587             p[2] = cast(sub_sub_uint_t)(hi & lomask);
588             p[1] = cast(sub_sub_uint_t)(lo >> SHIFT);
589             p[0] = cast(sub_sub_uint_t)(lo & lomask);
590             return p;
591         }
592     }
593 }
594 
595 template isWideIntInstantiation(U)
596 {
597     private static void isWideInt(bool signed, int bits)(wideIntImpl!(signed, bits) x)
598     {
599     }
600 
601     enum bool isWideIntInstantiation = is(typeof(isWideInt(U.init)));
602 }
603 
604 @nogc public wideIntImpl!(signed, bits) abs(bool signed, int bits)(wideIntImpl!(signed, bits) x) pure nothrow
605 {
606     if(x >= 0)
607         return x;
608     else
609         return -x;
610 }
611 
612 private struct Internals(int bits)
613 {
614     alias wideIntImpl!(true, bits) wint_t;
615     alias wideIntImpl!(false, bits) uwint_t;
616 
617     @nogc static void unsignedDivide(uwint_t dividend, uwint_t divisor,
618                                      out uwint_t quotient, out uwint_t remainder) pure nothrow
619     {
620         assert(divisor != 0);
621 
622         uwint_t rQuotient = 0;
623         uwint_t cDividend = dividend;
624 
625         while (divisor <= cDividend)
626         {
627             // find N so that (divisor << N) <= cDividend && cDividend < (divisor << (N + 1) )
628 
629             uwint_t N = 0;
630             uwint_t cDivisor = divisor;
631             while (cDividend > cDivisor)
632             {
633                 if (cDivisor.signBit())
634                     break;
635 
636                 if (cDividend < (cDivisor << 1))
637                     break;
638 
639                 cDivisor <<= 1;
640                 ++N;
641             }
642             cDividend = cDividend - cDivisor;
643             rQuotient += (uwint_t(1) << N);
644         }
645 
646         quotient = rQuotient;
647         remainder = cDividend;
648     }
649 
650     @nogc static void signedDivide(wint_t dividend, wint_t divisor,
651                                    out wint_t quotient, out wint_t remainder) pure nothrow
652     {
653         uwint_t q, r;
654         unsignedDivide(uwint_t(abs(dividend)), uwint_t(abs(divisor)), q, r);
655 
656         // remainder has same sign as the dividend
657         if (dividend < 0)
658             r = -r;
659 
660         // negate the quotient if opposite signs
661         if ((dividend >= 0) != (divisor >= 0))
662             q = -q;
663 
664         quotient = q;
665         remainder = r;
666 
667         assert(remainder == 0 || ((remainder < 0) == (dividend < 0)));
668     }
669 }
670 
671 // Verify that toString is callable from pure / nothrow / @nogc code as long as
672 // the callback also has these attributes.
673 pure nothrow @nogc unittest
674 {
675     int256 x = 123;
676     FormatSpec!char fspec;
677 
678     fspec.spec = 's';
679     x.toString((const(char)[]) {}, fspec);
680 
681     // Verify that wide strings actually work
682     FormatSpec!dchar dfspec;
683     dfspec.spec = 's';
684     x.toString((const(dchar)[] x) { assert(x == "123"); }, dfspec);
685 }
686 
687 unittest
688 {
689     import std..string : format;
690 
691     int128 x;
692     x.hi = 1;
693     x.lo = 0x158E_4609_13D0_0001;
694     assert(format("%s", x) == "20000000000000000001");
695     assert(format("%d", x) == "20000000000000000001");
696     assert(format("%x", x) == "1158E460913D00001");
697 
698     x.hi = 0xFFFF_FFFF_FFFF_FFFE;
699     x.lo = 0xEA71_B9F6_EC2F_FFFF;
700     assert(format("%d", x) == "-20000000000000000001");
701     assert(format("%x", x) == "FFFFFFFFFFFFFFFEEA71B9F6EC2FFFFF");
702 
703     x.hi = x.lo = 0;
704     assert(format("%d", x) == "0");
705 
706     x.hi = x.lo = 0xFFFF_FFFF_FFFF_FFFF;
707     assert(format("%d", x) == "-1"); // array index boundary condition
708 }
709 
710 unittest
711 {
712     long step = 164703072086692425;
713     for (long si = long.min; si <= long.max - step; si += step)
714     {
715         for (long sj = long.min; sj <= long.max - step; sj += step)
716         {
717             ulong ui = cast(ulong)si;
718             ulong uj = cast(ulong)sj;
719             int128 csi = si;
720             uint128 cui = si;
721             int128 csj = sj;
722             uint128 cuj = sj;
723             assert(csi == csi);
724             assert(~~csi == csi);
725             assert(-(-csi) == csi);
726             assert(++csi == si + 1);
727             assert(--csi == si);
728 
729             string testSigned(string op)
730             {
731                 return "assert(cast(ulong)(si" ~ op ~ "sj) == cast(ulong)(csi" ~ op ~ "csj));";
732             }
733 
734             string testMixed(string op)
735             {
736                 return "assert(cast(ulong)(ui" ~ op ~ "sj) == cast(ulong)(cui" ~ op ~ "csj));"
737                      ~ "assert(cast(ulong)(si" ~ op ~ "uj) == cast(ulong)(csi" ~ op ~ "cuj));";
738             }
739 
740             string testUnsigned(string op)
741             {
742                 return "assert(cast(ulong)(ui" ~ op ~ "uj) == cast(ulong)(cui" ~ op ~ "cuj));";
743             }
744 
745             string testAll(string op)
746             {
747                 return testSigned(op) ~ testMixed(op) ~ testUnsigned(op);
748             }
749 
750             mixin(testAll("+"));
751             mixin(testAll("-"));
752             mixin(testAll("*"));
753             mixin(testAll("|"));
754             mixin(testAll("&"));
755             mixin(testAll("^"));
756             if (sj != 0)
757             {
758                 mixin(testSigned("/"));
759                 mixin(testSigned("%"));
760                 if (si >= 0 && sj >= 0)
761                 {
762                     // those operations are not supposed to be the same at
763                     // higher bitdepth: a sign-extended negative may yield higher dividend
764                     testMixed("/");
765                     testUnsigned("/");
766                     testMixed("%");
767                     testUnsigned("%");
768                 }
769             }
770         }
771     }
772 }
773 
774 unittest
775 {
776     // Just a little over 2^64, so it actually needs int128.
777     // Hex value should be 0x1_158E_4609_13D0_0001.
778     enum x = int128.literal!"20_000_000_000_000_000_001";
779     assert(x.hi == 0x1 && x.lo == 0x158E_4609_13D0_0001);
780     assert((x >>> 1) == 0x8AC7_2304_89E8_0000);
781 
782     enum y = int128.literal!"0x1_158E_4609_13D0_0001";
783     enum z = int128.literal!"0x1_158e_4609_13d0_0001"; // case insensitivity
784     assert(x == y && y == z && x == z);
785 }
786 
787 unittest
788 {
789     import std..string : format;
790 
791     // Malformed literals that should be rejected
792     assert(!__traits(compiles, int128.literal!""));
793     assert(!__traits(compiles, int128.literal!"-"));
794 
795     // Negative literals should be supported
796     auto x = int128.literal!"-20000000000000000001";
797     assert(x.hi == 0xFFFF_FFFF_FFFF_FFFE &&
798            x.lo == 0xEA71_B9F6_EC2F_FFFF);
799     assert(format("%d", x) == "-20000000000000000001");
800     assert(format("%x", x) == "FFFFFFFFFFFFFFFEEA71B9F6EC2FFFFF");
801 
802     // Negative literals should not be supported for unsigned types
803     assert(!__traits(compiles, uint128.literal!"-1"));
804 
805     // Hex formatting tests
806     x = 0;
807     assert(format("%x", x) == "0");
808     x = -1;
809     assert(format("%x", x) == "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
810 }