smatch_sval.c

   1 /*
   2  * smatch/smatch_sval.c
   3  *
   4  * Copyright (C) 2012 Oracle.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  *
   9  * Basically the point of sval is that it can hold both ULLONG_MAX and
  10  * LLONG_MIN.  If it is an unsigned type then we use sval.uvalue or if it is
  11  * signed we use sval.value.
  12  *
  13  * I considered just using one bit to store whether the value was signed vs
  14  * unsigned but I think it might help to have the type information so we know
  15  * how to do type promotion.
  16  *
  17  */
  18
  19 #include "smatch.h"
  20 #include "smatch_slist.h"
  21 #include "smatch_extra.h"
  22
  23 __ALLOCATOR(sval_t, "svals", sval);
  24
  25 sval_t *sval_alloc(sval_t sval)
  26 {
  27         sval_t *ret;
  28
  29         ret = __alloc_sval(0);
  30         *ret = sval;
  31         return ret;
  32 }
  33
  34 sval_t *sval_alloc_permanent(sval_t sval)
  35 {
  36         sval_t *ret;
  37
  38         ret = malloc(sizeof(*ret));
  39         *ret = sval;
  40         return ret;
  41 }
  42
  43 sval_t sval_blank(struct expression *expr)
  44 {
  45         sval_t ret;
  46
  47         ret.type = get_type(expr);
  48         if (!ret.type)
  49                 ret.type = &llong_ctype;
  50         ret.value = 123456789;
  51
  52         return ret;
  53 }
  54
  55 sval_t sval_type_val(struct symbol *type, long long val)
  56 {
  57         sval_t ret;
  58
  59         ret.type = type;
  60         ret.value = val;
  61         return ret;
  62 }
  63
  64 sval_t sval_from_val(struct expression *expr, long long val)
  65 {
  66         sval_t ret;
  67
  68         ret = sval_blank(expr);
  69         ret.value = val;
  70         ret = sval_cast(get_type(expr), ret);
  71
  72         return ret;
  73 }
  74
  75 int sval_unsigned(sval_t sval)
  76 {
  77         return type_unsigned(sval.type);
  78 }
  79
  80 int sval_signed(sval_t sval)
  81 {
  82         return !type_unsigned(sval.type);
  83 }
  84
  85 int sval_bits(sval_t sval)
  86 {
  87         if (!sval.type)
  88                 return 32;
  89         return sval.type->bit_size;
  90 }
  91
  92 int sval_positive_bits(sval_t sval)
  93 {
  94         if (!sval.type)
  95                 return 31;
  96         if (sval_signed(sval))
  97                 return sval.type->bit_size - 1;
  98         return sval.type->bit_size;
  99 }
 100
 101 int sval_bits_used(sval_t sval)
 102 {
 103         int i;
 104
 105         for (i = 64; i >= 1; i--) {
 106                 if (sval.uvalue & (1ULL << (i - 1)))
 107                         return i;
 108         }
 109         return 0;
 110 }
 111
 112 int sval_is_negative(sval_t sval)
 113 {
 114         if (sval_cmp_val(sval, 0) < 0)
 115                 return 1;
 116         return 0;
 117 }
 118
 119 int sval_is_positive(sval_t sval)
 120 {
 121         return !sval_is_negative(sval);
 122 }
 123
 124 int sval_is_min(sval_t sval)
 125 {
 126         sval_t min = sval_type_min(sval.type);
 127
 128         if (sval_unsigned(sval)) {
 129                 if (sval.uvalue == 0)
 130                         return 1;
 131                 return 0;
 132         }
 133         /* return true for less than min as well */
 134         return (sval.value <= min.value);
 135 }
 136
 137 int sval_is_max(sval_t sval)
 138 {
 139         sval_t max = sval_type_max(sval.type);
 140
 141         if (sval_unsigned(sval))
 142                 return (sval.uvalue >= max.value);
 143         return (sval.value >= max.value);
 144 }
 145
 146 int sval_is_a_min(sval_t sval)
 147 {
 148         if (sval_signed(sval) && sval.value == SHRT_MIN)
 149                 return 1;
 150         if (sval_signed(sval) && sval.value == INT_MIN)
 151                 return 1;
 152         if (sval_signed(sval) && sval.value == LLONG_MIN)
 153                 return 1;
 154         return 0;
 155 }
 156
 157 int sval_is_a_max(sval_t sval)
 158 {
 159         if (sval.uvalue == SHRT_MAX)
 160                 return 1;
 161         if (sval.uvalue == INT_MAX)
 162                 return 1;
 163         if (sval.uvalue == LLONG_MAX)
 164                 return 1;
 165         if (sval.uvalue == USHRT_MAX)
 166                 return 1;
 167         if (sval.uvalue == UINT_MAX)
 168                 return 1;
 169         if (sval_unsigned(sval) && sval.uvalue == ULLONG_MAX)
 170                 return 1;
 171         return 0;
 172 }
 173
 174 /*
 175  * Returns -1 if one is smaller, 0 if they are the same and 1 if two is larger.
 176  */
 177 int sval_cmp(sval_t one, sval_t two)
 178 {
 179         struct symbol *type;
 180
 181         type = one.type;
 182         if (sval_positive_bits(two) > sval_positive_bits(one))
 183                 type = two.type;
 184         if (type_bits(type) < 31)
 185                 type = &int_ctype;
 186
 187         one = sval_cast(type, one);
 188         two = sval_cast(type, two);
 189
 190         if (type_unsigned(type)) {
 191                 if (one.uvalue < two.uvalue)
 192                         return -1;
 193                 if (one.uvalue == two.uvalue)
 194                         return 0;
 195                 return 1;
 196         }
 197         /* fix me handle type promotion and unsigned values */
 198         if (one.value < two.value)
 199                 return -1;
 200         if (one.value == two.value)
 201                 return 0;
 202         return 1;
 203 }
 204
 205 int sval_cmp_t(struct symbol *type, sval_t one, sval_t two)
 206 {
 207         sval_t one_cast, two_cast;
 208
 209         one_cast = sval_cast(type, one);
 210         two_cast = sval_cast(type, two);
 211         return sval_cmp(one_cast, two_cast);
 212 }
 213
 214 int sval_cmp_val(sval_t one, long long val)
 215 {
 216         sval_t sval;
 217
 218         sval = sval_type_val(&llong_ctype, val);
 219         return sval_cmp(one, sval);
 220 }
 221
 222 sval_t sval_cast(struct symbol *type, sval_t sval)
 223 {
 224         sval_t ret;
 225
 226         if (!type)
 227                 type = &llong_ctype;
 228
 229         ret.type = type;
 230         switch (sval_bits(ret)) {
 231         case 8:
 232                 if (sval_unsigned(ret))
 233                         ret.value = (long long)(unsigned char)sval.value;
 234                 else
 235                         ret.value = (long long)(char)sval.value;
 236                 break;
 237         case 16:
 238                 if (sval_unsigned(ret))
 239                         ret.value = (long long)(unsigned short)sval.value;
 240                 else
 241                         ret.value = (long long)(short)sval.value;
 242                 break;
 243         case 32:
 244                 if (sval_unsigned(ret))
 245                         ret.value = (long long)(unsigned int)sval.value;
 246                 else
 247                         ret.value = (long long)(int)sval.value;
 248                 break;
 249         default:
 250                 ret.value = sval.value;
 251         }
 252         return ret;
 253
 254 }
 255
 256 sval_t sval_preop(sval_t sval, int op)
 257 {
 258         switch (op) {
 259         case '!':
 260                 sval.value = !sval.value;
 261                 break;
 262         case '~':
 263                 sval.value = ~sval.value;
 264                 /* fixme: should probably cast this here */
 265                 break;
 266         case '-':
 267                 sval.value = -sval.value;
 268                 break;
 269         }
 270         return sval;
 271 }
 272
 273 static sval_t sval_binop_unsigned(struct symbol *type, sval_t left, int op, sval_t right)
 274 {
 275         sval_t ret;
 276
 277         ret.type = type;
 278         switch (op) {
 279         case '*':
 280                 ret.uvalue =  left.uvalue * right.uvalue;
 281                 break;
 282         case '/':
 283                 if (right.uvalue == 0) {
 284                         sm_msg("debug: %s: divide by zero", __func__);
 285                         ret.uvalue = 123456789;
 286                 } else {
 287                         ret.uvalue = left.uvalue / right.uvalue;
 288                 }
 289                 break;
 290         case '+':
 291                 ret.uvalue = left.uvalue + right.uvalue;
 292                 break;
 293         case '-':
 294                 ret.uvalue = left.uvalue - right.uvalue;
 295                 break;
 296         case '%':
 297                 if (right.uvalue == 0) {
 298                         sm_msg("internal error: %s: MOD by zero", __func__);
 299                         ret.uvalue = 123456789;
 300                 } else {
 301                         ret.uvalue = left.uvalue % right.uvalue;
 302                 }
 303                 break;
 304         case '|':
 305                 ret.uvalue = left.uvalue | right.uvalue;
 306                 break;
 307         case '&':
 308                 ret.uvalue = left.uvalue & right.uvalue;
 309                 break;
 310         case SPECIAL_RIGHTSHIFT:
 311                 ret.uvalue = left.uvalue >> right.uvalue;
 312                 break;
 313         case SPECIAL_LEFTSHIFT:
 314                 ret.uvalue = left.uvalue << right.uvalue;
 315                 break;
 316         case '^':
 317                 ret.uvalue = left.uvalue ^ right.uvalue;
 318                 break;
 319         default:
 320                 sm_msg("internal error: %s: unhandled binop %s", __func__,
 321                        show_special(op));
 322                 ret.uvalue = 1234567;
 323         }
 324         return ret;
 325 }
 326
 327
 328 static sval_t sval_binop_signed(struct symbol *type, sval_t left, int op, sval_t right)
 329 {
 330         sval_t ret;
 331
 332         ret.type = type;
 333         switch (op) {
 334         case '*':
 335                 ret.value =  left.value * right.value;
 336                 break;
 337         case '/':
 338                 if (right.value == 0) {
 339                         sm_msg("debug: %s: divide by zero", __func__);
 340                         ret.value = 123456789;
 341                 } else if (left.value == LLONG_MIN && right.value == -1) {
 342                         sm_msg("debug: %s: invalid divide LLONG_MIN/-1", __func__);
 343                         ret.value = 12345678;
 344                 } else {
 345                         ret.value = left.value / right.value;
 346                 }
 347                 break;
 348         case '+':
 349                 ret.value = left.value + right.value;
 350                 break;
 351         case '-':
 352                 ret.value = left.value - right.value;
 353                 break;
 354         case '%':
 355                 if (right.value == 0) {
 356                         sm_msg("internal error: %s: MOD by zero", __func__);
 357                         ret.value = 123456789;
 358                 } else {
 359                         ret.value = left.value % right.value;
 360                 }
 361                 break;
 362         case '|':
 363                 ret.value = left.value | right.value;
 364                 break;
 365         case '&':
 366                 ret.value = left.value & right.value;
 367                 break;
 368         case SPECIAL_RIGHTSHIFT:
 369                 ret.value = left.value >> right.value;
 370                 break;
 371         case SPECIAL_LEFTSHIFT:
 372                 ret.value = left.value << right.value;
 373                 break;
 374         case '^':
 375                 ret.value = left.value ^ right.value;
 376                 break;
 377         default:
 378                 sm_msg("internal error: %s: unhandled binop %s", __func__,
 379                        show_special(op));
 380                 ret.value = 1234567;
 381         }
 382         return ret;
 383 }
 384
 385 sval_t sval_binop(sval_t left, int op, sval_t right)
 386 {
 387         struct symbol *type;
 388         sval_t ret;
 389
 390         type = left.type;
 391         if (sval_positive_bits(right) > sval_positive_bits(left))
 392                 type = right.type;
 393         if (type_positive_bits(type) < 31)
 394                 type = &int_ctype;
 395
 396         if (type_unsigned(type))
 397                 ret = sval_binop_unsigned(type, left, op, right);
 398         else
 399                 ret = sval_binop_signed(type, left, op, right);
 400         return ret;
 401 }
 402
 403 const char *sval_to_str(sval_t sval)
 404 {
 405         char buf[30];
 406
 407         if (sval_unsigned(sval) && sval.value == ULLONG_MAX)
 408                 return "u64max";
 409         if (sval.value == LLONG_MAX)
 410                 return "s64max";
 411         if (sval_unsigned(sval) && sval.value == UINT_MAX)
 412                 return "u32max";
 413         if (sval.value == INT_MAX)
 414                 return "s32max";
 415         if (sval_unsigned(sval) && sval.value == USHRT_MAX)
 416                 return "u16max";
 417
 418         if (sval_signed(sval) && sval.value == SHRT_MIN)
 419                 return "s16min";
 420         if (sval_signed(sval) && sval.value == INT_MIN)
 421                 return "s32min";
 422         if (sval_signed(sval) && sval.value == LLONG_MIN)
 423                 return "s64min";
 424
 425         if (sval_unsigned(sval))
 426                 snprintf(buf, sizeof(buf), "%llu", sval.value);
 427         else if (sval.value < 0)
 428                 snprintf(buf, sizeof(buf), "(%lld)", sval.value);
 429         else
 430                 snprintf(buf, sizeof(buf), "%lld", sval.value);
 431
 432         return alloc_sname(buf);
 433 }
 434
 435 const char *sval_to_numstr(sval_t sval)
 436 {
 437         char buf[30];
 438
 439         if (sval_unsigned(sval))
 440                 snprintf(buf, sizeof(buf), "%llu", sval.value);
 441         else if (sval.value < 0)
 442                 snprintf(buf, sizeof(buf), "(%lld)", sval.value);
 443         else
 444                 snprintf(buf, sizeof(buf), "%lld", sval.value);
 445
 446         return alloc_sname(buf);
 447 }
 448
 449 sval_t ll_to_sval(long long val)
 450 {
 451         sval_t ret;
 452
 453         ret.type = &llong_ctype;
 454         ret.value = val;
 455         return ret;
 456 }
 457
 458 static void free_svals(struct symbol *sym)
 459 {
 460         clear_sval_alloc();
 461 }
 462
 463 void register_sval(int my_id)
 464 {
 465         add_hook(&free_svals, END_FUNC_HOOK);
 466 }