在C中使用内联汇编进行位奇偶校验？
我正在尝试计算大量uint64的位奇偶校验 。 比特奇偶校验是指接受uint64的函数，如果设置的比特数是偶数则输出0，否则为1。
目前我正在使用以下function（@Troyseph，在这里找到）：
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
它利用了机器的奇偶校验标志 。 但我不能让它与我的C程序一起工作（我知道旁边没有汇编）。
问题 如何在C源文件中包含上面（或类似）代码作为内联汇编，以便相反运行parity64()函数？
（我在Intel Xeon Haswell上使用GCC和64位Ubuntu 14）
如果有任何帮助，可在以下例程中调用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上的两个向量的“点积”，即GF（2）。）
您将不得不使用扩展内联汇编（这是一个gcc扩展）来获得类似的效果。
您的parity64function可以更改如下 –
uint parity64(uint64 n){ uint result = 0; __asm__("addq $0, %0" : : "r"(n) :); __asm__("jnp 1f"); __asm__("movl $1, %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（）。 看到：
这可能听起来有点刺耳，但我相信需要说。 请不要亲自接受; 我并不是说这是一种侮辱，特别是因为你已经承认你“在没有集会的情况下知道”。 但如果您认为这样的代码：
CheckParity PROC mov rax, 0 add rcx, 0 jnp jmp_over mov rax, 1 jmp_over: ret CheckParity ENDP
将击败C编译器生成的内容 ，然后你真的没有使用内联汇编的业务。 在这5行代码中，我看到2条指令显然是次优的。 它可以通过稍微重写它来优化：
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
或者，如果您有随机输入值可能会阻止分支预测器 （ 即 ，输入值的奇偶校验没有可预测的模式），那么删除分支将更快，将其写为：
xor eax, eax test ecx, ecx setp al ret
或者也许等价（在某些处理器上会更快，但不一定全部）：
xor eax, eax test ecx, ecx mov ecx, 1 cmovp eax, ecx ret
鉴于我现有的x86 ISA知识以及我之前的基准测试，这些只是我能够看到的改进。 但是，任何人都被愚弄，这无疑是最快的代码，因为（借用迈克尔·阿布拉什），“没有最快的代码” – 有些人几乎总能让它变得更快。
当你是一个专家的汇编语言程序员和一个关于x86 ISA的复杂性的向导时，使用内联汇编有足够的问题 。 优化器现在非常好，这意味着真正的大师很难产生更好的代码（尽管当然不是不可能）。 它还需要值得信赖的基准测试来validation您的假设并确认您的优化内联汇编实际上更快。 永远不要让自己使用内联汇编来超越编译器的优化器而不运行良好的基准测试 。 我发现你的问题没有证据表明你做过这样的事情。 我在这里推测，但看起来你看到代码是用汇编编写的，并且假设它意味着它会更快。 这种情况很少发生。 C编译器最终也会发出汇编语言代码，并且它通常比我们人类能够生成的更优化，因为时间和资源有限，而且有限的专业知识更少。
在这种特殊情况下，有一种观点认为内联汇编将比C编译器的输出更快，因为C编译器将无法智能地使用x86架构的内置奇偶校验标志（PF）。 你可能是对的，但这是一个非常不稳定的假设，远非普遍化。 正如我所说，优化编译器现在非常智能，并且它们会针对特定体系结构进行优化（假设您指定了正确的选项），因此优化器会发出使用PF的代码并不会让我感到惊讶。 您必须查看反汇编才能确定。
作为我的意思的一个例子，考虑x86提供的高度专业化的BSWAP指令。 您可能天真地认为内联汇编需要利用它，但事实并非如此。 以下C代码在几乎所有主要编译器上编译成BSWAP指令：
uint32 SwapBytes(uint32 x) { return ((x << 24) & 0xff000000 ) | ((x << 8) & 0x00ff0000 ) | ((x >> 8) & 0x0000ff00 ) | ((x >> 24) & 0x000000ff ); }
即使不是更好，性能也是等效的，因为优化器对代码的作用有了更多的了解。 实际上，这种forms对内联汇编的一个主要好处是编译器可以使用此代码执行常量折叠（ 即 ，使用编译时常量调用时）。 此外，代码更易读（至少对于C程序员而言）， 更容易出错，并且比使用内联汇编更容易维护。 哦，如果您想要定位x86以外的架构，我是否提到它的合理可移植性？
我知道我已经做了很多这方面的工作，我希望你能理解我说这是一个喜欢编写高度调整的汇编代码的人，这些代码优于编译器的性能优化器。 但每次我这样做，都只是：挑战，伴随着牺牲。 它不是灵丹妙药，你需要记住检查你的假设，包括：
- 这个代码实际上是我的应用程序的瓶颈，这样优化它甚至可以产生任何明显的差异吗？
- 优化器实际上是否为我编写的代码发出了次优的机器语言指令？
- 我天真地认为是次优的我错了吗？ 也许优化器比我对目标体系结构的了解更多， 看起来像慢速或次优代码实际上更快。 （请记住，较少的代码不一定更快。）
- 我是否在一个有意义的，真实的基准测试中进行了测试，并certificate编译器生成的代码很慢并且我的内联汇编实际上更快？
- 是否绝对没有办法调整C代码以说服优化器发出更接近，等于甚至优于内联汇编性能的更好的机器代码？
为了回答其中一些问题，我设置了一个基准。 （使用MSVC，因为这是我的方便;如果你的目标是GCC，最好使用那个编译器，但我们仍然可以得到一个大概。我使用并推荐Google的基准测试库 。）我立刻遇到了问题。 看，我首先在“调试”模式下运行我的基准测试，编译中的断言validation我的“调整”/“优化”代码实际上为所有测试用例生成与原始代码相同的结果（可能已知是工作/正确的）。 在这种情况下，断言立即被解雇。 事实certificate，用汇编语言编写的CheckParity例程并没有返回与用C编写的parity64例程相同的结果！ 嗯，哦。 那么，这是我们需要添加到上面列表的另一个项目：
- 我确保我的“优化”代码返回正确的结果吗？
这个特别重要，因为如果你做错了也很容易做出更快的事情。 :-)我开玩笑，但并不完全，因为我在追求更快的代码时多次这样做。
我相信Michael Petch已经指出了出现差异的原因：在x86实现中，奇偶校验标志（PF）只关注低字节中的位，而不是整个值。 如果这就是你所需要的，那就太好了。 但即使这样，我们也可以回到C代码并进一步优化它以减少工作量，这将使其更快 – 或许比汇编代码更快，从而消除了内联汇编所具有的一个优势。
现在，让我们假设您需要完整值的奇偶校验，因为这是您正在使用的原始实现，并且您只是尝试在不改变其行为的情况下使其更快。 因此，在我们甚至可以进行有意义的基准测试之前，我们需要修复汇编代码的逻辑。 幸运的是，由于我迟到了这个答案， Ajay Brahmakshatriya （与其他人合作）已经完成了这项工作，为我节省了额外的努力。
……除了，不完全。 当我第一次起草这个答案时，我的基准测试显示他的“调整”代码的第9版 仍然没有产生与原始C函数相同的结果，因此根据我们的测试用例它是不合适的。 你在评论中说他的代码“适用于你” ，这意味着要么（A）原始的C代码正在做额外的工作，使它不必要地慢，这意味着你可以调整它以在自己的游戏中击败内联汇编或者更糟糕的是，（B）你没有足够的测试用例，新的“优化”代码实际上是一个等待的错误。 从那时起， Ped7g提出了一些修复 ，它们都修复了导致返回错误结果的错误，并进一步改进了代码。 这里所需的输入量以及他所经历的草稿数量应该certificate编写正确的内联汇编以击败编译器的难度。 但我们还没有完成！ 他的内联汇编仍然写得不正确。 SETcc指令需要一个8位寄存器作为它的操作数，但是他的代码不使用寄存器说明符来请求它，这意味着代码要么不能编译（因为Clang足够智能来检测这个错误），要么编译GCC但不会正确执行，因为该指令具有无效操作数。
我确信您对测试的重要性了吗？ 我会坚持信念，然后转向基准测试部分。 基准测试结果使用了Ajay代码的最终草案，Ped7g的改进以及我的额外调整。 我还比较了你链接的那个问题的一些其他解决方案，修改了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
现在，请记住这些是用于随机生成的64位输入值，这会中断分支预测。 如果您的输入值以可预测的方式偏向于奇偶校验或非奇偶校验，则分支预测器将对您有效，而不是对您有用，并且某些方法可能更快。 这强调了针对模拟真实用例的数据进行基准测试的重要性。 （也就是说，当我编写通用库函数时，我倾向于优化随机输入，平衡大小和速度。）
注意原始C函数与其他函数的比较。 我要声称进一步优化它可能是浪费大量时间的浪费。 所以希望你能从这个答案中学到一些更通用的东西，而不是只是向下滚动来复制粘贴代码片段。 🙂
Naivefunction是一个完全未经优化的健全性检查，用于确定平价，取自此处 。 我用它来validation你原来的C代码，并为基准测试提供基线。 因为它逐个循环遍历每个位，所以它相对较慢，如预期的那样：
unsigned int Naive(uint64 n) { bool parity = false; while (n) { parity = !parity; n &= (n - 1); } return parity; }
OriginalCCode正是它听起来的样子 – 它是您拥有的原始C代码，如问题所示。 请注意它是如何与Ajay Brahmakshatriya的内联汇编代码的调整/修正版本完全同时发布的！ 现在，由于我在MSVC中运行此基准测试，它不支持64位构建的内联汇编，我不得不使用包含该函数的外部汇编模块，并从那里调用它，这引入了一些额外的开销。 使用GCC的内联汇编，编译器可能已经能够内联代码，从而省略函数调用。 因此，在GCC上，您可能会看到内联汇编版本的速度提高了一纳秒（或者可能没有）。 这值得吗？ 你是法官。 作为参考，这是我为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的函数来自他的答案 ，这只是循环到每位主题的变体，并且与预期一致，缓慢：
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是这个答案的代码，修改为支持64位值，以及我的调整版本。 它们使操作并行化，从而显着提高了逐位循环策略的速度。 “调整”的版本是基于Mathew Hendry最初为Sean Eron Anderson的Bit Twiddling Hacks提出的优化，并且确实比我们在原版上加速了一点。
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基于该问题的已接受答案 ，已修改为支持64位值。 我知道这会很慢，因为它是另一种循环每位策略，但显然有人认为这是一种很好的方法。 有趣的是看到它实际上有多慢，甚至与我称之为“天真”的方法相比，它本质上是相同的，但更快，代码更简单。
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这一事实来保存分支。它比原始版本快得多，在时间上与“天真”方法相当：
unsigned int has_even_parity_Tweaked(uint64 n) { uint64 count = 0; uint64 b = 1; for (uint64 i = 0; i < 64; ++i) { count += static_cast(static_cast(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 （人口数，或汉明重量） - 这使我们能够编写在两个操作中执行此操作的汇编代码。
（好吧，实际上是三个指令，因为POPCNT在某些微体系结构上的实现存在一个错误，它会对其目标寄存器产生错误依赖 ，并且为了确保我们从代码中获得最大吞吐量，我们需要通过预先打破这种依赖性来打破这种依赖性。清除目标寄存器。幸运的是，这是一个非常便宜的操作，通常可以通过寄存器重命名来“免费”处理。）
PopCount PROC xor eax, eax ; break false dependency popcnt rax, rcx and eax, 1 ret PopCount ENDP
事实上，事实certificate，当您定位支持POPCNT的微体系结构时，GCC知道为__builtin_parityll内在函数准确发出此代码。 否则，它使用上面显示的回退实现。 从基准测试中可以看出，这是迄今为止最快的代码。 这不是一个主要的区别，所以除非你在一个紧密的循环中重复这样做，否则它不太重要，但它是一个可衡量的差异，并且可能你不会如此大量地优化它，除非你的分析器表明这是一个热点。
但POPCNT指令确实有缺点，不能在旧处理器上使用，所以我还测量了一个代码的“后备”版本，它使用一系列普遍支持的指令进行人口统计。 这是PopCount_Downlevel函数，取自我的私人库，最初改编自这个答案和其他来源。
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 ，它简化了操作，因此需要更少的总指令。 有趣的事实：英特尔的编译器（ICC）总是使用基于人口计数的算法来实现__builtin_parityll ; 如果目标体系结构支持它，它会发出POPCNT指令，否则，它使用与我在此处显示的代码基本相同的代码来模拟它。
或者，更好的是，忘记整个复杂的混乱，让你的编译器处理它。 这就是内置插件的用途，而且正是出于这个目的。
如何在C源文件中包含上面（或类似）代码作为内联汇编，以便相反运行
parity64()函数？
这是一个XY问题 …你认为你需要内联该程序集以从中受益，所以你问到如何内联它 …但你不需要内联它 。
您不应该将汇编包含在C源代码中，因为在这种情况下您不需要 ，并且更好的替代方法（在可移植性和可维护性方面）是将两个源代码分开，单独编译它们使用链接器链接它们 。
在parity64.c你应该有你的可移植版本（带有名为bool CheckParity(size_t result)的包装器），你可以在非x86 / 64情况下默认使用它。
您可以将其编译为对象文件，如下所示： gcc -c parity64.c -o parity64.o
…然后将程序集生成的目标代码与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
…然后链接生成的对象代码如下： gcc bindot.c parity64.o -o bindot
类似地，如果你想使用__builtin_parityl （正如hdantes回答所建议的那样 ，你可以（并且应该）再次将这些代码与可移植代码分开（在同一个地方保留其他gcc / x86优化 ）。在parity64_x86.c你可能有：
bool CheckParity(size_t result) { return __builtin_parityl(result); }
要编译它，您的命令将是： gcc -c parity64_x86.c -o parity64.o
…然后链接生成的对象代码如下： 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); }
您可以构建它并将其链接到任何上述parity64.o版本，如下所示： gcc bindot.c parity64.o -o bindot ...
当你有时间时，我强烈建议您阅读编译器的手册 ...