// Written in the D programming language /** * Implements a signed 128 bit integer type. * Author: Walter Bright Copyright: Copyright (c) 2022, D Language Foundation License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0) Source: $(PHOBOSSRC std/int128.d) */ module std.int128; private import core.int128; /*********************************** * 128 bit signed integer type. */ public struct Int128 { @safe pure nothrow @nogc { Cent data; /// core.int128.Cent /**************** * Construct an `Int128` from a `long` value. * The upper 64 bits are formed by sign extension. * Params: * lo = signed lower 64 bits */ this(long lo) { data.lo = lo; data.hi = lo < 0 ? ~0L : 0; } /**************** * Construct an `Int128` from a `ulong` value. * The upper 64 bits are set to zero. * Params: * lo = unsigned lower 64 bits */ this(ulong lo) { data.lo = lo; data.hi = 0; } /**************** * Construct an `Int128` from a `long` value. * Params: * hi = upper 64 bits * lo = lower 64 bits */ this(long hi, long lo) { data.hi = hi; data.lo = lo; } /******************** * Construct an `Int128` from a `Cent`. * Params: * data = Cent data */ this(Cent data) { this.data = data; } /******************** * Returns: hash value for Int128 */ size_t toHash() const { return cast(size_t)((data.lo & 0xFFFF_FFFF) + (data.hi & 0xFFFF_FFFF) + (data.lo >> 32) + (data.hi >> 32)); } /************************ * Compare for equality * Params: lo = signed value to compare with * Returns: true if Int128 equals value */ bool opEquals(long lo) const { return data.lo == lo && data.hi == (lo >> 63); } /************************ * Compare for equality * Params: lo = unsigned value to compare with * Returns: true if Int128 equals value */ bool opEquals(ulong lo) const { return data.hi == 0 && data.lo == lo; } /************************ * Compare for equality * Params: op2 = value to compare with * Returns: true if Int128 equals value */ bool opEquals(Int128 op2) const { return data.hi == op2.data.hi && data.lo == op2.data.lo; } /** Support unary arithmentic operator + * Params: op = "+" * Returns: lvalue of result */ Int128 opUnary(string op)() const if (op == "+") { return this; } /** Support unary arithmentic operator - ~ * Params: op = "-", "~" * Returns: lvalue of result */ Int128 opUnary(string op)() const if (op == "-" || op == "~") { static if (op == "-") return Int128(neg(this.data)); else static if (op == "~") return Int128(com(this.data)); } /** Support unary arithmentic operator ++ -- * Params: op = "++", "--" * Returns: lvalue of result */ Int128 opUnary(string op)() if (op == "++" || op == "--") { static if (op == "++") this.data = inc(this.data); else static if (op == "--") this.data = dec(this.data); else static assert(0, op); return this; } /** Support casting to a bool * Params: T = bool * Returns: true if value is not zero */ bool opCast(T : bool)() const { return tst(this.data); } } // @safe pure nothrow @nogc /** Support casting to an integral type * Params: T = integral type * Returns: low bits of value reinterpreted as T */ T opCast(T : long)() const if (is(byte : T)) { return cast(T) this.data.lo; } /// @safe unittest { const Int128 a = Int128(0xffff_ffff_ffff_ffffL, 0x0123_4567_89ab_cdefL); assert(cast(long) a == 0x0123_4567_89ab_cdefL); assert(cast(int) a == 0x89ab_cdef); assert(cast(byte) a == cast(byte) 0xef); } /** Support casting to floating point type * Params: T = floating point type * Returns: value cast to floating point with environment-dependent * rounding if the value is not exactly representable */ T opCast(T : real)() const { import core.math : ldexp; if (cast(long) this.data.hi >= 0) return ldexp(cast(T) this.data.hi, 64) + this.data.lo; else { const absData = neg(this.data); return -ldexp(cast(T) absData.hi, 64) - absData.lo; } } /// @safe unittest { const Int128 a = Int128(-1L << 60); assert(cast(double) a == -(2.0 ^^ 60)); assert(cast(double) (a * a) == 2.0 ^^ 120); } /** Support binary arithmetic operators + - * / % & | ^ << >> >>> * Params: * op = one of the arithmetic binary operators * op2 = second operand * Returns: value after the operation is applied */ Int128 opBinary(string op)(Int128 op2) const if (op == "+" || op == "-" || op == "*" || op == "/" || op == "%" || op == "&" || op == "|" || op == "^") { static if (op == "+") return Int128(add(this.data, op2.data)); else static if (op == "-") return Int128(sub(this.data, op2.data)); else static if (op == "*") return Int128(mul(this.data, op2.data)); else static if (op == "/") return Int128(div(this.data, op2.data)); else static if (op == "%") { Cent modulus; divmod(this.data, op2.data, modulus); return Int128(modulus); } else static if (op == "&") return Int128(and(this.data, op2.data)); else static if (op == "|") return Int128(or(this.data, op2.data)); else static if (op == "^") return Int128(xor(this.data, op2.data)); else static assert(0, "wrong op value"); } /// ditto Int128 opBinary(string op, Int)(const Int op2) const if ((op == "+" || op == "-" || op == "*" || op == "/" || op == "%" || op == "&" || op == "|" || op == "^") && is(Int : long) && __traits(isIntegral, Int)) { static if (__traits(isUnsigned, Int)) return mixin("this " ~ op ~ " Int128(0, op2)"); else return mixin("this " ~ op ~ " Int128((cast(long) op2) >> 63 , op2)"); } /// ditto Int128 opBinary(string op, IntLike)(auto ref IntLike op2) const if ((op == "+" || op == "-" || op == "*" || op == "/" || op == "%" || op == "&" || op == "|" || op == "^") && is(IntLike : long) && !__traits(isIntegral, IntLike)) { return opBinary!(op)(__traits(getMember, op2, __traits(getAliasThis, IntLike)[0])); } /// ditto Int128 opBinaryRight(string op, Int)(const Int op2) const if ((op == "+" || op == "-" || op == "*" || op == "/" || op == "%" || op == "&" || op == "|" || op == "^") && is(Int : long) && __traits(isIntegral, Int)) { static if (__traits(isUnsigned, Int)) mixin("return Int128(0, op2) " ~ op ~ " this;"); else mixin("return Int128((cast(long) op2) >> 63, op2) " ~ op ~ " this;"); } /// ditto Int128 opBinaryRight(string op, IntLike)(auto ref IntLike op2) const if ((op == "+" || op == "-" || op == "*" || op == "/" || op == "%" || op == "&" || op == "|" || op == "^") && is(IntLike : long) && !__traits(isIntegral, IntLike)) { return opBinaryRight!(op)(__traits(getMember, op2, __traits(getAliasThis, IntLike)[0])); } /// ditto Int128 opBinary(string op)(long op2) const if (op == "<<") { return Int128(shl(this.data, cast(uint) op2)); } /// ditto Int128 opBinary(string op)(long op2) const if (op == ">>") { return Int128(sar(this.data, cast(uint) op2)); } /// ditto Int128 opBinary(string op)(long op2) const if (op == ">>>") { return Int128(shr(this.data, cast(uint) op2)); } /** arithmetic assignment operators += -= *= /= %= &= |= ^= <<= >>= >>>= * Params: op = one of +, -, etc. * op2 = second operand * Returns: lvalue of updated left operand */ ref Int128 opOpAssign(string op)(Int128 op2) if (op == "+" || op == "-" || op == "*" || op == "/" || op == "%" || op == "&" || op == "|" || op == "^" || op == "<<" || op == ">>" || op == ">>>") { mixin("this = this " ~ op ~ " op2;"); return this; } /// ditto ref Int128 opOpAssign(string op, Int)(auto ref Int op2) if ((op == "+" || op == "-" || op == "*" || op == "/" || op == "%" || op == "&" || op == "|" || op == "^" || op == "<<" || op == ">>" || op == ">>>") && is(Int : long)) { mixin("this = this " ~ op ~ " op2;"); return this; } /** support arithmentic comparison operators < <= > >= * Params: op2 = right hand operand * Returns: -1 for less than, 0 for equals, 1 for greater than */ int opCmp(Int128 op2) const @nogc nothrow pure @safe { return this == op2 ? 0 : gt(this.data, op2.data) * 2 - 1; } /// ditto int opCmp(Int)(const Int op2) const @nogc nothrow pure @safe if (is(Int : long) && __traits(isIntegral, Int)) { static if (__traits(isUnsigned, Int)) return opCmp(Int128(0, op2)); else return opCmp(Int128((cast(long) op2) >> 63, op2)); } /// ditto int opCmp(IntLike)(auto ref IntLike op2) const if (is(IntLike : long) && !__traits(isIntegral, IntLike)) { return opCmp(__traits(getMember, op2, __traits(getAliasThis, IntLike)[0])); } /** * Formats `Int128` with either `%d`, `%x`, `%X`, or `%s` (same as `%d`). * * Params: * sink = $(REF_ALTTEXT Output range, isOutputRange, std, range, primitives) * to write to. * fmt = A $(REF FormatSpec, std,format) which controls how the number * is displayed. * * Throws: * $(REF FormatException, std,format) if the format specifier is * not one of 'd', 'x', 'X', 's'. * * See_Also: $(REF formatValue, std,format) */ void toString(Writer, FormatSpec)(scope ref Writer sink, scope const ref FormatSpec fmt) const { import std.range.primitives : put; import std.format : FormatException, Fmt = FormatSpec; static if (is(FormatSpec == Fmt!Char, Char)) { // Puts "Char" into scope if the pattern matches. } static assert(is(Char), "Expecting `FormatSpec` to be instantiation of `std.format.FormatSpec`"); Char[39] buf = void; size_t bufStart = void; Char signChar = 0; if (fmt.spec == 'd' || fmt.spec == 's') { const bool isNeg = 0 > cast(long) this.data.hi; Cent val = isNeg ? neg(this.data) : this.data; immutable Cent radix = { lo: 10, hi: 0 }; Cent modulus; bufStart = buf.length; do { uint x = void; if (ugt(radix, val)) { x = cast(uint) val.lo; val = Cent(0, 0); } else { val = udivmod(val, radix, modulus); x = cast(uint) modulus.lo; } buf[--bufStart] = cast(Char) ('0' + x); } while (tst(val)); if (isNeg) signChar = '-'; else if (fmt.flPlus) signChar = '+'; else if (fmt.flSpace) signChar = ' '; } else if (fmt.spec == 'x' || fmt.spec == 'X') { immutable hexDigits = fmt.spec == 'X' ? "0123456789ABCDEF" : "0123456789abcdef"; ulong a = data.lo; bufStart = buf.length - 1; size_t penPos = buf.length - 1; do { if ((buf[penPos] = hexDigits[0xF & cast(uint) a]) != '0') bufStart = penPos; a >>>= 4; } while (--penPos >= buf.length - 16); a = data.hi; do { if ((buf[penPos] = hexDigits[0xF & cast(uint) a]) != '0') bufStart = penPos; a >>>= 4; } while (--penPos >= buf.length - 32); } else { throw new FormatException("Format specifier not understood: %" ~ fmt.spec); } const minw = (buf.length - bufStart) + int(signChar != 0); const maxw = minw < fmt.width ? fmt.width : minw; const difw = maxw - minw; static void putRepeatedChars(Char c)(scope ref Writer sink, size_t n) { static immutable Char[8] array = [c, c, c, c, c, c, c, c]; foreach (_; 0 .. n / 8) put(sink, array[0 .. 8]); if (n & 7) put(sink, array[0 .. n & 7]); } if (!fmt.flDash && !fmt.flZero && difw) putRepeatedChars!' '(sink, difw); if (signChar) { Char[1] signCharBuf = signChar; put(sink, signCharBuf[0 .. 1]); } if (!fmt.flDash && fmt.flZero && difw) putRepeatedChars!'0'(sink, difw); put(sink, buf[bufStart .. $]); if (fmt.flDash && difw) putRepeatedChars!' '(sink, difw); } /** `toString` is rarely directly invoked; the usual way of using it is via $(REF format, std, format): */ @safe unittest { import std.format : format; assert(format("%s", Int128.max) == "170141183460469231731687303715884105727"); assert(format("%s", Int128.min) == "-170141183460469231731687303715884105728"); assert(format("%x", Int128.max) == "7fffffffffffffffffffffffffffffff"); assert(format("%X", Int128.max) == "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"); assert(format("%032X", Int128(123L)) == "0000000000000000000000000000007B"); assert(format("%+ 40d", Int128(123L)) == " +123"); assert(format("%+-40d", Int128(123L)) == "+123 "); } /// Also can format as `wchar` or `dchar`. @safe unittest { import std.conv : to; assert(to!wstring(Int128.max) == "170141183460469231731687303715884105727"w); assert(to!dstring(Int128.max) == "170141183460469231731687303715884105727"d); } enum min = Int128(long.min, 0); /// minimum value enum max = Int128(long.max, ulong.max); /// maximum value } /********************************************* Tests ************************************/ version (unittest) { import core.stdc.stdio; @trusted void print(Int128 c) { printf("%lld, %lld\n", c.data.hi, c.data.lo); } @trusted void printx(Int128 c) { printf("%llx, %llx\n", c.data.hi, c.data.lo); } } /// Int128 tests @safe pure nothrow @nogc unittest { Int128 c = Int128(5, 6); assert(c == c); assert(c == +c); assert(c == - -c); assert(~c == Int128(~5, ~6)); ++c; assert(c == Int128(5, 7)); assert(--c == Int128(5, 6)); assert(!!c); assert(!Int128()); assert(c + Int128(10, 20) == Int128(15, 26)); assert(c - Int128(1, 2) == Int128(4, 4)); assert(c * Int128(100, 2) == Int128(610, 12)); assert(c / Int128(3, 2) == Int128(0, 1)); assert(c % Int128(3, 2) == Int128(2, 4)); assert((c & Int128(3, 2)) == Int128(1, 2)); assert((c | Int128(3, 2)) == Int128(7, 6)); assert((c ^ Int128(3, 2)) == Int128(6, 4)); assert(c + 15 == Int128(5, 21)); assert(c - 15 == Int128(4, -9)); assert(c * 15 == Int128(75, 90)); assert(c / 15 == Int128(0, 6148914691236517205)); assert(c % 15 == Int128(0, 11)); assert((c & 15) == Int128(0, 6)); assert((c | 15) == Int128(5, 15)); assert((c ^ 15) == Int128(5, 9)); assert(15 + c == Int128(5, 21)); assert(15 - c == Int128(-5, 9)); assert(15 * c == Int128(75, 90)); assert(15 / c == Int128(0, 0)); assert(15 % c == Int128(0, 15)); assert((15 & c) == Int128(0, 6)); assert((15 | c) == Int128(5, 15)); assert((15 ^ c) == Int128(5, 9)); assert(c << 1 == Int128(10, 12)); assert(-c >> 1 == Int128(-3, 9223372036854775805)); assert(-c >>> 1 == Int128(9223372036854775805, 9223372036854775805)); assert((c += 1) == Int128(5, 7)); assert((c -= 1) == Int128(5, 6)); assert((c += Int128(0, 1)) == Int128(5, 7)); assert((c -= Int128(0, 1)) == Int128(5, 6)); assert((c *= 2) == Int128(10, 12)); assert((c /= 2) == Int128(5, 6)); assert((c %= 2) == Int128()); c += Int128(5, 6); assert((c *= Int128(10, 20)) == Int128(160, 120)); assert((c /= Int128(10, 20)) == Int128(0, 15)); c += Int128(72, 0); assert((c %= Int128(10, 20)) == Int128(1, -125)); assert((c &= Int128(3, 20)) == Int128(1, 0)); assert((c |= Int128(8, 2)) == Int128(9, 2)); assert((c ^= Int128(8, 2)) == Int128(1, 0)); c |= Int128(10, 5); assert((c <<= 1) == Int128(11 * 2, 5 * 2)); assert((c >>>= 1) == Int128(11, 5)); c = Int128(long.min, long.min); assert((c >>= 1) == Int128(long.min >> 1, cast(ulong) long.min >> 1)); assert(-Int128.min == Int128.min); assert(Int128.max + 1 == Int128.min); c = Int128(5, 6); assert(c < Int128(6, 5)); assert(c > 10); c = Int128(-1UL); assert(c == -1UL); c = Int128(-1L); assert(c == -1L); } @system unittest { alias Seq(T...) = T; Int128 c = Int128(-1L); assert(c.opCmp(-1L) == 0); // To avoid regression calling opCmp with any integral type needs to // work without the compiler complaining "opCmp called with argument // X matches both <...>". static foreach (Int; Seq!(long, int, short, byte, ulong, uint, ushort, ubyte, dchar, wchar, char)) assert(c < Int.max); static foreach (Int; Seq!(int, short, byte)) assert(c.opCmp(Int(-1)) == 0); assert(c < true); // To avoid regression calling opCmp with any type that converts to an // integral type through alias this needs to work regardless of whether // the alias is safe/pure/nothrow/nogc and regardless of whether the // type has a disabled postblit. static struct Wrapped(T) { T value; uint count; T get() @system { ++count; return value; } // not const alias get this; @disable this(this); // no implicit copies } assert(c.opCmp(Wrapped!long(-1)) == 0); auto w = Wrapped!ulong(ulong.max); w.count++; // avoid invalid D-Scanner message that w could have been declared const assert(c < w); const zero = Int128(0L); const one = Int128(1L); const neg_one = Int128(-1L); const neg_two = Int128(-2L); // Correct result with ulong.max: assert(zero + ulong.max == ulong.max); assert(one * ulong.max == ulong.max); assert((neg_one & ulong.max) == ulong.max); assert((zero | ulong.max) == ulong.max); assert((zero ^ ulong.max) == ulong.max); // Correct result with negative arguments: assert(zero + -1L == -1L); assert(neg_two * -3L == 6L); assert(neg_two / -2L == 1L); assert(neg_two % -2L == 0L); assert((neg_one & -1L) == -1L); assert((zero | -1L) == -1L); assert((zero ^ -1L) == -1L); // Ensure alias this still works. { Int128 a = zero; assert((a ^= w) == ulong.max); } assert((Wrapped!long(-1L) + zero) == -1L); }