Próbuję utworzyć kod (obecnie używający clang ++ - 3.8), który dodaje dwie liczby składające się z wielu słów maszynowych. Aby uprościć rzeczy na chwilę, dodaje tylko 128-bitowe liczby, ale chciałbym móc to uogólnić.Tworzenie dobrego dodatku z kodem carry z clang
Pierwsze kilka typedefs:
typedef unsigned long long unsigned_word;
typedef __uint128_t unsigned_128;
A "Wynik" Typ:
struct Result
{
unsigned_word lo;
unsigned_word hi;
};
Pierwsza funkcja f
, przyjmuje dwie pary bez znaku słowa i zwraca rezultacie, jako półproduktu krok, wstawiając oba te 64-bitowe słowa do 128-bitowego słowa przed ich dodaniem, tak jak:
Result f (unsigned_word lo1, unsigned_word hi1, unsigned_word lo2, unsigned_word hi2)
{
Result x;
unsigned_128 n1 = lo1 + (static_cast<unsigned_128>(hi1) << 64);
unsigned_128 n2 = lo2 + (static_cast<unsigned_128>(hi2) << 64);
unsigned_128 r1 = n1 + n2;
x.lo = r1 & ((static_cast<unsigned_128>(1) << 64) - 1);
x.hi = r1 >> 64;
return x;
}
To faktycznie dostaje inlined całkiem ładnie tak:
movq 8(%rsp), %rsi
movq (%rsp), %rbx
addq 24(%rsp), %rsi
adcq 16(%rsp), %rbx
Teraz, zamiast Pisałem prostszą funkcję za pomocą szczęk wielu precyzyjnych primatives, jak poniżej:
static Result g (unsigned_word lo1, unsigned_word hi1, unsigned_word lo2, unsigned_word hi2)
{
Result x;
unsigned_word carryout;
x.lo = __builtin_addcll(lo1, lo2, 0, &carryout);
x.hi = __builtin_addcll(hi1, hi2, carryout, &x.carry);
return x;
}
To daje następujące montaż:
movq 24(%rsp), %rsi
movq (%rsp), %rbx
addq 16(%rsp), %rbx
addq 8(%rsp), %rsi
adcq $0, %rbx
W tym przypadku jest dodatkowy dodatek. Zamiast zwykłego add
na lo-słowach, a następnie adc
na hi-words, to tylko add
s słowa lo, następnie robi adc
na hi-word ponownie z argument zero.
To może nie wyglądać źle, ale kiedy spróbujesz tego z większymi słowami (powiedzmy 192bit, 256bit), szybko dostaniesz bałagan or
s i inne instrukcje dotyczące prowadzenia łańcucha, zamiast prostego łańcucha add
, adc
, adc
, ... adc
.
Prymitywy o wielu precyzjach wydają się robić straszną robotę dokładnie w tym, co zamierzają zrobić.
Czego szukam to kod, który mógłbym uogólnić na dowolną długość (nie trzeba tego robić, wystarczy, żebym mógł się dowiedzieć, jak to zrobić), który klang produkuje dodatki w taki sposób, że jest równie skuteczny jak co robi z wbudowanym 128-bitowym typem (którego niestety nie da się łatwo uogólnić). Zakładam, że powinien to być łańcuch o numerach adc
s, ale jestem zadowolony z argumentów i kodu, że powinno to być coś innego.
Jest to jedna z tych narożnych przypadków, w których kompilatory obecnie pobierają. Jeśli naprawdę ci na tym zależy, musisz użyć wbudowanego zestawu. GMP robi dużo tego materiału do przenoszenia i wszystko jest w zespole. – Mysticial
Już zadałem pytanie o nagrodę w tej sprawie. http://stackoverflow.com/questions/29029572/multi-word-addition-using-the-carry-flag Podejrzewam, że znajdziesz tę samą odpowiedź (lub jej brak), którą zrobiłem. –