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