Продолжим изучение Ассемблера. В этой статье я покажу, как написать программу для поиска простых чисел на Ассемблер.
Другие статьи на тему Ассемблер:
Напомню, простые числа — это такие, которые делятся только на единицу и на себя. Если у них есть другие делители, то такие числа называются составными. Для поиска простых чисел существует целая куча алгоритмов. Мы воспользуемся одним из них — решетом Эратосфена.
Программа для поиска простых чисел на Ассемблер
В чем суть алгоритма? Он постепенно отфильтровывает все числа за исключением простых. Начиная с числа 2 и заканчивая n. Число n задаешь ты. Как только алгоритм натыкается на очередное простое число a, он пробегает по всему списку до конца (до n) и вычеркивает из него все числа, которые делятся на a. Есть наглядная анимированная гифка. Посмотри ее, и сразу поймешь, как работает решето Эратосфена.
Что здесь происходит?
- Начинаем с двойки.
- Смотрим: очередное число a помечено как составное? Да — идем на шаг 5.
- Если не помечено (не вычеркнуто), значит, a — простое.
- Пробегаем по всему списку и вычеркиваем все числа, которые делятся на a.
- Инкрементируем текущее число.
- Повторяем шаги 2–5, пока не достигли n.
Каким образом будем бегать по списку и вычеркивать оттуда составные числа? Сначала нам этот список надо создать! Причем в регистры его точно втиснуть не получится. Нам потребуется битовый массив размером n. По биту на каждое число от 2 до n (или вполовину меньше, если мы оптимизируем алгоритм так, чтобы он не видел четные числа; это ты можешь сделать в качестве домашнего задания). Соответственно, чем больше n, до которого ты хочешь найти простое число, тем вместительней должен быть массив.
Все понятно? Давай закодим!
Реализация
Сначала создаем битовый массив и заполняем его нулями. Мы помещаем массив по адресу 0x8000. Этот произвольно выбранный адрес не конфликтует с нашим кодом, не пересекается с ним.
Обрати внимание на квадратные скобки вот в этой строчке: mov [bx], al. Что они значат? Так мы просим процессор: а скопируй-ка то значение, что хранится в регистре AL, в ячейку памяти, на которую указывает регистр BX. И уж точно это не значит, что мы копируем значение регистра AL в регистр BX.
Идем дальше. Если очередное число простое, выводим его на экран.
Что тут делаем? Начинаем с двойки (записываем ее AX). Затем заходим в цикл и помещаем в BX указатель на ту ячейку битового массива, которая соответствует числу из регистра AX. Затем смотрим, записан ли там нолик (ты же помнишь, мы сначала инициализировали весь массив нулями). Если там не ноль, а единица, значит, мы на какой-то из предыдущих итераций уже пометили это число как составное. В таком случае прыгаем на @@already_marked. А если все-таки ноль, вызываем display_number, чтобы показать найденное простое число.
Обрати внимание на префикс byte в инструкции cmp. Он говорит ассемблеру о том, что мы сравниваем байты (8-битные значения), а не слова (16-битные значения).
Здесь, как и в предыдущем куске кода, сначала помещаем в BX указатель на ту ячейку битового массива, которая соответствует числу из регистра AX. Но только первоначально выполняем инструкцию add дважды. Зачем? Нам сейчас нужно не само простое число, а те числа, которые делятся на него.
Перед тем как пометить очередное число как составное, проверяем, чтобы значение регистра BX не выходило за пределы таблицы: table + table_size (CoMParsion). Инструкция jnc говорит процессору: прыгни, если флаг переноса не установлен в единицу (Jump if Not Carry). Ну или если по-русски: прыгни, если левый операнд инструкции cmp больше правого или равен ему.
Если значение регистра BX все еще находится в пределах битового массива, записываем единичку в ту ячейку памяти, на которую указывает BX. Обрати внимание: квадратные скобки в строчке mov byte [bx], 1 означают, что мы записываем единицу по адресу, на который указывает BX. Мы здесь не присваиваем единицу регистру BX.
И мы снова используем префикс byte (на этот раз в инструкции mov). Тем самым говорим ассемблеру, что присваиваем байт (8 бит), а не слово (16 бит).
Дальше переходим к проверке следующего числа.
Что тут делаем? Если AX не достиг n (последнего числа, которое нас интересует), прыгаем на @@next_number и повторяем там все шаги алгоритма.
Остался последний штрих: добавь в конец программы строчки из библиотеки library.asm. Вот и всё!
Если ты переписал весь код правильно, то, когда запустишь программу, получишь список простых чисел. Поэкспериментируй с программой. Подставляй разные числа в table_size, и ты увидишь, как список простых чисел становится короче или длиннее.
И вот тебе еще домашнее задание: измени программу таким образом, чтобы между простыми числами вместо запятых выводились байты 0x0D и 0x0A (это значит, что тебе надо будет добавить дополнительный вызов для display_letter). Посмотри, что произойдет.
Какие бывают режимы адресации
Мы уже много раз использовали конструкцию [bx] в инструкции mov, чтобы получить доступ к адресу, который хранится в bx. В принципе, этого достаточно, чтобы создавать в памяти переменные и пользоваться ими. Ты можешь писать что-то вроде mov [bx], al / mov al, [bx], и будет тебе счастье.
Но это лишь один из режимов адресации, которые есть у процессора 8088. Когда ты разбираешься, в каких случаях какой режим лучше использовать, ты пишешь более эффективные программы. Вот распространенные режимы адресации, которые можно использовать в mov и во всех арифметических инструкциях.
Такие конструкции можно писать и в качестве левого операнда, и в качестве правого. Обрати внимание на слагаемые d8 и d16. d8 — это 8-битное смещение в диапазоне от –128 до 127. d16 — 16-битное смещение в диапазоне от 0 до 65 535.
И в чем же преимущество, когда ты знаешь не один режим адресации ( [BX]), а много? Смотри. Допустим, чтобы прочитать значение из ячейки памяти, где хранится нужный элемент массива, тебе необходимо сложить два регистра. Если ты, кроме [BX], ничего не знаешь, тебе придется сначала задействовать инструкцию add и только потом mov.
Но когда ты знаешь и другие режимы адресации, то, скорее всего, напишешь по-другому, лучше.
Инструкции перехода
До сих пор мы использовали только пять инструкций безусловного и условного перехода: jmp, je, jne, jc и jnc. Но процессор 8088 поддерживает намного больше инструкций перехода.
Самое важное, что тебе про них надо помнить, — что у инструкций условного перехода действует ограничение на длину прыжка. Они могут прыгать только на 128 байт назад и только на 127 байт вперед. Но не переживай. Тебе не придется лихорадочно подсчитывать байты своей программы. Если какой-то из условных переходов окажется слишком длинным, nasm сгенерирует дальний прыжок.
Вот список инструкций условного перехода, которые поддерживает 8088.
Большинство из этих инструкций напрямую соотносятся с операторами сравнения в языках высокого уровня.
Кстати, имей в виду, что некоторые инструкции процессора, например mov, никогда не переключают никакие биты регистра флагов. Это значит, что их можно вставлять между инструкцией сравнения и инструкцией перехода. Например, писать что-то вроде такого.
Что тут делается? Сравниваем AX с семеркой. Затем помещаем в BX значение 0x2222 — до того как сделать джамп. Если AX = 7, загружаем в BX значение 0x7777. Технически этот кусок кода работает медленнее, чем тот, что ниже. Но зато он короче!
Что выбрать, скорость или лаконичность, решай сам.
Итоги
Теперь ты умеешь работать не только с теми переменными, которые хранятся в регистрах, но и с теми, которые хранятся в памяти. Ты знаешь, какие бывают режимы адресации, и понимаешь, как выбирать наиболее подходящий. Плюс ты познакомился с целой кучей инструкций условного перехода. С таким арсеналом ты уже можешь писать на ассемблере довольно-таки мощные программы!
