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

Revision en1, by 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.

Tags assembler, gcc, hashing, fast multiplication

History

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