Неизвестный алгоритм сжатия

[didim99]

Доброго времени суток, уважаемые форумчане.

После пары месяцев самостоятельных изысканий прошу помощи у более опытных в данном вопросе людей, т.к. все мои попытки остались безрезультатны.

Имеется скомпиленная ELF-библиотека, реализующая помимо прочего некий алгоритм упаковки/распаковки текстовых данных. Реально ли восстановить этот алгоритм до кода на высокоуровневом ЯП из IDовского листинга и псевдокода hex-rays?

Функций реализующих этот самый алгоритм всего штук 10, основные из них всего 2 (из того, что мне удалось понять): sub_4D9B70 (0x004D9B70), на которую ссылается LZ_CompressFast (0x004DA1D0), и LZ_Uncompress (0x004DA200).

Может кто помочь понять этот алгоритм или хотя бы подсказать, в какую сторону копать (может есть уже его какая-то программная реализация?)

Саму библиотеку и "проект" IDы прилагаю.
1-5-0.zip
Так же прилагаю пример сжатого и несжатого файла (если нужно - их можно получить в неограниченном количестве)
sbx.zip
Всем заранее спасибо.

P.S. Если что не так, прошу сильно не пинать, т.к. тут впервые.

[OKOB]

"Неизвестный алгоритм сжатия"! Извините, наверное только вам. LZ - это Abraham Lempel и Jakob Ziv. Старый добрый алгоритм. Трудились вы не много, глядя на "проект" IDы. Аж названия функций получили благодаря паблик меткам. А погуглить названия функций не позволяет образование/желание/религия/мама/... (нужное подчеркнуть). А так бы сразу нашлось, что это кусок из Basic Compression Library (http://bcl.comli.eu/), а именно
* Name: lz.c
* Author: Marcus Geelnard
* Description: LZ77 coder/decoder implementation.
а копнув глубже нашли бы как советуют переписать LZ_Uncompress, что бы она от стандартной реализации не дающей размер распакованного блока, все же его возвращала. С исходными кодами уже веселей реверсить если даже что-то в реализации и было исправлено. Например сразу видно, что компилятор заинлайнил вот этот кусок кода
inpos += _LZ_ReadVarSize( &length, &in[ inpos ] );
inpos += _LZ_ReadVarSize( &offset, &in[ inpos ] );
и т.д.
Если сразу не заведется с распаковкой нужно собрать приложение с библиотекой и с исходным кодом и немного подебажить.
Домашняя работа не выполнена, садись два.

PS: Пинал не сильно, как просили.

[didim99]

Большое спасибо за пинок в нужную сторону. :)
Неизвестным этот алгоритм мне показался потому, что сжатый файл не похож на результат работы LZ77.
Так и есть, оказалось это LZ77 с небольшими наворотами. Эти самые навороты я успещно разобрал - все нечетные байты xor-нуты с 0xff, но дальше снова начинаются проблемы.

Я собрал эту самую библиотеку bcl, просто запустив мейкфайл в Ubuntu (возможно, это уже неправильно), и оно даже работает, однако, работает только в одну сторону - на сжатие (причем, судя по всему, работает корректно, сжатый файл выглядит точно так же, как отxorенный файл sasbx). На декомпрессию упорно не хочет работать (даже только что сжатых ей же файлов), выводя страничку помощи и все. Хотя если запустить файл bcltest, то получаю

Code:

Testing 000...

  Compression: 214828/2000149 bytes (10.7%) - OK!

    Compression speed: 257.3 KB/s (7590.99 ms)

    Uncompression speed: 942243.4 KB/s (2.07 ms)

ЧЯДНТ?

P.S. Практически ничего не понимаю в C и особенностях компиляции, знаю лишь базовые основы программирования и немного язык php, потому действую в основном методом научного тыка. Если такой уровень подготовки ниже порога вхождения сюда - извиняюсь, придется идти за помощью куда-то еще...
P.P.S. Естественно, я гуглил эти функции и далее гуглил алгоритмы семейчтва LZ, но в рунете ничего толком не удвлось найти, а с английским пока не очень в ладах.

[OKOB]

Не знаю как и что упорно не желает у вас работать на декомпрессию. Все работает аки часы. Код простой и может мешать только незнание С.
Сделал домашнее задание за вас. Восстановил код слоя над LZ, и сделал пример с распаковкой. Ваш тестовый файл Dayson_rev_30.sasbx распаковывается.

ЗЫ: Обращаю ваше внимание, что при упаковке\распаковке этими функциями исходный файл удаляется.

lz77.rar

[didim99]

Большое спасибо за помощь. Собрал ваши исходники gcc в той же Ubuntu - оно работает (правда пришлось заменить unlink() на remove()).
Кажется, пора заняться изучением C. :)

Тема закрыта.