How to Create a Lookup Table in C++

1. Create a Lookup Table in C++
2. Create a Lookup Table That Displays Cyclic Redundancy for 32-Bit Values in C++
3. Create a Pre-initialized Lookup Table in C++
4. Create a Lookup Table to Find All Possible Values Inside a Given Index in C++
5. Conclusion

Embedded systems are simple hardware devices made with affordable CPUs to be delivered to vendors at attractive prices. This price cut comes at the cost of limited processing power, and often these devices run a risk of stack overflow.

To avoid such risks, we can use lookup tables. Lookup tables are arrays storing data for something, which takes lots of processing power if done in real-time.

The lookup table provides a cost-effective solution to these problems.

This article explains the concepts of a lookup table, its implementation, drawbacks, and some code blocks to make understanding it easier.

Create a Lookup Table in C++

In this article, lookup tables are created in three different manners:

1. A lookup table that the program creates itself.
2. A manual lookup table is initialized at program startup, which the program uses later for reference.
3. A program that declares a lookup table created with a set of variables to find all possible values inside a given index.

The three cases mentioned above are all the possible ways a lookup table gets used in real-life scenarios.

Create a Lookup Table That Displays Cyclic Redundancy for 32-Bit Values in C++

This example creates a lookup table that checks for cyclic redundancy for 32-bit CRC calculations. CRC is also referred to as PEC in some conventions, but they both mean the same.

The following code blocks create a lookup table that prints a table of CRC calculations for 256 bits of data.

Import Packages

The program uses two import packages, namely:

1. iostream - for input/output operations
2. iomanip - to alter the final result of the program

Method Functions to Create a Lookup Table in C++

The first method, make_pec_table, takes the array table_pec as a parameter. This method deals with 8 bits of data, further expanding to 32 bits.

A do-while loop checks for the larger value between rem and 1 and raises it to the power of the value_of_polynomial variable. The do-while loop runs until the value of x remains non-zero.

The pec_gen method creates an unsigned variable pec, which stores the pec table, where the values inside the array table_pec are inserted here using a for loop.

Inside the main function, a local array table_pec is again created of size 256 bits. Then the method make_pec_table is called while the array table_pec is passed as a parameter.

Finally, the result is printed for all the 256 bits of data.

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

Create a Pre-initialized Lookup Table in C++

The following example is a code block from the SHA256 encryption algorithm. The program creates two sets of registers (which are nothing but lookup tables manually created for the program to take reference).

The first set of registers is the ones that are used for storing hexadecimal values of the first 64 numerical digits as hash keys. The values of these keys are stored inside the variable hash_keys, which are inside the constructor class hash_functions.

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

By default, reading data is the sole purpose of lookup tables. If a lookup table can be altered, then that indicates a mistake.

The array is initially declared with const to avoid such a scenario.

As the array contains hex values of the first 64 natural numbers, it doesn’t need any extra bit for signs. Thus, the array is declared unsigned.

If a lookup table has negative values, the array needs to be declared with a signed data type.

Another set of state registers initialized stores a similar set of hexadecimal values for the first 8 integers.

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

These two lookup tables are pre-initialized into the program to reduce time complexity and increase processing speed.

It’s because SHA256 conversion is, in itself, a lengthy process for the CPU. If it is programmed to calculate those values during runtime, it will drastically increase the time complexity of the program.

Once a lookup table is initialized, it can be used by calling it like any other variable.

A reason to add the lookup table inside a separate constructor and not inside another method is that lookup tables engulf huge disk space. Hence, it should be declared either in the global scope or as a static entity.

Suppose a lookup table is initialized inside a method as a local entity. In that case, the initialization process gets repeated every time the method is called.

It is bad practice to insert a method with huge initialization in the middle of program execution.

Having lookup tables at the startup or global scope is advantageous and cost-efficient.

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];
}

Here it must be noted that the application bleeds a lot of time and processing power during the initialization phase when these values are read. Once the initialization happens, the program requires minimum processing power to check between values.

The computer systems of previous generations and electronic devices used to have very little memory and disc space, which is still a source of concern. As a result, employing a lookup table in the firmware of those devices may take up a lot of disc space.

The variable that holds the lookup table was designated const or a constant variable in the example above. It was done to direct the compiler to avoid writing anything into the lookup table.

Even though const is defined, the application often forces the lookup table into the RAM. Because it is such a valuable resource, programmers need to hardcode the term flash while declaring variables.

flash is a slower form of memory that bottlenecks the application speed but saves precious RAM.

Create a Lookup Table to Find All Possible Values Inside a Given Index in C++

This particular example displays the values of the sine wave function for a given point and degree.

Import Packages

This example requires three import packages:

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

The iostream package has its implications for input-output operations. The math.h package is used to invoke math functions and trigonometric functions.

The conio.h package is used for compiler functions like clear screen, getch, etc.

Initialize Variables to Create a Lookup Table in C++

This program uses 3 floating-point variables - the variable array of 255 size, result, and array_elements. All the other variables are of integer datatype (PI is defined as 3.1415…..).

The array variable arr is declared with 255 sizes. In another loop, the variable sine_table stores the sine values for the given peaks.

Lastly, the variable sine_table is printed inside the same loop.

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

Conclusion

We hope you have grasped all the concepts of creating lookup tables neatly after reading this article. The examples presented here give a complete overview of how lookup tables are created and used inside a program.

After reading this article, you are expected to have grasped the benefits and cons of utilizing lookup tables in a program.