Это будет работать как любая другая библиотека BigInt, только (намного) быстрее и на более низком уровне: процессор выбирает одну цифру из кэша / ОЗУ, добавляет ее и снова записывает результат.
Почти все процессоры делают имеют эту встроенную функцию.Вы должны использовать программный цикл вокруг соответствующих инструкций, но это не замедляет работу, если цикл эффективен.(Это не тривиально на x86, из-за частичного останова флага, см. Ниже)
например, если x86 предоставил rep adc для выполнения src + = dst, принимая 2 указателя и длину в качестве ввода (например, rep movsd в memcpy), он все равно будет реализован как цикл в микрокоде.
32-битный процессор x86 может иметь внутреннюю реализацию rep adc, которая использует 64-битные добавления внутри, поскольку, вероятно, 32-битные процессорыеще есть 64-битный сумматор.Тем не менее, 64-битные процессоры, вероятно, не имеют сумматора с задержкой в один цикл 128b.Так что Я не ожидаю, что наличие специальной инструкции для этого даст ускорение по сравнению с тем, что вы можете сделать с программным обеспечением , по крайней мере, на 64-битном процессоре.
Возможно, специальное широкое добавлениеИнструкция была бы полезна для маломощного процессора с низкой тактовой частотой, где возможен очень широкий сумматор с задержкой в один цикл.
Нужные инструкции x86:
Конечно, adc работает с двоичными числами, а не с единичными десятичными цифрами.x86 может adc в 8, 16, 32 или 64-битных блоках, в отличие от процессоров RISC, которые обычно работают только при полной ширине регистра.( GMP называет каждый кусок "конечностью" ).(В x86 есть некоторые инструкции для работы с BCD или ASCII, но эти инструкции были отброшены для x86-64.)
imul / idiv являются знаковыми эквивалентами.Add работает для дополнения со знаком 2 так же, как и для unsigned, поэтому отдельной инструкции нет;просто посмотрите на соответствующие флаги, чтобы обнаружить переполнение со знаком и без знака .Но для adc помните, что только самый значимый фрагмент имеет бит знака;остальные - без знака.
ADX и BMI / BMI2 добавляют некоторые инструкции, такие как mulx: полное умножение без касания флагов, поэтому его можно чередовать с цепочкой adc для создания большего параллелизма на уровне команддля использования суперскалярных процессоров.
В x86, adc даже доступен с назначением памяти, поэтому он работает точно так, как вы описали: одна инструкция запускает целое чтение / изменение / запись фрагмента BigInteger,См. Пример ниже.
Большинство языков высокого уровня (включая C / C ++) не предоставляют флаг "переносить"
Обычно нет встроенных дополнений с переносомнепосредственно в библиотеках C. BigInteger обычно нужно писать в asm для хорошей производительности.
Однако у Intel фактически есть определенные встроенные функции для adc (и adcx / adox).
unsigned char _addcarry_u64 (unsigned char c_in, unsigned __int64 a, \
unsigned __int64 b, unsigned __int64 * out);
Таким образом, результат переноса обрабатывается как unsigned char в C. Для встроенного _addcarryx_u64, компилятор должен проанализировать цепочки зависимостей и решить, что добавить к adcx и что делать с adox, и как связать их вместе для реализации источника C.
IDK в чем смысл встроенных _addcarryx, вместо того, чтобы компилятор использовал adcx /adox для существующей _addcarry_u64 внутренней, когда есть параллельные цепочки dep, которые могут воспользоваться этим.Возможно, некоторые компиляторы недостаточно умны для этого.
Вот пример функции добавления BigInteger в синтаксисе NASM:
;;;;;;;;;;;; UNTESTED ;;;;;;;;;;;;
; C prototype:
; void bigint_add(uint64_t *dst, uint64_t *src, size_t len);
; len is an element-count, not byte-count
global bigint_add
bigint_add: ; AMD64 SysV ABI: dst=rdi, src=rsi, len=rdx
; set up for using dst as an index for src
sub rsi, rdi ; rsi -= dst. So orig_src = rsi + rdi
clc ; CF=0 to set up for the first adc
; alternative: peel the first iteration and use add instead of adc
.loop:
mov rax, [rsi + rdi] ; load from src
adc rax, [rdi] ; <================= ADC with dst
mov [rdi], rax ; store back into dst. This appears to be cheaper than adc [rdi], rax since we're using a non-indexed addressing mode that can micro-fuse
lea rdi, [rdi + 8] ; pointer-increment without clobbering CF
dec rdx ; preserves CF
jnz .loop ; loop while(--len)
ret
На старых процессорах, особенно до Sandybridge, adc вызовет остановку частичного флага при чтении CF после того, как dec записывает другие флаги. Цикл с другой инструкцией поможет старым процессорам, которые останавливаются при объединении записей частичных флагов, но не стоят этого для семейства SnB .
Развертывание петли также очень важно для adc петель. adc выполняет декодирование в несколько мопов в Intel, так что издержки цикла - это проблема, особенно если у вас есть дополнительные издержки цикла от избежания частичных остановок флагов. Если len является малой известной константой, обычно хорошо подходит полностью развернутый цикл. (например, компиляторы просто используют add / adc, чтобы сделать uint128_t на x86-64 .)
adc с назначением памяти кажется не самым эффективным способом, так как трюк с разницей в указателях позволяет нам использовать режим адресации с одним регистром для dst. (Без этого трюка операнды памяти не сработали бы с микроплавким предохранителем ).
Согласно таблицам инструкций Агнера Фога для Haswell и Skylake, adc r,m составляет 2 моп (слитый домен) с пропускной способностью один на 1 такт, тогда как adc m, r/i - 4 моп (слитый домен) , с пропускной способностью один на 2 такта. По-видимому, это не помогает, что Broadwell / Skylake запускают adc r,r/i как инструкцию с одним мопом (используя возможность иметь мопы с 3 входными зависимостями, представленные в Haswell для FMA). Я также не уверен на 100%, что результаты Агнера здесь, так как он не понимал, что процессоры семейства SnB только с индексированными режимами адресации с микроплавким предохранителем в декодерах / uop-кеше, а не в ядре не по порядку.
В любом случае, этот простой цикл «не развернут на всех» равен 6 мопам и должен выполняться с одной итерацией на 2 цикла на процессорах семейства Intel SnB. Даже если для слияния с частичным флагом требуется дополнительная моп, это все равно намного меньше, чем 8 мопов с объединенными доменами, которые могут быть выполнены за 2 цикла.
Некоторое незначительное развертывание может быть близко к 1 adc за цикл, поскольку эта часть составляет всего 4 моп. Однако 2 загрузки и одно хранилище за цикл не совсем устойчивы.
Возможны также умножение и деление с расширенной точностью, используя команды умножения и деления с увеличением / сужением. Конечно, все гораздо сложнее из-за характера умножения.
не очень полезно использовать SSE для переноса надстройки или AFAIK для любых других операций BigInteger.
Если вы разрабатываете новый набор инструкций, вы можете добавить BigInteger в векторные регистры, если у вас есть правильные инструкции для эффективного генерирования и распространения переноса . В этом потоке обсуждается стоимость и преимущества поддержки флагов переноса в аппаратных средствах по сравнению с тем, как программное обеспечение генерирует выполнение, как это делает MIPS: сравнивать для обнаружения обхода без знака, помещая результат в другой целочисленный регистр.