Blog. Just Blog

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

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Образ мышления: Assembler | Автор: ManHunter
Распаковка данных в формате LZ4 на Ассемблере
Распаковка данных в формате LZ4 на Ассемблере

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

В конце статьи вы найдете упаковщик, который сжимает данные по алгоритму LZ4. К нему прилагался bat-файл для демонстрации возможностей, меня удивило, что, несмотря на возможность прямой упаковки файлов, в нем сжимаемый файл передается упаковщику в качестве потока данных через STDIN. Выяснилось, что при упаковке файлов в начало упакованных данных добавляется маркер 03 21 4C 18, а при упаковке потока данных маркер меняется на 02 21 4C 18. На сайте с документацией по LZ4 такой маркер заявлен как устаревший формат блоков упакованных данных, который использовался в ранних версиях алгоритма. Но, как ни странно, при тестировании упаковщика на текстовых данных именно этот формат дал наибольшую степень сжатия. Да и на прочих данных результат оказался ничуть не хуже нового формата. Алгоритм распаковки для нового и старого формата отличается, поэтому функция распаковки учитывает этот момент. Соответственно, упакованные данные должны быть в legacy-формате. Более высокое сжатие дает упаковщик LZ4X от Ильи Муравьева, причем маркер в заголовке сжатых данных записывается правильный.
  1. ;------------------------------------------------------------
  2. ; Распаковка данных в формате LZ4
  3. ;------------------------------------------------------------
  4. ; Оригинальный код: Jim Leonard, модификация: ManHunter / PCL
  5. ;------------------------------------------------------------
  6. ; На входе:
  7. ;   lpCompressed - указатель на упакованные данные
  8. ;   lpOut - указатель на буфер для распакованных данных
  9. ; На выходе:
  10. ;   EAX = размер распакованных данных
  11. ;------------------------------------------------------------
  12. proc lz4_unpack lpCompressed:DWORD, lpOut:DWORD
  13.         pusha
  14.         mov     esi,[lpCompressed]
  15.         mov     edi,[lpOut]
  16.         lodsd
  17.         cmp     eax,184C2102h
  18.         jne     .done
  19.         lodsd
  20.         mov     ebx,eax
  21.         add     ebx,esi
  22.         xor     eax,eax
  23.         xor     ecx,ecx
  24. .parsetoken:
  25.         lodsb
  26.         movzx   edx,al
  27. .copyliterals:
  28.         mov     ecx,4
  29.         shr     al,cl
  30.         call    .buildfullcount
  31. .doliteralcopy:
  32.         rep     movsb
  33.         cmp     esi,ebx
  34.         jae     .done
  35. .copymatches:
  36.         lodsw
  37.         xchg    edx,eax
  38.         and     al,0Fh
  39.         call    .buildfullcount
  40. .domatchcopy:
  41.         push    esi
  42.         mov     esi,edi
  43.         sub     esi,edx
  44.         add     ecx,4
  45.         rep     movsb
  46.         pop     esi
  47.         jmp     .parsetoken
  48. .buildfullcount:
  49.         cmp     al,0Fh
  50.         xchg    ecx,eax
  51.         jne     .builddone
  52. .buildloop:
  53.         lodsb
  54.         add     ecx,eax
  55.         cmp     al,0FFh
  56.         je      .buildloop
  57. .builddone:
  58.         retn
  59. .done:
  60.         sub     edi,[lpOut]
  61.         mov     [esp+28],edi
  62.         popa
  63.         ret
  64. endp
В качестве параметров передается указатель на упакованные данные и указатель на буфер-приемник. На выходе в регистре EAX возвращается количество байт, которое было извлечено из сжатых данных. Если исходные данные не соответствуют формату, то в EAX возвращается 0. Размер принимающего буфера в процессе распаковки никак не проверяется, об этом вы должны позаботиться самостоятельно.

В заголовке LZ4 хранится информация о размере упакованных данных, но нет никакой информации об исходных данных. Хорошо, когда размер распакованных данных заранее известен или оперативную память под них можно выделить с запасом. Но если объем данных заранее не определен, то перед распаковкой его надо обязательно узнать. Для таких случаев я немного модифицировал функцию распаковки, чтобы она просто возвращала число байт, которые были бы заполнены в памяти после декомпрессии.
  1. ;---------------------------------------------------
  2. ; Получение размера распакованных данных
  3. ;---------------------------------------------------
  4. ; На входе:
  5. ;   lpCompressed - указатель на упакованные данные
  6. ; На выходе:
  7. ;   EAX = размер распакованных данных
  8. ;---------------------------------------------------
  9. proc lz4_size lpCompressed:DWORD
  10.         pusha
  11.         mov     esi,[lpCompressed]
  12.         xor     edi,edi
  13.         lodsd
  14.         cmp     eax,184C2102h
  15.         jne     .done
  16.         lodsd
  17.         mov     ebx,eax
  18.         add     ebx,esi
  19.         xor     eax,eax
  20.         xor     ecx,ecx
  21. .parsetoken:
  22.         lodsb
  23.         movzx   edx,al
  24. .copyliterals:
  25.         mov     ecx,4
  26.         shr     al,cl
  27.         call    .buildfullcount
  28. .doliteralcopy:
  29.         add     edi,ecx
  30.         add     esi,ecx
  31.         cmp     esi,ebx
  32.         jae     .done
  33. .copymatches:
  34.         lodsw
  35.         xchg    edx,eax
  36.         and     al,0Fh
  37.         call    .buildfullcount
  38. .domatchcopy:
  39.         add     ecx,4
  40.         add     edi,ecx
  41.         jmp     .parsetoken
  42. .buildfullcount:
  43.         cmp     al,0Fh
  44.         xchg    ecx,eax
  45.         jne     .builddone
  46. .buildloop:
  47.         lodsb
  48.         add     ecx,eax
  49.         cmp     al,0FFh
  50.         je      .buildloop
  51. .builddone:
  52.         retn
  53. .done:
  54.         ; EAX = размер распакованных данных
  55.         mov     [esp+28], edi
  56.         popa
  57.         ret
  58. endp
В качестве единственного параметра передается указатель на упакованные данные, на выходе в регистре EAX количество байт, которое получится после распаковки. Если исходные данные не соответствуют формату, то в EAX возвращается 0.

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

Пример программы с исходным текстом (FASM)Пример программы с исходным текстом (FASM)

LZ4.Unpack.Demo.zip (217,927 bytes)


Поделиться ссылкой ВКонтакте Поделиться ссылкой на Facebook Поделиться ссылкой на LiveJournal Поделиться ссылкой в Мой Круг Добавить в Мой мир Добавить на ЛиРу (Liveinternet) Добавить в закладки Memori Добавить в закладки Google
Просмотров: 493 | Комментариев: 3

Комментарии

Отзывы посетителей сайта о статье
котя (12.03.2021 в 17:07):
Ого, бомбаракета.

Автору - низкий поклон.

Забрал под unix
ManHunter (11.12.2020 в 10:04):
Только если будет пробегать рядом вместе с толковой документацией. Специально искать не планирую.

ЦитатаThis file format is in fact just plain LZ4 data with a custom header (magic number [8 bytes] and uncompressed file size [4 bytes, little endian]).

Так что отрезаешь заголовок и распаковываешь обычным LZ4. Может быть.
JSONLZ4 (11.12.2020 в 03:57):
А как насчет распаковки мозилловского формата JSONLZ4?
Там вроде LZ4 модифицированный какой-то

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

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2021
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.07 сек. / MySQL: 2 (0.0039 сек.) / Память: 4.75 Mb
Наверх