c - 高效的模 255 计算
问题描述
我正在尝试找到计算 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: sum 3+3+3+4 = 13, fold 1+3 = 4。如果折叠后的结果是base-1，我们需要生成 0 代替。DIGIT_SUM_THEN_FOLD使用这种方法。
A. Cockburn，“使用 8/16 位算法高效实现 OSI 传输协议校验和算法”，ACM SIGCOMM 计算机通信评论，卷。17 月 3 日，7 月/8 月。1987 年，第 13-20 页
显示了在校验和计算模255的上下文中有效地添加数字模的不同方法。base-1计算数字的逐字节总和，并在每次加法之后，添加加法中的任何进位。所以这将是一个ADD a, b,ADC a, 0序列。用数字写出这个加法链base 256很明显，计算基本上是乘以0x0101 ... 0101。结果将位于最高有效数字位置，除非需要单独从该位置的加法中捕获进位。此方法仅在一个base数字包含 2 k位时才有效。在这里我们有k=3。我尝试了三种不同的方法将结果重新映射base-1到 0，从而产生变体DIGIT_SUM_CARRY_OUT_1, DIGIT_SUM_CARRY_OUT_2,DIGIT_SUM_CARRY_OUT_3.
Joe Keane 在 1995/07/09 的新闻组 comp.lang.c 中演示了一种有效计算模 63 的有趣方法。虽然线程参与者 Peter L. Montgomery 证明了该算法是正确的，但不幸的是，基恩先生没有回应解释其推导的请求。该算法也在 H. Warren 的Hacker's Delight 2nd ed中重现。我能够以纯机械方式将其扩展到模 127 和模 255。这是（适当命名的）KEANE_MAGIC 变体。更新：自从我最初发布这个问题以来，我发现基恩的方法基本上是一个聪明的定点实现以下内容：return (uint32_t)(fmod (x * 256.0 / 255.0 + 0.5, 256.0) * (255.0 / 256.0));. 这使其成为下一个变体的近亲。
Henry S. Warren，《黑客的喜悦》第 2 版。，页。图 272 显示了一种“乘法右移”算法，大概是作者自己设计的，它基于 n mod 2 k-1 = floor (2 k / 2 k-1 * n) mod 2 k的数学性质。定点计算用于乘以因子 2 k / 2 k-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和n，求模表达式x % n涉及（至少在概念上）三个操作：除法、乘法和减法：
quotient = x / n;
product = quotient * n;
modulus = x - product;
但是，当n是 2 的幂 ( n = 2 p ) 时，可以更快地确定模数，只需屏蔽除低p位之外的所有位。
在大多数 CPU 上，加法、减法和位掩码是非常“便宜”（快速）的操作，乘法更“昂贵”并且除法非常昂贵——但请注意，大多数优化编译器会将除法转换为编译时常量乘法（乘以不同的常数）和位移（见下文）。
因此，如果我们可以将模 255 转换为模 256，而无需太多开销，我们可能会加快该过程。我们可以通过注意它x % n等价于(x + x / n) % (n + 1)†</sup> 来做到这一点。因此，我们现在的概念操作是：除法、加法和屏蔽。
在屏蔽低 8 位的特定情况下，基于 x86/x64 的 CPU（和其他？）可能能够执行进一步的优化，因为它们可以访问（大多数）寄存器的 8 位版本。
下面是 clang-cl 编译器为一个朴素的模 255 函数生成的内容（传入ecx并返回的参数eax）：
unsigned Naive255(unsigned x)
{
return x % 255;
}
mov edx, ecx
mov eax, 2155905153 ;
imul rax, rdx ; Replacing the IDIV with IMUL and SHR
shr rax, 39 ;
mov edx, eax
shl edx, 8
sub eax, edx
add eax, ecx
这是使用上述“技巧”生成的（显然更快）代码：
unsigned Trick255(unsigned x)
{
return (x + x / 255) & 0xFF;
}
mov eax, ecx
mov edx, 2155905153
imul rdx, rax
shr rdx, 39
add edx, ecx
movzx eax, dl ; Faster than an explicit AND mask?
在 Windows-10（64 位）平台（英特尔® 酷睿™ i7-8550U CPU）上测试此代码表明它显着（但不是非常）优于问题中提出的其他算法。
†</sup> David Eisenstat 给出的答案解释了这种等效性如何/为什么有效。
推荐阅读
- javascript - 如何在反应中创建更多状态？反应状态的属性数量是固定的吗？
- makefile - gnu make，包含`include`指令的路径
- azure-storage - Azure 静态网站功能（预览版）：上传文件
- java - 懒惰初始化角色集合失败：someEnttiy.otherTitles
- reactjs - 用于协作文本编辑的 IPFS
- python - PySpark 在 map() 和 reduce() 函数中对 self 的引用
- javascript - 如何将 Chrome 书签“date_added”值解析为日期
- javascript - 脚本在 Apple 的 Safari 中返回 NaN
- java - 初始化节点错误
- javascript - 在 jelly 脚本中使用 CSS