GCC Code Coverage Report
Directory: . Exec Total Coverage
File: src/util/integer_cln_imp.cpp Lines: 219 239 91.6 %
Date: 2021-03-23 Branches: 224 535 41.9 %

Line Exec Source
1
/*********************                                                        */
2
/*! \file integer_cln_imp.cpp
3
 ** \verbatim
4
 ** Top contributors (to current version):
5
 **   Aina Niemetz, Tim King, Gereon Kremer
6
 ** This file is part of the CVC4 project.
7
 ** Copyright (c) 2009-2021 by the authors listed in the file AUTHORS
8
 ** in the top-level source directory and their institutional affiliations.
9
 ** All rights reserved.  See the file COPYING in the top-level source
10
 ** directory for licensing information.\endverbatim
11
 **
12
 ** \brief [[ Add one-line brief description here ]]
13
 **
14
 ** [[ Add lengthier description here ]]
15
 ** \todo document this file
16
 **/
17
#include <sstream>
18
#include <string>
19
20
#include "cvc4autoconfig.h"
21
#include "util/integer.h"
22
23
#ifndef CVC4_CLN_IMP
24
#error "This source should only ever be built if CVC4_CLN_IMP is on !"
25
#endif /* CVC4_CLN_IMP */
26
27
#include "base/check.h"
28
29
using namespace std;
30
31
namespace CVC4 {
32
33
signed int Integer::s_fastSignedIntMin = -(1 << 29);
34
signed int Integer::s_fastSignedIntMax = (1 << 29) - 1;
35
signed long Integer::s_slowSignedIntMin =
36
    (signed long)std::numeric_limits<signed int>::min();
37
signed long Integer::s_slowSignedIntMax =
38
    (signed long)std::numeric_limits<signed int>::max();
39
40
unsigned int Integer::s_fastUnsignedIntMax = (1 << 29) - 1;
41
unsigned long Integer::s_slowUnsignedIntMax =
42
    (unsigned long)std::numeric_limits<unsigned int>::max();
43
44
unsigned long Integer::s_signedLongMin =
45
    std::numeric_limits<signed long>::min();
46
unsigned long Integer::s_signedLongMax =
47
    std::numeric_limits<signed long>::max();
48
unsigned long Integer::s_unsignedLongMax =
49
    std::numeric_limits<unsigned long>::max();
50
51
28098046
Integer& Integer::operator=(const Integer& x)
52
{
53
28098046
  if (this == &x) return *this;
54
28098046
  d_value = x.d_value;
55
28098046
  return *this;
56
}
57
58
260908401
bool Integer::operator==(const Integer& y) const
59
{
60
260908401
  return d_value == y.d_value;
61
}
62
63
607528
Integer Integer::operator-() const { return Integer(-(d_value)); }
64
65
1129812
bool Integer::operator!=(const Integer& y) const
66
{
67
1129812
  return d_value != y.d_value;
68
}
69
70
9294886
bool Integer::operator<(const Integer& y) const { return d_value < y.d_value; }
71
72
1133501
bool Integer::operator<=(const Integer& y) const
73
{
74
1133501
  return d_value <= y.d_value;
75
}
76
77
533400
bool Integer::operator>(const Integer& y) const { return d_value > y.d_value; }
78
79
785876
bool Integer::operator>=(const Integer& y) const
80
{
81
785876
  return d_value >= y.d_value;
82
}
83
84
8194537
Integer Integer::operator+(const Integer& y) const
85
{
86
8194537
  return Integer(d_value + y.d_value);
87
}
88
89
76970
Integer& Integer::operator+=(const Integer& y)
90
{
91
76970
  d_value += y.d_value;
92
76970
  return *this;
93
}
94
95
1463584
Integer Integer::operator-(const Integer& y) const
96
{
97
1463584
  return Integer(d_value - y.d_value);
98
}
99
100
9177
Integer& Integer::operator-=(const Integer& y)
101
{
102
9177
  d_value -= y.d_value;
103
9177
  return *this;
104
}
105
106
1096247
Integer Integer::operator*(const Integer& y) const
107
{
108
1096247
  return Integer(d_value * y.d_value);
109
}
110
111
8996
Integer& Integer::operator*=(const Integer& y)
112
{
113
8996
  d_value *= y.d_value;
114
8996
  return *this;
115
}
116
117
452453
Integer Integer::bitwiseOr(const Integer& y) const
118
{
119
452453
  return Integer(cln::logior(d_value, y.d_value));
120
}
121
122
280990
Integer Integer::bitwiseAnd(const Integer& y) const
123
{
124
280990
  return Integer(cln::logand(d_value, y.d_value));
125
}
126
127
716
Integer Integer::bitwiseXor(const Integer& y) const
128
{
129
716
  return Integer(cln::logxor(d_value, y.d_value));
130
}
131
132
1351635
Integer Integer::bitwiseNot() const { return Integer(cln::lognot(d_value)); }
133
134
1801478
Integer Integer::multiplyByPow2(uint32_t pow) const
135
{
136
3602956
  cln::cl_I ipow(pow);
137
3602956
  return Integer(d_value << ipow);
138
}
139
140
73032
bool Integer::isBitSet(uint32_t i) const
141
{
142
73032
  return !extractBitRange(1, i).isZero();
143
}
144
145
1811
void Integer::setBit(uint32_t i, bool value)
146
{
147
3622
  cln::cl_I mask(1);
148
1811
  mask = mask << i;
149
1811
  if (value)
150
  {
151
1783
    d_value = cln::logior(d_value, mask);
152
  }
153
  else
154
  {
155
28
    mask = cln::lognot(mask);
156
28
    d_value = cln::logand(d_value, mask);
157
  }
158
1811
}
159
160
802058
Integer Integer::oneExtend(uint32_t size, uint32_t amount) const
161
{
162
802058
  DebugCheckArgument((*this) < Integer(1).multiplyByPow2(size), size);
163
802058
  cln::cl_byte range(amount, size);
164
1604116
  cln::cl_I allones = (cln::cl_I(1) << (size + amount)) - 1;  // 2^size - 1
165
1604116
  Integer temp(allones);
166
167
1604116
  return Integer(cln::deposit_field(allones, d_value, range));
168
}
169
170
1182614
uint32_t Integer::toUnsignedInt() const { return cln::cl_I_to_uint(d_value); }
171
172
2015140
Integer Integer::extractBitRange(uint32_t bitCount, uint32_t low) const
173
{
174
2015140
  cln::cl_byte range(bitCount, low);
175
2015140
  return Integer(cln::ldb(d_value, range));
176
}
177
178
51869
Integer Integer::floorDivideQuotient(const Integer& y) const
179
{
180
51869
  return Integer(cln::floor1(d_value, y.d_value));
181
}
182
183
56886
Integer Integer::floorDivideRemainder(const Integer& y) const
184
{
185
56886
  return Integer(cln::floor2(d_value, y.d_value).remainder);
186
}
187
188
3771
void Integer::floorQR(Integer& q,
189
                      Integer& r,
190
                      const Integer& x,
191
                      const Integer& y)
192
{
193
7542
  cln::cl_I_div_t res = cln::floor2(x.d_value, y.d_value);
194
3771
  q.d_value = res.quotient;
195
3771
  r.d_value = res.remainder;
196
3771
}
197
198
Integer Integer::ceilingDivideQuotient(const Integer& y) const
199
{
200
  return Integer(cln::ceiling1(d_value, y.d_value));
201
}
202
203
Integer Integer::ceilingDivideRemainder(const Integer& y) const
204
{
205
  return Integer(cln::ceiling2(d_value, y.d_value).remainder);
206
}
207
208
3097
void Integer::euclidianQR(Integer& q,
209
                          Integer& r,
210
                          const Integer& x,
211
                          const Integer& y)
212
{
213
  // compute the floor and then fix the value up if needed.
214
3097
  floorQR(q, r, x, y);
215
216
3097
  if (r.strictlyNegative())
217
  {
218
    // if r < 0
219
    // abs(r) < abs(y)
220
    // - abs(y) < r < 0, then 0 < r + abs(y) < abs(y)
221
    // n = y * q + r
222
    // n = y * q - abs(y) + r + abs(y)
223
8
    if (r.sgn() >= 0)
224
    {
225
      // y = abs(y)
226
      // n = y * q - y + r + y
227
      // n = y * (q-1) + (r+y)
228
      q -= 1;
229
      r += y;
230
    }
231
    else
232
    {
233
      // y = -abs(y)
234
      // n = y * q + y + r - y
235
      // n = y * (q+1) + (r-y)
236
8
      q += 1;
237
8
      r -= y;
238
    }
239
  }
240
3097
}
241
242
475
Integer Integer::euclidianDivideQuotient(const Integer& y) const
243
{
244
950
  Integer q, r;
245
475
  euclidianQR(q, r, *this, y);
246
950
  return q;
247
}
248
249
2606
Integer Integer::euclidianDivideRemainder(const Integer& y) const
250
{
251
5212
  Integer q, r;
252
2606
  euclidianQR(q, r, *this, y);
253
5212
  return r;
254
}
255
256
Integer Integer::exactQuotient(const Integer& y) const
257
{
258
  DebugCheckArgument(y.divides(*this), y);
259
  return Integer(cln::exquo(d_value, y.d_value));
260
}
261
262
22941928
Integer Integer::modByPow2(uint32_t exp) const
263
{
264
22941928
  cln::cl_byte range(exp, 0);
265
22941928
  return Integer(cln::ldb(d_value, range));
266
}
267
268
6847
Integer Integer::divByPow2(uint32_t exp) const { return d_value >> exp; }
269
270
26264
Integer Integer::pow(unsigned long int exp) const
271
{
272
26264
  if (exp == 0)
273
  {
274
135
    return Integer(1);
275
  }
276
  else
277
  {
278
26129
    Assert(exp > 0);
279
52258
    cln::cl_I result = cln::expt_pos(d_value, exp);
280
26129
    return Integer(result);
281
  }
282
}
283
284
3396557
Integer Integer::gcd(const Integer& y) const
285
{
286
6793114
  cln::cl_I result = cln::gcd(d_value, y.d_value);
287
6793114
  return Integer(result);
288
}
289
290
13810637
Integer Integer::lcm(const Integer& y) const
291
{
292
27621274
  cln::cl_I result = cln::lcm(d_value, y.d_value);
293
27621274
  return Integer(result);
294
}
295
296
2564
Integer Integer::modAdd(const Integer& y, const Integer& m) const
297
{
298
5128
  cln::cl_modint_ring ry = cln::find_modint_ring(m.d_value);
299
5128
  cln::cl_MI xm = ry->canonhom(d_value);
300
5128
  cln::cl_MI ym = ry->canonhom(y.d_value);
301
5128
  cln::cl_MI res = xm + ym;
302
5128
  return Integer(ry->retract(res));
303
}
304
305
2558
Integer Integer::modMultiply(const Integer& y, const Integer& m) const
306
{
307
5116
  cln::cl_modint_ring ry = cln::find_modint_ring(m.d_value);
308
5116
  cln::cl_MI xm = ry->canonhom(d_value);
309
5116
  cln::cl_MI ym = ry->canonhom(y.d_value);
310
5116
  cln::cl_MI res = xm * ym;
311
5116
  return Integer(ry->retract(res));
312
}
313
314
466
Integer Integer::modInverse(const Integer& m) const
315
{
316
466
  PrettyCheckArgument(m > 0, m, "m must be greater than zero");
317
932
  cln::cl_modint_ring ry = cln::find_modint_ring(m.d_value);
318
932
  cln::cl_MI xm = ry->canonhom(d_value);
319
  /* normalize to modulo m for coprime check */
320
932
  cln::cl_I x = ry->retract(xm);
321
466
  if (x == 0 || cln::gcd(x, m.d_value) != 1)
322
  {
323
26
    return Integer(-1);
324
  }
325
880
  cln::cl_MI res = cln::recip(xm);
326
440
  return Integer(ry->retract(res));
327
}
328
329
51348
bool Integer::divides(const Integer& y) const
330
{
331
102696
  cln::cl_I result = cln::rem(y.d_value, d_value);
332
102696
  return cln::zerop(result);
333
}
334
335
7596801
Integer Integer::abs() const { return d_value >= 0 ? *this : -*this; }
336
337
363380
std::string Integer::toString(int base) const
338
{
339
726760
  std::stringstream ss;
340
363380
  switch (base)
341
  {
342
261
    case 2: fprintbinary(ss, d_value); break;
343
    case 8: fprintoctal(ss, d_value); break;
344
363111
    case 10: fprintdecimal(ss, d_value); break;
345
8
    case 16: fprinthexadecimal(ss, d_value); break;
346
    default: throw Exception("Unhandled base in Integer::toString()");
347
  }
348
363380
  std::string output = ss.str();
349
1116835
  for (unsigned i = 0; i <= output.length(); ++i)
350
  {
351
753455
    if (isalpha(output[i]))
352
    {
353
4
      output.replace(i, 1, 1, tolower(output[i]));
354
    }
355
  }
356
357
726760
  return output;
358
}
359
360
1160318
int Integer::sgn() const
361
{
362
2320636
  cln::cl_I sgn = cln::signum(d_value);
363
2320636
  return cln::cl_I_to_int(sgn);
364
}
365
366
12
bool Integer::strictlyPositive() const { return cln::plusp(d_value); }
367
368
109415
bool Integer::strictlyNegative() const { return cln::minusp(d_value); }
369
370
73046
bool Integer::isZero() const { return cln::zerop(d_value); }
371
372
20302737
bool Integer::isOne() const { return d_value == 1; }
373
374
bool Integer::isNegativeOne() const { return d_value == -1; }
375
376
247840
void Integer::parseInt(const std::string& s, unsigned base)
377
{
378
  cln::cl_read_flags flags;
379
247840
  flags.syntax = cln::syntax_integer;
380
247840
  flags.lsyntax = cln::lsyntax_standard;
381
247840
  flags.rational_base = base;
382
247840
  if (base == 0)
383
  {
384
    // infer base in a manner consistent with GMP
385
16
    if (s[0] == '0')
386
    {
387
10
      flags.lsyntax = cln::lsyntax_commonlisp;
388
20
      std::string st = s;
389
10
      if (s[1] == 'X' || s[1] == 'x')
390
      {
391
4
        st.replace(0, 2, "#x");
392
      }
393
6
      else if (s[1] == 'B' || s[1] == 'b')
394
      {
395
4
        st.replace(0, 2, "#b");
396
      }
397
      else
398
      {
399
2
        st.replace(0, 1, "#o");
400
      }
401
10
      readInt(flags, st, base);
402
8
      return;
403
    }
404
    else
405
    {
406
6
      flags.rational_base = 10;
407
    }
408
  }
409
247830
  readInt(flags, s, base);
410
}
411
412
247840
void Integer::readInt(const cln::cl_read_flags& flags,
413
                      const std::string& s,
414
                      unsigned base)
415
{
416
  try
417
  {
418
    // Removing leading zeroes, CLN has a bug for these inputs up to and
419
    // including CLN v1.3.2.
420
    // See
421
    // http://www.ginac.de/CLN/cln.git/?a=commit;h=4a477b0cc3dd7fbfb23b25090ff8c8869c8fa21a
422
    // for details.
423
247840
    size_t pos = s.find_first_not_of('0');
424
247840
    if (pos == std::string::npos)
425
    {
426
49010
      d_value = cln::read_integer(flags, "0", NULL, NULL);
427
    }
428
    else
429
    {
430
198830
      const char* cstr = s.c_str();
431
198830
      const char* start = cstr + pos;
432
198830
      const char* end = cstr + s.length();
433
198830
      d_value = cln::read_integer(flags, start, end, NULL);
434
    }
435
  }
436
60
  catch (...)
437
  {
438
60
    std::stringstream ss;
439
30
    ss << "Integer() failed to parse value \"" << s << "\" in base " << base;
440
30
    throw std::invalid_argument(ss.str());
441
  }
442
247810
}
443
444
45
bool Integer::fitsSignedInt() const
445
{
446
  // http://www.ginac.de/CLN/cln.html#Conversions
447
  // TODO improve performance
448
45
  Assert(s_slowSignedIntMin <= s_fastSignedIntMin);
449
45
  Assert(s_fastSignedIntMin <= s_fastSignedIntMax);
450
45
  Assert(s_fastSignedIntMax <= s_slowSignedIntMax);
451
452
135
  return (d_value <= s_fastSignedIntMax || d_value <= s_slowSignedIntMax)
453
225
         && (d_value >= s_fastSignedIntMin || d_value >= s_slowSignedIntMax);
454
}
455
456
897570
bool Integer::fitsUnsignedInt() const
457
{
458
  // TODO improve performance
459
897570
  Assert(s_fastUnsignedIntMax <= s_slowUnsignedIntMax);
460
897570
  return sgn() >= 0
461
3590280
         && (d_value <= s_fastUnsignedIntMax
462
1795142
             || d_value <= s_slowUnsignedIntMax);
463
}
464
465
45
signed int Integer::getSignedInt() const
466
{
467
  // ensure there isn't overflow
468
90
  CheckArgument(
469
45
      fitsSignedInt(), this, "Overflow detected in Integer::getSignedInt()");
470
45
  return cln::cl_I_to_int(d_value);
471
}
472
473
11927
unsigned int Integer::getUnsignedInt() const
474
{
475
  // ensure there isn't overflow
476
11927
  CheckArgument(fitsUnsignedInt(),
477
                this,
478
                "Overflow detected in Integer::getUnsignedInt()");
479
11927
  return cln::cl_I_to_uint(d_value);
480
}
481
482
bool Integer::fitsSignedLong() const
483
{
484
  return d_value <= s_signedLongMax && d_value >= s_signedLongMin;
485
}
486
487
bool Integer::fitsUnsignedLong() const
488
{
489
  return sgn() >= 0 && d_value <= s_unsignedLongMax;
490
}
491
492
2158
long Integer::getLong() const
493
{
494
  // ensure there isn't overflow
495
2160
  CheckArgument(d_value <= std::numeric_limits<long>::max(),
496
                this,
497
                "Overflow detected in Integer::getLong()");
498
2156
  CheckArgument(d_value >= std::numeric_limits<long>::min(),
499
                this,
500
                "Overflow detected in Integer::getLong()");
501
2156
  return cln::cl_I_to_long(d_value);
502
}
503
504
364
unsigned long Integer::getUnsignedLong() const
505
{
506
  // ensure there isn't overflow
507
366
  CheckArgument(d_value <= std::numeric_limits<unsigned long>::max(),
508
                this,
509
                "Overflow detected in Integer::getUnsignedLong()");
510
362
  CheckArgument(d_value >= std::numeric_limits<unsigned long>::min(),
511
                this,
512
                "Overflow detected in Integer::getUnsignedLong()");
513
362
  return cln::cl_I_to_ulong(d_value);
514
}
515
516
3685658
size_t Integer::hash() const { return equal_hashcode(d_value); }
517
518
94
bool Integer::testBit(unsigned n) const { return cln::logbitp(n, d_value); }
519
520
516709
unsigned Integer::isPow2() const
521
{
522
516709
  if (d_value <= 0) return 0;
523
  // power2p returns n such that d_value = 2^(n-1)
524
504001
  return cln::power2p(d_value);
525
}
526
527
260306
size_t Integer::length() const
528
{
529
260306
  int s = sgn();
530
260306
  if (s == 0)
531
  {
532
39146
    return 1;
533
  }
534
221160
  else if (s < 0)
535
  {
536
91126
    size_t len = cln::integer_length(d_value);
537
    /*If this is -2^n, return len+1 not len to stay consistent with the
538
     * definition above! From CLN's documentation of integer_length: This is
539
     * the smallest n >= 0 such that -2^n <= x < 2^n. If x > 0, this is the
540
     * unique n > 0 such that 2^(n-1) <= x < 2^n.
541
     */
542
91126
    size_t ord2 = cln::ord2(d_value);
543
91126
    return (len == ord2) ? (len + 1) : len;
544
  }
545
  else
546
  {
547
130034
    return cln::integer_length(d_value);
548
  }
549
}
550
551
36
void Integer::extendedGcd(
552
    Integer& g, Integer& s, Integer& t, const Integer& a, const Integer& b)
553
{
554
36
  g.d_value = cln::xgcd(a.d_value, b.d_value, &s.d_value, &t.d_value);
555
36
}
556
557
const Integer& Integer::min(const Integer& a, const Integer& b)
558
{
559
  return (a <= b) ? a : b;
560
}
561
562
const Integer& Integer::max(const Integer& a, const Integer& b)
563
{
564
  return (a >= b) ? a : b;
565
}
566
567
29066
std::ostream& operator<<(std::ostream& os, const Integer& n)
568
{
569
29066
  return os << n.toString();
570
}
571
26685
} /* namespace CVC4 */