Переходы, условия и циклы на уровне процессора

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

Зачем нарушать порядок

До сих пор учебный процессор М-8 шёл по ячейкам подряд: 0, 1, 2, 3. Счётчик команд (СК) после каждой выборки увеличивался на единицу, и больше с ним ничего не происходило. Такая программа похожа на эскалатор: встали на нижнюю ступеньку — доедете до верхней, свернуть некуда.

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

JUMP: переход без условий

Команда JUMP адрес записывает адрес в счётчик команд — и всё. Аккумулятор и память она не трогает.

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

Код операции JUMP — 0101. Команда JUMP 1 — это 0101 0001, или 51.

JZ: переход, если ноль

Команда JZ адрес (от английского jump if zero — «перейти, если ноль») сначала смотрит на флаг Z.

• Если Z = 1, она записывает адрес в СК — так же, как JUMP.
• Если Z = 0, она не делает ничего, и процессор берёт команду из следующей ячейки.

Флаг Z равен 1 ровно тогда, когда в аккумуляторе ноль. Получается, JZ задаёт процессору единственный вопрос, на который тот умеет отвечать: «в A сейчас ноль?» Этого достаточно, потому что многие проверки сводятся к вычитанию и сравнению с нулём.

Код операции JZ — 0110. Команда JZ 4 — это 0110 0100, или 64.

Обратный отсчёт

Напишем таймер, который считает 3, 2, 1, 0 и останавливается. В ячейку 14 положим число 3, в ячейку 15 — единицу, которую будем вычитать.

адрес  команда    что делает
  0    LOAD 14    A ← 3
  1    SUB 15     A ← A − 1
  2    JZ 4       в A ноль? тогда на адрес 4
  3    JUMP 1     иначе назад, к вычитанию
  4    HALT       стоп
 ...
 14    число 3
 15    число 1

Команды в ячейках 1, 2 и 3 образуют цикл: процессор проходит их снова и снова, пока не сработает JZ. Это видно по трассировке. В столбце «СК» — адрес выполняемой команды, в столбце «СК после» — адрес, откуда будет взята следующая.

В программе пять команд, а шагов вышло десять: команды цикла выполнялись по нескольку раз. На шагах 3 и 6 флаг Z равен 0, и JZ пропускает процессор дальше, к JUMP. На шаге 9 в аккумуляторе ноль, Z = 1, и JZ отправляет процессор на адрес 4.

Умножение сложением

Команды умножения у М-8 нет. Но 4 · 3 — это 4 + 4 + 4, а складывать и повторять мы уже умеем. Понадобятся две ячейки-помощницы: в одной копится сумма, в другой записано, сколько сложений осталось.

адрес  команда    что делает
  0    LOAD 13    A ← сумма
  1    ADD 14     A ← A + 4
  2    STORE 13   сумма ← A
  3    LOAD 15    A ← сколько раз осталось
  4    SUB 12     A ← A − 1
  5    STORE 15   запомнить остаток
  6    JZ 8       осталось 0 раз? тогда на адрес 8
  7    JUMP 0     иначе повторить
  8    HALT       стоп
 ...
 12    число 1    единица для вычитания
 13    число 0    сумма, здесь появится ответ
 14    число 4    что складываем
 15    число 3    сколько раз

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

Всего процессор выполнил 24 команды, и в ячейке 13 лежит 12. У настоящих процессоров команда умножения есть, и работает она гораздо быстрее: вместо долгих повторений там сдвиги и сложения из урока Вычитание, сравнение и АЛУ.

Из переходов — «если» и «пока»

В языках программирования, с которыми Вы ещё встретитесь, есть слова «если… то… иначе» и «пока… повторять». Процессор таких слов не знает: для него это узоры из JZ и JUMP.

«Пока» — это наш таймер: проверка, после которой либо выход, либо прыжок назад.

«Если… то… иначе» — это развилка. Вот как домофон мог бы сравнивать набранный код из ячейки 13 с правильным из ячейки 14. Два числа равны, когда их разность — ноль.

адрес  команда    что делает
  0    LOAD 13    A ← набранный код
  1    SUB 14     A ← A − правильный код
  2    JZ 4       разность ноль? коды совпали, на адрес 4
  3    HALT       иначе: стоп, дверь закрыта
  4    LOAD 12    то: A ← 1
  5    STORE 15   ячейка 15 ← 1, открыть дверь
  6    HALT       стоп
 ...
 12    число 1

Если в ячейках 13 и 14 лежит по 58, процессор пройдёт адреса 0, 1, 2, 4, 5, 6 и запишет в ячейку 15 единицу. Если набрать 85, разность выйдет 27, JZ не сработает, и программа остановится на адресе 3. В ячейке 15 останется ноль.

Бесконечный цикл

Цикл заканчивается, только если условие выхода когда-нибудь выполнится. Изменим в таймере одно число: будем вычитать не 1, а 2. В аккумуляторе побывают 3 и 1, а дальше не ноль: 1 − 2 в восьми битах даёт 1111 1111. Со знаком это −1, без знака — 255, но в любом случае не ноль. Затем 253, 251 и так далее. Все эти числа нечётные, нуля среди них нет, и JZ не сработает никогда.

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

Частые ошибки

• Думают, что JZ проверяет ячейку. JZ 4 смотрит на флаг Z, то есть на аккумулятор, а 4 — это адрес, куда перейти.
• Забывают JUMP в конце цикла. Без него процессор пройдёт команды цикла один раз и отправится дальше.
• Путают адрес перехода с числом шагов. JUMP 1 означает «следующая команда лежит в ячейке 1», а не «отступи на одну команду».
• Проверяют флаг слишком поздно. Z показывает, что лежит в A сейчас. Если между вычитанием и JZ в аккумулятор загрузили другое число, проверится уже оно.

Коротко

• Переход записывает новый адрес в счётчик команд, и программа продолжается с другого места.
• JUMP переходит всегда, JZ — только когда флаг Z равен 1, то есть в аккумуляторе ноль.
• Цикл — это группа команд с переходом назад в конце и условным выходом внутри.
• «Если… то… иначе» и «пока…» складываются из вычитания, JZ и JUMP.
• Если условие выхода не выполняется никогда, получается бесконечный цикл.

Девять команд и четыре ячейки данных ради одного умножения — это много. Как люди научились писать коротко и поручать остальное программе — в уроке От машинного кода к языкам программирования.