1 /* Operations with long integers. 2 Copyright (C) 2006, 2007, 2009 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it 7 under the terms of the GNU General Public License as published by the 8 Free Software Foundation; either version 3, or (at your option) any 9 later version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 #include "config.h" 21 #include "system.h" 22 #include "coretypes.h" 23 #include "tm.h" 24 #include "tree.h" 25 26 /* Returns mask for PREC bits. */ 27 28 double_int 29 double_int_mask (unsigned prec) 30 { 31 unsigned HOST_WIDE_INT m; 32 double_int mask; 33 34 if (prec > HOST_BITS_PER_WIDE_INT) 35 { 36 prec -= HOST_BITS_PER_WIDE_INT; 37 m = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1; 38 mask.high = (HOST_WIDE_INT) m; 39 mask.low = ALL_ONES; 40 } 41 else 42 { 43 mask.high = 0; 44 mask.low = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1; 45 } 46 47 return mask; 48 } 49 50 /* Clears the bits of CST over the precision PREC. If UNS is false, the bits 51 outside of the precision are set to the sign bit (i.e., the PREC-th one), 52 otherwise they are set to zero. 53 54 This corresponds to returning the value represented by PREC lowermost bits 55 of CST, with the given signedness. */ 56 57 double_int 58 double_int_ext (double_int cst, unsigned prec, bool uns) 59 { 60 if (uns) 61 return double_int_zext (cst, prec); 62 else 63 return double_int_sext (cst, prec); 64 } 65 66 /* The same as double_int_ext with UNS = true. */ 67 68 double_int 69 double_int_zext (double_int cst, unsigned prec) 70 { 71 double_int mask = double_int_mask (prec); 72 double_int r; 73 74 r.low = cst.low & mask.low; 75 r.high = cst.high & mask.high; 76 77 return r; 78 } 79 80 /* The same as double_int_ext with UNS = false. */ 81 82 double_int 83 double_int_sext (double_int cst, unsigned prec) 84 { 85 double_int mask = double_int_mask (prec); 86 double_int r; 87 unsigned HOST_WIDE_INT snum; 88 89 if (prec <= HOST_BITS_PER_WIDE_INT) 90 snum = cst.low; 91 else 92 { 93 prec -= HOST_BITS_PER_WIDE_INT; 94 snum = (unsigned HOST_WIDE_INT) cst.high; 95 } 96 if (((snum >> (prec - 1)) & 1) == 1) 97 { 98 r.low = cst.low | ~mask.low; 99 r.high = cst.high | ~mask.high; 100 } 101 else 102 { 103 r.low = cst.low & mask.low; 104 r.high = cst.high & mask.high; 105 } 106 107 return r; 108 } 109 110 /* Constructs long integer from tree CST. The extra bits over the precision of 111 the number are filled with sign bit if CST is signed, and with zeros if it 112 is unsigned. */ 113 114 double_int 115 tree_to_double_int (const_tree cst) 116 { 117 /* We do not need to call double_int_restrict here to ensure the semantics as 118 described, as this is the default one for trees. */ 119 return TREE_INT_CST (cst); 120 } 121 122 /* Returns true if CST fits in unsigned HOST_WIDE_INT. */ 123 124 bool 125 double_int_fits_in_uhwi_p (double_int cst) 126 { 127 return cst.high == 0; 128 } 129 130 /* Returns true if CST fits in signed HOST_WIDE_INT. */ 131 132 bool 133 double_int_fits_in_shwi_p (double_int cst) 134 { 135 if (cst.high == 0) 136 return (HOST_WIDE_INT) cst.low >= 0; 137 else if (cst.high == -1) 138 return (HOST_WIDE_INT) cst.low < 0; 139 else 140 return false; 141 } 142 143 /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in 144 unsigned HOST_WIDE_INT if UNS is true. */ 145 146 bool 147 double_int_fits_in_hwi_p (double_int cst, bool uns) 148 { 149 if (uns) 150 return double_int_fits_in_uhwi_p (cst); 151 else 152 return double_int_fits_in_shwi_p (cst); 153 } 154 155 /* Returns value of CST as a signed number. CST must satisfy 156 double_int_fits_in_shwi_p. */ 157 158 HOST_WIDE_INT 159 double_int_to_shwi (double_int cst) 160 { 161 return (HOST_WIDE_INT) cst.low; 162 } 163 164 /* Returns value of CST as an unsigned number. CST must satisfy 165 double_int_fits_in_uhwi_p. */ 166 167 unsigned HOST_WIDE_INT 168 double_int_to_uhwi (double_int cst) 169 { 170 return cst.low; 171 } 172 173 /* Returns A * B. */ 174 175 double_int 176 double_int_mul (double_int a, double_int b) 177 { 178 double_int ret; 179 mul_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high); 180 return ret; 181 } 182 183 /* Returns A + B. */ 184 185 double_int 186 double_int_add (double_int a, double_int b) 187 { 188 double_int ret; 189 add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high); 190 return ret; 191 } 192 193 /* Returns -A. */ 194 195 double_int 196 double_int_neg (double_int a) 197 { 198 double_int ret; 199 neg_double (a.low, a.high, &ret.low, &ret.high); 200 return ret; 201 } 202 203 /* Returns A / B (computed as unsigned depending on UNS, and rounded as 204 specified by CODE). CODE is enum tree_code in fact, but double_int.h 205 must be included before tree.h. The remainder after the division is 206 stored to MOD. */ 207 208 double_int 209 double_int_divmod (double_int a, double_int b, bool uns, unsigned code, 210 double_int *mod) 211 { 212 double_int ret; 213 214 div_and_round_double ((enum tree_code) code, uns, a.low, a.high, 215 b.low, b.high, &ret.low, &ret.high, 216 &mod->low, &mod->high); 217 return ret; 218 } 219 220 /* The same as double_int_divmod with UNS = false. */ 221 222 double_int 223 double_int_sdivmod (double_int a, double_int b, unsigned code, double_int *mod) 224 { 225 return double_int_divmod (a, b, false, code, mod); 226 } 227 228 /* The same as double_int_divmod with UNS = true. */ 229 230 double_int 231 double_int_udivmod (double_int a, double_int b, unsigned code, double_int *mod) 232 { 233 return double_int_divmod (a, b, true, code, mod); 234 } 235 236 /* Returns A / B (computed as unsigned depending on UNS, and rounded as 237 specified by CODE). CODE is enum tree_code in fact, but double_int.h 238 must be included before tree.h. */ 239 240 double_int 241 double_int_div (double_int a, double_int b, bool uns, unsigned code) 242 { 243 double_int mod; 244 245 return double_int_divmod (a, b, uns, code, &mod); 246 } 247 248 /* The same as double_int_div with UNS = false. */ 249 250 double_int 251 double_int_sdiv (double_int a, double_int b, unsigned code) 252 { 253 return double_int_div (a, b, false, code); 254 } 255 256 /* The same as double_int_div with UNS = true. */ 257 258 double_int 259 double_int_udiv (double_int a, double_int b, unsigned code) 260 { 261 return double_int_div (a, b, true, code); 262 } 263 264 /* Returns A % B (computed as unsigned depending on UNS, and rounded as 265 specified by CODE). CODE is enum tree_code in fact, but double_int.h 266 must be included before tree.h. */ 267 268 double_int 269 double_int_mod (double_int a, double_int b, bool uns, unsigned code) 270 { 271 double_int mod; 272 273 double_int_divmod (a, b, uns, code, &mod); 274 return mod; 275 } 276 277 /* The same as double_int_mod with UNS = false. */ 278 279 double_int 280 double_int_smod (double_int a, double_int b, unsigned code) 281 { 282 return double_int_mod (a, b, false, code); 283 } 284 285 /* The same as double_int_mod with UNS = true. */ 286 287 double_int 288 double_int_umod (double_int a, double_int b, unsigned code) 289 { 290 return double_int_mod (a, b, true, code); 291 } 292 293 /* Constructs tree in type TYPE from with value given by CST. Signedness of CST 294 is assumed to be the same as the signedness of TYPE. */ 295 296 tree 297 double_int_to_tree (tree type, double_int cst) 298 { 299 cst = double_int_ext (cst, TYPE_PRECISION (type), TYPE_UNSIGNED (type)); 300 301 return build_int_cst_wide (type, cst.low, cst.high); 302 } 303 304 /* Returns true if CST fits into range of TYPE. Signedness of CST is assumed 305 to be the same as the signedness of TYPE. */ 306 307 bool 308 double_int_fits_to_tree_p (const_tree type, double_int cst) 309 { 310 double_int ext = double_int_ext (cst, 311 TYPE_PRECISION (type), 312 TYPE_UNSIGNED (type)); 313 314 return double_int_equal_p (cst, ext); 315 } 316 317 /* Returns true if CST is negative. Of course, CST is considered to 318 be signed. */ 319 320 bool 321 double_int_negative_p (double_int cst) 322 { 323 return cst.high < 0; 324 } 325 326 /* Returns -1 if A < B, 0 if A == B and 1 if A > B. Signedness of the 327 comparison is given by UNS. */ 328 329 int 330 double_int_cmp (double_int a, double_int b, bool uns) 331 { 332 if (uns) 333 return double_int_ucmp (a, b); 334 else 335 return double_int_scmp (a, b); 336 } 337 338 /* Compares two unsigned values A and B. Returns -1 if A < B, 0 if A == B, 339 and 1 if A > B. */ 340 341 int 342 double_int_ucmp (double_int a, double_int b) 343 { 344 if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high) 345 return -1; 346 if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high) 347 return 1; 348 if (a.low < b.low) 349 return -1; 350 if (a.low > b.low) 351 return 1; 352 353 return 0; 354 } 355 356 /* Compares two signed values A and B. Returns -1 if A < B, 0 if A == B, 357 and 1 if A > B. */ 358 359 int 360 double_int_scmp (double_int a, double_int b) 361 { 362 if (a.high < b.high) 363 return -1; 364 if (a.high > b.high) 365 return 1; 366 if (a.low < b.low) 367 return -1; 368 if (a.low > b.low) 369 return 1; 370 371 return 0; 372 } 373 374 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it. */ 375 376 static unsigned 377 double_int_split_digit (double_int *cst, unsigned base) 378 { 379 unsigned HOST_WIDE_INT resl, reml; 380 HOST_WIDE_INT resh, remh; 381 382 div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0, 383 &resl, &resh, &reml, &remh); 384 cst->high = resh; 385 cst->low = resl; 386 387 return reml; 388 } 389 390 /* Dumps CST to FILE. If UNS is true, CST is considered to be unsigned, 391 otherwise it is signed. */ 392 393 void 394 dump_double_int (FILE *file, double_int cst, bool uns) 395 { 396 unsigned digits[100], n; 397 int i; 398 399 if (double_int_zero_p (cst)) 400 { 401 fprintf (file, "0"); 402 return; 403 } 404 405 if (!uns && double_int_negative_p (cst)) 406 { 407 fprintf (file, "-"); 408 cst = double_int_neg (cst); 409 } 410 411 for (n = 0; !double_int_zero_p (cst); n++) 412 digits[n] = double_int_split_digit (&cst, 10); 413 for (i = n - 1; i >= 0; i--) 414 fprintf (file, "%u", digits[i]); 415 } 416 417 418 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed 419 otherwise. */ 420 421 void 422 mpz_set_double_int (mpz_t result, double_int val, bool uns) 423 { 424 bool negate = false; 425 unsigned HOST_WIDE_INT vp[2]; 426 427 if (!uns && double_int_negative_p (val)) 428 { 429 negate = true; 430 val = double_int_neg (val); 431 } 432 433 vp[0] = val.low; 434 vp[1] = (unsigned HOST_WIDE_INT) val.high; 435 mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp); 436 437 if (negate) 438 mpz_neg (result, result); 439 } 440 441 /* Returns VAL converted to TYPE. If WRAP is true, then out-of-range 442 values of VAL will be wrapped; otherwise, they will be set to the 443 appropriate minimum or maximum TYPE bound. */ 444 445 double_int 446 mpz_get_double_int (const_tree type, mpz_t val, bool wrap) 447 { 448 unsigned HOST_WIDE_INT *vp; 449 size_t count, numb; 450 double_int res; 451 452 if (!wrap) 453 { 454 mpz_t min, max; 455 456 mpz_init (min); 457 mpz_init (max); 458 get_type_static_bounds (type, min, max); 459 460 if (mpz_cmp (val, min) < 0) 461 mpz_set (val, min); 462 else if (mpz_cmp (val, max) > 0) 463 mpz_set (val, max); 464 465 mpz_clear (min); 466 mpz_clear (max); 467 } 468 469 /* Determine the number of unsigned HOST_WIDE_INT that are required 470 for representing the value. The code to calculate count is 471 extracted from the GMP manual, section "Integer Import and Export": 472 http://gmplib.org/manual/Integer-Import-and-Export.html */ 473 numb = 8*sizeof(HOST_WIDE_INT); 474 count = (mpz_sizeinbase (val, 2) + numb-1) / numb; 475 if (count < 2) 476 count = 2; 477 vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof(HOST_WIDE_INT)); 478 479 vp[0] = 0; 480 vp[1] = 0; 481 mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val); 482 483 gcc_assert (wrap || count <= 2); 484 485 res.low = vp[0]; 486 res.high = (HOST_WIDE_INT) vp[1]; 487 488 res = double_int_ext (res, TYPE_PRECISION (type), TYPE_UNSIGNED (type)); 489 if (mpz_sgn (val) < 0) 490 res = double_int_neg (res); 491 492 return res; 493 } 494