1
2/* Compiler implementation of the D programming language
3 * Copyright (C) 1999-2019 by The D Language Foundation, All Rights Reserved
4 * written by KennyTM
5 * http://www.digitalmars.com
6 * Distributed under the Boost Software License, Version 1.0.
7 * http://www.boost.org/LICENSE_1_0.txt
8 * https://github.com/D-Programming-Language/dmd/blob/master/src/intrange.c
9 */
10
11#include "root/dsystem.h"
12
13#include "intrange.h"
14#include "mars.h"
15#include "mtype.h"
16#include "expression.h"
17
18// Copy the sign to the value *x*. Equivalent to `sign ? -x : x`.
19static uinteger_t copySign(uinteger_t x, bool sign)
20{
21    // return sign ? -x : x;
22    return (x - (uinteger_t)sign) ^ -(uinteger_t)sign;
23}
24
25#ifndef UINT64_MAX
26#define UINT64_MAX 0xFFFFFFFFFFFFFFFFULL
27#endif
28
29//==================== SignExtendedNumber ======================================
30
31SignExtendedNumber SignExtendedNumber::fromInteger(uinteger_t value_)
32{
33    return SignExtendedNumber(value_, value_ >> 63);
34}
35
36bool SignExtendedNumber::operator==(const SignExtendedNumber& a) const
37{
38    return value == a.value && negative == a.negative;
39}
40
41bool SignExtendedNumber::operator<(const SignExtendedNumber& a) const
42{
43    return (negative && !a.negative)
44        || (negative == a.negative && value < a.value);
45}
46
47SignExtendedNumber SignExtendedNumber::extreme(bool minimum)
48{
49    return SignExtendedNumber(minimum-1, minimum);
50}
51
52SignExtendedNumber SignExtendedNumber::max()
53{
54    return SignExtendedNumber(UINT64_MAX, false);
55}
56
57SignExtendedNumber& SignExtendedNumber::operator++()
58{
59    if (value != UINT64_MAX)
60        ++value;
61    else if (negative)
62    {
63        value = 0;
64        negative = false;
65    }
66    return *this;
67}
68
69SignExtendedNumber SignExtendedNumber::operator~() const
70{
71    if (~value == 0)
72        return SignExtendedNumber(~value);
73    else
74        return SignExtendedNumber(~value, !negative);
75}
76
77SignExtendedNumber SignExtendedNumber::operator-() const
78{
79    if (value == 0)
80        return SignExtendedNumber(-negative);
81    else
82        return SignExtendedNumber(-value, !negative);
83}
84
85SignExtendedNumber SignExtendedNumber::operator&(const SignExtendedNumber& rhs) const
86{
87    return SignExtendedNumber(value & rhs.value);
88}
89
90SignExtendedNumber SignExtendedNumber::operator|(const SignExtendedNumber& rhs) const
91{
92    return SignExtendedNumber(value | rhs.value);
93}
94
95SignExtendedNumber SignExtendedNumber::operator^(const SignExtendedNumber& rhs) const
96{
97    return SignExtendedNumber(value ^ rhs.value);
98}
99
100SignExtendedNumber SignExtendedNumber::operator+(const SignExtendedNumber& rhs) const
101{
102    uinteger_t sum = value + rhs.value;
103    bool carry = sum < value && sum < rhs.value;
104    if (negative != rhs.negative)
105        return SignExtendedNumber(sum, !carry);
106    else if (negative)
107        return SignExtendedNumber(carry ? sum : 0, true);
108    else
109        return SignExtendedNumber(carry ? UINT64_MAX : sum, false);
110}
111
112SignExtendedNumber SignExtendedNumber::operator-(const SignExtendedNumber& rhs) const
113{
114    if (rhs.isMinimum())
115        return negative ? SignExtendedNumber(value, false) : max();
116    else
117        return *this + (-rhs);
118}
119
120SignExtendedNumber SignExtendedNumber::operator*(const SignExtendedNumber& rhs) const
121{
122    // perform *saturated* multiplication, otherwise we may get bogus ranges
123    //  like 0x10 * 0x10 == 0x100 == 0.
124
125    /* Special handling for zeros:
126        INT65_MIN * 0 = 0
127        INT65_MIN * + = INT65_MIN
128        INT65_MIN * - = INT65_MAX
129        0 * anything = 0
130    */
131    if (value == 0)
132    {
133        if (!negative)
134            return *this;
135        else if (rhs.negative)
136            return max();
137        else
138            return rhs.value == 0 ? rhs : *this;
139    }
140    else if (rhs.value == 0)
141        return rhs * *this;   // don't duplicate the symmetric case.
142
143    SignExtendedNumber rv;
144    // these are != 0 now surely.
145    uinteger_t tAbs = copySign(value, negative);
146    uinteger_t aAbs = copySign(rhs.value, rhs.negative);
147    rv.negative = negative != rhs.negative;
148    if (UINT64_MAX / tAbs < aAbs)
149        rv.value = rv.negative-1;
150    else
151        rv.value = copySign(tAbs * aAbs, rv.negative);
152    return rv;
153}
154
155SignExtendedNumber SignExtendedNumber::operator/(const SignExtendedNumber& rhs) const
156{
157    /* special handling for zeros:
158        INT65_MIN / INT65_MIN = 1
159        anything / INT65_MIN = 0
160        + / 0 = INT65_MAX  (eh?)
161        - / 0 = INT65_MIN  (eh?)
162    */
163    if (rhs.value == 0)
164    {
165        if (rhs.negative)
166            return SignExtendedNumber(value == 0 && negative);
167        else
168            return extreme(negative);
169    }
170
171    uinteger_t aAbs = copySign(rhs.value, rhs.negative);
172    uinteger_t rvVal;
173
174    if (!isMinimum())
175        rvVal = copySign(value, negative) / aAbs;
176    // Special handling for INT65_MIN
177    //  if the denominator is not a power of 2, it is same as UINT64_MAX / x.
178    else if (aAbs & (aAbs-1))
179        rvVal = UINT64_MAX / aAbs;
180    // otherwise, it's the same as reversing the bits of x.
181    else
182    {
183        if (aAbs == 1)
184            return extreme(!rhs.negative);
185        rvVal = 1ULL << 63;
186        aAbs >>= 1;
187        if (aAbs & 0xAAAAAAAAAAAAAAAAULL) rvVal >>= 1;
188        if (aAbs & 0xCCCCCCCCCCCCCCCCULL) rvVal >>= 2;
189        if (aAbs & 0xF0F0F0F0F0F0F0F0ULL) rvVal >>= 4;
190        if (aAbs & 0xFF00FF00FF00FF00ULL) rvVal >>= 8;
191        if (aAbs & 0xFFFF0000FFFF0000ULL) rvVal >>= 16;
192        if (aAbs & 0xFFFFFFFF00000000ULL) rvVal >>= 32;
193    }
194    bool rvNeg = negative != rhs.negative;
195    rvVal = copySign(rvVal, rvNeg);
196
197    return SignExtendedNumber(rvVal, rvVal != 0 && rvNeg);
198}
199
200SignExtendedNumber SignExtendedNumber::operator%(const SignExtendedNumber& rhs) const
201{
202    if (rhs.value == 0)
203        return !rhs.negative ? rhs : isMinimum() ? SignExtendedNumber(0) : *this;
204
205    uinteger_t aAbs = copySign(rhs.value, rhs.negative);
206    uinteger_t rvVal;
207
208    // a % b == sgn(a) * abs(a) % abs(b).
209    if (!isMinimum())
210        rvVal = copySign(value, negative) % aAbs;
211    // Special handling for INT65_MIN
212    //  if the denominator is not a power of 2, it is same as UINT64_MAX%x + 1.
213    else if (aAbs & (aAbs - 1))
214        rvVal = UINT64_MAX % aAbs + 1;
215    //  otherwise, the modulus is trivially zero.
216    else
217        rvVal = 0;
218
219    rvVal = copySign(rvVal, negative);
220    return SignExtendedNumber(rvVal, rvVal != 0 && negative);
221}
222
223SignExtendedNumber SignExtendedNumber::operator<<(const SignExtendedNumber& rhs) const
224{
225    // assume left-shift the shift-amount is always unsigned. Thus negative
226    //  shifts will give huge result.
227    if (value == 0)
228        return *this;
229    else if (rhs.negative)
230        return extreme(negative);
231
232    uinteger_t v = copySign(value, negative);
233
234    // compute base-2 log of 'v' to determine the maximum allowed bits to shift.
235    // Ref: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
236
237    // Why is this a size_t? Looks like a bug.
238    size_t r, s;
239
240    r = (v > 0xFFFFFFFFULL) << 5; v >>= r;
241    s = (v > 0xFFFFULL    ) << 4; v >>= s; r |= s;
242    s = (v > 0xFFULL      ) << 3; v >>= s; r |= s;
243    s = (v > 0xFULL       ) << 2; v >>= s; r |= s;
244    s = (v > 0x3ULL       ) << 1; v >>= s; r |= s;
245                                           r |= (v >> 1);
246
247    uinteger_t allowableShift = 63 - r;
248    if (rhs.value > allowableShift)
249        return extreme(negative);
250    else
251        return SignExtendedNumber(value << rhs.value, negative);
252}
253
254SignExtendedNumber SignExtendedNumber::operator>>(const SignExtendedNumber& rhs) const
255{
256    if (rhs.negative || rhs.value > 63)
257        return negative ? SignExtendedNumber(-1, true) : SignExtendedNumber(0);
258    else if (isMinimum())
259        return rhs.value == 0 ? *this : SignExtendedNumber(-1ULL << (64 - rhs.value), true);
260
261    uinteger_t x = value ^ -negative;
262    x >>= rhs.value;
263    return SignExtendedNumber(x ^ -negative, negative);
264}
265
266
267//==================== IntRange ================================================
268
269IntRange IntRange::widest()
270{
271    return IntRange(SignExtendedNumber::min(), SignExtendedNumber::max());
272}
273
274IntRange IntRange::fromType(Type *type)
275{
276    return fromType(type, type->isunsigned());
277}
278
279IntRange IntRange::fromType(Type *type, bool isUnsigned)
280{
281    if (!type->isintegral() || type->toBasetype()->ty == Tvector)
282        return widest();
283
284    uinteger_t mask = type->sizemask();
285    SignExtendedNumber lower(0), upper(mask);
286    if (type->toBasetype()->ty == Tdchar)
287        upper.value = 0x10FFFFULL;
288    else if (!isUnsigned)
289    {
290        lower.value = ~(mask >> 1);
291        lower.negative = true;
292        upper.value = (mask >> 1);
293    }
294    return IntRange(lower, upper);
295}
296
297IntRange IntRange::fromNumbers2(const SignExtendedNumber numbers[2])
298{
299    if (numbers[0] < numbers[1])
300        return IntRange(numbers[0], numbers[1]);
301    else
302        return IntRange(numbers[1], numbers[0]);
303}
304IntRange IntRange::fromNumbers4(const SignExtendedNumber numbers[4])
305{
306    IntRange ab = fromNumbers2(numbers);
307    IntRange cd = fromNumbers2(numbers + 2);
308    if (cd.imin < ab.imin)
309        ab.imin = cd.imin;
310    if (cd.imax > ab.imax)
311        ab.imax = cd.imax;
312    return ab;
313}
314
315bool IntRange::contains(const IntRange& a) const
316{
317    return imin <= a.imin && imax >= a.imax;
318}
319
320bool IntRange::containsZero() const
321{
322    return (imin.negative && !imax.negative)
323        || (!imin.negative && imin.value == 0);
324}
325
326IntRange& IntRange::castUnsigned(uinteger_t mask)
327{
328    // .... 0x1eff ] [0x1f00 .. 0x1fff] [0 .. 0xff] [0x100 .. 0x1ff] [0x200 ....
329    //
330    // regular unsigned type. We just need to see if ir steps across the
331    //  boundary of validRange. If yes, ir will represent the whole validRange,
332    //  otherwise, we just take the modulus.
333    // e.g. [0x105, 0x107] & 0xff == [5, 7]
334    //      [0x105, 0x207] & 0xff == [0, 0xff]
335    uinteger_t minChunk = imin.value & ~mask;
336    uinteger_t maxChunk = imax.value & ~mask;
337    if (minChunk == maxChunk && imin.negative == imax.negative)
338    {
339        imin.value &= mask;
340        imax.value &= mask;
341    }
342    else
343    {
344        imin.value = 0;
345        imax.value = mask;
346    }
347    imin.negative = imax.negative = false;
348    return *this;
349}
350
351IntRange& IntRange::castSigned(uinteger_t mask)
352{
353    // .... 0x1e7f ] [0x1e80 .. 0x1f7f] [0x1f80 .. 0x7f] [0x80 .. 0x17f] [0x180 ....
354    //
355    // regular signed type. We use a technique similar to the unsigned version,
356    //  but the chunk has to be offset by 1/2 of the range.
357    uinteger_t halfChunkMask = mask >> 1;
358    uinteger_t minHalfChunk = imin.value & ~halfChunkMask;
359    uinteger_t maxHalfChunk = imax.value & ~halfChunkMask;
360    int minHalfChunkNegativity = imin.negative; // 1 = neg, 0 = nonneg, -1 = chunk containing ::max
361    int maxHalfChunkNegativity = imax.negative;
362    if (minHalfChunk & mask)
363    {
364        minHalfChunk += halfChunkMask+1;
365        if (minHalfChunk == 0)
366            -- minHalfChunkNegativity;
367    }
368    if (maxHalfChunk & mask)
369    {
370        maxHalfChunk += halfChunkMask+1;
371        if (maxHalfChunk == 0)
372            -- maxHalfChunkNegativity;
373    }
374    if (minHalfChunk == maxHalfChunk && minHalfChunkNegativity == maxHalfChunkNegativity)
375    {
376        imin.value &= mask;
377        imax.value &= mask;
378        // sign extend if necessary.
379        imin.negative = imin.value & ~halfChunkMask;
380        imax.negative = imax.value & ~halfChunkMask;
381        halfChunkMask += 1;
382        imin.value = (imin.value ^ halfChunkMask) - halfChunkMask;
383        imax.value = (imax.value ^ halfChunkMask) - halfChunkMask;
384    }
385    else
386    {
387        imin = SignExtendedNumber(~halfChunkMask, true);
388        imax = SignExtendedNumber(halfChunkMask, false);
389    }
390    return *this;
391}
392
393IntRange& IntRange::castDchar()
394{
395    // special case for dchar. Casting to dchar means "I'll ignore all
396    //  invalid characters."
397    castUnsigned(0xFFFFFFFFULL);
398    if (imin.value > 0x10FFFFULL)   // ??
399        imin.value = 0x10FFFFULL;   // ??
400    if (imax.value > 0x10FFFFULL)
401        imax.value = 0x10FFFFULL;
402    return *this;
403}
404
405IntRange& IntRange::cast(Type *type)
406{
407    if (!type->isintegral() || type->toBasetype()->ty == Tvector)
408        return *this;
409    else if (!type->isunsigned())
410        return castSigned(type->sizemask());
411    else if (type->toBasetype()->ty == Tdchar)
412        return castDchar();
413    else
414        return castUnsigned(type->sizemask());
415}
416
417IntRange& IntRange::castUnsigned(Type *type)
418{
419    if (!type->isintegral() || type->toBasetype()->ty == Tvector)
420        return castUnsigned(UINT64_MAX);
421    else if (type->toBasetype()->ty == Tdchar)
422        return castDchar();
423    else
424        return castUnsigned(type->sizemask());
425}
426
427IntRange IntRange::absNeg() const
428{
429    if (imax.negative)
430        return *this;
431    else if (!imin.negative)
432        return IntRange(-imax, -imin);
433    else
434    {
435        SignExtendedNumber imaxAbsNeg = -imax;
436        return IntRange(imaxAbsNeg < imin ? imaxAbsNeg : imin,
437                        SignExtendedNumber(0));
438    }
439}
440
441IntRange IntRange::unionWith(const IntRange& other) const
442{
443    return IntRange(imin < other.imin ? imin : other.imin,
444                    imax > other.imax ? imax : other.imax);
445}
446
447void IntRange::unionOrAssign(const IntRange& other, bool& union_)
448{
449    if (!union_ || imin > other.imin)
450        imin = other.imin;
451    if (!union_ || imax < other.imax)
452        imax = other.imax;
453    union_ = true;
454}
455
456void IntRange::splitBySign(IntRange& negRange, bool& hasNegRange,
457                           IntRange& nonNegRange, bool& hasNonNegRange) const
458{
459    hasNegRange = imin.negative;
460    if (hasNegRange)
461    {
462        negRange.imin = imin;
463        negRange.imax = imax.negative ? imax : SignExtendedNumber(-1, true);
464    }
465    hasNonNegRange = !imax.negative;
466    if (hasNonNegRange)
467    {
468        nonNegRange.imin = imin.negative ? SignExtendedNumber(0) : imin;
469        nonNegRange.imax = imax;
470    }
471}
472
473IntRange IntRange::operator~() const
474{
475    return IntRange(~imax, ~imin);
476}
477
478IntRange IntRange::operator-() const
479{
480    return IntRange(-imax, -imin);
481}
482
483IntRange IntRange::operator&(const IntRange& rhs) const
484{
485    // unsigned or identical sign bits
486    if ((imin.negative ^ imax.negative) != 1 && (rhs.imin.negative ^ rhs.imax.negative) != 1)
487    {
488        return IntRange(minAnd(*this, rhs), maxAnd(*this, rhs));
489    }
490
491    IntRange l = IntRange(*this);
492    IntRange r = IntRange(rhs);
493
494    // both intervals span [-1,0]
495    if ((l.imin.negative ^ l.imax.negative) == 1 && (r.imin.negative ^ r.imax.negative) == 1)
496    {
497        // cannot be larger than either l.max or r.max, set the other one to -1
498        SignExtendedNumber max = l.imax.value > r.imax.value ? l.imax : r.imax;
499
500        // only negative numbers for minimum
501        l.imax.value = -1;
502        l.imax.negative = true;
503        r.imax.value = -1;
504        r.imax.negative = true;
505
506        return IntRange(minAnd(l, r), max);
507    }
508    else
509    {
510        // only one interval spans [-1,0]
511        if ((l.imin.negative ^ l.imax.negative) == 1)
512        {
513            swap(l, r); // r spans [-1,0]
514        }
515
516        SignExtendedNumber minAndNeg = minAnd(l, IntRange(r.imin, SignExtendedNumber(-1)));
517        SignExtendedNumber minAndPos = minAnd(l, IntRange(SignExtendedNumber(0), r.imax));
518        SignExtendedNumber maxAndNeg = maxAnd(l, IntRange(r.imin, SignExtendedNumber(-1)));
519        SignExtendedNumber maxAndPos = maxAnd(l, IntRange(SignExtendedNumber(0), r.imax));
520
521        SignExtendedNumber min = minAndNeg < minAndPos ? minAndNeg : minAndPos;
522        SignExtendedNumber max = maxAndNeg > maxAndPos ? maxAndNeg : maxAndPos;
523
524        return IntRange(min, max);
525    }
526}
527
528IntRange IntRange::operator|(const IntRange& rhs) const
529{
530    // unsigned or identical sign bits:
531    if ((imin.negative ^ imax.negative) == 0 && (rhs.imin.negative ^ rhs.imax.negative) == 0)
532    {
533        return IntRange(minOr(*this, rhs), maxOr(*this, rhs));
534    }
535
536    IntRange l = IntRange(*this);
537    IntRange r = IntRange(rhs);
538
539    // both intervals span [-1,0]
540    if ((l.imin.negative ^ l.imax.negative) == 1 && (r.imin.negative ^ r.imax.negative) == 1)
541    {
542        // cannot be smaller than either l.min or r.min, set the other one to 0
543        SignExtendedNumber min = l.imin.value < r.imin.value ? l.imin : r.imin;
544
545        // only negative numbers for minimum
546        l.imin.value = 0;
547        l.imin.negative = false;
548        r.imin.value = 0;
549        r.imin.negative = false;
550
551        return IntRange(min, maxOr(l, r));
552    }
553    else
554    {
555        // only one interval spans [-1,0]
556        if ((imin.negative ^ imax.negative) == 1)
557        {
558            swap(l, r); // r spans [-1,0]
559        }
560
561        SignExtendedNumber minOrNeg = minOr(l, IntRange(r.imin, SignExtendedNumber(-1)));
562        SignExtendedNumber minOrPos = minOr(l, IntRange(SignExtendedNumber(0), r.imax));
563        SignExtendedNumber maxOrNeg = maxOr(l, IntRange(r.imin, SignExtendedNumber(-1)));
564        SignExtendedNumber maxOrPos = maxOr(l, IntRange(SignExtendedNumber(0), r.imax));
565
566        SignExtendedNumber min = minOrNeg < minOrPos ? minOrNeg : minOrPos;
567        SignExtendedNumber max = maxOrNeg > maxOrPos ? maxOrNeg : maxOrPos;
568
569        return IntRange(min, max);
570    }
571}
572
573IntRange IntRange::operator^(const IntRange& rhs) const
574{
575    return (*this & (~rhs)) | (~(*this) & rhs);
576}
577
578IntRange IntRange::operator+(const IntRange& rhs) const
579{
580    return IntRange(imin + rhs.imin, imax + rhs.imax);
581}
582
583IntRange IntRange::operator-(const IntRange& rhs) const
584{
585    return IntRange(imin - rhs.imax, imax - rhs.imin);
586}
587
588IntRange IntRange::operator*(const IntRange& rhs) const
589{
590    // [a,b] * [c,d] = [min (ac, ad, bc, bd), max (ac, ad, bc, bd)]
591    SignExtendedNumber bdy[4];
592    bdy[0] = imin * rhs.imin;
593    bdy[1] = imin * rhs.imax;
594    bdy[2] = imax * rhs.imin;
595    bdy[3] = imax * rhs.imax;
596    return IntRange::fromNumbers4(bdy);
597}
598
599IntRange IntRange::operator/(const IntRange& rhs) const
600{
601    // Handle divide by 0
602    if (rhs.imax.value == 0 && rhs.imin.value == 0)
603        return widest();
604
605    IntRange r = IntRange(rhs);
606
607    // Don't treat the whole range as divide by 0 if only one end of a range is 0.
608    // Issue 15289
609    if (r.imax.value == 0)
610    {
611        r.imax.value--;
612    }
613    else if (r.imin.value == 0)
614    {
615        r.imin.value++;
616    }
617
618    if (!imin.negative && !imax.negative && !r.imin.negative && !r.imax.negative)
619    {
620        return IntRange(imin / r.imax, imax / r.imin);
621    }
622    else
623    {
624        // [a,b] / [c,d] = [min (a/c, a/d, b/c, b/d), max (a/c, a/d, b/c, b/d)]
625        SignExtendedNumber bdy[4];
626        bdy[0] = imin / r.imin;
627        bdy[1] = imin / r.imax;
628        bdy[2] = imax / r.imin;
629        bdy[3] = imax / r.imax;
630
631        return IntRange::fromNumbers4(bdy);
632    }
633}
634
635IntRange IntRange::operator%(const IntRange& rhs) const
636{
637    IntRange irNum = *this;
638    IntRange irDen = rhs.absNeg();
639
640    /*
641     due to the rules of D (C)'s % operator, we need to consider the cases
642     separately in different range of signs.
643
644         case 1. [500, 1700] % [7, 23] (numerator is always positive)
645             = [0, 22]
646         case 2. [-500, 1700] % [7, 23] (numerator can be negative)
647             = [-22, 22]
648         case 3. [-1700, -500] % [7, 23] (numerator is always negative)
649             = [-22, 0]
650
651     the number 22 is the maximum absolute value in the denomator's range. We
652     don't care about divide by zero.
653     */
654
655    irDen.imin = irDen.imin + SignExtendedNumber(1);
656    irDen.imax = -irDen.imin;
657
658    if (!irNum.imin.negative)
659    {
660        irNum.imin.value = 0;
661    }
662    else if (irNum.imin < irDen.imin)
663    {
664        irNum.imin = irDen.imin;
665    }
666
667    if (irNum.imax.negative)
668    {
669        irNum.imax.negative = false;
670        irNum.imax.value = 0;
671    }
672    else if (irNum.imax > irDen.imax)
673    {
674        irNum.imax = irDen.imax;
675    }
676
677    return irNum;
678}
679
680IntRange IntRange::operator<<(const IntRange& rhs) const
681{
682    IntRange r = IntRange(rhs);
683    if (r.imin.negative)
684    {
685        r = IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
686    }
687
688    SignExtendedNumber lower = imin << (imin.negative ? r.imax : r.imin);
689    SignExtendedNumber upper = imax << (imax.negative ? r.imin : r.imax);
690
691    return IntRange(lower, upper);
692}
693
694IntRange IntRange::operator>>(const IntRange& rhs) const
695{
696    IntRange r = IntRange(rhs);
697    if (r.imin.negative)
698    {
699        r = IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
700    }
701
702    SignExtendedNumber lower = imin >> (imin.negative ? r.imin : r.imax);
703    SignExtendedNumber upper = imax >> (imax.negative ? r.imax : r.imin);
704
705    return IntRange(lower, upper);
706}
707
708SignExtendedNumber IntRange::maxOr(const IntRange& lhs, const IntRange& rhs)
709{
710    uinteger_t x = 0;
711    bool sign = false;
712    uinteger_t xorvalue = lhs.imax.value ^ rhs.imax.value;
713    uinteger_t andvalue = lhs.imax.value & rhs.imax.value;
714    IntRange lhsc = IntRange(lhs);
715    IntRange rhsc = IntRange(rhs);
716
717    // Sign bit not part of the .value so we need an extra iteration
718    if (lhsc.imax.negative ^ rhsc.imax.negative)
719    {
720        sign = true;
721        if (lhsc.imax.negative)
722        {
723            if (!lhsc.imin.negative)
724            {
725                lhsc.imin.value = 0;
726            }
727            if (!rhsc.imin.negative)
728            {
729                rhsc.imin.value = 0;
730            }
731        }
732    }
733    else if (lhsc.imin.negative & rhsc.imin.negative)
734    {
735        sign = true;
736    }
737    else if (lhsc.imax.negative & rhsc.imax.negative)
738    {
739        return SignExtendedNumber(-1, false);
740    }
741
742    for (uinteger_t d = 1ULL << (8 * sizeof(uinteger_t) - 1); d; d >>= 1)
743    {
744        if (xorvalue & d)
745        {
746            x |= d;
747            if (lhsc.imax.value & d)
748            {
749                if (~lhsc.imin.value & d)
750                {
751                    lhsc.imin.value = 0;
752                }
753            }
754            else
755            {
756                if (~rhsc.imin.value & d)
757                {
758                    rhsc.imin.value = 0;
759                }
760            }
761        }
762        else if (lhsc.imin.value & rhsc.imin.value & d)
763        {
764            x |= d;
765        }
766        else if (andvalue & d)
767        {
768            x |= (d << 1) - 1;
769            break;
770        }
771    }
772
773    return SignExtendedNumber(x, sign);
774}
775
776SignExtendedNumber IntRange::minOr(const IntRange& lhs, const IntRange& rhs)
777{
778    return ~maxAnd(~lhs, ~rhs);
779}
780
781SignExtendedNumber IntRange::maxAnd(const IntRange& lhs, const IntRange& rhs)
782{
783    uinteger_t x = 0;
784    bool sign = false;
785    IntRange lhsc = IntRange(lhs);
786    IntRange rhsc = IntRange(rhs);
787
788    if (lhsc.imax.negative & rhsc.imax.negative)
789    {
790        sign = true;
791    }
792
793    for (uinteger_t d = 1ULL << (8 * sizeof(uinteger_t) - 1); d; d >>= 1)
794    {
795        if (lhsc.imax.value & rhsc.imax.value & d)
796        {
797            x |= d;
798            if (~lhsc.imin.value & d)
799            {
800                lhsc.imin.value = 0;
801            }
802            if (~rhsc.imin.value & d)
803            {
804                rhsc.imin.value = 0;
805            }
806        }
807        else if (~lhsc.imin.value & d && lhsc.imax.value & d)
808        {
809            lhsc.imax.value |= d - 1;
810        }
811        else if (~rhsc.imin.value & d && rhsc.imax.value & d)
812        {
813            rhsc.imax.value |= d - 1;
814        }
815    }
816
817    return SignExtendedNumber(x, sign);
818}
819
820SignExtendedNumber IntRange::minAnd(const IntRange& lhs, const IntRange& rhs)
821{
822    return ~maxOr(~lhs, ~rhs);
823}
824
825void IntRange::swap(IntRange& a, IntRange& b)
826{
827    IntRange aux = a;
828    a = b;
829    b = aux;
830}
831
832const IntRange& IntRange::dump(const char* funcName, Expression *e) const
833{
834    printf("[(%c)%#018llx, (%c)%#018llx] @ %s ::: %s\n",
835           imin.negative?'-':'+', (unsigned long long)imin.value,
836           imax.negative?'-':'+', (unsigned long long)imax.value,
837           funcName, e->toChars());
838    return *this;
839}
840