?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
capped: fix handling of assignments
[smatch.git] / smatch_ranges.c
blob3eefe81bff314501c0ad9eaacb30ad2edc3c13f4
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 if (type->type == SYM_FN)
937 type = &ptr_ctype;
938 while (type->type == SYM_NODE)
939 type = get_real_base_type(type);
940
941 return alloc_rl(sval_type_min(type), sval_type_max(type));
942 }
943
944 static bool collapse_pointer_rl(struct range_list **rl, sval_t min, sval_t max)
945 {
946 struct range_list *new_rl = NULL;
947 struct data_range *tmp;
948 static bool recurse;
949 bool ret = false;
950 int cnt = 0;
951
952 /*
953 * With the mtag work, then we end up getting huge lists of mtags.
954 * That seems cool, but the problem is that we can only store about
955 * 8-10 mtags in the DB before we truncate the list. Also the mtags
956 * aren't really used at all so it's a waste of resources for now...
957 * In the future, we maybe will revisit this code.
958 *
959 */
960
961 if (recurse)
962 return false;
963 recurse = true;
964 if (!type_is_ptr(min.type))
965 goto out;
966
967 if (ptr_list_size((struct ptr_list *)*rl) < 8)
968 goto out;
969 FOR_EACH_PTR(*rl, tmp) {
970 if (!is_err_ptr(tmp->min))
971 cnt++;
972 } END_FOR_EACH_PTR(tmp);
973 if (cnt < 8)
974 goto out;
975
976 FOR_EACH_PTR(*rl, tmp) {
977 if (sval_cmp(tmp->min, valid_ptr_min_sval) >= 0 &&
978 sval_cmp(tmp->max, valid_ptr_max_sval) <= 0)
979 add_range(&new_rl, valid_ptr_min_sval, valid_ptr_max_sval);
980 else
981 add_range(&new_rl, tmp->min, tmp->max);
982 } END_FOR_EACH_PTR(tmp);
983
984 add_range(&new_rl, min, max);
985
986 *rl = new_rl;
987 ret = true;
988 out:
989 recurse = false;
990 return ret;
991 }
992
993 extern int rl_ptrlist_hack;
994 void add_range(struct range_list **list, sval_t min, sval_t max)
995 {
996 struct data_range *tmp;
997 struct data_range *new = NULL;
998 int check_next = 0;
999
1000 /*
1001 * There is at least on valid reason why the types might be confusing
1002 * and that's when you have a void pointer and on some paths you treat
1003 * it as a u8 pointer and on other paths you treat it as a u16 pointer.
1004 * This case is hard to deal with.
1005 *
1006 * There are other cases where we probably should be more specific about
1007 * the types than we are. For example, we end up merging a lot of ulong
1008 * with pointers and I have not figured out why we do that.
1009 *
1010 * But this hack works for both cases, I think. We cast it to pointers
1011 * or we use the bigger size.
1012 *
1013 */
1014 if (*list && rl_type(*list) != min.type) {
1015 if (rl_type(*list)->type == SYM_PTR) {
1016 min = sval_cast(rl_type(*list), min);
1017 max = sval_cast(rl_type(*list), max);
1018 } else if (min.type->type == SYM_PTR) {
1019 *list = cast_rl(min.type, *list);
1020 } else if (type_bits(rl_type(*list)) >= type_bits(min.type)) {
1021 min = sval_cast(rl_type(*list), min);
1022 max = sval_cast(rl_type(*list), max);
1023 } else {
1024 *list = cast_rl(min.type, *list);
1025 }
1026 }
1027
1028 if (sval_cmp(min, max) > 0) {
1029 min = sval_type_min(min.type);
1030 max = sval_type_max(min.type);
1031 }
1032
1033 if (collapse_pointer_rl(list, min, max))
1034 return;
1035
1036 /*
1037 * FIXME: This has a problem merging a range_list like: min-0,3-max
1038 * with a range like 1-2. You end up with min-2,3-max instead of
1039 * just min-max.
1040 */
1041 FOR_EACH_PTR(*list, tmp) {
1042 if (check_next) {
1043 /* Sometimes we overlap with more than one range
1044 so we have to delete or modify the next range. */
1045 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
1046 /* join 2 ranges here */
1047 new->max = tmp->max;
1048 DELETE_CURRENT_PTR(tmp);
1049 return;
1050 }
1051
1052 /* Doesn't overlap with the next one. */
1053 if (sval_cmp(max, tmp->min) < 0)
1054 return;
1055
1056 if (sval_cmp(max, tmp->max) <= 0) {
1057 /* Partially overlaps the next one. */
1058 new->max = tmp->max;
1059 DELETE_CURRENT_PTR(tmp);
1060 return;
1061 } else {
1062 /* Completely overlaps the next one. */
1063 DELETE_CURRENT_PTR(tmp);
1064 /* there could be more ranges to delete */
1065 continue;
1066 }
1067 }
1068 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
1069 /* join 2 ranges into a big range */
1070 new = alloc_range(min, tmp->max);
1071 REPLACE_CURRENT_PTR(tmp, new);
1072 return;
1073 }
1074 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
1075 new = alloc_range(min, max);
1076 INSERT_CURRENT(new, tmp);
1077 return;
1078 }
1079 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
1080 if (sval_cmp(max, tmp->max) < 0)
1081 max = tmp->max;
1082 else
1083 check_next = 1;
1084 new = alloc_range(min, max);
1085 REPLACE_CURRENT_PTR(tmp, new);
1086 if (!check_next)
1087 return;
1088 continue;
1089 }
1090 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
1091 return;
1092 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
1093 min = tmp->min;
1094 new = alloc_range(min, max);
1095 REPLACE_CURRENT_PTR(tmp, new);
1096 check_next = 1;
1097 continue;
1098 }
1099 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
1100 /* join 2 ranges into a big range */
1101 new = alloc_range(tmp->min, max);
1102 REPLACE_CURRENT_PTR(tmp, new);
1103 check_next = 1;
1104 continue;
1105 }
1106 /* the new range is entirely above the existing ranges */
1107 } END_FOR_EACH_PTR(tmp);
1108 if (check_next)
1109 return;
1110 new = alloc_range(min, max);
1111
1112 rl_ptrlist_hack = 1;
1113 add_ptr_list(list, new);
1114 rl_ptrlist_hack = 0;
1115 }
1116
1117 struct range_list *clone_rl(struct range_list *list)
1118 {
1119 struct data_range *tmp;
1120 struct range_list *ret = NULL;
1121
1122 FOR_EACH_PTR(list, tmp) {
1123 add_ptr_list(&ret, tmp);
1124 } END_FOR_EACH_PTR(tmp);
1125 return ret;
1126 }
1127
1128 struct range_list *clone_rl_permanent(struct range_list *list)
1129 {
1130 struct data_range *tmp;
1131 struct data_range *new;
1132 struct range_list *ret = NULL;
1133
1134 FOR_EACH_PTR(list, tmp) {
1135 new = alloc_range_perm(tmp->min, tmp->max);
1136 add_ptr_list(&ret, new);
1137 } END_FOR_EACH_PTR(tmp);
1138 return ret;
1139 }
1140
1141 struct range_list *rl_union(struct range_list *one, struct range_list *two)
1142 {
1143 struct data_range *tmp;
1144 struct range_list *ret = NULL;
1145
1146 FOR_EACH_PTR(one, tmp) {
1147 add_range(&ret, tmp->min, tmp->max);
1148 } END_FOR_EACH_PTR(tmp);
1149 FOR_EACH_PTR(two, tmp) {
1150 add_range(&ret, tmp->min, tmp->max);
1151 } END_FOR_EACH_PTR(tmp);
1152 return ret;
1153 }
1154
1155 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
1156 {
1157 struct data_range *tmp;
1158 struct range_list *ret = NULL;
1159
1160 if (!list)
1161 return NULL;
1162
1163 min = sval_cast(rl_type(list), min);
1164 max = sval_cast(rl_type(list), max);
1165 if (sval_cmp(min, max) > 0) {
1166 sval_t tmp = min;
1167 min = max;
1168 max = tmp;
1169 }
1170
1171 FOR_EACH_PTR(list, tmp) {
1172 if (sval_cmp(tmp->max, min) < 0) {
1173 add_range(&ret, tmp->min, tmp->max);
1174 continue;
1175 }
1176 if (sval_cmp(tmp->min, max) > 0) {
1177 add_range(&ret, tmp->min, tmp->max);
1178 continue;
1179 }
1180 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
1181 continue;
1182 if (sval_cmp(tmp->min, min) >= 0) {
1183 max.value++;
1184 add_range(&ret, max, tmp->max);
1185 } else if (sval_cmp(tmp->max, max) <= 0) {
1186 min.value--;
1187 add_range(&ret, tmp->min, min);
1188 } else {
1189 min.value--;
1190 max.value++;
1191 add_range(&ret, tmp->min, min);
1192 add_range(&ret, max, tmp->max);
1193 }
1194 } END_FOR_EACH_PTR(tmp);
1195 return ret;
1196 }
1197
1198 int ranges_equiv(struct data_range *one, struct data_range *two)
1199 {
1200 if (!one && !two)
1201 return 1;
1202 if (!one || !two)
1203 return 0;
1204 if (sval_cmp(one->min, two->min) != 0)
1205 return 0;
1206 if (sval_cmp(one->max, two->max) != 0)
1207 return 0;
1208 return 1;
1209 }
1210
1211 int rl_equiv(struct range_list *one, struct range_list *two)
1212 {
1213 struct data_range *one_range;
1214 struct data_range *two_range;
1215
1216 if (one == two)
1217 return 1;
1218
1219 PREPARE_PTR_LIST(one, one_range);
1220 PREPARE_PTR_LIST(two, two_range);
1221 for (;;) {
1222 if (!one_range && !two_range)
1223 return 1;
1224 if (!ranges_equiv(one_range, two_range))
1225 return 0;
1226 NEXT_PTR_LIST(one_range);
1227 NEXT_PTR_LIST(two_range);
1228 }
1229 FINISH_PTR_LIST(two_range);
1230 FINISH_PTR_LIST(one_range);
1231
1232 return 1;
1233 }
1234
1235 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
1236 {
1237 switch (comparison) {
1238 case '<':
1239 case SPECIAL_UNSIGNED_LT:
1240 if (sval_cmp(left->min, right->max) < 0)
1241 return 1;
1242 return 0;
1243 case SPECIAL_UNSIGNED_LTE:
1244 case SPECIAL_LTE:
1245 if (sval_cmp(left->min, right->max) <= 0)
1246 return 1;
1247 return 0;
1248 case SPECIAL_EQUAL:
1249 if (sval_cmp(left->max, right->min) < 0)
1250 return 0;
1251 if (sval_cmp(left->min, right->max) > 0)
1252 return 0;
1253 return 1;
1254 case SPECIAL_UNSIGNED_GTE:
1255 case SPECIAL_GTE:
1256 if (sval_cmp(left->max, right->min) >= 0)
1257 return 1;
1258 return 0;
1259 case '>':
1260 case SPECIAL_UNSIGNED_GT:
1261 if (sval_cmp(left->max, right->min) > 0)
1262 return 1;
1263 return 0;
1264 case SPECIAL_NOTEQUAL:
1265 if (sval_cmp(left->min, left->max) != 0)
1266 return 1;
1267 if (sval_cmp(right->min, right->max) != 0)
1268 return 1;
1269 if (sval_cmp(left->min, right->min) != 0)
1270 return 1;
1271 return 0;
1272 default:
1273 sm_perror("unhandled comparison %d", comparison);
1274 return 0;
1275 }
1276 return 0;
1277 }
1278
1279 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
1280 {
1281 if (left)
1282 return true_comparison_range(var, comparison, val);
1283 else
1284 return true_comparison_range(val, comparison, var);
1285 }
1286
1287 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
1288 {
1289 switch (comparison) {
1290 case '<':
1291 case SPECIAL_UNSIGNED_LT:
1292 if (sval_cmp(left->max, right->min) >= 0)
1293 return 1;
1294 return 0;
1295 case SPECIAL_UNSIGNED_LTE:
1296 case SPECIAL_LTE:
1297 if (sval_cmp(left->max, right->min) > 0)
1298 return 1;
1299 return 0;
1300 case SPECIAL_EQUAL:
1301 if (sval_cmp(left->min, left->max) != 0)
1302 return 1;
1303 if (sval_cmp(right->min, right->max) != 0)
1304 return 1;
1305 if (sval_cmp(left->min, right->min) != 0)
1306 return 1;
1307 return 0;
1308 case SPECIAL_UNSIGNED_GTE:
1309 case SPECIAL_GTE:
1310 if (sval_cmp(left->min, right->max) < 0)
1311 return 1;
1312 return 0;
1313 case '>':
1314 case SPECIAL_UNSIGNED_GT:
1315 if (sval_cmp(left->min, right->max) <= 0)
1316 return 1;
1317 return 0;
1318 case SPECIAL_NOTEQUAL:
1319 if (sval_cmp(left->max, right->min) < 0)
1320 return 0;
1321 if (sval_cmp(left->min, right->max) > 0)
1322 return 0;
1323 return 1;
1324 default:
1325 sm_perror("unhandled comparison %d", comparison);
1326 return 0;
1327 }
1328 return 0;
1329 }
1330
1331 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
1332 {
1333 if (left)
1334 return false_comparison_range_sval(var, comparison, val);
1335 else
1336 return false_comparison_range_sval(val, comparison, var);
1337 }
1338
1339 int possibly_true(struct expression *left, int comparison, struct expression *right)
1340 {
1341 struct range_list *rl_left, *rl_right;
1342 struct data_range *tmp_left, *tmp_right;
1343 struct symbol *type;
1344
1345 if (comparison == UNKNOWN_COMPARISON)
1346 return 1;
1347 if (comparison == IMPOSSIBLE_COMPARISON)
1348 return 0;
1349 if (!get_implied_rl(left, &rl_left))
1350 return 1;
1351 if (!get_implied_rl(right, &rl_right))
1352 return 1;
1353
1354 type = rl_type(rl_left);
1355 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
1356 type = rl_type(rl_right);
1357 if (type_positive_bits(type) < 31)
1358 type = &int_ctype;
1359
1360 rl_left = cast_rl(type, rl_left);
1361 rl_right = cast_rl(type, rl_right);
1362
1363 FOR_EACH_PTR(rl_left, tmp_left) {
1364 FOR_EACH_PTR(rl_right, tmp_right) {
1365 if (true_comparison_range(tmp_left, comparison, tmp_right))
1366 return 1;
1367 } END_FOR_EACH_PTR(tmp_right);
1368 } END_FOR_EACH_PTR(tmp_left);
1369 return 0;
1370 }
1371
1372 int possibly_false(struct expression *left, int comparison, struct expression *right)
1373 {
1374 struct range_list *rl_left, *rl_right;
1375 struct data_range *tmp_left, *tmp_right;
1376 struct symbol *type;
1377
1378 if (!get_implied_rl(left, &rl_left))
1379 return 1;
1380 if (!get_implied_rl(right, &rl_right))
1381 return 1;
1382
1383 type = rl_type(rl_left);
1384 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
1385 type = rl_type(rl_right);
1386 if (type_positive_bits(type) < 31)
1387 type = &int_ctype;
1388
1389 rl_left = cast_rl(type, rl_left);
1390 rl_right = cast_rl(type, rl_right);
1391
1392 FOR_EACH_PTR(rl_left, tmp_left) {
1393 FOR_EACH_PTR(rl_right, tmp_right) {
1394 if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
1395 return 1;
1396 } END_FOR_EACH_PTR(tmp_right);
1397 } END_FOR_EACH_PTR(tmp_left);
1398 return 0;
1399 }
1400
1401 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1402 {
1403 struct data_range *left_tmp, *right_tmp;
1404 struct symbol *type;
1405
1406 if (!left_ranges || !right_ranges || comparison == UNKNOWN_COMPARISON)
1407 return 1;
1408 if (comparison == IMPOSSIBLE_COMPARISON)
1409 return 0;
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 (true_comparison_range(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 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1430 {
1431 struct data_range *left_tmp, *right_tmp;
1432 struct symbol *type;
1433
1434 if (!left_ranges || !right_ranges || comparison == UNKNOWN_COMPARISON)
1435 return 1;
1436 if (comparison == IMPOSSIBLE_COMPARISON)
1437 return 0;
1438
1439 type = rl_type(left_ranges);
1440 if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1441 type = rl_type(right_ranges);
1442 if (type_positive_bits(type) < 31)
1443 type = &int_ctype;
1444
1445 left_ranges = cast_rl(type, left_ranges);
1446 right_ranges = cast_rl(type, right_ranges);
1447
1448 FOR_EACH_PTR(left_ranges, left_tmp) {
1449 FOR_EACH_PTR(right_ranges, right_tmp) {
1450 if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
1451 return 1;
1452 } END_FOR_EACH_PTR(right_tmp);
1453 } END_FOR_EACH_PTR(left_tmp);
1454 return 0;
1455 }
1456
1457 /* FIXME: the _rl here stands for right left so really it should be _lr */
1458 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1459 {
1460 if (left)
1461 return possibly_true_rl(a, comparison, b);
1462 else
1463 return possibly_true_rl(b, comparison, a);
1464 }
1465
1466 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1467 {
1468 if (left)
1469 return possibly_false_rl(a, comparison, b);
1470 else
1471 return possibly_false_rl(b, comparison, a);
1472 }
1473
1474 int rl_has_sval(struct range_list *rl, sval_t sval)
1475 {
1476 struct data_range *tmp;
1477
1478 FOR_EACH_PTR(rl, tmp) {
1479 if (sval_cmp(tmp->min, sval) <= 0 &&
1480 sval_cmp(tmp->max, sval) >= 0)
1481 return 1;
1482 } END_FOR_EACH_PTR(tmp);
1483 return 0;
1484 }
1485
1486 void tack_on(struct range_list **list, struct data_range *drange)
1487 {
1488 add_ptr_list(list, drange);
1489 }
1490
1491 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
1492 {
1493 add_ptr_list(rl_stack, rl);
1494 }
1495
1496 struct range_list *pop_rl(struct range_list_stack **rl_stack)
1497 {
1498 struct range_list *rl;
1499
1500 rl = last_ptr_list((struct ptr_list *)*rl_stack);
1501 delete_ptr_list_last((struct ptr_list **)rl_stack);
1502 return rl;
1503 }
1504
1505 struct range_list *top_rl(struct range_list_stack *rl_stack)
1506 {
1507 struct range_list *rl;
1508
1509 rl = last_ptr_list((struct ptr_list *)rl_stack);
1510 return rl;
1511 }
1512
1513 void filter_top_rl(struct range_list_stack **rl_stack, struct range_list *filter)
1514 {
1515 struct range_list *rl;
1516
1517 rl = pop_rl(rl_stack);
1518 rl = rl_filter(rl, filter);
1519 push_rl(rl_stack, rl);
1520 }
1521
1522 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
1523 {
1524 struct data_range *tmp;
1525 struct range_list *ret = NULL;
1526 sval_t min, max;
1527
1528 if (!rl)
1529 return NULL;
1530
1531 if (!type || type == rl_type(rl))
1532 return rl;
1533
1534 FOR_EACH_PTR(rl, tmp) {
1535 min = tmp->min;
1536 max = tmp->max;
1537 if (type_bits(type) < type_bits(rl_type(rl))) {
1538 min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
1539 max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
1540 }
1541 if (sval_cmp(min, max) > 0) {
1542 min = sval_cast(type, min);
1543 max = sval_cast(type, max);
1544 }
1545 add_range_t(type, &ret, min, max);
1546 } END_FOR_EACH_PTR(tmp);
1547
1548 return ret;
1549 }
1550
1551 int rl_fits_in_type(struct range_list *rl, struct symbol *type)
1552 {
1553 if (type_bits(rl_type(rl)) <= type_bits(type))
1554 return 1;
1555 if (sval_cmp(rl_max(rl), sval_type_max(type)) > 0)
1556 return 0;
1557 if (sval_is_negative(rl_min(rl)) &&
1558 sval_cmp(rl_min(rl), sval_type_min(type)) < 0)
1559 return 0;
1560 return 1;
1561 }
1562
1563 static int rl_type_consistent(struct range_list *rl)
1564 {
1565 struct data_range *tmp;
1566 struct symbol *type;
1567
1568 type = rl_type(rl);
1569 FOR_EACH_PTR(rl, tmp) {
1570 if (type != tmp->min.type || type != tmp->max.type)
1571 return 0;
1572 } END_FOR_EACH_PTR(tmp);
1573 return 1;
1574 }
1575
1576 static struct range_list *cast_to_bool(struct range_list *rl)
1577 {
1578 struct data_range *tmp;
1579 struct range_list *ret = NULL;
1580 int has_one = 0;
1581 int has_zero = 0;
1582 sval_t min = { .type = &bool_ctype };
1583 sval_t max = { .type = &bool_ctype };
1584
1585 FOR_EACH_PTR(rl, tmp) {
1586 if (tmp->min.value || tmp->max.value)
1587 has_one = 1;
1588 if (sval_is_negative(tmp->min) &&
1589 sval_is_negative(tmp->max))
1590 continue;
1591 if (tmp->min.value == 0 ||
1592 tmp->max.value == 0)
1593 has_zero = 1;
1594 if (sval_is_negative(tmp->min) &&
1595 tmp->max.value > 0)
1596 has_zero = 1;
1597 } END_FOR_EACH_PTR(tmp);
1598
1599 if (!has_zero)
1600 min.value = 1;
1601 if (has_one)
1602 max.value = 1;
1603
1604 add_range(&ret, min, max);
1605 return ret;
1606 }
1607
1608 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
1609 {
1610 struct data_range *tmp;
1611 struct range_list *ret = NULL;
1612
1613 if (!rl)
1614 return NULL;
1615
1616 if (!type)
1617 return rl;
1618 if (!rl_is_sane(rl))
1619 return alloc_whole_rl(type);
1620 if (type == rl_type(rl) && rl_type_consistent(rl))
1621 return rl;
1622
1623 if (type == &bool_ctype)
1624 return cast_to_bool(rl);
1625
1626 FOR_EACH_PTR(rl, tmp) {
1627 add_range_t(type, &ret, tmp->min, tmp->max);
1628 } END_FOR_EACH_PTR(tmp);
1629
1630 if (!ret)
1631 return alloc_whole_rl(type);
1632
1633 return ret;
1634 }
1635
1636 /*
1637 * This is the opposite of rl_intersection().
1638 */
1639 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
1640 {
1641 struct data_range *tmp;
1642
1643 FOR_EACH_PTR(filter, tmp) {
1644 rl = remove_range(rl, tmp->min, tmp->max);
1645 } END_FOR_EACH_PTR(tmp);
1646
1647 return rl;
1648 }
1649
1650 struct range_list *do_intersection(struct range_list *one_rl, struct range_list *two_rl)
1651 {
1652 struct data_range *one, *two;
1653 struct range_list *ret = NULL;
1654
1655
1656 PREPARE_PTR_LIST(one_rl, one);
1657 PREPARE_PTR_LIST(two_rl, two);
1658
1659 while (true) {
1660 if (!one || !two)
1661 break;
1662 if (sval_cmp(one->max, two->min) < 0) {
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, two->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, one->min, one->max);
1673 NEXT_PTR_LIST(one);
1674 continue;
1675 }
1676 if (sval_cmp(one->min, two->min) < 0 && sval_cmp(one->max, two->max) > 0) {
1677 add_range(&ret, two->min, two->max);
1678 NEXT_PTR_LIST(two);
1679 continue;
1680 }
1681 if (sval_cmp(one->min, two->max) <= 0 && sval_cmp(one->max, two->max) > 0) {
1682 add_range(&ret, one->min, two->max);
1683 NEXT_PTR_LIST(two);
1684 continue;
1685 }
1686 if (sval_cmp(one->min, two->max) <= 0) {
1687 sm_fatal("error calculating intersection of '%s' and '%s'", show_rl(one_rl), show_rl(two_rl));
1688 return NULL;
1689 }
1690 NEXT_PTR_LIST(two);
1691 }
1692
1693 FINISH_PTR_LIST(two);
1694 FINISH_PTR_LIST(one);
1695
1696 return ret;
1697 }
1698
1699 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
1700 {
1701 struct range_list *ret;
1702 struct symbol *ret_type;
1703 struct symbol *small_type;
1704 struct symbol *large_type;
1705
1706 if (!one || !two)
1707 return NULL;
1708
1709 ret_type = rl_type(one);
1710 small_type = rl_type(one);
1711 large_type = rl_type(two);
1712
1713 if (type_bits(rl_type(two)) < type_bits(small_type)) {
1714 small_type = rl_type(two);
1715 large_type = rl_type(one);
1716 }
1717
1718 one = cast_rl(large_type, one);
1719 two = cast_rl(large_type, two);
1720
1721 ret = do_intersection(one, two);
1722 return cast_rl(ret_type, ret);
1723 }
1724
1725 static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
1726 {
1727 sval_t zero;
1728 sval_t max;
1729
1730 max = rl_max(right);
1731 if (sval_is_max(max))
1732 return left;
1733 if (max.value == 0)
1734 return NULL;
1735 max.value--;
1736 if (sval_is_negative(max))
1737 return NULL;
1738 if (sval_cmp(rl_max(left), max) < 0)
1739 return left;
1740 zero = max;
1741 zero.value = 0;
1742 return alloc_rl(zero, max);
1743 }
1744
1745 static struct range_list *get_neg_rl(struct range_list *rl)
1746 {
1747 struct data_range *tmp;
1748 struct data_range *new;
1749 struct range_list *ret = NULL;
1750
1751 if (!rl)
1752 return NULL;
1753 if (sval_is_positive(rl_min(rl)))
1754 return NULL;
1755
1756 FOR_EACH_PTR(rl, tmp) {
1757 if (sval_is_positive(tmp->min))
1758 break;
1759 if (sval_is_positive(tmp->max)) {
1760 new = alloc_range(tmp->min, tmp->max);
1761 new->max.value = -1;
1762 add_range(&ret, new->min, new->max);
1763 break;
1764 }
1765 add_range(&ret, tmp->min, tmp->max);
1766 } END_FOR_EACH_PTR(tmp);
1767
1768 return ret;
1769 }
1770
1771 static struct range_list *get_pos_rl(struct range_list *rl)
1772 {
1773 struct data_range *tmp;
1774 struct data_range *new;
1775 struct range_list *ret = NULL;
1776
1777 if (!rl)
1778 return NULL;
1779 if (sval_is_negative(rl_max(rl)))
1780 return NULL;
1781
1782 FOR_EACH_PTR(rl, tmp) {
1783 if (sval_is_negative(tmp->max))
1784 continue;
1785 if (sval_is_positive(tmp->min)) {
1786 add_range(&ret, tmp->min, tmp->max);
1787 continue;
1788 }
1789 new = alloc_range(tmp->min, tmp->max);
1790 new->min.value = 0;
1791 add_range(&ret, new->min, new->max);
1792 } END_FOR_EACH_PTR(tmp);
1793
1794 return ret;
1795 }
1796
1797 static struct range_list *divide_rl_helper(struct range_list *left, struct range_list *right)
1798 {
1799 sval_t right_min, right_max;
1800 sval_t min, max;
1801
1802 if (!left || !right)
1803 return NULL;
1804
1805 /* let's assume we never divide by zero */
1806 right_min = rl_min(right);
1807 right_max = rl_max(right);
1808 if (right_min.value == 0 && right_max.value == 0)
1809 return NULL;
1810 if (right_min.value == 0)
1811 right_min.value = 1;
1812 if (right_max.value == 0)
1813 right_max.value = -1;
1814
1815 max = sval_binop(rl_max(left), '/', right_min);
1816 min = sval_binop(rl_min(left), '/', right_max);
1817
1818 return alloc_rl(min, max);
1819 }
1820
1821 static struct range_list *handle_divide_rl(struct range_list *left, struct range_list *right)
1822 {
1823 struct range_list *left_neg, *left_pos, *right_neg, *right_pos;
1824 struct range_list *neg_neg, *neg_pos, *pos_neg, *pos_pos;
1825 struct range_list *ret;
1826
1827 if (is_whole_rl(right))
1828 return NULL;
1829
1830 left_neg = get_neg_rl(left);
1831 left_pos = get_pos_rl(left);
1832 right_neg = get_neg_rl(right);
1833 right_pos = get_pos_rl(right);
1834
1835 neg_neg = divide_rl_helper(left_neg, right_neg);
1836 neg_pos = divide_rl_helper(left_neg, right_pos);
1837 pos_neg = divide_rl_helper(left_pos, right_neg);
1838 pos_pos = divide_rl_helper(left_pos, right_pos);
1839
1840 ret = rl_union(neg_neg, neg_pos);
1841 ret = rl_union(ret, pos_neg);
1842 return rl_union(ret, pos_pos);
1843 }
1844
1845 static struct range_list *ptr_add_mult(struct range_list *left, int op, struct range_list *right)
1846 {
1847 struct range_list *ret;
1848 sval_t l_sval, r_sval, res;
1849
1850 /*
1851 * This function is sort of the wrong API because it takes two pointer
1852 * and adds them together. The caller is expected to figure out
1853 * alignment. Neither of those are the correct things to do.
1854 *
1855 * Really this function is quite bogus...
1856 */
1857
1858 if (rl_to_sval(left, &l_sval) && rl_to_sval(right, &r_sval)) {
1859 res = sval_binop(l_sval, op, r_sval);
1860 return alloc_rl(res, res);
1861 }
1862
1863 if (rl_min(left).value != 0 || rl_max(right).value != 0) {
1864 ret = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
1865 return cast_rl(rl_type(left), ret);
1866 }
1867
1868 return alloc_whole_rl(rl_type(left));
1869 }
1870
1871 static struct range_list *handle_add_mult_rl(struct range_list *left, int op, struct range_list *right)
1872 {
1873 sval_t min, max;
1874
1875 if (type_is_ptr(rl_type(left)) || type_is_ptr(rl_type(right)))
1876 return ptr_add_mult(left, op, right);
1877
1878 if (sval_binop_overflows(rl_min(left), op, rl_min(right)))
1879 return NULL;
1880 min = sval_binop(rl_min(left), op, rl_min(right));
1881
1882 if (sval_binop_overflows(rl_max(left), op, rl_max(right)))
1883 return NULL;
1884 max = sval_binop(rl_max(left), op, rl_max(right));
1885
1886 return alloc_rl(min, max);
1887 }
1888
1889 static struct range_list *handle_sub_rl(struct range_list *left_orig, struct range_list *right_orig)
1890 {
1891 struct range_list *left_rl, *right_rl;
1892 struct symbol *type;
1893 sval_t min, max;
1894 sval_t min_ll, max_ll, res_ll;
1895 sval_t tmp;
1896
1897 /* TODO: These things should totally be using dranges where possible */
1898
1899 if (!left_orig || !right_orig)
1900 return NULL;
1901
1902 type = &int_ctype;
1903 if (type_positive_bits(rl_type(left_orig)) > type_positive_bits(type))
1904 type = rl_type(left_orig);
1905 if (type_positive_bits(rl_type(right_orig)) > type_positive_bits(type))
1906 type = rl_type(right_orig);
1907
1908 left_rl = cast_rl(type, left_orig);
1909 right_rl = cast_rl(type, right_orig);
1910
1911 max = rl_max(left_rl);
1912 min = sval_type_min(type);
1913
1914 min_ll = rl_min(left_rl);
1915 min_ll.type = &llong_ctype;
1916 max_ll = rl_max(right_rl);
1917 max_ll.type = &llong_ctype;
1918 res_ll = min_ll;
1919 res_ll.value = min_ll.value - max_ll.value;
1920
1921 if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
1922 tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
1923 if (sval_cmp(tmp, min) > 0)
1924 min = tmp;
1925 } else if (type_positive_bits(type) < 63 &&
1926 !sval_binop_overflows(min_ll, '-', max_ll) &&
1927 (min.value != 0 && sval_cmp(res_ll, min) >= 0)) {
1928 struct range_list *left_casted, *right_casted, *result;
1929
1930 left_casted = cast_rl(&llong_ctype, left_orig);
1931 right_casted = cast_rl(&llong_ctype, right_orig);
1932 result = handle_sub_rl(left_casted, right_casted);
1933 return cast_rl(type, result);
1934 }
1935
1936 if (!sval_is_max(rl_max(left_rl))) {
1937 tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
1938 if (sval_cmp(tmp, max) < 0)
1939 max = tmp;
1940 }
1941
1942 if (sval_is_min(min) && sval_is_max(max))
1943 return NULL;
1944
1945 return alloc_rl(min, max);
1946 }
1947
1948 static unsigned long long rl_bits_always_set(struct range_list *rl)
1949 {
1950 return sval_fls_mask(rl_min(rl));
1951 }
1952
1953 static unsigned long long rl_bits_maybe_set(struct range_list *rl)
1954 {
1955 return sval_fls_mask(rl_max(rl));
1956 }
1957
1958 static struct range_list *handle_OR_rl(struct range_list *left, struct range_list *right)
1959 {
1960 unsigned long long left_min, left_max, right_min, right_max;
1961 sval_t min, max;
1962 sval_t sval;
1963
1964 if ((rl_to_sval(left, &sval) || rl_to_sval(right, &sval)) &&
1965 !sval_binop_overflows(rl_max(left), '+', rl_max(right)))
1966 return rl_binop(left, '+', right);
1967
1968 left_min = rl_bits_always_set(left);
1969 left_max = rl_bits_maybe_set(left);
1970 right_min = rl_bits_always_set(right);
1971 right_max = rl_bits_maybe_set(right);
1972
1973 min.type = max.type = &ullong_ctype;
1974 min.uvalue = left_min | right_min;
1975 max.uvalue = left_max | right_max;
1976
1977 return cast_rl(rl_type(left), alloc_rl(min, max));
1978 }
1979
1980 static struct range_list *handle_XOR_rl(struct range_list *left, struct range_list *right)
1981 {
1982 unsigned long long left_set, left_maybe;
1983 unsigned long long right_set, right_maybe;
1984 sval_t zero, max;
1985
1986 left_set = rl_bits_always_set(left);
1987 left_maybe = rl_bits_maybe_set(left);
1988
1989 right_set = rl_bits_always_set(right);
1990 right_maybe = rl_bits_maybe_set(right);
1991
1992 zero = max = rl_min(left);
1993 zero.uvalue = 0;
1994 max.uvalue = fls_mask((left_maybe | right_maybe) ^ (left_set & right_set));
1995
1996 return cast_rl(rl_type(left), alloc_rl(zero, max));
1997 }
1998
1999 static sval_t sval_lowest_set_bit(sval_t sval)
2000 {
2001 sval_t ret = { .type = sval.type };
2002 int i;
2003
2004 for (i = 0; i < 64; i++) {
2005 if (sval.uvalue & 1ULL << i) {
2006 ret.uvalue = (1ULL << i);
2007 return ret;
2008 }
2009 }
2010 return ret;
2011 }
2012
2013 static struct range_list *handle_AND_rl(struct range_list *left, struct range_list *right)
2014 {
2015 struct bit_info *one, *two;
2016 struct range_list *rl;
2017 sval_t min, max, zero, bits_sval;
2018 unsigned long long bits;
2019
2020 one = rl_to_binfo(left);
2021 two = rl_to_binfo(right);
2022 bits = one->possible & two->possible;
2023 bits_sval = rl_max(left);
2024 bits_sval.uvalue = bits;
2025
2026 max = sval_min_nonneg(rl_max(left), rl_max(right));
2027 min = sval_lowest_set_bit(bits_sval);
2028
2029 rl = alloc_rl(min, max);
2030
2031 zero = rl_min(rl);
2032 zero.value = 0;
2033 add_range(&rl, zero, zero);
2034
2035 return rl;
2036 }
2037
2038 static struct range_list *handle_lshift(struct range_list *left_orig, struct range_list *right_orig)
2039 {
2040 struct range_list *left;
2041 struct data_range *tmp;
2042 struct range_list *ret = NULL;
2043 sval_t zero = { .type = rl_type(left_orig), };
2044 sval_t shift, min, max;
2045 bool add_zero = false;
2046
2047 if (!rl_to_sval(right_orig, &shift) || sval_is_negative(shift))
2048 return NULL;
2049 if (shift.value == 0)
2050 return left_orig;
2051
2052 /* Cast to unsigned for easier left shift math */
2053 if (type_positive_bits(rl_type(left_orig)) < 32)
2054 left = cast_rl(&uint_ctype, left_orig);
2055 else if(type_positive_bits(rl_type(left_orig)) == 63)
2056 left = cast_rl(&ullong_ctype, left_orig);
2057 else
2058 left = left_orig;
2059
2060 FOR_EACH_PTR(left, tmp) {
2061 min = tmp->min;
2062 max = tmp->max;
2063
2064 if (min.value == 0 || max.value > sval_type_max(max.type).uvalue >> shift.uvalue)
2065 add_zero = true;
2066 if (min.value == 0 && max.value == 0)
2067 continue;
2068 if (min.value == 0)
2069 min.value = 1;
2070 min = sval_binop(min, SPECIAL_LEFTSHIFT, shift);
2071 max = sval_binop(max, SPECIAL_LEFTSHIFT, shift);
2072 add_range(&ret, min, max);
2073 } END_FOR_EACH_PTR(tmp);
2074
2075 if (!rl_fits_in_type(ret, rl_type(left_orig)))
2076 add_zero = true;
2077 ret = cast_rl(rl_type(left_orig), ret);
2078 if (add_zero)
2079 add_range(&ret, zero, zero);
2080
2081 return ret;
2082 }
2083
2084 static struct range_list *handle_rshift(struct range_list *left_orig, struct range_list *right_orig)
2085 {
2086 struct data_range *tmp;
2087 struct range_list *ret = NULL;
2088 sval_t shift, min, max;
2089
2090 if (!rl_to_sval(right_orig, &shift) || sval_is_negative(shift))
2091 return NULL;
2092 if (shift.value == 0)
2093 return left_orig;
2094
2095 FOR_EACH_PTR(left_orig, tmp) {
2096 min = sval_binop(tmp->min, SPECIAL_RIGHTSHIFT, shift);
2097 max = sval_binop(tmp->max, SPECIAL_RIGHTSHIFT, shift);
2098 add_range(&ret, min, max);
2099 } END_FOR_EACH_PTR(tmp);
2100
2101 return ret;
2102 }
2103
2104 struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
2105 {
2106 struct symbol *cast_type;
2107 sval_t left_sval, right_sval;
2108 struct range_list *ret = NULL;
2109
2110 cast_type = rl_type(left);
2111 if (sval_type_max(rl_type(left)).uvalue < sval_type_max(rl_type(right)).uvalue)
2112 cast_type = rl_type(right);
2113 if (sval_type_max(cast_type).uvalue < INT_MAX)
2114 cast_type = &int_ctype;
2115
2116 left = cast_rl(cast_type, left);
2117 right = cast_rl(cast_type, right);
2118
2119 if (!left && !right)
2120 return NULL;
2121
2122 if (rl_to_sval(left, &left_sval) && rl_to_sval(right, &right_sval)) {
2123 sval_t val = sval_binop(left_sval, op, right_sval);
2124 return alloc_rl(val, val);
2125 }
2126
2127 switch (op) {
2128 case '%':
2129 ret = handle_mod_rl(left, right);
2130 break;
2131 case '/':
2132 ret = handle_divide_rl(left, right);
2133 break;
2134 case '*':
2135 case '+':
2136 ret = handle_add_mult_rl(left, op, right);
2137 break;
2138 case '|':
2139 ret = handle_OR_rl(left, right);
2140 break;
2141 case '^':
2142 ret = handle_XOR_rl(left, right);
2143 break;
2144 case '&':
2145 ret = handle_AND_rl(left, right);
2146 break;
2147 case '-':
2148 ret = handle_sub_rl(left, right);
2149 break;
2150 case SPECIAL_RIGHTSHIFT:
2151 return handle_rshift(left, right);
2152 case SPECIAL_LEFTSHIFT:
2153 return handle_lshift(left, right);
2154 }
2155
2156 return ret;
2157 }
2158
2159 void free_data_info_allocs(void)
2160 {
2161 struct allocator_struct *desc = &data_info_allocator;
2162 struct allocation_blob *blob = desc->blobs;
2163
2164 free_all_rl();
2165 clear_math_cache();
2166 clear_strip_cache();
2167
2168 desc->blobs = NULL;
2169 desc->allocations = 0;
2170 desc->total_bytes = 0;
2171 desc->useful_bytes = 0;
2172 desc->freelist = NULL;
2173 while (blob) {
2174 struct allocation_blob *next = blob->next;
2175 blob_free(blob, desc->chunking);
2176 blob = next;
2177 }
2178 clear_array_values_cache();
2179 clear_type_value_cache();
2180 clear_data_range_alloc();
2181 }
2182
2183 void split_comparison_rl(struct range_list *left_orig, int op, struct range_list *right_orig,
2184 struct range_list **left_true_rl, struct range_list **left_false_rl,
2185 struct range_list **right_true_rl, struct range_list **right_false_rl)
2186 {
2187 struct range_list *left_true, *left_false;
2188 struct range_list *right_true, *right_false;
2189 sval_t min, max;
2190
2191 min = sval_type_min(rl_type(left_orig));
2192 max = sval_type_max(rl_type(left_orig));
2193
2194 left_true = clone_rl(left_orig);
2195 left_false = clone_rl(left_orig);
2196 right_true = clone_rl(right_orig);
2197 right_false = clone_rl(right_orig);
2198
2199 switch (op) {
2200 case '<':
2201 case SPECIAL_UNSIGNED_LT:
2202 left_true = remove_range(left_orig, rl_max(right_orig), max);
2203 if (!sval_is_min(rl_min(right_orig))) {
2204 left_false = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
2205 }
2206
2207 right_true = remove_range(right_orig, min, rl_min(left_orig));
2208 if (!sval_is_max(rl_max(left_orig)))
2209 right_false = remove_range(right_orig, add_one(rl_max(left_orig)), max);
2210 break;
2211 case SPECIAL_UNSIGNED_LTE:
2212 case SPECIAL_LTE:
2213 if (!sval_is_max(rl_max(right_orig)))
2214 left_true = remove_range(left_orig, add_one(rl_max(right_orig)), max);
2215 left_false = remove_range(left_orig, min, rl_min(right_orig));
2216
2217 if (!sval_is_min(rl_min(left_orig)))
2218 right_true = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
2219 right_false = remove_range(right_orig, rl_max(left_orig), max);
2220
2221 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
2222 left_false = remove_range(left_false, rl_min(left_orig), rl_min(left_orig));
2223 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
2224 right_false = remove_range(right_false, rl_max(left_orig), rl_max(left_orig));
2225 break;
2226 case SPECIAL_EQUAL:
2227 left_true = rl_intersection(left_orig, right_orig);
2228 right_true = clone_rl(left_true);
2229
2230 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
2231 left_false = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
2232 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
2233 right_false = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
2234 break;
2235 case SPECIAL_UNSIGNED_GTE:
2236 case SPECIAL_GTE:
2237 if (!sval_is_min(rl_min(right_orig)))
2238 left_true = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
2239 left_false = remove_range(left_orig, rl_max(right_orig), max);
2240
2241 if (!sval_is_max(rl_max(left_orig)))
2242 right_true = remove_range(right_orig, add_one(rl_max(left_orig)), max);
2243 right_false = remove_range(right_orig, min, rl_min(left_orig));
2244
2245 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
2246 right_false = remove_range(right_false, rl_min(left_orig), rl_min(left_orig));
2247 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
2248 left_false = remove_range(left_false, rl_max(left_orig), rl_max(left_orig));
2249 break;
2250 case '>':
2251 case SPECIAL_UNSIGNED_GT:
2252 left_true = remove_range(left_orig, min, rl_min(right_orig));
2253 if (!sval_is_max(rl_max(right_orig)))
2254 left_false = remove_range(left_orig, add_one(rl_max(right_orig)), max);
2255
2256 right_true = remove_range(right_orig, rl_max(left_orig), max);
2257 if (!sval_is_min(rl_min(left_orig)))
2258 right_false = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
2259 break;
2260 case SPECIAL_NOTEQUAL:
2261 left_false = rl_intersection(left_orig, right_orig);
2262 right_false = clone_rl(left_false);
2263
2264 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
2265 left_true = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
2266 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
2267 right_true = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
2268 break;
2269 default:
2270 sm_perror(" unhandled comparison %d", op);
2271 }
2272
2273 if (left_true_rl) {
2274 *left_true_rl = left_true;
2275 *left_false_rl = left_false;
2276 }
2277 if (right_true_rl) {
2278 *right_true_rl = right_true;
2279 *right_false_rl = right_false;
2280 }
2281 }
Static analysis for C