在 C++ 中建立查詢表

Jay Shaw 2023年10月12日

C++ C++ Table

在 C++ 中建立查詢表
在 C++ 中建立一個顯示 32 位值的迴圈冗餘的查詢表
在 C++ 中建立預初始化的查詢表
在 C++ 中建立一個查詢表以查詢給定索引內的所有可能值
まとめ

嵌入式系統是簡單的硬體裝置，由價格實惠的 CPU 製成，以極具吸引力的價格交付給供應商。這種降價是以有限的處理能力為代價的，而且這些裝置通常存在堆疊溢位的風險。

為了避免這種風險，我們可以使用查詢表。查詢表是儲存資料的陣列，如果實時完成，它會佔用大量的處理能力。

查詢表為這些問題提供了一種經濟有效的解決方案。

本文解釋了查詢表的概念、實現、缺點和一些程式碼塊，以便於理解。

在 C++ 中建立查詢表

在本文中，查詢表以三種不同的方式建立：

程式自己建立的查詢表。
程式啟動時會初始化一個手動查表，供程式以後參考。
宣告使用一組變數建立的查詢表以查詢給定索引內的所有可能值的程式。

上面提到的三種情況都是查詢表在現實生活場景中使用的所有可能方式。

在 C++ 中建立一個顯示 32 位值的迴圈冗餘的查詢表

此示例建立一個查詢表，用於檢查 32 位 CRC 計算的迴圈冗餘。CRC 在某些約定中也稱為 PEC，但它們的含義相同。

以下程式碼塊建立一個查詢表，該表列印 256 位資料的 CRC 計算表。

匯入包

該程式使用了兩個匯入包，分別是：

iostream - 用於輸入/輸出操作
iomanip - 改變程式的最終結果

在 C++ 中建立查詢表的方法函式

第一種方法 make_pec_table 將陣列 table_pec 作為引數。該方法處理 8 位資料，進一步擴充套件到 32 位。

do-while 迴圈檢查 rem 和 1 之間的較大值，並將其提升到 value_of_polynomial 變數的冪。do-while 迴圈一直執行，直到 x 的值保持非零為止。

pec_gen 方法建立一個無符號變數 pec，它儲存 pec 表，其中使用 for 迴圈將陣列 table_pec 內的值插入此處。

在主函式內部，再次建立了一個大小為 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 加密演算法的程式碼塊。該程式建立了兩組暫存器（它們只是手動建立的查詢表以供程式參考）。

第一組暫存器用於將前 64 位數字的十六進位制值儲存為雜湊鍵。這些鍵的值儲存在變數 hash_keys 中，該變數位於建構函式類 hash_functions 中。

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

預設情況下，讀取資料是查詢表的唯一目的。如果可以更改查詢表，則表明存在錯誤。

陣列最初用 const 宣告以避免這種情況。

由於該陣列包含前 64 個自然數的十六進位制值，因此不需要任何額外的符號位。因此，陣列被宣告為無符號的。

如果查詢表具有負值，則需要使用帶符號資料型別宣告陣列。

另一組已初始化的狀態暫存器為前 8 個整數儲存一組類似的十六進位制值。

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

這兩個查詢表被預先初始化到程式中，以降低時間複雜度並提高處理速度。

這是因為 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 進行硬編碼。

flash 是一種較慢的記憶體形式，它會限制應用程式的速度，但可以節省寶貴的 RAM。

在 C++ 中建立一個查詢表以查詢給定索引內的所有可能值

此特定示例顯示給定點和度數的正弦波函式值。

匯入包

此示例需要三個匯入包：

iostream
math.h
conio.h

iostream 包對輸入輸出操作有其影響。math.h 包用於呼叫數學函式和三角函式。

conio.h 包用於編譯器功能，如清除螢幕、getch 等。

在 C++ 中初始化變數以建立查詢表

該程式使用 3 個浮點變數 - 大小為 255 的變數 array、result 和 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);
}

まとめ

我們希望你在閱讀本文後已經掌握了建立查詢表的所有概念。此處提供的示例完整概述瞭如何在程式中建立和使用查詢表。

閱讀本文後，你應該已經掌握了在程式中使用查詢表的好處和壞處。