Blog. Just Blog

Упаковка и распаковка данных в формате LZ77 на Ассемблере

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

Алгоритм сжатия LZ77, также известный как LZ1, впервые был опубликован в 1977 году и получил свое название по первым буквам фамилий его авторов - Abraham Lempel и Jacob Ziv. LZ77 стал родоначальником для множества других алгоритмов сжатия, в том числе и разобранных в предыдущих статьях. Из-за особенностей реализации, более-менее приличные результаты алгоритм показывает на данных с повторяющимися элементами. Например, текст или разреженные двоичные данные. Данные с уникальными последовательностями не только плохо сжимаются, но даже могут увеличиваться в размере после сжатия, так как к ним прибавляются служебные данные для распаковки.

У меня был ассемблерный исходник функций упаковки и распаковки данных в формате LZ77 от comrade, мне осталось только перевести их на синтаксис FASM. Функция упаковки осталась практически без изменений, за исключением небольшой оптимизации кода. Если посмотрите код упаковщика из приложенного архива, то увидите, что кроме упакованных данных в сжатый файл записывается 4-байтовый заголовок с размером исходных данных. Эта информация в последующем используется при распаковке.
  1. ;------------------------------------------------------------
  2. ; Упаковка данных в формате LZ77
  3. ;------------------------------------------------------------
  4. ; Оригинальный код: comrade, модификация: ManHunter / PCL
  5. ;------------------------------------------------------------
  6. ; На входе:
  7. ;   lpOut - указатель на исходные данные
  8. ;   dLen - размер исходных данных
  9. ;   lpCompressed - указатель на буфер для упакованных данных
  10. ; На выходе:
  11. ;   EAX = размер упакованных данных
  12. ;------------------------------------------------------------
  13. proc lz77_pack lpInput:DWORD,dLen:DWORD,lpCompressed:DWORD
  14.         locals
  15.             dwBestPos dd ?
  16.             dwBestLength dd ?
  17.             dwLength dd ?
  18.             dwStack dd ?
  19.         endl
  20.  
  21.         pusha
  22.  
  23.         mov     eax,[dLen]
  24.         xor     eax,7
  25.         inc     eax
  26.         shr     eax,3
  27.         push    eax
  28.         mov     [dwStack],esp
  29.         mov     esi,[lpInput]
  30.         mov     edi,[lpCompressed]
  31.         mov     ebx,[lpCompressed]
  32.         add     edi,eax
  33.         movsb
  34.         movsw
  35.         and     [dwLength],0
  36. @@next:
  37.         lea     esp,[esi-256]
  38.         xor     ecx,ecx
  39.         mov     [dwBestLength],ecx
  40.         cmp     esp,[lpInput]
  41.         jae     @@cp00
  42.         mov     esp,[lpInput]
  43. @@cp00:
  44.         cmp     esp,esi
  45.         jae     @@cp01
  46.         xor     ecx,ecx
  47.         mov     edx,esi
  48. @@cm00:
  49.         mov     al,[esp]
  50.         cmp     al,[edx]
  51.         jne     @@cm01
  52.         inc     edx
  53.         inc     esp
  54.         cmp     esp,esi
  55.         jae     @@cp01
  56.         mov     eax,[lpInput]
  57.         add     eax,[dLen]
  58.         cmp     edx, eax
  59.         jae     @@cp01
  60.         inc     ecx
  61.         jmp     @@cm00
  62. @@cm01:
  63.         inc     esp
  64.         cmp     ecx,[dwBestLength]
  65.         jbe     @@cp00
  66.         mov     [dwBestPos],esp
  67.         mov     [dwBestLength],ecx
  68.         jmp     @@cp00
  69. @@cp01:
  70.         lodsb
  71.         cmp     ecx,[dwBestLength]
  72.         jbe     @@cp03
  73.         mov     [dwBestPos],esp
  74.         mov     [dwBestLength],ecx
  75. @@cp03:
  76.         mov     edx,[dwLength]
  77.         btr     [ebx],edx
  78.         cmp     [dwBestLength],3
  79.         jb      @@nocp
  80.         mov     eax,esi
  81.         sub     eax,[dwBestPos]
  82.         stosb
  83.         mov     eax,[dwBestLength]
  84.         add     esi,[dwBestLength]
  85.         dec     esi
  86.         bts     [ebx],edx
  87. @@nocp:
  88.         stosb
  89.         inc     [dwLength]
  90.         cmp     [dwLength],32
  91.         jb      @@cp02
  92.         and     [dwLength],0
  93.         add     ebx,4
  94. @@cp02:
  95.         mov     eax,[lpInput]
  96.         add     eax,[dLen]
  97.         cmp     esi, eax
  98.         jnz     @@next
  99. @@done:
  100.         mov     esp,[dwStack]
  101.         add     ebx,4
  102.         mov     eax,ebx
  103.         sub     eax,[lpCompressed]
  104.         stosd
  105.         pop     ebx
  106.         sub     edi,[lpCompressed]
  107.         sub     edi,ebx
  108.         push    edi
  109.  
  110.         mov     esi,[lpCompressed]
  111.         mov     edi,[lpCompressed]
  112.         add     esi,ebx
  113.         add     edi,eax
  114.         mov     ecx,[esp]
  115.         rep     movsb
  116.  
  117.         pop     ecx
  118.         add     eax,ecx
  119.  
  120.         mov     [esp+28],eax
  121.         popa
  122.  
  123.         ret
  124. endp
В параметрах передается указатель на исходные данные, их размер и указатель на буфер-приемник для упакованных данных. На выходе в регистре EAX возвращается размер упакованных данных. Обратите внимание, что минимально необходимый размер буфера для приема упакованных данных считается по формуле:
  1.         ; EAX = размер исходных данных
  2.         mov     ecx,eax
  3.         xor     ecx,07h
  4.         inc     ecx
  5.         shr     ecx,3
  6.         add     eax,ecx
  7.         ; EAX = размер буфера-приемника
Функция распаковки претерпела наибольшие изменения, помимо адаптации ее под синтаксис FASM я постарался максимально оптимизировать код.
  1. ;------------------------------------------------------------
  2. ; Распаковка данных в формате LZ77
  3. ;------------------------------------------------------------
  4. ; Оригинальный код: comrade, модификация: ManHunter / PCL
  5. ;------------------------------------------------------------
  6. ; На входе:
  7. ;   lpCompressed - указатель на упакованные данные
  8. ;   dLen - размер упакованных данных
  9. ;   lpOut - указатель на буфер для распакованных данных
  10. ; На выходе:
  11. ;   EAX = размер распакованных данных
  12. ;------------------------------------------------------------
  13. proc lz77_unpack lpCompressed:DWORD,dLen:DWORD,lpOut:DWORD
  14.         pusha
  15.         push    ebp
  16.  
  17.         mov     esi,[lpCompressed]
  18.         mov     edi,[lpOut]
  19.         mov     ecx,[dLen]
  20.         lodsd
  21.         mov     ebx,eax
  22.         add     ebx,edi
  23.         mov     ebp,esi
  24.         mov     ecx,[esi+ecx-08h]
  25.         add     esi,ecx
  26.         movsw
  27.         movsb
  28.         xor     edx,edx
  29. .unpack:
  30.         lodsb
  31.         bt      [ebp],edx
  32.         jnc     @f
  33.         push    ebx
  34.         movzx   ebx,al
  35.         lodsb
  36.         movzx   ecx,al
  37.         push    esi
  38.         mov     esi,edi
  39.         sub     esi,ebx
  40.         sub     esi,ecx
  41.         rep     movsb
  42.         pop     esi
  43.         pop     ebx
  44.         dec     edi
  45.         mov     al,[edi]
  46. @@:
  47.         cmp     edx,32
  48.         jb      @f
  49.         xor     edx,edx
  50.         add     ebp,4
  51. @@:
  52.         stosb
  53.         inc     edx
  54.         cmp     edi,ebx
  55.         jb      .unpack
  56.  
  57.         pop     ebp
  58.         sub     edi,[lpOut]
  59.         mov     [esp+28],edi
  60.         popa
  61.         ret
  62. endp
В качестве параметров передается указатель на упакованные данные, их размер и указатель на буфер-приемник. На выходе в регистре EAX возвращается количество байт, которое было извлечено из сжатых данных. Размер принимающего буфера в процессе распаковки никак не проверяется, об этом вы должны позаботиться самостоятельно. В принципе, можно модифицировать упаковщик, чтобы размер упакованных данных сохранялся в их заголовке, но это вы уже сделайте самостоятельно.

В приложении примеры программ с исходными текстами. Это простейший упаковщик данных в формат LZ77, работающий через командную строку, и программа, которая извлекает из памяти иконку, упакованную по алгоритму LZ77, а затем выводит ее на форму.

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

LZ77.Pack.Unpack.Demo.zip (9,848 bytes)


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

Комментарии

Отзывы посетителей сайта о статье
ManHunter (31.01.2021 в 14:14):
Немного подкорректировал разбор командной строки в упаковщике, архив обновлен.

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

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

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