/*
* Copyright (C) 2015 Matthias Heizmann (heizmann@informatik.uni-freiburg.de)
* Copyright (C) 2015 University of Freiburg
*
* This file is part of the ULTIMATE ModelCheckerUtils Library.
*
* The ULTIMATE ModelCheckerUtils Library is free software: you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as published
* by the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* The ULTIMATE ModelCheckerUtils Library 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 Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with the ULTIMATE ModelCheckerUtils Library. If not, see .
*
* Additional permission under GNU GPL version 3 section 7:
* If you modify the ULTIMATE ModelCheckerUtils Library, or any covered work, by linking
* or combining it with Eclipse RCP (or a modified version of Eclipse RCP),
* containing parts covered by the terms of the Eclipse Public License, the
* licensors of the ULTIMATE ModelCheckerUtils Library grant you additional permission
* to convey the resulting work.
*/
package de.uni_freiburg.informatik.ultimate.util.datastructures;
import java.math.BigInteger;
import java.util.function.Function;
/**
* Representation of bitvectors.
*
* @author Matthias Heizmann
*
*/
public class BitvectorConstant {
/**
* Describes bitvector operations that can be mapped to the SMT theory of fixed-size bitvectors
* (http://smtlib.cs.uiowa.edu/theories-FixedSizeBitVectors.shtml or http://smtlib.cs.uiowa.edu/logics-all.shtml).
*
* @author Matthias Heizmann
* @author Daniel Dietsch (dietsch@informatik.uni-freiburg.de)
*
*/
public enum BvOp {
/**
* ((_ sign_extend i) x)
*
* extend x with sign bits to the (signed) equivalent bitvector of size m+i
*/
sign_extend(2, false, false),
/**
* ((_ zero_extend i) x)
*
* extend x with zeroes to the (unsigned) equivalent bitvector of size m+i
*/
zero_extend(2, false, false),
/**
* ((_ extract i j) (_ BitVec m) (_ BitVec n))
*
* extraction of bits i down to j from a bitvector of size m to yield a new bitvector of size n, where n = i - j
* + 1
*/
extract(3, false, false),
/**
* (concat(_ BitVec m) (_ BitVec n))
*
* concatinates two bitvectors to a bitvector of size m+n
*/
concat(2, false, false),
/**
* (bvadd (_ BitVec m) (_ BitVec m) (_ BitVec m))
*
* addition modulo 2^m
*/
bvadd(2, false, true),
/**
* (bvsub (_ BitVec m) (_ BitVec m) (_ BitVec m))
*
* 2's complement subtraction modulo 2^m
*/
bvsub(2, false, false),
/**
* (bvmul (_ BitVec m) (_ BitVec m) (_ BitVec m))
*
* multiplication modulo 2^m
*/
bvmul(2, false, true),
/**
* (bvudiv (_ BitVec m) (_ BitVec m) (_ BitVec m))
*
* unsigned division, truncating towards 0
*/
bvudiv(2, false, false),
/**
* (bvurem (_ BitVec m) (_ BitVec m) (_ BitVec m))
*
* unsigned remainder from truncating division
*/
bvurem(2, false, false),
/**
* (bvsdiv (_ BitVec m) (_ BitVec m) (_ BitVec m))
*
* 2's complement signed division
*/
bvsdiv(2, false, false),
/**
* (bvsrem (_ BitVec m) (_ BitVec m) (_ BitVec m))
*
* 2's complement signed remainder (sign follows dividend)
*/
bvsrem(2, false, false),
/**
* (bvsmod (_ BitVec m) (_ BitVec m) (_ BitVec m))
*
* 2's complement signed remainder (sign follows divisor)
*/
bvsmod(2, false, false),
/**
* (bvand (_ BitVec m) (_ BitVec m) (_ BitVec m))
*
* bitwise and
*/
bvand(2, false, true),
/**
* (bvor (_ BitVec m) (_ BitVec m) (_ BitVec m))
*
* bitwise or
*/
bvor(2, false, true),
/**
* (bvxor (_ BitVec m) (_ BitVec m) (_ BitVec m))
*
* bitwise exclusive or
*/
bvxor(2, false, true),
/**
* (bvnot (_ BitVec m) (_ BitVec m))
*
* bitwise negation
*/
bvnot(1, false, true),
/**
* (bvneg (_ BitVec m) (_ BitVec m))
*
* 2's complement unary minus
*/
bvneg(1, false, true),
/**
* (bvshl (_ BitVec m) (_ BitVec m) (_ BitVec m))
*
* shift left (equivalent to multiplication by 2^x where x is the value of the second argument)
*/
bvshl(2, false, false),
/**
* (bvlshr (_ BitVec m) (_ BitVec m) (_ BitVec m))
*
* logical shift right (equivalent to unsigned division by 2^x where x is the value of the second argument)
*/
bvlshr(2, false, false),
/**
* (bvashr (_ BitVec m) (_ BitVec m) (_ BitVec m))
*
* Arithmetic shift right, like logical shift right except that the most significant bits of the result always
* copy the most significant bit of the first argument.
*/
bvashr(2, false, false),
/**
* (bvult (_ BitVec m) (_ BitVec m) Bool)
*
* binary predicate for unsigned less-than
*/
bvult(2, true, false),
/**
* (bvule (_ BitVec m) (_ BitVec m) Bool)
*
* binary predicate for unsigned less than or equal
*/
bvule(2, true, false),
/**
* (bvugt (_ BitVec m) (_ BitVec m) Bool)
*
* binary predicate for unsigned greater than
*/
bvugt(2, true, false),
/**
* (bvuge (_ BitVec m) (_ BitVec m) Bool)
*
* binary predicate for unsigned greater than or equal
*/
bvuge(2, true, false),
/**
* (bvslt (_ BitVec m) (_ BitVec m) Bool)
*
* binary predicate for signed less than
*/
bvslt(2, true, false),
/**
* (bvsle (_ BitVec m) (_ BitVec m) Bool)
*
* binary predicate for signed less than or equal
*/
bvsle(2, true, false),
/**
* (bvsgt (_ BitVec m) (_ BitVec m) Bool)
*
* binary predicate for signed greater than
*/
bvsgt(2, true, false),
/**
* (bvsge (_ BitVec m) (_ BitVec m) Bool)
*
* binary predicate for signed greater than or equal
*/
bvsge(2, true, false);
private final int mArity;
private final boolean mIsBoolean;
private final boolean mIsAssociative;
private BvOp(final int arity, final boolean isBoolean, final boolean isAssoc) {
mArity = arity;
mIsBoolean = isBoolean;
mIsAssociative = isAssoc;
}
/**
* @return the arity of this operation
*/
public int getArity() {
return mArity;
}
/**
* @return true iff the result of this operation is of type boolean, false otherwise
*/
public boolean isBoolean() {
return mIsBoolean;
}
/**
* @return true iff the order of the operands does not matter.
*/
public boolean isCommutative() {
return mIsAssociative;
}
}
public enum ExtendOperation {
sign_extend(BvOp.sign_extend),
zero_extend(BvOp.zero_extend),;
private final BvOp mBvOp;
private ExtendOperation(final BvOp bvop) {
mBvOp = bvop;
}
public BvOp getBvOp() {
return mBvOp;
}
}
private final BigInteger mValue;
private final BigInteger mIndex;
public BitvectorConstant(final BigInteger value, final BigInteger index) {
super();
mValue = computeUnifiedValue(value, index);
mIndex = index;
}
public BitvectorConstant(final BigInteger value, final String index) {
super();
final BigInteger indexAsBi = new BigInteger(index);
mValue = computeUnifiedValue(value, indexAsBi);
mIndex = indexAsBi;
}
/**
* @return the result of value % 2^index
*/
private static BigInteger computeUnifiedValue(final BigInteger value, final BigInteger index) {
return value.mod(new BigInteger("2").pow(index.intValueExact()));
}
public BigInteger getValue() {
return mValue;
}
public BigInteger getIndex() {
return mIndex;
}
public String getStringIndex() {
return mIndex.toString();
}
public boolean isZero() {
return mValue.signum() == 0;
}
public boolean isOne() {
return mValue.equals(BigInteger.ONE);
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + (mIndex == null ? 0 : mIndex.hashCode());
result = prime * result + (mValue == null ? 0 : mValue.hashCode());
return result;
}
@Override
public boolean equals(final Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final BitvectorConstant other = (BitvectorConstant) obj;
if (mIndex == null) {
if (other.mIndex != null) {
return false;
}
} else if (!mIndex.equals(other.mIndex)) {
return false;
}
if (mValue == null) {
if (other.mValue != null) {
return false;
}
} else if (!mValue.equals(other.mValue)) {
return false;
}
return true;
}
/**
* returns the numeral SMT-LIB representation of this bitvector constant
*/
@Override
public String toString() {
return "(_ bv" + mValue + " " + mIndex + ")";
}
public static BitvectorConstant maxValue(final int index) {
return new BitvectorConstant(BigInteger.valueOf(2).pow(index).subtract(BigInteger.valueOf(1)),
BigInteger.valueOf(index));
}
public static BitvectorConstant maxValue(final BigInteger index) {
return new BitvectorConstant(BigInteger.valueOf(2).pow(index.intValueExact()).subtract(BigInteger.valueOf(1)),
index);
}
public static BitvectorConstant bvadd(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return similarIndexBvOp_BitvectorResult(bv1, bv2, x -> y -> x.add(y));
}
public static BitvectorConstant bvsub(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return similarIndexBvOp_BitvectorResult(bv1, bv2, x -> y -> x.subtract(y));
}
public static BitvectorConstant bvmul(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return similarIndexBvOp_BitvectorResult(bv1, bv2, x -> y -> x.multiply(y));
}
public static BitvectorConstant bvudiv(final BitvectorConstant bv1, final BitvectorConstant bv2) {
if (bv2.getValue().signum() == 0) {
return maxValue(bv1.getIndex());
}
return similarIndexBvOp_BitvectorResult(bv1, bv2, x -> y -> x.divide(y));
}
public static BitvectorConstant bvurem(final BitvectorConstant bv1, final BitvectorConstant bv2) {
if (bv2.getValue().signum() == 0) {
return bv1;
}
return similarIndexBvOp_BitvectorResult(bv1, bv2, x -> y -> x.remainder(y));
}
public static BitvectorConstant bvsdiv(final BitvectorConstant bv1, final BitvectorConstant bv2) {
if (toSignedInt(bv2.getValue(), bv2.getIndex()).signum() == 0) {
return bvudiv(bv1, bv2);
}
return similarIndexBvOp_BitvectorResult(bv1, bv2,
x -> y -> toSignedInt(x, bv1.getIndex()).divide(toSignedInt(y, bv2.getIndex())));
}
public static BitvectorConstant bvsrem(final BitvectorConstant bv1, final BitvectorConstant bv2) {
if (toSignedInt(bv2.getValue(), bv2.getIndex()).signum() == 0) {
return bvurem(bv1, bv2);
}
return similarIndexBvOp_BitvectorResult(bv1, bv2,
x -> y -> toSignedInt(x, bv1.getIndex()).remainder(toSignedInt(y, bv2.getIndex())));
}
public static BitvectorConstant bvsmod(final BitvectorConstant bv1, final BitvectorConstant bv2) {
final BigInteger bigInt1 = toSignedInt(bv1.getValue(), bv1.getIndex());
final BigInteger bigInt2 = toSignedInt(bv2.getValue(), bv2.getIndex());
BitvectorConstant uts1 = bv1;
BitvectorConstant uts2 = bv2;
if (bigInt1.signum() == -1) {
uts1 = bvneg(uts1);
}
if (bigInt2.signum() == -1) {
uts2 = bvneg(uts2);
}
final BitvectorConstant bvurem = bvurem(uts1, uts2);
if ((bigInt1.signum() == -1) && (bigInt2.signum() == 1)) {
return bvadd(bvneg(bvurem), bv2);
} else if ((bigInt1.signum() == 1) && (bigInt2.signum() == -1)) {
return bvadd(bvurem, bv2);
} else if ((bigInt1.signum() == -1) && (bigInt2.signum() == -1)) {
return bvneg(bvurem);
} else {
return bvurem;
}
}
public static BitvectorConstant bvand(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return similarIndexBvOp_BitvectorResult(bv1, bv2, x -> y -> x.and(y));
}
public static BitvectorConstant bvor(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return similarIndexBvOp_BitvectorResult(bv1, bv2, x -> y -> x.or(y));
}
public static BitvectorConstant bvxor(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return similarIndexBvOp_BitvectorResult(bv1, bv2, x -> y -> x.xor(y));
}
public static BitvectorConstant bvshl(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return similarIndexBvOp_BitvectorResult(bv1, bv2, x -> y -> x.shiftLeft(y.intValueExact()));
}
public static BitvectorConstant bvlshr(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return similarIndexBvOp_BitvectorResult(bv1, bv2, x -> y -> x.shiftRight(y.intValueExact()));
}
public static BitvectorConstant bvashr(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return similarIndexBvOp_BitvectorResult(bv1, bv2,
x -> y -> toSignedInt(x, bv1.getIndex()).shiftRight(y.intValueExact()));
}
public static BitvectorConstant bvnot(final BitvectorConstant bv) {
return new BitvectorConstant(bv.getValue().not(), bv.getIndex());
}
public static BitvectorConstant bvneg(final BitvectorConstant bv) {
return new BitvectorConstant(toSignedInt(bv.getValue(), bv.getIndex()).negate(), bv.getIndex());
}
public static BitvectorConstant similarIndexBvOp_BitvectorResult(final BitvectorConstant bv1,
final BitvectorConstant bv2, final Function> fun) {
if (bv1.getIndex().equals(bv2.getIndex())) {
return new BitvectorConstant(fun.apply(bv1.getValue()).apply(bv2.getValue()), bv1.getIndex());
}
throw new IllegalArgumentException("incompatible indices " + bv1.getIndex() + " " + bv2.getIndex());
}
public static Boolean comparison(final BitvectorConstant bv1, final BitvectorConstant bv2,
final Function> fun) {
if (bv1.getIndex().equals(bv2.getIndex())) {
return fun.apply(bv1.getValue()).apply(bv2.getValue());
}
throw new IllegalArgumentException("incompatible indices " + bv1.getIndex() + " " + bv2.getIndex());
}
// public static BitvectorConstant bvshl(BitvectorConstant b1, BitvectorConstant b2) {
// int effectiveShift = Math.min(b1.getIndex().intValueExact(), b2.getValue().intValue());
// return new BitvectorConstant(b1.getValue().multiply(new BigInteger("2").pow(effectiveShift)), b1.getIndex());
// }
public static boolean bvult(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return comparison(bv1, bv2, x -> y -> x.compareTo(y) < 0);
}
public static boolean bvule(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return comparison(bv1, bv2, x -> y -> x.compareTo(y) <= 0);
}
public static boolean bvugt(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return comparison(bv1, bv2, x -> y -> x.compareTo(y) > 0);
}
public static boolean bvuge(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return comparison(bv1, bv2, x -> y -> x.compareTo(y) >= 0);
}
public static boolean bvslt(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return comparison(bv1, bv2,
x -> y -> toSignedInt(x, bv1.getIndex()).compareTo(toSignedInt(y, bv2.getIndex())) < 0);
}
public static boolean bvsle(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return comparison(bv1, bv2,
x -> y -> toSignedInt(x, bv1.getIndex()).compareTo(toSignedInt(y, bv2.getIndex())) <= 0);
}
public static boolean bvsgt(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return comparison(bv1, bv2,
x -> y -> toSignedInt(x, bv1.getIndex()).compareTo(toSignedInt(y, bv2.getIndex())) > 0);
}
public static boolean bvsge(final BitvectorConstant bv1, final BitvectorConstant bv2) {
return comparison(bv1, bv2,
x -> y -> toSignedInt(x, bv1.getIndex()).compareTo(toSignedInt(y, bv2.getIndex())) >= 0);
}
public static BitvectorConstant concat(final BitvectorConstant bv1, final BitvectorConstant bv2) {
final BigInteger concatSize = bv1.getIndex().add(bv2.getIndex());
final BigInteger concatValue =
bv1.getValue().multiply(BigInteger.TWO.pow(bv2.getIndex().intValue())).add(bv2.getValue());
return new BitvectorConstant(concatValue, concatSize);
}
public static BitvectorConstant extract(final BitvectorConstant bv, final int upperIndex, final int lowerIndex) {
final String binaryString = bvToBinaryString(bv);
final int resultIndex = upperIndex + 1 - lowerIndex;
final String extractedBinaryString;
if (resultIndex < binaryString.length()) {
extractedBinaryString =
binaryString.substring(binaryString.length() - 1 - upperIndex, binaryString.length() - lowerIndex);
} else {
extractedBinaryString = binaryString;
}
final BigInteger extractedValue = binaryStringToBv(extractedBinaryString);
return new BitvectorConstant(extractedValue, BigInteger.valueOf(resultIndex));
}
private static BigInteger binaryStringToBv(final String extractedBinaryString) {
return new BigInteger(extractedBinaryString, 2);
}
private static String bvToBinaryString(final BitvectorConstant bv) {
final String number = bv.getValue().toString(2);
final String leadingZeros =
new String(new char[bv.getIndex().intValueExact() - number.length()]).replace('\0', '0');
final String result = leadingZeros + number;
assert result.length() == bv.getIndex().intValueExact();
return result;
}
public static BitvectorConstant zero_extend(final BitvectorConstant bv, final BigInteger indexExtension) {
return new BitvectorConstant(bv.getValue(), bv.getIndex().add(indexExtension));
}
public static BitvectorConstant sign_extend(final BitvectorConstant bv, final BigInteger indexExtension) {
final BigInteger signed = bv.toSignedInt();
return new BitvectorConstant(signed, bv.getIndex().add(indexExtension));
}
public static BigInteger toSignedInt(final BigInteger bvValue, final BigInteger bvIndex) {
final BigInteger firstNegative = new BigInteger("2").pow(bvIndex.intValueExact() - 1);
if (bvValue.compareTo(firstNegative) < 0) {
return bvValue;
}
final BigInteger biggestUnsigned = new BigInteger("2").pow(bvIndex.intValueExact());
return bvValue.subtract(biggestUnsigned);
}
public BigInteger toSignedInt() {
return toSignedInt(mValue, mIndex);
}
public static BitvectorConstantOperationResult apply(final BvOp sbo,
final BitvectorConstant... operands) {
if (operands == null) {
throw new IllegalArgumentException("No operands");
}
if (operands.length != sbo.getArity()) {
throw new IllegalArgumentException("Operation " + sbo + " has arity " + sbo.getArity() + " but "
+ operands.length + " operands given");
}
switch (sbo) {
case bvadd:
return new BitvectorConstantOperationResult(bvadd(operands[0], operands[1]));
case bvand:
return new BitvectorConstantOperationResult(bvand(operands[0], operands[1]));
case bvashr:
return new BitvectorConstantOperationResult(bvashr(operands[0], operands[1]));
case bvlshr:
return new BitvectorConstantOperationResult(bvlshr(operands[0], operands[1]));
case bvmul:
return new BitvectorConstantOperationResult(bvmul(operands[0], operands[1]));
case bvneg:
return new BitvectorConstantOperationResult(bvneg(operands[0]));
case bvnot:
return new BitvectorConstantOperationResult(bvnot(operands[0]));
case bvor:
return new BitvectorConstantOperationResult(bvor(operands[0], operands[1]));
case bvsdiv:
return new BitvectorConstantOperationResult(bvsdiv(operands[0], operands[1]));
case bvsge:
return new BitvectorConstantOperationResult(bvsge(operands[0], operands[1]));
case bvsgt:
return new BitvectorConstantOperationResult(bvsgt(operands[0], operands[1]));
case bvshl:
return new BitvectorConstantOperationResult(bvshl(operands[0], operands[1]));
case bvsle:
return new BitvectorConstantOperationResult(bvsle(operands[0], operands[1]));
case bvslt:
return new BitvectorConstantOperationResult(bvslt(operands[0], operands[1]));
case bvsrem:
return new BitvectorConstantOperationResult(bvsrem(operands[0], operands[1]));
case bvsub:
return new BitvectorConstantOperationResult(bvsub(operands[0], operands[1]));
case bvudiv:
return new BitvectorConstantOperationResult(bvudiv(operands[0], operands[1]));
case bvuge:
return new BitvectorConstantOperationResult(bvuge(operands[0], operands[1]));
case bvugt:
return new BitvectorConstantOperationResult(bvugt(operands[0], operands[1]));
case bvule:
return new BitvectorConstantOperationResult(bvule(operands[0], operands[1]));
case bvult:
return new BitvectorConstantOperationResult(bvult(operands[0], operands[1]));
case bvurem:
return new BitvectorConstantOperationResult(bvurem(operands[0], operands[1]));
case bvxor:
return new BitvectorConstantOperationResult(bvxor(operands[0], operands[1]));
default:
throw new UnsupportedOperationException("Operation currently unsupported: " + sbo);
}
}
/**
*
* @author Daniel Dietsch (dietsch@informatik.uni-freiburg.de)
*
*/
public static final class BitvectorConstantOperationResult {
private final BitvectorConstant mBvResult;
private final Boolean mBooleanResult;
public BitvectorConstantOperationResult(final BitvectorConstant result) {
mBvResult = result;
mBooleanResult = null;
}
public BitvectorConstantOperationResult(final boolean result) {
mBvResult = null;
mBooleanResult = result;
}
public boolean isBoolean() {
return mBooleanResult != null;
}
public boolean getBooleanResult() {
return mBooleanResult.booleanValue();
}
public BitvectorConstant getBvResult() {
return mBvResult;
}
}
}