Odwracanie kolejności w SSE/AVX

W ostatniej notce, o możliwościach zmiany kolejności uporządkowania bajtów i bibliotece ByteOrder, wspomniałem, że w wolnej chwili postaram pobawić się SSE i spróbować, w prosty i w miarę wydajny sposób, zaimplementować operację bswap znaną z 32/64-bitowych rejestrów na rejestrach 128-bitowych, a nawet 256-bitowych.

Poniekąd udało mi się to zrobić ;)

SSE2

Druga wersja strumieniowych rozszerzeń SMID dodała 144 nowych instrukcji do SSE. Kilka z nowych instrukcji całkowitoliczbowych, potrafiących zmieniać kolejność 16- i 32-bitowych elementów w 128-bitowym wektorze oraz instrukcji logicznych, będących w rzeczywistości rozszerzeniami instrukcji MMX dla wektorów XMM, mogą nam posłużyć do implementacji funkcji bswap128.

Wykorzystując możliwości SSE2, operację bswap dla 128-bitowego wektora można zapisać jako:

bswap128 proc
	; n = xmm0

	pshufd	xmm0, xmm0, 00011011b	; swap order of dwords

	pshuflw	xmm0, xmm0, 10110001b	; swap order of words
	pshufhw	xmm0, xmm0, 10110001b

	movdqa	xmm1, xmm0				; swap order of bytes
	psrlw	xmm0, 8
	psllw	xmm1, 8
	por		xmm0, xmm1

	ret 0
bswap128 endp

Operand order dla pshufd, pshuflw i pshufhw podano w formie binarnej, co powinno ułatwić zrozumienie działania. Instrukcje te działają w podobny sposób - kopiują z operandu źródłowego element do operandu docelowego w miejsce określone wartością operandu order, którego każde 2 bity wyznaczają miejsce kolejnego elementu.

Działanie tych instrukcji adekwatne jest poniższemu kodowi:

dest[0] = src[order & 0x03];
dest[1] = src[(order >> 2) & 0x03];
dest[2] = src[(order >> 4) & 0x03];
dest[3] = src[(order >> 6) & 0x03];

Instrukcje różnią się jedynie sposobem traktowania elementów i miejscem przeznaczenia, pshufd operuje na 32-bitowych elementach - dword, natomiast pshuflw i pshufhw na 16-bitowych - word, kolejno w dolnej i górnej połówce wektora.

W roli pshufd moglibyśmy również wykorzystać rozkaz shufps z SSE, który w takiej konfiguracji funkcjonalnie tak samo przetasuje elementy w wektorze.

Operacja bswap przedstawiona wyżej, można zaimplementować na instrukcjach intrinsic:

inline __m128i bswap128(__m128i n) {

	n = _mm_shuffle_epi32(n, _MM_SHUFFLE(0, 1, 2, 3));
	n = _mm_shufflelo_epi16(n, _MM_SHUFFLE(2, 3, 0, 1));
	n = _mm_shufflehi_epi16(n, _MM_SHUFFLE(2, 3, 0, 1));

	n = _mm_or_si128(
		_mm_srli_epi16(n, 8),
		_mm_slli_epi16(n, 8)
	);

	return n;
}

Kod całkiem zgrabny, ale idźmy dalej, będzie jeszcze lepiej!

SSE3

Korzystając z rozszerzeń SSE3, a dokładniej jego uzupełnienia SSSE3, które wprowadziło 16 nowych rozkazów, jako uzupełnienie 13 instrukcji z SSE3, możemy za pomocą instrukcji pshufb w łatwy sposób zamienić kolejność bajtów w rejestrze xmm. Instrukcja ta rozmieszcza elementy w wektorze bajtów zgodnie ze wzorcem zapisanym w wektorze źródłowym, jej działanie jest adekwatne algorytmowi:

for (int i = 0; i < 16; i++)
	data[i] = (mask[i] & 0x80) == 0 ? data[mask[i] & 0x0F] : 0;

A zatem, na bazie rozkazu pshufb możemy naszą funkcję swapującą zapisać jeszcze prościej:

.data

	align 16
	bswap128@mask dd 0C0D0E0Fh, 08090A0Bh, 04050607h, 00010203h

.code

bswap128 proc
	; n = xmm0

	pshufb	xmm0, xmmword ptr bswap128@mask
	ret	0

bswap128 endp

Warto tutaj pokusić się o definicję makra zamiast procedury ;)

Odpowiednikiem powyższego kodu z wykorzystaniem instrukcji intrinsic jest kod zapisany w postaci:

inline __m128i bswap128(__m128i n) {
	const static __int8 mask[] = { 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
	return _mm_shuffle_epi8(n, *reinterpret_cast<const __m128i*>(mask));
}

W porównaniu do wersji SSE2, dzięki instrukcji pshufb odwracanie kolejności bajtów w rejestrze xmm, stało się równie proste jak rozkaz bswap operujący na 32/64-bitowych rejestrach.

AVX

Advanced Vector Extensions rozszerza zestaw instrukcji SSE o kolejne nowości - rejestry 256-bitowe i nowe instrukcje na nich operujące, a także rozszerza niektóre dotychczasowe instrukcje SSE do działania z rejestrami ymm.

Implementacje przedstawione wyżej dla SSE2 i SSE3 można również zastosować na 256-bitowych rejestrach ymm, AVX rozszerza używane tam rozkazy o taka możliwość, wystarczy dodać prefiks v do tych mnemoników. W takim wypadku należy pamiętać, że vpshufd nadal używa 8-bitowej maski, a vpshufb działa równolegle na dolnej i górnej połówce wektora, więc nie uda nam się jednym zamachem przetasować elementów według oczekiwań. Musimy jeszcze przed lub po wykonaniu tych operacji zamienić miejscami dolną i górną część. Dokonać to możemy za pomocą vperm2i128:

vperm2i128	ymm0, ymm0, ymm0, 00100001b

lub odpowiedniego intrinsic:

n = _mm256_permute2x128_si256(n, n, _MM_SHUFFLE(0,2,0,1));

Tandem vperm2i128 i vpshufd w wersji opartej na SSE2 można zastąpić jedną z nowo dodanych instrukcji AVX służących do permutacji elementów wektora 256-bitowego. Nas najbardziej będzie interesował rozkaz operujący na elementach o najmniejszym rozmiarze, czyli vpermd (_mm256_permutevar8x32_epi32) traktujący wektor jako zbiór 8 elementów 32-bitowych.

Instrukcja ta wykonuje poniższy kod:

for (int i = 0; i < 8; i++)
	dest[i] = src[order[i] & 0x07];

Wykorzystując dodatkowo możliwość używania dodatkowego argumentu wyjściowego wprowadzonego przez AXV dla rozkazów SSE, możemy wersje z SSE2 zapisać w nowej postaci:

.data

	align 16
	bswap256@order dd 07h, 06h, 05h, 04h, 03h, 02h, 01h, 00h

.code

bswap256 proc
	; n = ymm0

	vmovdqa	ymm1, ymmword ptr bswap256@order
	vpermd	ymm0, ymm1, ymm0

	vpshuflw	ymm0, ymm0, 10110001b
	vpshufhw	ymm0, ymm0, 10110001b

	vpsllw	ymm1, ymm0, 8
	vpsrlw	ymm0, ymm0, 8
	vpor	ymm0, ymm0, ymm1

	ret	0
bswap256 endp

Najrozsądniejsze jednak wydaje się przeportowanie implementacji SSE3 na wersję AVX operującą na wektorach 256-bitowych, czyli skorzystanie z vpshufb:

.data

	align 16
	bswap256@mask dd 1C1D1E1Fh, 18191A1Bh, 14151617h, 00010203h,
					 0C0D0E0Fh, 08090A0Bh, 04050607h, 00010203h

.code

bswap256 proc
	; n = ymm0

	vperm2i128	ymm0, ymm0, ymm0, 00100001b
	vpshufb		ymm0, ymm0, ymmword ptr bswap256@mask
	ret	0

bswap256 endp

Algorytm reverse order

Przedstawione tutaj i w poprzedniej notce algorytmy, implementacje i sposoby odwracania kolejności bajtów, głownie dotyczyły stricte zmiany kolejności bajtów w danych i liczbach od 16-, aż do 256-bitowych. Rozpatrywano je przede wszystkim pod kątem przydatności w zastosowaniach związanych z problemem uporządkowania bajtów na różnych platformach sprzętowych.

W rzeczywistości są to proste algorytmy odwracania kolejności bajtów w dowolnym zbiorze/tablicy. Mogą być także wykorzystywane do szybkiego i bardzo efektywnego reversowania stringów czy innych elementów w tablicach, wektorach, czy innych spójnych kawałkach pamięci.

Wojciech Muła przeprowadził ciekawe eksperymenty i testy związane z odwracaniem stringów, testując implementacje oparte na standardowym wykorzystaniu pętli, instrukcji bswap oraz opartych na rozszerzeniach SSE2 i SSE3, bardzo podobnych do tych jakie przedstawiłem wyżej. Wyniki jego testów można znaleźć na jego stronie w notce Speedup reversing table of bytes, wyniki są bardzo ciekawe.

Przy okazji ciekawych rzeczy mogę wspomnieć o niecodzienny wykorzystaniu rozkazu bswap, jak przedstawił Gynvael Coldwind, można za jego pomocą wykryć emulator bochs lub QEMU.

Zachęcam wszystkich do zabaw w asemblerze i rozszerzeń SSE i AVX, czasem przeprowadzając proste eksperymenty można wiele nowego się dowiedzieć :)