quickcpplib::_xxx::algorithm::bit_interleave Namespace Reference

Namespaces
namespace	detail

Classes
struct	bit_deinterleave_result

Functions
template<class T , class R = typename detail::next_larger<T>::type, typename std::enable_if<(std::is_unsigned< T >::value), bool >::type = true>
R	bit_interleave (T a, T b) noexcept
	Interleaves the bits of a and b.
template<class T , class R = typename detail::next_smaller<T>::type, typename std::enable_if<(std::is_unsigned< T >::value), bool >::type = true>
bit_deinterleave_result< R >	bit_deinterleave (T x) noexcept
	Deinterleaves the bits in X into evens and odds.

Function Documentation

bit_interleave()

template<class T , class R = typename detail::next_larger<T>::type, typename std::enable_if<(std::is_unsigned< T >::value), bool >::type = true>

R quickcpplib::_xxx::algorithm::bit_interleave::bit_interleave ( T  a, T  b  )

inlinenoexcept

Interleaves the bits of a and b.

On my Intel i7-8565u laptop able to boost to 4.6Ghz:

Straight C edition on MSVC: 4.8052e+08 32-bit to 64-bit interleaves/sec which is 2.08108ns/interleave (9.57 cycles) Straight C edition on GCC: 3.39213e+08 32-bit to 64-bit interleaves/sec which is 2.948ns/interleave (13.56 cycles)

    {
#if 0  // defined(__AVX__) || defined(__SSE4_1__) || defined(__SSSE3__)
      /* https://lemire.me/blog/2018/01/09/how-fast-can-you-bit-interleave-32-bit-integers-simd-edition/
      says that AVX is considerably faster than the SSSE3 bit interleave if you need to interleave two 128
      bit values into a 256 bit value, but we don't support that here yet.
 
      PDEP has a 19 cycle latency on most AMD CPUs, the C fallback is considerably quicker.
      */
#else
      // Standard C fallback which processes both halves in parallel to leverage superscalar execution
      R ret1 = R(a), ret2 = R(b);
      constexpr R mask16 = R(0x0000ffff0000ffff), mask8 = R(0x00ff00ff00ff00ff) /* 0000 0000 1111 1111 */,
                  mask4 = R(0x0f0f0f0f0f0f0f0f) /* 0000 1111 */, mask2 = R(0x3333333333333333) /* 0011 0011 */,
                  mask1 = R(0x5555555555555555) /* 0101 0101 */;
      if(sizeof(T) >= 4)
      {
        ret1 = (ret1 ^ (ret1 << 16)) & mask16;
        ret2 = (ret2 ^ (ret2 << 16)) & mask16;
      }
      if(sizeof(T) >= 2)
      {
        ret1 = (ret1 ^ (ret1 << 8)) & mask8;
        ret2 = (ret2 ^ (ret2 << 8)) & mask8;
      }
      ret1 = (ret1 ^ (ret1 << 4)) & mask4;
      ret2 = (ret2 ^ (ret2 << 4)) & mask4;
      ret1 = (ret1 ^ (ret1 << 2)) & mask2;
      ret2 = (ret2 ^ (ret2 << 2)) & mask2;
      ret1 = (ret1 ^ (ret1 << 1)) & mask1;
      ret2 = (ret2 ^ (ret2 << 1)) & mask1;
      return ret1 | (ret2 << 1);
#endif
    }

bit_deinterleave()

template<class T , class R = typename detail::next_smaller<T>::type, typename std::enable_if<(std::is_unsigned< T >::value), bool >::type = true>

bit_deinterleave_result< R > quickcpplib::_xxx::algorithm::bit_interleave::bit_deinterleave ( T  x )

inlinenoexcept

Deinterleaves the bits in X into evens and odds.

    {
      constexpr T /* mask32 = T(0x00000000ffffffff), */ mask16 = T(0x0000ffff0000ffff),
                                                        mask8 = T(0x00ff00ff00ff00ff) /* 0000 0000 1111 1111 */,
                                                        mask4 = T(0x0f0f0f0f0f0f0f0f) /* 0000 1111 */,
                                                        mask2 = T(0x3333333333333333) /* 0011 0011 */,
                                                        mask1 = T(0x5555555555555555) /* 0101 0101 */;
      T ret1 = x & mask1, ret2 = (x >> 1) & mask1;
      ret1 = (ret1 ^ (ret1 >> 1)) & mask2;
      ret2 = (ret2 ^ (ret2 >> 1)) & mask2;
      ret1 = (ret1 ^ (ret1 >> 2)) & mask4;
      ret2 = (ret2 ^ (ret2 >> 2)) & mask4;
      if(sizeof(T) >= 2)
      {
        ret1 = (ret1 ^ (ret1 >> 4)) & mask8;
        ret2 = (ret2 ^ (ret2 >> 4)) & mask8;
      }
      if(sizeof(T) >= 4)
      {
        ret1 = (ret1 ^ (ret1 >> 8)) & mask16;
        ret2 = (ret2 ^ (ret2 >> 8)) & mask16;
      }
      if(sizeof(T) >= 8)
      {
        ret1 = (ret1 ^ (ret1 >> 16)) /*& mask32*/;
        ret2 = (ret2 ^ (ret2 >> 16)) /*& mask32*/;
      }
      return bit_deinterleave_result<R>{R(ret1), R(ret2)};
    }