Допустим имеем файл и нужно перенести его в своей программе на чужую машину. Если этот файл будет внешним (на подобии библиотеки или драйвера), то сразу бросится в глаза. А что если зашить его в своё тело и создавать при запуске основного приложения? Благо производительность современных процессоров это позволяет и жертва даже не успеет понять в чём дело. Другими словами получим матку, которая будет порождать файлы.
Всё-бы хорошо, только таскать в себе готовые бинарники типа exe\dll в несжатом виде тоже не лучшая идея – одних только "байтов выравнивания" в них под 50%, а для использования готовых архиваторов нужен к нему распаковщик. Так-что иметь в запазухе обычный зиппер это всегда гуд, а данная статья (надеюсь) поможет вам разобраться в его деталях. Буду использовать ассемблер FASM, двоичный редактор HxD, ну и виндовый кальк в инженерном виде.
----------------------------------------
Общие положения
Характерной особенностью данных является их избыточность. Причём наблюдается она у всех типов данных, будь то бинарный поток или человеческая речь. В надежде донести до собеседника свою мысль, мы невольно повторяем одинаковые слова – это улучшает восприятие информации. Но когда речь идёт о хранении или передаче данных средствами компьютерной техники, избыточность оказывает нам медвежью услугу, повышая её стоимость.
Процент избыточности привязан к типу данных, где место на олимпе занимают как-раз двоичные программы, ..потом идёт видео, графика и на последнем месте файлы типа *.txt. К примеру, если открыть любую программу или видос в каком-нибудь HEX-редакторе, можно чётко наблюдать в нём цепочки повторяющихся байт, которые так и хочется закодировать в формате "Байт-->Повторов". Поскольку здесь я планирую "поженить" именно две прожки, то мне как-нельзя лучше подходит алгоритм сжатия RLE, что переводится как Run-Length-Encoding.
В природе существуют ещё два алго сжатия – это "Лемпеля-Зива" (LZ) и нашумевший алгоритм "Хаффмана". Чтобы добиться наилучших результатов и создать универсальный паккер для любых типов данных, обычно три эти алгоритма комбинируют в один флакон. Однако для нашего случая будет достаточно только самого простого RLE, который мы поместим прямо в программу-матку.
В алгоритме RLE, для кодирования цепочек одинаковых байт (не обязательно нулей), применяют байт-маркеры. К примеру, маркер
05h,30h заставит декодер архиватора отправить на выход 5 байт со-значением 0х30, и т.д. (первый байт является счётчиком). Если в бинарнике байты следуют в разнобой, то они вообще никак не кодируются. Таким образом, на белом коне здесь маркеры, которые своим 2-байтным значением способны сжать болото из 127-ми повторяющихся байт. Но почему именно из 127, ведь максимальное значение байта равно 256? Здесь нужно остановиться и вспомнить, как процессор кодирует числа со-знаком..Бит "SF" в регистре флагов процессора EFLAGS
Примечательным фактом в программировании является то, что логические элементы процессора не понимают отрицательных чисел – для них все числа положительные. Когда перед программистом встаёт какая-нибудь математическая задача, то ответственность по контролю за отрицательными числами полностью ложится на его собственные плечи. Для этого инженеры ввели во-флаговый регистр
EFLAGS соответствующий бит и назвали его "знаковым" SF – Sign Flag. Он занял позицию (7) в этом регистре, что демонстрирует рисунок ниже (позаимствован из руководства Intel том.3):
В большинстве случаях, на флаги процессора воздействуют арифметические инструкции типа
ADD\SUB\MUL\DIV, логические инструкции XOR\AND\OR\NOT\NEG\INC\DEC, инструкции сдвигов и ротации SHR\SHL\ROR\ROL и некоторые другие. Это даём нам возможность при арифметических операциях контролировать флаг CF переноса битов из младшего байта в старший, флаг чётности битов в байте PF, флаг переноса битов из младшей тетрады байта в старшую AF, флаг нуля ZF, а так-же упомянутый флаг отрицательного числа SF.Таким образом, аппаратное обеспечение устанавливает флаг знака SF в единицу, если последняя арифметическая операция привела к отрицательному значению. В противном случае (для положительного результата) SF сбрасывается в 0. Отрицательное число характеризует самый старший бит результата. В зависимости от размера операндов инструкции, значимым битом является бит 7 (для байтов), бит 15 (для слов word), бит 31 (для двойных слов dword) или бит 63 (для четверных слов qword).
Поскольку мы планируем искать цепочку байт (а не слов или двойных слов), то соответственно должны контролировать бит 7. Для того-чтобы указать знак числа, достаточно одного разряда (бита). В зависимости от того, как мы воспринимаем число, значения байта может лежать в диапазоне от
-127..+127 (байт со-знаком), или 0..255 (байт без знака). Вот пример:
C-подобный:
Байт со-знаком: 10110111 = -55
Байт со-знаком: 00110111 = +55
Байт без знака: 10110111 = 183
|
+---> знаковый битДетали реализации алгоритма RLE
Допустим задана последовательность байт ниже, которая подлежит сжатию:
C-подобный:
Кодируемая строка:
-----------------------------------------------
41 41 41 41 42 42 42 42 42 43 43 44 45 46 47 48 AAAABBBBBCCDEFGHАлгоритм RLE советует нам заменить её структурой, где указывается значение кодируемого байта и счётчик его повторений. Если под счётчик использовать 1 байт, то мы сможем закодировать в нём 256 одинаковых элементов – далее будем называть этот "байт-маркером". Здесь напрашивается решение – вставлять маркер перед каждой последовательностью, например так:
C-подобный:
Закодированный вариант:
-------------------------------------------
04.41 05.42 02.43 01.44 01.45 01.46 01.47 01.48 .A.B.C.D.E.F.G.H
-----------------------------------
Коэффициент сжатия: 16 (вход) / 16 (выход) = 1% (нет сжатия)В данном случаем, маркером является каждый\первый байт пары (я отделил его точками). Работающий по такому алго декодер читает данные с входного потока словами, и использует старший байт в качестве счётчика для младшего. Всё идёт по-плану, пока цепочка не нарушится, после чего нам приходится тратить на каждый байт один маркер, и весь выигрыш вылетает в трубу.
Для решения этой проблемы, условимся воспринимать маркер, как байт со-знаком. То-есть мы задействуем семь младших бит для счётчика повторений
0..127, а самый старший 8-ой бит – будет флагом. Не смотря на то, что таким образом мы потеряли в длине 127 против 255, зато теперь получили логику и сможем ответить уже на два вопроса: "байты в строке дублируются (1), или-же идут в разнобой (0)?".В качестве примера к вышесказанному, попробуем закодировать по алгоритму RLE тот-же блок данных, только теперь в байт-маркере старший бит будет служить флагом, повторяется цепочка, или нет:
C-подобный:
;// диапазон: 00h..7Fh = 127 -> счётчик произвольных байт;
;// диапазон: 80h..FFh = 127 -> счётчик одинаковых байт.
// Кодируемая строка:
-----------------------------------------------
41 41 41 41 42 42 42 42 42 43 43 44 45 46 47 48 AAAABBBBBCCDEFGH
// Закодированный вариант:
-------------------------------------------
84 41 85 42 82 43 05 44 45 46 47 48 „A…B‚C.DEFGH
-----------------------------------
// Коэффициент сжатия: 16 / 12 = 1,33%Рассмотрим его подробней..
Декодер начинает чтение закодированных данных и тут-же врезается в первый маркер со-значением
0х84 (1000.0100b, т.е. старший бит взведён в единицу). Логической инструкцией XOR он проверяет его на знак и делает вывод, что значение следующего за ним байта нужно воспринимать как цепочку. Теперь, декодер вычитает константу 0х80 от маркера, и получает счётчик последовательности (здесь 4 или 0000.0100b). Следуя своему алгоритму, теперь декодер читает следующий байт 0х41, как перед ним восстают все данные для декодирования данной последовательности.Но что будет, когда декодер нарвётся (в примере выше) на маркер со-значением
0х05 ? Как говорилось выше, установленный в нуль знаковый бит является флагом нарушения последовательности, поэтому он просто сделает своё значение счётчиком, и отправит все последующие за собой байты, в выходной поток.Как-видим, логика алгоритма RLE проста до неприличия, однако при удачных обстоятельствах она позволяет сжать
127 повторяющихся байт буквально до 2-х байт. Если в процессе кодирования данных алгоритм обнаружит во-входном потоке цепочку более чем из 127 байт, то он должен будет вставить ещё один маркер, указав в нём длину торчащего наружу хвоста примерно так:
C-подобный:
130-байтная цепочка нулей: FF 00 83 00
260-байтная цепочка троек: FF 03 FF 03 85 03Обзор выше доказывает, что от алгоритма RLE можно получить хороший выхлоп только при сжатии последовательности одинаковых байт. В принципе, в исполняемых файлах типа exe\dll таких последовательностей хоть отбавляй, а для текущей задачи по слиянию двух файлов нам больше и не нужно – главное чтобы код удовлетворял требованиям.
Практическая часть – воплощение задуманного
В примере ниже продемонстрируем программу, которая выведет виндовое "окно для выбора файлов", после чего упакует его по описанному алгоритму RLE. Как упоминалось в начале статьи, декодерирование и распаковкой будет заниматься у нас программа-матка, поэтому декодер мы поместим не в эту программу, а в программу-носитель (хотя можно было сделать и универсальную).
Для запроса файла для упаковки, задействуем API-функцию GetOpenFileName(). Эта функция BOOL и возвращает
EAX=1, если нам "выпадет решка" и нуль, если файл открыть не удастся. У неё всего один аргумент – указатель на довольно информативную структуру "OpenFileName". Внутри этой структуры мы получим имя открываемого файла, со-всей его подноготной. Полное описание данной функции можно найти
Ссылка скрыта от гостей
:
C-подобный:
GetOpenFileName (
LPOPENFILENAME ofn ) //; линк на структуру "OpenFileName"После того-как файл откроем, выделяем под него память функцией VirtualAlloc() и скопируем в этот регион памяти всё содержимое файла. На следующем шаге выделяем ещё одну область памяти, куда будем сбрасывать зашифрованные данные. Ну и в конце вычисляем размер упакованных данных и записываем их в выходной файл "packed.bin" (выбрать по вкусу). Сам алгоритм сжатия прокомментирован по максимуму, поэтому не вижу смысла повторяться – вот пример:
C-подобный:
format PE gui
include 'win32ax.inc'
;//-------
.data
ofn OPENFILENAME
fName db 128 dup(0)
inHndl dd 0
fOut db 'packed.bin',0
outHndl dd 0
filter db 'Программы',0
db '*.exe;*.dll;*.sys;',0,0
capt db 'Упаковщик EXE-файлов',0
info db 'Имя файла: %s',13,10
db '-----------------------------',13,10
db 'Размер до сжатия....: %d байт',13,10
db 'Размер после сжатия: %d байт' ,0
endMes db 256 dup(0)
inpBuff dd 0
outBuff dd 0
fSize dd 0
;//-------
.code
start:
;//======= Подготовительные операции.. ==============
;// перед вызовом GetOpenFileName()
;// нужно заполнить некоторые поля структцры "OpenFileName" (ofn)
mov [ofn.lStructSize],76 ;// её длина в байтах
mov [ofn.lpstrFilter],filter ;// задаём тип открываемых файлов
mov [ofn.lpstrFile],fName ;// куда сохранить имя открываемого файла
mov [ofn.nMaxFile],512 ;// длинна в байтах имени (ХР и выше)
mov [ofn.Flags], OFN_EXPLORER ;// стиль виндового окна
invoke GetOpenFileName, ofn ;// запросить системное окно выбора файлов!
;// Открываем выбранный файл ;//
invoke _lopen,fName,2 ;// 2 = атрибут R\W
mov [inHndl],eax ;// запомнить его дескриптор
;// Запрашиваем его размер ;//
invoke GetFileSize,eax,0 ;//
mov [fSize],eax ;// запомнить размер файла
;// Выделяем буфер для чтения файла ;//
invoke VirtualAlloc,0,[fSize],0x3000,4
mov [inpBuff],eax ;// его адрес
;// Читаем в выделенный буфер весь файл ;//
invoke _lread,[inHndl],[inpBuff],[fSize]
;// Создаём выходной файл "packet.bin" ;//
invoke _lcreat,fOut,0 ;//
mov [outHndl],eax ;// его дескриптор
;// Выделяем под него буфер ;//
invoke VirtualAlloc,0,[fSize],0x3000,4
mov [outBuff],eax ;// его адреc.
;//============= КОДЕР ==========================
;// Теперь всё готово и можно паковать.
;// Байт-маркер в AH, ECX = длина файла
;// ESI = источник, EDI = приёмник
;//-----------------------------------------------
@pack: mov ecx,[fSize] ;// кол-во данных в буфере
mov edi,[outBuff] ;// адрес приёмника (для записи в файл)
mov esi,[inpBuff] ;// адрес источника данных
@find: xor eax,eax ;// очищаем маркер в AH!
lodsb ;// берём в AL очередной байт из ESI
cmp al,byte[esi] ;// сравниваем его со-следующим байтом
jnz @hash ;// нет одинаковой цепочки! (мусор)
call dubleCount ;// иначе: на процедуру подсчёта одинаковой цепочки
or ecx,ecx ;// конец файла? (проверить ECX на нуль)
jnz @find ;// нет - мотаем..
jmp @exit ;// иначе: на выход!
;// Процедура подсчёта длины НЕодинаковой последовательности.
;// Как найдём одинаковую цепочку - выходим.
;// Нужно проверять маркер на переполнение,
;// если он достигнет 0х7F, вставляем его в выходной поток.
;//---------------------------------
@hash: inc ah ;// считаем в маркер длину цепочки
cmp ah,7Fh ;// тест на знаковое переполнение
jz @save1 ;// вставить, если заполнился!
lodsb ;// иначе: возьмём следующий байт с потока(IN)
cmp al,byte[esi] ;// сравниваем его с соседним
je @save1 ;// одинаковая цепочка! пора на выход.
loop @hash ;// иначе: продолжаем считать
@save1: shr ax,8 ;// AL = маркер, AH = 0 (заодно обновили его)
stosb ;// вставляем маркер в поток(OUT)!
push ecx esi ;// внешний счётчик и указатель
mov ecx,eax ;// EСХ = длина цепочки неодинаковых байт
sub esi,ecx ;// вернём указатель источника назад
dec esi ;// ..коррекция.
rep movsb ;// скопировать EСХ-байт из IN в OUT!
pop esi ecx ;// восстановить внешний цикл!
loop @find ;// продолжаем сжимать блок..
;// Процедура "dubleCount", для подсчёта одинаковой цепочки байт.
;// С ней дела обстоят чуть проще..
;//--------------------------------
dubleCount:
or ah,10000000b ;// взводим старший (знаковый) бит в маркере
@dup: inc ah ;// считаем длину одинаковой цепочки
cmp ah,0 ;// проверка на переполнение маркера!
jnz @ok ;// переход, если в маркере есть место
rol ax,8 ;// иначе: AL = маркер, AH = значение байта
stosw ;// записать маркер и значение, в поток(OUT)
mov ah,80h ;// обновляем маркер!
@ok: lodsb ;// читаем дальше поток(IN)..
cmp al,byte[esi] ;// сравниваем соседние байты
jnz @save2 ;// нет последовательности!
loop @dup ;// всё идёт по-плану..
@save2: rol ax,8 ;// цепочка прервалась!
stosw ;// вставить маркер,
ret ;// ..и выйти из процедуры.
;// ============= КОНЕЦ КОДЕРА =======================
;// Запишем упакованные данные в файл.
;// Для начала нужно вычислить их размер.
@exit: nop ;//
mov ecx,edi ;// ECX = хвост потока(OUT)
sub ecx,[outBuff] ;// отнять от него начало
push ecx ;// запомнить разницу для вывода на экран
invoke _lwrite,[outHndl],[outBuff],ecx ;// запись сжатых данных в файл!
;// Прибить дескрипторы всех открытых файлов
invoke _lclose,[inHndl]
invoke _lclose,[outHndl]
;// Вывод инфы на экран
pop ecx ;// ECX = размер упакованного файла
invoke wsprintf,endMes,info,fName,[fSize],ecx ;// перевести всё в символы
invoke MessageBox,0,endMes,capt,0 ;// боксим в мессагу
invoke ExitProcess,0 ;// Game-Over!!!
.end start ;//
Нужно отметить, что профит коэффициента в
1.9 % достаточно неплохая единица. Ясно, что до архиватора RAR и всей его братии не дотягивает, но зато и накладных расходов меньше (попробуйте дизассемблировать любой из промышленных пакеров). Во-второй части темы, трепанации подлежит привязанный к данному алгоритму распаковщик, в котором кода ещё меньше и этом его огромный плюс. По-сути любой уважающий себя вирь имеет в своём теле подобный декриптор, а значит мы должны знать "врага в лицо". На этом "занавес" - встретимся во-второй части!
Последнее редактирование модератором:
