Fast counting the number of set bits in __m128i register

by

Here are some codes I used in an old project (there is a research paper about it). The function popcnt8 below computes the number of bits set in each byte.

SSE2-only version (based on Algorithm 3 in Hacker’s Delight book):

static const __m128i popcount_mask1 = _mm_set1_epi8(0x77);
static const __m128i popcount_mask2 = _mm_set1_epi8(0x0F);
static inline __m128i popcnt8(__m128i x) {
    __m128i n;
    // Count bits in each 4-bit field.
    n = _mm_srli_epi64(x, 1);
    n = _mm_and_si128(popcount_mask1, n);
    x = _mm_sub_epi8(x, n);
    n = _mm_srli_epi64(n, 1);
    n = _mm_and_si128(popcount_mask1, n);
    x = _mm_sub_epi8(x, n);
    n = _mm_srli_epi64(n, 1);
    n = _mm_and_si128(popcount_mask1, n);
    x = _mm_sub_epi8(x, n);
    x = _mm_add_epi8(x, _mm_srli_epi16(x, 4));
    x = _mm_and_si128(popcount_mask2, x);
    return x;
}

SSSE3 version (due to Wojciech Mula):

static const __m128i popcount_mask = _mm_set1_epi8(0x0F);
static const __m128i popcount_table = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
static inline __m128i popcnt8(__m128i n) {
    const __m128i pcnt0 = _mm_shuffle_epi8(popcount_table, _mm_and_si128(n, popcount_mask));
    const __m128i pcnt1 = _mm_shuffle_epi8(popcount_table, _mm_and_si128(_mm_srli_epi16(n, 4), popcount_mask));
    return _mm_add_epi8(pcnt0, pcnt1);
}

XOP version (equivalent to SSSE3, but uses XOP instructions which are faster on AMD Bulldozer)

static const __m128i popcount_mask = _mm_set1_epi8(0x0F);
static const __m128i popcount_table = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
static const __m128i popcount_shift = _mm_set1_epi8(-4);
static inline __m128i popcount8(__m128i n) {
    const __m128i pcnt0 = _mm_perm_epi8(popcount_table, popcount_table, _mm_and_si128(n, popcount_mask));
    const __m128i pcnt1 = _mm_perm_epi8(popcount_table, popcount_table, _mm_shl_epi8(n, popcount_shift));
    return _mm_add_epi8(pcnt0, pcnt1);
}

Function popcnt64 below counts the number of bits in the low and high 64-bit parts of the SSE register:

SSE2 version:

static inline __m128i popcnt64(__m128i n) {
    const __m128i cnt8 = popcnt8(n);
    return _mm_sad_epu8(cnt8, _mm_setzero_si128());
}

XOP version:

static inline __m128i popcnt64(__m128i n) {
    const __m128i cnt8 = popcnt8(n);
    return _mm_haddq_epi8(cnt8);
}

Finally, the function popcnt128 below count the number of bits in the whole 128-bit register:

static inline int popcnt128(__m128i n) {
    const __m128i cnt64 = popcnt64(n);
    const __m128i cnt64_hi = _mm_unpackhi_epi64(cnt64, cnt64);
    const __m128i cnt128 = _mm_add_epi32(cnt64, cnt64_hi);
    return _mm_cvtsi128_si32(cnt128);
}

However, a more efficient way to implement popcnt128 is to use hardware POPCNT instruction (on processors which support it):

static inline int popcnt128(__m128i n) {
    const __m128i n_hi = _mm_unpackhi_epi64(n, n);
    #ifdef _MSC_VER
        return __popcnt64(_mm_cvtsi128_si64(n)) + __popcnt64(_mm_cvtsi128_si64(n_hi));
    #else
        return __popcntq(_mm_cvtsi128_si64(n)) + __popcntq(_mm_cvtsi128_si64(n_hi));
    #endif
}

More Related Contents:

  1. What’s the difference between logical SSE intrinsics?
  2. print a __m128i variable
  3. Fastest Implementation of the Natural Exponential Function Using SSE
  4. Do I get a performance penalty when mixing SSE integer/float SIMD instructions
  5. How to determine if memory is aligned?
  6. Getting started with Intel x86 SSE SIMD instructions
  7. Compare 16 byte strings with SSE
  8. inlining failed in call to always_inline ‘_mm_mullo_epi32’: target specific option mismatch
  9. Intel SSE: Why does `_mm_extract_ps` return `int` instead of `float`?
  10. Why does mulss take only 3 cycles on Haswell, different from Agner’s instruction tables? (Unrolling FP loops with multiple accumulators)
  11. AVX2 what is the most efficient way to pack left based on a mask?
  12. How to solve the 32-byte-alignment issue for AVX load/store operations?
  13. How to efficiently perform double/int64 conversions with SSE/AVX?
  14. How to count character occurrences using SIMD
  15. SIMD signed with unsigned multiplication for 64-bit * 64-bit to 128-bit
  16. SIMD prefix sum on Intel cpu
  17. Why vectorizing the loop does not have performance improvement
  18. What’s missing/sub-optimal in this memcpy implementation?
  19. Loading 8 chars from memory into an __m256 variable as packed single precision floats
  20. Simd matmul program gives different numerical results
  21. Getting max value in a __m128i vector with SSE?
  22. Emulating shifts on 32 bytes with AVX
  23. C++ error: ‘_mm_sin_ps’ was not declared in this scope
  24. Count each bit-position separately over many 64-bit bitmasks, with AVX but not AVX2
  25. Get member of __m128 by index?
  26. SSE reduction of float vector
  27. Most efficient way to check if all __m128i components are 0 [using
  28. How to convert 32-bit float to 8-bit signed char? (4:1 packing of int32 to int8 __m256i)
  29. Where can I find an official reference listing the operation of SSE intrinsic functions?
  30. Efficient 4×4 matrix multiplication (C vs assembly)

Leave a Comment