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

Правка en1, от Gornak40, 2022-08-17 00:42:16

Compiler GCC provides the ability to use assembler inserts. This can be useful, for example, for multiplying two 64-bit numbers by a 64-bit module.

The fact is that multiplying two 64-bit registers, the processor stores the result in a pair of registers rdx (upper part) and rax (lower part). Division works in a similar way: the divisible is taken from the registers rdx and rax, after which the quotient is stored in rax, and the remainder is stored in rdx.

Using this knowledge, you can implement an analog of the following function:

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

In this way:

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;
}

We indicate the use of variables res for writing, a and b for reading. They accordingly receive designations %0, %1, %2. Operations are written using the standard AT&T syntax.

Now you can write hashes using a 64-bit module, which is equivalent to using a pair using a 32-bit module, without using __int128.

Теги assembler, gcc, hashing, fast multiplication

История

 
 
 
 
Правки
 
 
  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 Первая редакция (сохранено в черновиках)