bit.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_MEMORY_BIT_HPP__
#define NEFORCE_CORE_MEMORY_BIT_HPP__

 
#include "NeForce/core/typeinfo/types.hpp"
NEFORCE_BEGIN_NAMESPACE__
 
NEFORCE_BEGIN_CONSTANTS__


NEFORCE_INLINE17 constexpr byte_t POPCOUNT_TABLE[256] = {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2,
        3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
        3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
        6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,
        3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4,
        5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
        6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
 // BitManipulation
 
NEFORCE_END_CONSTANTS__

 
#ifdef NEFORCE_ARCH_BITS_64

constexpr int popcount64(const uint64_t x) noexcept {
    return constants::POPCOUNT_TABLE[static_cast<byte_t>(x & 0xFFULL)] +
           constants::POPCOUNT_TABLE[static_cast<byte_t>((x >> 8) & 0xFFULL)] +
           constants::POPCOUNT_TABLE[static_cast<byte_t>((x >> 16) & 0xFFULL)] +
           constants::POPCOUNT_TABLE[static_cast<byte_t>((x >> 24) & 0xFFULL)] +
           constants::POPCOUNT_TABLE[static_cast<byte_t>((x >> 32) & 0xFFULL)] +
           constants::POPCOUNT_TABLE[static_cast<byte_t>((x >> 40) & 0xFFULL)] +
           constants::POPCOUNT_TABLE[static_cast<byte_t>((x >> 48) & 0xFFULL)] +
           constants::POPCOUNT_TABLE[static_cast<byte_t>((x >> 56) & 0xFFULL)];
}

NEFORCE_CONSTEXPR14 int clz64(uint64_t x) noexcept {
    if (x == 0) {
        return 64;
    }
    int n = 0;
    if (x <= 0x00000000FFFFFFFFULL) {
        n += 32;
        x <<= 32;
    }
    if (x <= 0x0000FFFFFFFFFFFFULL) {
        n += 16;
        x <<= 16;
    }
    if (x <= 0x00FFFFFFFFFFFFFFULL) {
        n += 8;
        x <<= 8;
    }
    if (x <= 0x0FFFFFFFFFFFFFFFULL) {
        n += 4;
        x <<= 4;
    }
    if (x <= 0x3FFFFFFFFFFFFFFFULL) {
        n += 2;
        x <<= 2;
    }
    if (x <= 0x7FFFFFFFFFFFFFFFULL) {
        n += 1;
    }
    return n;
}
 
#endif

constexpr int popcount32(const uint32_t x) noexcept {
    return constants::POPCOUNT_TABLE[static_cast<byte_t>(x & 0xFFU)] +
           constants::POPCOUNT_TABLE[static_cast<byte_t>((x >> 8) & 0xFFU)] +
           constants::POPCOUNT_TABLE[static_cast<byte_t>((x >> 16) & 0xFFU)] +
           constants::POPCOUNT_TABLE[static_cast<byte_t>((x >> 24) & 0xFFU)];
}

NEFORCE_CONSTEXPR14 int clz32(uint32_t x) noexcept {
    if (x == 0) {
        return 32;
    }
    int n = 0;
    if (x <= 0x0000FFFFU) {
        n += 16;
        x <<= 16;
    }
    if (x <= 0x00FFFFFFU) {
        n += 8;
        x <<= 8;
    }
    if (x <= 0x0FFFFFFFU) {
        n += 4;
        x <<= 4;
    }
    if (x <= 0x3FFFFFFFU) {
        n += 2;
        x <<= 2;
    }
    if (x <= 0x7FFFFFFFU) {
        n += 1;
    }
    return n;
}

constexpr int popcount(const uintptr_t x) noexcept {
#ifdef NEFORCE_ARCH_BITS_64
    return popcount64(x);
#else
    return popcount32(x);
#endif
}

constexpr int countl_zero(const uintptr_t x) noexcept {
#ifdef NEFORCE_ARCH_BITS_64
    return clz64(x);
#else
    return clz32(x);
#endif
}

constexpr int countl_one(const uintptr_t x) noexcept { return countl_zero(~x); }

constexpr int countr_zero(const uintptr_t x) noexcept { return popcount((x & (~x + 1)) - 1); }

constexpr int countr_one(const uintptr_t x) noexcept { return countr_zero(~x); }
 

constexpr int lowest_set_bit_pos(const intptr_t x) noexcept { return x == 0 ? -1 : countr_zero(x); }

NEFORCE_CONSTEXPR14 int highest_set_bit_pos(const intptr_t x) noexcept {
    if (x == 0) {
        return -1;
    }
#ifdef NEFORCE_ARCH_BITS_64
    return 63 - clz64(x);
#else
    return 31 - clz32(x);
#endif
}
 

NEFORCE_CONSTEXPR14 bool parity32(uint32_t x) noexcept {
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return (x & 1) != 0;
}
 
#ifdef NEFORCE_ARCH_BITS_64

NEFORCE_CONSTEXPR14 bool parity64(uint64_t x) noexcept {
    x ^= x >> 32;
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return (x & 1) != 0;
}
 
#endif

constexpr bool parity(const uintptr_t x) noexcept {
#ifdef NEFORCE_ARCH_BITS_64
    return parity64(x);
#else
    return parity32(x);
#endif
}
 

constexpr int bit_width(const uintptr_t x) noexcept {
#ifdef NEFORCE_ARCH_BITS_64
    return x == 0 ? 0 : 64 - countl_zero(x);
#else
    return x == 0 ? 0 : 32 - countl_zero(x);
#endif
}

constexpr uintptr_t bit_floor(const uintptr_t x) noexcept { return x == 0 ? 0 : uintptr_t{1} << (bit_width(x) - 1); }

NEFORCE_CONSTEXPR14 uint64_t bit_ceil(const uintptr_t x) noexcept {
    if (x <= 1) {
        return 1;
    }
    const uint64_t floor = bit_floor(x);
    return floor == x ? x : floor << 1;
}

constexpr bool has_single_bit(const uintptr_t x) noexcept { return x != 0 && (x & (x - 1)) == 0; }

NEFORCE_CONSTEXPR14 uint32_t rotate_l32(const uint32_t x, const int s) noexcept {
    constexpr int bits = 32;
    const int shift = ((s % bits) + bits) % bits;
    if (shift == 0) {
        return x;
    }
    return (x << shift) | (x >> (bits - shift));
}

NEFORCE_CONSTEXPR14 uint32_t rotate_r32(const uint32_t x, const int s) noexcept { return rotate_l32(x, -s); }
 
#ifdef NEFORCE_ARCH_BITS_64

NEFORCE_CONSTEXPR14 uint64_t rotate_l64(const uint64_t x, const int s) noexcept {
    constexpr int bits = 64;
    const int shift = ((s % bits) + bits) % bits;
    if (shift == 0) {
        return x;
    }
    return (x << shift) | (x >> (bits - shift));
}

NEFORCE_CONSTEXPR14 uint64_t rotate_r64(const uint64_t x, const int s) noexcept { return rotate_l64(x, -s); }
 
#endif

NEFORCE_CONSTEXPR14 int rotate_l(const uintptr_t x, const int s) noexcept {
#ifdef NEFORCE_ARCH_BITS_64
    return rotate_l64(x, s);
#else
    return rotate_l32(x, s);
#endif
}

NEFORCE_CONSTEXPR14 int rotate_r(const uintptr_t x, const int s) noexcept {
#ifdef NEFORCE_ARCH_BITS_64
    return rotate_r64(x, s);
#else
    return rotate_r32(x, s);
#endif
}
 

constexpr uintptr_t bit_extract(const uintptr_t x, const int pos, const int len) noexcept {
    return (x >> pos) & ((uintptr_t{1} << len) - 1);
}

NEFORCE_CONSTEXPR14 uintptr_t bit_insert(const uintptr_t x, const uintptr_t bits, const int pos,
                                         const int len) noexcept {
    const uintptr_t mask = ((uintptr_t{1} << len) - 1) << pos;
    return (x & ~mask) | ((bits << pos) & mask);
}
 

NEFORCE_CONSTEXPR14 uint32_t reverse_bits32(uint32_t x) noexcept {
    x = ((x >> 1) & 0x55555555U) | ((x & 0x55555555U) << 1);
    x = ((x >> 2) & 0x33333333U) | ((x & 0x33333333U) << 2);
    x = ((x >> 4) & 0x0F0F0F0FU) | ((x & 0x0F0F0F0FU) << 4);
    x = ((x >> 8) & 0x00FF00FFU) | ((x & 0x00FF00FFU) << 8);
    x = ((x >> 16) & 0x0000FFFFU) | ((x & 0x0000FFFFU) << 16);
    return x;
}
 
#ifdef NEFORCE_ARCH_BITS_64

NEFORCE_CONSTEXPR14 uint64_t reverse_bits64(uint64_t x) noexcept {
    x = ((x >> 1) & 0x5555555555555555ULL) | ((x & 0x5555555555555555ULL) << 1);
    x = ((x >> 2) & 0x3333333333333333ULL) | ((x & 0x3333333333333333ULL) << 2);
    x = ((x >> 4) & 0x0F0F0F0F0F0F0F0FULL) | ((x & 0x0F0F0F0F0F0F0F0FULL) << 4);
    x = ((x >> 8) & 0x00FF00FF00FF00FFULL) | ((x & 0x00FF00FF00FF00FFULL) << 8);
    x = ((x >> 16) & 0x0000FFFF0000FFFFULL) | ((x & 0x0000FFFF0000FFFFULL) << 16);
    x = (x >> 32) | (x << 32);
    return x;
}
 
#endif

constexpr uintptr_t reverse_bits(const uintptr_t x) noexcept {
#ifdef NEFORCE_ARCH_BITS_64
    return reverse_bits64(x);
#else
    return reverse_bits32(x);
#endif
}
 

constexpr uintptr_t mask_from_to(const int from, const int to) noexcept {
    return ((uintptr_t{1} << (to - from + 1)) - 1) << from;
}
 // BitManipulation
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_MEMORY_BIT_HPP__