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