Собственно, проблема в самой запаковке - я понятия не имею, как написать программу, для сжатия. До этого со сжатиями не работал, всё что сделал, это переписал распаковщик 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;
А ты пробовал прогой Трикзтера распаковать данные? У него вроде под LZSS заточено GBA.
Цитата: Greengh0st от 18 марта 2015, 21:15А ты пробовал прогой Трикзтера распаковать данные? У него вроде под LZSS заточено GBA.
Она LZ77, а не LZSS
TTEMMA, можно увидить исходник на C#?
Цитата: SPOT от 18 марта 2015, 21:23TTEMMA, можно увидить исходник на 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;
}
}
}
Цитата: TTEMMA от 18 марта 2015, 21:00Относительно, как всё это работает - понимаю. Но не могу понять, как сжать распакованные данные?
Аналогично тому, как они разжимаются, только наоборот :)
А что конкретно не ясно, уточни?
Не понятно больше то, как написать функцию для поиска одинаковых значений, а потом ещё и установки флагов под эти найденные повторы
Известно, что распаковщик написать проще, чем запаковщик.) Марат бы мог подсказать, только он вроде и не зареган здесь.
Для примеров распаковки не помешали бы и файлы для наглядности (запакованный, распакованный).
Прошу
Готов помочь разобраться, но времени сейчас совсем нет.
Буду рад и благодарен вашей помощи
Как успехи?
На этой неделе у меня будет возможность обсудить эту тему.
Ох, шикарно, буду ждать.
Спойлер
#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;
}
Ух ты, быстро:) Спасибо.
Осталось только мне под Delphi переписать и все.
Советую переходить на С++. Конечно, я тоже начинал с Delphi и Pascal, но большую часть вещей там не сделаешь. В моём коде в самом начале файла "st101_compressed.bin" записывается размер упакованных данных. Функция поиска использует полный перебор. Для описания совпадений и контрольных байтов с флагами используются соответствующие структуры.
Декомпрессор я не писал, поэтому прошу проверить корректность сжатия.
Цитата: TTEMMA от 24 марта 2015, 12:48Ух ты, быстро :) Спасибо.
Осталось только мне под Delphi переписать и все.
Не забудь реверснутый код потом приложить. :)
Цитата: Proton от 24 марта 2015, 13:09Советую переходить на С++. Конечно, я тоже начинал с Delphi и Pascal, но большую часть вещей там не сделаешь. В моём коде в самом начале файла "st101_compressed.bin" записывается размер упакованных данных. Функция поиска использует полный перебор. Для описания совпадений и контрольных байтов с флагами используются соответствующие структуры.
Декомпрессор я не писал, поэтому прошу проверить корректность сжатия.
Да я собираюсь переходить, или на C++, или на C#.
Относительно, я всё понял, вечерком начну переписывать.
Цитата: Mefistotel от 24 марта 2015, 13:10
Цитата: TTEMMA от 24 марта 2015, 12:48Ух ты, быстро :) Спасибо.
Осталось только мне под Delphi переписать и все.
Не забудь реверснутый код потом приложить. :)
Хорошо;)
Скомпилировал ваш проект, сжал распакованный файл и пытался расжать с помощью моей программы - получается совсем не то, что должно быть.
Убрал с вашего исходника добавления размера файла, начало хидера поставил на 0, начала исходного файла на 1. После этого стал похож на оригинал(распакованный), но вот беда, размер больше на $20, и только начальные байты похожи на оригинал, дальше то не те байты, то оригинальные.
Ошибка в функции write_lz.
Цитата: 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.
Вон оно как, спасибо за информацию, запомню:)
Спасибо за подсказку. Прошу проверить.
Спойлер
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;
};
Цитата: 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;
Всё верно. Случайно добавил лишнюю "F" в маске.
Марат, а ты свою утилиту для Monster World в C++, С# или Delphi писал?
На дельфи. Я всё пишу на дельфях. Я уже привык к дельфи.
К сожалению, под самый конец сбивается...
(http://s7.hostingkartinok.com/uploads/images/2015/03/3579ce5c338cbfedd3e075691e560a15.png)
Может я что-то не так исправил:
Спойлер
#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;
}Здесь ошибка. Сдвиг надо делать вправо, а не влево.
Цитата: Марат от 25 марта 2015, 13:48Здесь ошибка. Сдвиг надо делать вправо, а не влево.
Исправил, заработало.
Большое спасибо, Proton, большое спасибо, Марат. Вы мои кумиры! ;)
Ребята, извините за косячный код. На скорую руку, без проверки на расжатие.
Цитата: Proton от 25 марта 2015, 15:26Ребята, извините за косячный код. На скорую руку, без проверки на расжатие.
Да ничего, главное разобрались и всё работает. Кстати, сжатие лучше чем оригинал.
Может и нагавн*кодил, но работает :)
Спойлер
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;