Erstellen eine Nachschlagetabelle in C++

1. Erstellen Sie eine Nachschlagetabelle in C++
2. Erstellen Sie eine Nachschlagetabelle, die die zyklische Redundanz für 32-Bit-Werte in C++ anzeigt
3. Erstellen eine vorinitialisierte Nachschlagetabelle in C++
4. Erstellen Sie eine Nachschlagetabelle, um alle möglichen Werte in einem bestimmten Index in C++ zu finden
5. Fazit

Eingebettete Systeme sind einfache Hardwaregeräte mit erschwinglichen CPUs, die zu attraktiven Preisen an Anbieter geliefert werden. Diese Preissenkung geht mit begrenzter Rechenleistung einher, und bei diesen Geräten besteht häufig die Gefahr eines Stapelüberlaufs.

Um solche Risiken zu vermeiden, können wir Nachschlagetabellen verwenden. Nachschlagetabellen sind Arrays, die Daten für etwas speichern, was viel Rechenleistung erfordert, wenn es in Echtzeit ausgeführt wird.

Die Nachschlagetabelle bietet eine kostengünstige Lösung für diese Probleme.

In diesem Artikel werden die Konzepte einer Nachschlagetabelle, ihre Implementierung, Nachteile und einige Codeblöcke erläutert, um das Verständnis zu erleichtern.

Erstellen Sie eine Nachschlagetabelle in C++

In diesem Artikel werden Nachschlagetabellen auf drei verschiedene Arten erstellt:

1. Eine Nachschlagetabelle, die das Programm selbst erstellt.
2. Beim Programmstart wird eine manuelle Lookup-Tabelle initialisiert, die das Programm später als Referenz verwendet.
3. Ein Programm, das eine Nachschlagetabelle deklariert, die mit einer Reihe von Variablen erstellt wurde, um alle möglichen Werte in einem bestimmten Index zu finden.

Die drei oben genannten Fälle sind alle möglichen Möglichkeiten, wie eine Nachschlagetabelle in realen Szenarien verwendet wird.

Erstellen Sie eine Nachschlagetabelle, die die zyklische Redundanz für 32-Bit-Werte in C++ anzeigt

Dieses Beispiel erstellt eine Nachschlagetabelle, die auf zyklische Redundanz für 32-Bit-CRC-Berechnungen prüft. CRC wird in einigen Konventionen auch als PEC bezeichnet, aber beide bedeuten dasselbe.

Die folgenden Codeblöcke erstellen eine Nachschlagetabelle, die eine Tabelle mit CRC-Berechnungen für 256 Datenbits druckt.

Pakete importieren

Das Programm verwendet zwei Importpakete, nämlich:

1. iostream – für Ein-/Ausgabeoperationen
2. iomanip - um das Endergebnis des Programms zu verändern

Methodenfunktionen zum Erstellen einer Nachschlagetabelle in C++

Die erste Methode make_pec_table nimmt das Array table_pec als Parameter. Dieses Verfahren verarbeitet 8 Bit Daten und erweitert sich weiter auf 32 Bit.

Eine do-while-Schleife sucht nach dem größeren Wert zwischen rem und 1 und potenziert ihn mit der Variable value_of_polynomial. Die do-while-Schleife läuft, bis der Wert von x ungleich Null bleibt.

Die Methode pec_gen erzeugt eine vorzeichenlose Variable pec, die die Tabelle pec speichert, wo die Werte innerhalb des Arrays table_pec hier mit einer for-Schleife eingefügt werden.

Innerhalb der main-Funktion wird wiederum ein lokales Array table_pec mit einer Grösse von 256 Bit angelegt. Dann wird die Methode make_pec_table aufgerufen, während das Array table_pec als Parameter übergeben wird.

Schließlich wird das Ergebnis für alle 256 Datenbits gedruckt.

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

Erstellen eine vorinitialisierte Nachschlagetabelle in C++

Das folgende Beispiel ist ein Codeblock aus dem SHA256-Verschlüsselungsalgorithmus. Das Programm erstellt zwei Sätze von Registern (die nichts als manuell erstellte Nachschlagetabellen sind, auf die das Programm Bezug nimmt).

Der erste Satz von Registern wird zum Speichern von Hexadezimalwerten der ersten 64 numerischen Ziffern als Hash-Schlüssel verwendet. Die Werte dieser Schlüssel werden in der Variablen hash_keys gespeichert, die sich in der Konstruktorklasse hash_functions befindet.

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

Standardmäßig ist das Lesen von Daten der einzige Zweck von Nachschlagetabellen. Wenn eine Nachschlagetabelle geändert werden kann, weist dies auf einen Fehler hin.

Das Array wird zunächst mit const deklariert, um ein solches Szenario zu vermeiden.

Da das Array Hex-Werte der ersten 64 natürlichen Zahlen enthält, benötigt es kein zusätzliches Bit für Vorzeichen. Somit wird das Array als unsigned deklariert.

Wenn eine Nachschlagetabelle negative Werte hat, muss das Array mit einem vorzeichenbehafteten Datentyp deklariert werden.

Ein anderer initialisierter Satz von Zustandsregistern speichert einen ähnlichen Satz von Hexadezimalwerten für die ersten 8 ganzen Zahlen.

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

Diese beiden Nachschlagetabellen sind im Programm vorinitialisiert, um die Zeitkomplexität zu reduzieren und die Verarbeitungsgeschwindigkeit zu erhöhen.

Dies liegt daran, dass die SHA256-Konvertierung an sich ein langwieriger Prozess für die CPU ist. Wenn es so programmiert ist, dass es diese Werte während der Laufzeit berechnet, wird es die Zeitkomplexität des Programms drastisch erhöhen.

Sobald eine Nachschlagetabelle initialisiert ist, kann sie verwendet werden, indem sie wie jede andere Variable aufgerufen wird.

Ein Grund, die Nachschlagetabelle in einen separaten Konstruktor und nicht in eine andere Methode einzufügen, ist, dass Nachschlagetabellen sehr viel Speicherplatz verschlingen. Daher sollte es entweder im globalen Bereich oder als statische Entität deklariert werden.

Angenommen, eine Nachschlagetabelle wird innerhalb einer Methode als lokale Entität initialisiert. In diesem Fall wird der Initialisierungsprozess bei jedem Aufruf der Methode wiederholt.

Es ist keine gute Praxis, mitten in der Programmausführung eine Methode mit großer Initialisierung einzufügen.

Es ist vorteilhaft und kosteneffizient, Nachschlagetabellen im Startup- oder globalen Bereich zu haben.

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

Hierbei ist zu beachten, dass die Applikation beim Auslesen dieser Werte in der Initialisierungsphase viel Zeit und Rechenleistung frisst. Sobald die Initialisierung erfolgt ist, benötigt das Programm eine minimale Verarbeitungsleistung, um zwischen den Werten zu prüfen.

Die Computersysteme früherer Generationen und elektronische Geräte hatten früher sehr wenig Speicher und Speicherplatz, was immer noch Anlass zur Sorge gibt. Infolgedessen kann die Verwendung einer Nachschlagetabelle in der Firmware dieser Geräte viel Speicherplatz beanspruchen.

Die Variable, die die Nachschlagetabelle enthält, wurde im obigen Beispiel als const oder als konstante Variable bezeichnet. Es wurde getan, um den Compiler anzuweisen, nichts in die Nachschlagetabelle zu schreiben.

Obwohl const definiert ist, zwingt die Anwendung die Lookup-Tabelle oft in den Arbeitsspeicher. Da es sich um eine so wertvolle Ressource handelt, müssen Programmierer den Begriff flash fest codieren, während sie Variablen deklarieren.

flash ist eine langsamere Form von Speicher, die die Anwendungsgeschwindigkeit einschränkt, aber wertvollen RAM spart.

Erstellen Sie eine Nachschlagetabelle, um alle möglichen Werte in einem bestimmten Index in C++ zu finden

Dieses spezielle Beispiel zeigt die Werte der Sinuswellenfunktion für einen bestimmten Punkt und Grad an.

Pakete importieren

Dieses Beispiel erfordert drei Importpakete:

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

Das Paket iostream hat seine Implikationen für Input-Output-Operationen. Das Paket math.h wird verwendet, um mathematische Funktionen und trigonometrische Funktionen aufzurufen.

Das Paket conio.h wird für Compiler-Funktionen wie clear screen, getch ​​usw. verwendet.

Initialisieren Sie Variablen zum Erstellen einer Nachschlagetabelle in C++

Dieses Programm verwendet 3 Fließkommavariablen - die Variable array mit einer Größe von 255, result und array_elements. Alle anderen Variablen sind vom Datentyp Integer (PI ist definiert als 3.1415…..).

Die Array-Variable arr wird mit 255 Größen deklariert. In einer weiteren Schleife speichert die Variable sine_table die Sinuswerte für die angegebenen Peaks.

Zuletzt wird die Variable sine_table in derselben Schleife gedruckt.

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

Fazit

Wir hoffen, dass Sie nach dem Lesen dieses Artikels alle Konzepte zum Erstellen von Nachschlagetabellen verstanden haben. Die hier vorgestellten Beispiele geben einen vollständigen Überblick darüber, wie Nachschlagetabellen erstellt und in einem Programm verwendet werden.

Nachdem Sie diesen Artikel gelesen haben, sollten Sie die Vor- und Nachteile der Verwendung von Nachschlagetabellen in einem Programm verstanden haben.