Идентификация 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 |
::сравнение вещественных чисел. Команды сравнения вещественных чисел 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) |
Таким образом, вещественная конструкция "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 |
отношение |
состояние флагов 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 |
компилятор |
алгоритм анализа флагов FPU |
Borland C++ |
копирует флаги сопроцессора в регистр флагов основного процессора |
Microsoft Visual C++ |
тест битовой маски |
WATCOM C |
копирует флаги сопроцессора в регистр флагов основного процессора |
Free Pascal |
копирует флаги сопроцессора в регистр флагов основного процессора |
Условные команды булевой установки. Начиная с 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 |
Прочие условные команды. Микропроцессоры серии 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 |
::Команды условной пересылки.
Старшие процессоры семейства 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
Да… после таких упражнений тов. Буль будет во сне сниться! Но… таковы уж издержки цивилизации. К слову сказать, подавляющее большинство компиляторов достаточно лояльно относятся к условным переходам и не стремятся к их тотальному изгнанию.Так что…. особо напрягаться при анализе оптимизированного кода не приходится (правда, к ручной оптимизации это не относится – профессиональные разработчики выкидывают переходы первую очередь).