ミジンコがTuring CompleteでCPUを自作した話

 ミジンコがTuring Completeで CPUを自作した話 IPUSIRON 第100回 ゆるいハッキング⼤会 in TOKYO（2023年10⽉21⽇） 1

 ⽬次 ➤ ⾃⼰紹介 ➤ 本テーマを選択した理由 ➤ ⾃作CPUをテーマにするということ ➤ Turing Completeの紹介 ➤ Turing Completeの進め⽅ ➤ 参考になる（かもしれない）書籍の紹介 ➤ 【おまけ】直近の予定 2

 ⾃⼰紹介 ➤ HN：IPUSIRON（イプシロン） ➤ @ipusiron ➤ Security Akademeiaを運営 ➤ ➤ ➤ 2000年頃～。 職業は⽂筆家 ➤ 33冊超。積読75cm。 ➤ メインは執筆活動。サブでは⾊々。 ゆるハック登壇･･･今回で5回⽬ 積読（2022年11⽉撮影） 3

 近年の出版物（著作・翻訳本・監訳本） ➤ セキュリティを情報・物理的・⼈的の観点から研究。 4

 本テーマを 選択した理由 5

 2023年の夏の活動 ➤ 5⽉ 仕事 6⽉ 晴読⾬読 ➤ 7⽉ 8⽉ Turing Complete ➤ 夏休み3.5ヶ⽉ ➤ 仕事の空⽩期間（たまたま） ➤ ⼤きな休みなので、集中して実績解除しようと考え た。 前半2ヶ⽉は読書 ➤ CPU本、デジタル回路本 ➤ 再読を含む。 後半1.5ヶ⽉はTuring Complete ➤ 9⽉ 攻略記事をブログへ ➤ 仕事 ➤ https://akademeia.info/?page_id=32179 同時に、10⽉の本発表のネタにしようと考えていた。 ➤ 成果物から成果物を⽣み出せば、より効果的。 6

• https://akademeia.info/?page_id=32179

 7

 8

 ⾃作CPUを テーマにするということ 9

 ⾃作CPUをテーマにした理由（裏） ➤ ➤ ⾃作○○ ➤ ⾃作CPU、⾃作OS、⾃作コンパイラー ➤ TCP⾃作、ルーター⾃作、ポートスキャナ⾃作 ➤ ⾃作本棚、⾃作⾃動⾞、セルフビルドホーム ⾃作というキーワードに（⾃分を含めて）惹かれる⼈が多い。 ➤ ➤ 「⾃作」というキーワードをつけるだけで（⼀定数）売れる。 ⾃作に惹かれる理由 ➤ 好奇⼼･･･より詳しくなりたい、実験・ものづくりが好き ➤ 探究⼼･･･ブラックボックスの解消 ➤ 夢を与えてくれる･･･今の⾃分にとっては難題（コンプレックス）だが、⼈⽣の中でいつかその障害を乗り越え たい。 ➤ ⾃作CPU･･･自作○○の中でも、大きなテーマの1つ ➤ ⼈⽣で1回達成（実績解除）しておけば、その後の⼈⽣を⽣きやすくなる。 10

 ⾃作CPUの攻め⽅ ➤ ⾃作CPUに挑戦すると⼀⾔でいっても、さまざまな攻め⽅がある。 ➤ ハードウェアとソフトウェア ➤ ボトムアップとトップダウン ➤ 既存のCPUを使うか ➤ どの攻め⽅が合っているかは⼈それぞれ。 ➤ 得意分野や好きな分野との兼ね合い。 11

 ハードウェアとソフトウェア ➤ ➤ ハードウェア ➤ ICチップを買い集めて、それらをはんだ付けしてCPUを作る。 ➤ ⾦銭的・時間的コストが⼤･･･部品の調達、道具の準備 ➤ 電⼦⼯作のスキル必須･･･はんだ付け、基盤作成、配線作業、ケース作成 ➤ ハードウェア特有の課題多数･･･ノイズ、電源問題、熱問題などいろいろ課題はある。 ➤ 失敗すれば⽂鎮未満。 ➤ ⼀番ストイック性を要求される。 ソフトウェア ➤ PCと評価ボードがあればよいだけ。はんだ付け不要。 ➤ CPUの回路図をハードウェア記述⾔語で書いても100⾏未満。マザーボードやメモリーといった周辺回路を合わ せても、150⾏程度。 ➤ FPGA評価ボードは15k前後。 ➤ ⼀度満⾜してしまうとせっかく購⼊した基盤がタンスの肥やしになりやすい。 12

 ボトムアップとトップダウン ➤ ➤ ボトムアップ⼿法 ➤ 従来型。 ➤ 具体（抽象度が低い）⇒抽象（抽象度が⾼い） ➤ （アーキテクチャー⇒）論理回路⇒レジスタ⇒ALU⇒･･･ ➤ 着実かつ合理的なアプローチ ➤ 初⼼者には全体像が⾒通しにくい。ソフトウェアの理解が希薄になりやすい。 トップダウン⼿法 ➤ 抽象⇒具体 ➤ CPUエミュレーター⇒エミュレーターのコードをハードウェア記述⾔語に変換（移植）⇒ ハードウェアに書き込む ➤ 不明点が明らかになる。最終的にCPUの全体像が⾒通しよくなる。 13

 既存のCPUを使うか ➤ 昔使われていた既存CPU･･･8085、8600、Z80など ➤ ⾃作CPUというより、⾃作ワンボードマイコンに興味がある⼈向け。 ➤ 既存CPUを使うと ➤ 周辺回路を組む、配線に注⼒できる･･･既存CPUのピン仕様を理解しなければなら ない。 ➤ ➤ 過去のプログラムを流⽤できる。 CPUを実現する内部回路は以前としてブラックボックスのまま。 14

 Turing Completeの紹介 15

 TURING COMPLETEを採⽤した理由 ➤ 論理回路のクイズを解きながら、最終的に仮想のコンピュー タを作り上げる。 ➤ NANDゲート⇒･･･⇒CPU⇒CPU周り⇒アセンブリー⾔語 ➤ PCのみで完結。 ➤ Steamで2k。⾦銭的コスト最⼩。 ➤ ゲームなので、CPUへの情熱が薄くても、飽きにくい。 ➤ 困難にぶつかっても、攻略記事で解決でき、挫折しにくい。 ➤ ⼀種のシミュレーターだがボトムアップ的に学習できる。 ➤ 具体（基本的な論理回路）⇒抽象（アセンブリ⾔語） 16

 ミジンコがTuring Completeに挑戦した理由 ➤ 『ホワイトハッカーの教科書』の執筆にあたり、挑戦済みだった。 ➤ P.154で紹介。 ➤ 今年の夏にデジタル回路本を多読（再読を含む）。その実⼒試しとして再挑戦。 ➤ どうやら⼤幅なアップグレードがあったようで、ステージの⼀部が新しくなり、過 去のセーブではうまく動かなくなっていた。 ➤ 過去のセーブをリセットして、ゼロから再挑戦。 ➤ ネットの攻略記事･･･過去の攻略、正解の回答のみで考え⽅がほとんどない ➤ できる⼈にとっては常識なのかもしれないが、考え⽅が重要だと思った。 ➤ チャンスととらえて、攻略記事を⾃分で書いた。 17

 Turing Completeの特徴 ➤ ➤ ➤ メリット ➤ シミュレーターなので、ハードウェア特有のわずらわしさがない。 ➤ ストーリーモードは全80ステージ。段階を追って経験を積め、飽きずに進められる。 ➤ ストーリーモードをクリアしても、サンドボックスモードでずっと楽しめる。 ➤ Mac対応。セーブデータの同期もOK。 デメリット ➤ シミュレーターであり本物ではない。本物を作ったという実績は解除できない。 ➤ すべてのデジタル回路を学べるわけではない。 どのくらいでクリアできるか？ ➤ 経験者や早い⼈なら、1週間 ➤ ゼロからで解説記事を読みながらなら、1ヶ⽉ 18

 19

 20

 21

 7つのカテゴリー 1. Basic Logicカテゴリー 2. ArithmeticカテゴリーとMemoryカテゴリー 3. CPU Architectureカテゴリー 4. Programmingカテゴリー 5. CPU Architecture 2カテゴリー 6. Functionsカテゴリー 7. Assembly Challengesカテゴリー 22

 Turing Completeの進め⽅ 23

 英語が不安なら ➤ DeepL翻訳 ➤ Capture2Text ➤ ゲーム画⾯は通常コピーできない。 ➤ ⼀発で「SS⇒OCR⇒Google翻訳」できる。 24

 [Fn1]キーで 範囲選択 ゲーム内のテキスト Capture2Text 25

 Turing Completeの進め⽅ ➤ 「真理値表を追うことはできる⇒⾃⼒で回路を組む」にはギャップがある。 ➤ ➤ 回答だけ⾒てステージを進めてもあまり⾝についている感じがしない。 コンポーネントやワイヤーが増えると難易度が⾼くなる。 ➤ ⾊分け、配置を⼯夫する。 26

 【例 1】XOR回路 ➤ 構成するコンポーネントが増えてくる例 ➤ XORゲート ➤ ➤ ➤ 2つの⼊⼒が異なる場合に1、それ以外は0 を出⼒する。 ⾔い換えると、不⼀致回路。 XOR Gateステージ ➤ XORゲートの内部を作る。 A B XOR(A,B) 0 0 0 0 1 1 1 0 1 1 1 0 XORの真理値表 27

 D A G C E B F XOR回路の回答例 A B C (=NOT(B)) D (=AND(A,C)) E (=NOT(A)) F (=AND(E,B)) G (=OR(D,F)) 0 0 1 0 1 0 0 0 1 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 0 上記回路の真理値表 28

 【例 1】XOR回路 ➤ 確かに与えられた回路はXORゲートと同じ真理値表になった。 ➤ ➤ これは落ち着いてやれば誰でもできる。 この⼀⾒複雑な回路を⾃⼒で組めるか？ ➤ ➤ 続き ひらめきや経験・知識が必要。 内部回路を覚えるものではなく、その場かつ⾃⼒で解ければよい。 ➤ ひらめき不要の数学的アプローチ 29

 ひらめき不要の数学的アプローチ A B Y (=XOR(A,B)) 0 0 0 0 1 1 1 0 1 1 1 0 XORの真理値表 論理式 論理式から得られた回路（別解） 30

 【例I 2】3 BIT DECODER回路 ➤ ワイヤーが増えた例 ➤ ポイントは本数をわざと減らした状況で⼀部 の機能を満たしてから、それを拡張する。 ➤ 3 Bit Decoder回路ステージ ➤ 2進コードが与えられると、対応する出⼒ 端⼦のみONにする。 ➤ ⼊⼒が3ビット（3本線） ➤ 出⼒が8ビット（8本線） 31

 正解の回路 ➤ いきなりこの回路を解くのは難しい。 32

 ワイヤー数を減らした回路からスタートする ➤ ⼊⼒のワイヤー数を減らす ➤ ➤ 1 Bit Decoder 1 Bit Decoderが完成したら ➤ ⇒2 Bit Decoder⇒3 Bit Decoder 1 Bit Decoderの回路 2 Bit Decoderの回路 33

 Turing Completeで2 Bit Decoderを作る ➤ ワイヤーの⾊を⼯夫して、組み合わせの規則性を⾒い出す。 34

 3 Bit Decoderに拡張するために並べる ➤ 同じ回路を並べる。 ➤ 3⼊⼒型のANDコンポーネントに置き換える。 ➤ つながっていない⼊⼒ピンをつなげる。 3 Bit Decoderが完成した 35

 ミジンコが好きなステージ ➤ その1 Logic Engineステージ ➤ OR/NAND/NOR/ANDの演算装置を作 る。 ➤ これまで作り上げてきた回路を並べる。 ➤ シンプルながらも、成⾧を実感できるス テージ。 36

 サンドボックスで左シフト・右シフトを追加した 37

 ミジンコが好きなステージ ➤ その2 Opcodesステージ ➤ ADD/SUB/AND/OR/NOT/XORというオペ コードを解釈する回路を組み込む。 ➤ LEGアーキテクチャーをベースにする。 ➤ ➤ Wire Spaghettiステージの回路 ➤ 6つのレジスター ➤ 4バイト命令を解釈 ゲットしたEqualコンポーネントを活⽤すると、 デコーダーが不要になり、すっきりする。 38

 Wire Spaghettiステージの回路 39

 Opcodesステージの回路 40

 ⻤⾨となるステージ ➤ その1 Little Boxステージ ➤ 4バイトメモリー（2⾏2列のメモリー セル）を作る。 41

 42

 ⻤⾨となるステージ ➤ ➤ その2 The Mazeステージ ➤ ロボットを迷路から脱出させる。 ➤ 作成したCPUから数値を出⼒すること で、ロボットを制御できる。 左⼿法を実装する。 ➤ 40⾏程度のプログラム。 迷路の例（テストパターン1） 43

 44

 注⽬すべきポイント その1 ➤ ワイヤーの本数に注⽬する･･･ビット数に対応。 ➤ 対称性、組み合わせパターンを意識する･･･同じような回路や配線が並ぶことがよくあ る。 ➤ ⼊出⼒が最優先･･･いきなり内部の構造を⾒ない。回路の⼊出⼒が⼀番重要。 ➤ 問題⽂をよく読む･･･思い込みを避ける。ヒントがあるかも。 45

 注⽬すべきポイント ➤ その2 ⼊⼿したコンポーネントの活⽤を検討する･･･ステップアップ形式なので⼊⼿したコ ンポーネントがヒント。 ➤ 特に、Switchコンポーネント、マルチプレクサーが活躍する。 ➤ 迷ったらSwitchコンポーネント。 46

 Switchコンポーネント ➤ 1 Bit Switchコンポーネント ➤ ➤ C=0なら「無限⼤の抵抗値」 ➤ ➤ 実質的にワイヤーが切断されている状況 C＝1ならパスさせる ➤ ➤ 実質的に「スリーステートバッファー」 と等価 A=Z ⽔道管の仕切り弁のイメージ ステーステートバッファーの真理値表 47

 SwitchコンポーネントでXOR回路を実現する 1 Bit Switchコンポーネント 48

 セレクターを作れる ➤ セレクター ➤ ➤ ⼊⼒セレクターと出⼒セレクターがある。 ⼊⼒セレクター ➤ ➤ ⽔道管が合流している状況。⼊⼒のどちらを通すか は切り替え弁がある。 ⼊⼒セレクター ⼊⼒A,Bは何ビットであってもよい。 49

 セレクターの構成法 ➤ ➤ その1 ① 2つのスリーステートバッファーを並列に並べる。 ② セレクターの出⼒は1本なので、 スリーステートバッファーの出⼒を 合流して1本化する。 50

 セレクターの構成法 ➤ ➤ 0 ③ 2つのスリーステートバッファの⼊⼒はそのまま ➤ ➤ その2 2本の⽔道管。セレクターの⼊⼒2本と⼀致。 0 1 ④ 問題は仕切り弁の操作。 ➤ 本来セレクターの切り替え弁は1ビットしかない。 ➤ 分岐して、⽚⽅だけNOTを通す。 1 ➤ これでどちらか⼀⽅だけがONになる。 ➤ つまり、どちらかの仕切り弁は閉じて、もう⽚⽅は必ず開く。 0 1 これでセレクターが完成。 51

 Switchコンポーネントの活⽤例 その1 Input Selector回路（2-8セレクター） 52

 Switchコンポーネントの活⽤例 その2 RAMの組み込み 53

 Switchコンポーネントの活⽤例 その3 Registerコンポーネント DECコンポーネント Immediate Values回路の⼀部 54

 注⽬すべきポイント その3 ➤ どうしても回路がわからなければ、愚直に数学的アプローチで解く。 ➤ ソフトウェア的なアプローチ以外もある。 55

 Robot Raceステージ ➤ Robot Raceステージ ➤ ゴール･･･CPUからロボットを操作して、 レースに勝利させる（ゴールに到達させ る）。 ➤ 0～3を出⼒することで、右・下・左・上と 操作できる。 ロボットレースのコース 56

 Robot Raceステージを愚直に解く ➤ 今回はコース固定･･･テストは1パターン ➤ ロボットを制御するアルゴリズムを実装する のではなく、 ➤ ➤ 1マスずつの動きをプログラム化すればよ い。 プログラムは251バイト ➤ 7⾏⽬以降、1⾏4バイト ➤ Programコンポーネントのメモリー容量ぎ りぎり。 プログラムの⼀部 57

 58

 Robot Raceステージを素朴に解く ➤ 迷路を解くアルゴリズム ➤ ➤ 1直線の迷路なので、もったいない。 コースの規則性に注⽬ ➤ ➤ 別解 規則性があれば処理を共通化できそう。 実装プログラムは192バイト 59

 Robot Raceステージをエレガントに解く ➤ トラックの経路の特徴を⾒抜く ➤ ヒルベルト曲線 別解2 ➤ フラクタル図形の1つ。 ➤ 1本の線で全部のブロックを通るようにして、空間を覆い尽くす曲線の1つ。 60

 実績「FastBot」を解除するには ➤ 実績「FastBot」 ➤ 64バイト以下のコードでRobot Raceステージをクリアする。 ➤ 再帰的なアプローチの実装コードだと100バイト未満だが、実績解除までには⾄らな い。 ➤ 原点に戻る ➤ ➤ コースは固定。 ➤ ロボットの制御は0～3を出⼒するだけ。 ➤ プログラムで数値を出⼒させるのではなく、回路的に出⼒させればよい。 コードのサイズはゼロ ➤ 実績解除できるはず 61

 62

 63

 Turing Completeをクリアしたら ➤ ⾃作CPUという実績を解除できて満⾜感を得られた。 ➤ Turing Completeを極める。やりこみ要素がある。 ➤ すべての実績解除 ➤ サンドボックスでオリジナルCPUやリアルCPUを作成する。 ➤ CPU本の積読を解消する。 ➤ 別のCPU系のゲームに挑戦する。 ➤ ➤ NandGame ➤ Virtual Circuit Board 別アプローチで実際にCPUを作ってみる。 ➤ ➤ FPGA評価ボード、ICを集めて作るなど ⾃作CPUには満⾜したものとして、まったく別のジャンルの何かに挑戦する。 64

 NandGame ➤ 同種のゲーム。 ➤ ブラウザーで操作可。無料。 ➤ ➤ https://nandgame.com ⾒た⽬が独特で、慣れないと⾒にくい。 NandGameのステージ構成 65

• https://nandgame.com

 Turing Completeによるカウンター回路 NandGameによるカウンター回路 66

 Visual Circuit Board（VCB） ➤ ペイントソフト的UIを持ったシミュレーター。 ➤ Steamで1.5k ➤ 現状サンドボックスのみであり、⼈を選ぶ。 67

 68

 参考になる（かもしれない） 書籍の紹介 69

 参考図書の探し⽅ ➤ 最近の本であれば、「⾃作CPU」「コンピュータアーキテクチャー」と銘打った本 ➤ 古い本であれば、ワンボードマイコンやホビーマイコンの⼿作り本 ➤ デジタル回路の本 70

 ちょっと古いマイコン本 『はじめてつくる デジタル回路』 『古典電脳物語』 71

 超古い本 その1 『マイコン⼿づくり塾』（昭和５６年） 72

 超古い本 その2 『100万⼈のマイクロコンピュータ』 （昭和52年） 73

 定番本 『CODE』 『CPUの創りかた』 74

 『解析魔法少女美咲ちゃん マジカル・オープン！』 75

 最近の本 その1 『作ろう！CPU』 『組み⽴てながら理解する コンピュータの仕組み』 76

 最近の本 その2 『トランジスタ技術 2020年５⽉号』 77

 【おまけ】 直近の予定 78

 直近の活動・その1 技術書典15 オフラインマーケット参加 ➤ 11⽉12⽇ ➤ 池袋サンシャインシティ ➤ 展⽰ホールD ➤ サークル「ミライ・ハッキング・ラボ」 ➤ サークル配置番号は「く13」 技術書典14の様⼦ 79

 直近の活動・その2 「名著百選フェア2023」 ➤ 11⽉12⽇～12⽉31⽇ ➤ ブックファースト新宿店 ➤ 「私が今年、出会った⼀冊」と題し て、推薦した「名著」を⼀堂に集め 紹介するフェア。 ➤ IT技術書のフェアではなく、全ジャ ンルのフェア。 ➤ 参加する著述家は250名程度。 ➤ フェア対象本の購⼊者先着1,000名様 に、全推薦書とおすすめコメントを 掲載した特製冊⼦を進呈。 80

 直近の活動・その3 ➤ ➤ ➤ ➤ 『ハッキング・ラボのつくりかた 2024年2⽉中旬〜下旬予定 現在初校完。11⽉に著者校正2、12⽉に念 校。 5⽉ ➤ ⼤幅パワーアップ ➤ 1,200ページ超 仕事 完全版の執筆 6⽉ 執筆に5ヶ⽉。 前作の「よかった点を増強」＆「課題点を 修正」。 完全版』 晴読⾬読 7⽉ 8⽉ Turing Complete 9⽉ 仕事 初校ゲラチェック 81

 82

 ご清聴 ありがとうございました 83