16位色AlphaBlend深度探索

　　在網上看了很多關于16位色的AlphaBlend計算方法，在GameRes上看到很多高手寫的文章，深有感觸，這些文章要不就是單說原理卻沒有程序，要不就有程序卻沒有很好的原理解釋，要不兩樣都有，但就程序跟原理就像硬拼在一起一樣，看了原理看程序卻不知道程序在干什么，要知道很多16位色處理的AlphaBlend程序是用彙編寫的，這更頭疼了，看見一堆沒有解釋的彙編代碼，頭都大了……也許是我太笨了……

　　因此萌生了寫一篇對16位色AlphaBlend的原理及程序的詳解文章，希望我這篇文章能對一些初涉圖像編程的后來者有所幫助:)

　　為什么單單研究16位色的Alpha混合？而不研究24位，32位的？

　　第一、節省空間，它只有兩個字節，比起24位（三字節），32位（四節節）色的存儲容量會省很多，雖然對于目前的大內存系統，不算什么，但放在顯存中時，就很重要了，雖然目前顯卡的緩存容量也在向內存靠攏，但省點還是好的:) 畢竟你也不希望你的程序是個吃內存的怪獸吧？！

　　第二、速度，有人可能會不贊同這個觀點：24位、32位色的RGB分量是單獨的一個字節，計算起來起碼沒有16位那么麻煩！方法是人想出來的，16位的處理另有方法計算，可以不用把RGB分量拆開而直接計算，稍后會講到。而24位不是4字節對齊，在內存的計算中會比較吃虧，相對16位，32位，特別是大面積復制及計算時會差些，而32位與16位呢？呃，在數字上我們可以看到一點，在處理32位數據時，我們可以處理兩個16位的數據……

　　第三、視覺，在人的視覺方面來說，高于16位的顏色，人眼几乎分辨不出區別來，那么要那么大的顏色干啥呢？當然，這里只針對做游戲來說的，如果你是想做圖像處理的，那么24位以上的顏色是必要的，畢竟那些細節不能掉失:)

　　接下來開始入正題了。

　　在16位色狀態下，根據不同顯卡對像素的處理不同，16位色的像素格式共有兩種，一種的RGB分量為(R:5, G:5, B:5)，另一種的RGB分量為(R:5, G:6, B:5)。數字是代表所占的位(Bit)數。前一種只有15位是有效的。

　　注意，在16位模式時要先取得顯卡的像素模式，否則，處理時如果跟顯卡的像素格式不一致會產生偏色的現像！還有一點，Windows Bitmap的16位色格式是倒過來的，即顏色順序是BGR，剛好跟顯卡的顏色順序調了個頭，當然你可以設定Bitmap的顏色掩碼來實現Bitmap與顯卡格式一致。

　　接下來，我們要介紹的是這個AlphaBlend算法了，AlphaBlend算法即我們通常所說的半透明效果算法，我們可以設置Alpha值來把兩圖進行不同透明度混合。

　　AlphaBlend常規算法如下：
　　提示：獲取某個顏色的值可使用顏色掩碼，如：555色顯卡的顏色掩碼為 R(0x7C00), G(0x03E0), B(0x001F), 設顏色值為Value，則 R = ( Value & 0x7C00 ) >> 10; G = ( Value & 0x03E0 ) >> 5; B = ( Value & 0x001F ) >> 5;　計算完畢后要把顏色分量結合為一個顏色值時使用逆操作即可。

　　如若你的程序不需要太高效率，那么這種算法是挺適合你的，容易理解也容易實現。

　　接下來我們對此算法作一下改進，把括號拆開，現在變成這樣了，這几條公式跟上面的有什么區別呢？要知道，在計算機中，一般來說，乘除計算是比加減要慢得多的，現在我們把它由原來的兩次乘法變成一次乘法：
　　想想，還有沒有得再進一步優化呢？有！我們知道Alpha值是在 0 ~ 1范圍內的，是一個浮點數，計算機的浮點數計算也是一個效率殺手，我們應該怎樣去掉它呢？把它變成整數！

　　但怎樣變呢？把它的范圍擴大！對啦，正解！在16位色 555或565模式，平均來說每個分量最大取5位(bit)，而25=30，我們可以把它擴大32倍，足夠用了！即取 0 <= Alpha <= 32　內的整數值。那么只需要公式兩邊均乘以32即可。現在我們的Alpha值不再是原來的Alpha了，而是一個大于等于0且小于等于32的Alpha值，我們把它命名為 Alpha32。于是，公式再次變成： 　　提示：除以32可以使用C語言中的移位運算來實現。

　　到目前為止，好像能優化的地方已經很難找了，還有其它方法能更快地實現運算嗎？當然是有的，否則我還用寫嗎？！那就是不要把各個分量拆開再運算，而把整個顏色值進行運算，這樣就省去了拆分的步驟，也不用進行三次相同的操作了！但不是直接把顏色值拿來進行運算，需要對顏色值進行一些前期處理再進行運算。事實上，我們接下來的這個方法還是針對每個分量進行處理的，只不過，我們把它這個處理變成一次處理三個分量。這樣運算一次即相當于三次的運算。

　　以下的所有的文字如無特別說明則均針對16位色555模式RGB順序進行處理。

　　首先，我們分析一下像素的格式，其格式為(二進制) : 0RRR RRGG GGGB BBBB。

　　如果我們直接對像素進行運算，那么其運算過程如下：
　　但大家需要留意的是，紅綠藍分量乘后，如果有進位，向哪里進位？必然會溢出到相鄰的分量上，這樣計算結果就會出現錯誤了！那么需要有多大空間才不會相互影響呢？我們知道25=32，而我們的Alpha位數為5，5位的分量乘以最大級數32也只是向左移5位，所以我們只需要5位就足夠了，這里只是作下解釋，下面這個方法不需要你親自去移位D:) 　　因此，我們需要想一個辦法來讓它有足夠多的位置來進位且不用過多的復雜計算。我們可以把這個像素復制一份，這樣，像素就變成了32位了(Value32): 0RRR RRGG GGGB BBBB 0RRR RRGG GGGB BBBB。然后怎樣做呢？我們使用一個掩碼(Mask32): 0000 0011 1110 0000 0111 1100 0001 1111（0x3E07C1F）。我們把 Value32 & Mask32 即可得　 0000 00GG GGG0 0000 0RRR RR00 000B BBBB。大家可以留意到，剛好它們之間就間隔了5位，如果兩個這樣的32位值相乘，它們就有足夠的進位空間了。如下：　　但是，我們不能給你5位，你給我生成10位數啊，那樣我們還怎樣運算？好的，現在把它變回5位，不知道你留意到沒有，在上面我們講述公式3時，Alpha32后來還需要除以32的，除以32是什么意思？剛好是右移5位！這樣 10 – 5 = 5剛剛好！現在還有個問題，有人會說進行乘或加還好辦，有足夠位可以進位，那么當Color1-Color2這樣時怎么辦呢？它會向前借位的啊！呃……這個是一個問題，但似乎這個問題并不影響大局，只要你眼力不是特別好的話，在效果上看不出有什么太大區別的，我們是求速度嘛，別計較那么多！

　　好，假設我們通過運算得到了一個源點及目標點的計算結果Color3：GGGG GGGG GGG0 RRRR RRRR RRBB BBBB BBBB，我們怎樣把它還原到我們的16位的顏色值呢？OK，執行一下我們怎樣把它變成這個樣子的逆運算就行了！如下：　　哈哈，還是用C語言描述舒服啊，不用寫那么多公式！

　　這樣我們就得到了一個經過AlphaBlend的結果值

　　下面就是我們的重頭戲了，代碼實現！可能會有人奇怪，為什么要寫三份實現代碼呢？那是因為，使用純C語言實現的函數雖然可移植性佳，但同時，它也失去了使用機器更強大功能的機會。使用普通彙編代碼也是同類問題，就是在沒有MMX的機器上，普通彙編代碼能實現比純C更高的效率，當然，如果編譯器的能力足夠強大，純C程序與彙編的速度可以几乎相等。還有個版本就是MMX版本，此版本利用了MMX加速功能，速度比普通的彙編代碼提高一倍不止！要注意的是，MMX版本我們釆用的仍然是顏色量計算的，原因在后面在該算法前再詳述。　　 　　

　　好了，廢話少說：

//首先是登場的是使用C++的實現
void DrawAlphaBlend_cpp(

　　WORD * dstAddr, // 目標圖的起始地址
　　WORD * srcAddr, // 源圖的起始地址
　　DWORD cntX, // 橫軸要處理的寬度

　　DWORD cntY, // 縱軸要處理的高度
　　DWORD dstSkipBytes, // 目標地址在處理完橫向寬度最后一個點后要跳過多少個字節
　　DWORD srcSkipBytes, // 源地址在處理完橫向寬度最后一個點后要跳過多少個字節
　　DWORD srcAlphaLevel )// Alpha級數 0 ~ 32
{

　　DWORD srcColor; // 源點顏色
　　DWORD dstColor; // 目標點顏色
　　// 此值要根據你所需要處理的像素格式而定,這里僅指 16 位色 555模式 RGB順序
　　DWORD Mask32 = 0x3E07C1F;
　　WORD xCnt = cntX; // 暫存寬度值，以便循環運算


　　for( ;cntY>0; --cntY, cntX = xCnt )
　　{

　　　　for( ; cntX>0; --cntX )
　　　　{
　　　　　　srcColor = *srcAddr | (*srcAddr<<16); dstcolor =" *dstAddr" srccolor =" (srcColor" srccolor =" (srcColor">>16 | (srcColor & 0x0000ffff );

　　　　　　
　　　　　　// 改變目標圖的點為結果點，這樣直接顯示目標圖即可知道整個結果
　　　　　　*dstAddr = srcColor;
　　　　　　++dstAddr;
　　　　　　++srcAddr;
　　　　}
　　　　dstAddr = (WORD*)((BYTE*)dstAddr + dstSkipBytes);

　　　　srcAddr = (WORD*)((BYTE*)srcAddr + srcSkipBytes);
　　}
}

// 接下來是普通彙編的實現
void DrawAlphaBlend_asm(

　　WORD * dstAddr, // 目標圖的起始地址
　　WORD * srcAddr, // 源圖的起始地址
　　WORD cntX, // 橫軸要處理的寬度

　　WORD cntY, // 縱軸要處理的高度
　　DWORD dstSkipBytes, // 目標地址在處理完橫向寬度最后一個點后要跳過多少個字節到下一行
　　DWORD srcSkipBytes, // 源地址在處理完橫向寬度最后一個點后要跳過多少個字節到下一行
　　WORD srcAlphaLevel )// Alpha級數 0 ~ 32
{

　　DWORD Mask32 = 0x3E07C1F;

　　// 簡單 alpha 運算　　
　　__asm
　　{
　　　　mov edi, dword ptr dstAddr; // 源地址

　　　　mov esi, dword ptr srcAddr; // 目標地址
　　　　mov cx, cntY; // cx 為行數

Next_Row:

　　　　cmp cx, 0; // 如果 高度(即要處理的行數) 為零則結束運算
　　　　je All_End;

　　　　mov dx, cntX;

　　　　mov word ptr PointCnt, dx; // PointCnt 為一行的點數
Next_Point:
　　　　cmp PointCnt, 0; // 點數為零則開始下一行的計算

　　　　je Pre_Next_Row;

　　　　mov ax, [esi]; // 裝載 源點顏色值
　　　　mov bx, [edi]; // 裝載 目標點顏色值

　　　　shl eax, 16; // eax, 左移 16位,
　　　　mov ax, [esi]; // eax = 0RRR RRGG GGGB BBBB 0RRR RRGG GGGB BBBB

　　　　shl ebx, 16; // ebx 左移 16 位

　　　　mov bx, [edi]; // ebx = 0RRR RRGG GGGB BBBB 0RRR RRGG GGGB BBBB

　　　　// ... 源點及目標點顏色拆包, 不懂什么叫拆包？算了這個稱呼是我隨便安上去的……
　　　　and eax, Mask32; // eax = 0000 00GG GGG0 0000 0RRR RR00 000B BBBB
　　　　and ebx, Mask32; // ebx = 0000 00GG GGG0 0000 0RRR RR00 000B BBBB
　　　　// ... 源點及目標點顏色拆包 完畢, 下面進行計算

　　　　sub eax, ebx; // 源顏色減去目標顏色
　　　　xor edx, edx; // 清空 edx
　　　　mov dx, word ptr srcAlphaLevel ; // dx = srcAlphaLevel

　　　　mul edx; // 乘 Alpha 值, edx 被沖掉數據
　　　　shr eax, 5; // 除以32
　　　　add eax, ebx; // 加上 ebx目標顏色

　　　　and eax, Mask32; // 下面進行打包
　　　　mov bx, ax; // bx = Low_Word( eax );
　　　　shr eax, 16; // 把 結果顏色右移 16位，現在 ax = High_Word( eax );

　　　　or ax, bx; // 把ax 與 bx作一下或，即成為16位的結果顏色值, 保存在 ax中

　　　　mov word ptr [edi], ax; // 得到結果

　　　　add esi, 2;
　　　　add edi, 2;
　　　　dec PointCnt;
　　　　jmp Next_Point; // 下一點處理

Pre_Next_Row: // 在開始下一行時的准備工作
　　　　add esi, srcSkipBytes;
　　　　add edi, dstSkipBytes;　　　　
　　　　dec cx;

　　　　jmp Next_Row;
All_End:
　　}
}

　　接下來，是我們的MMX算法了，但我們注意到MMX沒有針對于DWORD及QWORD的乘法，每次我們對像素進行處理時，我們必須進行兩次乘法，實際來說，釆用以上的算法在我的賽揚M處理器 1.6G，512DDR內存,40GSTAT硬槃上，用MMX算法會比使用常規分色量MMX算法要慢，兩圖互換的速度是170fps 左右而常規分分色量MMX能達到270fps，在云風前輩的文章（參考資料13）說能帶來10%的效率提升，但我做不到……因此這里提供是常規的分色量 MMX算法。


void DrawAlphaBlend_MMX(
　　WORD * dstAddr,
　　WORD * srcAddr,

　　DWORD cntX,
　　DWORD cntY,
　　DWORD dstSkipBytes,
　　DWORD srcSkipBytes,
　　DWORD srcAlphaLevel )
{
　　DWORD LeavePoint = cntX & 0x03; // 每次處理四個點,有沒剩余點?

　　DWORD RMask = 0x1F<<10;
　　DWORD GMask = 0x1F<<5;
　　DWORD BMask = 0x1F;

　　cntX >>= 2;// 每行取4的倍數個點
　　__asm
　　{
　　　　mov esi, dword ptr srcAddr; // ebx 為源地址

　　　　mov edi, dword ptr dstAddr; // eax 為目標地址　　

　　　　// red mask
　　　　// mm4 = (2進制) 0111 1100 0000 0000 | 0111 1100 0000 0000 | 0111 1100 0000 0000 | 0111 1100 0000 0000
　　　　mov eax, RMask;
　　　　mov ebx, eax;

　　　　shl eax, 16;
　　　　mov ax, bx;
　　　　movd mm4, eax;

　　　　movq mm1, mm4;
　　　　psllq mm4, 32;
　　　　por mm4, mm1;

　　　　// green mask
　　　　// mm5 = (2進制) 0000 0011 1110 0000 | 0000 0011 1110 0000 | 0000 0011 1110 0000 | 0000 0011 1110 0000
　　　　mov eax, GMask;
　　　　mov ebx, eax;
　　　　shl eax, 16;

　　　　mov ax, bx;
　　　　movd mm5, eax;
　　　　movq mm1, mm5;

　　　　psllq mm5, 32;
　　　　por mm5, mm1;

　　　　// blue mask
　　　　// mm6 = (2進制) 0000 0000 0001 1111 | 0000 0000 0001 1111 | 0000 0000 0001 1111 | 0000 0000 0001 1111
　　　　mov eax, BMask;

　　　　mov ebx, eax;
　　　　shl eax, 16;
　　　　mov ax, bx;

　　　　movd mm6, eax;
　　　　movq mm1, mm6;
　　　　psllq mm6, 32;

　　　　por mm6, mm1;

　　　　// alpha group
　　　　// mm7 = (16進制) 00AA 00AA 00AA 00AA
　　　　mov eax, srcAlphaLevel;
　　　　mov bx, ax;

　　　　shl eax, 16;
　　　　mov ax, bx;
　　　　movd mm7, eax;

　　　　movq mm1, mm7;
　　　　psllq mm7, 32;
　　　　por mm7, mm1;

　　　　mov ecx, cntY; // ecx 為要復制的行數
Next_Row: // 下一行處理
　　　　cmp ecx, 0; // 如果 ecx 計數為零，則退出處理

　　　　je All_End;

　　　　mov ebx, cntX; // edx 存儲的是要處理的次數 (每兩個點為一次,兩個點為同時處理的)
Next_Point: // 下兩個點處理
　　　　cmp ebx, 0; // 如果 edx 為零, 則跳到下一行

　　　　je Prepare_Next_Row;

Calculate_Points:
　　　　movq mm0, [esi]; // 取源四點像素
　　　　movq mm1, [edi]; // 取目標四點像素


　　　　movq mm2, mm0;
　　　　movq mm3, mm1;

　　　　// Red
　　　　pand mm2, mm4;

　　　　pand mm3, mm4;
　　　　psrlw mm2, 5; // 右移5位，這個沒什么關系，只要有足夠的進位位置就行了
　　　　psrlw mm3, 5;

　　　　psubsw mm2, mm3; // 有符號減　　　　
　　　　pmullw mm2, mm7; // 有符號乘取低位
　　　　psraw mm2, 5; // mm2 /= 32;

　　　　paddsw mm2, mm3;
　　　　psllw mm2, 5;
　　　　pand mm2, mm4; // mm2 存儲的是紅分量的結果

　　　　// Green

　　　　movq mm3, mm0; // 備份mm0 ---> mm3
　　　　pand mm0, mm5;
　　　　pand mm1, mm5;

　　　　psubsw mm0, mm1; // 有符號減　　　　
　　　　pmullw mm0, mm7; // 有符號乘取低位
　　　　psraw mm0, 5; // mm0 /= 32

　　　　paddsw mm0, mm1;
　　　　pand mm0, mm5;// mm0 存儲的是紅分量的結果

　　　　// Blue
　　　　movq mm1, [edi];　// mm1 = dstColor ( B )

　　　　pand mm3, mm6;
　　　　pand mm1, mm6;
　　　　psubsw mm3, mm1; // 有符號減

　　　　pmullw mm3, mm7; // 有符號乘取低位
　　　　psraw mm3, 5; // mm3 /= 32
　　　　paddsw mm3, mm1;　　　　
　　　　pand mm3, mm6;// mm3 存儲的是紅分量的結果


　　　　por mm0, mm3;
　　　　por mm0, mm2;

　　　　cmp ebx, 0; // 為了復用以上的計算代碼，因此加多一步檢測操作

　　　　je Handle_Leave_Point;

　　　　movq qword ptr [edi], mm0; // 存數據

　　　　// 地址增加
　　　　add esi, 8;

　　　　add edi, 8;
　　　　dec ebx;
　　　　jmp Next_Point; // 跳到下兩個點

Prepare_Next_Row:

　　　　cmp LeavePoint, 0;
　　　　ja Calculate_Points;

Prepare_Next_Row_2:
　　　　add esi, srcSkipBytes; // 源地址跳過不處理字節

　　　　add edi, dstSkipBytes; // 目標地址跳過不處理字節　　　　
　　　　dec ecx;
　　　　jmp Next_Row; // 跳去處理下一行

Handle_Leave_Point: // 處理剩下的點
　　　　// 來到這里肯定是有 1 ~ 3個點

　　　　movd eax, mm0;
　　　　mov word ptr [edi], ax;
　　　　inc edi;

　　　　inc edi;
　　　　inc esi;
　　　　inc esi;

　　　　// 判斷是否大于１個點
　　　　cmp LeavePoint, 1;

　　　　jna Prepare_Next_Row_2;

　　　　shr eax, 16;
　　　　mov word ptr [edi], ax;

　　　　inc edi;
　　　　inc edi;
　　　　inc esi;
　　　　inc esi;

　　　　// 判斷是否大于2個點
　　　　cmp LeavePoint, 2;

　　　　jna Prepare_Next_Row_2;

　　　　psrlq mm0, 32;
　　　　movd eax, mm0;
　　　　mov word ptr [edi], ax;

　　　　inc edi;
　　　　inc edi;
　　　　inc esi;
　　　　inc esi;

　　　　jmp Prepare_Next_Row_2;

All_End: // 操作結束
　　　　emms;
　　};
}

參考資料：
1. http://dev.gameres.com/Program/Visual/2D/WindowsAlpha.mht Windows的位图alpha混合技术
2. http://dev.gameres.com/Program/Visual/2D/256Alpha.htm 基于256色的Alpha混合方法（查表法）的实现方法
3. http://dev.gameres.com/Program/Visual/2D/Alphajd.htm 16位Alpha混合的简单算法
4. http://dev.gameres.com/Program/Visual/2D/Ddutil.htm 来自alpha混合的困惑
5. http://dev.gameres.com/Program/Visual/2D/IntelAlpha.htm 可能是最快的算法alpha blend汇编源代码，Intel官方提供
6. http://dev.gameres.com/Program/Visual/2D/qAlpha.htm 快速Alpha混合
7. http://dev.gameres.com/Program/Visual/2D/AlphaQiantan.htm Alpha混合浅谈
8. http://dev.gameres.com/Program/Visual/2D/16MMXa.htm 16位Alpha混合的MMX优化
9. http://dev.gameres.com/Program/Visual/2D/AlphaBlending.htm Alpha-Blending 技术简介
10. http://dev.gameres.com/Program/Visual/2D/mmxaddalpha.htm MMX版本的Alpha Blend算法实现
11. http://dev.gameres.com/Program/Visual/2D/16bitalpha.htm 16位BIT模式下的ALPHA运算
12. http://dev.gameres.com/Program/Visual/2D/64Kalpha.htm 64K 色模式下的快速 Alpha混合算法
13. http://dev.gameres.com/Program/Visual/2D/MMXAlpha.htm 利用MMX优化64K色Alpha混合算法
14. http://dev.gameres.com/Program/Visual/2D/JianYiAlpha.htm 简易Alpha混合算法