На Geektimes летом была статья про Megaprocessor — процессор из дискретных транзисторов и светодиодов, который весит полтонны и занимает всю гостиную в обычном таунхаусе под Кембриджем. Я решил воспользоваться своей географической близостью к этому мегапроекту, и запрограммировать для него что-нибудь презентабельное — например, спортировать для Megaprocessor мою предыдущую хабрапрограммку «Digital Rain».
Система команд Megaprocessor описана на сайте разработчика.
Большинство команд состоят из одного байта, за которым может следовать непосредственный операнд (один или два байта). Регистров общего назначения всего четыре (R0-R3), при этом они не равноправны: например, для команд доступа к памяти адрес должен быть либо в R2, либо в R3; а операнд — в одном из двух оставшихся регистров.
Программистам, привыкшим к системе команд x86 или ARM, набор команд Megaprocessor покажется крайне бедным: нет ни косвенной адресации «база+смещение», ни непосредственных операндов у арифметических команд (за исключением
Итак, приступим.
Программа для Megaprocessor начинается (по адресу 0) с таблицы векторов прерываний. Каждому из четырёх векторов отведены по четыре байта. Начиная с адреса 0x10 может располагаться собственно код программы. Из 64КБ адресного пространства, вся первая половина (до адреса 0x8000) может использоваться кодом; адреса 0xA000-0xA0FF соответствуют «дисплею» — дискретной памяти, каждый бит которой снабжён светодиодным индикатором. marks ошибся, написав «Объем памяти составляет 256 байт.» — это объём «видеопамяти», а не основной памяти для кода и данных.
Из четырёх векторов прерываний в нашей программе используется только вектор
Первым делом после запуска нужно инициализировать стек и переменные. Стек пусть растёт вниз, начиная с адреса 0x2000 — этого нам хватит с большим запасом. Переменные понадобятся всего две:
Поскольку записать байт по адресу
Основная часть программы — бесконечный цикл, в котором мы проходим справа налево по каждому «столбцу дисплея», и сдвигаем в нём «каплю» на одну позицию вниз. Младшие два бита «капли» обозначают её цвет (3 — «горит»; 0, 1 или 2 — «не горит»), оставшиеся шесть битов — координату (0..63), поэтому «сдвиг вниз» означает прибавление 4. Как только «капля» доползла до низа «дисплея» (значение превысило 255), заменяем её новым случайным байтом.
Прибавить 4 одной командой невозможно, поэтому мы дважды повторяем
Как будем генерировать случайные числа? RANDU, который я использовал в 32-битном «Digital Rain», уже не подходит: Megaprocessor способен умножать только 16-битные числа; поэтому из списка простых ГСЧ возьмём такой, где множитель 16-битный. Мне понравился ГСЧ, обозначенный как «Turbo Pascal».
Этот простой и симпатичный ГСЧ возвращает сгенерированное значение в r0, но к сожалению, портит значения всех остальных регистров. Обратим внимание, что в обоих случаях, когда мы вызываем
Последняя здесь хитрость — то, что вычисление
Теперь самое интересное — вторая половина цикла
Чтобы «зажечь» или «погасить» нужный бит, нужно первым делом вычислить адрес соответствующего байта «видеопамяти». Поскольку у нас номер «столбца» хранится в
И вот что получается в итоге:
Остался последний штрих: сделать, чтобы «капли» мигали, как на гифке-КДПВ. Фактически это значит, что программа будет работать вдвое медленее: на каждой итерации цикла
Итак, «каплю» нужно зажигать в том случае, если а) два нижних бита её значения оба установлены; б) мы на зажигающей полуитерации; — и гасить во всех остальных случаях. Самый простой способ всё это реализовать — заменить в последовательности команд, определяющей цвет капли (
В начале цикла
Последнее, что осталось добавить — на зажигающей полуитерации установить ещё один бит, в байте по смещению -4 от самой «капли»:
Проверка
Теперь капли мигают, как и задумано:
Сейчас, чтобы попробовать запустить на Megaprocessor свою собственную программу, нужно договариваться с его создателем о визите к нему домой; но через месяц, по его словам, Megaprocessor переедет в Кембриджский центр истории компьютеров, и будет доступен широкой публике пять дней в неделю.
Успехов в мегапрограммировании!
Система команд 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
выполняет переход в том случае, если результат последнего действия положительный, т.е. бит цвета снят.И вот что получается в итоге:
Код целиком
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 переедет в Кембриджский центр истории компьютеров, и будет доступен широкой публике пять дней в неделю.
Успехов в мегапрограммировании!
Поделиться с друзьями
Комментарии (5)
gleb_l
12.09.2016 00:29Пора писать эмулятор мегапроцессора — чтобы тренироваться в RISC-асме и выводить красивые картинки могли бы фанаты не только в окрестностях Кембриджа
tyomitch
12.09.2016 09:46+2У автора на сайте есть его собственный эмулятор — только для Windows, и довольно неудобный в использовании; но хоть что-то.
SLY_G
Пожалуй, лучшее посвящение хабру. Самое масштабное, по меньшей мере.
Boomburum
Не могу не согласиться :)