Kageki (TD4互換機) でpopcnt (1のビットを数える)

TD4の命令を実行できる自作CPU「Kageki」で popcnt (1のビットを数える) をしてみた。

未定義の命令の使用

今回は、通常の命令だけではプログラムROMの容量が足りなそうであったため、未定義ではあるものの実装上動作する命令を使用することにした。
それは、00100100 である。
この命令の上位ニブルは IN A 命令と同じであるが、下位ニブルが IN A の仕様に反して 0000 になっていない。

Kageki、および本家TD4では、この下位ニブルは加算器の入力の一方に直結されている。
また、加算器のキャリー出力も、無条件でフラグとして保存されるようになっている。
したがって、この命令は IN A 命令に続いて ADD A, 0100 命令を実行したかのような結果になる。
これにより、普通に IN A 命令と ADD A, 0100 命令を書くより1ワード節約できる。

ただし、やはり未定義の命令なので、エミュレータによっては動かないことがある。
例えば、TD4 Emulator Web では 0100 の加算が行われず、通常の IN A 命令のようにふるまった。

仕様

入力ポートから4ビットの値を読み込み、そのうち「1」のビットの数を出力ポートに出力する。

プログラム

位置 機械語   アセンブリ言語
---------------------------------------------------------
0    01110000        MOV B, 0000
1    00100100        DATAB 0b00100100 ; IN A; ADD A, 0100
2    11100100        JNC SKIP1
3    01010010        ADD B, 0010
4    00001000 SKIP1: ADD A, 1000
5    11100111        JNC SKIP2
6    01010001        ADD B, 0001
7    00000100 SKIP2: ADD A, 0100
8    11100111        JNC SKIP2
9    00001101        ADD A, 1101
A    11101100        JNC SKIP3
B    01010010        ADD B, 0010
C    00000010 SKIP3: ADD A, 0010
D    11101111        JNC SKIP4
E    01010001        ADD B, 0001
F    10010000 SKIP4: OUT B

解説

• 0番地 : Bレジスタを0に初期化する。 (この後、Bレジスタに「1」のビット数を格納する)
• 1番地～6番地 : 入力の上位2ビットを処理する。
  • 1番地 : Aレジスタに入力ポートの値を読み込み、上位2びっとに 01 を加算する (未定義の命令)
  • 2番地 : 上位2ビットが 11 であった場合、ここに 01 を加算するとキャリーが発生するので、ジャンプしない。上位ビットがそれ以外であった場合、キャリーは発生せず、ジャンプしてBレジスタへ2を加算する処理をスキップする。
  • 3番地 : (上位2ビットが 11 であった場合) Bレジスタに2を加算する。
  • 4番地 : Aレジスタの上位2ビットに 10 を加算する。入力の上位2ビットにより、以下の動作となる。
    • 入力が 00 → 1番地で 01 となっている → 加算結果は 11 となり、キャリーは発生しない
    • 入力が 01 → 1番地で 10 となっている → 加算結果は 00 となり、キャリーが発生する
    • 入力が 10 → 1番地で 11 となっている → 加算結果は 01 となり、キャリーが発生する
    • 入力が 11 → 1番地で 00 となっている → 加算結果は 10 となり、キャリーは発生しない
  • 5番地 : 4番地でキャリーが発生しない場合 (上位2ビットで立っているビットがちょうど1個でない場合) 6番地の加算をスキップする。
  • 6番地 : (上位2ビットで立っているビットがちょうど1個の場合) Bレジスタに1を加算する。
• 7番地～8番地 : Aレジスタの上位2ビットを 00 にする。
• 9番地～E番地 : 入力の下位2ビットを処理する。
  • 9番地～B番地 : 1番地～3番地と同様に、「1」のビットが2個かどうかの判定を行う。
    • 00 にした上位2ビットに 11 を加算し、下位2ビットからのキャリーが全体のキャリーになるようにする。
  • C番地～E番地 : 4番地～6番地と同様に、「1」のビットが1個かどうかの判定を行う。
    • 9番地～B番地の処理でキャリーが発生しなかった場合、Aレジスタの上位2ビットは 11 であり、下位2ビットからのキャリーが全体のキャリーになるようにする。
    • 9番地～B番地の処理でキャリーが発生した場合、Aレジスタの上位2ビットは 00 となるが、この場合どっちみちここでキャリーは発生しないはずなので問題無い。
• F番地 : 計算結果を出力する。

実行結果

入力ポートに Pmod SWT を、出力ポートに 1-Digit 7seg Board を接続して実行した。
グレイコードを用い、全パターンの入力を試した。