Visual C++ x64 带进位加法

Question

由于Visual C++中x64架构无法使用内联汇编，而且似乎没有ADC的固有函数，如果我想编写一个带进位加法的函数并将其包含在C++命名空间中，该怎么办呢？请注意，模拟比较运算符不是一种选择，因为这个256兆字节的加法运算对性能至关重要。

- jnm2

---

告诉我们更多关于这个“256兆位加法”的信息。使用SIMD同时进行多个加法很可能会更快，即使考虑到进位需要作为额外步骤处理的情况。 - Ben Voigt

我已经做了那一部分的研究。请参见 https://dev59.com/_Gox5IYBdhLWcg3w9o2h。 - jnm2

@jnm2 - x64的方法似乎是编写单独的汇编代码，并从您的C++函数中调用它。汇编器已经是该软件包的一部分。 - Bo Persson

Answer 1

现在MSVC中有一个内置函数可以用于ADC： _addcarry_u64。以下是代码：

#include <inttypes.h>
#include <intrin.h>
#include <stdio.h>

typedef struct {
    uint64_t x1;
    uint64_t x2;
    uint64_t x3;
    uint64_t x4;
} uint256;

void add256(uint256 *x, uint256 *y) {
    unsigned char c = 0;
    c = _addcarry_u64(c, x->x1, y->x1, &x->x1);
    c = _addcarry_u64(c, x->x2, y->x2, &x->x2);
    c = _addcarry_u64(c, x->x3, y->x3, &x->x3);
    _addcarry_u64(c, x->x4, y->x4, &x->x4);
}

int main() {
    //uint64_t x1, x2, x3, x4;
    //uint64_t y1, y2, y3, y4;
    uint256 x, y;
    x.x1 = x.x2 = x.x3 = -1; x.x4 = 0;
    y.x1 = 2; y.x2 = y.x3 = y.x4 = 0;

    printf(" %016" PRIx64 "%016" PRIx64 "%016" PRIx64 "%016" PRIx64 "\n", x.x4, x.x3, x.x2, x.x1);
    printf("+");
    printf("%016" PRIx64 "%016" PRIx64 "%016" PRIx64 "%016" PRIx64 "\n", y.x4, y.x3, y.x2, y.x1);
    add256(&x, &y);
    printf("=");
    printf("%016" PRIx64 "%016" PRIx64 "%016" PRIx64 "%016" PRIx64 "\n", x.x4, x.x3, x.x2, x.x1);
}

从Visual Studio Express 2013生成以下汇编输出：

mov rdx, QWORD PTR x$[rsp]
mov r8, QWORD PTR x$[rsp+8] 
mov r9, QWORD PTR x$[rsp+16]
mov rax, QWORD PTR x$[rsp+24]
add rdx, QWORD PTR y$[rsp]
adc r8, QWORD PTR y$[rsp+8]
adc r9, QWORD PTR y$[rsp+16]
adc rax, QWORD PTR y$[rsp+24]

该代码段包含一个 add 和三个 adc，这是预期的。

编辑:

对于 _addcarry_u64 的功能，存在一些混淆。如果您查看我在此答案开头提供的链接的 Microsoft 文档，它将说明它不需要任何特殊的硬件支持。这会产生 adc 并且可以在所有 x86-64 处理器上运行 (即使更老的处理器也能运行 _addcarry_u32)。它在我测试过的 Ivy Bridge 系统上运行良好。

然而，_addcarryx_u64 需要 adx (根据 MSFT 的文档)，并且它确实无法在我的 Ivy Bridge 系统上运行。

- Z boson

---

此答案需要免责声明，此指令仅适用于第四代酷睿处理器（Haswell及以上）。再过5至10年，以及一个支持电话号码，您才能盲目依赖其可用性。 - Hans Passant

@HansPassant 我无法确认。你有参考资料吗？ - jnm2

@HansPassant，你错了，这在我的Ivy Bridge系统上运行良好，而且在所有x86-64处理器上都应该可以正常工作。你读了我的答案吗？你注意到编译器生成的是adc而不是adcx吗？我更新了答案，这样你甚至可以在自己的系统上测试它（我假设你可以在Broadwell之前找到一个）并查看生成的汇编代码。现在我编辑了我的问题，你可以给我点赞了。这是你能做的最少的事情。 - Z boson

没关系，我说错了也无所谓，这不是我的问题。更重要的是，由你来记录“第四代酷睿”系列处理器的具体型号。抱歉，这并不包括你提到的型号，因此您将得到旧指令。看来你暂时还不能选择Haswell处理器了。顺便说一下，这是非常好的处理器。 - Hans Passant

@HansPassant，ADX指令是添加到Broadwell而不是Haswell的。我拥有一个Haswell处理器（但没有Broadwell），但这不是我测试的对象。我记录哪些处理器是“第4代Core”是我的责任。这与我的答案无关。也许英特尔的文档有误？ - Z boson

@HansPassant，英特尔已经更新了他们的文档，包括白皮书和Intel intrinsic guide。所以我是正确的。他们的文档是错误的。_addcarry_u64只会产生adc。为什么你要相信文档比汇编更多呢？现在是时候取消你的反对票并支持我的观点了。 - Z boson

Answer 2

VS2010内置支持编译和链接使用MASM（ml64.exe）翻译的汇编代码。您只需要跳过一些步骤即可启用它：

• 在“解决方案资源管理器”窗口中右键单击项目，选择“生成自定义”，勾选“masm”。
• 选择“项目+添加新项”，选择C++文件模板，但将其命名为something.asm。
• 确保项目具有x64平台目标。选择“生成+配置管理器”，在“活动解决方案平台”组合框中选择“x64”。如果缺少，请选择<New>并从第一个组合框中选择x64。如果缺少，则必须重新运行安装程序并添加对64位编译器的支持。

使用MASM语法编写汇编代码，参考此处。快速入门教程在此。

汇编代码的框架如下：

.CODE
PUBLIC Foo
Foo PROC
  ret                    ; TODO: make useful
Foo ENDP
END

这段代码可以在C++中被调用：

extern "C" void Foo();

int main(int argc, char* argv[])
{
    Foo();
    return 0;
}

完整的调试支持是可用的，通常您至少需要使用Debug + Windows + Registers窗口。

- Hans Passant

---

在这种情况下，最理想的解决方案将是内联函数（内联汇编）。使用汇编器并链接目标文件不会做到这一点，而MSVC中的64位代码不允许内联汇编。因此，这意味着OP必须编写很多其他函数（编译器可能已经做得很好了）作为汇编语言，以避免函数调用。 - Z boson

Answer 3

我使用了一个unsigned long long数组来实现256位整数，并使用x64汇编语言实现了带进位的加法。以下是C++调用者的代码：

#include "stdafx.h"

extern "C" void add256(unsigned long long *a, unsigned long long * b, unsigned long long *c);

int _tmain(int argc, _TCHAR* argv[])
{
    unsigned long long a[4] = {0x8000000000000001, 2, 3, 4};
    unsigned long long b[4] = {0x8000000000000005, 6, 7, 8};
    unsigned long long c[4] = {0, 0, 0, 0};
    add256(a, b, c); // c[] == {6, 9, 10, 12};
    return 0;
}

add256 是用汇编语言实现的：

    ; void add256(unsigned long long *a, unsigned long long * b, unsigned long long *c)

.CODE
PUBLIC add256
add256 PROC

    mov                 qword ptr [rsp+18h],r8    
    mov                 qword ptr [rsp+10h],rdx    
    mov                 qword ptr [rsp+8],rcx    
    push                rdi    

    ; c[0] = a[0] + b[0];

    mov                 rax,qword ptr 16[rsp]
    mov                 rax,qword ptr [rax]    
    mov                 rcx,qword ptr 24[rsp]
    add                 rax,qword ptr [rcx]    
    mov                 rcx,qword ptr 32[rsp]
    mov                 qword ptr [rcx],rax    

    ; c[1] = a[1] + b[1] + CARRY;

    mov                 rax,qword ptr 16[rsp]
    mov                 rax,qword ptr [rax+8]    
    mov                 rcx,qword ptr 24[rsp]
    adc                 rax,qword ptr [rcx+8]    
    mov                 rcx,qword ptr 32[rsp]
    mov                 qword ptr [rcx+8],rax    

    ; c[2] = a[2] + b[2] + CARRY;

    mov                 rax,qword ptr 16[rsp]
    mov                 rax,qword ptr [rax+10h]    
    mov                 rcx,qword ptr 24[rsp]
    adc                 rax,qword ptr [rcx+10h]    
    mov                 rcx,qword ptr 32[rsp]
    mov                 qword ptr [rcx+10h],rax    

    ; c[3] = a[3] + b[3] + CARRY;

    mov                 rax,qword ptr 16[rsp]
    mov                 rax,qword ptr [rax+18h]    
    mov                 rcx,qword ptr 24[rsp]
    adc                 rax,qword ptr [rcx+18h]    
    mov                 rcx,qword ptr 32[rsp]
    mov                 qword ptr [rcx+18h],rax    

    ; }

    pop                 rdi    
    ret    

    add256              endp

    end                        

我知道你表示你不想要一个模拟带进位解决方案，而是想要一个高性能的解决方案，但是，你仍然可以考虑以下仅使用C++的解决方案，它有一种很好的模拟256位数字的方法：

#include "stdafx.h"

int _tmain(int argc, _TCHAR* argv[])
{
    unsigned long long a[4] = {0x8000000000000001, 2, 3, 4};
    unsigned long long b[4] = {0x8000000000000005, 6, 7, 8};
    unsigned long long c[4] = {0, 0, 0, 0};
    c[0] = a[0] + b[0]; // 6
    c[1] = a[1] + b[1] + (c[0] < a[0]); // 9
    c[2] = a[2] + b[2] + (c[1] < a[1]); // 10
    c[3] = a[3] + b[3] + (c[2] < a[2]); // 12
    return 0;
}

- Stephen Quan

---

抱歉晚了，但是C++的解决方案不正确。为了简化问题，考虑a=01，b=11，进位=1，则c=01，进位=1，但是c<a是错误的。 - knivil