Mnożenie w GF(2) - jak to zrobić szybciej w c++?

Question

Chcę mnożyć liczby w Galois fields. Mnożenie liczb 32-bitowych możemy zdefiniować równoważnie w GF(2^32), gdzie współczynnikami wielomianów będą tylko 0 i 1, ale potrzebujemy do tego 64-bitowych intów (gdzie p to jakiś nieredukowalny wielomian stopnia 32, tj. jego pierwsze 32 bity):

uint32_t p = 4194311;

uint32_t multiply( uint32_t a, uint32_t b )
{
    uint64_t c = 0;

    for( unsigned int i = 0; i < 32; ++i )
    {
        c ^= a & ( 1 << i ) ? (uint64_t) b << i : 0;
    }

    for( unsigned int i = 32; i --> 0 ; )
    {
        if( c & ( 1 << ( i + 32 ) ) )
        {
            c ^= 1 << ( i + 32 );
            c ^= (uint64_t) p << i;
        }
    }

    return (uint32_t) c;
}

Nie dość, że jest to wolne w porównaniu z normalnym mnożeniem, to jeszcze nie mogę wykonać mnożenia 64-bitowych liczb, bo do tego potrzebowałbym 128-bitowych intów.

Ogółem to mnożenie może być podobno bardzo szybkie, równie szybkie jak normalne mnożenie, a do tego oczywiście znajduje zastosowania kryptograficzne. Tylko jak to zrobić szybciej?

Podobno zestaw instrukcji CLMUL instruction set może to robić szybciej i potrafi mnożyć większe liczby:

https://en.wikipedia.org/wiki/CLMUL_instruction_set#cite_note-2

Ale jak go użyć? Tu piszą podobnie o zestawach instrukcji, które czynią to mnożenie szybkim:

Intel has added the PCLMULQDQ instruction, highlighting its use for GCM.[12] In 2011, SPARC added the XMULX and XMULXHI instructions, which also perform 64 × 64 bit carry-less multiplication. In 2015, SPARC added the XMPMUL instruction, which performs XOR multiplication of much larger values, up to 2048 × 2048 bit input values producing a 4096-bit result. These instructions enable fast multiplication over GF(2n), and can be used with any field representation.

https://en.wikipedia.org/wiki/Galois/Counter_Mode

Czy wie ktoś jak użyć instrukcji CLMUL?

 

Answer 1

Jest coś takiego jak intrinsics functions, które pozwalają na korzystanie z instrukcji AVX, MMX, SSE itd.

Sprawdź, czy twój kompilator ma te funkcje.

Comments

Znalazłem coś takiego:

https://wunkolo.github.io/post/2020/05/pclmulqdq-tricks/

I na przykład ten kod:

#include <cstdint>
#include <cstdio>
#include <bitset>
#include <immintrin.h>

int main()
{
	const std::uint64_t Bits
		= 0b00011000100000000001000000000010000000001000000100000001000000001;
	// Print input value in binary
	std::puts(("Bits:\t" + std::bitset<64>(Bits).to_string()).c_str());
	const __m128i Result = _mm_clmulepi64_si128(
		_mm_set_epi64x(0, Bits), // Input 64-bit "a"
		_mm_set1_epi8(0xFF),     // Input 128-bit "b'(full of 1 bits)
		0                        // Multiply the lower 64-bits of each of the inputs
	);
	const std::uint64_t Lo = _mm_cvtsi128_si64(Result);   // Extract  low 64-bits of result
	const std::uint64_t Hi = _mm_extract_epi64(Result, 1); // Extract high 64-bits of result

	// Print result in binary
	std::puts(("Lo:\t" + std::bitset<64>(Lo).to_string()).c_str());
	std::puts(("Hi:\t" + std::bitset<64>(Hi).to_string()).c_str());
}

// Bits:   0011000100000000001000000000010000000001000000100000001000000001
// Lo:     1110111100000000000111111111110000000000111111100000000111111111
// Hi:     0001000011111111111000000000001111111111000000011111111000000000

Działa mi w Visual Studio, chociaż go nie rozumiem. Ale wydaje się, że w takim razie można te instrukcje wykorzystać, bez większego bólu.

Answer 2

To co udało mi się zrobić na podstawie kodów stąd:

https://wunkolo.github.io/post/2020/05/pclmulqdq-tricks/

To użycie instrukcji do carry-less multiplication dwóch liczb 64-bitowych. Wygląda to tak:

#include <immintrin.h>

uint64_t multiply(uint64_t a, uint64_t b)
{
    uint64_t c = 0;

    __m128i result = _mm_clmulepi64_si128(_mm_set_epi64x(0, a), _mm_set_epi64x(0, b), 0);

    c = _mm_cvtsi128_si64(result);

    return c;
}

Mniejsze liczby niż 64-bitowe też można mnożyć, choć chyba nie ma dedykowanej instrukcji do tego (nie wiem), a może byłaby szybsza, gdyby była. Nie wiem, czy można mnożyć liczby większe niż 64-bitowe w ramach tych instrukcji. Żeby działać na 128-bitowych intach i w ogóle zadeklarować 128-bitowe liczby też zdaje się trzeba specjalnych instrukcji SSE, plus właśnie pclmulqdq.

I co najważniejsze - działa to podobnie szybko jak normalne mnożenie, przynajmniej w praktycznych zastosowaniach, nie mierzyłem prędkości samego kodu, patrzę jak szybko wyniki całego programu pipelajnują mi się do terminala (tak to się nazywa?). Wcześniej działało to 3-4 razy wolniej niż zwykłe mnożenie.

Ale to nie wszystko. Jak na razie szybciej wykonuje mi się tylko carry-less multiplication, tymczasem mnożenie w GF(2^k) wymaga jeszcze skrócenia wyniku modulo pewien wielomian. Nie wiem, czy CLMUL instruction set na to pozwala, ale chyba nie. Z tego co czytam tu:

https://en.wikipedia.org/wiki/CLMUL_instruction_set

mnożenie dwóch 64-bitowych liczb, to jest wszystko, co ten zestaw daje.