屏幕传输算法

转载自：http://www.dewen.org/q/484

发一下以前研究过的屏幕传输算法，垫垫底。

屏幕监控是远程控制中的一项主要功能，有了此功能能使操作远程电脑像操作本地电脑一样方便。
实现方法很多，原理就是不断地把远程电脑屏幕的图像发送到本地电脑，本地电脑把图像显示出来。
最早期的实现方法只是不断地传送bmp图像，这样做不仅传输延时很大，且cpu特别是服务端的cpu占用率很大。
为了解决以上两个问题，可以采用传输屏幕变化的部分，传输过程中压缩解压缩的方法。

传输屏幕变化的部分：应用得比较好的有3种方式，1.驱动级的Mirror Driver 、2.GDI+下的算法方式，3.RDP传输协议(远程桌面)

Mirror Driver
大名鼎鼎的VNC就是采用这种技术，屏幕传输像看电影一样非常流畅且cpu占用率为0%~1%。
传统截取屏幕采用api hook方式，调用bitblt截取的是ddb位图，要用getbits转换为dib格式的位图，不仅增加截屏的时间消耗，而且会截取未变化的区域，产生冗余数据。
而使用Mirror Driver的图形驱动技术 ，应用程序调用win32 gdi 函数进行图形输出请求，这个请求通过核心模式gdi发送。核心模式gdi把这些请求发送到相应的图形驱动程序。如，显示器驱动程序，通信流程图如下：

使用这种截屏技术较API Hook截屏方式的优越性在于：
1。驱动截屏技术是一种标准技术，为微软公司所推荐，而API Hook截屏是一种非标准的技术，不为微软公司所推荐。
2。API Hook技术在实际截屏时，采用API函数实现，截取DDB位图，必须经过一次DDB到DIB的转换；而驱动技术直接从其管理的DIB位图（表面）中将截取区域的图形数据拷贝到应用程序，显著的降低了一次截屏的时间消耗。
3。如果屏幕图形小区域范围变化较快，屏幕变化区域矩形坐标R1、R2、R3……、Rn相继到达，由于一次截屏时间消耗降低，区域矩形坐标叠加的概率变小，这样屏幕变化区域及时的得到了处理，不仅增加了连续性，而且产生的数据量很小。
所以无论是做远程桌面还是屏幕录制，基于MirrorDriver的屏幕截取将会是一个不错的选择，无论从性能，占用资源的大小来说都要优于API Hook的截屏方式。

Mirror  Dirver 技术涉及核心图形驱动的编写，实现上较为复杂，网络上也没有开源的driver ，但可以利用免费的driver，如Tight  VNC中提供的Mirage  Driver，UtralVNC中提供的Winvnc   video  hook  driver，下载安装程序安装即可。安装后可以在设备管理器中看到如下所示的图：

调用Mirror  Driver 的代码可以从VNC源代码中去挖掘，VNC中都封装好了与Mirror  Driver 的调用关系，我们只用关心VNC中封装的一个指向变化矩形的RECT结构和一个指向变化数据的指针。在我们的屏幕传输模块中，服务端发送一个RECT结构，发送一个由数据指针指向的byte[]数组，客户端接收到数据，按RECT结构中的4个点把byte[]数组Paint到Picture控件中，然后再重复上面的操作，即可发送屏幕的变化部分。虽然使用Mirror  Driver 技术cpu占用率小、网络传输数据量小，但是需要安装驱动程序，每次截屏的时候屏幕会出现明显的刷新，且有时处理不当会出现BSOD(Blue  Screen Of  Death)。对于一个具有高隐蔽性的木马来说Mirror  Driver技术来做屏幕传输是不适合的。**GDI下 的算法方式**：算法是程序的灵魂，在这里可以看到算法在优化屏幕传输上所起的作用。应用得比较好的算法分为分块异或屏传，固定块隔行扫描，动态分块隔行扫描。

分块异或屏传：
原理：前后保存两次bmp位图，把屏幕分成若干块(局域网一般为4~6块，广域网一般为8~32块)并编号，前后两副位图分别按对应编号块逐个像素点做异或(XOR)操作，若异或后的结果全是零,证明两个被分块的位图相等，不为零则两个被分块的位图不相等，不相等则把异或的结果进行压缩，并发送。
每个块处理完后，则把后一副图像记为前一副图像，再保存一副bmp位图作为后一副图像，再执行前面的分块异或发送操作。

注意这里为什么要每个像素点做异或操作，再压缩发送，而不是每块图像做CRC32，不相同则直接发送图像呢？
因为屏幕上的变化在很短的时间内，往往都是小范围的变化，这就意味着有很多相同的像素点，那么两块图像异或的结果就会有很多的零。
这么多的零经过压缩算法压缩，数据量会减少很多。比如 经过压缩后，10000001 可以表示为10*61的形式，当然压缩算法不只是压缩连续的0或1。
经过以上算法优化传输屏幕变化，实际的网络传输量会变得很小，屏幕传输流畅，著名的灰鸽子屏幕传输就采用此算法。

固定块隔行扫描，动态分块隔行扫描：
Radmin影子远程控制系统相信很多人都知道，用到4899端口，早期系统管理员用来管理远程的计算机。速度很快，特别是屏幕传输，可以和3389远程桌面媲美。
Radmin是俄罗斯人编写的收费软件，没有开源的代码，隔行扫描算法最初是受到其反汇编代码启发得来的。
原理：前后保存两次bmp位图，把屏幕分成若干块并编号，前后两副位图分别按对应编号块对比，对比的方法是，隔若干行(一般是10行)对比前后两幅图像的一行中的像素点是否相同,若不同则压缩发送当前块中的图像。
因为是隔若干行对比一行，所以叫隔行扫描。只用扫描少数的行，就可以判断屏幕变化的部分，速度是很快的。
接着，有人提出这样每次只能扫描那些固定的行，所以每次重新扫描时会对上次扫描的行编号+n行，这样就避免了总是扫描相同的行，称为“百叶窗”技术。
随后算法经过优化，出现了“动态分块隔行扫描”算法，应用此算法，速度更快。
原理：在固定块隔行扫描的基础上，改“把屏幕分成若干块”为“由屏幕的变化区域动态确定要发送的矩形”。当扫描到有不相同的行时，由一个恒定的值确定变化矩形的宽，然后在这个宽度范围内向左和向右对比像素点，确定变化矩形的长，再把矩形的坐标点和矩形的图像(byte[]数组)保存到发送队列，接着由之前 扫描行的编号+矩形的宽度所得的行编号开始扫描，重复上面的操作，扫描到屏幕的最后一行为止，最后服务端传输发送队列的数据到客户端。客户端按矩形的坐标和数据，把矩形paint到picture控件上。
动态分块隔行扫描示意图：

近期，在动态隔行扫描算法的基础上，又发展起来“热点追踪”的思想，即跟踪鼠标的操作，因为这是最容易引起变化的地方，因为鼠标的移动，鼠标的点击，屏幕都会变化。

在我开发的程序中，使用了“动态分块隔行扫描+热点追踪”的算法，速度流畅，cpu占用率小。

总结：在这里可以看到算法的力量了，为什么会创造出这么好的算法呢？ 其实万变不离其中，以上算法都衍生于《计算机程序设计的艺术》一书中所介绍的算法。“动态分块”的思想来自“动态规划”算法，“固定分块”的 思想来自“分治法”，分而治之的思想。
压缩解压缩：在屏幕传输中压缩算法的好坏，直接影响屏幕传输的流畅度和cpu的占用率。压缩图像的算法很多，JPEG、Huffman、RLE(Run Length Encode)、LZW等，TSP木马选用的LZW压缩算法。