在 C 中使用内联汇编来实现位奇偶校验？
Working inline assembly in C for bit parity?
我正在尝试计算大量 uint64 的 位奇偶校验 。通过位奇偶校验，我的意思是一个函数接受 uint64 并在设置位数为偶数时输出 0，否则输出 1。
目前我正在使用以下功能（@Troyseph，发现here）：
uint parity64(uint64 n){
n ^= n >> 1;
n ^= n >> 2;
n = (n & 0x1111111111111111) * 0x1111111111111111;
return (n >> 60) & 1;
}
相同的 SO 页面具有以下汇编例程（来自@papadp）：
.code
; bool CheckParity(size_t Result)
CheckParity PROC
mov rax, 0
add rcx, 0
jnp jmp_over
mov rax, 1
jmp_over:
ret
CheckParity ENDP
END
利用机器的parity flag。但是我无法让它与我的 C 程序一起工作（我知道几乎没有汇编）。
问题。如何将上述（或类似）代码作为内联汇编包含在我的 C 源文件中，以便 parity64() 函数运行它？
（我在 Intel Xeon Haswell 上使用 64 位 Ubuntu 14 的 GCC）
如果有任何帮助，parity64() 函数在以下例程中调用：
uint bindot(uint64* a, uint64* b, uint64 entries){
uint parity = 0;
for(uint i=0; i<entries; ++i)
parity ^= parity64(a[i] & b[i]); // Running sum!
return parity;
}
（这应该是场 Z/2Z 上两个向量的 "dot product"，又名 GF(2)。）
您必须使用扩展的内联汇编（它是 gcc 扩展）才能获得类似的效果。
您的 parity64 函数可以更改如下 -
uint parity64_unsafe_and_broken(uint64 n){
uint result = 0;
__asm__("addq [=10=], %0" : : "r"(n) :);
// editor's note: compiler-generated instructions here can destroy EFLAGS
// Don't depending on FLAGS / regs surviving between asm statements
// also, jumping out of an asm statement safely requires asm goto
__asm__("jnp 1f");
__asm__("movl , %0" : "=r"(result) : : );
__asm__("1:");
return result;
}
但是正如@MichaelPetch 所评论的，奇偶校验标志仅在低 8 位上计算。因此，如果您的 n 小于 255，这将适用于您。对于更大的数字，您将不得不使用您在问题中提到的代码。
要使其适用于 64 位，您可以通过
将 32 位整数的奇偶校验折叠为单个字节
n = (n >> 32) ^ n;
n = (n >> 16) ^ n;
n = (n >> 8) ^ n;
这段代码必须刚好在汇编之前函数的开头。
您必须检查它如何影响性能。
我能得到的最优化是
uint parity64(uint64 n){
unsigned char result = 0;
n = (n >> 32) ^ n;
n = (n >> 16) ^ n;
n = (n >> 8) ^ n;
__asm__("test %1, %1 \n\t"
"setp %0"
: "+r"(result)
: "r"(n)
:
);
return result;
}
因为 C 在处理位操作时很糟糕，我建议使用 gcc 内置函数，在本例中为 __builtin_parityl()。参见：
How can I include the above (or similar) code as inline assembly in my C source file, so that the parity64() function runs that instead?
这是一个 XY problem...您认为您需要 内联 该程序集才能从中获益，因此您询问 如何内联它...但是你不需要内联它.
您不应该将汇编包含到您的 C 源代码中，因为在这种情况下您不需要，并且更好的选择（就可移植性和可维护性而言）是将两部分源代码分开，分别编译它们并使用 linker to link 它们 .
在 parity64.c 中你应该有你的 便携式 版本（带有一个名为 bool CheckParity(size_t result) 的包装器），你可以在 non-x86/64 中默认使用它情况。
你可以像这样编译成目标文件：gcc -c parity64.c -o parity64.o
...然后link汇编生成的目标代码，C代码：gcc bindot.c parity64.o -o bindot
在 parity64_x86.s 中，您的问题可能包含以下汇编代码：
.code
; bool CheckParity(size_t Result)
CheckParity PROC
mov rax, 0
add rcx, 0
jnp jmp_over
mov rax, 1
jmp_over:
ret
CheckParity ENDP
END
您可以使用 gcc 和以下命令将其编译为替代 parity64.o 目标文件目标代码：gcc -c parity64_x86.s -o parity64.o
... 然后 link 生成的目标代码如下： gcc bindot.c parity64.o -o bindot
类似地，如果您想改用 __builtin_parityl（如 所建议，您可以（并且应该）再次将该代码分开（在与其他 gcc/x86 优化) 来自你的可移植代码。在parity64_x86.c你可能有：
bool CheckParity(size_t result) {
return __builtin_parityl(result);
}
要编译这个，你的命令是：gcc -c parity64_x86.c -o parity64.o
... 然后 link 生成的目标代码如下： gcc bindot.c parity64.o -o bindot
附带说明一下，如果您想检查程序集 gcc 将由此产生：gcc -S parity64_x86.c
汇编中的注释表明 C 中等效的函数原型为 bool CheckParity(size_t Result)，因此考虑到这一点，bindot.c 可能如下所示：
extern bool CheckParity(size_t Result);
uint64_t bindot(uint64_t *a, uint64_t *b, size_t entries){
uint64_t parity = 0;
for(size_t i = 0; i < entries; ++i)
parity ^= a[i] & b[i]; // Running sum!
return CheckParity(parity);
}
您可以将此 link 构建为上述 parity64.o 版本的 任何 ，如下所示：gcc bindot.c parity64.o -o bindot...
我强烈推荐阅读the manual for your compiler，有空的话...
这听起来可能有点刺耳，但我认为有必要说一下。请不要往心里去；我并不是说这是一种侮辱，尤其是因为你已经承认你“几乎不了解任何集会”。但是如果你认为这样的代码：
CheckParity PROC
mov rax, 0
add rcx, 0
jnp jmp_over
mov rax, 1
jmp_over:
ret
CheckParity ENDP
会，那你就真的没必要用内联汇编了。就在那 5 行代码中，我看到 2 条指令很明显 sub-optimal。可以通过稍微重写来优化它：
xor eax, eax
test ecx, ecx ; logically, should use RCX, but see below for behavior of PF
jnp jmp_over
mov eax, 1 ; or possibly even "inc eax"; would need to verify
jmp_over:
ret
或者，如果您有 random input values that are likely to foil the branch predictor（即，输入值的奇偶性没有可预测的模式），那么删除它会更快b运行ch，写成：
xor eax, eax
test ecx, ecx
setp al
ret
或者等效的（在某些处理器上会更快，但不一定是所有处理器）：
xor eax, eax
test ecx, ecx
mov ecx, 1
cmovp eax, ecx
ret
考虑到我对 x86 ISA 的现有知识以及我之前进行的基准测试，这些只是我能想到的改进。但为免有人被愚弄，这无疑 不是 最快的代码，因为（借用 Michael Abrash 的话），“没有最快的代码这样的东西”——几乎总有人可以让它更快。
enough problems with using inline assembly 当你是专家时 assembly-language 程序员和向导当涉及到 x86 ISA 的复杂性时。优化器现在非常好，这意味着真正的专家很难编写出更好的代码（当然也不是不可能）。它还采用 trustworthy 基准来验证您的假设并确认您优化的内联汇编实际上更快。 在没有 运行 好的基准测试 的情况下，切勿承诺使用内联汇编来超越编译器的优化器。我在你的问题中看不到任何证据表明你做过这样的事情。我在这里推测，但它 看起来 就像您看到代码是用汇编语言编写的，并认为这意味着它会更快。这种情况很少见。 C 编译器最终也会生成汇编语言代码，并且它通常比我们人类能够生成的代码更优化，给定有限的时间和资源，更不用说有限的专业知识。
在这种特殊情况下，有一种观点认为内联汇编比 C 编译器的输出更快，因为 C 编译器将无法智能地使用 x86 体系结构的 built-in 奇偶校验标志 (PF ) 对其有利。你可能是对的，但这是一个非常不稳定的假设，远非普遍适用。正如我所说，优化编译器现在非常聪明，它们确实针对特定架构进行了优化（假设您指定了正确的选项），因此优化器 会 发出使用 PF 的代码。您必须查看反汇编才能确定。
作为我的意思的一个例子，考虑 x86 提供的高度专业化的 BSWAP 指令。您可能天真地认为需要内联汇编才能利用它，但事实并非如此。以下 C 代码在几乎所有主要编译器上编译为 BSWAP 指令：
uint32 SwapBytes(uint32 x)
{
return ((x << 24) & 0xff000000 ) |
((x << 8) & 0x00ff0000 ) |
((x >> 8) & 0x0000ff00 ) |
((x >> 24) & 0x000000ff );
}
性能将是等效的，如果不是更好的话，因为优化器对代码的作用有更多的了解。事实上，这种形式相对于内联汇编的 主要 好处是编译器可以使用此代码执行常量折叠（ 即 ，当使用compile-time 常量）。此外，与使用内联汇编相比，代码更易读（至少对于 C 程序员而言）， 更少 error-prone，并且更容易维护。哦，我有没有提到，如果您想针对 x86 以外的架构，它是相当便携的？
我知道我在大做文章，我想让你明白我是作为一个 喜欢 写作 highly-tuned 的人这么说的性能优于编译器优化器的汇编代码。但每次我这样做，都只是：一个挑战，伴随着牺牲。它不是万灵药，您需要记得检查您的假设，包括：
- 这段代码是否真的是我的应用程序中的瓶颈，以至于优化它甚至会产生任何可察觉的差异？
- 优化器是否真的为我编写的代码发出 sub-optimal 机器语言指令？
- 我天真地认为 sub-optimal 是不是我错了？也许优化器比我更了解目标架构， 看起来 慢或 sub-optimal 代码实际上更快。 （请记住，更少的代码不一定更快。）
- 我是否在有意义的 real-world 基准测试中测试了它，并证明 compiler-generated 代码很慢而我的内联汇编实际上更快？
- 我绝对没有办法调整 C 代码来说服优化器发出接近、等于或等于 更好 的机器代码甚至优于我的内联汇编的性能？
为了尝试回答其中一些问题，我设置了一个小基准。 （使用 MSVC，因为那是我手边的东西；如果你的目标是 GCC，最好使用那个编译器，但我们仍然可以得到一个大概的想法。我使用并推荐 Google's benchmarking library。）我 马上 运行 成问题。看，我首先 运行 我在“调试”模式下的基准测试，其中编译的断言验证我的“调整”/“优化”代码实际上为所有测试用例产生与原始代码相同的结果（即大概知道是 working/correct）。在这种情况下，一个断言立即被触发。事实证明，用汇编语言编写的 CheckParity 例程与 parity64 而不是 return 相同的结果] 用C写的例程！ Uh-oh。嗯，这是我们需要添加到上面列表中的另一个项目符号：
- 我是否确保我的“优化”代码是 return 正确的结果？
这一点尤其重要，因为如果你也做错了，很容易让事情变得更快。 :-) 我开玩笑，但不完全是，因为为了追求更快的代码，我已经做过很多次了。
我相信Michael Petch已经指出了差异的原因：在x86实现中，奇偶校验标志（PF）只关注低字节中的位，而不是整个值。如果这就是您所需要的，那就太好了。但即便如此，我们仍可以回到 C 代码并进一步优化 it 以减少工作量，这将使它更快——可能比汇编代码更快，从而消除内联的一个优势集会曾经有过。
现在，让我们假设您需要完整值的奇偶校验，因为这是您使用的原始实现，您只是想让它更快 而不是 改变它的行为。因此，我们需要 修复 汇编代码的逻辑，然后才能继续对其进行有意义的基准测试。幸运的是，由于我写这个答案的时间较晚，（在其他人的协助下）已经完成了这项工作，省去了我额外的工作。
…除了，不完全是。当我第一次起草这个答案时，我的基准显示 draft 9 of his "tweaked" code still did not produce the same result as the original C function, so it's unsuitable according to our test cases. , which means either (A) the original C code was doing extra work, making it needlessly slow, meaning that you can probably tweak it to beat the inline assembly at its own game, or worse, (B) you have insufficient test cases and the new "optimized" code is actually a bug lying in wait. Since that time, ，它既修复了导致错误结果被 returned 的错误，又进一步改进了代码。这里需要的输入量，以及他经历过的草稿数量，应该可以证明编写正确的内联汇编来击败编译器的难度。但我们还没有完成！他的内联汇编仍然写错了。 SETcc 指令需要一个 8 位寄存器作为它们的操作 运行d，但他的代码没有使用寄存器说明符来请求它，这意味着代码要么无法编译（因为 Clang 很聪明足以检测此错误）或 将 在 GCC 上编译但不会正确执行，因为该指令具有无效的 ope运行d.
我让您相信测试的重要性了吗？我会相信它，并继续进行基准测试部分。基准测试结果使用 Ajay 代码的最终草案，其中包含 Ped7g 的改进和我的额外调整。我还比较了 that question you linked 中针对 64 位整数修改的其他一些解决方案，以及我自己的一些发明。这是我的基准测试结果（移动 Haswell i7-4850HQ）：
Benchmark Time CPU Iterations
-------------------------------------------------------------------
Naive 36 ns 36 ns 19478261
OriginalCCode 4 ns 4 ns 194782609
Ajay_Brahmakshatriya_Tweaked 4 ns 4 ns 194782609
Shreyas_Shivalkar 37 ns 37 ns 17920000
TypeIA 5 ns 5 ns 154482759
TypeIA_Tweaked 4 ns 4 ns 160000000
has_even_parity 227 ns 229 ns 3200000
has_even_parity_Tweaked 36 ns 36 ns 19478261
GCC_builtin_parityll 4 ns 4 ns 186666667
PopCount 3 ns 3 ns 248888889
PopCount_Downlevel 5 ns 5 ns 100000000
现在请记住，这些是针对 randomly-generated 64 位输入值的，这会破坏 b运行ch 预测。如果您的输入值以可预测的方式存在偏差，无论是偏向奇偶校验还是 non-parity，那么 b运行ch 预测器将为您 而不是 反对你，某些方法可能会更快。这强调了针对模拟 real-world 用例的数据进行基准测试的重要性。 （也就是说，当我编写通用库函数时，我倾向于针对 运行dom 输入进行优化，平衡大小和速度。）
注意原始 C 函数与其他函数的比较。我要声明，进一步优化它 可能 是在浪费大量时间。所以希望你从这个答案中学到了更一般的东西，而不是仅仅向下滚动到 copy-paste 代码片段。 :-)
Naive 函数是一个完全未优化的完整性检查，用于确定奇偶校验，取自 here。我什至用它来验证您的原始 C 代码，并为基准测试提供基准。由于它循环遍历每一位，one-by-one，它相对较慢，正如预期的那样：
unsigned int Naive(uint64 n)
{
bool parity = false;
while (n)
{
parity = !parity;
n &= (n - 1);
}
return parity;
}
OriginalCCode 正是它听起来的样子——它是您拥有的原始 C 代码，如问题中所示。请注意它是如何在 与 Ajay Brahmakshatriya 的内联汇编代码的 tweaked/corrected 版本完全同时 发布的！现在，因为我 运行 MSVC 中的这个基准测试不支持 6 的内联汇编-bit 构建，我不得不使用一个包含该函数的外部汇编模块，并从那里调用它，这引入了一些额外的开销。使用 GCC 的内联汇编，编译器可能已经能够内联代码，从而省略函数调用。因此，在 GCC 上，您可能会看到 inline-assembly 版本最多快一纳秒（或可能不会）。值得吗？你是法官。作为参考，这是我针对 Ajay_Brahmakshatriya_Tweaked:
测试的代码
Ajay_Brahmakshatriya_Tweaked PROC
mov rax, rcx ; Windows 64-bit calling convention passes parameter in ECX (System V uses EDI)
shr rax, 32
xor rcx, rax
mov rax, rcx
shr rax, 16
xor rcx, rax
mov rax, rcx
shr rax, 8
xor eax, ecx ; Ped7g's TEST is redundant; XOR already sets PF
setnp al
movzx eax, al
ret
Ajay_Brahmakshatriya_Tweaked ENDP
名为 Shreyas_Shivalkar 的函数来自 his answer here，它只是 loop-through-each-bit 主题的一个变体，并且符合预期，很慢：
Shreyas_Shivalkar PROC
; unsigned int parity = 0;
; while (x != 0)
; {
; parity ^= x;
; x >>= 1;
; }
; return (parity & 0x1);
xor eax, eax
test rcx, rcx
je SHORT Finished
Process:
xor eax, ecx
shr rcx, 1
jne SHORT Process
Finished:
and eax, 1
ret
Shreyas_Shivalkar ENDP
TypeIA 和 TypeIA_Tweaked 是来自 this answer, modified to support 64-bit values, and my tweaked version. They parallelize the operation, resulting in a significant speed improvement over the loop-through-each-bit strategy. The "tweaked" version is based on an optimization originally suggested by Mathew Hendry to Sean Eron Anderson's Bit Twiddling Hacks 的代码，并且确实比原来的 speed-up 少了一点。
unsigned int TypeIA(uint64 n)
{
n ^= n >> 32;
n ^= n >> 16;
n ^= n >> 8;
n ^= n >> 4;
n ^= n >> 2;
n ^= n >> 1;
return !((~n) & 1);
}
unsigned int TypeIA_Tweaked(uint64 n)
{
n ^= n >> 32;
n ^= n >> 16;
n ^= n >> 8;
n ^= n >> 4;
n &= 0xf;
return ((0x6996 >> n) & 1);
}
has_even_parity 基于 the accepted answer to that question，修改为支持 64 位值。我知道这会很慢，因为这是另一种 loop-through-each-bit 策略，但显然 有人 认为这是一个好方法。有趣的是，它实际上有多慢，甚至与我称之为“朴素”的方法相比，它本质上做同样的事情，但速度更快，使用 less-complicated 代码。
unsigned int has_even_parity(uint64 n)
{
uint64 count = 0;
uint64 b = 1;
for (uint64 i = 0; i < 64; ++i)
{
if (n & (b << i)) { ++count; }
}
return (count % 2);
}
has_even_parity_Tweaked 是上面的替代版本，它利用布尔值可以隐式转换为 0 和 1 的事实来节省 b运行ch。它比原来的要快得多, 在与“幼稚”方法相当的时间打卡：
unsigned int has_even_parity_Tweaked(uint64 n)
{
uint64 count = 0;
uint64 b = 1;
for (uint64 i = 0; i < 64; ++i)
{
count += static_cast<int>(static_cast<bool>(n & (b << i)));
}
return (count % 2);
}
现在我们进入正题。函数 GCC_builtin_parityll 包含 GCC 在您使用其 __builtin_parityll 内在函数时将发出的汇编代码。其他一些人建议您使用这个内在函数，我必须附和他们的支持。它的性能与我们迄今为止看到的最好的性能相当，并且它有几个额外的优点：（1）它使代码简单易读（比 C 版本更简单）； (2) 它可以移植到不同的体系结构，并且可以预期在那里也保持快速； (3) 随着 GCC 改进其实现，您的代码可能会通过简单的重新编译变得更快。您可以获得内联汇编的所有好处，没有任何缺点。
GCC_builtin_parityll PROC ; GCC's __builtin_parityll
mov edx, ecx
shr rcx, 32
xor edx, ecx
mov eax, edx
shr edx, 16
xor eax, edx
xor al, ah
setnp al
movzx eax, al
ret
GCC_builtin_parityll ENDP
PopCount 是我自己发明的优化实现。为了想出这个，我回过头来考虑我们实际上想做什么。 “奇偶校验”的定义是偶数个设置位。因此，可以简单地通过计算设置位的数量并测试该计数是偶数还是奇数来计算它。这是两个逻辑操作。幸运的是，在最近几代的 x86 处理器（Intel Nehalem 或 AMD Barcelona，以及更新的处理器）上，有一条指令计算设置位的数量——POPCNT（人口计数，或汉明权重）——它允许我们编写在两个操作中执行此操作的汇编代码。
（好吧，实际上是三个指令，因为在创建 a false dependency on its destination register 的某些微体系结构上 POPCNT 的实现中存在错误，并确保我们从中获得最大吞吐量代码，我们需要通过 pre-clearing 目标寄存器来打破这种依赖性。幸运的是，这是一个非常便宜的操作，通常可以通过寄存器重命名“免费”处理。）
PopCount PROC
xor eax, eax ; break false dependency
popcnt rax, rcx
and eax, 1
ret
PopCount ENDP
事实上，事实证明，当您以支持 POPCNT 的微体系结构为目标时，GCC 知道为 __builtin_parityll 内部函数准确发出此代码（否则，它使用下面显示的回退实现).正如您从基准测试中看到的那样，这是迄今为止最快的代码。这不是主要区别，因此除非您在一个紧密的循环中重复执行此操作，否则它不太重要，但这是一个可衡量的差异，并且大概您不会对此进行如此大的优化，除非您的探查器表明这是一个hot-spot.
但是 POPCNT 指令确实有在旧处理器上不可用的缺点，因此我还测量了代码的“后备”版本，该代码使用 universally-supported 序列进行人口计数] 指示。那就是 PopCount_Downlevel 函数，取自我的私人图书馆，最初改编自 this answer 和其他来源。
PopCount_Downlevel PROC
mov rax, rcx
shr rax, 1
mov rdx, 5555555555555555h
and rax, rdx
sub rcx, rax
mov rax, 3333333333333333h
mov rdx, rcx
and rcx, rax
shr rdx, 2
and rdx, rax
add rdx, rcx
mov rcx, 0FF0F0F0F0F0F0F0Fh
mov rax, rdx
shr rax, 4
add rax, rdx
mov rdx, 0FF01010101010101h
and rax, rcx
imul rax, rdx
shr rax, 56
and eax, 1
ret
PopCount_Downlevel ENDP
正如您从基准测试中看到的那样，此处所需的所有 bit-twiddling 指令都以性能为代价。它比 POPCNT 慢，但在所有系统上都受支持并且仍然相当快。如果您无论如何都需要位计数，这将是最好的解决方案，特别是因为它可以用纯 C 编写而无需求助于内联汇编，可能会产生更快的速度：
unsigned int PopCount_Downlevel(uint64 n)
{
uint64 temp = n - ((n >> 1) & 0x5555555555555555ULL);
temp = (temp & 0x3333333333333333ULL) + ((temp >> 2) & 0x3333333333333333ULL);
temp = (temp + (temp >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
temp = (temp * 0x0101010101010101ULL) >> 56;
return (temp & 1);
}
但是 运行 你自己的基准测试，看看你是否会更好地使用其他实现之一，比如 OriginalCCode，它简化了操作，因此需要更少的总指令。有趣的事实：Intel 的编译器 (ICC) 总是使用人口 count-based 算法来实现 __builtin_parityll；如果目标体系结构支持它，它会发出 POPCNT 指令，否则，它会使用与我在此处显示的基本相同的代码来模拟它。
或者，更好的是，只是忘记整个复杂的混乱，让你的编译器处理它。这就是 built-in 的用途，而正是为了这个目的。
我正在尝试计算大量 uint64 的 位奇偶校验 。通过位奇偶校验，我的意思是一个函数接受 uint64 并在设置位数为偶数时输出 0，否则输出 1。
目前我正在使用以下功能（@Troyseph，发现here）：
uint parity64(uint64 n){
n ^= n >> 1;
n ^= n >> 2;
n = (n & 0x1111111111111111) * 0x1111111111111111;
return (n >> 60) & 1;
}
相同的 SO 页面具有以下汇编例程（来自@papadp）：
.code
; bool CheckParity(size_t Result)
CheckParity PROC
mov rax, 0
add rcx, 0
jnp jmp_over
mov rax, 1
jmp_over:
ret
CheckParity ENDP
END
利用机器的parity flag。但是我无法让它与我的 C 程序一起工作（我知道几乎没有汇编）。
问题。如何将上述（或类似）代码作为内联汇编包含在我的 C 源文件中，以便 parity64() 函数运行它？
（我在 Intel Xeon Haswell 上使用 64 位 Ubuntu 14 的 GCC）
如果有任何帮助，parity64() 函数在以下例程中调用：
uint bindot(uint64* a, uint64* b, uint64 entries){
uint parity = 0;
for(uint i=0; i<entries; ++i)
parity ^= parity64(a[i] & b[i]); // Running sum!
return parity;
}
（这应该是场 Z/2Z 上两个向量的 "dot product"，又名 GF(2)。）
您必须使用扩展的内联汇编（它是 gcc 扩展）才能获得类似的效果。
您的 parity64 函数可以更改如下 -
uint parity64_unsafe_and_broken(uint64 n){
uint result = 0;
__asm__("addq [=10=], %0" : : "r"(n) :);
// editor's note: compiler-generated instructions here can destroy EFLAGS
// Don't depending on FLAGS / regs surviving between asm statements
// also, jumping out of an asm statement safely requires asm goto
__asm__("jnp 1f");
__asm__("movl , %0" : "=r"(result) : : );
__asm__("1:");
return result;
}
但是正如@MichaelPetch 所评论的，奇偶校验标志仅在低 8 位上计算。因此，如果您的 n 小于 255，这将适用于您。对于更大的数字，您将不得不使用您在问题中提到的代码。
要使其适用于 64 位，您可以通过
将 32 位整数的奇偶校验折叠为单个字节n = (n >> 32) ^ n;
n = (n >> 16) ^ n;
n = (n >> 8) ^ n;
这段代码必须刚好在汇编之前函数的开头。
您必须检查它如何影响性能。
我能得到的最优化是
uint parity64(uint64 n){
unsigned char result = 0;
n = (n >> 32) ^ n;
n = (n >> 16) ^ n;
n = (n >> 8) ^ n;
__asm__("test %1, %1 \n\t"
"setp %0"
: "+r"(result)
: "r"(n)
:
);
return result;
}
因为 C 在处理位操作时很糟糕，我建议使用 gcc 内置函数，在本例中为 __builtin_parityl()。参见：
How can I include the above (or similar) code as inline assembly in my C source file, so that the
parity64()function runs that instead?
这是一个 XY problem...您认为您需要 内联 该程序集才能从中获益，因此您询问 如何内联它...但是你不需要内联它.
您不应该将汇编包含到您的 C 源代码中，因为在这种情况下您不需要，并且更好的选择（就可移植性和可维护性而言）是将两部分源代码分开，分别编译它们并使用 linker to link 它们 .
在 parity64.c 中你应该有你的 便携式 版本（带有一个名为 bool CheckParity(size_t result) 的包装器），你可以在 non-x86/64 中默认使用它情况。
你可以像这样编译成目标文件：gcc -c parity64.c -o parity64.o
...然后link汇编生成的目标代码，C代码：gcc bindot.c parity64.o -o bindot
在 parity64_x86.s 中，您的问题可能包含以下汇编代码：
.code
; bool CheckParity(size_t Result)
CheckParity PROC
mov rax, 0
add rcx, 0
jnp jmp_over
mov rax, 1
jmp_over:
ret
CheckParity ENDP
END
您可以使用 gcc 和以下命令将其编译为替代 parity64.o 目标文件目标代码：gcc -c parity64_x86.s -o parity64.o
... 然后 link 生成的目标代码如下： gcc bindot.c parity64.o -o bindot
类似地，如果您想改用 __builtin_parityl（如 parity64_x86.c你可能有：
bool CheckParity(size_t result) {
return __builtin_parityl(result);
}
要编译这个，你的命令是：gcc -c parity64_x86.c -o parity64.o
... 然后 link 生成的目标代码如下： gcc bindot.c parity64.o -o bindot
附带说明一下，如果您想检查程序集 gcc 将由此产生：gcc -S parity64_x86.c
汇编中的注释表明 C 中等效的函数原型为 bool CheckParity(size_t Result)，因此考虑到这一点，bindot.c 可能如下所示：
extern bool CheckParity(size_t Result);
uint64_t bindot(uint64_t *a, uint64_t *b, size_t entries){
uint64_t parity = 0;
for(size_t i = 0; i < entries; ++i)
parity ^= a[i] & b[i]; // Running sum!
return CheckParity(parity);
}
您可以将此 link 构建为上述 parity64.o 版本的 任何 ，如下所示：gcc bindot.c parity64.o -o bindot...
我强烈推荐阅读the manual for your compiler，有空的话...
这听起来可能有点刺耳，但我认为有必要说一下。请不要往心里去；我并不是说这是一种侮辱，尤其是因为你已经承认你“几乎不了解任何集会”。但是如果你认为这样的代码：
CheckParity PROC
mov rax, 0
add rcx, 0
jnp jmp_over
mov rax, 1
jmp_over:
ret
CheckParity ENDP
会
xor eax, eax
test ecx, ecx ; logically, should use RCX, but see below for behavior of PF
jnp jmp_over
mov eax, 1 ; or possibly even "inc eax"; would need to verify
jmp_over:
ret
或者，如果您有 random input values that are likely to foil the branch predictor（即，输入值的奇偶性没有可预测的模式），那么删除它会更快b运行ch，写成：
xor eax, eax
test ecx, ecx
setp al
ret
或者等效的（在某些处理器上会更快，但不一定是所有处理器）：
xor eax, eax
test ecx, ecx
mov ecx, 1
cmovp eax, ecx
ret
考虑到我对 x86 ISA 的现有知识以及我之前进行的基准测试，这些只是我能想到的改进。但为免有人被愚弄，这无疑 不是 最快的代码，因为（借用 Michael Abrash 的话），“没有最快的代码这样的东西”——几乎总有人可以让它更快。
enough problems with using inline assembly 当你是专家时 assembly-language 程序员和向导当涉及到 x86 ISA 的复杂性时。优化器现在非常好，这意味着真正的专家很难编写出更好的代码（当然也不是不可能）。它还采用 trustworthy 基准来验证您的假设并确认您优化的内联汇编实际上更快。 在没有 运行 好的基准测试 的情况下，切勿承诺使用内联汇编来超越编译器的优化器。我在你的问题中看不到任何证据表明你做过这样的事情。我在这里推测，但它 看起来 就像您看到代码是用汇编语言编写的，并认为这意味着它会更快。这种情况很少见。 C 编译器最终也会生成汇编语言代码，并且它通常比我们人类能够生成的代码更优化，给定有限的时间和资源，更不用说有限的专业知识。
在这种特殊情况下，有一种观点认为内联汇编比 C 编译器的输出更快，因为 C 编译器将无法智能地使用 x86 体系结构的 built-in 奇偶校验标志 (PF ) 对其有利。你可能是对的，但这是一个非常不稳定的假设，远非普遍适用。正如我所说，优化编译器现在非常聪明，它们确实针对特定架构进行了优化（假设您指定了正确的选项），因此优化器 会 发出使用 PF 的代码。您必须查看反汇编才能确定。
作为我的意思的一个例子，考虑 x86 提供的高度专业化的 BSWAP 指令。您可能天真地认为需要内联汇编才能利用它，但事实并非如此。以下 C 代码在几乎所有主要编译器上编译为 BSWAP 指令：
uint32 SwapBytes(uint32 x)
{
return ((x << 24) & 0xff000000 ) |
((x << 8) & 0x00ff0000 ) |
((x >> 8) & 0x0000ff00 ) |
((x >> 24) & 0x000000ff );
}
性能将是等效的，如果不是更好的话，因为优化器对代码的作用有更多的了解。事实上，这种形式相对于内联汇编的 主要 好处是编译器可以使用此代码执行常量折叠（ 即 ，当使用compile-time 常量）。此外，与使用内联汇编相比，代码更易读（至少对于 C 程序员而言）， 更少 error-prone，并且更容易维护。哦，我有没有提到，如果您想针对 x86 以外的架构，它是相当便携的？
我知道我在大做文章，我想让你明白我是作为一个 喜欢 写作 highly-tuned 的人这么说的性能优于编译器优化器的汇编代码。但每次我这样做，都只是：一个挑战，伴随着牺牲。它不是万灵药，您需要记得检查您的假设，包括：
- 这段代码是否真的是我的应用程序中的瓶颈，以至于优化它甚至会产生任何可察觉的差异？
- 优化器是否真的为我编写的代码发出 sub-optimal 机器语言指令？
- 我天真地认为 sub-optimal 是不是我错了？也许优化器比我更了解目标架构， 看起来 慢或 sub-optimal 代码实际上更快。 （请记住，更少的代码不一定更快。）
- 我是否在有意义的 real-world 基准测试中测试了它，并证明 compiler-generated 代码很慢而我的内联汇编实际上更快？
- 我绝对没有办法调整 C 代码来说服优化器发出接近、等于或等于 更好 的机器代码甚至优于我的内联汇编的性能？
为了尝试回答其中一些问题，我设置了一个小基准。 （使用 MSVC，因为那是我手边的东西；如果你的目标是 GCC，最好使用那个编译器，但我们仍然可以得到一个大概的想法。我使用并推荐 Google's benchmarking library。）我 马上 运行 成问题。看，我首先 运行 我在“调试”模式下的基准测试，其中编译的断言验证我的“调整”/“优化”代码实际上为所有测试用例产生与原始代码相同的结果（即大概知道是 working/correct）。在这种情况下，一个断言立即被触发。事实证明，用汇编语言编写的 CheckParity 例程与 parity64 而不是 return 相同的结果] 用C写的例程！ Uh-oh。嗯，这是我们需要添加到上面列表中的另一个项目符号：
- 我是否确保我的“优化”代码是 return 正确的结果？
这一点尤其重要，因为如果你也做错了，很容易让事情变得更快。 :-) 我开玩笑，但不完全是，因为为了追求更快的代码，我已经做过很多次了。
我相信Michael Petch已经指出了差异的原因：在x86实现中，奇偶校验标志（PF）只关注低字节中的位，而不是整个值。如果这就是您所需要的，那就太好了。但即便如此，我们仍可以回到 C 代码并进一步优化 it 以减少工作量，这将使它更快——可能比汇编代码更快，从而消除内联的一个优势集会曾经有过。
现在，让我们假设您需要完整值的奇偶校验，因为这是您使用的原始实现，您只是想让它更快 而不是 改变它的行为。因此，我们需要 修复 汇编代码的逻辑，然后才能继续对其进行有意义的基准测试。幸运的是，由于我写这个答案的时间较晚，
…除了，不完全是。当我第一次起草这个答案时，我的基准显示 draft 9 of his "tweaked" code still did not produce the same result as the original C function, so it's unsuitable according to our test cases. SETcc 指令需要一个 8 位寄存器作为它们的操作 运行d，但他的代码没有使用寄存器说明符来请求它，这意味着代码要么无法编译（因为 Clang 很聪明足以检测此错误）或 将 在 GCC 上编译但不会正确执行，因为该指令具有无效的 ope运行d.
我让您相信测试的重要性了吗？我会相信它，并继续进行基准测试部分。基准测试结果使用 Ajay 代码的最终草案，其中包含 Ped7g 的改进和我的额外调整。我还比较了 that question you linked 中针对 64 位整数修改的其他一些解决方案，以及我自己的一些发明。这是我的基准测试结果（移动 Haswell i7-4850HQ）：
Benchmark Time CPU Iterations
-------------------------------------------------------------------
Naive 36 ns 36 ns 19478261
OriginalCCode 4 ns 4 ns 194782609
Ajay_Brahmakshatriya_Tweaked 4 ns 4 ns 194782609
Shreyas_Shivalkar 37 ns 37 ns 17920000
TypeIA 5 ns 5 ns 154482759
TypeIA_Tweaked 4 ns 4 ns 160000000
has_even_parity 227 ns 229 ns 3200000
has_even_parity_Tweaked 36 ns 36 ns 19478261
GCC_builtin_parityll 4 ns 4 ns 186666667
PopCount 3 ns 3 ns 248888889
PopCount_Downlevel 5 ns 5 ns 100000000
现在请记住，这些是针对 randomly-generated 64 位输入值的，这会破坏 b运行ch 预测。如果您的输入值以可预测的方式存在偏差，无论是偏向奇偶校验还是 non-parity，那么 b运行ch 预测器将为您 而不是 反对你，某些方法可能会更快。这强调了针对模拟 real-world 用例的数据进行基准测试的重要性。 （也就是说，当我编写通用库函数时，我倾向于针对 运行dom 输入进行优化，平衡大小和速度。）
注意原始 C 函数与其他函数的比较。我要声明，进一步优化它 可能 是在浪费大量时间。所以希望你从这个答案中学到了更一般的东西，而不是仅仅向下滚动到 copy-paste 代码片段。 :-)
Naive 函数是一个完全未优化的完整性检查，用于确定奇偶校验，取自 here。我什至用它来验证您的原始 C 代码，并为基准测试提供基准。由于它循环遍历每一位，one-by-one，它相对较慢，正如预期的那样：
unsigned int Naive(uint64 n)
{
bool parity = false;
while (n)
{
parity = !parity;
n &= (n - 1);
}
return parity;
}
OriginalCCode 正是它听起来的样子——它是您拥有的原始 C 代码，如问题中所示。请注意它是如何在 与 Ajay Brahmakshatriya 的内联汇编代码的 tweaked/corrected 版本完全同时 发布的！现在，因为我 运行 MSVC 中的这个基准测试不支持 6 的内联汇编-bit 构建，我不得不使用一个包含该函数的外部汇编模块，并从那里调用它，这引入了一些额外的开销。使用 GCC 的内联汇编，编译器可能已经能够内联代码，从而省略函数调用。因此，在 GCC 上，您可能会看到 inline-assembly 版本最多快一纳秒（或可能不会）。值得吗？你是法官。作为参考，这是我针对 Ajay_Brahmakshatriya_Tweaked:
Ajay_Brahmakshatriya_Tweaked PROC
mov rax, rcx ; Windows 64-bit calling convention passes parameter in ECX (System V uses EDI)
shr rax, 32
xor rcx, rax
mov rax, rcx
shr rax, 16
xor rcx, rax
mov rax, rcx
shr rax, 8
xor eax, ecx ; Ped7g's TEST is redundant; XOR already sets PF
setnp al
movzx eax, al
ret
Ajay_Brahmakshatriya_Tweaked ENDP
名为 Shreyas_Shivalkar 的函数来自 his answer here，它只是 loop-through-each-bit 主题的一个变体，并且符合预期，很慢：
Shreyas_Shivalkar PROC
; unsigned int parity = 0;
; while (x != 0)
; {
; parity ^= x;
; x >>= 1;
; }
; return (parity & 0x1);
xor eax, eax
test rcx, rcx
je SHORT Finished
Process:
xor eax, ecx
shr rcx, 1
jne SHORT Process
Finished:
and eax, 1
ret
Shreyas_Shivalkar ENDP
TypeIA 和 TypeIA_Tweaked 是来自 this answer, modified to support 64-bit values, and my tweaked version. They parallelize the operation, resulting in a significant speed improvement over the loop-through-each-bit strategy. The "tweaked" version is based on an optimization originally suggested by Mathew Hendry to Sean Eron Anderson's Bit Twiddling Hacks 的代码，并且确实比原来的 speed-up 少了一点。
unsigned int TypeIA(uint64 n)
{
n ^= n >> 32;
n ^= n >> 16;
n ^= n >> 8;
n ^= n >> 4;
n ^= n >> 2;
n ^= n >> 1;
return !((~n) & 1);
}
unsigned int TypeIA_Tweaked(uint64 n)
{
n ^= n >> 32;
n ^= n >> 16;
n ^= n >> 8;
n ^= n >> 4;
n &= 0xf;
return ((0x6996 >> n) & 1);
}
has_even_parity 基于 the accepted answer to that question，修改为支持 64 位值。我知道这会很慢，因为这是另一种 loop-through-each-bit 策略，但显然 有人 认为这是一个好方法。有趣的是，它实际上有多慢，甚至与我称之为“朴素”的方法相比，它本质上做同样的事情，但速度更快，使用 less-complicated 代码。
unsigned int has_even_parity(uint64 n)
{
uint64 count = 0;
uint64 b = 1;
for (uint64 i = 0; i < 64; ++i)
{
if (n & (b << i)) { ++count; }
}
return (count % 2);
}
has_even_parity_Tweaked 是上面的替代版本，它利用布尔值可以隐式转换为 0 和 1 的事实来节省 b运行ch。它比原来的要快得多, 在与“幼稚”方法相当的时间打卡：
unsigned int has_even_parity_Tweaked(uint64 n)
{
uint64 count = 0;
uint64 b = 1;
for (uint64 i = 0; i < 64; ++i)
{
count += static_cast<int>(static_cast<bool>(n & (b << i)));
}
return (count % 2);
}
现在我们进入正题。函数 GCC_builtin_parityll 包含 GCC 在您使用其 __builtin_parityll 内在函数时将发出的汇编代码。其他一些人建议您使用这个内在函数，我必须附和他们的支持。它的性能与我们迄今为止看到的最好的性能相当，并且它有几个额外的优点：（1）它使代码简单易读（比 C 版本更简单）； (2) 它可以移植到不同的体系结构，并且可以预期在那里也保持快速； (3) 随着 GCC 改进其实现，您的代码可能会通过简单的重新编译变得更快。您可以获得内联汇编的所有好处，没有任何缺点。
GCC_builtin_parityll PROC ; GCC's __builtin_parityll
mov edx, ecx
shr rcx, 32
xor edx, ecx
mov eax, edx
shr edx, 16
xor eax, edx
xor al, ah
setnp al
movzx eax, al
ret
GCC_builtin_parityll ENDP
PopCount 是我自己发明的优化实现。为了想出这个，我回过头来考虑我们实际上想做什么。 “奇偶校验”的定义是偶数个设置位。因此，可以简单地通过计算设置位的数量并测试该计数是偶数还是奇数来计算它。这是两个逻辑操作。幸运的是，在最近几代的 x86 处理器（Intel Nehalem 或 AMD Barcelona，以及更新的处理器）上，有一条指令计算设置位的数量——POPCNT（人口计数，或汉明权重）——它允许我们编写在两个操作中执行此操作的汇编代码。
（好吧，实际上是三个指令，因为在创建 a false dependency on its destination register 的某些微体系结构上 POPCNT 的实现中存在错误，并确保我们从中获得最大吞吐量代码，我们需要通过 pre-clearing 目标寄存器来打破这种依赖性。幸运的是，这是一个非常便宜的操作，通常可以通过寄存器重命名“免费”处理。）
PopCount PROC
xor eax, eax ; break false dependency
popcnt rax, rcx
and eax, 1
ret
PopCount ENDP
事实上，事实证明，当您以支持 POPCNT 的微体系结构为目标时，GCC 知道为 __builtin_parityll 内部函数准确发出此代码（否则，它使用下面显示的回退实现).正如您从基准测试中看到的那样，这是迄今为止最快的代码。这不是主要区别，因此除非您在一个紧密的循环中重复执行此操作，否则它不太重要，但这是一个可衡量的差异，并且大概您不会对此进行如此大的优化，除非您的探查器表明这是一个hot-spot.
但是 POPCNT 指令确实有在旧处理器上不可用的缺点，因此我还测量了代码的“后备”版本，该代码使用 universally-supported 序列进行人口计数] 指示。那就是 PopCount_Downlevel 函数，取自我的私人图书馆，最初改编自 this answer 和其他来源。
PopCount_Downlevel PROC
mov rax, rcx
shr rax, 1
mov rdx, 5555555555555555h
and rax, rdx
sub rcx, rax
mov rax, 3333333333333333h
mov rdx, rcx
and rcx, rax
shr rdx, 2
and rdx, rax
add rdx, rcx
mov rcx, 0FF0F0F0F0F0F0F0Fh
mov rax, rdx
shr rax, 4
add rax, rdx
mov rdx, 0FF01010101010101h
and rax, rcx
imul rax, rdx
shr rax, 56
and eax, 1
ret
PopCount_Downlevel ENDP
正如您从基准测试中看到的那样，此处所需的所有 bit-twiddling 指令都以性能为代价。它比 POPCNT 慢，但在所有系统上都受支持并且仍然相当快。如果您无论如何都需要位计数，这将是最好的解决方案，特别是因为它可以用纯 C 编写而无需求助于内联汇编，可能会产生更快的速度：
unsigned int PopCount_Downlevel(uint64 n)
{
uint64 temp = n - ((n >> 1) & 0x5555555555555555ULL);
temp = (temp & 0x3333333333333333ULL) + ((temp >> 2) & 0x3333333333333333ULL);
temp = (temp + (temp >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
temp = (temp * 0x0101010101010101ULL) >> 56;
return (temp & 1);
}
但是 运行 你自己的基准测试，看看你是否会更好地使用其他实现之一，比如 OriginalCCode，它简化了操作，因此需要更少的总指令。有趣的事实：Intel 的编译器 (ICC) 总是使用人口 count-based 算法来实现 __builtin_parityll；如果目标体系结构支持它，它会发出 POPCNT 指令，否则，它会使用与我在此处显示的基本相同的代码来模拟它。
或者，更好的是，只是忘记整个复杂的混乱，让你的编译器处理它。这就是 built-in 的用途，而正是为了这个目的。