summaryrefslogtreecommitdiff
path: root/src/analysis/scan/patterns/backends/acism.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/analysis/scan/patterns/backends/acism.c')
-rw-r--r--src/analysis/scan/patterns/backends/acism.c1522
1 files changed, 1522 insertions, 0 deletions
diff --git a/src/analysis/scan/patterns/backends/acism.c b/src/analysis/scan/patterns/backends/acism.c
new file mode 100644
index 0000000..53bad11
--- /dev/null
+++ b/src/analysis/scan/patterns/backends/acism.c
@@ -0,0 +1,1522 @@
+
+/* Chrysalide - Outil d'analyse de fichiers binaires
+ * acism.c - méthode de recherche basée sur l'algorithme Aho-Corasick Interleaved State-transition Matrix
+ *
+ * Copyright (C) 2022 Cyrille Bagard
+ *
+ * This file is part of Chrysalide.
+ *
+ * Chrysalide is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * Chrysalide is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Foobar. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+
+#include "acism.h"
+
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+
+#include "acism-int.h"
+#include "../../../../common/sort.h"
+
+
+
+/* ---------------------- IMPLANTATION D'UNE NOUVELLE APPROCHE ---------------------- */
+
+
+/* Initialise la classe des méthodes basée sur ACISM. */
+static void g_acism_backend_class_init(GAcismBackendClass *);
+
+/* Initialise une instance de méthodes basée sur ACISM. */
+static void g_acism_backend_init(GAcismBackend *);
+
+/* Supprime toutes les références externes. */
+static void g_acism_backend_dispose(GAcismBackend *);
+
+/* Procède à la libération totale de la mémoire. */
+static void g_acism_backend_finalize(GAcismBackend *);
+
+
+
+/* --------------------- IMPLEMENTATION DES FONCTIONS DE CLASSE --------------------- */
+
+
+/* Indique la taille maximale des suites d'octets recherchées. */
+size_t g_acism_backend_get_atom_max_size(const GAcismBackend *);
+
+/* Intègre un motif limité de contenu à rechercher. */
+static void g_acism_backend_setup_for(GAcismBackend *, const uint8_t *, size_t, uint32_t [2]);
+
+/* Inscrit dans le moteur une chaîne de caractères à rechercher. */
+static bool g_acism_backend_enroll_plain_pattern(GAcismBackend *, const uint8_t *, size_t, uint32_t [2]);
+
+#ifdef __USE_BYTE_FREQ
+
+/* Compare un niveau de fréquence avec un autre. */
+static int compare_byte_frequencies(const acism_freq_rank_t *, const acism_freq_rank_t *);
+
+/* Détermine les identifiants de chaque valeur 8 bits utile. */
+static void g_acism_backend_define_codes(GAcismBackend *);
+
+#endif
+
+/* Construit l'arborescence de noeuds de lecture. */
+static void g_acism_backend_build_trie(GAcismBackend *);
+
+/* Construit l'arborescence de noeuds de lecture. */
+static void g_acism_backend_build_suffix_links(GAcismBackend *);
+
+#ifdef __SORT_BEFORE_BITMASK
+
+/* Compare des noeuds selon l'espace de codes couvert. */
+static int compare_node_according_to_code_range(const acism_trie_node_t **, const acism_trie_node_t **);
+
+#endif
+
+/* Organise la convertion de l'arborescence en tableau. */
+static void g_acism_backend_prepare_interleave_array(GAcismBackend *);
+
+/* Compresse l'arborescence dans un tableau de position. */
+static void g_acism_backend_build_interleave_array(GAcismBackend *);
+
+/* Met en ordre les derniers détails avant un premier scan. */
+static bool g_acism_backend_warm_up(GAcismBackend *);
+
+/* Récupère les identifiants finaux pour un motif recherché. */
+static patid_t g_acism_backend_build_plain_pattern_id(const GAcismBackend *, const uint32_t [2]);
+
+/* Détermine le nombre d'identifiants constitués. */
+static size_t g_acism_backend_count_plain_pattern_ids(const GAcismBackend *);
+
+/* Parcours un contenu binaire à la recherche de motifs. */
+static void g_acism_backend_run_scan(const GAcismBackend *, GScanContext *);
+
+/* Affiche les caractéristques d'un noeud et de ses enfants. */
+static void visit_and_output_node(const acism_trie_node_t *, unsigned int);
+
+/* Imprime quelques faits quant aux éléments mis en place. */
+static void g_acism_backend_output_stats(const GAcismBackend *);
+
+
+
+/* ---------------------------------------------------------------------------------- */
+/* IMPLANTATION D'UNE NOUVELLE APPROCHE */
+/* ---------------------------------------------------------------------------------- */
+
+
+/* Indique le type défini pour un moteur de recherche pour données. */
+G_DEFINE_TYPE(GAcismBackend, g_acism_backend, G_TYPE_ENGINE_BACKEND);
+
+
+/******************************************************************************
+* *
+* Paramètres : klass = classe à initialiser. *
+* *
+* Description : Initialise la classe des méthodes basée sur ACISM. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_acism_backend_class_init(GAcismBackendClass *klass)
+{
+ GObjectClass *object; /* Autre version de la classe */
+ GEngineBackendClass *backend; /* Version de classe parente */
+
+ object = G_OBJECT_CLASS(klass);
+
+ object->dispose = (GObjectFinalizeFunc/* ! */)g_acism_backend_dispose;
+ object->finalize = (GObjectFinalizeFunc)g_acism_backend_finalize;
+
+ backend = G_ENGINE_BACKEND_CLASS(klass);
+
+ backend->get_max_size = (get_backend_atom_max_size_fc)g_acism_backend_get_atom_max_size;
+ backend->enroll_plain = (enroll_plain_into_backend_fc)g_acism_backend_enroll_plain_pattern;
+ backend->warm_up = (warm_up_backend_fc)g_acism_backend_warm_up;
+ backend->build_id = (build_backend_plain_pattern_id_fc)g_acism_backend_build_plain_pattern_id;
+ backend->count_ids = (count_backend_plain_pattern_ids_fc)g_acism_backend_count_plain_pattern_ids;
+ backend->run_scan = (run_backend_scan_fc)g_acism_backend_run_scan;
+ backend->output = (output_backend_stats_fc)g_acism_backend_output_stats;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = instance à initialiser. *
+* *
+* Description : Initialise une instance de méthodes basée sur ACISM. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_acism_backend_init(GAcismBackend *backend)
+{
+#ifdef __USE_BYTE_FREQ
+ size_t i; /* Boucle de parcours #1 */
+ acism_freq_rank_t *iter; /* Boucle de parcours #2 */
+#endif
+
+#ifdef __USE_BYTE_FREQ
+ memset(backend->codes_for_bytes, 0, 256 * sizeof(acism_code_t));
+#endif
+
+ backend->nchars = 0;
+
+#ifdef __USE_BYTE_FREQ
+ for (i = 0, iter = backend->frequencies; i < 256; i++, iter++)
+ {
+ iter->frequency = 0;
+ iter->rank = i;
+ }
+#endif
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = instance d'objet GLib à traiter. *
+* *
+* Description : Supprime toutes les références externes. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_acism_backend_dispose(GAcismBackend *backend)
+{
+ G_OBJECT_CLASS(g_acism_backend_parent_class)->dispose(G_OBJECT(backend));
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = instance d'objet GLib à traiter. *
+* *
+* Description : Procède à la libération totale de la mémoire. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_acism_backend_finalize(GAcismBackend *backend)
+{
+ if (backend->sources != NULL)
+ free(backend->sources);
+
+ if (backend->nodes != NULL)
+ free(backend->nodes);
+
+ if (backend->bitmap_usage != NULL)
+ delete_bit_field(backend->bitmap_usage);
+
+ if (backend->states != NULL)
+ free(backend->states);
+
+ if (backend->coverages != NULL)
+ free(backend->coverages);
+
+ G_OBJECT_CLASS(g_acism_backend_parent_class)->finalize(G_OBJECT(backend));
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : - *
+* *
+* Description : Crée une méthode de recherche basée sur l'algorithme Acism. *
+* *
+* Retour : Méthode mise en place. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+GEngineBackend *g_acism_backend_new(void)
+{
+ GAcismBackend *result; /* Structure à retourner */
+
+ result = g_object_new(G_TYPE_ACISM_BACKEND, NULL);
+
+ return G_ENGINE_BACKEND(result);
+
+}
+
+
+
+/* ---------------------------------------------------------------------------------- */
+/* IMPLEMENTATION DES FONCTIONS DE CLASSE */
+/* ---------------------------------------------------------------------------------- */
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = moteur de recherche à consulter. *
+* *
+* Description : Indique la taille maximale des suites d'octets recherchées. *
+* *
+* Retour : Valeur strictement positive. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+size_t g_acism_backend_get_atom_max_size(const GAcismBackend *backend)
+{
+ size_t result; /* Taille à faire connaître */
+
+ result = ACSIM_ATOM_SIZE;
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = moteur de recherche à préparer. *
+* pattern = chaîne de caractères classique à intégrer. *
+* len = taille de cette chaîne. *
+* tmp_id = identifiants temporaires vers le motif. [OUT] *
+* *
+* Description : Intègre un motif limité de contenu à rechercher. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_acism_backend_setup_for(GAcismBackend *backend, const uint8_t *pattern, size_t len, uint32_t tmp_id[2])
+{
+ size_t current; /* Indice de source courante */
+ acism_source_t *source; /* Définition à mémoriser */
+
+ /**
+ * Les motifs '\x00\x00\x00\x00abcd1234' et '\x01\x01\x01\x01abcd1234'
+ * peuvent constituer deux cibles différentes, mais ils comportent
+ * normalement la même séquence atomique à rechercher : 'abcd1234'.
+ *
+ * Chaque motif 'abcd1234' proposé est enregistré ici, et se verra in fine
+ * attribuer un identifiant propre. Le regroupement des motifs identiques
+ * et la constitution des identifiants finaux sont réalisés au moment de la
+ * construction de l'arborescence de recherche.
+ */
+
+ /* Pré-inscription pour l'extérieur */
+
+ current = backend->sources_count;
+
+ tmp_id[0] = current;
+ tmp_id[1] = 0; /* Non utilisé */
+
+ /* Inscription en interne */
+
+ backend->sources = realloc(backend->sources, ++backend->sources_count * sizeof(acism_source_t));
+
+ source = &backend->sources[current];
+
+ source->atoms = pattern;
+ source->len = len;
+
+ backend->nchars += len;
+
+#ifdef __USE_BYTE_FREQ
+ for (i = 0; i < len; i++)
+ backend->frequencies[pattern[i]].frequency++;
+#endif
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = moteur de recherche à manipuler. *
+* plain = chaîne de caractères classique à intégrer. *
+* len = taille de cette chaîne. *
+* tmp_id = identifiants temporaires vers le motif. [OUT] *
+* *
+* Description : Inscrit dans le moteur une chaîne de caractères à rechercher.*
+* *
+* Retour : Bilan de l'opération. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static bool g_acism_backend_enroll_plain_pattern(GAcismBackend *backend, const uint8_t *plain, size_t len, uint32_t tmp_id[2])
+{
+ bool result; /* Bilan à retourner */
+
+ assert(len <= ACSIM_ATOM_SIZE);
+
+ result = true;
+
+ /**
+ * Le traitement différé des chaînes à rechercher permet deux choses :
+ * - la construction d'une table de permutation ;
+ * - le décompte des noeuds à allouer (en une seule fois).
+ *
+ * Si l'intention du premier point est louable (densifier les champs de bits
+ * pour allouer moins et tenir plus facilement dans le cache du CPU), la
+ * permetutation est extrèmement coûteuse pendant la phase de scan
+ * (une lecture supplémentaire par octet de données scannées).
+ *
+ * Le second point reste valable (à priori).
+ *
+ * L'appel à la fonction g_acism_backend_setup_for() demeure donc, et l'arbre
+ * est construit dans un second temps. La distinction de cette fonction avec
+ * la procédure d'enrôlement permet potentiellement d'étuer une bascule à
+ * moindre coût un jour.
+ */
+
+ g_acism_backend_setup_for(backend, plain, len, tmp_id);
+
+ return result;
+
+}
+
+
+#ifdef __USE_BYTE_FREQ
+
+
+/******************************************************************************
+* *
+* Paramètres : a = premier élément à comparer. *
+* b = second élément à comparer. *
+* *
+* Description : Compare un niveau de fréquence avec un autre. *
+* *
+* Retour : Bilan de la comparaison. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static int compare_byte_frequencies(const acism_freq_rank_t *a, const acism_freq_rank_t *b)
+{
+ int result; /* Bilan à retourner */
+
+ /**
+ * Afin d'obtenir les plus grosses fréquences en premier,
+ * l'ordre de comparaison est inversé : b < a ?
+ */
+
+ result = sort_unsigned_long(b->frequency, a->frequency);
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = moteur de recherche à préparer. *
+* *
+* Description : Détermine les identifiants de chaque valeur 8 bits utile. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_acism_backend_define_codes(GAcismBackend *backend)
+{
+ size_t i; /* Boucle de parcours #1 */
+ acism_freq_rank_t *iter; /* Boucle de parcours #2 */
+
+ /**
+ * La redistribution des valeurs d'octet va permettre de compacter
+ * par la suite les masques de cellules utilisées pour construire
+ * le plus petit tableau des états.
+ *
+ * L'idée est de grouper le plus possible les états (représentés
+ * par un indice) autour de l'état 0.
+ */
+
+ qsort(backend->frequencies, 256, sizeof(acism_freq_rank_t), (__compar_fn_t)compare_byte_frequencies);
+
+ /* 0 == racine */
+ backend->codes_count++;
+
+ for (i = 0, iter = backend->frequencies; i < 256; i++, iter++)
+ {
+ if (iter->frequency == 0)
+ break;
+
+ backend->codes_for_bytes[iter->rank] = backend->codes_count++;
+
+ }
+
+}
+
+
+#endif
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = moteur de recherche à préparer. *
+* *
+* Description : Construit l'arborescence de noeuds de lecture. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_acism_backend_build_trie(GAcismBackend *backend)
+{
+ size_t i; /* Boucle de parcours #1 */
+ acism_trie_node_t *next; /* Prochain noeud disponible */
+ acism_trie_node_t *node; /* Tête de parcours */
+ acism_source_t *source; /* Définition à mémoriser */
+ size_t k; /* Boucle de parcours #2 */
+ acism_code_t code; /* Identifiant de symbole */
+ acism_trie_node_t *parent; /* Sauvegarde d'un accès */
+ uint32_t current_start; /* Indice de gestionnaire */
+
+ backend->nodes = calloc(backend->nchars + 1, sizeof(acism_trie_node_t));
+
+ for (i = 0; i < (backend->nchars + 1); i++)
+ {
+ backend->nodes[i].min_child_code = MAX_ACISM_CODE;
+ backend->nodes[i].max_child_code = MIN_ACISM_CODE;
+ }
+
+ next = backend->nodes + 1;
+
+ for (i = 0; i < backend->sources_count; i++)
+ {
+ node = backend->nodes;
+
+ source = &backend->sources[i];
+
+ /* Parcours des noeuds contenus */
+
+ for (k = 0; k < source->len && node->child != NULL; k++)
+ {
+#ifdef __USE_BYTE_FREQ
+ code = backend->codes_for_bytes[source->atoms[k]];
+#else
+ code = 1 + source->atoms[k];
+#endif
+
+ /* Insertion d'un nouveau noeud au début des enfants */
+ if (code < node->child->code)
+ {
+ next->parent = node;
+ next->suffix_link = node;
+ next->data = source->atoms[k];
+ next->code = code;
+
+ next->sibling = node->child;
+ node->child = next++;
+
+ if (code < node->min_child_code) node->min_child_code = code;
+ if (code > node->max_child_code) node->max_child_code = code;
+ node->children_count++;
+
+ node = node->child;
+
+ k++;
+ break;
+
+ }
+
+ parent = node;
+
+ /* Recherche du point d'insertion idéal */
+ for (node = node->child;
+ node->sibling != NULL && code >= node->sibling->code;
+ node = node->sibling);
+
+ /* Si le noeud idéal n'existe pas, insertion ordonnée */
+ if (code > node->code)
+ {
+ next->parent = parent;
+ next->suffix_link = parent;
+ next->data = source->atoms[k];
+ next->code = code;
+
+ next->sibling = node->sibling;
+ node->sibling = next++;
+
+ if (code < parent->min_child_code) parent->min_child_code = code;
+ if (code > parent->max_child_code) parent->max_child_code = code;
+ parent->children_count++;
+
+ node = node->sibling;
+
+ k++;
+ break;
+
+ }
+
+ }
+
+ /* Si un atome (partiellement ?) identique a déjà été inscrit */
+ if (k == source->len)
+ {
+ /**
+ * L'atome déjà inscrit est plus long, et on se trouve ici dans le
+ * parcours de l'arborescence qui mène à sa conclusion, sans
+ * inscription d'une fin de parcours au point courant.
+ */
+ if (node->matched_atom == 0)
+ goto register_leaf;
+
+ /**
+ * Rattachement au motif strictement identique.
+ */
+ else
+ {
+ assert(backend->sources[node->matched_atom - 1].is_first);
+
+ source->is_first = false;
+ source->first_source = node->matched_atom - 1;
+ source->index = backend->sources[source->first_source].coverage[SOURCE_COVERAGE_COUNT]++;
+
+ }
+
+ }
+
+ else
+ {
+ /* Creéation d'une nouvelle branche avec le reliquat */
+ for (; k < source->len; k++)
+ {
+#ifdef __USE_BYTE_FREQ
+ code = backend->codes_for_bytes[source->atoms[k]];
+#else
+ code = 1 + source->atoms[k];
+#endif
+
+ next->parent = node;
+ next->suffix_link = node;
+ next->data = source->atoms[k];
+ next->code = code;
+
+ node->child = next++;
+
+ if (code < node->min_child_code) node->min_child_code = code;
+ if (code > node->max_child_code) node->max_child_code = code;
+ node->children_count++;
+
+ node = node->child;
+
+ }
+
+ register_leaf:
+
+ node->matched_atom = i + 1;
+
+ source->is_first = true;
+ source->coverage[SOURCE_COVERAGE_COUNT] = 1;
+
+ }
+
+ }
+
+ backend->nodes_used = next - backend->nodes;
+
+ /* Construction des bases pour identifiants */
+
+ current_start = 0;
+
+ for (i = 0; i < backend->sources_count; i++)
+ {
+ source = &backend->sources[i];
+
+ if (source->is_first)
+ {
+ source->coverage[SOURCE_COVERAGE_START] = current_start;
+
+ current_start += source->coverage[SOURCE_COVERAGE_COUNT];
+
+ }
+
+ }
+
+ assert(current_start == backend->sources_count);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = moteur de recherche à préparer. *
+* *
+* Description : Construit l'arborescence de noeuds de lecture. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_acism_backend_build_suffix_links(GAcismBackend *backend)
+{
+ size_t max_pos; /* Tête de lecture finale */
+ acism_trie_node_t **stack; /* Pile des noeuds à traiter */
+ size_t rd_pos; /* Tête de lecture */
+ size_t wr_pos; /* Tête d'écriture */
+ acism_trie_node_t *node; /* Noeud à traiter */
+ acism_trie_node_t *parent; /* Noeud parent de la chaîne */
+ acism_trie_node_t *iter; /* Boucle de parcours */
+
+ max_pos = backend->nodes_used;
+
+ stack = calloc(max_pos, sizeof(acism_trie_node_t *));
+
+ /* Initialisation du parcours */
+
+ rd_pos = 0;
+ wr_pos = 0;
+
+ stack[wr_pos++] = &backend->nodes[0];
+
+ assert(backend->nodes->sibling == NULL);
+
+ /* Traitement manuel de démarrage pour éviter une condition en [0] */
+
+ for (iter = backend->nodes->child; iter != NULL; iter = iter->sibling)
+ stack[wr_pos++] = iter;
+
+ rd_pos++;
+
+ /* Suivi des liens déjà en place */
+
+ while (rd_pos < max_pos)
+ {
+ assert(rd_pos < wr_pos);
+
+ node = stack[rd_pos++];
+
+ /* Remontée jusqu'à la découverte d'un lien d'intérêt */
+
+ for (parent = node->suffix_link; parent != NULL; parent = parent->suffix_link)
+ {
+ for (iter = parent->child; iter != NULL; iter = iter->sibling)
+ if (iter->code == node->code && iter != node)
+ {
+ node->suffix_link = iter;
+ break;
+ }
+
+ if (iter != NULL)
+ break;
+
+ }
+
+ if (parent == NULL /* && node != &backend->nodes [0] */)
+ node->suffix_link = backend->nodes;
+
+ /* Inscription des noeuds suivants */
+
+ for (iter = node->child; iter != NULL; iter = iter->sibling)
+ stack[wr_pos++] = iter;
+
+ }
+
+ /* Sortie propre */
+
+ free(stack);
+
+}
+
+
+#ifdef __SORT_BEFORE_BITMASK
+
+
+/******************************************************************************
+* *
+* Paramètres : a = premier élément à comparer. *
+* b = second élément à comparer. *
+* *
+* Description : Compare des noeuds selon l'espace de codes couvert. *
+* *
+* Retour : Bilan de la comparaison. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static int compare_node_according_to_code_range(const acism_trie_node_t **a, const acism_trie_node_t **b)
+{
+ int result; /* Bilan à retourner */
+ const acism_trie_node_t *_a; /* Autre vision de l'élément #1*/
+ const acism_trie_node_t *_b; /* Autre vision de l'élément #1*/
+ acism_code_t range_a; /* Espacement des codes #1 */
+ acism_code_t range_b; /* Espacement des codes #2 */
+
+ result = 0;
+
+ _a = *a;
+ _b = *b;
+
+ if (_a->child == NULL)
+ result = (_b->child == NULL ? 0 : 1);
+
+ else if (_b->child == NULL)
+ result = (_a->child == NULL ? 0 : -1);
+
+ else
+ {
+ assert(_a->min_child_code <= _a->max_child_code);
+ range_a = _a->max_child_code - _a->min_child_code;
+
+ assert(_b->min_child_code <= _b->max_child_code);
+ range_b = _b->max_child_code - _b->min_child_code;
+
+ result = sort_unsigned_long(range_b, range_a);
+
+ if (result == 0)
+ result = sort_unsigned_long(_b->children_count, _a->children_count);
+
+ }
+
+ return result;
+
+}
+
+
+#endif
+
+
+#if 1
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = moteur de recherche à préparer. *
+* *
+* Description : Organise la convertion de l'arborescence en tableau. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
+{
+#ifdef __SORT_BEFORE_BITMASK
+ acism_trie_node_t **list; /* Liste de noeuds alloués */
+#endif
+ size_t i; /* Boucle de parcours #1 */
+ size_t last_free_state; /* Dernier emplacement dispo. */
+ size_t full_size; /* Cartographie entière */
+ bitfield_t *global_usage; /* Cartographie des usages */
+#ifndef NDEBUG
+ size_t pops[3]; /* Décomptes individuels */
+ size_t bsum; /* Somme de tous les bits */
+#endif
+ bitfield_t *usage; /* Cartographie locale */
+ acism_trie_node_t *node; /* Noeud en cours de traitement*/
+ size_t highest; /* Poids du bit le plus fort */
+ acism_trie_node_t *iter; /* Boucle de parcours #2 */
+ size_t first_freedom_word; /* Premier mot avec des dispos.*/
+ size_t free_state; /* Emplacement libre trouvé */
+
+ /* Préparation de la liste de noeuds à inscrire */
+
+#ifdef __SORT_BEFORE_BITMASK
+
+ list = calloc(backend->nodes_used, sizeof(acism_trie_node_t *));
+
+ for (i = 0; i < backend->nodes_used; i++)
+ list[i] = backend->nodes + i;
+
+ qsort(list + 1, backend->nodes_used - 1, sizeof(acism_trie_node_t *),
+ (__compar_fn_t)compare_node_according_to_code_range);
+
+#endif
+
+ /* Insertion des noeuds dans l'ordre prévu */
+
+ last_free_state = 257;
+ full_size = last_free_state + 257;
+ global_usage = create_bit_field(full_size, false);
+
+#ifndef NDEBUG
+
+ pops[0] = 0;
+ pops[1] = 0;
+ pops[2] = 0;
+
+ bsum = 0;
+
+#endif
+
+ usage = create_bit_field(257, false);
+
+ for (i = 0; i < backend->nodes_used; i++)
+ {
+#ifdef __SORT_BEFORE_BITMASK
+ node = list[i];
+#else
+ node = backend->nodes + i;
+#endif
+
+ /* Préparation du masque du noeud */
+
+ truncate_bit_field(&usage, 257);
+
+ reset_all_in_bit_field(usage);
+
+ set_in_bit_field(usage, 0, 1);
+
+#ifndef NDEBUG
+ pops[0]++;
+#endif
+
+ highest = 0;
+
+ for (iter = node->child; iter != NULL; iter = iter->sibling)
+ {
+ set_in_bit_field(usage, iter->code, 1);
+
+#ifndef NDEBUG
+ pops[0]++;
+#endif
+
+ if (iter->code > highest)
+ highest = iter->code;
+
+ }
+
+#ifndef NDEBUG
+ pops[1] += popcount_for_bit_field(usage);
+#endif
+
+ assert(popcount_for_bit_field(usage) == (node->children_count + 1));
+
+ truncate_bit_field(&usage, ++highest);
+
+ /* Recherche d'une position idéale */
+
+ if (i == 0)
+ {
+ first_freedom_word = 0;
+ free_state = 0;
+ }
+
+ else
+ free_state = find_interleaving_index_for_acism(global_usage, usage, &first_freedom_word);
+
+ /* Suivi global */
+
+ assert(!test_in_bit_field(global_usage, free_state));
+
+ or_bit_field_at(global_usage, usage, free_state);
+
+#ifndef NDEBUG
+ bsum += node->children_count + 1;
+ assert(popcount_for_bit_field(global_usage) == bsum);
+#endif
+
+ node->state_index = free_state;
+
+ if ((free_state + 257) > last_free_state)
+ {
+ last_free_state += 257;
+ full_size += 257;
+ resize_bit_field(&global_usage, full_size);
+ }
+
+ }
+
+ /* Sotie encadrée */
+
+#ifndef NDEBUG
+
+ pops[2] = popcount_for_bit_field(global_usage);
+
+ assert(pops[0] == pops[1]);
+ assert(pops[0] == pops[2]);
+
+#endif
+
+ backend->bitmap_usage = global_usage;
+
+ delete_bit_field(usage);
+
+#ifdef __SORT_BEFORE_BITMASK
+ free(list);
+#endif
+
+}
+
+
+#else
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = moteur de recherche à préparer. *
+* *
+* Description : Organise la convertion de l'arborescence en tableau. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
+{
+ size_t max_pos; /* Tête de lecture finale */
+ acism_trie_node_t **stack; /* Pile des noeuds à traiter */
+ size_t last_free_state; /* Dernier emplacement dispo. */
+ size_t full_size; /* Cartographie entière */
+ bitfield_t *global_usage; /* Cartographie des usages */
+ bitfield_t *usage; /* Cartographie locale */
+ size_t rd_pos; /* Tête de lecture */
+ size_t wr_pos; /* Tête d'écriture */
+ size_t first_freedom_word; /* Premier mot avec des dispos.*/
+ acism_trie_node_t *node; /* Noeud à traiter */
+ acism_trie_node_t *iter; /* Boucle de parcours */
+ size_t free_state; /* Emplacement libre trouvé */
+
+ max_pos = backend->nodes_used;
+
+ stack = calloc(max_pos, sizeof(acism_trie_node_t *));
+
+ last_free_state = 257;
+ full_size = last_free_state + 257;
+ global_usage = create_bit_field(full_size, false);
+
+ usage = create_bit_field(257, false);
+
+ /* Initialisation du parcours */
+
+ rd_pos = 0;
+ wr_pos = 0;
+
+ stack[wr_pos++] = &backend->nodes[0];
+
+ assert(backend->nodes->sibling == NULL);
+
+ /* Traitement manuel de démarrage pour éviter une condition en [0] */
+
+ set_in_bit_field(global_usage, 0, 1);
+
+ for (iter = backend->nodes->child; iter != NULL; iter = iter->sibling)
+ {
+ set_in_bit_field(global_usage, iter->code, 1);
+ stack[wr_pos++] = iter;
+ }
+
+ rd_pos++;
+
+ first_freedom_word = 0;
+
+ /* Suivi des liens déjà en place */
+
+ while (rd_pos < max_pos)
+ {
+ assert(rd_pos < wr_pos);
+
+ node = stack[rd_pos++];
+
+ /* Préparation du masque du noeud et inscription des noeuds suivants */
+
+ reset_all_in_bit_field(usage);
+
+ set_in_bit_field(usage, 0, 1);
+
+ for (iter = node->child; iter != NULL; iter = iter->sibling)
+ {
+ set_in_bit_field(usage, iter->code, 1);
+ stack[wr_pos++] = iter;
+ }
+
+ assert(popcount_for_bit_field(usage) == (node->children_count + 1));
+
+ /* Recherche d'une position idéale */
+
+ free_state = find_interleaving_index_for_acism(global_usage, usage, &first_freedom_word);
+
+ /* Suivi global */
+
+ assert(!test_in_bit_field(global_usage, free_state));
+
+ or_bit_field_at(global_usage, usage, free_state);
+
+ node->state_index = free_state;
+
+ if ((free_state + 257) > last_free_state)
+ {
+ last_free_state += 257;
+ full_size += 257;
+ resize_bit_field(&global_usage, full_size);
+ }
+
+ }
+
+ /* Sotie encadrée */
+
+ backend->bitmap_usage = global_usage;
+
+ delete_bit_field(usage);
+
+ free(stack);
+
+}
+
+
+#endif
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = moteur de recherche à préparer. *
+* *
+* Description : Compresse l'arborescence dans un tableau de position. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_acism_backend_build_interleave_array(GAcismBackend *backend)
+{
+ size_t maxsize; /* Taille maximale du tableau */
+ size_t i; /* Boucle de parcours #1 */
+ acism_trie_node_t *node; /* Noeud à transcrire */
+ acism_state_t *base; /* Base d'une série de cellules*/
+ uint32_t *coverage; /* Couverture des inscriptions */
+ acism_source_t *source; /* Définition originelle */
+ acism_trie_node_t *iter; /* Sous-noeud à inscrire #2 */
+ acism_trie_node_t *child; /* Sous-noeud à inscrire #3 */
+ uint16_t offset; /* Décalage local */
+
+ maxsize = get_bit_field_size(backend->bitmap_usage);
+
+ backend->states = calloc(maxsize, sizeof(acism_state_t));
+ backend->coverages = calloc(maxsize, 2 * sizeof(uint32_t));
+
+ for (i = 0; i < backend->nodes_used; i++)
+ {
+ node = &backend->nodes[i];
+ base = backend->states + node->state_index;
+
+ assert(base[0].code == 0);
+ assert(base[0].index == 0);
+
+ if (node->matched_atom > 0)
+ {
+ source = &backend->sources[node->matched_atom - 1];
+
+ base[0].match = 1;
+ base[0].single_source = source->coverage[SOURCE_COVERAGE_COUNT] == 1 ? 1 : 0;
+ base[0].atom_size = backend->sources[node->matched_atom - 1].len - 1;
+
+ coverage = &backend->coverages[node->state_index * 2];
+
+ coverage[SOURCE_COVERAGE_START] = source->coverage[SOURCE_COVERAGE_START];
+ coverage[SOURCE_COVERAGE_END] = coverage[SOURCE_COVERAGE_START] \
+ + source->coverage[SOURCE_COVERAGE_COUNT];
+
+ for (iter = node->parent->suffix_link; iter != NULL; iter = iter->suffix_link)
+ {
+ for (child = iter->child; child != NULL; child = child->sibling)
+ if (child->code == node->code && child->matched_atom > 0)
+ break;
+
+ if (child != NULL)
+ {
+ base[0].suffix = 1;
+ break;
+ }
+
+ }
+
+ }
+
+ base[0].index = i == 0 ? 0 : node->suffix_link->state_index;
+
+ for (child = node->child; child != NULL; child = child->sibling)
+ {
+ offset = child->code;
+
+ assert(base[offset].code == 0);
+ assert(base[offset].index == 0);
+
+ base[offset].code = child->code;
+ base[offset].index = child->state_index;
+
+ }
+
+ }
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = moteur de recherche à préparer. *
+* *
+* Description : Met en ordre les derniers détails avant un premier scan. *
+* *
+* Retour : Bilan de l'opération. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static bool g_acism_backend_warm_up(GAcismBackend *backend)
+{
+ bool result; /* Bilan à retourner */
+
+ result = true;
+
+#ifdef __USE_BYTE_FREQ
+
+ /**
+ * Attribue un identifiant unique pour chaque octet présent dans les
+ * motifs recherchés.
+ */
+ g_acism_backend_define_codes(backend);
+
+#endif
+
+ /**
+ * Construit une arborescence de lecture à partir des différents
+ * octets présents dans les motifs.
+ *
+ * Les couvertures des futurs tableaux de correspondances sont
+ * établies au passage, ouvrant la voie aux définitions d'identifiant
+ * pour les motifs enregistrés.
+ */
+ g_acism_backend_build_trie(backend);
+
+ /**
+ * Met en place les liens suivis en cas d'échec de correspondance
+ * lors de la lecture d'un octet supplémentaire.
+ */
+ g_acism_backend_build_suffix_links(backend);
+
+ /**
+ * Conversion de l'arborescence en tableau plat et compressé.
+ */
+
+ g_acism_backend_prepare_interleave_array(backend);
+
+ g_acism_backend_build_interleave_array(backend);
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = moteur de recherche à manipuler. *
+* tmp_id = identifiants temporaires vers le motif. [OUT] *
+* *
+* Description : Récupère les identifiants finaux pour un motif recherché. *
+* *
+* Retour : Identifiant constitué ou INVALID_PATTERN_ID en cas d'échec. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static patid_t g_acism_backend_build_plain_pattern_id(const GAcismBackend *backend, const uint32_t tmp_id[2])
+{
+ patid_t result; /* Identifiant à retourner */
+ acism_source_t *source; /* Motif d'origine concerné */
+ acism_source_t *reference; /* Renvoi vers un même motif */
+
+ assert(tmp_id[0] < backend->sources_count);
+
+ /**
+ * L'indicateur tmp_id[1] n'est pas utilisé ici.
+ */
+
+ source = backend->sources + tmp_id[0];
+
+ if (source->is_first)
+ result = source->coverage[SOURCE_COVERAGE_START];
+
+ else
+ {
+ reference = backend->sources + source->first_source;
+
+ assert(source->index < reference->coverage[SOURCE_COVERAGE_COUNT]);
+
+ result = reference->coverage[SOURCE_COVERAGE_START] + source->index;
+
+ }
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = moteur de recherche à manipuler. *
+* *
+* Description : Détermine le nombre d'identifiants constitués. *
+* *
+* Retour : Quantité de gestionnaires de suivi à prévoir. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static size_t g_acism_backend_count_plain_pattern_ids(const GAcismBackend *backend)
+{
+ size_t result; /* Quantité à retourner */
+
+ result = backend->sources_count;
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = moteur de recherche à manipuler. *
+* context = lieu d'enregistrement des résultats. *
+* *
+* Description : Parcours un contenu binaire à la recherche de motifs. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_acism_backend_run_scan(const GAcismBackend *backend, GScanContext *context)
+{
+ GBinContent *content; /* Contenu binaire manipulé */
+ phys_t dlen; /* Quantité de données */
+ vmpa2t pos; /* Point de départ ciblé */
+ const bin_t *data; /* Données à analyser */
+#ifdef __USE_BYTE_FREQ
+ acism_code_t codes_for_bytes[256]; /* Copie des codes d'accès */
+#endif
+ acism_state_t *root; /* Racine de l'arborescence */
+ uint32_t *coverages; /* Bornes de suivi de positions*/
+ unsigned int state; /* Tête de lecture courante */
+ phys_t i; /* Boucle de parcours #1 */
+ acism_code_t code; /* Code du caractère courant */
+ unsigned int next; /* Prochaine tête à valider */
+ acism_state_t next_state; /* Prochaine tête à valider */
+ uint32_t k; /* Boucle de parcours #2 */
+ uint32_t final_k; /* Dernier indice à traiter */
+ unsigned int iter; /* Boucle de parcours #3 */
+ acism_state_t test_state; /* Test de validité alternative*/
+ acism_state_t sub_state; /* Test de validité alternative*/
+
+ content = g_scan_context_get_content(context);
+
+ dlen = g_binary_content_compute_size(content);
+
+ g_binary_content_compute_start_pos(content, &pos);
+ data = g_binary_content_get_raw_access(content, &pos, dlen);
+
+ /* Suivi via l'arborescence aplatie */
+
+#ifdef __USE_BYTE_FREQ
+ memcpy(&codes_for_bytes, backend->codes_for_bytes, 256 * sizeof(acism_code_t));
+#endif
+
+ root = backend->states;
+ if (root == NULL) goto done;
+
+ coverages = backend->coverages;
+
+ state = ROOT_STATE_INDEX;
+
+ for (i = 0; i < dlen; i++)
+ {
+#ifdef __USE_BYTE_FREQ
+ code = codes_for_bytes[data[i]];
+#else
+ code = 1 + data[i];
+#endif
+
+ /* Déplacement de la tête de lecture dans l'arborescence */
+
+ retry:
+
+ next = state + code;
+
+ if (root[next].code == code)
+ {
+ next = root[next].index;
+ next_state = root[next];
+ }
+
+ else if (state != ROOT_STATE_INDEX)
+ {
+ state = root[state].index;
+ goto retry;
+ }
+
+ else
+ continue;
+
+ /* Remontée d'éventuels résultats */
+
+ if (next_state.match)
+ {
+ k = coverages[next * 2 + SOURCE_COVERAGE_START];
+
+ if (next_state.single_source)
+ g_scan_context_store_atom_match_end(context, k, i);
+ //g_umem_slice_put_uint64(matches[0/*k*/], i - next_state.atom_size);
+
+ else
+ {
+ final_k = coverages[next * 2 + SOURCE_COVERAGE_END];
+
+ for (; k < final_k; k++)
+ g_scan_context_store_atom_match_end(context, k, i);
+ //g_umem_slice_put_uint64(matches[0/*k*/], i - next_state.atom_size);
+
+ }
+
+ if (next_state.suffix)
+ {
+ for (iter = root[state].index; ; iter = root[iter].index)
+ {
+ test_state = root[iter + code];
+
+ if (test_state.code == code)
+ {
+ sub_state = root[test_state.index];
+
+ if (sub_state.match)
+ {
+ assert(sub_state.atom_size < next_state.atom_size);
+
+ k = coverages[test_state.index * 2 + SOURCE_COVERAGE_START];
+
+ if (sub_state.single_source)
+ g_scan_context_store_atom_match_end(context, k, i);
+ //g_umem_slice_put_uint64(matches[0/*k*/], i - sub_state.atom_size);
+
+ else
+ {
+ final_k = coverages[test_state.index * 2 + SOURCE_COVERAGE_END];
+
+ for (; k < final_k; k++)
+ g_scan_context_store_atom_match_end(context, k, i);
+ //g_umem_slice_put_uint64(matches[0/*k*/], i - sub_state.atom_size);
+
+ }
+
+ }
+
+ }
+
+ if (iter == ROOT_STATE_INDEX)
+ break;
+
+ }
+
+ }
+
+
+ }
+
+ /* Bascule au caractère suivant */
+
+ state = next;
+
+ }
+
+ done:
+
+ g_object_unref(G_OBJECT(content));
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : node = noeud d'arborescence à traiter. *
+* level = profondeur courante. *
+* *
+* Description : Affiche les caractéristques d'un noeud et de ses enfants. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void visit_and_output_node(const acism_trie_node_t *node, unsigned int level)
+{
+ unsigned int i; /* Boucle de parcours #1 */
+ acism_trie_node_t *iter; /* Boucle de parcours #2 */
+
+ for (i = 0; i < level; i++)
+ printf(" ");
+
+ printf(" '%c' (code=%hhu)\n", node->data, node->code);
+
+ for (iter = node->child; iter != NULL; iter = iter->sibling)
+ visit_and_output_node(iter, level + 1);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : backend = moteur de recherche à consulter. *
+* *
+* Description : Imprime quelques faits quant aux éléments mis en place. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_acism_backend_output_stats(const GAcismBackend *backend)
+{
+ printf("nodes used: %zu\n", backend->nodes_used);
+
+ printf("full_size: %zu (real: %zu)\n",
+ get_bit_field_size(backend->bitmap_usage),
+ popcount_for_bit_field(backend->bitmap_usage));
+
+ visit_and_output_node(backend->nodes, 0);
+
+}
generated by cgit v0.11.2-87-g4458 at 2024-04-28 13:06:59 (GMT)