path: root/util/generic/bitops.h

#pragma once

#include "ylimits.h"
#include "typelist.h"

#include <util/system/compiler.h>
#include <util/system/yassert.h>

#ifdef _MSC_VER
    #include <intrin.h>
#endif

namespace NBitOps {
    namespace NPrivate {
        template <unsigned N, typename T>
        struct TClp2Helper {
            static Y_FORCE_INLINE T Calc(T t) noexcept {
                const T prev = TClp2Helper<N / 2, T>::Calc(t);

                return prev | (prev >> N);
            }
        };

        template <typename T>
        struct TClp2Helper<0u, T> {
            static Y_FORCE_INLINE T Calc(T t) noexcept {
                return t - 1;
            }
        };

        extern const ui64 WORD_MASK[];
        extern const ui64 INVERSE_WORD_MASK[];

        // see http://www-graphics.stanford.edu/~seander/bithacks.html#ReverseParallel

        Y_FORCE_INLINE ui64 SwapOddEvenBits(ui64 v) {
            return ((v >> 1ULL) & 0x5555555555555555ULL) | ((v & 0x5555555555555555ULL) << 1ULL);
        }

        Y_FORCE_INLINE ui64 SwapBitPairs(ui64 v) {
            return ((v >> 2ULL) & 0x3333333333333333ULL) | ((v & 0x3333333333333333ULL) << 2ULL);
        }

        Y_FORCE_INLINE ui64 SwapNibbles(ui64 v) {
            return ((v >> 4ULL) & 0x0F0F0F0F0F0F0F0FULL) | ((v & 0x0F0F0F0F0F0F0F0FULL) << 4ULL);
        }

        Y_FORCE_INLINE ui64 SwapOddEvenBytes(ui64 v) {
            return ((v >> 8ULL) & 0x00FF00FF00FF00FFULL) | ((v & 0x00FF00FF00FF00FFULL) << 8ULL);
        }

        Y_FORCE_INLINE ui64 SwapBytePairs(ui64 v) {
            return ((v >> 16ULL) & 0x0000FFFF0000FFFFULL) | ((v & 0x0000FFFF0000FFFFULL) << 16ULL);
        }

        Y_FORCE_INLINE ui64 SwapByteQuads(ui64 v) {
            return (v >> 32ULL) | (v << 32ULL);
        }

#if defined(__GNUC__)
        inline unsigned GetValueBitCountImpl(unsigned int value) noexcept {
            Y_ASSERT(value); // because __builtin_clz* have undefined result for zero.
            return std::numeric_limits<unsigned int>::digits - __builtin_clz(value);
        }

        inline unsigned GetValueBitCountImpl(unsigned long value) noexcept {
            Y_ASSERT(value); // because __builtin_clz* have undefined result for zero.
            return std::numeric_limits<unsigned long>::digits - __builtin_clzl(value);
        }

        inline unsigned GetValueBitCountImpl(unsigned long long value) noexcept {
            Y_ASSERT(value); // because __builtin_clz* have undefined result for zero.
            return std::numeric_limits<unsigned long long>::digits - __builtin_clzll(value);
        }
#else
        /// Stupid realization for non-GCC. Can use BSR from x86 instructions set.
        template <typename T>
        inline unsigned GetValueBitCountImpl(T value) noexcept {
            Y_ASSERT(value);     // because __builtin_clz* have undefined result for zero.
            unsigned result = 1; // result == 0 - impossible value, see Y_ASSERT().
            value >>= 1;
            while (value) {
                value >>= 1;
                ++result;
            }

            return result;
        }
#endif

#if defined(__GNUC__)
        inline unsigned CountTrailingZeroBitsImpl(unsigned int value) noexcept {
            Y_ASSERT(value); // because __builtin_ctz* have undefined result for zero.
            return __builtin_ctz(value);
        }

        inline unsigned CountTrailingZeroBitsImpl(unsigned long value) noexcept {
            Y_ASSERT(value); // because __builtin_ctz* have undefined result for zero.
            return __builtin_ctzl(value);
        }

        inline unsigned CountTrailingZeroBitsImpl(unsigned long long value) noexcept {
            Y_ASSERT(value); // because __builtin_ctz* have undefined result for zero.
            return __builtin_ctzll(value);
        }
#else
        /// Stupid realization for non-GCC. Can use BSF from x86 instructions set.
        template <typename T>
        inline unsigned CountTrailingZeroBitsImpl(T value) noexcept {
            Y_ASSERT(value); // because __builtin_ctz* have undefined result for zero.
            unsigned result = 0;
            while (!(value & 1)) {
                value >>= 1;
                ++result;
            }

            return result;
        }
#endif

        template <typename T>
        Y_FORCE_INLINE T RotateBitsLeftImpl(T value, const ui8 shift) noexcept {
            constexpr ui8 bits = sizeof(T) * 8;
            constexpr ui8 mask = bits - 1;
            Y_ASSERT(shift <= mask);

            // do trick with mask to avoid undefined behaviour
            return (value << shift) | (value >> ((-shift) & mask));
        }

        template <typename T>
        Y_FORCE_INLINE T RotateBitsRightImpl(T value, const ui8 shift) noexcept {
            constexpr ui8 bits = sizeof(T) * 8;
            constexpr ui8 mask = bits - 1;
            Y_ASSERT(shift <= mask);

            // do trick with mask to avoid undefined behaviour
            return (value >> shift) | (value << ((-shift) & mask));
        }

#if defined(_x86_) && defined(__GNUC__)
        Y_FORCE_INLINE ui8 RotateBitsRightImpl(ui8 value, ui8 shift) noexcept {
            __asm__("rorb   %%cl, %0"
                    : "=r"(value)
                    : "0"(value), "c"(shift));
            return value;
        }

        Y_FORCE_INLINE ui16 RotateBitsRightImpl(ui16 value, ui8 shift) noexcept {
            __asm__("rorw   %%cl, %0"
                    : "=r"(value)
                    : "0"(value), "c"(shift));
            return value;
        }

        Y_FORCE_INLINE ui32 RotateBitsRightImpl(ui32 value, ui8 shift) noexcept {
            __asm__("rorl   %%cl, %0"
                    : "=r"(value)
                    : "0"(value), "c"(shift));
            return value;
        }

        Y_FORCE_INLINE ui8 RotateBitsLeftImpl(ui8 value, ui8 shift) noexcept {
            __asm__("rolb   %%cl, %0"
                    : "=r"(value)
                    : "0"(value), "c"(shift));
            return value;
        }

        Y_FORCE_INLINE ui16 RotateBitsLeftImpl(ui16 value, ui8 shift) noexcept {
            __asm__("rolw   %%cl, %0"
                    : "=r"(value)
                    : "0"(value), "c"(shift));
            return value;
        }

        Y_FORCE_INLINE ui32 RotateBitsLeftImpl(ui32 value, ui8 shift) noexcept {
            __asm__("roll   %%cl, %0"
                    : "=r"(value)
                    : "0"(value), "c"(shift));
            return value;
        }

    #if defined(_x86_64_)
        Y_FORCE_INLINE ui64 RotateBitsRightImpl(ui64 value, ui8 shift) noexcept {
            __asm__("rorq   %%cl, %0"
                    : "=r"(value)
                    : "0"(value), "c"(shift));
            return value;
        }

        Y_FORCE_INLINE ui64 RotateBitsLeftImpl(ui64 value, ui8 shift) noexcept {
            __asm__("rolq   %%cl, %0"
                    : "=r"(value)
                    : "0"(value), "c"(shift));
            return value;
        }
    #endif
#endif
    }
}

/**
 * Computes the next power of 2 higher or equal to the integer parameter `t`.
 * If `t` is a power of 2 will return `t`.
 * Result is undefined for `t == 0`.
 */
template <typename T>
static inline T FastClp2(T t) noexcept {
    Y_ASSERT(t > 0);
    using TCvt = typename ::TUnsignedInts::template TSelectBy<TSizeOfPredicate<sizeof(T)>::template TResult>::type;
    return 1 + ::NBitOps::NPrivate::TClp2Helper<sizeof(TCvt) * 4, T>::Calc(static_cast<TCvt>(t));
}

/**
 * Check if integer is a power of 2.
 */
template <typename T>
Y_CONST_FUNCTION constexpr bool IsPowerOf2(T v) noexcept {
    return v > 0 && (v & (v - 1)) == 0;
}

/**
 * Returns the number of leading 0-bits in `value`, starting at the most significant bit position.
 */
template <typename T>
static inline unsigned GetValueBitCount(T value) noexcept {
    Y_ASSERT(value > 0);
    using TCvt = typename ::TUnsignedInts::template TSelectBy<TSizeOfPredicate<sizeof(T)>::template TResult>::type;
    return ::NBitOps::NPrivate::GetValueBitCountImpl(static_cast<TCvt>(value));
}

/**
 * Returns the number of trailing 0-bits in `value`, starting at the least significant bit position
 */
template <typename T>
static inline unsigned CountTrailingZeroBits(T value) noexcept {
    Y_ASSERT(value > 0);
    using TCvt = typename ::TUnsignedInts::template TSelectBy<TSizeOfPredicate<sizeof(T)>::template TResult>::type;
    return ::NBitOps::NPrivate::CountTrailingZeroBitsImpl(static_cast<TCvt>(value));
}

/*
 * Returns 64-bit mask with `bits` lower bits set.
 */
Y_FORCE_INLINE ui64 MaskLowerBits(ui64 bits) {
    return ::NBitOps::NPrivate::WORD_MASK[bits];
}

/*
 * Return 64-bit mask with `bits` set starting from `skipbits`.
 */
Y_FORCE_INLINE ui64 MaskLowerBits(ui64 bits, ui64 skipbits) {
    return MaskLowerBits(bits) << skipbits;
}

/*
 * Return 64-bit mask with all bits set except for `bits` lower bits.
 */
Y_FORCE_INLINE ui64 InverseMaskLowerBits(ui64 bits) {
    return ::NBitOps::NPrivate::INVERSE_WORD_MASK[bits];
}

/*
 * Return 64-bit mask with all bits set except for `bits` bitst starting from `skipbits`.
 */
Y_FORCE_INLINE ui64 InverseMaskLowerBits(ui64 bits, ui64 skipbits) {
    return ~MaskLowerBits(bits, skipbits);
}

/*
 * Returns 0-based position of the most significant bit that is set. 0 for 0.
 */
Y_FORCE_INLINE ui64 MostSignificantBit(ui64 v) {
#ifdef __GNUC__
    ui64 res = v ? (63 - __builtin_clzll(v)) : 0;
#elif defined(_MSC_VER) && defined(_64_)
    unsigned long res = 0;
    if (v)
        _BitScanReverse64(&res, v);
#else
    ui64 res = 0;
    if (v)
        while (v >>= 1)
            ++res;
#endif
    return res;
}

/**
 * Returns 0-based position of the least significant bit that is set. 0 for 0.
 */
Y_FORCE_INLINE ui64 LeastSignificantBit(ui64 v) {
#ifdef __GNUC__
    ui64 res = v ? __builtin_ffsll(v) - 1 : 0;
#elif defined(_MSC_VER) && defined(_64_)
    unsigned long res = 0;
    if (v)
        _BitScanForward64(&res, v);
#else
    ui64 res = 0;
    if (v) {
        while (!(v & 1)) {
            ++res;
            v >>= 1;
        }
    }
#endif
    return res;
}

/*
 * Returns 0 - based position of the most significant bit (compile time)
 * 0 for 0.
 */
constexpr ui64 MostSignificantBitCT(ui64 x) {
    return x > 1 ? 1 + MostSignificantBitCT(x >> 1) : 0;
}

/*
 * Return rounded up binary logarithm of `x`.
 */
Y_FORCE_INLINE ui8 CeilLog2(ui64 x) {
    return static_cast<ui8>(MostSignificantBit(x - 1)) + 1;
}

Y_FORCE_INLINE ui8 ReverseBytes(ui8 t) {
    return t;
}

Y_FORCE_INLINE ui16 ReverseBytes(ui16 t) {
    return static_cast<ui16>(::NBitOps::NPrivate::SwapOddEvenBytes(t));
}

Y_FORCE_INLINE ui32 ReverseBytes(ui32 t) {
    return static_cast<ui32>(::NBitOps::NPrivate::SwapBytePairs(
        ::NBitOps::NPrivate::SwapOddEvenBytes(t)));
}

Y_FORCE_INLINE ui64 ReverseBytes(ui64 t) {
    return ::NBitOps::NPrivate::SwapByteQuads((::NBitOps::NPrivate::SwapOddEvenBytes(t)));
}

Y_FORCE_INLINE ui8 ReverseBits(ui8 t) {
    return static_cast<ui8>(::NBitOps::NPrivate::SwapNibbles(
        ::NBitOps::NPrivate::SwapBitPairs(
            ::NBitOps::NPrivate::SwapOddEvenBits(t))));
}

Y_FORCE_INLINE ui16 ReverseBits(ui16 t) {
    return static_cast<ui16>(::NBitOps::NPrivate::SwapOddEvenBytes(
        ::NBitOps::NPrivate::SwapNibbles(
            ::NBitOps::NPrivate::SwapBitPairs(
                ::NBitOps::NPrivate::SwapOddEvenBits(t)))));
}

Y_FORCE_INLINE ui32 ReverseBits(ui32 t) {
    return static_cast<ui32>(::NBitOps::NPrivate::SwapBytePairs(
        ::NBitOps::NPrivate::SwapOddEvenBytes(
            ::NBitOps::NPrivate::SwapNibbles(
                ::NBitOps::NPrivate::SwapBitPairs(
                    ::NBitOps::NPrivate::SwapOddEvenBits(t))))));
}

Y_FORCE_INLINE ui64 ReverseBits(ui64 t) {
    return ::NBitOps::NPrivate::SwapByteQuads(
        ::NBitOps::NPrivate::SwapBytePairs(
            ::NBitOps::NPrivate::SwapOddEvenBytes(
                ::NBitOps::NPrivate::SwapNibbles(
                    ::NBitOps::NPrivate::SwapBitPairs(
                        ::NBitOps::NPrivate::SwapOddEvenBits(t))))));
}

/*
 * Reverse first `bits` bits
 * 1000111000111000 , bits = 6 => 1000111000000111
 */
template <typename T>
Y_FORCE_INLINE T ReverseBits(T v, ui64 bits) {
    return bits ? (T(v & ::InverseMaskLowerBits(bits)) | T(ReverseBits(T(v & ::MaskLowerBits(bits)))) >> ((ui64{sizeof(T)} << ui64{3}) - bits)) : v;
}

/*
 * Referse first `bits` bits starting from `skipbits` bits
 * 1000111000111000 , bits = 4, skipbits = 2 => 1000111000011100
 */
template <typename T>
Y_FORCE_INLINE T ReverseBits(T v, ui64 bits, ui64 skipbits) {
    return (T(ReverseBits((v >> skipbits), bits)) << skipbits) | T(v & MaskLowerBits(skipbits));
}

/* Rotate bits left. Also known as left circular shift.
 */
template <typename T>
Y_FORCE_INLINE T RotateBitsLeft(T value, const ui8 shift) noexcept {
    static_assert(std::is_unsigned<T>::value, "must be unsigned arithmetic type");
    return ::NBitOps::NPrivate::RotateBitsLeftImpl((TFixedWidthUnsignedInt<T>)value, shift);
}

/* Rotate bits right. Also known as right circular shift.
 */
template <typename T>
Y_FORCE_INLINE T RotateBitsRight(T value, const ui8 shift) noexcept {
    static_assert(std::is_unsigned<T>::value, "must be unsigned arithmetic type");
    return ::NBitOps::NPrivate::RotateBitsRightImpl((TFixedWidthUnsignedInt<T>)value, shift);
}

/* Rotate bits left. Also known as left circular shift.
 */
template <typename T>
constexpr T RotateBitsLeftCT(T value, const ui8 shift) noexcept {
    static_assert(std::is_unsigned<T>::value, "must be unsigned arithmetic type");

    // do trick with mask to avoid undefined behaviour
    return (value << shift) | (value >> ((-shift) & (sizeof(T) * 8 - 1)));
}

/* Rotate bits right. Also known as right circular shift.
 */
template <typename T>
constexpr T RotateBitsRightCT(T value, const ui8 shift) noexcept {
    static_assert(std::is_unsigned<T>::value, "must be unsigned arithmetic type");

    // do trick with mask to avoid undefined behaviour
    return (value >> shift) | (value << ((-shift) & (sizeof(T) * 8 - 1)));
}

/* Remain `size` bits to current `offset` of `value`
   size, offset are less than number of bits in size_type
 */
template <size_t Offset, size_t Size, class T>
Y_FORCE_INLINE T SelectBits(T value) {
    static_assert(Size < sizeof(T) * 8, "violated: Size < sizeof(T) * 8"); 
    static_assert(Offset < sizeof(T) * 8, "violated: Offset < sizeof(T) * 8"); 
    T id = 1;
    return (value >> Offset) & ((id << Size) - id);
}

/* Set `size` bits of `bits` to current offset of `value`. Requires that bits <= (1 << size) - 1
   size, offset are less than number of bits in size_type
 */
template <size_t Offset, size_t Size, class T>
void SetBits(T& value, T bits) {
    static_assert(Size < sizeof(T) * 8, "violated: Size < sizeof(T) * 8"); 
    static_assert(Offset < sizeof(T) * 8, "violated: Offset < sizeof(T) * 8"); 
    T id = 1;
    T maxValue = ((id << Size) - id);
    Y_ASSERT(bits <= maxValue);
    value &= ~(maxValue << Offset);
    value |= bits << Offset;
}

inline constexpr ui64 NthBit64(int bit) {
    return ui64(1) << bit;
}

inline constexpr ui64 Mask64(int bits) {
    return NthBit64(bits) - 1;
}