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

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

Система команд Megaprocessor описана на сайте разработчика ^[3]. Большинство команд состоят из одного байта, за которым может следовать непосредственный операнд (один или два байта). Регистров общего назначения всего четыре (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 ^[4] ошибся, написав «Объем памяти составляет 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 ^[5], который я использовал в 32-битном «Digital Rain», уже не подходит: Megaprocessor способен умножать только 16-битные числа; поэтому из списка простых ГСЧ ^[6] возьмём такой, где множитель 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 выполняет переход в том случае, если результат последнего действия положительный, т.е. бит цвета снят.

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

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

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:  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:
        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;

        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;

seed:   dw 1;
position:;

Остался последний штрих: сделать, чтобы «капли» мигали, как на гифке-КДПВ. Фактически это значит, что программа будет работать вдвое медленее: на каждой итерации цикла 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.

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

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

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:  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, #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;
        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;
        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;

seed:   dw 1;
flag:   db 2;
position:;

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

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

Автор: tyomitch

Источник ^[8]