123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285 |
- // Bits/bytes manipulation tools
- //
- // Platform: ISO C++ 98/11
- // $Id$
- //
- // (c) __vic 2011
- #ifndef __VIC_BITS_H
- #define __VIC_BITS_H
- #include<__vic/defs.h>
- #include<__vic/stdint.h>
- #include<climits>
- #if defined(_MSC_VER) && !defined(__VIC_NO_BUILTINS)
- #include<intrin.h>
- #endif
- #if __cpp_static_assert
- #define __VIC_ASSERT_UINT(T) \
- static_assert(T(-1) > 0, "Unsigned type is required")
- #else
- #define __VIC_ASSERT_UINT(T) \
- typedef char assert_argument_is_unsigned[T(-1) > 0 : 1 : -1]
- #endif
- namespace __vic {
- //----------------------------------------------------------------------------
- // Returns low-order nibble (or tetrad, or half-byte) of the byte
- __VIC_CONSTEXPR_FUNC uint8_t lo_nibble(uint8_t b)
- {
- return b & 0x0F;
- }
- //----------------------------------------------------------------------------
- // Returns high-order nibble (or tetrad, or half-byte) of the byte
- __VIC_CONSTEXPR_FUNC uint8_t hi_nibble(uint8_t b)
- {
- return b >> 4;
- }
- //------------------------------------------------------------------------------
- // Returns value with all most significant bits are 1 (others - 0)
- // Parameter specifies the number of "ones"
- template<class T>
- inline T msb_ones(unsigned bits_num)
- {
- return ~T(0) << (sizeof(T) * CHAR_BIT - bits_num);
- }
- //------------------------------------------------------------------------------
- // Returns value with all least significant bits are 1 (others - 0)
- // Parameter specifies the number of "ones"
- template<class T>
- inline T lsb_ones(unsigned bits_num)
- {
- return ~(~T(0) << bits_num);
- }
- //------------------------------------------------------------------------------
- // Clears all but bits_num least significant bits
- template<class T>
- inline T get_lsbs(T v, unsigned bits_num)
- {
- return v & lsb_ones<T>(bits_num);
- }
- //----------------------------------------------------------------------------
- // Returns char code 0..255
- __VIC_CONSTEXPR_FUNC int ord(char ch)
- {
- return static_cast<unsigned char>(ch);
- }
- //----------------------------------------------------------------------------
- // Swap high-order nibble with low-order one
- __VIC_CONSTEXPR_FUNC uint8_t swapped_nibbles(uint8_t b)
- {
- return (b << 4) | (b >> 4);
- }
- //----------------------------------------------------------------------------
- //----------------------------------------------------------------------------
- // Counts 1-bits
- template<class UInt>
- __VIC_CONSTEXPR14 unsigned popcount_uint(UInt v)
- {
- __VIC_ASSERT_UINT(UInt);
- unsigned c = 0;
- for(; v; v >>= 1) c += v & 1;
- return c;
- }
- //----------------------------------------------------------------------------
- inline unsigned popcount(unsigned v)
- {
- #if defined(__GNUC__) && !defined(__VIC_NO_BUILTINS)
- return __builtin_popcount(v);
- #elif defined(_MSC_VER) && !defined(__VIC_NO_BUILTINS)
- return __popcnt(v);
- #else
- return popcount_uint(v);
- #endif
- }
- //----------------------------------------------------------------------------
- inline unsigned popcount(unsigned long v)
- {
- #if defined(__GNUC__) && !defined(__VIC_NO_BUILTINS)
- return __builtin_popcountl(v);
- #else
- return popcount_uint(v);
- #endif
- }
- //----------------------------------------------------------------------------
- #ifdef __VIC_LONGLONG
- inline unsigned popcount(unsigned __VIC_LONGLONG v)
- {
- #if defined(__GNUC__) && !defined(__VIC_NO_BUILTINS)
- return __builtin_popcountll(v);
- #elif defined(_MSC_VER) && !defined(__VIC_NO_BUILTINS)
- return static_cast<unsigned>(__popcnt64(v));
- #else
- return popcount_uint(v);
- #endif
- }
- #endif
- //----------------------------------------------------------------------------
- inline unsigned popcount(unsigned short v)
- {
- #if defined(__GNUC__) && !defined(__VIC_NO_BUILTINS)
- return __builtin_popcount(v);
- #else
- return popcount_uint(v);
- #endif
- }
- //----------------------------------------------------------------------------
- inline unsigned popcount(unsigned char v)
- {
- #if defined(__GNUC__) && !defined(__VIC_NO_BUILTINS)
- return __builtin_popcount(v);
- #else
- return popcount_uint(v);
- #endif
- }
- //----------------------------------------------------------------------------
- //----------------------------------------------------------------------------
- // Returns position of the most significant 1-bit
- // Precondition: v != 0
- template<class UInt>
- inline unsigned msb_position_uint(UInt v)
- {
- __VIC_ASSERT_UINT(UInt);
- unsigned c = 0;
- while(v >>= 1) c++;
- return c;
- }
- //----------------------------------------------------------------------------
- inline unsigned msb_position(unsigned v)
- {
- #if defined(__GNUC__) && !defined(__VIC_NO_BUILTINS)
- return sizeof(v) * CHAR_BIT - __builtin_clz(v) - 1U;
- #else
- return msb_position_uint(v);
- #endif
- }
- //----------------------------------------------------------------------------
- inline unsigned msb_position(unsigned long v)
- {
- #if defined(__GNUC__) && !defined(__VIC_NO_BUILTINS)
- return sizeof(v) * CHAR_BIT - __builtin_clzl(v) - 1U;
- #else
- return msb_position_uint(v);
- #endif
- }
- //----------------------------------------------------------------------------
- #ifdef __VIC_LONGLONG
- inline unsigned msb_position(unsigned __VIC_LONGLONG v)
- {
- #if defined(__GNUC__) && !defined(__VIC_NO_BUILTINS)
- return sizeof(v) * CHAR_BIT - __builtin_clzll(v) - 1U;
- #else
- return msb_position_uint(v);
- #endif
- }
- #endif
- //----------------------------------------------------------------------------
- inline unsigned msb_position(unsigned short v)
- {
- #if defined(__GNUC__) && !defined(__VIC_NO_BUILTINS)
- return msb_position(static_cast<unsigned>(v));
- #else
- return msb_position_uint(v);
- #endif
- }
- //----------------------------------------------------------------------------
- inline unsigned msb_position(unsigned char v)
- {
- #if defined(__GNUC__) && !defined(__VIC_NO_BUILTINS)
- return msb_position(static_cast<unsigned>(v));
- #else
- return msb_position_uint(v);
- #endif
- }
- //----------------------------------------------------------------------------
- //----------------------------------------------------------------------------
- template<class UInt>
- inline UInt rotl_uint(UInt v, int shift)
- {
- const int w = sizeof(UInt) * CHAR_BIT; // width in bits
- //return (v << shift) | (v >> (w - shift)); // UB if shift == 0
- return (v << shift) | (v >> ((w - shift) & (w - 1)));
- }
- //----------------------------------------------------------------------------
- template<class UInt>
- inline UInt rotr_uint(UInt v, int shift)
- {
- const int w = sizeof(UInt) * CHAR_BIT; // width in bits
- //return (v >> shift) | (v << (w - shift)); // UB if shift == 0
- return (v >> shift) | (v << ((w - shift) & (w - 1)));
- }
- //----------------------------------------------------------------------------
- inline unsigned rotl(unsigned v, int sh) { return rotl_uint(v, sh); }
- inline unsigned long rotl(unsigned long v, int sh) { return rotl_uint(v, sh); }
- inline unsigned short rotl(unsigned short v, int sh) { return rotl_uint(v, sh); }
- inline unsigned char rotl(unsigned char v, int sh) { return rotl_uint(v, sh); }
- //----------------------------------------------------------------------------
- inline unsigned rotr(unsigned v, int sh) { return rotr_uint(v, sh); }
- inline unsigned long rotr(unsigned long v, int sh) { return rotr_uint(v, sh); }
- inline unsigned short rotr(unsigned short v, int sh) { return rotr_uint(v, sh); }
- inline unsigned char rotr(unsigned char v, int sh) { return rotr_uint(v, sh); }
- //----------------------------------------------------------------------------
- #ifdef __VIC_LONGLONG
- inline unsigned __VIC_LONGLONG rotl(unsigned __VIC_LONGLONG v, int sh)
- {
- return rotl_uint(v, sh);
- }
- inline unsigned __VIC_LONGLONG rotr(unsigned __VIC_LONGLONG v, int sh)
- {
- return rotr_uint(v, sh);
- }
- #endif
- //----------------------------------------------------------------------------
- //----------------------------------------------------------------------------
- template<class UInt>
- inline bool ispow2(UInt n)
- {
- __VIC_ASSERT_UINT(UInt);
- return popcount(n) == 1;
- }
- //----------------------------------------------------------------------------
- template<class UInt>
- inline unsigned ceil_log2(UInt n)
- {
- __VIC_ASSERT_UINT(UInt);
- return n >> 1 ? msb_position(UInt(n - 1)) + 1 : 0;
- }
- //----------------------------------------------------------------------------
- template<class UInt>
- inline unsigned floor_log2(UInt n)
- {
- __VIC_ASSERT_UINT(UInt);
- return n ? msb_position(n) : 0;
- }
- //----------------------------------------------------------------------------
- // Returns the number x: ispow2(x) && x >= n
- template<class UInt>
- inline UInt ceil2(UInt n)
- {
- __VIC_ASSERT_UINT(UInt);
- if(n == 0 || n == 1) return 1;
- return UInt(1) << (msb_position(UInt(n - 1)) + 1);
- }
- //----------------------------------------------------------------------------
- // If n != 0 returns the number x: ispow2(x) && x <= n
- // Otherwise 0 is returned
- template<class UInt>
- inline UInt floor2(UInt n)
- {
- __VIC_ASSERT_UINT(UInt);
- return n ? UInt(1) << msb_position(n) : 0;
- }
- //----------------------------------------------------------------------------
- #undef __VIC_ASSERT_UINT
- } // namespace
- #endif // header guard
|