zenglOX v3.0.2 PNG(Portable Network Graphics) and BUG Fix
zenglong 2015-03-11 17:16:39
当前版本移植了lodepng项目，该项目除了可以分析PNG图片的结构外，还将Deflate即zlib的压缩与解压缩算法也包含进来了，对libc即C库文件的依赖也很小，因此可以方便的移植到hobby OS中 ...
页面导航：
项目下载地址：
v3.0.2版本的项目地址：
github.com地址：https://github.com/zenglong/zenglOX (只包含git提交上来的源代码)
Dropbox地址：点此进入Dropbox网盘
Google Drive地址：点此进入Google Drive云端硬盘
sourceforge地址：https://sourceforge.net/projects/zenglox/files
在上面的三个网盘中(不包括github)，v3.0.2版本的相关文件，都位于zenglOX_v3.0.2的文件夹中，在该文件夹里，zenglOX_v3.0.2.zip文件为当前版本的源代码的压缩包，zenglOX.iso文件为当前版本的iso镜像(读者可以将iso文件挂载到VirtualBox或VMware里，进行测试)，lodepng-master.zip文件为lodepng项目的源代码的压缩包，readme.txt文件为当前版本的说明文档。
概述：
当前版本移植了lodepng项目，该项目的链接地址为：http://lodev.org/lodepng/ ，lodepng除了可以分析PNG图片的结构外，还将Deflate即zlib的压缩与解压缩算法也包含
进来了，对libc即C库文件的依赖也很小，因此可以方便的移植到hobby OS中。
当前版本就创建了一个基于lodepng项目的showpng程式，使用该程式可以将png图片显示出来，显示效果可以查看screenshot目录下的v302_1.jpg截图：
图1
由于showpng程式默认位于iso镜像里，所以需要通过isoget -all命令来获取该程式及相关的png示例图片文件。
如果磁盘没进行过分区格式化的话，先使用fdisk，format工具对磁盘进行分区格式化(当然，也可以将之前版本的磁盘镜像拷贝到当前版本里，Qemu模拟器的磁盘镜像文件为hd_qemu.img)。具体的分区格式化命令，如下所示(仅供参考，你可以根据需要设置自己的分区大小等)：
分区格式化的命令详情，请参考"zenglOX v1.5.0 zenglfs文件系统..."对应的官方文章。
分区格式化后，使用mount命令挂载hd与iso目录:
上面mount hd ...命令的详情，也可以参考"zenglOX v1.5.0 zenglfs文件系统..."的官方文章。
接着就可以使用isoget -all命令了：
上面的isoget -all命令会将showpng程式拷贝到hd/bin目录下，并将相关测试用的png图片拷贝到hd/img目录中。
由于showpng程式会自动搜索hd/img目录，因此，在使用时，直接给出png的文件名即可，如下所示：
解析并显示出一张图片后，showpng会将父任务即shell任务唤醒，让shell继续执行，因此上面就可以在shell中连续运行三个showpng程式了，从而不用为了显示三幅图片而启动三个shell了。
showpng程式与依赖的lodepng项目的源代码位于build_initrd_img目录下的extra目录中，分别对应为showpng.c与lodepng.c文件，其中，lodepng.c文件是从网盘的lodepng-master.zip压缩包里提取出来的，将原来的lodepng.cpp重命名为lodepng.c，并对该文件的代码作了些移植处理，让其可以在zenglOX系统中正常执行。
稍后会根据lodepng源码，对PNG图片结构及Deflate算法进行分析。
=========================================
BUG Fix(BUG修复)
=========================================
1. 修复zlox_kheap.c(内核堆)与zlox_uheap.c(用户堆)中，在对页表项进行操作后，没有更新TLB缓存的BUG。有关TLB缓存的内容，在之前zenglOX v1.0.0版本对应的官方文章中解释过。
之前版本由于没有更新TLB，就容易导致堆里的数据错误。例如，当从iso镜像拷贝比较大的文件时，当触发了堆中的expand(线性地址扩展)操作时，新分配的页表项不能及时更新到TLB里，从而会导致读到堆里的正常数据，会被突然变成一些无效的数据，这些无效的数据写入到磁盘里，就会导致磁盘里的文件会出现部分内容是无效的情况。
2. 修复模拟器下可能出现的无法收到按键irq中断的BUG，主要是对zlox_ps2.c文件里的zlox_ps2_init即PS/2控制器的初始化函数进行调整，直接将PS/2控制器的configure byte即配置字节设置为0x47 ，然后写入到PS/2控制器中。
省略掉之前版本里的读取configure byte的步骤，因为configure byte是通过0x60的I/O端口读取出来的，而0x60端口又被用于鼠标与键盘设备的输入事件中。在鼠标键盘没有被禁用的情况下，0x60端口容易读取出鼠标键盘设备的数据出来，而非真实的configure byte值。
即便鼠标键盘被禁用的情况下，也无法保证0x60读出来的就是原始的configure byte值，因为，很多PS/2命令的反馈信息也需要通过0x60端口读出来。因此，就省略掉读操作，而直接将需要设置的值写进去即可。
有关ps/2控制器的详情，可以参考 http://wiki.osdev.org/%228042%22_PS/2_Controller 该链接对应的维基百科文章。
configure byte里控制了是否开启鼠标键盘设备，以及是否开启鼠标键盘的中断。因此，错误的configure byte值就会导致鼠标或键盘无响应的情况发生。
=========================================
其他的一些改动
=========================================
1. 当用户程式通过系统调用，出现内存地址不存在之类的分页错误时，只会当掉当前任务，不会当掉整个系统。改动的地方位于zlox_paging.c文件的zlox_page_fault函数里。
2. 增加shift + tab系统热键，当你同时按下shift与tab键时，可以在各窗口之间进行切换，当然桌面是不参与窗口的这种切换的。
之所以不用alt + tab组合键，是因为该组合键容易被模拟器所在的主机给劫持掉(主要是bochs模拟器)，而且alt作为通用热键，在模拟器下有时候收不到释放信号(松开alt键时，有时收不到相关的中断信号)。
shift + tab组合键最终会通过zlox_my_windows.c文件的zlox_shift_tab_window函数来进行切换窗口的操作。
另外，在你拖动窗口时，该系统热键是不会起作用的。因为拖动窗口时，又进行切换窗口的话，容易导致一些显示上的问题。
PNG(Portable Network Graphics)：
在当前版本中，提供了几个测试用的png图片文件，下面我们以isodir/img/r.png文件为例，来对PNG结构进行分析：
Linux下可以使用vim编辑器来查看文件的十六进制格式的数据。一开始通过vim编辑器打开r.png文件时，会看到一堆乱码，因为png里存储的数据，大部分是一些图像结构数据和一些压缩数据。可以在vim中，先输入冒号进入交互式命令界面，然后输入%!xxd命令，就可以切换到如上所示的十六进制编辑界面。该界面与windows下的十六进制编辑器winhex软件的界面就很像了，适合在Linux下分析PNG文件的结构。要让vim返回到原始数据界面，可以在交互式命令中输入%!xxd -r命令(也就是给%!xxd添加一个-r参数)即可。由于我们不需要修改png文件，因此，在退出vim时，请使用q!命令：强制以不保存的方式来退出编辑器。
在 http://en.wikipedia.org/wiki/Portable_Network_Graphics (维基百科链接) 和 http://tools.ietf.org/html/rfc2083 (RFC2083)这两个链接中，都对PNG的文件结构作了介绍。
首先，PNG文件的开头是8个字节的标准头部信息：
可以通过上面的89 50 4e 47 0d 0a 1a 0a这8个字节来大致的识别出一个文件是否是PNG类型。因此，这8个字节可以看作是PNG的signature(签名)。
第1个字节0x89已经超过了ASCII表里的最后一个0x7f字符，当编辑器读取到这个字节时，就知道该文件是一个包含了非ASCII码在内的二进制文件，就可以将其当成二进制文件来处理。
第2个到第4个字节：0x50 0x4e 0x47则是'P'，'N'，'G'这三个字符的ASCII码，使用普通的文本编辑器查看文件时，通过这三个字符就可以初略的看出文件类型出来。
第5个到第6个字节：0x0d 0x0a则是DOS风格的换行符(CRLF)。
第7个字节：0x1a是end-of-file(文件结束字符)，当在dos下使用type命令显示文件内容时，通过这个文件结束符，就可以停止文件内容的显示，以防止在dos下将后面的图像数据以乱码的形式显示出来。
第8个字节：0x0a则是unix风格的换行符。通过换行符就可以在普通文本编辑器中，将PNG的头部与其他数据通过换行隔开。
PNG的标准头部信息之后，是由一系列的chunks(块)组成：
上面红色标记的十六进制部分，就是PNG里的第一个chunk(块)，从右边的ASCII显示区域里，可以看到这是一个IHDR类型的块。PNG头部信息之后的块，都必须以一个IHDR类型的块开始，并以一个IEND类型的块结束。在这两个块之间，可以包含多个其他类型的块。
每个chunk(块)都由4个部分组成：第一部分是块的Length(长度)信息，例如上面的0000 000d这4个字节就表示IHDR块的第3个data数据部分的长度为13个字节。第二部分是块的类型，例如上面的4948 4452就是类型的ASCII编码，对应为IHDR这4个字符。第三部分为块的data数据部分，例如上面的0000 00c3 0000 00c5 0802 0000 00这13个字节就是IHDR块的数据部分，块数据部分的字节的二进制含义是跟块类型相关的。第四部分是块的CRC(Cyclic Redundancy Check)即循环冗余校验部分，例如上面的66 44d1 e0这4个字节，用于校验块类型与块数据部分是否正确(但不包括块长度部分)，CRC校验算法在上面给出的RFC2083链接中有介绍。
PNG文件里的第一个块必须是IHDR块，IHDR块的数据部分的结构如下(以上面提到的0000 00c3 0000 00c5 0802 0000 00这13个字节为例进行说明)：
在r.png图片中，跟随在IHDR块后面的是IDAT块：
根据前面介绍的块结构可知，上面红色标记的十六进制数据中，开头的00 00a6 1e这4个字节是块的长度，由于是PNG里的结构数据是采用的大字节序(与网络传输相对应，网络中也是采用的大字节序来进行数据传输)，因此，IDAT块的data数据部分的长度为0x0000a61e即42526字节，长度信息后面的49 4441 54这4个字节则是'I'，'D'，'A'，'T'这4个字符的ASCII码。然后，接下来的78 daac 9d77 b85d 5599 fff7 ...... 这42526个字节的数据就是IDAT块的实际的数据部分，该部分的数据是经过zlib压缩过的数据。在zlib标准中，本身是可以包含不同的压缩算法在里面的，在PNG中目前主要使用的是Deflate压缩算法，zlib可以看作是对Deflate压缩好的数据的一层封装。
在 http://tools.ietf.org/html/rfc1950 (RFC1950)的链接中，就介绍了zlib标准的封装格式，大致的封装格式如下所示：
上面的CMF是Compression Method and flags的英文缩写，它由单个字节组成，该字节里的低4位用于表示CM(Compression method即压缩方法)，高4位用于表示CINFO(Compression info即和压缩方法相关的一些压缩信息)。当低4位的CM为8时，表示上面所示的compressed data压缩数据部分是采用的Deflate压缩算法，当高4位的CINFO为7时，则表示LZ77编码的window size(窗口尺寸)为32K，LZ77编码是Deflate算法在正式压缩之前，对数据的一种预处理过程，它可以减少重复的数据所占用的空间，比如可以将重复的数据用distance距离偏移值及length长度来表示等，window size是编码算法中所使用的缓存的尺寸大小。前面r.png图片的IDAT块的数据部分的第一个字节就是0x78，低4位为8，说明r.png采用的是Deflate压缩算法，高4位为7，说明LZ77编码的窗口尺寸为32K。
上面的FLG是flag标志字节，该字节由三个部分组成：
低4位的FCHECK是用于校验CMF与FLG字段的。FDICT用于判断是否存在DICTID，当该位被置1时，则说明FLG与compressed data压缩数据之间存在DICTID即词典的ID值，当该位为0时，则不存在DICTID。FLEVEL字段用于表示压缩级别，具体的级别值与含义，请参考zlib的RFC1950链接。前面r.png里的IDAT块的数据部分的第二个字节是0xda，因此，r.png的FCHECK值为0x1a，FDICT为0，也就是没有DICTID，FLEVEL的值为3，即压缩级别为3，也就是maximum compression(最大化的压缩)。
由于r.png没有DICTID，因此，跟在CMF与FLG这两个字节后面的数据就是compressed data(压缩的数据)：
上面的ac 9d77 b85d 5599 fff7 ...... 这些压缩数据是采用Deflate算法来压缩的，要了解Deflate的解压缩过程，最好的方法是先通过一些简单的例子，结合gdb调试器，加上lodepng项目的源代码，分析清楚它的压缩过程，在了解了压缩过程后，解压缩过程也就一目了然了。因此，下面将通过lodepng项目的一个测试例子来进行说明。
从网盘中下载并解压lodepng-master.zip文件：
上面将lodepng-master.zip解压到了lodepng目录中，进入解压后的目录，并在该目录内创建一个mytest目录：
将lodepng.cpp与lodepng.h拷贝到mytest里：
上面在拷贝时，将lodepng.cpp重命名为lodepng.c，因为，下面我们要测试的是C程式，在使用lodepng项目时，当编写C++程式时，就使用lodepng.cpp文件名，当编写C程式时，就使用lodepng.c文件名。
使用编辑器创建一个mytest.c文件，内容如下：
上面测试代码中，会使用lodepng_deflate函数将in字符串进行Deflate压缩，压缩后的数据存储到out缓存里，接着再用lodepng_inflate函数将out里的压缩数据，解压缩到out2缓存里，可以先用gdb来进行简单的调试，通过对比in与out2的字符串值，就可以知道压缩与解压缩是否成功了：
上面先通过gcc将mytest.c与lodepng.c文件一起编译为mytest程式，通过gdb调试可以看到，out缓存里的0x05 0xc1 0x01 0x01 0x00 ...... 这17个字节就是字符串"AABCCDD"经过Deflate算法压缩后的数据，最后，out2里的解压缩后的字符串也是"AABCCDD"，因此，压缩与解压缩测试通过。
下面只需要通过gdb调试lodepng_deflate函数，就可以了解其压缩过程了，不过要完全理解Deflate的话，还必须先了解Deflate的一些基本标准(一些文字上的基本说明)，Deflate算法的文字说明可以参考 http://tools.ietf.org/html/rfc1951 (RFC1951)的链接。另外，Deflate又用到了信息论里的霍夫曼编码，有关霍夫曼编码的详情，可以参考 霍夫曼编码_维基百科 该链接对应的维基百科文章，霍夫曼编码可以说是整个压缩算法的核心理论依据，所以，最好是先了解霍夫曼编码，再去看Deflate的RFC1951文档，RFC1951文档的开头部分还好理解(结合霍夫曼编码的理论知识来看)，看到后面，如果没有lodepng项目的源代码的话，估计会比较难理解。
lodepng_deflate函数最终会进入deflateDynamic函数来完成具体的压缩工作：
该函数中，会先执行LZ77编码，前面提到过，LZ77用于在压缩之前，对数据做个预处理：
由于原始数据比较短，没什么长的重复性的数据，因此，预处理中，直接将"AABCCDD"这几个字符依次写入到data数组中，作为后面需要处理的数据源。
deflateDynamic函数接着会通过下面的代码，来计算'A'，'B'，'C'，‘D’这几个字符出现的频率：
也就是统计'A'出现了几次，'B'出现了几次等等，同时还添加了一个额外的256，用来表示结束符。
然后根据频率信息，就可以通过HuffmanTree_makeFromFrequencies函数来构建霍夫曼树了：
在HuffmanTree_makeFromFrequencies函数里，会通过lodepng_huffman_code_lengths函数来构建霍夫曼的二叉树(采用相关的coins算法)：
根据上面的coins，我们可以画出如下所示的二叉树：
图2
从上图所示的二叉树里，我们可以得到A，B，C，D的编码位长度信息：
上面lengths['A']为2，即在压缩数据里，可以只用2个二进制位来表示'A'。同理，lengths['B']为3，即可以用3个二进制位来表示'B'。
在lodepng_huffman_code_lengths函数得出编码的位长度信息后，就会进入到HuffmanTree_makeFromLengths2函数，来正式构建与编解码相关的tree(树)结构，在介绍该函数之前，需要先了解下HuffmanTree结构体，该结构体的定义如下(位于lodepng.c文件中)：
在HuffmanTree结构体中，lengths(编码位长度)字段已经在之前的函数里得出来了，通过lengths字段可以进一步得出上面的tree1d字段，具体代码如下：
通过上面的step 1，step 2及step 3这三个步骤(这3个步骤是上面提到的RFC1951文档里设计好的算法)，就可以由lengths数组换算出tree1d数组的值出来：
从上面gdb的输出信息里可以看到，'A'的编码位长为2，对应的tree1d['A']值为0x3f0，而0x3f0的二进制格式为：0011 1111 0000，则红色标记的00即0x3f0的最低2位就是'A'的二进制编码。
'B'的编码位长为3，对应的tree1d['B']值为0x7e6，而0x7e6的二进制格式为：0111 1110 0110 ，则红色标记的110即0x7e6的最低3位就是'B'的二进制编码。
'C'的编码位长为2，对应的tree1d['C']值为0x3f1，则'C'的二进制编码为01。
'D'的编码位长为2，对应的tree1d['D']值为0x3f2，则'D'的二进制编码为10。
但是实际存储的压缩编码是翻转后的编码，例如110会被存储为011，这需要理解下面的tree2d数组，以及解压缩时，二进制流的读取方式才能理解(二进制流是从低位往高位来读取的，tree2d数组则是从高位往低位来构建的)。
在前面构建出tree1d数组后，就可以通过HuffmanTree_make2DTree函数来构建tree2d数组了：
gdb中的调试输出情况如下：
上面tree1d['A']的值为0x3f0，0x3f0的低2位为00，因此，bit = (unsigned char)((tree->tree1d[n] >> (tree->lengths[n] - i - 1)) & 1)语句在i为0时，读取出来的bit就是0，并且一开始treepos值为0，那么，tree->tree2d[2 * treepos + bit]对应的就是tree->tree2d[0]，由于此时的bit不是last bit(最后一位)，因此，tree->tree2d[0]就被设置为了nodefilled + tree->numcodes的值，其中，nodefilled值为1，tree->numcodes的值为257，因此，tree->tree2d[0]的值就是258。
接着，当i为1时，读取出的第二个bit也是0，treepos此时变为了1，由于该bit是最后一个二进制编码，因此tree->tree2d[2 * treepos + bit]即tree->tree2d[2]就被设置为了'A'的ASCII码，也就是65。
从这里可以看出来，tree2d数组实际上就是用来解压缩用的，当我们从需要解压的二进制流中第一次读取出bit(二进制位)，且bit为0时，一开始treepos为0，则tree->tree2d[2 * treepos + bit] 就是 tree->tree2d[0] ，而tree->tree2d[0]的值为258，258大于257(总编码数)，用258减去257，得到的1作为下一次的treepos值，接着，我们从二进制流中再读取出一个bit，假设该bit的值也为0，那么tree->tree2d[2 * treepos + bit]就是tree->tree2d[2]，而tree->tree2d[2]的值为65，65小于257，那么这个65就是刚才读取出来的二进制编码00所对应的解压后的值了，65是'A'的ASCII码，这样就将'A'解压还原出来了。
因此，"AABCCDD"的压缩过程，其实就是：先得到他们的lengths(编码位长度)，由lengths计算出tree1d数组，压缩过程不计算tree2d应该也可以，只不过计算下tree2d可以防止溢出等错误发生，保存压缩数据时，只需先将lengths保存在前面，然后结合tree1d数组，将'A'，'B'，‘C’，‘D’实际的二进制编码保存在lengths后面即可。
解压缩时，先将lengths读取出来，由lengths计算出tree1d数组，再由tree1d与lengths计算出tree2d数组，最后将lengths后面的二进制流一位一位的读取出来，每读取一位，就将该二进制位在tree2d数组中进行定位，当从tree2d数组中读取出来的值小于257(总编码数)时，那么该值就是需要解压出来的数据了。
在实际保存压缩数据时，Deflate算法还将lengths信息又做了一次霍夫曼编码，因为，lengths数组里存储的是257个编码的编码位长度信息，因此，有必要先压缩一下再输出。
lodepng.c文件的deflateDynamic函数里的tree_cl ，就是上面的lengths经过霍夫曼编码后，所形成的霍夫曼树，tree_cl作为HuffmanTree结构体变量，里面同样存在lengths，tree1d，tree2d这些数组，因此，在最终形成的压缩数据里，一开始会是tree_cl的lengths信息，然后是由tree_cl的lengths与tree1d所得出的二进制编码流。所以，实际解压缩时，会先由tree_cl的lengths，计算出tree_cl的tree1d数组，再由tree_cl的lengths结合tree_cl的tree1d来得出tree_cl的tree_2d数组，接着，将其后的二进制流通过tree_cl的tree2d数组来还原出实际编码的lengths信息出来，由实际编码的lengths计算出实际编码的tree1d，再计算出实际编码的tree2d，最后，将余下的实际编码的二进制流，通过实际编码的tree2d来还原出需要解压缩的值出来。
在tree_cl的lengths之前，Deflate算法还会放入一些其他的信息：
第一个BFINAL二进制位用于表示当前块是否是压缩数据流中的最后一块，接着写入10作为BTYPE的二进制值(从低位往高位方向写入)，表示采用dynamic Huffman codes(动态霍夫曼编码)，将HLIT即tree_ll(该霍夫曼树里有'A'，‘B’, 'C', 'D'之类的编码的lengths，tree1d，tree2d等信息)的总编码数减去257，并输出到接下来的5位中，将HDIST即tree_d(该霍夫曼树主要用于LZ77编码里重复性数据的处理)的总编码数减去1，并输出到接下来的5位中，最后得出HCLEN即上面提到过的tree_cl的lengths数组的长度信息，解压缩时，就需要先根据HCLEN的值，来将tree_cl的lengths数组给读取出来。此外，一开始读取出来的tree_cl的lengths数组的值是打乱过的，在lodepng.c文件里有一个CLCL_ORDER数组，该数组里的值就是根据RFC1951文档来设置的：
通过上面这个数组，就可以将tree_cl里打乱的lengths数组里的值还原为正常顺序。
前面提到的mytest测试程序里的out变量用于存储压缩数据：
上面out变量里的17个字节是压缩数据，这些数据的解压过程如下图所示：
图3
以上就是Deflate相关的内容。限于篇幅，作者只能介绍其中一部分内容，读者如果需要完全弄清楚里面的机制，还需要结合前面提到的RFC1951文档与lodepng.c文件的代码，进行更深层次的分析。
lodepng项目，在将PNG图片里的压缩数据通过Deflate算法解压后，如果有必要的话，再经过lodepng_convert函数进行color Type的类型转换，就可以得到像素的R，G，B，A值，将还原后的像素颜色值输出到窗口界面，就可以看到PNG图片了。
因此PNG结构中的难点，主要还是Deflate算法。
PNG当中，其他没介绍到的内容，比如过滤算法，隔行扫描，调色板等内容，请参考前面提到过的维基百科文章与RFC2083文档。
文章中的相关链接：
本篇文章里面，涉及到的一些资料的链接地址如下：
http://en.wikipedia.org/wiki/Portable_Network_Graphics (维基百科链接) 和 http://tools.ietf.org/html/rfc2083 (RFC2083) 这两个链接中介绍了PNG的结构。
http://tools.ietf.org/html/rfc1950 (RFC1950) 描述zlib的标准文档。
http://tools.ietf.org/html/rfc1951 (RFC1951) 描述Deflate压缩数据格式的标准文档。
霍夫曼编码_维基百科 维基百科里对霍夫曼编码的描述。
如果文章中，有链接地址无法直接访问的话，请使用代理访问。
OK，就到这里，休息，休息一下 o(∩_∩)o~~
我可以教你学琴，但是给不了你成功。
项目下载地址：
v3.0.2版本的项目地址：
github.com地址：https://github.com/zenglong/zenglOX (只包含git提交上来的源代码)
Dropbox地址：点此进入Dropbox网盘
Google Drive地址：点此进入Google Drive云端硬盘
sourceforge地址：https://sourceforge.net/projects/zenglox/files
在上面的三个网盘中(不包括github)，v3.0.2版本的相关文件，都位于zenglOX_v3.0.2的文件夹中，在该文件夹里，zenglOX_v3.0.2.zip文件为当前版本的源代码的压缩包，zenglOX.iso文件为当前版本的iso镜像(读者可以将iso文件挂载到VirtualBox或VMware里，进行测试)，lodepng-master.zip文件为lodepng项目的源代码的压缩包，readme.txt文件为当前版本的说明文档。
概述：
当前版本移植了lodepng项目，该项目的链接地址为：http://lodev.org/lodepng/ ，lodepng除了可以分析PNG图片的结构外，还将Deflate即zlib的压缩与解压缩算法也包含
进来了，对libc即C库文件的依赖也很小，因此可以方便的移植到hobby OS中。
当前版本就创建了一个基于lodepng项目的showpng程式，使用该程式可以将png图片显示出来，显示效果可以查看screenshot目录下的v302_1.jpg截图：
图1
由于showpng程式默认位于iso镜像里，所以需要通过isoget -all命令来获取该程式及相关的png示例图片文件。
如果磁盘没进行过分区格式化的话，先使用fdisk，format工具对磁盘进行分区格式化(当然，也可以将之前版本的磁盘镜像拷贝到当前版本里，Qemu模拟器的磁盘镜像文件为hd_qemu.img)。具体的分区格式化命令，如下所示(仅供参考，你可以根据需要设置自己的分区大小等)：
zenglOX> fdisk -hd 0 -pt 1 -type zenglfs -start 0 -num 123456 fdisk write MBR success , ....... zenglOX> format -hd 0 -pt 1 -type zenglfs format success , ..... |
分区格式化的命令详情，请参考"zenglOX v1.5.0 zenglfs文件系统..."对应的官方文章。
分区格式化后，使用mount命令挂载hd与iso目录:
zenglOX> mount hd 0 1 mount to [hd] success! ..... zenglOX> mount iso mount iso to [iso] success! ... |
上面mount hd ...命令的详情，也可以参考"zenglOX v1.5.0 zenglfs文件系统..."的官方文章。
接着就可以使用isoget -all命令了：
zenglOX> isoget -all
........................
copy content of iso/IMG/R.PNG;1 to hd/img/r.png success
copy content of iso/IMG/H.PNG;1 to hd/img/h.png success
copy content of iso/IMG/S.PNG;1 to hd/img/s.png success
copy content of iso/EXTRA/SHOWPNG.;1 to hd/bin/showpng success
|
上面的isoget -all命令会将showpng程式拷贝到hd/bin目录下，并将相关测试用的png图片拷贝到hd/img目录中。
由于showpng程式会自动搜索hd/img目录，因此，在使用时，直接给出png的文件名即可，如下所示：
zenglOX> showpng s.png now load and decode hd/img/s.png now wake up the parent task! zenglOX> showpng h.png now load and decode hd/img/h.png now wake up the parent task! zenglOX> showpng r.png now load and decode hd/img/r.png now wake up the parent task! |
解析并显示出一张图片后，showpng会将父任务即shell任务唤醒，让shell继续执行，因此上面就可以在shell中连续运行三个showpng程式了，从而不用为了显示三幅图片而启动三个shell了。
showpng程式与依赖的lodepng项目的源代码位于build_initrd_img目录下的extra目录中，分别对应为showpng.c与lodepng.c文件，其中，lodepng.c文件是从网盘的lodepng-master.zip压缩包里提取出来的，将原来的lodepng.cpp重命名为lodepng.c，并对该文件的代码作了些移植处理，让其可以在zenglOX系统中正常执行。
稍后会根据lodepng源码，对PNG图片结构及Deflate算法进行分析。
=========================================
BUG Fix(BUG修复)
=========================================
1. 修复zlox_kheap.c(内核堆)与zlox_uheap.c(用户堆)中，在对页表项进行操作后，没有更新TLB缓存的BUG。有关TLB缓存的内容，在之前zenglOX v1.0.0版本对应的官方文章中解释过。
之前版本由于没有更新TLB，就容易导致堆里的数据错误。例如，当从iso镜像拷贝比较大的文件时，当触发了堆中的expand(线性地址扩展)操作时，新分配的页表项不能及时更新到TLB里，从而会导致读到堆里的正常数据，会被突然变成一些无效的数据，这些无效的数据写入到磁盘里，就会导致磁盘里的文件会出现部分内容是无效的情况。
2. 修复模拟器下可能出现的无法收到按键irq中断的BUG，主要是对zlox_ps2.c文件里的zlox_ps2_init即PS/2控制器的初始化函数进行调整，直接将PS/2控制器的configure byte即配置字节设置为0x47 ，然后写入到PS/2控制器中。
省略掉之前版本里的读取configure byte的步骤，因为configure byte是通过0x60的I/O端口读取出来的，而0x60端口又被用于鼠标与键盘设备的输入事件中。在鼠标键盘没有被禁用的情况下，0x60端口容易读取出鼠标键盘设备的数据出来，而非真实的configure byte值。
即便鼠标键盘被禁用的情况下，也无法保证0x60读出来的就是原始的configure byte值，因为，很多PS/2命令的反馈信息也需要通过0x60端口读出来。因此，就省略掉读操作，而直接将需要设置的值写进去即可。
有关ps/2控制器的详情，可以参考 http://wiki.osdev.org/%228042%22_PS/2_Controller 该链接对应的维基百科文章。
configure byte里控制了是否开启鼠标键盘设备，以及是否开启鼠标键盘的中断。因此，错误的configure byte值就会导致鼠标或键盘无响应的情况发生。
=========================================
其他的一些改动
=========================================
1. 当用户程式通过系统调用，出现内存地址不存在之类的分页错误时，只会当掉当前任务，不会当掉整个系统。改动的地方位于zlox_paging.c文件的zlox_page_fault函数里。
2. 增加shift + tab系统热键，当你同时按下shift与tab键时，可以在各窗口之间进行切换，当然桌面是不参与窗口的这种切换的。
之所以不用alt + tab组合键，是因为该组合键容易被模拟器所在的主机给劫持掉(主要是bochs模拟器)，而且alt作为通用热键，在模拟器下有时候收不到释放信号(松开alt键时，有时收不到相关的中断信号)。
shift + tab组合键最终会通过zlox_my_windows.c文件的zlox_shift_tab_window函数来进行切换窗口的操作。
另外，在你拖动窗口时，该系统热键是不会起作用的。因为拖动窗口时，又进行切换窗口的话，容易导致一些显示上的问题。
PNG(Portable Network Graphics)：
在当前版本中，提供了几个测试用的png图片文件，下面我们以isodir/img/r.png文件为例，来对PNG结构进行分析：
[email protected]:~/Downloads/zenglOX_v3.0.2/isodir/img$ vim r.png 0000000: 8950 4e47 0d0a 1a0a 0000 000d 4948 4452 .PNG........IHDR 0000010: 0000 00c3 0000 00c5 0802 0000 0066 44d1 .............fD. 0000020: e000 00a6 1e49 4441 5478 daac 9d77 b85d .....IDATx...w.] 0000030: 5599 fff7 b989 bf99 71c6 e933 2a88 d424 U.......q..3*..$ 0000040: 0408 0402 1129 2110 a449 07e9 2028 3252 .....)!..I.. (2R 0000050: d451 71d0 5194 667b 9451 9447 10a4 490b .Qq.Q.f{.Q.G..I. .................................................................. .................................................................. .................................................................. [email protected]:~/Downloads/zenglOX_v3.0.2/isodir/img$ |
Linux下可以使用vim编辑器来查看文件的十六进制格式的数据。一开始通过vim编辑器打开r.png文件时，会看到一堆乱码，因为png里存储的数据，大部分是一些图像结构数据和一些压缩数据。可以在vim中，先输入冒号进入交互式命令界面，然后输入%!xxd命令，就可以切换到如上所示的十六进制编辑界面。该界面与windows下的十六进制编辑器winhex软件的界面就很像了，适合在Linux下分析PNG文件的结构。要让vim返回到原始数据界面，可以在交互式命令中输入%!xxd -r命令(也就是给%!xxd添加一个-r参数)即可。由于我们不需要修改png文件，因此，在退出vim时，请使用q!命令：强制以不保存的方式来退出编辑器。
在 http://en.wikipedia.org/wiki/Portable_Network_Graphics (维基百科链接) 和 http://tools.ietf.org/html/rfc2083 (RFC2083)这两个链接中，都对PNG的文件结构作了介绍。
首先，PNG文件的开头是8个字节的标准头部信息：
[email protected]:~/Downloads/zenglOX_v3.0.2/isodir/img$ vim r.png 0000000: 8950 4e47 0d0a 1a0a 0000 000d 4948 4452 .PNG........IHDR 0000010: 0000 00c3 0000 00c5 0802 0000 0066 44d1 .............fD. .................................................................. .................................................................. [email protected]:~/Downloads/zenglOX_v3.0.2/isodir/img$ |
可以通过上面的89 50 4e 47 0d 0a 1a 0a这8个字节来大致的识别出一个文件是否是PNG类型。因此，这8个字节可以看作是PNG的signature(签名)。
第1个字节0x89已经超过了ASCII表里的最后一个0x7f字符，当编辑器读取到这个字节时，就知道该文件是一个包含了非ASCII码在内的二进制文件，就可以将其当成二进制文件来处理。
第2个到第4个字节：0x50 0x4e 0x47则是'P'，'N'，'G'这三个字符的ASCII码，使用普通的文本编辑器查看文件时，通过这三个字符就可以初略的看出文件类型出来。
第5个到第6个字节：0x0d 0x0a则是DOS风格的换行符(CRLF)。
第7个字节：0x1a是end-of-file(文件结束字符)，当在dos下使用type命令显示文件内容时，通过这个文件结束符，就可以停止文件内容的显示，以防止在dos下将后面的图像数据以乱码的形式显示出来。
第8个字节：0x0a则是unix风格的换行符。通过换行符就可以在普通文本编辑器中，将PNG的头部与其他数据通过换行隔开。
PNG的标准头部信息之后，是由一系列的chunks(块)组成：
[email protected]:~/Downloads/zenglOX_v3.0.2/isodir/img$ vim r.png 0000000: 8950 4e47 0d0a 1a0a 0000 000d 4948 4452 .PNG........IHDR 0000010: 0000 00c3 0000 00c5 0802 0000 0066 44d1 .............fD. 0000020: e0....................................................... .................................................................. [email protected]:~/Downloads/zenglOX_v3.0.2/isodir/img$ |
上面红色标记的十六进制部分，就是PNG里的第一个chunk(块)，从右边的ASCII显示区域里，可以看到这是一个IHDR类型的块。PNG头部信息之后的块，都必须以一个IHDR类型的块开始，并以一个IEND类型的块结束。在这两个块之间，可以包含多个其他类型的块。
每个chunk(块)都由4个部分组成：第一部分是块的Length(长度)信息，例如上面的0000 000d这4个字节就表示IHDR块的第3个data数据部分的长度为13个字节。第二部分是块的类型，例如上面的4948 4452就是类型的ASCII编码，对应为IHDR这4个字符。第三部分为块的data数据部分，例如上面的0000 00c3 0000 00c5 0802 0000 00这13个字节就是IHDR块的数据部分，块数据部分的字节的二进制含义是跟块类型相关的。第四部分是块的CRC(Cyclic Redundancy Check)即循环冗余校验部分，例如上面的66 44d1 e0这4个字节，用于校验块类型与块数据部分是否正确(但不包括块长度部分)，CRC校验算法在上面给出的RFC2083链接中有介绍。
PNG文件里的第一个块必须是IHDR块，IHDR块的数据部分的结构如下(以上面提到的0000 00c3 0000 00c5 0802 0000 00这13个字节为例进行说明)：
- Width：使用4个字节来表示PNG图片的宽度(以像素为单位)，上例中的0000 00c3这头4个字节，就表示r.png图片的宽为195像素。
- Height：使用4个字节来表示PNG图片的高度(以像素为单位)，上例中的0000 00c5这4个字节，就表示r.png图片的高为197像素。
- Bit depth：使用1个字节来表示PNG图片的位深，上例中的08这个字节，就表示r.png图片的位深为8 ，从上面RFC2083链接中，可以看到，位深并非每个像素所占的位数，而是per sample(每个采样)或者per palette index(每个调色板索引)的二进制位数，该值需要和下面的Color Type字段配合起来，才能知道图片中每个像素的具体组成情况。
- Color Type：该字段的值(单个字节)需要和上面的Bit depth字段配合起来，才能确定图片的像素的具体组成情况，上例中的02这个字节就表示r.png图片的Color Type为2。
- Compression method：使用1个字节来表示图片所使用的压缩方法，目前只有一个有效的值即0，表示Deflate算法。上例中的第11个字节00就表示r.png采用的就是Deflate即zlib压缩算法。
- Filter method：使用1个字节来表示图片所使用的过滤算法，目前也只有一个有效的值即0，上例中的第12个字节就是00 ，过滤算法可以参考上面的RFC2083链接。
- Interlace method：使用1个字节来表示图片是否采用了Adam7隔行扫描，如果值是0则表示没有采用隔行扫描，如果值是1则表示采用了Adam7隔行扫描，上例中的第13个字节00，就表示r.png图片没有使用隔行扫描。在上面提到的维基百科链接与RFC2083链接中，都对隔行扫描进行了介绍。
| Color Type | 允许的Bit depth值 | 像素解释 |
|---|---|---|
| 0 | 1, 2, 4, 8, 16 |
Each pixel is a grayscale sample. 解压缩后，每个像素值是一个灰度采样。 |
| 2 | 8, 16 |
Each pixel is an R,G,B triple. 解压缩后，每个像素值是由red, green, blue即红绿蓝三原色组成的。 |
| 3 | 1, 2, 4, 8 |
Each pixel is a palette index; a PLTE chunk must appear. 解压缩后，每个像素值是一个调色板索引值。 由于涉及到调色板，因此，必须有一个PLTE块存在。 |
| 4 | 8, 16 |
Each pixel is a grayscale sample, followed by an alpha sample. 解压缩后，每个像素值是一个灰度采样，同时， 后面还跟随一个alpha通道的采样值。 |
| 6 | 8, 16 |
Each pixel is an R,G,B triple, followed by an alpha sample. 解压缩后，每个像素值是由红绿蓝三原色组成，同时， 后面还跟随一个alpha通道的采样值。 |
在r.png图片中，跟随在IHDR块后面的是IDAT块：
[email protected]:~/Downloads/zenglOX_v3.0.2/isodir/img$ vim r.png 0000000: 8950 4e47 0d0a 1a0a 0000 000d 4948 4452 .PNG........IHDR 0000010: 0000 00c3 0000 00c5 0802 0000 0066 44d1 .............fD. 0000020: e000 00a6 1e49 4441 5478 daac 9d77 b85d .....IDATx...w.] 0000030: 5599 fff7 b989 bf99 71c6 e933 2a88 d424 U.......q..3*..$ 0000040: 0408 0402 1129 2110 a449 07e9 2028 3252 .....)!..I.. (2R 0000050: d451 71d0 5194 667b 9451 9447 10a4 490b .Qq.Q.f{.Q.G..I. .................................................................. .................................................................. .................................................................. [email protected]:~/Downloads/zenglOX_v3.0.2/isodir/img$ |
根据前面介绍的块结构可知，上面红色标记的十六进制数据中，开头的00 00a6 1e这4个字节是块的长度，由于是PNG里的结构数据是采用的大字节序(与网络传输相对应，网络中也是采用的大字节序来进行数据传输)，因此，IDAT块的data数据部分的长度为0x0000a61e即42526字节，长度信息后面的49 4441 54这4个字节则是'I'，'D'，'A'，'T'这4个字符的ASCII码。然后，接下来的78 daac 9d77 b85d 5599 fff7 ...... 这42526个字节的数据就是IDAT块的实际的数据部分，该部分的数据是经过zlib压缩过的数据。在zlib标准中，本身是可以包含不同的压缩算法在里面的，在PNG中目前主要使用的是Deflate压缩算法，zlib可以看作是对Deflate压缩好的数据的一层封装。
在 http://tools.ietf.org/html/rfc1950 (RFC1950)的链接中，就介绍了zlib标准的封装格式，大致的封装格式如下所示：
0 1
+---+---+
|CMF|FLG| (more-->)
+---+---+
(if FLG.FDICT set)
0 1 2 3
+---+---+---+---+
| DICTID | (more-->)
+---+---+---+---+
+=====================+---+---+---+---+
|...compressed data...| ADLER32 |
+=====================+---+---+---+---+
|
上面的CMF是Compression Method and flags的英文缩写，它由单个字节组成，该字节里的低4位用于表示CM(Compression method即压缩方法)，高4位用于表示CINFO(Compression info即和压缩方法相关的一些压缩信息)。当低4位的CM为8时，表示上面所示的compressed data压缩数据部分是采用的Deflate压缩算法，当高4位的CINFO为7时，则表示LZ77编码的window size(窗口尺寸)为32K，LZ77编码是Deflate算法在正式压缩之前，对数据的一种预处理过程，它可以减少重复的数据所占用的空间，比如可以将重复的数据用distance距离偏移值及length长度来表示等，window size是编码算法中所使用的缓存的尺寸大小。前面r.png图片的IDAT块的数据部分的第一个字节就是0x78，低4位为8，说明r.png采用的是Deflate压缩算法，高4位为7，说明LZ77编码的窗口尺寸为32K。
上面的FLG是flag标志字节，该字节由三个部分组成：
bits 0 to 4 FCHECK (check bits for CMF and FLG) bit 5 FDICT (preset dictionary) bits 6 to 7 FLEVEL (compression level) |
低4位的FCHECK是用于校验CMF与FLG字段的。FDICT用于判断是否存在DICTID，当该位被置1时，则说明FLG与compressed data压缩数据之间存在DICTID即词典的ID值，当该位为0时，则不存在DICTID。FLEVEL字段用于表示压缩级别，具体的级别值与含义，请参考zlib的RFC1950链接。前面r.png里的IDAT块的数据部分的第二个字节是0xda，因此，r.png的FCHECK值为0x1a，FDICT为0，也就是没有DICTID，FLEVEL的值为3，即压缩级别为3，也就是maximum compression(最大化的压缩)。
由于r.png没有DICTID，因此，跟在CMF与FLG这两个字节后面的数据就是compressed data(压缩的数据)：
[email protected]:~/Downloads/zenglOX_v3.0.2/isodir/img$ vim r.png 0000000: 8950 4e47 0d0a 1a0a 0000 000d 4948 4452 .PNG........IHDR 0000010: 0000 00c3 0000 00c5 0802 0000 0066 44d1 .............fD. 0000020: e000 00a6 1e49 4441 5478 daac 9d77 b85d .....IDATx...w.] 0000030: 5599 fff7 b989 bf99 71c6 e933 2a88 d424 U.......q..3*..$ 0000040: 0408 0402 1129 2110 a449 07e9 2028 3252 .....)!..I.. (2R 0000050: d451 71d0 5194 667b 9451 9447 10a4 490b .Qq.Q.f{.Q.G..I. .................................................................. .................................................................. .................................................................. [email protected]:~/Downloads/zenglOX_v3.0.2/isodir/img$ |
上面的ac 9d77 b85d 5599 fff7 ...... 这些压缩数据是采用Deflate算法来压缩的，要了解Deflate的解压缩过程，最好的方法是先通过一些简单的例子，结合gdb调试器，加上lodepng项目的源代码，分析清楚它的压缩过程，在了解了压缩过程后，解压缩过程也就一目了然了。因此，下面将通过lodepng项目的一个测试例子来进行说明。
从网盘中下载并解压lodepng-master.zip文件：
[email protected]:~$ unzip -d lodepng lodepng-master.zip [email protected]:~$ ls lodepng/ ............. [email protected]:~$ |
上面将lodepng-master.zip解压到了lodepng目录中，进入解压后的目录，并在该目录内创建一个mytest目录：
[email protected]:~$ cd lodepng/lodepng-master/ [email protected]:~/lodepng/lodepng-master$ ls examples/ lodepng.h lodepng_util.h lodepng_benchmark.cpp lodepng_unittest.cpp pngdetail.cpp lodepng.cpp lodepng_util.cpp README.md [email protected]:~/lodepng/lodepng-master$ mkdir mytest [email protected]:~/lodepng/lodepng-master$ cd mytest [email protected]:~/lodepng/lodepng-master/mytest$ |
将lodepng.cpp与lodepng.h拷贝到mytest里：
[email protected]:~/lodepng/lodepng-master/mytest$ cp ../lodepng.cpp ./lodepng.c [email protected]:~/lodepng/lodepng-master/mytest$ cp ../lodepng.h ./lodepng.h [email protected]:~/lodepng/lodepng-master/mytest$ ls lodepng.c lodepng.h [email protected]:~/lodepng/lodepng-master/mytest$ |
上面在拷贝时，将lodepng.cpp重命名为lodepng.c，因为，下面我们要测试的是C程式，在使用lodepng项目时，当编写C++程式时，就使用lodepng.cpp文件名，当编写C程式时，就使用lodepng.c文件名。
使用编辑器创建一个mytest.c文件，内容如下：
#include "lodepng.h" #include <stdlib.h> #define UNUSED(x) (void)(x) int main(int argc, char *argv[]) { char * in = "AABCCDD"; size_t insize = 7; size_t outsize = 0; size_t outsize2 = 0; unsigned char* out = (unsigned char*)malloc(10); unsigned char* out2 = (unsigned char*)malloc(10); UNUSED(argc); UNUSED(argv); lodepng_deflate(&out, &outsize, (const unsigned char*)in, insize, &lodepng_default_compress_settings); lodepng_inflate(&out2, &outsize2, out, outsize, &lodepng_default_decompress_settings); free(out); free(out2); return 0; } |
上面测试代码中，会使用lodepng_deflate函数将in字符串进行Deflate压缩，压缩后的数据存储到out缓存里，接着再用lodepng_inflate函数将out里的压缩数据，解压缩到out2缓存里，可以先用gdb来进行简单的调试，通过对比in与out2的字符串值，就可以知道压缩与解压缩是否成功了：
[email protected]:~/lodepng/lodepng-master/mytest$ ls lodepng.c lodepng.h mytest.c [email protected]:~/lodepng/lodepng-master/mytest$ gcc lodepng.c mytest.c -ansi -pedantic -Wall -Wextra -g3 -o mytest [email protected]:~/lodepng/lodepng-master/mytest$ gdb -q mytest ....................................... Breakpoint 1, main (argc=1, argv=0xbffff394) at mytest.c:16 16 lodepng_deflate(&out, &outsize, (const unsigned char*)in, insize, &lodepng_default_compress_settings); (gdb) n 18 lodepng_inflate(&out2, &outsize2, (gdb) p outsize $1 = 17 (gdb) x/17bx out 0x80600a8: 0x05 0xc1 0x01 0x01 0x00 0x00 0x00 0x82 0x80600b0: 0xa0 0x6d 0xa6 0xff 0x37 0x05 0x30 0xad 0x80600b8: 0x03 (gdb) n 21 free(out); (gdb) p out2 $2 = (unsigned char *) 0x8059018 "AABCCDD" (gdb) p in $3 = 0x80573fc "AABCCDD" ....................................... [email protected]:~/lodepng/lodepng-master/mytest$ |
上面先通过gcc将mytest.c与lodepng.c文件一起编译为mytest程式，通过gdb调试可以看到，out缓存里的0x05 0xc1 0x01 0x01 0x00 ...... 这17个字节就是字符串"AABCCDD"经过Deflate算法压缩后的数据，最后，out2里的解压缩后的字符串也是"AABCCDD"，因此，压缩与解压缩测试通过。
下面只需要通过gdb调试lodepng_deflate函数，就可以了解其压缩过程了，不过要完全理解Deflate的话，还必须先了解Deflate的一些基本标准(一些文字上的基本说明)，Deflate算法的文字说明可以参考 http://tools.ietf.org/html/rfc1951 (RFC1951)的链接。另外，Deflate又用到了信息论里的霍夫曼编码，有关霍夫曼编码的详情，可以参考 霍夫曼编码_维基百科 该链接对应的维基百科文章，霍夫曼编码可以说是整个压缩算法的核心理论依据，所以，最好是先了解霍夫曼编码，再去看Deflate的RFC1951文档，RFC1951文档的开头部分还好理解(结合霍夫曼编码的理论知识来看)，看到后面，如果没有lodepng项目的源代码的话，估计会比较难理解。
lodepng_deflate函数最终会进入deflateDynamic函数来完成具体的压缩工作：
[email protected]:~/lodepng/lodepng-master/mytest$ gdb -q mytest ................................................... (gdb) s deflateDynamic (out=0xbffff270, bp=0xbffff230, hash=0xbffff218, data=0x80573fc "AABCCDD", datapos=0, dataend=7, settings=0x80561e0, final=1) at lodepng.c:1706 1706 unsigned error = 0; ................................................... [email protected]:~/lodepng/lodepng-master/mytest$ |
该函数中，会先执行LZ77编码，前面提到过，LZ77用于在压缩之前，对数据做个预处理：
[email protected]:~/lodepng/lodepng-master/mytest$ gdb -q mytest ................................................... (gdb) n 1763 error = encodeLZ77(&lz77_encoded, hash, data, datapos, dataend, settings->windowsize, (gdb) 1765 if(error) break; (gdb) p lz77_encoded $1 = {data = 0x805e458, size = 7, allocsize = 42} (gdb) p lz77_encoded->data $2 = (unsigned int *) 0x805e458 (gdb) p lz77_encoded->data[0] $3 = 65 (gdb) p/c lz77_encoded->data[0] $4 = 65 'A' (gdb) p/c lz77_encoded->data[1] $5 = 65 'A' (gdb) p/c lz77_encoded->data[2] $6 = 66 'B' (gdb) p/c lz77_encoded->data[3] $7 = 67 'C' (gdb) p/c lz77_encoded->data[4] $8 = 67 'C' (gdb) p/c lz77_encoded->data[5] $9 = 68 'D' (gdb) p/c lz77_encoded->data[6] $10 = 68 'D' (gdb) ................................................... [email protected]:~/lodepng/lodepng-master/mytest$ |
由于原始数据比较短，没什么长的重复性的数据，因此，预处理中，直接将"AABCCDD"这几个字符依次写入到data数组中，作为后面需要处理的数据源。
deflateDynamic函数接着会通过下面的代码，来计算'A'，'B'，'C'，‘D’这几个字符出现的频率：
/*Count the frequencies of lit, len and dist codes*/ for(i = 0; i != lz77_encoded.size; ++i) { unsigned symbol = lz77_encoded.data[i]; ++frequencies_ll.data[symbol]; if(symbol > 256) { unsigned dist = lz77_encoded.data[i + 2]; ++frequencies_d.data[dist]; i += 3; } } frequencies_ll.data[256] = 1; /*there will be exactly 1 end code, at the end of the block*/ |
也就是统计'A'出现了几次，'B'出现了几次等等，同时还添加了一个额外的256，用来表示结束符。
然后根据频率信息，就可以通过HuffmanTree_makeFromFrequencies函数来构建霍夫曼树了：
/*Make both huffman trees, one for the lit and len codes, one for the dist codes*/ error = HuffmanTree_makeFromFrequencies(&tree_ll, frequencies_ll.data, 257, frequencies_ll.size, 15); |
在HuffmanTree_makeFromFrequencies函数里，会通过lodepng_huffman_code_lengths函数来构建霍夫曼的二叉树(采用相关的coins算法)：
[email protected]:~/lodepng/lodepng-master/mytest$ gdb -q mytest ................................................... (gdb) until 848 lodepng_huffman_code_lengths (lengths=0x805e988, frequencies=0x805e488, numcodes=257, maxbitlen=15) at lodepng.c:848 848 cleanup_coins(coins, coinmem); (gdb) p coins[0] $27 = {symbols = {data = 0x805ef30, size = 2, allocsize = 12}, weight = 0.25} (gdb) p/c coins[0]->symbols->data[0] $28 = 66 'B' (gdb) p coins[0]->symbols->data[1] $29 = 256 (gdb) p coins[1] $30 = {symbols = {data = 0x805efd8, size = 3, allocsize = 18}, weight = 0.5} (gdb) p/c coins[1]->symbols->data[0] $31 = 66 'B' (gdb) p coins[1]->symbols->data[1] $33 = 256 (gdb) p/c coins[1]->symbols->data[2] $34 = 65 'A' (gdb) p coins[2] $35 = {symbols = {data = 0x805ef40, size = 2, allocsize = 12}, weight = 0.5} (gdb) p/c coins[2]->symbols->data[0] $36 = 67 'C' (gdb) p/c coins[2]->symbols->data[1] $37 = 68 'D' (gdb) p coins[3] $38 = {symbols = {data = 0x805eff0, size = 5, allocsize = 24}, weight = 1} (gdb) p/c coins[3]->symbols->data[0] $40 = 66 'B' (gdb) p coins[3]->symbols->data[1] $42 = 256 (gdb) p/c coins[3]->symbols->data[2] $43 = 65 'A' (gdb) p/c coins[3]->symbols->data[3] $44 = 67 'C' (gdb) p/c coins[3]->symbols->data[4] $45 = 68 'D' ................................................... [email protected]:~/lodepng/lodepng-master/mytest$ |
根据上面的coins，我们可以画出如下所示的二叉树：
图2
从上图所示的二叉树里，我们可以得到A，B，C，D的编码位长度信息：
[email protected]:~/lodepng/lodepng-master/mytest$ gdb -q mytest ................................................... (gdb) p lengths['A'] $47 = 2 (gdb) p lengths['B'] $48 = 3 (gdb) p lengths['C'] $49 = 2 (gdb) p lengths['D'] $50 = 2 (gdb) p lengths[256] $51 = 3 ................................................... [email protected]:~/lodepng/lodepng-master/mytest$ |
上面lengths['A']为2，即在压缩数据里，可以只用2个二进制位来表示'A'。同理，lengths['B']为3，即可以用3个二进制位来表示'B'。
在lodepng_huffman_code_lengths函数得出编码的位长度信息后，就会进入到HuffmanTree_makeFromLengths2函数，来正式构建与编解码相关的tree(树)结构，在介绍该函数之前，需要先了解下HuffmanTree结构体，该结构体的定义如下(位于lodepng.c文件中)：
/* Huffman tree struct, containing multiple representations of the tree */ typedef struct HuffmanTree { unsigned* tree2d; unsigned* tree1d; unsigned* lengths; /*the lengths of the codes of the 1d-tree*/ unsigned maxbitlen; /*maximum number of bits a single code can get*/ unsigned numcodes; /*number of symbols in the alphabet = number of codes*/ } HuffmanTree; |
在HuffmanTree结构体中，lengths(编码位长度)字段已经在之前的函数里得出来了，通过lengths字段可以进一步得出上面的tree1d字段，具体代码如下：
static unsigned HuffmanTree_makeFromLengths2(HuffmanTree* tree) { ................................................... tree->tree1d = (unsigned*)lodepng_malloc(tree->numcodes * sizeof(unsigned)); if(!tree->tree1d) error = 83; /*alloc fail*/ ................................................... if(!error) { /*step 1: count number of instances of each code length*/ for(bits = 0; bits != tree->numcodes; ++bits) ++blcount.data[tree->lengths[bits]]; /*step 2: generate the nextcode values*/ for(bits = 1; bits <= tree->maxbitlen; ++bits) { nextcode.data[bits] = (nextcode.data[bits - 1] + blcount.data[bits - 1]) << 1; } /*step 3: generate all the codes*/ for(n = 0; n != tree->numcodes; ++n) { if(tree->lengths[n] != 0) tree->tree1d[n] = nextcode.data[tree->lengths[n]]++; } } ................................................... if(!error) return HuffmanTree_make2DTree(tree); else return error; } |
通过上面的step 1，step 2及step 3这三个步骤(这3个步骤是上面提到的RFC1951文档里设计好的算法)，就可以由lengths数组换算出tree1d数组的值出来：
[email protected]:~/lodepng/lodepng-master/mytest$ gdb -q mytest ................................................... (gdb) until 643 HuffmanTree_makeFromLengths2 (tree=0xbffff174) at lodepng.c:643 643 uivector_cleanup(&blcount); (gdb) p tree->lengths['A'] $54 = 2 (gdb) p/x tree->tree1d['A'] $56 = 0x3f0 (gdb) p tree->lengths['B'] $57 = 3 (gdb) p/x tree->tree1d['B'] $58 = 0x7e6 (gdb) p tree->lengths['C'] $59 = 2 (gdb) p/x tree->tree1d['C'] $60 = 0x3f1 (gdb) p tree->lengths['D'] $61 = 2 (gdb) p/x tree->tree1d['D'] $62 = 0x3f2 ................................................... [email protected]:~/lodepng/lodepng-master/mytest$ |
从上面gdb的输出信息里可以看到，'A'的编码位长为2，对应的tree1d['A']值为0x3f0，而0x3f0的二进制格式为：0011 1111 0000，则红色标记的00即0x3f0的最低2位就是'A'的二进制编码。
'B'的编码位长为3，对应的tree1d['B']值为0x7e6，而0x7e6的二进制格式为：0111 1110 0110 ，则红色标记的110即0x7e6的最低3位就是'B'的二进制编码。
'C'的编码位长为2，对应的tree1d['C']值为0x3f1，则'C'的二进制编码为01。
'D'的编码位长为2，对应的tree1d['D']值为0x3f2，则'D'的二进制编码为10。
但是实际存储的压缩编码是翻转后的编码，例如110会被存储为011，这需要理解下面的tree2d数组，以及解压缩时，二进制流的读取方式才能理解(二进制流是从低位往高位来读取的，tree2d数组则是从高位往低位来构建的)。
在前面构建出tree1d数组后，就可以通过HuffmanTree_make2DTree函数来构建tree2d数组了：
static unsigned HuffmanTree_make2DTree(HuffmanTree* tree) { .................................................. tree->tree2d = (unsigned*)lodepng_malloc(tree->numcodes * 2 * sizeof(unsigned)); if(!tree->tree2d) return 83; /*alloc fail*/ .................................................. for(n = 0; n < tree->numcodes * 2; ++n) { tree->tree2d[n] = 32767; /*32767 here means the tree2d isn't filled there yet*/ } for(n = 0; n < tree->numcodes; ++n) /*the codes*/ { for(i = 0; i != tree->lengths[n]; ++i) /*the bits for this code*/ { unsigned char bit = (unsigned char)((tree->tree1d[n] >> (tree->lengths[n] - i - 1)) & 1); /*oversubscribed, see comment in lodepng_error_text*/ if(treepos > 2147483647 || treepos + 2 > tree->numcodes) return 55; if(tree->tree2d[2 * treepos + bit] == 32767) /*not yet filled in*/ { if(i + 1 == tree->lengths[n]) /*last bit*/ { tree->tree2d[2 * treepos + bit] = n; /*put the current code in it*/ treepos = 0; } else { /*put address of the next step in here, first that address has to be found of course (it's just nodefilled + 1)...*/ ++nodefilled; /*addresses encoded with numcodes added to it*/ tree->tree2d[2 * treepos + bit] = nodefilled + tree->numcodes; treepos = nodefilled; } } else treepos = tree->tree2d[2 * treepos + bit] - tree->numcodes; } } for(n = 0; n < tree->numcodes * 2; ++n) { if(tree->tree2d[n] == 32767) tree->tree2d[n] = 0; /*remove possible remaining 32767's*/ } return 0; } |
gdb中的调试输出情况如下：
[email protected]:~/lodepng/lodepng-master/mytest$ gdb -q mytest (gdb) until 573 HuffmanTree_make2DTree (tree=0xbffff174) at lodepng.c:573 573 unsigned char bit = (unsigned char)((tree->tree1d[n] >> (tree->lengths[n] - i - 1)) & 1); (gdb) p/c n $66 = 65 'A' (gdb) p/x tree->tree1d['A'] $73 = 0x3f0 ................................................... (gdb) p tree->tree2d[0] $68 = 258 (gdb) p tree->tree2d[2] $70 = 65 ................................................... [email protected]:~/lodepng/lodepng-master/mytest$ |
上面tree1d['A']的值为0x3f0，0x3f0的低2位为00，因此，bit = (unsigned char)((tree->tree1d[n] >> (tree->lengths[n] - i - 1)) & 1)语句在i为0时，读取出来的bit就是0，并且一开始treepos值为0，那么，tree->tree2d[2 * treepos + bit]对应的就是tree->tree2d[0]，由于此时的bit不是last bit(最后一位)，因此，tree->tree2d[0]就被设置为了nodefilled + tree->numcodes的值，其中，nodefilled值为1，tree->numcodes的值为257，因此，tree->tree2d[0]的值就是258。
接着，当i为1时，读取出的第二个bit也是0，treepos此时变为了1，由于该bit是最后一个二进制编码，因此tree->tree2d[2 * treepos + bit]即tree->tree2d[2]就被设置为了'A'的ASCII码，也就是65。
从这里可以看出来，tree2d数组实际上就是用来解压缩用的，当我们从需要解压的二进制流中第一次读取出bit(二进制位)，且bit为0时，一开始treepos为0，则tree->tree2d[2 * treepos + bit] 就是 tree->tree2d[0] ，而tree->tree2d[0]的值为258，258大于257(总编码数)，用258减去257，得到的1作为下一次的treepos值，接着，我们从二进制流中再读取出一个bit，假设该bit的值也为0，那么tree->tree2d[2 * treepos + bit]就是tree->tree2d[2]，而tree->tree2d[2]的值为65，65小于257，那么这个65就是刚才读取出来的二进制编码00所对应的解压后的值了，65是'A'的ASCII码，这样就将'A'解压还原出来了。
因此，"AABCCDD"的压缩过程，其实就是：先得到他们的lengths(编码位长度)，由lengths计算出tree1d数组，压缩过程不计算tree2d应该也可以，只不过计算下tree2d可以防止溢出等错误发生，保存压缩数据时，只需先将lengths保存在前面，然后结合tree1d数组，将'A'，'B'，‘C’，‘D’实际的二进制编码保存在lengths后面即可。
解压缩时，先将lengths读取出来，由lengths计算出tree1d数组，再由tree1d与lengths计算出tree2d数组，最后将lengths后面的二进制流一位一位的读取出来，每读取一位，就将该二进制位在tree2d数组中进行定位，当从tree2d数组中读取出来的值小于257(总编码数)时，那么该值就是需要解压出来的数据了。
在实际保存压缩数据时，Deflate算法还将lengths信息又做了一次霍夫曼编码，因为，lengths数组里存储的是257个编码的编码位长度信息，因此，有必要先压缩一下再输出。
lodepng.c文件的deflateDynamic函数里的tree_cl ，就是上面的lengths经过霍夫曼编码后，所形成的霍夫曼树，tree_cl作为HuffmanTree结构体变量，里面同样存在lengths，tree1d，tree2d这些数组，因此，在最终形成的压缩数据里，一开始会是tree_cl的lengths信息，然后是由tree_cl的lengths与tree1d所得出的二进制编码流。所以，实际解压缩时，会先由tree_cl的lengths，计算出tree_cl的tree1d数组，再由tree_cl的lengths结合tree_cl的tree1d来得出tree_cl的tree_2d数组，接着，将其后的二进制流通过tree_cl的tree2d数组来还原出实际编码的lengths信息出来，由实际编码的lengths计算出实际编码的tree1d，再计算出实际编码的tree2d，最后，将余下的实际编码的二进制流，通过实际编码的tree2d来还原出需要解压缩的值出来。
在tree_cl的lengths之前，Deflate算法还会放入一些其他的信息：
static unsigned deflateDynamic(ucvector* out, size_t* bp, Hash* hash, const unsigned char* data, size_t datapos, size_t dataend, const LodePNGCompressSettings* settings, unsigned final) { .............................................. /*Write block type*/ addBitToStream(bp, out, BFINAL); addBitToStream(bp, out, 0); /*first bit of BTYPE "dynamic"*/ addBitToStream(bp, out, 1); /*second bit of BTYPE "dynamic"*/ /*write the HLIT, HDIST and HCLEN values*/ HLIT = (unsigned)(numcodes_ll - 257); HDIST = (unsigned)(numcodes_d - 1); HCLEN = (unsigned)bitlen_cl.size - 4; /*trim zeroes for HCLEN. HLIT and HDIST were already trimmed at tree creation*/ while(!bitlen_cl.data[HCLEN + 4 - 1] && HCLEN > 0) --HCLEN; addBitsToStream(bp, out, HLIT, 5); addBitsToStream(bp, out, HDIST, 5); addBitsToStream(bp, out, HCLEN, 4); .............................................. } |
第一个BFINAL二进制位用于表示当前块是否是压缩数据流中的最后一块，接着写入10作为BTYPE的二进制值(从低位往高位方向写入)，表示采用dynamic Huffman codes(动态霍夫曼编码)，将HLIT即tree_ll(该霍夫曼树里有'A'，‘B’, 'C', 'D'之类的编码的lengths，tree1d，tree2d等信息)的总编码数减去257，并输出到接下来的5位中，将HDIST即tree_d(该霍夫曼树主要用于LZ77编码里重复性数据的处理)的总编码数减去1，并输出到接下来的5位中，最后得出HCLEN即上面提到过的tree_cl的lengths数组的长度信息，解压缩时，就需要先根据HCLEN的值，来将tree_cl的lengths数组给读取出来。此外，一开始读取出来的tree_cl的lengths数组的值是打乱过的，在lodepng.c文件里有一个CLCL_ORDER数组，该数组里的值就是根据RFC1951文档来设置的：
static const unsigned CLCL_ORDER[NUM_CODE_LENGTH_CODES]
= {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
|
通过上面这个数组，就可以将tree_cl里打乱的lengths数组里的值还原为正常顺序。
前面提到的mytest测试程序里的out变量用于存储压缩数据：
[email protected]:~/lodepng/lodepng-master/mytest$ gdb -q mytest ................................................... (gdb) x/17bx out 0x80600a8: 0x05 0xc1 0x01 0x01 0x00 0x00 0x00 0x82 0x80600b0: 0xa0 0x6d 0xa6 0xff 0x37 0x05 0x30 0xad 0x80600b8: 0x03 ................................................... [email protected]:~/lodepng/lodepng-master/mytest$ |
上面out变量里的17个字节是压缩数据，这些数据的解压过程如下图所示：
图3
以上就是Deflate相关的内容。限于篇幅，作者只能介绍其中一部分内容，读者如果需要完全弄清楚里面的机制，还需要结合前面提到的RFC1951文档与lodepng.c文件的代码，进行更深层次的分析。
lodepng项目，在将PNG图片里的压缩数据通过Deflate算法解压后，如果有必要的话，再经过lodepng_convert函数进行color Type的类型转换，就可以得到像素的R，G，B，A值，将还原后的像素颜色值输出到窗口界面，就可以看到PNG图片了。
因此PNG结构中的难点，主要还是Deflate算法。
PNG当中，其他没介绍到的内容，比如过滤算法，隔行扫描，调色板等内容，请参考前面提到过的维基百科文章与RFC2083文档。
文章中的相关链接：
本篇文章里面，涉及到的一些资料的链接地址如下：
http://en.wikipedia.org/wiki/Portable_Network_Graphics (维基百科链接) 和 http://tools.ietf.org/html/rfc2083 (RFC2083) 这两个链接中介绍了PNG的结构。
http://tools.ietf.org/html/rfc1950 (RFC1950) 描述zlib的标准文档。
http://tools.ietf.org/html/rfc1951 (RFC1951) 描述Deflate压缩数据格式的标准文档。
霍夫曼编码_维基百科 维基百科里对霍夫曼编码的描述。
如果文章中，有链接地址无法直接访问的话，请使用代理访问。
OK，就到这里，休息，休息一下 o(∩_∩)o~~
我可以教你学琴，但是给不了你成功。
—— 和你在一起