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_min(sval_t sval)
 113 {
 114         sval_t min = sval_type_min(sval.type);
 115
 116         if (sval_unsigned(sval)) {
 117                 if (sval.uvalue == 0)
 118                         return 1;
 119                 return 0;
 120         }
 121         /* return true for less than min as well */
 122         return (sval.value <= min.value);
 123 }
 124
 125 int sval_is_max(sval_t sval)
 126 {
 127         sval_t max = sval_type_max(sval.type);
 128
 129         if (sval_unsigned(sval))
 130                 return (sval.uvalue >= max.value);
 131         return (sval.value >= max.value);
 132 }
 133
 134 int sval_is_a_min(sval_t sval)
 135 {
 136         if (sval_signed(sval) && sval.value == SHRT_MIN)
 137                 return 1;
 138         if (sval_signed(sval) && sval.value == INT_MIN)
 139                 return 1;
 140         if (sval_signed(sval) && sval.value == LLONG_MIN)
 141                 return 1;
 142         return 0;
 143 }
 144
 145 int sval_is_a_max(sval_t sval)
 146 {
 147         if (sval.uvalue == SHRT_MAX)
 148                 return 1;
 149         if (sval.uvalue == INT_MAX)
 150                 return 1;
 151         if (sval.uvalue == LLONG_MAX)
 152                 return 1;
 153         if (sval.uvalue == USHRT_MAX)
 154                 return 1;
 155         if (sval.uvalue == UINT_MAX)
 156                 return 1;
 157         if (sval_unsigned(sval) && sval.uvalue == ULLONG_MAX)
 158                 return 1;
 159         return 0;
 160 }
 161
 162 /*
 163  * Returns -1 if one is smaller, 0 if they are the same and 1 if two is larger.
 164  */
 165 int sval_cmp(sval_t one, sval_t two)
 166 {
 167         struct symbol *type;
 168
 169         type = one.type;
 170         if (sval_positive_bits(two) > sval_positive_bits(one))
 171                 type = two.type;
 172         if (type_bits(type) < 31)
 173                 type = &int_ctype;
 174
 175         one = sval_cast(type, one);
 176         two = sval_cast(type, two);
 177
 178         if (type_unsigned(type)) {
 179                 if (one.uvalue < two.uvalue)
 180                         return -1;
 181                 if (one.uvalue == two.uvalue)
 182                         return 0;
 183                 return 1;
 184         }
 185         /* fix me handle type promotion and unsigned values */
 186         if (one.value < two.value)
 187                 return -1;
 188         if (one.value == two.value)
 189                 return 0;
 190         return 1;
 191 }
 192
 193 int sval_cmp_t(struct symbol *type, sval_t one, sval_t two)
 194 {
 195         sval_t one_cast, two_cast;
 196
 197         one_cast = sval_cast(type, one);
 198         two_cast = sval_cast(type, two);
 199         return sval_cmp(one_cast, two_cast);
 200 }
 201
 202 int sval_cmp_val(sval_t one, long long val)
 203 {
 204         sval_t sval;
 205
 206         sval = sval_type_val(&llong_ctype, val);
 207         return sval_cmp(one, sval);
 208 }
 209
 210 sval_t sval_cast(struct symbol *type, sval_t sval)
 211 {
 212         sval_t ret;
 213
 214         if (!type)
 215                 type = &llong_ctype;
 216
 217         ret.type = type;
 218         switch (sval_bits(ret)) {
 219         case 8:
 220                 if (sval_unsigned(ret))
 221                         ret.value = (long long)(unsigned char)sval.value;
 222                 else
 223                         ret.value = (long long)(char)sval.value;
 224                 break;
 225         case 16:
 226                 if (sval_unsigned(ret))
 227                         ret.value = (long long)(unsigned short)sval.value;
 228                 else
 229                         ret.value = (long long)(short)sval.value;
 230                 break;
 231         case 32:
 232                 if (sval_unsigned(ret))
 233                         ret.value = (long long)(unsigned int)sval.value;
 234                 else
 235                         ret.value = (long long)(int)sval.value;
 236                 break;
 237         default:
 238                 ret.value = sval.value;
 239         }
 240         return ret;
 241
 242 }
 243
 244 sval_t sval_preop(sval_t sval, int op)
 245 {
 246         switch (op) {
 247         case '!':
 248                 sval.value = !sval.value;
 249                 break;
 250         case '~':
 251                 sval.value = ~sval.value;
 252                 /* fixme: should probably cast this here */
 253                 break;
 254         case '-':
 255                 sval.value = -sval.value;
 256                 break;
 257         }
 258         return sval;
 259 }
 260
 261 static sval_t sval_binop_unsigned(struct symbol *type, sval_t left, int op, sval_t right)
 262 {
 263         sval_t ret;
 264
 265         ret.type = type;
 266         switch (op) {
 267         case '*':
 268                 ret.uvalue =  left.uvalue * right.uvalue;
 269                 break;
 270         case '/':
 271                 if (right.uvalue == 0) {
 272                         sm_msg("debug: %s: divide by zero", __func__);
 273                         ret.uvalue = 123456789;
 274                 } else {
 275                         ret.uvalue = left.uvalue / right.uvalue;
 276                 }
 277                 break;
 278         case '+':
 279                 ret.uvalue = left.uvalue + right.uvalue;
 280                 break;
 281         case '-':
 282                 ret.uvalue = left.uvalue - right.uvalue;
 283                 break;
 284         case '%':
 285                 if (right.uvalue == 0) {
 286                         sm_msg("internal error: %s: MOD by zero", __func__);
 287                         ret.uvalue = 123456789;
 288                 } else {
 289                         ret.uvalue = left.uvalue % right.uvalue;
 290                 }
 291                 break;
 292         case '|':
 293                 ret.uvalue = left.uvalue | right.uvalue;
 294                 break;
 295         case '&':
 296                 ret.uvalue = left.uvalue & right.uvalue;
 297                 break;
 298         case SPECIAL_RIGHTSHIFT:
 299                 ret.uvalue = left.uvalue >> right.uvalue;
 300                 break;
 301         case SPECIAL_LEFTSHIFT:
 302                 ret.uvalue = left.uvalue << right.uvalue;
 303                 break;
 304         case '^':
 305                 ret.uvalue = left.uvalue ^ right.uvalue;
 306                 break;
 307         default:
 308                 sm_msg("internal error: %s: unhandled binop %s", __func__,
 309                        show_special(op));
 310                 ret.uvalue = 1234567;
 311         }
 312         return ret;
 313 }
 314
 315
 316 static sval_t sval_binop_signed(struct symbol *type, sval_t left, int op, sval_t right)
 317 {
 318         sval_t ret;
 319
 320         ret.type = type;
 321         switch (op) {
 322         case '*':
 323                 ret.value =  left.value * right.value;
 324                 break;
 325         case '/':
 326                 if (right.value == 0) {
 327                         sm_msg("debug: %s: divide by zero", __func__);
 328                         ret.value = 123456789;
 329                 } else if (left.value == LLONG_MIN && right.value == -1) {
 330                         sm_msg("debug: %s: invalid divide LLONG_MIN/-1", __func__);
 331                         ret.value = 12345678;
 332                 } else {
 333                         ret.value = left.value / right.value;
 334                 }
 335                 break;
 336         case '+':
 337                 ret.value = left.value + right.value;
 338                 break;
 339         case '-':
 340                 ret.value = left.value - right.value;
 341                 break;
 342         case '%':
 343                 if (right.value == 0) {
 344                         sm_msg("internal error: %s: MOD by zero", __func__);
 345                         ret.value = 123456789;
 346                 } else {
 347                         ret.value = left.value % right.value;
 348                 }
 349                 break;
 350         case '|':
 351                 ret.value = left.value | right.value;
 352                 break;
 353         case '&':
 354                 ret.value = left.value & right.value;
 355                 break;
 356         case SPECIAL_RIGHTSHIFT:
 357                 ret.value = left.value >> right.value;
 358                 break;
 359         case SPECIAL_LEFTSHIFT:
 360                 ret.value = left.value << right.value;
 361                 break;
 362         case '^':
 363                 ret.value = left.value ^ right.value;
 364                 break;
 365         default:
 366                 sm_msg("internal error: %s: unhandled binop %s", __func__,
 367                        show_special(op));
 368                 ret.value = 1234567;
 369         }
 370         return ret;
 371 }
 372
 373 sval_t sval_binop(sval_t left, int op, sval_t right)
 374 {
 375         struct symbol *type;
 376         sval_t ret;
 377
 378         type = left.type;
 379         if (sval_positive_bits(right) > sval_positive_bits(left))
 380                 type = right.type;
 381         if (type_positive_bits(type) < 31)
 382                 type = &int_ctype;
 383
 384         if (type_unsigned(type))
 385                 ret = sval_binop_unsigned(type, left, op, right);
 386         else
 387                 ret = sval_binop_signed(type, left, op, right);
 388         return ret;
 389 }
 390
 391 const char *sval_to_str(sval_t sval)
 392 {
 393         char buf[30];
 394
 395         if (sval_unsigned(sval) && sval.value == ULLONG_MAX)
 396                 return "u64max";
 397         if (sval.value == LLONG_MAX)
 398                 return "s64max";
 399         if (sval_unsigned(sval) && sval.value == UINT_MAX)
 400                 return "u32max";
 401         if (sval.value == INT_MAX)
 402                 return "s32max";
 403         if (sval_unsigned(sval) && sval.value == USHRT_MAX)
 404                 return "u16max";
 405
 406         if (sval_signed(sval) && sval.value == SHRT_MIN)
 407                 return "s16min";
 408         if (sval_signed(sval) && sval.value == INT_MIN)
 409                 return "s32min";
 410         if (sval_signed(sval) && sval.value == LLONG_MIN)
 411                 return "s64min";
 412
 413         if (sval_unsigned(sval))
 414                 snprintf(buf, sizeof(buf), "%llu", sval.value);
 415         else if (sval.value < 0)
 416                 snprintf(buf, sizeof(buf), "(%lld)", sval.value);
 417         else
 418                 snprintf(buf, sizeof(buf), "%lld", sval.value);
 419
 420         return alloc_sname(buf);
 421 }
 422
 423 const char *sval_to_numstr(sval_t sval)
 424 {
 425         char buf[30];
 426
 427         if (sval_unsigned(sval))
 428                 snprintf(buf, sizeof(buf), "%llu", sval.value);
 429         else if (sval.value < 0)
 430                 snprintf(buf, sizeof(buf), "(%lld)", sval.value);
 431         else
 432                 snprintf(buf, sizeof(buf), "%lld", sval.value);
 433
 434         return alloc_sname(buf);
 435 }
 436
 437 sval_t ll_to_sval(long long val)
 438 {
 439         sval_t ret;
 440
 441         ret.type = &llong_ctype;
 442         ret.value = val;
 443         return ret;
 444 }
 445
 446 static void free_svals(struct symbol *sym)
 447 {
 448         clear_sval_alloc();
 449 }
 450
 451 void register_sval(int my_id)
 452 {
 453         add_hook(&free_svals, END_FUNC_HOOK);
 454 }