Команды ассемблера

Команда lea для арифметики

Для выполнения некоторых арифметических операций можно использовать команду leaIntel® 64 and IA-32 Architectures Optimization Reference Manual, 3.5.1.3 Using LEA. Она вычисляет адрес своего операнда-источника и помещает этот адрес в операнд-назначение. Ведь она не производит чтение памяти по этому адресу, верно? А значит, всё равно, что она будет вычислять: адрес или какие-то другие числа.

Вспомним, как формируется адрес операнда:

 смещение(база, индекс, множитель)

Вычисленный адрес будет равен база + индекс ? множитель + смещение.

Чем это нам удобно? Так мы можем получить команду с двумя операндами-источниками и одним результатом:

movl  $10, %eax
movl  $7, %ebx
 
leal  5(%eax)       ,%ecx  /* %ecx = %eax + 5 = 15                   */
leal  -3(%eax)      ,%ecx  /* %ecx = %eax - 3 = 7                    */
leal  (%eax,%ebx)   ,%ecx  /* %ecx = %eax + %ebx ? 1 = 17            */
leal  (%eax,%ebx,2) ,%ecx  /* %ecx = %eax + %ebx ? 2 = 24            */
leal  1(%eax,%ebx,2),%ecx  /* %ecx = %eax + %ebx ? 2 + 1 = 25        */
leal  (,%eax,8)     ,%ecx  /* %ecx = %eax ? 8 = 80                   */
leal  (%eax,%eax,2) ,%ecx  /* %ecx = %eax + %eax ? 2 = %eax ? 3 = 30 */
leal  (%eax,%eax,4) ,%ecx  /* %ecx = %eax + %eax ? 4 = %eax ? 5 = 50 */
leal  (%eax,%eax,8) ,%ecx  /* %ecx = %eax + %eax ? 8 = %eax ? 9 = 90 */

Вспомните, что при сложении командой add результат записывается на место одного из слагаемых. Теперь, наверно, стало ясно главное преимущество lea в тех случаях, где её можно применить: она не перезаписывает операнды-источники. Как вы это сможете использовать, зависит только от вашей фантазии: прибавить константу к регистру и записать в другой регистр, сложить два регистра и записать в третий… Также lea можно применять для умножения регистра на 3, 5 и 9, как показано выше.

Команда loop

Синтаксис:

 loop  метка

Принцип работы:

Напишем программу для вычисления суммы чисел от 1 до 10 (конечно же, воспользовавшись формулой суммы арифметической прогрессии, можно переписать этот код и без цикла - но ведь это только пример).

.data
printf_format:
        .string  "%d\n "
 
.text
.globl main
main:
        movl  $0, %eax          /* в %eax будет результат, поэтому в 
                                   начале его нужно обнулить         */
        movl  $10, %ecx         /* 10 шагов цикла                    */
 
sum:
        addl  %ecx, %eax        /* %eax = %eax + %ecx                */
        loop  sum
 
        /* %eax = 55, %ecx = 0 */
 
/*
 * следующий код выводит число в %eax на экран и завершает программу
 */
        pushl %eax
        pushl $printf_format
        call  printf
        addl  $8, %esp
 
        movl  $0, %eax
        ret

На Си это выглядело бы так:

#include  <stdio.h >

int main()
{
  int eax, ecx;
  eax = 0;
  ecx = 10;
  do
  {
    eax += ecx;
  } while(--ecx);
  printf( "%d\n ", eax);
  return 0;
}

Команды сравнения и условные переходы. Безусловный переход

Команда loop неявно сравнивает регистр %ecx с нулём. Это довольно удобно для организации циклов, но часто циклы бывают намного сложнее, чем те, что можно записать при помощи loop. К тому же нужен эквивалент конструкции if(){}. Вот команды, позволяющие выполнять произвольные сравнения операндов:

 cmp   операнд_2, операнд_1

Команда cmp выполняет вычитание операнд_1 - операнд_2 и устанавливает флаги. Результат вычитания нигде не запоминается.

Внимание! Обратите внимание на порядок операндов в записи команды: сначала второй, потом первый.

Сравнили, установили флаги, - и что дальше? А у нас есть целое семейство jump-команд, которые передают управление другим командам. Эти команды называются командами условного перехода. Каждой из них поставлено в соответствие условие, которое она проверяет. Синтаксис:

 jcc   метка

Команды jcc не существует, вместо cc нужно подставить мнемоническое обозначение условия.

Таким образом, je проверяет равенство операндов команды сравнения, jl проверяет условие операнд_1 < операнд_2 и так далее. У каждой команды есть противоположная: просто добавляем букву n:

Теперь пример использования этих команд:

.text
        /* Тут пропущен код, который получает некоторое значение в %eax.
           Пусть нас интересует случай, когда %eax = 15 */

        cmpl  $15, %eax         /* сравнение                         */
        jne   not_equal        /* если операнды не равны, перейти на 
                                   метку not_equal                   */
 
        /* сюда управление перейдёт только в случае, когда переход не 
           сработал, а значит, %eax = 15 */
 
not_equal:
        /* а сюда управление перейдёт в любом случае */

Сравните с кодом на Си:

if(eax == 15)
{
  /* сюда управление перейдёт только в случае, когда переход не сработал,
     а значит, %eax = 15 */
}
/* а сюда управление перейдёт в любом случае */

Кроме команд условного перехода, область применения которых ясна сразу, также существует команда безусловного перехода. Эта команда чем-то похожа на оператор goto языка Си. Синтаксис:

 jmp   адрес

Эта команда передаёт управление на адрес, не проверяя никаких условий. Заметьте, что адрес может быть задан в виде непосредственного значения (метки), регистра или обращения к памяти.

Произвольные циклы

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

Программа: поиск наибольшего элемента в массиве

.data
printf_format:
        .string  "%d\n "
 
array:
        .long -10, -15, -148, 12, -151, -3, -72
array_end:
 
.text
.globl main
main:
        movl  array, %eax         /* в %eax будет храниться результат;
                                   в начале наибольшее значение - array[0]*/
        movl  $array+4, %ebx      /* в %ebx находится адрес текущего 
                                   элемента массива                  */
        jmp   ch_bound          /* проверить границы массива */
loop_start:                     /* начало цикла                      */
        cmpl  %eax, (%ebx)      /* сравнить текущий элемент массива с 
                                   текущим наибольшим значением из %eax
                                                                     */
        jle   less              /* если текущий элемент массива меньше 
                                   или равен наибольшему, пропустить 
                                   следующий код                     */
        movl  (%ebx), %eax      /* а вот если элемент массива 
                                   превосходит наибольший, значит, его 
                                   значение и есть новый максимум    */
less:
        addl  $4, %ebx          /* увеличить %ebx на размер одного 
                                   элемента массива, 4 байта         */
ch_bound:
        cmpl  $array_end, %ebx  /* сравнить адрес текущего элемента и 
                                   адрес конца массива               */
        jne    loop_start        /* если они не равны, повторить цикл снова* 
/*
 * следующий код выводит число из %eax на экран и завершает программу
 */
        pushl %eax
        pushl $printf_format
        call  printf
        addl  $8, %esp
 
        movl  $0, %eax
        ret

Сначала мы заносим в регистр %eax число array[0]. После этого мы сравниваем каждый элемент массива, начиная со следующего (нам незачем сранивать нулевой элемент с самим собой), с текущим наибольшим значением из %eax, и, если этот элемент больше, он становится текущим наибольшим. После просмотра всего массива в %eax находится наибольший элемент. Отметим, что если массив состоит из 1 элемента, то следующий после нулевого элемента будет находиться за границей массива, поэтому перед циклом стоит безусловный переход на проверку границы.

Этот код соответствует приблизительно следующему на Си:

#include  <stdio.h >
 
int main()
{
  static int array[] = { -10, -15, -148, 12, -151, -3, -72 };
  static int *array_end =  array[sizeof(array) / sizeof(int)];
  int max = array[0];
  int *p = array+1;
 
  while (p != array_end)
  {
    if(*p  > max)
    {
      max = *p;
    }
    p++;
  }
 
  printf( "%d\n ", max);
  return 0;
}

Возможно, такой способ обхода массива не очень привычен для вас. В Си принято использовать переменную с номером текущего элемента, а не указатель на него. Никто не запрещает пойти этим же путём и на ассемблере:

.data
printf_format:
        .string  "%d\n "
 
array:
        .long 10, 15, 148, -3, 151, 3, 72
array_size:
        .long (. - array)/4  /* количество элементов массива */
 
.text
.globl main
main:
        movl  array, %eax          /* в %eax будет храниться результат;
                                   в начале наибольшее значение - array[0]  */
        movl  $1, %ecx            /* начать просмотр с первого элемента 
                                                                     */
        jmp   ch_bound
loop_start:                     /* начало цикла                      */
        cmpl  %eax, array(,%ecx,4)  /* сравнить текущий элемент 
                                   массива с текущим наибольшим 
                                   значением из %eax                 */
        jle   less              /* если текущий элемент массива меньше 
                                   или равен наибольшему, пропустить 
                                   следующий код                     */
        movl  array(,%ecx,4), %eax  /* а вот если элемент массива 
                                   превосходит наибольший, значит, его 
                                   значение и есть новый максимум    */
less:
        incl  %ecx              /* увеличить на 1 номер текущего 
                                   элемента                          */
ch_bound:
        cmpl  array_size, %ecx  /* сравнить номер текущего элемента с 
                                   общим числом элементов            */
        jne    loop_start       /* если они не равны, повторить цикл снова */

/*
 * следующий код выводит число в %eax на экран и завершает программу
 */
        pushl %eax
        pushl $printf_format
        call  printf
        addl  $8, %esp
 
        movl $0, %eax
        ret

Рассматривая код этой программы, вы, наверно, уже поняли, как создавать произвольные циклы с постусловием на ассемблере, наподобие do{} while(); в Си. Ещё раз повторю эту конструкцию, выкинув весь код, не относящийся к циклу:

loop_start:                    /* начало цикла                      */
 
        /* вот тут находится тело цикла */
 
        cmpl  ...              /* что-то с чем-то сравнить для 
                                  принятия решения о выходе из цикла */
        jne    loop_start      /* подобрать соответствующую команду 
                                  условного перехода для повторения цикла     */           

В Си есть ещё один вид цикла, с проверкой условия перед входом в тело цикла (цикл с предусловием): while(){}. Немного изменив предыдущий код, получаем следующее:

        jmp    check
loop_start:                    /* начало цикла                      */
 
        /* вот тут находится тело цикла */
 
check:
        cmpl  ...              /* что-то с чем-то сравнить для 
                                  принятия решения о выходе из цикла */
        jne    loop_start      /* подобрать соответствующую команду 
                                  условного перехода для повторения цикла     */           

Кто-то скажет: а ещё есть цикл for()! Но цикл

for(init; cond; incr)
{
  body;
}
эквивалентен такой конструкции:
init;
while(cond)
{
  body;
  incr;
}

Таким образом, нам достаточно и уже рассмотренных двух видов циклов.

Логическая арифметика

Кроме выполнения обычных арифметических вычислений, можно проводить и логические, то есть битовые.

 and   источник, приёмник
 or    источник, приёмник
 xor   источник, приёмник
 not   операнд
 test  операнд_1, операнд_2

Команды and, or и xor ведут себя так же, как и операторы языка Си , |, ^. Эти команды устанавливают флаги согласно результату.

Команда not инвертирует каждый бит операнда (изменяет на противоположный), так же как и оператор языка Си $$\sim$$.

Команда test выполняет побитовое И над операндами, как и команда and, но, в отличие от неё, операнды не изменяет, а только устанавливает флаги. Её также называют командой логического сравнения, потому что с её помощью удобно проверять, установлены ли определённые биты. Например, так:

        testb $0b00001000, %al  /* установлен ли 3-й (с нуля) бит?   */
        je    not_set
        /* нужные биты установлены */
not_set:
        /* биты не установлены */

Обратите внимание на запись константы в двоичной системе счисления: используется префикс 0b.

Команду test можно применять для сравнения значения регистра с нулём:

        testl %eax, %eax
        je    is_zero
        /* %eax != 0 */
is_zero:
        /* %eax == 0 */

Intel Optimization Manual рекомендует использовать test вместо cmp для сравнения регистра с нулёмIntel® 64 and IA-32 Architectures Optimization Reference Manual, 3.5.1.7 Compares.

Ещё следует упомянуть об одном трюке с xor. Как вы знаете, a XOR a = 0. Пользуясь этой особенностью, xor часто применяют для обнуления регистров:

xorl  %eax, %eax
/* теперь %eax == 0 */

Почему применяют xor вместо mov? Команда xor короче, а значит, занимает меньше места в процессорном кэше, меньше времени тратится на декодирование, и программа выполняется быстрее. Но эта команда устанавливает флаги. Поэтому, если вам нужно сохранить состояние флагов, применяйте movIntel® 64 and IA-32 Architectures Optimization Reference Manual, 3.5.1.6 Clearing Registers and Dependency Breaking Idioms.

Иногда для обнуления регистра применяют команду sub. Помните, она тоже устанавливает флаги.

subl  %eax, %eax
/* теперь %eax == 0 */

К логическим командам также можно отнести команды сдвигов:

 /* Shift Arithmetic Left/SHift logical Left */
 sal/shl количество_сдвигов, назначение

 /* SHift logical Right */
 shr     количество_сдвигов, назначение 

 /* Shift Arithmetic Right */
 sar     количество_сдвигов, назначение

количество_сдвигов может быть задано непосредственным значением или находиться в регистре %cl. Учитываются только младшие 5 бит регистра %cl, так что количество сдвигов может варьироваться в пределах от 0 до 31.

Принцип работы команды shl:

                              До сдвига:
          +---+     +----------------------------------+
          | ? |     | 10001000100010001000100010001011 |
          +---+     +----------------------------------+
         Флаг CF    Операнд
 
                       Сдвиг влево на 1 бит:
          +---+     +----------------------------------+
          | 1 |  <-- | 00010001000100010001000100010110 |  <-- 0
          +---+     +----------------------------------+
         Флаг CF    Операнд
 
                      Сдвиг влево на 3 бита:
 +----+   +---+     +----------------------------------+
 | 10 |   | 0 |  <-- | 01000100010001000100010001011000 |  <-- 000
 +----+   +---+     +----------------------------------+
Улетели  Флаг CF    Операнд
в никуда

Принцип работы команды shr:

                  До сдвига:
        +----------------------------------+     +---+
        | 10001000100010001000100010001011 |     | ? |
        +----------------------------------+     +---+
        Операнд                                  Флаг CF

          Логический сдвиг вправо на 1 бит:
        +----------------------------------+     +---+
  0 -- > | 01000100010001000100010001000101 | -- > | 1 |
        +----------------------------------+     +---+
        Операнд                                 Флаг CF

          Логический сдвиг вправо на 3 бита:
        +----------------------------------+     +---+  +----+
000 -- > | 00010001000100010001000100010001 | -- > | 0 |  | 11 |
        +----------------------------------+     +---+  +----+
        Операнд                                 Флаг CF Улетели
                                                        в никуда

Эти две команды называются командами логического сдвига, потому что они работают с операндом как с массивом бит. Каждый "выдвигаемый " бит попадает в флаг cf, причём с другой стороны операнда "вдвигается " бит 0. Таким образом, в флаге cf оказывается самый последний "выдвинутый " бит. Такое поведение вполне допустимо для работы с беззнаковыми числами, но числа со знаком будут обработаны неверно из-за того, что знаковый бит может быть потерян.

Для работы с числами со знаком существуют команды арифметического сдвига. Команды shl и sal выполняют полностью идентичные действия, так как при сдвиге влево знаковый бит не теряется (расширение знакового бита влево становится новым знаковым битом). Для сдвига вправо применяется команда sar. Она "вдвигает " слева знаковый бит исходного значения, таким образом сохраняя знак числа:

                  До сдвига:
        +----------------------------------+     +---+
        | 10001000100010001000100010001011 |     | ? |
        +----------------------------------+     +---+
        Операнд                                  Флаг CF
        старший бит равен 1 == >
          == > значение отрицательное == >
          == >  "вдвинуть " бит 1 ---+
                                  |
  +-------------------------------+
  |
  V       Арифметический сдвиг вправо на 1 бит:
        +----------------------------------+     +---+
  1 -- > | 11000100010001000100010001000101 | -- > | 1 |
        +----------------------------------+     +---+
        Операнд                                 Флаг CF

          Арифметический сдвиг вправо на 3 бита:
        +----------------------------------+     +---+  +----+
111 -- > | 11110001000100010001000100010001 | -- > | 0 |  | 11 |
        +----------------------------------+     +---+  +----+
        Операнд                                 Флаг CF Улетели
                                                        в никуда

Многие программисты Си знают об умножении и делении на степени двойки (2, 4, 8…) при помощи сдвигов. Этот трюк отлично работает и в ассемблере, используйте его для оптимизации.

Кроме сдвигов обычных, существуют циклические сдвиги:

 /* ROtate Right */
 ror   количество_сдвигов, назначение

 /* ROtate Left */
 rol   количество_сдвигов, назначение

Объясню на примере циклического сдвига влево на три бита: три старших ( "левых ") бита "выдвигаются " из регистра влево и "вдвигаются " в него справа. При этом в флаг cfзаписывается самый последний "выдвинутый " бит.

Принцип работы команды rol:

                              До сдвига:
      +---+         +----------------------------------+
      | ? |         | 10001000100010001000100010001011 |
      +---+         +----------------------------------+
     Флаг CF        Операнд
 
                      Циклический сдвиг влево на 1 бит:
      +---+  1    1 +----------------------------------+
      | 1 |  <--+--- | 00010001000100010001000100010111 | ---+
      +---+    |    +----------------------------------+    |
     Флаг CF   V    Операнд                                 ^
               |                                            |
               +------------------- >--- >--- >----------------+
                1
 
                      Циклический сдвиг влево на 3 бита:
      +---+  0  100 +----------------------------------+
      | 0 |  <--+--- | 01000100010001000100010001011100 | ---+
      +---+    |    +----------------------------------+    |
     Флаг CF   V    Операнд                                 ^
               |                                            |
               +------------------- >--- >--- >----------------+
                100

Принцип работы команды ror:

                  До сдвига:
        +----------------------------------+         +---+
        | 10001000100010001000100010001011 |         | ? |
        +----------------------------------+         +---+
        Операнд                                     Флаг CF

          Циклический сдвиг вправо на 1 бит:
        +----------------------------------+ 1    1  +---+
   +--- | 11000100010001000100010001000101 | ---+-- > | 1 |
   |    +----------------------------------+    |    +---+
   ^    Операнд                                 V   Флаг CF
   |                                            |
   +------------------- <--- <--- <----------------+
                                               1

          Циклический сдвиг вправо на 3 бита:
        +----------------------------------+ 011  0  +---+
   +--- | 01110001000100010001000100010001 | ---+-- > | 0 |
   |    +----------------------------------+    |    +---+
   ^    Операнд                                 V   Флаг CF
   |                                            |
   +------------------- <--- <--- <----------------+
                                             011

Существует ещё один вид сдвигов - циклический сдвиг через флаг cf. Эти команды рассматривают флаг cf как продолжение операнда.

 /* Rotate through Carry Right */
 rcr   количество_сдвигов, назначение 

 /* Rotate through Carry Left */
 rcl   количество_сдвигов, назначение

Принцип работы команды rcl:

                              До сдвига:
         +---+      +----------------------------------+
         | X |      | 10001000100010001000100010001011 |
         +---+      +----------------------------------+
        Флаг CF     Операнд
 
                      Циклический сдвиг влево через CF на 1 бит:
      X  +---+      +----------------------------------+
    +- <- | 1 |  <--- | 0001000100010001000100010001011X | ---+
    |    +---+      +----------------------------------+    |
    V   Флаг CF     Операнд                                 ^
    |                                                       |
    +------------------------------ >--- >--- >----------------+
 
                      Циклический сдвиг влево через CF на 3 бита:
     X10 +---+      +----------------------------------+
    +- <- | 0 |  <--- | 01000100010001000100010001011X10 | ---+
    |    +---+      +----------------------------------+    |
    V   Флаг CF     Операнд                                 ^
    |                                                       |
    +------------------------------ >--- >--- >----------------+

Принцип работы команды rcr:

                   До сдвига:
         +----------------------------------+      +---+
         | 10001000100010001000100010001011 |      | X |
         +----------------------------------+      +---+
         Операнд                                  Флаг CF
 
           Циклический сдвиг вправо через CF на 1 бит:
         +----------------------------------+      +---+  X
    +--- | X1000100010001000100010001000101 | --- > | 1 | - >-+
    |    +----------------------------------+      +---+    |
    ^    Операнд                                  Флаг CF   V
    |                                                       |
    +------------------- <--- <--- <---------------------------+
 
           Циклический сдвиг вправо через CF на 3 бита:
         +----------------------------------+      +---+ 11X
    +--- | 11X10001000100010001000100010001 | --- > | 0 | - >-+
    |    +----------------------------------+      +---+    |
    ^    Операнд                                  Флаг CF   V
    |                                                       |
    +------------------- <--- <--- <---------------------------+

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

int main()
{
  int a = 0x11223344;
  int shift_count = 8;

  a = (a  < < shift_count) | (a  > > (32 - shift_count));

  printf( "%x\n ", a);
  return 0;
}

Подпрограммы

Термином "подпрограмма " будем называть и функции, которые возвращают значение, и функции, не возвращающие значение (void proc(…)). Подпрограммы нужны для достижения одной простой цели - избежать дублирования кода. В ассемблере есть две команды для организации работы подпрограмм.

call  метка

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

Для возврата из подпрограммы используется команда ret.

ret
ret   число

Принцип работы:

Существует несколько способов передачи аргументов в подпрограмму.

Рассмотрим передачу аргументов через стек подробнее. Предположим, нам нужно написать подпрограмму, принимающую три аргумента типа long (4 байта). Код:

sub:
        pushl %ebp              /* запоминаем текущее значение 
                                   регистра %ebp, при этом %esp -= 4 */
        movl  %esp, %ebp        /* записываем текущее положение 
                                   вершины стека в %ebp              */
 
        /* пролог закончен, можно начинать работу */
 
        subl  $8, %esp          /* зарезервировать место для локальных 
                                   переменных                        */
 
 
        movl  8(%ebp),  %eax    /* что-то cделать с параметрами      */
        movl  12(%ebp), %eax
        movl  16(%ebp), %eax
 
 
        /* эпилог */
 
        movl  %ebp, %esp        /* возвращем вершину стека в исходное 
                                   положение                         */
        popl  %ebp              /* восстанавливаем старое значение 
                                   %ebp, при этом %esp += 4          */
        ret
 
main:
        pushl $0x00000010       /* поместить параметры в стек        */
        pushl $0x00000020
        pushl $0x00000030
        call  sub               /* вызвать подпрограмму              */
        addl  $12, %esp

С вызовом всё ясно: помещаем аргументы в стек и даём команду call. А вот как в подпрограмме удобно достать параметры из стека? Вспомним про регистр %ebp.

Мы сохраняем предыдущее значение регистра %ebp, а затем записываем в него указатель на текущую вершину стека. Теперь у нас есть указатель на стек в известном состоянии. Сверху в стек можно помещать сколько угодно данных, %esp поменяется, но у нас останется доступ к параметрам через %ebp. Часто эта последовательность команд в начале подпрограммы называется "прологом ".

.                      .
.                      .
.                      .
+----------------------+ 0x0000F040  <-- новое значение %ebp
| старое значение %ebp |
+----------------------+ 0x0000F044  <-- %ebp + 4
|    адрес возврата    |
+----------------------+ 0x0000F048  <-- %ebp + 8
|      0x00000030      |
+----------------------+ 0x0000F04C  <-- %ebp + 12
|      0x00000020      |
+----------------------+ 0x0000F050  <-- %ebp + 16
|      0x00000010      |
+----------------------+ 0x0000F054
.                      .
.                      .
.                      .

Используя адрес из %ebp, мы можем ссылаться на параметры:

 8(%ebp) = 0x00000030
12(%ebp) = 0x00000020
16(%ebp) = 0x00000010

Как видите, если идти от вершины стека в сторону аргументов, то мы будем встречать аргументы в обратном порядке по отношению к тому, как их туда поместили. Нужно сделать одно из двух: или помещать аргументы в обратном порядке (чтобы доставать их в прямом порядке), или учитывать обратный порядок аргументов в подпрограмме. В Си принято при вызове помещать аргументы в обратном порядке. Так как операционная система Linux и большинство библиотек для неё написаны именно на Си, для обеспечения переносимости и совместимости лучше использовать "сишный " способ передачи аргументов и в ваших ассемблерных программах.

Подпрограмме могут понадобиться собственные локальные переменные. Их принято держать в стеке, так как в этом случае легко обеспечить необходимое время жизни локальных переменных: достаточно в конце подпрограммы вытолкнуть их из стека. Для того, чтобы зарезервировать для них место, мы просто уменьшим содержимое регистра %esp на размер наших переменных. Это действие эквивалентно использованию соответствующего количества команд push, только быстрее, так как не требует записи в память. Предположим, что нам нужно 2 переменные типа long (4 байта), итого 2 * 4 = 8 байт. Таким образом, регистр %esp нужно уменьшить на 8. Теперь стек выглядит так:

.                        .
.                        .
.                        .
+------------------------+ 0x0000F038  <-- %ebp - 8
| локальная переменная 2 |
+------------------------+ 0x0000F03C  <-- %ebp - 4
| локальная переменная 1 |
+------------------------+ 0x0000F040  <-- %ebp
|  старое значение %ebp  |
+------------------------+ 0x0000F044  <-- %ebp + 4
|     адрес возврата     |
+------------------------+ 0x0000F048  <-- %ebp + 8
|       0x00000030       |
+------------------------+ 0x0000F04C  <-- %ebp + 12
|       0x00000020       |
+------------------------+ 0x0000F050  <-- %ebp + 16
|       0x00000010       |
+------------------------+ 0x0000F054
.                        .
.                        .
.                        .

Вы не можете делать никаких предположений о содержимом локальных переменных. Никто их для вас не инициализировал нулём. Можете для себя считать, что там находятся случайные значения.

При возврате из процедуры мы восстанавливаем старое значение %ebp из стека, потому что после возврата вызывающая функция вряд ли будет рада найти в регистре %ebp неизвестно что (а если серьёзно, этого требует ABI). Для этого необходимо, чтобы старое значение %ebp было на вершине стека. Если подпрограмма что-то поместила в стек после старого %ebp, она должна это убрать. К счастью, мы не должны считать, сколько байт мы поместили, сколько достали и сколько ещё осталось. Мы можем просто поместить значение регистра %ebp в регистр %esp, и стек станет точно таким же, как и после сохранения старого %ebp в начале подпрограммы. После этого команда ret возвращает управление вызывающему коду. Эта последовательность команд часто называется "эпилогом " подпрограммы.

Внимание! Сразу после того, как вы восстановили значение %esp в эпилоге, вы должны считать, что локальные переменные уничтожены. Хотя они ещё не перезаписаны, они, несомненно, будут затёрты последующими командами push, поэтому вы не должны сохранять указатели на локальные переменные дальше эпилога своей функции.

Остаётся одна маленькая проблема: в стеке всё ещё находятся аргументы для подпрограммы. Это можно решить одним из следующих способов:

В Си используется последний способ. Так как мы поместили в стек 3 значения типа long по 4 байта каждый, мы должны увеличить %esp на 12, что и делает команда addl сразу после call.

Заметьте, что не всегда обязательно выравнивать стек. Если вы вызываете несколько подпрограмм подряд (но не в цикле!), то можно разрешить аргументам "накопиться " в стеке, а потом убрать их всех одной командой. Если ваша подпрограмма не содержит вызовов других подпрограмм в цикле и вы уверены, что оставшиеся аргументы в стеке не вызовут проблем переполнения стека, то аргументы можно не убирать вообще. Всё равно это сделает команда эпилога, которая восстанавливает %esp из %ebp. С другой стороны, если не уверены - лучше уберите аргументы, от одной лишней команды программа медленнее не станет.

Строго говоря, все эти действия с %ebp не требуются. Вы можете использовать %ebp для хранения своих значений, никак не связанных со стеком, но тогда вам придётся обращаться к аргументам и локальным переменным через %esp или другие регистры, в которые вы поместите указатели. Трюк состоит в том, чтобы не изменять %esp после резервирования места для локальных переменных и до конца функции: так вы сможете использовать %esp на манер %ebp, как было показано выше. Не изменять %esp значит, что вы не сможете использовать push и pop (иначе все смещения переменных в стеке относительно %esp "поплывут "); вам понадобится создать необходимое число локальных переменных для хранения этих временных значений. С одной стороны, этот способ доступа к переменным немного сложнее, так как вы должны заранее просчитать, сколько места в стеке вам понадобится. С другой стороны, у вас появляется еще один свободный регистр %ebp. Так что если вы решите пойти этой дорогой, вы должны заранее продумать, сколько места для локальных переменных вам понадобится, и дальше обращаться к ним через смещения относительно %esp.

И последнее: если вы хотите использовать вашу подпрограмму за пределами данного файла, не забудьте сделать её глобальной с помощью директивы .globl.

Посмотрим на код, который выводил содержимое регистра %eax на экран, вызывая функцию стандартной библиотеки Си printf(3). Вы его уже видели в предыдущих программах, но там он был приведен без объяснений. Для справки привожу цитату из man:

PRINTF(3)            Linux Programmer 's Manual            PRINTF(3)
 
NAME
       printf - formatted output conversion
 
SYNOPSIS
       #include  <stdio.h >
 
       int printf(const char *format, ...);
.data
printf_format:
        .string  "%d\n "
 
.text
        /* printf(printf_format, %eax); */
        pushl %eax              /* аргумент, подлежащий печати       */
        pushl $printf_format    /* аргумент format                   */
        call  printf            /* вызов printf()                    */
        addl  $8, %esp          /* выровнять стек                    */

Обратите внимание на обратный порядок аргументов и очистку стека от аргументов.

Внимание! Значения регистров глобальны, вызывающая и вызываемая подпрограммы видят одни и те же регистры. Конечно же, подпрограмма может изменять значения любых пользовательских регистров, но она обязана при возврате восстановить значения регистров %ebp, %ebx, %esi, %edi и %esp. Сохранение остальных регистров перед вызовом подпрограммы - задача программиста. Даже если вы заметили, что подпрограмма не изменяет какой-то регистр, это не повод его не сохранять. Ведь неизвестно, как будут обстоять дела в следующей версии подпрограммы. Вы не должны делать каких-либо предположений о состоянии регистров на момент выхода из подпрограммы. Можете считать, что они содержат случайные значения. Также внимания требует флаг df. При вызове подпрограмм флаг должен быть равен 0. Подпрограмма при возврате также должна установить флаг в 0. Коротко: если вам вдруг нужно установить этот флаг для какой-то операции, сбросьте его сразу, как только надобность в нём исчезнет.

До этого момента мы обходились общим термином "подпрограмма ". Но если подпрограмма - функция, она должна как-то передать возвращаемое значение. Это принято делать при помощи регистра %eax. Перед началом эпилога функция должна поместить в %eax возвращаемое значение.

Программа: печать таблицы умножения

Рассмотрим программу посложнее. Итак, программа для печати таблицы умножения. Размер таблицы умножения вводит пользователь. Нам понадобится вызвать функцию scanf(3) для ввода, printf(3) для вывода и организовать два вложенных цикла для вычислений.

.data
input_prompt:
        .string  "enter size (1-255):  "
 
scanf_format:
        .string  "%d "
 
printf_format:
        .string  "%5d  "
 
printf_newline:
        .string  "\n "
 
size:
        .long 0
 
.text
.globl main
main:
        /* запросить у пользователя размер таблицы */
        pushl $input_prompt     /* format                            */
        call  printf            /* вызов printf                      */
 
        /* считать размер таблицы в переменную size */
        pushl $size             /* указатель на переменную size      */
        pushl $scanf_format     /* format                            */
        call  scanf             /* вызов scanf                       */
 
        addl  $12, %esp         /* выровнять стек одной командой сразу 
                                   после двух функций                */
 
        movl  $0, %eax          /* в регистре %ax команда mulb будет 
                                   выдавать результат, но мы печатаем 
                                   всё содержимое %eax, поэтому два 
                                   старших байта %eax должны быть 
                                   нулевыми                          */
 
        movl  $0, %ebx          /* номер строки                      */
 
print_line:
        incl  %ebx              /* увеличить номер строки на 1       */
        cmpl  size, %ebx
        ja    print_line_end    /* если номер строки больше 
                                   запрошенного размера, завершить цикл
                                                                     */
 
        movl  $0, %ecx          /* номер колонки                     */
 
print_num:
        incl  %ecx              /* увеличить номер колонки на 1      */
        cmpl  size, %ecx
        ja    print_num_end     /* если номер колонки больше 
                                   запрошенного размера, завершить цикл
                                                                     */
 
        movb  %bl, %al          /* команда mulb ожидает второй 
                                   операнд в %al                     */
        mulb  %cl               /* вычислить %ax = %cl * %al         */
 
        pushl %ebx              /* сохранить используемые регистры 
                                   перед вызовом printf              */
        pushl %ecx
 
        pushl %eax              /* данные для печати                 */
        pushl $printf_format    /* format                            */
        call  printf            /* вызов printf                      */
        addl  $8, %esp          /* выровнять стек                    */
 
        popl  %ecx              /* восстановить регистры             */
        popl  %ebx
 
        jmp   print_num         /* перейти в начало цикла            */
print_num_end:
 
        pushl %ebx              /* сохранить регистр                 */
 
        pushl $printf_newline   /* напечатать символ новой строки    */
        call  printf
        addl  $4, %esp
 
        popl  %ebx              /* восстановить регистр              */
 
        jmp   print_line        /* перейти в начало цикла            */
print_line_end:
 

        movl  $0, %eax          /* завершить программу               */
        ret

Программа: вычисление факториала

Теперь напишем рекурсивную функцию для вычисления факториала. Она основана на следующей формуле:

.data
printf_format:
        .string  "%d\n "
 
.text
/* int factorial(int) */
factorial:
        pushl %ebp
        movl  %esp, %ebp
 
        /* извлечь аргумент в %eax */
        movl  8(%ebp), %eax
 
        /* факториал 0 равен 1 */
        cmpl  $0, %eax
        jne   not_zero
 
        movl  $1, %eax
        jmp   return
not_zero:
 
        /* следующие 4 строки вычисляют выражение
           %eax = factorial(%eax - 1) */
 
        decl  %eax
        pushl %eax
        call  factorial
        addl  $4, %esp
 
        /* извлечь в %ebx аргумент и вычислить %eax = %eax * %ebx */
 
        movl  8(%ebp), %ebx
        mull  %ebx
 
        /* результат в паре %edx:%eax, но старшие 32 бита нужно 
           отбросить, так как они не помещаются в int */
 
return:
        movl  %ebp, %esp
        popl  %ebp
        ret
 
.globl main
main:
        pushl %ebp
        movl  %esp, %ebp
 
        pushl $5
        call  factorial
 
        pushl %eax
        pushl $printf_format
        call  printf
 
        /* стек можно не выравнивать, это будет сделано
           во время выполнения эпилога */
 
        movl  $0, %eax                  /* завершить программу */
 
        movl  %ebp, %esp
        popl  %ebp
        ret

Любой программист знает, что если существует очевидное итеративное (реализуемое при помощи циклов) решение задачи, то именно ему следует отдавать предпочтение перед рекурсивным. Итеративный алгоритм нахождения факториала даже проще, чем рекурсивный; он следует из определения факториала: $$n!=1 /cdot 2 /cdot /dots /cdot n$$

Говоря проще, нужно перемножить все числа от 1 до $$n$$.

Функция - на то и функция, что её можно заменить, при этом не изменяя вызывающий код. Для запуска следующего кода просто замените функцию из предыдущей программы вот этой новой версией:

factorial:
        movl  4(%esp), %ecx
 
        cmpl  $0, %ecx
        jne   not_zero
 
        movl  $1, %eax
        ret
 
not_zero:
 
        movl  $1, %eax
loop_start:
        mull  %ecx
        loop  loop_start
 
        ret

Что же здесь изменено? Рекурсия переписана в виде цикла. Кадр стека больше не нужен, так как в стек ничего не перемещается и другие функции не вызываются. Пролог и эпилог поэтому убраны, при этом регистр %ebp не используется вообще. Но если бы он использовался, сначала нужно было бы сохранить его значение, а перед возвратом восстановить.

Автор увлёкся процессом и написал 64-битную версию этой функции. Она возвращает результат в паре %eax:%edx и может вычислить $$20!!=2432902008176640000$$.

.data
printf_format:
        .string  "%llu\n "
 
.text
.type   factorial, @function    /* long long int factorial(int)      */
factorial:
        movl  4(%esp), %ecx
 
        cmpl  $0, %ecx
        jne   not_zero
 
        movl  $1, %eax
        ret
 
not_zero:
 
        movl  $1, %esi          /* младшие 32 бита                   */
        movl  $0, %edi          /* старшие 32 бита                   */
loop_start:
        movl  %esi, %eax        /* загрузить младшие биты для 
                                   умножения                         */
        mull  %ecx              /* %eax:%edx = младшие биты * %ecx   */
        movl  %eax, %esi        /* записать младшие биты 
                                   обратно в %esi                    */
 
        movl  %edi, %eax        /* загрузить старшие биты            */
        movl  %edx, %edi        /* записать в %edi старшие биты 
                                   предыдущего умножения; теперь 
                                   результат умножения младших битов 
                                   находится в %esi:%edi, а старшие 
                                   биты - в %eax для следующего 
                                   умножения                         */
        mull  %ecx              /* %eax:%edx = старшие биты * %ecx   */
        addl  %eax, %edi        /* сложить полученный результат со 
                                   старшими битами предыдущего 
                                   умножения                         */
 
        loop  loop_start
 
        movl  %esi, %eax        /* результат вернуть в паре          */
        movl  %edi, %edx        /* %eax:%edx                         */
 
        ret
.size   factorial, .-factorial
 
.globl main
main:
        pushl %ebp
        movl  %esp, %ebp
 
        pushl $20
        call  factorial
 
        pushl %edx
        pushl %eax
        pushl $printf_format
        call  printf
 
        /* стек можно не выравнивать, это будет сделано во время 
           выполнения эпилога */
 
        movl  $0, %eax          /* завершить программу               */
 
        movl  %ebp, %esp
        popl  %ebp
        ret

Умножение 64-битного числа на 32-битное делается как при умножении "в столбик ":

     %edi       %esi
?               %ecx
---------------------
%edi?%ecx  %esi?%ecx
    A           |
   /|\          |
    +-- <-- <-- <--+
   старшие 32 бита

Но произведение %esi ? %ecx не поместится в 32 бита, останутся ещё старшие 32 бита. Их мы должны прибавить к старшим 32-м битам результата. Приблизительно так вы это делаете на бумаге в десятичной системе:

  2  5      25 ? 3 = 75
?    3
  ----
    15
+ 6
  ----
  7  5

Задание: напишите программу-считалочку. Есть числа от 0 до $$m$$, которые располагаются по кругу. Счёт начинается с элемента 0. Каждый $$n$$-й элемент удаляют. Счёт продолжается с элемента, следующего за удалённым. Напишите программу, выводящую список вычеркнутых элементов. Подсказка: используйте malloc(3) для получения $$m+1$$ байт памяти и занесите в каждый байт число 1 при помощи memset(3). Значение 1 означает, что элемент существует, значением 0 отмечайте удалённые элементы. При счете пропускайте удалённые элементы.

Системные вызовы

Программа, которая не взаимодействует с внешним миром, вряд ли может сделать что-то полезное. Вывести сообщение на экран, прочитать данные из файла, установить сетевое соединение - это всё примеры действий, которые программа не может совершить без помощи операционной системы. В Linux пользовательский интерфейс ядра организован через системные вызовы. Системный вызов можно рассматривать как функцию, которую для вас выполняет операционная система.

Теперь наша задача состоит в том, чтобы разобраться, как происходит системный вызов. Каждый системный вызов имеет свой номер. Все они перечислены в файле /usr/include/asm-i386/unistd.h.

Системные вызовы считывают свои параметры из регистров. Номер системного вызова нужно поместить в регистр %eax. Параметры помещаются в остальные регистры в таком порядке:

Таким образом, используя все регистры общего назначения, можно передать максимум 6 параметров. Системный вызов производится вызовом прерывания 0x80. Такой способ вызова (с передачей параметров через регистры) называется fastcall. В других системах (например, *BSD) могут применяться другие способы вызова.

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

В качестве примера можете посмотреть код программы Hello world.

Структуры

Объявляя структуры в Си, вы не задумывались о том, как располагаются в памяти её элементы. В ассемблере понятия "структура " нет, зато есть "блок памяти ", его адрес и смещение в этом блоке. Объясню на примере:

Пусть этот блок памяти размером 4 байта расположен по адресу 0x00010000. Это значит, что адрес байта 0x23 равен 0x00010000. Соответственно, адрес байта 0x72 равен 0x00010001. Говорят, что байт 0x72 расположен по смещению 1 от начала блока памяти. Тогда байт 0x45 расположен по смещению 2, а байт 0x17 - по смещению 3. Таким образом, адрес элемента = базовый адрес + смещение.

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

Примеры (внизу указано смещение элементов в байтах; заполнители обозначены XX):

struct     Выравнивание структуры: 1, размер: 1
{          +----+
  char c;  | c  |
};         +----+
           0

struct     Выравнивание структуры: 2, размер: 4
{          +----+----+----+----+
  char c;  | c  | XX |    s    |
  short s; +----+----+----+----+
};          0         2

struct     Выравнивание структуры: 4, размер: 8
{          +----+----+----+----+----+----+----+----+
  char c;  | с  | XX   XX   XX |         i         |
  int i;   +----+----+----+----+----+----+----+----+
};          0                   4

struct     Выравнивание структуры: 4, размер: 8
{          +----+----+----+----+----+----+----+----+
  int i;   |         i         | c  | XX   XX   XX |
  char c;  +----+----+----+----+----+----+----+----+
};          0                   4

struct     Выравнивание структуры: 4, размер: 12
{          +----+----+----+----+----+----+----+----+----+----+----+----+
  char c;  | c  | XX   XX   XX |         i         |    s    | XX   XX |
  int i;   +----+----+----+----+----+----+----+----+----+----+----+----+
  short s;  0                   4                   8
};

struct     Выравнивание структуры: 4, размер: 8
{          +----+----+----+----+----+----+----+----+
  int i;   |         i         | c  | XX |    s    |
  char c;  +----+----+----+----+----+----+----+----+
  short s;  0                   4         6
};

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

Программа: вывод размера файла

Напишем программу, которая выводит размер файла. Для этого потребуется вызвать функцию stat(2) и прочитать данные из структуры, которую она заполнит. man 2 stat:

 
STAT(2)                  Системные вызовы                  STAT(2)
 
ИМЯ
       stat, fstat, lstat - получить статус файла
 
КРАТКАЯ СВОДКА
       #include  <sys/types.h >
       #include  <sys/stat.h >
       #include  <unistd.h >
 
       int stat(const char *file_name, struct stat *buf);
 
ОПИСАНИЕ
       stat возвращает информацию о файле, заданном с помощью 
       file_name, и заполняет буфер buf.
 
       Все эти функции возвращают структуру stat, которая содержит 
       такие поля:
 
          struct stat {
              dev_t         st_dev;     /* устройство                */
              ino_t         st_ino;     /* индексный дескриптор      */
              mode_t        st_mode;    /* режим доступа             */
              nlink_t       st_nlink;   /* количество жестких ссылок */
              uid_t         st_uid;     /* идентификатор 
                                           пользователя-владельца    */
              gid_t         st_gid;     /* идентификатор 
                                           группы-владельца          */
              dev_t         st_rdev;    /* тип устройства (если это 
                                           устройство)               */
              off_t         st_size;    /* общий размер в байтах     */
              unsigned long st_blksize; /* размер блока ввода-вывода */
                                        /* в файловой системе        */
              unsigned long st_blocks;  /* количество выделенных 
                                           блоков                    */
              time_t        st_atime;   /* время последнего доступа  */
              time_t        st_mtime;   /* время последнего 
                                           изменения                 */
              time_t        st_ctime;   /* время последней смены 
                                           состояния                 */
          };

Так, теперь осталось только вычислить смещение поля st_size… Но что это за типы - dev_t, ino_t? Какого они размера? Следует заглянуть в заголовочный файл и узнать, что обозначено при помощи typedef. Я сделал так:

 
[user@host:~]$ cpp /usr/include/sys/types.h | less

Далее, ищу в выводе препроцессора определение dev_t, нахожу:

 typedef __dev_t dev_t; 

Ищу __dev_t:

 __extension__ typedef __u_quad_t __dev_t; 

Ищу __u_quad_t:

__extension__ typedef unsigned long long int __u_quad_t; 

Значит, sizeof(dev_t) = 8.

Мы бы могли и дальше продолжать искать, но в реальности всё немного по-другому. Если вы посмотрите на определение struct stat (cpp /usr/include/sys/stat.h | less), вы увидите поля с именами __pad1, __pad2, __unused4 и другие (зависит от системы). Эти поля не используются, они нужны для совместимости, и поэтому в man они не описаны. Так что самый верный способ не ошибиться - это просто попросить компилятор Си посчитать это смещение для нас (вычитаем из адреса поля адрес структуры, получаем смещение):

 
#include  <sys/types.h >
#include  <sys/stat.h >
#include  <unistd.h >
#include  <stdio.h >

int main()
{
  struct stat t;
  printf( "sizeof = %zu, offset = %td\n ",
         sizeof(t),
         ((void *)  t.st_size) - ((void *)  t));
  return 0;
}

На моей системе программа напечатала sizeof = 88, offset = 44. На вашей системе это значение может отличаться по описанным причинам. Теперь у нас есть все нужные данные об этой структуре, пишем программу:

.data
str_usage:
        .string  "usage: %s filename\n "
 
printf_format:
        .string  "%u\n "
 
.text
.globl main
main:
        pushl %ebp
        movl  %esp, %ebp
 
        subl  $88, %esp         /* выделить 88 байт под struct stat  */
 
        cmpl  $2, 8(%ebp)       /* argc == 2?                        */
        je    args_ok
                                /* программе передали не 2 аргумента, 
                                   вывести usage                     */
        movl  12(%ebp), %ebx    /* поместить в %ebx адрес массива argv 
                                                                     */
        pushl (%ebx)            /* argv[0]                           */
        pushl $str_usage
        call  printf
 
        movl  $1, %eax          /* выйти с кодом 1                   */
        jmp   return
 
args_ok:
        leal  -88(%ebp), %ebx   /* поместить адрес структуры в 
                                   регистр %ebx                      */
        pushl %ebx
 
        movl  12(%ebp), %ecx    /* поместить в %ecx адрес массива argv 
                                                                     */
        pushl 4(%ecx)           /* argv[1] - имя файла               */
        call  stat
 
        cmpl  $0, %eax          /* stat() вернул 0?                  */
        je    stat_ok
 
        /* stat() вернул ошибку, нужно вызвать perror(argv[1]) и 
           завершить программу */
 
        movl  12(%ebp), %ecx
        pushl 4(%ecx)
        call  perror
 
        movl  $1, %eax
        jmp   return
 
stat_ok:
        pushl 44(%ebx)          /* нужное нам поле по смещению 44    */
        pushl $printf_format
        call  printf
 
        movl  $0, %eax          /* выйти с кодом 0                   */
 
return:
        movl  %ebp, %esp
        popl  %ebp
        ret

Обратите внимание на обработку ошибок: если передано не 2 аргумента - выводим описание использования программы и выходим, если stat(2) вернул ошибку - выводим сообщение об ошибке и выходим.

Наверное, могут возникнуть некоторые сложности с пониманием, как расположены argc и argv в стеке. Допустим, вы запустили программу как

 
[user@host:~]$ ./program test-file

Тогда стек будет выглядеть приблизительно так:

.                        .
.                        .
.                        .
+------------------------+ 0x0000EFE4  <-- %ebp - 88
|       struct stat      |
+------------------------+ 0x0000F040  <-- %ebp
|  старое значение %ebp  |
+------------------------+ 0x0000F044  <-- %ebp + 4
|     адрес возврата     |
+------------------------+ 0x0000F048  <-- %ebp + 8
|          argc          |
+------------------------+ 0x0000F04C  <-- %ebp + 12
|  указатель на argv[0]  | ---------------------------- 
+------------------------+ 0x0000F050  <-- %ebp + 16   | 
.                        .              --------------- 
.                        .              | 
.                        .              V 
                                 +-------------+        +-------------+
                                 | argv[0]     | ----- > |  "./program " |
                                 +-------------+        +-------------+
                                 | argv[1]     | -\
                                 +-------------+   \    +-------------+
                                 | argv[2] = 0 |    \- > |  "test-file " |
                                 +-------------+        +-------------+

Таким образом, в стек помещается два параметра: argc и указатель на первый элемент массива argv[]. Где-то в памяти расположен блок из трёх указателей: указатель на строку "./program ", указатель на строку "test-file " и указатель NULL. Нам в стеке передали адрес этого блока памяти.

Программа: печать файла наоборот

Напишем программу, которая читает со стандартного ввода всё до конца файла, а потом выводит введённые строки в обратном порядке. Для этого мы во время чтения будем помещать строки в связный список, а потом пройдем этот список в обратном порядке и напечатаем строки.

Внимание! Сохраните исходный код этой программы в файл с расширением .S - S в верхнем регистре.

.data
printf_format:
        .string  " <%s >\n "

#define READ_CHUNK 128

.text

/* char *read_str(int *is_eof) */
read_str:
        pushl %ebp
        movl  %esp, %ebp

        pushl %ebx              /* сохранить регистры                */
        pushl %esi
        pushl %edi

        movl  $0,   %ebx        /* прочитано байт                    */
        movl  $READ_CHUNK, %edi /* размер буфера                     */
        pushl %edi
        call  malloc
        addl  $4, %esp          /* убрать аргументы                  */
        movl  %eax, %esi        /* указатель на начало буфера        */
        decl  %edi              /* в конце должен быть нулевой байт, 
                                   зарезервировать место для него    */

        pushl stdin             /* fgetc() всегда будет вызываться с 
                                   этим аргументом                   */

1: /* read_start */
        call  fgetc             /* прочитать 1 символ                */
        cmpl  $0xa, %eax        /* новая строка  '\n '?                */
        je    2f                /* read_end                          */
        cmpl  $-1, %eax         /* конец файла?                      */
        je    4f                /* eof_yes                           */
        movb  %al, (%esi,%ebx,1)  /* записать прочитанный символ в 
                                   буфер                             */
        incl  %ebx              /* инкрементировать счётчик 
                                   прочитанных байт                  */
        cmpl  %edi, %ebx        /* буфер заполнен?                   */
        jne   1b                /* read_start                        */

        addl  $READ_CHUNK, %edi /* увеличить размер буфера           */
        pushl %edi              /* размер                            */
        pushl %esi              /* указатель на буфер                */
        call  realloc
        addl  $8, %esp          /* убрать аргументы                  */
        movl  %eax, %esi        /* результат в %eax - новый указатель 
                                                                     */
        jmp   1b                /* read_start                        */
2: /* read_end */

3: /* eof_no */
        movl  8(%ebp), %eax     /* *is_eof = 0                       */
        movl  $0, (%eax)
        jmp   5f                /* eof_end                           */
4: /* eof_yes */
        movl  8(%ebp), %eax     /* *is_eof = 1                       */
        movl  $1, (%eax)
5: /* eof_end */

        movb  $0, (%esi,%ebx,1) /* записать в конец буфера  '\0 '      */

        movl  %esi, %eax        /* результат в %eax                  */

        addl  $4, %esp          /* убрать аргумент fgetc()           */

        popl  %edi              /* восстановить регистры             */
        popl  %esi              
        popl  %ebx

        movl  %ebp, %esp
        popl  %ebp
        ret

/*
struct list_node
{
  struct list_node *prev;
  char *str;
};
*/

.globl main
main:
        pushl %ebp
        movl  %esp, %ebp

        subl  $4, %esp          /* int is_eof;                       */

        movl  $0, %edi          /* в %edi будет храниться указатель на 
                                   предыдущую структуру              */

1: /* read_start */
        leal  -4(%ebp), %eax    /* %eax =  is_eof;                   */
        pushl %eax
        call  read_str
        movl  %eax, %esi        /* указатель на прочитанную строку 
                                   поместить в %esi                  */

        pushl $8                /* выделить 8 байт под структуру     */
        call  malloc

        movl  %edi, (%eax)      /* указатель на предыдущую структуру */
        movl  %esi, 4(%eax)     /* указатель на строку               */

        movl  %eax, %edi        /* теперь эта структура - предыдущая */

        addl  $8, %esp          /* убрать аргументы                  */

        cmpl  $0, -4(%ebp)      /* is_eof == 0?                      */
        jne   2f
        jmp   1b
2: /* read_end */


3: /* print_start */
                                /* просматривать список в обратном 
                                   порядке, так что в %edi адрес 
                                   текущей структуры                 */
        pushl 4(%edi)           /* указатель на строку из текущей 
                                   структуры                         */
        pushl $printf_format
        call  printf            /* вывести на экран                  */

        addl  $4, %esp          /* убрать из стека только 
                                   $printf_format                    */
        call  free              /* освободить память, занимаемую 
                                   строкой                           */

        pushl %edi              /* указатель на структуру для 
                                   освобождения памяти               */
        movl  (%edi), %edi      /* заменить указатель в %edi на 
                                   следующий                         */
        call  free              /* освободить память, занимаемую 
                                   структурой                        */

        addl  $8, %esp          /* убрать аргументы                  */

        cmpl  $0, %edi          /* адрес новой структуры == NULL?    */
        je    4f
        jmp   3b
4: /* print_end */

        movl  $0, %eax          /* выйти с кодом 0                   */

return:
        movl  %ebp, %esp
        popl  %ebp
        ret

Для того, чтобы послать с клавиатуры сигнал о конце файла, нажмите Ctrl-D

 
[user@host:~]$ gcc print.S -o print
[user@host:~]$ ./print
aaa
bbbb
ccccc
^D < >
 <ccccc >
 <bbbb >
 <aaa >

Обратите внимание, что мы ввели 4 строки: "aaa ", "bbbb ", "ccccc ", " ".

В этой программе был использован некоторый новый синтаксис. Во-первых, вы видите директиву препроцессора #define. Препроцессор Си (cpp) может быть использован для обработки исходного кода на ассемблере: нужно всего лишь использовать расширение .S для файла с исходным кодом. Файлы с таким расширением gcc предварительно обрабатывает препроцессором cpp, после чего компилирует как обычно.

Во-вторых, были использованы метки-числа, причём некоторые из них повторяются в двух функциях. Почему бы не использовать текстовые метки, как в предыдущих примерах? Можно, но они должны быть уникальными. Например, если бы мы определили метку read_start и в функции read_str, и в main, GCC бы выдал ошибку при компиляции:

 
[user@host:~]$ gcc print.S
print.S: Assembler messages:
print.S:85: Error: symbol `read_start ' is already defined

Поэтому, используя текстовые метки, приходится каждый раз придумывать уникальное имя. А можно использовать метки-числа, компилятор преобразует их в уникальные имена сам. Чтобы поставить метку, просто используйте любое положительное число в качестве имени. Чтобы сослаться на метку, которая определена ранее, используйте Nb (мнемоническое значение - backward), а чтобы сослаться на метку, которая определена дальше в коде, используйте Nf (мнемоническое значение - forward).

Операции с цепочками данных

При обработке данных часто приходится иметь дело с цепочками данных. Цепочка, как подсказывает название, представляет собой массив данных - несколько переменных одного размера, расположенных друг за другом в памяти. В Си вы использовали массив и индексную переменную, например, argv[i]. Но в ассемблере для последовательной обработки цепочек есть специализированные команды. Синтаксис:

 lods
 stos

"Странно ", - скажет кто-то, - "откуда эти команды знают, где брать данные и куда их записывать? Ведь у них и аргументов-то нет! " Вспомните про регистры %esi и %edi и про их немного странные имена: "индекс источника " (англ. source index) и "индекс приёмника " (англ. destination index). Так вот, все цепочечные команды подразумевают, что в регистре %esiнаходится указатель на следующий необработанный элемент цепочки-источника, а в регистре %edi - указатель на следующий элемент цепочки-приёмника.

Направление просмотра цепочки задаётся флагом df: 0 - просмотр вперед, 1 - просмотр назад.

Итак, команда lods загружает элемент из цепочки-источника в регистр %eax/%ax/%al (размер регистра выбирается в зависимости от суффикса команды). После этого значение регистра %esi увеличивается или уменьшается (в зависимости от направления просмотра) на значение, равное размеру элемента цепочки.

Команда stos записывает содержимое регистра %eax/%ax/%al в цепочку-приёмник. После этого значение регистра %edi увеличивается или уменьшается (в зависимости от направления просмотра) на значение, равное размеру элемента цепочки.

Вот пример программы, которая работает с цепочечными командами. Конечно же, она занимается бестолковым делом, но в противном случае она была бы гораздо сложнее. Она увеличивает каждый байт строки str_in на 1, то есть заменяет a на b, b на с, и так далее.

.data
printf_format:
        .string  "%s\n "

str_in:
        .string  "abc123()!@!777 "
        .set str_in_length, .-str_in

.bss
str_out:
        .space str_in_length

.text
.globl main
main:
        pushl %ebp
        movl  %esp, %ebp

        movl  $str_in, %esi     /* цепочка-источник                  */
        movl  $str_out, %edi    /* цепочка-приёмник                  */

        movl  $str_in_length - 1, %ecx  /* длина строки без нулевого 
                                   байта (нулевой байт не обрабатываем)
                                                                     */
1:
        lodsb                   /* загрузить байт из источника в %al */
        incb  %al               /* произвести какую-то операцию с %al 
                                                                     */
        stosb                   /* сохранить %al в приёмнике         */
        loop  1b

        movsb                   /* копировать нулевой байт           */

        /* важно: сейчас %edi указывает на конец цепочки-приёмника */

        pushl $str_out
        pushl $printf_format
        call  printf            /* вывести на печать                 */

        movl  $0, %eax

        movl  %ebp, %esp
        popl  %ebp
        ret
[user@host:~]$ ./stringop
bcd234)* "A "888
[user@host:~]$ 

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

 movs
 cmps
 scas

Размер элементов цепочки, которые обрабатывают эти команды, зависит от использованного суффикса команды.

Команда movs выполняет копирование одного элемента из цепочки-источника в цепочку-приёмник.

Команда cmps выполняет сравнение элемента из цепочки-источника и цепочки-приёмника (фактически, как и cmp, выполняет вычитание, источник - приёмник, результат никуда не записывается, но флаги устанавливаются).

Команда scas предназначена для поиска определённого элемента в цепочке. Она сравнивает содержимое регистра %eax/%ax/%al и содержимое элемента цепочки (выполняется вычитание %eax/%ax/%al - элемент_цепочки, результат не записывается, но флаги устанавливаются). Адрес цепочки должен быть помещён в регистр %edi.

После того, как эти команды выполнили своё основное действие, они увеличивают/уменьшают индексные регистры на размер элемента цепочки. Подчеркну тот факт, что эти команды обрабатывают только один элемент цепочки. Таким образом, нужно организовать что-то вроде цикла для обработки всей цепочки. Для этих целей существуют префиксы команд:

 rep
 repe/repz
 repne/repnz

Эти префиксы ставятся перед командой, например: repe scas. Префикс организовывает как бы цикл из одной команды, при этом с каждым шагом цикла значение регистра %ecx автоматически уменьшается на 1.

Также следует указать команды для управления флагом df:

 cld
 std

cld (CLear Direction flag) сбрасывает флаг df.

std (SeT Direction flag) устанавливает флаг df.

Пример: memcpy

Вооружившись новыми знаниями, попробуем заново изобрести функцию memcpy(3):

.data
printf_format:
        .string  "%s\n "

str_in:
        .string  "abc123()!@!777 "
        .set str_in_length, .-str_in

.bss
str_out:
        .space str_in_length

.text

/* void *my_memcpy(void *dest, const void *src, size_t n); */

my_memcpy:
        pushl %ebp
        movl  %esp, %ebp

        pushl %esi
        pushl %edi

        movl  8(%ebp), %edi     /* цепочка-назначение                */
        movl  12(%ebp), %esi    /* цепочка-источник                  */
        movl  16(%ebp), %ecx    /* длина                             */

        rep movsb

        movl  8(%ebp), %eax     /* вернуть dest                      */

        popl  %edi
        popl  %esi

        movl  %ebp, %esp
        popl  %ebp
        ret

.globl main
main:
        pushl %ebp
        movl  %esp, %ebp

        pushl $str_in_length
        pushl $str_in
        pushl $str_out
        call  my_memcpy

        pushl $str_out
        pushl $printf_format
        call  printf

        movl  $0, %eax

        movl  %ebp, %esp
        popl  %ebp
        ret

Вы, наверно, будете удивлены, если я вам скажу, что эта реализация memcpy всё равно не самая быстрая. "Что ещё можно сделать? " - спросите вы. Ведь мы можем копировать данные не по одному байту, а по целых 4 байта за раз при помощи movsl. Тогда у нас получается приблизительно такой алгоритм: копируем как можно больше данных блоками по 4 байта, после этого остаётся хвостик в 0, 1, 2 или 3 байта; этот остаток можно скопировать при помощи movsb. Поэтому нашу memcpy лучше переписать вот так:

/* void *my_memcpy(void *dest, const void *src, size_t n); */

my_memcpy:
        pushl %ebp
        movl  %esp, %ebp

        pushl %esi
        pushl %edi

        movl  8(%ebp), %edi     /* цепочка-назначение                */
        movl  12(%ebp), %esi    /* цепочка-источник                  */
        movl  16(%ebp), %edx    /* длина                             */

        movl  %edx, %ecx
        shrl  $2, %ecx          /* делить на 2^2 = 4; теперь в 
                                   находится %ecx количество 4-байтных 
                                   кусочков                          */
        rep movsl

        movl  %edx, %ecx
        andl  $3, %ecx          /* $3 == $0b11, оставить только два 
                                   младших бита, то есть остаток от 
                                   деления на 4                      */
        jz    1f                /* если результат 0, пропустить 
                                   цепочечную команду                */
        rep movsb
1:

        movl  8(%ebp), %eax     /* вернуть dest                      */

        popl  %edi
        popl  %esi

        movl  %ebp, %esp
        popl  %ebp
        ret

Пример: strlen

Теперь strlen: нам нужно сравнить каждый байт цепочки с 0, остановиться, когда найдём 0, и вернуть количество ненулевых байт. Как счетчик мы будем использовать регистр %ecx, который автоматически изменяют все префиксы. Но префиксы уменьшают счетчик и прекращают выполнение команды, когда %ecx равен 0. Поэтому перед цепочечной командой мы поместим в %ecx число 0xffffffff, и этот регистр будет уменьшатся в ходе выполнения цепочечной команды. Результат получится в обратном коде, поэтому мы используем команду not для инвертирования всех битов. И после этого ещё уменьшим результат на 1, так как нулевой байт тоже был посчитан.

.data
printf_format:
        .string  "%u\n "

str_in:
        .string  "abc123()!@!777 "

.text

/* size_t my_strlen(const char *s); */

my_strlen:
        pushl %ebp
        movl  %esp, %ebp

        pushl %edi

        movl  8(%ebp), %edi             /* цепочка */

        movl  $0xffffffff, %ecx
        xorl  %eax, %eax                /* %eax = 0 */

        repne scasb

        notl  %ecx
        decl  %ecx

        movl  %ecx, %eax

        popl  %edi

        movl  %ebp, %esp
        popl  %ebp
        ret

.globl main
main:
        pushl %ebp
        movl  %esp, %ebp

        pushl $str_in
        call  my_strlen

        pushl %eax
        pushl $printf_format
        call  printf

        movl  $0, %eax

        movl  %ebp, %esp
        popl  %ebp
        ret

Как реализованы другие стандартные цепочечные функции, можно посмотреть, например, в исходных кодах ядра Linux в файлах /usr/src/linux/arch/x86/include/asm/string_*.h,/usr/src/linux/arch/x86/lib/{mem*,str*}. Оттуда взяты все примеры для этого раздела.

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

Конструкция switch

Оператор switch языка Си можно переписать на ассемблере разными способами. Рассмотрим несколько вариантов того, какими могут быть значения у case:

Рассмотрим решение для первого случая. Вспомним, что команда jmp принимает адрес не только в виде непосредственного значения (метки), но и как обращение к памяти. Значит, мы можем осуществлять переход на адрес, вычисленный в процессе выполнения. Теперь вопрос: как можно вычислить адрес? А нам не нужно ничего вычислять, мы просто поместим все адреса case-веток в массив. Пользуясь проверяемым значением как индексом массива, выбираем нужный адрес case-ветки. Таким образом, процессор всё вычислит за нас. Посмотрите на следующий код:

.data
printf_format:
        .string  "%u\n "

.text
.globl main

main:
        pushl %ebp
        movl  %esp, %ebp

        movl  $1, %eax          /* получить в %eax некоторое 
                                   интересующее нас значение         */

                                /* мы предусмотрели случаи только для 
                                   0, 1, 3, поэтому,                 */
        cmpl  $3, %eax          /* если %eax больше 3 
                                   (как беззнаковое),                */
        ja    case_default      /* перейти к default                 */

        jmp   *jump_table(,%eax,4) /* перейти по адресу, содержащемуся 
                                   в памяти jump_table + %eax*4      */

.section .rodata
        .p2align 4
jump_table:                     /* массив адресов                    */
        .long case_0            /* адрес этого элемента массива: 
                                                     jump_table + 0  */
        .long case_1            /*                   jump_table + 4  */
        .long case_default      /*                   jump_table + 8  */
        .long case_3            /*                   jump_table + 12 */
.text

case_0:
        movl  $5, %ecx          /* тело case-блока                   */
        jmp   switch_end        /* имитация break - переход в конец 
                                   switch                            */

case_1:
        movl  $15, %ecx
        jmp   switch_end

case_3:
        movl  $35, %ecx
        jmp   switch_end

case_default:
        movl  $100, %ecx

switch_end:

        pushl %ecx              /* вывести %ecx на экран, выйти      */
        pushl $printf_format
        call  printf

        movl  $0, %eax

        movl  %ebp, %esp
        popl  %ebp
        ret

Этот код эквивалентен следующему коду на Си:

#include  <stdio.h >

int main()
{
  unsigned int a, c;

  a = 1;
  switch(a)
  {
    case 0:
      c = 5;
      break;

    case 1:
      c = 15;
      break;

    case 3:
      c = 35;
      break;

    default:
      c = 100;
      break;
  }

  printf( "%u\n ", c);
  return 0;
}

Смотрите: в секции .rodata (данные только для чтения) создаётся массив из 4 значений. Мы обращаемся к нему как к обычному массиву, индексируя его по %eax:jump_table(,%eax,4). Но зачем перед этим стоит звёздочка? Она означает, что мы хотим перейти по адресу, содержащемуся в памяти по адресу jump_table(,%eax,4) (если бы её не было, мы бы перешли по этому адресу и начали исполнять массив jump_table как код).

Заметьте, что тут нам понадобились значения 0, 1, 3, укладывающиеся в маленький промежуток [0; 3]. Так как для значения 2 не предусмотрено особой обработки, в массиве адресов jump_table индексу 2 соответствует case_default. Перед тем, как сделать jmp, нужно обязательно убедиться, что проверяемое значение входит в наш промежуток, и если не входит - перейти на default. Если вы этого не сделаете, то, когда попадётся значение, находящееся за пределами массива, программа, в лучшем случае, получит segmentation fault, а в худшем (если рядом с этим масивом адресов в памяти окажется еще один массив адресов) код продолжит исполнение вообще непонятно где.

Теперь рассмотрим случай, когда значения для веток case находятся на большом расстоянии друг от друга. Очевидно, что способ с массивом адресов не подходит, иначе массив занимал бы большое количество памяти и содержал в основном адреса ветки default. В этом случае лучшее, что может сделать программист, - выразить switch как последовательное сравнение со всеми перечисленными значениями. Если значений довольно много, придётся применить немного логики: приблизительно прикинуть, какие ветки будут исполняться чаще всего, и отсортировать их в таком порядке в коде. Это нужно для того, чтобы наиболее часто исполняемые ветки исполнялись после маленького числа сравнений. Допустим, у нас есть варианты 5, 38, 70 и 1400, причём 70 будет появляться чаще всего:

.data
printf_format:
        .string  "%u\n "

.text
.globl main

main:
        pushl %ebp
        movl  %esp, %ebp

        movl  $70, %eax         /* получить в %eax некоторое 
                                   интересующее нас значение         */

        cmpl  $70, %eax
        je    case_70

        cmpl  $5, %eax
        je    case_5

        cmpl  $38, %eax
        je    case_38

        cmpl  $1400, %eax
        je    case_1400

case_default:
        movl  $100, %ecx
        jmp   switch_end

case_5:
        movl  $5, %ecx
        jmp   switch_end

case_38:
        movl  $15, %ecx
        jmp   switch_end

case_70:
        movl  $25, %ecx
        jmp   switch_end

case_1400:
        movl  $35, %ecx

switch_end:

        pushl %ecx

        pushl $printf_format
        call  printf

        movl  $0, %eax

        movl  %ebp, %esp
        popl  %ebp
        ret

Единственное, на что хочется обратить внимание, - на расположение ветки default: если все сравнения оказались ложными, код default выполняется автоматически.

Наконец, третий, комбинированный, вариант. Путь имеем варианты 35, 36, 37, 39, 1200, 1600 и 7000. Тогда мы видим промежуток [35; 39] и ещё три числа. Код будет выглядеть приблизительно так:

        movl  $1, %eax          /* получить в %eax некоторое 
                                   интересующее нас значение         */

        cmpl  $35, %eax
        jb    case_default

        cmpl  $39, %eax
        ja    switch_compare

        jmp   *jump_table-140(,%eax,4)

.section .rodata
        .p2align 4
jump_table:
        .long case_35
        .long case_36
        .long case_37
        .long case_default
        .long case_39
.text

switch_compare:
        cmpl  $1200, %eax
        jmp   case_1200

        cmpl  $1600, %eax
        jmp   case_1600

        cmpl  $7000, %eax
        jmp   case_7000

case_default:
        /* ... */
        jmp   switch_end

case_35:
        /* ... */
        jmp   switch_end

        ... ещё код ...
switch_end:

Заметьте, что промежуток начинается с числа 35, а не с 0. Для того, чтобы не производить вычитание 35 отдельной командой и не создавать массив, в котором от 0 до 34 идёт адреса метки default, сначала проверяется принадлежность числа промежутку [35; 39], а затем производится переход, но массив адресов считается размещённым на 35 двойных слов "ниже " в памяти (то есть, на 35 ? 4 = 140 байт). В результате получается, что адрес перехода считывается из памяти по адресу jump_table - 35*4 + %eax*4 = jump_table + (%eax - 35)*4. Выиграли одно вычитание.

В этом примере, как и в предыдущих, имеет смысл переставить некоторые части этого кода в начало, если вы заранее знаете, какие значения вам придётся обрабатывать чаще всего.

Пример: интерпретатор языка Brainfuck

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

В начальном состоянии все ячейки содержат значение 0, а текущей является крайняя левая ячейка.

Вот несколько программ с объяснениями:

+ >+ >+        Устанавливает первые три ячейки в 1
[-]          Обнуляет текущую ячейку
[ > > >+ < < <-]   Перемещает значение текущей ячейки в ячейку, расположенную
              "тремя шагами правее "

Интерпретация программы состоит из двух шагов: загрузка программы и собственно исполнение. Во время загрузки следует проверить корректность программы (соответствие []) и расположить код программы в памяти в удобном для выполнения виде. Для этого каждой команде присваивается номер операции, начиная с 0, - для того, чтобы можно было выполнять операции при помощи помощи перехода по массиву адресов, как в switch.

Большинство программ на Brainfuck содержат последовательности одинаковых команд < > + -, которые можно выполнять не по одной, а все сразу. Например, выполняя код +++++, можно выполнить пять раз увеличение на 1, или один раз увеличение на 5. Таким образом, довольно простыми средствами можно сильно оптимизировать выполнение программы.

Вот программы, которые вызовут ошибки загрузки:

[       No matching  '] ' found for a  '[ '
]       No matching  '[ ' found for a  '] '

А эти программы вызовут ошибки выполнения:

 <       Memory underflow
+[ >+]   Memory overflow

Исходный код:

#define BF_PROGRAM_SIZE 1024
#define BF_MEMORY_CELLS 32768
#define BF_MEMORY_SIZE BF_MEMORY_CELLS*4

#define BF_OP_LOOP_START 0
#define BF_OP_LOOP_END   1
#define BF_OP_MOVE_LEFT  2
#define BF_OP_MOVE_RIGHT 3
#define BF_OP_INC        4
#define BF_OP_DEC        5
#define BF_OP_PUTC       6
#define BF_OP_GETC       7
#define BF_OP_EXIT       8

.section .rodata
str_memory_underflow:
        .string  "Memory underflow\n "

str_memory_overflow:
        .string  "Memory overflow\n "

str_loop_start_not_found:
        .string  "No matching  '[ ' found for a  '] '\n "

str_loop_end_not_found:
        .string  "No matching  '] ' found for a  '[ '\n "

.data
bf_program_ptr:
        .long 0

bf_program_size:
        .long 0

/*
 * Программа загружается в память вот так:
 * =============================
 * код_операции, операнд,
 * код_операции, операнд,
 * код_операции, операнд, ...
 * =============================
 * И код_операции, и операнд занимают по 4 байта.
 * Таким образом, одна команда занимает в памяти 8 байт.
 *
 * Для команды [ (начало цикла) операндом является номер команды, 
 * следующий за концом цикла.
 *
 * Для команды ] (конец цикла) операндом является номер команды-начала 
 * цикла ].
 *
 * Для остальных команд ( <  > + - . ,) операнд задаёт количество 
 * повторений этой команды.  Например, для кода +++++ должен быть 
 * сгенерирован код операции BF_OP_INC с операндом 5, который при 
 * выполнении увеличит текущую ячейку на 5.
 */

.text
.globl main
main:
        pushl %ebp
        movl  %esp, %ebp

/* ******************************************* */
/* загрузка программы                          */
/* ******************************************* */

        movl  $BF_PROGRAM_SIZE, %ecx
        movl  %ecx, bf_program_size
        pushl %ecx
        call  malloc
        movl  %eax, bf_program_ptr

        movl  %eax, %ebx        /* %ebx - указатель на блок памяти, 
                                   содержащий внутреннее представление 
                                   программы                         */
        xorl  %ecx, %ecx        /* %ecx - номер текущей команды      */
        xorl  %esi, %esi        /* %esi - предыдущая команда, символ */

bf_read_loop:
        pushl %ecx
        pushl stdin
        call  fgetc
        addl  $4, %esp
        popl  %ecx

        cmpl  $-1, %eax
        je    bf_read_end

        cmpl  $ '[, %eax         /* команды, которые всегда 
                                   обрабатываются по одной: [ и ]    */
        je    bf_read_loop_start

        cmpl  $ '], %eax
        je    bf_read_loop_end

        cmpl  %esi, %eax        /* текущая команда такая же, как и 
                                   предыдущая?                       */
        jne   not_dupe

        incl  -4(%ebx,%ecx,8)   /* такая же. Но %ecx указывает на 
                                   следующую команду, поэтому 
                                   используем отрицательное смещение -4
                                                                     */
        jmp   bf_read_loop

not_dupe:                       /* другая                            */
        cmpl  $ ' <, %eax
        je    bf_read_move_left

        cmpl  $ ' >, %eax
        je    bf_read_move_right

        cmpl  $ '+, %eax
        je    bf_read_inc

        cmpl  $ '-, %eax
        je    bf_read_dec

        cmpl  $ '., %eax
        je    bf_read_putc

        cmpl  $ ',, %eax
        je    bf_read_getc

        jmp   bf_read_loop

bf_read_loop_start:
        movl  $BF_OP_LOOP_START, (%ebx,%ecx,8)
        movl  $0, 4(%ebx,%ecx,8)
        jmp   bf_read_switch_end

bf_read_loop_end:
        movl  $BF_OP_LOOP_END, (%ebx,%ecx,8)
        movl  %ecx, %edx
bf_read_loop_end_find:
        testl %edx, %edx
        jz    bf_read_loop_end_not_found
        decl  %edx
        cmpl  $0, 4(%ebx,%edx,8)
        je    bf_read_loop_end_found
        jmp   bf_read_loop_end_find
bf_read_loop_end_not_found:
        jmp   loop_start_not_found
bf_read_loop_end_found:
        leal  1(%ecx), %edi
        movl  %edi, 4(%ebx,%edx,8)
        movl  %edx, 4(%ebx,%ecx,8)
        jmp   bf_read_switch_end

bf_read_move_left:
        movl  $BF_OP_MOVE_LEFT, (%ebx,%ecx,8)
        jmp   bf_read_switch_end_1

bf_read_move_right:
        movl  $BF_OP_MOVE_RIGHT, (%ebx,%ecx,8)
        jmp   bf_read_switch_end_1

bf_read_inc:
        movl  $BF_OP_INC, (%ebx,%ecx,8)
        jmp   bf_read_switch_end_1

bf_read_dec:
        movl  $BF_OP_DEC, (%ebx,%ecx,8)
        jmp   bf_read_switch_end_1

bf_read_putc:
        movl  $BF_OP_PUTC, (%ebx,%ecx,8)
        jmp   bf_read_switch_end_1

bf_read_getc:
        movl  $BF_OP_GETC, (%ebx,%ecx,8)

bf_read_switch_end_1:
        movl  $1, 4(%ebx,%ecx,8)

bf_read_switch_end:

        movl  %eax, %esi        /* сохранить текущую команду для 
                                   сравнения                         */

        incl  %ecx

        leal  (,%ecx,8), %edx   /* блок памяти закончился?           */
        cmpl  bf_program_size, %edx
        jne   bf_read_loop

        addl  $BF_PROGRAM_SIZE, %edx  /* увеличить размер блока памяти 
                                                                     */
        movl  %edx, bf_program_size
        pushl %ecx
        pushl %edx
        pushl %ebx
        call  realloc
        addl  $8, %esp
        popl  %ecx
        movl  %eax, bf_program_ptr
        movl  %eax, %ebx

        jmp   bf_read_loop

bf_read_end:

        movl  $BF_OP_EXIT, (%ebx,%ecx,8)  /* последней добавить 
                                             команду выхода          */
        movl  $1, 4(%ebx,%ecx,8)

/*
 * Ищем незакрытые  '[ ':
 * Ищем 0 в поле операнда.  Саму команду не проверяем, так как 0 может 
 * быть операндом только у  '[ '.
 */

        xorl  %edx, %edx
1:
        cmpl  $0, 4(%ebx,%ecx,8)
        je    loop_end_not_found
        incl  %ecx
        testl %edx, %ecx
        je    2f
        jmp   1b
2:

/* ******************************************* */
/* выполнение программы                        */
/* ******************************************* */


        pushl $BF_MEMORY_SIZE   /* выделить блок памяти для памяти 
                                   программы                         */
        call  malloc
        addl  $4, %esp
        movl  %eax, %esi

        xorl  %ecx, %ecx        /* %ecx - номер текущей команды      */
        xorl  %edi, %edi        /* %edi - номер текущей ячейки памяти 
                                                                     */

interpreter_loop:
        movl  (%ebx,%ecx,8), %eax     /* %eax - команда              */
        movl  4(%ebx,%ecx,8), %edx    /* %edx - операнд              */

        jmp   *interpreter_jump_table(,%eax,4)
.section .rodata
interpreter_jump_table:
        .long bf_op_loop_start
        .long bf_op_loop_end
        .long bf_op_move_left
        .long bf_op_move_right
        .long bf_op_inc
        .long bf_op_dec
        .long bf_op_putc
        .long bf_op_getc
        .long bf_op_exit
.text

bf_op_loop_start:
        cmpl  $0, (%esi,%edi,4)
        je    bf_op_loop_start_jump
        incl  %ecx
        jmp   interpreter_loop
bf_op_loop_start_jump:
        movl  %edx, %ecx
        jmp   interpreter_loop

bf_op_loop_end:
        movl  %edx, %ecx
        jmp   interpreter_loop

bf_op_move_left:
        movl  %edi, %eax
        subl  %edx, %eax        /* если номер новой ячейки 
                                   памяти  < 0 ...                    */
        js    memory_underflow
        movl  %eax, %edi
        incl  %ecx
        jmp   interpreter_loop

bf_op_move_right:
        movl  %edi, %eax
        addl  %edx, %eax        /* если номер новой ячейки памяти 
                                   больше допустимого...             */
        cmpl  $BF_MEMORY_CELLS, %eax
        jae   memory_overflow
        movl  %eax, %edi
        incl  %ecx
        jmp   interpreter_loop

bf_op_inc:
        addl  %edx, (%esi,%edi,4)
        incl  %ecx
        jmp   interpreter_loop

bf_op_dec:
        subl  %edx, (%esi,%edi,4)
        incl  %ecx
        jmp   interpreter_loop

bf_op_putc:
        xorl  %eax, %eax
        movb  (%esi,%edi,4), %al
        pushl %ecx
        pushl %edi
        movl  %edx, %edi
        pushl stdout
        pushl %eax
bf_op_putc_loop:
        call  fputc
        decl  %edi
        testl %edi, %edi
        jne   bf_op_putc_loop
        addl  $4, %esp
        call  fflush
        addl  $4, %esp
        popl  %edi
        popl  %ecx
        incl  %ecx
        jmp   interpreter_loop

bf_op_getc:
        pushl %ecx
        pushl %edi
        movl  %edx, %edi
        pushl stdin
bf_op_getc_loop:
        call  getc
        decl  %edi
        testl %edi, %edi
        jne   bf_op_getc_loop
        addl  $4, %esp
        movl  %eax, (%esi,%edi,4)
        popl  %edi
        popl  %ecx
        incl  %ecx
        jmp   interpreter_loop

bf_op_exit:
        xorl  %eax, %eax
        jmp   interpreter_exit

/* ******************************************* */
/* обработчики ошибок                          */
/* ******************************************* */

memory_underflow:
        pushl $str_memory_underflow
        call  printf
        movl  $1, %eax
        jmp   interpreter_exit

memory_overflow:
        pushl $str_memory_overflow
        call  printf
        movl  $1, %eax
        jmp   interpreter_exit

loop_start_not_found:
        pushl $str_loop_start_not_found
        call  printf
        movl  $1, %eax
        jmp   interpreter_exit

loop_end_not_found:
        pushl $str_loop_end_not_found
        call  printf
        movl  $1, %eax

interpreter_exit:
        movl  %ebp, %esp
        popl  %ebp
        .size main, .-main

Булевы выражения

Рассмотрим такой код на языке Си:

if(((a  > 5)    (b  < 10)) || (c == 0))
{
  do_something();
}

В принципе, булево выражение можно вычислять как обычное арифметическое, то есть в такой последовательности:

Такой способ вычисления называется полным. Можем ли мы вычислить значение этого выражения быстрее? Смотрите, если c == 0, то всё выражение будет иметь значение true в любом случае, независимо от a и b. А вот если c != 0, то приходится проверять значения a и b. Таким образом, наш код (фактически) превращается в такой:

if(c == 0)
{
  goto do_it;
}
if((a  > 5)    (b  < 10))
{
  goto do_it;
}
goto dont_do_it;

do_it:
  do_something();

dont_do_it:

В принципе, можно пойти дальше: если a <= 5, нас не интересует сравнение b < 10: всё равно выражение равно false.

if(c == 0)
{
  goto do_it;
}
if(a  > 5)
{
  if(b  < 10)
  {
    goto do_it;
  }
}
goto dont_do_it;

do_it:
  do_something();

dont_do_it:

Такой способ вычисления выражений называется сокращённым (от англ. short-circuit evaluation), потому что позволяет вычислить выражение, не проверяя всех входящих в него подвыражений. Можно вывести такие формальные правила:

В принципе, сокращённое вычисление булевых выражений помогает написать более быстрый (а часто и более простой) код. С другой стороны, возникают проблемы, если одно из подвыражений при вычислении вызывает побочные эффекты (англ. side effects), например вызов функции:

if((c == 0) || foo())
{
  do_something();
}

Если мы используем сокращённое вычисление и оказывается, что c == 0, то функция foo() вызвана не будет, потому что от её результата значение выражения уже не зависит. Хорошо это или плохо, зависит от конкретной ситуации, но, без сомнения, способ выполнения такого кода становится не очевидным.

Во многих языках высокого уровня сокращённое вычисление выражений требуется от компилятора стандартом языка (например, в Си). Однако, обычно задаются более строгие правила вычислений. В большинстве стандартов языков требуется, чтобы выражения соединённые оператором OR (или AND) вычислялись строго слева направо, и если очередное значение будет true (соответственно, false для AND), то вычисление данной цепочки OR-ов (AND-ов) прекращается. Но нужно отметить, что первый пример в этой главе всё равно является корректным с точки зрения стандарта Си (хотя c == 0 стоит в конце выражения, а вычисляется первым), так как сравнение локальных переменных не вызывает побочных эффектов и компилятор вправе реорганизовать код таким образом.

Теперь перейдём к тому, как это реализовывается на ассемблере. Начнём с полного вычисления:

cmpl  $5, a
/* так, а что дальше? */

Действительно, нам нужно сохранить результат сравнения в переменную. Из команд, анализирующих флаги, мы знаем только семейство jcc, но они нам не подходят. Кроме jcc, существует семейство setcc. Они проверяют состояние флагов точно так же, как и jcc. На основе флагов операнд устанавливается в 1, если проверяемое условие cc истинно, и в 0, если условие ложно.

setcc операнд

Требуется заметить, что команды setcc работают только с операндами (хранящимися в регистрах и памяти) размером один байт.

Тогда полное вычисление будет выглядеть так:

        cmpl  $5, a
        seta  %al
        cmpl  $10, b
        setb  %bl
        andb  %bl, %al
        cmpl  $0, c
        sete  %bl
        orb   %bl, %al
        jz    is_false
is_true:
        ...
is_false:
        ...

Обратите внимание, что команда or устанавливает флаги, и нам не нужно отдельно сравнивать %al с нулём.

Сокращённое вычисление:

        cmpl  $0, c
        je    is_true
        cmpl  $5, a
        jbe   is_false
        cmpl  $10, b
        jae   is_false
is_true:
        ...
is_false:
        ...

Как видите, этот код является не только более коротким, но и завершает своё исполнение, как только результат становится известен. Таким образом, сокращённое вычисление намного быстрее полного.

См. также