如何实现 SWAR 无符号小于？

Question

我试图使用s 的uint64_t8 个车道uint8_t；我的目标是实现逐车道小于。如果相应车道 in的值小于该车道 in 的值，则此操作，给定x和y，应0xFF在车道内产生结果，否则。逐车道小于或等于也可以。xy0x00

根据我所看到的，我猜我需要一个车道差异或零操作（定义为doz(x, y) = if (x < y) then 0 else (x - y)），然后使用它来构建一个选择掩码。但是，我见过的所有车道减法方法都是有符号的，我不确定如何使用它们来完成此类任务。

有没有办法做到这一点，使用差异或零或其他方式？

Answer 1

事实证明，基于 DOZ 是错误的做法。所有这些都是没有意义的，不要使用它。

然而，我见过的所有车道减法方法都是有符号的

这是令人惊讶的，因为减法既没有符号也没有无符号，所以只有一个减法并且可以两种方式解释。至少，这就是它在 2 的补码世界中的工作方式。

作为参考，SWAR 减法如下所示：（来源：SIMD 和 SWAR 技术）

SWAR sub z = x - y
    z = ((x | H) - (y &~H)) ^ ((x ^~y) & H)

DOZ 可以以此为基础。一个完整的DOZ 是矫枉过正，如果它是一个原始的有意义的。但是 SWAR DOZ 会通过计算差异来工作，然后将其归零 if x < y，这是我们一直想要的条件。所以让我们只计算它而不是整个 DOZ。该条件基于此：何时从高位借用？

1. 如果 x 的高位为零，y 的高位为 1。
2. 如果x和y的高位相同，差的高位为1。等效地：如果x和y的高位相同，并且第二高位有借位。

SWAR sub的第一部分， ((x | H) - (y &~H))计算（除其他外）第二高位的借位。SWAR 差异的高位是第二高位的借位的倒数（来自 H 的位要么被借位“吃掉”，要么不被借位）。

把它放在一起，SWAR unsigned-less-than 可以像这样工作：

tmp = ((~x ^ y) & ~((x | H) - (y &~H)) | (~x & y)) & H
less_than_mask = (tmp << 1) - (tmp >> 7)

部分：

• (~x ^ y) =“位相同”的掩码，用于“高位相同”
• ~((x | H) - (y &~H)) = 元素低位的差异，用于“借出第二高位”
• (~x & y) =“x 为零，y 为一”的掩码，用于“x 的高位为零，y 的高位为一”
• & H 接近尾声，用于只从高位中取出与借位对应的位
• (tmp << 1) - (tmp >> 7)将上一步抓取的位展开到通道掩码中。替代方案：(tmp >> 7) * 255。这是 SWAR 逻辑明确依赖于通道大小的唯一步骤，并且每个通道都需要相同，即使对于 SWAR sub，您可以混合通道大小。

通过应用 De Morgan 规则，可以在表达式级别删除一个操作：

tmp = (~(x ^ y | (x | H) - (y & ~H)) | ~x & y) & H

但是~x无论如何都需要计算，因此在程序集级别可能无济于事，具体取决于它的编译方式。

也许可以进行一些简化。

Answer 2

哪种方法最快将取决于目标平台的处理器架构中可用的指令类型，例如移位加、加、三输入加、三输入逻辑指令。它还取决于是否需要吞吐量或延迟优化版本，以及处理器架构的超标量。

以下 ISO C 99 代码提供了两种替代方案。一个使用直接取自文献 ( LTU_VARIANT = 1)的无符号字节方式比较，另一个 ( LTU_VARIANT = 0) 我自己设计的基于减半加法（即两个整数之和除以二，向下取整）。这是基于以下事实：对于 [0,255] 中的整数 a、b，a < ^u b ? ~a + b >= 256.

但是，这将需要 9 位的总和，因此我们可以使用 a < ^u b ? ((~a + b) >> 1) >= 128相反，可以通过众所周知的位旋转技术在 8 位内计算平均值。我所知道的唯一提供 SIMD 减半作为硬件指令的处理器架构vhadd是Arm NEON。

我已经包含了一个用于功能测试的测试框架，但是需要进行基准测试来确定哪个版本在给定平台上表现更好。

此答案可能与其他答案部分重叠；金橘的剥皮方法有很多种。

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

#define LTU_VARIANT (1)                    // 0 or 1 
#define UINT64_H8   (0x8080808080808080U)  // byte-wise sign bits (MSBs)

uint64_t sign_to_mask8 (uint64_t a)
{
    a = a & UINT64_H8;    // isolate sign bits
    a = a + a - (a >> 7); // extend them to full byte to create mask
    return a;
}

uint64_t vhaddu8 (uint64_t a, uint64_t b)
{
    /* Peter L. Montgomery's observation (newsgroup comp.arch, 2000/02/11,
       https://groups.google.com/d/msg/comp.arch/gXFuGZtZKag/_5yrz2zDbe4J):
       (A+B)/2 = (A AND B) + (A XOR B)/2.
    */
    return (a & b) + (((a ^ b) >> 1) & ~UINT64_H8);
}

uint64_t ltu8_core (uint64_t a, uint64_t b)
{
    /* Sebastiano Vigna, "Broadword implementation of rank/select queries." 
       In: International Workshop on Experimental and Efficient Algorithms, 
       pp. 154-168, Springer Berlin Heidelberg, 2008.
    */
    return (((a | UINT64_H8) - (b & ~UINT64_H8)) | (a ^ b)) ^ (a | ~b);
}

uint64_t vcmpltu8 (uint64_t a, uint64_t b)
{
#if LTU_VARIANT==1
    return sign_to_mask8 (ltu8_core (a, b));
#else // LTU_VARIANT
    return sign_to_mask8 (vhaddu8 (~a, b));
#endif // LTU_VARIANT
}

uint64_t ref_func (uint64_t a, uint64_t b)
{
    uint8_t a0 = (uint8_t)((a >>  0) & 0xff);
    uint8_t a1 = (uint8_t)((a >>  8) & 0xff);
    uint8_t a2 = (uint8_t)((a >> 16) & 0xff);
    uint8_t a3 = (uint8_t)((a >> 24) & 0xff);
    uint8_t a4 = (uint8_t)((a >> 32) & 0xff);
    uint8_t a5 = (uint8_t)((a >> 40) & 0xff);
    uint8_t a6 = (uint8_t)((a >> 48) & 0xff);
    uint8_t a7 = (uint8_t)((a >> 56) & 0xff);
    uint8_t b0 = (uint8_t)((b >>  0) & 0xff);
    uint8_t b1 = (uint8_t)((b >>  8) & 0xff);
    uint8_t b2 = (uint8_t)((b >> 16) & 0xff);
    uint8_t b3 = (uint8_t)((b >> 24) & 0xff);
    uint8_t b4 = (uint8_t)((b >> 32) & 0xff);
    uint8_t b5 = (uint8_t)((b >> 40) & 0xff);
    uint8_t b6 = (uint8_t)((b >> 48) & 0xff);
    uint8_t b7 = (uint8_t)((b >> 56) & 0xff);
    uint8_t r0 = (a0 < b0) ? 0xff : 0x00;
    uint8_t r1 = (a1 < b1) ? 0xff : 0x00;
    uint8_t r2 = (a2 < b2) ? 0xff : 0x00;
    uint8_t r3 = (a3 < b3) ? 0xff : 0x00;
    uint8_t r4 = (a4 < b4) ? 0xff : 0x00;
    uint8_t r5 = (a5 < b5) ? 0xff : 0x00;
    uint8_t r6 = (a6 < b6) ? 0xff : 0x00;
    uint8_t r7 = (a7 < b7) ? 0xff : 0x00;

    return ( ((uint64_t)r0 <<  0) +
             ((uint64_t)r1 <<  8) +
             ((uint64_t)r2 << 16) +
             ((uint64_t)r3 << 24) +
             ((uint64_t)r4 << 32) +
             ((uint64_t)r5 << 40) +
             ((uint64_t)r6 << 48) +
             ((uint64_t)r7 << 56) );
}

/*
  https://groups.google.com/forum/#!original/comp.lang.c/qFv18ql_WlU/IK8KGZZFJx4J
  From: geo <gmars...@gmail.com>
  Newsgroups: sci.math,comp.lang.c,comp.lang.fortran
  Subject: 64-bit KISS RNGs
  Date: Sat, 28 Feb 2009 04:30:48 -0800 (PST)

  This 64-bit KISS RNG has three components, each nearly
  good enough to serve alone.    The components are:
  Multiply-With-Carry (MWC), period (2^121+2^63-1)
  Xorshift (XSH), period 2^64-1
  Congruential (CNG), period 2^64
*/
static uint64_t kiss64_x = 1234567890987654321ULL;
static uint64_t kiss64_c = 123456123456123456ULL;
static uint64_t kiss64_y = 362436362436362436ULL;
static uint64_t kiss64_z = 1066149217761810ULL;
static uint64_t kiss64_t;
#define MWC64  (kiss64_t = (kiss64_x << 58) + kiss64_c, \
                kiss64_c = (kiss64_x >> 6), kiss64_x += kiss64_t, \
                kiss64_c += (kiss64_x < kiss64_t), kiss64_x)
#define XSH64  (kiss64_y ^= (kiss64_y << 13), kiss64_y ^= (kiss64_y >> 17), \
                kiss64_y ^= (kiss64_y << 43))
#define CNG64  (kiss64_z = 6906969069ULL * kiss64_z + 1234567ULL)
#define KISS64 (MWC64 + XSH64 + CNG64)

int main (void) 
{
    uint64_t a, b, res, ref, n = 0;

    printf ("Testing vcmpltu8: byte-wise unsigned comparison with mask result\n");
    printf ("using LTU variant %d\n", LTU_VARIANT);
    do {
        a = KISS64;
        b = KISS64;
        res = vcmpltu8 (a, b);
        ref = ref_func (a, b);
        if (res != ref) {
            printf ("\nerr @ a=%016" PRIx64 "  b=%016" PRIx64 " : res=%016" PRIx64 "  ref=%016" PRIx64 "\n",
                    a, b, res, ref);
            return EXIT_FAILURE;
        }
        n++;
        if (!(n & 0xffffff)) printf ("\r%016" PRIx64, n);
    } while (a);
    printf ("\ntest passed\n");
    return EXIT_SUCCESS;
}

Answer 3

这是一种独立于体系结构的方法。我确信它可以使用细化，但它似乎工作得很好。使用 x86 gcc/clang，它可以编译为 20/19 条指令。

这个想法是首先解决两个字节都小于 128 或不小于 128 时的问题，并用该结果在每个字节中设置位 7。然后修补其他案例。最后将第7位向下涂抹。

#include <stdio.h>
#include <stdint.h>

uint64_t bwlt(uint64_t a, uint64_t b) {
  uint64_t lo7 = ~0ull / 255 * 127,        // low 7 bits set in each byte
           alo7 = a & lo7,                 // mask low 7 bits in a
           blo7 = b & lo7,                 // mask low 7 bits in b
           r = (lo7 - alo7 + blo7) & ~lo7, // set 8th bits with a < b
           diff = (a ^ b) & ~lo7;          // 8th bits that differ
  r &= ~(a & diff);                        // unset if a[i]_7=1,b[i]_7=0
  r |= b & diff;                           // set if a[i]_7=0,b[i]_7=1
  return (r << 1) - (r >> 7);
}

int main(void) {
  uint64_t a = 0x11E1634052A6B7CB;
  uint64_t b = 0x1EAEF1E85F26734E;
  printf("r=%016llx\n", bwlt(a, b));
  return 0;
}

一个测试用例：

$ gcc foo.c -o foo
$ ./foo
r=ff00ffffff000000