xref: /src/external/gpl3/gcc.old/dist/gcc/d/dmd/intrange.d

/**
 * Implement $(LINK2 https://digitalmars.com/articles/b62.html, Value Range Propagation).
 *
 * Copyright:   Copyright (C) 1999-2022 by The D Language Foundation, All Rights Reserved
 * Authors:     $(LINK2 https://www.digitalmars.com, Walter Bright)
 * License:     $(LINK2 https://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
 * Source:      $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/intrange.d, _intrange.d)
 * Documentation:  https://dlang.org/phobos/dmd_intrange.html
 * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/intrange.d
 */

module dmd.intrange;

import core.stdc.stdio;

import dmd.astenums;
import dmd.mtype;
import dmd.expression;
import dmd.globals;

private uinteger_t copySign(uinteger_t x, bool sign)
{
    // return sign ? -x : x;
    return (x - cast(uinteger_t)sign) ^ -cast(uinteger_t)sign;
}

struct SignExtendedNumber
{
    uinteger_t value;
    bool negative;

    static SignExtendedNumber fromInteger(uinteger_t value_)
    {
        return SignExtendedNumber(value_, value_ >> 63);
    }

    static SignExtendedNumber extreme(bool minimum)
    {
        return SignExtendedNumber(minimum - 1, minimum);
    }

    static SignExtendedNumber max()
    {
        return SignExtendedNumber(ulong.max, false);
    }

    static SignExtendedNumber min()
    {
        return SignExtendedNumber(0, true);
    }

    bool isMinimum() const
    {
        return negative && value == 0;
    }

    bool opEquals(const ref SignExtendedNumber a) const
    {
        return value == a.value && negative == a.negative;
    }

    int opCmp(const ref SignExtendedNumber a) const
    {
        if (negative != a.negative)
        {
            if (negative)
                return -1;
            else
                return 1;
        }
        if (value < a.value)
            return -1;
        else if (value > a.value)
            return 1;
        else
            return 0;
    }

    SignExtendedNumber opUnary(string op : "++")()
    {
        if (value != ulong.max)
            ++value;
        else if (negative)
        {
            value = 0;
            negative = false;
        }
        return this;
    }

    SignExtendedNumber opUnary(string op : "~")() const
    {
        if (~value == 0)
            return SignExtendedNumber(~value);
        else
            return SignExtendedNumber(~value, !negative);
    }

    SignExtendedNumber opUnary(string op : "-")() const
    {
        if (value == 0)
            return SignExtendedNumber(-cast(ulong)negative);
        else
            return SignExtendedNumber(-value, !negative);
    }

    SignExtendedNumber opBinary(string op : "&")(SignExtendedNumber rhs) const
    {
        return SignExtendedNumber(value & rhs.value);
    }

    SignExtendedNumber opBinary(string op : "|")(SignExtendedNumber rhs)
    {
        return SignExtendedNumber(value | rhs.value);
    }

    SignExtendedNumber opBinary(string op : "^")(SignExtendedNumber rhs)
    {
        return SignExtendedNumber(value ^ rhs.value);
    }

    SignExtendedNumber opBinary(string op : "+")(SignExtendedNumber rhs)
    {
        uinteger_t sum = value + rhs.value;
        bool carry = sum < value && sum < rhs.value;
        if (negative != rhs.negative)
            return SignExtendedNumber(sum, !carry);
        else if (negative)
            return SignExtendedNumber(carry ? sum : 0, true);
        else
            return SignExtendedNumber(carry ? ulong.max : sum, false);
    }


    SignExtendedNumber opBinary(string op : "-")(SignExtendedNumber rhs)
    {
        if (rhs.isMinimum())
            return negative ? SignExtendedNumber(value, false) : max();
        else
            return this + (-rhs);
    }

    SignExtendedNumber opBinary(string op : "*")(SignExtendedNumber rhs)
    {
        // perform *saturated* multiplication, otherwise we may get bogus ranges
        //  like 0x10 * 0x10 == 0x100 == 0.

        /* Special handling for zeros:
            INT65_MIN * 0 = 0
            INT65_MIN * + = INT65_MIN
            INT65_MIN * - = INT65_MAX
            0 * anything = 0
        */
        if (value == 0)
        {
            if (!negative)
                return this;
            else if (rhs.negative)
                return max();
            else
                return rhs.value == 0 ? rhs : this;
        }
        else if (rhs.value == 0)
            return rhs * this; // don't duplicate the symmetric case.

        SignExtendedNumber rv;
        // these are != 0 now surely.
        uinteger_t tAbs = copySign(value, negative);
        uinteger_t aAbs = copySign(rhs.value, rhs.negative);
        rv.negative = negative != rhs.negative;
        if (ulong.max / tAbs < aAbs)
            rv.value = rv.negative - 1;
        else
            rv.value = copySign(tAbs * aAbs, rv.negative);
        return rv;
    }

    SignExtendedNumber opBinary(string op : "/")(SignExtendedNumber rhs)
    {
        /* special handling for zeros:
            INT65_MIN / INT65_MIN = 1
            anything / INT65_MIN = 0
            + / 0 = INT65_MAX  (eh?)
            - / 0 = INT65_MIN  (eh?)
        */
        if (rhs.value == 0)
        {
            if (rhs.negative)
                return SignExtendedNumber(value == 0 && negative);
            else
                return extreme(negative);
        }

        uinteger_t aAbs = copySign(rhs.value, rhs.negative);
        uinteger_t rvVal;

        if (!isMinimum())
            rvVal = copySign(value, negative) / aAbs;
        // Special handling for INT65_MIN
        //  if the denominator is not a power of 2, it is same as ulong.max / x.
        else if (aAbs & (aAbs - 1))
            rvVal = ulong.max / aAbs;
        // otherwise, it's the same as reversing the bits of x.
        else
        {
            if (aAbs == 1)
                return extreme(!rhs.negative);
            rvVal = 1UL << 63;
            aAbs >>= 1;
            if (aAbs & 0xAAAAAAAAAAAAAAAAUL) rvVal >>= 1;
            if (aAbs & 0xCCCCCCCCCCCCCCCCUL) rvVal >>= 2;
            if (aAbs & 0xF0F0F0F0F0F0F0F0UL) rvVal >>= 4;
            if (aAbs & 0xFF00FF00FF00FF00UL) rvVal >>= 8;
            if (aAbs & 0xFFFF0000FFFF0000UL) rvVal >>= 16;
            if (aAbs & 0xFFFFFFFF00000000UL) rvVal >>= 32;
        }
        bool rvNeg = negative != rhs.negative;
        rvVal = copySign(rvVal, rvNeg);

        return SignExtendedNumber(rvVal, rvVal != 0 && rvNeg);
    }

    SignExtendedNumber opBinary(string op : "%")(SignExtendedNumber rhs)
    {
        if (rhs.value == 0)
            return !rhs.negative ? rhs : isMinimum() ? SignExtendedNumber(0) : this;

        uinteger_t aAbs = copySign(rhs.value, rhs.negative);
        uinteger_t rvVal;

        // a % b == sgn(a) * abs(a) % abs(b).
        if (!isMinimum())
            rvVal = copySign(value, negative) % aAbs;
        // Special handling for INT65_MIN
        //  if the denominator is not a power of 2, it is same as ulong.max % x + 1.
        else if (aAbs & (aAbs - 1))
            rvVal = ulong.max % aAbs + 1;
        //  otherwise, the modulus is trivially zero.
        else
            rvVal = 0;

        rvVal = copySign(rvVal, negative);
        return SignExtendedNumber(rvVal, rvVal != 0 && negative);
    }

    SignExtendedNumber opBinary(string op : "<<")(SignExtendedNumber rhs)
    {
        // assume left-shift the shift-amount is always unsigned. Thus negative
        //  shifts will give huge result.
        if (value == 0)
            return this;
        else if (rhs.negative)
            return extreme(negative);

        uinteger_t v = copySign(value, negative);

        // compute base-2 log of 'v' to determine the maximum allowed bits to shift.
        // Ref: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog

        // Why is this a size_t? Looks like a bug.
        size_t r, s;

        r = (v > 0xFFFFFFFFUL) << 5; v >>= r;
        s = (v > 0xFFFFUL    ) << 4; v >>= s; r |= s;
        s = (v > 0xFFUL      ) << 3; v >>= s; r |= s;
        s = (v > 0xFUL       ) << 2; v >>= s; r |= s;
        s = (v > 0x3UL       ) << 1; v >>= s; r |= s;
                                               r |= (v >> 1);

        uinteger_t allowableShift = 63 - r;
        if (rhs.value > allowableShift)
            return extreme(negative);
        else
            return SignExtendedNumber(value << rhs.value, negative);
    }

    SignExtendedNumber opBinary(string op : ">>")(SignExtendedNumber rhs)
    {
        if (rhs.negative || rhs.value > 63)
            return negative ? SignExtendedNumber(-1, true) : SignExtendedNumber(0);
        else if (isMinimum())
            return rhs.value == 0 ? this : SignExtendedNumber(-1UL << (64 - rhs.value), true);

        uinteger_t x = value ^ -cast(int)negative;
        x >>= rhs.value;
        return SignExtendedNumber(x ^ -cast(int)negative, negative);
    }

    SignExtendedNumber opBinary(string op : "^^")(SignExtendedNumber rhs)
    {
        // Not yet implemented
        assert(0);
    }
}

struct IntRange
{
    SignExtendedNumber imin, imax;

    this(IntRange another)
    {
        imin = another.imin;
        imax = another.imax;
    }

    this(SignExtendedNumber a)
    {
        imin = a;
        imax = a;
    }

    this(SignExtendedNumber lower, SignExtendedNumber upper)
    {
        imin = lower;
        imax = upper;
    }

    static IntRange fromType(Type type)
    {
        return fromType(type, type.isunsigned());
    }

    static IntRange fromType(Type type, bool isUnsigned)
    {
        if (!type.isintegral() || type.toBasetype().ty == Tvector)
            return widest();

        uinteger_t mask = type.sizemask();
        auto lower = SignExtendedNumber(0);
        auto upper = SignExtendedNumber(mask);
        if (type.toBasetype().ty == Tdchar)
            upper.value = 0x10FFFFUL;
        else if (!isUnsigned)
        {
            lower.value = ~(mask >> 1);
            lower.negative = true;
            upper.value = (mask >> 1);
        }
        return IntRange(lower, upper);
    }

    static IntRange fromNumbers2(SignExtendedNumber* numbers)
    {
        if (numbers[0] < numbers[1])
            return IntRange(numbers[0], numbers[1]);
        else
            return IntRange(numbers[1], numbers[0]);
    }

    static IntRange fromNumbers4(SignExtendedNumber* numbers)
    {
        IntRange ab = fromNumbers2(numbers);
        IntRange cd = fromNumbers2(numbers + 2);
        if (cd.imin < ab.imin)
            ab.imin = cd.imin;
        if (cd.imax > ab.imax)
            ab.imax = cd.imax;
        return ab;
    }

    static IntRange widest()
    {
        return IntRange(SignExtendedNumber.min(), SignExtendedNumber.max());
    }

    IntRange castSigned(uinteger_t mask)
    {
        // .... 0x1e7f ] [0x1e80 .. 0x1f7f] [0x1f80 .. 0x7f] [0x80 .. 0x17f] [0x180 ....
        //
        // regular signed type. We use a technique similar to the unsigned version,
        //  but the chunk has to be offset by 1/2 of the range.
        uinteger_t halfChunkMask = mask >> 1;
        uinteger_t minHalfChunk = imin.value & ~halfChunkMask;
        uinteger_t maxHalfChunk = imax.value & ~halfChunkMask;
        int minHalfChunkNegativity = imin.negative; // 1 = neg, 0 = nonneg, -1 = chunk containing ::max
        int maxHalfChunkNegativity = imax.negative;
        if (minHalfChunk & mask)
        {
            minHalfChunk += halfChunkMask + 1;
            if (minHalfChunk == 0)
                --minHalfChunkNegativity;
        }
        if (maxHalfChunk & mask)
        {
            maxHalfChunk += halfChunkMask + 1;
            if (maxHalfChunk == 0)
                --maxHalfChunkNegativity;
        }
        if (minHalfChunk == maxHalfChunk && minHalfChunkNegativity == maxHalfChunkNegativity)
        {
            imin.value &= mask;
            imax.value &= mask;
            // sign extend if necessary.
            imin.negative = (imin.value & ~halfChunkMask) != 0;
            imax.negative = (imax.value & ~halfChunkMask) != 0;
            halfChunkMask += 1;
            imin.value = (imin.value ^ halfChunkMask) - halfChunkMask;
            imax.value = (imax.value ^ halfChunkMask) - halfChunkMask;
        }
        else
        {
            imin = SignExtendedNumber(~halfChunkMask, true);
            imax = SignExtendedNumber(halfChunkMask, false);
        }
        return this;
    }

    IntRange castUnsigned(uinteger_t mask)
    {
        // .... 0x1eff ] [0x1f00 .. 0x1fff] [0 .. 0xff] [0x100 .. 0x1ff] [0x200 ....
        //
        // regular unsigned type. We just need to see if ir steps across the
        //  boundary of validRange. If yes, ir will represent the whole validRange,
        //  otherwise, we just take the modulus.
        // e.g. [0x105, 0x107] & 0xff == [5, 7]
        //      [0x105, 0x207] & 0xff == [0, 0xff]
        uinteger_t minChunk = imin.value & ~mask;
        uinteger_t maxChunk = imax.value & ~mask;
        if (minChunk == maxChunk && imin.negative == imax.negative)
        {
            imin.value &= mask;
            imax.value &= mask;
        }
        else
        {
            imin.value = 0;
            imax.value = mask;
        }
        imin.negative = imax.negative = false;
        return this;
    }

    IntRange castDchar()
    {
        // special case for dchar. Casting to dchar means "I'll ignore all
        //  invalid characters."
        castUnsigned(0xFFFFFFFFUL);
        if (imin.value > 0x10FFFFUL) // ??
            imin.value = 0x10FFFFUL; // ??
        if (imax.value > 0x10FFFFUL)
            imax.value = 0x10FFFFUL;
        return this;
    }

    IntRange _cast(Type type)
    {
        if (!type.isintegral() || type.toBasetype().ty == Tvector)
            return this;
        else if (!type.isunsigned())
            return castSigned(type.sizemask());
        else if (type.toBasetype().ty == Tdchar)
            return castDchar();
        else
            return castUnsigned(type.sizemask());
    }

    IntRange castUnsigned(Type type)
    {
        if (!type.isintegral() || type.toBasetype().ty == Tvector)
            return castUnsigned(ulong.max);
        else if (type.toBasetype().ty == Tdchar)
            return castDchar();
        else
            return castUnsigned(type.sizemask());
    }

    bool contains(IntRange a)
    {
        return imin <= a.imin && imax >= a.imax;
    }

    bool containsZero() const
    {
        return (imin.negative && !imax.negative)
            || (!imin.negative && imin.value == 0);
    }

    IntRange absNeg() const
    {
        if (imax.negative)
            return this;
        else if (!imin.negative)
            return IntRange(-imax, -imin);
        else
        {
            SignExtendedNumber imaxAbsNeg = -imax;
            return IntRange(imaxAbsNeg < imin ? imaxAbsNeg : imin,
                            SignExtendedNumber(0));
        }
    }

    IntRange unionWith(const ref IntRange other) const
    {
        return IntRange(imin < other.imin ? imin : other.imin,
                        imax > other.imax ? imax : other.imax);
    }

    void unionOrAssign(IntRange other, ref bool union_)
    {
        if (!union_ || imin > other.imin)
            imin = other.imin;
        if (!union_ || imax < other.imax)
            imax = other.imax;
        union_ = true;
    }

    ref const(IntRange) dump(const(char)* funcName, Expression e) const return
    {
        printf("[(%c)%#018llx, (%c)%#018llx] @ %s ::: %s\n",
               imin.negative?'-':'+', cast(ulong)imin.value,
               imax.negative?'-':'+', cast(ulong)imax.value,
               funcName, e.toChars());
        return this;
    }

    void splitBySign(ref IntRange negRange, ref bool hasNegRange, ref IntRange nonNegRange, ref bool hasNonNegRange) const
    {
        hasNegRange = imin.negative;
        if (hasNegRange)
        {
            negRange.imin = imin;
            negRange.imax = imax.negative ? imax : SignExtendedNumber(-1, true);
        }
        hasNonNegRange = !imax.negative;
        if (hasNonNegRange)
        {
            nonNegRange.imin = imin.negative ? SignExtendedNumber(0) : imin;
            nonNegRange.imax = imax;
        }
    }

    IntRange opUnary(string op:"~")() const
    {
        return IntRange(~imax, ~imin);
    }

    IntRange opUnary(string op : "-")()
    {
        return IntRange(-imax, -imin);
    }

    // Credits to Timon Gehr for the algorithms for &, |
    // https://github.com/tgehr/d-compiler/blob/master/vrange.d
    IntRange opBinary(string op : "&")(IntRange rhs) const
    {
        // unsigned or identical sign bits
        if ((imin.negative ^ imax.negative) != 1 && (rhs.imin.negative ^ rhs.imax.negative) != 1)
        {
            return IntRange(minAnd(this, rhs), maxAnd(this, rhs));
        }

        IntRange l = IntRange(this);
        IntRange r = IntRange(rhs);

        // both intervals span [-1,0]
        if ((imin.negative ^ imax.negative) == 1 && (rhs.imin.negative ^ rhs.imax.negative) == 1)
        {
            // cannot be larger than either l.max or r.max, set the other one to -1
            SignExtendedNumber max = l.imax.value > r.imax.value ? l.imax : r.imax;

            // only negative numbers for minimum
            l.imax.value = -1;
            l.imax.negative = true;
            r.imax.value = -1;
            r.imax.negative = true;

            return IntRange(minAnd(l, r), max);
        }
        else
        {
            // only one interval spans [-1,0]
            if ((l.imin.negative ^ l.imax.negative) == 1)
            {
                swap(l, r); // r spans [-1,0]
            }

            auto minAndNeg = minAnd(l, IntRange(r.imin, SignExtendedNumber(-1)));
            auto minAndPos = minAnd(l, IntRange(SignExtendedNumber(0), r.imax));
            auto maxAndNeg = maxAnd(l, IntRange(r.imin, SignExtendedNumber(-1)));
            auto maxAndPos = maxAnd(l, IntRange(SignExtendedNumber(0), r.imax));

            auto min = minAndNeg < minAndPos ? minAndNeg : minAndPos;
            auto max = maxAndNeg > maxAndPos ? maxAndNeg : maxAndPos;

            auto range = IntRange(min, max);
            return range;
        }
    }

    // Credits to Timon Gehr for the algorithms for &, |
    // https://github.com/tgehr/d-compiler/blob/master/vrange.d
    IntRange opBinary(string op : "|")(IntRange rhs) const
    {
        // unsigned or identical sign bits:
        if ((imin.negative ^ imax.negative) == 0 && (rhs.imin.negative ^ rhs.imax.negative) == 0)
        {
            return IntRange(minOr(this, rhs), maxOr(this, rhs));
        }

        IntRange l = IntRange(this);
        IntRange r = IntRange(rhs);

        // both intervals span [-1,0]
        if ((imin.negative ^ imax.negative) == 1 && (rhs.imin.negative ^ rhs.imax.negative) == 1)
        {
            // cannot be smaller than either l.min or r.min, set the other one to 0
            SignExtendedNumber min = l.imin.value < r.imin.value ? l.imin : r.imin;

            // only negative numbers for minimum
            l.imin.value = 0;
            l.imin.negative = false;
            r.imin.value = 0;
            r.imin.negative = false;

            return IntRange(min, maxOr(l, r));
        }
        else
        {
            // only one interval spans [-1,0]
            if ((imin.negative ^ imax.negative) == 1)
            {
                swap(l, r); // r spans [-1,0]
            }

            auto minOrNeg = minOr(l, IntRange(r.imin, SignExtendedNumber(-1)));
            auto minOrPos = minOr(l, IntRange(SignExtendedNumber(0), r.imax));
            auto maxOrNeg = maxOr(l, IntRange(r.imin, SignExtendedNumber(-1)));
            auto maxOrPos = maxOr(l, IntRange(SignExtendedNumber(0), r.imax));

            auto min = minOrNeg < minOrPos ? minOrNeg : minOrPos;
            auto max = maxOrNeg > maxOrPos ? maxOrNeg : maxOrPos;

            auto range = IntRange(min, max);
            return range;
        }
    }

    IntRange opBinary(string op : "^")(IntRange rhs) const
    {
        return this & ~rhs | ~this & rhs;
    }

    IntRange opBinary(string op : "+")(IntRange rhs)
    {
        return IntRange(imin + rhs.imin, imax + rhs.imax);
    }

    IntRange opBinary(string op : "-")(IntRange rhs)
    {
        return IntRange(imin - rhs.imax, imax - rhs.imin);
    }

    IntRange opBinary(string op : "*")(IntRange rhs)
    {
        // [a,b] * [c,d] = [min (ac, ad, bc, bd), max (ac, ad, bc, bd)]
        SignExtendedNumber[4] bdy;
        bdy[0] = imin * rhs.imin;
        bdy[1] = imin * rhs.imax;
        bdy[2] = imax * rhs.imin;
        bdy[3] = imax * rhs.imax;
        return IntRange.fromNumbers4(bdy.ptr);
    }

    IntRange opBinary(string op : "/")(IntRange rhs)
    {
        // Handle divide by 0
        if (rhs.imax.value == 0 && rhs.imin.value == 0)
            return widest();

        // Don't treat the whole range as divide by 0 if only one end of a range is 0.
        // Issue 15289
        if (rhs.imax.value == 0)
        {
            rhs.imax.value--;
        }
        else if(rhs.imin.value == 0)
        {
            rhs.imin.value++;
        }

        if (!imin.negative && !imax.negative && !rhs.imin.negative && !rhs.imax.negative)
        {
            return IntRange(imin / rhs.imax, imax / rhs.imin);
        }
        else
        {
            // [a,b] / [c,d] = [min (a/c, a/d, b/c, b/d), max (a/c, a/d, b/c, b/d)]
            SignExtendedNumber[4] bdy;
            bdy[0] = imin / rhs.imin;
            bdy[1] = imin / rhs.imax;
            bdy[2] = imax / rhs.imin;
            bdy[3] = imax / rhs.imax;

            return IntRange.fromNumbers4(bdy.ptr);
        }
    }

    IntRange opBinary(string op : "%")(IntRange rhs)
    {
        IntRange irNum = this;
        IntRange irDen = rhs.absNeg();

        /*
         due to the rules of D (C)'s % operator, we need to consider the cases
         separately in different range of signs.

             case 1. [500, 1700] % [7, 23] (numerator is always positive)
                 = [0, 22]
             case 2. [-500, 1700] % [7, 23] (numerator can be negative)
                 = [-22, 22]
             case 3. [-1700, -500] % [7, 23] (numerator is always negative)
                 = [-22, 0]

         the number 22 is the maximum absolute value in the denomator's range. We
         don't care about divide by zero.
         */

        irDen.imin = irDen.imin + SignExtendedNumber(1);
        irDen.imax = -irDen.imin;

        if (!irNum.imin.negative)
        {
            irNum.imin.value = 0;
        }
        else if (irNum.imin < irDen.imin)
        {
            irNum.imin = irDen.imin;
        }

        if (irNum.imax.negative)
        {
            irNum.imax.negative = false;
            irNum.imax.value = 0;
        }
        else if (irNum.imax > irDen.imax)
        {
            irNum.imax = irDen.imax;
        }

        return irNum;
    }

    IntRange opBinary(string op : "<<")(IntRange rhs)
    {
        if (rhs.imin.negative)
        {
            rhs = IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
        }

        SignExtendedNumber lower = imin << (imin.negative ? rhs.imax : rhs.imin);
        SignExtendedNumber upper = imax << (imax.negative ? rhs.imin : rhs.imax);

        return IntRange(lower, upper);
    }

    IntRange opBinary(string op : ">>")(IntRange rhs)
    {
        if (rhs.imin.negative)
        {
            rhs = IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
        }

        SignExtendedNumber lower = imin >> (imin.negative ? rhs.imin : rhs.imax);
        SignExtendedNumber upper = imax >> (imax.negative ? rhs.imax : rhs.imin);

        return IntRange(lower, upper);
    }

    IntRange opBinary(string op : ">>>")(IntRange rhs)
    {
        if (rhs.imin.negative)
        {
            rhs = IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
        }

        return IntRange(imin >> rhs.imax, imax >> rhs.imin);
    }

    IntRange opBinary(string op : "^^")(IntRange rhs)
    {
        // Not yet implemented
        assert(0);
    }

private:
    // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
    // https://github.com/tgehr/d-compiler/blob/master/vrange.d
    static SignExtendedNumber maxOr(const IntRange lhs, const IntRange rhs)
    {
        uinteger_t x = 0;
        auto sign = false;
        auto xor = lhs.imax.value ^ rhs.imax.value;
        auto and = lhs.imax.value & rhs.imax.value;
        auto lhsc = IntRange(lhs);
        auto rhsc = IntRange(rhs);

        // Sign bit not part of the .value so we need an extra iteration
        if (lhsc.imax.negative ^ rhsc.imax.negative)
        {
            sign = true;
            if (lhsc.imax.negative)
            {
                if (!lhsc.imin.negative)
                {
                    lhsc.imin.value = 0;
                }
                if (!rhsc.imin.negative)
                {
                    rhsc.imin.value = 0;
                }
            }
        }
        else if (lhsc.imin.negative & rhsc.imin.negative)
        {
            sign = true;
        }
        else if (lhsc.imax.negative & rhsc.imax.negative)
        {
            return SignExtendedNumber(-1, false);
        }

        for (uinteger_t d = 1LU << (8 * uinteger_t.sizeof - 1); d; d >>= 1)
        {
            if (xor & d)
            {
                x |= d;
                if (lhsc.imax.value & d)
                {
                    if (~lhsc.imin.value & d)
                    {
                        lhsc.imin.value = 0;
                    }
                }
                else
                {
                    if (~rhsc.imin.value & d)
                    {
                        rhsc.imin.value = 0;
                    }
                }
            }
            else if (lhsc.imin.value & rhsc.imin.value & d)
            {
                x |= d;
            }
            else if (and & d)
            {
                x |= (d << 1) - 1;
                break;
            }
        }

        auto range = SignExtendedNumber(x, sign);
        return range;
    }

    // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
    // https://github.com/tgehr/d-compiler/blob/master/vrange.d
    static SignExtendedNumber minOr(const IntRange lhs, const IntRange rhs)
    {
        return ~maxAnd(~lhs, ~rhs);
    }

    // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
    // https://github.com/tgehr/d-compiler/blob/master/vrange.d
    static SignExtendedNumber maxAnd(const IntRange lhs, const IntRange rhs)
    {
        uinteger_t x = 0;
        bool sign = false;
        auto lhsc = IntRange(lhs);
        auto rhsc = IntRange(rhs);

        if (lhsc.imax.negative & rhsc.imax.negative)
        {
            sign = true;
        }

        for (uinteger_t d = 1LU << (8 * uinteger_t.sizeof - 1); d; d >>= 1)
        {
            if (lhsc.imax.value & rhsc.imax.value & d)
            {
                x |= d;
                if (~lhsc.imin.value & d)
                {
                    lhsc.imin.value = 0;
                }
                if (~rhsc.imin.value & d)
                {
                    rhsc.imin.value = 0;
                }
            }
            else if (~lhsc.imin.value & d && lhsc.imax.value & d)
            {
                lhsc.imax.value |= d - 1;
            }
            else if (~rhsc.imin.value & d && rhsc.imax.value & d)
            {
                rhsc.imax.value |= d - 1;
            }
        }

        auto range = SignExtendedNumber(x, sign);
        return range;
    }

    // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
    // https://github.com/tgehr/d-compiler/blob/master/vrange.d
    static SignExtendedNumber minAnd(const IntRange lhs, const IntRange rhs)
    {
        return ~maxOr(~lhs, ~rhs);
    }

    static swap(ref IntRange a, ref IntRange b)
    {
        auto aux = a;
        a = b;
        b = aux;
    }
}