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