第二十二章 SIMD · 逆向工程基礎

# 第二十二章 SIMD SIMD是Single Instruction, Multiple Data的首字母。簡單說就是單指令多數據流。就像FPU，FPU看起來更像獨立于x86處理器。 SIMD開始于MMX x86。8個新的64位寄存器MM0-MM7被添加。每個MMX寄存器包含2個32-bit值/4個16-bit值/8字節。比如可以通過一次添加兩個值到MMX寄存器來添加8個8-bit（字節）。一個簡單的例子就是圖形編輯器，將圖像表示為一個二維數組，當用戶改變圖像的亮度，編輯器必須添加每個像素的差值。為了簡單起見，將每個像素定義為一個8位字節，就可以同時改變8個像素的亮度。當使用MMX的時候，這些寄存器實際上位于FPU寄存器。所以可以同時使用FPU和MMX寄存器。有人可能會認為，intel基于晶體管保存，事實上，這種共生關系的原因是：老的操作系統不知道額外的CPU寄存器，上下文切換是不會保存這些寄存器，可以節省FPU寄存器。這樣激活MMX的CPU+舊的操作系統+利用MMX特性的處理器=所有一起工作。 SSE-SIMD寄存器擴展至128bits，獨立于FPU。 AVX-另一種256bits擴展。實際應用還包括內存復制(memcpy)和內存比較(memcmp)等等。一個例子是：DES加密算法需要64-bits block，56-bits key,加密塊生成64位結果。DES算法可以認為是一個非常大的電子電路，帶有網格和AND/OR/NOT門。 Bitslice DES2—可以同時處理塊和密鑰。比如說unsigned int類型變量在X86下可以容納32位，因此，使用64+56 unsigned int類型的變量，可以同時存儲32個blocks-keys對。我寫了一個爆破Oracle RDBMS密碼/哈希（基于DES）的工具。稍微修改了DES算法（SSE2和AVX）現在可以同時加密128或256block-keys對。 http://conus.info/utils/ops_SIMD/ ## 22.1 Vectorization 向量化3，例如循環用兩個數組生成一個數組。循環體從輸入數組中取值，處理后存儲到另一個數組。重要的一點是操作了每一個元素。向量化—同時處理多個元素。向量化并不是新的技術：本書的作者在1998年使用Cray Y-MP EL“lite”時從Cray Y-MP supercomputer line看到過。例子： ``` #!cpp for (i = 0; i < 1024; i++) { C[i] = A[i]*B[i]; } ``` 這段代碼從A和B中取出元素，相乘，并把結果保存到C。如果每個元素為32位int型，那么可以從A中加載4個元素到128bits XMM寄存器，B加載到另一個XMM寄存器，通過執行PMULID（Multiply Packed Signed Dword Integers and Store Low Result）和PMULHW(Multiply Packed Signed Integers and Store High Result)，一次可以得到4個64位結果。循環次數從1024變成1024/4，當然更快。一些簡單的情況下某些編譯器可以自動向量化，Intel C++5. 函數如下： ``` #!cpp int f (int sz, int *ar1, int *ar2, int *ar3) { for (int i=0; i<sz; i++) ar3[i]=ar1[i]+ar2[i]; return 0; }; ``` ### 22.1.1 Intel C++ Intel C++ 11.1.051 win32下編譯： icl intel.cpp /QaxSSE2 /Faintel.asm /Ox 可以得到(IDA中): ``` #!bash ; int __cdecl f(int, int *, int *, int *) public ?f@@YAHHPAH00@Z ?f@@YAHHPAH00@Z proc near var_10 = dword ptr -10h sz = dword ptr 4 ar1 = dword ptr 8 ar2 = dword ptr 0Ch ar3 = dword ptr 10h push edi push esi push ebx push esi mov edx, [esp+10h+sz] test edx, edx jle loc_15B mov eax, [esp+10h+ar3] cmp edx, 6 jle loc_143 cmp eax, [esp+10h+ar2] jbe short loc_36 mov esi, [esp+10h+ar2] sub esi, eax lea ecx, ds:0[edx*4] neg esi cmp ecx, esi jbe short loc_55 loc_36: ; CODE XREF: f(int,int *,int *,int *)+21 cmp eax, [esp+10h+ar2] jnb loc_143 mov esi, [esp+10h+ar2] sub esi, eax lea ecx, ds:0[edx*4] cmp esi, ecx jb loc_143 loc_55: ; CODE XREF: f(int,int *,int *,int *)+34 cmp eax, [esp+10h+ar1] jbe short loc_67 mov esi, [esp+10h+ar1] sub esi, eax neg esi cmp ecx, esi jbe short loc_7F loc_67: ; CODE XREF: f(int,int *,int *,int *)+59 cmp eax, [esp+10h+ar1] jnb loc_143 mov esi, [esp+10h+ar1] sub esi, eax cmp esi, ecx jb loc_143 loc_7F: ; CODE XREF: f(int,int *,int *,int *)+65 mov edi, eax ; edi = ar1 and edi, 0Fh ; is ar1 16-byte aligned? jz short loc_9A ; yes test edi, 3 jnz loc_162 neg edi add edi, 10h shr edi, 2 loc_9A: ; CODE XREF: f(int,int *,int *,int *)+84 lea ecx, [edi+4] cmp edx, ecx jl loc_162 mov ecx, edx sub ecx, edi and ecx, 3 neg ecx add ecx, edx test edi, edi jbe short loc_D6 mov ebx, [esp+10h+ar2] mov [esp+10h+var_10], ecx mov ecx, [esp+10h+ar1] xor esi, esi loc_C1: ; CODE XREF: f(int,int *,int *,int *)+CD mov edx, [ecx+esi*4] add edx, [ebx+esi*4] mov [eax+esi*4], edx inc esi cmp esi, edi jb short loc_C1 mov ecx, [esp+10h+var_10] mov edx, [esp+10h+sz] loc_D6: ; CODE XREF: f(int,int *,int *,int *)+B2 mov esi, [esp+10h+ar2] lea esi, [esi+edi*4] ; is ar2+i*4 16-byte aligned? test esi, 0Fh jz short loc_109 ; yes! mov ebx, [esp+10h+ar1] mov esi, [esp+10h+ar2] loc_ED: ; CODE XREF: f(int,int *,int *,int *)+105 movdqu xmm1, xmmword ptr [ebx+edi*4] movdqu xmm0, xmmword ptr [esi+edi*4] ; ar2+i*4 is not 16-byte aligned, so load it to xmm0 paddd xmm1, xmm0 movdqa xmmword ptr [eax+edi*4], xmm1 add edi, 4 cmp edi, ecx jb short loc_ED jmp short loc_127 ; --------------------------------------------------------------------------- loc_109: ; CODE XREF: f(int,int *,int *,int *)+E3 mov ebx, [esp+10h+ar1] mov esi, [esp+10h+ar2] loc_111: ; CODE XREF: f(int,int *,int *,int *)+125 movdqu xmm0, xmmword ptr [ebx+edi*4] paddd xmm0, xmmword ptr [esi+edi*4] movdqa xmmword ptr [eax+edi*4], xmm0 add edi, 4 cmp edi, ecx jb short loc_111 loc_127: ; CODE XREF: f(int,int *,int *,int *)+107 ; f(int,int *,int *,int *)+164 cmp ecx, edx jnb short loc_15B mov esi, [esp+10h+ar1] mov edi, [esp+10h+ar2] loc_133: ; CODE XREF: f(int,int *,int *,int *)+13F mov ebx, [esi+ecx*4] add ebx, [edi+ecx*4] mov [eax+ecx*4], ebx inc ecx cmp ecx, edx jb short loc_133 jmp short loc_15B ; --------------------------------------------------------------------------- loc_143: ; CODE XREF: f(int,int *,int *,int *)+17 ; f(int,int *,int *,int *)+3A ... mov esi, [esp+10h+ar1] mov edi, [esp+10h+ar2] xor ecx, ecx loc_14D: ; CODE XREF: f(int,int *,int *,int *)+159 mov ebx, [esi+ecx*4] add ebx, [edi+ecx*4] mov [eax+ecx*4], ebx inc ecx cmp ecx, edx jb short loc_14D loc_15B: ; CODE XREF: f(int,int *,int *,int *)+A ; f(int,int *,int *,int *)+129 ... xor eax, eax pop ecx pop ebx pop esi pop edi retn ; --------------------------------------------------------------------------- loc_162: ; CODE XREF: f(int,int *,int *,int *)+8C ; f(int,int *,int *,int *)+9F xor ecx, ecx jmp short loc_127 ?f@@YAHHPAH00@Z endp ``` SSE2相關指令是： ``` MOVDQU (Move Unaligned Double Quadword)—僅僅從內存加載16個字節到XMM寄存器。 PADDD (Add Packed Integers)—把源存儲器與目的寄存器按雙字對齊無符號整數普通相加,結果送入目的寄存器,內存變量必須對齊內存16字節. MOVDQA (Move Aligned Double Quadword)—把源存儲器內容值送入目的寄存器,當有m128時,必須對齊內存16字節. ``` 如果工作元素超過4對，并且指針ar3按照16字節對齊，SSE2指令將被執行：如果ar2按照16字節對齊，則代碼如下： ``` movdqu xmm0, xmmword ptr [ebx+edi*4] ; ar1+i*4 paddd xmm0, xmmword ptr [esi+edi*4] ; ar2+i*4 movdqa xmmword ptr [eax+edi*4], xmm0 ; ar3+i*4 ``` 否則,ar2處的值將用MOVDQU加載到XMM0，它不需要對齊指針，代碼如下： ``` movdqu xmm1, xmmword ptr [ebx+edi*4] ; ar1+i*4 movdqu xmm0, xmmword ptr [esi+edi*4] ; ar2+i*4 is not 16-byte aligned, so load it to xmm0 paddd xmm1, xmm0 movdqa xmmword ptr [eax+edi*4], xmm1 ; ar3+i*4 ``` 其他情況，將沒有SSE2代碼被執行。 ### 22.1.2 GCC gcc用-O3 選項同時打開SSE2支持: -msse2. 可以得到(GCC 4.4.1): ``` #!bash ; f(int, int *, int *, int *) public _Z1fiPiS_S_ _Z1fiPiS_S_ proc near var_18 = dword ptr -18h var_14 = dword ptr -14h var_10 = dword ptr -10h arg_0 = dword ptr 8 arg_4 = dword ptr 0Ch arg_8 = dword ptr 10h arg_C = dword ptr 14h push ebp mov ebp, esp push edi push esi push ebx sub esp, 0Ch mov ecx, [ebp+arg_0] mov esi, [ebp+arg_4] mov edi, [ebp+arg_8] mov ebx, [ebp+arg_C] test ecx, ecx jle short loc_80484D8 cmp ecx, 6 lea eax, [ebx+10h] ja short loc_80484E8 loc_80484C1: ; CODE XREF: f(int,int *,int *,int *)+4B ; f(int,int *,int *,int *)+61 ... xor eax, eax nop lea esi, [esi+0] loc_80484C8: ; CODE XREF: f(int,int *,int *,int *)+36 mov edx, [edi+eax*4] add edx, [esi+eax*4] mov [ebx+eax*4], edx add eax, 1 cmp eax, ecx jnz short loc_80484C8 loc_80484D8: ; CODE XREF: f(int,int *,int *,int *)+17 ; f(int,int *,int *,int *)+A5 add esp, 0Ch xor eax, eax pop ebx pop esi pop edi pop ebp retn ; --------------------------------------------------------------------------- align 8 loc_80484E8: ; CODE XREF: f(int,int *,int *,int *)+1F test bl, 0Fh jnz short loc_80484C1 lea edx, [esi+10h] cmp ebx, edx jbe loc_8048578 loc_80484F8: ; CODE XREF: f(int,int *,int *,int *)+E0 lea edx, [edi+10h] cmp ebx, edx ja short loc_8048503 cmp edi, eax jbe short loc_80484C1 loc_8048503: ; CODE XREF: f(int,int *,int *,int *)+5D mov eax, ecx shr eax, 2 mov [ebp+var_14], eax shl eax, 2 test eax, eax mov [ebp+var_10], eax jz short loc_8048547 mov [ebp+var_18], ecx mov ecx, [ebp+var_14] xor eax, eax xor edx, edx nop loc_8048520: ; CODE XREF: f(int,int *,int *,int *)+9B movdqu xmm1, xmmword ptr [edi+eax] movdqu xmm0, xmmword ptr [esi+eax] add edx, 1 paddd xmm0, xmm1 movdqa xmmword ptr [ebx+eax], xmm0 add eax, 10h cmp edx, ecx jb short loc_8048520 mov ecx, [ebp+var_18] mov eax, [ebp+var_10] cmp ecx, eax jz short loc_80484D8 loc_8048547: ; CODE XREF: f(int,int *,int *,int *)+73 lea edx, ds:0[eax*4] add esi, edx add edi, edx add ebx, edx lea esi, [esi+0] loc_8048558: ; CODE XREF: f(int,int *,int *,int *)+CC mov edx, [edi] add eax, 1 add edi, 4 add edx, [esi] add esi, 4 mov [ebx], edx add ebx, 4 cmp ecx, eax jg short loc_8048558 add esp, 0Ch xor eax, eax pop ebx pop esi pop edi pop ebp retn ; --------------------------------------------------------------------------- loc_8048578: ; CODE XREF: f(int,int *,int *,int *)+52 cmp eax, esi jnb loc_80484C1 jmp loc_80484F8 _Z1fiPiS_S_ endp ``` 幾乎一樣，但沒有Intel的細致。 ## 22.2 SIMD strlen() implementation SIMD指令可能通過特殊的宏8插入到C/C++代碼中。MSVC中他們被保存在intrin.h中。 Strlen()函數9的實現使用了SIMD指令，比常規的實現快了2-2.5倍。該函數將16個字符加載到一個XMM寄存器并檢查是否為零 ``` #!cpp size_t strlen_sse2(const char *str) { register size_t len = 0; const char *s=str; bool str_is_aligned=(((unsigned int)str)&0xFFFFFFF0) == (unsigned int)str; if (str_is_aligned==false) return strlen (str); __m128i xmm0 = _mm_setzero_si128(); __m128i xmm1; int mask = 0; for (;;) { xmm1 = _mm_load_si128((__m128i *)s); xmm1 = _mm_cmpeq_epi8(xmm1, xmm0); if ((mask = _mm_movemask_epi8(xmm1)) != 0) { unsigned long pos; _BitScanForward(&pos, mask); len += (size_t)pos; break; } s += sizeof(__m128i); len += sizeof(__m128i); }; return len; } ``` (這里的例子基于源代碼). MSVC 2010 /Ox 編譯選項: ``` #!bash _pos$75552 = -4 ; size = 4 _str$ = 8 ; size = 4 ?strlen_sse2@@YAIPBD@Z PROC ; strlen_sse2 push ebp mov ebp, esp and esp, -16 ; fffffff0H mov eax, DWORD PTR _str$[ebp] sub esp, 12 ; 0000000cH push esi mov esi, eax and esi, -16 ; fffffff0H xor edx, edx mov ecx, eax cmp esi, eax je SHORT $LN4@strlen_sse lea edx, DWORD PTR [eax+1] npad 3 $LL11@strlen_sse: mov cl, BYTE PTR [eax] inc eax test cl, cl jne SHORT $LL11@strlen_sse sub eax, edx pop esi mov esp, ebp pop ebp ret 0 $LN4@strlen_sse: movdqa xmm1, XMMWORD PTR [eax] pxor xmm0, xmm0 pcmpeqb xmm1, xmm0 pmovmskb eax, xmm1 test eax, eax jne SHORT $LN9@strlen_sse $LL3@strlen_sse: movdqa xmm1, XMMWORD PTR [ecx+16] add ecx, 16 ; 00000010H pcmpeqb xmm1, xmm0 add edx, 16 ; 00000010H pmovmskb eax, xmm1 test eax, eax je SHORT $LL3@strlen_sse $LN9@strlen_sse: bsf eax, eax mov ecx, eax mov DWORD PTR _pos$75552[esp+16], eax lea eax, DWORD PTR [ecx+edx] pop esi mov esp, ebp pop ebp ret 0 ?strlen_sse2@@YAIPBD@Z ENDP ; strlen_sse2 ``` 首先，檢查str指針，如果不是按照16字節對齊則調用常規實現。然后使用movdqa指令加載16個字節到xmm1.這里不使用movdqu的原因是如果指針不一致則從內存中加載的數據可能會不一致。是的，它可能會以這種方式做，如果指針對齊，使用MOVDQA加載數據，否則使用比較慢的MOVDQU。但是我們應該注意到這樣的警告：在windowsNT操作系統但不限于該操作系統，內存頁按4kb對齊。每個win32進程獨占4GB虛擬內存。事實上，只有部分地址空間與真實物理內存對應，如果進程訪問的內存沒有對應物理內存，將觸發異常。這是虛擬內存的工作方式10. 一個函數一次加載16個字節，可能會跨內存分塊訪問。我們考慮這樣一種情況，操作系統在x008c0000分配8192（0x2000）字節,因此塊字節從地質0x008c0000到0x008c1fff。內存塊之后從0x008c2000什么都沒有，操作系統沒有分配任何內存。訪問該地址將觸發異常。假如內存塊包含的最后5個字符如下： ``` 0x008c1ff8 ’h’ 0x008c1ff9 ’e’ 0x008c1ffa ’l’ 0x008c1ffb ’l’ 0x008c1ffc ’o’ 0x008c1ffd ’x00’ 0x008c1ffe random noise 0x008c1fff random noise ``` 正常情況下，strlen()只會讀取到”hello”。如果我們使用MOVDQU讀取16個字節，將會觸發異常，應該避免這種情況。因為我們要確保16字節對齊，保證我們不會讀取未分配的內存。讓我們回到函數： ``` _mm_setzero_si128()—宏pxor xmm0, xmm0—清空XMM0寄存器。 _mm_load_si128()—宏 MOVDQA, 從內存加載16個字節到XMM寄存器。 _mm_cmpeq_epi8()—宏PCMPEQB,比較XMM寄存器的字節位，如果相等則為0xff否則為0。 ``` 比如： ``` XMM1: 11223344556677880000000000000000 XMM0: 11ab3444007877881111111111111111 ``` 執行pcmpeqb xmm1, xmm0之后，XMM1寄存器的值為： ``` XMM1: ff0000ff0000ffff0000000000000000 ``` 在本例中該指令比較每一個16字節塊與16字節0字節塊對比，XMM0通過pxor xmm0 xmm0置零。接下來宏_mm_movemask_epi8() —這是PMOVMSKB指令。 ``` pmovmskb eax, xmm1 ``` pmovmskb創建源操作數每一個字節的自高位掩碼，并保存結果到目的操作數的低byte。源操作數必須為MMX寄存器，目的操作數必須為32位通用寄存器。比如： ``` XMM1: 0000ff00000000000000ff0000000000 ``` 對應的EAX： ``` EAX=0010000000100000b ``` 之后bsf eax,eax被執行，eax值為5，意味著第一個是1的位置是5（從0開始）。 MSVC關于這個指令的宏是：_BitScanForward. 至此，找到結尾0的位置，然后程序返回長度計數。整個過程大致就是這樣。順便提一下，MSVC為了優化，使用了兩個并排的循環。 SSE 4.2(英特爾core i7)提供了更多的指令,這些可能更容易字符串操作。 http://www.strchr.com/strcmp_and_strlen_using_sse_4.2