Микроконтроллер Nintendo "Game and Watch" или как ускорить инкремент
В первых наладонных электронных играх Nintendo — Game & Watch (которые в СССР клонировали в виде «Волк ловит яйца» и т.п.) в качестве процессора использовались 4–битные микроконтроллеры Sharp серии SM–5xx
Например в популярных версиях про Микки–Мауса, морячка Попайя или Donkey Kong–а трудился чип SM–510.
Счётчик команд в этом чипе был сегментированным и в пределах сегмента адрес команды был 6–битным (значения от 0 до 63).
Традиционно счётчик команд при переходе к следующей инкрементируется, т.е. увеличивается на единицу и многие сочли бы это одним из самых простых арифметических действий для такой задачи, однако создатели Sharp SM–510 посчитали инкремент 6–битного счётчика слишком долгой операцией и упростили её.
«Проблема» с инкрементами тут в том, что чтобы вычислить i–ый разряд надо знать произошло переполнение в разряде i–1 или нет — по триггерам счётчика «бежит» электронная волна вот этого вот вычисления переноса и окончательного вычисления разряда. Чем больше бит, тем дольше эта волна бежит и тем большую паузу нужно выдерживать в электронных схемах чтобы быть уверенным что всё число посчиталось до конца. Вот эта пауза разработчикам видимо и не понравилась, т.к. инкременты 4–битных значений в этом микроконтроллере были, но 6–битный счётчик инструкций видимо в них не вписывался.
Краткий мануал по процессору можно посмотреть тут: bitsavers.org/components/sharp/_dataBooks/1990_Sharp_Microcomputers_Data_Book.pdf
Очень кратко обрисую его характеристики:
ROM 2772 x 8 бит
RAM 128 x 4 бита (из которых 32 x 4 бита VRAM находятся вне чипа)
49 инструкций
2 уровня вложенности стека (вызова процедур)
4-битная RAM и 8-битная ROM — инструкции 8-битные и иногда даже двухбайтовые если нужен операнд. Т.к. почти все регистры были 4-битными, то например чтобы адресовать RAM использовались два индексных регистра Bm и Bl. Последний был 4-битным, а первый 3-битным и в инструкциях например сложения они давали адрес ячейки RAM с которой складывался аккумулятор. Двухбайтовой инструкцией можно было сразу загрузить и Bm и Bl, а однобайтовыми инкрементировать или декрементировать Bl для скорости.
С ROM всё было еще запутаннее — PC состоял из трёх частей: Pu, Pm и Pl с битностями 2:4:6. Из арифметики по сути были только разные варианты сложения, десятичная коррекция, инверсия бит и прокрутка аккумулятора. В общем минимализм еще тот. Тактовая частота в 32768 Гц и её настраиваемый делитель с обработчиком прерываний прямо таки намекают на 1 прерывание в секунду чтобы обновить новыми цифрами времени LCD. Так что действительно не только Game, но и Watch напрашивался с самого начала.
Но вернёмся к «инкременту» PC: в документации Sharp этот трюк обозначен как «polynomial counter» и отсылает к Регистрам сдвига с линейной обратной связью.
Работает это вот как: на каждом шаге регистр сдвигается на 1 бит вправо и при этом новый появляющийся слева бит вычисляется как NOT (X XOR Y), где X и Y — это самые нижние биты счётчика до сдвига. Еще проще это выражение осмысливать как (X == Y), а на Си в эмуляторе MAME куда мне пришлось залезть чтобы до конца осознать документацию это выражается так (здесь — с сокращениями):
В результате если начинать считать от нуля, то получается такая вот красивая табличка неповторяющихся кодов (в 16–ричной системе исчисления «шаг: адрес»):
Т.е. последствием является то, что указатель инструкций «хаотично мечется» по памяти (и действительно главным упором LFSR является ГПСЧ), однако посещая каждую ячейку только один раз… точнее почти каждую, так как на последнем шаге 3f полученным адресом является не ff, а 00 — дело в том, что этот счётчик при затравочном значении ff просто на каждом шаге будет получать результат такой же — ff. Таким образом полный цикл до «проворота» в нём не 64 шага, а 63 и поэтому программы в SM–510 в каждой субстранице тоже имеют максимальный размер в 63 шага.
Такой код применяется потому что он быстрее честного и тупого как валенок инкремента из–за того, что не надо ждать распространяющейся по разрядам задержки по учёту бита переноса из предыдущего разряда — здесь почти каждый бит зависит только от одного соседнего и только бит feed зависит от двух самых нижних, но тоже в простой зависимости.
Вот такой лайфхак. xD
Например в популярных версиях про Микки–Мауса, морячка Попайя или Donkey Kong–а трудился чип SM–510.
Счётчик команд в этом чипе был сегментированным и в пределах сегмента адрес команды был 6–битным (значения от 0 до 63).
Традиционно счётчик команд при переходе к следующей инкрементируется, т.е. увеличивается на единицу и многие сочли бы это одним из самых простых арифметических действий для такой задачи, однако создатели Sharp SM–510 посчитали инкремент 6–битного счётчика слишком долгой операцией и упростили её.
«Проблема» с инкрементами тут в том, что чтобы вычислить i–ый разряд надо знать произошло переполнение в разряде i–1 или нет — по триггерам счётчика «бежит» электронная волна вот этого вот вычисления переноса и окончательного вычисления разряда. Чем больше бит, тем дольше эта волна бежит и тем большую паузу нужно выдерживать в электронных схемах чтобы быть уверенным что всё число посчиталось до конца. Вот эта пауза разработчикам видимо и не понравилась, т.к. инкременты 4–битных значений в этом микроконтроллере были, но 6–битный счётчик инструкций видимо в них не вписывался.
Краткий мануал по процессору можно посмотреть тут: bitsavers.org/components/sharp/_dataBooks/1990_Sharp_Microcomputers_Data_Book.pdf
Очень кратко обрисую его характеристики:
ROM 2772 x 8 бит
RAM 128 x 4 бита (из которых 32 x 4 бита VRAM находятся вне чипа)
49 инструкций
2 уровня вложенности стека (вызова процедур)
4-битная RAM и 8-битная ROM — инструкции 8-битные и иногда даже двухбайтовые если нужен операнд. Т.к. почти все регистры были 4-битными, то например чтобы адресовать RAM использовались два индексных регистра Bm и Bl. Последний был 4-битным, а первый 3-битным и в инструкциях например сложения они давали адрес ячейки RAM с которой складывался аккумулятор. Двухбайтовой инструкцией можно было сразу загрузить и Bm и Bl, а однобайтовыми инкрементировать или декрементировать Bl для скорости.
С ROM всё было еще запутаннее — PC состоял из трёх частей: Pu, Pm и Pl с битностями 2:4:6. Из арифметики по сути были только разные варианты сложения, десятичная коррекция, инверсия бит и прокрутка аккумулятора. В общем минимализм еще тот. Тактовая частота в 32768 Гц и её настраиваемый делитель с обработчиком прерываний прямо таки намекают на 1 прерывание в секунду чтобы обновить новыми цифрами времени LCD. Так что действительно не только Game, но и Watch напрашивался с самого начала.
Но вернёмся к «инкременту» PC: в документации Sharp этот трюк обозначен как «polynomial counter» и отсылает к Регистрам сдвига с линейной обратной связью.
Работает это вот как: на каждом шаге регистр сдвигается на 1 бит вправо и при этом новый появляющийся слева бит вычисляется как NOT (X XOR Y), где X и Y — это самые нижние биты счётчика до сдвига. Еще проще это выражение осмысливать как (X == Y), а на Си в эмуляторе MAME куда мне пришлось залезть чтобы до конца осознать документацию это выражается так (здесь — с сокращениями):
int feed = ((pc >> 1 ^ pc) & 1)? 0 : 0x20;
new_pc = feed | (pc >> 1 & 0x1f);
В результате если начинать считать от нуля, то получается такая вот красивая табличка неповторяющихся кодов (в 16–ричной системе исчисления «шаг: адрес»):
00:00 01:20 02:30 03:38 04:3c 05:3e 06:1f 07:2f
08:37 09:3b 0a:3d 0b:1e 0c:0f 0d:27 0e:33 0f:39
10:1c 11:2e 12:17 13:2b 14:35 15:1a 16:0d 17:06
18:03 19:21 1a:10 1b:28 1c:34 1d:3a 1e:1d 1f:0e
20:07 21:23 22:31 23:18 24:2c 25:36 26:1b 27:2d
28:16 29:0b 2a:25 2b:12 2c:09 2d:04 2e:22 2f:11
30:08 31:24 32:32 33:19 34:0c 35:26 36:13 37:29
38:14 39:2a 3a:15 3b:0a 3c:05 3d:02 3e:01 3f:00
Т.е. последствием является то, что указатель инструкций «хаотично мечется» по памяти (и действительно главным упором LFSR является ГПСЧ), однако посещая каждую ячейку только один раз… точнее почти каждую, так как на последнем шаге 3f полученным адресом является не ff, а 00 — дело в том, что этот счётчик при затравочном значении ff просто на каждом шаге будет получать результат такой же — ff. Таким образом полный цикл до «проворота» в нём не 64 шага, а 63 и поэтому программы в SM–510 в каждой субстранице тоже имеют максимальный размер в 63 шага.
Такой код применяется потому что он быстрее честного и тупого как валенок инкремента из–за того, что не надо ждать распространяющейся по разрядам задержки по учёту бита переноса из предыдущего разряда — здесь почти каждый бит зависит только от одного соседнего и только бит feed зависит от двух самых нижних, но тоже в простой зависимости.
Вот такой лайфхак. xD
3 комментария
P.S. Спасибо за статью! Порадовали. Где то в комментах проскакивало, что Вы собираетесь пойти крестовым походом на 6502, буду рад почитать.
Кстати на nesdev.com вчера (с этой же статьи по сути) мне рассказали, что похожий чип Sharp SM-59x трудился в NES в чипе региональной защиты CIC в американских картриджах. Т.е. Nintendo с Sharp так сказать совсем даже не прекратила отношения по этой линии тогда. :)