Конвертировать _mm_clmulepi64_si128 в vmull_{high}_p64
У меня есть следующее встроенное Intel PCLMULQDQ (безудержное умножение):
__m128i a, b; // Set to some value
__m128i r = _mm_clmulepi64_si128(a, b, 0x10);
0x10 говорит мне, что умножение:
r = a[63:0] * b[127:64]
Мне нужно преобразовать его в NEON (или, вернее, использовать расширение Crypto):
poly64_t a, b; // Set to some value
poly16x8_t = vmull_p64(...) or vmull_high_p64(...);
Я думаю vmull_p64 работает на младших 64-битных, а vmull_high_p64 работает на старших 64 битах. Я думаю, что мне нужно сместить одно из значений 128-битных значений для имитации _mm_clmulepi64_si128(a, b, 0x10), Документы для PMULL, PMULL2 (вектор) не слишком ясны, и я не уверен, каков будет результат, потому что я не понимаю спецификатор расположения 2. ARM ACLE 2.0 тоже не слишком полезен:
poly128_t vmull_p64 (poly64_t, poly64_t);Выполняет расширение полиномиального умножения в нижней части двойного слова. Доступно на ARMv8 AArch32 и AArch64.
poly128_t vmull_high_p64 (poly64x2_t, poly64x2_t);Выполняет расширение полиномиального умножения на старшей части двойных слов. Доступно на ARMv8 AArch32 и AArch64.
Как мне конвертировать _mm_clmulepi64_si128 в vmull_{high}_p64?
Для любого, кто задумывается об инвестициях в NEON, PMULL и PMULL2... 64-битный множитель и поддержка полиномов того стоят. Тесты показывают, что код GCC для GMAC снизился с 12,7 до 90 МБ / с (C/C++) до 1,6 и 670 МБ / с (NEON и PMULL{2}).
2 ответа
Поскольку вы уточнили источник вашей путаницы с комментарием:
Полное умножение дает результат, вдвое больший, чем входы. При добавлении может быть получено не более одного выносного бита, а в муль - целая верхняя половина.
Умножение в точности эквивалентно сдвигам + сложениям, и эти сдвиги приносят биты от одного операнда до 2N - 1 (когда входы имеют ширину N битов). Смотрите пример Википедии.
В обычном целочисленном умножении (с переносом в шагах добавления), как в x86 mul В инструкции, выполняемой из частичных сумм, можно установить старший бит, поэтому результат будет ровно в два раза шире.
XOR - это добавление без переноса, поэтому умножение без переноса - это тот же алгоритм сдвига и добавления, но с XOR вместо сложения с переносом. В умножении без переноса перенос отсутствует, поэтому старший бит результата полной ширины всегда равен нулю. Intel даже делает это явным образом в разделе "Операция" в руководстве по x86 для insn для pclmuludq: DEST[127] ← 0;, Этот раздел точно документирует все сдвиги и XORing, которые производят результат.
PMULL[2] документы кажутся мне довольно понятными. Пункт назначения должен быть .8H вектор (что означает восемь 16-битных (Halfword) элементов). Источники для PMULL должен быть .8B векторы (8 однобайтовых элементов), а источники PMULL2 должен быть .16B (16 однобайтовых элементов, из которых используются только верхние 8 каждого источника).
Если это был ARM32 NEON, где верхняя половина каждого 16B векторного регистра является более узким регистром с нечетным номером, PMULL2 не было бы полезно ни для чего.
Там нет раздела "операция", чтобы точно описать , какие биты умножаются на какие другие биты. К счастью, документ, связанный в комментариях, хорошо суммирует доступные инструкции для ARMv7 и ARMv8 32 и 64 бит. Спецификаторы организации.8B / .8H кажутся фиктивными, потому что PMULL выполняет одну 64x64 -> 128 переносимых мул, как инструкция SSE pclmul. ARMv7 VMULL.P8 NEON insn делает упакованные 8x8->16, но дает понять, что PMULL (и ARMv8 AArch32 VMULL.P8) разные.
Очень жаль, что ARM doc ничего об этом не говорит; кажется ужасно не хватает, особенно в заблуждение .8B вектор организации вещи. Эта статья показывает пример использования ожидаемого .1q а также .1d (а также .2d) организации, поэтому, возможно, ассемблеру все равно, что, по вашему мнению, означают ваши данные, если они имеют правильный размер.
Чтобы умножить максимум на минимум, нужно сдвинуть одно из них.
Например, если вам нужны все четыре комбинации (a0*b0, a1*b0, a0*b1, a1*b1), как вы делаете для построения умножения 128x128 -> 128 из 64x64 -> 128 умножений (с Карацубой), Вы можете сделать это так:
pmull a0b0.8H, a.8B, b.8B
pmull2 a1b1.8H, a.16B, b.16B
swap a's top and bottom half, which I assume can be done efficiently somehow
pmull a1b0.8H, swapped_a.8B, b.8B
pmull2 a0b1.8H, swapped_a.16B, b.16B
Таким образом, похоже, что выбор дизайна ARM, включающий инструкции нижнего-нижнего и верхнего-верхнего, но не перекрестного умножения (или константу селектора, как в x86), не вызывает особой неэффективности. А поскольку инструкции ARM не могут просто использовать дополнительные элементы, как способ машинного кодирования переменной длины x86, то это, вероятно, не вариант.
Другая версия того же самого, с настоящей инструкцией случайного воспроизведения и потом с Карацубой (дословно скопировано из Внедрения GCM на ARMv8). Но все-таки выдуманные регистрационные имена. По пути в статье повторно используется один и тот же временный регистр, но я назвал их так, как мог бы использовать для версии на языке C. Это делает операцию умножения с расширенной точностью довольно ясной. Компилятор может использовать мертвые регистры для нас.
1: pmull a0b0.1q, a.1d, b.1d
2: pmull2 a1b1.1q, a.2d, b.2d
3: ext.16b swapped_b, b, b, #8
4: pmull a0b1.1q, a.1d, swapped_b.1d
5: pmull2 a1b0.1q, a.2d, swapped_b.2d
6: eor.16b xor_cross_muls, a0b1, a1b0
7: ext.16b cross_low, zero, xor_cross_muls, #8
8: eor.16b result_low, a0b0, cross_low
9: ext.16b cross_high, xor_cross_muls, zero, #8
10: eor.16b result_high, a1b1, cross_high
Как мне преобразовать _mm_clmulepi64_si128 в vmull_{high}_p64?
Вот результаты примера программы ниже. Преобразования:
_mm_clmulepi64_si128(a, b, 0x00)→vmull_p64(vgetq_lane_u64(a, 0), vgetq_lane_u64(b, 0))_mm_clmulepi64_si128(a, b, 0x01)→vmull_p64(vgetq_lane_u64(a, 1), vgetq_lane_u64(b, 0))_mm_clmulepi64_si128(a, b, 0x10)→vmull_p64(vgetq_lane_u64(a, 0), vgetq_lane_u64(b, 1))_mm_clmulepi64_si128(a, b, 0x11)→vmull_p64(vgetq_lane_u64(a, 1), vgetq_lane_u64(b, 1))
Для случая (4), _mm_clmulepi64_si128(a, b, 0x11)также имеет место следующее:
_mm_clmulepi64_si128(a, b, 0x11)→vmull_high_p64((poly64x2_t)a, (poly64x2_t)b)
Я предполагаю, что случаи (1) - (4) могут вылиться в память, если не соблюдать осторожность, потому что vgetq_lane_u64 возвращает скалярный или не векторный тип. Я также предполагаю, что case (5) имеет склонность оставаться в регистрах Q, потому что это векторный тип.
x86_64 и _mm_clmulepi64_si128:
$ ./mul-sse-neon.exe
IS_X86: true
****************************************
clmulepi64(a, b, 0x00)
a[0]: 0x2222222222222222, a[1]: 0x4444444444444444
b[0]: 0x3333333333333333, b[1]: 0x5555555555555555
r[0]: 0x606060606060606, r[1]: 0x606060606060606
****************************************
clmulepi64(a, b, 0x01)
a[0]: 0x2222222222222222, a[1]: 0x4444444444444444
b[0]: 0x3333333333333333, b[1]: 0x5555555555555555
r[0]: 0xc0c0c0c0c0c0c0c, r[1]: 0xc0c0c0c0c0c0c0c
****************************************
clmulepi64(a, b, 0x10)
a[0]: 0x2222222222222222, a[1]: 0x4444444444444444
b[0]: 0x3333333333333333, b[1]: 0x5555555555555555
r[0]: 0xa0a0a0a0a0a0a0a, r[1]: 0xa0a0a0a0a0a0a0a
****************************************
clmulepi64(a, b, 0x11)
a[0]: 0x2222222222222222, a[1]: 0x4444444444444444
b[0]: 0x3333333333333333, b[1]: 0x5555555555555555
r[0]: 0x1414141414141414, r[1]: 0x1414141414141414
ARM64 и vmull_p64:
$ ./mul-sse-neon.exe
IS_ARM: true
****************************************
vmull_p64(a, b, 0x00)
a[0]: 0x2222222222222222, a[1]: 0x4444444444444444
b[0]: 0x3333333333333333, b[1]: 0x5555555555555555
r[0]: 0x606060606060606, r[1]: 0x606060606060606
****************************************
vmull_p64(a, b, 0x01)
a[0]: 0x2222222222222222, a[1]: 0x4444444444444444
b[0]: 0x3333333333333333, b[1]: 0x5555555555555555
r[0]: 0xa0a0a0a0a0a0a0a, r[1]: 0xa0a0a0a0a0a0a0a
****************************************
vmull_p64(a, b, 0x10)
a[0]: 0x2222222222222222, a[1]: 0x4444444444444444
b[0]: 0x3333333333333333, b[1]: 0x5555555555555555
r[0]: 0xc0c0c0c0c0c0c0c, r[1]: 0xc0c0c0c0c0c0c0c
****************************************
vmull_p64(a, b, 0x11)
a[0]: 0x2222222222222222, a[1]: 0x4444444444444444
b[0]: 0x3333333333333333, b[1]: 0x5555555555555555
r[0]: 0x1414141414141414, r[1]: 0x1414141414141414
Пример программы mul-sse-neon.cc:
#define IS_ARM (__arm__ || __arm32__ || __aarch32__ || __arm64__ || __aarch64__)
#define IS_X86 (__i386__ || __i586__ || __i686__ || __amd64__ || __x86_64__)
#if (IS_ARM)
# include <arm_neon.h>
# if defined(__ARM_ACLE) || defined(__GNUC__)
# include <arm_acle.h>
# endif
#endif
#if (IS_X86)
# include <emmintrin.h>
# if defined(__GNUC__)
# include <x86intrin.h>
# endif
#endif
#if (IS_ARM)
typedef uint64x2_t word128;
#elif (IS_X86)
typedef __m128i word128;
#else
# error "Need a word128"
#endif
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
void print_val(const word128* value, const char* label);
/* gcc -DNDEBUG -g3 -O0 -march=native mul-sse-neon.cc -o mul-sse-neon.exe */
/* gcc -DNDEBUG -g3 -O0 -march=armv8-a+crc+crypto mul-sse-neon.cc -o mul-sse-neon.exe */
int main(int argc, char* argv[])
{
#if (IS_ARM)
printf("IS_ARM: true\n");
#elif (IS_X86)
printf("IS_X86: true\n");
#endif
word128 a,b, r;
a[0] = 0x2222222222222222, a[1] = 0x4444444444444444;
b[0] = 0x3333333333333333, b[1] = 0x5555555555555555;
#if (IS_ARM)
printf("****************************************\n");
printf("vmull_p64(a, b, 0x00)\n");
r = (uint64x2_t)vmull_p64(vgetq_lane_u64(a, 0), vgetq_lane_u64(b,0));
print_val(&a, "a"); print_val(&b, "b"); print_val(&r, "r");
printf("****************************************\n");
printf("vmull_p64(a, b, 0x01)\n");
r = (uint64x2_t)vmull_p64(vgetq_lane_u64(a, 0), vgetq_lane_u64(b,1));
print_val(&a, "a"); print_val(&b, "b"); print_val(&r, "r");
printf("****************************************\n");
printf("vmull_p64(a, b, 0x10)\n");
r = (uint64x2_t)vmull_p64(vgetq_lane_u64(a, 1), vgetq_lane_u64(b,0));
print_val(&a, "a"); print_val(&b, "b"); print_val(&r, "r");
printf("****************************************\n");
printf("vmull_p64(a, b, 0x11)\n");
r = (uint64x2_t)vmull_p64(vgetq_lane_u64(a, 1), vgetq_lane_u64(b,1));
print_val(&a, "a"); print_val(&b, "b"); print_val(&r, "r");
#elif (IS_X86)
printf("****************************************\n");
printf("clmulepi64(a, b, 0x00)\n");
r = _mm_clmulepi64_si128(a, b, 0x00);
print_val(&a, "a"); print_val(&b, "b"); print_val(&r, "r");
printf("****************************************\n");
printf("clmulepi64(a, b, 0x01)\n");
r = _mm_clmulepi64_si128(a, b, 0x01);
print_val(&a, "a"); print_val(&b, "b"); print_val(&r, "r");
printf("****************************************\n");
printf("clmulepi64(a, b, 0x10)\n");
r = _mm_clmulepi64_si128(a, b, 0x10);
print_val(&a, "a"); print_val(&b, "b"); print_val(&r, "r");
printf("****************************************\n");
printf("clmulepi64(a, b, 0x11)\n");
r = _mm_clmulepi64_si128(a, b, 0x11);
print_val(&a, "a"); print_val(&b, "b"); print_val(&r, "r");
#endif
return 0;
}
static const word128 s_v = {0,0};
static const char s_l[] = "";
void print_val(const word128* value, const char* label)
{
const word128* v = (value ? value : &s_v);
const char* l = (label ? label : s_l);
#if (IS_ARM)
printf("%s[0]: 0x%" PRIx64 ", %s[1]: 0x%" PRIx64 "\n", l, (*v)[0], l, (*v)[1]);
#elif (IS_X86)
printf("%s[0]: 0x%" PRIx64 ", %s[1]: 0x%" PRIx64 "\n", l, (*v)[0], l, (*v)[1]);
#endif
}
Код для vmull_high_p64 как следует. Он всегда дает один и тот же результат, потому что всегда принимает одни и те же высокие слова:
printf("****************************************\n");
printf("vmull_p64(a, b)\n");
r = (uint64x2_t)vmull_high_p64((poly64x2_t)a, (poly64x2_t)b);
print_val(&a, "a"); print_val(&b, "b"); print_val(&r, "r");
Для полноты, переключаем данные на:
word128 a,b, r;
a[0] = 0x2222222233333333, a[1] = 0x4444444455555555;
b[0] = 0x6666666677777777, b[1] = 0x8888888899999999;
Дает следующие результаты:
$ ./mul-sse-neon.exe
IS_X86: true
****************************************
clmulepi64(a, b, 0x00)
a[0]: 0x2222222233333333, a[1]: 0x4444444455555555
b[0]: 0x6666666677777777, b[1]: 0x8888888899999999
r[0]: 0xd0d0d0d09090909, r[1]: 0xc0c0c0c08080808
****************************************
clmulepi64(a, b, 0x01)
a[0]: 0x2222222233333333, a[1]: 0x4444444455555555
b[0]: 0x6666666677777777, b[1]: 0x8888888899999999
r[0]: 0x191919191b1b1b1b, r[1]: 0x181818181a1a1a1a
****************************************
clmulepi64(a, b, 0x10)
a[0]: 0x2222222233333333, a[1]: 0x4444444455555555
b[0]: 0x6666666677777777, b[1]: 0x8888888899999999
r[0]: 0x111111111b1b1b1b, r[1]: 0x101010101a1a1a1a
****************************************
clmulepi64(a, b, 0x11)
a[0]: 0x2222222233333333, a[1]: 0x4444444455555555
b[0]: 0x6666666677777777, b[1]: 0x8888888899999999
r[0]: 0x212121212d2d2d2d, r[1]: 0x202020202c2c2c2c
А также:
$ ./mul-sse-neon.exe
IS_ARM: true
****************************************
vmull_p64(a, b, 0x00)
a[0]: 0x2222222233333333, a[1]: 0x4444444455555555
b[0]: 0x6666666677777777, b[1]: 0x8888888899999999
r[0]: 0xd0d0d0d09090909, r[1]: 0xc0c0c0c08080808
****************************************
vmull_p64(a, b, 0x01)
a[0]: 0x2222222233333333, a[1]: 0x4444444455555555
b[0]: 0x6666666677777777, b[1]: 0x8888888899999999
r[0]: 0x111111111b1b1b1b, r[1]: 0x101010101a1a1a1a
****************************************
vmull_p64(a, b, 0x10)
a[0]: 0x2222222233333333, a[1]: 0x4444444455555555
b[0]: 0x6666666677777777, b[1]: 0x8888888899999999
r[0]: 0x191919191b1b1b1b, r[1]: 0x181818181a1a1a1a
****************************************
vmull_p64(a, b, 0x11)
a[0]: 0x2222222233333333, a[1]: 0x4444444455555555
b[0]: 0x6666666677777777, b[1]: 0x8888888899999999
r[0]: 0x212121212d2d2d2d, r[1]: 0x202020202c2c2c2c