我正在尝试找到计算32位无符号整数模255的最有效方法。我的主要重点是找到适用于x86和ARM平台并具有适用性的算法。首先，我试图避免内存操作（可能会很昂贵），因此我正在寻找位运算的方法，同时避免使用表格。我还试图避免潜在的昂贵操作，如分支和乘法，并最小化所使用的操作和寄存器数量。
下面的ISO-C99代码捕捉了我迄今为止尝试的八个变体。它包括一个详尽测试的框架。我添加了一些“粗略”的执行时间测量，这似乎足以获得第一次性能印象。在我尝试过的少数平台上（都具有快速整数乘法），变体WARREN_MUL_SHR_2、WARREN_MUL_SHR_1和DIGIT_SUM_CARRY_OUT_1似乎是性能最好的。我的实验表明，在Compiler Explorer上尝试的x86、ARM、PowerPC和MIPS编译器都非常好地利用了特定于平台的功能，例如三输入LEA、字节扩展指令、乘积累加和指令预测。
变体NAIVE_USING_DIV使用整数除法，后跟除数的反向乘法和减法。这是基线情况。现代编译器知道如何有效地实现无符号整数除以255（通过乘法），并将在适当时使用离散替换来进行反向乘法。要计算模base-1，可以对base位数求和，然后折叠结果。例如3334 mod 9：求和3+3+3+4 = 13，折叠1+3 = 4。如果折叠后的结果为base-1，则需要生成0。DIGIT_SUM_THEN_FOLD使用此方法。
A. Cockburn，“Efficient implementation of the OSI transport protocol checksum algorithm using 8/16-bit arithmetic”，ACM SIGCOMM Computer Communication Review，Vol. 17，No. 3，July/Aug. 1987，pp. 13-20
展示了一种在模255的checksum计算中高效地添加数字取模
Joe Keane在1995年7月9日的comp.lang.c新闻组中演示了一种计算模63的有趣方法。虽然参与讨论的Peter L. Montgomery证明了该算法的正确性，但不幸的是，Keane先生未能回应请求解释其推导过程。这个算法也在H. Warren的Hacker's Delight 2nd ed中复制了出来。我能够将其扩展到模-127和模-255，这就是（适当命名为）KEANE_MAGIC变体。更新:自从我最初发布这个问题以来，我已经成功地找出了Keane的方法基本上是以下代码的巧妙固定点实现：
Henry S. Warren在第二版Hacker's Delight 2nd ed.的第272页展示了一种“乘-移位”算法，推测该算法是由作者自己设计的，它基于数学性质：n mod 2k-1=floor(2k/2k-1*n) mod 2k。使用固定点计算乘以因子2k/2k-1。我构建了两个变体，它们在如何处理将
下面的ISO-C99代码捕捉了我迄今为止尝试的八个变体。它包括一个详尽测试的框架。我添加了一些“粗略”的执行时间测量，这似乎足以获得第一次性能印象。在我尝试过的少数平台上（都具有快速整数乘法），变体WARREN_MUL_SHR_2、WARREN_MUL_SHR_1和DIGIT_SUM_CARRY_OUT_1似乎是性能最好的。我的实验表明，在Compiler Explorer上尝试的x86、ARM、PowerPC和MIPS编译器都非常好地利用了特定于平台的功能，例如三输入LEA、字节扩展指令、乘积累加和指令预测。
变体NAIVE_USING_DIV使用整数除法，后跟除数的反向乘法和减法。这是基线情况。现代编译器知道如何有效地实现无符号整数除以255（通过乘法），并将在适当时使用离散替换来进行反向乘法。要计算模base-1，可以对base位数求和，然后折叠结果。例如3334 mod 9：求和3+3+3+4 = 13，折叠1+3 = 4。如果折叠后的结果为base-1，则需要生成0。DIGIT_SUM_THEN_FOLD使用此方法。
A. Cockburn，“Efficient implementation of the OSI transport protocol checksum algorithm using 8/16-bit arithmetic”，ACM SIGCOMM Computer Communication Review，Vol. 17，No. 3，July/Aug. 1987，pp. 13-20
展示了一种在模255的checksum计算中高效地添加数字取模
base-1的不同方法。对数字进行逐字节求和，在每次加法后，也要加上任何进位。因此，这将是一个ADD a, b，ADC a, 0序列。使用base 256数字编写出此方法的加法链时，清楚地表明该计算基本上是使用0x0101 ... 0101进行乘法运算。结果将位于最高有效数字位置，除了需要单独捕获该位置的加法进位。当base数字包括2k位时，此方法仅适用。在这里，我们有k=3。我尝试了三种不同的重映射base-1结果为0的方法，分别得到变体DIGIT_SUM_CARRY_OUT_1、DIGIT_SUM_CARRY_OUT_2和DIGIT_SUM_CARRY_OUT_3。Joe Keane在1995年7月9日的comp.lang.c新闻组中演示了一种计算模63的有趣方法。虽然参与讨论的Peter L. Montgomery证明了该算法的正确性，但不幸的是，Keane先生未能回应请求解释其推导过程。这个算法也在H. Warren的Hacker's Delight 2nd ed中复制了出来。我能够将其扩展到模-127和模-255，这就是（适当命名为）KEANE_MAGIC变体。更新:自从我最初发布这个问题以来，我已经成功地找出了Keane的方法基本上是以下代码的巧妙固定点实现：
return (uint32_t)(fmod (x * 256.0 / 255.0 + 0.5, 256.0) * (255.0 / 256.0));。这使它成为下一个变体的近亲。Henry S. Warren在第二版Hacker's Delight 2nd ed.的第272页展示了一种“乘-移位”算法，推测该算法是由作者自己设计的，它基于数学性质：n mod 2k-1=floor(2k/2k-1*n) mod 2k。使用固定点计算乘以因子2k/2k-1。我构建了两个变体，它们在如何处理将
base-1的初步结果映射到0方面有所不同。这些是变量WARREN_MUL_SHR_1和WARREN_MUL_SHR_2。
有没有比我目前已经确定的三个最佳候选算法更加高效的模255计算算法，尤其是对于整数乘法速度较慢的平台？针对这种情况，对Keane的无乘法算法进行有效修改，以便对四个base 256数字进行求和，似乎具有特别的意义。
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define NAIVE_USING_DIV (1)
#define DIGIT_SUM_THEN_FOLD (2)
#define DIGIT_SUM_CARRY_OUT_1 (3)
#define DIGIT_SUM_CARRY_OUT_2 (4)
#define DIGIT_SUM_CARRY_OUT_3 (5)
#define KEANE_MAGIC (6) // Joe Keane, comp.lang.c, 1995/07/09
#define WARREN_MUL_SHR_1 (7) // Hacker's Delight, 2nd ed., p. 272
#define WARREN_MUL_SHR_2 (8) // Hacker's Delight, 2nd ed., p. 272
#define VARIANT (WARREN_MUL_SHR_2)
uint32_t mod255 (uint32_t x)
{
#if VARIANT == NAIVE_USING_DIV
return x - 255 * (x / 255);
#elif VARIANT == DIGIT_SUM_THEN_FOLD
x = (x & 0xffff) + (x >> 16);
x = (x & 0xff) + (x >> 8);
x = (x & 0xff) + (x >> 8) + 1;
x = (x & 0xff) + (x >> 8) - 1;
return x;
#elif VARIANT == DIGIT_SUM_CARRY_OUT_1
uint32_t t;
t = 0x01010101 * x;
t = (t >> 24) + (t < x);
if (t == 255) t = 0;
return t;
#elif VARIANT == DIGIT_SUM_CARRY_OUT_2
uint32_t t;
t = 0x01010101 * x;
t = (t >> 24) + (t < x) + 1;
t = (t & 0xff) + (t >> 8) - 1;
return t;
#elif VARIANT == DIGIT_SUM_CARRY_OUT_3
uint32_t t;
t = 0x01010101 * x;
t = (t >> 24) + (t < x);
t = t & ((t - 255) >> 8);
return t;
#elif VARIANT == KEANE_MAGIC
x = (((x >> 16) + x) >> 14) + (x << 2);
x = ((x >> 8) + x + 2) & 0x3ff;
x = (x - (x >> 8)) >> 2;
return x;
#elif VARIANT == WARREN_MUL_SHR_1
x = (0x01010101 * x + (x >> 8)) >> 24;
x = x & ((x - 255) >> 8);
return x;
#elif VARIANT == WARREN_MUL_SHR_2
x = (0x01010101 * x + (x >> 8)) >> 24;
if (x == 255) x = 0;
return x;
#else
#error unknown VARIANT
#endif
}
uint32_t ref_mod255 (uint32_t x)
{
volatile uint32_t t = x;
t = t % 255;
return t;
}
// timing with microsecond resolution
#if defined(_WIN32)
#if !defined(WIN32_LEAN_AND_MEAN)
#define WIN32_LEAN_AND_MEAN
#endif
#include <windows.h>
double second (void)
{
LARGE_INTEGER t;
static double oofreq;
static int checkedForHighResTimer;
static BOOL hasHighResTimer;
if (!checkedForHighResTimer) {
hasHighResTimer = QueryPerformanceFrequency (&t);
oofreq = 1.0 / (double)t.QuadPart;
checkedForHighResTimer = 1;
}
if (hasHighResTimer) {
QueryPerformanceCounter (&t);
return (double)t.QuadPart * oofreq;
} else {
return (double)GetTickCount() * 1.0e-3;
}
}
#elif defined(__linux__) || defined(__APPLE__)
#include <stddef.h>
#include <sys/time.h>
double second (void)
{
struct timeval tv;
gettimeofday(&tv, NULL);
return (double)tv.tv_sec + (double)tv.tv_usec * 1.0e-6;
}
#else
#error unsupported platform
#endif
int main (void)
{
double start, stop;
uint32_t res, ref, x = 0;
printf ("Testing VARIANT = %d\n", VARIANT);
start = second();
do {
res = mod255 (x);
ref = ref_mod255 (x);
if (res != ref) {
printf ("error @ %08x: res=%08x ref=%08x\n", x, res, ref);
return EXIT_FAILURE;
}
x++;
} while (x);
stop = second();
printf ("test passed\n");
printf ("elapsed = %.6f seconds\n", stop - start);
return EXIT_SUCCESS;
}
x = ((x + x / 255u) & 0xFFu);似乎总是给出正确的答案，并且在我的本地机器上（clang-cl/Visual Studio，64位Windows-10）始终优于所有其他方法。一个除法，一个加法和一个微不足道的掩码。 - Adrian Molex = 255 q + r，其中0 ≤ r < 255，则公式计算为(255 q + r + q) mod 256 = (256 q + r) mod 256 = r，正如所期望的那样。 - David EisenstatWARREN_MUL_SHR_1相同，比WARREN_MUL_SHR_2稍慢。太棒了。 - njuffa/Ox /arch:AVX2的计算机上，你的解决方案比我问题中的任何变体都要快。 - njuffa