Программируем «Мегапроцессор»

На Geektimes летом была статья про Megaprocessor — процессор из дискретных транзисторов и светодиодов, который весит полтонны и занимает всю гостиную в обычном таунхаусе под Кембриджем. Я решил воспользоваться своей географической близостью к этому мегапроекту, и запрограммировать для него что-нибудь презентабельное — например, спортировать для Megaprocessor мою предыдущую хабрапрограммку «Digital Rain».

Система команд Megaprocessor описана на сайте разработчика.

Большинство команд состоят из одного байта, за которым может следовать непосредственный операнд (один или два байта). Регистров общего назначения всего четыре (R0-R3), при этом они не равноправны: например, для команд доступа к памяти адрес должен быть либо в R2, либо в R3; а операнд — в одном из двух оставшихся регистров.

Программистам, привыкшим к системе команд x86 или ARM, набор команд Megaprocessor покажется крайне бедным: нет ни косвенной адресации «база+смещение», ни непосредственных операндов у арифметических команд (за исключением addq ±1, addq ±2). Зато есть пара неожиданных возможностей: отдельная команда sqrt, и режим .wt для команд сдвига, который заменяет результат суммой выдвинутых битов. Таким образом можно, например, парой команд ld.b r1, #15; lsr.wt r0, r1 вычислить количество единичных битов в r0 (вопрос, столь любимый собеседователями на работу!). Мнемоника ld для команды, загружающей в регистр непосредственное значение (вместо привычной по x86 или ARM мнемоники mov) указывает на способ её выполнения: фактически, с точки зрения процессора, выполняется ld.b r1, (pc++).

Итак, приступим.

Программа для Megaprocessor начинается (по адресу 0) с таблицы векторов прерываний. Каждому из четырёх векторов отведены по четыре байта. Начиная с адреса 0x10 может располагаться собственно код программы. Из 64КБ адресного пространства, вся первая половина (до адреса 0x8000) может использоваться кодом; адреса 0xA000-0xA0FF соответствуют «дисплею» — дискретной памяти, каждый бит которой снабжён светодиодным индикатором. marks ошибся, написав «Объем памяти составляет 256 байт.» — это объём «видеопамяти», а не основной памяти для кода и данных.

Из четырёх векторов прерываний в нашей программе используется только вектор reset, а в остальных векторах стоит «заглушка» из одной инструкции reti. (Программистам для x86 или ARM команда возврата из обработчика прерывания знакома под мнемоникой iret.) Ни одно из этих прерываний в нашей программе произойти всё равно не может, так что можно было бы даже и «заглушки» для них не ставить.

reset:       jmp    start;
             nop;
ext_int:     reti;
             nop;
             nop;
             nop;        
div_zero:    reti;
             nop;
             nop;
             nop;        
illegal:     reti;
             nop;
             nop;
             nop;

Первым делом после запуска нужно инициализировать стек и переменные. Стек пусть растёт вниз, начиная с адреса 0x2000 — этого нам хватит с большим запасом. Переменные понадобятся всего две: seed для текущего значения ГСЧ, и массив position из 32 значений — по одному на каждый «столбец дисплея», чтобы следить, где в этом столбце ползёт «капля». Массив инициализируем просто 32 случайными байтами. Команда jsr — вызов подпрограммы — соответствует call в x86 или bl в ARM.

start:
        ld.w    r0, #0x2000;
        move    sp, r0;

        // set random positions
        ld.b    r1, #32;
init_loop:
        jsr     rand; // returns random value in r0
        ld.b    r2, #position;
        add     r2, r1;
        st.b    (r2), r0;
        addq    r1, #-1;
        bne     init_loop;

Поскольку записать байт по адресу (#position + r1) невозможно одной командой, приходится сначала отдельной командой сложения вычислять адрес.

Основная часть программы — бесконечный цикл, в котором мы проходим справа налево по каждому «столбцу дисплея», и сдвигаем в нём «каплю» на одну позицию вниз. Младшие два бита «капли» обозначают её цвет (3 — «горит»; 0, 1 или 2 — «не горит»), оставшиеся шесть битов — координату (0..63), поэтому «сдвиг вниз» означает прибавление 4. Как только «капля» доползла до низа «дисплея» (значение превысило 255), заменяем её новым случайным байтом.

busy_loop:
        ld.b    r1, #32;
next_col:
        ld.b    r2, #position;
        add     r2, r1;
        ld.b    r0, (r2);
        addq    r0, #2;
        addq    r0, #2;
        btst    r0, #8;
        beq     save;
        jsr     rand;
save:   st.b    (r2), r0;
        addq    r1, #-1;
        bmi     busy_loop;

Прибавить 4 одной командой невозможно, поэтому мы дважды повторяем addq r0, #2, и затем проверяем восьмой бит результата, чтобы определить, не превысило ли значение 255. Если превысило, то сохраняем в массив position новое случайное значение; иначе сохраняем старое, увеличенное на 4. Команда условного перехода bmi переходит к началу цикла busy_loop в том случае, если результат последнего действия отрицательный, т.е. после обработки нулевого столбца.

Как будем генерировать случайные числа? RANDU, который я использовал в 32-битном «Digital Rain», уже не подходит: Megaprocessor способен умножать только 16-битные числа; поэтому из списка простых ГСЧ возьмём такой, где множитель 16-битный. Мне понравился ГСЧ, обозначенный как «Turbo Pascal».

rand:   ld.w    r0, seed;
        ld.w    r1, #33797;
        mulu;
        addq    r2, #1;
        st.w    seed, r2;
        move    r0, r2;
        ret;

Этот простой и симпатичный ГСЧ возвращает сгенерированное значение в r0, но к сожалению, портит значения всех остальных регистров. Обратим внимание, что в обоих случаях, когда мы вызываем rand, у нас в r1 хранится индекс «столбца дисплея», и его нужно сохранять и восстанавливать; а потом в r2 должно оказаться смещение (#position + r1). Значит, можно вычисление этого смещения засунуть внутрь rand:

rand:   push    r1;            // !
        ld.w    r0, seed;
        ld.w    r1, #33797;
        mulu;
        addq    r2, #1;
        st.w    seed, r2;
        pop     r1;            // !
        move    r0, r2;
        ld.b    r2, #position; // !
        add     r2, r1;        // !
        ret;

start:  ld.w    r0, #0x2000;
        move    sp, r0;

        // set random positions
        ld.b    r1, #32;
init_loop:
        jsr     rand;
        st.b    (r2), r0;
        addq    r1, #-1;
        bne     init_loop;

busy_loop:
        ld.b    r1, #32;
next_col:
        ld.b    r2, #position;
        add     r2, r1;
        ld.b    r0, (r2);
        addq    r0, #2;
        addq    r0, #2;
        btst    r0, #8;
        beq     save;
        jsr     rand;
save:   st.b    (r2), r0;
        addq    r1, #-1;
        bmi     busy_loop;

Последняя здесь хитрость — то, что вычисление ld.b r2, #position; add r2, r1; в начале цикла next_col можно заменить прыжком внутрь подпрограммы rand:

rand:   push    r1;
        ld.w    r0, seed;
        ld.w    r1, #33797;
        mulu;
        addq    r2, #1;
        st.w    seed, r2;
        pop     r1;
        move    r0, r2;
add_position:
        ld.b    r2, #position;
        add     r2, r1;
        ret;

start:  <...>

busy_loop:
        ld.b    r1, #32;
next_col:
        jsr     add_position; // !
        ld.b    r0, (r2);
        addq    r0, #2;
        addq    r0, #2;
        btst    r0, #8;
        beq     save;
        jsr     rand;
save:   st.b    (r2), r0;
        addq    r1, #-1;
        bmi     busy_loop;

Теперь самое интересное — вторая половина цикла next_col, которая и будет отрисовывать «каплю» на дисплее.

        move    r3, r1; // x     (0..1f)
        lsr     r3, #3; // byte addr in row (0..3)
        ld.b    r2, #0xfc; // y mask
        and     r2, r0; // y * 4 (0..fc)
        add     r3, r2; // byte addr in screen
        ld.w    r2, #0xa000;
        add     r3, r2; // byte addr in memory
        ld.b    r2, #2;
        lsr.wt  r0, r2;
        ld.b    r2, #7;
        and     r2, r1; // bit index in byte (0..7)
        lsl     r2, #1;
        lsr     r0, #2;
        roxr    r2, #1;
        ld.b    r0, (r3);
        // and now apply
        test    r2;
        bpl     blank;
        bset    r0, r2;
        jmp     apply;
blank:  bclr    r0, r2;
apply:  st.b    (r3), r0;
        jmp     next_col;

Чтобы «зажечь» или «погасить» нужный бит, нужно первым делом вычислить адрес соответствующего байта «видеопамяти». Поскольку у нас номер «столбца» хранится в r1, а положение и «цвет» капли — в r0, то адрес байта вычисляется как (r1 >> 3) + (r0 & 0xfc) + 0xa000. После этого командами ld.b r2, #2; lsr.wt r0, r2; мы определяем цвет капли: если оба младших бита в r0 были установлены, то в результате этих команд в r0 будет значение 2; иначе — значение 0 или 1. Наконец, в трёх нижних битах r2 мы запоминаем номер нужного бита «видеопамяти», и «вдвигаем» в старший бит r2 цвет капли последовательностью lsl r2, #1; lsr r0, #2; roxr r2, #1; — вторая команда выдвигает бит цвета из r0 во флаг CF, а последняя (циклический сдвиг вправо с участием CF) вдвигает этот бит в r2. Когда регистров не хватает для всех нужных значений, приходится исхитряться! Наконец, из «видеопамяти» извлекается байт по нужному адресу, и в зависимости от бита цвета, в этом байте либо устанавливается, либо сбрасывается нужный бит. Команды bset и bclr используют только младшие биты своего второго операнда, так что бит цвета в старшем бите r2 им не мешает. Проверяем этот старший бит мы последовательностью test r2; bpl blank; — команда условного перехода bpl выполняет переход в том случае, если результат последнего действия положительный, т.е. бит цвета снят.

И вот что получается в итоге:




Остался последний штрих: сделать, чтобы «капли» мигали, как на гифке-КДПВ. Фактически это значит, что программа будет работать вдвое медленее: на каждой итерации цикла busy_loop будет сначала зажигать, а потом гасить каждую «каплю». На зажигающей полуитерации нужно будет устанавливать два бита видеопамяти: и для текущего положения «капли», и для предыдущего (погашенного последней полуитерацией).

Итак, «каплю» нужно зажигать в том случае, если а) два нижних бита её значения оба установлены; б) мы на зажигающей полуитерации; — и гасить во всех остальных случаях. Самый простой способ всё это реализовать — заменить в последовательности команд, определяющей цвет капли (ld.b r2, #2; lsr.wt r0, r2;) фиксированное значение #2 на переменную flag, которая будет иметь значение 2 на зажигающей полуитерации, и 1 на гасящей:

busy_loop:
        ld.b    r1, #3;   // !
        ld.b    r2, flag; // !
        sub     r1, r2;   // !
        st.b    flag, r1; // !

        ld.b    r1, #32;
next_col:
        jsr     add_position;
        ld.b    r0, (r2);
        ld.b    r3, flag; // !
        lsr     r3, #1;   // !
        lsl     r3, #2;   // !
        add     r0, r3;   // !
        btst    r0, #8;
        beq     save;
        jsr     rand;
save:   st.b    (r2), r0;
        addq    r1, #-1;
        bmi     busy_loop;

        move    r3, r1; // x     (0..1f)
        lsr     r3, #3; // byte addr in row (0..3)
        ld.b    r2, #0xfc; // y mask
        and     r2, r0; // y * 4 (0..fc)
        add     r3, r2; // byte addr in screen
        ld.w    r2, #0xa000;
        add     r3, r2; // byte addr in memory
        ld.b    r2, flag;  // !
        lsr.wt  r0, r2;

В начале цикла busy_loop мы вычитаем текущее значение flag из 3, т.е. меняем 2 на 1, а 1 на 2. Затем вместо продвижения «капли» вниз на каждой итерации (addq r0, #2; addq r0, #2;) мы прибавляем к r0 значение (flag >> 1) << 2, т.е. 4 на зажигающей полуитерации, и 0 на гасящей.

Последнее, что осталось добавить — на зажигающей полуитерации установить ещё один бит, в байте по смещению -4 от самой «капли»:

        // and now apply
        test    r2;
        bpl     blank;
        bset    r0, r2;
        st.b    (r3), r0;  // !
        addq    r3, #-2;   // !
        addq    r3, #-2;   // !
        btst    r3, #8;    // !
        bne     next_col;  // !
        ld.b    r0, (r3);  // !
        bset    r0, r2;    // !
        jmp     apply;
blank:  bclr    r0, r2;
apply:  st.b    (r3), r0;
        jmp     next_col;

Проверка btst r3, #8; bne next_col; обеспечивает, что мы не выйдем за верхний край «дисплея» и не попытаемся записать что-то по адресу 0x9FFx.

Теперь капли мигают, как и задумано:




Сейчас, чтобы попробовать запустить на Megaprocessor свою собственную программу, нужно договариваться с его создателем о визите к нему домой; но через месяц, по его словам, Megaprocessor переедет в Кембриджский центр истории компьютеров, и будет доступен широкой публике пять дней в неделю.

Успехов в мегапрограммировании!