Фундаментальные основы хакерства. Определяем циклы в двоичном коде программы - «Новости»

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

Су­щес­тву­ют три основных типа цик­ла:

1. 
   

   Цик­лы с усло­вием в начале.

   
   
   
   
   


2. 
   

   Цик­лы с усло­вием в кон­це.

   
   
   
   
   


3. 
   

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

   
   
   
   
   

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

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

Та­ким обра­зом, со сто­роны тран­сля­тора впол­не дос­таточ­но под­дер­жки усло­вий одно­го типа. И дей­стви­тель­но, опе­рато­ры цик­лов while, do и for язы­ка С/C++ работа­ют исклю­читель­но с усло­виями про­дол­жения цик­ла. Опе­ратор while язы­ка Delphi так­же работа­ет с усло­вием про­дол­жения, и исклю­чение сос­тавля­ет один лишь repeat-until, ожи­дающий усло­вие завер­шения цик­ла.

Циклы с условиями в начале

Их так­же называ­ют цик­лами с пре­дус­лови­ем. В язы­ках С/C++ и Delphi под­дер­жка цик­лов с пре­дус­лови­ем обес­печива­ется опе­рато­ром while (условие), где условие — это усло­вие про­дол­жения цик­ла. То есть цикл while (a < 10) a++; выпол­няет­ся до тех пор, пока усло­вие (a>10) оста­ется истинным. Одна­ко тран­сля­тор при желании может инверти­ровать усло­вие про­дол­жения цик­ла на усло­вие его завер­шения. На плат­форме Intel 80x86 такой трюк эко­номит от одной до двух машин­ных команд.

Об­рати вни­мание: ниже при­веден цикл с усло­вием завер­шения цик­ла.

А далее — с усло­вием про­дол­жения цик­ла.

Как вид­но на кар­тинках, цикл с усло­вием завер­шения на одну коман­ду короче! Поэто­му прак­тичес­ки все ком­пилято­ры (даже неоп­тимизи­рующие) всег­да генери­руют пер­вый вари­ант. А некото­рые осо­бо ода­рен­ные даже уме­ют прев­ращать цик­лы с пре­дус­лови­ем в еще более эффектив­ные цик­лы с пос­тусло­вием (см. пункт «Цик­лы с усло­вием в кон­це»).

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

Циклы с условием в конце

Их так­же называ­ют цик­лами с пос­тусло­вием. В язы­ке С/C++ под­дер­жка цик­лов с пос­тусло­вием обес­печива­ется парой опе­рато­ров do … while, а в язы­ке Delphi — repeat … until. Цик­лы с пос­тусло­вием без каких‑либо проб­лем непос­редс­твен­но отоб­ража­ются с язы­ка высоко­го уров­ня на машин­ный код и наобо­рот. То есть, в отли­чие от цик­лов с пре­дус­лови­ем, инверсии усло­вия не про­исхо­дит.

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

Срав­ним код цик­ла с пос­тусло­вием и код цик­ла с пре­дус­лови­ем. Не прав­да ли, цикл с усло­вием в кон­це ком­пак­тнее и быс­трее? Некото­рые ком­пилято­ры (нап­ример, Microsoft Visual C++) уме­ют тран­сли­ровать цик­лы с пре­дус­лови­ем в цик­лы с пос­тусло­вием. На пер­вый взгляд, это вопи­ющая самоде­ятель­ность ком­пилято­ра — если прог­раммист хочет про­верять усло­вие в начале, то какое пра­во име­ет тран­сля­тор ста­вить его в кон­це?

На самом же деле раз­ница меж­ду «до» и «пос­ле» не столь зна­читель­на. Если ком­пилятор уве­рен, что цикл выпол­няет­ся хотя бы один раз, то он впра­ве выпол­нять про­вер­ку ког­да угод­но. Разуме­ется, при этом необ­ходимо нес­коль­ко скор­ректи­ровать усло­вие про­вер­ки: while (a<b) не экви­вален­тно do ... while (a<b), так как в пер­вом слу­чае при (a == b) уже про­исхо­дит выход из цик­ла, а во вто­ром — цикл выпол­няет еще одну ите­рацию. Одна­ко этой беде лег­ко помочь: уве­личим а на еди­ницу (do ... while ((a+1)<b)) или выч­тем эту еди­ницу из b (do ... while (ab-1))), и... теперь все будет работать!

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