/*
 * Copyright (C) 2012 Oracle.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
 */

/*
 * Basically the point of sval is that it can hold both ULLONG_MAX and
 * LLONG_MIN.  If it is an unsigned type then we use sval.uvalue or if it is
 * signed we use sval.value.
 *
 * I considered just using one bit to store whether the value was signed vs
 * unsigned but I think it might help to have the type information so we know
 * how to do type promotion.
 *
 */

#include "smatch.h"
#include "smatch_slist.h"
#include "smatch_extra.h"

__ALLOCATOR(sval_t, "svals", sval);

sval_t *sval_alloc(sval_t sval)
{
        sval_t *ret;

        ret = __alloc_sval(0);
        *ret = sval;
        return ret;
}

sval_t *sval_alloc_permanent(sval_t sval)
{
        sval_t *ret;

        ret = malloc(sizeof(*ret));
        *ret = sval;
        return ret;
}

sval_t sval_blank(struct expression *expr)
{
        sval_t ret;

        ret.type = get_type(expr);
        if (!ret.type)
                ret.type = &int_ctype;
        ret.value = 123456789;

        return ret;
}

sval_t sval_type_val(struct symbol *type, long long val)
{
        sval_t ret;

        if (!type)
                type = &llong_ctype;

        ret.type = type;
        ret.value = val;
        return ret;
}

sval_t sval_type_fval(struct symbol *type, long double fval)
{
        sval_t ret;

        ret.type = &ldouble_ctype;
        ret.ldvalue = fval;
        return sval_cast(type, ret);
}

sval_t sval_from_val(struct expression *expr, long long val)
{
        sval_t ret;

        ret = sval_blank(expr);
        ret.value = val;
        ret = sval_cast(get_type(expr), ret);

        return ret;
}

sval_t sval_from_fval(struct expression *expr, long double fval)
{
        sval_t ret;

        ret.type = &ldouble_ctype;
        ret.ldvalue = fval;
        ret = sval_cast(get_type(expr), ret);

        return ret;
}

int sval_is_ptr(sval_t sval)
{
        if (!sval.type)
                return 0;
        return (sval.type->type == SYM_PTR || sval.type->type == SYM_ARRAY);
}

bool sval_is_fp(sval_t sval)
{
        return type_is_fp(sval.type);
}

int sval_unsigned(sval_t sval)
{
        if (is_ptr_type(sval.type))
                return true;
        return type_unsigned(sval.type);
}

int sval_signed(sval_t sval)
{
        return !type_unsigned(sval.type);
}

int sval_bits(sval_t sval)
{
        return type_bits(sval.type);
}

int sval_bits_used(sval_t sval)
{
        int i;

        for (i = 64; i >= 1; i--) {
                if (sval.uvalue & (1ULL << (i - 1)))
                        return i;
        }
        return 0;
}

int sval_is_negative(sval_t sval)
{
        if (type_unsigned(sval.type))
                return 0;
        if (sval.value < 0)
                return 1;
        return 0;
}

int sval_is_positive(sval_t sval)
{
        return !sval_is_negative(sval);
}

static bool fp_is_min(sval_t sval)
{
        if (sval.type == &float_ctype)
                return sval.fvalue == -FLT_MAX;
        if (sval.type == &double_ctype)
                return sval.dvalue == -DBL_MAX;
        if (sval.type == &ldouble_ctype)
                return sval.ldvalue == -LDBL_MAX;
        sm_perror("%s: bad type: '%s'", __func__, type_to_str(sval.type));
        return false;
}

int sval_is_min(sval_t sval)
{
        sval_t min = sval_type_min(sval.type);

        if (sval_is_fp(sval))
                return fp_is_min(sval);

        if (sval_unsigned(sval)) {
                if (sval.uvalue == 0)
                        return 1;
                return 0;
        }
        /* return true for less than min as well */
        return (sval.value <= min.value);
}

static bool fp_is_max(sval_t sval)
{
        if (sval.type == &float_ctype)
                return sval.fvalue == FLT_MAX;
        if (sval.type == &double_ctype)
                return sval.dvalue == DBL_MAX;
        if (sval.type == &ldouble_ctype)
                return sval.ldvalue == LDBL_MAX;
        sm_perror("%s: bad type: '%s'", __func__, type_to_str(sval.type));
        return false;
}

int sval_is_max(sval_t sval)
{
        sval_t max = sval_type_max(sval.type);

        if (sval_is_fp(sval))
                return fp_is_max(sval);

        if (sval_unsigned(sval))
                return (sval.uvalue >= max.value);
        return (sval.value >= max.value);
}

int sval_is_a_min(sval_t sval)
{
        if (sval_is_min(sval))
                return 1;

        if (sval_is_fp(sval))
                return 0;

        if (sval_signed(sval) && sval.value == SHRT_MIN)
                return 1;
        if (sval_signed(sval) && sval.value == INT_MIN)
                return 1;
        if (sval_signed(sval) && sval.value == LLONG_MIN)
                return 1;
        return 0;
}

int sval_is_a_max(sval_t sval)
{
        if (sval_is_max(sval))
                return 1;

        if (sval_is_fp(sval))
                return 0;

        if (sval.uvalue == SHRT_MAX)
                return 1;
        if (sval.uvalue == INT_MAX)
                return 1;
        if (sval.uvalue == LLONG_MAX)
                return 1;
        if (sval.uvalue == USHRT_MAX)
                return 1;
        if (sval.uvalue == UINT_MAX)
                return 1;
        if (sval_unsigned(sval) && sval.uvalue == ULLONG_MAX)
                return 1;
        if (sval.value > valid_ptr_max - 1000 &&
            sval.value < valid_ptr_max + 1000)
                return 1;
        return 0;
}

int sval_is_negative_min(sval_t sval)
{
        if (sval_is_fp(sval))
                return 0;

        if (!sval_is_negative(sval))
                return 0;
        return sval_is_min(sval);
}

int sval_cmp_t(struct symbol *type, sval_t one, sval_t two)
{
        sval_t one_cast, two_cast;

        one_cast = sval_cast(type, one);
        two_cast = sval_cast(type, two);
        return sval_cmp(one_cast, two_cast);
}

int sval_cmp_val(sval_t one, long long val)
{
        sval_t sval;

        sval = sval_type_val(&llong_ctype, val);
        return sval_cmp(one, sval);
}

sval_t sval_min(sval_t one, sval_t two)
{
        if (sval_cmp(one, two) > 0)
                return two;
        return one;
}

sval_t sval_max(sval_t one, sval_t two)
{
        if (sval_cmp(one, two) < 0)
                return two;
        return one;
}

int sval_too_low(struct symbol *type, sval_t sval)
{
        if (sval_is_negative(sval) && type_unsigned(type))
                return 1;
        if (type_signed(type) && sval_unsigned(sval))
                return 0;
        if (type_signed(sval.type) &&
            sval.value < sval_type_min(type).value)
                return 1;
        if (sval_cmp(sval, sval_type_min(type)) < 0)
                return 1;
        return 0;
}

int sval_too_high(struct symbol *type, sval_t sval)
{
        if (sval_is_negative(sval))
                return 0;
        if (sval.uvalue > sval_type_max(type).uvalue)
                return 1;
        return 0;
}

int sval_fits(struct symbol *type, sval_t sval)
{
        /* everything fits into floating point */
        if (type_is_fp(type))
                return 1;
        /* floating points don't fit into int */
        if (type_is_fp(sval.type))
                return 0;

        if (sval_too_low(type, sval))
                return 0;
        if (sval_too_high(type, sval))
                return 0;
        return 1;
}

static sval_t cast_to_fp(struct symbol *type, sval_t sval)
{
        sval_t ret = {};

        ret.type = type;
        if (type == &float_ctype) {
                if (!sval_is_fp(sval)) {
                        if (sval_unsigned(sval))
                                ret.fvalue = sval.uvalue;
                        else
                                ret.fvalue = sval.value;
                } else if (sval.type == &float_ctype)
                        ret.fvalue = sval.fvalue;
                else if (sval.type == &double_ctype)
                        ret.fvalue = sval.dvalue;
                else
                        ret.fvalue = sval.ldvalue;
        } else if (type == &double_ctype) {
                if (!sval_is_fp(sval)) {
                        if (sval_unsigned(sval))
                                ret.dvalue = sval.uvalue;
                        else
                                ret.dvalue = sval.value;
                } else if (sval.type == &float_ctype)
                        ret.dvalue = sval.fvalue;
                else if (sval.type == &double_ctype)
                        ret.dvalue = sval.dvalue;
                else
                        ret.dvalue = sval.ldvalue;
        } else if (type == &ldouble_ctype) {
                if (!sval_is_fp(sval)) {
                        if (sval_unsigned(sval))
                                ret.ldvalue = (long double)sval.uvalue;
                        else
                                ret.ldvalue = (long double)sval.value;
                } else if (sval.type == &float_ctype)
                        ret.ldvalue = sval.fvalue;
                else if (sval.type == &double_ctype)
                        ret.ldvalue = sval.dvalue;
                else
                        ret.ldvalue = sval.ldvalue;
        } else {
                sm_perror("%s: bad type: %s", __func__, type_to_str(type));
        }

        return ret;
}

static sval_t cast_from_fp(struct symbol *type, sval_t sval)
{
        sval_t ret = {};

        ret.type = &llong_ctype;
        if (sval.type == &float_ctype)
                ret.value = sval.fvalue;
        else if (sval.type == &double_ctype)
                ret.value = sval.dvalue;
        else if (sval.type == &ldouble_ctype)
                ret.value = sval.ldvalue;
        else
                sm_perror("%s: bad type: %s", __func__, type_to_str(type));

        return sval_cast(type, ret);
}

sval_t sval_cast(struct symbol *type, sval_t sval)
{
        sval_t ret;

        if (!type)
                type = &int_ctype;

        if (type_is_fp(type))
                return cast_to_fp(type, sval);
        if (type_is_fp(sval.type))
                return cast_from_fp(type, sval);

        ret.type = type;
        switch (sval_bits(ret)) {
        case 1:
                ret.value = !!sval.value;
                break;
        case 8:
                if (sval_unsigned(ret))
                        ret.value = (long long)(unsigned char)sval.value;
                else
                        ret.value = (long long)(char)sval.value;
                break;
        case 16:
                if (sval_unsigned(ret))
                        ret.value = (long long)(unsigned short)sval.value;
                else
                        ret.value = (long long)(short)sval.value;
                break;
        case 32:
                if (sval_unsigned(ret))
                        ret.value = (long long)(unsigned int)sval.value;
                else
                        ret.value = (long long)(int)sval.value;
                break;
        default:
                ret.value = sval.value;
        }
        return ret;

}

sval_t sval_preop(sval_t sval, int op)
{
        switch (op) {
        case '!':
                sval.value = !sval.value;
                break;
        case '~':
                sval.value = ~sval.value;
                sval = sval_cast(sval.type, sval);
                break;
        case '-':
                sval.value = -sval.value;
                sval = sval_cast(sval.type, sval);
                break;
        }
        return sval;
}

static sval_t sval_binop_unsigned(struct symbol *type, sval_t left, int op, sval_t right)
{
        sval_t ret;

        ret.type = type;
        switch (op) {
        case '*':
                ret.uvalue =  left.uvalue * right.uvalue;
                break;
        case '/':
                if (right.uvalue == 0) {
                        sm_debug("%s: divide by zero", __func__);
                        ret.uvalue = 123456789;
                } else {
                        ret.uvalue = left.uvalue / right.uvalue;
                }
                break;
        case '+':
                ret.uvalue = left.uvalue + right.uvalue;
                break;
        case '-':
                ret.uvalue = left.uvalue - right.uvalue;
                break;
        case '%':
                if (right.uvalue == 0) {
                        sm_perror(" %s: MOD by zero", __func__);
                        ret.uvalue = 123456789;
                } else {
                        ret.uvalue = left.uvalue % right.uvalue;
                }
                break;
        case '|':
                ret.uvalue = left.uvalue | right.uvalue;
                break;
        case '&':
                ret.uvalue = left.uvalue & right.uvalue;
                break;
        case SPECIAL_RIGHTSHIFT:
                ret.uvalue = left.uvalue >> right.uvalue;
                break;
        case SPECIAL_LEFTSHIFT:
                ret.uvalue = left.uvalue << right.uvalue;
                break;
        case '^':
                ret.uvalue = left.uvalue ^ right.uvalue;
                break;
        default:
                sm_perror(" %s: unhandled binop %s", __func__,
                       show_special(op));
                ret.uvalue = 1234567;
        }
        return ret;
}


static sval_t sval_binop_signed(struct symbol *type, sval_t left, int op, sval_t right)
{
        sval_t ret;

        ret.type = type;
        switch (op) {
        case '*':
                ret.value =  left.value * right.value;
                break;
        case '/':
                if (right.value == 0) {
                        sm_debug("%s: divide by zero", __func__);
                        ret.value = 123456789;
                } else if (left.value == LLONG_MIN && right.value == -1) {
                        sm_debug("%s: invalid divide LLONG_MIN/-1", __func__);
                        ret.value = 12345678;
                } else {
                        ret.value = left.value / right.value;
                }
                break;
        case '+':
                ret.value = left.value + right.value;
                break;
        case '-':
                ret.value = left.value - right.value;
                break;
        case '%':
                if (right.value == 0) {
                        sm_perror(" %s: MOD by zero", __func__);
                        ret.value = 123456789;
                } else {
                        ret.value = left.value % right.value;
                }
                break;
        case '|':
                ret.value = left.value | right.value;
                break;
        case '&':
                ret.value = left.value & right.value;
                break;
        case SPECIAL_RIGHTSHIFT:
                ret.value = left.value >> right.value;
                break;
        case SPECIAL_LEFTSHIFT:
                ret.value = left.value << right.value;
                break;
        case '^':
                ret.value = left.value ^ right.value;
                break;
        default:
                sm_perror(" %s: unhandled binop %s", __func__,
                       show_special(op));
                ret.value = 1234567;
        }
        return ret;
}

static sval_t ptr_binop(struct symbol *type, sval_t left, int op, sval_t right)
{
        sval_t ret;
        int align;

        if (op != '+' && op != '-')
                return sval_binop_unsigned(type, left, op, right);

        ret.type = type;
        if (type->type == SYM_PTR)
                type = get_real_base_type(type);
        align = type->ctype.alignment;
        if (align <= 0)
                align = 1;

        if (op == '+') {
                if (type_is_ptr(left.type))
                        ret.value = left.value + right.value * align;
                else
                        ret.value = left.value * align + right.value;
        } else {
                if (!type_is_ptr(left.type)) {
                        left.value = -left.value;
                        ret = ptr_binop(type, left, '+', right);
                } else if (!type_is_ptr(right.type)) {
                        right.value = -right.value;
                        ret = ptr_binop(type, left, '+', right);
                } else {
                        ret.value = (left.value - right.value) / align;
                }
        }

        if (op == '-')
                ret.type = ssize_t_ctype;
        return ret;
}

sval_t sval_binop(sval_t left, int op, sval_t right)
{
        struct symbol *type;
        sval_t ret;

        type = get_promoted_type(left.type, right.type);

        if (type_is_ptr(type))
                ret = ptr_binop(type, left, op, right);
        else if (type_unsigned(type))
                ret = sval_binop_unsigned(type, left, op, right);
        else
                ret = sval_binop_signed(type, left, op, right);
        return sval_cast(type, ret);
}

int sval_unop_overflows(sval_t sval, int op)
{
        if (op != '-')
                return 0;
        if (sval_positive_bits(sval) == 32 && sval.value == INT_MIN)
                return 1;
        if (sval_positive_bits(sval) == 64 && sval.value == LLONG_MIN)
                return 1;
        if (sval_is_negative(sval))
                return 0;
        if (sval_signed(sval))
                return 0;
        if (sval_bits(sval) == 32 && sval.uvalue > INT_MAX)
                return 1;
        if (sval_bits(sval) == 64 && sval.uvalue > LLONG_MAX)
                return 1;
        return 0;
}

int sval_binop_overflows(sval_t left, int op, sval_t right)
{
        struct symbol *type;
        sval_t max, min;

        type = left.type;
        if (type_positive_bits(right.type) > type_positive_bits(left.type))
                type = right.type;
        if (type_positive_bits(type) < 31)
                type = &int_ctype;

        max = sval_type_max(type);
        min = sval_type_min(type);

        switch (op) {
        case '+':
                if (sval_is_negative(left) && sval_is_negative(right)) {
                        if (left.value < min.value + right.value)
                                return 1;
                        return 0;
                }
                if (sval_is_negative(left) || sval_is_negative(right))
                        return 0;
                if (left.uvalue > max.uvalue - right.uvalue)
                                return 1;
                return 0;
        case '*':
                if (type_signed(type)) {
                        if (left.value == 0 || right.value == 0)
                                return 0;
                        if (left.value > max.value / right.value)
                                return 1;
                        if (left.value == -1 || right.value == -1)
                                return 0;
                        return left.value != left.value * right.value / right.value;

                }
                return right.uvalue != 0 && left.uvalue > max.uvalue / right.uvalue;
        case '-':
                if (type_unsigned(type)) {
                        if (sval_cmp(left, right) < 0)
                                return 1;
                        return 0;
                }
                if (sval_is_negative(left) && sval_is_negative(right))
                        return 0;

                if (sval_is_negative(left)) {
                        if (left.value < min.value + right.value)
                                return 1;
                        return 0;
                }
                if (sval_is_negative(right)) {
                        if (right.value == min.value)
                                return 1;
                        right = sval_preop(right, '-');
                        if (sval_binop_overflows(left, '+', right))
                                return 1;
                        return 0;
                }
                return 0;
        case SPECIAL_LEFTSHIFT:
                if (sval_cmp(left, sval_binop(max, invert_op(op), right)) > 0)
                        return 1;
                return 0;
        }
        return 0;
}

int sval_binop_overflows_no_sign(sval_t left, int op, sval_t right)
{

        struct symbol *type;

        type = left.type;
        if (type_positive_bits(right.type) > type_positive_bits(left.type))
                type = right.type;
        if (type_positive_bits(type) <= 31)
                type = &uint_ctype;
        else
                type = &ullong_ctype;

        left = sval_cast(type, left);
        right = sval_cast(type, right);
        return sval_binop_overflows(left, op, right);
}

int find_first_zero_bit(unsigned long long uvalue)
{
        int i;

        for (i = 0; i < 64; i++) {
                if (!(uvalue & (1ULL << i)))
                        return i;
        }
        return i;
}

int sm_fls64(unsigned long long uvalue)
{
        int high_bit = 0;

        while (uvalue) {
                uvalue >>= 1;
                high_bit++;
        }

        return high_bit;
}

unsigned long long fls_mask(unsigned long long uvalue)
{
        int high_bit = 0;

        high_bit = sm_fls64(uvalue);
        if (high_bit == 0)
                return 0;

        return ((unsigned long long)-1) >> (64 - high_bit);
}

unsigned long long sval_fls_mask(sval_t sval)
{
        return fls_mask(sval.uvalue);
}

static char *fp_to_str(sval_t sval)
{
        char buf[32];

        if (sval.type == &float_ctype)
                snprintf(buf, sizeof(buf), "%f", sval.fvalue);
        else if (sval.type == &double_ctype)
                snprintf(buf, sizeof(buf), "%e", sval.dvalue);
        else if (sval.type == &ldouble_ctype) {
                snprintf(buf, sizeof(buf), "%Lf", sval.ldvalue);
        } else
                snprintf(buf, sizeof(buf), "nan");

        return alloc_sname(buf);
}

const char *sval_to_str(sval_t sval)
{
        char buf[32];

        if (sval_is_fp(sval))
                return fp_to_str(sval);

        if (sval_is_ptr(sval) && sval.value == valid_ptr_max)
                return "ptr_max";
        if (sval_unsigned(sval) && sval.value == ULLONG_MAX)
                return "u64max";
        if (sval_unsigned(sval) && sval.value == UINT_MAX)
                return "u32max";
        if (sval.value == USHRT_MAX)
                return "u16max";

        if (sval_signed(sval) && sval.value == LLONG_MAX)
                return "s64max";
        if (sval.value == INT_MAX)
                return "s32max";
        if (sval.value == SHRT_MAX)
                return "s16max";

        if (sval_signed(sval) && sval.value == SHRT_MIN)
                return "s16min";
        if (sval_signed(sval) && sval.value == INT_MIN)
                return "s32min";
        if (sval_signed(sval) && sval.value == LLONG_MIN)
                return "s64min";

        if (sval_unsigned(sval))
                snprintf(buf, sizeof(buf), "%llu", sval.value);
        else if (sval.value < 0)
                snprintf(buf, sizeof(buf), "(%lld)", sval.value);
        else
                snprintf(buf, sizeof(buf), "%lld", sval.value);

        return alloc_sname(buf);
}

const char *sval_to_str_or_err_ptr(sval_t sval)
{
        char buf[12];

        if (option_project != PROJ_KERNEL ||
            !is_ptr_type(sval.type))
                return sval_to_str(sval);

        if (!sval_is_fp(sval) && sval.uvalue >= -4905ULL) {
                snprintf(buf, sizeof(buf), "(%lld)", sval.value);
                return alloc_sname(buf);
        }

        return sval_to_str(sval);
}

const char *sval_to_numstr(sval_t sval)
{
        char buf[30];

        if (type_is_fp(sval.type))
                return fp_to_str(sval);

        if (sval_unsigned(sval))
                snprintf(buf, sizeof(buf), "%llu", sval.value);
        else if (sval.value < 0)
                snprintf(buf, sizeof(buf), "(%lld)", sval.value);
        else
                snprintf(buf, sizeof(buf), "%lld", sval.value);

        return alloc_sname(buf);
}

sval_t ll_to_sval(long long val)
{
        sval_t ret;

        ret.type = &llong_ctype;
        ret.value = val;
        return ret;
}

static void free_svals(struct symbol *sym)
{
        if (__inline_fn)
                return;
        clear_sval_alloc();
}

void register_sval(int my_id)
{
        add_hook(&free_svals, AFTER_FUNC_HOOK);
}