SIMD-within-a-register version of min/max

Question

Suppose I have two uint16_t[4] arrays, a and b. Each integer in these arrays is in the range [0, 16383], so bits 14 and 15 aren't set. Then I have some code to find the minimum and maximum among a[i] and b[i] for each i:

uint16_t min[4], max[4];
for (int i = 0; i < 4; i++) {
    if (a[i] < b[i]) {
        min[i] = a[i];
        max[i] = b[i];
    } else {
        min[i] = b[i];
        max[i] = a[i];
    }
}

Suppose for some reason I can't/won't use SIMD, but I'd still like to compute this as fast as possible, on a 64-bit platform. Thus, a natural solution is to use the SIMD-within-a-register (SWAR) paradigm on 64-bit registers to compute these 4 values in a single iteration, rather than over 4 iterations with 16-bit arithmetic.

What bit-twiddling hacks could be used to implement either (min or max) or ideally both operations using the SWAR paradigm, so that the resulting code is faster than the loop above? My target architecture is ARMv8, so feel free to use any ARMv8 instructions that help reducing instruction counts.

C, assembly, or C + inline assembly solutions are all welcome.

Answer 1

You could use code like this, though it's really a lot longer than just doing it with SIMD:

orr     x2, x0, #0x8000800080008000     // x2 = 0x8000 | x0
sub     x2, x2, x1                      // x2 = (0x8000 | x0) - x1
and     x2, x2, #0x8000800080008000      // x2 = x0 < x1 ? 0x0000 : 0x8000
mov     x3, #0x7fff7fff7fff7fff
add     x2, x3, x2, lsr #15             // x2 = x0 < x1 ? 0x7fff : 0x8000
eor     x4, x0, x1                      // x4 = x0 ^ x1
and     x3, x4, x2                      // x3 = x0 < x1 ? x0 ^ x1 : 0x0000
eor     x4, x1, x3                      // x4 = x0 < x1 ? x0 : x1
eor     x3, x0, x3                      // x3 = x0 < x1 ? x1 : x0

The critical path of this algorithm has 6 instructions. The instructions

mov     x3, #0x7fff7fff7fff7fff
eor     x4, x0, x1                      // x4 = x0 ^ x1

are not on the critical path. If executed in a loop, the constant load can likely be hoisted out. The last two instructions can be evaluated independently, yielding minimum and maximum with the same latency.