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

12
module dmd.intrange;
13

14
import core.stdc.stdio;
15

16
import dmd.mtype;
17
import dmd.expression;
18
import dmd.globals;
19

20
private uinteger_t copySign(uinteger_t x, bool sign)
21
{
22
    // return sign ? -x : x;
23 1
    return (x - cast(uinteger_t)sign) ^ -cast(uinteger_t)sign;
24
}
25

26
struct SignExtendedNumber
27
{
28
    uinteger_t value;
29
    bool negative;
30

31
    static SignExtendedNumber fromInteger(uinteger_t value_)
32
    {
33 0
        return SignExtendedNumber(value_, value_ >> 63);
34
    }
35

36
    static SignExtendedNumber extreme(bool minimum)
37
    {
38 1
        return SignExtendedNumber(minimum - 1, minimum);
39
    }
40

41
    static SignExtendedNumber max()
42
    {
43 1
        return SignExtendedNumber(ulong.max, false);
44
    }
45

46
    static SignExtendedNumber min()
47
    {
48 1
        return SignExtendedNumber(0, true);
49
    }
50

51
    bool isMinimum() const
52
    {
53 1
        return negative && value == 0;
54
    }
55

56
    bool opEquals(const ref SignExtendedNumber a) const
57
    {
58 0
        return value == a.value && negative == a.negative;
59
    }
60

61
    int opCmp(const ref SignExtendedNumber a) const
62
    {
63 1
        if (negative != a.negative)
64
        {
65 1
            if (negative)
66 1
                return -1;
67
            else
68 1
                return 1;
69
        }
70 1
        if (value < a.value)
71 1
            return -1;
72 1
        else if (value > a.value)
73 1
            return 1;
74
        else
75 1
            return 0;
76
    }
77

78
    SignExtendedNumber opUnary(string op : "++")()
79
    {
80
        if (value != ulong.max)
81
            ++value;
82
        else if (negative)
83
        {
84
            value = 0;
85
            negative = false;
86
        }
87
        return this;
88
    }
89

90
    SignExtendedNumber opUnary(string op : "~")() const
91
    {
92 1
        if (~value == 0)
93 1
            return SignExtendedNumber(~value);
94
        else
95 1
            return SignExtendedNumber(~value, !negative);
96
    }
97

98
    SignExtendedNumber opUnary(string op : "-")() const
99
    {
100 1
        if (value == 0)
101 1
            return SignExtendedNumber(-cast(ulong)negative);
102
        else
103 1
            return SignExtendedNumber(-value, !negative);
104
    }
105

106
    SignExtendedNumber opBinary(string op : "&")(SignExtendedNumber rhs) const
107
    {
108
        return SignExtendedNumber(value & rhs.value);
109
    }
110

111
    SignExtendedNumber opBinary(string op : "|")(SignExtendedNumber rhs)
112
    {
113
        return SignExtendedNumber(value | rhs.value);
114
    }
115

116
    SignExtendedNumber opBinary(string op : "^")(SignExtendedNumber rhs)
117
    {
118
        return SignExtendedNumber(value ^ rhs.value);
119
    }
120

121
    SignExtendedNumber opBinary(string op : "+")(SignExtendedNumber rhs)
122
    {
123 1
        uinteger_t sum = value + rhs.value;
124 1
        bool carry = sum < value && sum < rhs.value;
125 1
        if (negative != rhs.negative)
126 1
            return SignExtendedNumber(sum, !carry);
127 1
        else if (negative)
128 1
            return SignExtendedNumber(carry ? sum : 0, true);
129
        else
130 1
            return SignExtendedNumber(carry ? ulong.max : sum, false);
131
    }
132

133

134
    SignExtendedNumber opBinary(string op : "-")(SignExtendedNumber rhs)
135
    {
136 1
        if (rhs.isMinimum())
137 1
            return negative ? SignExtendedNumber(value, false) : max();
138
        else
139 1
            return this + (-rhs);
140
    }
141

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

147
        /* Special handling for zeros:
148
            INT65_MIN * 0 = 0
149
            INT65_MIN * + = INT65_MIN
150
            INT65_MIN * - = INT65_MAX
151
            0 * anything = 0
152
        */
153 1
        if (value == 0)
154
        {
155 1
            if (!negative)
156 1
                return this;
157 0
            else if (rhs.negative)
158 0
                return max();
159
            else
160 0
                return rhs.value == 0 ? rhs : this;
161
        }
162 1
        else if (rhs.value == 0)
163 1
            return rhs * this; // don't duplicate the symmetric case.
164

165 1
        SignExtendedNumber rv;
166
        // these are != 0 now surely.
167 1
        uinteger_t tAbs = copySign(value, negative);
168 1
        uinteger_t aAbs = copySign(rhs.value, rhs.negative);
169 1
        rv.negative = negative != rhs.negative;
170 1
        if (ulong.max / tAbs < aAbs)
171 1
            rv.value = rv.negative - 1;
172
        else
173 1
            rv.value = copySign(tAbs * aAbs, rv.negative);
174 1
        return rv;
175
    }
176

177
    SignExtendedNumber opBinary(string op : "/")(SignExtendedNumber rhs)
178
    {
179
        /* special handling for zeros:
180
            INT65_MIN / INT65_MIN = 1
181
            anything / INT65_MIN = 0
182
            + / 0 = INT65_MAX  (eh?)
183
            - / 0 = INT65_MIN  (eh?)
184
        */
185 1
        if (rhs.value == 0)
186
        {
187 0
            if (rhs.negative)
188 0
                return SignExtendedNumber(value == 0 && negative);
189
            else
190 0
                return extreme(negative);
191
        }
192

193 1
        uinteger_t aAbs = copySign(rhs.value, rhs.negative);
194 1
        uinteger_t rvVal;
195

196 1
        if (!isMinimum())
197 1
            rvVal = copySign(value, negative) / aAbs;
198
        // Special handling for INT65_MIN
199
        //  if the denominator is not a power of 2, it is same as ulong.max / x.
200 0
        else if (aAbs & (aAbs - 1))
201 0
            rvVal = ulong.max / aAbs;
202
        // otherwise, it's the same as reversing the bits of x.
203
        else
204
        {
205 0
            if (aAbs == 1)
206 0
                return extreme(!rhs.negative);
207 0
            rvVal = 1UL << 63;
208 0
            aAbs >>= 1;
209 0
            if (aAbs & 0xAAAAAAAAAAAAAAAAUL) rvVal >>= 1;
210 0
            if (aAbs & 0xCCCCCCCCCCCCCCCCUL) rvVal >>= 2;
211 0
            if (aAbs & 0xF0F0F0F0F0F0F0F0UL) rvVal >>= 4;
212 0
            if (aAbs & 0xFF00FF00FF00FF00UL) rvVal >>= 8;
213 0
            if (aAbs & 0xFFFF0000FFFF0000UL) rvVal >>= 16;
214 0
            if (aAbs & 0xFFFFFFFF00000000UL) rvVal >>= 32;
215
        }
216 1
        bool rvNeg = negative != rhs.negative;
217 1
        rvVal = copySign(rvVal, rvNeg);
218

219 1
        return SignExtendedNumber(rvVal, rvVal != 0 && rvNeg);
220
    }
221

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

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

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

241
        rvVal = copySign(rvVal, negative);
242
        return SignExtendedNumber(rvVal, rvVal != 0 && negative);
243
    }
244

245
    SignExtendedNumber opBinary(string op : "<<")(SignExtendedNumber rhs)
246
    {
247
        // assume left-shift the shift-amount is always unsigned. Thus negative
248
        //  shifts will give huge result.
249 1
        if (value == 0)
250 1
            return this;
251 1
        else if (rhs.negative)
252 0
            return extreme(negative);
253

254 1
        uinteger_t v = copySign(value, negative);
255

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

259
        // Why is this a size_t? Looks like a bug.
260 1
        size_t r, s;
261

262 1
        r = (v > 0xFFFFFFFFUL) << 5; v >>= r;
263 1
        s = (v > 0xFFFFUL    ) << 4; v >>= s; r |= s;
264 1
        s = (v > 0xFFUL      ) << 3; v >>= s; r |= s;
265 1
        s = (v > 0xFUL       ) << 2; v >>= s; r |= s;
266 1
        s = (v > 0x3UL       ) << 1; v >>= s; r |= s;
267 1
                                               r |= (v >> 1);
268

269 1
        uinteger_t allowableShift = 63 - r;
270 1
        if (rhs.value > allowableShift)
271 1
            return extreme(negative);
272
        else
273 1
            return SignExtendedNumber(value << rhs.value, negative);
274
    }
275

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

283 1
        uinteger_t x = value ^ -cast(int)negative;
284 1
        x >>= rhs.value;
285 1
        return SignExtendedNumber(x ^ -cast(int)negative, negative);
286
    }
287

288
    SignExtendedNumber opBinary(string op : "^^")(SignExtendedNumber rhs)
289
    {
290
        // Not yet implemented
291
        assert(0);
292
    }
293
}
294

295
struct IntRange
296
{
297
    SignExtendedNumber imin, imax;
298

299 1
    this(IntRange another)
300
    {
301 1
        imin = another.imin;
302 1
        imax = another.imax;
303
    }
304

305 1
    this(SignExtendedNumber a)
306
    {
307 1
        imin = a;
308 1
        imax = a;
309
    }
310

311 1
    this(SignExtendedNumber lower, SignExtendedNumber upper)
312
    {
313 1
        imin = lower;
314 1
        imax = upper;
315
    }
316

317
    static IntRange fromType(Type type)
318
    {
319 1
        return fromType(type, type.isunsigned());
320
    }
321

322
    static IntRange fromType(Type type, bool isUnsigned)
323
    {
324 1
        if (!type.isintegral() || type.toBasetype().ty == Tvector)
325 1
            return widest();
326

327 1
        uinteger_t mask = type.sizemask();
328 1
        auto lower = SignExtendedNumber(0);
329 1
        auto upper = SignExtendedNumber(mask);
330 1
        if (type.toBasetype().ty == Tdchar)
331 1
            upper.value = 0x10FFFFUL;
332 1
        else if (!isUnsigned)
333
        {
334 1
            lower.value = ~(mask >> 1);
335 1
            lower.negative = true;
336 1
            upper.value = (mask >> 1);
337
        }
338 1
        return IntRange(lower, upper);
339
    }
340

341
    static IntRange fromNumbers2(SignExtendedNumber* numbers)
342
    {
343 1
        if (numbers[0] < numbers[1])
344 1
            return IntRange(numbers[0], numbers[1]);
345
        else
346 1
            return IntRange(numbers[1], numbers[0]);
347
    }
348

349
    static IntRange fromNumbers4(SignExtendedNumber* numbers)
350
    {
351 1
        IntRange ab = fromNumbers2(numbers);
352 1
        IntRange cd = fromNumbers2(numbers + 2);
353 1
        if (cd.imin < ab.imin)
354 1
            ab.imin = cd.imin;
355 1
        if (cd.imax > ab.imax)
356 1
            ab.imax = cd.imax;
357 1
        return ab;
358
    }
359

360
    static IntRange widest()
361
    {
362 1
        return IntRange(SignExtendedNumber.min(), SignExtendedNumber.max());
363
    }
364

365
    IntRange castSigned(uinteger_t mask)
366
    {
367
        // .... 0x1e7f ] [0x1e80 .. 0x1f7f] [0x1f80 .. 0x7f] [0x80 .. 0x17f] [0x180 ....
368
        //
369
        // regular signed type. We use a technique similar to the unsigned version,
370
        //  but the chunk has to be offset by 1/2 of the range.
371 1
        uinteger_t halfChunkMask = mask >> 1;
372 1
        uinteger_t minHalfChunk = imin.value & ~halfChunkMask;
373 1
        uinteger_t maxHalfChunk = imax.value & ~halfChunkMask;
374 1
        int minHalfChunkNegativity = imin.negative; // 1 = neg, 0 = nonneg, -1 = chunk containing ::max
375 1
        int maxHalfChunkNegativity = imax.negative;
376 1
        if (minHalfChunk & mask)
377
        {
378 1
            minHalfChunk += halfChunkMask + 1;
379 1
            if (minHalfChunk == 0)
380 1
                --minHalfChunkNegativity;
381
        }
382 1
        if (maxHalfChunk & mask)
383
        {
384 1
            maxHalfChunk += halfChunkMask + 1;
385 1
            if (maxHalfChunk == 0)
386 1
                --maxHalfChunkNegativity;
387
        }
388 1
        if (minHalfChunk == maxHalfChunk && minHalfChunkNegativity == maxHalfChunkNegativity)
389
        {
390 1
            imin.value &= mask;
391 1
            imax.value &= mask;
392
            // sign extend if necessary.
393 1
            imin.negative = (imin.value & ~halfChunkMask) != 0;
394 1
            imax.negative = (imax.value & ~halfChunkMask) != 0;
395 1
            halfChunkMask += 1;
396 1
            imin.value = (imin.value ^ halfChunkMask) - halfChunkMask;
397 1
            imax.value = (imax.value ^ halfChunkMask) - halfChunkMask;
398
        }
399
        else
400
        {
401 1
            imin = SignExtendedNumber(~halfChunkMask, true);
402 1
            imax = SignExtendedNumber(halfChunkMask, false);
403
        }
404 1
        return this;
405
    }
406

407
    IntRange castUnsigned(uinteger_t mask)
408
    {
409
        // .... 0x1eff ] [0x1f00 .. 0x1fff] [0 .. 0xff] [0x100 .. 0x1ff] [0x200 ....
410
        //
411
        // regular unsigned type. We just need to see if ir steps across the
412
        //  boundary of validRange. If yes, ir will represent the whole validRange,
413
        //  otherwise, we just take the modulus.
414
        // e.g. [0x105, 0x107] & 0xff == [5, 7]
415
        //      [0x105, 0x207] & 0xff == [0, 0xff]
416 1
        uinteger_t minChunk = imin.value & ~mask;
417 1
        uinteger_t maxChunk = imax.value & ~mask;
418 1
        if (minChunk == maxChunk && imin.negative == imax.negative)
419
        {
420 1
            imin.value &= mask;
421 1
            imax.value &= mask;
422
        }
423
        else
424
        {
425 1
            imin.value = 0;
426 1
            imax.value = mask;
427
        }
428 1
        imin.negative = imax.negative = false;
429 1
        return this;
430
    }
431

432
    IntRange castDchar()
433
    {
434
        // special case for dchar. Casting to dchar means "I'll ignore all
435
        //  invalid characters."
436 1
        castUnsigned(0xFFFFFFFFUL);
437 1
        if (imin.value > 0x10FFFFUL) // ??
438 0
            imin.value = 0x10FFFFUL; // ??
439 1
        if (imax.value > 0x10FFFFUL)
440 0
            imax.value = 0x10FFFFUL;
441 1
        return this;
442
    }
443

444
    IntRange _cast(Type type)
445
    {
446 1
        if (!type.isintegral() || type.toBasetype().ty == Tvector)
447 1
            return this;
448 1
        else if (!type.isunsigned())
449 1
            return castSigned(type.sizemask());
450 1
        else if (type.toBasetype().ty == Tdchar)
451 1
            return castDchar();
452
        else
453 1
            return castUnsigned(type.sizemask());
454
    }
455

456
    IntRange castUnsigned(Type type)
457
    {
458 1
        if (!type.isintegral() || type.toBasetype().ty == Tvector)
459 0
            return castUnsigned(ulong.max);
460 1
        else if (type.toBasetype().ty == Tdchar)
461 0
            return castDchar();
462
        else
463 1
            return castUnsigned(type.sizemask());
464
    }
465

466
    bool contains(IntRange a)
467
    {
468 1
        return imin <= a.imin && imax >= a.imax;
469
    }
470

471
    bool containsZero() const
472
    {
473 0
        return (imin.negative && !imax.negative)
474 0
            || (!imin.negative && imin.value == 0);
475
    }
476

477
    IntRange absNeg() const
478
    {
479 1
        if (imax.negative)
480 0
            return this;
481 1
        else if (!imin.negative)
482 1
            return IntRange(-imax, -imin);
483
        else
484
        {
485 1
            SignExtendedNumber imaxAbsNeg = -imax;
486 1
            return IntRange(imaxAbsNeg < imin ? imaxAbsNeg : imin,
487
                            SignExtendedNumber(0));
488
        }
489
    }
490

491
    IntRange unionWith(const ref IntRange other) const
492
    {
493 1
        return IntRange(imin < other.imin ? imin : other.imin,
494 1
                        imax > other.imax ? imax : other.imax);
495
    }
496

497
    void unionOrAssign(IntRange other, ref bool union_)
498
    {
499 1
        if (!union_ || imin > other.imin)
500 1
            imin = other.imin;
501 1
        if (!union_ || imax < other.imax)
502 1
            imax = other.imax;
503 1
        union_ = true;
504
    }
505

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

515
    void splitBySign(ref IntRange negRange, ref bool hasNegRange, ref IntRange nonNegRange, ref bool hasNonNegRange) const
516
    {
517 0
        hasNegRange = imin.negative;
518 0
        if (hasNegRange)
519
        {
520 0
            negRange.imin = imin;
521 0
            negRange.imax = imax.negative ? imax : SignExtendedNumber(-1, true);
522
        }
523 0
        hasNonNegRange = !imax.negative;
524 0
        if (hasNonNegRange)
525
        {
526 0
            nonNegRange.imin = imin.negative ? SignExtendedNumber(0) : imin;
527 0
            nonNegRange.imax = imax;
528
        }
529
    }
530

531
    IntRange opUnary(string op:"~")() const
532
    {
533 1
        return IntRange(~imax, ~imin);
534
    }
535

536
    IntRange opUnary(string op : "-")()
537
    {
538 1
        return IntRange(-imax, -imin);
539
    }
540

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

551 1
        IntRange l = IntRange(this);
552 1
        IntRange r = IntRange(rhs);
553

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

560
            // only negative numbers for minimum
561 1
            l.imax.value = -1;
562 1
            l.imax.negative = true;
563 1
            r.imax.value = -1;
564 1
            r.imax.negative = true;
565

566 1
            return IntRange(minAnd(l, r), max);
567
        }
568
        else
569
        {
570
            // only one interval spans [-1,0]
571 1
            if ((l.imin.negative ^ l.imax.negative) == 1)
572
            {
573 1
                swap(l, r); // r spans [-1,0]
574
            }
575

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

581 1
            auto min = minAndNeg < minAndPos ? minAndNeg : minAndPos;
582 1
            auto max = maxAndNeg > maxAndPos ? maxAndNeg : maxAndPos;
583

584 1
            auto range = IntRange(min, max);
585 1
            return range;
586
        }
587
    }
588

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

599 1
        IntRange l = IntRange(this);
600 1
        IntRange r = IntRange(rhs);
601

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

608
            // only negative numbers for minimum
609 1
            l.imin.value = 0;
610 1
            l.imin.negative = false;
611 1
            r.imin.value = 0;
612 1
            r.imin.negative = false;
613

614 1
            return IntRange(min, maxOr(l, r));
615
        }
616
        else
617
        {
618
            // only one interval spans [-1,0]
619 1
            if ((imin.negative ^ imax.negative) == 1)
620
            {
621 1
                swap(l, r); // r spans [-1,0]
622
            }
623

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

629 1
            auto min = minOrNeg < minOrPos ? minOrNeg : minOrPos;
630 1
            auto max = maxOrNeg > maxOrPos ? maxOrNeg : maxOrPos;
631

632 1
            auto range = IntRange(min, max);
633 1
            return range;
634
        }
635
    }
636

637
    IntRange opBinary(string op : "^")(IntRange rhs) const
638
    {
639 1
        return this & ~rhs | ~this & rhs;
640
    }
641

642
    IntRange opBinary(string op : "+")(IntRange rhs)
643
    {
644 1
        return IntRange(imin + rhs.imin, imax + rhs.imax);
645
    }
646

647
    IntRange opBinary(string op : "-")(IntRange rhs)
648
    {
649 1
        return IntRange(imin - rhs.imax, imax - rhs.imin);
650
    }
651

652
    IntRange opBinary(string op : "*")(IntRange rhs)
653
    {
654
        // [a,b] * [c,d] = [min (ac, ad, bc, bd), max (ac, ad, bc, bd)]
655 1
        SignExtendedNumber[4] bdy;
656 1
        bdy[0] = imin * rhs.imin;
657 1
        bdy[1] = imin * rhs.imax;
658 1
        bdy[2] = imax * rhs.imin;
659 1
        bdy[3] = imax * rhs.imax;
660 1
        return IntRange.fromNumbers4(bdy.ptr);
661
    }
662

663
    IntRange opBinary(string op : "/")(IntRange rhs)
664
    {
665
        // Handle divide by 0
666 1
        if (rhs.imax.value == 0 && rhs.imin.value == 0)
667 0
            return widest();
668

669
        // Don't treat the whole range as divide by 0 if only one end of a range is 0.
670
        // Issue 15289
671 1
        if (rhs.imax.value == 0)
672
        {
673 0
            rhs.imax.value--;
674
        }
675 1
        else if(rhs.imin.value == 0)
676
        {
677 1
            rhs.imin.value++;
678
        }
679

680 1
        if (!imin.negative && !imax.negative && !rhs.imin.negative && !rhs.imax.negative)
681
        {
682 1
            return IntRange(imin / rhs.imax, imax / rhs.imin);
683
        }
684
        else
685
        {
686
            // [a,b] / [c,d] = [min (a/c, a/d, b/c, b/d), max (a/c, a/d, b/c, b/d)]
687 1
            SignExtendedNumber[4] bdy;
688 1
            bdy[0] = imin / rhs.imin;
689 1
            bdy[1] = imin / rhs.imax;
690 1
            bdy[2] = imax / rhs.imin;
691 1
            bdy[3] = imax / rhs.imax;
692

693 1
            return IntRange.fromNumbers4(bdy.ptr);
694
        }
695
    }
696

697
    IntRange opBinary(string op : "%")(IntRange rhs)
698
    {
699 1
        IntRange irNum = this;
700 1
        IntRange irDen = rhs.absNeg();
701

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

706
             case 1. [500, 1700] % [7, 23] (numerator is always positive)
707
                 = [0, 22]
708
             case 2. [-500, 1700] % [7, 23] (numerator can be negative)
709
                 = [-22, 22]
710
             case 3. [-1700, -500] % [7, 23] (numerator is always negative)
711
                 = [-22, 0]
712

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

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

720 1
        if (!irNum.imin.negative)
721
        {
722 1
            irNum.imin.value = 0;
723
        }
724 1
        else if (irNum.imin < irDen.imin)
725
        {
726 1
            irNum.imin = irDen.imin;
727
        }
728

729 1
        if (irNum.imax.negative)
730
        {
731 1
            irNum.imax.negative = false;
732 1
            irNum.imax.value = 0;
733
        }
734 1
        else if (irNum.imax > irDen.imax)
735
        {
736 1
            irNum.imax = irDen.imax;
737
        }
738

739 1
        return irNum;
740
    }
741

742
    IntRange opBinary(string op : "<<")(IntRange rhs)
743
    {
744 1
        if (rhs.imin.negative)
745
        {
746 1
            rhs = IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
747
        }
748

749 1
        SignExtendedNumber lower = imin << (imin.negative ? rhs.imax : rhs.imin);
750 1
        SignExtendedNumber upper = imax << (imax.negative ? rhs.imin : rhs.imax);
751

752 1
        return IntRange(lower, upper);
753
    }
754

755
    IntRange opBinary(string op : ">>")(IntRange rhs)
756
    {
757 1
        if (rhs.imin.negative)
758
        {
759 1
            rhs = IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
760
        }
761

762 1
        SignExtendedNumber lower = imin >> (imin.negative ? rhs.imin : rhs.imax);
763 1
        SignExtendedNumber upper = imax >> (imax.negative ? rhs.imax : rhs.imin);
764

765 1
        return IntRange(lower, upper);
766
    }
767

768
    IntRange opBinary(string op : ">>>")(IntRange rhs)
769
    {
770 1
        if (rhs.imin.negative)
771
        {
772 1
            rhs = IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
773
        }
774

775 1
        return IntRange(imin >> rhs.imax, imax >> rhs.imin);
776
    }
777

778
    IntRange opBinary(string op : "^^")(IntRange rhs)
779
    {
780
        // Not yet implemented
781
        assert(0);
782
    }
783

784
private:
785
    // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
786
    // https://github.com/tgehr/d-compiler/blob/master/vrange.d
787
    static SignExtendedNumber maxOr(const IntRange lhs, const IntRange rhs)
788
    {
789 1
        uinteger_t x = 0;
790 1
        auto sign = false;
791 1
        auto xor = lhs.imax.value ^ rhs.imax.value;
792 1
        auto and = lhs.imax.value & rhs.imax.value;
793 1
        auto lhsc = IntRange(lhs);
794 1
        auto rhsc = IntRange(rhs);
795

796
        // Sign bit not part of the .value so we need an extra iteration
797 1
        if (lhsc.imax.negative ^ rhsc.imax.negative)
798
        {
799 1
            sign = true;
800 1
            if (lhsc.imax.negative)
801
            {
802 1
                if (!lhsc.imin.negative)
803
                {
804 1
                    lhsc.imin.value = 0;
805
                }
806 1
                if (!rhsc.imin.negative)
807
                {
808 1
                    rhsc.imin.value = 0;
809
                }
810
            }
811
        }
812 1
        else if (lhsc.imin.negative & rhsc.imin.negative)
813
        {
814 1
            sign = true;
815
        }
816 1
        else if (lhsc.imax.negative & rhsc.imax.negative)
817
        {
818 1
            return SignExtendedNumber(-1, false);
819
        }
820

821 1
        for (uinteger_t d = 1LU << (8 * uinteger_t.sizeof - 1); d; d >>= 1)
822
        {
823 1
            if (xor & d)
824
            {
825 1
                x |= d;
826 1
                if (lhsc.imax.value & d)
827
                {
828 1
                    if (~lhsc.imin.value & d)
829
                    {
830 1
                        lhsc.imin.value = 0;
831
                    }
832
                }
833
                else
834
                {
835 1
                    if (~rhsc.imin.value & d)
836
                    {
837 1
                        rhsc.imin.value = 0;
838
                    }
839
                }
840
            }
841 1
            else if (lhsc.imin.value & rhsc.imin.value & d)
842
            {
843 1
                x |= d;
844
            }
845 1
            else if (and & d)
846
            {
847 1
                x |= (d << 1) - 1;
848 1
                break;
849
            }
850
        }
851

852 1
        auto range = SignExtendedNumber(x, sign);
853 1
        return range;
854
    }
855

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

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

872 1
        if (lhsc.imax.negative & rhsc.imax.negative)
873
        {
874 1
            sign = true;
875
        }
876

877 1
        for (uinteger_t d = 1LU << (8 * uinteger_t.sizeof - 1); d; d >>= 1)
878
        {
879 1
            if (lhsc.imax.value & rhsc.imax.value & d)
880
            {
881 1
                x |= d;
882 1
                if (~lhsc.imin.value & d)
883
                {
884 1
                    lhsc.imin.value = 0;
885
                }
886 1
                if (~rhsc.imin.value & d)
887
                {
888 1
                    rhsc.imin.value = 0;
889
                }
890
            }
891 1
            else if (~lhsc.imin.value & d && lhsc.imax.value & d)
892
            {
893 1
                lhsc.imax.value |= d - 1;
894
            }
895 1
            else if (~rhsc.imin.value & d && rhsc.imax.value & d)
896
            {
897 1
                rhsc.imax.value |= d - 1;
898
            }
899
        }
900

901 1
        auto range = SignExtendedNumber(x, sign);
902 1
        return range;
903
    }
904

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

912
    static swap(ref IntRange a, ref IntRange b)
913
    {
914 1
        auto aux = a;
915 1
        a = b;
916 1
        b = aux;
917
    }
918
}

Read our documentation on viewing source code .

Loading