compiler2/Int.cc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // Copyright (c) 2000-2015 Ericsson Telecom AB
   3 // All rights reserved. This program and the accompanying materials
   4 // are made available under the terms of the Eclipse Public License v1.0
   5 // which accompanies this distribution, and is available at
   6 // http://www.eclipse.org/legal/epl-v10.html
   7 ///////////////////////////////////////////////////////////////////////////////
   8 #include "../common/dbgnew.hh"
   9 #include "Int.hh"
  10 #include "string.hh"
  11 #include "error.h"
  12 #include "Setting.hh"
  13
  14 #include <openssl/crypto.h>
  15
  16 #include <stdlib.h>
  17 #include <stdio.h>
  18 #include <errno.h>
  19 #include <math.h>
  20
  21 // We cannot check without using a "./configure" script or such if we have
  22 // llabs() or not.  Define our own function instead.
  23 inline long long ll_abs(long long x) { return ((x >= 0) ? (x) : (-x)); }
  24
  25 namespace Common {
  26
  27 string Int2string(const Int& i)
  28 {
  29   char *s = NULL;
  30   s = mprintf("%lld", i);
  31   string str(s);
  32   Free(s);
  33   return str;
  34 }
  35
  36 Int string2Int(const char *s, const Location& loc)
  37 {
  38   errno = 0;
  39   Int i = strtoll(s, NULL, 10);
  40   switch (errno) {
  41   case ERANGE: {
  42     if (loc.get_filename() != NULL) {
  43       loc.error("Overflow when converting `%s' to integer value: %s", s,
  44         strerror(errno));
  45     } else {
  46       FATAL_ERROR("Overflow when converting `%s' to integer value: %s", s,
  47         strerror(errno));
  48     }
  49     break; }
  50   case 0:
  51     break;
  52   default:
  53     FATAL_ERROR("Unexpected error when converting `%s' to integer: %s", s,
  54       strerror(errno));
  55   }
  56   return i;
  57 }
  58
  59 int_val_t::int_val_t() : native_flag(true)
  60 {
  61   val.openssl = NULL;
  62 }
  63
  64 int_val_t::int_val_t(const int_val_t& v)
  65 {
  66   native_flag = v.is_native();
  67   if (native_flag) val.native = v.get_val();
  68   else val.openssl = BN_dup(v.get_val_openssl());
  69 }
  70
  71 int_val_t::int_val_t(const char *s, const Location& loc)
  72 {
  73   BIGNUM *n = NULL;
  74   if (!BN_dec2bn(&n, *s == '+' ? s + 1 : s))
  75     loc.error("Unexpected error when converting `%s' to integer", s);
  76   if (BN_num_bits(n) > (int)sizeof(long long) * 8 - 1) {
  77     native_flag = false;
  78     val.openssl = n;
  79   } else {
  80     native_flag = true;
  81     val.native = string2Int(s, loc);
  82     BN_free(n);
  83   }
  84 }
  85
  86 int_val_t::~int_val_t()
  87 {
  88   if (!native_flag) BN_free(val.openssl);
  89 }
  90
  91 string int_val_t::t_str() const
  92 {
  93   char *tmp = NULL;
  94   if (native_flag) {
  95     tmp = mprintf("%lld", val.native);
  96     string s(tmp);
  97     Free(tmp);
  98     return s;
  99   } else {
 100     if (!(tmp = BN_bn2dec(val.openssl)))
 101       FATAL_ERROR("int_val_t::t_str()");
 102     string s(tmp);
 103     OPENSSL_free(tmp);
 104     return s;
 105   }
 106 }
 107
 108 BIGNUM *int_val_t::to_openssl() const
 109 {
 110   BIGNUM *big = NULL;
 111   if (native_flag) {
 112     string str = Int2string(val.native);
 113     if (!BN_dec2bn(&big, str.c_str())) FATAL_ERROR("int_val_t::to_openssl()");
 114   } else {
 115     big = BN_dup(val.openssl);
 116     if (!big) FATAL_ERROR("int_val_t::to_openssl()");
 117   }
 118   return big;
 119 }
 120
 121 bool int_val_t::operator==(Int right) const
 122 {
 123   if (!native_flag) return false;
 124   return val.native == right;
 125 }
 126
 127 bool int_val_t::operator==(const int_val_t& v) const
 128 {
 129   if (native_flag != v.is_native()) return false;
 130   if (native_flag) return val.native == v.get_val();
 131   return !BN_cmp(val.openssl, v.get_val_openssl());
 132 }
 133
 134 bool int_val_t::operator<(const int_val_t& v) const
 135 {
 136   if (native_flag) {
 137     if (v.is_native()) {
 138       return val.native < v.get_val();
 139     } else {
 140       BIGNUM *this_big = to_openssl();
 141       if (!this_big) FATAL_ERROR("int_val_t::operator<(int_val_t& v)");
 142       int this_equ = BN_cmp(this_big, v.get_val_openssl());
 143       BN_free(this_big);
 144       return this_equ == -1;
 145     }
 146   } else {
 147     if (v.is_native()) {
 148       BIGNUM *v_big = v.to_openssl();
 149       if (!v_big) FATAL_ERROR("int_val_t::operator<(int_val_t& v)");
 150       int v_equ = BN_cmp(val.openssl, v_big);
 151       BN_free(v_big);
 152       return v_equ == -1;
 153     } else {
 154       return BN_cmp(val.openssl, v.val.openssl) == -1;
 155     }
 156   }
 157 }
 158
 159 int_val_t int_val_t::operator-() const
 160 {
 161   if (native_flag) {
 162     if (val.native == LLONG_MIN) {
 163       BIGNUM *result = int_val_t(LLONG_MIN).to_openssl();
 164       BN_set_negative(result, 0);
 165       return int_val_t(result);
 166     } else {
 167       return int_val_t(-val.native);
 168     }
 169   } else {
 170     BIGNUM *llong_max_plus_one = int_val_t(LLONG_MIN).to_openssl();
 171     BN_set_negative(llong_max_plus_one, 0);
 172     int cmp = BN_cmp(val.openssl, llong_max_plus_one);
 173     BN_free(llong_max_plus_one);
 174     if (cmp == 0) {
 175       return int_val_t(LLONG_MIN);
 176     } else {
 177       BIGNUM *result = BN_dup(val.openssl);
 178       BN_set_negative(result, !BN_is_negative(result));
 179       return int_val_t(result);
 180     }
 181   }
 182 }
 183
 184 int_val_t int_val_t::operator+(const int_val_t& right) const
 185 {
 186   //  a +  b =   a add b
 187   //  a + -b =   a sub b
 188   // -a +  b =   b sub a
 189   // -a + -b = -(a add b)
 190   // Use only inline functions and BN_* directly.  Call out for operator- in
 191   // the beginning.
 192   bool a_neg = is_negative();
 193   bool b_neg = right.is_negative();
 194   bool r_neg = a_neg && b_neg;
 195   if (!a_neg && b_neg) return operator-(-right);
 196   if (a_neg && !b_neg) return right.operator-(-(*this));
 197   if (native_flag) {
 198     long long result_;
 199     if (right.is_native()) {
 200       unsigned long long result = val.native + right.get_val();
 201       result_ = val.native + right.get_val();
 202       if (static_cast<long long>(result) != result_ ||
 203           (!r_neg && result_ < 0) || (r_neg && result_ > 0)) {
 204         // We can safely assume that the sum of two non-negative long long
 205         // values fit in an unsigned long long.  limits.h says:
 206         // # ifndef ULLONG_MAX
 207         // # define ULLONG_MAX (LLONG_MAX * 2ULL + 1)
 208         // # endif
 209         // This is the most complicated case.  We cannot be sure that
 210         // sizeof(BN_ULONG) == sizeof(long long).  First convert the long long
 211         // to string and feed BN_dec2bn.
 212         BIGNUM *left_ = to_openssl();
 213         BIGNUM *right_ = right.to_openssl();
 214         BN_add(left_, left_, right_);
 215         BN_free(right_);
 216         return int_val_t(left_);
 217       } else {
 218         return int_val_t(result_);
 219       }
 220     } else {
 221       // long long (>= 0) + BIGNUM == BIGNUM.
 222       BIGNUM *result = BN_new();
 223       BIGNUM *left_ = to_openssl();
 224       BN_add(result, left_, right.get_val_openssl());
 225       return int_val_t(result);
 226     }
 227   } else {
 228     // BIGNUM + long long (>= 0) == BIGNUM.
 229     BIGNUM *result = BN_new();
 230     BIGNUM *right_;
 231     right_ = right.is_native() ? right.to_openssl() : right.get_val_openssl();
 232     BN_add(result, val.openssl, right_);
 233     if (right.is_native())
 234       BN_free(right_);
 235     return int_val_t(result);
 236   }
 237 }
 238
 239 int_val_t int_val_t::operator-(const int_val_t& right) const
 240 {
 241   //  a -  b =   a sub b
 242   // -a -  b = -(a add b)
 243   //  a - -b =   a add b
 244   // -a - -b =  -a add b  = b sub a
 245   bool a_neg = is_negative();
 246   bool b_neg = right.is_negative();
 247   if (!a_neg && b_neg) return operator+(-right);
 248   if (a_neg && !b_neg) return -right.operator+(-(*this));
 249   if (native_flag) {
 250     if (right.is_native()) {
 251       // Since both operands are non-negative the most negative result of a
 252       // subtraction can be -LLONG_MAX and according to limits.h:
 253       // # ifndef LLONG_MIN
 254       // # define LLONG_MIN (-LLONG_MAX-1)
 255       // # endif
 256       return int_val_t(val.native - right.get_val());
 257     } else {
 258       BIGNUM *left_bn = to_openssl();
 259       BN_sub(left_bn, left_bn, right.get_val_openssl());
 260       // The result can be small enough to fit in long long.  The same is true
 261       // for division.  Back conversion is a really costly operation using
 262       // strings all the time.  TODO Improve it.
 263       if (BN_num_bits(left_bn) <= (int)sizeof(long long) * 8 - 1) {
 264         char *result_str = BN_bn2dec(left_bn);
 265         Int result_ll = string2Int(result_str, Location());
 266         OPENSSL_free(result_str);
 267         BN_free(left_bn);
 268         return int_val_t(result_ll);
 269       } else {
 270         return int_val_t(left_bn);
 271       }
 272     }
 273   } else {
 274     BIGNUM *result = BN_new();
 275     BIGNUM *right_bn;
 276     right_bn = right.is_native() ? right.to_openssl() :
 277       right.get_val_openssl();
 278     BN_sub(result, val.openssl, right_bn);
 279     if (right.is_native()) BN_free(right_bn);
 280     if (BN_num_bits(result) <= (int)sizeof(long long) * 8 - 1) {
 281       char *result_str = BN_bn2dec(result);
 282       Int result_ll = string2Int(result_str, Location());
 283       OPENSSL_free(result_str);
 284       return int_val_t(result_ll);
 285     } else {
 286       return int_val_t(result);
 287     }
 288   }
 289 }
 290
 291 int_val_t int_val_t::operator*(const int_val_t& right) const
 292 {
 293   if ((native_flag && val.native == 0LL) ||
 294     (right.native_flag && right.val.native == 0LL))
 295     return int_val_t(0LL);
 296   if (native_flag) {
 297     if (right.native_flag) {
 298       // 2^15 is used as a simple heuristic.
 299       // TODO: Improve.
 300       if (ll_abs(val.native) < 32768LL && ll_abs(right.val.native) < 32768LL) {
 301         return int_val_t(val.native * right.val.native);
 302       } else {
 303         BIGNUM *left_bn = to_openssl();
 304         BIGNUM *right_bn = right.to_openssl();
 305         BN_CTX *ctx = BN_CTX_new();
 306         BN_CTX_init(ctx);
 307         BN_mul(left_bn, left_bn, right_bn, ctx);
 308         BN_CTX_free(ctx);
 309         BN_free(right_bn);
 310         if (BN_num_bits(left_bn) < (int)sizeof(long long) * 8) {
 311           BN_free(left_bn);
 312           return int_val_t(val.native * right.val.native);
 313         } else {
 314           return int_val_t(left_bn);
 315         }
 316       }
 317     } else {
 318       BIGNUM *this_bn = to_openssl();
 319       BN_CTX *ctx = BN_CTX_new();
 320       BN_CTX_init(ctx);
 321       BN_mul(this_bn, this_bn, right.get_val_openssl(), ctx);
 322       BN_CTX_free(ctx);
 323       return int_val_t(this_bn);
 324     }
 325   } else {
 326     BIGNUM *result = BN_new();
 327     BIGNUM *right_bn;
 328     BN_CTX *ctx = BN_CTX_new();
 329     BN_CTX_init(ctx);
 330     right_bn = right.native_flag ? right.to_openssl()
 331       : right.get_val_openssl();
 332     BN_mul(result, val.openssl, right_bn, ctx);
 333     BN_CTX_free(ctx);
 334     if (right.native_flag) BN_free(right_bn);
 335     return int_val_t(result);
 336   }
 337 }
 338
 339 int_val_t int_val_t::operator/(const int_val_t& right) const
 340 {
 341   if (native_flag && val.native == 0LL)
 342     return int_val_t(0LL);
 343   if (right.is_native() && right.get_val() == 0LL)
 344     FATAL_ERROR("Division by zero after semantic check");
 345   if (native_flag) {
 346     if (right.native_flag) {
 347       return int_val_t(val.native / right.get_val());
 348     } else {
 349       BIGNUM *left_bn = to_openssl();
 350       BN_CTX *ctx = BN_CTX_new();
 351       BN_CTX_init(ctx);
 352       BN_div(left_bn, NULL, left_bn, right.get_val_openssl(), ctx);
 353       BN_CTX_free(ctx);
 354       if (BN_num_bits(left_bn) <= (int)sizeof(long long) * 8 - 1) {
 355         char *result_str = BN_bn2dec(left_bn);
 356         Int result_ll = string2Int(result_str, Location());
 357         OPENSSL_free(result_str);
 358         BN_free(left_bn);
 359         return int_val_t(result_ll);
 360       } else {
 361         return int_val_t(left_bn);
 362       }
 363     }
 364   } else {
 365     BIGNUM *result = BN_new();
 366     BIGNUM *right_bn;
 367     BN_CTX *ctx = BN_CTX_new();
 368     BN_CTX_init(ctx);
 369     right_bn = right.is_native() ? right.to_openssl() :
 370       right.get_val_openssl();
 371     BN_div(result, NULL, val.openssl, right_bn, ctx);
 372     BN_CTX_free(ctx);
 373     if (BN_num_bits(result) <= (int)sizeof(long long) * 8 - 1) {
 374       char *result_str = BN_bn2dec(result);
 375       Int result_ll = string2Int(result_str, Location());
 376       OPENSSL_free(result_str);
 377       return int_val_t(result_ll);
 378     } else {
 379       if (right.is_native())
 380         BN_free(right_bn);
 381       return int_val_t(result);
 382     }
 383   }
 384 }
 385
 386 int_val_t int_val_t::operator&(Int right) const
 387 {
 388   // TODO Right can be int_val_t.  Now it works only if right fits in
 389   // BN_ULONG.  If it's not true right must be converted to BIGNUM and the
 390   // bits should be set with BN_is_bit_set/BN_set_bit.
 391   BN_ULONG right_bn_ulong = (BN_ULONG)right;
 392   if (right != (long long)right_bn_ulong)
 393     FATAL_ERROR("Bitmask is too big");
 394   if (native_flag) {
 395     return int_val_t(val.native & right);
 396   } else {
 397     BIGNUM *tmp = BN_dup(val.openssl);
 398     BN_mask_bits(tmp, sizeof(BN_ULONG) * 8);
 399     BN_ULONG word = BN_get_word(tmp);
 400     BN_free(tmp);
 401     return int_val_t(word & right_bn_ulong);
 402   }
 403 }
 404
 405 int_val_t int_val_t::operator>>(Int right) const
 406 {
 407   if (native_flag) {
 408     // Shifting right (or left) with a number greater or equal to the bits of
 409     // the type of the left operand has an undefined behaviour.
 410     // http://bytes.com/groups/c/495137-right-shift-weird-result-why
 411     Int shifted_value = right >= static_cast<Int>(sizeof(Int) * 8) ? 0 :
 412       val.native >> right;
 413     return int_val_t(shifted_value);
 414   } else {
 415     BIGNUM *result = BN_new();
 416     BN_rshift(result, val.openssl, right);
 417     if (BN_num_bits(result) < (int)sizeof(long long) * 8 - 1) {
 418       char *result_str = BN_bn2dec(result);
 419       Int result_ll = string2Int(result_str, Location());
 420       OPENSSL_free(result_str);
 421       BN_free(result);
 422       return int_val_t(result_ll);
 423     } else {
 424       return int_val_t(result);
 425     }
 426   }
 427 }
 428
 429 const Int& int_val_t::get_val() const
 430 {
 431   if (!native_flag) FATAL_ERROR("Invalid conversion of a large integer value");
 432   return val.native;
 433 }
 434
 435 BIGNUM *int_val_t::get_val_openssl() const
 436 {
 437   if (native_flag) FATAL_ERROR("Invalid conversion of a large integer value");
 438   return val.openssl;
 439 }
 440
 441 Real int_val_t::to_real() const
 442 {
 443   if (native_flag) {
 444     return (double)val.native;
 445   } else {
 446     char *result_str = BN_bn2dec(val.openssl);
 447     Real result = 0.0;
 448     // Use fixed-point notation.  The mantissa is usually at most 52-bits.
 449     // Bigger integer values will be rounded.
 450     if (sscanf(result_str, "%lf", &result) != 1)
 451       FATAL_ERROR("Conversion of integer value `%s' to float failed",
 452                   result_str);  // No deallocation, it'll crash anyway...
 453     OPENSSL_free(result_str);
 454     return result;
 455   }
 456 }
 457
 458 int_val_t& int_val_t::operator=(const int_val_t& right)
 459 {
 460   if (!native_flag) BN_free(val.openssl);
 461   native_flag = right.native_flag;
 462   if (native_flag) val.native = right.get_val();
 463   else val.openssl = BN_dup(right.get_val_openssl());
 464   return *this;
 465 }
 466
 467 int_val_t& int_val_t::operator<<=(Int right)
 468 {
 469   // It makes no sense to support negative operands. GCC returns constant "0"
 470   // with "warning: left shift count is negative" for these shifts.
 471   // BN_set_word is not enough since sizeof(BN_ULONG) != sizeof(long long).
 472   // In TTCN-3 <<= right means >>= -right.
 473   if (right < 0) FATAL_ERROR("The second operand of bitwise shift operators "
 474     "cannot be negative");
 475   if (right == 0) return *this;
 476   if (native_flag) {
 477     BIGNUM *result = BN_new();
 478     BN_dec2bn(&result, Int2string(val.native).c_str());
 479     BN_lshift(result, result, right);
 480     if (BN_num_bits(result) > (int)sizeof(long long) * 8 - 1) {
 481       val.openssl = result;
 482       native_flag = false;
 483     } else {
 484       val.native <<= right;
 485       BN_free(result);
 486     }
 487   } else {
 488     BN_lshift(val.openssl, val.openssl, right);
 489   }
 490   return *this;
 491 }
 492
 493 int_val_t& int_val_t::operator>>=(Int right)
 494 {
 495   if (right < 0) FATAL_ERROR("The second operand of bitwise shift operators "
 496     "cannot be negative");
 497   if (right == 0) return *this;
 498   if (native_flag) {
 499     val.native >>= right;
 500   } else {
 501     BN_rshift(val.openssl, val.openssl, right);
 502     if (BN_num_bits(val.openssl) <= (int)sizeof(long long) * 8 - 1) {
 503       char *result_str = BN_bn2dec(val.openssl);
 504       Int result_ll = string2Int(result_str, Location());
 505       OPENSSL_free(result_str);
 506       native_flag = true;
 507       BN_free(val.openssl);
 508       val.native = result_ll;
 509     }
 510   }
 511   return *this;
 512 }
 513
 514 int_val_t& int_val_t::operator+=(Int right)
 515 {
 516   // Unfortunately we have to check the sign of the "right" operand and
 517   // perform addition or subtraction accordingly.
 518   if (right == 0) return *this;
 519   bool neg = right < 0;
 520   if (native_flag) {
 521     BIGNUM *result = BN_new();
 522     BN_set_word(result, (BN_ULONG)val.native);
 523     if (neg) BN_sub_word(result, (BN_ULONG)right);
 524     else BN_add_word(result, (BN_ULONG)right);
 525     if (BN_num_bits(result) > (int)sizeof(long long) * 8 - 1) {
 526       val.openssl = result;
 527       native_flag = false;
 528     } else {
 529       val.native += right;
 530       BN_free(result);
 531     }
 532   } else {
 533     if (neg) BN_sub_word(val.openssl, (BN_ULONG)right);
 534     else BN_add_word(val.openssl, (BN_ULONG)right);
 535     if (BN_num_bits(val.openssl) <= (int)sizeof(long long) * 8 - 1) {
 536       // TODO BN_ULONG != long long.
 537       BN_ULONG tmp = BN_get_word(val.openssl);
 538       if (BN_is_negative(val.openssl)) tmp *= -1;
 539       BN_free(val.openssl);
 540       val.native = tmp;
 541       native_flag = true;
 542     }
 543   }
 544   return *this;
 545 }
 546
 547 }  // Common