找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 4970|回复: 1

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

[复制链接]

1109

主题

1649

回帖

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
244
威望
743 点
宅币
24180 个
贡献
46222 次
宅之契约
0 份
在线时间
2294 小时
注册时间
2014-1-26
发表于 2015-2-1 22:33:31 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有账号?立即注册→加入我们

×
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. int Escape=0;
  7. int Repeat=0;
  8. int Absolute=0;
  9. BYTE NbToCopy,NbCopied;
  10. int Delta=0;

  11. //打开文件
  12. fp=fopen(文件名,"rb");

  13. //读取BMP文件头
  14. fread(&BMFH,1,sizeof(BMFH),fp);
  15. fread(&BMIF,1,sizeof(BMIF),fp);

  16. //分配内存存储压缩后的数据
  17. pbImage=(BYTE*)malloc(BMIF.biSizeImage);

  18. //读取位图文件
  19. fread(pbImage,1,BMIF.biSizeImage,fp);

  20. x=0;y=0;
  21. for(i=0;i<BMIF.biSizeImage;i++)
  22. {
  23.         if(Escape)//如果当前字节是“额外信息”
  24.         {
  25.                 if(Delta==1)//如果是要确定下一个像素的X位置
  26.                 {
  27.                         x+=(int)pbImage[i];//当前字节决定下一个像素的X位置
  28.                         Delta=2;//确定下一个像素的Y位置
  29.                         continue;
  30.                 }
  31.                 if(Delta==2)//如果是要确定下一个像素的Y位置
  32.                 {
  33.                         y+=(int)pbImage[i];//当前字节决定下一个像素的Y位置
  34.                         Delta=0;//像素确定完毕
  35.                         continue;
  36.                 }
  37.                 if(Absolute)//绝对模式,也就是复制没有经过压缩的数据
  38.                 {
  39.                         if(NbCopied<NbToCopy)//如果没有复制完数据
  40.                         {
  41.                                 画像素(x++,y,pbImage[i]);//x,y,颜色
  42.                                 NbCopied++;
  43.                         }
  44.                         else if(NbCopied & 1)//绝对模式下的原始数据必须是2字节对齐。
  45.                                 NbCopied++;
  46.                         else//已经复制完并且对齐
  47.                                 Absolute=0;
  48.                         continue;
  49.                 }
  50.                 //如果没有确定对这个字节的操作
  51.                 switch(pbImage[i])
  52.                 {
  53.                 case 0://行结尾
  54.                         x=0;
  55.                         y++;
  56.                         break;
  57.                 case 1://位图结尾
  58.                         goto EndOfBitmap;
  59.                 case 2://确定下一个像素的位置
  60.                         Delta=1;
  61.                         break;
  62.                 default://绝对模式
  63.                         Absolute=1;
  64.                         NbToCopy=pbImage[i];
  65.                         NbCopied=0;
  66.                         break;
  67.                 }
  68.                 continue;
  69.         }
  70.         if(Repeat)//如果上一个字节确定了这个字节的重复量
  71.         {
  72.                 while(Repeat--)//重复画这个字节
  73.                         画像素(x++,y,pbImage[i]);//x,y,颜色
  74.                 Repeat=0;
  75.                 continue;
  76.         }
  77.         if(pbImage[i])//任何操作都没有确定
  78.                 Repeat=(int)pbImage[i];
  79.         else
  80.                 Escape=1;
  81. }

  82. EndOfBitmap:
  83. //位图读取完毕
复制代码
或者用x86汇编表示就是这样:
  1. mov esi,源                ;源=RLE压缩数据
  2. mov edi,目标        ;目标=解压后的位图数据
  3. xor ecx,ecx

  4. ParseRLE8:                ;开始分析RLE压缩的数据
  5. lodsb                        ;先读取一个字节
  6. or al,al                ;判断是否进入Escape
  7. jz Escape

  8. mov cl,al                ;非Escape模式,重复写入下一个字节。
  9. lodsb
  10. rep stosb
  11. jmp ParseRLE8        ;继续

  12. Escape:                        ;Escape模式:
  13. lodsb                        ;读取一个字节,判断操作
  14. cmp al,0
  15. jz EOL                        ;0=行结尾
  16. cmp al,1
  17. jz EOB                        ;1=位图结尾
  18. cmp al,2
  19. jz Delta                ;2=设置下一个像素的偏移坐标

  20. mov cl,al                ;其它=绝对模式
  21. shr cl,1
  22. rep movsw                ;先按照字复制
  23. and al,1                ;然后复制剩余部分
  24. jz .nomore
  25. movsb
  26. .nomore:
  27. jmp ParseRLE8        ;继续

  28. EOL:                        ;行结尾处理方式
  29. mov eax,edi
  30. xor edx,edx
  31. sub eax,目标        ;取得当前总共写入的字节数
  32. div dword[每行字节数];计算当前的行数
  33. inc eax
  34. mul dword[每行字节数];再计算下一行的字节偏移
  35. add eax,目标        ;然后加上目标的地址,计算下一个像素的指针。
  36. mov edi,eax
  37. jmp ParseRLE8        ;继续

  38. EOB:                        ;位图结尾
  39. jmp 搞定

  40. Delta:                        ;指定下一个像素的位置
  41. xor eax,eax
  42. lodsb
  43. add edi,eax                ;x偏移
  44. lodsb                        ;y偏移
  45. mul dword[每行字节数]
  46. add edi,eax
  47. jmp ParseRLE8        ;继续
复制代码
回复

使用道具 举报

1109

主题

1649

回帖

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
244
威望
743 点
宅币
24180 个
贡献
46222 次
宅之契约
0 份
在线时间
2294 小时
注册时间
2014-1-26
 楼主| 发表于 2015-2-6 03:12:16 | 显示全部楼层
这两种语言的处理逻辑完全不一样。C语言是基于当前读取的字节来判断,而汇编的则是直接根据需求读取要解压的内容然后直接写目标。
回复 赞! 靠!

使用道具 举报

QQ|Archiver|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2024-3-29 12:40 , Processed in 0.043864 second(s), 32 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表