summaryrefslogtreecommitdiff
path: root/src/checked.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/checked.cc')
-rw-r--r--src/checked.cc409
1 files changed, 409 insertions, 0 deletions
diff --git a/src/checked.cc b/src/checked.cc
new file mode 100644
index 000000000..e428109ec
--- /dev/null
+++ b/src/checked.cc
@@ -0,0 +1,409 @@
+/* Helper functions for checked numbers
+ Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
+ Copyright (C) 2010-2011 BUGSENG srl (http://bugseng.com)
+
+This file is part of the Parma Polyhedra Library (PPL).
+
+The PPL is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3 of the License, or (at your
+option) any later version.
+
+The PPL is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software Foundation,
+Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
+
+For the most up-to-date information see the Parma Polyhedra Library
+site: http://www.cs.unipr.it/ppl/ . */
+
+#include <ppl-config.h>
+#include "checked.defs.hh"
+#include <climits>
+
+namespace Parma_Polyhedra_Library {
+
+Minus_Infinity MINUS_INFINITY;
+Plus_Infinity PLUS_INFINITY;
+Not_A_Number NOT_A_NUMBER;
+
+namespace Checked {
+
+//! Holds the precision parameter used for irrational calculations.
+unsigned irrational_precision;
+
+struct number_struct {
+ unsigned int base;
+ bool neg_mantissa;
+ bool neg_exponent;
+ std::string mantissa;
+ unsigned int base_for_exponent;
+ unsigned long exponent;
+};
+
+/*! \brief
+ Returns the integer value associated with the ASCII code \p c, in
+ the base \p base positional number system, if there is such an
+ association; returns \f$-1\f$ otherwise.
+*/
+inline int
+get_digit(int c, int base = 10) {
+ if (c >= '0' && c < '0' + (base > 10 ? 10 : base))
+ return c - '0';
+ if (base > 10) {
+ base -= 10;
+ if (c >= 'A' && c < 'A' + base)
+ return c - 'A' + 10;
+ if (c >= 'a' && c < 'a' + base)
+ return c - 'a' + 10;
+ }
+ return -1;
+}
+
+/*! \brief
+ Adds the number represented (in the modulus-and-sign representation)
+ by \p b_neg and \p b_mod to the number represented by \p a_neg and
+ \p a_mod, assigning the result to the latter. Returns
+ <CODE>false</CODE> is the result cannot be represented; returns
+ <CODE>true</CODE> otherwise.
+*/
+inline bool
+sum_sign(bool& a_neg, unsigned long& a_mod,
+ bool b_neg, unsigned long b_mod) {
+ if (a_neg == b_neg) {
+ if (a_mod > ULONG_MAX - b_mod)
+ return false;
+ a_mod += b_mod;
+ }
+ else if (a_mod >= b_mod)
+ a_mod -= b_mod;
+ else {
+ a_neg = !a_neg;
+ a_mod = b_mod - a_mod;
+ }
+ return true;
+}
+
+
+/*! \brief
+ Helper function for parse_number(): reads the numerator or
+ denominator part of a number from \p is into \p num, returning the
+ appropriate Result value.
+*/
+Result
+parse_number_part(std::istream& is, number_struct& num) {
+ enum anonymous_enum { BASE, INTEGER, FRACTIONAL, EXPONENT } state = BASE;
+ PPL_UNINITIALIZED(unsigned long, max_exp_div);
+ PPL_UNINITIALIZED(int, max_exp_rem);
+ bool empty_exponent = true;
+ bool empty_mantissa = true;
+ long exponent_offset = 0;
+ long exponent_offset_scale = 1;
+ num.base = 10;
+ num.base_for_exponent = 10;
+ num.neg_mantissa = false;
+ num.neg_exponent = false;
+ num.mantissa.erase();
+ num.exponent = 0;
+ int c;
+ do {
+ c = is.get();
+ } while (isspace(c));
+ switch (c) {
+ case '-':
+ num.neg_mantissa = true;
+ // Fall through.
+ case '+':
+ c = is.get();
+ if (c == 'i' || c == 'I')
+ goto inf;
+ if (c != '.')
+ break;
+ // Fall through.
+ case '.':
+ state = FRACTIONAL;
+ c = is.get();
+ break;
+ case 'n':
+ case 'N':
+ c = is.get();
+ if (c != 'a' && c != 'A')
+ goto error;
+ c = is.get();
+ if (c != 'n' && c != 'N')
+ goto error;
+ return V_NAN;
+ inf:
+ case 'i':
+ case 'I':
+ c = is.get();
+ if (c != 'n' && c != 'n')
+ goto error;
+ c = is.get();
+ if (c != 'f' && c != 'F')
+ goto error;
+ return num.neg_mantissa ? V_EQ_MINUS_INFINITY : V_EQ_PLUS_INFINITY;
+ }
+ if (state != FRACTIONAL) {
+ if (get_digit(c, 10) < 0)
+ goto error;
+ if (c == '0') {
+ int d = is.get();
+ if (d == 'x' || d == 'X') {
+ num.base = 16;
+ num.base_for_exponent = 16;
+ state = INTEGER;
+ c = is.get();
+ }
+ else {
+ c = d;
+ empty_mantissa = false;
+ }
+ }
+ else {
+ num.mantissa += (char) c;
+ empty_mantissa = false;
+ c = is.get();
+ }
+ }
+ while (true) {
+ switch (state) {
+ case BASE:
+ if (get_digit(c, 10) >= 0) {
+ if (c != '0' || !num.mantissa.empty())
+ num.mantissa += (char) c;
+ empty_mantissa = false;
+ break;
+ }
+ if (c == '^') {
+ c = is.get();
+ if (c != '^')
+ goto error;
+ std::string::const_iterator i;
+ num.base = 0;
+ for (i = num.mantissa.begin(); i != num.mantissa.end(); i++) {
+ num.base = num.base * 10 + (*i - '0');
+ if (num.base > 36)
+ goto error;
+ }
+ if (num.base < 2)
+ goto error;
+ num.base_for_exponent = num.base;
+ num.mantissa.erase();
+ empty_mantissa = true;
+ state = INTEGER;
+ break;
+ }
+ goto integer;
+ case INTEGER:
+ if (get_digit(c, num.base) >= 0) {
+ if (c != '0' || !num.mantissa.empty())
+ num.mantissa += (char) c;
+ empty_mantissa = false;
+ break;
+ }
+ integer:
+ if (c == '.') {
+ state = FRACTIONAL;
+ break;
+ }
+ goto fractional;
+ case FRACTIONAL:
+ if (get_digit(c, num.base) >= 0) {
+ --exponent_offset;
+ if (c != '0' || !num.mantissa.empty())
+ num.mantissa += (char) c;
+ empty_mantissa = false;
+ break;
+ }
+ fractional:
+ if (empty_mantissa)
+ goto error;
+ if (c == 'e' || c == 'E')
+ goto exp;
+ if (c == 'p' || c == 'P') {
+ if (num.base == 16) {
+ num.base_for_exponent = 2;
+ exponent_offset_scale = 4;
+ goto exp;
+ }
+ else
+ goto error;
+ }
+ if (c == '*') {
+ c = is.get();
+ if (c != '^')
+ goto error;
+ exp:
+ state = EXPONENT;
+ max_exp_div = LONG_MAX / num.base;
+ max_exp_rem = LONG_MAX % num.base;
+ c = is.get();
+ if (c == '-') {
+ num.neg_exponent = true;
+ break;
+ }
+ if (c == '+')
+ break;
+ continue;
+ }
+ goto ok;
+ case EXPONENT:
+ int d = get_digit(c, 10);
+ if (d >= 0) {
+ empty_exponent = false;
+ if (num.exponent > max_exp_div
+ || (num.exponent == max_exp_div && d > max_exp_rem))
+ return V_CVT_STR_UNK;
+ num.exponent = num.exponent * 10 + d;
+ break;
+ }
+ if (empty_exponent)
+ goto error;
+ goto ok;
+ }
+ c = is.get();
+ }
+
+ {
+ ok:
+ is.unget();
+ unsigned int n = num.mantissa.size();
+ while (n > 0 && num.mantissa[n - 1] == '0') {
+ --n;
+ ++exponent_offset;
+ }
+ num.mantissa.erase(n);
+ bool neg;
+ if (exponent_offset < 0) {
+ neg = true;
+ exponent_offset = -exponent_offset;
+ }
+ else
+ neg = false;
+ sum_sign(num.neg_exponent, num.exponent,
+ neg, exponent_offset * exponent_offset_scale);
+ return V_EQ;
+ }
+
+ error:
+ is.unget();
+ return V_CVT_STR_UNK;
+}
+
+/* \brief
+ Reads a number from \p is writing it into \p num, the numerator,
+ and \p den, the denominator; the appropriate Result value is
+ returned.
+*/
+Result
+parse_number(std::istream& is, number_struct& num, number_struct& den) {
+ // Read the numerator.
+ Result r = parse_number_part(is, num);
+ if (r != V_EQ)
+ return r;
+ if (is.get() != '/') {
+ is.unget();
+ den.base = 0;
+ return r;
+ }
+ // Read the denominator.
+ r = parse_number_part(is, den);
+ if (r != V_EQ)
+ return V_CVT_STR_UNK;
+ if (num.base == den.base
+ && num.base_for_exponent == den.base_for_exponent) {
+ if (sum_sign(num.neg_exponent, num.exponent,
+ !den.neg_exponent, den.exponent)) {
+ if (num.neg_exponent) {
+ den.neg_exponent = false;
+ den.exponent = num.exponent;
+ num.exponent = 0;
+ }
+ else
+ den.exponent = 0;
+ }
+ }
+ return V_EQ;
+}
+
+
+Result
+input_mpq(mpq_class& to, std::istream& is) {
+ number_struct num_struct;
+ number_struct den_struct;
+ Result r = parse_number(is, num_struct, den_struct);
+ if (r == V_CVT_STR_UNK) {
+ is.setstate(is.failbit);
+ return r;
+ }
+ is.clear(is.rdstate() & ~is.failbit);
+ if (r != V_EQ)
+ return r;
+ if (den_struct.base && den_struct.mantissa.empty())
+ return V_NAN;
+ if (num_struct.mantissa.empty()) {
+ to = 0;
+ return V_EQ;
+ }
+ mpz_ptr num = to.get_num().get_mpz_t();
+ mpz_ptr den = to.get_den().get_mpz_t();
+ mpz_set_str(num, num_struct.mantissa.c_str(), num_struct.base);
+ if (den_struct.base) {
+ if (num_struct.neg_mantissa ^ den_struct.neg_mantissa)
+ mpz_neg(num, num);
+ mpz_set_str(den, den_struct.mantissa.c_str(), den_struct.base);
+ if (num_struct.exponent || den_struct.exponent) {
+ // Multiply the exponents into the numerator and denominator.
+ mpz_t z;
+ mpz_init(z);
+ if (num_struct.exponent) {
+ mpz_ui_pow_ui(z, num_struct.base_for_exponent, num_struct.exponent);
+ if (num_struct.neg_exponent)
+ mpz_mul(den, den, z);
+ else
+ mpz_mul(num, num, z);
+ }
+ if (den_struct.exponent) {
+ mpz_ui_pow_ui(z, den_struct.base_for_exponent, den_struct.exponent);
+ if (den_struct.neg_exponent)
+ mpz_mul(num, num, z);
+ else
+ mpz_mul(den, den, z);
+ }
+ mpz_clear(z);
+ }
+ }
+ else {
+ if (num_struct.neg_mantissa)
+ mpz_neg(num, num);
+ if (num_struct.exponent) {
+ if (num_struct.neg_exponent) {
+ // Add the negative exponent as a denominator.
+ mpz_ui_pow_ui(den, num_struct.base_for_exponent, num_struct.exponent);
+ goto end;
+ }
+ // Multiply the exponent into the numerator.
+ mpz_t z;
+ mpz_init(z);
+ mpz_ui_pow_ui(z, num_struct.base_for_exponent, num_struct.exponent);
+ mpz_mul(num, num, z);
+ mpz_clear(z);
+ }
+ mpz_set_ui(den, 1);
+ return V_EQ;
+ }
+ end:
+ // GMP operators require rationals in canonical form.
+ to.canonicalize();
+ return V_EQ;
+}
+
+} // namespace Checked
+
+} // namespace Parma_Polyhedra_Library
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-26 13:06:30 +0000