Всем привет!
На этих выходных в Санкт-Петербурге прошёл очередной фестиваль Chaos Constructions, на котором собрались фанаты, программисты и разработчики, чтобы посоревноваться в мастерстве создания demo.
О том, что такое demo, можно почитать на сайте организаторов. А если вкратце, то участникам даётся задача сделать что-то впечатляющее на spectrum'е или аналогичном ретро-железе, и при этом ставятся ограничения на размер программ и длительность демки. Например, меня очень впечатлила вот эта на Spectrum'е, которая уместилась всего в 256 байт! Да, демка выводится на большой экран с отличным звуком, поэтому зрелище впечатляет!
Наша компания выступила спонсором фестиваля, а мы с коллегами организовали и провели конкурс hardware hack, целью которого стало определить архитекутуру процессора, имея минимум знаний о ней и скромный набор инструментов.
О том, как проходил конкурс, как и что мы к нему готовили и будет моя статья. Кому интересно, прошу под кат.
Итак, целью конкурса hardware hack было определить архитекутуру процессора, имея минимум знаний о ней и скромный набор инструментов. После архитектурных раскопок необходимо было внести изменения в исходную программу или запрограммировать что-то своё. В конечном итоге оценивалось потраченное время и вау-фактор того, что получилось.
Важный нюанс — в руки «игроков» должна была попасть какая-то железка (причем, лучше ретро), а не обычный комп. А, как говорится, «используй то, что под рукою, и не ищи себе другое». Вот мы и взяли материнскую плату от нашего прибора Беркут-ЕТ, немного поработали напильником (а также немного фрезой, отвёртками и пр.) и вместо привычного приборчика получился классный гаджет:
С обратной стороны такое (интерфейсную плату, где стоит 1G ethernet и FPGA, мы не подключали):
На борту платы вполне old-school'ная начинка (на самом деле новый Беркут-ЕТ уже имеет более современню, ARM-овую платформу):
Поскольку раньше у контроллеров не было такой развитой периферии как сейчас (плюс мы чего-то не знали много лет назад), мы всё, что можно, заводили на FPGA, а дальше уже программировали интерфейсы по своему усмотрению. Так на периферию FPGA попали LCD, светодиоды, клавиатура.
Ресурсы AVR весьма ограничены — у него и так миллион задач по управлению измерениями и т.п. вещами. Поэтому в FPGA есть графический контроллер. Собственный, спреферансом и профурсетками фреймбуфером и линиями Брезенхема, а также прямоугольниками, секторами, кругами, знако-генератором (три размера символов + разворот) и даже пунктирными линиями. Этот контроллер позволяет выводить графики на экран практически молниеносно, т.к. он, в отличие от AVR, работает на 50 МГц. Вот, например, такая картинка появляется за доли секунды:
Однако, при всём богатстве функций есть одно узкое место — объём памяти фреймбуфера. Хватает только на 8 цветов. Поэтому для каждого пикселя используется 3 бита, которые аккуратненько упаковываются в байты для оптимального использования памяти.
Аналогично дела обстоят с клавиатурой: FPGA генерирует импульсы на матрицу и отслеживает нажатия, а процессору достаётся только прерывание и статусный регистр о нажатых кнопках. И с диодами — процессор пишет в регистр FPGA, а выходы регистра уже подключены к диодам.
Архитектура (укрупнённо) такая:
Но что-то я увлёкся архитектурой. Просто хотелось дать представление об экспонатах, чтобы они не были для читателя чёрным ящиком.
Таким образом, железяка со всей необходимой периферией ввода-вывода для проведения конкурса (целых пять штук) у нас уже была и она вполне подходила по формату.
По задумке мы должны были предоставить для «раскопок» некий процессор, архитектура которого участникам заранее не известна. На деле это означало, что мы должны были дать инструмент, который позволит изучить память, переменные, стек, и т.д. и поэкспериментировать с изменением её содержимого и, следовательно, алгоритма. Давать отладчик для AVR'а показалось слишком громоздим и муторным решением — всё-таки на раскопки давалось всего 3 часа, да и подключать к каждой плате по отладчику и компу не очень хотелось…
И тогда мы решили написать свой легковесный стековый интерпретатор, который помимо работы со стеком и математических/логических операций сумел бы выводить графические примитивы на экран, пищать и «поджигать» светодиоды. Почему именно стековый? Он нам показался достаточно простым, и к тому же было просто интересно попробовать сделать что-то вроде forth'а, но с ограниченным набором команд, но и прозрачным интерфейсом для расширения системы команд.
Ну а для «ковыряния» в памяти решили написать отладчик. Чего уж там мелочиться: делать, так по-взрослому ;)
Рассказывать в этой статье подробно про стековый интерпретатор я не планировал (дайте знать, напишу отдельную статью со всеми деталями, кодом и компилятором). Ограничусь кратким экскурсом.
Стековый интерпретатор читает память программ и в зависимости от кода операции выполняет определённые действия с вершиной стека. Как правило — с вершины стека забирается 1-2-3, редко 4 значения (а в общем случае — сколько угодно) и результат операции кладётся обратно на стек. Эта архитектура очень просто реализуется, причём не только программно.
При этом программа выглядит несколько необычно, потому что отсутствует «привычная» запись (вместо неё используется обратная польская). Например, чтобы просуммировать два числа, надо выполнить две операции «положить на стек число», а потом операцию «сумма». В итоге на вершине стека окажется результат суммирования, а два операнда со стека будут убраны. Короче, мозг нужно немного сломать.
Для своего интепретатора мы взяли самый необходимый набор команд (в сумме чуть более 20):
Такой набор вполне позволяет организовать циклы, условные переходы, инкременты счётчиков и прочие конструкции первой необходимости. От определения функций (как в forth'е) мы отказались
сразу, чтобы не усложнять. Переменные тоже не стали реализовывать, как потом оказалось — зря.
Сначала написали интерпретатор на С под обычную линуксовую машинку. Одновременно с этим появился и «компилятор» на python'е, который переводит текстовые команды в байт-код.
Когда с интерпретатором (кстати, назвали его funfte, так как forth — это «четвёртый», а английское «fifth» уже занято под другой интерпретатор) всё стало понятно, оставалось только разработать отладчик, а потом соединить всё воедино.
Вот, что у нас получилось (не забываем, что для участников всё должно быть максимально запутано, поэтому на самом экране подписей быть не может), схематично:
Благодаря тому, что funfte имеет только две области памяти — программную и стек, в отладчике автоматически появилось две колонки. В первой — распечатка памятя программ, а во второй — стека. Справа внизу отображается PC, а строка ввода внизу позволяет со встроенной клавиатуры вводить команды записи и чтения памяти, а также управлять breakpoint'ами и листингом.
Все числа, конечно же, в hex'е.
Управление отладчиком и вводом команд мы перенесли на кнопки:
А наш отладчик научили самому необходимому:
В итоге, когда всё закодировали и перенесли на AVR (конечно же, использовали все наработки из «родного» проекта, включая клавиатуру, диоды, LCD-контроллер и массу готовых объектов), написали простенький пример на получившемся языке, который в цикле «поджигает» диоды, выводит строчку «DEMO» и заставляет бегать зелёный кубик по экрану слева направо и обратно.
Ура, Заработало! И вот, как выглядит в интерактиве
В субботу 29 августа с пятью прошитыми девайсами мы пришли на chaos construction и разместились в зоне hack space.
Что порадовало: мы даже не успели дождаться официального старта нашего конкурса, потому что наши загадочные девайсы попали в руки прожжёных memory-digger'ов.
Я и мои коллеги очень боялись, что мы придумали что-то слишком сложное и никто не сможет разобраться. И, к счастью, ошиблись! Уже через десять минут один из участников смог изменить цвет выводимого прямоугольника и побежал шёпот про «стек», «форт» и тому подобные вещи.
А через час прямоугольник, который должен был двигаться слева направо и обратно, изменил своё поведение (не сам, конечно, а с помощью одного из победителей конкурса). Для этого необходимо было отреверсить список команд, понять алгоритм и в том цикле, где прямоугольник меняет координаты X, изменять координату Y.
Более того, у хакеров на столах уже лежал полный список команд нашего мега-процессора, включая (внимание!) даже те команды, которые в примере не использовались.
На следующем заходе, после двух часов раскопок нам в руки дали девайс, в котором была прошита программа всего на 16 байт(, Карл)! В общем зачёте эта работа заняла первое место.
И вот ещё одна любопытная работа:
Итог первого дня: больше десяти человек поучаствовали, справились почти все. Отлично!
Ну что же, на следующий день мы решили немного поменять задачу.
Теперь участникам была открыта вся система команд и, чего уж там, код интерпретатора. Нужно было написать что-нибудь впечатляющее. И снова результат превзошёл ожидания: через пару часов у меня в github'е уже лежал pull request на 4 новые команды для интерпретатора, которые позволяли обращаться к любой ячейке стека и памяти. Т.е. фактически появилась возможность объявлять переменные. У них конечно не было имени, нужно было помнить их адрес, но всё же.
После мёржа, сборки и заливки прошивки у нас появилась новая демка, которая меняет собственный код в ходе выполнения. Она заняла 52 байта и второе место в нашем конкурсе.
Также во второй день нам помогли найти и пофиксить несколько багов, за что всем участникам огромное спасибо!
В конце дня на официальном закрытии фестиваля мы вручили призы победителям
Призы, конечно же, тоже сделали своими руками
Что я хотел бы сказать в заключение. Спасибо организаторам фестиваля за классное, драйвовое мероприятие, за возможность в нём поучаствовать и за полученное удовольствие от общения с по-настоящему увлечёнными людьми. Спасибо всем, кто поучаствовал в нашем конкурсе: нам было безумно приятно видеть, что мы не зря старались. Конечно же, интерпретатор в таком виде не очень практически полезен, но позволяет отвлечься от высокоуровневого программирования, в котором 90% интересных подробностей скрыты от разработчика, и немного потренировать память и внимание, а также узнать что-то новое и весело провести время.
И, конечно же, благодарю своих коллег за командную работу по подготовке к конкурсу.
PS: мы сделали одно большое упущение: не сделали управление бипером в полном объёме. Мы дали возможность управлять только длительностью, а нужно было ещё управление частотой заложить. Тогда демки могли бы быть с музыкальным сопровождением. Ну ничего, в следующем году наверстаем упущенное!
На этих выходных в Санкт-Петербурге прошёл очередной фестиваль Chaos Constructions, на котором собрались фанаты, программисты и разработчики, чтобы посоревноваться в мастерстве создания demo.
О том, что такое demo, можно почитать на сайте организаторов. А если вкратце, то участникам даётся задача сделать что-то впечатляющее на spectrum'е или аналогичном ретро-железе, и при этом ставятся ограничения на размер программ и длительность демки. Например, меня очень впечатлила вот эта на Spectrum'е, которая уместилась всего в 256 байт! Да, демка выводится на большой экран с отличным звуком, поэтому зрелище впечатляет!
Наша компания выступила спонсором фестиваля, а мы с коллегами организовали и провели конкурс hardware hack, целью которого стало определить архитекутуру процессора, имея минимум знаний о ней и скромный набор инструментов.
О том, как проходил конкурс, как и что мы к нему готовили и будет моя статья. Кому интересно, прошу под кат.
Итак, целью конкурса hardware hack было определить архитекутуру процессора, имея минимум знаний о ней и скромный набор инструментов. После архитектурных раскопок необходимо было внести изменения в исходную программу или запрограммировать что-то своё. В конечном итоге оценивалось потраченное время и вау-фактор того, что получилось.
Важный нюанс — в руки «игроков» должна была попасть какая-то железка (причем, лучше ретро), а не обычный комп. А, как говорится, «используй то, что под рукою, и не ищи себе другое». Вот мы и взяли материнскую плату от нашего прибора Беркут-ЕТ, немного поработали напильником (а также немного фрезой, отвёртками и пр.) и вместо привычного приборчика получился классный гаджет:
С обратной стороны такое (интерфейсную плату, где стоит 1G ethernet и FPGA, мы не подключали):
Немного про архитектуру и про внутренности платы
На борту платы вполне old-school'ная начинка (на самом деле новый Беркут-ЕТ уже имеет более современню, ARM-овую платформу):
- AVR ATmega256 8 МГц + целых 40 килобайт памяти (подключен внешний чип на 32, а встроенной 8) и 256К программ!
- FPGA Cyclone II, подключена к AVR по параллельной шине (отдельный чипселект), 5000 логических ячеек
- LCD 320x240, работающий в восьмицветном режиме (см. ниже), подключен к FPGA
- матричная клавиатура, подключенная к FPGA
- 8 светодиодов
- beep'ер
- ftdi конвертер USB в uart
Поскольку раньше у контроллеров не было такой развитой периферии как сейчас (плюс мы чего-то не знали много лет назад), мы всё, что можно, заводили на FPGA, а дальше уже программировали интерфейсы по своему усмотрению. Так на периферию FPGA попали LCD, светодиоды, клавиатура.
Ресурсы AVR весьма ограничены — у него и так миллион задач по управлению измерениями и т.п. вещами. Поэтому в FPGA есть графический контроллер. Собственный, с
Однако, при всём богатстве функций есть одно узкое место — объём памяти фреймбуфера. Хватает только на 8 цветов. Поэтому для каждого пикселя используется 3 бита, которые аккуратненько упаковываются в байты для оптимального использования памяти.
Аналогично дела обстоят с клавиатурой: FPGA генерирует импульсы на матрицу и отслеживает нажатия, а процессору достаётся только прерывание и статусный регистр о нажатых кнопках. И с диодами — процессор пишет в регистр FPGA, а выходы регистра уже подключены к диодам.
Архитектура (укрупнённо) такая:
Но что-то я увлёкся архитектурой. Просто хотелось дать представление об экспонатах, чтобы они не были для читателя чёрным ящиком.
Таким образом, железяка со всей необходимой периферией ввода-вывода для проведения конкурса (целых пять штук) у нас уже была и она вполне подходила по формату.
А что будем reverse engineer'ить?
По задумке мы должны были предоставить для «раскопок» некий процессор, архитектура которого участникам заранее не известна. На деле это означало, что мы должны были дать инструмент, который позволит изучить память, переменные, стек, и т.д. и поэкспериментировать с изменением её содержимого и, следовательно, алгоритма. Давать отладчик для AVR'а показалось слишком громоздим и муторным решением — всё-таки на раскопки давалось всего 3 часа, да и подключать к каждой плате по отладчику и компу не очень хотелось…
И тогда мы решили написать свой легковесный стековый интерпретатор, который помимо работы со стеком и математических/логических операций сумел бы выводить графические примитивы на экран, пищать и «поджигать» светодиоды. Почему именно стековый? Он нам показался достаточно простым, и к тому же было просто интересно попробовать сделать что-то вроде forth'а, но с ограниченным набором команд, но и прозрачным интерфейсом для расширения системы команд.
Ну а для «ковыряния» в памяти решили написать отладчик. Чего уж там мелочиться: делать, так по-взрослому ;)
Немного про стековый интерпретатор
Рассказывать в этой статье подробно про стековый интерпретатор я не планировал (дайте знать, напишу отдельную статью со всеми деталями, кодом и компилятором). Ограничусь кратким экскурсом.
Стековый интерпретатор читает память программ и в зависимости от кода операции выполняет определённые действия с вершиной стека. Как правило — с вершины стека забирается 1-2-3, редко 4 значения (а в общем случае — сколько угодно) и результат операции кладётся обратно на стек. Эта архитектура очень просто реализуется, причём не только программно.
При этом программа выглядит несколько необычно, потому что отсутствует «привычная» запись (вместо неё используется обратная польская). Например, чтобы просуммировать два числа, надо выполнить две операции «положить на стек число», а потом операцию «сумма». В итоге на вершине стека окажется результат суммирования, а два операнда со стека будут убраны. Короче, мозг нужно немного сломать.
Стековый интепрететатор funfte
Для своего интепретатора мы взяли самый необходимый набор команд (в сумме чуть более 20):
- для работы со стеком (push, drop, swap, etc...)
- для математических операций (add, sub, mul, inc, dec, etc..)
- для условий и переходов (if, jump, cond. jump)
- и, конечно же, для вывода на экран, на пищалку и диоды
Такой набор вполне позволяет организовать циклы, условные переходы, инкременты счётчиков и прочие конструкции первой необходимости. От определения функций (как в forth'е) мы отказались
сразу, чтобы не усложнять. Переменные тоже не стали реализовывать, как потом оказалось — зря.
Сначала написали интерпретатор на С под обычную линуксовую машинку. Одновременно с этим появился и «компилятор» на python'е, который переводит текстовые команды в байт-код.
Когда с интерпретатором (кстати, назвали его funfte, так как forth — это «четвёртый», а английское «fifth» уже занято под другой интерпретатор) всё стало понятно, оставалось только разработать отладчик, а потом соединить всё воедино.
Отладчик: только в hex'е, только хардкор!
Вот, что у нас получилось (не забываем, что для участников всё должно быть максимально запутано, поэтому на самом экране подписей быть не может), схематично:
Благодаря тому, что funfte имеет только две области памяти — программную и стек, в отладчике автоматически появилось две колонки. В первой — распечатка памятя программ, а во второй — стека. Справа внизу отображается PC, а строка ввода внизу позволяет со встроенной клавиатуры вводить команды записи и чтения памяти, а также управлять breakpoint'ами и листингом.
Все числа, конечно же, в hex'е.
Управление отладчиком и вводом команд мы перенесли на кнопки:
- F1 — рестарт, выполняем введённую программу с начала
- F3 — continue
- F4 — next
- Enter — выполнение введённой команды
- 0..9 — ввод чисел и символов (как на кнопочных телефонах)
- X — удаление последнего введённого символа (backspace)
- reboot(кнопочка справа, её не видно на фото) — перезагружаем девайс и получаем исходное состояние
А наш отладчик научили самому необходимому:
- выполнять программу шаг за шагом (next): кнопка F4
- установить breakpoint: b addr
- удалить breakpoint: d addr
- продолжить выполнение (continue): кнопка F3
- записать значение в память: w addr data
- изменить program counter: p new-pc-value
- делать листинг, начиная с адреса в памяти:l addr. Листинг будет автоматически выполняться с адреса pc, если после команды l выполнение программы продолжилось.
В итоге, когда всё закодировали и перенесли на AVR (конечно же, использовали все наработки из «родного» проекта, включая клавиатуру, диоды, LCD-контроллер и массу готовых объектов), написали простенький пример на получившемся языке, который в цикле «поджигает» диоды, выводит строчку «DEMO» и заставляет бегать зелёный кубик по экрану слева направо и обратно.
Ура, Заработало! И вот, как выглядит в интерактиве
Первый день фестиваля
В субботу 29 августа с пятью прошитыми девайсами мы пришли на chaos construction и разместились в зоне hack space.
Что порадовало: мы даже не успели дождаться официального старта нашего конкурса, потому что наши загадочные девайсы попали в руки прожжёных memory-digger'ов.
Я и мои коллеги очень боялись, что мы придумали что-то слишком сложное и никто не сможет разобраться. И, к счастью, ошиблись! Уже через десять минут один из участников смог изменить цвет выводимого прямоугольника и побежал шёпот про «стек», «форт» и тому подобные вещи.
А через час прямоугольник, который должен был двигаться слева направо и обратно, изменил своё поведение (не сам, конечно, а с помощью одного из победителей конкурса). Для этого необходимо было отреверсить список команд, понять алгоритм и в том цикле, где прямоугольник меняет координаты X, изменять координату Y.
Более того, у хакеров на столах уже лежал полный список команд нашего мега-процессора, включая (внимание!) даже те команды, которые в примере не использовались.
На следующем заходе, после двух часов раскопок нам в руки дали девайс, в котором была прошита программа всего на 16 байт
И вот ещё одна любопытная работа:
Итог первого дня: больше десяти человек поучаствовали, справились почти все. Отлично!
Второй день фестиваля
Ну что же, на следующий день мы решили немного поменять задачу.
Теперь участникам была открыта вся система команд и, чего уж там, код интерпретатора. Нужно было написать что-нибудь впечатляющее. И снова результат превзошёл ожидания: через пару часов у меня в github'е уже лежал pull request на 4 новые команды для интерпретатора, которые позволяли обращаться к любой ячейке стека и памяти. Т.е. фактически появилась возможность объявлять переменные. У них конечно не было имени, нужно было помнить их адрес, но всё же.
После мёржа, сборки и заливки прошивки у нас появилась новая демка, которая меняет собственный код в ходе выполнения. Она заняла 52 байта и второе место в нашем конкурсе.
Также во второй день нам помогли найти и пофиксить несколько багов, за что всем участникам огромное спасибо!
Награждение победителей
В конце дня на официальном закрытии фестиваля мы вручили призы победителям
Призы, конечно же, тоже сделали своими руками
Небольшое заключение
Что я хотел бы сказать в заключение. Спасибо организаторам фестиваля за классное, драйвовое мероприятие, за возможность в нём поучаствовать и за полученное удовольствие от общения с по-настоящему увлечёнными людьми. Спасибо всем, кто поучаствовал в нашем конкурсе: нам было безумно приятно видеть, что мы не зря старались. Конечно же, интерпретатор в таком виде не очень практически полезен, но позволяет отвлечься от высокоуровневого программирования, в котором 90% интересных подробностей скрыты от разработчика, и немного потренировать память и внимание, а также узнать что-то новое и весело провести время.
И, конечно же, благодарю своих коллег за командную работу по подготовке к конкурсу.
PS: мы сделали одно большое упущение: не сделали управление бипером в полном объёме. Мы дали возможность управлять только длительностью, а нужно было ещё управление частотой заложить. Тогда демки могли бы быть с музыкальным сопровождением. Ну ничего, в следующем году наверстаем упущенное!
