BitOps.h

#ifndef ROSE_BitOps_H
#define ROSE_BitOps_H
 
#include <Sawyer/Assert.h>
#include <Sawyer/Optional.h>
 
namespace Rose {
 
namespace BitOps {
 
template<typename Unsigned>
inline size_t nBits(Unsigned x = Unsigned(0)) {
    return 8*sizeof(Unsigned);
}
 
template<typename Unsigned>
inline Unsigned all(bool b = true) {
    return Unsigned(0) - Unsigned(b ? 1 : 0);
}
 
template<typename Unsigned> inline Unsigned lowMask(size_t n);
 
template<typename Unsigned>
inline Unsigned allLsb(Unsigned src, size_t w, bool b = true) {
    ASSERT_require(w <= nBits(src));
    if (b) {
        return src | lowMask<Unsigned>(w);
    } else {
        return src & ~lowMask<Unsigned>(w);
    }
}
 
template<typename Unsigned>
inline Unsigned lowMask(size_t n) {
    return n >= nBits<Unsigned>() ? all<Unsigned>(true) : (Unsigned(1) << n) - Unsigned(1);
}
 
template<typename Unsigned>
inline Unsigned highMask(size_t n) {
    return n >= nBits<Unsigned>() ? all<Unsigned>(true) : lowMask<Unsigned>(n) << (nBits<Unsigned>() - n);
}
 
template<typename Unsigned>
inline Unsigned select(Unsigned cond, Unsigned a, Unsigned b) {
    return (a & cond) | (b & ~cond);
}
 
template<typename Unsigned>
inline Unsigned shiftLeft(Unsigned src, size_t n, bool b = false) {
    if (n >= nBits(src)) {
        return all<Unsigned>(b);
    } else {
        return Unsigned(src << n) | (all<Unsigned>(b) & lowMask<Unsigned>(n));
    }
}
 
template<typename Unsigned>
inline Unsigned shiftLeftLsb(Unsigned src, size_t w, size_t n, bool b = false) {
    ASSERT_require(w <= nBits(src));
    if (n >= w) {
        return allLsb(src, w, b);
    } else {
        return select(lowMask<Unsigned>(w), shiftLeft(src, n, b), src);
    }
}
 
template<typename Unsigned>
inline Unsigned shiftRight(Unsigned src, size_t n, bool b = false) {
    if (n >= nBits(src)) {
        return all<Unsigned>(b);
    } else {
        return Unsigned(src >> n) | (all<Unsigned>(b) & highMask<Unsigned>(n));
    }
}
 
template<typename Unsigned>
inline Unsigned shiftRightLsb(Unsigned src, size_t w, size_t n, bool b = false) {
    ASSERT_require(w <= nBits(src));
    if (n >= w) {
        return allLsb(src, w, b);
    } else {
        return select(lowMask<Unsigned>(w), shiftRight(src & lowMask<Unsigned>(w), n, b), src);
    }
}
 
template<typename Unsigned>
inline Unsigned position(size_t i) {
    return i < nBits<Unsigned>() ? shiftLeft(Unsigned(1), i) : Unsigned(0);
}
 
template<typename Unsigned>
inline Unsigned positionLsb(Unsigned src, size_t w, size_t i) {
    ASSERT_require(w <= nBits(src));
    return select(lowMask<Unsigned>(w), position<Unsigned>(i), src);
}
 
template<typename Unsigned>
inline Unsigned mask(size_t least, size_t greatest) {
    ASSERT_require(greatest < nBits<Unsigned>());
    ASSERT_require(greatest >= least);
    return shiftLeft(lowMask<Unsigned>(greatest - least + 1), least);
}
 
template<typename Unsigned>
inline Unsigned maskLsb(Unsigned src, size_t w, size_t least, size_t greatest) {
    ASSERT_require(w <= nBits(src));
    return select(lowMask<Unsigned>(w), mask<Unsigned>(least, greatest), src);
}
 
template<typename Unsigned>
inline bool bit(Unsigned src, size_t i) {
    return i < nBits(src) ? (src & position<Unsigned>(i)) != 0 : false;
}
 
template<typename Unsigned>
inline bool bitLsb(Unsigned src, size_t w, size_t i) {
    return i < w ? (src & position<Unsigned>(i)) != 0 : false;
}
 
template<typename Unsigned>
inline bool msb(Unsigned src) {
    return bit(src, nBits(src) - 1);
}
 
template<typename Unsigned>
inline bool msbLsb(Unsigned src, size_t w) {
    ASSERT_require(w <= nBits(src));
    return w > 0 ? bit(src, w-1) : false;
}
 
template<typename Unsigned>
inline Unsigned shiftRightSigned(Unsigned src, size_t n) {
    return shiftRight(src, n, msb(src));
}
 
 
template<typename Unsigned>
inline Unsigned shiftRightSigned(Unsigned src, size_t w, size_t n) {
    return shiftRightLsb(src, n, w, msbLsb(src, w));
}
 
template<typename Unsigned>
inline Unsigned bits(Unsigned src, size_t least, size_t greatest) {
    return shiftRight(src & mask<Unsigned>(least, greatest), least);
}
 
template<typename Unsigned>
inline Unsigned bitsLsb(Unsigned src, size_t w, size_t least, size_t greatest) {
    return shiftRight(src & mask<Unsigned>(least, greatest) & lowMask<Unsigned>(w), least);
}
 
 
template<typename UnsignedTarget, typename UnsignedSource>
inline UnsignedTarget convert(UnsignedSource x, bool b = false) {
    if (nBits(x) < nBits<UnsignedTarget>()) {
        // extending
        return UnsignedTarget(x) | (all<UnsignedTarget>(b) & ~lowMask<UnsignedTarget>(nBits(x)));
    } else {
        // truncating
        return UnsignedTarget(x & lowMask<UnsignedSource>(nBits<UnsignedTarget>()));
    }
}
 
template<typename UnsignedTarget, typename UnsignedSource>
inline UnsignedTarget convertSigned(UnsignedSource x) {
    return convert<UnsignedTarget>(x, msb(x));
}
 
template<typename Unsigned>
inline Unsigned signExtend(Unsigned src, size_t n) {
    if (n < nBits(src)) {
        if (msbLsb(src, n)) {
            src |= mask<Unsigned>(n, nBits(src)-1);
        } else {
            src &= ~mask<Unsigned>(n, nBits(src)-1);
        }
    }
    return src;
}
 
template<typename Unsigned>
inline Unsigned signExtendLsb(Unsigned src, size_t n, size_t m) {
    ASSERT_require(n > 0);
    ASSERT_require(m >= n);
    ASSERT_require(m <= nBits(src));
    if (m == n) {
        return src;
    } else {
        Unsigned newBitsMask = mask<Unsigned>(n, m-1);
        if (bit(src, n-1)) {
            return src | newBitsMask;
        } else {
            return src & ~newBitsMask;
        }
    }
}
 
template<typename Unsigned>
inline Unsigned rotateLeft(Unsigned src, size_t n) {
    n %= nBits(src);
    return shiftLeft(src, n) | shiftRight(src, nBits(src)-n);
}
 
template<typename Unsigned>
inline Unsigned rotateLeftLsb(Unsigned src, size_t w, size_t n) {
    ASSERT_require(w <= nBits(src));
    n = w ? n % w : 0;
    return select(lowMask<Unsigned>(w),
                  shiftLeftLsb(src, w, n) | shiftRightLsb(src, w-n),
                  src);
}
 
template<typename Unsigned>
inline Unsigned rotateRight(Unsigned src, size_t n) {
    n %= nBits(src);
    return shiftRight(src, n) | shiftLeft(src, nBits(src)-n);
}
 
template<typename Unsigned>
inline Unsigned rotateRightLsb(Unsigned src, size_t w, size_t n) {
    ASSERT_require(w <= nBits(src));
    n = w ? n % w : 0;
    return select(lowMask<Unsigned>(w),
                  shiftRightLsb(src, w, n) | shiftLeftLsb(src, w, w-n),
                  src);
}
 
template<typename Unsigned>
inline Unsigned replicate(Unsigned src, size_t n) {
    ASSERT_require(n != 0);
    if (n >= nBits(src)) {
        return src;
    } else {
        size_t ngroups = (nBits(src) + 1) / n;
        Unsigned retval = 0;
        for (size_t i = 0; i < ngroups; ++i)
            retval |= shiftLeft(src & lowMask<Unsigned>(n), i*n);
        return retval;
    }
}
 
template<typename Unsigned>
inline Unsigned replicateLsb(Unsigned src, size_t w, size_t n) {
    ASSERT_require(w <= nBits(src));
    return select(lowMask<Unsigned>(w), replicate(src, n), src);
}
 
template<typename Unsigned>
inline Sawyer::Optional<size_t> highestSetBit(Unsigned src) {
    if (src) {
        for (size_t i = nBits(src); i > 0; --i) {
            if (bit(src, i-1))
                return i-1;
        }
    }
    return Sawyer::Nothing();
}
 
template<typename Unsigned>
inline size_t nSet(Unsigned src) {
    size_t retval = 0;
    while (src != 0) {
        if ((src & 1) != 0)
            ++retval;
        src >>= 1;
    }
    return retval;
}
 
} // namespace
} // namespace
#endif