Compare two __m128i values for total order

Question

I need a way to compare values of type __m128i in C++ for a total order between any values of type __m128i. The type of order doesn't matter as long as it establishes a total order between all values of type __m128i. Hence the comparison might be less-than between 128-bit integers or something else entirely as long as is provides a total order.

I tried using the < operator, but that didn't return a bool, but instead seems to compare the vector components of __m128i (i.e. SIMD):

#include <emmintrin.h>

inline bool isLessThan(__m128i a, __m128i b) noexcept {
     // error: cannot convert '__vector(2) long int' to 'bool' in return
     return a < b;
}

Another possibility would be to use memcmp/strcmp or similar, but this would very likely not be optimal. Targeting modern Intel x86-64 CPUs with at least SSE4.2 and AVX2, are there any intrinsics / instructions I could use for such comparisons? How to do it?

PS: Similar questions have been asked for checking equality but not for ordering:

• How to compare __m128 types?
• Testing equality between two __m128i variables

Answer 1

Here you go.

inline bool isLessThan( __m128i a, __m128i b )
{
    /* Compare 8-bit lanes for ( a < b ), store the bits in the low 16 bits of the
       scalar value: */
    const int less = _mm_movemask_epi8( _mm_cmplt_epi8( a, b ) );

    /* Compare 8-bit lanes for ( a > b ), store the bits in the low 16 bits of the
       scalar value: */
    const int greater = _mm_movemask_epi8( _mm_cmpgt_epi8( a, b ) );

    /* It's counter-intuitive, but this scalar comparison does the right thing.
       Essentially, integer comparison searches for the most significant bit that
       differs... */
    return less > greater;
}

The order is less than ideal ’coz pcmpgtb treats these bytes as signed integers, but you said it’s not important for your use case.

---

Update: here’s a slightly slower version with uint128_t sort order.

// True if a < b, for unsigned 128 bit integers
inline bool cmplt_u128( __m128i a, __m128i b )
{
    // Flip the sign bits in both arguments.
    // Transforms 0 into -128 = minimum for signed bytes,
    // 0xFF into +127 = maximum for signed bytes
    const __m128i signBits = _mm_set1_epi8( (char)0x80 );
    a = _mm_xor_si128( a, signBits );
    b = _mm_xor_si128( b, signBits );

    // Now the signed byte comparisons will give the correct order
    const int less = _mm_movemask_epi8( _mm_cmplt_epi8( a, b ) );
    const int greater = _mm_movemask_epi8( _mm_cmpgt_epi8( a, b ) );
    return less > greater;
}

We build unsigned compares out of signed by range-shifting the unsigned inputs to signed (by flipping the high bit = subtract 128).