使用C进行内联汇编以实现位奇偶校验? [英] Working inline assembly in C for bit parity?

问题描述

我正在尝试计算大量uint64的位奇偶校验.所谓位奇偶校验，是指一个接受uint64并在设置的位数为偶数时输出0的函数，否则为1.

I'm trying to compute the bit parity of a large number of uint64's. By bit parity I mean a function that accepts a uint64 and outputs 0 if the number of set bits is even, and 1 otherwise.

当前，我正在使用以下功能(@Troyseph提供，位于

Currently I'm using the following function (by @Troyseph, found here):

uint parity64(uint64 n){
  n ^= n >> 1;
  n ^= n >> 2;
  n = (n & 0x1111111111111111) * 0x1111111111111111;
  return (n >> 60) & 1;
}

同一SO页面具有以下汇编例程(通过@papadp):

The same SO page has the following assembly routine (by @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程序一起使用(我几乎没有汇编程序就知道).

which takes advantage of the machine's parity flag. But I cannot get it to work with my C program (I know next to no assembly).

问题.如何在C源文件中将上述(或类似)代码作为内联程序集包含在内，以使parity64()函数代替它运行?

Question. 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?

(我将GCC与Intel Xeon Haswell上的64位Ubuntu 14一起使用)

(I'm using GCC with 64-bit Ubuntu 14 on an Intel Xeon Haswell)

如果有帮助，可以在以下例程中调用parity64()函数:

In case it's of any help, the parity64() function is called inside the following routine:

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).)

(This is supposed to be the "dot product" of two vectors over the field Z/2Z, aka. GF(2).)

推荐答案

您将必须使用扩展的嵌入式程序集(这是gcc扩展名)才能获得类似的效果.

You will have to use extended inline assembly (which is a gcc extension) to get the similar effect.

您的parity64函数可以进行以下更改-

Your parity64 function can be changed as follows -

uint parity64_unsafe_and_broken(uint64 n){
    uint result = 0;
    __asm__("addq $0, %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 $1, %0" : "=r"(result) : : );
    __asm__("1:");
    return result;
}

但是正如@MichaelPetch所评论的那样，仅在低8位上计算奇偶校验标志.因此，如果您的n小于255，这将对您有用.对于更大的数字，您将必须使用问题中提到的代码.

But as commented by @MichaelPetch the parity flag is computed only on the lower 8 bits. So this will work for your if your n is less than 255. For bigger numbers you will have to use the code you mentioned in your question.

要使其适用于64位，您可以通过

To get it working for 64 bits you can collapse the parity of the 32 bit integer into single byte by doing

n = (n >> 32) ^ n;
n = (n >> 16) ^ n;
n = (n >> 8) ^ n;

此代码必须仅在函数开始时才进行汇编.

This code will have to be just at the start of the function before the assembly.

您将必须检查它如何影响性能.

You will have to check how it affects the performance.

我能得到的最优化的是

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进行内联汇编以实现位奇偶校验?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！