加载中…
个人资料
夜雨盛唱
夜雨盛唱
  • 博客等级:
  • 博客积分:0
  • 博客访问:41,531
  • 关注人气:13
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

图片压缩处理LZSS压缩算法简介

(2011-10-12 23:15:16)
标签:

杂谈

分类: 科技

对于压缩图片的破解,大家提出了问题。我们知道汉化游戏时一部分为tile图片,而另一部分就是经过lzss等算法压缩过的图片,专业的破解我还没有涉及,但我在此为大家列举一些重要的算法知识和工具。
  (蓝色-本贴的分段标题 绿色-文章标题 红色-出处作者 橙色-我对文章的说明理解)

  ---基本知识---
  【特殊的格式可以用现成的工具,就是大家提到的gbacomp,天使汉化组的解压程序也很受欢迎】
  gbacomp即GBA LZ77压缩数据处理程序,作用是把GBA游戏rom内的压缩数据解压出来形成文件,并且修改后压缩并导入rom
           ---天使汉化组有关GBA LZSS 解压程序 v1.0说明中提到
  GBA LZSS 解压程序v1.0:天使汉化组仿照另一个解压工具gbacomp制作的

  【LZ77的历史,它是LZSS的基础,gbacomp工具实现的原理】
  1977/1978,两个聪明的以色列人提出基于字典模型的算法LZ77,LZ78,这两个经典文献提出的算法成为了当代几乎所有流行压缩软件的算法核心。1982年, LZSS算法作为LZ77的改良被提出,大量的压缩软件使用了这个算法,如zip,arj,lharc等,1985年,LZ78的改良LZW提出,LZW也得到广泛的应用,如GIF图像中的压缩算法,Unix下的compress程序。但由于LZW存在专利问题,此后的应用并没有LZSS广泛。
           ---
www.phyz.net

  ---压缩算法说明---
  LZ77算法
  1977年,Jacob Ziv和Abraham Lempel描述了一种基于滑动窗口缓存的技术,该缓存用于保存最近刚刚处理的文本(J. Ziv and A. Lempel, “A Universal Algorithm for Sequential Data Compression”, IEEE Transaction on Information Theory, May 1977)。这个算法一般称为IZ77。
  LZ77和它的变体发现,在正文流中词汇和短语(GIF中的图像模式)很可能会出现重复。当出现一个重复时,重复的序列可以用一个短的编码来代替。压缩程序扫描这样的重复,同时生成编码来代替重复序列。随着时间的过去,编码可以重用来捕获新的序列。算法必须设计成解压程序能够在编码和原始数据序列推导出当前的映射。
  在研究LZ77的细节之前,先看一个简单的例子(J. Weiss and D. Schremp, “Putting Data on a Diet”, IEEE Spectrum, August 1993)。考虑这样一句话:
  the brown fox jumped over the brown foxy jumping frog
  这个短语的长度总共是53个八位组 = 424 bit。算法从左向右处理这个文本。初始时,每个字符被映射成9 bit的编码,二进制的1跟着该字符的8 bit ASCII码。在处理进行时,算法查找重复的序列。当碰到一个重复时,算法继续扫描直到该重复序列终止。换句话说,每次出现一个重复时,算法包括尽可能多的字符。碰到的第一个这样的序列是the brown fox。这个序列被替换成指向前一个序列的指针和序列的长度。在这种情况下,前一个序列的the brown fox出现在26个字符之前,序列的长度是13个字符。对于这个例子,假定存在两种编码选项:8 bit的指针和4 bit的长度,或者12 bit的指针和6 bit的长度。使用2 bit的首部来指示选择了哪种选项,00表示第一种选项,01表示第二种选项。因此,the brown fox的第二次出现被编码为 <00b><26d><13 d >,或者00 00011010 1101。
  压缩报文的剩余部分是字母y;序列<00b><27d><5 d >替换了由一个空格跟着jump组成的序列,以及字符序列ing frog。
  压缩过的报文由35个9 bit字符和两个编码组成,总长度为35 x 9 + 2 x 14 = 343比特。和原来未压缩的长度为424比特的报文相比,压缩比为1.24。
  表:编码的数据流
  位置 1 2 3 4 5 6 7 8 9
  字符 A A B C B B A B C
  表:编码过程
  步骤 位置 匹配串 字符  输出
  1   1   --  A   (0,0)A
  2   2   A  B   (1,1)B
  3   4   --  C   (0,0)C
  4   5   B  B   (2,1)B
  5   7   AB C   (5,2)C
  对于LZ77压缩文本的解压很简单。解压算法必须保存解压输出的最后N个字符。当碰到编码字符串时,解压算法使用<指针>,和<长度>,字段将编码替换成实际的正文字符串。

  LZSS算法
  LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题,但这个解决方案包含有冗余信息。冗余信息表现在两个方面,一是空指针,二是编码器可能输出额外的字符,这种字符可能包含在下一个匹配串中。LZSS算法以比较有效的方法解决这个问题,它的思想是如果匹配串的长度比指针本身的长度长就输出指针,否则就输出真实字符。由于输出的压缩数据流中包含有指针和字符本身,为了区分它们就需要有额外的标志位,即ID位。
LZSS编码算法的具体执行步骤如下:
  把编码位置置于输入数据流的开始位置。
  在前向缓冲器中查找窗口中最长的匹配串
  ① Pointer :=匹配串指针。
  ② Length :=匹配串长度。
  判断匹配串长度Length是否大于等于最小匹配串长度(MIN_LENGTH) ,
  如果“是”:输出指针,然后把编码位置向前移动Length个字符。
  如果“否”:输出前向缓冲存储器中的第1个字符,然后把编码位置向前移动一个字符。
  如果前向缓冲器不是空的,就返回到步骤2。
  例:编码字符串如表03-05-3所示,编码过程如表03-05-4所示。现说明如下:
  “步骤”栏表示编码步骤。
  “位置”栏表示编码位置,输入数据流中的第1个字符为编码位置1。
  “匹配”栏表示窗口中找到的最长的匹配串。
  “字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。
  “输出”栏的输出为:
  ① 如果匹配串本身的长度Length >= MIN_LENGTH,输出指向匹配串的指针,格式为(Back_chars, Chars_length)。该指针告诉译码器“在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出”。
  ② 如果匹配串本身的长度Length >= MIN_LENGTH,则输出真实的匹配串。
  表:输入数据流
  位置 1 2 3 4 5 6 7 8 9 10 11
  字符 A A B B C B B A A  B C
  表:编码过程(MIN_LENGTH = 2)
  步骤 位置 匹配串 输出
  1  1   --   A
  2  2   A   A
  3  3   --    B
  4  4   B   B
  5  5   --   C
  6  6   B B  (3,2)
  7  8   A A B (7,3)
  8  11   C   C
  在相同的计算环境下,LZSS算法可获得比LZ77更高的压缩比,而译码同样简单。这也就是为什么这种算法成为开发新算法的基础。许多后来开发的文档压缩程序都使用了LZSS的思想,例如PKZip,ARJ,LHArc和ZOO等等,其差别仅仅是指针的长短、窗口的大小等有所不同。
LZSS同样可以和熵编码联合使用,例如ARJ就与霍夫曼编码联用,而PKZip则与Shannon-Fano联用,它的后续版本也采用霍夫曼编码。

  ---压缩算法与图片---
  [转贴]图片库的压缩保存
  Author:crazymens  From:CSDNBlog-crazymens的专栏
  【没有涉及到实质问题,但是这是开发游戏的思想,来告诉你开发者使用压缩算法的初衷,能和开发者同样思路就是破解的捷径吧】
  我们知道,随着游戏画面清晰度的不断提高,游戏所占用的硬盘空间也在不断增大。为此,我们有必要将有些大容量的数据做压缩保存,图片库就是一个很好的例子。
  首先要谈到的就是压缩算法问题,现在的压缩算法很多,选择那一种好呢?大家一定会想到在网页上常用到的JPEG格式和GIF格式,但是这两种算法都不适合在游戏中使用。就游戏开发来说,我们必须选择一种压缩率高、解码速度又快的算法。如果采用JPEG无损压缩算法,那么压缩率就不高,采用有损压缩的话虽然压缩率很高但在游戏中图像是不能有所损坏的。还有,JPEG算法的一个最大缺点就是解码速度太慢。GIF算法性能很高,压缩率高解码又快,只可惜它不能压缩超过256色的图像。但如果您做的游戏是256色的话,那么使用GIF算法是再好不过的了。
  如果您的游戏画面采用了真彩色或您想将图像压缩的再好一点,那么无疑您得自己研制一套压缩程序。这里,我为大家提供了两个方案:
  方案一:采用LZSS或LZH压缩算法。
  方案二:使用DCL压缩软件开发包,这个程序是本人在网络上无意发现的,使用非常方便,而且它不是压缩文件而是压缩内存中的数据又存放在内存中,所以非常适合在游戏中使用。唯一的缺陷就是压缩率不是非常高。

  【下面的文章是针对一般游戏制作图片压缩破解的教程,但是对GBArom破解应该很有帮助】
  [转贴]浅谈LZSS与游戏图片破解
  Author: Zane  From: ZaneStudio.net
  【很多游戏采用LZSS】
  业余游戏制作者最头疼的就是没有美工的支持了。很多业余游戏制作所使用的图片都是来自于网上的很有限的一些图片资源,然而这些图片并不能完整配套,所以业余游戏的画面往往显得单调或者搭配不协调(使用多个不属于一系列的图片资源)。基于此,也有不少业余游戏采用“窃取”商业游戏图片于己用的方式(反正业余游戏一般都不用于商业目的),这种方法使用的就是一系列完整、配套的图片,画面就会显得专业、协调得多,但是,前提是能够破解商业游戏的图片格式。多数商业游戏并不会将图片资源以可以直接打开的常用格式存放,而是会做一定的压缩处理,这样做有两个好处:其一,图片不易被用户直接修改或用于其他用途;其二,减小游戏图片资源所占用的磁盘空间。
  最近,我为了获取图片资源,研究了一些游戏的图片压缩格式,发现有不少游戏采用了LZSS压缩,例如《天使音乐会》、《神奇传说系列》(只针对《时空道标》和《远征奥德赛》两作,因为没有其他的在手边)。于是,我在网上查阅了一些关于LZSS压缩的资料,实现了这些游戏的图片资源破解。
  LZSS压缩是LZ77压缩的改进方式,相对于LZ77减少了冗余度。LZSS在压缩比率上相对其它压缩并没有太大优势,然而它的压缩/解压缩速度却非常快,因此往往用在速度优先的场合(当然,游戏图片解压缩就是速度优先的)。基于这个优势,LZSS被大量采用,例如微软以前常使用的compress.exe/expand.exe就是采用LZSS实现的(这里顺便提一下,《神奇传说时空道标》的图片压缩完全就是用compress.exe的方式压缩的,连文件头都完整存在,因此可以直接用expand.exe来解压缩,就不用自己忙活了^_^)。
  【针对一个源程序讲解LZSS压缩的原理】
  在文章的末尾我给出了一个用LZSS压缩/解压缩的源程序,是Haruhiko Okumura在1989年所写,后来被广泛使用。但是由于其源代码相当晦涩,所以我在这里先把LZSS压缩的原理大致介绍一下:
  LZSS采用了一个大小为N的滑动窗口用于在文件中滑动,其中后F大小作为一个前向缓冲,在窗口中前N-F.

 

[转自:http://bbs.a9vg.com/thread-402729-1-1.html]

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有