首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> VC >> 關於VC++

從 C 到組合語言:MD5 演算法極致優化實戰(附效能對比)

     編輯:關於VC++

效能對比先行:數據說話

同樣對 0~99,999,999 共一億個整數計算 MD5:

  • MD5C (純 C 參考實作):999 秒
  • MD5ASM (手寫 x86 組語優化):181 秒

提速 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 變換函數 FF

MD5 主迴路執行 64 輪 FF 運算,每輪原始 C 編譯產生 ~23 條組語,16 條涉及記憶體存取(平均 10 週期),邏輯運算僅 4 週期。記憶體存取佔總耗時 70%+。

3.1 強制變數駐留暫存器


#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]。

3.2 單指令優化: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 條。

3.3 多指令融合: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 條指令,零記憶體存取。

3.4 完整 FF 巨集對比

版本指令數記憶體存取備註
C 編譯輸出2316基準
暫存器化110強制 register 變數
lea 融合100三數相加合併

進階方向:MMX/SSE/AVX

MD5 狀態為 4×32bit=128bit,恰好適合 XMM 暫存器。可嘗試:

  • PAND/POR/PXOR 並行處理 4 組 32bit 邏輯運算
  • PSLLD/PSRLD/POR 模擬 32bit 旋轉
  • PADDD 並行加法

參考:MMX 程式設計指南。需注意 U/V 流水線配對與資料相依。

優化心法總結

  1. 演算法優先:選對演算法(如雜湊表 vs 線性搜尋)勝過任何微優化
  2. 記憶體是瓶頸:暫存器化、消除冗餘載存、善用 lea、cmov 等零記憶體指令
  3. 信任系統庫:memcpy/memset/strlen 等已極致優化,別重造輪子
  4. SIMD 為王:資料平行場景優先考慮 SSE/AVX/NEON
  5. 測試驗證:每次優化必須跑基準測試,防止「優化」變「劣化」

專案結構

  • MD5C:RFC 1321 參考 C 實作
  • MD5ASM:本文優化版,含 test1~test3 漸進優化分支
  • main():窮舉 0~99,999,999 計時基準

原始碼下載見附件。從 8 小時降到 4 分鐘的旅程,始於對每個指令的敬畏。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved