2 * Implement $(LINK2 https://digitalmars.com/articles/b62.html, Value Range Propagation).
4 * Copyright: Copyright (C) 1999-2023 by The D Language Foundation, All Rights Reserved
5 * Authors: $(LINK2 https://www.digitalmars.com, Walter Bright)
6 * License: $(LINK2 https://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
14 import core
.stdc
.stdio
;
18 import dmd
.expression
;
21 private uinteger_t
copySign(uinteger_t x
, bool sign
) @safe
23 // return sign ? -x : x;
24 return (x
- cast(uinteger_t
)sign
) ^
-cast(uinteger_t
)sign
;
27 struct SignExtendedNumber
32 static SignExtendedNumber
fromInteger(uinteger_t value_
) @safe
34 return SignExtendedNumber(value_
, value_
>> 63);
37 static SignExtendedNumber
extreme(bool minimum
) @safe
39 return SignExtendedNumber(minimum
- 1, minimum
);
42 static SignExtendedNumber
max() @safe
44 return SignExtendedNumber(ulong.max
, false);
47 static SignExtendedNumber
min() @safe
49 return SignExtendedNumber(0, true);
52 bool isMinimum() const @safe
54 return negative
&& value
== 0;
57 bool opEquals(const ref SignExtendedNumber a
) const @safe
59 return value
== a
.value
&& negative
== a
.negative
;
62 int opCmp(const ref SignExtendedNumber a
) const @safe
64 if (negative
!= a
.negative
)
73 else if (value
> a
.value
)
79 SignExtendedNumber
opUnary(string op
: "++")()
81 if (value
!= ulong.max
)
91 SignExtendedNumber
opUnary(string op
: "~")() const
94 return SignExtendedNumber(~value
);
96 return SignExtendedNumber(~value
, !negative
);
99 SignExtendedNumber
opUnary(string op
: "-")() const
102 return SignExtendedNumber(-cast(ulong)negative
);
104 return SignExtendedNumber(-value
, !negative
);
107 SignExtendedNumber
opBinary(string op
: "&")(SignExtendedNumber rhs
) const
109 return SignExtendedNumber(value
& rhs
.value
);
112 SignExtendedNumber
opBinary(string op
: "|")(SignExtendedNumber rhs
)
114 return SignExtendedNumber(value | rhs
.value
);
117 SignExtendedNumber
opBinary(string op
: "^")(SignExtendedNumber rhs
)
119 return SignExtendedNumber(value ^ rhs
.value
);
122 SignExtendedNumber
opBinary(string op
: "+")(SignExtendedNumber rhs
)
124 uinteger_t sum
= value
+ rhs
.value
;
125 bool carry
= sum
< value
&& sum
< rhs
.value
;
126 if (negative
!= rhs
.negative
)
127 return SignExtendedNumber(sum
, !carry
);
129 return SignExtendedNumber(carry ? sum
: 0, true);
131 return SignExtendedNumber(carry ?
ulong.max
: sum
, false);
135 SignExtendedNumber
opBinary(string op
: "-")(SignExtendedNumber rhs
)
138 return negative ?
SignExtendedNumber(value
, false) : max();
140 return this + (-rhs
);
143 SignExtendedNumber
opBinary(string op
: "*")(SignExtendedNumber rhs
)
145 // perform *saturated* multiplication, otherwise we may get bogus ranges
146 // like 0x10 * 0x10 == 0x100 == 0.
148 /* Special handling for zeros:
150 INT65_MIN * + = INT65_MIN
151 INT65_MIN * - = INT65_MAX
158 else if (rhs
.negative
)
161 return rhs
.value
== 0 ? rhs
: this;
163 else if (rhs
.value
== 0)
164 return rhs
* this; // don't duplicate the symmetric case.
166 SignExtendedNumber rv
;
167 // these are != 0 now surely.
168 uinteger_t tAbs
= copySign(value
, negative
);
169 uinteger_t aAbs
= copySign(rhs
.value
, rhs
.negative
);
170 rv
.negative
= negative
!= rhs
.negative
;
171 if (ulong.max
/ tAbs
< aAbs
)
172 rv
.value
= rv
.negative
- 1;
174 rv
.value
= copySign(tAbs
* aAbs
, rv
.negative
);
178 SignExtendedNumber
opBinary(string op
: "/")(SignExtendedNumber rhs
)
180 /* special handling for zeros:
181 INT65_MIN / INT65_MIN = 1
182 anything / INT65_MIN = 0
183 + / 0 = INT65_MAX (eh?)
184 - / 0 = INT65_MIN (eh?)
189 return SignExtendedNumber(value
== 0 && negative
);
191 return extreme(negative
);
194 uinteger_t aAbs
= copySign(rhs
.value
, rhs
.negative
);
198 rvVal
= copySign(value
, negative
) / aAbs
;
199 // Special handling for INT65_MIN
200 // if the denominator is not a power of 2, it is same as ulong.max / x.
201 else if (aAbs
& (aAbs
- 1))
202 rvVal
= ulong.max
/ aAbs
;
203 // otherwise, it's the same as reversing the bits of x.
207 return extreme(!rhs
.negative
);
210 if (aAbs
& 0xAAAAAAAAAAAAAAAAUL
) rvVal
>>= 1;
211 if (aAbs
& 0xCCCCCCCCCCCCCCCCUL
) rvVal
>>= 2;
212 if (aAbs
& 0xF0F0F0F0F0F0F0F0UL
) rvVal
>>= 4;
213 if (aAbs
& 0xFF00FF00FF00FF00UL
) rvVal
>>= 8;
214 if (aAbs
& 0xFFFF0000FFFF0000UL
) rvVal
>>= 16;
215 if (aAbs
& 0xFFFFFFFF00000000UL
) rvVal
>>= 32;
217 bool rvNeg
= negative
!= rhs
.negative
;
218 rvVal
= copySign(rvVal
, rvNeg
);
220 return SignExtendedNumber(rvVal
, rvVal
!= 0 && rvNeg
);
223 SignExtendedNumber
opBinary(string op
: "%")(SignExtendedNumber rhs
)
226 return !rhs
.negative ? rhs
: isMinimum() ?
SignExtendedNumber(0) : this;
228 uinteger_t aAbs
= copySign(rhs
.value
, rhs
.negative
);
231 // a % b == sgn(a) * abs(a) % abs(b).
233 rvVal
= copySign(value
, negative
) % aAbs
;
234 // Special handling for INT65_MIN
235 // if the denominator is not a power of 2, it is same as ulong.max % x + 1.
236 else if (aAbs
& (aAbs
- 1))
237 rvVal
= ulong.max
% aAbs
+ 1;
238 // otherwise, the modulus is trivially zero.
242 rvVal
= copySign(rvVal
, negative
);
243 return SignExtendedNumber(rvVal
, rvVal
!= 0 && negative
);
246 SignExtendedNumber
opBinary(string op
: "<<")(SignExtendedNumber rhs
)
248 // assume left-shift the shift-amount is always unsigned. Thus negative
249 // shifts will give huge result.
252 else if (rhs
.negative
)
253 return extreme(negative
);
255 uinteger_t v
= copySign(value
, negative
);
257 // compute base-2 log of 'v' to determine the maximum allowed bits to shift.
258 // Ref: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
260 // Why is this a size_t? Looks like a bug.
263 r
= (v
> 0xFFFFFFFFUL
) << 5; v
>>= r
;
264 s
= (v
> 0xFFFFUL
) << 4; v
>>= s
; r |
= s
;
265 s
= (v
> 0xFFUL
) << 3; v
>>= s
; r |
= s
;
266 s
= (v
> 0xFUL
) << 2; v
>>= s
; r |
= s
;
267 s
= (v
> 0x3UL
) << 1; v
>>= s
; r |
= s
;
270 uinteger_t allowableShift
= 63 - r
;
271 if (rhs
.value
> allowableShift
)
272 return extreme(negative
);
274 return SignExtendedNumber(value
<< rhs
.value
, negative
);
277 SignExtendedNumber
opBinary(string op
: ">>")(SignExtendedNumber rhs
)
279 if (rhs
.negative || rhs
.value
> 63)
280 return negative ?
SignExtendedNumber(-1, true) : SignExtendedNumber(0);
281 else if (isMinimum())
282 return rhs
.value
== 0 ?
this : SignExtendedNumber(-1UL << (64 - rhs
.value
), true);
284 uinteger_t x
= value ^
-cast(int)negative
;
286 return SignExtendedNumber(x ^
-cast(int)negative
, negative
);
289 SignExtendedNumber
opBinary(string op
: "^^")(SignExtendedNumber rhs
)
291 // Not yet implemented
298 SignExtendedNumber imin
, imax
;
300 this(IntRange another
) @safe
306 this(SignExtendedNumber a
) @safe
312 this(SignExtendedNumber lower
, SignExtendedNumber upper
) @safe
318 static IntRange
fromType(Type type
)
320 return fromType(type
, type
.isunsigned());
323 static IntRange
fromType(Type type
, bool isUnsigned
)
325 if (!type
.isintegral() || type
.toBasetype().ty
== Tvector
)
328 uinteger_t mask
= type
.sizemask();
329 auto lower
= SignExtendedNumber(0);
330 auto upper
= SignExtendedNumber(mask
);
331 if (type
.toBasetype().ty
== Tdchar
)
332 upper
.value
= 0x10FFFFUL
;
333 else if (!isUnsigned
)
335 lower
.value
= ~(mask
>> 1);
336 lower
.negative
= true;
337 upper
.value
= (mask
>> 1);
339 return IntRange(lower
, upper
);
342 static IntRange
fromNumbers2(SignExtendedNumber
* numbers
)
344 if (numbers
[0] < numbers
[1])
345 return IntRange(numbers
[0], numbers
[1]);
347 return IntRange(numbers
[1], numbers
[0]);
350 static IntRange
fromNumbers4(SignExtendedNumber
* numbers
)
352 IntRange ab
= fromNumbers2(numbers
);
353 IntRange cd
= fromNumbers2(numbers
+ 2);
354 if (cd
.imin
< ab
.imin
)
356 if (cd
.imax
> ab
.imax
)
361 static IntRange
widest() @safe
363 return IntRange(SignExtendedNumber
.min(), SignExtendedNumber
.max());
366 IntRange
castSigned(uinteger_t mask
) @safe
368 // .... 0x1e7f ] [0x1e80 .. 0x1f7f] [0x1f80 .. 0x7f] [0x80 .. 0x17f] [0x180 ....
370 // regular signed type. We use a technique similar to the unsigned version,
371 // but the chunk has to be offset by 1/2 of the range.
372 uinteger_t halfChunkMask
= mask
>> 1;
373 uinteger_t minHalfChunk
= imin
.value
& ~halfChunkMask
;
374 uinteger_t maxHalfChunk
= imax
.value
& ~halfChunkMask
;
375 int minHalfChunkNegativity
= imin
.negative
; // 1 = neg, 0 = nonneg, -1 = chunk containing ::max
376 int maxHalfChunkNegativity
= imax
.negative
;
377 if (minHalfChunk
& mask
)
379 minHalfChunk
+= halfChunkMask
+ 1;
380 if (minHalfChunk
== 0)
381 --minHalfChunkNegativity
;
383 if (maxHalfChunk
& mask
)
385 maxHalfChunk
+= halfChunkMask
+ 1;
386 if (maxHalfChunk
== 0)
387 --maxHalfChunkNegativity
;
389 if (minHalfChunk
== maxHalfChunk
&& minHalfChunkNegativity
== maxHalfChunkNegativity
)
393 // sign extend if necessary.
394 imin
.negative
= (imin
.value
& ~halfChunkMask
) != 0;
395 imax
.negative
= (imax
.value
& ~halfChunkMask
) != 0;
397 imin
.value
= (imin
.value ^ halfChunkMask
) - halfChunkMask
;
398 imax
.value
= (imax
.value ^ halfChunkMask
) - halfChunkMask
;
402 imin
= SignExtendedNumber(~halfChunkMask
, true);
403 imax
= SignExtendedNumber(halfChunkMask
, false);
408 IntRange
castUnsigned(uinteger_t mask
) @safe
410 // .... 0x1eff ] [0x1f00 .. 0x1fff] [0 .. 0xff] [0x100 .. 0x1ff] [0x200 ....
412 // regular unsigned type. We just need to see if ir steps across the
413 // boundary of validRange. If yes, ir will represent the whole validRange,
414 // otherwise, we just take the modulus.
415 // e.g. [0x105, 0x107] & 0xff == [5, 7]
416 // [0x105, 0x207] & 0xff == [0, 0xff]
417 uinteger_t minChunk
= imin
.value
& ~mask
;
418 uinteger_t maxChunk
= imax
.value
& ~mask
;
419 if (minChunk
== maxChunk
&& imin
.negative
== imax
.negative
)
429 imin
.negative
= imax
.negative
= false;
433 IntRange
castDchar() @safe
435 // special case for dchar. Casting to dchar means "I'll ignore all
436 // invalid characters."
437 castUnsigned(0xFFFFFFFFUL
);
438 if (imin
.value
> 0x10FFFFUL
) // ??
439 imin
.value
= 0x10FFFFUL
; // ??
440 if (imax
.value
> 0x10FFFFUL
)
441 imax
.value
= 0x10FFFFUL
;
445 IntRange
_cast(Type type
)
447 if (!type
.isintegral() || type
.toBasetype().ty
== Tvector
)
449 else if (!type
.isunsigned())
450 return castSigned(type
.sizemask());
451 else if (type
.toBasetype().ty
== Tdchar
)
454 return castUnsigned(type
.sizemask());
457 IntRange
castUnsigned(Type type
)
459 if (!type
.isintegral() || type
.toBasetype().ty
== Tvector
)
460 return castUnsigned(ulong.max
);
461 else if (type
.toBasetype().ty
== Tdchar
)
464 return castUnsigned(type
.sizemask());
467 bool contains(IntRange a
) @safe
469 return imin
<= a
.imin
&& imax
>= a
.imax
;
472 bool containsZero() const @safe
474 return (imin
.negative
&& !imax
.negative
)
475 ||
(!imin
.negative
&& imin
.value
== 0);
478 IntRange
absNeg() const @safe
482 else if (!imin
.negative
)
483 return IntRange(-imax
, -imin
);
486 SignExtendedNumber imaxAbsNeg
= -imax
;
487 return IntRange(imaxAbsNeg
< imin ? imaxAbsNeg
: imin
,
488 SignExtendedNumber(0));
492 IntRange
unionWith(const ref IntRange other
) const @safe
494 return IntRange(imin
< other
.imin ? imin
: other
.imin
,
495 imax
> other
.imax ? imax
: other
.imax
);
498 void unionOrAssign(IntRange other
, ref bool union_
) @safe
500 if (!union_ || imin
> other
.imin
)
502 if (!union_ || imax
< other
.imax
)
507 ref const(IntRange
) dump(const(char)* funcName
, Expression e
) const return
509 printf("[(%c)%#018llx, (%c)%#018llx] @ %s ::: %s\n",
510 imin
.negative?
'-':'+', cast(ulong)imin
.value
,
511 imax
.negative?
'-':'+', cast(ulong)imax
.value
,
512 funcName
, e
.toChars());
516 void splitBySign(ref IntRange negRange
, ref bool hasNegRange
, ref IntRange nonNegRange
, ref bool hasNonNegRange
) const @safe
518 hasNegRange
= imin
.negative
;
521 negRange
.imin
= imin
;
522 negRange
.imax
= imax
.negative ? imax
: SignExtendedNumber(-1, true);
524 hasNonNegRange
= !imax
.negative
;
527 nonNegRange
.imin
= imin
.negative ?
SignExtendedNumber(0) : imin
;
528 nonNegRange
.imax
= imax
;
532 IntRange
opUnary(string op
:"~")() const
534 return IntRange(~imax
, ~imin
);
537 IntRange
opUnary(string op
: "-")()
539 return IntRange(-imax
, -imin
);
542 // Credits to Timon Gehr for the algorithms for &, |
543 // https://github.com/tgehr/d-compiler/blob/master/vrange.d
544 IntRange
opBinary(string op
: "&")(IntRange rhs
) const
546 // unsigned or identical sign bits
547 if ((imin
.negative ^ imax
.negative
) != 1 && (rhs
.imin
.negative ^ rhs
.imax
.negative
) != 1)
549 return IntRange(minAnd(this, rhs
), maxAnd(this, rhs
));
552 IntRange l
= IntRange(this);
553 IntRange r
= IntRange(rhs
);
555 // both intervals span [-1,0]
556 if ((imin
.negative ^ imax
.negative
) == 1 && (rhs
.imin
.negative ^ rhs
.imax
.negative
) == 1)
558 // cannot be larger than either l.max or r.max, set the other one to -1
559 SignExtendedNumber max
= l
.imax
.value
> r
.imax
.value ? l
.imax
: r
.imax
;
561 // only negative numbers for minimum
563 l
.imax
.negative
= true;
565 r
.imax
.negative
= true;
567 return IntRange(minAnd(l
, r
), max
);
571 // only one interval spans [-1,0]
572 if ((l
.imin
.negative ^ l
.imax
.negative
) == 1)
574 swap(l
, r
); // r spans [-1,0]
577 auto minAndNeg
= minAnd(l
, IntRange(r
.imin
, SignExtendedNumber(-1)));
578 auto minAndPos
= minAnd(l
, IntRange(SignExtendedNumber(0), r
.imax
));
579 auto maxAndNeg
= maxAnd(l
, IntRange(r
.imin
, SignExtendedNumber(-1)));
580 auto maxAndPos
= maxAnd(l
, IntRange(SignExtendedNumber(0), r
.imax
));
582 auto min
= minAndNeg
< minAndPos ? minAndNeg
: minAndPos
;
583 auto max
= maxAndNeg
> maxAndPos ? maxAndNeg
: maxAndPos
;
585 auto range
= IntRange(min
, max
);
590 // Credits to Timon Gehr for the algorithms for &, |
591 // https://github.com/tgehr/d-compiler/blob/master/vrange.d
592 IntRange
opBinary(string op
: "|")(IntRange rhs
) const
594 // unsigned or identical sign bits:
595 if ((imin
.negative ^ imax
.negative
) == 0 && (rhs
.imin
.negative ^ rhs
.imax
.negative
) == 0)
597 return IntRange(minOr(this, rhs
), maxOr(this, rhs
));
600 IntRange l
= IntRange(this);
601 IntRange r
= IntRange(rhs
);
603 // both intervals span [-1,0]
604 if ((imin
.negative ^ imax
.negative
) == 1 && (rhs
.imin
.negative ^ rhs
.imax
.negative
) == 1)
606 // cannot be smaller than either l.min or r.min, set the other one to 0
607 SignExtendedNumber min
= l
.imin
.value
< r
.imin
.value ? l
.imin
: r
.imin
;
609 // only negative numbers for minimum
611 l
.imin
.negative
= false;
613 r
.imin
.negative
= false;
615 return IntRange(min
, maxOr(l
, r
));
619 // only one interval spans [-1,0]
620 if ((imin
.negative ^ imax
.negative
) == 1)
622 swap(l
, r
); // r spans [-1,0]
625 auto minOrNeg
= minOr(l
, IntRange(r
.imin
, SignExtendedNumber(-1)));
626 auto minOrPos
= minOr(l
, IntRange(SignExtendedNumber(0), r
.imax
));
627 auto maxOrNeg
= maxOr(l
, IntRange(r
.imin
, SignExtendedNumber(-1)));
628 auto maxOrPos
= maxOr(l
, IntRange(SignExtendedNumber(0), r
.imax
));
630 auto min
= minOrNeg
< minOrPos ? minOrNeg
: minOrPos
;
631 auto max
= maxOrNeg
> maxOrPos ? maxOrNeg
: maxOrPos
;
633 auto range
= IntRange(min
, max
);
638 IntRange
opBinary(string op
: "^")(IntRange rhs
) const
640 return this & ~rhs |
~this & rhs
;
643 IntRange
opBinary(string op
: "+")(IntRange rhs
)
645 return IntRange(imin
+ rhs
.imin
, imax
+ rhs
.imax
);
648 IntRange
opBinary(string op
: "-")(IntRange rhs
)
650 return IntRange(imin
- rhs
.imax
, imax
- rhs
.imin
);
653 IntRange
opBinary(string op
: "*")(IntRange rhs
)
655 // [a,b] * [c,d] = [min (ac, ad, bc, bd), max (ac, ad, bc, bd)]
656 SignExtendedNumber
[4] bdy
;
657 bdy
[0] = imin
* rhs
.imin
;
658 bdy
[1] = imin
* rhs
.imax
;
659 bdy
[2] = imax
* rhs
.imin
;
660 bdy
[3] = imax
* rhs
.imax
;
661 return IntRange
.fromNumbers4(bdy
.ptr
);
664 IntRange
opBinary(string op
: "/")(IntRange rhs
)
666 // Handle divide by 0
667 if (rhs
.imax
.value
== 0 && rhs
.imin
.value
== 0)
670 // Don't treat the whole range as divide by 0 if only one end of a range is 0.
672 if (rhs
.imax
.value
== 0)
676 else if(rhs
.imin
.value
== 0)
681 if (!imin
.negative
&& !imax
.negative
&& !rhs
.imin
.negative
&& !rhs
.imax
.negative
)
683 return IntRange(imin
/ rhs
.imax
, imax
/ rhs
.imin
);
687 // [a,b] / [c,d] = [min (a/c, a/d, b/c, b/d), max (a/c, a/d, b/c, b/d)]
688 SignExtendedNumber
[4] bdy
;
689 bdy
[0] = imin
/ rhs
.imin
;
690 bdy
[1] = imin
/ rhs
.imax
;
691 bdy
[2] = imax
/ rhs
.imin
;
692 bdy
[3] = imax
/ rhs
.imax
;
694 return IntRange
.fromNumbers4(bdy
.ptr
);
698 IntRange
opBinary(string op
: "%")(IntRange rhs
)
700 IntRange irNum
= this;
701 IntRange irDen
= rhs
.absNeg();
704 due to the rules of D (C)'s % operator, we need to consider the cases
705 separately in different range of signs.
707 case 1. [500, 1700] % [7, 23] (numerator is always positive)
709 case 2. [-500, 1700] % [7, 23] (numerator can be negative)
711 case 3. [-1700, -500] % [7, 23] (numerator is always negative)
714 the number 22 is the maximum absolute value in the denomator's range. We
715 don't care about divide by zero.
718 irDen
.imin
= irDen
.imin
+ SignExtendedNumber(1);
719 irDen
.imax
= -irDen
.imin
;
721 if (!irNum
.imin
.negative
)
723 irNum
.imin
.value
= 0;
725 else if (irNum
.imin
< irDen
.imin
)
727 irNum
.imin
= irDen
.imin
;
730 if (irNum
.imax
.negative
)
732 irNum
.imax
.negative
= false;
733 irNum
.imax
.value
= 0;
735 else if (irNum
.imax
> irDen
.imax
)
737 irNum
.imax
= irDen
.imax
;
743 IntRange
opBinary(string op
: "<<")(IntRange rhs
)
745 if (rhs
.imin
.negative
)
747 rhs
= IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
750 SignExtendedNumber lower
= imin
<< (imin
.negative ? rhs
.imax
: rhs
.imin
);
751 SignExtendedNumber upper
= imax
<< (imax
.negative ? rhs
.imin
: rhs
.imax
);
753 return IntRange(lower
, upper
);
756 IntRange
opBinary(string op
: ">>")(IntRange rhs
)
758 if (rhs
.imin
.negative
)
760 rhs
= IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
763 SignExtendedNumber lower
= imin
>> (imin
.negative ? rhs
.imin
: rhs
.imax
);
764 SignExtendedNumber upper
= imax
>> (imax
.negative ? rhs
.imax
: rhs
.imin
);
766 return IntRange(lower
, upper
);
769 IntRange
opBinary(string op
: ">>>")(IntRange rhs
)
771 if (rhs
.imin
.negative
)
773 rhs
= IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
776 return IntRange(imin
>> rhs
.imax
, imax
>> rhs
.imin
);
779 IntRange
opBinary(string op
: "^^")(IntRange rhs
)
781 // Not yet implemented
786 // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
787 // https://github.com/tgehr/d-compiler/blob/master/vrange.d
788 static SignExtendedNumber
maxOr(const IntRange lhs
, const IntRange rhs
) @safe
792 auto xor = lhs
.imax
.value ^ rhs
.imax
.value
;
793 auto and = lhs
.imax
.value
& rhs
.imax
.value
;
794 auto lhsc
= IntRange(lhs
);
795 auto rhsc
= IntRange(rhs
);
797 // Sign bit not part of the .value so we need an extra iteration
798 if (lhsc
.imax
.negative ^ rhsc
.imax
.negative
)
801 if (lhsc
.imax
.negative
)
803 if (!lhsc
.imin
.negative
)
807 if (!rhsc
.imin
.negative
)
813 else if (lhsc
.imin
.negative
& rhsc
.imin
.negative
)
817 else if (lhsc
.imax
.negative
& rhsc
.imax
.negative
)
819 return SignExtendedNumber(-1, false);
822 for (uinteger_t d
= 1LU << (8 * uinteger_t
.sizeof
- 1); d
; d
>>= 1)
827 if (lhsc
.imax
.value
& d
)
829 if (~lhsc
.imin
.value
& d
)
836 if (~rhsc
.imin
.value
& d
)
842 else if (lhsc
.imin
.value
& rhsc
.imin
.value
& d
)
853 auto range
= SignExtendedNumber(x
, sign
);
857 // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
858 // https://github.com/tgehr/d-compiler/blob/master/vrange.d
859 static SignExtendedNumber
minOr(const IntRange lhs
, const IntRange rhs
) @safe
861 return ~maxAnd(~lhs
, ~rhs
);
864 // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
865 // https://github.com/tgehr/d-compiler/blob/master/vrange.d
866 static SignExtendedNumber
maxAnd(const IntRange lhs
, const IntRange rhs
) @safe
870 auto lhsc
= IntRange(lhs
);
871 auto rhsc
= IntRange(rhs
);
873 if (lhsc
.imax
.negative
& rhsc
.imax
.negative
)
878 for (uinteger_t d
= 1LU << (8 * uinteger_t
.sizeof
- 1); d
; d
>>= 1)
880 if (lhsc
.imax
.value
& rhsc
.imax
.value
& d
)
883 if (~lhsc
.imin
.value
& d
)
887 if (~rhsc
.imin
.value
& d
)
892 else if (~lhsc
.imin
.value
& d
&& lhsc
.imax
.value
& d
)
894 lhsc
.imax
.value |
= d
- 1;
896 else if (~rhsc
.imin
.value
& d
&& rhsc
.imax
.value
& d
)
898 rhsc
.imax
.value |
= d
- 1;
902 auto range
= SignExtendedNumber(x
, sign
);
906 // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
907 // https://github.com/tgehr/d-compiler/blob/master/vrange.d
908 static SignExtendedNumber
minAnd(const IntRange lhs
, const IntRange rhs
) @safe
910 return ~maxOr(~lhs
, ~rhs
);
913 static swap(ref IntRange a
, ref IntRange b
)