12bit LZW压缩算法的实现问题

shawind

哦，是这样，谢谢提供信息。
我也直接用bzip2好了，这个好像比zlib的压缩率稍微高点。
rar本来不错，速度和压缩率都很理想，可惜版权物。

lw

话说FX你的硬件损坏率是不是高了点。。。。

john_he

我有本书专门讲多媒体应用中的各种压缩算法……

书名？

话说之前我在翻译的一个逆向工程相关的文章里也有讲压缩算法。可惜压缩算法那部分我坑了一年一直没翻完。主要是中间做了大概65%的时候那翻译稿突然在U盘里浮云了，让我没想法了……

insani那个？我觉得你那个翻译得超级不错啊！

LZSS的压缩率还是相当不错的啦，特别是结合它的解压速度和复杂度来看的话能达到这个水平就相当不错了。
不过一般在字典压缩之后（注意一定是先字典压缩）接一个算术编码或者Huffman之类的熵减算法会是个不错的选择。其实zlib的deflate算法也是LZ77改进型+Huffman而已……并不复杂。

压缩图像用无损压缩能得到的收效始终还是太小。BMP的话要是在做deflate之前先做一次差分的话能得到更好的压缩率，也不会带来太多overhead（图不大的话嗯）。呵呵不过再多弄几步就变成PNG了。

实际开发中还是用zlib的deflate比较好吧，毕竟是相当成熟的库，也支持内存到内存的streaming，可以用于几乎所有情况。
图象我也倾向于直接用PNG，原因也是有成熟的库。

不过换个角度想，如果图象用jpeg或png，音频用ogg的话，几乎没有多少数据可以压缩了……
可能还有.x之类的文本格式的3D模型……

哦，是这样，谢谢提供信息。
我也直接用bzip2好了，这个好像比zlib的压缩率稍微高点。
rar本来不错，速度和压缩率都很理想，可惜版权物。

7-Zip的LZMA算法有没有考虑过？压缩率肯定比RAR高，而且声称解压比RAR快……以上小道消息

rednaxela

引用第11楼lw于2007-12-31 16:41发表的  :
话说FX你的硬件损坏率是不是高了点。。。。

没坏，我只是格了U盘才想起还有重要文件在里面而已 T T

引用第10楼shawind于2007-12-31 16:39发表的  :
哦，是这样，谢谢提供信息。
我也直接用bzip2好了，这个好像比zlib的压缩率稍微高点。
rar本来不错，速度和压缩率都很理想，可惜版权物。

不推荐的说……BZIP2相对来说真够慢的。要压缩率它比不过LZMA和PPM，要速度比不过deflate，我对它没足够的爱。当你发布的东西是2M而你能压到500K那确实有很大差别，但当你发布的东西是2G压到了1.5G跟1.51G其实差不了多少（死

rednaxela

引用第12楼john_he于2007-12-31 17:08发表的  :
insani那个

浮云了 T T
把现在手里还有的碎片的其中一段拿出来：

对资源数据进行压缩,无疑是一种时间换空间的典型例子.即便不在乎准备数据时压缩过程所消耗的时间,编写游戏引擎的程序员却不得不关注运行时解压过程所占用的时间和资源(CPU占用率,内存空间等).所幸,现在主流计算机具备优秀的计算能力,因而使用压缩数据的使用场景被大大扩展了.

应用在游戏归档级别的,只可能是无损数据压缩.本篇正文中所讨论的也只是一些常见的无损压缩算法(或思路).需要注意的是,游戏所使用的数据资源通常在原始文件级就已经压缩过了,无论是采用标准格式还是专有格式.例如,图像的PNG,JPEG,音频的OGG,视频的众多编码方式等.对这样已经压缩过的数据,在归档级别再次压缩带来的收益甚微而开销却依然可观,因而是否在归档级采用数据压缩往往因资源类型(或格式)而异.

从制作者的角度来看,我们可以看看吉里吉里2的例子.使用吉里吉里2制作游戏时,可以通过"吉里吉里 Releaser"将数据打包为一个或多个XP3格式的归档文件.选定需要打包的工程目录后,转到"文件"栏,如下图:
[img ]krkrrel_file.jpg[/img ]
(图截自KCDDP制作的KAGeXpress,感谢其中文化贡献)
可以看到,在此例被纳入归档的文件中,将被压缩的是左边的.ks和.tjs文件,它们都是脚本/程序文件,原本是纯文本;将不被压缩的是中间的.jpg,.png和.ogg文件,它们都是本身就经过了一定压缩的图像或音频文件;另外也有右边指定不纳入归档的.kep文件,只是一个配置而已.

好吧,这次算废话得比较少的了.
就像Haeleth在原文的回复里所说,这是让许多人脑子爆浆的一环 XD
所以请留心看,如何在不调试游戏程序的前提下,猜出数据被什么算法压缩过.
下面开始正题了~
)

游戏数据归档往往会对其中内容采取某种形式的压缩,有时对不同类型的文件甚至会混合搭配不同的压缩算法.因此,一个游戏破解者成功的重要一环在于理解典型的压缩格式.

此外,你需要具备单纯从压缩后的数据辨认出常见压缩算法的能力.这样当你盯着转储(dump)出来的十六进制数据时,你才知道接下来该怎么办.在今天的这部分里,我们将讲述一些最流行的压缩格式,它们的工作原理,及其在"实战中"的辨认方式.

首先,请注意在理论上这个工作颇为困难.理想的压缩算法计算出的数据基本上与随机噪音没什么区别(虽然很不直观,这样的数据反而含有最高密度的信息).幸好,游戏还有两个额外需求: 程序要能够快速访问到数据,同时要易于一般程序员编写.

这两个需求意味着游戏通常要么使用工业标准的压缩格式,或者相对简单快捷而又易于编码的压缩算法.两种情况中,前者常包含我们能辨认出来的标识信息;后者只有轻微的数据压缩,得到的数据看起来像是"压缩数据"而不像是随机噪音.

zlib

就让我们从一个工业标准,zlib开始.这是一个开源的压缩函数库,实现了.zip和.gz文件所使用的经典"deflate"(也就是压缩)算法.它很快也很可靠,加上是现成而且完全免费的,许多地方都会用到它,包括游戏归档中.

怎么辨认它呢? 0x78 0x9C. 标准zlib压缩过的数据块会以这两个字节开头,表明它是以算法的默认设置压缩的(默认压缩级别,用32K的缓存"deflate").另外,0x78 0xDA也很常见,跟前面一样不过采用的是最高压缩级别.如果你在归档里估计是原始文件开头的地方看到了上述两种情况,欢喜吧,因为你不费吹灰之力就解决了一个大谜团.

对这种格式进行解码很方便,因为几乎每种现代编程语言都有相应的zlib库.用C的话,你只需与libz相链接,并调用:

1. #include <zlib.h>
2. uncompress(new_buffer, &new_size, comp_buffer, comp_size);

复制代码

请确保申请到足够空间来容纳解压后的数据: 最好就是归档的内容索引已经提供了文件的原始大小.该函数会返回一个状态值,同时会把实际解压数据的大小更新到new_size里.

使用Python的话,对付zlib也是异常简单:

1. new_data = comp_data.decode('zlib')

复制代码

Python内建的字符串编码方法(例如ASCII, UTF-8, Shift-JIS等)的其中一种就是zlib编码.所以如果你把数据看作字符串的话就能直接解压.另一种选择是引入zlib库并使用更直接的函数调用来获得更细致的控制.

要压缩数据也很简单,在C语言里用compress()——或者要指定压缩级别时,用compress2();在Python里用字符串的encode('zlib')方法(或者zlib调用)就可以了.

图不上传了……等我什么时候恢复了元气再继续翻那东西吧。原本翻的慢是因为我加了很多内容进去，可是浮云了 T T

shawind

引用第12楼john_he于2007-12-31 17:08发表的  :

7-Zip的LZMA算法有没有考虑过？压缩率肯定比RAR高，而且声称解压比RAR快……以上小道消息

LZMA是LGPL的，拖着个DLL，肉眼都能看出来游戏打包用了什么算法，对拆解的人未免太亲切了。

引用第13楼rednaxela于2007-12-31 17:10发表的  :

不推荐的说……BZIP2相对来说真够慢的。要压缩率它比不过LZMA和PPM，要速度比不过deflate，我对它没足够的爱。当你发布的东西是2M而你能压到500K那确实有很大差别，但当你发布的东西是2G压到了1.5G跟1.51G其实差不了多少（死

我想压的是大量的类似x文件的模型文件和少量的BMP格式的纹理。用哪一种会比较好点呢？
xx

john_he

引用第15楼shawind于2007-12-31 17:22发表的  :


我想压的是大量的类似x文件的模型文件和少量的BMP格式的纹理。用哪一种会比较好点呢？
xx

BMP为什么不转成PNG？引擎不支持？
x文件其实deflate就够了，bzip2跟deflate速度上还是有一定差异的。

shawind

是的，本来材质就不多，基本是以模型的顶点颜色为主。
再则是因为用Opengl，再加png库显得太麻烦了，目前是直接用zlib的。
也许先LZW一下，然后再用zlib？x文件里面的冗余数据也很可观。