Сборка АЦП (Добавить с переносом) в C++
Есть инструкция по сборке ADC, Я нашел это означает "Добавить с переносом". Но я не знаю, что это значит. Или как написать эту инструкцию на C++. И я знаю, что это не то же самое, что ADD, Поэтому делать простое суммирование не правильно.
ИНФОРМАЦИЯ:
Скомпилировано в Windows. Я использую 32-битную установку Windows. Мой процессор - Core 2 Duo от Intel.
8 ответов
ADC такой же, как ADD, но добавляет дополнительный 1, если установлен флаг переноса процессора.
Язык C++ не имеет никакого понятия флага переноса, поэтому создание встроенной функции-оболочки вокруг ADC инструкция неуклюжа. Однако Intel все равно сделала это: unsigned char _addcarry_u32 (unsigned char c_in, unsigned a, unsigned b, unsigned * out);, В последний раз я проверял, что gcc плохо справился с этим (сохранив результат переноса в целочисленный регистр вместо того, чтобы оставить его в CF), но, надеюсь, собственный компилятор Intel справится с этим лучше.
См. Также вики-тег x86 для документации по сборке.
Компилятор будет использовать ADC для вас при добавлении целых чисел шире, чем один регистр, например, при добавлении int64_t в 32-битном коде, или __int128_t в 64-битном коде.
#include <stdint.h>
#ifdef __x86_64__
__int128_t add128(__int128_t a, __int128_t b) { return a+b; }
#endif
# clang 3.8 -O3 for x86-64, SystemV ABI.
# __int128_t args passed in 2 regs each, and returned in rdx:rax
add rdi, rdx
adc rsi, rcx
mov rax, rdi
mov rdx, rsi
ret
вывод asm из проводника компилятора Godbolt. лязг-х -fverbose-asm не очень хорошо, но GCC 5.3 / 6.1 тратит впустую два mov инструкции, так что это менее читабельно.
Тем не менее, процессор Intel имеет специальную инструкцию под названием adc. Эта команда ведет себя так же, как команда добавления. Единственная дополнительная вещь - то, что это также добавляет флаг переноса значения. Таким образом, это может быть очень удобно для добавления больших целых чисел. Предположим, вы хотите добавить 32-разрядные целые числа с 16-разрядными регистрами. Как мы можем сделать это? Ну, скажем, первое целое число содержится в регистровой паре DX:AX, а второе - в BX:CX. Вот как:
add ax, cx adc dx, bxАх, во-первых, младший 16-бит добавляется с помощью add ax, cx. Затем старшее 16-битное значение добавляется с помощью adc вместо add. Это связано с тем, что: при переполнении бит переноса автоматически добавляется в старший 16-разрядный бит. Так что, не громоздкая проверка. Этот метод может быть расширен до 64 бит и т. Д. Обратите внимание: если 32-разрядное целочисленное сложение тоже переполняется при старшем 16-разрядном, результат будет неправильным и установлен флаг переноса, например, Добавление 5 миллиардов до 5 млрд.
Все с этого момента, помните, что это в значительной степени попадает в зону определенного поведения реализации.
Вот небольшой пример, который работает для VS 2010 (32-разрядная, WinXp)
Предостережение: $7.4/1- "Объявление asm условно поддерживается; его значение определяется реализацией. [Примечание: Обычно оно используется для передачи информации через реализацию ассемблеру. - Конечное примечание]"
int main(){
bool carry = false;
int x = 0xffffffff + 0xffffffff;
__asm {
jc setcarry
setcarry:
mov carry, 1
}
}
Поведение АЦП можно моделировать как на C, так и на C++. В следующем примере добавляются два числа (хранятся как массивы без знака, так как они слишком велики, чтобы поместиться в один без знака).
unsigned first[10];
unsigned second[10];
unsigned result[11];
.... /* first and second get defined */
unsigned carry = 0;
for (i = 0; i < 10; i++) {
result[i] = first[i] + second[i] + carry;
carry = (first[i] > result[i]);
}
result[10] = carry;
Надеюсь это поможет.
В x86-64 инструкция ADD добавляет два 64-битных целых числа:add rax, rbxделаетrax = rax + rbx.
Он также устанавливает флаг переноса в 1, когда произошло беззнаковое переполнение (= когда результат не умещается в 64 бита), в противном случае он устанавливает флаг переноса в 0.
В C++ вы можете моделировать ADD следующим образом:
uint64_t a, b;
bool carry;
a += b;
carry = (a < b); // a+b can't be smaller than b: there must have been an overflow
Инструкция ADC аналогична ADD, но добавляет к результату флаг переноса:
adc rax, rbxделаетrax = rax + rbx + carry_flag.
Он также устанавливает флаг переноса, если произошло беззнаковое переполнение.
В С++:
uint64_t tmp = b + carry;
a += tmp;
carry = (tmp < carry) + (a < tmp); // only one overflow can happen
Инструкции ADD и ADC можно использовать для сложения больших целых чисел (с n «цифрами»).
Используйте ADD для младших цифр, затем используйте ADC ( n – 1) раз, чтобы сложить остальные цифры.
Это « алгоритм сложения учебников ».
Например, добавление 256-битных больших целых чисел с четырьмя 64-битными «цифрами»:
mov rax, [rsi] ; load the least significant source digit
mov rbx, [rsi + 8] ; ...
mov rcx, [rsi + 16]
mov rdx, [rsi + 24]
add [rdi], rax ; add it to the least significant destination digit
adc [rdi + 8], rbx ; ... propagate carry up
adc [rdi + 16], rcx
adc [rdi + 24], rdx
Последние версииclangКомпилятор может распознавать сложение больших целых чисел и использовать ADD/ADC для его реализации .
constexpr uint64_t n = 4;
uint64_t dst[n], src[n];
// Add src to dst.
uint64_t carry = 0;
for (int i = 0; i < n; i++) {
uint64_t tmp = src[i] + carry;
dst[i] += tmp;
carry = (tmp < carry) + (dst[i] < tmp);
}
В этом есть ошибка. Попробуйте этот ввод:
unsigned first[10] = {0x00000001};
unsigned second[10] = {0xffffffff, 0xffffffff};
Результат должен быть {0, 0, 1, ...}, но результат {0, 0, 0, ...}
Изменение этой строки:
carry = (first[i] > result[i]);
к этому:
if (carry)
carry = (first[i] >= result[i]);
else
carry = (first[i] > result[i]);
исправляет это.
Это мой самый быстрый код:
template <class Ty>
constexpr bool add_carry_ux(bool carry_in, Ty src1, Ty src2, Ty* sum_out)
{
const Ty sum = src1 + src2;
const bool carry_out = (sum < src1) | ((sum == ~static_cast<Ty>(0)) & carry_in);
*sum_out = sum + carry_in;
return carry_out;
}
КАК М:
add_carry_ux(bool, unsigned long, unsigned long, unsigned long*):
add rsi, rdx
movzx eax, dil
setc dl
add rax, rsi
cmp rsi, -1
mov QWORD PTR [rcx], rax
sete al
movzx edx, dl
and eax, edi
or eax, edx
ret
unsigned long result;
unsigned int first;
unsigned int second;
result = first + second;
result += (result & 0x10000) ? 1 : 0;
result &= 0xFFFF