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                 ret = left / right;
 101                 break;
 102         case '+':
 103                 ret = left + right;
 104                 break;
 105         case '-':
 106                 ret = left - right;
 107                 break;
 108         case '%':
 109                 ret = left % right;
 110                 break;
 111         case '|':
 112                 ret = left | right;
 113                 break;
 114         case '&':
 115                 ret = left & right;
 116                 break;
 117         case SPECIAL_RIGHTSHIFT:
 118                 ret = left >> right;
 119                 break;
 120         case SPECIAL_LEFTSHIFT:
 121                 ret = left << right;
 122                 break;
 123         case '^':
 124                 ret = left ^ right;
 125                 break;
 126         default:
 127                 *undefined = 1;
 128                 *discard = 1;
 129         }
 130         return ret;
 131 }
 132
 133 static int get_implied_value_helper(struct expression *expr, long long *val, int what)
 134 {
 135         struct smatch_state *state;
 136         struct symbol *sym;
 137         char *name;
 138
 139         if (get_value(expr, val))
 140                 return 1;
 141
 142         name = get_variable_from_expr(expr, &sym);
 143         if (!name)
 144                 return 0;
 145         state = get_state(SMATCH_EXTRA, name, sym);
 146         free_string(name);
 147         if (!state || !state->data)
 148                 return 0;
 149         if (what == VAL_SINGLE)
 150                 return get_single_value_from_dinfo(get_dinfo(state), val);
 151         if (what == VAL_MAX) {
 152                 *val = get_dinfo_max(get_dinfo(state));
 153                 if (*val == whole_range.max) /* this means just guessing */
 154                         return 0;
 155                 return 1;
 156         }
 157         *val = get_dinfo_min(get_dinfo(state));
 158         if (*val == whole_range.min)
 159                 return 0;
 160         return 1;
 161 }
 162
 163 static int get_implied_single_fuzzy_max(struct expression *expr, long long *max)
 164 {
 165         struct sm_state *sm;
 166         struct sm_state *tmp;
 167
 168         if (get_implied_max(expr, max))
 169                 return 1;
 170
 171         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 172         if (!sm)
 173                 return 0;
 174
 175         *max = whole_range.min;
 176         FOR_EACH_PTR(sm->possible, tmp) {
 177                 long long new_min;
 178
 179                 new_min = get_dinfo_min(get_dinfo(tmp->state));
 180                 if (new_min > *max)
 181                         *max = new_min;
 182         } END_FOR_EACH_PTR(tmp);
 183
 184         if (*max > whole_range.min)
 185                 return 1;
 186         return 0;
 187 }
 188
 189 static int get_implied_single_fuzzy_min(struct expression *expr, long long *min)
 190 {
 191         struct sm_state *sm;
 192         struct sm_state *tmp;
 193
 194         if (get_implied_min(expr, min))
 195                 return 1;
 196
 197         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 198         if (!sm)
 199                 return 0;
 200
 201         *min = whole_range.max;
 202         FOR_EACH_PTR(sm->possible, tmp) {
 203                 long long new_max;
 204
 205                 new_max = get_dinfo_max(get_dinfo(tmp->state));
 206                 if (new_max < *min)
 207                         *min = new_max;
 208         } END_FOR_EACH_PTR(tmp);
 209
 210         if (*min < whole_range.max)
 211                 return 1;
 212         return 0;
 213 }
 214
 215 static long long _get_implied_value(struct expression *expr, int *discard, int *undefined, int implied)
 216 {
 217         long long ret = BOGUS;
 218
 219         switch (implied) {
 220         case IMPLIED:
 221                 if (!get_implied_value_helper(expr, &ret, VAL_SINGLE)) {
 222                         *undefined = 1;
 223                         *discard = 1;
 224                 }
 225                 break;
 226         case FUZZYMAX:
 227                 if (!get_implied_single_fuzzy_max(expr, &ret)) {
 228                         *undefined = 1;
 229                         *discard = 1;
 230                 }
 231                 break;
 232         case FUZZYMIN:
 233                 if (!get_implied_single_fuzzy_min(expr, &ret)) {
 234                         *undefined = 1;
 235                         *discard = 1;
 236                 }
 237                 break;
 238         default:
 239                 *undefined = 1;
 240                 *discard = 1;
 241         }
 242         return ret;
 243 }
 244
 245 static long long _get_value(struct expression *expr, int *discard, int *undefined, int implied)
 246 {
 247         int dis = 0;
 248         long long ret = BOGUS;
 249
 250         if (!expr) {
 251                 *undefined = 1;
 252                 return BOGUS;
 253         }
 254         if (!discard)
 255                 discard = &dis;
 256         if (*discard) {
 257                 *undefined = 1;
 258                 return BOGUS;
 259         }
 260
 261         expr = strip_parens(expr);
 262
 263         switch (expr->type){
 264         case EXPR_VALUE:
 265                 ret = expr->value;
 266                 ret = cast_to_type(expr, ret);
 267                 break;
 268         case EXPR_PREOP:
 269                 ret = handle_preop(expr, discard, undefined, implied);
 270                 break;
 271         case EXPR_POSTOP:
 272                 ret = _get_value(expr->unop, discard, undefined, implied);
 273                 break;
 274         case EXPR_CAST:
 275         case EXPR_FORCE_CAST:
 276         case EXPR_IMPLIED_CAST:
 277                 ret = _get_value(expr->cast_expression, discard, undefined, implied);
 278                 return cast_to_type(expr, ret);
 279         case EXPR_BINOP:
 280                 ret = handle_binop(expr, discard, undefined, implied);
 281                 break;
 282         case EXPR_PTRSIZEOF:
 283         case EXPR_SIZEOF:
 284                 ret = get_expression_value(expr);
 285                 break;
 286         default:
 287                 ret = _get_implied_value(expr, discard, undefined, implied);
 288         }
 289         if (*discard) {
 290                 *undefined = 1;
 291                 return BOGUS;
 292         }
 293         return ret;
 294 }
 295
 296 /* returns 1 if it can get a value literal or else returns 0 */
 297 int get_value(struct expression *expr, long long *val)
 298 {
 299         int undefined = 0;
 300
 301         *val = _get_value(expr, NULL, &undefined, NOTIMPLIED);
 302         if (undefined)
 303                 return 0;
 304         return 1;
 305 }
 306
 307 int get_implied_max(struct expression *expr, long long *val)
 308 {
 309         return get_implied_value_helper(expr, val, VAL_MAX);
 310 }
 311
 312 int get_implied_min(struct expression *expr, long long *val)
 313 {
 314         return get_implied_value_helper(expr, val, VAL_MIN);
 315 }
 316
 317 int get_implied_value(struct expression *expr, long long *val)
 318 {
 319         int undefined = 0;
 320
 321         *val =  _get_value(expr, NULL, &undefined, IMPLIED);
 322         return !undefined;
 323 }
 324
 325 int get_fuzzy_max(struct expression *expr, long long *val)
 326 {
 327         int undefined = 0;
 328
 329         *val =  _get_value(expr, NULL, &undefined, FUZZYMAX);
 330         return !undefined;
 331 }
 332
 333 int get_fuzzy_min(struct expression *expr, long long *val)
 334 {
 335         int undefined = 0;
 336
 337         *val =  _get_value(expr, NULL, &undefined, FUZZYMIN);
 338         return !undefined;
 339 }