标题: ls11格式详解
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-2 15:18 资料 文集 短消息 看全部作者
作者 Maxwell
转载请注明 转自轩辕春秋文化论坛 设计与修改区http://www.xycq.net/forum/index.php?showforum=48
原帖地址http://www.xycq.net/forum/index.php?showtopic=35276
谢谢合作

转载前请先联系作者


ls11压缩算法是字典和lz两种算法的结合体,ls11有256字节256个项的字典。
首先来看一下对一个二进制数的分解。
对于任意一个二进制数(除了0之外其他数均以1开头,也即要去掉前面无意义的0)总可以分解成两个m(m>0)位二进制数的和,其中一个是由n(n=m-1)个1和一个0组成(称为b1)另一个数任意(称为b2)。
例如
0分解为 0 0
1分解为 0 1
10分解为 10 00
11 分解为 10 01
100分解为 10 10
101分解为 10 11
110分解为 110 000
111分解为 110 001
......
1001011分解为111110 001101

可以看出如果一个p位的二进制数<1...10(p-1个1)则可以分解为两个p-1位数,如果>=1...10(p-1个1)则可以分解为两个p位数
对于所有二进制数都是可分解的。

ls11算法的一个基础就是这种分解。
把若干个数分解后按b1b2顺序依次排列起来就形成一个二进制串,我们可以从头扫描唯一确定一个序列还原这些数。具体方法为从开头开始数连续的1的个数(设为a),则第一个分解是a+1位,第一个b1为1...10(a个1),再向后取a+1位是b2,将b1b2相加就得到第一个数,依次做下去就可以还原所有的数。
例如
序列[转自轩辕www.xycq.net/forum]
11111110 00000110 0 1 1110 0001 0 0
可以按如下步骤还原
1. 11111110 xxx 这是8位b1
2. 11111110 00000110 xxx 因为前面是8位,b2也是8位
3. b1 + b2 = 100000100
4. 11111110 00000110 0 xxx 第二个数的b1为0 1位
5. 11111110 00000110 0 1 xxx 第二个数的b2也是1位
6. b1 + b2 = 1
7. 11111110 00000110 0 1 1110 xxx 第三个数的b1为4位
8. 11111110 00000110 0 1 1110 0001 xxx 第三个数的b2也是4位
9. b1 + b2 = 1111
10. 11111110 00000110 0 1 1110 0001 0 xxx 第四个数的b1为1位
11. 11111110 00000110 0 1 1110 0001 0 0 第四个数的b2也是1位
12. b1 + b2 = 0
13. 已经到达串尾,结束
这样还原出来四个数分别是 100000100, 1, 1111, 0 对应的十进制是260, 1, 15, 0

这个分解还原的算法搞懂了之后下面来看解压的算法
ls11有一个256字节256项的字典,每项长度一字节
对于解出来的数,小于256的就用字典里的项代替,大于256的则减去256计为a,再解它后面的一个数并加上3计为b,向回偏移a个位置后复制b个字节。具体的通过一个例子来说明

下面一个字典用于举例,只给出用到的项,其他项忽略不写了
[0] 11111111  代表第0项值为11111111
......
[8] 10001101
......
[13] 11010011
......
[255] 00011001

要解压的串[转自轩辕www.xycq.net/forum]
0 0  110 010  11111110 00000001  110 111  11111110 00000100  0 1

1. 从0 0解出0,从字典查找第0项,原文为11111111
2. 从110 010解出1000即8,从字典查找第8项,原文为11111111 10001101
3. 用上面的方法解出255,原文为11111111 10001101 00011001
4. 同上,原文为11111111 10001101 00011001 11010011
5. 解出258 > 255 继续解下一个数为1
6. 从当前位置(在原文的四个字节之后)后退258-256 = 2个位置即第三个数处开始复制,共复制1 + 3 = 4个
11111111 10001101 00011001 11010011 00011001 复制第一个
                           ^                      ^
11111111 10001101 00011001 11010011 00011001 11010011  第二个
                                       ^                    ^
11111111 10001101 00011001 11010011 00011001 11010011 00011001  第三个
                                                 ^                       ^

11111111 10001101 00011001 11010011 00011001 11010011 00011001 11010011  第四个
                                                             ^                     ^
这样就完成了整个解码。
上面随便写的这段压缩码用六个字节代表了8个字节的原文。
在应用这种算法的时候需要预先知道原文的长度,因为压缩后的长度可能不正好是一个字节长,通过检查解压出来的原文是否已经达到指定长度来判断解压是否完成。

这个算法是由van破解出来的,感谢他的工作。
van的文章在http://www.xycq.net/forum/index.php?showtopic=34612


精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-2 15:41 资料 文集 短消息 看全部作者
作者 Maxwell
转载请注明 转自轩辕春秋文化论坛 设计与修改区http://www.xycq.net/forum/index.php?showforum=48
原帖地址http://www.xycq.net/forum/index.php?showtopic=35276
谢谢合作

转载前请先联系作者


这是我写的解压缩代码。
调用Decode(BYTE *dict, BYTE *in, size_t insize, BYTE *out, size_t outsize)函数解压缩,dict为ls11的字典,in为压缩的数据,insize为压缩数据长度,out为存放原文的位置,outsize为原文长度,out要保证至少有outsize字节长。函数执行完毕后out内的内容即为解压出来的原文。
注意在调用解压函数前要保证数据确实是压缩过的,如果要传入的insize == outsize那说明是没有压缩的,就不能调用解压函数。
调用示例
TLS11 ls11;

if (insize != outsize)
{
    ls11.Decode(dict, in, insize, out, outsize);
}


ls11.h
=====================
// 作者: Maxwell
// 出处: 轩辕春秋文化论坛 设计与修改区
// http://www.xycq.net/forum/index.php?showforum=48
// 授权使用于非商业用途
// 使用本代码请保留上述文字
//---------------------------------------------------------------------------

#ifndef LS11H
#define LS11H

#include <_stddef.h>
//---------------------------------------------------------------------------
typedef unsigned char BYTE;

class TLS11
{
public:
    bool Decode(const BYTE *dict, const BYTE *in, size_t insize, BYTE *out, size_t outsize);
    bool Encode(BYTE *dict, BYTE *in, size_t insize, BYTE *out, size_t outsize);

protected:
    size_t _inpos;
    int _bitpos;
    const BYTE *_in;

    unsigned int GetCode(void);
};

#endif


ls11.cpp
=====================
// 作者: Maxwell
// 出处: 轩辕春秋文化论坛 设计与修改区
// http://www.xycq.net/forum/index.php?showforum=48
// 授权使用于非商业用途
// 使用本代码请保留上述文字
//---------------------------------------------------------------------------
#pragma hdrstop
#include "ls11.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)

bool TLS11:ecode(const BYTE *dict, const BYTE *in, size_t insize, BYTE *out, size_t outsize)
{
    size_t outpos = 0;
    unsigned int code, off, len;
    bool rs = true;

    _inpos = 0;
    _bitpos = 7;
    _in = in;
    while (_inpos < insize && outpos < outsize)
    {
        code = GetCode();

        if (code < 256)
        {
            out[outpos++] = dict[code];
        }
        else
        {
            off = code - 256;
            len = GetCode() + 3;
            for (unsigned int i = 0; i < len; i++)
            {
                out[outpos] = out[outpos - off];
                outpos++;
            }
        }
    }

    return rs;
}

bool TLS11::Encode(BYTE *dict, BYTE *in, size_t insize, BYTE *out, size_t outsize)
{
}

unsigned int TLS11::GetCode(void)
{
    unsigned int code, code2;
    int l;
    BYTE bit;

    code = 0;
    code2 = 0;
    l = 0;
    do
    {
        bit = (BYTE)((_in[_inpos] >> _bitpos) & 0x01);
        code = (code << 1) | bit;
        l++;
        _bitpos--;
        if (_bitpos < 0)
        {
            _bitpos = 7;
            _inpos++;
        }
    }while (bit);
    for (int i = 0; i < l; i++)
    {
        bit = (BYTE)((_in[_inpos] >> _bitpos) & 0x01);
        code2 = (code2 << 1) | bit;
        _bitpos--;
        if (_bitpos < 0)
        {
            _bitpos = 7;
            _inpos++;
        }
    }
    code += code2;

    return code;
}


精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-2 16:11 资料 文集 短消息 看全部作者
这些东西是我凭记忆写的,请van和东方无翼来检查一下细节上是不是有错误。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-2 16:21 资料 文集 短消息 看全部作者


QUOTE:
原帖由van于2004-12-02, 16:17:32发表
补充一点,insize=outsize时表示未压缩,可以直接跳过解压的程序

感谢van提醒,我这就改一下。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-2 21:44 资料 文集 短消息 看全部作者
编码的过程也不复杂,麻烦在于压缩时具体的参数不知道,不过推测一下大约是这么个过程,先用lz算法压缩一遍,然后计算未压缩部分的频率,并根据频率生成字典,随后用字典压缩。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-2 22:02 资料 文集 短消息 看全部作者


QUOTE:
原帖由gameplore于2004-12-02, 21:57:05发表
刚才细推了一下,发现最关键的是不能从解码过程看出滑动窗口的长度N和编码时每次处理的块长度F

我想这两个参数都可以定为整个原文长度,在实际的压缩中效率是可以接受的。另外修改一点是压缩是以一段话为单位的,而字典是整个文件公用的,应该是对文件中所有的压缩段用过lz之后再统计频率的。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-2 22:04 资料 文集 短消息 看全部作者


QUOTE:
原帖由van于2004-12-02, 21:58:39发表
编码部分的汇编代码比较复杂,同时需要较多的工作内存。不过没有必要去了解实际的编码过程,这个算法的压缩效率很一般,只是解码算法比较简单,方便实时解压而已。

字典是很容易生成的,无非是按频率排序,频率越高对应编码越短

难道在游戏里还存在着压缩的代码?
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-2 22:14 资料 文集 短消息 看全部作者


QUOTE:
原帖由gameplore于2004-12-02, 22:07:53发表
编码字典与解码字典可能是同一个字典么

只有一个字典吧,就是解码字典,比如把频率最高的字节放在最前面,压缩的时候一查,哦,在第0个位置,这样把这个字节压缩成什么就出来了。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-2 22:38 资料 文集 短消息 看全部作者


QUOTE:
原帖由van于2004-12-02, 22:24:01发表
字典是直接对原文做频率统计后得出的。
字典可以求逆(把a=t改成b[t]=a),压缩的时候a、b两个是同时存在的

我觉得对完整原文统计不如对lz过还保持不变的那些原文进行统计压缩率高。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-3 10:57 资料 文集 短消息 看全部作者


QUOTE:
原帖由东方无翼于2004-12-03, 8:07:07发表
同意这一点。
不过这个算法不注重压缩效率。属于压着玩的  

这个算法压缩率还是挺高的,我记得以前估算了一下好像有的文件压缩率有0.6左右,是个不错的算法了。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-3 10:58 资料 文集 短消息 看全部作者


QUOTE:
原帖由东方无翼于2004-12-03, 8:22:24发表
刚才我试了van解出来的M_Msg.s9  怎么也出错进不了游戏?不是我的san9有问题吧。

并且van能不能解释一下压缩后长度和原文长度后面那8个字节的意义?
其中前四字节,Msg文件都是0000 0120,图像文件有0000 0103和0000 0102(是吧,Maxwell来看看对不对)。
后四个字节在van的M_Msg.s9里是CCCC CCCC。是怎么算出来的?

对,是这样的,而且好像是0102的没有调色板吧,记不清了,原来的资料遗失了
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-3 13:09 资料 文集 短消息 看全部作者
头像里的0103 0102是什么van可知道?这个东西随便改个数值会有些奇怪的变化。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-3 14:02 资料 文集 短消息 看全部作者
后面的CCCCCCCC是不对的,应该改成00000000,这样那个m_msg应该就能能用了
van说了这么句话,你试试看。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-3 14:14 资料 文集 短消息 看全部作者


QUOTE:
原帖由gameplore于2004-12-03, 14:12:16发表

QUOTE:
原帖由Maxwell于2004-12-03, 14:02:48发表
后面的CCCCCCCC是不对的,应该改成00000000,这样那个m_msg应该就能能用了
van说了这么句话,你试试看。

我解压出来的,后面就是0,其余跟van的一样。

另,我还试过改原m_msg.s9中的压缩长度47EEF和为压缩长度9DE3A,发现只有改9DE3A才有影响,说明程序根本没有理会前面那个压缩后长度47EEF,而是直接用文件长度-0x120来计算压缩后长度。感觉san9.exe就是认定那个文件是压缩过的。

那你调整一下0120这个数值行不行?让它计算出来的压缩长度等于未压缩长度。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-3 14:20 资料 文集 短消息 看全部作者


QUOTE:
原帖由gameplore于2004-12-03, 14:15:37发表
尝试了一下压回去,却不能还原   

可能编码方法不太正确  

压缩算法可能有问题吧,我一直没有仔细研究lz系列算法,只是大致明白原理,从来没有写过代码。lz是个贪心算法吧?不一定能够达到最大压缩率是吗?
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-3 14:27 资料 文集 短消息 看全部作者
那你的字典压缩压缩了没有?更新了字典了没有?
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-3 15:09 资料 文集 短消息 看全部作者


QUOTE:
原帖由gameplore于2004-12-03, 14:51:32发表
根据解码时的描述:
向回偏移a个位置后复制b个字节

所以猜测编码时采用的是类似于lz77的那种方法,不过原来的编码可能没有全文本扫描匹配,而只在前后一定长度范围内扫描。。。

其实分块大小和窗口大小只影响压缩速度和压缩率,并不影响解压缩。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2004-12-4 11:07 资料 文集 短消息 看全部作者
原来gameplore是用vc的高手呀,以后这个版上有人请教vc的问题你可要出手呀。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2005-1-16 19:26 资料 文集 短消息 看全部作者


QUOTE:
原帖由爱喝绿茶于2005-01-16, 16:20:20发表
编译无法通过,有完整的cpp文件或程序吗?

给出的应该都是完整的代码,自己加上调用部分就可以了。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2005-1-20 11:27 资料 文集 短消息 看全部作者
应该是你复制代码的时候出了问题,重新从论坛上复制一遍就可以了。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2005-4-6 12:35 资料 文集 短消息 看全部作者
修改器应该不是很难做,只要有解压,压缩,GB<->BIG5几个就可以了。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2005-4-19 08:35 资料 文集 短消息 看全部作者
我考虑过表格的问题,不过后来测试了一下速度完全可以满足需要,因此保留了那种比较直观的算法。
精华帖
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5799
编号 622
注册 2004-7-7


发表于 2005-12-11 22:28 资料 文集 短消息 看全部作者
这个算法是van反汇编得到的。这个算法的可靠性是有保障的,不必非要搞清楚算法的名字,由于这个算法的一些特点,很难而且也不需要搞清楚压缩算法的细节。根据解压算法很容易构造一个压缩算法,即使这个算法跟光荣的算法不一致也能让解压算法正常工作。
精华帖
顶部

正在浏览此帖的会员 - 共 17 人在线




当前时区 GMT+8, 现在时间是 2024-11-20 12:34
京ICP备2023018092号 轩辕春秋 2003-2023 www.xycq.org.cn

Powered by Discuz! 5.0.0 2001-2006 Comsenz Inc.
Processed in 0.017572 second(s), 9 queries , Gzip enabled

清除 Cookies - 联系我们 - 轩辕春秋 - Archiver - WAP