ホーム >
家族のギャラリー >
ペントミノを解く >
第7章 ペントミノ専用ハードウェア >
7.3 PSPソフトウェア編
興味のある人もあまりいないと思いますが、PICという少し特殊？な組み込み用プロセッサを利用する上で少し工夫したところを紹介します。一般的なペントミノの解法には参考にならないと思います。
ソフトウェア作成は、MPLABというPICの開発環境についてくるアセンブラ(MPASM)を使います。無料で提供されているのがアマチュアには嬉しい。アセンブラでプログラミングするのは苦労することも多いですが、パズルを解くのと似たような楽しさがあります。とくに今回の8ビットPICは楽しむのに丁度良いサイズ。
1. スタック
アセンブラではC言語のようなautomatic変数は無いので変数は自分でスタックに積む。さらに今回のPICはCALL命令の戻り番地を積むスタックが8個しかないので、ペントミノ12ピース分を再帰呼び出しすることはできない。
そこで再帰呼び出しをCALLではなく、GOTOでジャンプし、戻り先も自分で管理する。そもそも呼び出し元が２箇所しかないので、どちらかに戻ればよいので楽（ひとつは処理の完了時だし）。
このスタックも少ないデータメモリを使用するが、一番大食いだったのがこのスタックのための領域。192バイトしかない領域の72バイトも使用。
2. ピース定義データ
ピースデータは12種のピースの回転・鏡像で63データ。データあたり4座標で計252バイトとなり、データメモリの192バイトよりも多い。
PICはデータメモリとプログラムメモリが別々になっており、プログラムコード内に定義したデータは配列としてアクセスすることができない。プログラムに埋めこんだピース定義データは、1つずつサブルーチンコールで取り出す。このためアクセスするのにそれなりのマシンサイクルを要する。
取り出し方は、配列の添え字にあたる値をプログラムカウンタに加算することで無理矢理ジャンプさせ、飛び先にリテラルをWレジスタ（作業レジスタ）に入れてリターンするという特殊な命令(RETLW)を書いておき、値を返す。PICではよく使われる方法だが、かなりトリッキー。
3. ピースデータの有効利用
２項のようにピース定義データ（相対座標）を取り出すのは、座標毎にサブルーチンコールで行うため処理時間がかかる。そこで、取り出したピースデータはとても貴重。一度取り出したら使い回せるようにする。と、いってもデータメモリが少ないので大量のデータは持てない。
ピースデータが必要なのは、以下の４つの処理フェーズとなる。これらの処理でピース定義からのサブルーチンコールによる取り出しは、１回のみで済ませる。C言語版では、毎回ピース定義配列を参照していた。
- （１）ピースが置けるか判定
- （２）ピースを盤面に置く
- （３）盤面からピースを剥がす
- （４）完成したときにピース形状を表示する
※Ｃ言語版では（４）の処理にピースの座標データは使わず、盤面に記録されたピース番号をもとにリストを出力している。まず、（１）のフェーズ時にピース定義を取り出し、４座標（１つのピースは５個のセルからできているので、基点の他に４座標ある）を変数に記憶。
そのデータを元に（１）の判定を行って、置ければそのデータを（２）ピースを盤面に置く処理に使う。さらに（３）（４）に備え、盤面に置いたピース各セルの座標５個（基点＋４箇所）を変数と共にスタックに積む。途中で配置できなくなり、戻ってきたときに盤面からピースを剥がす（３）ときに、このスタック上の座標データを使う。
最終的に12ピース全てが配置できたときに、スタック上には、配置したピースの順番に座標も積まれている。このスタック上の順番に、12ピースの位置、形状を順次表示することができる。実際には最初に置くXピースの表示が最初にならないように工夫している。
4. 盤面
今回、ピースを置く盤面は1つの座標に4ビット（2座標で1バイト）使い、番兵を含め1列6座標で4バイト（4ビット×6座標分＋番兵1バイト)とした。10列分で40バイトと、11列目の番兵に3バイトで計47バイト使用。
C言語版と同様に各座標には配置したピース番号を格納したが、今回ピースの配置の位置は３項で書いたように、スタックに積んだ情報で表示するので盤面にピース番号は不要。置いてあることが分かるように1座標につき1ビットの情報量で間に合う。4ビット使用した理由は、1ビット毎にフラグを立てたりチェックする処理は手間がかかり遅いので、処理時間を気にしたため。
この盤面デーブルの情報を1座標4ビットから1ビットに変更すれば、11バイトで済むので、メモリは36バイトの削減が可能。
5. 割り込みによる表示
PICが一所懸命頑張って解いている様子を表示したくて、演算中にプログレスバー、解数などを表示することにした。
ダイナミック表示（LEDを１列ずつ順次表示することで全体が点灯しているように表示）にPICのタイマ割り込みを使用。定期的に割り込みを発生させ1列分を表示する。タイマ割り込みは256マシンサイクル毎に発生するが、これでは短すぎるのでプリスケーラというカウンタで1/32する。
これで割り込み間隔は、クロック20MHz×1/(4*256*32)≒610Hz（1.638m秒）となる。
※ 4は１マシンサイクル必要なクロック数。マトリックスLEDは11列（赤10列＋緑1列）を使うので、610Hz/11列 = 約55Hzで1画面を表示できる。この位の速度で書き換えれば表示がチラチラすることもない。
割り込み処理では、表示バッファの内容をI/Oポートに出力し、表示列をシフトすることと、タクトスイッチの監視・長押しチェックを行う。スイッチの状態によるが30マシンサイクル程度必要。
通常処理に占める割り込み処理は、(30命令×610回) / 5,000,000命令（5MIPS）= 0.366% で、ごく僅か。全解を求める時間、約12分のうち、2.6秒程度しかLEDの表示には要していない。
これとは別に、プログレスバーのデータ作成や解数データの作成に多少時間がかかっている。
6. バンク切り替え
汎用データメモリは96バイトが2バンクに分かれているので、使うメモリに応じてバンク切り替えが必要。今回使ったPICには、バンク間での共有メモリがないので頻繁にバンク切り替えが必要な場面があり、ちょっと面倒。
基本的にペントミノを解く処理はバンク0を利用し、スタックと表示にバンク1を使用した。
割り込みが発生したときにバンクを意識するのが面倒で、当初はバンク1実行中は割り込みを禁止していた。しかし割り込み禁止フラグを立てるのを忘れ、幾度となく暴走。また、割り込み禁止フラグのON/OFFにも2マシンサイクル必要なので処理にも時間がかかる。そこで禁止にするのではなく、割り込み発生時にどのバンクを使っていたか記憶し、割り込み処理完了時に元のバンクに戻すように変更した。
結果的に処理速度にはそれほどの影響はなかったがスッキリしたコードになった。