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