Вычисление наибольшего общего делителя
Реализуем функцию, вычисляющую наибольший общий делитель двух целых чисел. Мы уже записывали алгоритм вычисления НОД на псевдокоде. На языке Си эта функция выглядит следующим образом:
int gcd(int x, int y) { // цел алг. gcd(цел x, цел y) int a, b, r; // | цел a, b, r; a = x; b = y; // | a := x; b := y; while (b != 0) { // | цикл пока b != 0 r = a % b; // | | r := a % b; a = b; // | | a := b; b = r; // | | b := r; } // | конец цикла return a; // | ответ := a; } // конец алгоритма
Вместо НОД мы назвали функцию "gcd" (от слов greatest common divizor), поскольку в языке Си русские буквы в именах функций и переменных использовать нельзя. Запишем эту программу на языке RTL. Переменные a, b, r мы будем хранить в регистрах R0, R1, R2.
// Вход в функцию: push FP; // сохраним значение FP в стеке; FP := SP; // определим новое значение FP; push R1; // сохраним значения регистров R1 push R2; // и R2 // R0 := m[FP+8]; // a := x; R1 := m[FP+12]; // b := y; L1: // метка начала цикла CC0 := R1 - 0; // сравнить b с нулем if (eq) goto L2; // если результат равен нулю, // то перейти на метку L2 R2 := R0 % R1; // r := a % b; R0 := R1; // a := b; R1 := R2; // b := r; goto L1 // перейти на метку L1 L2: // метка конца цикла // ответ уже содержится в R0 // выход из функции: pop R2; // восстановим значения R2 pop R1; // и R1 pop FP; // восстановим значение FP return; // вернемся в вызывающую программу
Эту программу можно переписать на конкретный Ассемблер, например, на Ассемблер "Masm" фирмы Microsoft для процессоров Intel 80x86. Первое, что надо сделать при переводе с RTL на Ассемблер — это распределить регистры, т.е. задать отображение виртуальных регистров R0, R1, ... на конкретные регистры данного процессора. У процессоров серии Intel 80x86 есть всего 8 общих регистров: это регистры
EAX, EBX, ECX, EDX, ESI, EDI, EBP, ESP.
Процессор Intel сконструирован таким образом, что каждый регистр выполняет в определенных командах свою особую роль (Intel 80x86 — это CISC-процессор; в RISC-процессорах все регистры равноправны).
В частности, команда деления всегда использует в качестве делимого длинное восьмибайтовое целое число, содержащееся в паре регистров (EDX, EAX), где старшие байты в регистре EDX. В результате выполнения команды деления вычисляется как частное, так и остаток от деления: частное помещается в регистр EAX, остаток — в регистр EDX.
В данной программе на языке RTL остаток от деления помещается в регистр R2. Поэтому регистр R2 удобно отобразить на регистр EDX, это позволит избежать лишних пересылок результата из одного регистра в другой. Итак, зафиксируем следующее распределение регистров:
R0 — EAX R1 — EBX R2 — EDX FP — EBP SP — ESP
После того как распределены регистры, остается только переписать каждую строку RTL программы на конкретный Ассемблер. Для этого необходимо знать ограниченный набор команд, реализующих операции языка RTL в конкретном Ассемблере. Например, в нашем случае операция пересылки из одного регистра в другой или из памяти в регистр реализуется командой mov, операция деления реализуется командой div и т.д. Программа на языке Ассемблера Intel 80386 записывается следующим образом:
.386 .model flat, stdcall .code
gcd: ; Вход в функцию: push EBP ; сохраним старое значение EBP mov EBP, ESP ; определим новое значение EBP push EBX ; сохраним значения EBX push EDX ; и EDX. ; mov EAX, [EBP+8] ; EAX := x mov EBX, [EBP+12] ; EBX := y L1: ; метка начала цикла cmp EBX, 0 ; сравнить EBX с нулем je L2 ; если результат равен нулю, ; то перейти на метку L2 mov EDX, 0 ; div EBX ; EDX := EAX % EBX mov EAX, EBX ; EAX := EBX mov EBX, EDX ; EBX := EDX jmp L1 ; перейти на метку L1 L2: ; метка конца цикла ; ответ уже содержится в EAX ; выход из функции: pop EDX ; восстановим значения EDX pop EBX ; и EBX pop EBP ; восстановим значение EBP ret ; возврат из функции
public gcd end