アルゴリズム説明

アルゴリズムの中心部分を説明します。一度に変換すると、bscによるデータサイズの推定がうまく行かなかったため、ステップに分解してデータタイプのヒントを与えています。ステップに分解しても結局組み合わせ回路が合成されるため、回路オーバヘッドはありません。

      Bit#(8) xa = a[15:8];

横方向アドレスであるxaは縦方向アドレス(上位8bit)をそのまま使用します。

      Int#(10) yax = 256 - signExtend(unpack(a[7:0]));

一方、縦方向アドレスyaは横方向アドレス(下位8bit)をunpackにより整数化し、符号拡張した上で256から引きます。

      Bit#(8) ya = truncate(pack(yax));

その後unpackによりビットベクターとし、最後にtruncateで8bitベクターに戻します。データタイプ変換関数はここに掲載されています。

      if (sel) return b;
      else if (sw) return {ya, xa};
      else return a; // normal state

最後にselがtrueならｂ(メモリダンプFSMによるアドレス)、falseでswがtrueならxとyの入れ替え&yの反転(90°回転)、falseならオリジナルのa(ゲームFSMによるアドレス)を選択します。

実行結果

図508.1に実行結果を示します。首を左に90度傾けた上で正しく実行できました。

変更後のソース

変更したMux.bsv:

typedef Bit#(16) Addr_t;

interface Mux_ifc;
   (* prefix="" *)
   method Addr_t outp(Bool sw, Bool sel, Addr_t a, Addr_t b);
endinterface

(* synthesize, always_ready = "outp", no_default_clock, no_default_reset *)
module mkMux(Mux_ifc);
    method Addr_t outp(Bool sw, Bool sel, Addr_t a, Addr_t b);
      Bit#(8) xa = a[15:8];
      Int#(10) yax = 256 - signExtend(unpack(a[7:0]));
      Bit#(8) ya = truncate(pack(yax));
      if (sel) return b;
      else if (sw) return {ya, xa};
      else return a; // normal state
   endmethod
endmodule

変更箇所はこのアドレスの縦横入れ替えと、VRAM初期値のデータの縦横入れ替えの2点となります。後者はプログラムでも可能ですが、csvに変換した上でexcelのコピーのオプションの行列の入れ替え機能で実施しました。

追記：改良版の記事はここ

前のブログ 次のブログ

画面の縦横の入れ替え

Landscapeのモニタを使用しているため、Space Invadersは正立していますが、本来から比べると縦方向に縮んでいます。これを修正するには画面の縦と横を入れ替えます。VRAMの読み出しアドレスのxとyを入れ替えれば良いはずです。

過去記事のVRAMのアドレス周りの図403.1を見ると、アドレスマルチプレクサが流用できそうです。これはFSMからのアドレスをメモリダンプ中にスイッチするものです。

元のMux.bsv:

typedef Bit#(16) Addr_t;

interface Mux_ifc;
   (* prefix="" *)
   method Addr_t outp(Bool sel, Addr_t a, Addr_t b);
endinterface

(* synthesize, always_ready = "outp", no_default_clock, no_default_reset *)
module mkMux(Mux_ifc);
   method Addr_t outp(Bool sel, Addr_t a, Addr_t b);
      if (sel) return b;
      else     return a;
   endmethod
endmodule

このソースにおいて、中心部分はセレクタであり、

      if (sel) return b;
      else     return a;

このようにselがtrueならｂ(メモリダンプFSMによるアドレス)、falseならa(ゲームFSMによるアドレス)を選択していました。

これに対し、図507.1のように新に1bitのスイッチを加え、スイッチがONのときにはゲームFSMによるアドレスの縦と横を入れ替えるように設計変更します。

具体的には通常時のアドレスa系のx座標アドレス(下位8bit)とy座標アドレス(上位8bit)を入れ替え、さらにy座標は上下反転します。上下反転は、256からアドレスを引くことで実現します。

$$ \begin{eqnarray} \left\{ \begin{array}{l} x&\Leftarrow&y \\ y&\Leftarrow&256 - x \end{array} \right. \end{eqnarray} $$

改良版の記事はここ

前のブログ 次のブログ

ブロック図

旧版(verilog版)のブロック構成と、BSVで再設計したブロック構成を示します。再設計の際にグルーロジックを取り込んだため、4個のモジュールが1個になりhandshake階層をなくすことができました。

前のブログ 次のブログ

OneStageソース

前稿で述べたルールの前後にインタフェース、レジスタ宣言、メソッド宣言を加えてソースが完成しました。

// OneStageのインタフェース定義
interface Fifo_ifc;
(* prefix="" *) 
   // GameFSMからの書き込み有効信号
   method Action if_write_enable((* port="wr_en" *)Bool wen);
(* prefix="rd" *)
   // 各SoundFSMからの読み取り有効信号 (0～3)
   method Action if_read_enable0(Bool en0);
(* prefix="rd" *)
   method Action if_read_enable1(Bool en1);
(* prefix="rd" *)
   method Action if_read_enable2(Bool en2);
(* prefix="rd" *)
   method Action if_read_enable3(Bool en3);
(* result="empty" *)
   // キューが空かどうかを返すメソッド
   method Bool if_empty();
endinterface

// OneStageの実装
(* synthesize, always_ready, always_enabled *)
module mkOneStage(Fifo_ifc);

     // 入力信号のレジスタ
   Reg#(Bool) in_wen <- mkReg(False);  // 書き込み有効
   Reg#(Bool) in_ren0 <- mkReg(False); // 読み取り有効 (SoundFSM0)
   Reg#(Bool) in_ren1 <- mkReg(False); // 読み取り有効 (SoundFSM1)
   Reg#(Bool) in_ren2 <- mkReg(False); // 読み取り有効 (SoundFSM2)
   Reg#(Bool) in_ren3 <- mkReg(False); // 読み取り有効 (SoundFSM3)
   // キューが空かどうかの状態
   Reg#(Bool) in_empty <- mkReg(True);

   // キューへの書き込みルール
   rule rule_write (in_wen && in_empty);
         in_empty <= False;  // キューを!emptyにする
   endrule

   // キューからの読み取りルール
   rule rule_read ((in_ren0 || in_ren1 || in_ren2 || in_ren3) && !in_empty);
         in_empty <= True;  // キューをemptyにする
   endrule

   // 各メソッドの実装
   method Action if_write_enable(Bool wen);
      in_wen <= wen;
   endmethod
   method Action if_read_enable0(Bool en0);
      in_ren0 <= en0;
   endmethod
   method Action if_read_enable1(Bool en1);
      in_ren1 <= en1;
   endmethod
   method Action if_read_enable2(Bool en2);
      in_ren2 <= en2;
   endmethod
   method Action if_read_enable3(Bool en3);
      in_ren3 <= en3;
   endmethod
   method Bool if_empty();
      return in_empty;  // キューが空かどうかを返す
   endmethod

endmodule: mkOneStage

前のブログ 次のブログ

OneStageの変更

OneStageとはGameFSMとSoundFSMのインタフェースを行うモジュールです。元々FIFOだったのですが、FIFOの段数だけサウンドがレコードされていき、遅延して演奏されるようになったので、リアルタイム性のため1段のFIFO(=One Stage FIFO)としました。

前回Verilogで設計したものを今回BSVに移植します。ロジック的には大したことのないモジュールでVerilogで書いても工数はあまり変わりません。

図504.1にステート遷移図を示します。1段のキューを模擬する動作であり、

• emptyかつwriteの場合は!empty (=full)に遷移します。
• !empty (=full)かつreadの場合はemptyに遷移します。

通常、GameFSMが書き込むことにより!emptyとなった場合は、演奏途中でもemptyを見ているため、SoundFSMはすぐに読み出します。すぐにreadを返すためまたemptyとなります。

例外は自機増加音で、プリエンプション禁止であるため、!emptyとなってもreadが返りません。従って演奏が終わるまで!emptyのままとなります。出力側はemptyを見ているため、この場合は出力が待たされ取りこぼしが防止されます。

BSVでの記述

これはステートマシンなので、以前に示したように、

• ステートベース設計
• シーケンスベース設計

の2通りの設計手法があります。自動FSMによるシーケンスベース設計も可能ですが、あまりにも簡単なステートマシンなので、ステート遷移のルールを直に記述します。ren信号はread enableの意味です。

図504.1をBSVのルール文で書くと

rule rule_write (in_wen && in_empty);
   in_empty <= False;
endrule
rule rule_read ((in_ren0 || in_ren1 || in_ren2 || in_ren3) && !in_empty);
   in_empty <= True;
endrule

となります。

• write_enable (in_wen)はキューへの書き込みのためのGameFSMからの出力です。
• read_enable (in_ren0～3)はキューからの引き取りのためのSoundFSMからの出力ですが、SoundFSMが4種類あるので、4つの信号となります。

別々のルールにおいて、同一資源であるin_emptyに書き込むのが若干気になります。スケジューリング時点でエラーが出るかもしれないと思いましたが、出ませんでした。これは、2つのルールがそれぞれemtpyと!emptyでガードされており、ルールに重なりが無いので、同一リソースへのライトハザードが起きないためでしょう。

前のブログ 次のブログ

「BSV (Bluespec SystemVerilog)を用いたサウンドFSMのシーケンスベースによる再設計」と題する記事をQiitaに投稿しました。

前回のBSVによる設計ではGameFSMとSoundFSMで敢えて異なる設計手法としましたが、今回はSoundFSMもシーケンスベース設計に変更しました。その理由は、ステートベース設計ではステート分解を人力で行うため、高級言語のメリットがあまり出ないためです。さらに、同じ機能をステートベース設計とシーケンスベース設計とで設計してみて、結果の違いを見たかったためです。

前のブログ 次のブログ

BSVソース

完成したBSVのソースを貼り付けます。1つのソースで4種のFSMを合成し分けているため、やや複雑になっています。

SoundFSM.bsv:

// ステートマシンライブラリのインポート
import StmtFSM::*;

// サウンドコードの定義
`define SOUND1_ON      1         // 自弾発射音_ON
`define SOUND2_ON      2         // 自機爆発音_ON
`define SOUND3_ON      3         // インベーダ爆発音_ON
`define SOUND4_ON      4         // インベーダ歩行音1_ON
`define SOUND5_ON      5         // インベーダ歩行音2_ON
`define SOUND6_ON      6         // インベーダ歩行音3_ON
`define SOUND7_ON      7         // インベーダ歩行音4_ON
`define SOUND8_ON      8         // UFO爆発音_ON
`define SOUND9_ON      9         // 自機増加音_ON
`define SOUND10_ON   10        // UFO飛行音_ON
`define SOUND10_OFF  11        // UFO飛行音_OFF
`define NULL                'h80        // 無音

// 各FSMが起動する条件を定義
`define COND_FSM0 !emptyf && (code == `SOUND1_ON || code == `SOUND2_ON || code == `SOUND9_ON)
`define COND_FSM1 !emptyf && (code == `SOUND3_ON)
`define COND_FSM2 !emptyf && (code == `SOUND4_ON || code == `SOUND5_ON || code == `SOUND6_ON || code == `SOUND7_ON)
`define COND_FSM3 !emptyf && (code == `SOUND8_ON || code == `SOUND10_ON || code == `SOUND10_OFF)

// 型定義
typedef UInt#(15) Addr_t;    // アドレス型
typedef UInt#(8) Data_t;      // データ型
typedef Bit#(4) Code_t;       // サウンドコード型

// インターフェース定義
interface FSM_ifc;
   method Action sound(Code_t code);      // サウンドコードを受け取る
   method Action rom_data(Data_t indata); // ROMデータを受け取る
   method Action sync(Bool lrclk);        // シンクロ信号を受け取る
   method Action empty(Bool flag);        // FIFOが空かどうかのフラグを受け取る
   method Addr_t rom_address();           // 現在のROMアドレスを返す
   method Data_t sdout();                 // 現在のサウンドデータを返す
   method Bool soundon();                 // サウンドがONかどうかを返す
   method Bool fifo_ren();                // FIFOから読み出し可能かどうかを返す
endinterface

// サウンドFSMの生成
 (* synthesize,always_ready,always_enabled *)
`ifdef FSM0
module mkSoundFSM0(FSM_ifc);
`elsif FSM1
module mkSoundFSM1(FSM_ifc);
`elsif FSM2
module mkSoundFSM2(FSM_ifc);
`elsif FSM3
module mkSoundFSM3(FSM_ifc);
`endif

// ワイヤとレジスタの宣言
Wire#(Code_t) code <- mkWire,    // サウンドコード用のワイヤ
              current <- mkRegU; // 現在のサウンドコード用のレジスタ
Wire#(Bool) lrclk <- mkWire;     // 左右クロック用のワイヤ
Reg#(Data_t) romdata <- mkRegU,  // ROMデータ用のレジスタ
             data <- mkRegU,     // データ一時保存用
             dout <- mkReg(`NULL); // 出力用データ
Reg#(UInt#(32)) workd <- mkRegU; // 作業用データ
Reg#(UInt#(15)) dcount <- mkRegU; // データカウント用
Reg#(Addr_t) worka <- mkRegU,    // 作業用アドレス
             romaddr <- mkRegU,  // ROMアドレス用
             addr <- mkRegU;     // 一時アドレス用
Reg#(UInt#(8)) ii <- mkReg(0);   // ループカウンタ
Reg#(Bool) son <- mkReg(False),  // サウンドONフラグ
           sonEarly <- mkReg(False), // 早期サウンドONフラグ
           ren <- mkReg(False),  // 読み取り許可フラグ
           emptyf <- mkReg(True); // 空フラグ
// FSM3専用のUFOフラグ
`ifdef FSM3
    Reg#(Bool) fUFO <- mkReg(False);
`endif

// サブ関数：メモリからデータを読み取る
   //   READ MEM
   //     input:  worka
   //     output: romdata;
   function Stmt readmem;
      return (seq
         addr <= worka;      // アドレスをセット
         noAction;               // アクションなし(データセットアップタイム)
         data <= romdata;   // データを読み取る
      endseq);
   endfunction

   // サブ関数：カウント値を読み取る
   //   READ COUNT
   //     input:  romaddr
   //     output: (romaddr,...,romaddr+3) => dcount;
   //             romaddr + 4 => romaddr;
   function Stmt readcount;
      return (seq
         workd <= 0;
         for (ii <= 0; ii <= 3; ii <= ii + 1) seq
            worka <= romaddr + extend(3-ii);
            readmem;             // メモリからデータを読み取る
            if (ii == 3) dcount <= truncate(workd<<8) | extend(romdata);
            else workd <= workd<<8 | extend(romdata);
         endseq
         romaddr <= romaddr + 4;  // アドレスを更新
      endseq);
   endfunction
      
   // メインのステートマシン
   Stmt main = seq
      while(True) seq
         // 初期化アクション
         action
            dout <= `NULL;
            sonEarly <= False;
            son <= False;
            ren <= False;
         endaction

 // 条件に応じて待機
`ifdef FSM0
         await(`COND_FSM0);
         action
            ren <= True;
            current <= code;
         endaction
`elsif FSM1
         await(`COND_FSM1);
         action
            ren <= True;
            current <= code;
         endaction
`elsif FSM2
         await(`COND_FSM2);
         action
            ren <= True;
            current <= code;
         endaction
`elsif FSM3
         await(`COND_FSM3 || fUFO);      // FSM3はUFOフラグも考慮
         if (`COND_FSM3) action
            fUFO <= (code == `SOUND10_ON);    // UFOフラグをセット
            ren <= True;
            current <= code;
         endaction else if (fUFO) action
            current <= `SOUND10_ON;      // UFOフラグがTrueならUFO音を継続
        endaction
`endif
   // FIFOが空でないことを確認
         await(emptyf);
         ren <= False;

    // UFO音のオフコマンド処理（FSM3専用）
`ifdef FSM3
         if (code == `SOUND10_OFF) continue;
`endif

    // LRクロックのエッジにシンクロ
         await(lrclk);
         await(!lrclk);
         delay(4);

    // サウンドコードに基づいてROMアドレスを設定
         action    
            case (current)
`ifdef FSM0
               `SOUND1_ON:  romaddr <=     0 + 16;
               `SOUND2_ON:  romaddr <=  3422 + 16;
               `SOUND9_ON:  romaddr <= 16150 + 16;
`elsif FSM1
               `SOUND3_ON:  romaddr <=     0 + 16;
`elsif FSM2
               `SOUND4_ON:  romaddr <=     0 + 16;
               `SOUND5_ON:  romaddr <=  1266 + 16;
               `SOUND6_ON:  romaddr <=  2836 + 16;
               `SOUND7_ON:  romaddr <=  4406 + 16;
`elsif FSM3
               `SOUND8_ON:  romaddr <=     0 + 16;
               `SOUND10_ON: romaddr <= 25968 + 16;
`endif
            endcase
         endaction

    // カウント値を読み取り、次のROMアドレスを計算
         readcount;
         romaddr <= romaddr + extend(dcount) + 4;
      
    // 再度カウント値を読み取り、ROMアドレスを調整
         readcount;
         romaddr <= romaddr - 1;

    // サウンドデータの再生
         while (!((dcount == 0) || 
`ifdef FSM0
            (`COND_FSM0 && current !=`SOUND9_ON))) seq
`elsif FSM1
            (`COND_FSM1)))seq
`elsif FSM2
            (`COND_FSM2))) seq
`elsif FSM3
            (`COND_FSM3))) seq
`endif
            if (sonEarly == False) seq
               readmem;           // データ読み出し(3 clock)
               action
                  sonEarly <= True;
                  son <= False;    // サウンドオフ
                  dout <= `NULL;   // データ無効
               endaction
            endseq else seq
               readmem;           // データ読み出し(3 clock)
               action
                  son <= True;     // サウンドオン
                  dout <= romdata; // データ出力
               endaction
            endseq

            delay(11);  // readmemが3クロック、その次のactionが1クロックで計4クロック。
                              // さらにdelay()後の終端処理の1クロックを加えて、whileループが16クロックに
                              // なるように11クロック遅延を挿入
            action
               romaddr <= romaddr + 1;
               worka <= romaddr + 1;
               dcount <= dcount - 1;
            endaction
         endseq

    // UFOフラグをリセット（FSM3専用）
`ifdef FSM3
         if ((code == `SOUND8_ON || code == `SOUND10_OFF) && !emptyf) fUFO <= False;
`endif
      endseq
   endseq;

  // 自動ステートマシン生成
   mkAutoFSM(main);
   
  // メソッド実装
   method Action sound(Code_t incode);
      code <= incode;
   endmethod
   method Action rom_data(Data_t indata);
      romdata <= indata;
   endmethod
   method Addr_t rom_address();
      return addr;
   endmethod
   method Data_t sdout();
      return dout;
   endmethod
   method Bool soundon();
      return son;
   endmethod
   method Action sync(Bool inlrclk);
      lrclk <= inlrclk;
   endmethod
   method Bool fifo_ren();
      return ren;
   endmethod
   method Action empty(Bool flag);
      emptyf <= flag;
   endmethod

`ifdef FSM0
endmodule: mkSoundFSM0
`elsif FSM1
endmodule: mkSoundFSM1
`elsif FSM2
endmodule: mkSoundFSM2
`elsif FSM3
endmodule: mkSoundFSM3
`endif

これをverilogに合成するには、FSM0であれば、

$ bsc -verilog -D FSM0 SoundFSM.bsv

のようにマクロ定義により行います。

前のブログ 次のブログ

サウンドデータ修正手順

ゲームサウンドの改良のため、サウンドROMの内容を修正します。サウンドROMの作成法は記載していなかったので、その備忘のためでもあります。以下に手順の大略を示します。

1. オリジナルサウンドを(http://www.classicgaming.cc/classics/space-invaders/sounds)で入手する。Player shootingとKilled Space Invaderのサウンドの表示が誤って入れ替わっているようです。
2. Windows上のサウンドツールである Audacityにより適宜音量を調整する。そのままだと歩行音とのバランスが悪く歩行音が聞こえにくいため、歩行音以外の音量を下げて平均化する。ただし後述のように、頻繁に鳴る音でなければ多少大き目でも良い。
3. waveを8bitに圧縮変換する。コマンドは

$ ffmpeg -i input.wav -ac 1 -ar 11025 -acodec pcm_u8 -fflags +bitexact -flags:v +bitexact -flags:a +bitexact output.wav

ここで、拡張子に.wavが必要。

1. サウンド毎のwaveバイナリが作成されたので、チャネル毎にwaveをcatでまとめ、ROMイメージのバイナリファイルを作成する。
   　Ch.0 --- Code 1, 2, 9
   　Ch.1 --- Code 3
   　Ch.2 --- Code 4, 5, 6, 7
   　Ch.3 --- Code 8, 10
   
2. wcによりエントリアドレスを調べておく。エントリアドレスは、直前のROM累積サイズ+16。
   
3. make_coe(以下)コマンドにより、バイナリからVivadoの読めるCOEファイルに変換する。

#! /bin/bash
export input=$1.bin
export output=$1.coe
echo 'memory_initialization_radix=16;' > $output
echo -n 'memory_initialization_vector=' >> $output
od -An -t x1 -v < $1.bin >> $output
echo ';' >> $output

修正点

• Code2 (自機爆発音) ---- 若干延長してフェードアウトエンベロープを加えた。

• Code1 (自機弾発射音), 3 (インベーダ爆発音), 9 (自機増加音) ---- 歩行音とのバランスで音量を下げすぎたため、音量を若干上げた。

頻繁に鳴る音、例えばインベーダ破壊音が大きめだとうるさく感じますが、まれな音、例えば自機増加音や自機破壊音は大きめでも問題ないことがわかりました。ゲームバランスと言われますが、音量にもバランスがあるようです。

修正後のサウンドROM構造

ROMのエントリポイントは上記のとおりStartアドレスから+16となります。

前のブログ 次のブログ

プチ音の再修正

ゲームFSMからのコマンドにより、サウンドはサウンドFSMで演奏されます。サウンドとサウンドの間は、サウンドが鳴り続けないように、一旦OFFにします。

シミュレーション波形を観測している際に、UFO飛行音は連続して再生されるので、一旦サウンドをOFFにするとプチ音がするのではないかと思い、ONを継続するように変更したところ、却ってプチ音がするようになりました。

確かにステートベース設計の旧版では一旦サウンドをOFFにしていたため、そのように戻したところ、プチ音は聞こえなくなりました。

修正前はson=False、dout=NULLのためにプチ音が鳴っていると思い、son=True, dout=前データを継続としましたが、却ってプチ音が鳴るようです。波形は再修正後です。

サウンドFSM(UFO音チャネル#3)のアルゴリズム

フラグのON/OFFアルゴリズムを表500.1にまとめました。

上記でプチ音対策で修正した箇所は表500.1の緑色表示の部分です。一旦son <= TrueとONを継続するように修正しましたが、OFFに戻しました。

まず、通常のサウンドNo.1及び3は以下のフローとなります。

1. GameFSMはempty == Trueの場合にコードを出力し、同時にOneStageFSMに対してwr_enを発行します。
2. OneStageFSMはempty = False(=Full)とします。
3. SoundFSMは正当コードかつempty == False (=Full)を待ち、入力されたらrd_en = TrueをOneStageFSMに返します。
4. OneStageFSMはempty = Trueとします。
5. GameFSMはempty == Trueを待ち、入力されたら終了です。
6. SoundFSMもempty == Trueを待ち、入力されたらrd_en = Falseとします。
7. SoundFSMはUFOオフコマンドならUFOフラグをOFFして終了します。
8. SoundFSMはUFOオフコマンドでなければフォーマットをデコードします。
9. SoundFSMはサウンドをカウント分演奏します。

次に、通常のサウンドで無い場合No.2は、UFOフラグがTrueの時であり、GameFSMのコードがキューに無くてもUFO飛行音を演奏し続けます。

1. GameFSMはなにもしません。
2. SoundFSMはUFOフラグ==Trueの場合には、実行しますがrd_en = Trueは返しません。これはキューに何もないためです。
3. SoundFSMは内部的にはUFO飛行音と扱います。
4. SoundFSMはフォーマットをデコードします。
5. SoundFSMはサウンドをカウント分演奏します。

前のブログ 次のブログ

サウンドFSM毎に固有のROMを持ちますが、ROMとアクセスアドレス、データの関係表です。各コードは3段のエントリとなっており、それぞれフォーマット格納アドレス、フォーマット長、データ格納アドレス、データ長、サウンド格納アドレス、サウンドデータの順となっています。

バスアクセスのシミュレーションエラーが出たため、まとめておこうと思い上記の表を作成しましたが、エラーの原因はROMの内容が古かったためでした。

前のブログ 次のブログ