Ответ 1
Для этого существует внутреннее значение: _addcarry_u64. Тем не менее, только Visual Studio и ICC (по крайней мере, VS 2013 и 2015 и ICC 13 и ICC 15) делают это эффективно. Clang 3.7 и GCC 5.2 все еще не создают эффективный код с этим внутренним.
Кроме того, Clang имеет встроенный модуль, который можно было бы подумать, __builtin_addcll, но он также не создает эффективный код.
Причина, по которой Visual Studio делает это, заключается в том, что она не позволяет встроенную сборку в 64-разрядном режиме, поэтому компилятор должен предоставить способ сделать это с помощью встроенного (хотя Microsoft не спеша это реализовала).
Поэтому в Visual Studio используйте _addcarry_u64. При использовании ICC _addcarry_u64 или встроенной сборки. С Clang и GCC используйте встроенную сборку.
Заметим, что с микроархитектуры Broadwell есть две новые инструкции: adcx и adox, с которыми вы можете получить доступ с _addcarryx_u64 внутренний. Документация Intel для этих встроенных функций отличалась от сборки, созданной компилятором, но, похоже, их документация правильная. Тем не менее, Visual Studio по-прежнему только создает adcx с _addcarryx_u64, тогда как ICC создает как adcx, так и adox с этим внутренним. Но хотя ICC создает обе команды, он не создает наиболее оптимальный код (ICC 15), и поэтому встроенная сборка по-прежнему необходима.
Лично я считаю, что для этого требуется нестандартная функция C/С++, такая как встроенная сборка или внутренняя среда, это слабость C/С++, но другие могут не согласиться. Инструкция adc была в наборе команд x86 с 1979 года. Я бы не затаил дыхание компиляторами C/С++, которые могли бы оптимально определить, когда вы хотите adc. Конечно, они могут иметь встроенные типы, такие как __int128, но в тот момент, когда вы хотите, чтобы более крупный тип, который не был встроен, вы должны использовать некоторые нестандартные функции C/С++, такие как встроенная сборка или встроенные функции.
В терминах встроенного кода сборки для этого я уже опубликовал решение для 256-битного добавления для восьми 64-битных целых чисел в регистре в многословном добавлении с использованием флага переноса.
Вот код, который был отправлен повторно.
#define ADD256(X1, X2, X3, X4, Y1, Y2, Y3, Y4) \
__asm__ __volatile__ ( \
"addq %[v1], %[u1] \n" \
"adcq %[v2], %[u2] \n" \
"adcq %[v3], %[u3] \n" \
"adcq %[v4], %[u4] \n" \
: [u1] "+&r" (X1), [u2] "+&r" (X2), [u3] "+&r" (X3), [u4] "+&r" (X4) \
: [v1] "r" (Y1), [v2] "r" (Y2), [v3] "r" (Y3), [v4] "r" (Y4))
Если вы хотите явно загрузить значения из памяти, вы можете сделать что-то вроде этого
//uint64_t dst[4] = {1,1,1,1};
//uint64_t src[4] = {1,2,3,4};
asm (
"movq (%[in]), %%rax\n"
"addq %%rax, %[out]\n"
"movq 8(%[in]), %%rax\n"
"adcq %%rax, 8%[out]\n"
"movq 16(%[in]), %%rax\n"
"adcq %%rax, 16%[out]\n"
"movq 24(%[in]), %%rax\n"
"adcq %%rax, 24%[out]\n"
: [out] "=m" (dst)
: [in]"r" (src)
: "%rax"
);
Это производит почти идентичную сборку, как из следующей функции в ICC
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);
}
У меня ограниченный опыт работы с встроенной сборкой GCC (или встроенной сборкой в целом - я обычно использую ассемблер, такой как NASM), поэтому, возможно, есть более сложные встроенные сборочные решения.
Итак, я ищу код, который я мог бы обобщить на любую длину
Чтобы ответить на этот вопрос, вот еще одно решение, использующее мета-программирование шаблонов. Я использовал этот трюк для разворачивания цикла. Это создает оптимальный код с ICC. Если Clang или GCC когда-либо реализовали _addcarry_u64 эффективно, это было бы хорошим общим решением.
#include <x86intrin.h>
#include <inttypes.h>
#define LEN 4 // N = N*64-bit add e.g. 4=256-bit add, 3=192-bit add, ...
static unsigned char c = 0;
template<int START, int N>
struct Repeat {
static void add (uint64_t *x, uint64_t *y) {
c = _addcarry_u64(c, x[START], y[START], &x[START]);
Repeat<START+1, N>::add(x,y);
}
};
template<int N>
struct Repeat<LEN, N> {
static void add (uint64_t *x, uint64_t *y) {}
};
void sum_unroll(uint64_t *x, uint64_t *y) {
Repeat<0,LEN>::add(x,y);
}
Сборка с ICC
xorl %r10d, %r10d #12.13
movzbl c(%rip), %eax #12.13
cmpl %eax, %r10d #12.13
movq (%rsi), %rdx #12.13
adcq %rdx, (%rdi) #12.13
movq 8(%rsi), %rcx #12.13
adcq %rcx, 8(%rdi) #12.13
movq 16(%rsi), %r8 #12.13
adcq %r8, 16(%rdi) #12.13
movq 24(%rsi), %r9 #12.13
adcq %r9, 24(%rdi) #12.13
setb %r10b
Мета-программирование является основной особенностью ассемблеров, поэтому слишком плохо C и С++ (за исключением метапрограмм метапрограмм шаблонов) не имеют решения для этого (язык D).
Встроенная сборка, в которой я использовал выше, которая ссылалась на память, вызывала некоторые проблемы в функции. Вот новая версия, которая, кажется, работает лучше
void foo(uint64_t *dst, uint64_t *src)
{
__asm (
"movq (%[in]), %%rax\n"
"addq %%rax, (%[out])\n"
"movq 8(%[in]), %%rax\n"
"adcq %%rax, 8(%[out])\n"
"movq 16(%[in]), %%rax\n"
"addq %%rax, 16(%[out])\n"
"movq 24(%[in]), %%rax\n"
"adcq %%rax, 24(%[out])\n"
:
: [in] "r" (src), [out] "r" (dst)
: "%rax"
);
}