smatch_math.c

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