1 | /* Operations with long integers. |
---|---|

2 | Copyright (C) 2006-2017 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 | #ifndef DOUBLE_INT_H |

21 | #define DOUBLE_INT_H |

22 | |

23 | /* A large integer is currently represented as a pair of HOST_WIDE_INTs. |

24 | It therefore represents a number with precision of |

25 | 2 * HOST_BITS_PER_WIDE_INT bits (it is however possible that the |

26 | internal representation will change, if numbers with greater precision |

27 | are needed, so the users should not rely on it). The representation does |

28 | not contain any information about signedness of the represented value, so |

29 | it can be used to represent both signed and unsigned numbers. For |

30 | operations where the results depend on signedness (division, comparisons), |

31 | it must be specified separately. For each such operation, there are three |

32 | versions of the function -- double_int_op, that takes an extra UNS argument |

33 | giving the signedness of the values, and double_int_sop and double_int_uop |

34 | that stand for its specializations for signed and unsigned values. |

35 | |

36 | You may also represent with numbers in smaller precision using double_int. |

37 | You however need to use double_int_ext (that fills in the bits of the |

38 | number over the prescribed precision with zeros or with the sign bit) before |

39 | operations that do not perform arithmetics modulo 2^precision (comparisons, |

40 | division), and possibly before storing the results, if you want to keep |

41 | them in some canonical form). In general, the signedness of double_int_ext |

42 | should match the signedness of the operation. |

43 | |

44 | ??? The components of double_int differ in signedness mostly for |

45 | historical reasons (they replace an older structure used to represent |

46 | numbers with precision higher than HOST_WIDE_INT). It might be less |

47 | confusing to have them both signed or both unsigned. */ |

48 | |

49 | struct double_int |

50 | { |

51 | /* Normally, we would define constructors to create instances. |

52 | Two things prevent us from doing so. |

53 | First, defining a constructor makes the class non-POD in C++03, |

54 | and we certainly want double_int to be a POD. |

55 | Second, the GCC conding conventions prefer explicit conversion, |

56 | and explicit conversion operators are not available until C++11. */ |

57 | |

58 | static double_int from_uhwi (unsigned HOST_WIDE_INT cst); |

59 | static double_int from_shwi (HOST_WIDE_INT cst); |

60 | static double_int from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low); |

61 | |

62 | /* Construct from a fuffer of length LEN. BUFFER will be read according |

63 | to byte endianness and word endianness. */ |

64 | static double_int from_buffer (const unsigned char *buffer, int len); |

65 | |

66 | /* No copy assignment operator or destructor to keep the type a POD. */ |

67 | |

68 | /* There are some special value-creation static member functions. */ |

69 | |

70 | static double_int mask (unsigned prec); |

71 | static double_int max_value (unsigned int prec, bool uns); |

72 | static double_int min_value (unsigned int prec, bool uns); |

73 | |

74 | /* The following functions are mutating operations. */ |

75 | |

76 | double_int &operator ++ (); // prefix |

77 | double_int &operator -- (); // prefix |

78 | double_int &operator *= (double_int); |

79 | double_int &operator += (double_int); |

80 | double_int &operator -= (double_int); |

81 | double_int &operator &= (double_int); |

82 | double_int &operator ^= (double_int); |

83 | double_int &operator |= (double_int); |

84 | |

85 | /* The following functions are non-mutating operations. */ |

86 | |

87 | /* Conversion functions. */ |

88 | |

89 | HOST_WIDE_INT to_shwi () const; |

90 | unsigned HOST_WIDE_INT to_uhwi () const; |

91 | |

92 | /* Conversion query functions. */ |

93 | |

94 | bool fits_uhwi () const; |

95 | bool fits_shwi () const; |

96 | bool fits_hwi (bool uns) const; |

97 | |

98 | /* Attribute query functions. */ |

99 | |

100 | int trailing_zeros () const; |

101 | int popcount () const; |

102 | |

103 | /* Arithmetic query operations. */ |

104 | |

105 | bool multiple_of (double_int, bool, double_int *) const; |

106 | |

107 | /* Arithmetic operation functions. */ |

108 | |

109 | /* The following operations perform arithmetics modulo 2^precision, so you |

110 | do not need to call .ext between them, even if you are representing |

111 | numbers with precision less than HOST_BITS_PER_DOUBLE_INT bits. */ |

112 | |

113 | double_int set_bit (unsigned) const; |

114 | double_int mul_with_sign (double_int, bool unsigned_p, bool *overflow) const; |

115 | double_int wide_mul_with_sign (double_int, bool unsigned_p, |

116 | double_int *higher, bool *overflow) const; |

117 | double_int add_with_sign (double_int, bool unsigned_p, bool *overflow) const; |

118 | double_int sub_with_overflow (double_int, bool *overflow) const; |

119 | double_int neg_with_overflow (bool *overflow) const; |

120 | |

121 | double_int operator * (double_int) const; |

122 | double_int operator + (double_int) const; |

123 | double_int operator - (double_int) const; |

124 | double_int operator - () const; |

125 | double_int operator ~ () const; |

126 | double_int operator & (double_int) const; |

127 | double_int operator | (double_int) const; |

128 | double_int operator ^ (double_int) const; |

129 | double_int and_not (double_int) const; |

130 | |

131 | double_int lshift (HOST_WIDE_INT count) const; |

132 | double_int lshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const; |

133 | double_int rshift (HOST_WIDE_INT count) const; |

134 | double_int rshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const; |

135 | double_int alshift (HOST_WIDE_INT count, unsigned int prec) const; |

136 | double_int arshift (HOST_WIDE_INT count, unsigned int prec) const; |

137 | double_int llshift (HOST_WIDE_INT count, unsigned int prec) const; |

138 | double_int lrshift (HOST_WIDE_INT count, unsigned int prec) const; |

139 | double_int lrotate (HOST_WIDE_INT count, unsigned int prec) const; |

140 | double_int rrotate (HOST_WIDE_INT count, unsigned int prec) const; |

141 | |

142 | /* You must ensure that double_int::ext is called on the operands |

143 | of the following operations, if the precision of the numbers |

144 | is less than HOST_BITS_PER_DOUBLE_INT bits. */ |

145 | |

146 | double_int div (double_int, bool, unsigned) const; |

147 | double_int sdiv (double_int, unsigned) const; |

148 | double_int udiv (double_int, unsigned) const; |

149 | double_int mod (double_int, bool, unsigned) const; |

150 | double_int smod (double_int, unsigned) const; |

151 | double_int umod (double_int, unsigned) const; |

152 | double_int divmod_with_overflow (double_int, bool, unsigned, |

153 | double_int *, bool *) const; |

154 | double_int divmod (double_int, bool, unsigned, double_int *) const; |

155 | double_int sdivmod (double_int, unsigned, double_int *) const; |

156 | double_int udivmod (double_int, unsigned, double_int *) const; |

157 | |

158 | /* Precision control functions. */ |

159 | |

160 | double_int ext (unsigned prec, bool uns) const; |

161 | double_int zext (unsigned prec) const; |

162 | double_int sext (unsigned prec) const; |

163 | |

164 | /* Comparative functions. */ |

165 | |

166 | bool is_zero () const; |

167 | bool is_one () const; |

168 | bool is_minus_one () const; |

169 | bool is_negative () const; |

170 | |

171 | int cmp (double_int b, bool uns) const; |

172 | int ucmp (double_int b) const; |

173 | int scmp (double_int b) const; |

174 | |

175 | bool ult (double_int b) const; |

176 | bool ule (double_int b) const; |

177 | bool ugt (double_int b) const; |

178 | bool slt (double_int b) const; |

179 | bool sle (double_int b) const; |

180 | bool sgt (double_int b) const; |

181 | |

182 | double_int max (double_int b, bool uns); |

183 | double_int smax (double_int b); |

184 | double_int umax (double_int b); |

185 | |

186 | double_int min (double_int b, bool uns); |

187 | double_int smin (double_int b); |

188 | double_int umin (double_int b); |

189 | |

190 | bool operator == (double_int cst2) const; |

191 | bool operator != (double_int cst2) const; |

192 | |

193 | /* Please migrate away from using these member variables publicly. */ |

194 | |

195 | unsigned HOST_WIDE_INT low; |

196 | HOST_WIDE_INT high; |

197 | |

198 | }; |

199 | |

200 | #define HOST_BITS_PER_DOUBLE_INT (2 * HOST_BITS_PER_WIDE_INT) |

201 | |

202 | /* Constructors and conversions. */ |

203 | |

204 | /* Constructs double_int from integer CST. The bits over the precision of |

205 | HOST_WIDE_INT are filled with the sign bit. */ |

206 | |

207 | inline double_int |

208 | double_int::from_shwi (HOST_WIDE_INT cst) |

209 | { |

210 | double_int r; |

211 | r.low = (unsigned HOST_WIDE_INT) cst; |

212 | r.high = cst < 0 ? -1 : 0; |

213 | return r; |

214 | } |

215 | |

216 | /* Some useful constants. */ |

217 | /* FIXME(crowl): Maybe remove after converting callers? |

218 | The problem is that a named constant would not be as optimizable, |

219 | while the functional syntax is more verbose. */ |

220 | |

221 | #define double_int_minus_one (double_int::from_shwi (-1)) |

222 | #define double_int_zero (double_int::from_shwi (0)) |

223 | #define double_int_one (double_int::from_shwi (1)) |

224 | #define double_int_two (double_int::from_shwi (2)) |

225 | #define double_int_ten (double_int::from_shwi (10)) |

226 | |

227 | /* Constructs double_int from unsigned integer CST. The bits over the |

228 | precision of HOST_WIDE_INT are filled with zeros. */ |

229 | |

230 | inline double_int |

231 | double_int::from_uhwi (unsigned HOST_WIDE_INT cst) |

232 | { |

233 | double_int r; |

234 | r.low = cst; |

235 | r.high = 0; |

236 | return r; |

237 | } |

238 | |

239 | inline double_int |

240 | double_int::from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low) |

241 | { |

242 | double_int r; |

243 | r.low = low; |

244 | r.high = high; |

245 | return r; |

246 | } |

247 | |

248 | inline double_int & |

249 | double_int::operator ++ () |

250 | { |

251 | *this += double_int_one; |

252 | return *this; |

253 | } |

254 | |

255 | inline double_int & |

256 | double_int::operator -- () |

257 | { |

258 | *this -= double_int_one; |

259 | return *this; |

260 | } |

261 | |

262 | inline double_int & |

263 | double_int::operator &= (double_int b) |

264 | { |

265 | *this = *this & b; |

266 | return *this; |

267 | } |

268 | |

269 | inline double_int & |

270 | double_int::operator ^= (double_int b) |

271 | { |

272 | *this = *this ^ b; |

273 | return *this; |

274 | } |

275 | |

276 | inline double_int & |

277 | double_int::operator |= (double_int b) |

278 | { |

279 | *this = *this | b; |

280 | return *this; |

281 | } |

282 | |

283 | /* Returns value of CST as a signed number. CST must satisfy |

284 | double_int::fits_signed. */ |

285 | |

286 | inline HOST_WIDE_INT |

287 | double_int::to_shwi () const |

288 | { |

289 | return (HOST_WIDE_INT) low; |

290 | } |

291 | |

292 | /* Returns value of CST as an unsigned number. CST must satisfy |

293 | double_int::fits_unsigned. */ |

294 | |

295 | inline unsigned HOST_WIDE_INT |

296 | double_int::to_uhwi () const |

297 | { |

298 | return low; |

299 | } |

300 | |

301 | /* Returns true if CST fits in unsigned HOST_WIDE_INT. */ |

302 | |

303 | inline bool |

304 | double_int::fits_uhwi () const |

305 | { |

306 | return high == 0; |

307 | } |

308 | |

309 | /* Logical operations. */ |

310 | |

311 | /* Returns ~A. */ |

312 | |

313 | inline double_int |

314 | double_int::operator ~ () const |

315 | { |

316 | double_int result; |

317 | result.low = ~low; |

318 | result.high = ~high; |

319 | return result; |

320 | } |

321 | |

322 | /* Returns A | B. */ |

323 | |

324 | inline double_int |

325 | double_int::operator | (double_int b) const |

326 | { |

327 | double_int result; |

328 | result.low = low | b.low; |

329 | result.high = high | b.high; |

330 | return result; |

331 | } |

332 | |

333 | /* Returns A & B. */ |

334 | |

335 | inline double_int |

336 | double_int::operator & (double_int b) const |

337 | { |

338 | double_int result; |

339 | result.low = low & b.low; |

340 | result.high = high & b.high; |

341 | return result; |

342 | } |

343 | |

344 | /* Returns A & ~B. */ |

345 | |

346 | inline double_int |

347 | double_int::and_not (double_int b) const |

348 | { |

349 | double_int result; |

350 | result.low = low & ~b.low; |

351 | result.high = high & ~b.high; |

352 | return result; |

353 | } |

354 | |

355 | /* Returns A ^ B. */ |

356 | |

357 | inline double_int |

358 | double_int::operator ^ (double_int b) const |

359 | { |

360 | double_int result; |

361 | result.low = low ^ b.low; |

362 | result.high = high ^ b.high; |

363 | return result; |

364 | } |

365 | |

366 | void dump_double_int (FILE *, double_int, bool); |

367 | |

368 | #define ALL_ONES HOST_WIDE_INT_M1U |

369 | |

370 | /* The operands of the following comparison functions must be processed |

371 | with double_int_ext, if their precision is less than |

372 | HOST_BITS_PER_DOUBLE_INT bits. */ |

373 | |

374 | /* Returns true if CST is zero. */ |

375 | |

376 | inline bool |

377 | double_int::is_zero () const |

378 | { |

379 | return low == 0 && high == 0; |

380 | } |

381 | |

382 | /* Returns true if CST is one. */ |

383 | |

384 | inline bool |

385 | double_int::is_one () const |

386 | { |

387 | return low == 1 && high == 0; |

388 | } |

389 | |

390 | /* Returns true if CST is minus one. */ |

391 | |

392 | inline bool |

393 | double_int::is_minus_one () const |

394 | { |

395 | return low == ALL_ONES && high == -1; |

396 | } |

397 | |

398 | /* Returns true if CST is negative. */ |

399 | |

400 | inline bool |

401 | double_int::is_negative () const |

402 | { |

403 | return high < 0; |

404 | } |

405 | |

406 | /* Returns true if CST1 == CST2. */ |

407 | |

408 | inline bool |

409 | double_int::operator == (double_int cst2) const |

410 | { |

411 | return low == cst2.low && high == cst2.high; |

412 | } |

413 | |

414 | /* Returns true if CST1 != CST2. */ |

415 | |

416 | inline bool |

417 | double_int::operator != (double_int cst2) const |

418 | { |

419 | return low != cst2.low || high != cst2.high; |

420 | } |

421 | |

422 | /* Return number of set bits of CST. */ |

423 | |

424 | inline int |

425 | double_int::popcount () const |

426 | { |

427 | return popcount_hwi (high) + popcount_hwi (low); |

428 | } |

429 | |

430 | |

431 | #ifndef GENERATOR_FILE |

432 | /* Conversion to and from GMP integer representations. */ |

433 | |

434 | void mpz_set_double_int (mpz_t, double_int, bool); |

435 | double_int mpz_get_double_int (const_tree, mpz_t, bool); |

436 | #endif |

437 | |

438 | namespace wi |

439 | { |

440 | template <> |

441 | struct int_traits <double_int> |

442 | { |

443 | static const enum precision_type precision_type = CONST_PRECISION; |

444 | static const bool host_dependent_precision = true; |

445 | static const unsigned int precision = HOST_BITS_PER_DOUBLE_INT; |

446 | static unsigned int get_precision (const double_int &); |

447 | static wi::storage_ref decompose (HOST_WIDE_INT *, unsigned int, |

448 | const double_int &); |

449 | }; |

450 | } |

451 | |

452 | inline unsigned int |

453 | wi::int_traits <double_int>::get_precision (const double_int &) |

454 | { |

455 | return precision; |

456 | } |

457 | |

458 | inline wi::storage_ref |

459 | wi::int_traits <double_int>::decompose (HOST_WIDE_INT *scratch, unsigned int p, |

460 | const double_int &x) |

461 | { |

462 | gcc_checking_assert (precision == p); |

463 | scratch[0] = x.low; |

464 | if ((x.high == 0 && scratch[0] >= 0) || (x.high == -1 && scratch[0] < 0)) |

465 | return wi::storage_ref (scratch, 1, precision); |

466 | scratch[1] = x.high; |

467 | return wi::storage_ref (scratch, 2, precision); |

468 | } |

469 | |

470 | #endif /* DOUBLE_INT_H */ |

471 |