diff options
author | Cyrille Bagard <nocbos@gmail.com> | 2023-01-30 06:59:35 (GMT) |
---|---|---|
committer | Cyrille Bagard <nocbos@gmail.com> | 2023-01-30 06:59:35 (GMT) |
commit | db3b204dd7a71b2f74a4e69b2159a96e3ab66614 (patch) | |
tree | 34174311b7ac504f03a10a889ada7f28db7a06c0 /src/analysis/scan/patterns/backends/acism.c | |
parent | 34ee1bfca78e8423cfa29329fdc756569d6b1960 (diff) |
Save an initial version of rost.
Diffstat (limited to 'src/analysis/scan/patterns/backends/acism.c')
-rw-r--r-- | src/analysis/scan/patterns/backends/acism.c | 1295 |
1 files changed, 1295 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..12339f2 --- /dev/null +++ b/src/analysis/scan/patterns/backends/acism.c @@ -0,0 +1,1295 @@ + +/* 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 Bitmap. */ +static void g_acism_backend_class_init(GAcismBackendClass *); + +/* Initialise une instance de méthodes basée sur Bitmap. */ +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 patid_t g_acism_backend_setup_for(GAcismBackend *, GScanContext *, const uint8_t *, size_t); + +/* Inscrit dans le moteur une chaîne de caractères à rechercher. */ +static patid_t g_acism_backend_enroll_plain_pattern(GAcismBackend *, GScanContext *, const uint8_t *, size_t); + +#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 void g_acism_backend_warm_up(GAcismBackend *); + +/* Parcours un contenu binaire à la recherche de motifs. */ +static void g_acism_backend_run_scan(const GAcismBackend *, GScanContext *, GBinContent *); + +/* 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 Bitmap. * +* * +* 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->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 Bitmap. * +* * +* 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) +{ + 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. * +* context = contexte de l'analyse à mener. * +* plain = chaîne de caractères classique à intégrer. * +* len = taille de cette chaîne. * +* * +* Description : Intègre un motif limité de contenu à rechercher. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static patid_t g_acism_backend_setup_for(GAcismBackend *backend, GScanContext *context, const uint8_t *pattern, size_t len) +{ + patid_t result; /* Identifiant à retourner */ + size_t i; /* Boucle de parcours */ + int ret; /* Bilan d'une comparaison */ + acism_source_t *source; /* Définition à mémoriser */ + + result = INVALID_PATTERN_ID; + + /*Recherche d'un motif déjà sollicité */ + + /** + * '\x00\x00\x00\x00abcd1234' '\x01\x01\x01\x01abcd1234' peuvent en effet + * constituer deux cibles différentes, mais elles comportent normalement + * la même séquence atomique à rechercher : 'abcd1234'. + */ + + for (i = 0; i < backend->sources_count; i++) + { + source = backend->sources + i; + + if (source->len != len) + continue; + + ret = memcmp(source->atoms, pattern, len); + + if (ret == 0) + { + result = source->pid; + break; + } + + } + + /* Introduction d'un nouveau motif au besoin */ + + if (result == INVALID_PATTERN_ID) + { + backend->sources = realloc(backend->sources, ++backend->sources_count * sizeof(acism_source_t)); + + source = &backend->sources[backend->sources_count - 1]; + + source->atoms = pattern; + source->len = len; + + result = g_scan_context_get_new_pattern_id(context); + source->pid = result; + + backend->nchars += len; + +#ifdef __USE_BYTE_FREQ + for (i = 0; i < len; i++) + backend->frequencies[pattern[i]].frequency++; +#endif + + } + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* context = contexte de l'analyse à mener. * +* plain = chaîne de caractères classique à intégrer. * +* len = taille de cette chaîne. * +* * +* Description : Inscrit dans le moteur une chaîne de caractères à rechercher.* +* * +* Retour : Bilan de l'opération. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static patid_t g_acism_backend_enroll_plain_pattern(GAcismBackend *backend, GScanContext *context, const uint8_t *plain, size_t len) +{ + patid_t result; /* Identifiant à retourner */ + + assert(len <= ACSIM_ATOM_SIZE); + + /** + * 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. + */ + + result = g_acism_backend_setup_for(backend, context, plain, len); + + 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++; + +#if 0 + for (i = 0, iter = backend->frequencies; i < 256; i++, iter++) + { + if (iter->frequency == 0) + break; + + backend->codes_for_bytes[iter->rank] = backend->codes_count++; + + } +#else + for (i = 0; i < 256; i++) + backend->codes_for_bytes[i] = backend->codes_count++; +#endif + +} + + +#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 */ + + 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]; + + 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; + + } + + } + + /* 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; + + } + + node->matched_atom = i + 1; + + } + + backend->nodes_used = next - backend->nodes; + +} + + +/****************************************************************************** +* * +* 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 */ + bitfield_t *usage; /* Cartographie locale */ + acism_trie_node_t *node; /* Noeud en cours de traitement*/ + acism_trie_node_t *iter; /* Boucle de parcours #2 */ + size_t free_state; /* Emplacement libre trouvé */ + bool found; /* Bilan de recherche */ + + size_t bsum; + + /* 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); + + bsum = 0; + + 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 */ + + 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); + + assert(popcount_for_bit_field(usage) == (node->children_count + 1)); + + /* Recherche d'une position idéale */ + + if (i == 0) + free_state = 0; + + else + for (free_state = 1; free_state < last_free_state; free_state++) + { + found = test_zeros_within_bit_field(global_usage, free_state, usage); + if (found) break; + } + + /* Suivi global */ + + assert(!test_in_bit_field(global_usage, free_state)); + + or_bit_field_at(global_usage, usage, free_state); + + bsum += node->children_count + 1; + assert(popcount_for_bit_field(global_usage) == bsum); + + 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); + +#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 */ + acism_trie_node_t *node; /* Noeud à traiter */ + acism_trie_node_t *iter; /* Boucle de parcours */ + size_t free_state; /* Emplacement libre trouvé */ + bool found; /* Bilan de recherche */ + + 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++; + + /* 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 */ + + for (free_state = 1; free_state < last_free_state; free_state++) + { + found = test_zeros_within_bit_field(global_usage, free_state, usage); + if (found) break; + } + + /* 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*/ + 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->pids = calloc(maxsize, sizeof(patid_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) + { + base[0].match = 1; + base[0].atom_size = backend->sources[node->matched_atom - 1].len; + + backend->pids[node->state_index] = backend->sources[node->matched_atom - 1].pid; + + 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 : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_acism_backend_warm_up(GAcismBackend *backend) +{ +#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. + */ + 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); + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* context = lieu d'enregistrement des résultats. * +* content = données binaires à analyser. * +* * +* 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) +{ + 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; +#endif + acism_state_t *root; /* Racine de l'arborescence */ + acism_state_t *state; /* Tête de lecture courante */ + phys_t i; /* Boucle de parcours #1 */ + acism_code_t code; /* Code du caractère courant */ + acism_state_t *next; /* Prochaine tête à valider */ + acism_state_t *iter; /* Boucle de parcours #2 */ + acism_state_t *test; /* Test de validité alternative*/ + + 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 + codes_for_bytes = backend->codes_for_bytes; +#endif + + root = backend->states; + + state = root; + + for (i = 0; i < dlen; i++) + { +#ifdef __USE_BYTE_FREQ + code = 1 + 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 (next->code == code) + next = root + next->index; + + else if (state != root) + { + state = root + state->index; + goto retry; + } + + else + continue; + + /* Remontée d'éventuels résultats */ + + if (next->match) + { + g_scan_context_register_atom_match(context, + backend->pids[next - root], + i + 1 - next->atom_size); + + if (next->suffix) + { + for (iter = root + state->index; ; iter = root + iter->index) + { + test = iter + code; + + if (test->code == code) + { + test = root + test->index; + + if (test->match) + { + assert(test->atom_size < next->atom_size); + + g_scan_context_register_atom_match(context, + backend->pids[test - root], + i + 1 - test->atom_size); + + } + + } + + if (iter == root) + break; + + } + + } + + + } + + /* Bascule au caractère suivant */ + + state = next; + + } + +} + + +/****************************************************************************** +* * +* 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); + +} |