【算法】解释RLE8压缩的BMP文件

0xAA55

BMP文件是位图文件，它自带了一种很无用的压缩功能——Run-Length Encode压缩算法。
BMP文件的结构是一个BITMAPFILEHEADER和一个BITMAPINFO，后面就是位图信息了。其中BITMAPINFO是一个BITMAPINFOHEADER和一个调色板。这几个结构体都定义在Windows.h里（可能并不是直接在里面定义的）
BITMAPINFOHEADER中的biCompression成员指定了这个位图是否经过压缩。它有四个数值：BI_RGB（没有压缩）、BI_RLE8（8位RLE压缩）、BI_RLE4（4位RLE压缩）、BI_BITFIELD（在BITMAPINFO的调色板位置指定了颜色值的红绿蓝的位域定义，这个不是“压缩”）。
如果BITMAPINFOHEADER.biCompression的值是BI_RLE8或BI_RLE4，那么BITMAPINFOHEADER.biSizeImage的值就是压缩过的全部位图数据的尺寸了。
它的压缩算法是这样的：
用非零字节表示重复的像素，比如03 55，相当于55 55 55，或者10 AA，那就是AA AA AA AA AA AA AA AA AA AA AA AA AA AA AA AA。
而如果是零，那么紧接着后面的那个字节用于表示“特殊的情况”。如果是00 00，那么表示这是一行的结尾，如果是00 01，那是整个位图的结尾，而如果是00 02，那么紧接着后面的两个字节表示下一个要描述的像素的坐标偏移量（比如00 02 10 10，表示下一个要描述的像素的位置在相对当前像素(16,16)的位置）
如果紧接着后面的字节不是0、1、2，那么表示后面的字节是“没有经过压缩”的，这些字节应该是2字节对齐，不足的用00补全，比如00 05 12 34 56 78 9A 00，表示12 34 56 78 9A。
假设一个位图有如下的数据：
03 04 05 06 00 03 45 56 67 00 02 78 00 02 05 01
02 78 00 00 09 1E 00 01
那么它解压后应该是这样：
04 04 04 06 06 06 06 06 45 56 67 78 78 然后下一个像素的位置相对于当前是05 01
78 78 跳到下一行
1E 1E 1E 1E 1E 1E 1E 1E 1E 位图结束
用类似C语言的伪代码表示解压RLE8的过程是：

1. unsigned x,y;
   
2. size_t i;
   
3. BITMAPFILEHEADER BMFH;
   
4. BITMAPINFOHEADER BMIF;
   
5. BYTE*pbImage;
   
6. 
   
7. int Escape=0;
   
8. int Repeat=0;
   
9. int Absolute=0;
   
10. BYTE NbToCopy,NbCopied;
    
11. int Delta=0;
    
12. 
    
13. //打开文件
    
14. fp=fopen(文件名,"rb");
    
15. 
    
16. //读取BMP文件头
    
17. fread(&BMFH,1,sizeof(BMFH),fp);
    
18. fread(&BMIF,1,sizeof(BMIF),fp);
    
19. 
    
20. //分配内存存储压缩后的数据
    
21. pbImage=(BYTE*)malloc(BMIF.biSizeImage);
    
22. 
    
23. //读取位图文件
    
24. fread(pbImage,1,BMIF.biSizeImage,fp);
    
25. 
    
26. x=0;y=0;
    
27. for(i=0;i<BMIF.biSizeImage;i++)
    
28. {
    
29.         if(Escape)//如果当前字节是“额外信息”
    
30.         {
    
31.                 if(Delta==1)//如果是要确定下一个像素的X位置
    
32.                 {
    
33.                         x+=(int)pbImage[i];//当前字节决定下一个像素的X位置
    
34.                         Delta=2;//确定下一个像素的Y位置
    
35.                         continue;
    
36.                 }
    
37.                 if(Delta==2)//如果是要确定下一个像素的Y位置
    
38.                 {
    
39.                         y+=(int)pbImage[i];//当前字节决定下一个像素的Y位置
    
40.                         Delta=0;//像素确定完毕
    
41.                         continue;
    
42.                 }
    
43.                 if(Absolute)//绝对模式，也就是复制没有经过压缩的数据
    
44.                 {
    
45.                         if(NbCopied<NbToCopy)//如果没有复制完数据
    
46.                         {
    
47.                                 画像素(x++,y,pbImage[i]);//x,y,颜色
    
48.                                 NbCopied++;
    
49.                         }
    
50.                         else if(NbCopied & 1)//绝对模式下的原始数据必须是2字节对齐。
    
51.                                 NbCopied++;
    
52.                         else//已经复制完并且对齐
    
53.                                 Absolute=0;
    
54.                         continue;
    
55.                 }
    
56.                 //如果没有确定对这个字节的操作
    
57.                 switch(pbImage[i])
    
58.                 {
    
59.                 case 0://行结尾
    
60.                         x=0;
    
61.                         y++;
    
62.                         break;
    
63.                 case 1://位图结尾
    
64.                         goto EndOfBitmap;
    
65.                 case 2://确定下一个像素的位置
    
66.                         Delta=1;
    
67.                         break;
    
68.                 default://绝对模式
    
69.                         Absolute=1;
    
70.                         NbToCopy=pbImage[i];
    
71.                         NbCopied=0;
    
72.                         break;
    
73.                 }
    
74.                 continue;
    
75.         }
    
76.         if(Repeat)//如果上一个字节确定了这个字节的重复量
    
77.         {
    
78.                 while(Repeat--)//重复画这个字节
    
79.                         画像素(x++,y,pbImage[i]);//x,y,颜色
    
80.                 Repeat=0;
    
81.                 continue;
    
82.         }
    
83.         if(pbImage[i])//任何操作都没有确定
    
84.                 Repeat=(int)pbImage[i];
    
85.         else
    
86.                 Escape=1;
    
87. }
    
88. 
    
89. EndOfBitmap:
    
90. //位图读取完毕

复制代码

或者用x86汇编表示就是这样：

1. mov esi,源                ;源=RLE压缩数据
   
2. mov edi,目标        ;目标=解压后的位图数据
   
3. xor ecx,ecx
   
4. 
   
5. ParseRLE8:                ;开始分析RLE压缩的数据
   
6. lodsb                        ;先读取一个字节
   
7. or al,al                ;判断是否进入Escape
   
8. jz Escape
   
9. 
   
10. mov cl,al                ;非Escape模式，重复写入下一个字节。
    
11. lodsb
    
12. rep stosb
    
13. jmp ParseRLE8        ;继续
    
14. 
    
15. Escape:                        ;Escape模式：
    
16. lodsb                        ;读取一个字节，判断操作
    
17. cmp al,0
    
18. jz EOL                        ;0=行结尾
    
19. cmp al,1
    
20. jz EOB                        ;1=位图结尾
    
21. cmp al,2
    
22. jz Delta                ;2=设置下一个像素的偏移坐标
    
23. 
    
24. mov cl,al                ;其它=绝对模式
    
25. shr cl,1
    
26. rep movsw                ;先按照字复制
    
27. and al,1                ;然后复制剩余部分
    
28. jz .nomore
    
29. movsb
    
30. .nomore:
    
31. jmp ParseRLE8        ;继续
    
32. 
    
33. EOL:                        ;行结尾处理方式
    
34. mov eax,edi
    
35. xor edx,edx
    
36. sub eax,目标        ;取得当前总共写入的字节数
    
37. div dword[每行字节数];计算当前的行数
    
38. inc eax
    
39. mul dword[每行字节数];再计算下一行的字节偏移
    
40. add eax,目标        ;然后加上目标的地址，计算下一个像素的指针。
    
41. mov edi,eax
    
42. jmp ParseRLE8        ;继续
    
43. 
    
44. EOB:                        ;位图结尾
    
45. jmp 搞定
    
46. 
    
47. Delta:                        ;指定下一个像素的位置
    
48. xor eax,eax
    
49. lodsb
    
50. add edi,eax                ;x偏移
    
51. lodsb                        ;y偏移
    
52. mul dword[每行字节数]
    
53. add edi,eax
    
54. jmp ParseRLE8        ;继续

复制代码

0xAA55

这两种语言的处理逻辑完全不一样。C语言是基于当前读取的字节来判断，而汇编的则是直接根据需求读取要解压的内容然后直接写目标。