flow: fix some parent transition fallout
[smatch.git] / smatch_sval.c
blob39aa1741bdd41b2d57a721df6d17ed0c0d0e10d9
1 /*
2 * Copyright (C) 2012 Oracle.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
19 * Basically the point of sval is that it can hold both ULLONG_MAX and
20 * LLONG_MIN. If it is an unsigned type then we use sval.uvalue or if it is
21 * signed we use sval.value.
23 * I considered just using one bit to store whether the value was signed vs
24 * unsigned but I think it might help to have the type information so we know
25 * how to do type promotion.
29 #include "smatch.h"
30 #include "smatch_slist.h"
31 #include "smatch_extra.h"
33 __ALLOCATOR(sval_t, "svals", sval);
35 sval_t *sval_alloc(sval_t sval)
37 sval_t *ret;
39 ret = __alloc_sval(0);
40 *ret = sval;
41 return ret;
44 sval_t *sval_alloc_permanent(sval_t sval)
46 sval_t *ret;
48 ret = malloc(sizeof(*ret));
49 *ret = sval;
50 return ret;
53 sval_t sval_blank(struct expression *expr)
55 sval_t ret;
57 ret.type = get_type(expr);
58 if (!ret.type)
59 ret.type = &int_ctype;
60 ret.value = 123456789;
62 return ret;
65 sval_t sval_type_val(struct symbol *type, long long val)
67 sval_t ret;
69 if (!type)
70 type = &int_ctype;
72 ret.type = type;
73 ret.value = val;
74 return ret;
77 sval_t sval_from_val(struct expression *expr, long long val)
79 sval_t ret;
81 ret = sval_blank(expr);
82 ret.value = val;
83 ret = sval_cast(get_type(expr), ret);
85 return ret;
88 int sval_unsigned(sval_t sval)
90 return type_unsigned(sval.type);
93 int sval_signed(sval_t sval)
95 return !type_unsigned(sval.type);
98 int sval_bits(sval_t sval)
100 return type_bits(sval.type);
103 int sval_bits_used(sval_t sval)
105 int i;
107 for (i = 64; i >= 1; i--) {
108 if (sval.uvalue & (1ULL << (i - 1)))
109 return i;
111 return 0;
114 int sval_is_negative(sval_t sval)
116 if (type_unsigned(sval.type))
117 return 0;
118 if (sval.value < 0)
119 return 1;
120 return 0;
123 int sval_is_positive(sval_t sval)
125 return !sval_is_negative(sval);
128 int sval_is_min(sval_t sval)
130 sval_t min = sval_type_min(sval.type);
132 if (sval_unsigned(sval)) {
133 if (sval.uvalue == 0)
134 return 1;
135 return 0;
137 /* return true for less than min as well */
138 return (sval.value <= min.value);
141 int sval_is_max(sval_t sval)
143 sval_t max = sval_type_max(sval.type);
145 if (sval_unsigned(sval))
146 return (sval.uvalue >= max.value);
147 return (sval.value >= max.value);
150 int sval_is_a_min(sval_t sval)
152 if (sval_signed(sval) && sval.value == SHRT_MIN)
153 return 1;
154 if (sval_signed(sval) && sval.value == INT_MIN)
155 return 1;
156 if (sval_signed(sval) && sval.value == LLONG_MIN)
157 return 1;
158 return 0;
161 int sval_is_a_max(sval_t sval)
163 if (sval.uvalue == SHRT_MAX)
164 return 1;
165 if (sval.uvalue == INT_MAX)
166 return 1;
167 if (sval.uvalue == LLONG_MAX)
168 return 1;
169 if (sval.uvalue == USHRT_MAX)
170 return 1;
171 if (sval.uvalue == UINT_MAX)
172 return 1;
173 if (sval_unsigned(sval) && sval.uvalue == ULLONG_MAX)
174 return 1;
175 if (sval.value > valid_ptr_max - 1000 &&
176 sval.value < valid_ptr_max + 1000)
177 return 1;
178 return 0;
181 int sval_is_negative_min(sval_t sval)
183 if (!sval_is_negative(sval))
184 return 0;
185 return sval_is_min(sval);
188 int sval_cmp_t(struct symbol *type, sval_t one, sval_t two)
190 sval_t one_cast, two_cast;
192 one_cast = sval_cast(type, one);
193 two_cast = sval_cast(type, two);
194 return sval_cmp(one_cast, two_cast);
197 int sval_cmp_val(sval_t one, long long val)
199 sval_t sval;
201 sval = sval_type_val(&llong_ctype, val);
202 return sval_cmp(one, sval);
205 sval_t sval_min(sval_t one, sval_t two)
207 if (sval_cmp(one, two) > 0)
208 return two;
209 return one;
212 sval_t sval_max(sval_t one, sval_t two)
214 if (sval_cmp(one, two) < 0)
215 return two;
216 return one;
219 int sval_too_low(struct symbol *type, sval_t sval)
221 if (sval_is_negative(sval) && type_unsigned(type))
222 return 1;
223 if (type_signed(type) && sval_unsigned(sval))
224 return 0;
225 if (sval_cmp(sval, sval_type_min(type)) < 0)
226 return 1;
227 return 0;
230 int sval_too_high(struct symbol *type, sval_t sval)
232 if (sval_is_negative(sval))
233 return 0;
234 if (sval.uvalue > sval_type_max(type).uvalue)
235 return 1;
236 return 0;
239 int sval_fits(struct symbol *type, sval_t sval)
241 if (sval_too_low(type, sval))
242 return 0;
243 if (sval_too_high(type, sval))
244 return 0;
245 return 1;
248 sval_t sval_cast(struct symbol *type, sval_t sval)
250 sval_t ret;
252 if (!type)
253 type = &int_ctype;
255 ret.type = type;
256 switch (sval_bits(ret)) {
257 case 8:
258 if (sval_unsigned(ret))
259 ret.value = (long long)(unsigned char)sval.value;
260 else
261 ret.value = (long long)(char)sval.value;
262 break;
263 case 16:
264 if (sval_unsigned(ret))
265 ret.value = (long long)(unsigned short)sval.value;
266 else
267 ret.value = (long long)(short)sval.value;
268 break;
269 case 32:
270 if (sval_unsigned(ret))
271 ret.value = (long long)(unsigned int)sval.value;
272 else
273 ret.value = (long long)(int)sval.value;
274 break;
275 default:
276 ret.value = sval.value;
278 return ret;
282 sval_t sval_preop(sval_t sval, int op)
284 switch (op) {
285 case '!':
286 sval.value = !sval.value;
287 break;
288 case '~':
289 sval.value = ~sval.value;
290 sval = sval_cast(sval.type, sval);
291 break;
292 case '-':
293 sval.value = -sval.value;
294 sval = sval_cast(sval.type, sval);
295 break;
297 return sval;
300 static sval_t sval_binop_unsigned(struct symbol *type, sval_t left, int op, sval_t right)
302 sval_t ret;
304 ret.type = type;
305 switch (op) {
306 case '*':
307 ret.uvalue = left.uvalue * right.uvalue;
308 break;
309 case '/':
310 if (right.uvalue == 0) {
311 sm_msg("debug: %s: divide by zero", __func__);
312 ret.uvalue = 123456789;
313 } else {
314 ret.uvalue = left.uvalue / right.uvalue;
316 break;
317 case '+':
318 ret.uvalue = left.uvalue + right.uvalue;
319 break;
320 case '-':
321 ret.uvalue = left.uvalue - right.uvalue;
322 break;
323 case '%':
324 if (right.uvalue == 0) {
325 sm_msg("internal error: %s: MOD by zero", __func__);
326 ret.uvalue = 123456789;
327 } else {
328 ret.uvalue = left.uvalue % right.uvalue;
330 break;
331 case '|':
332 ret.uvalue = left.uvalue | right.uvalue;
333 break;
334 case '&':
335 ret.uvalue = left.uvalue & right.uvalue;
336 break;
337 case SPECIAL_RIGHTSHIFT:
338 ret.uvalue = left.uvalue >> right.uvalue;
339 break;
340 case SPECIAL_LEFTSHIFT:
341 ret.uvalue = left.uvalue << right.uvalue;
342 break;
343 case '^':
344 ret.uvalue = left.uvalue ^ right.uvalue;
345 break;
346 default:
347 sm_msg("internal error: %s: unhandled binop %s", __func__,
348 show_special(op));
349 ret.uvalue = 1234567;
351 return ret;
355 static sval_t sval_binop_signed(struct symbol *type, sval_t left, int op, sval_t right)
357 sval_t ret;
359 ret.type = type;
360 switch (op) {
361 case '*':
362 ret.value = left.value * right.value;
363 break;
364 case '/':
365 if (right.value == 0) {
366 sm_msg("debug: %s: divide by zero", __func__);
367 ret.value = 123456789;
368 } else if (left.value == LLONG_MIN && right.value == -1) {
369 sm_msg("debug: %s: invalid divide LLONG_MIN/-1", __func__);
370 ret.value = 12345678;
371 } else {
372 ret.value = left.value / right.value;
374 break;
375 case '+':
376 ret.value = left.value + right.value;
377 break;
378 case '-':
379 ret.value = left.value - right.value;
380 break;
381 case '%':
382 if (right.value == 0) {
383 sm_msg("internal error: %s: MOD by zero", __func__);
384 ret.value = 123456789;
385 } else {
386 ret.value = left.value % right.value;
388 break;
389 case '|':
390 ret.value = left.value | right.value;
391 break;
392 case '&':
393 ret.value = left.value & right.value;
394 break;
395 case SPECIAL_RIGHTSHIFT:
396 ret.value = left.value >> right.value;
397 break;
398 case SPECIAL_LEFTSHIFT:
399 ret.value = left.value << right.value;
400 break;
401 case '^':
402 ret.value = left.value ^ right.value;
403 break;
404 default:
405 sm_msg("internal error: %s: unhandled binop %s", __func__,
406 show_special(op));
407 ret.value = 1234567;
409 return ret;
412 sval_t sval_binop(sval_t left, int op, sval_t right)
414 struct symbol *type;
415 sval_t ret;
417 type = left.type;
418 if (sval_positive_bits(right) > sval_positive_bits(left))
419 type = right.type;
420 if (type_positive_bits(type) < 31)
421 type = &int_ctype;
423 if (type_unsigned(type))
424 ret = sval_binop_unsigned(type, left, op, right);
425 else
426 ret = sval_binop_signed(type, left, op, right);
427 return sval_cast(type, ret);
430 int sval_unop_overflows(sval_t sval, int op)
432 if (op != '-')
433 return 0;
434 if (sval_positive_bits(sval) == 32 && sval.value == INT_MIN)
435 return 1;
436 if (sval_positive_bits(sval) == 64 && sval.value == LLONG_MIN)
437 return 1;
438 if (sval_is_negative(sval))
439 return 0;
440 if (sval_signed(sval))
441 return 0;
442 if (sval_bits(sval) == 32 && sval.uvalue > INT_MAX)
443 return 1;
444 if (sval_bits(sval) == 64 && sval.uvalue > LLONG_MAX)
445 return 1;
446 return 0;
449 int sval_binop_overflows(sval_t left, int op, sval_t right)
451 struct symbol *type;
452 sval_t max, min;
454 type = left.type;
455 if (type_positive_bits(right.type) > type_positive_bits(left.type))
456 type = right.type;
457 if (type_positive_bits(type) < 31)
458 type = &int_ctype;
460 max = sval_type_max(type);
461 min = sval_type_min(type);
463 switch (op) {
464 case '+':
465 if (sval_is_negative(left) && sval_is_negative(right)) {
466 if (left.value < min.value + right.value)
467 return 1;
468 return 0;
470 if (sval_is_negative(left) || sval_is_negative(right))
471 return 0;
472 if (left.uvalue > max.uvalue - right.uvalue)
473 return 1;
474 return 0;
475 case '*':
476 return right.uvalue != 0 && left.uvalue > max.uvalue / right.uvalue;
477 case '-':
478 if (type_unsigned(type)) {
479 if (sval_cmp(left, right) < 0)
480 return 1;
481 return 0;
483 if (sval_is_negative(left) && sval_is_negative(right))
484 return 0;
486 if (sval_is_negative(left)) {
487 if (left.value < min.value + right.value)
488 return 1;
489 return 0;
491 if (sval_is_negative(right)) {
492 if (right.value == min.value)
493 return 1;
494 right = sval_preop(right, '-');
495 if (sval_binop_overflows(left, '+', right))
496 return 1;
497 return 0;
499 return 0;
500 case SPECIAL_LEFTSHIFT:
501 if (sval_cmp(left, sval_binop(max, invert_op(op), right)) > 0)
502 return 1;
503 return 0;
505 return 0;
508 unsigned long long fls_mask(unsigned long long uvalue)
510 unsigned long long high_bit = 0;
512 while (uvalue) {
513 uvalue >>= 1;
514 high_bit++;
517 if (high_bit == 0)
518 return 0;
520 return ((unsigned long long)-1) >> (64 - high_bit);
523 unsigned long long sval_fls_mask(sval_t sval)
525 return fls_mask(sval.uvalue);
528 const char *sval_to_str(sval_t sval)
530 char buf[30];
532 if (sval_unsigned(sval) && sval.value == ULLONG_MAX)
533 return "u64max";
534 if (sval_unsigned(sval) && sval.value == UINT_MAX)
535 return "u32max";
536 if (sval_unsigned(sval) && sval.value == USHRT_MAX)
537 return "u16max";
539 if (sval_signed(sval) && sval.value == LLONG_MAX)
540 return "s64max";
541 if (sval_signed(sval) && sval.value == INT_MAX)
542 return "s32max";
543 if (sval_signed(sval) && sval.value == SHRT_MAX)
544 return "s16max";
546 if (sval_signed(sval) && sval.value == SHRT_MIN)
547 return "s16min";
548 if (sval_signed(sval) && sval.value == INT_MIN)
549 return "s32min";
550 if (sval_signed(sval) && sval.value == LLONG_MIN)
551 return "s64min";
553 if (sval_unsigned(sval))
554 snprintf(buf, sizeof(buf), "%llu", sval.value);
555 else if (sval.value < 0)
556 snprintf(buf, sizeof(buf), "(%lld)", sval.value);
557 else
558 snprintf(buf, sizeof(buf), "%lld", sval.value);
560 return alloc_sname(buf);
563 const char *sval_to_numstr(sval_t sval)
565 char buf[30];
567 if (sval_unsigned(sval))
568 snprintf(buf, sizeof(buf), "%llu", sval.value);
569 else if (sval.value < 0)
570 snprintf(buf, sizeof(buf), "(%lld)", sval.value);
571 else
572 snprintf(buf, sizeof(buf), "%lld", sval.value);
574 return alloc_sname(buf);
577 sval_t ll_to_sval(long long val)
579 sval_t ret;
581 ret.type = &llong_ctype;
582 ret.value = val;
583 return ret;
586 static void free_svals(struct symbol *sym)
588 if (__inline_fn)
589 return;
590 clear_sval_alloc();
593 void register_sval(int my_id)
595 add_hook(&free_svals, AFTER_FUNC_HOOK);