VHDLで文字列リストを作成する: ベスト・プラクティスと実装例

VHDLにおけるテキスト文字列は、一般的に固定長の文字配列に限定されます。これはハードウェアを記述する言語として当然のことで、可変長文字列には動的メモリが必要になるためです。

文字列の配列を定義するには、格納したい最大文字列数分の領域をコンパイル時に確保する必要があります。さらに悪いことに、文字列の最大長を決めて、すべての要素をその文字数にパディングしなければなりません。以下のコードは、そのような構造の使用例です。

 type arr_type is array (0 to 3) of string(1 to 10); signal arr : arr_type; begin arr(0) <= "Amsterdam "; arr(1) <= "Bangkok "; arr(2) <= "Copenhagen"; arr(3) <= "Damascus "; 

ハードウェアの観点からは理にかなっていますが、VHDLテストベンチで文字列配列を使うのは煩雑になります。そこで、動的な文字列リスト・パッケージを作成することにしました。この記事で説明します。

完全なコードは以下のフォームからダウンロードできます。

Pythonのリスト・クラス

動的なVHDLリストを、よく知られたリスト実装をモデルに作成します。このVHDL文字列リストは、Pythonの組み込みリスト・クラスの振る舞いを模倣します。Pythonリストのappend()、insert()、pop()メソッドを採用します。

まず、インタラクティブなPythonシェルで実験してみましょう。

リストを宣言し、4つの文字列を追加します。

 IPython 7.19.0 -- An enhanced Interactive Python. Type '?' for help. In [1]: l = [] In [2]: l.append("Amsterdam") In [3]: l.append("Bangkok") In [4]: l.append("Copenhagen") In [5]: l.append("Damascus") 

append()メソッドは単純で、オブジェクトをリストの末尾に追加します。

pop()メソッドで確認できます。これは要素を削除して呼び出し元に返します。引数で取得する要素の位置を指定します。インデックス0から順にポップしてリストが空になるまで繰り返すと、昇順で内容が取得できます:

 In [6]: for _ in range(len(l)): print(l.pop(0)) Amsterdam Bangkok Copenhagen Damascus 

リストを再び埋めます。今度はinsert()メソッドを使って、順不同で要素を追加:

 In [7]: l.insert(0, "Bangkok") In [8]: l.insert(1, "Copenhagen") In [9]: l.insert(0, "Amsterdam") In [10]: l.insert(3, "Damascus") 

insert()関数では、新しいアイテムを挿入するインデックスを指定できます。上記の例では、最初の例と同じリストが作成されました。配列のように走査して確認:

 In [11]: for i in range(len(l)): print(l[i]) Amsterdam Bangkok Copenhagen Damascus 

Pythonのブラケット[]演算子はアイテムを削除せず、リストを配列のように振る舞わせます。ブラケット内の数値でインデックスされたスロットの内容が取得できます。

今度はリストの末尾からポップして空にします。Pythonリストの特徴として、負のインデックスで末尾から数えられます。これはブラケット演算子、insert()、pop()メソッドで機能します。

インデックス-1でポップすると、常にリストの最後の要素が取得されます。これをForループに入れると、リストが逆順で空になります:

 In [12]: for _ in range(len(l)): print(l.pop(-1)) Damascus Copenhagen Bangkok Amsterdam 

負のインデックスで挿入も可能です。以下の例の最後の行では、「Copenhagen」をインデックス-1に挿入しています:

 In [13]: l.append("Amsterdam") In [14]: l.append("Bangkok") In [15]: l.append("Damascus") In [16]: l.insert(-1, "Copenhagen") # 最後から2番目の位置に挿入 

走査すると、「Copenhagen」が最後から2番目の要素になっていることがわかります:

 In [17]: for i in range(len(l)): print(l[i]) Amsterdam Bangkok Copenhagen Damascus 

ここが核心部分ですが(理にかなっています):

インデックス-1に挿入すると新しいアイテムは最後から2番目になるが、-1からポップすると最後のアイテムが取得されます。

これは-1が現在リストにある最後の要素の位置を指すためです。ポップ時は最後の要素を要求しています。しかし挿入時は、現在リストにある最後の要素の位置に新しいアイテムを挿入するよう要求しているため、新しいアイテムが最終要素を1スロット押し出すことになります。

インデックス-1をポップすると「Damascus」が返され、「Copenhagen」ではないことで確認できます:

 In [18]: l.pop(-1) # 最後の位置からポップ Out[18]: 'Damascus' 

リストには3要素が残っています:

 In [19]: for i in range(len(l)): print(l[i]) Amsterdam Bangkok Copenhagen 

リストの長さは以下のように取得できます:

 In [20]: len(l) Out[20]: 3 

clear()を呼ぶとリストを空にできます:

 In [21]: l.clear() In [22]: len(l) Out[22]: 0 

ご覧の通り、Pythonリストは多機能で多くのプログラマーに理解されています。そのため、この成功の公式をベースにVHDLリストを実装します。

文字列リストVHDLサブプログラムのプロトタイプ

文字列リストをメンバ・メソッドを持つオブジェクトのように扱うには、保護型として宣言する必要があります。そして、同じ名前string_listのパッケージに配置します。

以下のコードは、保護型の「パブリック」部分であるサブプログラムのプロトタイプを示しています。

 package string_list is type string_list is protected procedure append(str : string); procedure insert(index : integer; str : string); impure function get(index : integer) return string; procedure delete(index : integer); procedure clear; impure function length return integer; end protected; end package; 

append()、insert()、clear()プロシージャはPythonの対応するメソッドと同一ですが、pop()関数を直接VHDLに移植することはできません。問題は、動的オブジェクトを保護型から簡単に渡せないことです。

この制約を克服するため、pop()機能をget()とdelete()の2つのサブプログラムに分割しました。これにより、まず配列のように要素にインデックスでアクセスし、不要になったら削除できます。例えば、シミュレーター・コンソールに文字列を出力した後などです。

length()不純関数は、Pythonの組み込みlen()関数のように振る舞います。リスト内の文字列数を返します。

文字列リストVHDLの実装

保護型は宣言部と本体の2つのセクションで構成されます。宣言部はユーザーから見えますが、本体にはサブプログラムの実装とプライベート変数が含まれます。それでは、文字列リストの内部動作を明らかにしましょう。

以下のフォームにメールアドレスを入力して、完全なコードとModelSimプロジェクトを受け取ってください！

内部データ構造として単方向連結リストを使用します。

関連記事: VHDLで連結リストを作成する方法

以下のすべてのコードは保護型の本体にあるため、これらの構造はパッケージの外部から直接アクセスできません。すべての通信は、前セクションで説明した宣言領域のサブプログラムを通じて行う必要があります。

データ格納型と変数

以下のコードからわかるように、まずアクセス型、つまり動的メモリ上の文字列へのVHDLポインタを宣言します。動的メモリと言いましたが、これはFPGA上のDRAMではありません。このコードは合成不可能だからです。文字列リストは純粋にシミュレーション用コンポーネントであり、シミュレーションを実行しているコンピューターの動的メモリを使用します。

 type str_ptr is access string; type item; type item_ptr is access item; type item is record str : str_ptr; next_item : item_ptr; end record; 

str_ptrの後、itemを不完全型として宣言します。次の行でitem_ptrを作成する際にitemを参照するため、このようにする必要があります。

最後にitem型の完全な宣言を行います。文字列ポインタと次の要素へのポインタを含むレコードです。item->item_ptr->itemという型の循環依存があり、最初に不完全なitem型を宣言することでコンパイル・エラーを回避しています。

保護型には以下の2つの変数が含まれます: rootとlength_i。rootが指すアイテムがリストの最初の要素、配列インデックス0になります。length_i変数は常にリスト内の文字列数を反映します。

 variable root : item_ptr; variable length_i : integer := 0; 

Appendプロシージャ

以下のappend()プロシージャは、リストの最後の位置に文字列を挿入する簡易表記です。

 procedure append(str : string) is begin insert(length_i, str); end procedure; 

Pythonの例で説明したように、インデックス-1を使って最後から2番目の位置に挿入するのは簡単です: insert(-1, str)。しかし、最後の位置に挿入するには、引数としてリストの長さをインデックスに指定する必要があります。これがPythonリストに専用のappend()メソッドがある理由であり、私たちも同じように実装します。

Insertプロシージャ

以下のinsertプロシージャは4ステップで動作します。

まず、VHDLのnewキーワードを使って動的アイテム・オブジェクトを作成します。最初にリスト・アイテム・オブジェクトを作成し、それに格納する動的文字列オブジェクトを作成します。

 procedure insert(index : integer; str : string) is variable new_item : item_ptr; variable node : item_ptr; variable index_v : integer; begin -- 新しいオブジェクトを作成 new_item := new item; new_item.str := new string'(str); -- インデックスをリストの範囲に制限 if index >= length_i then index_v := length_i; elsif index <= -length_i then index_v := 0; else index_v := index mod length_i; end if; if index_v = 0 then -- 位置0に挿入する場合、新しいオブジェクトがrootになる new_item.next_item := root; root := new_item; else -- 挿入位置の後ろのノードを探す node := root; for i in 2 to index_v loop node := node.next_item; end loop; -- 新しいアイテムを挿入 new_item.next_item := node.next_item; node.next_item := new_item; end if; length_i := length_i + 1; end procedure; 

ステップ2は、インデックス引数をリストの範囲に適合するインデックスに変換することです。Pythonのlist.insert()実装は範囲外インデックスを許容しますが、私たちのVHDLリストも同様に許容します。ユーザーが範囲外の高すぎる/低すぎるインデックスを参照した場合、最高インデックスまたは要素0にデフォルトします。また、モジュロ演算子を使って、範囲内の負のインデックスを正の配列位置に変換します。

ステップ3では、挿入位置の後ろのノードを見つけるためにリストを走査します。連結リストでは常に、ルートへの挿入という特殊ケースを明示的に扱う必要があります。

ステップ4、最後のステップでは、length_i変数をインクリメントして簿記を最新に保ちます。

内部get_index関数とget_node関数

VHDLのオブジェクト渡しの制約により、pop()をget()とdelete()の2つのサブプログラムに分割することにしました。最初の関数でアイテムを取得し、2番目のプロシージャでリストから削除します。

しかし、インデックスまたはオブジェクトを検索するアルゴリズムはget()とdelete()で同一なので、2つのプライベート関数get_index()とget_node()として別途実装できます。

insert()とは異なり、Pythonのpop()関数は範囲外インデックスを許容せず、私たちのget_index()関数も同様です。ユーザー・エラーを防ぐため、要求されたインデックスが範囲外の場合はアサーション失敗を発生させます:

 impure function get_index(index : integer) return integer is begin assert index >= -length_i and index < length_i report "get index out of list range" severity failure; return index mod length_i; end function; 

以下のget_node()関数は、さらに一歩進んで指定インデックスの実際のオブジェクトを見つけます。get_index()を使って正しいノードを検索し、itemオブジェクトへのポインタを返します。

 impure function get_node(index : integer) return item_ptr is variable node : item_ptr; begin node := root; for i in 1 to get_index(index) loop node := node.next_item; end loop; return node; end function; 

Get関数

プライベートなget_node()関数のおかげで、パブリックなget()関数は非常にシンプルになります。正しいノードを取得し、文字列の内容をアンパックして呼び出し元に返すワンライナーです。

 impure function get(index : integer) return string is begin return get_node(index).str.all; end function; 

Deleteプロシージャ

delete()プロシージャもget_index()とget_node()を使用してアルゴリズムを簡略化します。まずget_index()で削除対象オブジェクトのインデックスを求め、以下のindex_c定数宣言で示すようにします。

 procedure delete(index : integer) is constant index_c : integer := get_index(index); variable node : item_ptr; variable parent_node : item_ptr; begin if index_c = 0 then node := root; root := root.next_item; else parent_node := get_node(index_c - 1); node := parent_node.next_item; parent_node.next_item := node.next_item; end if; deallocate(node.str); deallocate(node); length_i := length_i - 1; end procedure; 

次に、ノードをリストから切り離します。ルート・オブジェクトの場合は、次のアイテムをルートに設定。それ以外の場合、get_node()で親を見つけ、リストを再リンクして対象アイテムを切り離します。

最後に、VHDLキーワードdeallocateを呼んでメモリを解放し、length_i簿記変数を更新します。

Clearプロシージャ

すべてのアイテムを削除するclear()プロシージャは、Whileループでリストを走査し、要素がなくなるまで各要素でdelete()を呼びます。

 procedure clear is begin while length_i > 0 loop delete(0); end loop; end procedure; 

Length関数

良いプログラミング慣習に従い、length_i変数への直接アクセスを許す代わりにゲッター関数を提供します。

 impure function length return integer is begin return length_i; end function; 

ユーザーにとっては違いは気づかれません。パラメータなしの関数呼び出しには括弧が不要だからです(my_list.length)。しかし、ユーザーは内部簿記変数を変更できず、これが誤用を防ぐセーフガードになります。

テストベンチでの文字列リストの使用

リスト実装が完成したので、テストベンチで実行してみましょう。まず、パッケージから保護型をインポートします。以下のコードの1行目に示す通りです。

 use work.string_list.string_list; entity string_list_tb is end string_list_tb; architecture sim of string_list_tb is shared variable l : string_list; ... 

保護型はVHDLのクラスのような構造で、string_list型の共有変数を宣言することでオブジェクトを作成できます。上記の最後の行に示す通りです。Pythonの例で使った'l'と同じように、「リスト」を意味する'l'と名付けます。

これで、ソフトウェア的なアプローチでリストのデータにアクセスできます。以下のテストベンチ・プロセスに示す通り、共有変数にドット記法でパブリック・サブプログラムを参照できます(l.append("Amsterdam"))。

 begin SEQUENCER_PROC : process begin print("* Append four strings"); print(" l.append(Amsterdam)"); l.append("Amsterdam"); print(" l.append(Bangkok)"); l.append("Bangkok"); print(" l.append(Copenhagen)"); l.append("Copenhagen"); print(" l.append(Damascus)"); l.append("Damascus"); ... 

記事の長さを抑えるため完全なテストベンチと実行スクリプトは省略しましたが、以下のフォームにメールアドレスを入力すれば入手できます。完全なVHDLコードとModelSimプロジェクトを含むZIPファイルが数分以内にメールで届きます。

テストベンチの実行

上記のフォームからサンプル・プロジェクトをダウンロードした場合、以下の出力を再現できるはずです。正確な手順はZIPファイル内の「How to run.txt」を参照してください。

これは手動チェック用テストベンチで、テスト・ケースを冒頭のPython例にできるだけ近づけています。Pythonのpop()メソッドの代わりに、VHDLリストのget()関数に続けてdelete()を呼びます。これと同じことができます。

以下のModelSimコンソールへの出力からわかる通り、VHDLリストはPythonの対応物と同様に振る舞います。

 # * Append four strings # l.append(Amsterdam) # l.append(Bangkok) # l.append(Copenhagen) # l.append(Damascus) # * Pop all strings from the beginning of the list # l.get(0): Amsterdam # l.get(1): Bangkok # l.get(2): Copenhagen # l.get(3): Damascus # * Insert four strings in shuffled order # l.insert(0, Bangkok) # l.insert(1, Copenhagen) # l.insert(0, Amsterdam) # l.insert(3, Damascus) # * Traverse the list like an array # l.get(0): Amsterdam # l.get(1): Bangkok # l.get(2): Copenhagen # l.get(3): Damascus # * Pop all strings from the end of the list # l.get(0): Damascus # l.get(1): Copenhagen # l.get(2): Bangkok # l.get(3): Amsterdam # * Append and insert at the second last position # l.append(Amsterdam) # l.append(Bangkok) # l.append(Damascus) # l.insert(-1, Copenhagen) # * Pop from the last position # l.get(-1): Damascus # * Traverse the list like an array # l.get(0): Amsterdam # l.get(1): Bangkok # l.get(2): Copenhagen # * Check the list length # l.length: 3 # * Clear the list # * Check the list length # l.length: 0 # * Done 

まとめ

VHDLの高級プログラミング機能は過小評価されていると思います。RTL設計には合成不可能なので役立ちませんが、検証目的には有益です。

実装は複雑でも、エンド・ユーザー(保護型を使用するテストベンチ作成者)にとってはシンプルになります。保護型がすべての複雑さを隠蔽するからです。

保護型を使用するには3行で済みます: パッケージをインポート、共有変数を宣言、テストベンチ・プロセスでサブプログラムを呼び出す。これはVHDLコンポーネントをインスタンス化するよりもシンプルです。

関連記事: VHDLで連結リストを作成する方法

記事下のコメント欄で感想をお聞かせください！