/* 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 .
*/
#include "acism.h"
#include
#include
#include
#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);
}