На початку було слово, а точніше ідея або ... до проектування приступити.
При написанні однієї програми, що обчислює кросворди судоку, спочатку виникла необхідність у
вкладених циклах глибиною п'ять, а потім аж навіть о дев'ятій
циклів. Тут-то і виникла потреба в
оптимізації. Тим більше що остаточний варіант з полегшено-спрощеними алгоритмом (з одного боку) містив вже ... двадцять сім
вкладених циклів. Крім того, у Паскаля від дядька Бормана, починаючи c Turbo Pascal'я і аж до самих Дельфах, в ролі індексу зовсім можна юзати масив. Тобто якщо ваш цикл досить-таки глибокий, наприклад, аж у 5
поверхів, то ви повинні для кожного вкладення свою змінну використовувати.
Тобто в розділі опису пишемо, наприклад, так:
Var i1, i2, i3, i4, i5. byte;
А в розділі виконання відповідно:
For i1: = 1 to 2 do
For i2: = 1 to 3 do
For i3: = 1 to 4 do
For i4: = 1 to 5 do
For i5: = 1 to 6 do SomeProcedure;
Дану алгоритмічну аномалію і будемо автоматизувати. Крім того, уявіть собі циклу-монстра,
у якого 27 вкладень!
Для даного наукового дослідження в ролі молотка з цвяхами нам знадобиться всього нічого: Turbo Pascal і Turbo Debugger for Dos - вистачить хоч греблю гати. Крім того, до інструменту потрібні
дрова у вигляді ваших прямих ручок і голови з якісним сірою речовиною (вміння молитися богу Паскалю написанням відповідного коду як мінімум вітається теж).
Перш за все, щоб дані не гуляли самі по собі, а процедури і функції теж не нудьгували десь,
і ті, і інші об'єднаємо під прапором ООП.
Перш за все починаємо проектувати наш об'єкт. Але, щоб стало відразу ясно, «малюємо» відповідну схему. Нехай в ролі піддослідного кролика буде цикл глибиною п'ять:
For i [1]: = Dn [1] to Up [1] do
For i [2]: = Dn [2] to Up [2] do
For i [3]: = Dn [3] to Up [3] do
For i [4]: = Dn [4] to Up [4] do
For i [5]: = Dn [5] to Up [5] do MainProc;
Які запчастини для нашого об'єкта звідси вже можна вкрасти? Це індексна змінна (точніше масив) i, нижня межа - масив Dn, а верхня, відповідно Up і процедура MainProc, яка і є процедурою, багаторазово використовуваної нашим циклом. Крім того, з огляду на те, що досить-таки важко придумати короткий і точна назва, цю процедуру ми і назвемо головною (тим більше що для неї весь цей сир-бор і намічається), що і відображено в її назві MainProc.
У Турбо Паскалі відкривайте бібліотеку, в якій наш об'єкт живе, і поїхали розбиратися, що в ньому почому.
Ось і опис об'єкта:
TLoopRunner = object
i, Dn, Up. TByteArray10;
Depth. byte;
MainProcAddr: Pointer;
ParamsStackIndex: byte;
RunItProcOfs: word;
CallCodeOfProcToLoopOfs: word;
Constructor Init (SomeProcAddr: Pointer;
SomeDepth: byte;
SomeDn, SomeUp: TByteArray10);
Procedure RunIt; virtual;
End;
Тепер, що за дивні слова TByteArray10 і Pointer з'явилися в нашому писанні? Це просто. У розділі типів, тобто Type, TByteArray10 описаний як масив з десяти
байт:
TByteArray10 = array [1..10] of byte;
Тепер, потрібно про дії, які і перетворюють наш об'єкт в багатовимірний цикл. Спочатку про конструктора. Хоча, за великим рахунком, можна було обійтися простою процедурою, але так як ця процедура повинна виконуватися першою, то вона і наділена статусом конструктора. А ім'я теж стандартне, як і у всіх його братів-конструкторів, тобто
Init:
Constructor Init (SomeProcAddr: Pointer; SomeDepth:
byte; SomeDn, SomeUp: TByteArray10);
Далі ще одну дію, в якому наш цикл і знаходиться. Називається він RunIt, тобто виконати. Параметрів у нього не буде - вони йому не потрібні, зате воно буде віртуальним і не тому, що це модно, а тому, що це спростить нашу роботу по пожвавленню нашого ж об'єкта:
Procedure RunIt; virtual;
Procedure PushParam (AParamAddr: Pointer; AParamType: TParametersTypes);
До речі, а які можуть бути параметри, передані в процедуру або функцію? Щоб не ламати голову, перераховуємо стандартні, додаючи до кожного назвою префікс pt (бо TParametersTypes). Дане перерахування якраз і знаходиться в розділі типів нашої бібліотеки:
TParametersTypes = (ptByte, ptShortInt, ptWord, ptInteger, ptLongInt, ptReal, ptString, ptArray);
Перефразовуючи одного персонажа, можна сказати: «Ми проектували, проектували і нарешті спроектували. ». Що тут додати, крім простого «да уж»?
В процесі інкарнації
Тепер від квіточок до ягідка, тобто розглядаємо, як це все господарство реалізовано і працює.
Перш за все, тіло нашого багатоповерхового циклу знаходиться в процедурі RunIt, яка, до речі, як і всі порядні процедури, описана в розділі втілень, тобто після слова implementation. Причому відразу зверніть увагу, що чарівне слово virtual пішло, а замість нього прийшло не менше чарівне слово assembler, а місце слова begin зайняло слово asm - процедура зроблена з чистого асма:
Procedure TLoopRunner.RunIt; assembler;
Asm
End;
Крім того, сама процедура по суті складається з одинадцяти (десять - наші вкладені цикли, а одинадцятий - код виклику головною процедури MainProcAddr. До речі, приводити все десять просто немає сенсу - вони однотипні, є хіба що ньюанси в першому і в десятому. Щоб показати як відбувається перехід від одного циклу до іншого, на додаток до першої подпрограмме взята друга.), як раніше говорили, підпрограм, і ми теж будемо називати ці частини так.
Тепер розглянемо код, яким наша процедура RunIt викликається (до речі, код був отриманий з відладчика Turbo Debugger):
Повертаємо з стека значення bp, яке
ми зберегли в ньому при вході в процедуру.
Якщо ви заглянете на наступні поверхи, то побачите майже один і той же код. Відмінності ж будуть в «добавках» для
регістра di, щоб отримати відповідні зміщення для доступу до всіх елементів масивів i, Dn і Up. Наприклад, для другого поверху це будуть відповідно числа 2, 0Сh і 16h. Крім того, на всіх інших поверхах ми повертаємося на попередній не довгим поверненням, тобто НЕ retf'ом, а просто ret'ом, тому що ми знаходимося всі в тій же процедурі RunIt, що означає - у тому ж самому сегменті коду, тому для повернення ми повинні змінювати тільки значення регістра ip, а cs не чіпати. Крім того, для повернення з поверху ми повинні писати не мнемонічний код інструкції повернення, тобто НЕ ret, а код цієї інструкції - db 0C3h. Тут, очевидно, що через те, що процедура RunIt оголошена як асемблерна, то Паскаль по імені Турбо вважає все ret'и довгими і встромляє
відповідний код довгого повернення (можете переконається в цьому самі, помінявши де-небудь db 0C3h на ret).
І окреме слово про поверсі десятому. Якщо, наприклад, з першого поверху на другий ми переходимо по «драбинці» call @@ Loop02_Begin, то над десятим поверхом вже нічого немає, тому з десятого ми просто відразу ж повертаємося на дев'ятий за рахунок коду інструкції ret, тобто 0С3h (після цієї інструкції йдуть ще два nop'a, тобто разом з кодом повернення отримуємо 3 байта - якраз те, що треба, щоб вписати в це місце, якщо знадобиться, інструкцію виклику головною процедури. А навіщо це треба - дізнаєтеся нижче).
Покажи цю статтю друзям: