Сообщений в теме: 32

[Марат]

Ошибка в функции write_lz.

Сообщение отредактировал Марат: 24 Март 2015 - 18:15

[Марат]

 

А ты пробовал прогой Трикзтера распаковать данные? У него вроде под LZSS заточено GBA.

Она LZ77, а не LZSS

 

LZSS - это частный случай LZ77. К слову,  в LZSS флаги идут не в отдельном байте, а между литералами и парой длина + смещение.

Алгоритм примерно такой:

if ReadBit() = 1 then
begin
 Literal:= ReadBits(8);
 ....
end else
begin
 MatchLength:= ReadBits(4);
 MatchOffset:= ReadBits(12);
....
end;

Тот алгоритм, что у тебя в Ромхакинге обычно называют LZ77.

[TTEMMA]

Вон оно как, спасибо за информацию, запомню

[Proton]

Спасибо за подсказку. Прошу проверить.

uint32_t write_lz(uint32_t &read_pos, uint8_t* write_buf, uint32_t &write_pos, lz_t lz, chunk_t &chunk)
{
    uint32_t lz_size;
    uint8_t lz1,lz2;
    uint16_t lz_dist, lz_len;
    uint16_t lz_d1, lz_d2;

    lz_dist=lz.distance;
    lz_len=(lz.length-MIN_MATCH_LENGTH)&0x0f;

    lz_len=(lz_len<<4)&0xf0;

    lz_d1=(lz_dist&0xff00)>>8;
    lz_d2=lz_dist&0xff;

    lz1=lz_d2;
    lz2=lz_d1|lz_len;

    write_buf[write_pos++]=lz1;
    write_buf[write_pos++]=lz2;

    read_pos=read_pos+lz.length;

    cout << hex << "\nLZ = ["<< setw(2) << (int)lz1 << (int)lz2 << "]";
    cout << hex << "\tLENGTH = [" << setw(2) << (int)lz.length << "]";
    cout << hex << "\tOFFSET = [" << setw(2) << (int)lz.offset << "]";
    cout << hex << "\tDISTANCE = [" << setw(2) << (int)lz.distance << "]";

    chunk.code=chunk.code>>1;
    chunk.code=chunk.code|0x00;
    chunk.bitcount++;

    lz_size=2;

    return lz_size;
};

[Марат]

Спасибо за подсказку. Прошу проверить.

uint32_t write_lz(uint32_t &read_pos, uint8_t* write_buf, uint32_t &write_pos, lz_t lz, chunk_t &chunk)
{
    uint32_t lz_size;
    uint8_t lz1,lz2;
    uint16_t lz_dist, lz_len;
    uint16_t lz_d1, lz_d2;

    lz_dist=lz.distance;
    lz_len=(lz.length-MIN_MATCH_LENGTH)&0x0f;

    lz_len=(lz_len<<4)&0xf0;

    lz_d1=(lz_dist&0xff00)>>8;
    lz_d2=lz_dist&0xff;

    lz1=lz_d2;
    lz2=lz_d1|lz_len;

    write_buf[write_pos++]=lz1;
    write_buf[write_pos++]=lz2;

    read_pos=read_pos+lz.length;

    cout << hex << "\nLZ = ["<< setw(2) << (int)lz1 << (int)lz2 << "]";
    cout << hex << "\tLENGTH = [" << setw(2) << (int)lz.length << "]";
    cout << hex << "\tOFFSET = [" << setw(2) << (int)lz.offset << "]";
    cout << hex << "\tDISTANCE = [" << setw(2) << (int)lz.distance << "]";

    chunk.code=chunk.code>>1;
    chunk.code=chunk.code|0x00;
    chunk.bitcount++;

    lz_size=2;

    return lz_size;
};

 

У тебя же 12 битное смещение, поэтому надо писать так:

 lz_d1=(lz_dist&0xf00)>>8;

[Proton]

Всё верно. Случайно добавил лишнюю "F" в маске.

Марат, а ты свою утилиту для Monster World в C++, С# или Delphi писал?

[Марат]

На дельфи. Я всё пишу на дельфях. Я уже привык к дельфи.

[TTEMMA]

К сожалению, под самый конец сбивается...

Может я что-то не так исправил:

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <iomanip>

const uint32_t DATA_SIZE = 65535;
const uint32_t WINDOW_SIZE = 4095;
const uint32_t MAX_MATCH_LENGTH = 17;
const uint32_t MIN_MATCH_LENGTH = 2;

const uint8_t READ_BIT = 0x01;
const uint8_t WRITE_BIT = 0x80;

struct chunk_t
{
    uint8_t code, bitcount;
};

struct lz_t
{
    uint16_t length, offset, distance;
};

lz_t search_lz (uint32_t pos, uint8_t* buffer, uint32_t inputsize);
uint32_t write_lz (uint32_t &read_pos, uint8_t* write_buf, uint32_t &write_pos, lz_t lz, chunk_t &chunk);
uint32_t write_lit (uint32_t &read_pos, uint8_t* read_buf, uint32_t &write_pos, uint8_t* write_buf, chunk_t &chunk);
void reset_chunk (chunk_t &chunk);

using namespace std;

int main(int argc, char **argv)
{

    uint8_t* _inputData;
    uint8_t* _outputData;

    uint32_t _inputPosition;
    uint32_t _outputPosition;

    uint32_t _headerPosition;

    uint32_t _inputSize;
    uint32_t _outputSize;

    lz_t lz, lz_alt;
    chunk_t chunk;
    chunk.code=0;
    chunk.bitcount=0;

    _headerPosition = 0;
    _inputPosition = 0;
    _outputPosition = 1;

    const char* input_name = "st101.uncompress";
    const char* output_name = "st101_compressed.bin";

    FILE *input_file;
    input_file = fopen(input_name, "rb");
    if (input_file==NULL)
    {
        fputs ("Input file error",stderr);
        exit (1);
    }

    fseek(input_file, 0, SEEK_END);
    _inputSize=ftell(input_file);
    _outputSize=0;

    rewind(input_file);
    _inputData = (uint8_t*) malloc (sizeof(uint8_t)*_inputSize);
    _outputData = (uint8_t*) malloc (sizeof(uint8_t)*_inputSize);
    fread(_inputData,sizeof(uint8_t),_inputSize, input_file);
    fclose(input_file);

    write_lit(_inputPosition, _inputData, _outputPosition, _outputData, chunk);

    while (_inputPosition<_inputSize)

    {

        lz=search_lz(_inputPosition,_inputData,_inputSize);
        lz_alt=search_lz(_inputPosition+1,_inputData,_inputSize);

        if (lz_alt.length>lz.length && lz_alt.length>=MIN_MATCH_LENGTH)
        {
            write_lit(_inputPosition, _inputData, _outputPosition, _outputData, chunk);
        }

        else
        {

            if (lz.length<MIN_MATCH_LENGTH)
            {

                write_lit(_inputPosition, _inputData, _outputPosition, _outputData, chunk);

            }

            else
            {

                write_lz(_inputPosition, _outputData, _outputPosition, lz, chunk);

            }

        }


        if (chunk.bitcount==8)

        {
            _outputData[_headerPosition]=chunk.code;
            chunk.code=0x00;
            chunk.bitcount=0;
            _headerPosition=_outputPosition++;
        }

    }

    if (chunk.bitcount<8 && chunk.bitcount!=0)

    {
        int bit_shift;
        bit_shift=8-chunk.bitcount;
        chunk.code=chunk.code<<bit_shift;
        _outputData[_headerPosition]=chunk.code;
    }

    _outputSize = _outputPosition;

    FILE *output_file;

    if (!_outputData)
    {
        return 1;
    }

    output_file = fopen(output_name, "wb");
    if (output_file==NULL)
    {
        fputs ("Output file error",stderr);
        exit (1);
    }

    if(!output_file)
    {
        return 1;
    }

    fwrite(_outputData, _outputSize, 1, output_file);
    fclose(output_file);

    free(_outputData);
    free(_inputData);

    return 0;

}


lz_t search_lz (uint32_t pos, uint8_t* buffer, uint32_t inputsize)
{
    lz_t variant;
    variant.length=0;
    variant.offset=0;
    variant.distance=0;

    uint16_t lz_off=0;
    uint16_t lz_len=0;
    uint8_t match=0;

    int win;
    win=pos-(WINDOW_SIZE);

    if (win<0) win=0;

    for (int i=win; i<pos && i+MAX_MATCH_LENGTH < pos+MAX_MATCH_LENGTH; i++)
    {
        if ((buffer[i]==buffer[pos]))
        {
            match=1;

            while((buffer[i+match]==buffer[pos+match])&&(pos+match<inputsize))
            {
                if (match>=MAX_MATCH_LENGTH)
                {
                    break;
                }
                match++;
            }

            if(match>lz_len)
            {
                lz_len=match;
                lz_off=i;
            }
        }

        if(match>=MAX_MATCH_LENGTH)
        {
            lz_len=MAX_MATCH_LENGTH;
            break;
        }

    }

    variant.length=lz_len;
    variant.offset=lz_off;
    variant.distance=pos-lz_off;

    return variant;
}

uint32_t write_lz(uint32_t &read_pos, uint8_t* write_buf, uint32_t &write_pos, lz_t lz, chunk_t &chunk)
{
    uint32_t lz_size;
    uint8_t lz1,lz2;
    uint16_t lz_dist, lz_len;
    uint16_t lz_d1, lz_d2;

    lz_dist=lz.distance;
    lz_len=(lz.length-MIN_MATCH_LENGTH)&0x0f;

    lz_len=(lz_len<<4)&0xf0;

    lz_d1=(lz_dist&0xf00)>>8;
    lz_d2=lz_dist&0xff;

    lz1=lz_d2;
    lz2=lz_d1|lz_len;

    write_buf[write_pos++]=lz1;
    write_buf[write_pos++]=lz2;

    read_pos=read_pos+lz.length;

    chunk.code=chunk.code>>1;
    chunk.code=chunk.code|0x00;
    chunk.bitcount++;

    lz_size=2;

    return lz_size;
};


uint32_t write_lit(uint32_t &read_pos, uint8_t* read_buf, uint32_t &write_pos, uint8_t* write_buf, chunk_t &chunk)
{
    int lit_size;

    write_buf[write_pos++]=read_buf[read_pos++];

    chunk.code=chunk.code>>1;
    chunk.code=chunk.code|0x80;
    chunk.bitcount++;

    lit_size=1;

    return lit_size;
}

void reset_chunk (chunk_t &chunk)
{
    chunk.code=0;
    chunk.bitcount=0;
}

[Марат]

    if (chunk.bitcount<8 && chunk.bitcount!=0)

    {
        int bit_shift;
        bit_shift=8-chunk.bitcount;
        chunk.code=chunk.code<<bit_shift;
        _outputData[_headerPosition]=chunk.code;
    }

Здесь ошибка. Сдвиг надо делать вправо, а не влево.

[TTEMMA]

Здесь ошибка. Сдвиг надо делать вправо, а не влево.

Исправил, заработало.

 

Большое спасибо, Proton, большое спасибо, Марат. Вы мои кумиры!

[Proton]

Ребята, извините за косячный код. На скорую руку, без проверки на расжатие.

[TTEMMA]

Ребята, извините за косячный код. На скорую руку, без проверки на расжатие.

Да ничего, главное разобрались и всё работает. Кстати, сжатие лучше чем оригинал.

[TTEMMA]

Может и нагавн*кодил, но работает

Type
chunk_t = record
  code, bitcount : byte;
end;
lz_t = record
  length, offset, distance : Word;
end;

const
Window_Size = 4095;
Max_Match_Length = 17;
Min_Match_Length = 2;

Procedure search_lz(pos:integer;Buffer:Array of byte; inputsize:integer;var lz:lz_t);
var
lz_off,lz_len:integer;
match:byte;
win:integer;
begin
lz_off:=0;
lz_len:=0;
match:=0;
win:=pos-Window_Size;
if win<0 then
win:=0;
while (win<pos) and (win+Max_Match_Length<pos+Max_Match_Length) do
 begin
   if Buffer[win]=Buffer[pos] then
     begin
       match:=1;
       while (Buffer[win+match]=Buffer[pos+match]) and (pos+match<inputsize) do
        begin
         if match>=Max_Match_Length then Break;
         inc(match);
        end;
       if match>lz_len then
        begin
          lz_len:=match;
          lz_off:=win;
        end;
     end;
   if match>Max_Match_Length  then
   begin
     lz_len:=Max_Match_Length;
     break;
   end;
   inc(win);
 end;
lz.length:=lz_len;
lz.offset:=lz_off;
lz.distance:=pos-lz_off;
end;

Procedure write_lz(var read_pos:integer;var write_buf:Array of byte;var write_pos:integer;var lz:lz_t;var chunk:chunk_t);
var
lz1,lz2:byte;
lz_dist,lz_len:word;
lz_d1,lz_d2:word;
begin
lz_dist:=lz.distance;
lz_len:=(lz.length-Min_Match_Length) and $0F;
lz_len:=(lz_len shl 4) and $F0;
lz_d1:=(lz_dist and $0F00) shr 8;
lz_d2:=lz_dist and $FF;
lz1:=lz_d2;
lz2:=lz_d1 or lz_len;
write_buf[write_pos]:=lz1;
inc(write_pos);
write_buf[write_pos]:=lz2;
inc(write_pos);
read_pos:=read_pos+lz.length;
chunk.code:=chunk.code shr 1;
chunk.code:=chunk.code or $00;
inc(chunk.bitcount);
end;

Procedure write_lit(var read_pos:integer;var read_buf:Array of byte;var write_pos:integer;var write_buf:Array of byte;var chunk:chunk_t);
begin
  write_buf[write_pos]:=read_buf[read_pos];
  inc(write_pos);inc(read_pos);
  chunk.code:=chunk.code shr 1;
  chunk.code:=chunk.code or $80;
  inc(chunk.bitcount);
end;

Procedure LZSSCompress(LZss_Ms:TStream);
var
input,output:Array of byte;
inputposition,outputposition,headerposition:integer;
inputsize,outputsize:integer;
lz,lz_alt:lz_t;
chunk:chunk_t;
bit_shift:byte;
begin
  chunk.code:=0;
  chunk.bitcount:=0;
  headerposition:=0;
  inputposition:=0;
  outputposition:=1;
  inputsize:=LZss_Ms.Size;
  SetLength(input,inputsize);
  SetLength(output,inputsize);
  LZss_Ms.Read(input[0],inputsize);
  lzss_ms.Size:=0;
  LZss_Ms.Position:=0;
  write_lit(inputPosition, input, outputPosition, output, chunk);
  while inputposition<inputsize do
   begin
     search_lz(inputPosition,input,inputSize,lz);
     search_lz(inputPosition+1,input,inputSize,lz_alt);
     if (lz_alt.length>lz.length) and (lz_alt.length>=Min_Match_Length) then
       write_lit(inputPosition, input, outputPosition, output, chunk)
     else begin
            if lz.length<Min_Match_Length then
              write_lit(inputPosition, input, outputPosition, output, chunk)
            else
              write_lz(inputPosition, output, outputPosition, lz, chunk);
          end;
     if chunk.bitcount=8 then
      begin
        output[headerposition]:=chunk.code;
        chunk.code:=$00;
        chunk.bitcount:=0;
        headerPosition:=outputPosition;
        inc(outputposition)
      end;
   end;
if (chunk.bitcount<8) and (chunk.bitcount<>0) then
 begin
   bit_shift:=8-chunk.bitcount;
   chunk.code:=chunk.code shr bit_shift;
   output[headerposition]:=chunk.code;
 end;
SetLength(output,outputposition);
LZss_Ms.WriteBuffer(output[0],outputposition);
LZss_Ms.Position:=0;
end;