1/* Operations with long integers. 2 Copyright (C) 2006, 2007, 2009 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it 7under the terms of the GNU General Public License as published by the 8Free Software Foundation; either version 3, or (at your option) any 9later version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT 12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along 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 28double_int 29double_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 57double_int 58double_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 68double_int 69double_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 82double_int 83double_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 114double_int 115tree_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 124bool 125double_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 132bool 133double_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 146bool 147double_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 158HOST_WIDE_INT 159double_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 167unsigned HOST_WIDE_INT 168double_int_to_uhwi (double_int cst) 169{ 170 return cst.low; 171} 172 173/* Returns A * B. */ 174 175double_int 176double_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 185double_int 186double_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 195double_int 196double_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 208double_int 209double_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 222double_int 223double_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 230double_int 231double_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 240double_int 241double_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 250double_int 251double_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 258double_int 259double_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 268double_int 269double_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 279double_int 280double_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 287double_int 288double_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 296tree 297double_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 307bool 308double_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 320bool 321double_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 329int 330double_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 341int 342double_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 359int 360double_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 376static unsigned 377double_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 393void 394dump_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 421void 422mpz_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 445double_int 446mpz_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