同樣對 0~99,999,999 共一億個整數計算 MD5:
提速 5.5 倍。代價:失去跨平台性,僅能在 x86 Windows 運行。
原始 Encode 將 UINT4* 逐字節拆解為 unsigned char*:
static void Encode(unsigned char* output, unsigned int* input, unsigned int len) {
for (i=0,j=0; j>8) & 0xff);
output[j+2] = ((input[i]>>16) & 0xff);
output[j+3] = ((input[i]>>24) & 0xff);
}
}
洞察:x86 小端序下,UINT4 記憶體布局恰好就是四個連續位元組 output[j..j+3]。整個函數等價於:
output = (unsigned char*)input; // 零指令開銷
原始 MD5_memcpy 逐位元組搬移:
for (i=0; i
鐵律:任何記憶體搬移、比較、填充,**永遠呼叫 memcpy/CopyMemory/RtlMoveMemory**。作業系統內核已針對 CPU 快取行、SIMD、預取指令深度優化,手寫迴圈無法超越。
MD5 主迴路執行 64 輪 FF 運算,每輪原始 C 編譯產生 ~23 條組語,16 條涉及記憶體存取(平均 10 週期),邏輯運算僅 4 週期。記憶體存取佔總耗時 70%+。
#define a esi
#define b edi
#define c edx
#define d ebx
#define tmp1 eax
#define tmp2 ecx
四個狀態變數 a,b,c,d 全程留在暫存器,消除絕大多數 mov [mem], reg/mov reg, [mem]。
F、旋轉、加法
// F(x,y,z) = (x&y) | (~x&z)
mov tmp1, b
and tmp1, c
mov tmp2, b
not tmp2
and tmp2, d
or tmp2, tmp1 ; F(b,c,d) -> tmp2
add tmp2, x ; + X[k]
add tmp2, ac ; + 常數
add a, tmp2 ; a += F + X + AC
rol a, s ; 循環左移 s 位
add a, b ; a += b
從 23 條降至 11 條。
lea 實現三數相加
; 原版:add tmp2, ac / add a, tmp2 (2 條)
; 優化:lea a, [tmp2 + a + ac] (1 條)
lea a, [tmp2 + a + ac] ; Base + Index + Disp,Scale=1
add a, x
rol a, s
add a, b
最終核心巨集僅 10 條指令,零記憶體存取。
| 版本 | 指令數 | 記憶體存取 | 備註 |
|---|---|---|---|
| C 編譯輸出 | 23 | 16 | 基準 |
| 暫存器化 | 11 | 0 | 強制 register 變數 |
lea 融合 | 10 | 0 | 三數相加合併 |
MD5 狀態為 4×32bit=128bit,恰好適合 XMM 暫存器。可嘗試:
PAND/POR/PXOR 並行處理 4 組 32bit 邏輯運算PSLLD/PSRLD/POR 模擬 32bit 旋轉PADDD 並行加法參考:MMX 程式設計指南。需注意 U/V 流水線配對與資料相依。
lea、cmov 等零記憶體指令memcpy/memset/strlen 等已極致優化,別重造輪子MD5C:RFC 1321 參考 C 實作MD5ASM:本文優化版,含 test1~test3 漸進優化分支main():窮舉 0~99,999,999 計時基準原始碼下載見附件。從 8 小時降到 4 分鐘的旅程,始於對每個指令的敬畏。