Идентификация IF - THEN - ELSE

Идентификация IF - THEN - ELSE — Архив WASM.RU

Значение каждого элемента текста определяется
контекстом его употребления. Текст не описывает мир,
а вступает в сложные взаимоотношения с миром.
Тезис аналитической философии
Существует два вида алгоритмов - безусловные и условные. Порядок действий безусловного алгоритма всегда постоянен и не зависит от входных данных. Например: "a=b+c". Порядок действий условных алгоритмов, напротив, зависит от входных данных. Например: "если c не равно нулю, то: a=b/c; иначе: вывести сообщение об ошибке".
Обратите внимание на выделенные жирным шрифтом ключевые слова "если", "то" и "иначе", называемые операторами условия или условными операторами. Без них не обходится ни одна программа (вырожденные примеры наподобие "Hello, World!" - не в счет). Условные операторы - сердце любого языка программирования. Поэтому, чрезвычайно важно уметь их правильно идентифицировать.
В общем виде (не углубляясь в синтаксические подробности отдельных языков программирования) оператор условия схематично изображается так:
IF (условие) THEN { оператор_1; оператор_2;} ELSE { оператор_a; оператор_b;}
Задача компилятора - преобразовать эту конструкцию в последовательность машинных команд, выполняющих оператор_1, оператор_2, если условие истинно и, соответственно - оператор_a, оператор_b; если оно ложно. Однако микропроцессоры серии 80x86 поддерживают весьма скромный набор условных команд, ограниченный фактически одними условными переходами. Программистам, знакомым лишь с IBM PC, такое ограничение не покажется чем-то неестественным, между тем, существует масса процессоров, поддерживающих префикс условного выполнения инструкции. Т.е. вместо того, чтобы писать:

Код (Text):

TEST ECX,ECX

JNZ xxx

MOV EAX,0x666

там поступают так:

Код (Text):

TEST ECX,ECX

IFZ MOV EAX,0x666

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

Код (Text):

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

20 GOTO 40

30 PRINT "A=B"

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

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

Листинг 139 

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

Код (Text):

IF (условие) THEN {оператор_1; оператор_2}

в следующий псевдокод:

Код (Text):

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

оператор_1;

оператор_2;

continue:

...

Листинг 140

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

Код (Text):

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""? Все равно компилятор инвертирует истинность условия и сгенерирует следующий код:

Код (Text):

10 IF A=B THEN 30

20 PRINT "A<>B"

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

Листинг 142

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

Код (Text):

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

GOTO continue

do:

оператор1;

оператор2;

continue:

...

Листинг 143

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

Код (Text):

IF (условие) THEN {оператор_1; оператор_2;} ELSE {оператор_a; оператор_b;}

Одни компиляторы поступают так:

Код (Text):

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

// Ветка ELSE

оператор_a;

оператор_b

GOTO continue

do_it:

//Ветка IF

оператор_1;

оператор_2;

continue:

А другие так:

Код (Text):

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:

Код (Text):

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))Е" и вглядимся в результат его трансляции:

Код (Text):

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

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

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

:continue <--! <---

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

Листинг 146

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

Код (Text):

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

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

goto continue -----! ! !

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

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

:continue <-!

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

Листинг 147

и так:

Код (Text):

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

IF a==0 THEN continue--! !

:do_it ! <-----!

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

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

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

Листинг 148

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

Код (Text):

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 можно попасть двумя различными путями!
До сих пор мы отображали логические операции на деревья, но ведь деревья создавались как раз для противоположной цели - преобразованию последовательности элементарных условий к интуитивно понятному представлению. Займемся этим? Пусть в тексте программы встретится следующий код:

Код (Text):

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" транслируется в следующие команды процессора:

Код (Text):

CMP A,B

Jxx do_it

continue:

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

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

Zero flag Carry Flag Sing Flag

a == b 1 ? ? JZ JE

a != b 0 ? ? JNZ JNE

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 ? 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" транслируется в одну из двух следующих последовательностей инструкций процессора:

Код (Text):

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 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" широко используются оптимизирующими компиляторами для устранения ветвлений, т.е. избавления от условных переходов, т.к. последние очищают конвейер процессора, чем серьезно снижают производительность программы.

команда отношение условие

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 беззнаковое 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 [...]CX, 0\JZ do_it" на более короткий эквивалент "J[...]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).

Код (Text):

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 беззнаковое 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". Покажем это на следующем примере:

Код (Text):

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++, на выходе мы получим такой код:

Код (Text):

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+1D j

mov [ebp+var_b], 0FFFFFFFFh

; Записываем в переменную var_b значение -1

continue: ; CODE XREF: _main+26 j

; Конец ветвления 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++ в режиме агрессивной оптимизации в обоих случаях генерирует идентичный код. Смотрите:

Код (Text):

_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" (это было сделано для лучшего спаривания инструкций), однако, если их сравнить, то выяснится - реализации обеих конструкций абсолютно идентичны друг другу!
Однако с точки зрения языка условный оператор "?" выгодно отличается от ветвления тем, что может непосредственно использоваться в выражениях, например:

Код (Text):

main()

{

int a;

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

}

Листинг 156

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

Код (Text):

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-разрядном режиме условный переход "бьет" в пределах всего четырех гигабайтного адресного пространства и все эти проблемы исчезают, как бородавки после сеанса Кашпировского.
Листинги примеров. А теперь для лучшего уяснения материала, рассмотренного в этой главе, давайте рассмотрим несколько "живых" примеров, откомпилированных различными компиляторами. Начнем с исследования элементарных целочисленных отношений:

Код (Text):

#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+ должен выглядеть так:

Код (Text):

main proc near ; CODE XREF: start+AF p

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+C j

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+21 j

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+36 j

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+4B j

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+60 j

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+75 j

mov esp, ebp

pop ebp

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

retn

main endp

Листинг 159

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

Код (Text):

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+11 j

mov ax, offset aAB ; "a<b"

push ax

call _printf

add sp, 2

loc_10050: ; CODE XREF: _main+13 j

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

Листинг 160

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

Код (Text):

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+11 j

Листинг 161

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

Код (Text):

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+F j

Листинг 162

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

Код (Text):

#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

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

Код (Text):

_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+A j

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+21 j

; Смотрите - в нашем дереве уже есть метка 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+27 j

; Смотрим - метка 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+19 j _main+2F j ...

; Смотрите - ветки 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+4A j

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("+++")". Итак, исходный текст дизассемблируемой программы выглядел так:

Код (Text):

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). Иначе выходной операнд устанавливается в ноль.

Код (Text):

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, которое в не оптимизированном виде выглядит так:

Код (Text):

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

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

Код (Text):

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 (вычитание с заемом). По этому поводу решим вторую задачу:

Код (Text):

SUB EBX,EAX

SBB ECX,ECX

AND ECX,EBX

ADD EAX,ECX

Листинг 169

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

Код (Text):

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, - т.е. это классический алгоритм поиск минимума среди двух знаковых чисел. А вот еще один пример:

Код (Text):

CMP EAX,1

SBB EAX,EAX

AND ECX,EAX

XOR EAX,-1

AND EAX,EBX

OR EAX,ECX

Листинг 171

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

Код (Text):

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

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

Войти или зарегистрироваться

Идентификация IF - THEN - ELSE

Идентификация IF - THEN - ELSE — Архив WASM.RU

archive
New Member

Войти или зарегистрироваться

Идентификация IF - THEN - ELSE

Идентификация IF - THEN - ELSE — Архив WASM.RU

archive New Member

Быстрый поиск

archive
New Member