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.
30 #include "smatch_slist.h"
31 #include "smatch_extra.h"
33 __ALLOCATOR(sval_t
, "svals", sval
);
35 sval_t
*sval_alloc(sval_t sval
)
39 ret
= __alloc_sval(0);
44 sval_t
*sval_alloc_permanent(sval_t sval
)
48 ret
= malloc(sizeof(*ret
));
53 sval_t
sval_blank(struct expression
*expr
)
57 ret
.type
= get_type(expr
);
59 ret
.type
= &int_ctype
;
60 ret
.value
= 123456789;
65 sval_t
sval_type_val(struct symbol
*type
, long long val
)
77 sval_t
sval_from_val(struct expression
*expr
, long long val
)
81 ret
= sval_blank(expr
);
83 ret
= sval_cast(get_type(expr
), ret
);
88 int sval_is_ptr(sval_t sval
)
92 return (sval
.type
->type
== SYM_PTR
|| sval
.type
->type
== SYM_ARRAY
);
95 int sval_unsigned(sval_t sval
)
97 if (is_ptr_type(sval
.type
))
99 return type_unsigned(sval
.type
);
102 int sval_signed(sval_t sval
)
104 return !type_unsigned(sval
.type
);
107 int sval_bits(sval_t sval
)
109 return type_bits(sval
.type
);
112 int sval_bits_used(sval_t sval
)
116 for (i
= 64; i
>= 1; i
--) {
117 if (sval
.uvalue
& (1ULL << (i
- 1)))
123 int sval_is_negative(sval_t sval
)
125 if (type_unsigned(sval
.type
))
132 int sval_is_positive(sval_t sval
)
134 return !sval_is_negative(sval
);
137 int sval_is_min(sval_t sval
)
139 sval_t min
= sval_type_min(sval
.type
);
141 if (sval_unsigned(sval
)) {
142 if (sval
.uvalue
== 0)
146 /* return true for less than min as well */
147 return (sval
.value
<= min
.value
);
150 int sval_is_max(sval_t sval
)
152 sval_t max
= sval_type_max(sval
.type
);
154 if (sval_unsigned(sval
))
155 return (sval
.uvalue
>= max
.value
);
156 return (sval
.value
>= max
.value
);
159 int sval_is_a_min(sval_t sval
)
161 if (sval_is_min(sval
))
163 if (sval_signed(sval
) && sval
.value
== SHRT_MIN
)
165 if (sval_signed(sval
) && sval
.value
== INT_MIN
)
167 if (sval_signed(sval
) && sval
.value
== LLONG_MIN
)
172 int sval_is_a_max(sval_t sval
)
174 if (sval_is_max(sval
))
176 if (sval
.uvalue
== SHRT_MAX
)
178 if (sval
.uvalue
== INT_MAX
)
180 if (sval
.uvalue
== LLONG_MAX
)
182 if (sval
.uvalue
== USHRT_MAX
)
184 if (sval
.uvalue
== UINT_MAX
)
186 if (sval_unsigned(sval
) && sval
.uvalue
== ULLONG_MAX
)
188 if (sval
.value
> valid_ptr_max
- 1000 &&
189 sval
.value
< valid_ptr_max
+ 1000)
194 int sval_is_negative_min(sval_t sval
)
196 if (!sval_is_negative(sval
))
198 return sval_is_min(sval
);
201 int sval_cmp_t(struct symbol
*type
, sval_t one
, sval_t two
)
203 sval_t one_cast
, two_cast
;
205 one_cast
= sval_cast(type
, one
);
206 two_cast
= sval_cast(type
, two
);
207 return sval_cmp(one_cast
, two_cast
);
210 int sval_cmp_val(sval_t one
, long long val
)
214 sval
= sval_type_val(&llong_ctype
, val
);
215 return sval_cmp(one
, sval
);
218 sval_t
sval_min(sval_t one
, sval_t two
)
220 if (sval_cmp(one
, two
) > 0)
225 sval_t
sval_max(sval_t one
, sval_t two
)
227 if (sval_cmp(one
, two
) < 0)
232 int sval_too_low(struct symbol
*type
, sval_t sval
)
234 if (sval_is_negative(sval
) && type_unsigned(type
))
236 if (type_signed(type
) && sval_unsigned(sval
))
238 if (type_signed(sval
.type
) &&
239 sval
.value
< sval_type_min(type
).value
)
241 if (sval_cmp(sval
, sval_type_min(type
)) < 0)
246 int sval_too_high(struct symbol
*type
, sval_t sval
)
248 if (sval_is_negative(sval
))
250 if (sval
.uvalue
> sval_type_max(type
).uvalue
)
255 int sval_fits(struct symbol
*type
, sval_t sval
)
257 if (sval_too_low(type
, sval
))
259 if (sval_too_high(type
, sval
))
264 sval_t
sval_cast(struct symbol
*type
, sval_t sval
)
272 switch (sval_bits(ret
)) {
274 ret
.value
= !!sval
.value
;
277 if (sval_unsigned(ret
))
278 ret
.value
= (long long)(unsigned char)sval
.value
;
280 ret
.value
= (long long)(char)sval
.value
;
283 if (sval_unsigned(ret
))
284 ret
.value
= (long long)(unsigned short)sval
.value
;
286 ret
.value
= (long long)(short)sval
.value
;
289 if (sval_unsigned(ret
))
290 ret
.value
= (long long)(unsigned int)sval
.value
;
292 ret
.value
= (long long)(int)sval
.value
;
295 ret
.value
= sval
.value
;
301 sval_t
sval_preop(sval_t sval
, int op
)
305 sval
.value
= !sval
.value
;
308 sval
.value
= ~sval
.value
;
309 sval
= sval_cast(sval
.type
, sval
);
312 sval
.value
= -sval
.value
;
313 sval
= sval_cast(sval
.type
, sval
);
319 static sval_t
sval_binop_unsigned(struct symbol
*type
, sval_t left
, int op
, sval_t right
)
326 ret
.uvalue
= left
.uvalue
* right
.uvalue
;
329 if (right
.uvalue
== 0) {
330 sm_msg("debug: %s: divide by zero", __func__
);
331 ret
.uvalue
= 123456789;
333 ret
.uvalue
= left
.uvalue
/ right
.uvalue
;
337 ret
.uvalue
= left
.uvalue
+ right
.uvalue
;
340 ret
.uvalue
= left
.uvalue
- right
.uvalue
;
343 if (right
.uvalue
== 0) {
344 sm_perror(" %s: MOD by zero", __func__
);
345 ret
.uvalue
= 123456789;
347 ret
.uvalue
= left
.uvalue
% right
.uvalue
;
351 ret
.uvalue
= left
.uvalue
| right
.uvalue
;
354 ret
.uvalue
= left
.uvalue
& right
.uvalue
;
356 case SPECIAL_RIGHTSHIFT
:
357 ret
.uvalue
= left
.uvalue
>> right
.uvalue
;
359 case SPECIAL_LEFTSHIFT
:
360 ret
.uvalue
= left
.uvalue
<< right
.uvalue
;
363 ret
.uvalue
= left
.uvalue
^ right
.uvalue
;
366 sm_perror(" %s: unhandled binop %s", __func__
,
368 ret
.uvalue
= 1234567;
374 static sval_t
sval_binop_signed(struct symbol
*type
, sval_t left
, int op
, sval_t right
)
381 ret
.value
= left
.value
* right
.value
;
384 if (right
.value
== 0) {
385 sm_debug("%s: divide by zero", __func__
);
386 ret
.value
= 123456789;
387 } else if (left
.value
== LLONG_MIN
&& right
.value
== -1) {
388 sm_debug("%s: invalid divide LLONG_MIN/-1", __func__
);
389 ret
.value
= 12345678;
391 ret
.value
= left
.value
/ right
.value
;
395 ret
.value
= left
.value
+ right
.value
;
398 ret
.value
= left
.value
- right
.value
;
401 if (right
.value
== 0) {
402 sm_perror(" %s: MOD by zero", __func__
);
403 ret
.value
= 123456789;
405 ret
.value
= left
.value
% right
.value
;
409 ret
.value
= left
.value
| right
.value
;
412 ret
.value
= left
.value
& right
.value
;
414 case SPECIAL_RIGHTSHIFT
:
415 ret
.value
= left
.value
>> right
.value
;
417 case SPECIAL_LEFTSHIFT
:
418 ret
.value
= left
.value
<< right
.value
;
421 ret
.value
= left
.value
^ right
.value
;
424 sm_perror(" %s: unhandled binop %s", __func__
,
431 static sval_t
ptr_binop(struct symbol
*type
, sval_t left
, int op
, sval_t right
)
436 if (op
!= '+' && op
!= '-')
437 return sval_binop_unsigned(type
, left
, op
, right
);
440 if (type
->type
== SYM_PTR
)
441 type
= get_real_base_type(type
);
442 align
= type
->ctype
.alignment
;
447 if (type_is_ptr(left
.type
))
448 ret
.value
= left
.value
+ right
.value
* align
;
450 ret
.value
= left
.value
* align
+ right
.value
;
452 if (!type_is_ptr(left
.type
)) {
453 left
.value
= -left
.value
;
454 ret
= ptr_binop(type
, left
, '+', right
);
455 } else if (!type_is_ptr(right
.type
)) {
456 right
.value
= -right
.value
;
457 ret
= ptr_binop(type
, left
, '+', right
);
459 ret
.value
= (left
.value
- right
.value
) / align
;
466 sval_t
sval_binop(sval_t left
, int op
, sval_t right
)
471 type
= get_promoted_type(left
.type
, right
.type
);
473 if (type_is_ptr(type
))
474 ret
= ptr_binop(type
, left
, op
, right
);
475 else if (type_unsigned(type
))
476 ret
= sval_binop_unsigned(type
, left
, op
, right
);
478 ret
= sval_binop_signed(type
, left
, op
, right
);
479 return sval_cast(type
, ret
);
482 int sval_unop_overflows(sval_t sval
, int op
)
486 if (sval_positive_bits(sval
) == 32 && sval
.value
== INT_MIN
)
488 if (sval_positive_bits(sval
) == 64 && sval
.value
== LLONG_MIN
)
490 if (sval_is_negative(sval
))
492 if (sval_signed(sval
))
494 if (sval_bits(sval
) == 32 && sval
.uvalue
> INT_MAX
)
496 if (sval_bits(sval
) == 64 && sval
.uvalue
> LLONG_MAX
)
501 int sval_binop_overflows(sval_t left
, int op
, sval_t right
)
507 if (type_positive_bits(right
.type
) > type_positive_bits(left
.type
))
509 if (type_positive_bits(type
) < 31)
512 max
= sval_type_max(type
);
513 min
= sval_type_min(type
);
517 if (sval_is_negative(left
) && sval_is_negative(right
)) {
518 if (left
.value
< min
.value
+ right
.value
)
522 if (sval_is_negative(left
) || sval_is_negative(right
))
524 if (left
.uvalue
> max
.uvalue
- right
.uvalue
)
528 if (type_signed(type
)) {
529 if (left
.value
== 0 || right
.value
== 0)
531 if (left
.value
> max
.value
/ right
.value
)
533 if (left
.value
== -1 || right
.value
== -1)
535 return left
.value
!= left
.value
* right
.value
/ right
.value
;
538 return right
.uvalue
!= 0 && left
.uvalue
> max
.uvalue
/ right
.uvalue
;
540 if (type_unsigned(type
)) {
541 if (sval_cmp(left
, right
) < 0)
545 if (sval_is_negative(left
) && sval_is_negative(right
))
548 if (sval_is_negative(left
)) {
549 if (left
.value
< min
.value
+ right
.value
)
553 if (sval_is_negative(right
)) {
554 if (right
.value
== min
.value
)
556 right
= sval_preop(right
, '-');
557 if (sval_binop_overflows(left
, '+', right
))
562 case SPECIAL_LEFTSHIFT
:
563 if (sval_cmp(left
, sval_binop(max
, invert_op(op
), right
)) > 0)
570 int sval_binop_overflows_no_sign(sval_t left
, int op
, sval_t right
)
576 if (type_positive_bits(right
.type
) > type_positive_bits(left
.type
))
578 if (type_positive_bits(type
) <= 31)
581 type
= &ullong_ctype
;
583 left
= sval_cast(type
, left
);
584 right
= sval_cast(type
, right
);
585 return sval_binop_overflows(left
, op
, right
);
588 unsigned long long fls_mask(unsigned long long uvalue
)
590 unsigned long long high_bit
= 0;
600 return ((unsigned long long)-1) >> (64 - high_bit
);
603 unsigned long long sval_fls_mask(sval_t sval
)
605 return fls_mask(sval
.uvalue
);
608 const char *sval_to_str(sval_t sval
)
612 if (sval_is_ptr(sval
) && sval
.value
== valid_ptr_max
)
614 if (sval_unsigned(sval
) && sval
.value
== ULLONG_MAX
)
616 if (sval_unsigned(sval
) && sval
.value
== UINT_MAX
)
618 if (sval
.value
== USHRT_MAX
)
621 if (sval_signed(sval
) && sval
.value
== LLONG_MAX
)
623 if (sval
.value
== INT_MAX
)
625 if (sval
.value
== SHRT_MAX
)
628 if (sval_signed(sval
) && sval
.value
== SHRT_MIN
)
630 if (sval_signed(sval
) && sval
.value
== INT_MIN
)
632 if (sval_signed(sval
) && sval
.value
== LLONG_MIN
)
635 if (sval_unsigned(sval
))
636 snprintf(buf
, sizeof(buf
), "%llu", sval
.value
);
637 else if (sval
.value
< 0)
638 snprintf(buf
, sizeof(buf
), "(%lld)", sval
.value
);
640 snprintf(buf
, sizeof(buf
), "%lld", sval
.value
);
642 return alloc_sname(buf
);
645 const char *sval_to_str_or_err_ptr(sval_t sval
)
649 if (option_project
!= PROJ_KERNEL
||
650 !is_ptr_type(sval
.type
))
651 return sval_to_str(sval
);
653 if (sval
.uvalue
>= -4905ULL) {
654 snprintf(buf
, sizeof(buf
), "(%lld)", sval
.value
);
655 return alloc_sname(buf
);
658 return sval_to_str(sval
);
661 const char *sval_to_numstr(sval_t sval
)
665 if (sval_unsigned(sval
))
666 snprintf(buf
, sizeof(buf
), "%llu", sval
.value
);
667 else if (sval
.value
< 0)
668 snprintf(buf
, sizeof(buf
), "(%lld)", sval
.value
);
670 snprintf(buf
, sizeof(buf
), "%lld", sval
.value
);
672 return alloc_sname(buf
);
675 sval_t
ll_to_sval(long long val
)
679 ret
.type
= &llong_ctype
;
684 static void free_svals(struct symbol
*sym
)
691 void register_sval(int my_id
)
693 add_hook(&free_svals
, AFTER_FUNC_HOOK
);