Фундаментальные основы хакерства

       

Идентификация if – then – else


Значение каждого элемента текста определяется контекстом его употребления. Текст не описывает мир, а вступает в сложные взаимоотношения с миром.

Тезис аналитической философии

Существует два вида алгоритмов – безусловные

и условные. Порядок действий безусловного алгоритма всегда постоянен и не зависит от входных данных. Например: "a=b+c". Порядок действий условных алгоритмов, напротив, зависит от входных данных. Например: "если c не равно нулю, то: a=b/c; иначе: вывести сообщение об ошибке".

Обратите внимание на выделенные жирным шрифтом ключевые слова "если", "то" и "иначе", называемые операторами условия или условными операторами. Без них не обходится ни одна программа (вырожденные примеры наподобие "Hello, World!" – не в счет). Условные операторы – сердце любого языка программирования. Поэтому, чрезвычайно важно уметь их правильно идентифицировать.

В общем виде (не углубляясь в синтаксические подробности отдельных языков программирования) оператор условия схематично изображается так:

IF (условие) THEN { оператор1; оператор2;} ELSE { операторa; операторb;}

Задача компилятора – преобразовать эту конструкцию в последовательность машинных команд, выполняющих оператор1, оператор2, если условие

истинно и, соответственно - операторa, операторb; если оно ложно. Однако микропроцессоры серии 80x86 поддерживают весьма скромный набор условных команд, ограниченный фактически одними условными переходами (касательно исключений см. "Оптимизация ветвлений"). Программистам, знакомым лишь с IBM PC, такое ограничение не покажется чем-то неестественным, между тем, существует масса процессоров, поддерживающих префикс условного выполнения инструкции. Т.е. вместо того, чтобы писать: "TEST ECX,ECX/JNZ xxx/MOV EAX,0x666", там поступают так: "TEST ECX,ECX/IFZ MOV EAX,0x666". "IFZ" – и есть префикс условного выполнения, разрешающий выполнение следующей команды только в том случае, если установлен флаг нуля.


В этом смысле микропроцессоры 80x86 можно сравнить с ранними диалектами языка Бейсика, не разрешающими использовать в условных выражениях никакой другой оператор кроме "GOTO". Сравните:

IF A=B THEN PRINT "A=B"      10 IF A=B THEN GOTO 30

20 GOTO 40

30 PRINT "A=B"

40 ... // прочий код программы

Листинг 139 Новый диалект "Бейсика"   Старый диалект "Бейсика"



Если вы когда-нибудь программировали на старых диалектах Бейсика, то, вероятно, помните, что гораздо выгоднее выполнять GOTO если условие

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

Большинство компиляторов (даже не оптимизирующих) инвертируют истинность условия, транслируя конструкцию "IF (условие) THEN {оператор1; оператор2}" в следующий псевдокод:

IF (NOT

условие) THEN

continue


оператор1;

оператор2;

continue:



Листинг 140

Следовательно, для восстановления исходного текста программы, нам придется вновь инвертировать условие и "подцепить" блок операторов {оператор1; оператор2} к ключевому слову THEN. Т.е. если откомпилированный код выглядит так:

10 IF A<>B THEN 30

20 PRINT "A=B"

30 …// прочий код программы

Листинг 141

Можно с уверенностью утверждать, что в исходном тексте присутствовали следующие строки: "IF A=B THEN PRINT "A=B"". А если, программист, наоборот, проверял переменные A и B на неравенство, т.е. "IF A<>B THEN PRINT "A<>B""? Все равно компилятор инвертирует истинность условия и сгенерирует следующий код:

10 IF A=B THEN 30

20 PRINT "A<>B"

30 …// прочий код программы

Листинг 142

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



IF (условие) THEN

do


GOTO continue

do:

оператор1;

оператор2;

continue:



Листинг 143

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

Рассмотрим теперь как транслируется полная конструкция "IF (условие) THEN { оператор1; оператор2;} ELSE { операторa; операторb;}". Одни компиляторы поступают так:

IF (условие) THEN do_it

// Ветка ELSE

операторa;

операторb

GOTO continue

 

do_it:

//Ветка IF

оператор1;

оператор2;

continue:

А другие так:

IF (NOT условие) THEN else

//Ветка IF

оператор1;

оператор2;

GOTO continue

 

else:

// Ветка ELSE

операторa;

операторb

continue:

Листинг 144

Разница межу ними в том, что вторые инвертируют истинность условия, а первые – нет. Поэтому, не зная "нрава" компилятора, определить: как выглядел подлинный исходный текст программы – невозможно! Однако это не создает проблем, ибо условие всегда можно записать так, как это удобно. Допустим, не нравится вам конструкция "IF (c<>0) THEN a=b/c ELSE PRINT "Ошибка!"" пишите ее так: "IF (c==0) THEN PRINT "Ошибка!" ELSE a=b/c" и – ни каких гвоздей!

Типы условий: Условия делятся на простые (элементарные)

и сложные

(составные). Пример первых – "if (a==b)…", вторых "if ((a==b) && (a!=0))…". Очевидно, что любое сложное условие можно разложить на ряд простых условий. Вот с простых условий мы и начнем.

Существуют два основных типа элементарных условий: условия отношений

("меньше", "равно", "больше", "меньше или равно", "не равно", "больше или равно", соответственно обозначаемые как: "<", "==", ">", "<=", "!=", ">=") и логические условия ("И", "ИЛИ", "НЕ", "И исключающее ИЛИ", в Си-нотации соответственно обозначаемые так: "&", "|", "!", "^").


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

Если условие истинно, оно возвращает булево значение TRUE, соответственно, если ложно – FALSE. Внутренне (физическое) представление булевых переменных зависит от конкретной реализации и может быть любым. По общепринятому соглашению, FALSE равно нулю, а TRUE не равно нулю. Часто (но не всегда) TRUE равно единице, но на это нельзя полагаться! Так, код "IF ((a>b)!=0)…" абсолютно корректен, а: "IF ((a>b)==1)…" привязан к конкретной реализации и потому нежелателен.

Обратите внимание: "IF ((a>b)!=0)…" проверяет на неравенство нулю отнюдь не значения самих переменных a и b, а именно – результата их сравнения. Рассмотрим следующий пример: "IF ((666==777)==0) printf("Woozl!")" – как вы думаете, что отобразится на экране, если его запустить? Правильно – "Woozl"! Почему? Ведь ни 666, ни 777

не равно нулю! Да, но ведь 666 != 777, следовательно, условие (666==777) – ложно, следовательно равно нулю. Кстати, если записать "IF ((a=b)==0)…" получится совсем иной результат – значение переменной b будет присвоено переменной a, и потом проверено на равенство нулю.

Логические условия чаще всего используются для связывания двух или более элементарных условий отношения в составное. Например, "IF ((a==b) && (a!=0))…". При трансляции программы компилятор всегда выполняют развертку составных условий в простые. В данном случае это происходит так: "IF a==b THEN IF a=0 THEN…"

На втором этапе выполняется замена условных операторов на оператор GOTO:

IF a!=b THEN continue

IF a==0 THEN continue

…// код условия

:continue

…// прочий код

Листинг 145

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


Причем, если первое условие ложно, то следующее за ним вычислено не будет! Это дает возможность писать код наподобие следующего: "if ((filename) & (f=fopen(&filename[0],"rw")))…" – если указатель filename указывает на невыделенную область памяти (т.е. попросту говоря содержит нуль – логическое FALSE), функция fopen

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

Перейдем теперь к вопросу идентификации логических условий и анализу сложных выражений. Вернемся к уже облюбованному нами выражению "if ((a==b) && (a!=0))…" и вглядимся в результат его трансляции:

IF a!=b THEN continue  -------!

IF a==0 THEN continue ---!    !

…// код условия          !    !

:continue             <--! <---

…// прочий код

Листинг 146

Легко видеть – он выдает себя серией условных переходов к одной и той же метке, причем, - обратите внимание, - выполняется проверка на неравенство каждого из элементарных условий, а сама метка расположена позади кода условия.

Идентификация логической операции "ИЛИ" намного сложнее в силу неоднозначности ее трансляции. Рассмотрим это на примере выражения "if ((a==b) || (a!=0))…". Его можно разбить на элементарные операции и так:

IF a==b THEN do_it -----------!

IF a!=0 THEN do_it ––-!       !

goto continue –––!    !       !

:do_it           ! <--! <-----!

…// код условия  !

:continue      <-!

…// прочий код

Листинг 147

и так:

IF a==b THEN do_it  -----------!

IF a==0 THEN continue--!       !

:do_it                 ! <-----!

…// код условия        !

:continue  <-----------!

…// прочий код

Листинг 148

Первый вариант обладает весьма запоминающийся внешностью – серия проверок (без инверсии условия) на одну и ту же метку, расположенную перед кодом условия, а в конце этой серии – безусловный переход на метку, расположенную позади кода условия.



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

и AND. Кстати, о смещенных операциях – рассмотрим результат трансляции следующего выражения: "if ((a==b) || (a==c) && a(!=0))…":

IF a==b THEN check_null

IF a!=c THEN continue

check_null:

IF a==0 THEN continue

…// код условия

continue:

…// прочий код

Листинг 149

Как из непроходимого леса элементарных условий получить одно удобочитаемое составное условие? Начинаем плясать от печки, т.е. от первой операции сравнения. Смотрите, если условие a==b

окажется истинно, оно "выводит из игры" проверку условия a!=c. Такая конструкция характерна для операции OR – т.е. достаточно выполнения хотя бы одного условия из двух для "срабатывания" кода. Пишем в уме или карандашом: "if ((a==b) || …)", далее – если условие (a!=c) истинно, все дальнейшие проверки прекращаются, и происходит передача управления на метку, расположенную позади условного кода. Логично предположить, что мы имеем дело в последней операцией OR в цепочке сравнений – это ее "почерк". Значит, мы инвертируем условие выражения и продолжаем писать: "if ((a==b) || (a==c)…)". Последний бастион – проверка условия "a==0". Выполнить условный код, миновав его не удаться, - следовательно, это не OR, а AND! А AND

всегда инвертирует условие срабатывания, и поэтому, оригинальный код должен был выглядеть так: "if ((a==b) || (a==c) && (a!=0))". Ура! У нас получилось!

Впрочем, как любил поговаривать Дмитрий Николаевич, не обольщайтесь – то, что мы рассмотрели – это простейший пример. В реальной жизни оптимизирующие компиляторы такого понаворочают….

___Впрочем, для ломания головы вполне хватит и не оптимизирующих, но прежде, чем перейти к изучению конкретных реализаций, рассмотрим на последок две "редкоземельные" операции NOT и XOR.



__NOT – одноместная операция, поэтому, она не может использоваться для связывания, однако,

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

Выход – в использовании двухуровневой системы ретрансляции. На первом этапе элементарные условия преобразуются к некоторой промежуточной форме записи, наглядно и непротиворечиво отображающей взаимосвязь элементарных операций. Затем осуществляется окончательная трансляция в любую подходящую нотацию (например, Си, Бейсик или Pascal).

Единственная проблема – выбрать удачную промежуточную форму. Существует множество решений, но в книге по соображениям экономии бумажного пространства, мы рассмотрим только одно – деревья.

Изобразим каждое элементарное условие в виде узла, с двумя ветвями, соответствующим состояниям: условие истинно и условие ложно. Для наглядности обозначим "ложь" равнобедренным треугольником, а "истину" – квадратом и условимся всегда располагать ложь на левой, а истину на правой ветке. Получившуюся конструкцию назовем "гнездом" (nest).



Рисунок 22 0х015 Схематическое представление гнезда (nest).

Гнезда могут объединяться в деревья, соединясь узлами с ветками другого узла. Причем, каждый узел может соединяться только с одним гнездом, но всякое гнездо может соединяться с несколькими узлами. Непонятно? Не волнуйтесь, сейчас со всем этим мы самым внимательным образом разберемся.

Рассмотрим объединение двух элементарных условий логической операцией "AND" на примере выражения "((a==b) && (a!=0))".


Извлекаем первое слева условие (a==b), "усаживаем" его в гнездо с двумя ветвями: левая соответствует случаю, когда a!=b

(т.е. условие a==b – ложно), а правая, соответственно, – наоборот. Затем, то же самое делаем и со вторым условием (a!=0). У нас получаются два очень симпатичных гнездышка, – остается лишь связать их меж собой операцией логического "AND". Как известно, "AND" выполняет второе условие только в том случае, если истинно первое. Значит, гнездо (a!=0) следует прицепить к правой ветке гнезда (a==b). Тогда – правая ветка гнезда (a!=0) будет соответствовать истинности выражения "((a==b) && (a!=0))", а обе левые ветки – его ложности. Обозначим первую ситуацию меткой "do_it", а вторую – "continue". В результате дерево должно принять вид, изображенный на рис. 23.

Для наглядности отметим маршрут из вершины дерева к метке "do_it" жирной красной стрелкой. Как видите, в пункт "do_it" можно попасть только одним путем. Вот так графически выглядит операция "AND".



Рисунок 23 0х016 Графическое представление операции AND в виде двоичного дерева. Обратите внимание – в пункт do_it можно попасть только одним путем!

Перейдем теперь к операции логического "OR". Рассмотрим конструкцию "((a==b) || (a!=0))". Если условие "(a==b)" истинно, то и все выражение считается истинным. Следовательно, правая ветка гнезда "(a==b)" связана с меткой "do_it". Если же условие же "(a==b)" ложно, то выполняется проверка следующего условия. Значит, левая ветка гнезда "(a==b)" связана с гнездом "(a!=b)". Очевидно, если условие "(a!=b)" истинно, то истинно и все выражение "((a==b) || (a!=0))", напротив, если условие "(a!=b)" ложно, то ложно и все выражение, т.к. проверка условия "(a!=b)" выполняется только в том случае, если условие "(a==b)" ложно.


Отсюда мы заключаем, что левая ветка гнезда "(a!=b)" связана с меткой "continue", а правая – с "do_it". (см. рис. 24). Обратите внимание – в пункт "do_it" можно попасть двумя различными путями! Вот так графически выглядит операция "OR".



Рисунок 24 0х017 Графическое представление операции OR в виде двоичного дерева. Обратите внимание – в пункт do_it можно попасть двумя различными путями!

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

IF a==b THEN check_null

IF a!=c THEN continue

check_null:

IF a==0 THEN continue

…// код условия

continue:

…// прочий код

Листинг 150

Извлекаем условие (a==b) и сажаем его в "гнездо", - смотрим: если оно ложно, то выполняется проверка (a!=c), значит, гнездо (a!=c) связано с левой веткой гнезда (a==b). Если же условие (a==b) истинно, то управление передается метке check_null, проверяющей истинность условия (a==0), следовательно, гнездо (a==0) связано с правой веткой гнезда (a==b). В свою очередь, если условие (a!=с) истинно, управление получает метка "continue", в противном случае – "check_null". Значит, гнездо (a!=0) связано одновременно и с правой веткой гнезда (a==b) и с левой веткой гнезда (a!=c).

Конечно, это проще рисовать, чем описывать! Если вы все правильно зарисовали, у вас должно получится дерево очень похожее на изображенное на рисунке 25.

Смотрите: к гнезду "(a==0)" можно попасть двумя путями – либо через гнездо (a==b), либо через цепочку двух гнезд (a==b) à

(a!=c). Следовательно, эти гнезда связаны операцией OR. Записываем: "if ( (a==b) || !(a!=c)….)". Откуда взялся NOT? Так ведь гнездо (a==0) связано с левой веткой гнезда (a!=с), т.е. проверяется ложность его истинности! (Кстати, "ложность истинности" – очень хорошо звучит).


Избавляемся от NOT, инвертируя условие: "if ( (a==b) || (a==c)….)…". Далее – из гнезда (a==0) до пункта do_it

можно добраться только одним путем, значит, оно связано операцией AND. Записываем: "if (((a==b) || (a==c)) && !(a==0))…". Теперь избавляемся от лишних скобок и операции NOT. В результате получается: "if ((a==b) || (a==c) && (a!=0)) {// Код условия}"

Не правда ли все просто? Причем вовсе необязательно строить деревья вручную, - при желании можно написать программу, берущую эту работу на себя.



Рисунок 25 0х018 Графическое представление сложного выражения

Исследование конкретных реализаций.

Прежде чем приступать к отображению конструкции "IF (сложное условие) THEN

оператор1:оперратор2 ELSE

оператора:операторb" на машинный язык, вспомним, что, во-первых, агрегат "IF – THEN – ELSE" можно выразить через "IF – THEN", во-вторых, "THEN оператор1:оперратор2" можно выразить через "THEN GOTO do_it", в-третьих, любое сложное условие можно свести к последовательности элементарных условий отношения. Таким образом, на низком уровне мы будем иметь дело лишь с конструкциями "IF (простое условие отношения) THEN GOTO do_it", а уже из них, как из кирпичиков, можно сложить что угодно.

Итак, условия отношения, или другими словами, результат операции сравнения двух чисел. В микропроцессорах Intel 80x86 сравнение целочисленных значений осуществляется командой CMP, а вещественных – одной из следующих инструкций сопроцессора: FCOM, FCOMP, FCOMPP, FCOMI, FCOMIP, FUCOMI, FUCOMIP. Предполагается, что читатель уже знаком с языком ассемблера, поэтому не будем подробно останавливаться на этих инструкциях и рассмотрим их лишь вкратце.

::CMP. Команда CMP эквивалентна операции целочисленного вычитания SUB, за одним исключением – в отличие от SUB, CMP

не изменяет операндов, а воздействует лишь на флаги основного процессора: флаг нуля, флаг переноса, флаг знака



и флаг переполнения.

Флаг нуля

устанавливается в единицу, если результат вычитания равен нулю, т.е. операнды равны друг другу.

Флаг переноса

устанавливается в единицу, если в процессе вычитания произошел заем из старшего бита уменьшаемого операнда, т.е. уменьшаемое меньше вычитаемого.

Флаг знака равен старшему – знаковому – биту результата вычислений, т.е. результат вычислений – отрицательное число.

Флаг переполнения устанавливается в единицу, если в результате вычислений "залез" в старший бит, приводя к потере знака числа.

Для проверки состояния флагов существует множество команд условных переходов, выполняющихся в случае, если определенный флаг (набор флагов) установлен (сброшен). Инструкции, использующиеся для анализа результата сравнения целых чисел, перечислены в таблице 16.

В общем случае конструкция "IF (элементарное условие отношения) THEN do_it" транслируется в следующие команды процессора:

CMP   A,B

Jxx   do_it

continue:

__Однако шаблон "CMP/Jxx" не

Между инструкциями "CMP" и "Jxx" могут находиться и другие команды, не изменяющие флагов процессора, например "MOV", "LEA".

__синонимы

условие

состояние флагов

инструкция

Zero flag

Carry Flag

Sing Flag

a == b

1

?

?

JZ

JE

a != b

0

?

?

JNZ

JNE

a < b

беззнаковое

?

1

?

JC

JB

JNAE

 
знаковое

?

?

!=OF

JL

JNGE

a > b

беззнаковое

0

0

?

JA

JNBE

знаковое

0

?

==OF

JG

JNLE

a >=b

беззнаковое

?

0

?

JAE

JNB

JNC

знаковое

?

?

==OF

JGE

JNL

a <= b

беззнаковое

(ZF == 1) || (CF == 1)

?

JBE

JNA

знаковое

1

?

!=OF

JLE

JNG

Таблица 16 Соответствие операций отношения командам процессора



::сравнение вещественных чисел. Команды сравнения вещественных чисел FCOMxx

(см. таблицу 18) в отличие от команд целочисленного сравнения воздействуют на регистры сопроцессора, а не основного процессора. На первый взгляд – логично, но весь камень преткновения в том, что инструкций условного перехода, управляемых флагами сопроцессора, не существует! К тому же, флаги сопроцессора непосредственно недоступны, - чтобы прочитать их статус необходимо выгрузить регистр состояния сопроцессора SW

в память или регистр общего назначения основного процессора.

Хуже всего – анализировать флаги вручную! Если при сравнении целых чисел можно и не задумываться: какими именно флагами управляется условный переход, достаточно написать, скажем: "CMP A,B; JGE do_it". ("Jump [if] Great [or] Equal" – прыжок, если A

больше или равно B), то теперь этот номер не пройдет! Правда, можно схитрить и скопировать флаги сопроцессора в регистр флагов основного процессора, а затем использовать "родные" инструкции условного перехода из серии Jxx.

Конечно, непосредственно скопировать флаги из сопроцессора в основной процессор нельзя и эту операцию приходится осуществлять в два этапа. Сначала флаги FPU выгружать в память или регистр общего назначения, а уже оттуда заталкивать в регистр флагов CPU. Непосредственно модифицировать регистр флагов CPU умеет только одна команда – POPF. Остается только выяснить – каким флагам сопроцессора, какие флаги процессора соответствуют. И вот что удивительно – флаги 8й, 10й и 14й сопроцессора совпадают с 0ым, 2ым и 6ым флагами процессора – CF, PF и ZF соответственно (см. таблицу 17). То есть – старшей байт регистра флагов сопроцессора можно безо всяких преобразований затолкать в младший байт регистра флагов процессора и это будет работать, но… при этом исказятся 1й, 3й и 5й биты флагов CPU, никак не используемые в текущих версиях процессора, но зарезервированные на будущее. Менять значение зарезервированных битов нельзя! Кто знает, вдруг завтра один из них будут отвечать за самоуничтожение процессора? Шутка, конечно, но в ней есть своя доля истины.



К счастью, никаких сложных манипуляций нам проделывать не придется – разработчики процессора предусмотрели специальную команду – SAHF, копирующую 8й, 10й, 12й, 14й и 15й бит регистра AX в 0й, 2й, 4й, 6й и 7й бит регистра флагов CPU соответственно. Сверяясь по таблице 17 мы видим, что 7й бит регистра флагов CPU содержит флаг знака, а соответствующий ему флаг FPU – признак занятости сопроцессора!

Отсюда следует, что для анализа результата сравнения вещественных чисел использовать знаковые условные переходы(JL, JG, JLE, JNL, JNLE, JGE, JNGE) нельзя! Они работают с флагами знака и переполнения, – естественно, если вместо флага знака им подсовывают флаг занятости сопроцессора, а флаг переполнения оставляют в "подвешенном" состоянии, условный переход будет срабатывать не так, как вам бы этого хотелось! Применяйте лишь беззнаковые инструкции перехода – JE, JB, JA

и др. (см. таблицу 16)

Разумеется, это не означает, что сравнивать знаковые вещественные значения нельзя, - можно, еще как! Но для анализа результатов сравнения обязательно всегда использовать только беззнаковые условные переходы!

CPU

7

6

5

4

3

2

1

0

SF

ZF

--

AF

--

PC

--

CF

FPU

15

14

13

12

11

10

9

8

Busy!

C3(ZF)

TOP

C2(PF)

C1

C0(CF)

Таблица 17 Соответствие флагов CPU и FPU

Таким образом, вещественная конструкция "IF (элементарное условие отношения) THEN do_it" транслируется в одну из двух следующих последовательностей инструкций процессора:

fld         [a]               fld         [a]

fcomp       [b]               fcomp       [b]

fnstsw      ax                fnstsw      ax

sahf                         test        ah, bit_mask

jxx         do_it             jnz         do_it

Листинг 151

Первый вариант более нагляден, зато второй работает быстрее. Однако, такой код (из всех известных мне компиляторов) умеет генерировать один лишь Microsoft Visual C++.


Borland C++ и хваленый WATCOM C испытывают неопределимую тягу к инструкции SAHF, чем вызывают небольшие тормоза, но чрезвычайно упрощают анализ кода, - ибо, встретив команду наподобие JNA, мы и спросонок скажем, что переход выполняется когда a <= b, а вот проверка битвой маски "TEST AH, 0x41/JNZ do_it" заставит нас крепко задуматься или машинально потянуться к справочнику за разъяснениями (см. таблицу 16)

Команды семейства FUCOMIxx в этом смысле гораздо удобнее в обращении, т.к. возвращают результат сравнения непосредственно в регистры основного процессора, но – увы – их "понимает" только Pentium Pro, а в более ранних микропроцессорах они отсутствуют. Поэтому, вряд ли читателю доведется встретиться с ними в реальных программах, так что не имеет никакого смысла останавливаться на этом вопросе. Во всяком случае, всегда можно обратится к странице 3-112 руководства "Instruction Set Reference", где эти команды подробно описаны.

инструкция

назначение

результат

FCOM

Сравнивает вещественное значение, находящееся на вершине стека сопроцессора, с операндом, находящимся в памяти или стеке FPU

флаги FPU

FCOMP

То же самое, что и FCOM, но с выталкиванием вещественного значения с вершины стека

FCOMPP

Сравнивает два вещественных значения, лежащих на вершине стека сопроцессора, затем выталкивает их из стека

FCOMI

Сравнивает вещественное значение, находящееся на вершине стека сопроцессора с другим вещественным значением, находящимся в стеке FPU

флаги CPU

FCOMIP

Сравнивает вещественное значение, находящееся на вершине стека сопроцессора с другим вещественным значением, находящимся в стеке FPU, затем выталкивает верхнее значение из стека

FUCOMI

Неупорядоченно сравнивает вещественное значение, находящееся на вершине стека сопроцессора с другим вещественным значением, находящимся в стеке FPU

FUCOMIP

Неупорядоченно сравнивает вещественное значение, находящееся на вершине стека сопроцессора с другим вещественным значением, находящимся в стеке FPU, затем выталкивает верхнее значение из стека

<


Таблица 18 Команды сравнения вещественных значений

флаги FPU

назначение

битовая маска

OE

Флаг переполнения

Overfull Flag

#0x0008

C0

Флаг переноса

Carry Flag

#0x0100

C1

---

#0x0200

C2

Флаг четности

Partite Flag

#0x0400

C3

Флаг нуля

Zero Flag

#0x4000

Таблица 19 Назначение и битовые маски флагов сопроцессора

отношение

состояние флагов FPU

SAHF

битовая маска

a<b

C0 == 1

JB

#0x0100 == 1

a>b

C0 == 0

C3 == 0

JNBE

#0x4100 == 0

a==b

C3 == 1

JZ

#0x4000 == 1

a!=b

C3 == 0

JNZ

#0x4000 == 0

a>=b

C0 == 0

JNB

#0x0100 == 0

a<=b

C0 == 1

C3 === 1

JNA

#0x4100 == 1

Таблица 20 Состояние регистров флагов для различных операций отношения. 'a' – левый, а 'b' правый операнд команды сравнения вещественных значений

компилятор

алгоритм анализа флагов FPU

Borland C++

копирует флаги сопроцессора в регистр флагов основного процессора

Microsoft Visual C++

тест битовой маски

WATCOM C

копирует флаги сопроцессора в регистр флагов основного процессора

Free Pascal

копирует флаги сопроцессора в регистр флагов основного процессора

Таблица 21 "Характер" некоторых компиляторов

Условные команды булевой установки. Начиная с 80386 чипа, язык микропроцессоров Intel обогатился командой условной установки байта – SETxx, устанавливающей свой единственный операнд в единицу (булево TRUE), если условие "xx" равно и, соответственно, сбрасывающую его в нуль (булево FALSE), если условие "xx" – ложно.

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

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


там же "Булевы сравнения" и "Идентификация условного оператора (условие)?do_it:continue").

команда

отношение

условие

SETA

SETNBE

a>b

беззнаковое

CF

== 0 && ZF

== 0

SETG

SETNLE

знаковое

ZF == 0 && SF == OF

SETAE

SETNC

SETNB

a>=b

беззнаковое

CF == 0

SETGE

SETNL

знаковое

SF

== OF

SETB

SETC

SETNAE

a<b

беззнаковое

CF == 1

SETL

SETNGE

знаковое

SF

!= OF

SETBE

SETNA

a<=b

беззнаковое

CF

== 1 || ZF

== 1

SETLE

SETNG

знаковое

ZF == 1 || SF != OF

SETE

SETZ

a==b

–––

ZF == 1

SETNE

SETNZ

a!=0

–––

ZF

== 0

Таблица 22 Условные команды булевой установки

Прочие условные команды. Микропроцессоры серии 80x86 поддерживают множество условных команд, в общем случае не отображающихся на операции отношения, а потому и редко использующиеся компиляторами (можно даже сказать – вообще не использующиеся), но зато часто встречающиеся в ассемблерных вставках. Словом, они заслуживают хотя бы беглого упоминания.

::Команды условного перехода.

Помимо описанных в таблице 16, существует еще восемь других условных переходов – JCXZ, JECXZ, JO, JNO, JP

(он же JPE), JNP

(он же JPO), JS

и JNS. Из них только JCXZ и JECXZ имеют непосредственное отношение к операциям сравнения. Оптимизирующие компиляторы могут заменять конструкцию "CMP [E]CX, 0\JZ do_it" на более короткий эквивалент "J[E]CX do_it", однако, чаще всего они (в силу ограниченности интеллекта и лени своих разработчиков) этого не делают.

Условные переходы JO и JNS

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

Условные переходы JS и JNS

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



Условные переходы JP и JNP

вообще практически не используются, ну разве что в экзотичных ассемблерных вставках.

команда

переход, если…

флаги

JCXZ

регистр CX равен нулю

CX  == 0

JECXZ

регистр ECX равен нулю

ECX == 0

JO

переполнение

OF  == 1

JNO

нет переполнения

OF  == 0

JP

JPE

число бит младшего байта результата четно

PF  == 1

JNP

JPO

число бит младшего байта результата нечетно

PF  == 0

JS

знаковый бит установлен

SF  == 1

JNS

знаковый бит сброшен

SF  == 0

Таблица 23 Вспомогательные условные переходы

::Команды условной пересылки.

Старшие процессоры семейства Pentium (Pentium Pro, Pentium II, CLERION) поддерживают команду условной пересылки CMOVxx, пересылающей значение из источника в приемник, если условие xx – истинно. Это позволяет писать намного более эффективный код, не содержащий ветвлений и укладывающийся в меньшее число инструкций.

Рассмотрим конструкцию "IF a<b THEN a=b". Сравните: как она транслируется с использованием условных переходов (1) и команды условной пересылки (2).

CMP A,B                      CMP A, B

JAE continue:                CMOVB A, B

MOV A,B

continue:

1)                           2)

Листинг 152

К сожалению, ни один из известных мне компиляторов на момент написания этих строк, никогда не использовал CMOVxx при генерации кода, однако, выигрыш от нее настолько очевиден, что появления усовершенствованных оптимизирующих компиляторов следует ожидать в самом ближайшем будущем. Вот почему эта команда включена в настоящий обзор. В таблице 24 дана ее краткое, но вполне достаточное для дизассемблирования программ, описание. За более подробными разъяснениями обращайтесь к странице 3-59 справочного руководства "Instruction Set Reference" от Intel.

команда

отношение

условие

CMOVA

CMOVNBE

a>b

беззнаковое

CF

== 0 && ZF

== 0

CMOVG

CMOVNLE

знаковое

ZF == 0 && SF == OF

CMOVAE

CMOVNC

CMOVNB

a>=b

беззнаковое

CF == 0

CMOVGE

CMOVNL

знаковое

SF

== OF

CMOVB

CMOVC

CMOVNAE

a<b

беззнаковое

CF == 1

CMOVL

CMOVNGE

знаковое

SF

!= OF

CMOVBE

CMOVNA

a<=b

беззнаковое

CF

== 1 || ZF

== 1

CMOVLE

CMOVNG

знаковое

ZF == 1 || SF != OF

CMOVE

CMOVZ

a==b

–––

ZF == 1

CMOVNE

CMOVNZ

a!=0

–––

ZF == 0

<


Таблица 24 Основные команды условной пересылки

Булевы сравнения.

Логической лжи (FALSE) соответствует значение ноль, а логической истине (TRUE) – любое ненулевое значение. Таким образом, булевы отношения сводятся к операции сравнения значения переменной с нулем. Конструкция "IF (a) THEN do_it" транслируется в "IF (a!=0) THEN do_it".

Практически все компиляторы заменяют инструкцию "CMP A, 0" более короткой командой "TEST A,A" или "OR A,A". Во всех случаях, если A==0, устанавливается флаг нуля и, соответственно, наоборот.

Поэтому, встретив к дизассемблером тексте конструкцию a la "TEST EAX, EAX\ JZ do_it" можно с уверенностью утверждать, что мы имеем дело с булевым сравнением.

Идентификация условного оператора "(условие)?do_it:continue"

Конструкция "a=(условие)?do_it:continue" языка Си в общем случае транслируется так: "IF (условие) THEN a=do_it ELSE a=continue", однако результат компиляции обоих конструкций вопреки распространенному мнению, не всегда идентичен.

В силу ряда обстоятельств оператор "?" значительно легче поддается оптимизации, чем ветвление "IF – THEN – ELSE". Покажем это на следующем примере:

main()

{

int a;       // Переременная специально не иницилизирована

int b;       // чтобы компилятор не заменил ее константой

a=(a>0)?1:-1; // Условный оператор

if (b>0)            // Ветвление

b=1;

else

b=-1;

return a+b;

}

Листинг 153

Если пропустить эту программу сквозь компилятор Microsoft Visual C++, на выходе мы получим такой код:

push   ebp

mov    ebp, esp

; Открываем кадр стека

sub    esp, 8

; Резервируем место для локальных переменных

; // Условный оператор ?

; Начало условного оператора ?

xor    eax, eax

; Обнуляем EAX

cmp    [ebp+var_a], 0

; Сравниваем переменную a с нулем

setle  al

; Поместить в al значение 0x1, если var_a



<= 0

; Соответственно, поместить в al

значение 0, если var_a>0

dec    eax

; Уменьшить EAX на единицу

; Теперь,    если var_a

> 0, то EAX

:= -1

;            если var_a <=0, то

EAX := 0

and    eax, 2

; Сбросить все биты, кроме второго слева, считая от одного

; Теперь,    если var_a

> 0, то EAX

:= 2

;            если var_a <=0, то

EAX := 0

add    eax, 0FFFFFFFFh

; Отнять от EAX 0x1

; Теперь,    если var_a

> 0, то EAX

:= 1

;            если var_a <=0, то

EAX := -1

mov    [ebp+var_a], eax

; Записать результат в переменную var_a

; Конец оператора ?

; Обратите внимание: для трансляции условного оператора не потребовалось ни

; одного условного перехода, - компилятор сумел обойтись без ветвлений!

; // Ветвление

; Начало ветвления IF – THEN - ELSE

cmp    [ebp+var_b], 0

; Сравнение переменной var_b

с нулем

jle    short else

; Переход, если var_b <= 0

; Ветка "var_b > 0"

mov    [ebp+var_b], 1

; Записываем в переменную var_b

значение 1

jmp    short continue

; Переход

к метке continue

; Ветка "var_b > 0"

else:                             ; CODE XREF: _main+1Dj

mov    [ebp+var_b], 0FFFFFFFFh

; Записываем в переменную var_b

значение -1

continue:                               ; CODE XREF: _main+26j

; Конец

ветвления IF-THEN-ELSE

; Обратите внимание – представление ветвления "IF-THEN-ELSE" намного компактнее

; условного оператора "?", однако, содержит в себе условные переходы, ощутимо

; снижающие быстродействие программы

mov    eax, [ebp+var_a]

; Загружаем в EAX значение переменной var_a

add    eax, [ebp+var_b]

; Складываем значение переменной var_a со значением переменной var_b

; и помещаем результат в EAX

mov    esp, ebp

pop    ebp

; Закрываем кадр стека

retn

Листинг 154

Таким образом, мы видим, что нельзя апории утверждать, будто бы результат трансляции условного оператора "?" всегда эквивалентен результату трансляции конструкции "IF-THEN-ELSE".


Однако тот же Microsoft Visual C++ в режиме агрессивной оптимизации в обоих случаях генерирует идентичный код. Смотрите:

_main        proc near

push   ecx

; Резервируем место для локальных переменных a и b

; Поскольку, они никогда не используются вместе, а только поочередно,

; компилятор помещает их в одну ячейку памяти

mov    edx, [esp+0]                            ; команда N1 оператора ?

; Загрузка в EDX значения переменной a

xor    eax, eax                                ; команда N2 оператора ?

; Обнуляем EAX

; Поскольку, команда setle al изменяет содержимое одного лишь al, и не трогает

; остальную часть регистра, нам приходится очищать его самостоятельно

test   edx, edx                                ; команда N3 оператора ?

; Проверка переменной a на равенство нулю

mov    edx, [esp+0]                            ; команда N1 ветвления IF

; Загрузка в EDX значения переменной b

setle  al                                      ; команда N4 оператора ?

; Поместить в al значение 0x1, если a <= 0

; Соответственно, поместить в al

значение 0, если a>0

dec    eax                                     ; команда N5 оператора ?

; Уменьшить EAX на единицу

; Теперь,    если a > 0, то EAX := -1

;            если a <=0, то EAX := 0

xor    ecx, ecx                                ; команда N2 ветвления IF

; Обнулить ECX

and    eax, 2                                  ; команда N6 оператора ?

; Сбросить все биты, кроме второго слева, считая от одного

; Теперь,    если a > 0, то EAX := 2

;            если a <=0, то EAX := 0

dec    eax                                     ; команда N7 оператора ?

; Уменьшить EAX на единицу

; Теперь,    если a > 0, то EAX := 1

;            если a <=0, то EAX := -1

test   edx, edx                                ; команда N3 ветвления IF

; Проверка переменной b на равенство нулю

setle  cl                                      ; команда N4 ветвления IF



; Поместить в сl значение 0x1, если b <= 0

; Соответственно, поместить в cl

значение 0, если b>0

dec    ecx                                     ; команда N5 ветвления IF

; Уменьшить ECX на единицу

; Теперь,    если b > 0, то ECX := -1

;            если b <=0, то ECX := 0

and    ecx, 2                                  ; команда N6 ветвления IF

; Сбросить все биты, кроме второго слева, считая от одного

; Теперь,    если b > 0, то ECX := 2

;            если b <=0, то ECX := 0

dec    ecx                                     ; команда N7 ветвления IF

; Уменьшить ECX на единицу

; Теперь,    если b > 0, то ECX := -1

;            если b <=0, то ECX := 0

add    eax, ecx

; Сложить переменную a с переменной b

pop    ecx

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

retn

_main        endp

Листинг 155

Компилятор некоторым образом перемешал команды, относящиеся к условному оператору "?", с командами ветвления "IF-THEN-ELSE" (это было сделано для лучшего спаривания инструкций), однако, если их сравнить, то выяснится – реализации обеих конструкций абсолютно идентичны друг другу!

Однако с точки зрения языка условный оператор "?" выгодно отличается от ветвления тем, что может непосредственно использоваться в выражениях, например:

main()

{

int a;

printf("Hello, %s\n", (a>0)?"Sailor":"World!");

}

Листинг 156

Попробуйте так же компактно реализовать это с помощью ветвлений! Но на самом деле, это удобство лишь внешнее, а компилятор транслирует приведенный пример так:

main()

{

int a;

char *p;

static char s0[]="Sailor";

static char s1[]="World";

if (a>0) p=s0; else p=s1;

printf("Hello, %s\n", p);

}

Листинг 157

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



Например, маловероятно, чтобы программист строил свой листинг, как показано в последнем примере. Зачем вводить статические переменные и сложным образом манипулировать с указателем, когда проще поступить использовать условный оператор вместо ветвления?

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

Идентификация типов. Условные команды – ключ к идентификации типов. Поскольку, анализ результата сравнения знаковых и беззнаковых переменных осуществляется различными группами инструкций, можно уверенно и однозначно отличить signed int от unsigned int.

Вообще же, идентификация типов – тема отдельного разговора, поэтому не будет отклоняться в сторону, а рассмотрим ее чуточку позже в одноименной главе.

16 разрядный режим.
Одна из неприятных особенностей 16-разрядного режима – ограниченная "дальнобойность" команд условного перехода. Разработчики микропроцессора в стремлении добиться высокой компактности кода, отвели на целевой адрес всего один байт, ограничив тем самым длину прыжка интервалом в 255 байт. Это, так называемый, короткий

(short) переход, адресуемый относительным знаковым смещением, отсчитываемым от начала следующий за инструкцией перехода командой (см. рис 26). Такая схема адресации ограничивает длину прыжка "вперед" (т.е. "вниз") всего 128 байтами, а "назад" (т.е. "вверх") и того меньше – 127! (Прыжок вперед короче потому, что ему требуется "пересечь" и саму команду перехода). Этих ограничений лишен ближний

(near) безусловный переход, адресуемый двумя байтами и действующий в пределах всего сегмента.



Рисунок 26 0х019 Внутреннее представление короткого (short) перехода

Короткие переходы усложняют трансляцию ветвлений – ведь не всякий целевой адрес находится в пределах 128 байт! Существует множество путей обойти это ограничение.


Наиболее популярен следующий примем: если транслятор видит, что целевой адрес выходит за пределы досягаемости условного перехода, он инвертирует условие срабатывания и совершает короткий (short) переход на метку continue, а на do_it передает управление ближним (near) переходом, действующим в пределах одного сегмента (см. рис. 27)



Рисунок 27 0х01A Трансляция коротких переходов

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

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

Листинги примеров. А теперь для лучшего уяснения материала, рассмотренного в этой главе, давайте рассмотрим несколько "живых" примеров, откомпилированных различными компиляторами. Начнем с исследования элементарных целочисленных отношений:

#include <stdio.h>

main()

{

int a; int b;

if (a<b) printf("a<b");

if (a>b) printf("a>b");

if (a==b) printf("a==b");

if (a!=b) printf("a!=b");

if (a>=b) printf("a>=b");

if (a<=b) printf("a<=b");

}

Листинг 158

Результат компиляции этого примера компилятором Microsoft Visual C+ должен выглядеть так:

main         proc near           ; CODE XREF: start+AFp

var_b        = dword      ptr -8

var_a        = dword      ptr -4

push   ebp

mov    ebp, esp

; Открываем кадр стека

sub    esp, 8

; Резервируем память для локальных переменных var_a и var_b

mov    eax, [ebp+var_a]

; Загружаем в EAX значение переменной var_a

cmp    eax, [ebp+var_b]

; Сравниваем значение переменной var_a со значением переменной var_b



jge    short loc_40101B

; Если var_a

>= var_b то переход на continue иначе – печать строки

; Обратите внимание, что оригинальный код выглядел так:

; if (a<b) printf("a<b");

; Т.е. условие отношения было инвентировано компилятором!

; Знаковая операция JGE говорит о том, что и сравнивыемые переменные

; var_a и var_b

– так же знаковые

; // ВЕТКА DO_IT

push   offset aAB_4 ; "a<b"

call   _printf

add    esp, 4

; Печать строки "a<b"

; // ВЕТКА CONTINUE

loc_40101B:                       ; CODE XREF: main+Cj

mov    ecx, [ebp+var_a]

; Загружаем в ECX значение переменной var_a

cmp    ecx, [ebp+var_b]

; Сравниваем значение переменной var_a с переменной var_b

jle    short loc_401030

; Переход, если var_a

<= var_b, иначе – печать строки

; Следовательно, строка печатается, когда !(var_a <= var_b), или

; var_a > var_b. Тогда исходный код программы должен выглядеть так:

; if (a>b) printf("a>b");

push   offset aAB_3 ; "a>b"

call   _printf

add    esp, 4

;

loc_401030:                       ; CODE XREF: main+21j

mov    edx, [ebp+var_a]

; Загружаем в EDX значение переменной var_a

cmp    edx, [ebp+var_b]

; Сравниваем значение переменной var_a с переменной var_b

jnz    short loc_401045

; Переход если var_a!=var_b, иначе печать строки

; Следовательно, оригинальный код программы выглядел так:

; if (a==b) printf("a==b");

push   offset aAB   ; "a==b"

call   _printf

add    esp, 4

loc_401045:                       ; CODE XREF: main+36j

mov    eax, [ebp+var_a]

; Загружаем в EAX значение переменной var_a

cmp    eax, [ebp+var_b]

; Сравниваем значение переменной var_a со значением переменной var_b

jz     short loc_40105A

; Переход, если var_a==var_b, иначе – печать строки.

; Следовательно, оригинальный код программы выглядел так:

; if (a!==b) printf("a!=b");



push   offset aAB_0 ; "a!=b"

call   _printf

add    esp, 4

loc_40105A:                       ; CODE XREF: main+4Bj

mov    ecx, [ebp+var_a]

; Загружаем в ECX значение переменной var_a

cmp    ecx, [ebp+var_b]

; Сравниваем значение переменной var_a с переменной var_b

jl     short loc_40106F

; Переход, если var_a

< var_b, иначе – печать строки

; Следовательно, оригинальный код программы выглядел так:

; if (a>=b) printf("a>=b");

push   offset aAB_1 ; "a>=b"

call   _printf

add    esp, 4

loc_40106F:                       ; CODE XREF: main+60j

mov    edx, [ebp+var_a]

; Загружаем в EDX значение переменной var_a

cmp    edx, [ebp+var_b]

; Сравниваем значение переменной var_a с переменной var_b

jg     short loc_401084

; Переход если var_a>var_b, иначе печать строки

; Следовательно, оригинальный код программы выглядел так:

; if (a<=b) printf("a<=b");

push   offset aAB_2 ; "a<=b"

call   _printf

add    esp, 4

loc_401084:                       ; CODE XREF: main+75j

mov    esp, ebp

pop    ebp

; Закрываем кадр стека

retn

main         endp

Листинг 159

А теперь сравним этот, 32-разрядный код, с 16- разрядным кодом, сгенерированном компилятором Microsoft C++ 7.0 (ниже, для экономии места приведен лишь фрагмент):

mov    ax, [bp+var_a]

; Загрузить в AX

значение переменной var_a

cmp    [bp+var_b], ax

; Сравнить значение переменной var_a

со значением переменной var_b

jl     loc_10046

; Переход на код печати строки, если var_a

< var_b

jmp    loc_10050

; Безусловный переход на continue

; Смотрите! Компилятор, не будучи уверен, что "дальнобойности" короткого

; условного перехода хватит для достижения метки continue, вместо этого

; прыгнул на метку do_it, расположенную неподалеку – в гарантированной

; досягаемости, а передачу управления на continue взял на себя



; безусловный переход

; Таким образом, инверсия истинности условия сравнения имело место дважды

; первый раз при трансляции условия отношения, второй раз – при генерации

; машинного кода. А NOT

на NOT

можно сократить!

; Следовательно, оригинальный код выглядел так:

; if (a<b) printf("a<b");

loc_10046:                        ; CODE XREF: _main+11j

mov    ax, offset aAB      ; "a<b"

push   ax

call   _printf

add    sp, 2

loc_10050:                        ; CODE XREF: _main+13j

; // прочий код

Листинг 160

А теперь заменим тип сравниваемых переменных с int на float и посмотрим, как это повлияет на сгенерированный код. Результат компиляции Microsoft Visual C++ должен выглядеть так (ниже приведен лишь фрагмент):

fld    [ebp+var_a]

; Загрузка значения вещественной переменной var_a на вершину стека сопроцессора

fcomp  [ebp+var_b]

; Сравнение значение переменной var_a с переменной var_b

; с сохранением результата сравнения во флагах сопроцессора

fnstsw ax

; Скопировать регистр флагов сопроцессора в регистр AX

test   ah, 1

; Нулевой бит регистра AH установлен?

; Соответственно: восьмой бит регистра флагов сопроцессора установлен?

; А что у нас храниться в восьмом бите?

; Ага, восьмой бит содержит флаг переноса.

jz     short loc_20

; Переход, если флаг переноса сброшен, т.е. это равносильно конструкции jnc

; при сравнении целочисленных значений. Смотрим по таблице 16 – синоним jnc

; команда jnb.

; Следовательно, оригинальный код выглядел так:

; if (a<b) printf("a<b");

push   offset $SG339 ; "a<b"

call   _printf

add    esp, 4

loc_20:                                 ; CODE XREF: _main+11j

Листинг 161

Гораздо нагляднее код, сгенерированный компилятором Borland C++ или WATCOM C. Смотрите:

fld    [ebp+var_a]

; Загрузка значения вещественной переменной var_a на вершину стека сопроцессора

fcomp  [ebp+var_b]



; Сравнение значение переменной var_a с переменной var_b

; с сохранением результата сравнения во флагах сопроцессора

fnstsw ax

; Скопировать регистр флагов сопроцессора в регистр AX

sahf

; Скопировать соответствующие биты регистра AH во флаги основного процессора

jnb    short loc_1003C

; Переход, если !(a<b), иначе печать строки printf("a<b")

; Теперь, не копаясь ни в каких справочных таблицах, можно восстановить

; оригинальный

код:

; if (a<b) printf("a<b");

push   offset unk_100B0 ; format

call   _printf

pop    ecx

loc_1003C:                        ; CODE XREF: _main+Fj

Листинг 162

Теперь, "насобачившись" на идентификации элементарных условий, перейдем к вещам по настоящему сложным. Рассмотрим следующий пример:

#include <stdio.h>

main()

{

unsigned int a; unsigned int b; int c; int d;

if (d) printf("TRUE"); else if (((a>b) && (a!=0)) || ((a==c) && (c!=0))) printf("OK\n");

if (c==d) printf("+++\n");

}

Листинг 163

Результат его компиляции должен выглядеть приблизительно так:

_main        proc near

var_d        = dword      ptr -10h

var_C        = dword      ptr -0Ch

var_b        = dword      ptr -8

var_a        = dword      ptr -4

push   ebp

mov    ebp, esp

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

sub    esp, 10h

; Резервирование места для локальный переменных

cmp    [ebp+var_d], 0

; Сравнение значение переменной var_d с нулем

jz     short loc_1B

; Если переменная var_d

равна нулю, переход к метке loc_1B, иначе

; печать строки TRUE. Схематически это можно изобразить так:

;                       var_d == 0

;                     /            \

;                  loc_1B          printf("TRUE");

push   offset $SG341 ; "TRUE"

call   _printf

add    esp, 4

jmp    short loc_44

; "Ага", говорим мы голосом Пяточка, искушающего Кенгу!



; Вносим этот условный переход в наше дерево

;

;                       var_d == 0

;                     /            \

;                  loc_1B          printf("TRUE");

;                                      |

;                                     loc_44

loc_1B:                                 ; CODE XREF: _main+Aj

mov    eax, [ebp+var_a]

; Загружаем в EAX значение переменной var_a

cmp    eax, [ebp+var_b]

; Сравниваем переменную var_a с переменной var_b

jbe    short loc_29

; Если var_a

меньше или равна переменной var_b, то переход на loc_29

; Прививаем новое гнездо к нашему дереву, попутно обращая внимание не то, что

; var_a и var_b

беззнаковые переменные!

;

;                       var_d == 0

;                     /            \

;                  loc_1B          printf("TRUE");

;                     |                 |

;              var_a  <= var_b        loc_44

;             /              \ 

;         continue           loc_29

cmp    [ebp+var_a], 0

; Сравниваем значение переменной var_a с нулем

jnz    short loc_37

; Переход на loc_37, если var_a

не равна нулю

;

;                       var_d == 0

;                     /            \

;                  loc_1B          printf("TRUE");

;                     |                 |

;              var_a  <= var_b        loc_44

;             /              \ 

;         var_a !=0           loc_29

;        /         \

;    continue       loc_37

loc_29:                                 ; CODE XREF: _main+21j

; Смотрите – в нашем дереве уже есть метка loc_29! Корректируем его!

;

;                       var_d

== 0

;                     /            \

;                  loc_1B          printf("TRUE");

;                     |                 |

;              var_a  <= var_b        loc_44

;             /              \ 

;         var_a !=0           loc_29

;         /         \          |



;        |          |          |

;         \       loc_37       |

;          \                   |

;           \------------------+

mov    ecx, [ebp+var_a]

; Загружаем в ECX значение переменной var_a

cmp    ecx, [ebp+var_C]

; Сравниваем значение переменной var_a с переменной var_C

jnz    short loc_44

; переход, если var_a != var_C

;

;                       var_d == 0

;                     /            \

;                  loc_1B          printf("TRUE");

;                     |                 |

;              var_a  <= var_b        loc_44

;             /              \ 

;         var_a !=0           loc_29

;         /         \          |

;        |          |          |

;         \       loc_37       |

;          \                   |

;           \------------------+

;                     |

;               var_a != var_C

;              /               \

;          continue            loc_44

cmp    [ebp+var_C], 0

; Сравнение значения переменной var_C с нулем

jz     short loc_44

; Переход на loc_44 если var_C

== 0

;

;                       var_d == 0

;                     /            \

;                  loc_1B          printf("TRUE");

;                     |                 |

;              var_a  <= var_b        loc_44

;             /              \          |

;         var_a !=0           loc_29    |

;         /         \          |        |

;        |          |          |        |

;         \       loc_37       |        |

;          \                   |        |

;           \------------------+        |

;                     |                 |

;               var_a != var_C          |

;              /               \       /

;         var_C == 0            |     /

;        /          \            |   /

;     continue       \-----------+--/

;                                |

;                               loc_44

loc_37:                                 ; CODE XREF: _main+27j



; Смотрим – метка loc_37 уже есть в дереве! Прививаем!

;

;                       var_d

== 0

;                     /            \

;                  loc_1B          printf("TRUE");

;                     |                 |

;              var_a  <= var_b       loc_44

;             /              \       |

;         var_a !=0           loc_29 |

;         /         \          |     |

;        |           \         |     |

;         \           \-----à | ß--------!

;          \                   |     |     !

;           \------------------+    /      !

;                     |            /       !

;               var_a != var_C    /        !

;              /               \ /         !

;         var_C == 0            |          !

;        /          \            |         !

;        !           \-----------+         !

;        !                       |         !

;        !                       !         !

;        \---------------------------------!------!

;                                !                !

;                               loc_44         loc_37

;                                                 |

;                                              printf("OK");

push   offset $SG346 ; "OK\n"

call   _printf

add    esp, 4

loc_44:                                 ; CODE XREF: _main+19j    _main+2Fj ...

; Смотрите – ветки loc_44 и loc_37 смыкаются!

;

;                       var_d == 0

;                     /            \

;                  loc_1B          printf("TRUE");

;                     |                 |

;              var_a  <= var_b        loc_44

;             /              \        |

;         var_a !=0           loc_29  |

;         /         \          |      |

;        |           \         |      |

;         \           \-----à | ß--------!

;          \                   |      |    !

;           \------------------+     /     !



;                     |             /      !

;               var_a != var_C     /       !

;              /               \  /        !

;         var_C == 0            \|         !

;        /          \            |         !

;        !           \-----------+         !

;        !                       |         !

;        !                       !         !

;        \---------------------------------!------!

;                                !                !

;                               loc_44         loc_37

;                                 |               |

;                                 |            printf("OK");

;                                 |                |

;                                  \-------+-------/

;                                          |

;                                          |

mov    edx, [ebp+var_C]

; Загружаем в EDX значение переменной var_C

cmp    edx, [ebp+var_d]

; Сравниваем значение var_C

со значением переменной var_D

jnz    short loc_59

; Переход, если var_C

!= var_D

push   offset $SG348 ; "+++\n"

call   _printf

add    esp, 4

;                       var_d == 0

;                     /            \

;                  loc_1B          printf("TRUE");

;                     |                 |

;              var_a  <= var_b        loc_44

;             /              \        |

;         var_a !=0           loc_29  |

;         /         \          |      |

;        |           \         |      |

;         \           \-----à | ß--------!

;          \                   |      |    !

;           \------------------+     /     !

;                     |             /      !

;               var_a != var_C     /       !

;              /               \  /        !

;         var_C == 0             |         !

;        /          \            |         !

;        !           \-----------+         !

;        !                       |         !



;        !                       !         !

;        \---------------------------------!------!

;                                !                !

;                               loc_44         loc_37

;                                 |               |

;                                 |            printf("OK");

;                                 |                |

;                                  \-------+-------/

;                                          |

;                                          |

;                                      var_C != var_D

;                                     /              \

;                            printf("+++")            !

;                                                   конец

loc_59:                                 ; CODE XREF: _main+4Aj

             mov    esp, ebp

             pop    ebp

             retn

_main        endp

Листинг 164

В итоге вырастает огромное разлапистое дерево, в котором на первый взгляд просто невозможно разобраться. Но, как говориться, глаза страшатся, а руки делают. Первым делом, оптимизируем дерево: избавимся от "перекрученных" ветвей, инвертировав условие в гнезде, и выкинем все метки – теперь, когда скелет дерева построен, они уже не нужны. Если все сделать правильно, дерево должен выглядеть так:



Рисунок 28 0х01В Логическое древо

Сразу же бросается в глаза, что все пути проходят точку "Z", сплетающую все ветви воедино. Это значит, что мы имеем дело с двумя

самостоятельными деревьями, представленными собственными конструкциями "IF". Замечательно! Такой поворот событий весьма упрощает анализ – раз деревья независимые, то и анализироваться они могут независимо! Итак, начинаем с верхнего из них….

От гнезда "var_d !=0" отходят две ветки – правая ведет к "printf("OK")" и далее к завершению конструкции "IF – THEN [ELSE]", а левая, прежде чем выйти к точке "Z", минует целое полчище гнезд.


В переводе на русский язык ситуация выглядит так: "если переменная var_d не равна нулю, то печатаем "OK" и сваливаем, иначе выполняем дополнительные проверки". Проще говоря: "IF (var_d !=0) THEN printf("OK") ELSE …". Т.е. левая ветка гнезда (var_d != 0) есть ветка "ELSE". Изучим ее?

От гнезда (var_a <= var_b) к узлу "printf("OK")" ведут два пути: !(var_a <= var_b) à !(var_a ==0 )

и !(var_a != var_c) à !(var_c == 0). Где есть альтернатива – там всегда есть OR. Т.е. либо первый путь, либо второй. В то же время, узлы обоих путей последовательно связаны друг с другом, - значит, они объедены операций AND. Таким, образом, эта ветка должна выглядеть так: "IF (( var_a > var_b) && (var_0 != 0)) || (var_a == var_c) && (var_c != 0)) printf("OK")", прививаем "ELSE" к первому IF и получаем. "IF (var_d !=0) THEN printf("OK") ELSE IF(( var_a > var_b) && (var_0 != 0)) || (var_a == var_c) && (var_c != 0)) printf("OK")"

Ну, а разбор второго дерева вообще тривиален: "IF (var_c==var_d) printf("+++")". Итак, исходный текст дизассемблируемой программы выглядел так:

u_int a; u_int b; ?_int c; ?_int d;

if (d) printf("TRUE");

else

if (((a>b) && (a!=0)) || ((a==c) && (c!=0))) printf("OK\n");

if (c==d) printf("+++\n");

Листинг 165

Тип переменных a и b мы определили как unsigned int, т.к. они результат сравнения анализировался беззнаковой условной командой – jnb. А вот тип переменных c и d, увы, определить так и не удалось. Однако это не умоляет значимости того факта, что мы смогли ретранслировать сложное условие, в котором без деревьев было бы немудрено и запутаться…

- Больше всего следует опасаться идей, которые переходят в дела.

Френк Херберт "Мессия дюны"

Оптимизация ветвлений: Какое коварство – под флагом оптимизации сделать каждую строчку кода головоломкой.


Тьфу-ты, тут ящика пива не хватит, чтобы с этим справиться (а с этим лучше справляться вообще без пива – на трезвую голову). Итак, предположим, встретился вам код следующего содержания. На всякий случай, чтобы избавить вас от копания по справочникам (хотя, покопаться в них лишний раз – только на пользу) отмечу, что команда SETGE устанавливает выходной операнд в 1, если флаги состояния SF и OF равны (т.е. SF==OF). Иначе выходной операнд устанавливается в ноль.

mov eax, [var_A]

xor ecx,ecx

cmp eax, 0x666

setge cl

dec ecx

and ecx, 0xFFFFFC00

add ecx, 0x300

mov [var_zzz],ecx

Листинг 166

На первый взгляд этот фрагмент заимствован из какого-то хитро-запутанного защитного механизма, но нет. Перед вами результат компиляции следующего тривиального выражения: if (a<0x666) zzz=0x200 else zzz=0x300, которое в не оптимизированном виде выглядит так:

mov eax,[var_A]

cmp eax,0x666

jge Label_1

mov ecx, 0x100

jmp lable_2

Label_1:

mov ecx, 0x300

Lable_2:

mov [var_zzz],ecx

Листинг 167

Чем же компилятору не понравился такой вариант? Между прочим, он даже короче. Короче-то, он короче, но содержит ветвления,  - т.е. внеплановые изменения нормального хода выполнения программы. А ветвления отрицательно сказываются на производительности, хотя бы уже потому, что они приводят к очистке конвейера. Конвейер же в современных  процессорах очень длинный и быстро его не заполнишь… Поэтому, избавление от ветвлений путем хитроумных математических вычислений вполне оправдано и горячо приветствуется. Попутно это усложняет анализ программы, защищая ее от всех посторонних личностей типа хакеров (т.е. нас с вами).

Впрочем, если хорошенько подумать…. Начнем пошагово исполнять программу, мысленно комментируя каждую строчку.

mov eax, [var_A]

; eax == var_A

xor ecx,ecx

; ecx=0;

cmp eax, 0x666

; if eax<0x666 { SF=1; OF=0} else {SF=0; OF=0}

setge cl

; if eax<0x666 (т.е. SF==1, OF ==0) cl=0 else cl=1

dec ecx



; if eax<0x666 ecx=-1 else ecx=0

and ecx, 0xFFFFFC00

; if eax<0x666 (т.е. ecx==-1) ecx=0xFFFFFC00 (-0x400) else ecx=0;

add ecx, 0x300

; if eax<0x666 (т.е. ecx=-0x400) ecx=0x100 else ecx=0x300;

mov [esp+0x66],ecx

Листинг 168

Получилось! Мы разобрались с этим алгоритмом и успешно реверсировали его! Теперь видно, что это довольно простой пример (в жизни будут нередко попадаться и более сложные). Но основная идея ясна, - если встречаются команда SETxx  – держите нос по ветру: пахнет условными переходами! В вырожденных случаях SETxx может быть заменена на SBB

(вычитание с заемом). По этому поводу решим вторую задачу:

SUB EBX,EAX

SBB ECX,ECX

AND ECX,EBX

ADD EAX,ECX

Листинг 169

Что этот код делает? Какие-то сложные арифметические действия? Посмотрим…

SUB EBX,EAX

; if (EBX<EAX) SF=1 else SF=0

SBB ECX,ECX

; if (EBX<EAX) ECX=-1 else ECX=0

AND ECX,EBX

; if (EBX<EAX) ECX=EBX else ECX=0

ADD EAX,ECX

; if (EBX<EAX) EAX=EAX+(EBX-EAX) else EAX=EAX

Листинг 170

Раскрывая скобки в последнем выражении (мы ведь не забыли, что от EBX

отняли EAX?) получаем: if (EBX<EAX) EAX=EBX, - т.е. это классический алгоритм поиск минимума среди двух знаковых чисел. А вот еще один пример:

CMP EAX,1

SBB EAX,EAX

AND ECX,EAX

XOR EAX,-1

AND EAX,EBX

OR  EAX,ECX

Листинг 171

Попробуйте решить его сами и только потом загляните в ответ:

CMP EAX,1

; if (EAX!=0) SF=0 else SF=1

SBB EAX,EAX

; if (EAX!=0) EAX=-1 else EAX=0

AND ECX,EAX

; if (EAX!=0) ECX=ECX else ECX=0

XOR EAX,-1

; if (EAX!=0) EAX=0 else EAX=-1

AND EAX,EBX

; if (EAX!=0) EAX=0 else EAX=EBX

OR  EAX,ECX

; if (EAX!=0) EAX=ECX else EAX=EBX

Листинг 172

Да… после таких упражнений тов. Буль будет во сне сниться! Но… таковы уж издержки цивилизации. К слову сказать, подавляющее большинство компиляторов достаточно лояльно относятся к условным переходам и не стремятся к их тотальному изгнанию.Так что…. особо напрягаться при анализе оптимизированного кода не приходится (правда, к ручной оптимизации это не относится – профессиональные разработчики выкидывают переходы первую очередь).


Содержание раздела