← Шестая часть

В предыдущем посте мы спроектировали CPU. Я определился с набором команд, написал ассемблер, проверил каждый опкод и создал процессор, работающий в кремнии (или, точнее, в FPGA Altera Cyclone II EP2C5T144C8, что тоже довольно близко). Но у нас пока нет осмысленного ПО (микрокода калькулятора) для запуска на «железе».

В этой части проекта оправдали себя все эксперименты с прототипами на C++, описанные в частях 2 и 3.

Когда я начал писать addsub.asm (самую первую команду, которую я портировал), то не смотрел на пустую страницу, задаваясь вопросом, как работает BCD-сложение. У меня уже имелась эталонная реализация на C++ (addsub.cpp в проекте Proto), верифицированная на тысячах тестовых векторов. Алгоритм был известен, пограничные случаи найдены и охарактеризованы. Я проработал поведение защитного разряда и бита фиксации. Оставалось лишь транслировать это всё на язык ассемблера; задача всё равно сложная, но совершенно иного уровня сложности, нежели изобретение алгоритма в процессе его написания.

Я хотел бы сделать упор на этот двухэтапный процесс, потому что может показаться, что без него можно обойтись. Написание кода прототипа на C++ с последующей ручной трансляцией на язык ассемблера кажется избыточной и долгой работой. Однако она перестанет казаться избыточной к моменту, когда вы будете отлаживать неочевидный пограничный случай округления в 16-ниббловом BCD-вычитании. Наличие золотого эталона, с которым можно выполнять сравнения, не избыточно: это единственное, что стоит между вами и неделями кропотливого труда или даже провалом проекта.

Чтобы убедиться в этом, стоит рассмотреть историю собственного ПО калькулятора HP. Первая версия HP-35 в 1972 году была выпущена с багом: при вводе 2.02 ln ex получался результат 2 вместо 2.02. Численные алгоритмы в этой машине не имели автоматизированных тестовых векторов для выявления пограничных случаев — инженеры HP валидировали результаты вручную, сравнивая их с распечатанными таблицами, и конкретно это значение они упустили. Когда баг обнаружили, один из основателей компании сломал карандаш на совещании, на котором кто-то из присутствующих предложил просто не рассказывать об этом покупателям. HP предложило бесплатную замену всем владельцам, кого затронула эта проблема. Вернули калькуляторы только 25%, но урок о тщательном численном тестировании оказался дорогим.

The HP-35 (1972) — the world's first scientific pocket calculator, and the machine whose ln(2.02) bug taught the industry that hand-checking results against printed tables is not enough. — HP35 (1972 год)

Утилита calctest (о которой я говорил в части 4) упростила этот процесс. При прогоне через calctest новой функции она сразу сообщает, соответствует ли микрокод прототипу. Если вы допустите ошибку в ассемблерном коде, то будете точно знать, какой случай оказался сбойным и вам не придётся ориентироваться по симптомам.

Три грани калькуляторного микрокода

В текущей версии микрокод состоит примерно из двух десятков ассемблерных файлов. Их можно разбить на три группы, разделённые не только организационно, но и концептуально: у каждой из них есть свои входные и выходные данные, а также разный стиль сложности. (Четвёртый модуль — слой скриптинга, будет рассмотрен в отдельном разделе).

1. Ввод чисел

input.asm обрабатывает всё, что происходит между нажатием на клавишу и записью в регистр X правильно отформатированного числа. Список случаев, который он должен реализовать правильно, длиннее, чем вы могли бы ожидать: нули в начале, десятичный разделитель (допускается только один!), знак (может встречаться перед мантиссой или экспонентой), разделитель экспоненты, переключение между вводом мантиссы и экспоненты в процессе ввода числа, отклонение дополнительных разрядов, когда дисплей заполнен, обработка CHS (смены знака) в зависимости от того, вводится ли мантисса или экспонента. Если подняться на один уровень вверх, то там он должен обрабатывать семантику записи в стек: должен ли ввод цифры после ENTER извлекать текущий X или перезаписывать его, а также другие аспекты манипуляций с пользовательским стеком.

Модуль ввода также отвечает за выбор того, в каком режиме выполняется нажатие на цифру. Нажатие на 5 может означать: добавление цифры 5 в вводимое число; переключение точности дисплея на 5 разрядов, если пользователь находится в режиме DISP (интерактивный селектор формата и точности), или выбор регистра памяти 5, если пользователь нажал на STO или RCL. Одна точка входа обрабатывает все три случая, считывая в начале переменную состояния. Мне оставалось лишь правильно реализовать переходы между состояниями.

Здесь просто необходимым оказался прототип Pathfinding/Input на C++. Конечный автомат ввода имел так много пограничных случаев, что отладка непосредственно на языке ассемблера была бы очень утомительной. В версии на C++ используются имена переменных, напрямую соответствующие ассемблерным регистрам, которыми они станут: Si_r3 для индекса экрана (в конечном итоге регистр R3), Mi_r5 для индекса мантиссы (R5), Di_r2 для позиции десятичного разделителя (R2). Такая система наименований превратила портирование на язык ассемблера в почти механическую задачу: для каждой переменной на C++ уже имелся заранее выделенный регистр, ожидающий её. Эвристика была полностью проработана и протестирована на C++ до того, как я приступил к написанию первой строки ассемблерного кода.

2. Вывод на дисплей

Вывод на дисплей с его разными режимами был столь же сложной задачей. display.asm — это самый большой файл всего проекта (больше, чем сложение/вычитание, больше, чем логарифм, больше всего остального).

Калькулятор поддерживает три десятичных режима отображения (Fixed, Scientific, Engineering) плюс Raw (все 16 разрядов мантиссы, что полезно для отладки или когда нужно видеть все получившиеся разряды). У каждого режима есть собственные правила форматирования. Например, инженерный режим хранит экспоненту как число, кратное 3 и соответствующим образом меняет положение мантиссы: 0.1234 отображается как 123.4 E-03, а не как 1.234 E-01, потому что инженеры думают в миллиметрах и микрометрах и хотят читать непосредственно единицы СИ. (Может показаться, что это просто, но попробуйте реализовать это сами).

Округление тоже происходит здесь, а не в пользовательских регистрах. Это сделано намеренно: необходимо, чтобы внутренние регистры сохраняли полную 16-разрядную точность, но дисплей может отображать меньше разрядов. Этап округления должен обрабатывать случай переноса, в котором округление последнего отображаемого разряда приводит к тому, что он становится равным 10; это распространяется влево и даже может изменить величину (экспоненту) числа, что, в свою очередь, может привести к превышению максимального предела отображаемых значений. В самом крайнем случае такое округление может привести к переполнению результата; тогда мы отображаем максимально большое число. Такое вызванное округлением «переполнение» отличается от «истинного» переполнения, отображаемого как ошибка.

Этот модуль я написал последним, после того, как обеспечил работу ввода и основных вычислений; я осознавал, что он будет самым сложным. Это единственный модуль, для которого у меня нет эталона на C++. К тому времени я очень хорошо освоился в написании ассемблерного кода, поэтому решил пропустить этот этап.

3. Вычисления на языке ассемблера

Это ядро калькулятора. Ассемблерный код почти полностью отображается на файлы прототипов C++, написанные на предыдущих этапах проекта. Для каждой основной функции существует соответствующий ассемблерный файл:

addsub.asm — сложение и вычитание с защитным разрядом и битом фиксации
mul.asm — алгоритм понибблового умножения (на основе таблиц)
div.asm — длинное деление сдвигом и вычитанием
sqrt.asm — квадратный корень, вычисляемый итерациями Ньютона-Рафсона
log.asm / exp.asm — CORDIC псевдоделения/умножения в стиле HP
tan.asm / atan.asm / atan2.asm — десятичный тангенс CORDIC
sin.asm / cos.asm — созданы на основе тангенса CORDIC

Алгоритм CORDIC имеет любопытную историю. Джек Волдер придумал его в 1956 году (сам алгоритм мы разбирали в части 3; ниже рассказывается его история), когда работал в отделе авиационной электроники Convair; его задача заключалась в замене аналогового ресолвера навигационного компьютера сверхзвукового бомбардировщика B-58 на более быструю цифровую систему. В 1959 году он опубликовал свои результаты в IRE Transactions on Electronic Computers. Многие годы алгоритм оставался нишевой методикой, используемой в военных навигационных системах. В 1971 году Джон Стивен Вальтер из Hewlett-Packard обобщил алгоритм так, чтобы он мог обрабатывать гиперболические функции, логарифмы и степенные функции при помощи той же структуры сдвига и сложения. Эта обобщённая методика, опубликованная весной 1971 года, на следующий год была напрямую реализована в HP-35 (первом в мире карманном научном калькуляторе).

Каждый из моих ассемблерных файлов изначально был прямым портом эквивалентных функций C++ из проекта Proto. Процесс работы был таким: я внимательно читал код на C++, следовал за потоком данных (в каких регистрах что хранится и в каком формате), а затем писал ассемблерный код, строго в соответствии с потоком эталонного кода, строка за строкой, операция за операцией. Я даже дословно оставлял те же комментарии, поэтому исходники выглядят похоже. Всё это помогло в отладке возникавших иногда проблем, которых было не так много благодаря этому строгому подходу.

Тестовые векторы из Proto, пропускаемые через calctest, подтверждали, что порт полностью соответствовал прототипу. В сложных случаях для отладки тестового вектора я использовал Qt-приложение.

Прототип на C++ обеспечивал сырую эвристику функциональности, но в нём по-прежнему недоставало обёртки и структуры основного калькулятора.

Вот пример части такой структуры. Это реальная точка входа из addsub.asm:

sc_ypowx    PROC
    Push    S1          ; Push X aside
    Loge                ; ln(y)
    Pop     S1          ; Restore X
    Multiply            ; x * ln(y)
    Expe                ; e^(result)
    Exit
sc_ypowx    ENDP

pre_calc_2 сбрасывает флаг ввода, сохраняет LASTX, копирует Y и X во временные регистры S0 и S1 и извлекает вершину пользовательского стека. addition выполняет операцию. post_calc_finalize повторно включает поднятие стека, проверяет на ошибки и копирует регистр результата в X.

Основной принцип заключался в том, что каждая операция должна ожидать наличия одного или обоих параметров во временных регистрах S0 и S1, а сохранять свой результат в другой временный регистр R (от result). Обёртка более высокого уровня управляет видимыми пользователю регистрами X, Y, Z, T и LastX.

Такая многослойная структура упрощает независимое тестирование и замену отдельных функций, но самое важное преимущество в том, что можно объединять их в цепочки, потому что они имеют согласованный с остальной частью системы интерфейс. Такое беспроблемное соединение в цепочки позволило реализовать более простой скриптовый язык.

Слой скриптинга

После того, как основные арифметические и трансцендентные функции заработали на языке ассемблера, для реализации большого количества остальных клавиш калькулятора требовались лишь сочетания этих функций. y^x — это e^(x * ln(y)). Обратная величина — это 1 / x. Факториал выполняет итеративное умножение на счётчик обратного отсчёта. Перевод из градусов в радианы — это умножение на константу.

Если бы я начал писать всё это на языке ассемблера, то процесс был бы кропотливым и я впустую тратил бы ROM. Вместо этого в калькуляторе есть маленький скриптовый интерпретатор. Скрипты хранятся в адресном пространстве данных (в свой собственной 2048-ниббловой области ROM), а скриптовый движок обрабатывает 4-битные токены, обозначающие операции: Plus, Minus, Multiply, Divide, Loge, Expe, Copy, If_Goto и так далее.

Скриптовый движок построен на основе стека (есть токены Push и Pop), но он может и напрямую работать с регистрами (например, он может загрузить константу в любой пользовательский или временный регистр). Он соблюдает установленный контракт, по которому каждая операция ожидает найти свои аргументы во временных регистрах S0/S1, а результаты сохраняются во временный регистр R, который тоже автоматически копируется в S0/S1 в случае операций-цепочек.

Идея не нова: Sinclair использовала такой же подход в микропроцессорах ZX81 и ZX Spectrum для реализации математики с плавающей запятой. У Z80 нет команд для чисел с плавающей запятой, поэтому в ROM Sinclair содержится небольшой интерпретатор, обрабатывающий таблицу однобайтных токенов (каждый из них соответствует короткой ассемблерной подпрограмме для операций наподобие сложения, умножения, синуса или логарифма). Далее сложные функции калькулятора в интерпретаторе BASIC выражаются как компактные последовательности таких токенов, а не как повторяющийся встроенный ассемблерный код. Доктор Стив Викерс, который в свои 27 лет писал Spectrum ROM полностью на языке ассемблера, использовал эту методику для того, чтобы уместить функции научного калькулятора в несколько килобайт.

Особенно изящной делает версию для Spectrum механизм вызова: программа Z80 вызывает калькулятор с плавающей запятой простым исполнением RST 28H, а затем помещает поток байтов токенов в код сразу после этого вызова. Интерпретатор считывает эти байты, обрабатывает каждую операцию и выполняет возврат результата в стек значений с плавающей запятой. Таким образом выражен весь вычислитель выражений интерпретатора BASIC и все научные функции. По сути, Викерс реализовал внутри ROM маленькую виртуальную машину. Эта напоминающая Forth стековая архитектура, очевидно, так захватила его, что следующим проектом Викерса после ухода из Sinclair стал Jupiter Ace (домашний компьютер, поставлявшийся с Forth вместо BASIC в качестве основного языка), язык которого стал прямым философским наследником виртуальной машины калькулятора Spectrum. Его и сегодня изучают люди, занимающиеся реверс-инжинирингом Spectrum ROM.

Наш скриптинг тоже очень компактен. В результате этого функция наподобие sc_ypowx (y в степени x) выглядит так:

sc_ypowx    PROC
    Push    S1          ; Push X aside
    Loge                ; ln(y)
    Pop     S1          ; Restore X
    Multiply            ; x * ln(y)
    Expe                ; e^(result)
    Exit
sc_ypowx    ENDP

Шесть строк. После того, как в ассемблерном коде появились Loge и Expe, это становится полной реализацией y^x. Скриптовый язык расположен поверх ассемблерного слоя подобно макросистеме, и неожиданно большая доля 35-клавишной структуры калькулятора реализована на этом уровне.

Функция обмена (sc_exchg, обмен значениями X и Y) занимает четыре строки; развёртывание стека RPN — шесть строк. Факториал занимает примерно двадцать пять, включая цикл и валидацию аргумента. Функция перевода градусов в радианы — это умножение на константу π/180 и так далее.

Мы говорили об этом в посте «Численные методы»: можно получить «36 операций по цене восьми». Это становится возможным благодаря слою скриптинга. Имея Loge, Expe, Sqrt и четыре основные операции, можно выразить большинство операций научного калькулятора. Интерпретатор и исполняемый им скрипт выполняют все функции высокого порядка, для которых бы в противном случае потребовались собственные ассемблерные реализации.

Скриптинговый компилятор реализован в виде скрипта на Python (cscript.py). Он считывает файлы .scp, ресолвит метки и выводит упакованные 4-битные токены в том же совместимом с $readmemh формате, который использует ассемблер. Когда я начал думать о компиляторе скриптов, то очевидным решением мне показалось простое копирование уже существующего ассемблера (casm.py) с вырезанием всех ассемблерных мнемоник и добавлением токенов скриптинга. После внесения нескольких небольших изменений скриптинговый компилятор научился обрабатывать скриптовый язык и генерировать токены скриптинга.

Как работает интерпретатор

Код интерпретатора занимает несколько десятков строк ассемблерного кода в scripting.asm. Базовый цикл выглядит так:

run_script  PROC
    aload   1               ; Load next token into r0, advance AP
    cmpi    OP_EXIT         ; Done?
    bra     ne, @1
    aload   1               ; Load error code
    cmpi    0
    ret     eq
    stm     NUM_ERR, r0     ; Store non-zero error code
    ret
@1: tblcall sc_table_0 - 1  ; Dispatch to the handler
    bra     run_script       ; Loop
run_script  ENDP

aload считывает одно слово (ниббл) из указателя адреса данных и увеличивает его. tblcall использует R0 в качестве индекса таблицы переходов и вызывает соответствующую подпрограмму. Вот в этом и заключается основной принцип работы движка. Сложность таится в таблицах диспетчеризации и обработчиках, на которые они указывают, а не в самом цикле. Многие скриптинговые токены позволяют сложным скриптам рекурсивно вызывать другие скриптовые функции.

Скриптинговый токен — это 4-битное значение, позволяющее использовать 16 возможных опкодов на каждую группу. Множество токенов разбито на три группы, чтобы упаковать в это узкое пространство больше операций. Группа 0 — это команды из одного ниббла, не получающие дополнительных аргументов: арифметические операции, основные точки входа управления потоком и два управляющих кода. Токен0xE — это код перехода в Группу 1: один дополнительный аргумент, за которым следуют индекс регистра, индекс флага или селектор тригонометрической функции. Токен 0xF — это код перехода в Группу 2: два дополнительных аргумента, за которыми следуют начальный и конечный регистр. В качестве пользовательских регистров используются X, Y, Z, T, LX, R, S0–S4, STAT_N/M/S/SUMX/SUMX2.

Полные таблицы токенов (все три группы, тестовые операции, имена пользовательских регистров, индексы всех констант) указаны в Scripting Language Reference папки docs/ репозитория.

Стоит упомянуть токен Test. Он проверяет регистр на одно из шести условий (ноль, отрицательный, равный S0, численная ошибка, недопустимый, больше или равен S0) и сохраняет булев результат в FLAG_TEST. Этот токен позволяет реализовывать в скриптах условное ветвление без непосредственного обращения к флаговому регистру CPU.

Чтобы привести конкретный пример, возьмём факториал; это один из самых сложных скриптов, использующий большинство фич языка:

sc_factorial PROC
    Setup                           ; Sets FLAG_S0_ZERO, FLAG_S1_ZERO
    If_Goto FLAG_S0_ZERO, @return_1 ; 0! = 1

    Call    comb_validate_1         ; Validate: non-negative integer
    Test    S0, TEST_NUM_ERR
    If_Goto FLAG_TEST, @return_inv  ; Error: return invalid

    Copy    S3, S0                  ; S3 = countdown (n)
    Push    S0                      ; Stack holds running product

@loop:
    Copy    S0, S3
    LoadConst S1, CONST_1
    Minus                           ; n - 1
    Test    R, TEST_IS_ZERO
    If_Goto FLAG_TEST, @done        ; Reached zero: stop

    Copy    S3, R                   ; New countdown
    Pop     S1                      ; Accumulated product
    Multiply                        ; product * n
    Push    R                       ; Push new product
    Jump    @loop

@done:
    Pop     R
    Exit
...
sc_factorial ENDP

Здесь есть цикл, написанный на языке, не имеющем команды цикла. Токен Jump обеспечивает безусловное перенаправление; If_Goto и If_Not_Goto обеспечивают условный выход. Стек данных (при помощи Push и Pop) хранит накопитель между итерациями. Код понятен, компилируется в компактную последовательность 4-битных токенов и выполняется в том же самом интерпретаторе, который обрабатывает всё остальное.

В конечном итоге, слой скриптинга со временем брал на себя всё больше и больше функций. Операции, которые изначально писались в ассемблерном коде (статические накопители, преобразование часов, минут и секунд, преобразование полярных/прямоугольных координат), с расширением возможностей языка мигрировали в скрипты. В итоге большинство функций калькулятора выполняется полностью в скрипте, а ассемблерный код обрабатывает только численные примитивы.

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

Однако всегда стоит быть консервативным, прагматичным и оставлять достаточно места для последующего расширения. Думайте шире, а реализуйте минимально.

Отладка микрокода: Qt-симулятор

При создании микрокода для собственного CPU существует одна сложность: когда возникают проблемы, невозможно просто добавить оператор print. CPU не знает, что такое print.

Чтобы эта задача была подъёмной, одним из первых я создал десктопное Qt-приложение, пропускающее весь дизайн Verilog через Verilator (потактово точный симулятор C++, о котором мы говорили раньше) и обёртывающее его в соответствующую среду отладки. В результате калькулятор работает на рабочем столе с полной графической клавиатурой и ЖК-дисплеем, который в точности рендерит набор символов HD44780U.

В правой части окна находится консоль отладки. Она принимает вводимые в поле команды и в ней даже работают знакомые функциональные клавиши: F11 выполняет шаг в одну команду, F10 выполняет код до вызова подпрограммы, F5 продолжает выполнение до следующей контрольной точки. Эти горячие клавиши считываются из файла конфигурации.

Отладчик понимает микрокод на уровне исходников. При загрузке файла листинга микрокода (сгенерированного ассемблером наряду с двоичным файлом), команда l показывает изначальные строки исходников:

> l key_plus
0C3E  key_plus:
0C3E        call    pre_calc_2
0C40        call    addition
0C42        jmp     post_calc_finalize
0C44  addition:
...

Контрольные точки принимают или шестнадцатеричные адреса, или непосредственно символьные имена. Например, bp key_plus устанавливает контрольную точку на входе в обработчик сложения, а bp division перехватывает подпрограмму деления. При срабатывании контрольной точки консоль выводит адрес и имя метки, поэтому мы всегда (а не только в двоичном файле) знаем, где находимся в коде.

Команда r выполняет дамп всех регистров и флагов CPU. Команда d дампит область ОЗУ в формате нибблов, что необходимо для изучения содержимого регистров калькулятора в процессе вычислений. dr отображает видимые пользователю регистры (X, Y, Z, T, LastX и временные регистры), отформатированные в виде чисел BCD, чтобы сразу можно видеть обрабатываемые значения. ds показывает статистические накопители. du отображает регистры памяти STO 0–9 и так далее; помощь вызывается командой h.

Также существует sr (запись регистра) для инъецирования значения из консоли непосредственно в регистр калькулятора и df для отображения целиком 16-битного флагового регистра. Две эти команды позволяют создать конкретное состояние, выполнить код до нужной точки в вычислениях и изучить, что в точности произошло.

Фреймворк тестирования интегрируется непосредственно в ту же консоль. tf tests.txt загружает тестовые векторы из проекта Proto на C++, а te выполняет их для живой симуляции. Те же векторы, которые проверяли прототип на C++, теперь проверяют микрокод на симулируемом оборудовании.

Полный набор команд отладчика, горячие клавиши, инструкции по сборке и подробности фреймворка тестирования есть в Qt Simulator and Debugger Reference в папке docs/ репозитория.

Всё это сэкономило мне кучу времени. Баги микрокода обычно сложно выявить: не сброшенный в нужный момент флаг, регистр, проиндексированный с промахом в ниббл, неправильное условие ветвления. Без возможности отладки на уровне исходников поиск этих проблем был бы очень медленным процессом. А при её наличии поиск большинства багов сводится к установке контрольной точки рядом с подозрительным кодом, пошаговому его выполнению, просмотру состояния регистров и нахождению строки, где происходит нечто неожиданное.

То же самое Qt-приложение компилируется в WebAssembly и запускается в браузере; именно так работает интерактивное демо на baltazarstudios.com, с которым можно поэкспериментировать вручную.

Микрокод в контексте

Микрокод — это не статический артефакт. После реализации 2021 года до версии 2025 года алгоритмы вычислений были переписаны на основе улучшенного эталонного Proto C++: более плотная обработка защитного разряда, улучшенное округление, CALLI и другие оптимизации. Также появилось несколько функций (atan2, статистические накопители), структура других была изменена. В слой скриптинга переносилось всё больше и больше функций, изначально написанных на языке ассемблера.

Из показанных ниже графиков можно получить некоторое представление об использовании микрокодом команд CPU.

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

В зависимости от вашего настроя, это может или пугать, или восхищать. Лично я определённо в восторге.

Проектируем с нуля калькулятор на FPGA. Часть 7: микрокод для самодельного CPU