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

[TTEMMA]

Собственно, проблема в самой запаковке - я понятия не имею, как написать программу, для сжатия. До этого со сжатиями не работал, всё что сделал, это переписал распаковщик LZ11 с C# на Delphi.
Ещё давно, Leo2236 переписал для меня распаковщик LZSS с C++ на Delphi. Само сжатие флаговое(Может есть и другие типы). Исходный код таков:
 

Код Выделить Развернуть

procedure TForm1.LZSSDec(LZSS_Ms:TStream);
var
Temp_Ms:Tmemorystream;
ch, Temp_, Temp: Byte;
i, jump, size, flag: Integer;
b: array[0..16] of Byte;
Temp_Offset, Last_Offset: DWORD;
begin
flag := 1;
LZSS_Ms.Position := 0;
Temp_Ms := TMemoryStream.Create;
while LZSS_Ms.Position < LZSS_Ms.Size do
begin
if flag = 1 then
begin
LZSS_Ms.Read(Temp, 1);
flag := Temp or $100;
end;
LZSS_Ms.Read(ch, 1);
if Bool(flag and 1) then Temp_Ms.Write(ch, 1) else
begin
LZSS_Ms.Read(Temp_, 1);
jump := ((Temp_ and $F) shl 8) or ch;
size := (Temp_ shr 4) + 2;
Temp_Offset := Temp_Ms.Position;
Temp_Ms.Position := Temp_Ms.Position - jump;
Last_Offset := Temp_Ms.Position;
for i := 0 to size - 1 do
begin
Temp_Ms.Read(b[i], 1);
if Temp_Ms.Position >= Temp_Ms.Size then
Temp_Ms.Position := Last_Offset;
end;
Temp_Ms.Position := Temp_Offset;
Temp_Ms.Write(b, size);
end;
flag := flag shr 1;
end;
LZSS_Ms.Size:=0;
Temp_Ms.Position:=0;
LZSS_Ms.CopyFrom(Temp_Ms,Temp_Ms.Size);
LZSS_Ms.Position:=0;
Temp_Ms.Free;
end;Относительно, как всё это работает - понимаю. Но не могу понять, как сжать распакованные данные? Объясните, дураку.
 
P.S.Вряд ли, но может кому и понадобится:

Спойлер

Код Выделить Развернуть

procedure LZ11Decompress(Source,Dest:TStream);
var
DestLength:LongWord;
buffer:TMemoryStream;
Flag:Byte;
i,j:integer;
Value,tempb:Byte;
BufferPointer,temp:Integer;
matchDistance, matchLength:Integer;
b1,b2,b3,b4:byte;
begin
Source.Position:=0;
Dest.Position:=0;
BufferPointer:=0;
Source.Read(DestLength,4);
DestLength:=DestLength shr 8;
if DestLength=0 then
Source.Read(DestLength,4);
Buffer:=TMemoryStream.Create;
while Source.Position<Source.Size do
begin
Source.Read(Flag,1);
for I := 0 to 7 do
begin
if (flag and $80) = 0 then
begin
Source.Read(Value,1);
Dest.Write(Value,1);
Buffer.Position:=BufferPointer;
buffer.Write(Value,1);
BufferPointer:=(BufferPointer+1) and $FFF;
end
else begin
Source.Read(B1,1);
Source.Read(B2,1);
case b1 shr 4 of
0: begin
Source.Read(B3,1);
matchDistance:=(((b2 and $F) shl 8) or b3) + 1;
matchLength:=(((b1 and $F) shl 4) or (b2 shr 4)) + 17;

end;
1: begin
Source.Read(B3,1);
Source.Read(B4,1);
matchDistance:=(((b3 and $F) shl 8) or b4) + 1;
matchLength:=(((b1 and $F) shl 12) or (b2 shl 4) or (b3 shr 4)) + 273;

end;
else  begin
matchDistance:= (((b1 and $F) shl 8) or b2) + 1;
matchLength:= (b1 shr 4) + 1;

end;
end;
for j := 1 to matchLength do
begin
temp:=(bufferPointer - matchDistance) and $FFF;
buffer.Position:=temp;
buffer.Read(tempb,1);
Dest.Write(tempb,1);
buffer.Position:=bufferPointer;
buffer.Write(tempb,1);
BufferPointer:=(BufferPointer+1) and $FFF;
end;
end;
if Source.Position>Source.Size then break;
if Dest.Position>DestLength then
begin
Dest.Size:=Dest.Size-1;
exit;
end;
flag:=flag shl 1;
end;
end;
end;

[Greengh0st]

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

[TTEMMA]

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

Она LZ77, а не LZSS

[SPOT]

TTEMMA, можно увидить исходник на C#?

[TTEMMA]

TTEMMA, можно увидить исходник на C#?

С C# я переписывал LZ11, а мне нужно разобраться с LZSS, но исходник вот:

Спойлер

Код Выделить Развернуть

public override void Decompress(Stream source, Stream destination)
{
// Set the source, destination, and buffer pointers
int sourcePointer = 0x4;
int destinationPointer = 0x0;
int bufferPointer = 0x0;
// Get the source and destination length
int sourceLength = (int)(source.Length - source.Position);
int destinationLength = PTStream.ReadInt32(source) >> 8;
if (destinationLength == 0)
{
// If the destination length is larger than 0xFFFFFF, then the next 4 bytes is the destination length
destinationLength = PTStream.ReadInt32(source);
sourcePointer += 4;
}
// Initalize the buffer
byte[] buffer = new byte[0x1000];
// Start decompression
while (sourcePointer < sourceLength)
{
byte flag = PTStream.ReadByte(source);
sourcePointer++;
for (int i = 0; i < 8; i++)
{
if ((flag & 0x80) == 0) // Not compressed
{
byte value = PTStream.ReadByte(source);
sourcePointer++;
destination.WriteByte(value);
destinationPointer++;
buffer[bufferPointer] = value;
bufferPointer = (bufferPointer + 1) & 0xFFF;
}
else // Data is compressed
{
int matchDistance, matchLength;
// Read in the first 2 bytes (since they are used for all of these)
byte b1 = PTStream.ReadByte(source), b2 = PTStream.ReadByte(source), b3, b4;
sourcePointer += 2;
// Let's determine how many bytes the distance & length pair take up
switch (b1 >> 4)
{
case 0: // 3 bytes
b3 = PTStream.ReadByte(source);
sourcePointer++;
matchDistance = (((b2 & 0xF) << 8) | b3) + 1;
matchLength = (((b1 & 0xF) << 4) | (b2 >> 4)) + 17;
break;
case 1: // 4 bytes
b3 = PTStream.ReadByte(source);
b4 = PTStream.ReadByte(source);
sourcePointer += 2;
matchDistance = (((b3 & 0xF) << 8) | b4) + 1;
matchLength = (((b1 & 0xF) << 12) | (b2 << 4) | (b3 >> 4)) + 273;
break;
default: // 2 bytes
matchDistance = (((b1 & 0xF) << 8) | b2) + 1;
matchLength = (b1 >> 4) + 1;
break;
}
for (int j = 0; j < matchLength; j++)
{
destination.WriteByte(buffer[(bufferPointer - matchDistance) & 0xFFF]);
destinationPointer++;
buffer[bufferPointer] = buffer[(bufferPointer - matchDistance) & 0xFFF];
bufferPointer = (bufferPointer + 1) & 0xFFF;
}
}
// Check to see if we reached the end of the source
if (sourcePointer >= sourceLength)
{
break;
}
// Check to see if we wrote too much data to the destination
if (destinationPointer > destinationLength)
{
throw new Exception("Too much data written to the destination.");
}
flag <<= 1;
}
}
}

[SPOT]

Относительно, как всё это работает - понимаю. Но не могу понять, как сжать распакованные данные?

Аналогично тому, как они разжимаются, только наоборот
А что конкретно не ясно, уточни?

[TTEMMA]

Не понятно больше то, как написать функцию для поиска одинаковых значений, а потом ещё и установки флагов под эти найденные повторы

[Mefistotel]

Известно, что распаковщик написать проще, чем запаковщик.) Марат бы мог подсказать, только он вроде и не зареган здесь.
Для примеров распаковки не помешали бы и файлы для наглядности (запакованный, распакованный).

[TTEMMA]

Прошу

[Proton]

Готов помочь разобраться, но времени сейчас совсем нет.

[TTEMMA]

Буду рад и благодарен вашей помощи

[SPOT]

Как успехи?

[Proton]

На этой неделе у меня будет возможность обсудить эту тему.

[TTEMMA]

Ох, шикарно, буду ждать.

[Proton]

Спойлер

Код Выделить Развернуть

#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;

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

_headerPosition = 2;
_inputPosition = 0;
_outputPosition = 3;

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;

cout << hex << "Size of data to be compressed: " << (int)_inputSize;

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);

cout << hex << "\nStarting compression...";
cout << hex << "\nInput position = [" << setw(4) << (int) _inputPosition << "]";
cout << hex << "\tOutput position = [" << setw(4) << (int) _outputPosition << "]";

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

while (_inputPosition<_inputSize)

{

cout << hex << "\nInput position = [" << setw(4) << (int) _inputPosition << "]";
cout << hex << "\tOutput position = [" << setw(4) << (int) _outputPosition << "]";

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;
}

h1=(_outputPosition-2)&0xff;
h2=((_outputPosition-2)&0xff00)>>8;

//h1=(_inputSize)&0xff;
//h2=((_inputSize)&0xff00)>>8;

_outputData[0]=h1;
_outputData[1]=h2;
_outputSize = _outputPosition;

cout << hex << "\nSize of compressed data: " << (int)(_outputPosition) << endl ;

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;
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_lit(uint32_t &read_pos, uint8_t* read_buf, uint32_t &write_pos, uint8_t* write_buf, chunk_t &chunk)
{
int lit_size;

cout << hex << "\nLITERAL = ["<< setw(2) << (int)read_buf[read_pos] << "]";
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;
}

[TTEMMA]

Ух ты, быстро:) Спасибо.
Осталось только мне под Delphi переписать и все.

[Proton]

Советую переходить на С++. Конечно, я тоже начинал с Delphi и Pascal, но большую часть вещей там не сделаешь. В моём коде в самом начале файла "st101_compressed.bin" записывается размер упакованных данных. Функция поиска использует полный перебор. Для описания совпадений и контрольных байтов с флагами используются соответствующие структуры.
Декомпрессор я не писал, поэтому прошу проверить корректность сжатия.

[Mefistotel]

Ух ты, быстро Спасибо.
Осталось только мне под Delphi переписать и все.

Не забудь реверснутый код потом приложить.

[TTEMMA]

Советую переходить на С++. Конечно, я тоже начинал с Delphi и Pascal, но большую часть вещей там не сделаешь. В моём коде в самом начале файла "st101_compressed.bin" записывается размер упакованных данных. Функция поиска использует полный перебор. Для описания совпадений и контрольных байтов с флагами используются соответствующие структуры.
Декомпрессор я не писал, поэтому прошу проверить корректность сжатия.

Да я собираюсь переходить, или на C++, или на C#.
Относительно, я всё понял, вечерком начну переписывать.
 
 

 

Ух ты, быстро Спасибо.
Осталось только мне под Delphi переписать и все.

Не забудь реверснутый код потом приложить.
 

Хорошо;)

[TTEMMA]

Скомпилировал ваш проект, сжал распакованный файл и пытался расжать с помощью моей программы - получается совсем не то, что должно быть.
Убрал с вашего исходника добавления размера файла, начало хидера поставил на 0, начала исходного файла на 1. После этого стал похож на оригинал(распакованный), но вот беда, размер больше на $20, и только начальные байты похожи на оригинал, дальше то не те байты, то оригинальные.