smatch_math.c

   1 /*
   2  * smatch/smatch_math.c
   3  *
   4  * Copyright (C) 2010 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include "smatch.h"
  11 #include "smatch_slist.h"
  12 #include "smatch_extra.h"
  13
  14 static long long _get_implied_value(struct expression *expr, int *undefined, int implied);
  15 static long long _get_value(struct expression *expr, int *undefined, int implied);
  16
  17 #define BOGUS 12345
  18
  19 #define NOTIMPLIED  0
  20 #define IMPLIED     1
  21 #define IMPLIED_MIN 2
  22 #define IMPLIED_MAX 3
  23 #define FUZZYMAX    4
  24 #define FUZZYMIN    5
  25
  26 static long long cast_to_type(struct expression *expr, long long val)
  27 {
  28         struct symbol *type = get_type(expr);
  29
  30         if (!type)
  31                 return val;
  32
  33         switch (type->bit_size) {
  34         case 8:
  35                 if (type->ctype.modifiers & MOD_UNSIGNED)
  36                         val = (long long)(unsigned char) val;
  37                 else
  38                         val = (long long)(char) val;
  39                 break;
  40         case 16:
  41                 if (type->ctype.modifiers & MOD_UNSIGNED)
  42                         val = (long long)(unsigned short) val;
  43                 else
  44                         val = (long long)(short) val;
  45                 break;
  46         case 32:
  47                 if (type->ctype.modifiers & MOD_UNSIGNED)
  48                         val = (long long)(unsigned int) val;
  49                 else
  50                         val = (long long)(int) val;
  51                 break;
  52         }
  53         return val;
  54 }
  55
  56 static int opposite_implied(int implied)
  57 {
  58         if (implied == IMPLIED_MIN)
  59                 return IMPLIED_MAX;
  60         if (implied == IMPLIED_MAX)
  61                 return IMPLIED_MIN;
  62         return implied;
  63 }
  64
  65 static long long handle_preop(struct expression *expr, int *undefined, int implied)
  66 {
  67         long long ret = BOGUS;
  68
  69         switch (expr->op) {
  70         case '~':
  71                 ret = ~_get_value(expr->unop, undefined, implied);
  72                 ret = cast_to_type(expr->unop, ret);
  73                 break;
  74         case '-':
  75                 ret = -_get_value(expr->unop, undefined, implied);
  76                 break;
  77         case '*':
  78                 ret = _get_implied_value(expr, undefined, implied);
  79                 break;
  80         default:
  81                 *undefined = 1;
  82         }
  83         return ret;
  84 }
  85
  86 static long long handle_divide(struct expression *expr, int *undefined, int implied)
  87 {
  88         long long left;
  89         long long right;
  90         long long ret = BOGUS;
  91
  92         left = _get_value(expr->left, undefined, implied);
  93         right = _get_value(expr->right, undefined, opposite_implied(implied));
  94
  95         if (right == 0)
  96                 *undefined = 1;
  97         else
  98                 ret = left / right;
  99
 100         return ret;
 101 }
 102
 103 static long long handle_subtract(struct expression *expr, int *undefined, int implied)
 104 {
 105         long long left;
 106         long long right;
 107
 108         left = _get_value(expr->left, undefined, implied);
 109         right = _get_value(expr->right, undefined, opposite_implied(implied));
 110
 111         return left - right;
 112 }
 113
 114 static long long handle_binop(struct expression *expr, int *undefined, int implied)
 115 {
 116         long long left;
 117         long long right;
 118         long long ret = BOGUS;
 119
 120         if (expr->type != EXPR_BINOP) {
 121                 *undefined = 1;
 122                 return ret;
 123         }
 124
 125         left = _get_value(expr->left, undefined, implied);
 126         right = _get_value(expr->right, undefined, implied);
 127
 128         switch (expr->op) {
 129         case '*':
 130                 ret =  left * right;
 131                 break;
 132         case '/':
 133                 ret = handle_divide(expr, undefined, implied);
 134                 break;
 135         case '+':
 136                 ret = left + right;
 137                 break;
 138         case '-':
 139                 ret = handle_subtract(expr, undefined, implied);
 140                 break;
 141         case '%':
 142                 if (right == 0)
 143                         *undefined = 1;
 144                 else
 145                         ret = left % right;
 146                 break;
 147         case '|':
 148                 ret = left | right;
 149                 break;
 150         case '&':
 151                 ret = left & right;
 152                 break;
 153         case SPECIAL_RIGHTSHIFT:
 154                 ret = left >> right;
 155                 break;
 156         case SPECIAL_LEFTSHIFT:
 157                 ret = left << right;
 158                 break;
 159         case '^':
 160                 ret = left ^ right;
 161                 break;
 162         default:
 163                 *undefined = 1;
 164         }
 165         return ret;
 166 }
 167
 168 static int get_implied_value_helper(struct expression *expr, long long *val, int what)
 169 {
 170         struct smatch_state *state;
 171         struct symbol *sym;
 172         char *name;
 173
 174         if (get_value(expr, val))
 175                 return 1;
 176
 177         name = get_variable_from_expr(expr, &sym);
 178         if (!name)
 179                 return 0;
 180         state = get_state(SMATCH_EXTRA, name, sym);
 181         free_string(name);
 182         if (!state || !state->data)
 183                 return 0;
 184         if (what == IMPLIED)
 185                 return estate_get_single_value(state, val);
 186         if (what == IMPLIED_MAX) {
 187                 *val = estate_max(state);
 188                 if (*val == whole_range.max) /* this means just guessing */
 189                         return 0;
 190                 return 1;
 191         }
 192         *val = estate_min(state);
 193         if (*val == whole_range.min)
 194                 return 0;
 195         return 1;
 196 }
 197
 198 static int get_fuzzy_max_helper(struct expression *expr, long long *max)
 199 {
 200         struct sm_state *sm;
 201         struct sm_state *tmp;
 202
 203         if (get_implied_max(expr, max))
 204                 return 1;
 205
 206         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 207         if (!sm)
 208                 return 0;
 209
 210         *max = whole_range.min;
 211         FOR_EACH_PTR(sm->possible, tmp) {
 212                 long long new_min;
 213
 214                 new_min = estate_min(tmp->state);
 215                 if (new_min > *max)
 216                         *max = new_min;
 217         } END_FOR_EACH_PTR(tmp);
 218
 219         if (*max > whole_range.min)
 220                 return 1;
 221         return 0;
 222 }
 223
 224 static int get_fuzzy_min_helper(struct expression *expr, long long *min)
 225 {
 226         struct sm_state *sm;
 227         struct sm_state *tmp;
 228
 229         if (get_implied_min(expr, min))
 230                 return 1;
 231
 232         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 233         if (!sm)
 234                 return 0;
 235
 236         *min = whole_range.max;
 237         FOR_EACH_PTR(sm->possible, tmp) {
 238                 long long new_max;
 239
 240                 new_max = estate_max(tmp->state);
 241                 if (new_max < *min)
 242                         *min = new_max;
 243         } END_FOR_EACH_PTR(tmp);
 244
 245         if (*min < whole_range.max)
 246                 return 1;
 247         return 0;
 248 }
 249
 250 static long long _get_implied_value(struct expression *expr, int *undefined, int implied)
 251 {
 252         long long ret = BOGUS;
 253
 254         switch (implied) {
 255         case IMPLIED:
 256         case IMPLIED_MAX:
 257         case IMPLIED_MIN:
 258                 if (!get_implied_value_helper(expr, &ret, implied))
 259                         *undefined = 1;
 260                 break;
 261         case FUZZYMAX:
 262                 if (!get_fuzzy_max_helper(expr, &ret))
 263                         *undefined = 1;
 264                 break;
 265         case FUZZYMIN:
 266                 if (!get_fuzzy_min_helper(expr, &ret))
 267                         *undefined = 1;
 268                 break;
 269         default:
 270                 *undefined = 1;
 271         }
 272         return ret;
 273 }
 274
 275 static int get_const_value(struct expression *expr, long long *val)
 276 {
 277         struct symbol *sym;
 278
 279         sym = expr->symbol;
 280         if (!sym)
 281                 return 0;
 282         if (!(sym->ctype.modifiers & MOD_CONST))
 283                 return 0;
 284         if (get_value(sym->initializer, val))
 285                 return 1;
 286         return 0;
 287 }
 288
 289 static long long _get_value(struct expression *expr, int *undefined, int implied)
 290 {
 291         long long ret = BOGUS;
 292
 293         if (!expr) {
 294                 *undefined = 1;
 295                 return BOGUS;
 296         }
 297         if (*undefined)
 298                 return BOGUS;
 299
 300         expr = strip_parens(expr);
 301
 302         switch (expr->type) {
 303         case EXPR_VALUE:
 304                 ret = expr->value;
 305                 ret = cast_to_type(expr, ret);
 306                 break;
 307         case EXPR_PREOP:
 308                 ret = handle_preop(expr, undefined, implied);
 309                 break;
 310         case EXPR_POSTOP:
 311                 ret = _get_value(expr->unop, undefined, implied);
 312                 break;
 313         case EXPR_CAST:
 314         case EXPR_FORCE_CAST:
 315         case EXPR_IMPLIED_CAST:
 316                 ret = _get_value(expr->cast_expression, undefined, implied);
 317                 return cast_to_type(expr, ret);
 318         case EXPR_BINOP:
 319                 ret = handle_binop(expr, undefined, implied);
 320                 break;
 321         case EXPR_PTRSIZEOF:
 322         case EXPR_SIZEOF:
 323                 ret = get_expression_value(expr);
 324                 break;
 325         case EXPR_SYMBOL:
 326                 if (get_const_value(expr, &ret))
 327                         break;
 328         default:
 329                 ret = _get_implied_value(expr, undefined, implied);
 330         }
 331         if (*undefined)
 332                 return BOGUS;
 333         return ret;
 334 }
 335
 336 /* returns 1 if it can get a value literal or else returns 0 */
 337 int get_value(struct expression *expr, long long *val)
 338 {
 339         int undefined = 0;
 340
 341         *val = _get_value(expr, &undefined, NOTIMPLIED);
 342         if (undefined)
 343                 return 0;
 344         return 1;
 345 }
 346
 347 int get_implied_value(struct expression *expr, long long *val)
 348 {
 349         int undefined = 0;
 350
 351         *val =  _get_value(expr, &undefined, IMPLIED);
 352         return !undefined;
 353 }
 354
 355 int get_implied_min(struct expression *expr, long long *val)
 356 {
 357         int undefined = 0;
 358
 359         *val =  _get_value(expr, &undefined, IMPLIED_MIN);
 360         return !undefined;
 361 }
 362
 363 int get_implied_max(struct expression *expr, long long *val)
 364 {
 365         int undefined = 0;
 366
 367         *val =  _get_value(expr, &undefined, IMPLIED_MAX);
 368         return !undefined;
 369 }
 370
 371 int get_fuzzy_min(struct expression *expr, long long *val)
 372 {
 373         int undefined = 0;
 374
 375         *val =  _get_value(expr, &undefined, FUZZYMIN);
 376         return !undefined;
 377 }
 378
 379 int get_fuzzy_max(struct expression *expr, long long *val)
 380 {
 381         int undefined = 0;
 382
 383         *val =  _get_value(expr, &undefined, FUZZYMAX);
 384         return !undefined;
 385 }
 386
 387 int get_absolute_min(struct expression *expr, long long *val)
 388 {
 389         struct symbol *type;
 390         long long min;
 391
 392         type = get_type(expr);
 393         if (!type) {
 394                 if (get_value(expr, val))
 395                         return 1;
 396                 return 0;
 397         }
 398         min = type_min(type);
 399         if (!get_implied_min(expr, val) || *val < min)
 400                 *val = min;
 401         return 1;
 402 }
 403
 404 int get_absolute_max(struct expression *expr, long long *val)
 405 {
 406         struct symbol *type;
 407         long long max;
 408
 409         type = get_type(expr);
 410         if (!type) {
 411                 if (get_value(expr, val))
 412                         return 1;
 413                 return 0;
 414         }
 415         max = type_max(type);
 416         if (!get_implied_max(expr, val) || *val > max)
 417                 *val = max;
 418         if (*val < type_min(type))
 419                 *val = max;
 420         return 1;
 421 }