Blog. Just Blog

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

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

Алгоритм компрессии LZSS - очередная модификация алгоритма LZ77 за авторством James Storer и Thomas Szymanski. По первым буквам их фамилий алгоритм и получил свое название. Впервые авторы опубликовали свою работу в 1982 году, с тех пор на базе LZSS появилось несколько компрессоров от разных авторов. Скорость упаковки не самая высокая, коэффициент сжатия тоже оставляет желать лучшего, зато хорошая скорость распаковки.

Как я уже упомянул выше, в природе есть несколько инструментов, использующих этот алгоритм сжатия. Я собрал утилиту для сжатия на основе исходников от Sebastian Steinhauer, она есть в прилагаемом архиве.

Упакованные данные в формате LZSS не предусматривают никакой информации о размере исходных данных, а также при распаковке алгоритм самостоятельно никак не определяет окончание потока упакованных данных. Так что для функции распаковки приходится передавать как минимум еще один параметр - размер упакованных данных.
  1. ;------------------------------------------------------------
  2. ; Распаковка данных в формате LZSS
  3. ;------------------------------------------------------------
  4. ; На входе:
  5. ;   lpCompressed - указатель на упакованные данные
  6. ;   lpOut - указатель на буфер для распакованных данных
  7. ;   dSize - размер упакованных данных
  8. ; На выходе:
  9. ;   EAX = размер распакованных данных
  10. ;------------------------------------------------------------
  11. proc lzss_unpack lpCompressed:DWORD, lpOut:DWORD, dSize:DWORD
  12.         pusha
  13.  
  14.         mov     esi,[lpCompressed]
  15.         mov     edi,[lpOut]
  16.  
  17.         mov     eax,[dSize]
  18.         lea     ebx,[esi+eax]
  19.  
  20. lzss_loop:
  21.         mov     ah,9
  22.         lodsb
  23.  
  24. lzss_main:
  25.         cmp     esi,ebx
  26.         jae     lzss_exit
  27.  
  28.         dec     ah
  29.         jz      lzss_loop
  30.  
  31.         rcr     al,1
  32.         jnc     read_block
  33.  
  34.         movsb
  35. lzss_next:
  36.         and     al,7Fh
  37.         jmp     lzss_main
  38. read_block:
  39.         movzx   edx,word[esi]
  40.         xchg    dl,dh
  41.         add     esi,2
  42.         mov     ecx,edx
  43.         and     ecx,15
  44.         add     ecx,3
  45.         shr     edx,4
  46.         push    esi
  47.         lea     esi,[edi-1]
  48.         sub     esi,edx
  49.         rep     movsb
  50.         pop     esi
  51.         jmp     lzss_next
  52. lzss_exit:
  53.         sub     edi,[lpOut]
  54.         mov     [esp+28],edi
  55.         popa
  56.         ret
  57. endp
Также по результатам тестирования я выяснил, что итоговый размер распакованных данных отличается в большую сторону от размера оригинальных данных. Пусть на несколько байт, но все-таки неточность присутствует. Так что при использовании этого алгоритма в реальных проектах надо обязательно это учитывать и принудительно обрезать распакованные данные до оригинального размера. По этой же причине не будет функции для определения размера распакованных данных. Это не тот случай, когда допустима погрешность даже в байт.

В приложении пример программы с исходным текстом, которая извлекает из памяти иконку, упакованную по алгоритму LZSS, и выводит ее на форму.

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

LZSS.Unpack.Demo.zip (38,555 bytes)


Поделиться ссылкой ВКонтакте
Просмотров: 317 | Комментариев: 6

Комментарии

Отзывы посетителей сайта о статье
Petya (12.02.2024 в 16:39):
Звиняйте. Слишком тонкий он у вас тут.
ManHunter (12.02.2024 в 16:30):
Petya, тут человек в юмор пытается, а ты умные слова говоришь.
Petya (12.02.2024 в 16:25):
Если серьёзно, то всё просто - LZ остались от оригинального алгоритма и означают Lempel&Ziv. А SS уже от упомянутых людей.
As is (11.02.2024 в 19:42):
Ну а 4то? - прикольно! Интересно, какой подход был-бы к образованию названия, если бы у одного из авторов фамилия начиналась, скажем, с буквы A?
ManHunter (11.02.2024 в 19:12):
Во, шутки за 300 подвезли.
As is (11.02.2024 в 19:10):
"LZ77 за авторством James Storer и Thomas Szymanski. По первым буквам их фамилий алгоритм и получил свое название." - буква Z, у одного из авторов, явно не первая в фамилии, и ни у одного, ни в фамилии, ни в имени нет буквы L :)

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

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

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