Упражнения. Пример 1.На языке ассемблера разработать подпрограмму пузырьковой сортировки массива

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

Решение. Вариант реализации подпрограммы сортировки SORT приводится ниже. Для работы процедуры необходимы две вспомогательные переменные CNT и ADD, размером в слово. Их можно определить в сегменте данных (как показано ниже) или выделить место в стеке (по методу хранения локальных данных процедур). Первая переменная хранит счетчик числа сравнений, а вторая – начальный адрес массива в памяти.

При каждом проходе счетчик CNT уменьшается на единицу, чтобы на следующей итерации не сортировать несколько последних уже отсортированных («всплывших» на свое место) элементов. Когда счетчик обнулится, сортировка считается завершенной.

Процедура использует регистр BX в качестве флага обмена (в начале он установлен), а регистр AX – для хранения элемента, который будет сравниваться с последующим. Если последующий элемент меньше текущего, они меняются местами и флаг обмена BX сбрасывается, сигнализируя об обмене.

CNT DW?; счетчик числа сравнений

ADD DW?; начальный адрес массива

SORT PROC

PUSH AX

PUSH BX

PUSH CX

MOV CX, [DI]; количество элементов массива

DEC CX; число проходов 0..CX-1

MOV CNT, CX; сохранить в памяти число проходов

PASS: MOV BX, 1; установить флаг обмена

DEC CNT; очередное сравнение

JZ SORT; сортировка завершена, если CNT = 0

MOV CX, CNT; число сравнений в CX

MOV DI, ADD; начальный адрес в DI

L: ADD DI, 2; переход к следующему элементу данных

MOV AX, [DI]; сохранить элемент в AX

CMP [DI+2], AX; сравнить элемент со следующим

JAE COUNT; следующий элемент меньше текущего

XCHG [DI+2], AX; обменять местами элементы

MOV [DI], AX

XOR BX, BX; обнулить флаг обмена

COUNT: LOOP L; проверить остальные элементы

CMP BX, 0; проверка на обмены

JE PASS; обмены элементов были проведены

SORT: MOV DI, ADD; восстанавливаем адрес начала списка

POP CX

POP BX

POP AX

RET

SORT ENDP

Пример 2. На языке ассемблера разработать подпрограмму бинарного поиска заданного элемента в упорядоченном массиве. Элементами массива должны быть беззнаковые целые числа размером слово. Искомый элемент должен быть помещен в регистр AX. Начальный адрес массива по-прежнему должен храниться в регистре DI, а количество элементов – в первом элементе.

Результат поиска должен быть возвращен через регистр SI и флаг CF: если значение не найдено флаг CF должен быть установлен в 1, а регистр SI содержать адрес последнего проверенного элемента; если поиск завершился успешно, флаг CF должен быть сброшен, а SI содержать адрес найденного элемента.

Решение. Процедура бинарного поиска BINSRCH приведена ниже (описание метода приведено в примере 4 главы 1). Она также использует вспомогательную переменную ARR, содержащую начальный адрес массива. Первым действием алгоритма является проверка искомого элемента на выход за границы диапазона. Для этого значение регистра AX сравнивается с первым и последним элементами массива. Если условие выхода за диапазон выполняется, устанавливается флаг CF с помощью команды STC и процедуры завершает работу. В противном случае происходит переход по метке SRCH к началу поиска элемента.

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

Затем полученный индекс SI добавляется к адресу начала массива DI. В результате происходит перемещение указателя на середину массива. Средний элемент сравнивается с искомым. Если элемент не равен искомому, поиск продолжится в левой или в правой половине массива.

В обоих случаях проверяется индекс на равенство 2 (признак окончания поиска), выполнение деления индекса SI пополам и дополнение его до ближайшего четного значения. Однако при поиске в левой половине текущий индекс SI вычитается из текущего адреса DI, а при поиске в правой половине – складывается с ним.

ARR DW?; начальный адрес списка в памяти

BINSRCH PROC

CMP AX, [DI+2]; сравнение искомого элемента с первым

JA LAST; искомое значение превосходит первый элемент

LEA SI, [DI+2]; иначе извлекаем адрес первого элемента

JE EXITF; искомый элемент равен первому

STC; устанавливаем флаг CF (элемент не найден)

EXITF: RET; выход из подпрограммы

LAST:MOV SI, ES:[DI]; определяем количество элементов

SHL SI, 1; умножаем на 2

ADD SI, DI; перемещаем указатель на последний элемент

CMP AX, ES:[SI]; сравнение искомого элемента с последним

JB SRCH; искомый элемент меньше последнего

JE EXITL; искомый элемент равен последнему

STC; устанавливаем флаг CF (элемент не найден)

EXITL: RET; выход из подпрограммы

SRCH:MOV ARR, DI; сохранение в памяти адреса начала массива

MOV SI, [DI]; определяем количество элементов

EVEN:TEST SI, 1; проверка на четность индекса

JZ ADDL; да, индекс четный

INC SI; приводим индекс к четному значению

ADDL:ADD DI, SI; определяем индекс середины массива

CMPL:CMP AX, [DI]; сравниваем искомый элемент со средним

JE EXIT; если средний элемент равен искомому, выход

JA HIGH; искомый элемент больше

CMP SI, 2; сравниваем индекс с 2

JNE SHRL; индекс больше 2

NO:STC; устанавливаем флаг CF (элемент не найден)

JE EXIT; выход из подпрограммы

SHRL:SHR SI, 1; делим индекс пополам

TEST SI, 1; проверка на четность

JZ SUBL; индекс четный

INC SI; делаем индекс четным

SUBL:SUB DI, SI; перемещаем указатель назад

JMP CMPL; переход на очередную проверку

HIGH: CMP SI, 2; сравниваем индекс с 2

JE NO; искомый элемент не найден

SHR SI, 1; делим индекс пополам

JMP EVEN

EXIT:MOV SI, DI; сохраняем адрес последнего сравнения в SI

MOV DI, ARR; восстанавливаем адрес начала списка

RET; выход из подпрограммы

BINSRCH ENDP

Контрольные вопросы

1. Каковы этапы разработки многомодульной программы на языке ассемблера?

2. Опишите структуру модуля на языке ассемблера.

3. Перечислите параметры и назначение директивы SEGMENT.

Дата добавления: 2014-11-16