?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
function_hooks: do set_fresh_mtag_returns() later
[smatch.git] / smatch_ranges.c
blobd1e2fc416c64479b33af7e634e8f855e32f6739a
1 /*
2 * Copyright (C) 2009 Dan Carpenter.
3 *
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.
8 *
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.
13 *
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
16 */
17
18 #include "parse.h"
19 #include "smatch.h"
20 #include "smatch_extra.h"
21 #include "smatch_slist.h"
22
23 ALLOCATOR(data_info, "smatch extra data");
24 ALLOCATOR(data_range, "data range");
25 __DO_ALLOCATOR(struct data_range, sizeof(struct data_range), __alignof__(struct data_range),
26 "permanent ranges", perm_data_range);
27 __DECLARE_ALLOCATOR(struct ptr_list, rl_ptrlist);
28
29 bool is_err_ptr(sval_t sval)
30 {
31 if (option_project != PROJ_KERNEL)
32 return false;
33 if (!type_is_ptr(sval.type))
34 return false;
35 if (sval.uvalue < -4095ULL)
36 return false;
37 return true;
38 }
39
40 bool is_err_or_null(struct range_list *rl)
41 {
42 struct range_list *no_null;
43
44 if (!rl)
45 return false;
46
47 if (rl_min(rl).value == 0 && rl_max(rl).value == 0)
48 return true;
49
50 if (rl_min(rl).value != 0)
51 no_null = rl;
52 else
53 no_null = remove_range(rl, rl_min(rl), rl_min(rl));
54
55 return is_err_ptr(rl_min(no_null)) && is_err_ptr(rl_max(no_null));
56 }
57
58 static bool is_oxdead(struct range_list *rl)
59 {
60 sval_t sval;
61
62 /* check for 0xdead000000000000 */
63 if (!rl_to_sval(rl, &sval))
64 return false;
65 if ((sval.uvalue >> (bits_in_pointer - 16)) == 0xdead)
66 return true;
67
68 return false;
69 }
70
71 bool is_noderef_ptr_rl(struct range_list *rl)
72 {
73 if (!rl)
74 return false;
75
76 if (rl_min(rl).value == 0 && rl_max(rl).value == 0)
77 return true;
78 if (is_err_or_null(rl))
79 return true;
80 if (is_oxdead(rl))
81 return true;
82 return false;
83 }
84
85 bool rl_is_zero(struct range_list *rl)
86 {
87 if (!rl)
88 return false;
89 if (rl_min(rl).value == 0 && rl_max(rl).value == 0)
90 return true;
91 return false;
92 }
93
94 static char *get_err_pointer_str(struct data_range *drange)
95 {
96 static char buf[20];
97
98 /*
99 * The kernel has error pointers where you do essentially:
100 *
101 * return (void *)(unsigned long)-12;
102 *
103 * But what I want here is to print -12 instead of the unsigned version
104 * of that.
105 *
106 */
107 if (!is_err_ptr(drange->min))
108 return NULL;
109
110 if (drange->min.value == drange->max.value)
111 snprintf(buf, sizeof(buf), "(%lld)", drange->min.value);
112 else
113 snprintf(buf, sizeof(buf), "(%lld)-(%lld)", drange->min.value, drange->max.value);
114 return buf;
115 }
116
117 char *show_rl(struct range_list *list)
118 {
119 struct data_range *prev_drange = NULL;
120 struct data_range *tmp;
121 char full[255];
122 char *p = full;
123 char *prev = full;
124 char *err_ptr;
125 int remain;
126 int i = 0;
127
128 full[0] = '\0';
129
130 FOR_EACH_PTR(list, tmp) {
131 remain = full + sizeof(full) - p;
132 if (remain < 48) {
133 snprintf(prev, full + sizeof(full) - prev, ",%s-%s",
134 sval_to_str(prev_drange->min),
135 sval_to_str(sval_type_max(prev_drange->min.type)));
136 break;
137 }
138 prev_drange = tmp;
139 prev = p;
140
141 err_ptr = get_err_pointer_str(tmp);
142 if (err_ptr) {
143 p += snprintf(p, remain, "%s%s", i++ ? "," : "", err_ptr);
144 } else if (sval_cmp(tmp->min, tmp->max) == 0) {
145 p += snprintf(p, remain, "%s%s", i++ ? "," : "",
146 sval_to_str(tmp->min));
147 } else {
148 p += snprintf(p, remain, "%s%s-%s", i++ ? "," : "",
149 sval_to_str(tmp->min),
150 sval_to_str(tmp->max));
151 }
152 } END_FOR_EACH_PTR(tmp);
153
154 return alloc_sname(full);
155 }
156
157 void free_all_rl(void)
158 {
159 clear_rl_ptrlist_alloc();
160 }
161
162 static int sval_too_big(struct symbol *type, sval_t sval)
163 {
164 if (type_bits(type) >= 32 &&
165 type_bits(sval.type) <= type_bits(type))
166 return 0;
167 if (sval.uvalue <= ((1ULL << type_bits(type)) - 1))
168 return 0;
169 if (type_signed(sval.type)) {
170 if (type_unsigned(type)) {
171 unsigned long long neg = ~sval.uvalue;
172 if (neg <= sval_type_max(type).uvalue)
173 return 0;
174 }
175 if (sval.value < sval_type_min(type).value)
176 return 1;
177 if (sval.value > sval_type_max(type).value)
178 return 1;
179 return 0;
180 }
181 if (sval.uvalue > sval_type_max(type).uvalue)
182 return 1;
183 return 0;
184 }
185
186 static int truncates_nicely(struct symbol *type, sval_t min, sval_t max)
187 {
188 unsigned long long mask;
189 int bits = type_bits(type);
190
191 if (type_is_fp(min.type) && !type_is_fp(type))
192 return 0;
193
194 if (bits >= type_bits(min.type))
195 return 0;
196
197 mask = -1ULL << bits;
198 return (min.uvalue & mask) == (max.uvalue & mask);
199 }
200
201 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
202 {
203 /* If we're just adding a number, cast it and add it */
204 if (sval_cmp(min, max) == 0) {
205 add_range(rl, sval_cast(type, min), sval_cast(type, max));
206 return;
207 }
208
209 /* If the range is within the type range then add it */
210 if (sval_fits(type, min) && sval_fits(type, max)) {
211 add_range(rl, sval_cast(type, min), sval_cast(type, max));
212 return;
213 }
214
215 if (truncates_nicely(type, min, max)) {
216 add_range(rl, sval_cast(type, min), sval_cast(type, max));
217 return;
218 }
219
220 /*
221 * If the range we are adding has more bits than the range type then
222 * add the whole range type. Eg:
223 * 0x8000000000000000 - 0xf000000000000000 -> cast to int
224 *
225 */
226 if (sval_too_big(type, min) || sval_too_big(type, max)) {
227 add_range(rl, sval_type_min(type), sval_type_max(type));
228 return;
229 }
230
231 /* Cast negative values to high positive values */
232 if (sval_is_negative(min) && type_unsigned(type)) {
233 if (sval_is_positive(max)) {
234 if (sval_too_high(type, max)) {
235 add_range(rl, sval_type_min(type), sval_type_max(type));
236 return;
237 }
238 add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
239 max = sval_type_max(type);
240 } else {
241 max = sval_cast(type, max);
242 }
243 min = sval_cast(type, min);
244 add_range(rl, min, max);
245 }
246
247 /* Cast high positive numbers to negative */
248 if (sval_unsigned(max) && sval_is_negative(sval_cast(type, max))) {
249 if (!sval_is_negative(sval_cast(type, min))) {
250 add_range(rl, sval_cast(type, min), sval_type_max(type));
251 min = sval_type_min(type);
252 } else {
253 min = sval_cast(type, min);
254 }
255 max = sval_cast(type, max);
256 add_range(rl, min, max);
257 }
258
259 add_range(rl, sval_cast(type, min), sval_cast(type, max));
260 return;
261 }
262
263 static int str_to_comparison_arg_helper(const char *str,
264 struct expression *call, int *comparison,
265 struct expression **arg, const char **endp)
266 {
267 int param;
268 const char *c = str;
269
270 if (*c != '[')
271 return 0;
272 c++;
273
274 if (*c == '<') {
275 c++;
276 if (*c == '=') {
277 *comparison = SPECIAL_LTE;
278 c++;
279 } else {
280 *comparison = '<';
281 }
282 } else if (*c == '=') {
283 c++;
284 c++;
285 *comparison = SPECIAL_EQUAL;
286 } else if (*c == '>') {
287 c++;
288 if (*c == '=') {
289 *comparison = SPECIAL_GTE;
290 c++;
291 } else {
292 *comparison = '>';
293 }
294 } else if (*c == '!') {
295 c++;
296 c++;
297 *comparison = SPECIAL_NOTEQUAL;
298 } else if (*c == '$') {
299 *comparison = SPECIAL_EQUAL;
300 } else {
301 return 0;
302 }
303
304 if (*c != '$')
305 return 0;
306 c++;
307
308 param = strtoll(c, (char **)&c, 10);
309 /*
310 * FIXME: handle parameter math. [==$1 + 100]
311 *
312 */
313 if (*c == ' ')
314 return 0;
315
316 if (*c == ',' || *c == ']')
317 c++; /* skip the ']' character */
318 if (endp)
319 *endp = (char *)c;
320
321 if (!call)
322 return 0;
323 *arg = get_argument_from_call_expr(call->args, param);
324 if (!*arg)
325 return 0;
326 if (*c == '-' && *(c + 1) == '>') {
327 char buf[256];
328 int n;
329
330 n = snprintf(buf, sizeof(buf), "$%s", c);
331 if (n >= sizeof(buf))
332 return 0;
333 if (buf[n - 1] == ']')
334 buf[n - 1] = '\0';
335 *arg = gen_expression_from_key(*arg, buf);
336 while (*c && *c != ']')
337 c++;
338 }
339 return 1;
340 }
341
342 int str_to_comparison_arg(const char *str, struct expression *call, int *comparison, struct expression **arg)
343 {
344 while (1) {
345 if (!*str)
346 return 0;
347 if (*str == '[')
348 break;
349 str++;
350 }
351 return str_to_comparison_arg_helper(str, call, comparison, arg, NULL);
352 }
353
354 static int get_val_from_key(int use_max, struct symbol *type, const char *c, struct expression *call, const char **endp, sval_t *sval)
355 {
356 struct expression *arg;
357 int comparison;
358 sval_t ret, tmp;
359
360 if (use_max)
361 ret = sval_type_max(type);
362 else
363 ret = sval_type_min(type);
364
365 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp)) {
366 *sval = ret;
367 return 0;
368 }
369
370 if (use_max && get_implied_max(arg, &tmp)) {
371 ret = tmp;
372 if (comparison == '<') {
373 tmp.value = 1;
374 ret = sval_binop(ret, '-', tmp);
375 }
376 }
377 if (!use_max && get_implied_min(arg, &tmp)) {
378 ret = tmp;
379 if (comparison == '>') {
380 tmp.value = 1;
381 ret = sval_binop(ret, '+', tmp);
382 }
383 }
384
385 *sval = ret;
386 return 1;
387 }
388
389 static sval_t add_one(sval_t sval)
390 {
391 sval.value++;
392 return sval;
393 }
394
395 static sval_t sub_one(sval_t sval)
396 {
397 sval.value--;
398 return sval;
399 }
400
401 void filter_by_comparison(struct range_list **rl, int comparison, struct range_list *right)
402 {
403 struct range_list *left_orig = *rl;
404 struct range_list *right_orig = right;
405 struct range_list *ret_rl = *rl;
406 struct symbol *cast_type;
407 sval_t min, max;
408
409 if (comparison == UNKNOWN_COMPARISON)
410 return;
411
412 cast_type = rl_type(left_orig);
413 if (sval_type_max(rl_type(left_orig)).uvalue < sval_type_max(rl_type(right_orig)).uvalue)
414 cast_type = rl_type(right_orig);
415 if (sval_type_max(cast_type).uvalue < INT_MAX)
416 cast_type = &int_ctype;
417
418 min = sval_type_min(cast_type);
419 max = sval_type_max(cast_type);
420 left_orig = cast_rl(cast_type, left_orig);
421 right_orig = cast_rl(cast_type, right_orig);
422
423 switch (comparison) {
424 case '<':
425 case SPECIAL_UNSIGNED_LT:
426 ret_rl = remove_range(left_orig, rl_max(right_orig), max);
427 break;
428 case SPECIAL_LTE:
429 case SPECIAL_UNSIGNED_LTE:
430 if (!sval_is_max(rl_max(right_orig)))
431 ret_rl = remove_range(left_orig, add_one(rl_max(right_orig)), max);
432 break;
433 case SPECIAL_EQUAL:
434 ret_rl = rl_intersection(left_orig, right_orig);
435 break;
436 case SPECIAL_GTE:
437 case SPECIAL_UNSIGNED_GTE:
438 if (!sval_is_min(rl_min(right_orig)))
439 ret_rl = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
440 break;
441 case '>':
442 case SPECIAL_UNSIGNED_GT:
443 ret_rl = remove_range(left_orig, min, rl_min(right_orig));
444 break;
445 case SPECIAL_NOTEQUAL:
446 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
447 ret_rl = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
448 break;
449 default:
450 sm_perror("unhandled comparison %s", show_special(comparison));
451 return;
452 }
453
454 *rl = cast_rl(rl_type(*rl), ret_rl);
455 }
456
457 static struct range_list *filter_by_comparison_call(const char *c, struct expression *call, const char **endp, struct range_list *start_rl)
458 {
459 struct symbol *type;
460 struct expression *arg;
461 struct range_list *casted_start, *right_orig;
462 int comparison;
463
464 /* For when we have a function that takes a function pointer. */
465 if (!call || call->type != EXPR_CALL)
466 return start_rl;
467
468 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp))
469 return start_rl;
470
471 if (!get_implied_rl(arg, &right_orig))
472 return start_rl;
473
474 type = &int_ctype;
475 if (type_positive_bits(rl_type(start_rl)) > type_positive_bits(type))
476 type = rl_type(start_rl);
477 if (type_positive_bits(rl_type(right_orig)) > type_positive_bits(type))
478 type = rl_type(right_orig);
479
480 casted_start = cast_rl(type, start_rl);
481 right_orig = cast_rl(type, right_orig);
482
483 filter_by_comparison(&casted_start, comparison, right_orig);
484 return cast_rl(rl_type(start_rl), casted_start);
485 }
486
487 static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, const char *c, const char **endp)
488 {
489 const char *start = c;
490 sval_t ret;
491
492 if (type == &float_ctype)
493 return sval_type_fval(type, strtof(start, (char **)endp));
494 else if (type == &double_ctype)
495 return sval_type_fval(type, strtod(start, (char **)endp));
496 else if (type == &ldouble_ctype)
497 return sval_type_fval(type, strtold(start, (char **)endp));
498
499 if (!strncmp(start, "max", 3)) {
500 ret = sval_type_max(type);
501 c += 3;
502 } else if (!strncmp(start, "u64max", 6)) {
503 ret = sval_type_val(type, ULLONG_MAX);
504 c += 6;
505 } else if (!strncmp(start, "s64max", 6)) {
506 ret = sval_type_val(type, LLONG_MAX);
507 c += 6;
508 } else if (!strncmp(start, "u32max", 6)) {
509 ret = sval_type_val(type, UINT_MAX);
510 c += 6;
511 } else if (!strncmp(start, "s32max", 6)) {
512 ret = sval_type_val(type, INT_MAX);
513 c += 6;
514 } else if (!strncmp(start, "u16max", 6)) {
515 ret = sval_type_val(type, USHRT_MAX);
516 c += 6;
517 } else if (!strncmp(start, "s16max", 6)) {
518 ret = sval_type_val(type, SHRT_MAX);
519 c += 6;
520 } else if (!strncmp(start, "min", 3)) {
521 ret = sval_type_min(type);
522 c += 3;
523 } else if (!strncmp(start, "s64min", 6)) {
524 ret = sval_type_val(type, LLONG_MIN);
525 c += 6;
526 } else if (!strncmp(start, "s32min", 6)) {
527 ret = sval_type_val(type, INT_MIN);
528 c += 6;
529 } else if (!strncmp(start, "s16min", 6)) {
530 ret = sval_type_val(type, SHRT_MIN);
531 c += 6;
532 } else if (!strncmp(start, "long_min", 8)) {
533 ret = sval_type_val(type, LONG_MIN);
534 c += 8;
535 } else if (!strncmp(start, "long_max", 8)) {
536 ret = sval_type_val(type, LONG_MAX);
537 c += 8;
538 } else if (!strncmp(start, "ulong_max", 9)) {
539 ret = sval_type_val(type, ULONG_MAX);
540 c += 9;
541 } else if (!strncmp(start, "ptr_max", 7)) {
542 ret = sval_type_val(type, valid_ptr_max);
543 c += 7;
544 } else if (start[0] == '[') {
545 /* this parses [==p0] comparisons */
546 get_val_from_key(1, type, start, call, &c, &ret);
547 } else if (type_positive_bits(type) == 64) {
548 ret = sval_type_val(type, strtoull(start, (char **)&c, 0));
549 } else {
550 ret = sval_type_val(type, strtoll(start, (char **)&c, 0));
551 }
552 *endp = c;
553 return ret;
554 }
555
556 static const char *jump_to_call_math(const char *value)
557 {
558 const char *c = value;
559
560 while (*c && *c != '[')
561 c++;
562
563 if (!*c)
564 return NULL;
565 c++;
566 if (*c == '<' || *c == '=' || *c == '>' || *c == '!')
567 return NULL;
568
569 return c;
570 }
571
572 static struct range_list *get_param_return_rl(struct expression *call, const char *call_math)
573 {
574 struct expression *arg;
575 int param;
576
577 call_math += 3;
578 param = atoi(call_math);
579
580 arg = get_argument_from_call_expr(call->args, param);
581 if (!arg)
582 return NULL;
583
584 return db_return_vals_no_args(arg);
585 }
586
587 static void str_to_rl_helper(struct expression *call, struct symbol *type, const char *str, const char **endp, struct range_list **rl)
588 {
589 struct range_list *rl_tmp = NULL;
590 sval_t prev_min, min, max;
591 const char *c;
592
593 prev_min = sval_type_min(type);
594 min = sval_type_min(type);
595 max = sval_type_max(type);
596 c = str;
597 while (*c != '\0' && *c != '[') {
598 if (*c == '+') {
599 if (sval_cmp(min, sval_type_min(type)) != 0)
600 min = max;
601 max = sval_type_max(type);
602 add_range_t(type, &rl_tmp, min, max);
603 break;
604 }
605 if (*c == '(')
606 c++;
607 min = parse_val(0, call, type, c, &c);
608 if (!sval_fits(type, min))
609 min = sval_type_min(type);
610 max = min;
611 if (*c == ')')
612 c++;
613 if (*c == '\0' || *c == '[') {
614 add_range_t(type, &rl_tmp, min, min);
615 break;
616 }
617 if (*c == ',') {
618 add_range_t(type, &rl_tmp, min, min);
619 c++;
620 continue;
621 }
622 if (*c == '+') {
623 min = prev_min;
624 max = sval_type_max(type);
625 add_range_t(type, &rl_tmp, min, max);
626 c++;
627 if (*c == '[' || *c == '\0')
628 break;
629 }
630 if (*c != '-') {
631 sm_msg("debug XXX: trouble parsing %s c = %s", str, c);
632 break;
633 }
634 c++;
635 if (*c == '(')
636 c++;
637 max = parse_val(1, call, type, c, &c);
638 if (!sval_fits(type, max))
639 max = sval_type_max(type);
640 if (*c == '+') {
641 max = sval_type_max(type);
642 add_range_t(type, &rl_tmp, min, max);
643 c++;
644 if (*c == '[' || *c == '\0')
645 break;
646 }
647 prev_min = max;
648 add_range_t(type, &rl_tmp, min, max);
649 if (*c == ')')
650 c++;
651 if (*c == ',')
652 c++;
653 }
654
655 *rl = rl_tmp;
656 *endp = c;
657 }
658
659 static void str_to_dinfo(struct expression *call, struct symbol *type, const char *value, struct data_info *dinfo)
660 {
661 struct range_list *math_rl;
662 const char *call_math;
663 const char *c;
664 struct range_list *rl = NULL;
665
666 if (!type)
667 type = &llong_ctype;
668
669 if (strcmp(value, "empty") == 0)
670 return;
671
672 if (strncmp(value, "[==$", 4) == 0) {
673 struct expression *arg;
674 int comparison;
675
676 if (!str_to_comparison_arg(value, call, &comparison, &arg))
677 return;
678 if (!get_implied_rl(arg, &rl))
679 return;
680 goto cast;
681 }
682
683 str_to_rl_helper(call, type, value, &c, &rl);
684 if (*c == '\0')
685 goto cast;
686
687 call_math = jump_to_call_math(value);
688 if (call_math && call_math[0] == 'r') {
689 math_rl = get_param_return_rl(call, call_math);
690 if (math_rl)
691 rl = rl_intersection(rl, math_rl);
692 goto cast;
693 }
694 if (call_math && parse_call_math_rl(call, call_math, &math_rl)) {
695 rl = rl_intersection(rl, math_rl);
696 goto cast;
697 }
698
699 /*
700 * For now if we already tried to handle the call math and couldn't
701 * figure it out then bail.
702 */
703 if (jump_to_call_math(c) == c + 1)
704 goto cast;
705
706 rl = filter_by_comparison_call(c, call, &c, rl);
707
708 cast:
709 rl = cast_rl(type, rl);
710 dinfo->value_ranges = rl;
711 }
712
713 static int rl_is_sane(struct range_list *rl)
714 {
715 struct data_range *tmp;
716 struct symbol *type;
717
718 type = rl_type(rl);
719 FOR_EACH_PTR(rl, tmp) {
720 if (!sval_fits(type, tmp->min))
721 return 0;
722 if (!sval_fits(type, tmp->max))
723 return 0;
724 if (sval_cmp(tmp->min, tmp->max) > 0)
725 return 0;
726 } END_FOR_EACH_PTR(tmp);
727
728 return 1;
729 }
730
731 void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
732 {
733 struct data_info dinfo = {};
734
735 str_to_dinfo(NULL, type, value, &dinfo);
736 if (!rl_is_sane(dinfo.value_ranges))
737 dinfo.value_ranges = alloc_whole_rl(type);
738 *rl = dinfo.value_ranges;
739 }
740
741 void call_results_to_rl(struct expression *expr, struct symbol *type, const char *value, struct range_list **rl)
742 {
743 struct data_info dinfo = {};
744
745 str_to_dinfo(strip_expr(expr), type, value, &dinfo);
746 *rl = dinfo.value_ranges;
747 }
748
749 int is_whole_rl(struct range_list *rl)
750 {
751 struct data_range *drange;
752
753 if (ptr_list_empty((struct ptr_list *)rl))
754 return 0;
755 drange = first_ptr_list((struct ptr_list *)rl);
756 if (sval_is_min(drange->min) && sval_is_max(drange->max))
757 return 1;
758 return 0;
759 }
760
761 int is_unknown_ptr(struct range_list *rl)
762 {
763 struct data_range *drange;
764 int cnt = 0;
765
766 if (is_whole_rl(rl))
767 return 1;
768
769 FOR_EACH_PTR(rl, drange) {
770 if (++cnt >= 3)
771 return 0;
772 if (sval_cmp(drange->min, valid_ptr_min_sval) == 0 &&
773 sval_cmp(drange->max, valid_ptr_max_sval) == 0)
774 return 1;
775 } END_FOR_EACH_PTR(drange);
776
777 return 0;
778 }
779
780 bool is_whole_ptr_rl(struct range_list *rl)
781 {
782 struct data_range *drange;
783 int cnt = 0;
784
785 /* A whole pointer range is either 0-ulong_max or NULL, valid range, and
786 * error pointers.
787 */
788 if (is_whole_rl(rl))
789 return true;
790
791 if (ptr_list_size((struct ptr_list *)rl) != 2)
792 return false;
793
794 FOR_EACH_PTR(rl, drange) {
795 cnt++;
796
797 if (cnt == 1) {
798 if (drange->min.value != 0 ||
799 drange->max.value != 0)
800 return false;
801 } if (cnt == 2) {
802 if (drange->min.value != valid_ptr_min ||
803 drange->max.value != ULONG_MAX)
804 return false;
805 }
806 } END_FOR_EACH_PTR(drange);
807
808 return true;
809 }
810
811 int is_whole_rl_non_zero(struct range_list *rl)
812 {
813 struct data_range *drange;
814
815 if (ptr_list_empty((struct ptr_list *)rl))
816 return 0;
817 drange = first_ptr_list((struct ptr_list *)rl);
818 if (sval_unsigned(drange->min) &&
819 drange->min.value == 1 &&
820 sval_is_max(drange->max))
821 return 1;
822 if (!sval_is_min(drange->min) || drange->max.value != -1)
823 return 0;
824 drange = last_ptr_list((struct ptr_list *)rl);
825 if (drange->min.value != 1 || !sval_is_max(drange->max))
826 return 0;
827 return 1;
828 }
829
830 sval_t rl_min(struct range_list *rl)
831 {
832 struct data_range *drange;
833 sval_t ret;
834
835 ret.type = &llong_ctype;
836 ret.value = LLONG_MIN;
837 if (ptr_list_empty((struct ptr_list *)rl))
838 return ret;
839 drange = first_ptr_list((struct ptr_list *)rl);
840 return drange->min;
841 }
842
843 sval_t rl_max(struct range_list *rl)
844 {
845 struct data_range *drange;
846 sval_t ret;
847
848 ret.type = &llong_ctype;
849 ret.value = LLONG_MAX;
850 if (ptr_list_empty((struct ptr_list *)rl))
851 return ret;
852 drange = last_ptr_list((struct ptr_list *)rl);
853 return drange->max;
854 }
855
856 int rl_to_sval(struct range_list *rl, sval_t *sval)
857 {
858 sval_t min, max;
859
860 if (!rl)
861 return 0;
862
863 min = rl_min(rl);
864 max = rl_max(rl);
865 if (sval_cmp(min, max) != 0)
866 return 0;
867 *sval = min;
868 return 1;
869 }
870
871 struct symbol *rl_type(struct range_list *rl)
872 {
873 if (!rl)
874 return NULL;
875 return rl_min(rl).type;
876 }
877
878 static struct data_range *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
879 {
880 struct data_range *ret;
881
882 if (perm)
883 ret = __alloc_perm_data_range(0);
884 else
885 ret = __alloc_data_range(0);
886 ret->min = min;
887 ret->max = max;
888 return ret;
889 }
890
891 struct data_range *alloc_range(sval_t min, sval_t max)
892 {
893 return alloc_range_helper_sval(min, max, 0);
894 }
895
896 struct data_range *alloc_range_perm(sval_t min, sval_t max)
897 {
898 return alloc_range_helper_sval(min, max, 1);
899 }
900
901 struct range_list *alloc_rl(sval_t min, sval_t max)
902 {
903 struct range_list *rl = NULL;
904
905 if (sval_cmp(min, max) > 0)
906 return alloc_whole_rl(min.type);
907
908 add_range(&rl, min, max);
909 return rl;
910 }
911
912 struct range_list *alloc_whole_rl(struct symbol *type)
913 {
914 if (!type || type_positive_bits(type) < 0)
915 type = &llong_ctype;
916 if (type->type == SYM_ARRAY)
917 type = &ptr_ctype;
918
919 return alloc_rl(sval_type_min(type), sval_type_max(type));
920 }
921
922 static bool collapse_pointer_rl(struct range_list **rl, sval_t min, sval_t max)
923 {
924 struct range_list *new_rl = NULL;
925 struct data_range *tmp;
926 static bool recurse;
927 bool ret = false;
928 int cnt = 0;
929
930 /*
931 * With the mtag work, then we end up getting huge lists of mtags.
932 * That seems cool, but the problem is that we can only store about
933 * 8-10 mtags in the DB before we truncate the list. Also the mtags
934 * aren't really used at all so it's a waste of resources for now...
935 * In the future, we maybe will revisit this code.
936 *
937 */
938
939 if (recurse)
940 return false;
941 recurse = true;
942 if (!type_is_ptr(min.type))
943 goto out;
944
945 if (ptr_list_size((struct ptr_list *)*rl) < 8)
946 goto out;
947 FOR_EACH_PTR(*rl, tmp) {
948 if (!is_err_ptr(tmp->min))
949 cnt++;
950 } END_FOR_EACH_PTR(tmp);
951 if (cnt < 8)
952 goto out;
953
954 FOR_EACH_PTR(*rl, tmp) {
955 if (sval_cmp(tmp->min, valid_ptr_min_sval) >= 0 &&
956 sval_cmp(tmp->max, valid_ptr_max_sval) <= 0)
957 add_range(&new_rl, valid_ptr_min_sval, valid_ptr_max_sval);
958 else
959 add_range(&new_rl, tmp->min, tmp->max);
960 } END_FOR_EACH_PTR(tmp);
961
962 add_range(&new_rl, min, max);
963
964 *rl = new_rl;
965 ret = true;
966 out:
967 recurse = false;
968 return ret;
969 }
970
971 extern int rl_ptrlist_hack;
972 void add_range(struct range_list **list, sval_t min, sval_t max)
973 {
974 struct data_range *tmp;
975 struct data_range *new = NULL;
976 int check_next = 0;
977
978 /*
979 * There is at least on valid reason why the types might be confusing
980 * and that's when you have a void pointer and on some paths you treat
981 * it as a u8 pointer and on other paths you treat it as a u16 pointer.
982 * This case is hard to deal with.
983 *
984 * There are other cases where we probably should be more specific about
985 * the types than we are. For example, we end up merging a lot of ulong
986 * with pointers and I have not figured out why we do that.
987 *
988 * But this hack works for both cases, I think. We cast it to pointers
989 * or we use the bigger size.
990 *
991 */
992 if (*list && rl_type(*list) != min.type) {
993 if (rl_type(*list)->type == SYM_PTR) {
994 min = sval_cast(rl_type(*list), min);
995 max = sval_cast(rl_type(*list), max);
996 } else if (min.type->type == SYM_PTR) {
997 *list = cast_rl(min.type, *list);
998 } else if (type_bits(rl_type(*list)) >= type_bits(min.type)) {
999 min = sval_cast(rl_type(*list), min);
1000 max = sval_cast(rl_type(*list), max);
1001 } else {
1002 *list = cast_rl(min.type, *list);
1003 }
1004 }
1005
1006 if (sval_cmp(min, max) > 0) {
1007 min = sval_type_min(min.type);
1008 max = sval_type_max(min.type);
1009 }
1010
1011 if (collapse_pointer_rl(list, min, max))
1012 return;
1013
1014 /*
1015 * FIXME: This has a problem merging a range_list like: min-0,3-max
1016 * with a range like 1-2. You end up with min-2,3-max instead of
1017 * just min-max.
1018 */
1019 FOR_EACH_PTR(*list, tmp) {
1020 if (check_next) {
1021 /* Sometimes we overlap with more than one range
1022 so we have to delete or modify the next range. */
1023 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
1024 /* join 2 ranges here */
1025 new->max = tmp->max;
1026 DELETE_CURRENT_PTR(tmp);
1027 return;
1028 }
1029
1030 /* Doesn't overlap with the next one. */
1031 if (sval_cmp(max, tmp->min) < 0)
1032 return;
1033
1034 if (sval_cmp(max, tmp->max) <= 0) {
1035 /* Partially overlaps the next one. */
1036 new->max = tmp->max;
1037 DELETE_CURRENT_PTR(tmp);
1038 return;
1039 } else {
1040 /* Completely overlaps the next one. */
1041 DELETE_CURRENT_PTR(tmp);
1042 /* there could be more ranges to delete */
1043 continue;
1044 }
1045 }
1046 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
1047 /* join 2 ranges into a big range */
1048 new = alloc_range(min, tmp->max);
1049 REPLACE_CURRENT_PTR(tmp, new);
1050 return;
1051 }
1052 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
1053 new = alloc_range(min, max);
1054 INSERT_CURRENT(new, tmp);
1055 return;
1056 }
1057 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
1058 if (sval_cmp(max, tmp->max) < 0)
1059 max = tmp->max;
1060 else
1061 check_next = 1;
1062 new = alloc_range(min, max);
1063 REPLACE_CURRENT_PTR(tmp, new);
1064 if (!check_next)
1065 return;
1066 continue;
1067 }
1068 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
1069 return;
1070 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
1071 min = tmp->min;
1072 new = alloc_range(min, max);
1073 REPLACE_CURRENT_PTR(tmp, new);
1074 check_next = 1;
1075 continue;
1076 }
1077 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
1078 /* join 2 ranges into a big range */
1079 new = alloc_range(tmp->min, max);
1080 REPLACE_CURRENT_PTR(tmp, new);
1081 check_next = 1;
1082 continue;
1083 }
1084 /* the new range is entirely above the existing ranges */
1085 } END_FOR_EACH_PTR(tmp);
1086 if (check_next)
1087 return;
1088 new = alloc_range(min, max);
1089
1090 rl_ptrlist_hack = 1;
1091 add_ptr_list(list, new);
1092 rl_ptrlist_hack = 0;
1093 }
1094
1095 struct range_list *clone_rl(struct range_list *list)
1096 {
1097 struct data_range *tmp;
1098 struct range_list *ret = NULL;
1099
1100 FOR_EACH_PTR(list, tmp) {
1101 add_ptr_list(&ret, tmp);
1102 } END_FOR_EACH_PTR(tmp);
1103 return ret;
1104 }
1105
1106 struct range_list *clone_rl_permanent(struct range_list *list)
1107 {
1108 struct data_range *tmp;
1109 struct data_range *new;
1110 struct range_list *ret = NULL;
1111
1112 FOR_EACH_PTR(list, tmp) {
1113 new = alloc_range_perm(tmp->min, tmp->max);
1114 add_ptr_list(&ret, new);
1115 } END_FOR_EACH_PTR(tmp);
1116 return ret;
1117 }
1118
1119 struct range_list *rl_union(struct range_list *one, struct range_list *two)
1120 {
1121 struct data_range *tmp;
1122 struct range_list *ret = NULL;
1123
1124 FOR_EACH_PTR(one, tmp) {
1125 add_range(&ret, tmp->min, tmp->max);
1126 } END_FOR_EACH_PTR(tmp);
1127 FOR_EACH_PTR(two, tmp) {
1128 add_range(&ret, tmp->min, tmp->max);
1129 } END_FOR_EACH_PTR(tmp);
1130 return ret;
1131 }
1132
1133 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
1134 {
1135 struct data_range *tmp;
1136 struct range_list *ret = NULL;
1137
1138 if (!list)
1139 return NULL;
1140
1141 min = sval_cast(rl_type(list), min);
1142 max = sval_cast(rl_type(list), max);
1143 if (sval_cmp(min, max) > 0) {
1144 sval_t tmp = min;
1145 min = max;
1146 max = tmp;
1147 }
1148
1149 FOR_EACH_PTR(list, tmp) {
1150 if (sval_cmp(tmp->max, min) < 0) {
1151 add_range(&ret, tmp->min, tmp->max);
1152 continue;
1153 }
1154 if (sval_cmp(tmp->min, max) > 0) {
1155 add_range(&ret, tmp->min, tmp->max);
1156 continue;
1157 }
1158 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
1159 continue;
1160 if (sval_cmp(tmp->min, min) >= 0) {
1161 max.value++;
1162 add_range(&ret, max, tmp->max);
1163 } else if (sval_cmp(tmp->max, max) <= 0) {
1164 min.value--;
1165 add_range(&ret, tmp->min, min);
1166 } else {
1167 min.value--;
1168 max.value++;
1169 add_range(&ret, tmp->min, min);
1170 add_range(&ret, max, tmp->max);
1171 }
1172 } END_FOR_EACH_PTR(tmp);
1173 return ret;
1174 }
1175
1176 int ranges_equiv(struct data_range *one, struct data_range *two)
1177 {
1178 if (!one && !two)
1179 return 1;
1180 if (!one || !two)
1181 return 0;
1182 if (sval_cmp(one->min, two->min) != 0)
1183 return 0;
1184 if (sval_cmp(one->max, two->max) != 0)
1185 return 0;
1186 return 1;
1187 }
1188
1189 int rl_equiv(struct range_list *one, struct range_list *two)
1190 {
1191 struct data_range *one_range;
1192 struct data_range *two_range;
1193
1194 if (one == two)
1195 return 1;
1196
1197 PREPARE_PTR_LIST(one, one_range);
1198 PREPARE_PTR_LIST(two, two_range);
1199 for (;;) {
1200 if (!one_range && !two_range)
1201 return 1;
1202 if (!ranges_equiv(one_range, two_range))
1203 return 0;
1204 NEXT_PTR_LIST(one_range);
1205 NEXT_PTR_LIST(two_range);
1206 }
1207 FINISH_PTR_LIST(two_range);
1208 FINISH_PTR_LIST(one_range);
1209
1210 return 1;
1211 }
1212
1213 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
1214 {
1215 switch (comparison) {
1216 case '<':
1217 case SPECIAL_UNSIGNED_LT:
1218 if (sval_cmp(left->min, right->max) < 0)
1219 return 1;
1220 return 0;
1221 case SPECIAL_UNSIGNED_LTE:
1222 case SPECIAL_LTE:
1223 if (sval_cmp(left->min, right->max) <= 0)
1224 return 1;
1225 return 0;
1226 case SPECIAL_EQUAL:
1227 if (sval_cmp(left->max, right->min) < 0)
1228 return 0;
1229 if (sval_cmp(left->min, right->max) > 0)
1230 return 0;
1231 return 1;
1232 case SPECIAL_UNSIGNED_GTE:
1233 case SPECIAL_GTE:
1234 if (sval_cmp(left->max, right->min) >= 0)
1235 return 1;
1236 return 0;
1237 case '>':
1238 case SPECIAL_UNSIGNED_GT:
1239 if (sval_cmp(left->max, right->min) > 0)
1240 return 1;
1241 return 0;
1242 case SPECIAL_NOTEQUAL:
1243 if (sval_cmp(left->min, left->max) != 0)
1244 return 1;
1245 if (sval_cmp(right->min, right->max) != 0)
1246 return 1;
1247 if (sval_cmp(left->min, right->min) != 0)
1248 return 1;
1249 return 0;
1250 default:
1251 sm_perror("unhandled comparison %d", comparison);
1252 return 0;
1253 }
1254 return 0;
1255 }
1256
1257 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
1258 {
1259 if (left)
1260 return true_comparison_range(var, comparison, val);
1261 else
1262 return true_comparison_range(val, comparison, var);
1263 }
1264
1265 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
1266 {
1267 switch (comparison) {
1268 case '<':
1269 case SPECIAL_UNSIGNED_LT:
1270 if (sval_cmp(left->max, right->min) >= 0)
1271 return 1;
1272 return 0;
1273 case SPECIAL_UNSIGNED_LTE:
1274 case SPECIAL_LTE:
1275 if (sval_cmp(left->max, right->min) > 0)
1276 return 1;
1277 return 0;
1278 case SPECIAL_EQUAL:
1279 if (sval_cmp(left->min, left->max) != 0)
1280 return 1;
1281 if (sval_cmp(right->min, right->max) != 0)
1282 return 1;
1283 if (sval_cmp(left->min, right->min) != 0)
1284 return 1;
1285 return 0;
1286 case SPECIAL_UNSIGNED_GTE:
1287 case SPECIAL_GTE:
1288 if (sval_cmp(left->min, right->max) < 0)
1289 return 1;
1290 return 0;
1291 case '>':
1292 case SPECIAL_UNSIGNED_GT:
1293 if (sval_cmp(left->min, right->max) <= 0)
1294 return 1;
1295 return 0;
1296 case SPECIAL_NOTEQUAL:
1297 if (sval_cmp(left->max, right->min) < 0)
1298 return 0;
1299 if (sval_cmp(left->min, right->max) > 0)
1300 return 0;
1301 return 1;
1302 default:
1303 sm_perror("unhandled comparison %d", comparison);
1304 return 0;
1305 }
1306 return 0;
1307 }
1308
1309 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
1310 {
1311 if (left)
1312 return false_comparison_range_sval(var, comparison, val);
1313 else
1314 return false_comparison_range_sval(val, comparison, var);
1315 }
1316
1317 int possibly_true(struct expression *left, int comparison, struct expression *right)
1318 {
1319 struct range_list *rl_left, *rl_right;
1320 struct data_range *tmp_left, *tmp_right;
1321 struct symbol *type;
1322
1323 if (comparison == UNKNOWN_COMPARISON)
1324 return 1;
1325 if (!get_implied_rl(left, &rl_left))
1326 return 1;
1327 if (!get_implied_rl(right, &rl_right))
1328 return 1;
1329
1330 type = rl_type(rl_left);
1331 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
1332 type = rl_type(rl_right);
1333 if (type_positive_bits(type) < 31)
1334 type = &int_ctype;
1335
1336 rl_left = cast_rl(type, rl_left);
1337 rl_right = cast_rl(type, rl_right);
1338
1339 FOR_EACH_PTR(rl_left, tmp_left) {
1340 FOR_EACH_PTR(rl_right, tmp_right) {
1341 if (true_comparison_range(tmp_left, comparison, tmp_right))
1342 return 1;
1343 } END_FOR_EACH_PTR(tmp_right);
1344 } END_FOR_EACH_PTR(tmp_left);
1345 return 0;
1346 }
1347
1348 int possibly_false(struct expression *left, int comparison, struct expression *right)
1349 {
1350 struct range_list *rl_left, *rl_right;
1351 struct data_range *tmp_left, *tmp_right;
1352 struct symbol *type;
1353
1354 if (!get_implied_rl(left, &rl_left))
1355 return 1;
1356 if (!get_implied_rl(right, &rl_right))
1357 return 1;
1358
1359 type = rl_type(rl_left);
1360 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
1361 type = rl_type(rl_right);
1362 if (type_positive_bits(type) < 31)
1363 type = &int_ctype;
1364
1365 rl_left = cast_rl(type, rl_left);
1366 rl_right = cast_rl(type, rl_right);
1367
1368 FOR_EACH_PTR(rl_left, tmp_left) {
1369 FOR_EACH_PTR(rl_right, tmp_right) {
1370 if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
1371 return 1;
1372 } END_FOR_EACH_PTR(tmp_right);
1373 } END_FOR_EACH_PTR(tmp_left);
1374 return 0;
1375 }
1376
1377 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1378 {
1379 struct data_range *left_tmp, *right_tmp;
1380 struct symbol *type;
1381
1382 if (!left_ranges || !right_ranges || comparison == UNKNOWN_COMPARISON)
1383 return 1;
1384
1385 type = rl_type(left_ranges);
1386 if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1387 type = rl_type(right_ranges);
1388 if (type_positive_bits(type) < 31)
1389 type = &int_ctype;
1390
1391 left_ranges = cast_rl(type, left_ranges);
1392 right_ranges = cast_rl(type, right_ranges);
1393
1394 FOR_EACH_PTR(left_ranges, left_tmp) {
1395 FOR_EACH_PTR(right_ranges, right_tmp) {
1396 if (true_comparison_range(left_tmp, comparison, right_tmp))
1397 return 1;
1398 } END_FOR_EACH_PTR(right_tmp);
1399 } END_FOR_EACH_PTR(left_tmp);
1400 return 0;
1401 }
1402
1403 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1404 {
1405 struct data_range *left_tmp, *right_tmp;
1406 struct symbol *type;
1407
1408 if (!left_ranges || !right_ranges || comparison == UNKNOWN_COMPARISON)
1409 return 1;
1410
1411 type = rl_type(left_ranges);
1412 if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1413 type = rl_type(right_ranges);
1414 if (type_positive_bits(type) < 31)
1415 type = &int_ctype;
1416
1417 left_ranges = cast_rl(type, left_ranges);
1418 right_ranges = cast_rl(type, right_ranges);
1419
1420 FOR_EACH_PTR(left_ranges, left_tmp) {
1421 FOR_EACH_PTR(right_ranges, right_tmp) {
1422 if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
1423 return 1;
1424 } END_FOR_EACH_PTR(right_tmp);
1425 } END_FOR_EACH_PTR(left_tmp);
1426 return 0;
1427 }
1428
1429 /* FIXME: the _rl here stands for right left so really it should be _lr */
1430 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1431 {
1432 if (left)
1433 return possibly_true_rl(a, comparison, b);
1434 else
1435 return possibly_true_rl(b, comparison, a);
1436 }
1437
1438 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1439 {
1440 if (left)
1441 return possibly_false_rl(a, comparison, b);
1442 else
1443 return possibly_false_rl(b, comparison, a);
1444 }
1445
1446 int rl_has_sval(struct range_list *rl, sval_t sval)
1447 {
1448 struct data_range *tmp;
1449
1450 FOR_EACH_PTR(rl, tmp) {
1451 if (sval_cmp(tmp->min, sval) <= 0 &&
1452 sval_cmp(tmp->max, sval) >= 0)
1453 return 1;
1454 } END_FOR_EACH_PTR(tmp);
1455 return 0;
1456 }
1457
1458 void tack_on(struct range_list **list, struct data_range *drange)
1459 {
1460 add_ptr_list(list, drange);
1461 }
1462
1463 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
1464 {
1465 add_ptr_list(rl_stack, rl);
1466 }
1467
1468 struct range_list *pop_rl(struct range_list_stack **rl_stack)
1469 {
1470 struct range_list *rl;
1471
1472 rl = last_ptr_list((struct ptr_list *)*rl_stack);
1473 delete_ptr_list_last((struct ptr_list **)rl_stack);
1474 return rl;
1475 }
1476
1477 struct range_list *top_rl(struct range_list_stack *rl_stack)
1478 {
1479 struct range_list *rl;
1480
1481 rl = last_ptr_list((struct ptr_list *)rl_stack);
1482 return rl;
1483 }
1484
1485 void filter_top_rl(struct range_list_stack **rl_stack, struct range_list *filter)
1486 {
1487 struct range_list *rl;
1488
1489 rl = pop_rl(rl_stack);
1490 rl = rl_filter(rl, filter);
1491 push_rl(rl_stack, rl);
1492 }
1493
1494 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
1495 {
1496 struct data_range *tmp;
1497 struct range_list *ret = NULL;
1498 sval_t min, max;
1499
1500 if (!rl)
1501 return NULL;
1502
1503 if (!type || type == rl_type(rl))
1504 return rl;
1505
1506 FOR_EACH_PTR(rl, tmp) {
1507 min = tmp->min;
1508 max = tmp->max;
1509 if (type_bits(type) < type_bits(rl_type(rl))) {
1510 min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
1511 max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
1512 }
1513 if (sval_cmp(min, max) > 0) {
1514 min = sval_cast(type, min);
1515 max = sval_cast(type, max);
1516 }
1517 add_range_t(type, &ret, min, max);
1518 } END_FOR_EACH_PTR(tmp);
1519
1520 return ret;
1521 }
1522
1523 int rl_fits_in_type(struct range_list *rl, struct symbol *type)
1524 {
1525 if (type_bits(rl_type(rl)) <= type_bits(type))
1526 return 1;
1527 if (sval_cmp(rl_max(rl), sval_type_max(type)) > 0)
1528 return 0;
1529 if (sval_is_negative(rl_min(rl)) &&
1530 sval_cmp(rl_min(rl), sval_type_min(type)) < 0)
1531 return 0;
1532 return 1;
1533 }
1534
1535 static int rl_type_consistent(struct range_list *rl)
1536 {
1537 struct data_range *tmp;
1538 struct symbol *type;
1539
1540 type = rl_type(rl);
1541 FOR_EACH_PTR(rl, tmp) {
1542 if (type != tmp->min.type || type != tmp->max.type)
1543 return 0;
1544 } END_FOR_EACH_PTR(tmp);
1545 return 1;
1546 }
1547
1548 static struct range_list *cast_to_bool(struct range_list *rl)
1549 {
1550 struct data_range *tmp;
1551 struct range_list *ret = NULL;
1552 int has_one = 0;
1553 int has_zero = 0;
1554 sval_t min = { .type = &bool_ctype };
1555 sval_t max = { .type = &bool_ctype };
1556
1557 FOR_EACH_PTR(rl, tmp) {
1558 if (tmp->min.value || tmp->max.value)
1559 has_one = 1;
1560 if (sval_is_negative(tmp->min) &&
1561 sval_is_negative(tmp->max))
1562 continue;
1563 if (tmp->min.value == 0 ||
1564 tmp->max.value == 0)
1565 has_zero = 1;
1566 if (sval_is_negative(tmp->min) &&
1567 tmp->max.value > 0)
1568 has_zero = 1;
1569 } END_FOR_EACH_PTR(tmp);
1570
1571 if (!has_zero)
1572 min.value = 1;
1573 if (has_one)
1574 max.value = 1;
1575
1576 add_range(&ret, min, max);
1577 return ret;
1578 }
1579
1580 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
1581 {
1582 struct data_range *tmp;
1583 struct range_list *ret = NULL;
1584
1585 if (!rl)
1586 return NULL;
1587
1588 if (!type)
1589 return rl;
1590 if (!rl_is_sane(rl))
1591 return alloc_whole_rl(type);
1592 if (type == rl_type(rl) && rl_type_consistent(rl))
1593 return rl;
1594
1595 if (type == &bool_ctype)
1596 return cast_to_bool(rl);
1597
1598 FOR_EACH_PTR(rl, tmp) {
1599 add_range_t(type, &ret, tmp->min, tmp->max);
1600 } END_FOR_EACH_PTR(tmp);
1601
1602 if (!ret)
1603 return alloc_whole_rl(type);
1604
1605 return ret;
1606 }
1607
1608 /*
1609 * This is the opposite of rl_intersection().
1610 */
1611 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
1612 {
1613 struct data_range *tmp;
1614
1615 FOR_EACH_PTR(filter, tmp) {
1616 rl = remove_range(rl, tmp->min, tmp->max);
1617 } END_FOR_EACH_PTR(tmp);
1618
1619 return rl;
1620 }
1621
1622 struct range_list *do_intersection(struct range_list *one_rl, struct range_list *two_rl)
1623 {
1624 struct data_range *one, *two;
1625 struct range_list *ret = NULL;
1626
1627
1628 PREPARE_PTR_LIST(one_rl, one);
1629 PREPARE_PTR_LIST(two_rl, two);
1630
1631 while (true) {
1632 if (!one || !two)
1633 break;
1634 if (sval_cmp(one->max, two->min) < 0) {
1635 NEXT_PTR_LIST(one);
1636 continue;
1637 }
1638 if (sval_cmp(one->min, two->min) < 0 && sval_cmp(one->max, two->max) <= 0) {
1639 add_range(&ret, two->min, one->max);
1640 NEXT_PTR_LIST(one);
1641 continue;
1642 }
1643 if (sval_cmp(one->min, two->min) >= 0 && sval_cmp(one->max, two->max) <= 0) {
1644 add_range(&ret, one->min, one->max);
1645 NEXT_PTR_LIST(one);
1646 continue;
1647 }
1648 if (sval_cmp(one->min, two->min) < 0 && sval_cmp(one->max, two->max) > 0) {
1649 add_range(&ret, two->min, two->max);
1650 NEXT_PTR_LIST(two);
1651 continue;
1652 }
1653 if (sval_cmp(one->min, two->max) <= 0 && sval_cmp(one->max, two->max) > 0) {
1654 add_range(&ret, one->min, two->max);
1655 NEXT_PTR_LIST(two);
1656 continue;
1657 }
1658 if (sval_cmp(one->min, two->max) <= 0) {
1659 sm_fatal("error calculating intersection of '%s' and '%s'", show_rl(one_rl), show_rl(two_rl));
1660 return NULL;
1661 }
1662 NEXT_PTR_LIST(two);
1663 }
1664
1665 FINISH_PTR_LIST(two);
1666 FINISH_PTR_LIST(one);
1667
1668 return ret;
1669 }
1670
1671 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
1672 {
1673 struct range_list *ret;
1674 struct symbol *ret_type;
1675 struct symbol *small_type;
1676 struct symbol *large_type;
1677
1678 if (!one || !two)
1679 return NULL;
1680
1681 ret_type = rl_type(one);
1682 small_type = rl_type(one);
1683 large_type = rl_type(two);
1684
1685 if (type_bits(rl_type(two)) < type_bits(small_type)) {
1686 small_type = rl_type(two);
1687 large_type = rl_type(one);
1688 }
1689
1690 one = cast_rl(large_type, one);
1691 two = cast_rl(large_type, two);
1692
1693 ret = do_intersection(one, two);
1694 return cast_rl(ret_type, ret);
1695 }
1696
1697 static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
1698 {
1699 sval_t zero;
1700 sval_t max;
1701
1702 max = rl_max(right);
1703 if (sval_is_max(max))
1704 return left;
1705 if (max.value == 0)
1706 return NULL;
1707 max.value--;
1708 if (sval_is_negative(max))
1709 return NULL;
1710 if (sval_cmp(rl_max(left), max) < 0)
1711 return left;
1712 zero = max;
1713 zero.value = 0;
1714 return alloc_rl(zero, max);
1715 }
1716
1717 static struct range_list *get_neg_rl(struct range_list *rl)
1718 {
1719 struct data_range *tmp;
1720 struct data_range *new;
1721 struct range_list *ret = NULL;
1722
1723 if (!rl)
1724 return NULL;
1725 if (sval_is_positive(rl_min(rl)))
1726 return NULL;
1727
1728 FOR_EACH_PTR(rl, tmp) {
1729 if (sval_is_positive(tmp->min))
1730 break;
1731 if (sval_is_positive(tmp->max)) {
1732 new = alloc_range(tmp->min, tmp->max);
1733 new->max.value = -1;
1734 add_range(&ret, new->min, new->max);
1735 break;
1736 }
1737 add_range(&ret, tmp->min, tmp->max);
1738 } END_FOR_EACH_PTR(tmp);
1739
1740 return ret;
1741 }
1742
1743 static struct range_list *get_pos_rl(struct range_list *rl)
1744 {
1745 struct data_range *tmp;
1746 struct data_range *new;
1747 struct range_list *ret = NULL;
1748
1749 if (!rl)
1750 return NULL;
1751 if (sval_is_negative(rl_max(rl)))
1752 return NULL;
1753
1754 FOR_EACH_PTR(rl, tmp) {
1755 if (sval_is_negative(tmp->max))
1756 continue;
1757 if (sval_is_positive(tmp->min)) {
1758 add_range(&ret, tmp->min, tmp->max);
1759 continue;
1760 }
1761 new = alloc_range(tmp->min, tmp->max);
1762 new->min.value = 0;
1763 add_range(&ret, new->min, new->max);
1764 } END_FOR_EACH_PTR(tmp);
1765
1766 return ret;
1767 }
1768
1769 static struct range_list *divide_rl_helper(struct range_list *left, struct range_list *right)
1770 {
1771 sval_t right_min, right_max;
1772 sval_t min, max;
1773
1774 if (!left || !right)
1775 return NULL;
1776
1777 /* let's assume we never divide by zero */
1778 right_min = rl_min(right);
1779 right_max = rl_max(right);
1780 if (right_min.value == 0 && right_max.value == 0)
1781 return NULL;
1782 if (right_min.value == 0)
1783 right_min.value = 1;
1784 if (right_max.value == 0)
1785 right_max.value = -1;
1786
1787 max = sval_binop(rl_max(left), '/', right_min);
1788 min = sval_binop(rl_min(left), '/', right_max);
1789
1790 return alloc_rl(min, max);
1791 }
1792
1793 static struct range_list *handle_divide_rl(struct range_list *left, struct range_list *right)
1794 {
1795 struct range_list *left_neg, *left_pos, *right_neg, *right_pos;
1796 struct range_list *neg_neg, *neg_pos, *pos_neg, *pos_pos;
1797 struct range_list *ret;
1798
1799 if (is_whole_rl(right))
1800 return NULL;
1801
1802 left_neg = get_neg_rl(left);
1803 left_pos = get_pos_rl(left);
1804 right_neg = get_neg_rl(right);
1805 right_pos = get_pos_rl(right);
1806
1807 neg_neg = divide_rl_helper(left_neg, right_neg);
1808 neg_pos = divide_rl_helper(left_neg, right_pos);
1809 pos_neg = divide_rl_helper(left_pos, right_neg);
1810 pos_pos = divide_rl_helper(left_pos, right_pos);
1811
1812 ret = rl_union(neg_neg, neg_pos);
1813 ret = rl_union(ret, pos_neg);
1814 return rl_union(ret, pos_pos);
1815 }
1816
1817 static struct range_list *ptr_add_mult(struct range_list *left, int op, struct range_list *right)
1818 {
1819 struct range_list *ret;
1820 sval_t l_sval, r_sval, res;
1821
1822 /*
1823 * This function is sort of the wrong API because it takes two pointer
1824 * and adds them together. The caller is expected to figure out
1825 * alignment. Neither of those are the correct things to do.
1826 *
1827 * Really this function is quite bogus...
1828 */
1829
1830 if (rl_to_sval(left, &l_sval) && rl_to_sval(right, &r_sval)) {
1831 res = sval_binop(l_sval, op, r_sval);
1832 return alloc_rl(res, res);
1833 }
1834
1835 if (rl_min(left).value != 0 || rl_max(right).value != 0) {
1836 ret = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
1837 return cast_rl(rl_type(left), ret);
1838 }
1839
1840 return alloc_whole_rl(rl_type(left));
1841 }
1842
1843 static struct range_list *handle_add_mult_rl(struct range_list *left, int op, struct range_list *right)
1844 {
1845 sval_t min, max;
1846
1847 if (type_is_ptr(rl_type(left)) || type_is_ptr(rl_type(right)))
1848 return ptr_add_mult(left, op, right);
1849
1850 if (sval_binop_overflows(rl_min(left), op, rl_min(right)))
1851 return NULL;
1852 min = sval_binop(rl_min(left), op, rl_min(right));
1853
1854 if (sval_binop_overflows(rl_max(left), op, rl_max(right)))
1855 return NULL;
1856 max = sval_binop(rl_max(left), op, rl_max(right));
1857
1858 return alloc_rl(min, max);
1859 }
1860
1861 static struct range_list *handle_sub_rl(struct range_list *left_orig, struct range_list *right_orig)
1862 {
1863 struct range_list *left_rl, *right_rl;
1864 struct symbol *type;
1865 sval_t min, max;
1866 sval_t min_ll, max_ll, res_ll;
1867 sval_t tmp;
1868
1869 /* TODO: These things should totally be using dranges where possible */
1870
1871 if (!left_orig || !right_orig)
1872 return NULL;
1873
1874 type = &int_ctype;
1875 if (type_positive_bits(rl_type(left_orig)) > type_positive_bits(type))
1876 type = rl_type(left_orig);
1877 if (type_positive_bits(rl_type(right_orig)) > type_positive_bits(type))
1878 type = rl_type(right_orig);
1879
1880 left_rl = cast_rl(type, left_orig);
1881 right_rl = cast_rl(type, right_orig);
1882
1883 max = rl_max(left_rl);
1884 min = sval_type_min(type);
1885
1886 min_ll = rl_min(left_rl);
1887 min_ll.type = &llong_ctype;
1888 max_ll = rl_max(right_rl);
1889 max_ll.type = &llong_ctype;
1890 res_ll = min_ll;
1891 res_ll.value = min_ll.value - max_ll.value;
1892
1893 if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
1894 tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
1895 if (sval_cmp(tmp, min) > 0)
1896 min = tmp;
1897 } else if (type_positive_bits(type) < 63 &&
1898 !sval_binop_overflows(min_ll, '-', max_ll) &&
1899 (min.value != 0 && sval_cmp(res_ll, min) >= 0)) {
1900 struct range_list *left_casted, *right_casted, *result;
1901
1902 left_casted = cast_rl(&llong_ctype, left_orig);
1903 right_casted = cast_rl(&llong_ctype, right_orig);
1904 result = handle_sub_rl(left_casted, right_casted);
1905 return cast_rl(type, result);
1906 }
1907
1908 if (!sval_is_max(rl_max(left_rl))) {
1909 tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
1910 if (sval_cmp(tmp, max) < 0)
1911 max = tmp;
1912 }
1913
1914 if (sval_is_min(min) && sval_is_max(max))
1915 return NULL;
1916
1917 return alloc_rl(min, max);
1918 }
1919
1920 static unsigned long long rl_bits_always_set(struct range_list *rl)
1921 {
1922 return sval_fls_mask(rl_min(rl));
1923 }
1924
1925 static unsigned long long rl_bits_maybe_set(struct range_list *rl)
1926 {
1927 return sval_fls_mask(rl_max(rl));
1928 }
1929
1930 static struct range_list *handle_OR_rl(struct range_list *left, struct range_list *right)
1931 {
1932 unsigned long long left_min, left_max, right_min, right_max;
1933 sval_t min, max;
1934 sval_t sval;
1935
1936 if ((rl_to_sval(left, &sval) || rl_to_sval(right, &sval)) &&
1937 !sval_binop_overflows(rl_max(left), '+', rl_max(right)))
1938 return rl_binop(left, '+', right);
1939
1940 left_min = rl_bits_always_set(left);
1941 left_max = rl_bits_maybe_set(left);
1942 right_min = rl_bits_always_set(right);
1943 right_max = rl_bits_maybe_set(right);
1944
1945 min.type = max.type = &ullong_ctype;
1946 min.uvalue = left_min | right_min;
1947 max.uvalue = left_max | right_max;
1948
1949 return cast_rl(rl_type(left), alloc_rl(min, max));
1950 }
1951
1952 static struct range_list *handle_XOR_rl(struct range_list *left, struct range_list *right)
1953 {
1954 unsigned long long left_set, left_maybe;
1955 unsigned long long right_set, right_maybe;
1956 sval_t zero, max;
1957
1958 left_set = rl_bits_always_set(left);
1959 left_maybe = rl_bits_maybe_set(left);
1960
1961 right_set = rl_bits_always_set(right);
1962 right_maybe = rl_bits_maybe_set(right);
1963
1964 zero = max = rl_min(left);
1965 zero.uvalue = 0;
1966 max.uvalue = fls_mask((left_maybe | right_maybe) ^ (left_set & right_set));
1967
1968 return cast_rl(rl_type(left), alloc_rl(zero, max));
1969 }
1970
1971 static sval_t sval_lowest_set_bit(sval_t sval)
1972 {
1973 sval_t ret = { .type = sval.type };
1974 int i;
1975
1976 for (i = 0; i < 64; i++) {
1977 if (sval.uvalue & 1ULL << i) {
1978 ret.uvalue = (1ULL << i);
1979 return ret;
1980 }
1981 }
1982 return ret;
1983 }
1984
1985 static struct range_list *handle_AND_rl(struct range_list *left, struct range_list *right)
1986 {
1987 struct bit_info *one, *two;
1988 struct range_list *rl;
1989 sval_t min, max, zero, bits_sval;
1990 unsigned long long bits;
1991
1992 one = rl_to_binfo(left);
1993 two = rl_to_binfo(right);
1994 bits = one->possible & two->possible;
1995 bits_sval = rl_max(left);
1996 bits_sval.uvalue = bits;
1997
1998 max = sval_min_nonneg(rl_max(left), rl_max(right));
1999 min = sval_lowest_set_bit(bits_sval);
2000
2001 rl = alloc_rl(min, max);
2002
2003 zero = rl_min(rl);
2004 zero.value = 0;
2005 add_range(&rl, zero, zero);
2006
2007 return rl;
2008 }
2009
2010 static struct range_list *handle_lshift(struct range_list *left_orig, struct range_list *right_orig)
2011 {
2012 struct range_list *left;
2013 struct data_range *tmp;
2014 struct range_list *ret = NULL;
2015 sval_t zero = { .type = rl_type(left_orig), };
2016 sval_t shift, min, max;
2017 bool add_zero = false;
2018
2019 if (!rl_to_sval(right_orig, &shift) || sval_is_negative(shift))
2020 return NULL;
2021 if (shift.value == 0)
2022 return left_orig;
2023
2024 /* Cast to unsigned for easier left shift math */
2025 if (type_positive_bits(rl_type(left_orig)) < 32)
2026 left = cast_rl(&uint_ctype, left_orig);
2027 else if(type_positive_bits(rl_type(left_orig)) == 63)
2028 left = cast_rl(&ullong_ctype, left_orig);
2029 else
2030 left = left_orig;
2031
2032 FOR_EACH_PTR(left, tmp) {
2033 min = tmp->min;
2034 max = tmp->max;
2035
2036 if (min.value == 0 || max.value > sval_type_max(max.type).uvalue >> shift.uvalue)
2037 add_zero = true;
2038 if (min.value == 0 && max.value == 0)
2039 continue;
2040 if (min.value == 0)
2041 min.value = 1;
2042 min = sval_binop(min, SPECIAL_LEFTSHIFT, shift);
2043 max = sval_binop(max, SPECIAL_LEFTSHIFT, shift);
2044 add_range(&ret, min, max);
2045 } END_FOR_EACH_PTR(tmp);
2046
2047 if (!rl_fits_in_type(ret, rl_type(left_orig)))
2048 add_zero = true;
2049 ret = cast_rl(rl_type(left_orig), ret);
2050 if (add_zero)
2051 add_range(&ret, zero, zero);
2052
2053 return ret;
2054 }
2055
2056 static struct range_list *handle_rshift(struct range_list *left_orig, struct range_list *right_orig)
2057 {
2058 struct data_range *tmp;
2059 struct range_list *ret = NULL;
2060 sval_t shift, min, max;
2061
2062 if (!rl_to_sval(right_orig, &shift) || sval_is_negative(shift))
2063 return NULL;
2064 if (shift.value == 0)
2065 return left_orig;
2066
2067 FOR_EACH_PTR(left_orig, tmp) {
2068 min = sval_binop(tmp->min, SPECIAL_RIGHTSHIFT, shift);
2069 max = sval_binop(tmp->max, SPECIAL_RIGHTSHIFT, shift);
2070 add_range(&ret, min, max);
2071 } END_FOR_EACH_PTR(tmp);
2072
2073 return ret;
2074 }
2075
2076 struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
2077 {
2078 struct symbol *cast_type;
2079 sval_t left_sval, right_sval;
2080 struct range_list *ret = NULL;
2081
2082 cast_type = rl_type(left);
2083 if (sval_type_max(rl_type(left)).uvalue < sval_type_max(rl_type(right)).uvalue)
2084 cast_type = rl_type(right);
2085 if (sval_type_max(cast_type).uvalue < INT_MAX)
2086 cast_type = &int_ctype;
2087
2088 left = cast_rl(cast_type, left);
2089 right = cast_rl(cast_type, right);
2090
2091 if (!left && !right)
2092 return NULL;
2093
2094 if (rl_to_sval(left, &left_sval) && rl_to_sval(right, &right_sval)) {
2095 sval_t val = sval_binop(left_sval, op, right_sval);
2096 return alloc_rl(val, val);
2097 }
2098
2099 switch (op) {
2100 case '%':
2101 ret = handle_mod_rl(left, right);
2102 break;
2103 case '/':
2104 ret = handle_divide_rl(left, right);
2105 break;
2106 case '*':
2107 case '+':
2108 ret = handle_add_mult_rl(left, op, right);
2109 break;
2110 case '|':
2111 ret = handle_OR_rl(left, right);
2112 break;
2113 case '^':
2114 ret = handle_XOR_rl(left, right);
2115 break;
2116 case '&':
2117 ret = handle_AND_rl(left, right);
2118 break;
2119 case '-':
2120 ret = handle_sub_rl(left, right);
2121 break;
2122 case SPECIAL_RIGHTSHIFT:
2123 return handle_rshift(left, right);
2124 case SPECIAL_LEFTSHIFT:
2125 return handle_lshift(left, right);
2126 }
2127
2128 return ret;
2129 }
2130
2131 void free_data_info_allocs(void)
2132 {
2133 struct allocator_struct *desc = &data_info_allocator;
2134 struct allocation_blob *blob = desc->blobs;
2135
2136 free_all_rl();
2137 clear_math_cache();
2138
2139 desc->blobs = NULL;
2140 desc->allocations = 0;
2141 desc->total_bytes = 0;
2142 desc->useful_bytes = 0;
2143 desc->freelist = NULL;
2144 while (blob) {
2145 struct allocation_blob *next = blob->next;
2146 blob_free(blob, desc->chunking);
2147 blob = next;
2148 }
2149 clear_array_values_cache();
2150 clear_type_value_cache();
2151 clear_data_range_alloc();
2152 }
2153
2154 void split_comparison_rl(struct range_list *left_orig, int op, struct range_list *right_orig,
2155 struct range_list **left_true_rl, struct range_list **left_false_rl,
2156 struct range_list **right_true_rl, struct range_list **right_false_rl)
2157 {
2158 struct range_list *left_true, *left_false;
2159 struct range_list *right_true, *right_false;
2160 sval_t min, max;
2161
2162 min = sval_type_min(rl_type(left_orig));
2163 max = sval_type_max(rl_type(left_orig));
2164
2165 left_true = clone_rl(left_orig);
2166 left_false = clone_rl(left_orig);
2167 right_true = clone_rl(right_orig);
2168 right_false = clone_rl(right_orig);
2169
2170 switch (op) {
2171 case '<':
2172 case SPECIAL_UNSIGNED_LT:
2173 left_true = remove_range(left_orig, rl_max(right_orig), max);
2174 if (!sval_is_min(rl_min(right_orig))) {
2175 left_false = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
2176 }
2177
2178 right_true = remove_range(right_orig, min, rl_min(left_orig));
2179 if (!sval_is_max(rl_max(left_orig)))
2180 right_false = remove_range(right_orig, add_one(rl_max(left_orig)), max);
2181 break;
2182 case SPECIAL_UNSIGNED_LTE:
2183 case SPECIAL_LTE:
2184 if (!sval_is_max(rl_max(right_orig)))
2185 left_true = remove_range(left_orig, add_one(rl_max(right_orig)), max);
2186 left_false = remove_range(left_orig, min, rl_min(right_orig));
2187
2188 if (!sval_is_min(rl_min(left_orig)))
2189 right_true = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
2190 right_false = remove_range(right_orig, rl_max(left_orig), max);
2191
2192 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
2193 left_false = remove_range(left_false, rl_min(left_orig), rl_min(left_orig));
2194 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
2195 right_false = remove_range(right_false, rl_max(left_orig), rl_max(left_orig));
2196 break;
2197 case SPECIAL_EQUAL:
2198 left_true = rl_intersection(left_orig, right_orig);
2199 right_true = clone_rl(left_true);
2200
2201 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
2202 left_false = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
2203 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
2204 right_false = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
2205 break;
2206 case SPECIAL_UNSIGNED_GTE:
2207 case SPECIAL_GTE:
2208 if (!sval_is_min(rl_min(right_orig)))
2209 left_true = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
2210 left_false = remove_range(left_orig, rl_max(right_orig), max);
2211
2212 if (!sval_is_max(rl_max(left_orig)))
2213 right_true = remove_range(right_orig, add_one(rl_max(left_orig)), max);
2214 right_false = remove_range(right_orig, min, rl_min(left_orig));
2215
2216 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
2217 right_false = remove_range(right_false, rl_min(left_orig), rl_min(left_orig));
2218 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
2219 left_false = remove_range(left_false, rl_max(left_orig), rl_max(left_orig));
2220 break;
2221 case '>':
2222 case SPECIAL_UNSIGNED_GT:
2223 left_true = remove_range(left_orig, min, rl_min(right_orig));
2224 if (!sval_is_max(rl_max(right_orig)))
2225 left_false = remove_range(left_orig, add_one(rl_max(right_orig)), max);
2226
2227 right_true = remove_range(right_orig, rl_max(left_orig), max);
2228 if (!sval_is_min(rl_min(left_orig)))
2229 right_false = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
2230 break;
2231 case SPECIAL_NOTEQUAL:
2232 left_false = rl_intersection(left_orig, right_orig);
2233 right_false = clone_rl(left_false);
2234
2235 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
2236 left_true = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
2237 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
2238 right_true = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
2239 break;
2240 default:
2241 sm_perror(" unhandled comparison %d", op);
2242 }
2243
2244 if (left_true_rl) {
2245 *left_true_rl = left_true;
2246 *left_false_rl = left_false;
2247 }
2248 if (right_true_rl) {
2249 *right_true_rl = right_true;
2250 *right_false_rl = right_false;
2251 }
2252 }
Static analysis for C