使用SSE计算无符号整数之间的绝对差异

Question

在C语言中，是否有一种无分支技术可以计算两个无符号整数之间的绝对差值？例如：给定变量a和b，当a=3，b=5或b=3，a=5时，我希望得到值2。最好还能使用SSE寄存器向量化计算。

- Jack Nock

Answer 1

有几种方法可以做到这一点，我只介绍其中一种：

SSE4

使用 PMINUD 和 PMAXUD 将寄存器#1中的较大值和寄存器#2中的较小值分开。

将它们相减即可。

MMX/SSE2

翻转两个值的符号位，因为下一个指令只接受有符号整数比较。

使用 PCMPGTD。将此结果用作掩码。

计算 (a-b) 和 (b-a) 的结果。

使用 POR (PAND (mask, a-b)，PANDN (mask, b-a)) 选择绝对差异的正确值。

- rwong

Answer 2

从tommesani.com得知，解决这个问题的一种方法是使用饱和无符号减法两次。

由于饱和减法永远不会低于0，因此可以计算： r1 = (a-b).saturating r2 = (b-a).saturating

如果a大于b，则r1将包含答案，r2将为0；反之亦然。 将两个部分结果进行OR运算即可得到所需结果。

根据VTUNE用户手册，PSUBUSB/PSUBUSW适用于128位寄存器，因此您应该能够通过这种方式获得大量并行性。

- Justin W

---

似乎只有无符号饱和子程序适用于字或字节，但幸运的是这正是我要找的。这个答案比使用SSE4.1 PMINU/PMAXU/PSUB得到的得票最高的答案略微好一些，因为在某些CPU上（例如Intel Haswell），POR可以在更多的端口上运行而不是PSUB。 - Peter Cordes

Answer 3

max(i,j) - min(i,j)
(i>j)*(i-j) + (j>i)*(j-i)

您可以使用SSE寄存器，但编译器可能会自动为您完成此操作。

- Anycorn

Answer 4

SSE2：

看起来与Phernost的第二个函数速度差不多。有时候GCC会安排它比Phernost的函数快一个周期，有时候会慢一点。

__m128i big = _mm_set_epi32( INT_MIN, INT_MIN, INT_MIN, INT_MIN );

a = _mm_add_epi32( a, big ); // re-center the variables: send 0 to INT_MIN,
b = _mm_add_epi32( b, big ); // INT_MAX to -1, etc.
__m128i diff = _mm_sub_epi32( a, b ); // get signed difference
__m128i mask = _mm_cmpgt_epi32( b, a ); // mask: need to negate difference?
mask = _mm_andnot_si128( big, mask ); // mask = 0x7ffff... if negating
diff = _mm_xor_si128( diff, mask ); // 1's complement except MSB
diff = _mm_sub_epi32( diff, mask ); // add 1 and restore MSB

SSSE3：

比之前的版本稍微快一点。取决于循环外部声明的内容有很多变化。（例如，将a和b声明为volatile可以使速度更快！这似乎是调度的随机效应。）但这始终比其他方式快一个周期左右。

__m128i big = _mm_set_epi32( INT_MIN, INT_MIN, INT_MIN, INT_MIN );

a = _mm_add_epi32( a, big ); // re-center the variables: send 0 to INT_MIN,
b = _mm_add_epi32( b, big ); // INT_MAX to -1, etc.
__m128i diff = _mm_sub_epi32( b, a ); // get reverse signed difference
__m128i mask = _mm_cmpgt_epi32( b, a ); // mask: need to negate difference?
mask = _mm_xor_si128( mask, big ); // mask cannot be 0 for PSIGND insn
diff = _mm_sign_epi32( diff, mask ); // negate diff if needed

SSE4（感谢rwong）：

无法进行测试。

__m128i diff = _mm_sub_epi32( _mm_max_epu32( a, b ), _mm_min_epu32( a, b ) );

- Potatoswatter

Answer 5

计算差异并返回绝对值

__m128i diff = _mm_sub_epi32(a, b);  
__m128i mask = _mm_xor_si128(diff, a);
mask = _mm_xor_si128(mask, b);
mask = _mm_srai_epi32(mask, 31);
diff = _mm_xor_si128(diff, mask);  
mask = _mm_srli_epi32(mask, 31);  
diff = _mm_add_epi32(diff, mask);  

这比使用有符号比较操作少了一个操作，并且产生更少的寄存器压力。

与之前相同的寄存器压力，多了2个操作，更好的分支和依赖链合并，指令对uops解码进行配对，以及单独的单元利用率。虽然这需要一个加载，但可能超出缓存。在此之后，我已经没有更多想法了。

__m128i mask, diff;
diff = _mm_set1_epi32(-1<<31); // dependency branch after
a = _mm_add_epi32(a, diff); // arithmetic sign flip
b = _mm_xor_si128(b, diff); // bitwise sign flip parallel with 'add' unit
diff = _mm_xor_si128(a, b); // reduce uops, instruction already decoded
mask = _mm_cmpgt_epi32(b, a); // parallel with xor
mask = _mm_and_si128(mask, diff); // dependency merge, branch after
a = _mm_xor_si128(a, mask); // if 2 'bit' units in CPU, parallel with next
b = _mm_xor_si128(b, mask); // reduce uops, instruction already decoded
diff = _mm_sub_epi32(a, b); // result

在Core2Duo上进行200万次迭代后，每个版本的时间差都无法测量。因此，请选择您更容易理解的版本。

- Phernost

---

“sum” 应该是 “diff” 吗？唉，现在我仔细阅读了你的代码，发现它与我的非常相似。但更聪明，很好地使用了有符号差异作为有符号比较。与零进行比较通常比右移更轻量级。 - Potatoswatter

实际上，我们都犯了一个错误：在第一个函数中，需要一个三输入共识函数，而不是三路异或。 - Potatoswatter

Answer 6

以下一个或多个条件可能会导致无分支代码，具体取决于计算机和编译器，因为条件表达式都非常简单。

我还没有阅读所有sse答案，但可能有些向量代码中包含以下内容；确实所有以下内容都可向量化（如果您首先进行无符号比较，或者通过首先切换msb进行伪造）。我认为提供一些实用的标量解答对这个问题会很有帮助。

unsigned udiff( unsigned a, unsigned b )
{
      unsigned result = a-b;   // ok if a<b;
      if(a <b ) result = -result; 
      return result;
}
unsigned udiff( unsigned a, unsigned b )
{
      unsigned n =(a<b)? (unsigned)-1 : 0u;
      unsigned result = a-b;
      return (result^n)-n; // 'result' if n = 0; '-result' if n = 0xFFFFFFFF
}


unsigned udiff( unsigned a, unsigned b )
{
      unsigned axb = a^b;
      if( a < b )  axb = 0;
      return (axb^b) - (axb^a);  // a-b, or b-a
}

这将适用于x86_64（或任何64位临时文件基本上是免费的）

unsigned udiff( unsigned a, unsigned b )
{
      unsigned n= (unsigned)( 
         (long long)((unsigned long long)a - (unsigned long long)b)>>32 
                      ); // same n as 2nd example
      unsigned result = a-b;
      return (result^n)-n; // 'result' if n = 0; '-result' if n = 0xFFFFFFFF
}

- greggo

Answer 7

尝试这个（假设第二补码，根据您要求SSE是可以的）：

int d = a-b;
int ad = ((d >> 30) | 1) * d;

解释：符号位（第31位）向下传播到第1位。 | 1 部分确保乘数为1或-1。在现代CPU上，乘法运算速度很快。

- zvrba

---

但是 a-b 的符号位并不表示 a < b。考虑 a=0xF0000000 和 b=1。如果是这样的话，你可以使用 abs(a-b)。 - greggo

Answer 8

嗯...这很容易...

int diff = abs( a - b );

易于向量化（使用SSE3）：

__m128i sseDiff = _mm_abs_epi32( _mm_sub_epi32( a, b ) );

a和b都是无符号整数。考虑a=0和b=0xffffffff的情况。正确的绝对差应该是0xffffffff，但你的解决方案会给出1。

- Goz

---

正如奇怪的编辑所解释的那样，这是错误的。另一个8位无符号整数的例子：对于4-255，正确的绝对差是251。但将其视为有符号数-5并取绝对值会得到5，这与255-250得到的答案相同。 - Peter Cordes