compiler2/Int.cc

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