Commit | Line | Data |
---|---|---|
970ed795 EL |
1 | /////////////////////////////////////////////////////////////////////////////// |
2 | // Copyright (c) 2000-2014 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 |