在 C++ 中创建查找表

Jay Shaw 2023年1月30日 2022年6月7日

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 <iostream>
#include <iomanip>

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<iostream>
#include<math.h>
#include<conio.h>

#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);
}

结论

我们希望你在阅读本文后已经掌握了创建查找表的所有概念。此处提供的示例完整概述了如何在程序中创建和使用查找表。

阅读本文后，你应该已经掌握了在程序中使用查找表的好处和坏处。