VHDL で文字列のリストを作成する方法

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 の組み込みリスト クラスの動作を模倣します。 append() を採用します 、insert() 、および pop() Python リストのメソッド

私が言いたいことをお見せするために、すぐに飛び込んでインタラクティブな 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

OK、リストを補充しましょう。今回は、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

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

In [13]: l.append("Amsterdam")
In [14]: l.append("Bangkok")
In [15]: l.append("Damascus")
In [16]: l.insert(-1, "Copenhagen") # insert at the second last position

リストをトラバースすると、「Copenhagen」が最後から 2 番目の要素になっていることがわかります。

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

さて、ここからが核心です (しかし、それは理にかなっています)。

-1 に挿入すると、新しいアイテムは最後から 2 番目になりますが、-1 からポップすると、最後のアイテムになります。

-1 は現在リストにある最後の要素の位置を参照するため、これは理にかなっています。ポップするときは、最後の要素を求めています。しかし、挿入するときは、現在リストにある最後の要素の位置に新しい項目を挿入するように求めます。したがって、新しいアイテムは最後の要素を 1 スロット分置き換えます。

これは、「コペンハーゲン」ではなく「ダマスカス」を返す要素 -1 をポップすることで確認できます。

In [18]: l.pop(-1) # pop from the last position
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() pop() を移植することはできません。 VHDL に直接機能します。問題は、VHDL の保護された型から動的オブジェクトを簡単に渡すことができないことです。

この制限を克服するために、pop() を分割しました 機能を 2 つのサブプログラムに分割:get() そして delete() .これにより、配列のように最初に要素にインデックスを付け、必要がなくなったら削除できます。たとえば、文字列をシミュレータ コンソールに出力した後などです。

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_ptr->item の間には循環依存があります 、そして最初に不完全な item を宣言することによって と入力すると、コンパイル エラーが回避されます。

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

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

追加手順

append() 以下に示す手順は、リストの最後の位置に文字列を挿入するための簡略表記です。

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

Python の例で説明したように、インデックス -1:insert(-1, str) を使用して、最後から 2 番目の位置に簡単に挿入できます。 .ただし、最後の位置に挿入するには、インデックス引数としてリストの長さが必要です。これがおそらく、Python のリストに専用の append() がある理由です。

手順を挿入

以下に示す挿入手順は、4 つのステップで機能します。

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

procedure insert(index : integer; str : string) is
  variable new_item : item_ptr;
  variable node : item_ptr;
  variable index_v : integer;
begin

  -- Create the new object
  new_item := new item;
  new_item.str := new string'(str);

  -- Restrict the index to the list range
  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

    -- The new object becomes root when inserting at position 0
    new_item.next_item := root;
    root := new_item;

  else

    -- Find the node to insert after
    node := root;
    for i in 2 to index_v loop
      node := node.next_item;
    end loop;

    -- Insert the new item
    new_item.next_item := node.next_item;
    node.next_item := new_item;

  end if;

  length_i := length_i + 1;

end procedure;

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

ステップ 3 では、リストをたどって、後に挿入するノードを見つけます。いつものように、リンクされたリストでは、ルートに挿入する特定のケースを明示的に処理する必要があります.

最後の 4 番目のステップは、length_i をインクリメントすることです。 簿記が最新であることを確認するための変数。

内部 get_index および get_node 関数

VHDL のオブジェクト受け渡しの制限により、pop() を分割することにしました。 2 つのサブプログラムに分割:get() そして delete() .最初の関数はアイテムを取得し、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_node() のため 関数、パブリック get() 機能がかなりシンプルになります。これは、正しいノードを取得し、文字列の内容をアンパックして、呼び出し元に返すワンライナーです。

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

削除手順

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() delete() を呼び出して While ループを使用してリストをトラバースする手順 すべての要素がなくなるまで。

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

長さ関数

優れたプログラミング プラクティスに準拠するために、ユーザーが length_i に直接アクセスできるようにするのではなく、getter 関数を提供しています。

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

パラメータなしで関数を呼び出すのに括弧は必要ないため (my_list.length ）。しかし、ユーザーは内部簿記変数を変更することはできません。これは誤用に対する保護手段です。

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

リストの実装が完了したので、テストベンチで実行します。最初に、以下のコードの最初の行に示されているように、保護された型をパッケージからインポートする必要があります。

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.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 の例にできるだけ近づけました。 pop() の代わりに Python メソッド。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 でリンク リストを作成する方法

記事の下のコメント欄であなたの考えを教えてください!