作者 Maxwell
转载请注明 转自[color=red]轩辕春秋文化论坛 设计与修改区[url=http://www.xycq.net/forum/index.php?showforum=48]http://www.xycq.net/forum/index.php?showforum=48[/url][/color]
原帖地址[url=http://www.xycq.net/forum/index.php?showtopic=35276]http://www.xycq.net/forum/index.php?showtopic=35276[/url]
谢谢合作

[color=blue]转载前请先联系作者[/color]


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相加就得到第一个数，依次做下去就可以还原所有的数。
例如
序列[color=#EEF2F7][转自轩辕www.xycq.net/forum][/color]
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

要解压的串[color=#EEF2F7][转自轩辕www.xycq.net/forum][/color]
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个字节的原文。
在应用这种算法的时候需要预先知道原文的长度，因为压缩后的长度可能不正好是一个字节长，通过检查解压出来的原文是否已经达到指定长度来判断解压是否完成。

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

作者 Maxwell
转载请注明 转自[color=red]轩辕春秋文化论坛 设计与修改区[url=http://www.xycq.net/forum/index.php?showforum=48]http://www.xycq.net/forum/index.php?showforum=48[/url][/color]
原帖地址[url=http://www.xycq.net/forum/index.php?showtopic=35276#entry429580]http://www.xycq.net/forum/index.php?showtopic=35276[/url]
谢谢合作

[color=blue]转载前请先联系作者[/color]


这是我写的解压缩代码。
调用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
// 出处: 轩辕春秋文化论坛 设计与修改区
// [url=http://www.xycq.net/forum/index.php?showforum=48]http://www.xycq.net/forum/index.php?showforum=48[/url]
// 授权使用于非商业用途
// 使用本代码请保留上述文字
//---------------------------------------------------------------------------

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

bool TLS11::Decode(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;
}

这些东西是我凭记忆写的，请van和东方无翼来检查一下细节上是不是有错误。

补充一点，insize=outsize时表示未压缩，可以直接跳过解压的程序

[quote]原帖由[i]van[/i]于2004-12-02, 16:17:32发表
补充一点，insize=outsize时表示未压缩，可以直接跳过解压的程序 [/quote]
感谢van提醒，我这就改一下。

这么复杂的解码都能研究出来，van真是厉害

Maxwell的解述很清晰，很容易明白解码过程。

我试着按照Maxwell所说的解码过程逆了一下，但发现难实现编码过程呀。基本上编码过程以lz为主，大概应该是这样的过程吧：

1. 按照LZ算法，适当选择缓冲区N的大小和每次处理的块F的大小；

2. 在缓冲区N中寻找与块F相匹配的最大字串，并记录下匹配的位置和匹配长度，分别记为i和l；（前面这两步就是标准的lz77压缩算法，可以参看lz77）；

3. 对于得到的i和l这两个数，需要做一些判断。如果l <= 3，那么对当前处理的字符就直接采用编码字典来进行编码，此时i的值修正为当前字符在编码字典中的索引；否则，i = i + 256; l = l - 3;

4. 对i和l进行编码。如果i <= 256，那么只对i进行编码，l不编码；否则i和l都编码。对i和i的编码方法就是Maxwell所说的将二进制数分解成两个数的方法。实际上，对i和l的编码页可以这样描述：先将该数表示成二进制（前面不带0），然后数bit个数，假设为n，然后输出n-2个连1加1个0，并用原数减掉11...0（n-2个1连1和1个0），两部分合起来就是i或ll的编码（实际上是把i和l占用的bit长度信息编码进去了）。对i和l编码就做为输出结果。（压缩本质：用i和l的编码替换了原来的串中的最大匹配串）

大概过程应该就是这样，但有一些细节问题：N和F的大小不知道；编码字典不知道；i和l同时编码应满足的条件不知；i和l的编码方法。

编码的过程也不复杂，麻烦在于压缩时具体的参数不知道，不过推测一下大约是这么个过程，先用lz算法压缩一遍，然后计算未压缩部分的频率，并根据频率生成字典，随后用字典压缩。

刚才细推了一下，发现最关键的是不能从解码过程看出滑动窗口的长度N和编码时每次处理的块长度F

编码部分的汇编代码比较复杂，同时需要较多的工作内存。不过没有必要去了解实际的编码过程，这个算法的压缩效率很一般，只是解码算法比较简单，方便实时解压而已。

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

[quote]原帖由[i]gameplore[/i]于2004-12-02, 21:57:05发表
刚才细推了一下，发现最关键的是不能从解码过程看出滑动窗口的长度N和编码时每次处理的块长度F [/quote]
我想这两个参数都可以定为整个原文长度，在实际的压缩中效率是可以接受的。另外修改一点是压缩是以一段话为单位的，而字典是整个文件公用的，应该是对文件中所有的压缩段用过lz之后再统计频率的。

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

字典是很容易生成的，无非是按频率排序，频率越高对应编码越短 [/quote]
难道在游戏里还存在着压缩的代码？

[quote]原帖由[i]Maxwell[/i]于2004-12-02, 22:02:25发表
我想这两个参数都可以定为整个原文长度，在实际的压缩中效率是可以接受的。另外修改一点是压缩是以一段话为单位的，而字典是整个文件公用的，应该是对文件中所有的压缩段用过lz之后再统计频率的。 [/quote]
编码字典与解码字典可能是同一个字典么

[quote]原帖由[i]gameplore[/i]于2004-12-02, 22:07:53发表
编码字典与解码字典可能是同一个字典么 [/quote]
只有一个字典吧，就是解码字典，比如把频率最高的字节放在最前面，压缩的时候一查，哦，在第0个位置，这样把这个字节压缩成什么就出来了。

字典是直接对原文做频率统计后得出的。
字典可以求逆（把a[i]=t改成b[t]=a[i]），压缩的时候a、b两个是同时存在的

[quote]原帖由[i]van[/i]于2004-12-02, 22:24:01发表
字典是直接对原文做频率统计后得出的。
字典可以求逆（把a[i]=t改成b[t]=a[i]），压缩的时候a、b两个是同时存在的 [/quote]
我觉得对完整原文统计不如对lz过还保持不变的那些原文进行统计压缩率高。

有个问题憋在心里很久了，问吧，你们又看不起我，不问把，我良心上有过不去。
这个帖子到底说明了什么东西？？？

看题目。

说的就是ls11压缩文件格式的解码方法。什么是ls11压缩文件？看看前面的帖子。比如san9中m_msg.s9、m_rtdn.s9就是用这种算法压缩的

[quote]原帖由[i]Maxwell[/i]于2004-12-02, 22:38:30发表
我觉得对完整原文统计不如对lz过还保持不变的那些原文进行统计压缩率高。 [/quote]
同意这一点。
不过这个算法不注重压缩效率。属于压着玩的

刚才我试了van解出来的M_Msg.s9  怎么也出错进不了游戏？不是我的san9有问题吧。

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

[quote]原帖由[i]东方无翼[/i]于2004-12-03, 8:07:07发表
同意这一点。
不过这个算法不注重压缩效率。属于压着玩的  [/quote]
这个算法压缩率还是挺高的，我记得以前估算了一下好像有的文件压缩率有0.6左右，是个不错的算法了。

[quote]原帖由[i]东方无翼[/i]于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。是怎么算出来的？ [/quote]
对，是这样的，而且好像是0102的没有调色板吧，记不清了，原来的资料遗失了

那个0x120是偏移。
至于后面的CCCCCCCC是不对的，应该改成00000000，这样那个m_msg应该就能能用了

头像里的0103 0102是什么van可知道？这个东西随便改个数值会有些奇怪的变化。

[quote]原帖由[i]东方无翼[/i]于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。是怎么算出来的？ [/quote]
我试了也不行；另外试了我自己解出来的也不行，都会出错。

似乎游戏程序认定M_msg.s9就是压缩过的，而并没有去比较哪两个长度，所以一读进来就立刻解压，殊不知本来就解压过了。

后面的CCCCCCCC是不对的，应该改成00000000，这样那个m_msg应该就能能用了
van说了这么句话，你试试看。

[quote]原帖由[i]Maxwell[/i]于2004-12-03, 14:02:48发表
后面的CCCCCCCC是不对的，应该改成00000000，这样那个m_msg应该就能能用了
van说了这么句话，你试试看。 [/quote]
我解压出来的，后面就是0，其余跟van的一样。

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

[quote]原帖由[i]gameplore[/i]于2004-12-03, 14:12:16发表
[quote]原帖由[i]Maxwell[/i]于2004-12-03, 14:02:48发表
后面的CCCCCCCC是不对的，应该改成00000000，这样那个m_msg应该就能能用了
van说了这么句话，你试试看。 [/quote]
我解压出来的，后面就是0，其余跟van的一样。

另，我还试过改原m_msg.s9中的压缩长度47EEF和为压缩长度9DE3A，发现只有改9DE3A才有影响，说明程序根本没有理会前面那个压缩后长度47EEF，而是直接用文件长度-0x120来计算压缩后长度。感觉san9.exe就是认定那个文件是压缩过的。 [/quote]
那你调整一下0120这个数值行不行？让它计算出来的压缩长度等于未压缩长度。

尝试了一下压回去，却不能还原   

可能编码方法不太正确

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

可能编码方法不太正确  [/quote]
压缩算法可能有问题吧，我一直没有仔细研究lz系列算法，只是大致明白原理，从来没有写过代码。lz是个贪心算法吧？不一定能够达到最大压缩率是吗？

[quote]原帖由[i]Maxwell[/i]于2004-12-03, 14:14:20发表
[quote]原帖由[i]gameplore[/i]于2004-12-03, 14:12:16发表
[quote]原帖由[i]Maxwell[/i]于2004-12-03, 14:02:48发表
后面的CCCCCCCC是不对的，应该改成00000000，这样那个m_msg应该就能能用了
van说了这么句话，你试试看。 [/quote]
我解压出来的，后面就是0，其余跟van的一样。

另，我还试过改原m_msg.s9中的压缩长度47EEF和为压缩长度9DE3A，发现只有改9DE3A才有影响，说明程序根本没有理会前面那个压缩后长度47EEF，而是直接用文件长度-0x120来计算压缩后长度。感觉san9.exe就是认定那个文件是压缩过的。 [/quote]
那你调整一下0120这个数值行不行？让它计算出来的压缩长度等于未压缩长度。 [/quote]
改那个数的确有影响，如果改成0，进入游戏后什么文字都没有了。

0x120的含义应该是：压缩文本起始地址偏移。

据猜测san9.exe处理m_msg的过程：
1)读入m_msg.s9；

2)读取为压缩长度，0x9DE3A，并分配这么长的buffer；

3)获取文件长度_get_file_length，用文件长度-偏移；

4)从偏移处开始解压，共解压文件长度-偏移这么长。

[quote]原帖由[i]Maxwell[/i]于2004-12-03, 14:20:01发表
[quote]原帖由[i]gameplore[/i]于2004-12-03, 14:15:37发表
尝试了一下压回去，却不能还原   

可能编码方法不太正确  [/quote]
压缩算法可能有问题吧，我一直没有仔细研究lz系列算法，只是大致明白原理，从来没有写过代码。lz是个贪心算法吧？不一定能够达到最大压缩率是吗？ [/quote]
我用的是lz77的方法，压回去后比原m_msg.s9稍小。但是由于寻找重复串时全文本比较，因此非常非常地慢。估计原来的压缩方法并没有这么慢。

那你的字典压缩压缩了没有？更新了字典了没有？

// Msg_Codec.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <crtdbg.h>

#ifndef BYTE
typedef unsigned char BYTE;
#endif

static const int DICT_LEN = 0x100;
static const int ACTUAL_LEN = 0x9DE3A;

class CLS11
{
// Operations
public:
    //---------------------------------------------------------------------------
    // Inputs:  pDict       -- Pointer to the dictionary.
    //          pSrc        -- Pointer to source data buffer.
    //          pDest       -- Pointer to destination data buffer.
    //          nLenActual  -- Length of valid source data.
    //          nLenSrc     -- Length of source data buffer.
    //          nLenDest    -- Length of destination data buffer.
    //          bCompress   -- true if LZ compression needs to be taken.
    // Returns: The length of encoded data.
    // Summary: Call this method to encode specified data with LS11.
    //--------------------------------------------------------------------------
    int Encode( BYTE *pDict, const BYTE *pSrc, BYTE *pDest, int nLenActual, int nLenSrc, int nLenDest, bool bCompress = false );
   
    //--------------------------------------------------------------------------
    // Inputs:  pDict       -- Pointer to the dictionary.
    //          pSrc        -- Pointer to source data buffer.
    //          pDest       -- Pointer to destination data buffer.
    //          nLenSrc     -- Length of source data buffer.
    //          nLenDest    -- Length of destination data buffer.
    //          nLenActual  -- Length of original data.
    // Returns: The length of decoded data.
    // Summary: Call this method to decode LS11-encoded data. This procedure is
    //          based on the code written by Maxwell & van.
    //--------------------------------------------------------------------------
    int Decode( BYTE *pDict, const BYTE *pSrc, BYTE *pDest, int nLenActual, int nLenSrc, int nLenDest );

// Properties
protected:
    int m_srcpos;
    int m_destpos;
    int m_bitpos;
    BYTE *m_pDest;
    const BYTE *m_pSrc;

// Implementations
protected:   
    void SetCode( unsigned int code );
    unsigned int GetCode( );
    void ReorderDict( BYTE const *pDictSrc, BYTE *pDictDest, int nLenDict );   
   
} ;

int CLS11::Encode( BYTE *pDict, const BYTE *pSrc, BYTE *pDest, int nLenActual, int nLenSrc, int nLenDest, bool bCompress )
{
    int off, len, lenmax, offmax;
    BYTE *pNewDict = new BYTE[DICT_LEN];
   
    m_pDest = pDest;
    m_pSrc = pSrc;
    m_srcpos = 0;
    m_destpos = 0;
    m_bitpos = 0;
        
    _ASSERT( nLenActual <= nLenSrc && pNewDict );

    memset( m_pDest, 0, nLenDest );
    ReorderDict( pDict, pNewDict, DICT_LEN );

    // If no compress needs to be taken, use dictionary only.
    if( !bCompress )
    {
        while( m_srcpos < nLenActual && m_destpos < nLenDest )
        {
            SetCode( pNewDict[m_pSrc[m_srcpos++]] );
        }
    }
    else
    {
        while( m_srcpos < nLenActual && m_destpos < nLenDest )
        {           
            // Scan whole text
            for( off = 1, lenmax = 0, offmax = 1; off <= m_srcpos; off++ )
            {
                for( len = 0; len + m_srcpos < nLenSrc && m_pSrc[m_srcpos - off + len] == m_pSrc[m_srcpos + len]; len++ );                        
                if( len > lenmax )
                {
                    lenmax = len;
                    offmax = off;
                }
            }
            // Replace the duplicated string with two number: offmax + 256 and lenmax - 3
            if( lenmax >= 3 )
            {
                SetCode( offmax + 256 );
                SetCode( lenmax - 3 );

                m_srcpos += lenmax;
            }
            else
            {
                SetCode( pNewDict[m_pSrc[m_srcpos++]] );
            }        
        }
    }

    while( m_bitpos )
    {
        m_pDest[m_destpos] <<= 1;
        m_bitpos++;
        if( m_bitpos > 7 )
        {
            m_bitpos = 0;
            m_destpos++;
            break;
        }
    }   

    delete [] pNewDict;
    return m_destpos;
}
int CLS11::Decode( BYTE *pDict, const BYTE *pSrc, BYTE *pDest, int nLenActual, int nLenSrc, int nLenDest )
{
    unsigned int code, off, len;   

    m_pSrc = pSrc;
    m_destpos = 0;
    m_srcpos = 0;
    m_bitpos = 7;

    _ASSERT( nLenActual <= nLenDest );
    while( m_srcpos < nLenSrc && m_destpos < nLenActual )
    {
        code = GetCode( );  
        if( code < 256 )
        {
            pDest[m_destpos++] = pDict[code];
        }
        else
        {            
            off = code - 256;
            len = GetCode( ) + 3;
            for( unsigned int i = 0; i < len && m_destpos < nLenDest; i++ )
            {
                pDest[m_destpos] = pDest[m_destpos - off];
                m_destpos++;
            }
        }
    }
    // Padding
    while( m_destpos < nLenActual )
    {
        pDest[m_destpos++] = pDict[0];
    }
    return m_destpos;
}

void CLS11::SetCode( unsigned int code )
{
    unsigned int temp, code1, code2;
    int len, i;
    temp = code;
    len = 0;
    code1 = 0;        
    // How many valid bits are contained in variable code
    while( temp > 1)
    {
        temp >>= 1;
        code1 = (code1 << 1) | 0x01;
        len++;
    }     
    if( (code1 << 1) <= code )
    {
        len++;
        code1 = code & (~1);
    }
    else
        code1--;

    code2 = code - code1;

    // Output bits of code1
    for( i = len - 1; i >= 0; i-- )
    {
        m_pDest[m_destpos] = (m_pDest[m_destpos] << 1) | (code1 >> i);
        m_bitpos++;
        if( m_bitpos > 7)
        {
            m_bitpos = 0;
            m_destpos++;
        }
    }
    // Output bits of code2
    for( i = len - 1; i >= 0; i-- )
    {
        m_pDest[m_destpos] = (m_pDest[m_destpos] << 1) | (code2 >> i);
        m_bitpos++;
        if( m_bitpos > 7)
        {
            m_bitpos = 0;
            m_destpos++;
        }
    }
}
unsigned int CLS11::GetCode( )
{
    unsigned int code1 = 0, code2 = 0;
    int len = 0, bit;
    do
    {
        bit = (m_pSrc[m_srcpos] >> m_bitpos) & 0x01;
        code1 = (code1 << 1) | bit;
        len++;
        m_bitpos--;
        if( m_bitpos < 0 )
        {
            m_bitpos = 7;
            m_srcpos++;
        }
    } while( bit );
    for( int i = 0; i < len; i++ )
    {
        bit = (m_pSrc[m_srcpos] >> m_bitpos) & 0x01;
        code2 = (code2 << 1) | bit;
        m_bitpos--;
        if( m_bitpos < 0 )
        {
            m_bitpos = 7;
            m_srcpos++;
        }
    }

    return (code1 + code2);
}

void CLS11::ReorderDict( const BYTE *pDictSrc, BYTE *pDictDest, int nLenDict )
{
    for( int i = 0; i < nLenDict; i++ )
    {
        for( int j = 0; j < nLenDict; j++ )
        {
            if( pDictSrc[j] == i )
            {
                pDictDest[i] = j;
                break;
            }
        }        
    }
}
// Big-endian to Little-endian or reverse
int Convert( int x )
{
    int ret = 0;
    BYTE *p = (BYTE *)(&x);
    ret = (p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3];   
    return ret;
}
void TestEncode()
{
    CLS11 ls11;
    BYTE *pDict, *pSrc, *pDest;

    int l1, l2, off, zero = 0;// Big-endian values

    pDict = new BYTE[DICT_LEN];   

    FILE *fin = fopen("C:/code/m_msg_dec.s9", "rb");
    FILE *fout = fopen("C:/code/m_msg_enc1.s9", "wb");
    FILE *fout2 = fopen("C:/code/m_msg_enc2.s9", "wb");

    _ASSERT( fin && fout && fout2 && pDict );

    fread( pDict, 0x10, 1, fin );
    fwrite( pDict, 0x10, 1, fout );
    fwrite( pDict, 0x10, 1, fout2 );

    fread( pDict, 0x100, 1, fin );
    fwrite( pDict, 0x100, 1, fout );   
    fwrite( pDict, 0x100, 1, fout2 );

    fread( &l1, 4, 1, fin );   
    pSrc = new BYTE[Convert(l1)];

    fread( &l2, 4, 1, fin );   
    pDest = new BYTE[Convert(l2)];

    fread( &off, 4, 1, fin );   

    _ASSERT( pSrc && pDest );
        
    fseek( fin, Convert(off), SEEK_SET );
    fseek( fout, Convert(off), SEEK_SET );   

    fread( pSrc, Convert(l1), 1, fin );   
    int nLen = ls11.Encode( pDict, pSrc, pDest, ACTUAL_LEN, Convert(l1), Convert(l2), false );
    fwrite( pDest, nLen, 1, fout );

    fseek( fout, 0x110, SEEK_SET );
    l1 = Convert( nLen );   
    fwrite( &l1, 4, 1, fout );
    fwrite( &l2, 4, 1, fout );   
    fwrite( &off, 4, 1, fout );
    fwrite( &zero, 4, 1, fout );

   
    nLen = ls11.Encode( pDict, pSrc, pDest, ACTUAL_LEN, Convert(l2), Convert(l2), true );   
    fseek( fout2, Convert(off), SEEK_SET );
    fwrite( pDest, nLen, 1, fout2 );

    fseek( fout2, 0x110, SEEK_SET );
    l1 = Convert( nLen );   
    fwrite( &l1, 4, 1, fout2 );
    fwrite( &l2, 4, 1, fout2 );   
    fwrite( &off, 4, 1, fout2 );
    fwrite( &zero, 4, 1, fout2 );

    fclose( fin );
    fclose( fout );
    fclose( fout2 );

    delete [] pDict;
    delete [] pSrc;
    delete [] pDest;
}

void TestDecode()
{
    CLS11 ls11;
    BYTE *pDict, *pSrc, *pDest;

    int l1, l2, off, zero = 0;

    pDict = new BYTE[DICT_LEN];   

    FILE *fin = fopen("I:/San9pk/m_msg.s9", "rb");
    FILE *fout = fopen("C:/code/m_msg_dec.s9", "wb");

    _ASSERT( fin && fout && pDict );

    fread( pDict, 0x10, 1, fin );
    fwrite( pDict, 0x10, 1, fout );

    fread( pDict, 0x100, 1, fin );
    fwrite( pDict, 0x100, 1, fout );   

    fread( &l1, 4, 1, fin );
    l1 = Convert( l1 );
    pSrc = new BYTE[l1];

    fread( &l2, 4, 1, fin );
    l2 = Convert( l2 );
    pDest = new BYTE[12];

    fread( &off, 4, 1, fin );
    off = Convert( off );

    _ASSERT( pSrc && pDest );
        
    fseek( fin, off, SEEK_SET );
    fseek( fout, off, SEEK_SET );

    fread( pSrc, 0x47EEF, 1, fin );

    int nLen = ls11.Decode( pDict, pSrc, pDest, ACTUAL_LEN, l1, l2 );

    fwrite( pDest, nLen, 1, fout );

    fseek( fout, 0x110, SEEK_SET );
    l1 = l2 = Convert( nLen );
    fwrite( &l1, 4, 1, fout );
    fwrite( &l2, 4, 1, fout );
    off = Convert( off );
    fwrite( &off, 4, 1, fout );
    fwrite( &zero, 4, 1, fout );

    fclose( fin );
    fclose( fout );

    delete [] pDict;
    delete [] pSrc;
    delete [] pDest;
}



int _tmain(int argc, _TCHAR* argv[])
{
    //TestDecode();
    TestEncode();
    return 0;
}

根据解码时的描述:
[color=blue]向回偏移a个位置后复制b个字节[/color]

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

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

所以猜测编码时采用的是类似于lz77的那种方法，不过原来的编码可能没有全文本扫描匹配，而只在前后一定长度范围内扫描。。。 [/quote]
其实分块大小和窗口大小只影响压缩速度和压缩率，并不影响解压缩。

前面的压缩编码方法有点小bug，调试后已经修正。解码出来的文件再压缩回去之后，san9.exe都能够正确识别。

附件:

m_msg_dec.s9: 从原来的m_msg.s9中解压出来的，并改了两个人的名字：
曹操==>嬴政；吕布==>项羽

m_msg_enc1.s9:采用最低压缩率（没有用lz扫描，而只用了字典）对m_msg_dec.s9重新压缩后的文件；

m_msg_end2.s9:采用最高压缩率（全文本lz扫描，对于lz来说应该是最高了）对m_msg_dec.s9重新压缩后的文件。

把m_msg_enc1.s9和m_msg_enc2.s9改名为m_msg.s9后放回去，游戏程序都能正确解压，而且进入游戏发现曹操和吕布的名字变成嬴政和项羽了  

很早之前，我就一直在考虑怎么改历史武将的姓名，无奈自己水平有限，很长时间以来都不知道怎么改。幸好得到van，maxwell等的帮助，今日才得以实现。   

另外还有一个问题，虽然名字是改了，可是旗子怎么还是没变呢？新武将的话，旗子应该是和姓有关系的，怎么历史武将的旗子不是根据姓名来确定的么？

附件装不下，分3个帖子

m_msg_enc2.s9

m_msg_enc1_part1.s9

m_msg_enc1 part2

真的要压缩回去

原来gameplore是用vc的高手呀，以后这个版上有人请教vc的问题你可要出手呀。

另外还有一个问题，虽然名字是改了，可是旗子怎么还是没变呢？新武将的话，旗子应该是和姓有关系的，怎么历史武将的旗子不是根据姓名来确定的么？

类似于三十，游戏里只支持一部分姓，所以对于历史武将，旗帜编号应该存在于剧本中

[quote]原帖由[i]Maxwell[/i]于2004-12-04, 11:07:38发表
原来gameplore是用vc的高手呀，以后这个版上有人请教vc的问题你可要出手呀。 [/quote]
高手不敢当，不过欢迎讨论

[quote]原帖由[i]van[/i]于2004-12-04, 12:18:19发表
类似于三十，游戏里只支持一部分姓，所以对于历史武将，旗帜编号应该存在于剧本中 [/quote]
这就试一下

编译无法通过，有完整的cpp文件或程序吗？

[quote]原帖由[i]爱喝绿茶[/i]于2005-01-16, 16:20:20发表
编译无法通过，有完整的cpp文件或程序吗？ [/quote]
给出的应该都是完整的代码，自己加上调用部分就可以了。

大哥知道是怎么回事吗?

应该是你复制代码的时候出了问题，重新从论坛上复制一遍就可以了。

网页上复制的是全角空格，在VC里将全角空格(0xa10xa1)全部替换为空格(0x32)就可以了

替换后发现少了个引用文件 stdio.h

可能吧，搞不好改好了_tchar 的某个地方就出来了。
金圭子解决了这些问题了吗？
指点一下啊！！！

[quote]原帖由[i]van[/i]于2005-01-20, 12:09:59发表
网页上复制的是全角空格，在VC里将全角空格(0xa10xa1)全部替换为空格(0x32)就可以了 [/quote]
真是不好意思，我为了对齐把两个半角的空格合并成一个全角的了。看来还造成了不少麻烦。

[quote]原帖由[i]爱喝绿茶[/i]于2005-01-21, 11:18:13发表
可能吧，搞不好改好了_tchar 的某个地方就出来了。
金圭子解决了这些问题了吗？
指点一下啊！！！ [/quote]
这个…………可惜我也是没解决………………直接放弃了。

好人做到底，把三九的也做出来吧！

作个能修改三九的MSG来，不能让三十专美于前啊！

代码有啦，怎么没有人帮忙做个出来呢？？？

[quote]原帖由[i]三国在飞[/i]于2005-04-01, 18:52:34发表
好人做到底，把三九的也做出来吧！

作个能修改三九的MSG来，不能让三十专美于前啊！

代码有啦，怎么没有人帮忙做个出来呢？？？ [/quote]
三九的msg好像不是很有规律

直接用ultraedit改改就可以啦

[quote]原帖由[i]gameplore[/i]于2005-04-01, 19:31:14发表
[quote]原帖由[i]三国在飞[/i]于2005-04-01, 18:52:34发表
好人做到底，把三九的也做出来吧！

作个能修改三九的MSG来，不能让三十专美于前啊！

代码有啦，怎么没有人帮忙做个出来呢？？？ [/quote]
三九的msg好像不是很有规律

直接用ultraedit改改就可以啦 [/quote]
不行，全是看不懂的乱码，怎么改，另外，乱改后游戏都进不去啊！

[quote]原帖由[i]三国在飞[/i]于2005-04-01, 22:15:56发表
不行，全是看不懂的乱码，怎么改，另外，乱改后游戏都进不去啊！ [/quote]
可以改的

乱码是因为解压缩之后还是BIG5，要用AppLocale启动UE32，选择繁体中文语言(BIG5)，然后再打开文件解压缩后的文件，就可以看见文字了。

至于输入，随便哪一个能输入BIG5码的输入法都可以

[quote]原帖由[i]gameplore[/i]于2005-04-05, 18:03:46发表
可以改的

乱码是因为解压缩之后还是BIG5，要用AppLocale启动UE32，选择繁体中文语言(BIG5)，然后再打开文件解压缩后的文件，就可以看见文字了。

至于输入，随便哪一个能输入BIG5码的输入法都可以 [/quote]
我做不出来的，不会解压啊，更不要说解压更改后再压缩回去！你能不能帮忙做个出来呢（修改器）

修改器应该不是很难做，只要有解压，压缩，GB<->BIG5几个就可以了。

[quote]原帖由[i]三国在飞[/i]于2005-04-05, 18:13:18发表
[quote]原帖由[i]gameplore[/i]于2005-04-05, 18:03:46发表
可以改的

乱码是因为解压缩之后还是BIG5，要用AppLocale启动UE32，选择繁体中文语言(BIG5)，然后再打开文件解压缩后的文件，就可以看见文字了。

至于输入，随便哪一个能输入BIG5码的输入法都可以 [/quote]
我做不出来的，不会解压啊，更不要说解压更改后再压缩回去！你能不能帮忙做个出来呢（修改器） [/quote]
原来是不会解压缩啊，其实前面的代码已经给出了。这里附上了一个简单的压缩/解压缩程序

我没有测试过，只在以前试过修改人名是可以的。完整的源代码也附上，想做完整的msg修改器的朋友可以以此为基础

程序仅仅提供压缩、解压缩功能，没有提供BIG5/GBK转码及修改功能。

使用方法：
1. 将m_msg.s9解压缩，假设解压后为m_msg_dec.s9；
2.用applocale开ultraedit32打开m_msg_dec.s9进行修改；
3.将m_msg_dec.s9压缩，假设压缩后为m_msg_enc.s9；
4.备份原来的m_msg.s9，将m_msg_enc.s9重命名为m_msg.s9，修改生效。