C++ でルックアップテーブルを作成する

Jay Shaw 2023年10月12日
  1. C++ でルックアップテーブルを作成する
  2. C++ で 32 ビット値の循環冗長性を表示するルックアップテーブルを作成する
  3. C++ で事前に初期化されたルックアップテーブルを作成する
  4. ルックアップテーブルを作成して、C++ の特定のインデックス内のすべての可能な値を検索する
  5. まとめ
C++ でルックアップテーブルを作成する

組み込みシステムは、手頃な価格の CPU で作られたシンプルなハードウェアデバイスであり、魅力的な価格でベンダーに提供されます。この値下げは、限られた処理能力を犠牲にしてもたらされ、多くの場合、これらのデバイスはスタックオーバーフローのリスクを伴います。

このようなリスクを回避するために、ルックアップテーブルを使用できます。ルックアップテーブルは、何かのデータを格納する配列であり、リアルタイムで実行すると多くの処理能力を必要とします。

ルックアップテーブルは、これらの問題に対する費用効果の高いソリューションを提供します。

この記事では、ルックアップテーブルの概念、その実装、欠点、およびルックアップテーブルを理解しやすくするためのいくつかのコードブロックについて説明します。

C++ でルックアップテーブルを作成する

この記事では、ルックアップテーブルは 3つの異なる方法で作成されます。

  1. プログラムが自身で作成するルックアップテーブル。
  2. 手動ルックアップテーブルは、プログラムの起動時に初期化され、プログラムは後で参照するために使用します。
  3. 一連の変数で作成されたルックアップテーブルを宣言して、特定のインデックス内のすべての可能な値を検索するプログラム。

上記の 3つのケースは、ルックアップテーブルが実際のシナリオで使用される可能性のあるすべての方法です。

C++ で 32 ビット値の循環冗長性を表示するルックアップテーブルを作成する

この例では、32 ビット CRC 計算の循環冗長性をチェックするルックアップテーブルを作成します。CRC は、一部の規則では PEC とも呼ばれますが、どちらも同じ意味です。

次のコードブロックは、256 ビットのデータの CRC 計算のテーブルを出力するルックアップテーブルを作成します。

パッケージのインポート

プログラムは 2つのインポートパッケージを使用します。

  1. iostream-入力/出力操作用
  2. iomanip-プログラムの最終結果を変更します

C++ でルックアップテーブルを作成するためのメソッド関数

最初のメソッド make_pec_table は、配列 table_pec をパラメーターとして受け取ります。この方法は 8 ビットのデータを処理し、さらに 32 ビットに拡張されます。

do-while ループは、rem と 1 の間の大きい方の値をチェックし、それを value_of_polynomial 変数の累乗に上げます。do-while ループは、x の値がゼロ以外になるまで実行されます。

pec_gen メソッドは、符号なし変数 pec を作成します。この変数は、pec テーブルを格納します。ここで、配列 table_pec 内の値は、for ループを使用してここに挿入されます。

main 関数内で、サイズ 256 ビットのローカル配列 table_pec が再び作成されます。次に、メソッド make_pec_table が呼び出され、配列 table_pec がパラメーターとして渡されます。

最後に、256 ビットのデータすべての結果が出力されます。

#include <iomanip>
#include <iostream>

void make_pec_table(unsigned long table_pec[]) {
  unsigned long value_of_polynomial = 0xEDB8320;
  unsigned long rem;
  unsigned char x = 0;
  do {
    // proceed  with data byte
    rem = x;
    for (unsigned long bit = 8; bit > 0; --bit) {
      if (rem & 1)
        rem = (rem >> 1) ^ value_of_polynomial;
      else
        rem = (rem >> 1);
    }
    table_pec[(size_t)x] = rem;
  } while (0 != ++x);
}

unsigned long pec_gen(unsigned char *m, size_t n, unsigned long table_pec[]) {
  unsigned long pec = 0xfffffffful;
  size_t i;
  for (i = 0; i < n; i++) pec = table_pec[*m++ ^ (pec & 0xff)] ^ (pec >> 8);
  return (~pec);
}

int main() {
  unsigned long table_pec[256];
  make_pec_table(table_pec);
  // display PEC table
  for (size_t i = 0; i < 256; i++) {
    std::cout << std::setfill('0') << std::setw(8) << std::hex << table_pec[i];
    if (i % 4 == 3)
      std::cout << std::endl;
    else
      std::cout << ", ";
  }
  return 0;
}

C++ で事前に初期化されたルックアップテーブルを作成する

次の例は、SHA256 暗号化アルゴリズムのコードブロックです。プログラムは 2 セットのレジスタを作成します(これは、プログラムが参照するために手動で作成されたルックアップテーブルに他なりません)。

最初のレジスタのセットは、最初の 64 桁の数値の 16 進値をハッシュキーとして格納するために使用されるものです。これらのキーの値は、コンストラクタークラス hash_functions 内にある変数 hash_keys 内に格納されます。

const unsigned int hash_functions::hash_keys[64] = {
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b,
    0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01,
    0x243185be, 0x550c7dc3, .....}

デフォルトでは、データの読み取りがルックアップテーブルの唯一の目的です。ルックアップテーブルを変更できる場合、それは間違いを示しています。

このようなシナリオを回避するために、アレイは最初に const で宣言されます。

配列には最初の 64 個の自然数の 16 進値が含まれているため、符号に余分なビットは必要ありません。したがって、配列は符号なしで宣言されます。

ルックアップテーブルに負の値がある場合、配列は符号付きデータタイプで宣言する必要があります。

初期化された状態レジスタの別のセットは、最初の 8つの整数の同様の 16 進値のセットを格納します。

void hash_functions::stateregister() {
  s_r[0] = 0x6a09e667;
  s_r[1] = 0xbb67ae85;
  s_r[2] = 0x3c6ef372;
  .....
}

これらの 2つのルックアップテーブルは、時間の複雑さを軽減し、処理速度を上げるために、プログラムに事前に初期化されています。

これは、SHA256 変換自体が CPU にとって時間のかかるプロセスであるためです。実行時にこれらの値を計算するようにプログラムされている場合、プログラムの時間の複雑さが大幅に増加します。

ルックアップテーブルが初期化されると、他の変数と同じように呼び出すことで使用できます。

別のメソッド内ではなく別のコンストラクター内にルックアップテーブルを追加する理由は、ルックアップテーブルが巨大なディスクスペースを飲み込むためです。したがって、グローバルスコープまたは静的エンティティとして宣言する必要があります。

ルックアップテーブルがローカルエンティティとしてメソッド内で初期化されているとします。その場合、メソッドが呼び出されるたびに初期化プロセスが繰り返されます。

プログラム実行の途中で、初期化が非常に大きいメソッドを挿入することはお勧めできません。

起動時またはグローバルスコープにルックアップテーブルがあると、有利で費用効果が高くなります。

for (int n = 0; n < 64; n++) {
  t1 = buffer[7] + hash_keys[n] + w[n];
}
for (n = 0; n < 8; n++) {
  s_r[n] += buffer[n];
}

ここで、これらの値が読み取られる初期化フェーズ中に、アプリケーションが多くの時間と処理能力をブリードすることに注意する必要があります。初期化が行われると、プログラムは値をチェックするために最小限の処理能力を必要とします。

前世代のコンピュータシステムや電子機器には、メモリとディスクスペースがほとんどありませんでしたが、これは依然として懸念事項です。その結果、これらのデバイスのファームウェアでルックアップテーブルを使用すると、多くのディスクスペースを占有する可能性があります。

ルックアップテーブルを保持する変数は、上記の例では const または定数変数として指定されています。これは、ルックアップテーブルに何も書き込まないようにコンパイラに指示するために行われました。

const が定義されていても、アプリケーションはルックアップテーブルを RAM に強制することがよくあります。これは非常に貴重なリソースであるため、プログラマーは変数を宣言する際にフラッシュという用語をハードコーディングする必要があります。

flash は低速のメモリ形式であり、アプリケーションの速度をボトルネックにしますが、貴重な RAM を節約します。

ルックアップテーブルを作成して、C++ の特定のインデックス内のすべての可能な値を検索する

この特定の例は、特定のポイントと次数の正弦波関数の値を表示します。

パッケージのインポート

この例では、3つのインポートパッケージが必要です。

  1. iostream
  2. math.h
  3. conio.h

iostream パッケージは、入出力操作に影響を及ぼします。math.h パッケージは、数学関数と三角関数を呼び出すために使用されます。

conio.h パッケージは、クリアスクリーン、getch などのコンパイラ機能に使用されます。

C++ でルックアップテーブルを作成するために変数を初期化する

このプログラムは、3つの浮動小数点変数(255 サイズの変数 arrayresult、および array_elements)を使用します。他のすべての変数は整数データタイプです(PI は 3.1415 …..として定義されています)。

配列変数 arr は 255 サイズで宣言されています。別のループでは、変数 sine_table が指定されたピークの正弦値を格納します。

最後に、変数 sine_table が同じループ内に出力されます。

#include <conio.h>
#include <math.h>

#include <iostream>

#define PI 3.14159265

float arr[255], final_result, array_elements;
int index, Deg, sine_table;

int main(void) {
  printf("Enter the degree\n");
  scanf("%d", &Deg);

  printf("Enter the index of total point\n");
  scanf("%d", &index);

  printf("Enter the max range\n");
  int r;
  scanf("%d", &r);

  final_result = Deg / index;

  for (int i = 0; i < index; i++) {
    int sum;
    sum += final_result;
    arr[i] = sum;
  }

  for (int n = 0; n < index; n++) {
    array_elements = (arr[n]);
    sine_table = sin(array_elements * PI / 180) * r;
    printf("%d\t", sine_table);
  }
  getch();
  return (0);
}

まとめ

この記事を読んだ後、ルックアップテーブルを作成するためのすべての概念をきちんと理解したことを願っています。ここに示す例は、プログラム内でルックアップテーブルが作成および使用される方法の完全な概要を示しています。

この記事を読んだ後、プログラムでルックアップテーブルを利用することの利点と短所を理解していることが期待されます。

関連記事 - C++ Table