/*

 * Copyright (c) 2012, 2015, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code 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

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package org.graalvm.compiler.core.common.type;

import static org.graalvm.compiler.core.common.calc.FloatConvert.I2D;

import static org.graalvm.compiler.core.common.calc.FloatConvert.I2F;

import static org.graalvm.compiler.core.common.calc.FloatConvert.L2D;

import static org.graalvm.compiler.core.common.calc.FloatConvert.L2F;

import java.nio.ByteBuffer;

import java.util.Formatter;

import org.graalvm.compiler.core.common.LIRKind;

import org.graalvm.compiler.core.common.NumUtil;

import org.graalvm.compiler.core.common.spi.LIRKindTool;

import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp;

import org.graalvm.compiler.core.common.type.ArithmeticOpTable.FloatConvertOp;

import org.graalvm.compiler.core.common.type.ArithmeticOpTable.IntegerConvertOp;

import org.graalvm.compiler.core.common.type.ArithmeticOpTable.ShiftOp;

import org.graalvm.compiler.core.common.type.ArithmeticOpTable.UnaryOp;

import org.graalvm.compiler.debug.GraalError;

import jdk.vm.ci.code.CodeUtil;

import jdk.vm.ci.meta.Constant;

import jdk.vm.ci.meta.JavaConstant;

import jdk.vm.ci.meta.JavaKind;

import jdk.vm.ci.meta.MetaAccessProvider;

import jdk.vm.ci.meta.PrimitiveConstant;

import jdk.vm.ci.meta.ResolvedJavaType;

import jdk.vm.ci.meta.SerializableConstant;

/**

 * Describes the possible values of a node that produces an int or long result.

 *

 * The description consists of (inclusive) lower and upper bounds and up (may be set) and down

 * (always set) bit-masks.

 */

public final class IntegerStamp extends PrimitiveStamp {

    private final long lowerBound;

    private final long upperBound;

    private final long downMask;

    private final long upMask;

    private IntegerStamp(int bits, long lowerBound, long upperBound, long downMask, long upMask) {

        super(bits, OPS);

        this.lowerBound = lowerBound;

        this.upperBound = upperBound;

        this.downMask = downMask;

        this.upMask = upMask;

        assert lowerBound >= CodeUtil.minValue(bits) : this;

        assert upperBound <= CodeUtil.maxValue(bits) : this;

        assert (downMask & CodeUtil.mask(bits)) == downMask : this;

        assert (upMask & CodeUtil.mask(bits)) == upMask : this;

    }

    public static IntegerStamp create(int bits, long lowerBoundInput, long upperBoundInput) {

        return create(bits, lowerBoundInput, upperBoundInput, 0, CodeUtil.mask(bits));

    }

    public static IntegerStamp create(int bits, long lowerBoundInput, long upperBoundInput, long downMask, long upMask) {

        assert (downMask & ~upMask) == 0 : String.format("\u21ca: %016x \u21c8: %016x", downMask, upMask);

        // Set lower bound, use masks to make it more precise

        long minValue = minValueForMasks(bits, downMask, upMask);

        long lowerBoundTmp = Math.max(lowerBoundInput, minValue);

        // Set upper bound, use masks to make it more precise

        long maxValue = maxValueForMasks(bits, downMask, upMask);

        long upperBoundTmp = Math.min(upperBoundInput, maxValue);

        // Assign masks now with the bounds in mind.

        final long boundedDownMask;

        final long boundedUpMask;

        long defaultMask = CodeUtil.mask(bits);

        if (lowerBoundTmp == upperBoundTmp) {

            boundedDownMask = lowerBoundTmp;

            boundedUpMask = lowerBoundTmp;

        } else if (lowerBoundTmp >= 0) {

            int upperBoundLeadingZeros = Long.numberOfLeadingZeros(upperBoundTmp);

            long differentBits = lowerBoundTmp ^ upperBoundTmp;

            int sameBitCount = Long.numberOfLeadingZeros(differentBits << upperBoundLeadingZeros);

            boundedUpMask = upperBoundTmp | -1L >>> (upperBoundLeadingZeros + sameBitCount);

            boundedDownMask = upperBoundTmp & ~(-1L >>> (upperBoundLeadingZeros + sameBitCount));

        } else {

            if (upperBoundTmp >= 0) {

                boundedUpMask = defaultMask;

                boundedDownMask = 0;

            } else {

                int lowerBoundLeadingOnes = Long.numberOfLeadingZeros(~lowerBoundTmp);

                long differentBits = lowerBoundTmp ^ upperBoundTmp;

                int sameBitCount = Long.numberOfLeadingZeros(differentBits << lowerBoundLeadingOnes);

                boundedUpMask = lowerBoundTmp | -1L >>> (lowerBoundLeadingOnes + sameBitCount) | ~(-1L >>> lowerBoundLeadingOnes);

                boundedDownMask = lowerBoundTmp & ~(-1L >>> (lowerBoundLeadingOnes + sameBitCount)) | ~(-1L >>> lowerBoundLeadingOnes);

            }

        }

        return new IntegerStamp(bits, lowerBoundTmp, upperBoundTmp, defaultMask & (downMask | boundedDownMask), defaultMask & upMask & boundedUpMask);

    }

    static long significantBit(long bits, long value) {

        return (value >>> (bits - 1)) & 1;

    }

    static long minValueForMasks(int bits, long downMask, long upMask) {

        if (significantBit(bits, upMask) == 0) {

            // Value is always positive. Minimum value always positive.

            assert significantBit(bits, downMask) == 0;

            return downMask;

        } else {

            // Value can be positive or negative. Minimum value always negative.

            return downMask | (-1L << (bits - 1));

        }

    }

    static long maxValueForMasks(int bits, long downMask, long upMask) {

        if (significantBit(bits, downMask) == 1) {

            // Value is always negative. Maximum value always negative.

            assert significantBit(bits, upMask) == 1;

            return CodeUtil.signExtend(upMask, bits);

        } else {

            // Value can be positive or negative. Maximum value always positive.

            return upMask & (CodeUtil.mask(bits) >>> 1);

        }

    }

    public static IntegerStamp stampForMask(int bits, long downMask, long upMask) {

        return new IntegerStamp(bits, minValueForMasks(bits, downMask, upMask), maxValueForMasks(bits, downMask, upMask), downMask, upMask);

    }

    @Override

    public IntegerStamp unrestricted() {

        return new IntegerStamp(getBits(), CodeUtil.minValue(getBits()), CodeUtil.maxValue(getBits()), 0, CodeUtil.mask(getBits()));

    }

    @Override

    public IntegerStamp empty() {

        return new IntegerStamp(getBits(), CodeUtil.maxValue(getBits()), CodeUtil.minValue(getBits()), CodeUtil.mask(getBits()), 0);

    }

    @Override

    public Stamp constant(Constant c, MetaAccessProvider meta) {

        if (c instanceof PrimitiveConstant) {

            long value = ((PrimitiveConstant) c).asLong();

            return StampFactory.forInteger(getBits(), value, value);

        }

        return this;

    }

    @Override

    public SerializableConstant deserialize(ByteBuffer buffer) {

        switch (getBits()) {

            case 1:

                return JavaConstant.forBoolean(buffer.get() != 0);

            case 8:

                return JavaConstant.forByte(buffer.get());

            case 16:

                return JavaConstant.forShort(buffer.getShort());

            case 32:

                return JavaConstant.forInt(buffer.getInt());

            case 64:

                return JavaConstant.forLong(buffer.getLong());

            default:

                throw GraalError.shouldNotReachHere();

        }

    }

    @Override

    public boolean hasValues() {

        return lowerBound <= upperBound;

    }

    @Override

    public JavaKind getStackKind() {

        if (getBits() > 32) {

            return JavaKind.Long;

        } else {

            return JavaKind.Int;

        }

    }

    @Override

    public LIRKind getLIRKind(LIRKindTool tool) {

        return tool.getIntegerKind(getBits());

    }

    @Override

    public ResolvedJavaType javaType(MetaAccessProvider metaAccess) {

        switch (getBits()) {

            case 1:

                return metaAccess.lookupJavaType(Boolean.TYPE);

            case 8:

                return metaAccess.lookupJavaType(Byte.TYPE);

            case 16:

                return metaAccess.lookupJavaType(Short.TYPE);

            case 32:

                return metaAccess.lookupJavaType(Integer.TYPE);

            case 64:

                return metaAccess.lookupJavaType(Long.TYPE);

            default:

                throw GraalError.shouldNotReachHere();

        }

    }

    /**

     * The signed inclusive lower bound on the value described by this stamp.

     */

    public long lowerBound() {

        return lowerBound;

    }

    /**

     * The signed inclusive upper bound on the value described by this stamp.

     */

    public long upperBound() {

        return upperBound;

    }

    /**

     * This bit-mask describes the bits that are always set in the value described by this stamp.

     */

    public long downMask() {

        return downMask;

    }

    /**

     * This bit-mask describes the bits that can be set in the value described by this stamp.

     */

    public long upMask() {

        return upMask;

    }

    public boolean isUnrestricted() {

        return lowerBound == CodeUtil.minValue(getBits()) && upperBound == CodeUtil.maxValue(getBits()) && downMask == 0 && upMask == CodeUtil.mask(getBits());

    }

    public boolean contains(long value) {

        return value >= lowerBound && value <= upperBound && (value & downMask) == downMask && (value & upMask) == (value & CodeUtil.mask(getBits()));

    }

    public boolean isPositive() {

        return lowerBound() >= 0;

    }

    public boolean isNegative() {

        return upperBound() <= 0;

    }

    public boolean isStrictlyPositive() {

        return lowerBound() > 0;

    }

    public boolean isStrictlyNegative() {

        return upperBound() < 0;

    }

    public boolean canBePositive() {

        return upperBound() > 0;

    }

    public boolean canBeNegative() {

        return lowerBound() < 0;

    }

    @Override

    public String toString() {

        StringBuilder str = new StringBuilder();

        str.append('i');

        str.append(getBits());

        if (hasValues()) {

            if (lowerBound == upperBound) {

                str.append(" [").append(lowerBound).append(']');

            } else if (lowerBound != CodeUtil.minValue(getBits()) || upperBound != CodeUtil.maxValue(getBits())) {

                str.append(" [").append(lowerBound).append(" - ").append(upperBound).append(']');

            }

            if (downMask != 0) {

                str.append(" \u21ca");

                new Formatter(str).format("%016x", downMask);

            }

            if (upMask != CodeUtil.mask(getBits())) {

                str.append(" \u21c8");

                new Formatter(str).format("%016x", upMask);

            }

        } else {

            str.append("<empty>");

        }

        return str.toString();

    }

    private IntegerStamp createStamp(IntegerStamp other, long newUpperBound, long newLowerBound, long newDownMask, long newUpMask) {

        assert getBits() == other.getBits();

        if (newLowerBound > newUpperBound || (newDownMask & (~newUpMask)) != 0 || (newUpMask == 0 && (newLowerBound > 0 || newUpperBound < 0))) {

            return empty();

        } else if (newLowerBound == lowerBound && newUpperBound == upperBound && newDownMask == downMask && newUpMask == upMask) {

            return this;

        } else if (newLowerBound == other.lowerBound && newUpperBound == other.upperBound && newDownMask == other.downMask && newUpMask == other.upMask) {

            return other;

        } else {

            return IntegerStamp.create(getBits(), newLowerBound, newUpperBound, newDownMask, newUpMask);

        }

    }

    @Override

    public Stamp meet(Stamp otherStamp) {

        if (otherStamp == this) {

            return this;

        }

        IntegerStamp other = (IntegerStamp) otherStamp;

        return createStamp(other, Math.max(upperBound, other.upperBound), Math.min(lowerBound, other.lowerBound), downMask & other.downMask, upMask | other.upMask);

    }

    @Override

    public IntegerStamp join(Stamp otherStamp) {

        if (otherStamp == this) {

            return this;

        }

        IntegerStamp other = (IntegerStamp) otherStamp;

        long newDownMask = downMask | other.downMask;

        long newLowerBound = Math.max(lowerBound, other.lowerBound);

        long newUpperBound = Math.min(upperBound, other.upperBound);

        long newUpMask = upMask & other.upMask;

        return createStamp(other, newUpperBound, newLowerBound, newDownMask, newUpMask);

    }

    @Override

    public boolean isCompatible(Stamp stamp) {

        if (this == stamp) {

            return true;

        }

        if (stamp instanceof IntegerStamp) {

            IntegerStamp other = (IntegerStamp) stamp;

            return getBits() == other.getBits();

        }

        return false;

    }

    @Override

    public boolean isCompatible(Constant constant) {

        if (constant instanceof PrimitiveConstant) {

            PrimitiveConstant prim = (PrimitiveConstant) constant;

            return prim.getJavaKind().isNumericInteger();

        }

        return false;

    }

    public long unsignedUpperBound() {

        if (sameSignBounds()) {

            return CodeUtil.zeroExtend(upperBound(), getBits());

        }

        return NumUtil.maxValueUnsigned(getBits());

    }

    public long unsignedLowerBound() {

        if (sameSignBounds()) {

            return CodeUtil.zeroExtend(lowerBound(), getBits());

        }

        return 0;

    }

    private boolean sameSignBounds() {

        return NumUtil.sameSign(lowerBound, upperBound);

    }

    @Override

    public int hashCode() {

        final int prime = 31;

        int result = 1;

        result = prime * result + super.hashCode();

        result = prime * result + (int) (lowerBound ^ (lowerBound >>> 32));

        result = prime * result + (int) (upperBound ^ (upperBound >>> 32));

        result = prime * result + (int) (downMask ^ (downMask >>> 32));

        result = prime * result + (int) (upMask ^ (upMask >>> 32));

        return result;

    }

    @Override

    public boolean equals(Object obj) {

        if (this == obj) {

            return true;

        }

        if (obj == null || getClass() != obj.getClass() || !super.equals(obj)) {

            return false;

        }

        IntegerStamp other = (IntegerStamp) obj;

        if (lowerBound != other.lowerBound || upperBound != other.upperBound || downMask != other.downMask || upMask != other.upMask) {

            return false;

        }

        return super.equals(other);

    }

    public static long upMaskFor(int bits, long lowerBound, long upperBound) {

        long mask = lowerBound | upperBound;

        if (mask == 0) {

            return 0;

        } else {

            return ((-1L) >>> Long.numberOfLeadingZeros(mask)) & CodeUtil.mask(bits);

        }

    }

    /**

     * Checks if the 2 stamps represent values of the same sign. Returns true if the two stamps are

     * both positive of null or if they are both strictly negative

     *

     * @return true if the two stamps are both positive of null or if they are both strictly

     *         negative

     */

    public static boolean sameSign(IntegerStamp s1, IntegerStamp s2) {

        return s1.isPositive() && s2.isPositive() || s1.isStrictlyNegative() && s2.isStrictlyNegative();

    }

    @Override

    public JavaConstant asConstant() {

        if (lowerBound == upperBound) {

            switch (getBits()) {

                case 1:

                    return JavaConstant.forBoolean(lowerBound != 0);

                case 8:

                    return JavaConstant.forByte((byte) lowerBound);

                case 16:

                    return JavaConstant.forShort((short) lowerBound);

                case 32:

                    return JavaConstant.forInt((int) lowerBound);

                case 64:

                    return JavaConstant.forLong(lowerBound);

            }

        }

        return null;

    }

    public static boolean addCanOverflow(IntegerStamp a, IntegerStamp b) {

        assert a.getBits() == b.getBits();

        return addOverflowsPositively(a.upperBound(), b.upperBound(), a.getBits()) ||

                        addOverflowsNegatively(a.lowerBound(), b.lowerBound(), a.getBits());

    }

    public static boolean addOverflowsPositively(long x, long y, int bits) {

        long result = x + y;

        if (bits == 64) {

            return (~x & ~y & result) < 0;

        } else {

            return result > CodeUtil.maxValue(bits);

        }

    }

    public static boolean addOverflowsNegatively(long x, long y, int bits) {

        long result = x + y;

        if (bits == 64) {

            return (x & y & ~result) < 0;

        } else {

            return result < CodeUtil.minValue(bits);

        }

    }

    public static long carryBits(long x, long y) {

        return (x + y) ^ x ^ y;

    }

    private static long saturate(long v, int bits) {

        if (bits < 64) {

            long max = CodeUtil.maxValue(bits);

            if (v > max) {

                return max;

            }

            long min = CodeUtil.minValue(bits);

            if (v < min) {

                return min;

            }

        }

        return v;

    }

    public static boolean multiplicationOverflows(long a, long b, int bits) {

        assert bits <= 64 && bits >= 0;

        long result = a * b;

        // result is positive if the sign is the same

        boolean positive = (a >= 0 && b >= 0) || (a < 0 && b < 0);

        if (bits == 64) {

            if (a > 0 && b > 0) {

                return a > 0x7FFFFFFF_FFFFFFFFL / b;

            } else if (a > 0 && b <= 0) {

                return b < 0x80000000_00000000L / a;

            } else if (a <= 0 && b > 0) {

                return a < 0x80000000_00000000L / b;

            } else {

                // a<=0 && b <=0

                return a != 0 && b < 0x7FFFFFFF_FFFFFFFFL / a;

            }

        } else {

            if (positive) {

                return result > CodeUtil.maxValue(bits);

            } else {

                return result < CodeUtil.minValue(bits);