Сжатие LZSS, нужна помощь.

Автор TTEMMA, 18 марта 2015, 21:00

« назад - далее »
Печать
Вниз СтраницыНазад 1 2 Все
Действия пользователя

Марат

#20
24 марта 2015, 18:13 Последнее редактирование: 24 марта 2015, 18:15 от Марат
Ошибка в функции write_lz.

Марат

#21
24 марта 2015, 18:55
Цитата: TTEMMA от 18 марта 2015, 21:23 

Цитата: Greengh0st от 18 марта 2015, 21: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

#22
24 марта 2015, 19:04
Вон оно как, спасибо за информацию, запомню:)

Proton

#23
25 марта 2015, 08:31
Спасибо за подсказку. Прошу проверить.
Спойлер

Код Выделить
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;
};
Программная неудача.

Марат

#24
25 марта 2015, 09:46
Цитата: Proton от 25 марта 2015, 08:31Спасибо за подсказку. Прошу проверить.
Спойлер

Код Выделить
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

#25
25 марта 2015, 10:17
Всё верно. Случайно добавил лишнюю "F" в маске.
Марат, а ты свою утилиту для Monster World в C++, С# или Delphi писал?
Программная неудача.

Марат

#26
25 марта 2015, 11:53
На дельфи. Я всё пишу на дельфях. Я уже привык к дельфи.

TTEMMA

#27
25 марта 2015, 13:40
К сожалению, под самый конец сбивается...

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

Код Выделить
#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;
}

Марат

#28
25 марта 2015, 13:48
Код Выделить
   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

#29
25 марта 2015, 13:52
Цитата: Марат от 25 марта 2015, 13:48Здесь ошибка. Сдвиг надо делать вправо, а не влево.
Исправил, заработало.
 
Большое спасибо, Proton, большое спасибо, Марат. Вы мои кумиры! ;)

Proton

#30
25 марта 2015, 15:26
Ребята, извините за косячный код. На скорую руку, без проверки на расжатие.
Программная неудача.

TTEMMA

#31
25 марта 2015, 15:34
Цитата: Proton от 25 марта 2015, 15:26Ребята, извините за косячный код. На скорую руку, без проверки на расжатие.
Да ничего, главное разобрались и всё работает. Кстати, сжатие лучше чем оригинал.

TTEMMA

#32
26 марта 2015, 00:22
Может и нагавн*кодил, но работает :)
Спойлер

Код Выделить
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;
Печать
Вверх СтраницыНазад 1 2 Все
Действия пользователя