Créer une table de recherche en C++

1. Créer une table de recherche en C++
2. Créer une table de recherche qui affiche la redondance cyclique pour les valeurs 32 bits en C++
3. Créer une table de recherche pré-initialisée en C++
4. Créer une table de recherche pour trouver toutes les valeurs possibles dans un index donné en C++
5. Conclusion

Les systèmes embarqués sont des dispositifs matériels simples fabriqués avec des processeurs abordables à livrer aux fournisseurs à des prix attractifs. Cette baisse de prix se fait au prix d’une puissance de traitement limitée, et souvent ces appareils courent un risque de débordement de pile.

Pour éviter de tels risques, nous pouvons utiliser des tables de recherche. Les tables de recherche sont des tableaux stockant des données pour quelque chose, ce qui nécessite beaucoup de puissance de traitement si elles sont effectuées en temps réel.

La table de consultation fournit une solution rentable à ces problèmes.

Cet article explique les concepts d’une table de recherche, son implémentation, ses inconvénients et certains blocs de code pour faciliter sa compréhension.

Créer une table de recherche en C++

Dans cet article, les tables de recherche sont créées de trois manières différentes :

1. Une table de recherche que le programme crée lui-même.
2. Une table de recherche manuelle est initialisée au démarrage du programme, que le programme utilise ultérieurement comme référence.
3. Un programme qui déclare une table de recherche créée avec un ensemble de variables pour trouver toutes les valeurs possibles à l’intérieur d’un index donné.

Les trois cas mentionnés ci-dessus sont toutes les manières possibles d’utiliser une table de recherche dans des scénarios réels.

Créer une table de recherche qui affiche la redondance cyclique pour les valeurs 32 bits en C++

Cet exemple crée une table de recherche qui vérifie la redondance cyclique pour les calculs CRC 32 bits. Le CRC est également appelé PEC dans certaines conventions, mais ils signifient tous les deux la même chose.

Les blocs de code suivants créent une table de recherche qui imprime une table de calculs CRC pour 256 bits de données.

Importer des packages

Le programme utilise deux packages d’importation, à savoir :

1. iostream - pour les opérations d’entrée/sortie
2. iomanip - pour modifier le résultat final du programme

Fonctions de méthode pour créer une table de recherche en C++

La première méthode, make_pec_table, prend le tableau table_pec en paramètre. Cette méthode traite 8 bits de données, s’étendant ensuite à 32 bits.

Une boucle do-while vérifie la plus grande valeur entre rem et 1 et l’élève à la puissance de la variable value_of_polynomial. La boucle do-while s’exécute jusqu’à ce que la valeur de x reste non nulle.

La méthode pec_gen crée une variable non signée pec, qui stocke la table pec, où les valeurs à l’intérieur du tableau table_pec sont insérées ici à l’aide d’une boucle for.

A l’intérieur de la fonction main, un tableau local table_pec est à nouveau créé de taille 256 bits. Puis la méthode make_pec_table est appelée tandis que le tableau table_pec est passé en paramètre.

Enfin, le résultat est imprimé pour tous les 256 bits de données.

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

Créer une table de recherche pré-initialisée en C++

L’exemple suivant est un bloc de code de l’algorithme de chiffrement SHA256. Le programme crée deux ensembles de registres (qui ne sont rien d’autre que des tables de recherche créées manuellement pour que le programme prenne référence).

Le premier ensemble de registres est celui qui est utilisé pour stocker les valeurs hexadécimales des 64 premiers chiffres numériques sous forme de clés de hachage. Les valeurs de ces clés sont stockées dans la variable hash_keys, qui se trouve à l’intérieur de la classe constructeur hash_functions.

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

Par défaut, la lecture des données est le seul objectif des tables de recherche. Si une table de recherche peut être modifiée, cela indique une erreur.

Le tableau est initialement déclaré avec const pour éviter un tel scénario.

Comme le tableau contient des valeurs hexadécimales des 64 premiers nombres naturels, il n’a pas besoin de bit supplémentaire pour les signes. Ainsi, le tableau est déclaré non signé.

Si une table de recherche a des valeurs négatives, le tableau doit être déclaré avec un type de données signé.

Un autre ensemble de registres d’état initialisé stocke un ensemble similaire de valeurs hexadécimales pour les 8 premiers entiers.

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

Ces deux tables de consultation sont pré-initialisées dans le programme pour réduire la complexité temporelle et augmenter la vitesse de traitement.

C’est parce que la conversion SHA256 est, en soi, un long processus pour le CPU. S’il est programmé pour calculer ces valeurs pendant l’exécution, cela augmentera considérablement la complexité temporelle du programme.

Une fois qu’une table de correspondance est initialisée, elle peut être utilisée en l’appelant comme n’importe quelle autre variable.

Une raison d’ajouter la table de recherche dans un constructeur séparé et non dans une autre méthode est que les tables de recherche engloutissent un espace disque énorme. Par conséquent, il doit être déclaré soit dans la portée globale, soit en tant qu’entité statique.

Supposons qu’une table de recherche soit initialisée dans une méthode en tant qu’entité locale. Dans ce cas, le processus d’initialisation est répété chaque fois que la méthode est appelée.

Il est déconseillé d’insérer une méthode avec une énorme initialisation au milieu de l’exécution du programme.

Avoir des tables de recherche au démarrage ou à l’échelle mondiale est avantageux et rentable.

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

Ici, il faut noter que l’application perd beaucoup de temps et de puissance de traitement lors de la phase d’initialisation lorsque ces valeurs sont lues. Une fois l’initialisation effectuée, le programme nécessite une puissance de traitement minimale pour vérifier entre les valeurs.

Les systèmes informatiques des générations précédentes et les appareils électroniques avaient très peu de mémoire et d’espace disque, ce qui est toujours une source de préoccupation. Par conséquent, l’utilisation d’une table de recherche dans le micrologiciel de ces appareils peut occuper beaucoup d’espace disque.

La variable qui contient la table de recherche a été désignée const ou une variable constante dans l’exemple ci-dessus. Cela a été fait pour demander au compilateur d’éviter d’écrire quoi que ce soit dans la table de recherche.

Même si const est défini, l’application force souvent la table de recherche dans la RAM. Parce qu’il s’agit d’une ressource si précieuse, les programmeurs doivent coder en dur le terme flash lors de la déclaration des variables.

flash est une forme de mémoire plus lente qui ralentit la vitesse de l’application mais économise de la RAM précieuse.

Créer une table de recherche pour trouver toutes les valeurs possibles dans un index donné en C++

Cet exemple particulier affiche les valeurs de la fonction d’onde sinusoïdale pour un point et un degré donnés.

Importer des packages

Cet exemple nécessite trois packages d’importation :

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

Le package iostream a ses implications pour les opérations d’entrée-sortie. Le package math.h est utilisé pour invoquer des fonctions mathématiques et des fonctions trigonométriques.

Le package conio.h est utilisé pour les fonctions du compilateur telles que clear screen, getch, etc.

Initialiser des variables pour créer une table de recherche en C++

Ce programme utilise 3 variables à virgule flottante - la variable array de taille 255, result et array_elements. Toutes les autres variables sont de type entier (PI est défini comme 3.1415…..).

La variable tableau arr est déclarée avec 255 tailles. Dans une autre boucle, la variable sine_table stocke les valeurs de sinus pour les pics donnés.

Enfin, la variable sine_table est imprimée à l’intérieur de la même boucle.

#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

Nous espérons que vous avez bien compris tous les concepts de création de tables de recherche après avoir lu cet article. Les exemples présentés ici donnent un aperçu complet de la façon dont les tables de recherche sont créées et utilisées dans un programme.

Après avoir lu cet article, on s’attend à ce que vous ayez compris les avantages et les inconvénients de l’utilisation de tables de recherche dans un programme.