Упаковка и распаковка данных в формате LZ77 на Ассемблере
Упаковка и распаковка данных в формате LZ77 на Ассемблере
Алгоритм сжатия LZ77, также известный как LZ1, впервые был опубликован в 1977 году и получил свое название по первым буквам фамилий его авторов - Abraham Lempel и Jacob Ziv. LZ77 стал родоначальником для множества других алгоритмов сжатия, в том числе и разобранных в предыдущих статьях. Из-за особенностей реализации, более-менее приличные результаты алгоритм показывает на данных с повторяющимися элементами. Например, текст или разреженные двоичные данные. Данные с уникальными последовательностями не только плохо сжимаются, но даже могут увеличиваться в размере после сжатия, так как к ним прибавляются служебные данные для распаковки.
У меня был ассемблерный исходник функций упаковки и распаковки данных в формате LZ77 от comrade, мне осталось только перевести их на синтаксис FASM. Функция упаковки осталась практически без изменений, за исключением небольшой оптимизации кода. Если посмотрите код упаковщика из приложенного архива, то увидите, что кроме упакованных данных в сжатый файл записывается 4-байтовый заголовок с размером исходных данных. Эта информация в последующем используется при распаковке.
Code (Assembler) : Убрать нумерацию
- ;------------------------------------------------------------
- ; Упаковка данных в формате LZ77
- ;------------------------------------------------------------
- ; Оригинальный код: comrade, модификация: ManHunter / PCL
- ;------------------------------------------------------------
- ; На входе:
- ; lpOut - указатель на исходные данные
- ; dLen - размер исходных данных
- ; lpCompressed - указатель на буфер для упакованных данных
- ; На выходе:
- ; EAX = размер упакованных данных
- ;------------------------------------------------------------
- proc lz77_pack lpInput:DWORD,dLen:DWORD,lpCompressed:DWORD
- locals
- dwBestPos dd ?
- dwBestLength dd ?
- dwLength dd ?
- dwStack dd ?
- endl
- pusha
- mov eax,[dLen]
- xor eax,7
- inc eax
- shr eax,3
- push eax
- mov [dwStack],esp
- mov esi,[lpInput]
- mov edi,[lpCompressed]
- mov ebx,[lpCompressed]
- add edi,eax
- movsb
- movsw
- and [dwLength],0
- @@next:
- lea esp,[esi-256]
- xor ecx,ecx
- mov [dwBestLength],ecx
- cmp esp,[lpInput]
- jae @@cp00
- mov esp,[lpInput]
- @@cp00:
- cmp esp,esi
- jae @@cp01
- xor ecx,ecx
- mov edx,esi
- @@cm00:
- mov al,[esp]
- cmp al,[edx]
- jne @@cm01
- inc edx
- inc esp
- cmp esp,esi
- jae @@cp01
- mov eax,[lpInput]
- add eax,[dLen]
- cmp edx, eax
- jae @@cp01
- inc ecx
- jmp @@cm00
- @@cm01:
- inc esp
- cmp ecx,[dwBestLength]
- jbe @@cp00
- mov [dwBestPos],esp
- mov [dwBestLength],ecx
- jmp @@cp00
- @@cp01:
- lodsb
- cmp ecx,[dwBestLength]
- jbe @@cp03
- mov [dwBestPos],esp
- mov [dwBestLength],ecx
- @@cp03:
- mov edx,[dwLength]
- btr [ebx],edx
- cmp [dwBestLength],3
- jb @@nocp
- mov eax,esi
- sub eax,[dwBestPos]
- stosb
- mov eax,[dwBestLength]
- add esi,[dwBestLength]
- dec esi
- bts [ebx],edx
- @@nocp:
- stosb
- inc [dwLength]
- cmp [dwLength],32
- jb @@cp02
- and [dwLength],0
- add ebx,4
- @@cp02:
- mov eax,[lpInput]
- add eax,[dLen]
- cmp esi, eax
- jnz @@next
- @@done:
- mov esp,[dwStack]
- add ebx,4
- mov eax,ebx
- sub eax,[lpCompressed]
- stosd
- pop ebx
- sub edi,[lpCompressed]
- sub edi,ebx
- push edi
- mov esi,[lpCompressed]
- mov edi,[lpCompressed]
- add esi,ebx
- add edi,eax
- mov ecx,[esp]
- rep movsb
- pop ecx
- add eax,ecx
- mov [esp+28],eax
- popa
- ret
- endp
Code (Assembler) : Убрать нумерацию
- ; EAX = размер исходных данных
- mov ecx,eax
- xor ecx,07h
- inc ecx
- shr ecx,3
- add eax,ecx
- ; EAX = размер буфера-приемника
Code (Assembler) : Убрать нумерацию
- ;------------------------------------------------------------
- ; Распаковка данных в формате LZ77
- ;------------------------------------------------------------
- ; Оригинальный код: comrade, модификация: ManHunter / PCL
- ;------------------------------------------------------------
- ; На входе:
- ; lpCompressed - указатель на упакованные данные
- ; dLen - размер упакованных данных
- ; lpOut - указатель на буфер для распакованных данных
- ; На выходе:
- ; EAX = размер распакованных данных
- ;------------------------------------------------------------
- proc lz77_unpack lpCompressed:DWORD,dLen:DWORD,lpOut:DWORD
- pusha
- push ebp
- mov esi,[lpCompressed]
- mov edi,[lpOut]
- mov ecx,[dLen]
- lodsd
- mov ebx,eax
- add ebx,edi
- mov ebp,esi
- mov ecx,[esi+ecx-08h]
- add esi,ecx
- movsw
- movsb
- xor edx,edx
- .unpack:
- lodsb
- bt [ebp],edx
- jnc @f
- push ebx
- movzx ebx,al
- lodsb
- movzx ecx,al
- push esi
- mov esi,edi
- sub esi,ebx
- sub esi,ecx
- rep movsb
- pop esi
- pop ebx
- dec edi
- mov al,[edi]
- @@:
- cmp edx,32
- jb @f
- xor edx,edx
- add ebp,4
- @@:
- stosb
- inc edx
- cmp edi,ebx
- jb .unpack
- pop ebp
- sub edi,[lpOut]
- mov [esp+28],edi
- popa
- ret
- endp
В приложении примеры программ с исходными текстами. Это простейший упаковщик данных в формат LZ77, работающий через командную строку, и программа, которая извлекает из памяти иконку, упакованную по алгоритму LZ77, а затем выводит ее на форму.
Примеры программ с исходными текстами (FASM)
Просмотров: 1656 | Комментариев: 1
Метки: Assembler, распаковка
Внимание! Статья опубликована больше года назад, информация могла устареть!
Комментарии
Отзывы посетителей сайта о статье
ManHunter
(31.01.2021 в 14:14):
Немного подкорректировал разбор командной строки в упаковщике, архив обновлен.
Добавить комментарий
Заполните форму для добавления комментария
Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Вам помог этот сайт?
Поблагодарили 35,982 раза
Поблагодарили 35,982 раза
Буду очень благодарен, если размеcтите мою кнопочку:
 |
Яндекс ИКС: 360 |
 |
 |