Blog. Just Blog

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

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

На просторах этих ваших интернетов обнаружился вот такой простенький алгоритм упаковки, обозначенный автором как LZ48. Собственно, это даже не совсем алгоритм, а исходник утилиты для упаковки и распаковки данных за авторством roudoudou. Больше никакой информации нет, поэтому пояснить, что означают цифры "48", я не могу, все вопросы к автору, если, конечно, найдете первоисточник. Вряд ли вы когда-нибудь встретите этот упаковщик в "дикой природе", но для коллекции сгодится. Да и для какой-нибудь лабораторной работы тоже может оказаться полезным.

Для упаковки и распаковки файлов используется упомянутая утилита, я ее скомпилировал из оригинального исходника в исполняемый файл. Степень сжатия по сравнению с другими алгоритмами слабенькая, тем не менее, это вполне себе полноценный алгоритм компрессии, имеющий право на существование. Текстовые файлы жмет примерно в половину, с бинарниками и уникальными наборами данных ситуация похуже. Скорость обработки данных как на упаковку, так и на распаковку, очень хорошая. Я портировал алгоритм распаковки с языка C на Ассемблер, вот что у меня получилось.
Code (Assembler) : Убрать нумерацию
  1. ;------------------------------------------------------------
  2. ; Распаковка данных в формате LZ48
  3. ; by ManHunter / PCL (www.manhunter.ru)
  4. ;------------------------------------------------------------
  5. ; На входе:
  6. ;   lpCompressed - указатель на упакованные данные
  7. ;   lpOut - указатель на буфер для распакованных данных
  8. ; На выходе:
  9. ;   EAX = размер распакованных данных
  10. ;------------------------------------------------------------
  11. proc lz48_unpack lpCompressed:DWORD, lpOut:DWORD
  12.         pusha
  13.         mov     esi,[lpCompressed]
  14.         mov     edi,[lpOut]
  15.  
  16.         xor     eax,eax
  17.         movsb
  18. .lz48_unpack:
  19.         lodsb
  20.         movzx   ecx,al
  21.         mov     edx,ecx
  22.         and     cl,0xF0
  23.         shr     cl,4
  24.         and     dl,0x0F
  25.  
  26.         cmp     cl,15
  27.         jne     .lz48_unpack_1
  28. .lz48_literal:
  29.         lodsb
  30.         add     ecx,eax
  31.         cmp     al,255
  32.         je      .lz48_literal
  33. .lz48_unpack_1:
  34.         rep     movsb
  35.  
  36.         cmp     dl,15
  37.         jne     .lz48_unpack_2
  38. .lz48_matchkey:
  39.         lodsb
  40.         add     edx,eax
  41.         cmp     al,255
  42.         je      .lz48_matchkey
  43. .lz48_unpack_2:
  44.         inc     edx
  45.         inc     edx
  46.         inc     edx
  47.  
  48.         lodsb
  49.         cmp     al,0xFF
  50.         je      .done
  51.  
  52.         inc     eax
  53.         push    esi
  54.         mov     esi,edi
  55.         sub     esi,eax
  56.         mov     ecx,edx
  57.         rep     movsb
  58.         pop     esi
  59.  
  60.         jmp     .lz48_unpack
  61. .done:
  62.         sub     edi,[lpOut]
  63.         mov     [esp+28],edi
  64.         popa
  65.         ret
  66. endp
В качестве параметров передается указатель на упакованные данные и указатель на буфер-приемник. На выходе в регистре EAX возвращается количество байт, которое было извлечено из сжатых данных. Размер принимающего буфера в процессе распаковки никак не проверяется, об этом вы должны позаботиться самостоятельно.

Если посмотреть исходник упаковщика, то там обнаружится код, который определяет размер буфера для приема распакованных данных. Поскольку больше никакой информации о размере исходных данных не сохраняется, придется им воспользоваться. Этот код я тоже портировал на Ассемблер:
Code (Assembler) : Убрать нумерацию
  1. ;---------------------------------------------------
  2. ; Получение размера распакованных данных
  3. ;---------------------------------------------------
  4. ; На входе:
  5. ;   lpCompressed - указатель на упакованные данные
  6. ; На выходе:
  7. ;   EAX = размер распакованных данных
  8. ;---------------------------------------------------
  9. proc lz48_size lpCompressed:DWORD
  10.         pusha
  11.         mov     esi,[lpCompressed]
  12.         inc     esi
  13.         xor     edi,edi
  14.         inc     edi
  15.         xor     eax,eax
  16. .lz48_size:
  17.         lodsb
  18.         movzx   ecx,al
  19.         mov     edx,ecx
  20.         and     cl,0xF0
  21.         shr     cl,4
  22.         and     dl,0x0F
  23.  
  24.         cmp     cl,15
  25.         jne     .lz48_size_1
  26. .lz48_size_literal:
  27.         lodsb
  28.         add     ecx,eax
  29.         cmp     al,255
  30.         je      .lz48_size_literal
  31. .lz48_size_1:
  32.         add     edi,ecx
  33.         add     esi,ecx
  34.  
  35.         cmp     dl,15
  36.         jne     .lz48_size_2
  37. .lz48_size_matchkey:
  38.         lodsb
  39.         add     edx,eax
  40.         cmp     al,255
  41.         je      .lz48_size_matchkey
  42. .lz48_size_2:
  43.         inc     edx
  44.         inc     edx
  45.         inc     edx
  46.  
  47.         cmp     byte[esi],0xFF
  48.         je      .done
  49.  
  50.         inc     esi
  51.         add     edi,edx
  52.         jmp     .lz48_size
  53. .done:
  54.         ; EAX = размер распакованных данных
  55.         mov     [esp+28],edi
  56.         popa
  57.         ret
  58. endp
В качестве единственного параметра передается указатель на упакованные данные, на выходе в регистре EAX количество байт, которое получится после распаковки.

Функция упаковки данных в формате LZ48. За основу взят все тот же исходник. На оптимизацию особо не налегал, кроме уж совсем очевидных мест, в остальном чистый подстрочник. Уверен, можно сделать и получше. Скорость работы при этом хорошая.
Code (Assembler) : Убрать нумерацию
  1. ;------------------------------------------------------------
  2. ; Упаковка данных в формате LZ48
  3. ; by ManHunter / PCL (www.manhunter.ru)
  4. ;------------------------------------------------------------
  5. ; На входе:
  6. ;   lpOut - указатель на исходные данные
  7. ;   dLen - размер исходных данных
  8. ;   lpCompressed - указатель на буфер для упакованных данных
  9. ; На выходе:
  10. ;   EAX = размер упакованных данных
  11. ;------------------------------------------------------------
  12. proc lz48_pack lpInput:DWORD,dLen:DWORD,lpCompressed:DWORD
  13.         locals
  14.             startscan dd ?
  15.             current dd ?
  16.             curscan dd ?
  17.             maxoffset dd ?
  18.             maxlength dd ?
  19.             matchlength dd ?
  20.             literal dd ?
  21.             literaloffset dd ?
  22.         endl
  23.  
  24.         pusha
  25.  
  26.         mov     esi,[lpInput]
  27.         mov     edi,[lpCompressed]
  28.         mov     [current],1
  29.         mov     [literal],0
  30.         mov     [literaloffset],1
  31.  
  32.         ; ioutput=1
  33.         xor     ebx,ebx
  34.         inc     ebx
  35.  
  36.         ; first byte always literal
  37.         movsb
  38.         dec     esi
  39.         dec     edi
  40.  
  41.         ; force short data encoding
  42.         cmp     [dLen],5
  43.         jae     .lz48_encode_loop
  44.  
  45.         movsb
  46.         mov     eax,[dLen]
  47.         dec     eax
  48.         mov     ecx,eax
  49.         shl     al,4
  50.         stosb
  51.         rep     movsb
  52.         mov     al,0xFF
  53.         stosb
  54.         add     ebx,[dLen]
  55.         inc     ebx
  56.         jmp     .loc_done
  57.  
  58. .lz48_encode_loop:
  59.         ; while (current<length) {
  60.         mov     eax,[dLen]
  61.         cmp     [current],eax
  62.         jae     .lz48_encode_loop_done
  63.  
  64.         ; maxlength=0
  65.         mov     [maxlength],0
  66.         ; startscan=current-255
  67.         ; if (startscan<0) startscan=0
  68.         mov     [startscan],0
  69.         mov     eax,[current]
  70.         sub     eax,255
  71.         js      .lz48_encode_01
  72.         mov     [startscan],eax
  73. .lz48_encode_01:
  74.         ; while (startscan<current) {
  75.         mov     eax,[current]
  76.         cmp     [startscan],eax
  77.         jae     .lz48_encode_11
  78.  
  79.         ; matchlength=0
  80.         mov     [matchlength],0
  81.         ; curscan=current
  82.         mov     eax,[current]
  83.         mov     [curscan],eax
  84.  
  85.         ; for (i=startscan;curscan<length;i++) {
  86.         mov     ecx,[startscan]
  87. .lz48_encode_20:
  88.         mov     eax,[dLen]
  89.         cmp     [curscan],eax
  90.         jae     .lz48_encode_22
  91.  
  92.         ; if (data[i]==data[curscan++])
  93.         mov     eax,[curscan]
  94.         mov     al,byte[esi+eax]
  95.         inc     [curscan]
  96.         cmp     al,byte[esi+ecx]
  97.         jne     .lz48_encode_22
  98.         ; matchlength++
  99.         inc     [matchlength]
  100.         inc     ecx
  101.         jmp     .lz48_encode_20
  102.         ; }
  103. .lz48_encode_22:
  104.         ; if (matchlength>=3 && matchlength>maxlength) {
  105.         mov     eax,[matchlength]
  106.         cmp     eax,3
  107.         jb      .lz48_encode_21
  108.         cmp     eax,[maxlength]
  109.         jbe     .lz48_encode_21
  110.  
  111.         ; maxlength=matchlength
  112.         mov     [maxlength],eax
  113.         ; maxoffset=startscan
  114.         mov     eax,[startscan]
  115.         mov     [maxoffset],eax
  116. .lz48_encode_21:
  117.         ; }
  118.  
  119.         ; startscan++;
  120.         inc     [startscan]
  121.         jmp     .lz48_encode_01
  122.         ; }
  123. .lz48_encode_11:
  124.         ; if (maxlength) {
  125.         cmp     [maxlength],0
  126.         je      .lz48_encode_31
  127.         ; ioutput+=LZ48_encode_block(odata+ioutput,data,
  128.         ; literaloffset,literal,current-maxoffset,maxlength)
  129.         push    [maxlength]
  130.         mov     eax,[current]
  131.         sub     eax,[maxoffset]
  132.         push    eax
  133.         push    [literal]
  134.         push    [literaloffset]
  135.         push    esi
  136.         mov     eax,edi
  137.         add     eax,ebx
  138.         push    eax
  139.         stdcall LZ48_encode_block
  140.         add     ebx,eax
  141.  
  142.         ; current+=maxlength
  143.         mov     eax,[maxlength]
  144.         add     eax,[current]
  145.         mov     [current],eax
  146.         ; literaloffset=current
  147.         mov     [literaloffset],eax
  148.         ; literal=0
  149.         mov     [literal],0
  150.         jmp     .lz48_encode_32
  151. .lz48_encode_31:
  152.         ; } else {
  153.         ; literal++;
  154.         inc     [literal]
  155.         ; current++;
  156.         inc     [current]
  157. .lz48_encode_32:
  158.         ; }
  159.         jmp     .lz48_encode_loop
  160. .lz48_encode_loop_done:
  161.         ; ioutput+=LZ48_encode_block(odata+ioutput,data,
  162.         ; literaloffset,literal,0,0)
  163.         push    0
  164.         push    0
  165.         push    [literal]
  166.         push    [literaloffset]
  167.         push    esi
  168.         mov     eax,edi
  169.         add     eax,ebx
  170.         push    eax
  171.         stdcall LZ48_encode_block
  172.         add     ebx,eax
  173. .loc_done:
  174.         mov     [esp+28],ebx
  175.         popa
  176.  
  177.         ret
  178. endp
  179.  
  180. proc LZ48_encode_extended_length lpCompressed:DWORD, dLen:DWORD
  181.         pusha
  182.         mov     eax,[dLen]
  183.         mov     edi,[lpCompressed]
  184.         ; int ioutput=0
  185.         xor     ebx,ebx
  186.         xor     ecx,ecx
  187.         dec     cl
  188.         ; while (length>255) {
  189. .leel_01:
  190.         cmp     eax,ecx
  191.         jbe     .leel_02
  192.         ; odata[ioutput++]=0xFF
  193.         mov     byte [edi+ebx],cl
  194.         inc     ebx
  195.         ; length-=255
  196.         sub     eax,ecx
  197.         jmp     .leel_01
  198. .leel_02:
  199.         ; odata[ioutput++]=length
  200.         mov     byte [edi+ebx],al
  201.         inc     ebx
  202.         mov     [esp+28],ebx
  203.         popa
  204.         ret
  205. endp
  206.  
  207. proc LZ48_encode_block lpCompressed:DWORD, lpData:DWORD,\
  208.         literaloffset:DWORD, literalcpt:DWORD, _offset:DWORD,\
  209.         maxlength:DWORD
  210.  
  211.         pusha
  212.         mov     edi,[lpCompressed]
  213.  
  214.         ; int ioutput=1
  215.         xor     ebx,ebx
  216.         inc     ebx
  217.         ; int token=0
  218.         xor     edx,edx
  219.  
  220.         ; if (literalcpt<15) {
  221.         cmp     [literalcpt],15
  222.         jae     .leb_01
  223.  
  224.         ; token=literalcpt<<4
  225.         mov     edx,[literalcpt]
  226.         shl     edx,4
  227.         jmp     .leb_02
  228. .leb_01:
  229.         ; } else {
  230.         ; token=0xF0
  231.         mov     dl,0xF0
  232.  
  233.         ; ioutput+=LZ48_encode_extended_length(odata+ioutput,literalcpt-15)
  234.         mov     eax,[literalcpt]
  235.         sub     eax,15
  236.         push    eax
  237.         mov     eax,edi
  238.         add     eax,ebx
  239.         push    eax
  240.         stdcall LZ48_encode_extended_length
  241.         add     ebx,eax
  242. .leb_02:
  243.         ; }
  244.  
  245.         ; for (i=0;i<literalcpt;i++) odata[ioutput++]=data[literaloffset++]
  246.         xor     ecx,ecx
  247.         mov     esi,[lpData]
  248. .leb_11:
  249.         cmp     ecx,[literalcpt]
  250.         jae     .leb_12
  251.  
  252.         mov     eax,[literaloffset]
  253.         mov     al,byte[esi+eax]
  254.         inc     [literaloffset]
  255.         mov     byte[edi+ebx],al
  256.         inc     ebx
  257.  
  258.         inc     ecx
  259.         jmp     .leb_11
  260. .leb_12:
  261.  
  262.         ; if (maxlength<18) {
  263.         cmp     [maxlength],18
  264.         jae     .leb_21
  265.  
  266.         ; if (maxlength>2) {
  267.         cmp     [maxlength],2
  268.         jbe     .leb_22
  269.  
  270.         ; token|=(maxlength-3)
  271.         mov     eax,[maxlength]
  272.         sub     eax,3
  273.         or      edx,eax
  274.         ; }
  275.         jmp     .leb_22
  276. .leb_21:
  277.         ; } else {
  278.         ; token|=0xF
  279.         or      dl,0xF
  280.         ; ioutput+=LZ48_encode_extended_length(odata+ioutput,maxlength-18)
  281.         mov     eax,[maxlength]
  282.         sub     eax,18
  283.         push    eax
  284.         mov     eax,edi
  285.         add     eax,ebx
  286.         push    eax
  287.         stdcall LZ48_encode_extended_length
  288.         add     ebx,eax
  289. .leb_22:
  290.         ; }
  291.  
  292.         ; odata[ioutput++]=offset-1
  293.         mov     eax,[_offset]
  294.         dec     eax
  295.         mov     byte [edi+ebx],al
  296.         inc     ebx
  297.         ; odata[0]=token
  298.         mov     byte [edi],dl
  299.  
  300.         ; return ioutput
  301.         mov     [esp+28],ebx
  302.         popa
  303.         ret
  304. endp
В параметрах передается указатель на исходные данные, их размер и указатель на буфер-приемник для упакованных данных. На выходе в регистре EAX возвращается размер упакованных данных. Минимально необходимый размер буфера для приема упакованных данных считается по той же формуле, что и у LZ77. В исходнике формула другая (длина * 1.1), но эта мне нравится больше.

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

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

LZ48.Pack.Unpack.Demo.zip (19,888 bytes)


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

Внимание! Статья опубликована больше года назад, информация могла устареть!

Комментарии

Отзывы посетителей сайта о статье
Комментариeв нет

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

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

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Это я :-)
Если программист в девять утра уже на работе, значит он там же и ночевал
Главная страница Web-мастеру и не только Образ мышления: Assembler Мои программы Software Темная сторона Силы Обзоры техники А еще я туда ем! Жизнь в оффлайне Всякая всячина
Карта сайта Ссылки Обратная связь Правила сайта Настройки сайта RSS-канал
Я в Telegram
Ограничение по возрасту 16+ Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Метки статей
.NET (32), AJAX (5), Assembler (375), COM (44), CSS (44), Exif (15), FASM (8), Firefox (7), HDD (17), Hello Teddy (9), HTML (53), iconBIT (4), JavaScript (77), MySQL (13), Nikon (19), PDF (10), PHP (125), Samsung (6), SEO (12), Sublime Text (9), Telegram (5), TintonLife (4), UGREEN (4), Windows 7 (67), аккумуляторы (23), аксессуары (12), анализаторы файлов (8), архиваторы (6), аттракционы (7), безопасность (55), браузеры (16), бытовая техника (21), варенье (19), ВВЦ (9), ВДНХ (14), видео (20), Воробьевы горы (9), вторые блюда (128), выпечка (31), выставки (120), генератор ПСЧ (10), графика (122), десерты (31), Египет (9), заготовки на зиму (47), закуска (23), закуска к пиву (26), зарядные устройства (24), защита (15), зоопарки (10), игры (36), иконки (22), интерфейс (26), исследование защиты (323), каша (4), клавиатура (7), Коломенское (37), консоль (7), концерты (52), Кузьминки (4), куклы (27), ледяные скульптуры (6), мои программы (69), мониторы (6), музеи (78), мультимедиа (82), мясо (63), напитки (14), ноутбуки (8), обфускация (7), окна (71), оформление сайта (51), парки Москвы (7), песчаные скульптуры (13), плееры (10), подводная съемка (4), поздравления (132), полезные функции (47), прохождения (4), процессы (25), птица (23), путешествия (26), распаковка (22), реверсинг (52), регулярные выражения (5), рыба (35), салаты (19), сброс триала (4), сеть (37), система (179), Сокольники (8), соусы (16), супы (14), телефоны (10), Тунис (6), умный дом (15), файлы справки (7), фаст-фуд (18), фестиваль цветов (5), флешки (5), фото (23), хеши (18), числа (8), юмор (12), яйца (19), Яндекс (11)
Вам помог этот сайт?
Сказать спасибо! Поблагодарили 35,952 раза
<< 2025 - ЯНВАРЬ >>
Пн Вт Ср Чт Пт Сб Вс
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    
Нашли на сайте орфографическую ошибку? Выделите ее мышкой и нажмите
Ctrl
+
Enter
Буду очень благодарен, если размеcтите мою кнопочку:
Личный блог ManHunter'а
Valid CSS Valid XHTML 1.0 Transitional Valid mobileOK Basic Valid RSS
Яндекс тИЦ: {YANDEX_TIC} Яндекс ИКС: 360
Сейчас я слушаю
---
Имя:

Сообщение:

Осталось символов: 200

   
-
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2025
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.07 сек. / MySQL: 2 (0.0047 сек.) / Память: 4.5 Mb
Наверх