Умножение 64-битных чисел по 64-битному модулю ассемблерной вставкой в GCC

Правка ru9, от Gornak40, 2022-08-17 00:36:47

Компилятор GCC предоставляет возможность использовать ассемблерные вставки. Это может быть полезно например для умножения двух 64-битных чисел по 64-битному модулю.

Дело в том, что умножая два 64-битных регистра, процессор сохраняет результат в паре регистров rdx (верхнюю часть) и rax (нижнюю часть). Деление же работает похожим образом: делимое берется с регистров rdx и rax, после чего в rax сохраняется частное, а в rdx остаток.

Используя эти знания можно реализовать аналог следующей функции:

inline long long mul(long long a, long long b) {
	return (__int128)a * b % 1000000014018503;
}

Вот таким образом:

inline long long mul(long long a, long long b) {
	long long res;
	asm(
		"mov %1, %%rax\n"
		"mov %2, %%rbx\n"
		"imul %%rbx\n"
		"mov $1000000014018503, %%rbx\n"
		"idiv %%rbx\n"
		"mov %%rdx, %0\n"
		:"=res"(res)
		:"a"(a), "b"(b)
	);
	return res;
}

Мы указываем на использование переменных res на запись, a и b на чтение. Они соответственно получают обозначения %0, %1, %2. Операции записываются с использованием стандартного AT&T синтаксиса.

Теперь вы умеете писать хеши по 64-битному модулю, что эквивалентно использованию пары по 32-битному модулю, без использования __int128.

Теги ассемблер, gcc, хеши, умножение

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Gornak40 2022-08-17 00:45:03 0 (published)
ru11 Русский Gornak40 2022-08-17 00:44:29 0 (опубликовано)
en2 Английский Gornak40 2022-08-17 00:42:48 117
en1 Английский Gornak40 2022-08-17 00:42:16 1468 Initial revision for English translation (saved to drafts)
ru10 Русский Gornak40 2022-08-17 00:38:02 2 Мелкая правка: 'ндартного AT&T синтаксис' -> 'ндартного _AT&T_ синтаксис'
ru9 Русский Gornak40 2022-08-17 00:36:47 8 Мелкая правка: 'льзования ***__int128***.\n' -> 'льзования ___int128_.\n'
ru8 Русский Gornak40 2022-08-17 00:36:17 24
ru7 Русский Gornak40 2022-08-17 00:34:49 31
ru6 Русский Gornak40 2022-08-17 00:33:34 3 Мелкая правка: 'ных регистор, процессо' -> 'ных регистров, процессо'
ru5 Русский Gornak40 2022-08-17 00:32:42 191
ru4 Русский Gornak40 2022-08-17 00:00:48 567
ru3 Русский Gornak40 2022-08-16 19:19:50 522 Мелкая правка: 'функции:\n~~~~~\ni' -> 'функции:\n\n~~~~~\ni'
ru2 Русский Gornak40 2022-08-16 18:29:43 75
ru1 Русский Gornak40 2022-08-16 18:20:20 233 Первая редакция (сохранено в черновиках)