1 /** 2 * Compiler implementation of the 3 * $(LINK2 http://www.dlang.org, D programming language). 4 * 5 * Copyright: Copyright (c) 1999-2016 by Digital Mars, All Rights Reserved 6 * Authors: $(LINK2 http://www.digitalmars.com, Walter Bright) 7 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0) 8 * Source: $(DMDSRC _intrange.d) 9 */ 10 11 module ddmd.intrange; 12 13 import core.stdc.stdio; 14 15 import ddmd.mtype; 16 import ddmd.expression; 17 import ddmd.globals; 18 19 enum UINT64_MAX = 0xFFFFFFFFFFFFFFFFUL; 20 21 static uinteger_t copySign(uinteger_t x, bool sign) 22 { 23 // return sign ? -x : x; 24 return (x - cast(uinteger_t)sign) ^ -cast(uinteger_t)sign; 25 } 26 27 struct SignExtendedNumber 28 { 29 uinteger_t value; 30 bool negative; 31 static SignExtendedNumber fromInteger(uinteger_t value_) 32 { 33 return SignExtendedNumber(value_, value_ >> 63); 34 } 35 36 static SignExtendedNumber extreme(bool minimum) 37 { 38 return SignExtendedNumber(minimum - 1, minimum); 39 } 40 41 static SignExtendedNumber max() 42 { 43 return SignExtendedNumber(UINT64_MAX, false); 44 } 45 46 static SignExtendedNumber min() 47 { 48 return SignExtendedNumber(0, true); 49 } 50 51 bool isMinimum() const 52 { 53 return negative && value == 0; 54 } 55 56 bool opEquals(const ref SignExtendedNumber a) const 57 { 58 return value == a.value && negative == a.negative; 59 } 60 61 int opCmp(const ref SignExtendedNumber a) const 62 { 63 if (negative != a.negative) 64 { 65 if (negative) 66 return -1; 67 else 68 return 1; 69 } 70 if (value < a.value) 71 return -1; 72 else if (value > a.value) 73 return 1; 74 else 75 return 0; 76 } 77 78 SignExtendedNumber opNeg() const 79 { 80 if (value == 0) 81 return SignExtendedNumber(-cast(ulong)negative); 82 else 83 return SignExtendedNumber(-value, !negative); 84 } 85 86 SignExtendedNumber opAdd(const SignExtendedNumber a) const 87 { 88 uinteger_t sum = value + a.value; 89 bool carry = sum < value && sum < a.value; 90 if (negative != a.negative) 91 return SignExtendedNumber(sum, !carry); 92 else if (negative) 93 return SignExtendedNumber(carry ? sum : 0, true); 94 else 95 return SignExtendedNumber(carry ? UINT64_MAX : sum, false); 96 } 97 98 SignExtendedNumber opSub(const SignExtendedNumber a) const 99 { 100 if (a.isMinimum()) 101 return negative ? SignExtendedNumber(value, false) : max(); 102 else 103 return this + (-a); 104 } 105 106 SignExtendedNumber opMul(const SignExtendedNumber a) const 107 { 108 // perform *saturated* multiplication, otherwise we may get bogus ranges 109 // like 0x10 * 0x10 == 0x100 == 0. 110 111 /* Special handling for zeros: 112 INT65_MIN * 0 = 0 113 INT65_MIN * + = INT65_MIN 114 INT65_MIN * - = INT65_MAX 115 0 * anything = 0 116 */ 117 if (value == 0) 118 { 119 if (!negative) 120 return this; 121 else if (a.negative) 122 return max(); 123 else 124 return a.value == 0 ? a : this; 125 } 126 else if (a.value == 0) 127 return a * this; // don't duplicate the symmetric case. 128 129 SignExtendedNumber rv; 130 // these are != 0 now surely. 131 uinteger_t tAbs = copySign(value, negative); 132 uinteger_t aAbs = copySign(a.value, a.negative); 133 rv.negative = negative != a.negative; 134 if (UINT64_MAX / tAbs < aAbs) 135 rv.value = rv.negative - 1; 136 else 137 rv.value = copySign(tAbs * aAbs, rv.negative); 138 return rv; 139 } 140 141 SignExtendedNumber opDiv(const SignExtendedNumber a) const 142 { 143 /* special handling for zeros: 144 INT65_MIN / INT65_MIN = 1 145 anything / INT65_MIN = 0 146 + / 0 = INT65_MAX (eh?) 147 - / 0 = INT65_MIN (eh?) 148 */ 149 if (a.value == 0) 150 { 151 if (a.negative) 152 return SignExtendedNumber(value == 0 && negative); 153 else 154 return extreme(negative); 155 } 156 157 uinteger_t aAbs = copySign(a.value, a.negative); 158 uinteger_t rvVal; 159 160 if (!isMinimum()) 161 rvVal = copySign(value, negative) / aAbs; 162 // Special handling for INT65_MIN 163 // if the denominator is not a power of 2, it is same as UINT64_MAX / x. 164 else if (aAbs & (aAbs - 1)) 165 rvVal = UINT64_MAX / aAbs; 166 // otherwise, it's the same as reversing the bits of x. 167 else 168 { 169 if (aAbs == 1) 170 return extreme(!a.negative); 171 rvVal = 1UL << 63; 172 aAbs >>= 1; 173 if (aAbs & 0xAAAAAAAAAAAAAAAAUL) rvVal >>= 1; 174 if (aAbs & 0xCCCCCCCCCCCCCCCCUL) rvVal >>= 2; 175 if (aAbs & 0xF0F0F0F0F0F0F0F0UL) rvVal >>= 4; 176 if (aAbs & 0xFF00FF00FF00FF00UL) rvVal >>= 8; 177 if (aAbs & 0xFFFF0000FFFF0000UL) rvVal >>= 16; 178 if (aAbs & 0xFFFFFFFF00000000UL) rvVal >>= 32; 179 } 180 bool rvNeg = negative != a.negative; 181 rvVal = copySign(rvVal, rvNeg); 182 183 return SignExtendedNumber(rvVal, rvVal != 0 && rvNeg); 184 } 185 186 SignExtendedNumber opMod(const SignExtendedNumber a) const 187 { 188 if (a.value == 0) 189 return !a.negative ? a : isMinimum() ? SignExtendedNumber(0) : this; 190 191 uinteger_t aAbs = copySign(a.value, a.negative); 192 uinteger_t rvVal; 193 194 // a % b == sgn(a) * abs(a) % abs(b). 195 if (!isMinimum()) 196 rvVal = copySign(value, negative) % aAbs; 197 // Special handling for INT65_MIN 198 // if the denominator is not a power of 2, it is same as UINT64_MAX%x + 1. 199 else if (aAbs & (aAbs - 1)) 200 rvVal = UINT64_MAX % aAbs + 1; 201 // otherwise, the modulus is trivially zero. 202 else 203 rvVal = 0; 204 205 rvVal = copySign(rvVal, negative); 206 return SignExtendedNumber(rvVal, rvVal != 0 && negative); 207 } 208 209 ref SignExtendedNumber opAddAssign(int a) 210 { 211 assert(a == 1); 212 if (value != UINT64_MAX) 213 ++value; 214 else if (negative) 215 { 216 value = 0; 217 negative = false; 218 } 219 return this; 220 } 221 222 SignExtendedNumber opShl(const SignExtendedNumber a) 223 { 224 // assume left-shift the shift-amount is always unsigned. Thus negative 225 // shifts will give huge result. 226 if (value == 0) 227 return this; 228 else if (a.negative) 229 return extreme(negative); 230 231 uinteger_t v = copySign(value, negative); 232 233 // compute base-2 log of 'v' to determine the maximum allowed bits to shift. 234 // Ref: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog 235 236 // Why is this a size_t? Looks like a bug. 237 size_t r, s; 238 239 r = (v > 0xFFFFFFFFUL) << 5; v >>= r; 240 s = (v > 0xFFFFUL ) << 4; v >>= s; r |= s; 241 s = (v > 0xFFUL ) << 3; v >>= s; r |= s; 242 s = (v > 0xFUL ) << 2; v >>= s; r |= s; 243 s = (v > 0x3UL ) << 1; v >>= s; r |= s; 244 r |= (v >> 1); 245 246 uinteger_t allowableShift = 63 - r; 247 if (a.value > allowableShift) 248 return extreme(negative); 249 else 250 return SignExtendedNumber(value << a.value, negative); 251 } 252 253 SignExtendedNumber opShr(const SignExtendedNumber a) 254 { 255 if (a.negative || a.value > 64) 256 return negative ? SignExtendedNumber(-1, true) : SignExtendedNumber(0); 257 else if (isMinimum()) 258 return a.value == 0 ? this : SignExtendedNumber(-1UL << (64 - a.value), true); 259 260 uinteger_t x = value ^ -cast(int)negative; 261 x >>= a.value; 262 return SignExtendedNumber(x ^ -cast(int)negative, negative); 263 } 264 } 265 266 struct IntRange 267 { 268 SignExtendedNumber imin, imax; 269 270 this(SignExtendedNumber a) 271 { 272 imin = a; 273 imax = a; 274 } 275 276 this(SignExtendedNumber lower, SignExtendedNumber upper) 277 { 278 imin = lower; 279 imax = upper; 280 } 281 282 static IntRange fromType(Type type) 283 { 284 return fromType(type, type.isunsigned()); 285 } 286 287 static IntRange fromType(Type type, bool isUnsigned) 288 { 289 if (!type.isintegral()) 290 return widest(); 291 292 uinteger_t mask = type.sizemask(); 293 auto lower = SignExtendedNumber(0); 294 auto upper = SignExtendedNumber(mask); 295 if (type.toBasetype().ty == Tdchar) 296 upper.value = 0x10FFFFUL; 297 else if (!isUnsigned) 298 { 299 lower.value = ~(mask >> 1); 300 lower.negative = true; 301 upper.value = (mask >> 1); 302 } 303 return IntRange(lower, upper); 304 } 305 306 static IntRange fromNumbers2(SignExtendedNumber* numbers) 307 { 308 if (numbers[0] < numbers[1]) 309 return IntRange(numbers[0], numbers[1]); 310 else 311 return IntRange(numbers[1], numbers[0]); 312 } 313 314 static IntRange fromNumbers4(SignExtendedNumber* numbers) 315 { 316 IntRange ab = fromNumbers2(numbers); 317 IntRange cd = fromNumbers2(numbers + 2); 318 if (cd.imin < ab.imin) 319 ab.imin = cd.imin; 320 if (cd.imax > ab.imax) 321 ab.imax = cd.imax; 322 return ab; 323 } 324 325 static IntRange widest() 326 { 327 return IntRange(SignExtendedNumber.min(), SignExtendedNumber.max()); 328 } 329 330 IntRange castSigned(uinteger_t mask) 331 { 332 // .... 0x1e7f ] [0x1e80 .. 0x1f7f] [0x1f80 .. 0x7f] [0x80 .. 0x17f] [0x180 .... 333 // 334 // regular signed type. We use a technique similar to the unsigned version, 335 // but the chunk has to be offset by 1/2 of the range. 336 uinteger_t halfChunkMask = mask >> 1; 337 uinteger_t minHalfChunk = imin.value & ~halfChunkMask; 338 uinteger_t maxHalfChunk = imax.value & ~halfChunkMask; 339 int minHalfChunkNegativity = imin.negative; // 1 = neg, 0 = nonneg, -1 = chunk containing ::max 340 int maxHalfChunkNegativity = imax.negative; 341 if (minHalfChunk & mask) 342 { 343 minHalfChunk += halfChunkMask + 1; 344 if (minHalfChunk == 0) 345 --minHalfChunkNegativity; 346 } 347 if (maxHalfChunk & mask) 348 { 349 maxHalfChunk += halfChunkMask + 1; 350 if (maxHalfChunk == 0) 351 --maxHalfChunkNegativity; 352 } 353 if (minHalfChunk == maxHalfChunk && minHalfChunkNegativity == maxHalfChunkNegativity) 354 { 355 imin.value &= mask; 356 imax.value &= mask; 357 // sign extend if necessary. 358 imin.negative = (imin.value & ~halfChunkMask) != 0; 359 imax.negative = (imax.value & ~halfChunkMask) != 0; 360 halfChunkMask += 1; 361 imin.value = (imin.value ^ halfChunkMask) - halfChunkMask; 362 imax.value = (imax.value ^ halfChunkMask) - halfChunkMask; 363 } 364 else 365 { 366 imin = SignExtendedNumber(~halfChunkMask, true); 367 imax = SignExtendedNumber(halfChunkMask, false); 368 } 369 return this; 370 } 371 372 IntRange castUnsigned(uinteger_t mask) 373 { 374 // .... 0x1eff ] [0x1f00 .. 0x1fff] [0 .. 0xff] [0x100 .. 0x1ff] [0x200 .... 375 // 376 // regular unsigned type. We just need to see if ir steps across the 377 // boundary of validRange. If yes, ir will represent the whole validRange, 378 // otherwise, we just take the modulus. 379 // e.g. [0x105, 0x107] & 0xff == [5, 7] 380 // [0x105, 0x207] & 0xff == [0, 0xff] 381 uinteger_t minChunk = imin.value & ~mask; 382 uinteger_t maxChunk = imax.value & ~mask; 383 if (minChunk == maxChunk && imin.negative == imax.negative) 384 { 385 imin.value &= mask; 386 imax.value &= mask; 387 } 388 else 389 { 390 imin.value = 0; 391 imax.value = mask; 392 } 393 imin.negative = imax.negative = false; 394 return this; 395 } 396 397 IntRange castDchar() 398 { 399 // special case for dchar. Casting to dchar means "I'll ignore all 400 // invalid characters." 401 castUnsigned(0xFFFFFFFFUL); 402 if (imin.value > 0x10FFFFUL) // ?? 403 imin.value = 0x10FFFFUL; // ?? 404 if (imax.value > 0x10FFFFUL) 405 imax.value = 0x10FFFFUL; 406 return this; 407 } 408 409 IntRange _cast(Type type) 410 { 411 if (!type.isintegral()) 412 return this; 413 else if (!type.isunsigned()) 414 return castSigned(type.sizemask()); 415 else if (type.toBasetype().ty == Tdchar) 416 return castDchar(); 417 else 418 return castUnsigned(type.sizemask()); 419 } 420 421 IntRange castUnsigned(Type type) 422 { 423 if (!type.isintegral()) 424 return castUnsigned(UINT64_MAX); 425 else if (type.toBasetype().ty == Tdchar) 426 return castDchar(); 427 else 428 return castUnsigned(type.sizemask()); 429 } 430 431 bool contains(IntRange a) 432 { 433 return imin <= a.imin && imax >= a.imax; 434 } 435 436 bool containsZero() const 437 { 438 return (imin.negative && !imax.negative) 439 || (!imin.negative && imin.value == 0); 440 } 441 442 IntRange absNeg() const 443 { 444 if (imax.negative) 445 return this; 446 else if (!imin.negative) 447 return IntRange(-imax, -imin); 448 else 449 { 450 SignExtendedNumber imaxAbsNeg = -imax; 451 return IntRange(imaxAbsNeg < imin ? imaxAbsNeg : imin, 452 SignExtendedNumber(0)); 453 } 454 } 455 456 IntRange unionWith(const ref IntRange other) const 457 { 458 return IntRange(imin < other.imin ? imin : other.imin, 459 imax > other.imax ? imax : other.imax); 460 } 461 462 void unionOrAssign(IntRange other, ref bool union_) 463 { 464 if (!union_ || imin > other.imin) 465 imin = other.imin; 466 if (!union_ || imax < other.imax) 467 imax = other.imax; 468 union_ = true; 469 } 470 471 ref const(IntRange) dump(const(char)* funcName, Expression e) const 472 { 473 printf("[(%c)%#018llx, (%c)%#018llx] @ %s ::: %s\n", 474 imin.negative?'-':'+', cast(ulong)imin.value, 475 imax.negative?'-':'+', cast(ulong)imax.value, 476 funcName, e.toChars()); 477 return this; 478 } 479 480 void splitBySign(ref IntRange negRange, ref bool hasNegRange, ref IntRange nonNegRange, ref bool hasNonNegRange) const 481 { 482 hasNegRange = imin.negative; 483 if (hasNegRange) 484 { 485 negRange.imin = imin; 486 negRange.imax = imax.negative ? imax : SignExtendedNumber(-1, true); 487 } 488 hasNonNegRange = !imax.negative; 489 if (hasNonNegRange) 490 { 491 nonNegRange.imin = imin.negative ? SignExtendedNumber(0) : imin; 492 nonNegRange.imax = imax; 493 } 494 } 495 }