assembly - 如何使用 SSE 计算模数/余数？

Question

在 x64/sse 上使用矢量指令计算 x % M 的最佳/最快方法是什么？ (% 我的意思是模数/余数)。

我找不到 packed mod 的任何操作码，所以我认为我能做的最好的事情是将 int 提升为 float，然后使用 DIVPS 和 ROUNDPS 计算 x - m * floor(x/m)。

或者是否有我缺少的更好的选择？

更新:M 仅在运行时已知，实际循环如下所示:

unsigned x[SIZE], M[SIZE], answer[SIZE];
for (int i = 0; i < SIZE; i++) {
  answer[i] = x[i] % M[i];
}

此外，M 的范围为 1 - 640000000，如果它有任何帮助的话。

Answer 1

如果 M 是一个编译时常量或在循环中是常量，那么您可以 calculated a reciprocal and then do multiplication and a shift 而不是使用除法.我们可以写

x/M = (x*(2^n/M))>>n

因子 2^n/M(又名 magic number)应该在循环之前或编译时计算。

例如，如果我们想要 x[i]/5 并且我们知道 x[i] 小于 2^15 我们可以使用 2^n/M = 0xCCCD 和 n = 18。

#include <stdio.h>
#define N 32768
int x[N], y[N], z[N];

int main(void) {
    for(int i=0; i<N; i++) x[i] = i;
    int M = 5;
    int fact = 0xCCCD;
    int n = 18;
    for(int i=0; i<N; i++) {
        y[i] = x[i]/M;
        z[i] = (fact*x[i])>>n;
        if(y[i] != z[i]) printf("%d %d\n", y[i], z[i]);
    }
}

有几种不同的方法可以确定魔数(Magic Number)和n。我用 Agner Fog's Vector Class Library(VCL) .它会为您使用 SSE2 或 AVX2 处理 32 位数字(而不是上面代码中的 15 位数字)。如果您想查看汇编代码来执行此操作，请访问他的 assembly library也为 SSE2(也许还有 AVX2)这样做

有关详细信息，请参阅 VCL 手册的第 22 页。在他的汇编库的手册中也有描述。