MathTools.icc

Go to the documentation of this file.

/*
    Copyright (c) 2002-2009 Tampere University.
 
    This file is part of TTA-Based Codesign Environment (TCE).
 
    Permission is hereby granted, free of charge, to any person obtaining a
    copy of this software and associated documentation files (the "Software"),
    to deal in the Software without restriction, including without limitation
    the rights to use, copy, modify, merge, publish, distribute, sublicense,
    and/or sell copies of the Software, and to permit persons to whom the
    Software is furnished to do so, subject to the following conditions:
 
    The above copyright notice and this permission notice shall be included in
    all copies or substantial portions of the Software.
 
    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
    THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
    DEALINGS IN THE SOFTWARE.
 */
/**
 * @file MathTools.icc
 *
 * Inline implementations.
 *
 * @author Ari Metsähalme 2005 (ari.metsahalme-no.spam-tut.fi)
 * @author Pekka Jääskeläinen 2006 (pekka.jaaskelainen-no.spam-tut.fi)
 */
 
#include <cstdlib>
#include <bitset>
#include <cmath>
#include <ctime>
#include "Exception.hh"
#include "MathTools.hh"
#include "BaseType.hh"
 
/**
 * Returns the number of bits required to represent the given (nonzero) number
 * as an unsigned number. Gives result(1) for 0.
 *
 * @note assumes that integers are stored as 2's complement.
 *
 * @param number The number.
 * @return The number of bits required to represent the given number.
 */
inline int
MathTools::requiredBits(unsigned long int number) {
    if (number == 0) {
        return 1;
    } else {
        return requiredBits0Bit0(number);
    }
}
 
/**
 * Returns the number of bits required to represent the given number
 * as an unsigned number. Gives result(0) for 0.
 */
inline int
MathTools::requiredBits0Bit0(long unsigned int number) {
    unsigned int bits = 0;
    while (number != 0) {
        number = number >> 1;
        bits++;
    }
    return bits;
}
 
/**
 * Returns ceiling of base-2 logarithm of given number as integer.
 */
inline int
MathTools::ceil_log2(long unsigned int number) {
    return static_cast<int>(ceil(log(number)/log(2.0)));
}
 
/**
 * Returns ceiling of divided numbers as integer.
 */
template<typename NumberType>
inline int
MathTools::ceil_div(NumberType dividee, NumberType diveder) {
    return static_cast<int>(ceil((double) dividee / (double) diveder));
}
 
 
 
/**
 * Returns the number of bits required to represent the given number as
 * a signed integer.
 *
 * @note assumes that integers are stored as 2's complement.
 *
 * @param number The number.
 * @return The number of bits required to represent the given number.
 */
 
inline int
MathTools::requiredBitsSigned(SLongWord number) {
    int bits = 1;
    while (number != -1 && number != 0) {
        number = number >> 1;
        bits++;
    }
    return bits;
}
 
/**
 * Returns the number of bits required to represent the given number as
 * a signed integer.
 *
 * @note assumes that integers are stored as 2's complement.
 *
 * @param number The number.
 * @return The number of bits required to represent the given number.
 */
 
inline int
MathTools::requiredBitsSigned(UInt32 number) {
    
    // first cast to a signed type
    int32_t numberSigned = static_cast<int32_t>(number);
    return requiredBitsSigned(static_cast<SLongWord>(numberSigned));
}
 
/**
 * Returns the number of bits required to represent the given number as
 * a signed integer.
 *
 * @note assumes that integers are stored as 2's complement.
 *
 * @param number The number.
 * @return The number of bits required to represent the given number.
 */
 
inline int
MathTools::requiredBitsSigned(int number) {
    
    return requiredBitsSigned(static_cast<SLongWord>(number));
}
 
/**
 * Returns the number of bits required to represent the given number as
 * a signed integer.
 *
 * @note assumes that integers are stored as 2's complement.
 *
 * @param number The number.
 * @return The number of bits required to represent the given number.
 */
 
inline int
MathTools::requiredBitsSigned(ULongWord number) {
    return requiredBitsSigned(static_cast<SLongWord>(number));
}
 
/**
 * Returns the number of bits required to represent the give number as
 * an unsigned number. 0 is implicit 0.
 *
 * @note assumes that integers are stored as 2's complement.
 *
 * @param number The number.
 * @return The number of bits required to represent the given number.
 */
inline unsigned int
MathTools::bitLength(long unsigned int number) {
    unsigned int bits = 0;
    while (number != 0) {
        number = number >> 1;
        bits++;
    }
    return bits;
}
 
 
/**
 * Compares bit fields (binary encoded) of enc1 and enc2.
 *
 * @verbatim
 * Example:
 *   ->|  |<-----| pos1  = 6
 * 00001101011011| enc1  = 859   =>     1101
 * 00001011110100| enc2  = 756   => =   1101
 *       ->|  |<-| pos2  = 2       ---------
 * --------------- width = 4            true
 * @endverbatim
 *
 * @param enc1 The first binary encoded bit field.
 * @param pos1 The first LSB bit from right of the enc1.
 * @param enc2 The second binary encoded bit field.
 * @param pos2 The first LSB bit from right of the enc2.
 * @param width The number of bits considered in the comparison.
 * @return True if the fields do match. Otherwise, false.
 */
inline bool
MathTools::bitFieldsEquals(
    unsigned enc1, unsigned pos1,
    unsigned enc2, unsigned pos2,
    unsigned width) {
 
    if (width) {
        enc1 = enc1 >> pos1;
        enc2 = enc2 >> pos2;
        enc1 = enc1 & ~(~(0u) << width);
        enc2 = enc2 & ~(~(0u) << width);
        return enc1 == enc2;
    }
    return false;
}
 
 
/**
 * Returns the value of the bit at a given position in an integer.
 *
 * @param integer The integer.
 * @param index Indicates which bit should be returned (0 = LSB).
 * @return The value of the bit indicated by the given index.
 */
inline bool
MathTools::bit(ULongWord integer, unsigned int index) {
    return (integer & (1 << index)) != 0;
}
 
 
/**
 * Sets or clears bit at the index.
 *
 * @param bits The bits.
 * @param index The index of the bit starting from zero. The bits are indexed
 *              from LSB.
 * @param bitState The state of the bit to be set. By default sets bit to one.
 */
template<class IntegerType>
inline
void
MathTools::setBit(
    IntegerType& bits, unsigned int index, bool bitState) {
    if (bitState) {
        bits |= IntegerType(1) << index;
    } else {
        bits &= ~(IntegerType(1) << index);
    }
}
 
 
/**
 * Chops a signed integer number to a given bit width.
 *
 * Overwrites all bits that do not fit in the given bit width with the sign
 * bit (the bit at position width - 1).
 *
 * This operation corresponds to reinterpreting the given number as a signed
 * word of given bit width.
 *
 * @param value A signed integer.
 * @param width Number of meaningful bits in the given integer.
 * @return The sign-extended value of the integer.
 * @exception OutOfRange If width > integer size
 */
inline SLongWord
MathTools::signExtendTo(SLongWord value, int width) {
 
    int bitsInInt = sizeof(value) * BYTE_BITWIDTH;
    if (width > bitsInInt) {
        throw OutOfRange(__FILE__, __LINE__, __func__);
    }
 
    value = value << (bitsInInt - width);
    value = value >> (bitsInInt - width);
 
    return value;
}
 
 
/**
 * Chops an unsigned integer number to a given bit width.
 *
 * Overwrites all bits that do not fit in the given bit width with zero.
 *
 * This operation corresponds to reinterpreting the given number as an
 * unsigned word of given bit width.
 *
 * @param value An unsigned integer.
 * @param width Number of meaningful bits in the given integer.
 * @return The zero-extended value of the integer.
 * @exception OutOfRange If width > integer size
 */
inline ULongWord
MathTools::zeroExtendTo(ULongWord value, int width) {
 
    int bitsInInt = sizeof(value) * BYTE_BITWIDTH;
    if (width > bitsInInt) {
        throw OutOfRange(__FILE__, __LINE__, __func__);
    }
 
    // and with a mask with only the lower 'width' bits '1'
    value = value & (~(ULongWord)0 >> (bitsInInt - width));
 
    return value;
}
 
 
/**
 * Same as signExtendTo, except without additional overhead of exceptions
 *
 * @param value A signed integer.
 * @param width Number of meaningful bits in the given integer.
 * @note width must not exceed int bitwidth!
 * @return The sign-extended value of the integer.
 */
inline SLongWord
MathTools::fastSignExtendTo(SLongWord value, int width) {
 
    const int bitsInInt = sizeof(SLongWord) * BYTE_BITWIDTH;
    
    value = value << (bitsInInt - width);
    value = value >> (bitsInInt - width);
 
    return value;
}
 
 
/**
 * Same as zeroExtendTo, except without additional overhead of exceptions
 *
 * @param value An unsigned integer.
 * @param width Number of meaningful bits in the given integer.
 * @note width must not exceed int bitwidth!
 * @return The zero-extended value of the integer.
 */
inline ULongWord
MathTools::fastZeroExtendTo(ULongWord value, int width) {
 
    const int bitsInInt = sizeof(value) * BYTE_BITWIDTH;
 
    // and with a mask with only the lower 'width' bits '1'
    value = value & (~(ULongWord)0 >> (bitsInInt - width));
 
    return value;
}
 
 
/**
 * Returns a random number between range min..max
 * 
 * @param min minimum value
 * @param max maximum value
 * @return The generated pseudo-random number
 */
inline int
MathTools::random(int min, int max) {
    static bool initialized = false;
    if (!initialized) {
        srand(std::time(0)); 
        initialized = true;
    }
    return (rand() % (max - min + 1)) + min;
}
 
/**
 * Rounds a number upwards to a number which is of power-2.
 */
inline unsigned int
MathTools::roundUpToPowerTwo(unsigned int number) {
    unsigned int i = 0;
    if (number == 0) {
        return 0;
    }
    for (; (1u << i) < number; i++) ;
    return (1u << i);
}
 
/**
 * Rounds a number downwards to a number which is of power-2.
 */
inline ULongWord
MathTools::roundDownToPowerTwo(ULongWord number) {
    ULongWord i = 0;
    if (number == 0) {
        return 0;
    }
    for (; 1lu << i <= number; i++) ;
    return (1lu<<i) >> 1;
}
 
/**
 * Rounds a number upwards to a number which is of power-2.
 */
inline int
MathTools::roundUpToPowerTwo(int number) {
    return static_cast<int>(roundUpToPowerTwo(
        static_cast<unsigned int>(number)));
}
 
/**
 * Rounds a number downwards to a number which is of power-2.
 */
inline SLongWord
MathTools::roundDownToPowerTwo(SLongWord number) {
    return static_cast<SLongWord>(roundDownToPowerTwo(
        static_cast<ULongWord>(number)));
}
 
 
/**
 * Returns true if the number is in set of 2^i where i is positive integer.
 */
inline bool
MathTools::isInPowerOfTwo(unsigned int number) {
    std::bitset<sizeof(unsigned int)*8> bits(number);
    return bits.count() == 1;
}
 
 
/**
 * Return integer range that can be expressed by a binary field.
 *
 * The template argument must implement:
 * - ResultNumberType(0), ResultNumberType(1),
 * - (-ResultNumberType) -> ResultNumberType,
 * - (ResultNumberType << unsigned) -> ResultNumberType and
 * - (ResultNumberType - int) -> ResultNumberType
 */
template<typename ResultNumberTypeS, typename ResultNumberTypeU>
inline std::pair<ResultNumberTypeS, ResultNumberTypeU>
MathTools::bitsToIntegerRange(
    unsigned bitWidth, bool signExtending) {
 
    if (bitWidth == 0) {
        return std::make_pair(ResultNumberTypeS(0), ResultNumberTypeU(0));
    }
 
    // Todo needs different handling when
    // bitWidth == bitWidth(ResultNumberType)
 
    ResultNumberTypeS currLowerBound(0);
    ResultNumberTypeU currUpperBound(0);
    if (signExtending) {
        currLowerBound = -(ResultNumberTypeS(1) << (bitWidth-1));
        currUpperBound = (ResultNumberTypeU(1) << (bitWidth-1))-1;
    } else {
        currUpperBound = (ResultNumberTypeU(1) << (bitWidth))-1;
    }
    return std::make_pair(currLowerBound, currUpperBound);
}