]>
Commit | Line | Data |
---|---|---|
b4c522fa IB |
1 | |
2 | /* Compiler implementation of the D programming language | |
8e788ac6 | 3 | * Copyright (C) 1999-2020 by The D Language Foundation, All Rights Reserved |
b4c522fa IB |
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 | ||
f9ab59ff | 11 | #include "root/dsystem.h" |
b4c522fa IB |
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`. | |
19 | static 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 | ||
31 | SignExtendedNumber SignExtendedNumber::fromInteger(uinteger_t value_) | |
32 | { | |
33 | return SignExtendedNumber(value_, value_ >> 63); | |
34 | } | |
35 | ||
36 | bool SignExtendedNumber::operator==(const SignExtendedNumber& a) const | |
37 | { | |
38 | return value == a.value && negative == a.negative; | |
39 | } | |
40 | ||
41 | bool SignExtendedNumber::operator<(const SignExtendedNumber& a) const | |
42 | { | |
43 | return (negative && !a.negative) | |
44 | || (negative == a.negative && value < a.value); | |
45 | } | |
46 | ||
47 | SignExtendedNumber SignExtendedNumber::extreme(bool minimum) | |
48 | { | |
49 | return SignExtendedNumber(minimum-1, minimum); | |
50 | } | |
51 | ||
52 | SignExtendedNumber SignExtendedNumber::max() | |
53 | { | |
54 | return SignExtendedNumber(UINT64_MAX, false); | |
55 | } | |
56 | ||
9d7d33ac IB |
57 | SignExtendedNumber& 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 | ||
69 | SignExtendedNumber SignExtendedNumber::operator~() const | |
70 | { | |
71 | if (~value == 0) | |
72 | return SignExtendedNumber(~value); | |
73 | else | |
74 | return SignExtendedNumber(~value, !negative); | |
75 | } | |
76 | ||
b4c522fa IB |
77 | SignExtendedNumber SignExtendedNumber::operator-() const |
78 | { | |
79 | if (value == 0) | |
80 | return SignExtendedNumber(-negative); | |
81 | else | |
82 | return SignExtendedNumber(-value, !negative); | |
83 | } | |
84 | ||
9d7d33ac | 85 | SignExtendedNumber SignExtendedNumber::operator&(const SignExtendedNumber& rhs) const |
b4c522fa | 86 | { |
9d7d33ac IB |
87 | return SignExtendedNumber(value & rhs.value); |
88 | } | |
89 | ||
90 | SignExtendedNumber SignExtendedNumber::operator|(const SignExtendedNumber& rhs) const | |
91 | { | |
92 | return SignExtendedNumber(value | rhs.value); | |
93 | } | |
94 | ||
95 | SignExtendedNumber SignExtendedNumber::operator^(const SignExtendedNumber& rhs) const | |
96 | { | |
97 | return SignExtendedNumber(value ^ rhs.value); | |
98 | } | |
99 | ||
100 | SignExtendedNumber 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) | |
b4c522fa IB |
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 | ||
9d7d33ac | 112 | SignExtendedNumber SignExtendedNumber::operator-(const SignExtendedNumber& rhs) const |
b4c522fa | 113 | { |
9d7d33ac | 114 | if (rhs.isMinimum()) |
b4c522fa IB |
115 | return negative ? SignExtendedNumber(value, false) : max(); |
116 | else | |
9d7d33ac | 117 | return *this + (-rhs); |
b4c522fa IB |
118 | } |
119 | ||
9d7d33ac | 120 | SignExtendedNumber SignExtendedNumber::operator*(const SignExtendedNumber& rhs) const |
b4c522fa IB |
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; | |
9d7d33ac | 135 | else if (rhs.negative) |
b4c522fa IB |
136 | return max(); |
137 | else | |
9d7d33ac | 138 | return rhs.value == 0 ? rhs : *this; |
b4c522fa | 139 | } |
9d7d33ac IB |
140 | else if (rhs.value == 0) |
141 | return rhs * *this; // don't duplicate the symmetric case. | |
b4c522fa IB |
142 | |
143 | SignExtendedNumber rv; | |
144 | // these are != 0 now surely. | |
145 | uinteger_t tAbs = copySign(value, negative); | |
9d7d33ac IB |
146 | uinteger_t aAbs = copySign(rhs.value, rhs.negative); |
147 | rv.negative = negative != rhs.negative; | |
b4c522fa IB |
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 | ||
9d7d33ac | 155 | SignExtendedNumber SignExtendedNumber::operator/(const SignExtendedNumber& rhs) const |
b4c522fa IB |
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 | */ | |
9d7d33ac | 163 | if (rhs.value == 0) |
b4c522fa | 164 | { |
9d7d33ac | 165 | if (rhs.negative) |
b4c522fa IB |
166 | return SignExtendedNumber(value == 0 && negative); |
167 | else | |
168 | return extreme(negative); | |
169 | } | |
170 | ||
9d7d33ac | 171 | uinteger_t aAbs = copySign(rhs.value, rhs.negative); |
b4c522fa IB |
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) | |
9d7d33ac | 184 | return extreme(!rhs.negative); |
b4c522fa IB |
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 | } | |
9d7d33ac | 194 | bool rvNeg = negative != rhs.negative; |
b4c522fa IB |
195 | rvVal = copySign(rvVal, rvNeg); |
196 | ||
197 | return SignExtendedNumber(rvVal, rvVal != 0 && rvNeg); | |
198 | } | |
199 | ||
9d7d33ac | 200 | SignExtendedNumber SignExtendedNumber::operator%(const SignExtendedNumber& rhs) const |
b4c522fa | 201 | { |
9d7d33ac IB |
202 | if (rhs.value == 0) |
203 | return !rhs.negative ? rhs : isMinimum() ? SignExtendedNumber(0) : *this; | |
b4c522fa | 204 | |
9d7d33ac | 205 | uinteger_t aAbs = copySign(rhs.value, rhs.negative); |
b4c522fa IB |
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 | ||
9d7d33ac | 223 | SignExtendedNumber SignExtendedNumber::operator<<(const SignExtendedNumber& rhs) const |
b4c522fa IB |
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; | |
9d7d33ac | 229 | else if (rhs.negative) |
b4c522fa IB |
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; | |
9d7d33ac | 248 | if (rhs.value > allowableShift) |
b4c522fa IB |
249 | return extreme(negative); |
250 | else | |
9d7d33ac | 251 | return SignExtendedNumber(value << rhs.value, negative); |
b4c522fa IB |
252 | } |
253 | ||
9d7d33ac | 254 | SignExtendedNumber SignExtendedNumber::operator>>(const SignExtendedNumber& rhs) const |
b4c522fa | 255 | { |
9d7d33ac | 256 | if (rhs.negative || rhs.value > 63) |
b4c522fa IB |
257 | return negative ? SignExtendedNumber(-1, true) : SignExtendedNumber(0); |
258 | else if (isMinimum()) | |
9d7d33ac | 259 | return rhs.value == 0 ? *this : SignExtendedNumber(-1ULL << (64 - rhs.value), true); |
b4c522fa IB |
260 | |
261 | uinteger_t x = value ^ -negative; | |
9d7d33ac | 262 | x >>= rhs.value; |
b4c522fa IB |
263 | return SignExtendedNumber(x ^ -negative, negative); |
264 | } | |
265 | ||
266 | ||
267 | //==================== IntRange ================================================ | |
268 | ||
269 | IntRange IntRange::widest() | |
270 | { | |
271 | return IntRange(SignExtendedNumber::min(), SignExtendedNumber::max()); | |
272 | } | |
273 | ||
274 | IntRange IntRange::fromType(Type *type) | |
275 | { | |
276 | return fromType(type, type->isunsigned()); | |
277 | } | |
278 | ||
279 | IntRange IntRange::fromType(Type *type, bool isUnsigned) | |
280 | { | |
70106db9 | 281 | if (!type->isintegral() || type->toBasetype()->ty == Tvector) |
b4c522fa IB |
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 | ||
297 | IntRange 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 | } | |
304 | IntRange 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 | ||
315 | bool IntRange::contains(const IntRange& a) const | |
316 | { | |
317 | return imin <= a.imin && imax >= a.imax; | |
318 | } | |
319 | ||
320 | bool IntRange::containsZero() const | |
321 | { | |
322 | return (imin.negative && !imax.negative) | |
323 | || (!imin.negative && imin.value == 0); | |
324 | } | |
325 | ||
326 | IntRange& 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 | ||
351 | IntRange& 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 | ||
393 | IntRange& 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 | ||
405 | IntRange& IntRange::cast(Type *type) | |
406 | { | |
70106db9 | 407 | if (!type->isintegral() || type->toBasetype()->ty == Tvector) |
b4c522fa IB |
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 | ||
417 | IntRange& IntRange::castUnsigned(Type *type) | |
418 | { | |
70106db9 | 419 | if (!type->isintegral() || type->toBasetype()->ty == Tvector) |
b4c522fa IB |
420 | return castUnsigned(UINT64_MAX); |
421 | else if (type->toBasetype()->ty == Tdchar) | |
422 | return castDchar(); | |
423 | else | |
424 | return castUnsigned(type->sizemask()); | |
425 | } | |
426 | ||
427 | IntRange 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 | ||
441 | IntRange 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 | ||
447 | void 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 | ||
456 | void 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 | ||
9d7d33ac IB |
473 | IntRange IntRange::operator~() const |
474 | { | |
475 | return IntRange(~imax, ~imin); | |
476 | } | |
477 | ||
478 | IntRange IntRange::operator-() const | |
479 | { | |
480 | return IntRange(-imax, -imin); | |
481 | } | |
482 | ||
483 | IntRange 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 | ||
528 | IntRange 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 | ||
573 | IntRange IntRange::operator^(const IntRange& rhs) const | |
574 | { | |
575 | return (*this & (~rhs)) | (~(*this) & rhs); | |
576 | } | |
577 | ||
578 | IntRange IntRange::operator+(const IntRange& rhs) const | |
579 | { | |
580 | return IntRange(imin + rhs.imin, imax + rhs.imax); | |
581 | } | |
582 | ||
583 | IntRange IntRange::operator-(const IntRange& rhs) const | |
584 | { | |
585 | return IntRange(imin - rhs.imax, imax - rhs.imin); | |
586 | } | |
587 | ||
588 | IntRange 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 | ||
599 | IntRange 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 | } | |
5b74dd0a | 613 | else if (r.imin.value == 0) |
9d7d33ac IB |
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 | ||
635 | IntRange 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 | ||
680 | IntRange 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 | ||
694 | IntRange 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 | ||
708 | SignExtendedNumber 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 | ||
776 | SignExtendedNumber IntRange::minOr(const IntRange& lhs, const IntRange& rhs) | |
777 | { | |
778 | return ~maxAnd(~lhs, ~rhs); | |
779 | } | |
780 | ||
781 | SignExtendedNumber 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 | ||
820 | SignExtendedNumber IntRange::minAnd(const IntRange& lhs, const IntRange& rhs) | |
821 | { | |
822 | return ~maxOr(~lhs, ~rhs); | |
823 | } | |
824 | ||
825 | void IntRange::swap(IntRange& a, IntRange& b) | |
826 | { | |
827 | IntRange aux = a; | |
828 | a = b; | |
829 | b = aux; | |
830 | } | |
b4c522fa IB |
831 | |
832 | const 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 | } |