Дизассемблиры

; // printf("Default");

push offset aDefault ; "Default" 

loc_410054:    ; CODE XREF: main_+28 j main_+2F j ...

call printf_

; Это  printf, получающий аргументы из case-обработчиков! 

add esp, 4

; Закрытие  кадра стека 

retn

main_  endp 
 

     В общем, WATCOM генерирует более хитрый, но, как ни странно, весьма наглядный и читабельный код.  

 

§2.1 Обрезка (балансировка) длинных деревьев 

     В некоторых (хотя и редких) случаях, операторы  множественного выбора содержат сотни (а то и тысячи) наборов значений, и если решать задачу сравнения "в  лоб", то высота логического дерева окажется гигантской до неприличия, а его прохождение займет весьма длительное время, что не лучшим образом скажется на производительности программы.

     Здесь возникает вопрос: чем собственно занимается оператор switch? Если отвлечься от устоявшейся идиомы "оператор SWITCH дает специальный способ выбора одного из многих вариантов, который заключается в проверке совпадения значения данного выражения с одной из заданных констант и соответствующем ветвлении", то можно сказать, что switch - оператор поиска соответствующего значения. В таком случае каноническое switch - дерево представляет собой тривиальный алгоритм последовательного поиска - самый неэффективный алгоритм из всех.

     Пусть, например, исходный текст программы  выглядел так:  
 

.

switch (a)

{

case 98 : …;

case 4  : …;

case 3  : …;

case 9  : …;

case 22 : …;

case 0  : …;

case 11 : …;

case 666: …;

case 096: …;

case 777: …;

case 7  : …;

} 

     Тогда соответствующее ему не оптимизированное логическое дерево будет достигать  в высоту одиннадцати гнезд (см. рис. 5 слева). Причем, на левой ветке корневого гнезда окажется аж десять других гнезд, а на правой - вообще ни одного (только соответствующий ему case - обработчик).

     Исправить "перекос" можно разрезав одну ветку на две и привив образовавшиеся половинки к новому гнезду, содержащему условие, определяющее в какой из веток следует искать сравниваемую переменную. Например, левая ветка может содержать гнезда с четными значениями, а правая - с нечетными. Но это плохой критерий: четных и нечетных значений редко бывает поровну и вновь образуется перекос. Гораздо надежнее поступить так: берется наименьшее из всех значений и бросается в кучу А, затем берется наибольшее из всех значений и бросается в кучу B. Так повторяется до тех пор, пока не рассортируются все, имеющиеся значения.

Поскольку оператор множественного выбора требует  уникальности каждого значения, т.е. каждое число может встречаться  в наборе (диапазоне) значений лишь однажды, легко показать, что:

     а) в обеих кучах будет содержаться  равное количество чисел (в худшем случае - в одной куче окажется на число больше);

     б) все числа кучи A меньше наименьшего из чисел кучи B. Следовательно, достаточно выполнить только одно сравнение, чтобы определить в какой из двух куч следует искать сравниваемое значения.

     Высота  нового дерева будет равна ((N+1/2)+1), где N - количество гнезд старого дерева. Действительно, ветвь дерева делится надвое и добавляется новое гнездо - отсюда и берется N/2 и +1, а (N+1) необходимо для округления результата деления в большую сторону. Т.е. если высота не оптимизированного дерева достигала 100 гнезд, то теперь она уменьшилась до 51. Затем можно разбить каждую из двух ветвей еще на две. Это уменьшит высоту дерева до 27 гнезд! Аналогично, последующее уплотнение даст 16 ' 12 ' 11 ' 9 ' 8… и все! Более плотная упаковка дерева невозможна. Восемь гнезд - это не сто! Полное прохождение оптимизированного дерева потребует менее девяти сравнений!

 

 

Рисунок 5 Логическое дерево до утрамбовки (слева) и после (справа) 

     "Трамбовать" логические деревья оператора множественного выбора умеют практически все компиляторы - даже не оптимизирующие! Это увеличивает производительность, но затрудняет анализ откомпилированной программы. Взглянув еще раз на рис. 5 - левое несбалансированное дерево наглядно и интуитивно - понятно. После же балансировки (правое дерево) совсем запутанное.

К счастью, балансировка дерева допускает эффективное  обращение. Но прежде, чем разбирать деревья введем понятие балансировочного узла. Балансировочный узел не изменяет логики работы двоичного дерева и являются факультативным узлом, единственная функция которого укорачивание длины ветвей. Балансировочный узел без потери функциональности дерева может быть замещен любой из своих ветвей. Причем каждая ветвь балансировочного узла должна содержать одно или более гнезд.

     Рассуждая от противного - все узлы логического  дерева, правая ветка которых содержит одно или более гнезд, могут быть замещены на эту самую правую ветку  без потери функциональности дерева, то данная конструкция представляет собой оператор switch. Правая ветка потому что оператор множественного выбора в "развернутом" состоянии представляет цепочку гнезд, соединенных левыми ветвями друг с другом, а на правых держащих case-обработчики, - вот и следует попытаться подцепить все правые гнезда на левую ветвь. Если это удается, значит, имеет место оператор множественного выбора, если нет – то с чем-то другим.

Рассмотрим  обращение балансировки на примере следующего дерева (см. рис. 6-а). Двигаясь от левой нижней ветви, следует продолжать взбираться на дерево до тех пор, пока не встретится узел, держащий на своей правой ветви одно или более гнезд. В данном случае - это узел (a > 5). Если данный узел заменить его гнездами (a==7) и (a == 9) функциональность дерева не нарушиться! (см. рис. 6-б). Аналогично узел (a > 10) может быть безболезненно заменен гнездами (a > 96), (a == 96), (a == 22) и (a == 11), а узел (a > 96) в свою очередь - гнездами (a == 98), (a == 666) и (a == 777). В конце -концов образуется классическое switch-дерево, в котором оператор множественного выбора распознается с первого взгляда.

 

 
 

 

Рисунок 6-а Обращение балансировки логического дерева 

 

Рисунок 6-б Обращение балансировки логического дерева 

     §2.2 Сложные случаи балансировки или оптимизирующая балансировка 

       Для уменьшения высоты "утрамбовываемого" дерева хитрые трансляторы стремятся замещать уже существующие гнезда балансировочными узлами. Рассмотрим следующий пример: (см. рис. 7). Для уменьшения высоты дерева транслятор разбивает его на две половины - в левую идут гнезда со значениями меньшие или равные единицы, а в правую - все остальные. Казалось бы, на правой ветке узла (a > 1) должно висеть гнездо (a == 2), но это не так! Здесь видно узел (a >2), к левой ветки которого прицеплен case-обработчик :2. Вполне логично - если (a > 1) и !(a > 2), то a == 2!

     Легко видеть, что узел (a > 2) жестко связан с узлом (a > 1) и работает на пару с последним. Нельзя выкинуть один из них, не нарушив работоспособности другого! Обратить балансировку дерева по описанному выше алгоритму без нарушения его функциональности невозможно! Отсюда может создаться мнение, что имеет место вовсе не оператор множественного выбора, а что-то другое.

Чтобы развеять это заблуждение придется предпринять ряд дополнительных шагов. Первое - у switch-дерева все case-обработчики  всегда находятся на правой ветви. Нужно посмотреть - можно ли трансформировать дерево так, чтобы case-обработчик 2 оказался на левой ветви балансировочного узла? Оказывается, можно: заменив (a > 2) на (a < 3) и поменяв ветви местами (другими словами выполнив инверсию). Второе - все гнезда switch-дерева содержат в себе условия равенства, - смотрим: можно ли заменить неравенство (a < 3) на аналогичное ему равенство? Да,  можно - (a == 2)!

     Вот, после всех этих преобразований, обращение  балансировки дерева удается выполнить  без труда!  

 

Рисунок 7 Хитрый случай балансировки 

§2.3 Ветвления в case-обработчиках. 

     В реальной жизни case-обработчики прямо-таки кишат ветвлениями, циклами и  прочими условными переходами всех мастей. Как следствие - логическое дерево приобретает вид ничуть не напоминающий оператор множественного выбора. Идентифицировав case-обработчики, можно бы решить эту проблему, но их нужно идентифицировать!

     За редкими исключениями, case-обработчики не содержат ветвлений относительно сравниваемой переменной. Действительно, конструкции "switch(a) …. case 666 : if (a == 666) …." или "switch(a) …. case 666 : if (a > 66) …." абсолютно лишены смысла. Таким образом, можно смело удалить из логического дерева все гнезда с условиями, не касающимися сравниваемой переменной (переменной коневого гнезда).

     Если программист в порыве собственной глупости или стремлении затруднит анализ программы "впаяет" в case-обработчики ветвления относительно сравниваемой переменной, то оказывается, это ничуть не затруднит анализ! "Впаянные" ветвления элементарно распознаются и обрезаются либо как избыточные, либо как никогда не выполняющиеся. Например, если к правой ветке гнезда (a == 3) прицепить гнездо (a > 0) - его можно удалить, как не несущее в себе никакой информации. Если же к правой ветке того же самого гнезда прицепить гнездо (a == 2) его можно удалить, как никогда не выполняющееся - если a == 3, то заведомо a != 2!  
 
 
 
 
 
 
 
 
 
 
 
 
 

Заключение

     Процесс дизассемблирования является важной частью при программировании и компиляции исходных текстов программ, особенно для начинающих программистов. Он позволяет получить исходные коды практически любого откомпилированного приложения и сделать подробный его анализ.

     Так же дизассемблирование позволяет выбрать  наиболее эффективный продукт для  компиляции и сборки приложений с целью оптимизации и быстродействия конечного программного продукта.

     В работе был произведен подробный  анализ дизассемблированного кода с  целью идентификации математических операций и операторов SWITCH - CASE – BREAK. Были рассмотрены все варианты сборки программ разными трансляторами, и установлено что наилучшим средством компилирования приложений является компилятор от фирмы Microsoft. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Список  используемой литературы 
 
 

1. Г. Шилдт Программирование на Си и С++ в Windows95

2. Р.  Ганеев Проектирование интерфейса  пользователя средствами Win32 API

3. Фролов  А. В., Фролов Г. В. Программирование  для Windows (Библиотека системного  программиста;Т.11-14)

4. "Введение в криптографию" под редакцией В.В.Ященко

5. С.Г.Баричев,  Р.Е.Серов "Основы современной криптографии"