Основы программирования

Вычисление наибольшего общего делителя


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

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


Содержание раздела