В начале было слово, а точнее идея или … к проектированию приступить.
При написании одной программы, вычисляющей кроссворды судоку, сначала возникла необходимость во
вложенных циклах глубиной пять, а потом аж даже в девять
циклов. Тут-то и возникла потребность в
оптимизации. Тем более что окончательный вариант с облегченно-упрощенным алгоритмом (с одной стороны) содержал уже… двадцать семь
вложенных циклов. Кроме того, у Паскаля от дяди Бормана, начиная 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;
Тогда уже наши i, Dn и Up – массивы по десять байт в каждом. Тогда возникает законный вопрос - кто такой MainProcAddr и почему он Pointer, а не как-нибудь иначе? Дело в том, что MainProcAddr - адрес главной процедуры, т.е. той самой, которую наш цикл и будет
мучать многократным исполнением, а адрес - он и есть Pointer или указатель (забегая немножко вперед, скажу, что Pointer состоит из двух слов, т.е. word’ов, один из которых сегмент, а другой - смещение). И чуть не забыли про Depth. Это глубина нашего цикла. (Остальные три поля ParamsStackIndex, RunItProcOfs и CallCodeOfProcToLoopOfs пока не трогаем – о них дальше, по ходу
повествования).
Теперь, нужно о действиях, которые и превращают наш объект в многомерный цикл. Сначала о конструкторе. Хотя, по большому счету, можно было обойтись простой процедурой, но так как эта процедура должна выполняться первой, то она и наделена статусом конструктора. А имя тоже стандартное, как и у всех его братьев-конструкторов, т.е.
Init:
Constructor Init (SomeProcAddr:Pointer; SomeDepth:
byte; SomeDn, SomeUp: TByteArray10);
Теперь о друзьях-параметрах нашего конструктора (т.е. тех, что в скобках после слова Init): SomeProcAddr – адрес некоторой процедуры, который будет передаваться в объект для многократного юзанья; SomeDepth – глубина; SomeDn, SomeUp – массивы верхних и нижних границ индекса цикла.
Дальше еще одно действие, в котором наш цикл и находится. Называется он RunIt, т.е. выполнить. Параметров у него не будет – они ему не нужны, зато оно будет виртуальным и не потому, что это модно, а потому, что это упростит нашу работу по оживлению нашего же объекта:
Procedure RunIt; virtual;
И еще одно. Но сначала - небольшое отступление. Дело в том, что в большинстве случаев процедуры и функции для своих действий требуют соответствующих данных, которые через параметры в процедуру или функцию передаются. У нас же на текущий момент есть только адрес процедуры. Поэтому нам нужно действие, которое будет нашей главной процедуре подсовывать данные. Дело в том, что, опять же забегая вперед, данные в процедуру или функцию передаются через стэк, а в стэк они помешаются ассемблерной инструкцией PUSH.
Процедура, которая подсовывает данные главной
функции, называется PushParam, т.е. затолкнуть параметр. Соответственно, у этой процедуры свои два параметра – это адрес параметра и его тип:
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. У нее параметров нет, но это только так кажется. На самом деле есть один параметр, который передается неявно, но все равно через стэк и этот параметр – адрес нашего экземпляра объекта. Вы, возможно, спросите – зачем? Здесь все просто – нам нужен адрес объекта для доступа на низком уровне (т.е. на уровне ассемблера) к данным или полям объекта. А если быть более точным, к массивам i, Dn и Up (если вы уже забыли, кто они и что они, то i – массив-счетчик всех наших циклов, Dn – массив, нижняя граница счетчика, т.е. от каких значений начинаем плясать, а Up, соответственно, - до каких).
Теперь рассмотрим код, которым наша процедура RunIt вызывается (кстати, код был получен из отладчика Turbo Debugger):
mov di, 00D6h |
Поместить в регистр di шестнадцатеричное число 00D6h (два первых нуля можно было не писать, но они есть, чтобы показать, что пересылаются именно 16 двоичных разрядов, что и составляет 4 разряда шестнадцатеричных). Теперь, что сие означает. А означает это то, что после выполнения этой инструкции в регистре di та часть адреса нашего объекта, которая называется смещением |
push dspush |
Помещаем в стэк значение регистра ds – ту часть адреса нашего объекта, которая называется сегментом |
push di |
Загоняем в стэк значение смещения из регистра di – теперь у нас в стэке и сегмент, и смещение нашего объекта. |
mov di, [di + |
Взять слово, т.е. word, по адресу (квадратные скобки как раз и указывают, что «взять по адресу»), сегмент которого в регистре ds (т.е. если регистр не указывается, то, по-умолчанию, это ds), а смещение получить сложением числа 28h и значения регистра di. Должен возникнуть законный вопрос, а почему именно 28h, а не 29h или даже 30h. Здесь все тоже очень просто: адрес самого объекта находится по адресу в регистрах ds:[di] (квадратные скобки опять говорят о том, что речь идет об адресе), а таблица виртуальных методов объекта - по адресу ds:[di + 28h]. Точнее, таблица этих самых методов находится после всех данных объекта, т.е. после i, Dn, Up, Depth. Но если вы сложите вместе размеры i, Dn, Up, Depth, вы 28h не получите никак, потому что по ходу нашего повествования мы будем добавлять еще поля в объект, а данный код взят из окончательного варианта. |
call far [di + 8] |
Произвести дальний (слово far с английского как раз и переводится как дальний) вызов процедуры по адресу, сегмент которого взят из ds, а смещение взято прибавлением 8 к значению из регистра di. Опять должен возникнуть вопрос – почему 8 и никак иначе. Тут тоже все очень просто. В таблице виртуальных методов, коим наш RunIt и является, находятся адреса и других процедур, т.е. Init и PushParam (которые, кстати, виртуальными не являются, а таблица все же называется таблицей виртуальных методов). Init – первая в описании объекта и она первая, соответственно, в таблице, кроме того, она дальняя, т.к. объект описан в отдельном модуле. Соответственно, первые четыре байта таблицы (два на сегмент и два на смещение ), т.е. от 0-го до 3-го – адрес метода Init, а байты с 4-го по 7-ой – адрес метода PushParam. Тогда еще 4-ка байтов, начиная с 8-го - адрес процедуры RunIt. |
Перед тем как…
Разбираемся с кодом-предисловием, который у нас в наличии перед первой подпрограммой. Перед тем как вызвать RunIt, в стэк загоняется адрес нашего объекта, а соответственно, теперь нам нужно его оттуда извлечь. Делается это строкой кода les di, self, т.е. загрузить пару регистров es и di (сегмент в es, а смещение в di) адресом из параметра self - адреса нашего объекта. Но в отладчике, кстати, вместо этой строки будет строка les di, [bp + 06], а перед ней еще четыре, которые компилятор сам воткнул без нашего ведома:
push bpmov |
Сохранить в стэке значение регистра bp |
mov bp, sp |
Поместить значение регистра sp в регистр |
xor ax, ax |
Взять значение регистра ax и к нему применить операцию ИСКЛЮЧАЮЩЕЕ ИЛИ (если для этой операции взять два одинаковых числа, а у нас ax и ax, то в итоге получим нуль) |
call 1A44: 0530 |
Вызвать процедуру по адресу 1A44: 0530 (зачем это нужно – загадка природы) |
Вообще же для доступа к параметрам, записанным в стэк – переданным
процедурой или функцией, используется регистр bp, поэтому его сначала нужно сохранить в стэке, а затем записать в него значение регистра указателя стэка, т.е. sp.
Дальше, если вы в отладчике после входа в процедуру RunIt обратите внимание на окошко со стэком, то увидите примерно следующее:
ss:3FFC 1B00 |
Здесь вершина стэка или значение указателя стэка 3FF6 (на то указует «птичка» - >). Так вот, в вершине стэка и в следущем слове, т.е. выше, находится смещение и сегмент адреса возврата из процедуры RunIt и он туда был помещен при выполнении команды call far [di + 8], т.е. при вызове процедуры RunIt. |
Следующие же два слова (т.е. двигаясь снизу вверх) - 00D6 и 1B00 как раз и есть адрес нашего объекта: смещение и сегмент. Таким образом, инструкцию les di, [bp+6] можно «пояснить» и так: первая - mov di, ss:[bp + 6] – записать слово по адресу ss:[bp+6] в регистр di, т.е. смещение нашего объекта в регистр di, вторая - mov es, ss:[bp + 8] – записать слово по адресу ss:[bp+8] в регистр es, т.е. сегмент нашего объекта в регистр es (кстати, так сделать нельзя – а почему – домашнее задание).
Кстати, опять нескромный вопрос – почему 6 и 8? Дело в следующем: значение bp равно значению sp, поэтому, чтобы получить смещение нашего объекта - 00D6, мы прибавляем 6, а для сегмента, т.е. для 1B00, берем 8. Вот и все предисловие. Возможно, это покажется замудренным-затуманенным – но, как говорится, трудно в учении, легко в кодинге.
На первом этаже
Двигаемся дальше – рассматриваем работу первой подпрограммы. Вот и ее код:
dec di |
Уменьшаем значение di на 1, чтобы в отладчике видеть, на каком «этаже» цикла мы находимся. |
@@Loop01_Begin: |
Эта строка – просто метка (можно было и не писать – по ней вызова не происходит – так, разве что для общего развития ) |
mov al,es:[di+0Bh] |
В регистр al (он восьмиразрядный, т.е. в один байт) записываем значение первого элемента массива нижних границ, т.е. Dn[1], который находится по адресу es:[di + 0Bh] (зачем, точнее почему, он там находится, вы уже должны разобраться сами) |
mov es:[di+1],al |
Теперь байт из регистра al записываем по адресу es:[di+1], т.е. в первый элемент массива i (почему так – уже не говорю). Данным двум строкам соответствует одна высокоуровневая операция i[1] := Dn[1] |
jmp @@Loop1_Body |
Прыгаем на метку @@Loop1_Body, т.е. сразу в тело цикла первого «этажа» |
@@inc_i1: |
Данная строка – метка @@inc_i1 – на нее будем переходить, когда надо будет первый индекс, т.е. i[1], увеличить на 1. |
inc byte ptr es:[di+1] |
Увеличить значение байта по адресу es:[di+1] на 1, т.е. увеличить значение i[1] на 1 (кстати, в начале мы di уменьшили на 1, так вот, в отладчике сразу видно, на каком «этаже» мы есть по этой строке) |
jmp @@Loop1_Body |
|
db 'Loop01_Body' |
Эта строка – «особое изобретение» - метка или «отпечатки пальцев», по которому мы вычисляем адрес тела цикла первого этажа |
nop |
Эти две строки ничего не делают, т.к. nop - это «no operation». В данном случае нужны, чтобы в отладчике предыдущая строка, т.е. db 'Loop01_Body' в отладчике не «сливалась» с последующим кодом (Отладчику пофиг, что там текст на самом деле – для него все байты, все код). Попробуйте убрать эти строки и посмотреть, что получается в отладчике – удобство резко понижается. |
@@Loop1_Body: |
Метка тела цикла с первого «этажа» |
call @@Loop02_Begin |
Отсюда переходим на второй «этаж», т.е. инструкцией call вызываем вторую подпрограмму, которая начинается с метки @@Loop02_Begin. |
mov al,es:[di+1] |
Снова в регистр al записываем байт с адреса es:[di+1], т.е. в al значение i[1]. |
mov dl,es:[di+15h] |
Теперь в dl байт с адреса es:[di+15h], т.е. первый байт массива верхних границ – Up[1]. |
cmp al,dl |
Сравниваем al и dl - если эти два значения не равны, то переходим на метку @@inc_i1. |
jne @@inc_i1 |
Возвращаем из стэка значение bp, которое мы сохранили в нем при входе в процедуру. |
pop bp retf |
Из процедуры RunIt возвращаемся дальним образом, т.е. к данному моменту текущим значением стэка должен быть 0109, а выше слово 191Е (у вас могут быть другие значения, а эти взяты выше по тексту). Соответственно, смещение и сегмент адреса возврата. И еще немножко ликбеза. Вообще же |
Если вы заглянете на следующие этажи, то увидите почти один и тот же код. Отличия же будут в «добавках» для
регистра 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 байта – как раз то, что надо, чтобы вписать в это место, если понадобится, инструкцию вызова главной процедуры. А зачем это надо – узнаете ниже).
(Продолжение следует)
