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

       

Идентификация циклов


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

тезис классического постструктурализма в его отечественном изводе

Циклы

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

Существуют три основных типа цикла: циклы с условием вначале (см. рис. 36 слева), циклы с условием в конце (см. рис. 36 в центре) и циклы с условием в середине (см. рис. 36 справа). Комбинированные циклы имеют несколько условий в разных местах, например, в начале и в конце одновременно.

Рисунок 36 0х024 Логическое дерево цикла с условием вначале (слева) и условием в конец (справа).

В свою очередь условия бывают двух типов: условия завершения цикла и условия продолжения цикла. В первом случае: если условие завершения истинно происходит переход в конец цикла, иначе – его продолжение. Во втором: если условие продолжения цикла ложно происходит переход в конец цикла, в противном случае – его продолжения. Легко показать, что условия продолжения цикла представляют собой инвертированные условия завершения. Таким образом, со стороны транслятора вполне достаточно поддержки условий одного типа. И действительно, операторы циклов while,do и for

языка Си работают исключительно с условиями продолжения цикла. Оператор while

языка Pascal так же работает с условием продолжения цикла, и исключение составляет один лишь repeat-until

ожидающий условие завершения цикла.

::Циклы с условиями в начале (так же называемые циклами с преусловием). В языках Си и Pascal поддержка циклов с преусловием обеспечивается оператором "while (условие)", где "условие" – условие продолжения цикла.
Т.е. цикл "while (a < 10) a++;"

выполняется до тех пор, пока условие (a > 10) остается истинным. Однако транслятор при желании может инвертировать условие продолжение цикла на условие завершения цикла. На платформе Intel 80x86 такой трюк экономит от одной до двух машинных команд. Смотрите: на листинге 180 слева приведен цикл с условием завершения, а справа – с условием продолжения. Как видно, цикл с условием завершения на одну команду короче! Поэтому, практически все компиляторы (даже не оптимизирующие) всегда генерируют левый вариант. (А некоторые, особо одаренные, даже умеют превращать циклы с предусловием в еще более эффективные циклы с пост-условием – см. "Циклы с условием в конце").

while:                             while:

CMP A, 10                          CMP A, 10

JAE end                            JB continue

INC A                              JMP end

JMP while                    continue:

end:                                     INC A

JMP while

end:

Листинг 180 Слева показан цикл с условием завершения цикла, а справа – тот же цикл, но с условием продолжения цикла. Как видно, цикл с условием завершения на одну команду короче.

Цикл с условием завершения не может быть непосредственно отображен на оператор while. Кстати, об этом часто забывают начинающие, допуская ошибку "что вижу, то пишу": "while (a >= 10) a++". С таким условием данный цикл вообще не выполниться ни разу! Но как выполнить инверсию условия и при этом гарантированно не ошибиться? Казалось бы, что может быть проще, - а вот попросите знакомого хакера назвать операцию, обратную "больше". Очень может быть (даже наверняка!) ответом будет… "меньше". А вот и нет, - правильный ответ "меньше или равно". Полный перечень обратных операций отношений можно найти в таблице 25, приведенной ниже

Логическая операция

Обратная логическая операция

==

!=

!=

==



<=



>=

<=



>=



<


Таблица 25 Обратные операции отношения

::Циклы с условием в конце (так же называемые циклами с пост-условием). В языке Си поддержка циклов с пост-условием обеспечивается парой операторов do – while, а в языке Pascal – repeat\until. Циклы с пост-условием без каких либо проблем непосредственно отображаются с языка высокого уровня на машинный код и, соответственно, наоборот. Т.е. в отличие от циклов с предусловием, инверсии условия не происходит.

Например: "do a++; while (a<10)" в общем случае компилируется в следующий код (обратите внимание: в переходе использовалась та же самая операция отношения, что и в исходном цикле, - красота и никаких ошибок при декомпиляции):

repeat: <---------!

INC A       !

CMP A, 10   !

JB repeat---!

end:

Листинг 181

Вернувшись страницей назад, сравним код цикла с пост-условием с кодом цикла с предусловием. Не правда ли, цикл с условием в конце компактнее и быстрее? Некоторые компиляторы (например, Microsoft Visual C++) умеют транслировать циклы с предусловием в циклы с пост-условием. На первый взгляд – это вопиющая самодеятельность компилятора, - если программист хочет проверять условие в начале, то какое право имеет транслятор ставить его в конце?! На самом же деле, разница между "до" или "после" не столь велика и значительна. Если компилятор уверен, что цикл выполняется хотя бы один раз, то он вправе выполнять проверку когда угодно. Разумеется, при этом необходимо несколько скорректировать условие проверки: "while (a<b)" не эквивалентно "do … while (a<b)", т.к. в первом случае при (a == b) уже происходит выход из цикла, а во втором цикл выполняется еще одну итерацию. Однако этой беде легко помочь: увеличим а на единицу ("do … while ((a+1)<b)") или вычтем эту единицу из b ("do … while (a<(b-1))") и… теперь все будет работать!

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


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

::Циклы со счетчиком.

Циклы со счетчиком (for) не являются самостоятельным типом циклов, а представляют собой всего лишь синтаксическую разновидность циклов с предусловием. В самом деле, "for (a = 0; a < 10; a++)" в первом приближении это то же самое, что и: "a = 0; while (a < 10) {…;a++;}". Однако, результаты компиляции двух этих конструкций не обязательно должны быть идентичны друг другу!

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

языка высокого уровня. Смотрите:

MOV A, xxx          ; Инициализация переменной "счетчика"

JMP conditional     ; Переход к проверке условия продолжения цикла

repeat:                    ; Начало цикла

…            ; // ТЕЛО

…            ; //      ЦИКЛА

ADD A, xxx [SUB A, xxx]; Модификация счетчика

conditional:        ; Проверка условия продолжения цикла

CMP A, xxx          ; ^

Jxx repeat          ; Переход в начало цикла, если условие истинно

Листинг 182

Непосредственный прыжок вниз может быть результат компиляции и цикла for, и оператора GOTO, но GOTO сейчас не в моде и используется крайне редко, а без него оператор условного перехода "IF – THEN" не может прыгнуть непосредственно в середину цикла while! Выходит, изо всех "кандидатов" остается только цикл for.

Некоторые, особо продвинутые компиляторы (Microsoft Visual C++, Borland C++, но не WATCOM C), поступают хитрее: анализируя код они еще на стадии компиляции пытаются определить: выполняется ли данный цикл хотя бы один раз и, если видят, что он действительно выполняется, превращают for в типичный цикл с постусловием:



MOV A, xxx          ; Инициализация переменной "счетчика"

repeat:             ; Начало цикла

…                   ; // ТЕЛО

…                   ; //      ЦИКЛА

ADD A, xxx [SUB A, xxx]; Модификация счетчика

CMP A, xxx          ; Проверка условия продолжения цикла

Jxx repeat          ; Переход в начало цикла, если условие истинно

Листинг 183

Наконец, самые крутые компиляторы (из которых автор на вскидку может назвать один лишь Microsoft Visual C++ 6.0) могут даже заменять циклы с приращением на циклы с убыванием при условии, что параметр цикла не используется операторами цикла, а лишь прокручивает цикл определенное число раз. Зачем это компилятору? Оказывается, циклы с убыванием гораздо короче – однобайтовая инструкция DEC

не только уменьшает операнд, но и выставляет Zero-флаг при достижении нуля. В результате, в команде CMP A, xxx

отпадает всякая необходимость.

MOV A, xxx         ; Инициализация переменной "счетчика"

repeat:                    ; Начало цикла

…                   ; // ТЕЛО

…                   ; //      ЦИКЛА

DEC A               ; Декремент счетчика

JNZ repeat          ; Повтор, пока A != 0

Листинг 184

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

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

дать невозможно.

Скажем так: если логика исследуемого цикла синтаксически удобнее выражается через оператор for, то и выражайте ее через for! В противном случае используйте while или do



(repeat\until) для циклов с пред- и пост- условием соответственно.

И в заключение пара слов о "кастрированных" циклах – язык Си позволяет опустить инициализацию переменной цикла, условие выхода из цикла, оператор приращения переменной или все это вместе. При этом for

вырождается во while, и становится практически неотличимым от него.

::Циклы с условием в середине.

Популярные языки высокого уровня непосредственно не поддерживают циклы с условием в середине, хотя необходимость в них возникает достаточно часто. Поэтому, программисты их реализуют на основе уже имеющихся циклов while (while\do) и оператора выхода из цикла break. Например:

while(1)                     repeat:

{                                  …

…                            CMP xxx

if (условие) break;          Jxx end

…                            …

}                            JMP repeat

end:

Листинг 185

Компилятор (если он не совсем Осел – Иi в смысле) разворачивает бесконечный цикл в безусловный переход JMP, направленный, естественно назад (ослы генерируют код like – "MOV EAX, 1\CMP EAX,1\JZ repeat"). Безусловный переход, направленный назад, весьма характерен – за исключением бесконечного цикла его может порождать один лишь оператор GOTO, но GOTO уже давно не в моде. А раз у нас есть бесконечный цикл, то условие его завершения может находиться лишь в середине этого цикла (сложные случаи многопоточных защит, модифицирующих из соседнего потока безусловный переход в NOP, мы пока не рассматриваем). Остается прочесать тело цикла и найти это самое условие.

Сделать это будет нетрудно – оператор break транслируется в переход на первую команду, следующую на JMP repeat, а сам break

получает управление от ветки IF (условие) – THEN – [ELSE]. Условие ее срабатывания и будет искомым условием завершения цикла. Вот, собственно, и все.

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


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

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

::Циклы с несколькими счетчиками.

Оператор "запятая" языка Си позволяет осуществлять множественную инициализацию и модификацию счетчиков цикла for. Например: "for (a=0, b=10; a != b; a++, b--)". А как насчет нескольких условий завершения? И "ветхий" и "новый " заветы (первое и второе издание K&R соответственно), и стандарт ANSI C, и руководства по С, прилагаемые к компиляторам Microsoft Visual C, Borland C, WATCOM C на этот счет хранят "партизанское" гробовое молчание.

Если попробовать скомпилировать следующий код "for (a=0, b=10; a >0, b <10 ; a++, b--)" он будет благополучно "проглочен" практически всеми компиляторами без малейших ругательств с их стороны, но ни один их них не откомпилирует данный пример правильно. Логическое условие (a1,a2,a3,…an) лишено смысла и компиляторы без малейших колебаний и зазрений совести отбросяст все, кроме самого правого выражения an. Оно-то и будет единолично пределять условие продолжение цикла. Один лишь WATCOM вяло ворчит по этому поводу: "Warning! W111: Meaningless use of an expression: the line contains an expression that does nothing useful. In the example "i = (1,5);", the expression "1," is meaningless. This message is also generated for a comparison that is useless"

Если условие продолжения цикла зависит от нескольких переменных, то их сравнения следует объединить в одно выражение посредством логических операций OR, AND



и др. Например: "for (a=0, b=10; (a >0 && b <10) ; a++, b--)" – цикл прерывается сразу же, как только одно из двух условий станет ложно;  "for (a=0, b=10; (a >0 || b <10); a++, b--)" – цикл продолжается до тех пор, пока истинно хотя бы одно условие из двух.

В остальном же циклы с несколькими счетчиками транслируются аналогично циклам с одним счетчиком, за исключением того, что инициализируется и модифицируется не одна, а сразу несколько переменных.

::Идентификация continue. Оператор continue приводит к непосредственной передаче управления на код проверки условия продолжения (завершения) цикла. В общем случае он транслируется в безусловный jump, в циклах с предусловием направленный вверх, а в циклах в постусловием – вниз. Код, следующий за continue, уже не получает управления, поэтому continue

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

Например: "while (a++ < 10) if (a == 2) continue;…" компилируется приблизительно так:

repeat:             ; Начало цикла while

INC A        ; a++

CMP A, 10    ; Проверка условия завершения цикла

JAE end             ; Конец, если a >= 10

CMP A,2             ; if (a == 2) …

JNZ woo             ; Переход к варианту "иначе", если a

!= 2

JMP repeat   ; ç continue

woo:         ; // ТЕЛО

…            ; //         ЦИКЛА

JMP repeat   ; Переход в начало цикла

Листинг 186

::Сложные условия.

До сих пор, говоря об условиях завершения и продолжения цикла, мы рассматривали лишь элементарные условия отношения, в то время как практически все языки высокого уровня допускают использование составных условий. Однако составные условия можно схематично изобразить в виде абстрактного "черного ящика" с входом/выходом и логическим двоичными деревом внутри. Построение и реконструкция логических деревьев подробно рассматриваются в главе "Идентификация IF – THEN – ELSE" здесь же нас интересует не сами условия, а организация циклов.



::Вложенные циклы.

Циклы – понятное дело – могут быть и вложенными. Казалось бы, какие проблемы? Начало каждого цикла надежно определяется по перекрестной ссылке, направленной вниз. Конец цикла – условный или безусловный переход на его начало. У каждого цикла только одно начло и только один конец (хотя условий выхода может быть сколько угодно, но это – другое дело). Причем, циклы не могут пересекаться – если между началом и концом одного цикла встречается начало другого цикла, то этот цикл – вложенный.

Но не все так просто: тут есть два подводных камня. Первый: оператор continue в циклах с предусловием, второй – сложные условия продолжения цикла с постусловием. Рассмотрим их подробнее.

Поскольку, continue в циклах с предусловием, транслируется в безусловный переход, направленный "вверх", он становится практически неотличим от конца цикла. Смотрите:

while(условие1)

{



if (условие2) continue;



}

транслируется в:

NOT

условие1 выхода из цикла–––––––––!  <-!  <-----!

…                                    !    !        !

если НЕ условие2 GOTO continue ---!  !    !        !

безусловный переход в начало ------)--)---!        !

continue:                   <-----!  !             !

…                                    !             !

безусловный переход в начало ---------)------------!

конец всего <------------------------!

Два конца и два начала вполне напоминают два цикла, из которых один вложен в другой. Правда, начала обоих циклов совмещены, но ведь может же такое быть, если в цикл с пост условием вложен цикл с предусловием? На первый взгляд да, но если подумать, то… ай-ай-ай! А ведь условие1

выхода из цикла прыгает аж за второй конец! Если это предусловие вложенного цикла, то оно прыгало бы за первый конец. А если условие1 – это предусловие материнского цикла, то конец вложенного цикла не смог бы передать на него управление. Выходит, это не два цикла, а один. А первый "конец" – результат трансляции оператора continue.



С разбором сложных условий продолжения цикла с постусловием дела обстоят еще лучше. Рассмотрим такой пример:

do

{



} while(условие1 || условие2);

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

…                   <---! <-!

условие продолжения1 ---!   !

условие прололжения2 -------!

Ну, чем не:

do

{

do

{



}while(условие1)

}while(условие2)

Строго говоря, предложенный вариант является логически верным, но синтаксически некрасивым. Материнский цикл крутит в своем теле один лишь вложенный цикл и не содержит никаких других операторов. Так зачем он тогда, спрашивается, нужен? Объединить его с вложенным циклом в один!

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

Начнем с самого простого – с циклов while\do:

#include <stdio.h>

main()

{

int a=0;

while(a++<10) printf("Оператор

цикла while\n");

do {

printf("Оператор

цикла do\n");

} while(--a >0);

}

Листинг 187 Демонстрация идентификации циклов while\do

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

main   proc near           ; CODE XREF: start+AFp

var_a        = dword      ptr -4

push   ebp

mov    ebp, esp

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

push   ecx

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

mov    [ebp+var_a], 0

; Заносим в переменную var_a

значение 0x0

loc_40100B:                       ; CODE XREF: main_401000+29j

;                                       ^^^^^^^^^^^^^^

; Перекрестная ссылка, направленная вниз, говорит о том, что это начло цикла

; Естественно: раз перекрестная ссылка направлена вниз, то переход,

; ссылающийся на этот адрес, будет направлен вверх!

mov    eax, [ebp+var_a]

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



mov    ecx, [ebp+var_a]

; Загружаем в EСX

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

; (недальновидность компилятора – можно было бы поступить и короче MOV ECX,EAX)

add    ecx, 1

; Увеличиваем ECX на единицу

mov    [ebp+var_a], ecx

; Обновляем var_a

cmp    eax, 0Ah

; Сравниваем старое ( до обновления) значение переменной var_a с числом 0xA

jge    short loc_40102B

; Если var_a

>= 0xA – прыжок "вперед", непосредственно за инструкцию

; безусловного перехода, направленного "назад"

; Раз "назад", значит, – это цикл, а, поскольку, условие выхода из цикла

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

; Для его отображения на цикл while

необходимо инвертировать условие выхода

; из цикла на условие продолжения цикла (Т.е. заменить >= на <)

; Сделав это, мы получаем:

; while (var_a++ < 0xA)…

;

// Начало

тела цикла

push   offset aOperatorCiklaW ; "Оператор

цикла while\n"

call   _printf

add    esp, 4

; printf("Оператор цикла while\n")

jmp    short loc_40100B

; Безусловный переход, направленный назад, на метку loc_40100B

; Между loc_40100B и jmp short loc_40100B есть только одно условие

; выхода из цикла – jge short loc_40102B, значит, исходный цикл

; выглядел так:

; while (var_a++ < 0xA) printf("Оператор цикла while\n")

loc_40102B:                       ; CODE XREF: main_401000+1Aj

; main_401000+45j

; ^^^^^^^^^^^^^^^^

; // Это начало цикла с пост-условием

; // Однако на данном этапе мы этого еще не знаем, хотя и можем догадываться

; // благодаря наличию перекрестной ссылки, направленной вниз

; Ага, никакого условия в начале цикла не присутствует, значит, это цикл

; с условием в конце или середине

push   offset aOperatorCiklaD ; "Оператор

цикла do\n"

call   _printf

add    esp, 4

; printf("Оператор цикла do\n")

; // Тело

цикла

mov    edx, [ebp+var_a]

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



sub    edx, 1

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

mov    [ebp+var_a], edx

; Обновляем переменную var_a

cmp    [ebp+var_a], 0

; Сравниваем переменную var_a

с нулем

jg     short loc_40102B

; Если var_a

> 0, то переход в начало цикла

; Поскольку, условие расположено в конце тела цикла, этот цикл – do:

; do printf("Оператор цикла

do\n"); while (--a > 0)


;

; // Для повышения читабельности дизассемблерного текста рекомендуется

; // заменить префиксы loc_ в начале цикла на while и do (repeat) в циклах

; // с пред- и пост- условием соответственно

mov    esp, ebp

pop    ebp

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

retn

main   endp

Листинг 188

Совсем другой результат получится если включить оптимизацию. Откомпилируем тот же самый пример с ключом "/Ox" (максимальная оптимизация) и посмотрим на результат, выданный компилятором:

main         proc near           ; CODE XREF: start+AFp

push   esi

push   edi

; Сохраняем регистры в стеке

mov    esi, 1

; Присваиваем ESI значение 0х1

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

; такого значения!

mov    edi, 0Ah

; Присваиваем EDI значение 0xA. Ага, это константа для проверки условия

; выхода из цикла

loc_40100C:                       ; CODE XREF: main+1Dj

; ^^^^^^^^^^^^^^^^^^^^

; Судя по перекрестной ссылке, направленной вниз, этот – цикл!

push   offset aOperatorCiklaW ; "Оператор

цикла while\n"

call   _printf

add    esp, 4

; printf("Оператор цикла

while\n")


; …тело цикла while? (растерянно так)

; Постой, постой! А где же предусловие?!

dec    edi

; Уменьшаем EDI на один

inc    esi

; Увеличиваем ESI на один

test   edi, edi

; Проверяем EDI на равенство нулю

ja     short loc_40100C

; Переход в начало цикла, пока EDI

!= 0

; Так… (задумчиво) Компилятор в порыве оптимизации превратил неэффективный

; цикл с предусловием в более компактный и быстрый цикл с пост-условием



; Имел ли он на это право? А почему нет?! Проанализировав код, компилятор понял

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

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

; Поэтому-то начальное значение переменной цикла равно единице, а не нулю!

; Т.е. while ((int a = 0) < 10) компилятор

заменил на do … while (((int a = 0)+1) < 10) ==

; do … while ((int a=1) < 10)

;

; Причем, что интересно, он не сравнивал переменную цикла с константой,

; а поместил константу в регистр и уменьшал его до тех пор, пока тот не стал

; равен нулю! Зачем? А затем, что так короче, да и работает быстрее

; Что ж, это все хорошо, но как нам декомпилировать этот цикл?

; Непосредственное отображение на язык Си дает следующую конструцию:

; var_ ESI = 1; var _EDI = 0xA;

; do {

;;printf("Оператор цикла

while\n"); var_EDI--; var_ESI++;


; } while(var_EDI > 0)

;

; Правда, коряво и запутано? Что-ж, тогда попытаемся избавится от одной

; из двух переменных. Это действительно возможно, т.к. они модифицируются

; синхронно, и var_EDI = 0xB – var_ESI

; ОК, выполняем подстановку:

; var_ ESI = 1; var _EDI = 0xB – var_ESI ; (== 0xA;)

; do {

;;printf("Оператор цикла

while\n"); var_EDI--; var_ESI++;


;                                   ^^^^^^^^^^

; Это мы вообще сокращаем, т.к. var_EDI уже выражена через var_ESI

; } while((0xB – var_ESI) > 0); (== var_ESI > 0xB)

;

; Что, ж уже получается нечто осмысленное:

;

; var_ ESI = 1; var _EDI == 0xA;

; do {

;;     printf("Оператор цикла

while\n"); var_ESI++;


; } while(var_ESI > 0xB)

; На этом можно и остановится, а можно и пойти дальше, преобразовав цикл

; с пост-условием в более наглядный цикл с предусловием

;

; var_ ESI = 1; var _EDI == 0xA; ß var_EDI не используется, можно сократить

; while (var_ESI <= 0xA) {

;;     printf("Оператор цикла

while\n"); var_ESI++;


; }

; Но и это не предел выразительности: во-первых var_ESI <= 0xA эквивалентно



; var_EDI < 0xB, а во-вторых, поскольку, переменная var_ESI используется лишь

; как счетчик, ее начальное значение можно безбоязненно привести к нулевому

; значению, а операцию инкремента внести в сам цикл:

; var_ ESI = 0;

; while (var_ESI++ < 0xA) ß

вычитаем единицу из левой и правой половины

; printf("Оператор цикла while\n");

;

; Ну, разве не красота?! Сравните этот вариант с первоначальным –

; насколько он стал яснее и понятнее

loc_40101F:                       ; CODE XREF: main+2Fj

;                                       ^^^^^^^^^^^^^^^^^^^^

; Перекрестная ссылка, направленная вниз, говорит о том, что это – начало цилка

; // Предусловия нет – значит, это цикл do

push   offset aOperatorCiklaD ; "Оператор

цикла do\n"

call   _printf

add    esp, 4

; printf("Оператор цикла do\n");

dec    esi

; Уменьшаем var_ESI

test   esi, esi

; Проверка ESI на равенство нулю

jg     short loc_40101F

; Продолжать цикл, пока var_ESI

> 0

;

; ОК. Этот цикл легко и непринужденно отображается на язык Си:

; do printf("Оператор цикла

do\n"); while (--var_ESI > 0 )


pop    edi

pop    esi

; Восстанавливаем сохраненные регистры

retn

main         endp

Листинг 189

Несколько иначе оптимизирует циклы компилятор Borland C++ 5.x. Смотрите:

_main        proc near           ; DATA XREF: DATA:00407044o

push   ebp

mov    ebp, esp

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

push   ebx

; Сохраняем EBP в стеке

xor    ebx, ebx

; Присваиваем регистровой переменной EBX

значение ноль

; Как легко догадаться – EBX и есть "a"

jmp    short loc_40108F

; Безусловный прыжок вниз. Очень похоже на цикл for…

loc_401084:                       ; CODE XREF: _main+19j

;                                       ^^^^^^^^^^^^^^^^^^^^^

; Перекрестная ссылка, направленная вниз – значит, это начало какого-то цикла



push   offset aOperatorCiklaW ; "Оператор

цикла while\n"

call   _printf

pop    ecx

; printf("Оператор цикла

while\n")


loc_40108F:                       ; CODE XREF: _main+6j

; А вот сюда был направлен самый первый jump

; Посмотрим: что же это такое?

mov    eax, ebx

; Копирование EBX в EAX

inc    ebx

; Увеличение EBX

cmp    eax, 0Ah

; Сравнение EAX со значением 0xA

jl     short loc_401084

; Переход в начало цикла, если EAX

< 0xA

; Вот так-то Borland оптимизировал код! Он расположил условие в конце цикла,

; но, чтобы не транслировать цикл с предусловием в цикл с постусловием,

; просто начал выполнение цикла с этого самого условия!

;

; Отображение этого цикла на язык Си дает:

; for (int a=0; a < 10; a++) printf("Оператор цикла

while\n")


;

; и, хотя подлинный цикл выглядел совсем не так, наш вариант нечем не хуже!

; (а может даже и лучше – нагляднее)

loc_401097:                       ; CODE XREF: _main+29j

;                                       ^^^^^^^^^^^^^^^^^^^^^

; Начало цикла!

; Условия нет – значит, это цикл с постусловием

push   offset aOperatorCiklaD ; "Оператор

цикла do\n"

call   _printf

pop    ecx

; printf("Оператор цикла do\n")

dec    ebx

; --var_EBX

test   ebx, ebx

jg     short loc_401097

; Продолжать цикл, пока var_EBX

> 0

; do printf("Оператор цикла

do\n"); while (--var_EBX > 0)


xor    eax, eax

; return 0

pop    ebx

pop    ebp

; Восстанавливаем сохраненные регистры

retn

_main        endp

Листинг 190

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

Компилятор Free Pascal 1.x ведет себя аналогично компилятору Borland C++ 5.0, всегда помещая условие в конец цикла и начиная с него выполнение while-циклов.



Компилятор WATCOM C не умеет преобразовывать циклы с предусловием в циклы с постусловием, вследствие чего располагает условие выхода из цикла в начале while-циклов, а в их конец вставляет безусловный jump. (Классика!)

Компилятор GCC вообще не оптимизирует циклы с предусловием, генерируя самый неоптимальный код. Смотрите:

mov    [ebp+var_a], 0

; Присвоение переменной a значения 0

mov    esi, esi

; Э… на редкость умный код! При его виде трудно не упасть со стула!

loc_401250:                       ; CODE XREF: sub_40123C+34j

;                                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

; Начало

цикла

mov    eax, [ebp+var_a]

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

inc    [ebp+var_a]

; Увеличение var_a

на единицу

cmp    eax, 9

; Сравнение EAX со значением 0x9

jle    short loc_401260

; Переход, если EAX <= 0x9 (EAX < 0xA)

jmp    short loc_401272

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

; Стало быть, предыдущий условный переход – переход на его продолжение

; Какой неоптимальный код! Зато нет инверсии условия продолжения цикла,

; что упрощает дизассемблирование

align

4

; Выравнивание перехода по адресам, кратным четырем, ускорят код, но заметно

; увеличивает его размер (особенно, если переходов очень много)

loc_401260:                       ; CODE XREF: sub_40123C+1Dj

add    esp, 0FFFFFFF4h

; Вычитание из ESP значения 12 (0xC)

push   offset aOperatorCiklaW ; "Оператор

цикла while\n"

call   printf

add    esp, 10h

; Восстанавливаем стек (0xC + 0x4 ) == 0x10

jmp    short loc_401250

; Переход в начало цикла

loc_401272:

; Конец цикла

Листинг 191

Разобравшись с while\do, перейдем к циклам for. Рассмотрим следующий пример:

#include <stdio.h>

main()

{

int a;

for (a=0;a<10;a++)  printf("Оператор

цикла for\n");

}

Листинг 192 Демонстрация идентификации циклов for

Результат компиляции Microsoft Visual C++ 6.0 с настройками по умолчанию будет выглядеть так:



main         proc near           ; CODE XREF: start+AFp

var_a        = dword      ptr -4

push   ebp

mov    ebp, esp

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

push   ecx

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

mov    [ebp+var_a], 0

; Присваиваем локальной переменной var_a значение 0

jmp    short loc_401016

; Непосредственный переход на код проверки условия продолжения цикла -

; характерный признак for

loc_40100D:                       ; CODE XREF: main+29j

;                                       ^^^^^^^^^^^^^^^^^^^^

; Перекрестная ссылка, направленная вниз говорит о том, что это начало цикла

mov    eax, [ebp+var_a]

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

add    eax, 1

; Увеличение EAX на единицу

mov    [ebp+var_a], eax

; Обновление EAX

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

; ++a

loc_401016:                       ; CODE XREF: main+Bj

cmp    [ebp+var_a], 0Ah

; Сравниваем var_a

со значением 0xA

jge    short loc_40102B

; Выход из цикла, если var_a

>= 0xA

push   offset aOperatorCiklaF ; "Оператор

цикла for\n"

call   _printf

add    esp, 4

; printf("Оператор цикла for\n")

jmp    short loc_40100D

; Безусловный переход в начало цикла

;

; Итак, что мы имеем?

; инициализация переменной var_a

; переход на проверку условия выхода из цикла –---–----!

; инкремент переменной var_a ß-------------------!    !

; проверка условия относительно var_a ß--------- ! ---!

; прыжок на выход из цикла, если условие истинно–!–---!

; вызов printf                                   !    !

; переход в начало цикла ------------------------!    !

; конец цикла ß-------------------------------–-–----!

;

; Проверка на завершения, расположенная в начале цикла, говорит о том, что

; это цикл с предусловием, но непосредственно выразить его через while

; не удается – мешает безусловный переход в середину цикла, минуя код



; инкремента переменной var_a

; Однако этот цикл с легкостью отображается на оператор for, смотрите:

; for (a = 0; a < 0xA; a++) printf("Оператор цикла

for\n")


;

; Действительно, цикл for сначала инициирует переменную – счетчик,

; затем проверяет условие продолжение цикла

; (оптимизируемое компилятором в условие завершение), далее выполняет

; оператор цикла, модифицирует счетчик, вновь проверяет условие и т.д.

;

loc_40102B:                       ; CODE XREF: main+1Aj

mov    esp, ebp

pop    ebp

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

retn

main         endp

Листинг 193

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

main         proc near           ; CODE XREF: start+AFp

push   esi

mov    esi, 0Ah

; Инициализируем переменную – счетчик

; Внимание! В исходном коде начальное значение счетчика равнялось нулю!

loc_401006:                       ; CODE XREF: main+14j

push   offset aOperatorCiklaF ; "Оператор

цикла for\n"

call   _printf

add    esp, 4

; printf("Оператор цикла for\n")

; Выполняем оператор цикла! Причем безо

всяких проверок!

; Хитрый компилятор проанализировал код и понял, что цикл выполняется

; по крайней мере один раз!

dec    esi

; Уменьшаем счетчик, хотя в исходном коде программы мы его увеличивали!

; Ну, правильно – dec \ jnz намного короче INC\ CMP reg, const\ jnz xxx

; Ой и мудрит компилятор! Кто же ему давал право так изменять цикл?!

; А очень просто – он понял, что параметр цикла в самом цикле используется

; только как счетчик, и нет никакой разницы – увеличивается он

; с каждой итерацией или уменьшается!

jnz    short loc_401006

; Переход в начало цикла если ESI

> 0

;

; М да, по внешнему виду это типичный

; a = 0xa; do printf("Оператор цикла

for\n"); while (--a)


;

; Если вас устраивает читабельность такой формы записи – оставляйте ее, а нет:

; for (a = 0; a < 10; a++) Оператор цикла

for\n")


;



; Постой, постой! На каком основании автор выполнил такое преобразование?!

; А на том самом – что и компилятор: раз параметр цикла используется только

; как счетчик, законна любая запись, выполняющая цикл ровно десять раз –

; остается выбрать ту, которая удобнее (с эстетической точки зрения)

; Никто же не будет утверждать, что

; for (a = 10; a > 0; a--) более

привычно чем for (a = 0; a < 10; a++)?

pop    esi

retn

main         endp

Листинг 194

А что скажет нам товарищ Borland C++ 5.0? Компилируем и смотрим:

_main        proc near           ; DATA XREF: DATA:00407044o

push   ebp

mov    ebp, esp

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

push   ebx

; Сохраняем EBX в стеке

xor    ebx, ebx

; Присваиваем регистровой переменной EBX

значение 0

loc_401082:                       ; CODE XREF: _main+15j

;                                      ^^^^^^^^^^^^^^^^^^^^^^

; Начало

цикла

push   offset aOperatorCiklaF ; format

call   _printf

pop    ecx

; Начинаем цикл с выполнения его тела

; OK, Borland

понял, что цикл выполняется по крайней мере раз

inc    ebx

; Увеличиваем параметр цикла

cmp    ebx, 0Ah

; Сравниваем EBX со значением 0xA

jl     short loc_401082

; Переход в начало цикла, пока EBX

< 0xA

xor    eax, eax

pop    ebx

pop    ebp

retn

_main        endp

Листинг 195

Видно, что Borland C++ 5.0 не дотягивает до Microsoft Visual C++ 6.0 – понять, что цикл выполняется один раз он понял, а вот реверс счетчика ума уже не хватило. Аналогичным образом поступает и большинство других компиляторов, в частности WATCOM C.

Теперь настала очередь циклов с условием в середине или циклов, завершаемых вручную оператором break. Рассмотрим следующий пример:

#include <stdio.h>

main()

{

int a=0;

while(1)

{

printf("1й оператор\n");

if (++a>10) break;

printf("2й оператор\n");

}

do

{

printf("1й оператор\n");



if (--a<0) break;

printf("2й оператор\n");

}while(1);

}

Листинг 196 Демонстрация идентификации break

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

main         proc near           ; CODE XREF: start+AFp

var_a        = dword      ptr -4

push   ebp

mov    ebp, esp

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

push   ecx

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

mov    [ebp+var_a], 0

; Присваиваем переменной var_a

значение 0х0

loc_40100B:                       ; CODE XREF: main+3Fj

;                                      ^^^^^^^^^^^^^^^^^^^^^

; Перекрестная ссылка, направленная вниз – цикл

mov    eax, 1

test   eax, eax

jz     short loc_401041

; Смотрите! Когда optimize disabled, - компилятор транслирует безусловный

; цикл "слишком буквально", т.к. присваивает EAX

значение 1 (TRUE)

; и затем педантично проверяет ее на равенство нулю

; Если в кои веки TRUE будет равно FALSE – произойдет выход из цикла

; Словом, все эти три инструкции – глупый и бесполезный код цикла

; while (1)

push   offset a1iOperator ; "1й оператор\n"

call   _printf

add    esp, 4

; printf("1й оператор\n")

mov    ecx, [ebp+var_a]

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

add    ecx, 1

; Увеличивем ECX на единицу

mov    [ebp+var_a], ecx

; Обновляем var_a

cmp    [ebp+var_a], 0Ah

; Сравниваем var_a

со значением 0xA

jle    short loc_401032

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

<= 0xA

; Но куда этот переход? Во-первых, переход направлен вниз, т.е. это уже

; не переход к началу цикла, следовательно и условие – не условие цикла, а

; результат компиляции конструкции IF – THEN

; Второе – переход прыгает на первую команду, следующую за безусловным

; jump loc_401041, передающим управление инструкции, следующей

; за командной jmp short loc_401075 – безусловного перехода, направленного

; вверх – в начало цикла



; Следовательно, jmp       short loc_401041 осуществляет выход из цикла, а

; jle short loc_401032 – продолжает его выполнение

jmp    short loc_401041

; ОК, - это переход на завершение цикла. А кто у нас завершает цикл?

; Ну, конечно же, break! Следовательно, окончательная декомпиляции выглядит так

; if (++var_a > 0xA) break

; Мы инвертировали "<=" в ">", т.к. JLE

передает управление на код продолжения

; цикла, а ветка THEN в нашем случае – на break

loc_401032:                       ; CODE XREF: main+2Ej

;                                      ^^^^^^^^^^^^^^^^^^^^^

; Перекрестная ссылка направлена вверх – следовательно, это не начало цикла

push   offset a2iOperator ; "2й оператор\n"

call   _printf

add    esp, 4

; printf("2й оператор\n")

jmp    short loc_40100B

; Прыжок в начало цикла. Вот мы и добрались до конца цикла

; Восстанавливаем исходный код:

; while(1)

; {

;      printf("1й оператор\n");

;      if (++var_a > 0xA) break;

;      printf("2й оператор\n");

;  }

;

loc_401041:                       ; CODE XREF: main+12j main+30j ...

;                                                            ^^^^^^^^^^

; Перекрестная ссылка, направленная вниз, говорит, что это начало цикла

push   offset a1iOperator_0 ; "1й оператор\n"

call   _printf

add    esp, 4

; printf("1й оператор\n")

mov    edx, [ebp+var_a]

sub    edx, 1

mov    [ebp+var_a], edx

; --var_a

cmp    [ebp+var_a], 0

; Сравниваем var_a со значением 0x0

jge    short loc_40105F

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

>= 0

; Смотрите: оператор break цикла do ничем не отличается от break цикла while!

; Поэтому, не будем разглагольствовать, а сразу его декомпилируем!

; if (var_a < 0) …

jmp    short loc_401075

; …break

loc_40105F:                       ; CODE XREF: main+5Bj

push   offset a2iOperator_0 ; "2й оператор\n"



call   _printf

add    esp, 4

; printf("2й оператор\n")

mov    eax, 1

test   eax, eax

jnz    short loc_401041

; А это – проверка продолжения цикла

loc_401075:                       ; CODE XREF: main+5Dj

mov    esp, ebp

pop    ebp

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

retn

main         endp

Листинг 197

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

Давайте откомпилируем тот же самый пример компилятором Microsoft Visual C++ 6.0 с ключом "/Ox" и посмотрим:

main         proc near           ; CODE XREF: start+AFp

push   esi

; Сохраняем ESI в стеке

xor    esi, esi

; Присваиваем ESI значение 0

; var_ESI = 0;

loc_401003:                       ; CODE XREF: main+23j

;                                      ^^^^^^^^^^^^^^^^^^^^^

; Перекрестная ссылка, направленная вперед

; Это – начало цикла

push   offset a1iOperator

; "1й оператор\n"

call   _printf

add    esp, 4

; printf("1й оператор\n")

;

; Ага! Проверки на дорогах нет, значит, это цикл с постусловием

; (или условием в середине)

inc    esi

; ++var_ESI

cmp    esi, 0Ah

; Сравниваем var_ESI

со значением 0xA

jg     short loc_401025

; Выход из цикла, если var_ESI

> 0xA

; Поскольку, данная команда – не последняя в теле цикла,

; это цикл с условием в середине

; if (var_ESI > 0xA) break

push   offset a2iOperator ; "2й оператор\n"

call   _printf

add    esp, 4

; printf("2й оператор\n")

jmp    short loc_401003

; Безусловный переход в начало цикла

; Как видно, оптимизирующий компилятор выкинул никому ненужную проверку

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



; Итак:

; var_ESI = 0

; for (;;)          ß

вырожденный for

представляет собой бесконечный цикл

; {

;      printf("1й оператор\n");

;      ++var_ESI;

;      if (var_ESI > 0xA) break;

;      printf("2й оператор\n");

; }

loc_401025:                       ; CODE XREF: main+14j

;                                      ^^^^^^^^^^^^^^^^^^^^^

; Это не начало цикла!

push   offset a1iOperator_0 ; "1й оператор\n"

call   _printf

add    esp, 4

; printf("1й оператор\n")

; Хм, как же это не начало цикла?! Очень похоже!

dec    esi

; --var_ESI

js     short loc_401050

; Выход из цикла, если var_ESI

< 0

inc    esi

; Увеличиваем var_ESI

на единицу

; М–м-м… (задумчиво)…

loc_401036:                       ; CODE XREF: main+4Ej

;                                      ^^^^^^^^^^^^^^^^^^^^^^

; А вот это начало цикла!

push   offset a2iOperator_0 ; "2й оператор\n"

call   _printf

; printf("2й оператор\n")

; Только странно, что начало цикла начинается с его, с позволения сказать,

; середины…

push   offset a1iOperator_0 ; "1й оператор\n"

call   _printf

add    esp, 8

; printf("1й оператор\n")

;

; ???!!! Что за чудеса творятся? Во-первых, вызов первого оператора второго

; цикла уже встречался ранее, во-вторых, не может же следом за серединой цикла

; следовать его начало?!

dec    esi

; --var_ESI

jnz    short loc_401036

; Продолжение цикла, пока var_ESI

!= 0

loc_401050:                       ; CODE XREF: main+33j

; Конец цикла

; Да… тут есть над чем подумать!

; Компилятор нормально "перевалил" первую строку цикла

; printf("1й оператор\n")

; а затем "напоролся" на ветвление:

; if

(--a<0) break

; Хитрые парни из Microsoft знают, что для супер - конвейерных процессоров

; (коими и являются чипы Pentium) ветвления все равно, что чертополох для



; Тиггеров. Кстати, Си-компиляторы под процессоры серии CONVEX

вообще

; отказываются компилировать циклы с ветвлениями, истощенно понося

; умственные способности программистов. А вы еще IBM PC

ругаете ;-)

; Вот и приходится компилятору исправлять ляпы программиста, что он делать

; в принципе не обязан, но за что ему большое человеческое спасибо!

; Компилятор как бы "прокручивает" цикл, "слепляя" вызовы функций printf

; и вынося ветвления в конец

; Образно исполняемый код можно представить трассой, а процессор – гонщиком

; Чем длиннее участок дороги без поворотов, тем быстрее его проскочит гонщик!

; Выносить условие из середины цикла в его конец компилятор вполне правомерен,

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

; не модифицируется ни функцией printf, ни какой другой

; Поэтому, не все ли равно где ее проверять? Конечно же не все равно!!!

; К моменту когда условие (--a < 10) становится истинно, успевает выполниться

; первый printf, а вот второй – уже не получает управления

; Вот для этого-то компилятор и поместил код проверки условия следом за

; первым вызовом первой функции printf, а затем изменил порядок вызова

; printf

в теле цикла. Это привело к тому, что на момент выхода из цикла

; по условию первый printf выполняется на один раз больше, чем второй

; (т.к. он встречается дважды)

; Остается разобраться с увеличением var_ESI – что бы это значило?

; Давайте рассуждать от противного: что произойдет, если выкинуть

; команду INC ESI? Поскольку, счетчик цикла при первой итерации цикла

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

; короче. Что бы этого не произошло, var_ESI искусственно увеличивается

; на единицу

; Ой, и не просто во всей этой головоломке разобраться, а представьте:

; насколько сложно реализовать компилятор, умеющий проделывать такие фокусы!

; А еще кто-то ругает автоматическую оптимизацию. Да уж! Конечно, руками-то

; можно и круче оптимизировать(особенно понимания смысл кода), но ведь эдак



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

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

; прилично окультурить

pop    esi

retn

main         endp

Листинг 198

Компиляторы Borland C++ и WATCOM при трансляции бесконечных циклов заменяют код проверки условия продолжения цикла на безусловный переход, но вот, увы, оптимизировать ветвления, вынося их в конец цикла так, как это делает Microsoft Visual C++ 6.0 они не умеют…

Теперь, после break, рассмотрим: как компиляторы транслирует его "астральный антипод", - оператор continue. Возьмем следующий пример:

#include <stdio.h>

main()

{

int a=0;

while (a++<10)

{

if (a == 2) continue;

printf("%x\n",a);

}

do

{

if (a == 2) continue;

printf("%x\n",a);

} while

(--a>0);

}

Листинг 199 Демонстрация идентификации continue

Результат его компиляции компилятором Microsoft Visual C++ 6.0 с настройками по умолчанию будет выглядеть так:

main         proc near           ; CODE XREF: start+AFp

var_a        = dword      ptr -4

push   ebp

mov    ebp, esp

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

push   ecx

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

mov    [ebp+var_a], 0

; Присваиваем локальной переменной var_a значение 0

loc_40100B:                       ; CODE XREF: main+22j main+35j

;                                                  ^^^^^^^^^^^^^^^^^^^

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

; начало двух циклов (один из которых – вложенный), либо переход в начало

; цикла

оператором

continue

mov    eax, [ebp+var_a]

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

mov    ecx, [ebp+var_a]

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

add    ecx, 1

; Увеличиваем ECX на единицу

mov    [ebp+var_a], ecx   

; Обновляем переменную var_a

cmp    eax, 0Ah

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



jge    short loc_401037

; Выход из цикла ( переход на команду, следующую за инструкцией, направленной

; вверх – в начало цикла) если var_a >= 0xA

cmp    [ebp+var_a], 2

; Сравниваем var_a

со значением 0x2

jnz    short loc_401024

; Если var_a

!= 2, то прыжок на команду, следующую за инструкцией

; безусловного перехода, направленной вверх – в начало цикла

; Очень похоже на условие выхода из цикла, но не будет спешить с выводами!

; Вспомним – в начале цикла нам встретились две перекрестные ссылки

; Безусловный переход "jmp short loc_40100B" как раз образует одну из них

; А кто "отвечает" за другую?

; Чтобы ответить на этот вопрос необходимо проанализировать остальной код цикла

jmp    short loc_40100B

; Безусловный переход, направленный в начало цикла – это либо конец цикла,

; либо continue

; Предположим, что это конец цикла. Тогда что же представляет собой

; "jge short loc_401037"? Предусловие выхода из цикла? Не похоже – в таком

; случае они прыгало бы гораздо "ближе" – на метку loc_401024

; А может, "jge short loc_401037" предусловие одного цикла, а

; "jnz short loc_401024" – постусловие другого, вложенного в него?

; Вполне возможно, но маловероятно – в этом случае постусловие представляло бы

; собой условие продолжения, а не завершения цилкла

; Поэтому, с некоторой долей неуверенности, мы можем принять конструкцию

; CMP var_a, 2 \ JNZ loc_401024 \ JMP loc_40100B за if (a==2) continue

loc_401024:                       ; CODE XREF: main+20j

mov    edx, [ebp+var_a]

push   edx

push   offset asc_406030 ; "%x\n"

call   _printf

add    esp, 8

; printf("%x\n",var_a)

jmp    short loc_40100B

; А вот это – явно конец цикла, т.к. jmp short loc_40100B – самая

; последняя ссылка на начало цикла

; Итак, подытожим, что мы имеем:

; Условие, расположенное в начале цикла, крутит этот цикл до тех пор, пока

; var_a < 0xA, причем инкремент параметра цикла происходит до его сравнения



; Затем следует еще одно условие, возвращающее управление в начало цикла, если

; var_a == 2. Строй замыкает оператор цикла printf

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

; начало. Т.е.

;

; Начало цикла:             <-----------! <--!

; Инкремент переменной var_a            !    !

; условие "далекого" выхода -------!    !    !

; условие "ближнего" продолжения --)----!    !

; тело цикла                       !         !

; безусловный переход в начало ----)---------!

; конец цикла                 <----!

;

; Условие "ближнего" продолжение не может быть концом цикла, т.к. тогда условию

; "далекого" выхода пришлось выйти аж из надлежащего цикла, на что ни break,

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

; может быть только оператором continue

и на языке Си всю эту конструкция

; будет выглядеть так:

; while(a++<10)            // <-- инкремент var_a и условие далекого выхода

; {

;      if (a == 2) continue;      // <-- условие ближнего продолжения

;      printf(%x\n",var_a);       // <-- тело цикла

; }                        // <-- безусловный переход на начало цикла

loc_401037:                       ; CODE XREF: main+1Aj main+5Dj

;                                                            ^^^^^^^^^

; Начало цикла

cmp    [ebp+var_a], 2

; Сравниваем переменную var_a

со значением 0x2

jnz    short loc_40103F

; Если var_a

!= 2, то продолжение цикла

jmp    short loc_401050

; Переход к коду проверки условия продолжения цикла

; Это бесспорно "continue" и вся конструкция выглядит так:

; if (a==2) continue

loc_40103F:                       ; CODE XREF: main+3Bj

mov    eax, [ebp+var_a]

push   eax

push   offset asc_406034 ; "%x\n"

call   _printf

add    esp, 8

; printf("%x\n", var_a)

loc_401050:                      ; CODE XREF: main+3Dj

mov    ecx, [ebp+var_a]

sub    ecx, 1



mov    [ebp+var_a], ecx

; --var_a

cmp    [ebp+var_a], 0

; Сравнение var_a

с нулем

jg     short loc_401037

; Пока var_a

> 0 продолжать цикл. Похоже на постусловие верно? Тогда:

; do

; {

;      if (a==2) continue;

;      printf("%x\n", var_a);

; } while (--var_a > 0);

;

mov    esp, ebp

pop    ebp

retn

main         endp

Листинг 200

А теперь посмотрим, как повлияла оптимизация ("/Ox") на вид циклов:

main         proc near           ; CODE XREF: start+AFp

push   esi

mov    esi, 1

loc_401006:                       ; CODE XREF: main+1Fj

;                                       ^^^^^^^^^^^^^^^^^^^^

; Начало цикла

cmp    esi, 2

jz     short loc_401019

; Переход на loc_401019, если ESI == 2

push   esi

push   offset asc_406030 ; "%x\n"

call   _printf

add    esp, 8

; printf("%x\n", ESI)

; Прим: эта ветка выполняется только если ESI

!=2

; Следовательно, ее можно изобразить так:

; if (ESI != 2) printf("%x\n", ESI)

loc_401019:                       ; CODE XREF: main+9j

mov    eax, esi

inc    esi

; ESI++;

cmp    eax, 0Ah

jl     short loc_401006

; Продолжение цикла пока (ESI++ < 0xA)

; Итого:

; do

; {

;      if (ESI != 2) printf("%x\n", ESI);

; } while (ESI++ < 0xA)

;

; А что, выглядит вполне читабельно, не правда ли? Ни чуть не хуже, чем

; if (ESI == 2) continue

;

loc_401021:                       ; CODE XREF: main+37j

;                                                   ^^^^^^^^

; Начало цикла

cmp    esi, 2

jz     short loc_401034

; Переход на loc_401034, если ESI == 2

push   esi

push   offset asc_406034 ; "%x\n"

call   _printf

add    esp, 8

; printf("%x\n",ESI);

; Прим. эта ветка выполняется лишь когда ESI

!= 2

loc_401034:                       ; CODE XREF: main+24j

dec    esi

; --ESI

test   esi, esi

jg     short loc_401021



; Условие продолжение цикла – крутить кака ESI

> 0

; Итого:

; do

; {

;      if (ESI != 2)

;      {

;            printf("%x\n", ESI);

;      }

 

; } while (--ESI > 0)

;

pop    esi

retn

main         endp

Листинг 201

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

практически неотличим от вложенного цикла, а на циклах с постусловием continue эквивалентен элементарному ветвлению.

Наконец, настала очередь циклов for, вращающих несколько счетчиков одновременно. Рассмотрим следующий пример:

main()

{

int a; int b;

for (a = 1, b = 10; a < 10, b > 1; a++, b --)

printf("%x %x\n", a, b);

}

Листинг 202 Демонстрация идентификации циклов for с несколькими счетчиками

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

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

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

mov    [ebp+var_a], 1

; Присваиваем переменной var_a

значение 0x1

mov    [ebp+var_b], 0Ah

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

значение 0xA

jmp    short loc_401028

; Прыжок на код проверки условия выхода из цикла

; Это характерная черта не оптимизированных циклов for

loc_401016:                       ; CODE XREF: main+43j

;                                                  ^^^^^^^^^

; Перекрестная ссылка, направленная вниз, говорит о том, что это – начало цикла

; А выше мы уже выяснили, что тип цикла - for

mov    eax, [ebp+var_a]

add    eax, 1

mov    [ebp+var_a], eax

; var_a++

mov    ecx, [ebp+var_b]

sub    ecx, 1

mov    [ebp+var_b], ecx

; var_b--

loc_401028:                       ; CODE XREF: main+14j

cmp    [ebp+var_b], 1



jle    short loc_401045

; Выход из цикла, если var_b

<= 0x1

; Обратите внимание: выполняется проверка лишь одного (второго слева) счетчика!

; Выражение (a1,a2,a3,…an) компилятор считает бессмысленным и берет лишь an

; молчаливо отбрасывая все остальное

; (из известных мне компиляторов на это ругается один WATCOM)

; В данном случае проверяется лишь условие (b

> 1), а (a

< 10) игнорируется!!!

mov    edx, [ebp+var_b]

push   edx

mov    eax, [ebp+var_a]

push   eax

push   offset aXX   ; "%x %x\n"

call   _printf

add    esp, 0Ch

; printf("%x %x\n", var_a, var_b)

jmp    short loc_401016

; Конец цикла

; Итак, данный цикл можно представить как:

; while(1)

; {

;      var_a++;

;      var_b--;

;      if (var_b <= 0x1) break;

;      printf("%x %x\n", var_a, var_b)

; }

;

; Но по соображениям удобочитаемости имеет смысл скомпоновать это код в for

; for (var_a=1,var_b=0xA;var_b>1;var_a++,var_b--) printf("%x %x\n",var_a,var_b)

;

loc_401045:                       ; CODE XREF: main+2Cj

mov    esp, ebp

pop    ebp

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

retn

main         endp

Листинг 203

Оптимизированный вариант программы рассматривать не будем, т.к. это не покажет нам ничего нового. Какой бы компилятор мы не выбрали – выражения инициализации и модификации счетчиков будут обрабатываться вполне корректно в порядке их объявления в тексте программы, а вот множественные выражения продолжения цикла не умеет правильно обрабатывать ни один компилятор!


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







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий