| /** |
| * 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; |
| } |
| } |
