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