Распаковка данных в формате LZ4 на Ассемблере

Алгоритм сжатия LZ4 был разработан Yann Collet в 2011-м году. При небольшом размере упаковщика и распаковщика, LZ4 обладает очень высокой скоростью обработки данных и хорошей степенью компрессии, поэтому используется в большом числе серьезных проектов. На офсайте есть ссылки на реализации этого алгоритма на различных языках программирования, в том числе и вариант на 16-битном Ассемблере от Jim Leonard. Для использования в своих программах я адаптировал его функцию распаковки LZ4.

В конце статьи вы найдете упаковщик, который сжимает данные по алгоритму LZ4. К нему прилагался bat-файл для демонстрации возможностей, меня удивило, что, несмотря на возможность прямой упаковки файлов, в нем сжимаемый файл передается упаковщику в качестве потока данных через STDIN. Выяснилось, что при упаковке файлов в начало упакованных данных добавляется маркер 03 21 4C 18, а при упаковке потока данных маркер меняется на 02 21 4C 18. На сайте с документацией по LZ4 такой маркер заявлен как устаревший формат блоков упакованных данных, который использовался в ранних версиях алгоритма. Но, как ни странно, при тестировании упаковщика на текстовых данных именно этот формат дал наибольшую степень сжатия. Да и на прочих данных результат оказался ничуть не хуже нового формата. Алгоритм распаковки для нового и старого формата отличается, поэтому функция распаковки учитывает этот момент. Соответственно, упакованные данные должны быть в legacy-формате. Более высокое сжатие дает упаковщик LZ4X от Ильи Муравьева, причем маркер в заголовке сжатых данных записывается правильный.В качестве параметров передается указатель на упакованные данные и указатель на буфер-приемник. На выходе в регистре EAX возвращается количество байт, которое было извлечено из сжатых данных. Если исходные данные не соответствуют формату, то в EAX возвращается 0. Размер принимающего буфера в процессе распаковки никак не проверяется, об этом вы должны позаботиться самостоятельно.

В заголовке LZ4 хранится информация о размере упакованных данных, но нет никакой информации об исходных данных. Хорошо, когда размер распакованных данных заранее известен или оперативную память под них можно выделить с запасом. Но если объем данных заранее не определен, то перед распаковкой его надо обязательно узнать. Для таких случаев я немного модифицировал функцию распаковки, чтобы она просто возвращала число байт, которые были бы заполнены в памяти после декомпрессии.В качестве единственного параметра передается указатель на упакованные данные, на выходе в регистре EAX количество байт, которое получится после распаковки. Если исходные данные не соответствуют формату, то в EAX возвращается 0.

В приложении пример программы с исходным текстом, которая извлекает из памяти иконку, упакованную по алгоритму LZ4, и выводит ее на форму. Там же в архиве оригинал ассемблерной функции распаковки от Jim Leonard, упаковщик LZ4 от Yann Collet с примерами и упаковщик LZ4X от Ильи Муравьева.


В связи с популярностью алгоритма LZ4, он с небольшими модификациями используется в различных программных продуктах. Например, с его помощью упаковываются файлы с закладками браузера Mozilla Firefox. Там вся разница заключается только в заголовке, который идет перед упакованными данными. После 8-байтного маркера-идентификатора (ASCIIZ-строка "mozLz40") в заголовке записан DWORD с размером оригинальных данных, так что ничего дополнительно вычислять не придется. Размер упакованных данных равен общему размеру данных минус 12 байт заголовка. Функция распаковки будет следующей:В приложении пример программы с исходным текстом, которая извлекает из памяти иконку, упакованную по алгоритму MozLZ4, и выводит ее на форму. Там же в архиве утилиты от Avi Halachmi для работы с упакованными закладками Mozilla Firefox.


Алгоритм LZ4 используется даже в Android-приложениях, а точнее при упаковке dll компоновщиком Xamarin. Тут тоже меняется только заголовок, а упакованные данные прекрасно извлекаются по уже знакомому вам методу. Заголовок состоит из 12 байт: 4 байта маркер "XALZ", затем какой-то четырехбайтный индекс и после него DWORD с размером исходных данных. Распаковывается практически так же, как и предыдущий пример.В приложении пример программы с исходным текстом, которая распаковывает dll, обработанную Xamarin и сохраняет распакованный файл в unpacked.dll.

Комментарии

Добавить комментарий

Для вставки цитаты выделите текст и нажмите сюда

Имя*:

Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.

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