/* Chrysalide - Outil d'analyse de fichiers binaires
* any.c - suite d'octets quelconques
*
* Copyright (C) 2023 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 "any.h"
#include <assert.h>
#include "any-int.h"
/* ------------------------ DECOMPOSITION DE MOTIF RECHERCHE ------------------------ */
/* Initialise la classe des séries d'octets quelconques. */
static void g_scan_token_node_any_class_init(GScanTokenNodeAnyClass *);
/* Initialise une instance de série d'octets quelconques. */
static void g_scan_token_node_any_init(GScanTokenNodeAny *);
/* Supprime toutes les références externes. */
static void g_scan_token_node_any_dispose(GScanTokenNodeAny *);
/* Procède à la libération totale de la mémoire. */
static void g_scan_token_node_any_finalize(GScanTokenNodeAny *);
/* --------------------- IMPLEMENTATION DES FONCTIONS DE CLASSE --------------------- */
/* Inscrit la définition d'un motif dans un moteur de recherche. */
static bool g_scan_token_node_any_enroll(GScanTokenNodeAny *, GEngineBackend *, size_t, size_t *);
/* Transforme les correspondances locales en trouvailles. */
static void g_scan_token_node_any_check_forward(const GScanTokenNodeAny *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *);
/* Transforme les correspondances locales en trouvailles. */
static void g_scan_token_node_any_check_backward(const GScanTokenNodeAny *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *);
/* ---------------------------------------------------------------------------------- */
/* DECOMPOSITION DE MOTIF RECHERCHE */
/* ---------------------------------------------------------------------------------- */
/* Indique le type défini pour une série d'octets quelconque, vide ou non. */
G_DEFINE_TYPE(GScanTokenNodeAny, g_scan_token_node_any, G_TYPE_SCAN_TOKEN_NODE);
/******************************************************************************
* *
* Paramètres : klass = classe à initialiser. *
* *
* Description : Initialise la classe des séries d'octets quelconques. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_scan_token_node_any_class_init(GScanTokenNodeAnyClass *klass)
{
GObjectClass *object; /* Autre version de la classe */
GScanTokenNodeClass *node; /* Version de classe parente */
object = G_OBJECT_CLASS(klass);
object->dispose = (GObjectFinalizeFunc/* ! */)g_scan_token_node_any_dispose;
object->finalize = (GObjectFinalizeFunc)g_scan_token_node_any_finalize;
node = G_SCAN_TOKEN_NODE_CLASS(klass);
node->apply = (apply_scan_token_node_flags_fc)NULL;
node->visit = (visit_scan_token_node_fc)NULL;
node->enroll = (enroll_scan_token_node_fc)g_scan_token_node_any_enroll;
node->check_forward = (check_scan_token_node_fc)g_scan_token_node_any_check_forward;
node->check_backward = (check_scan_token_node_fc)g_scan_token_node_any_check_backward;
}
/******************************************************************************
* *
* Paramètres : any = instance à initialiser. *
* *
* Description : Initialise une instance de série d'octets quelconques. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_scan_token_node_any_init(GScanTokenNodeAny *any)
{
any->min = 0;
any->has_max = false;
}
/******************************************************************************
* *
* Paramètres : any = instance d'objet GLib à traiter. *
* *
* Description : Supprime toutes les références externes. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_scan_token_node_any_dispose(GScanTokenNodeAny *any)
{
G_OBJECT_CLASS(g_scan_token_node_any_parent_class)->dispose(G_OBJECT(any));
}
/******************************************************************************
* *
* Paramètres : any = instance d'objet GLib à traiter. *
* *
* Description : Procède à la libération totale de la mémoire. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_scan_token_node_any_finalize(GScanTokenNodeAny *any)
{
G_OBJECT_CLASS(g_scan_token_node_any_parent_class)->finalize(G_OBJECT(any));
}
/******************************************************************************
* *
* Paramètres : min = éventuelle quantité minimale à retrouver. *
* max = éventuelle quantité maximale à retrouver. *
* *
* Description : Construit un noeud pointant une série d'octets quelconques. *
* *
* Retour : Mécanismes mis en place. *
* *
* Remarques : - *
* *
******************************************************************************/
GScanTokenNode *g_scan_token_node_any_new(const phys_t *min, const phys_t *max)
{
GScanTokenNode *result; /* Structure à retourner */
result = g_object_new(G_TYPE_SCAN_TOKEN_NODE_ANY, NULL);
if (!g_scan_token_node_any_create(G_SCAN_TOKEN_NODE_ANY(result), min, max))
g_clear_object(&result);
return result;
}
/******************************************************************************
* *
* Paramètres : any = séquence d'octets quelconques à initialiser pleinement.*
* min = éventuelle quantité minimale à retrouver. *
* max = éventuelle quantité maximale à retrouver. *
* *
* Description : Met en place un noeud pointant une série d'octets. *
* *
* Retour : Bilan de l'opération. *
* *
* Remarques : - *
* *
******************************************************************************/
bool g_scan_token_node_any_create(GScanTokenNodeAny *any, const phys_t *min, const phys_t *max)
{
bool result; /* Bilan à retourner */
result = true;
if (min != NULL)
any->min = *min;
else
any->min = 0;
if (max != NULL)
{
any->max = *max;
result = (any->min <= any->max);
if (result && any->min == any->max)
result = (any->min > 0);
}
any->has_max = (max != NULL);
return result;
}
/******************************************************************************
* *
* Paramètres : any = séquence d'octets quelconques à étendre. *
* extra = étendue supplémentaire à intégrer. *
* *
* Description : Etend un noeud pointant une série d'octets. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_scan_token_node_any_merge(GScanTokenNodeAny *any, GScanTokenNodeAny *extra)
{
any->min += extra->min;
if (any->has_max && extra->has_max)
any->max += extra->max;
}
/* ---------------------------------------------------------------------------------- */
/* IMPLEMENTATION DES FONCTIONS DE CLASSE */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : node = définition de la bribe à enregistrer. *
* backend = moteur de recherche à préchauffer. *
* maxsize = taille max. des atomes (mise en commun optimisée). *
* slow = niveau de ralentissement induit (0 = idéal). [OUT] *
* *
* Description : Inscrit la définition d'un motif dans un moteur de recherche.*
* *
* Retour : Bilan de l'opération à renvoyer. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool g_scan_token_node_any_enroll(GScanTokenNodeAny *node, GEngineBackend *backend, size_t maxsize, size_t *slow)
{
bool result; /* Statut à retourner */
bool forced; /* Inclusion dans un scan ? */
result = true;
forced = (g_scan_token_node_get_flags(G_SCAN_TOKEN_NODE(node)) & STNF_MAIN);
if (forced)
*slow += (maxsize * 4);
return result;
}
/******************************************************************************
* *
* Paramètres : node = définition de la bribe à manipuler. *
* params = accès direct aux éléments utiles aux validations. *
* cflags = altérations de traitement à respecter. *
* skip = détermine si l'analyse est différée. [OUT] *
* *
* Description : Transforme les correspondances locales en trouvailles. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_scan_token_node_any_check_forward(const GScanTokenNodeAny *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip)
{
ScanTokenNodeFlags flags; /* Particularités du noeud */
bool forced; /* Inclusion dans un scan ? */
phys_t size; /* Quantité d'octets considérés*/
phys_t match_size; /* Taille de correspondance */
phys_t i; /* Boucle de parcours #1 */
match_area_t *space; /* Nouvelle zone à intégrer */
match_area_t *area; /* Correspondance à valider */
match_area_t *next; /* Correspondance suivante */
phys_t after; /* Espace disposible après */
phys_t min_end; /* Fin la plus proche possible */
phys_t max_end; /* Fin la plus éloignée trouvée*/
bool updated; /* Existence de correspondance */
size_t rcount; /* Quantité de bornes présentes*/
const node_offset_range_t *ranges; /* Bornes d'espace à parcourir */
size_t r; /* Boucle de parcours #2 */
phys_t updated_edge; /* Nouvelle bordure de motif */
match_area_t *new_area; /* Copie de correspondance */
if (0x0) printf("=================== CHECK :: %s (skip? %d)\n", __FUNCTION__, *skip);
if (*skip)
return;
flags = g_scan_token_node_get_flags(G_SCAN_TOKEN_NODE(node));
forced = (flags & STNF_MAIN);
assert((!params->initialized && forced) || (params->initialized & !forced));
/**
* La situation forcée correspond au cas particulier d'une définition
* complètement abstraite : ??, ?? ??, etc.
*/
if (forced)
{
size = params->content_end - params->content_start;
if (node->has_max && 0 /* greedy ? */)
{
match_size = node->max;
if (match_size > size)
match_size = node->min;
}
else
match_size = node->min;
/**
* Si le contenu binaire est trop petit pour contenir au moins un enregistrement,
* aucune correspondance n'est enregistrée. Comme le noeud est le principale, ie.
* seul et unique, l'analyse s'arrête ensuite d'elle même.
*
* Si le contenu binaire est suffisamment large, des espaces sont créés et l'analyse
* se termine ensuite. La conservation des espaces n'est donc pas utile, ni réalisée.
*/
if (match_size <= size)
{
size -= (match_size - 1);
assert(cflags & TNCF_UPDATE_IN_PLACE);
for (i = 0; i < size; i++)
{
space = g_umem_slice_alloc(params->allocator);
space->start = params->content_start + i;
space->end = space->start + match_size;
add_tail_match_area(space, ¶ms->main_areas);
}
params->main_count += size;
}
}
/**
* Situation usuelle : des espaces séparent deux noeuds.
*/
else
{
assert(params->initialized);
/**
* Les espaces existants sont à compléter. La présence de tels espaces
* restant à traiter peut provenir d'un aiguillage imposé par un motif
* tel que :
*
* ( aa ?? ?? | bb cc dd ) [0-5] ee ee
*
* Deux espaces sont à considérer avant de rechercher des octets ee :
* [2-7] et [0-5].
*
* Note : ces espaces peuvent être disjoints.
*
* Si aucun espace n'est en place, un est créé.
*/
extend_node_search_offset(¶ms->offset, node->min, node->max, node->has_max);
/**
* Si un décalage enregistré ne peut être consommé par un noeud, les
* résultats sont étendus ici à minima ou maxima.
*/
if (flags & STNF_LAST)
{
assert(offsets_exist(¶ms->offset));
if (0x0) printf(" LIST : %p (sz = %zu)\n", params->main_areas, params->main_count);
for_each_match_area_safe(area, ¶ms->main_areas, next)
{
assert(area->end <= params->content_end);
after = params->content_end - area->end;
if (0x0) printf("---------- iter @ %u -> %u\n", (unsigned int)area->start, (unsigned int)area->end);
min_end = params->content_end;
max_end = params->content_start;
updated = false;
ranges = get_node_search_offset_ranges_2(¶ms->offset, &rcount);
for (r = 0; r < rcount; r++)
{
if (ranges[r].min > after)
continue;
updated_edge = area->end + ranges[r].min;
if (updated_edge < min_end)
min_end = updated_edge;
if (ranges[r].has_max)
{
if (ranges[r].max > after)
updated_edge = params->content_end;
else
updated_edge = area->end + ranges[r].max;
if (updated_edge > max_end)
max_end = updated_edge;
}
updated = true;
}
if (updated)
{
/**
* Si seuls les rejets sont d'intérêt, les correspondances établies
* ne se voient pas mises à jours ni retirées.
*/
if ((cflags & TNCF_KEEP_DISCARDED) == 0)
{
if (cflags & TNCF_UPDATE_IN_PLACE)
area->end = (1 /* greedy */ ? min_end : max_end);
else if (cflags & TNCF_CREATE_NEW)
{
new_area = g_umem_slice_alloc(params->allocator);
*new_area = *area;
new_area->end = (1 /* greedy */ ? min_end : max_end);
add_tail_match_area(new_area, ¶ms->created_areas);
params->created_count++;
}
#ifndef NDEBUG
else
assert(false);
#endif
}
}
else
{
/**
* Si la liste principale doit être mise à jour...
*/
if (cflags & TNCF_UPDATE_IN_PLACE)
{
del_match_area(area, ¶ms->main_areas);
assert(params->main_count > 0);
params->main_count--;
}
/**
* Au cas où le rejet est d'intérêt, l'absence de correspondance
* est conservée dans une liste dédiée.
*/
if (cflags & TNCF_KEEP_DISCARDED)
{
if (cflags & TNCF_UPDATE_IN_PLACE)
{
add_tail_match_area(area, ¶ms->kept_areas);
params->kept_count++;
}
else if (cflags & TNCF_CREATE_NEW)
{
new_area = g_umem_slice_alloc(params->allocator);
*new_area = *area;
new_area->end = (1 /* greedy */ ? min_end : max_end);
add_tail_match_area(new_area, ¶ms->kept_areas);
params->kept_count++;
}
#ifndef NDEBUG
else
assert(false);
#endif
}
}
}
disable_all_ranges_in_node_search_offset(¶ms->offset);
}
}
}
/******************************************************************************
* *
* Paramètres : node = définition de la bribe à manipuler. *
* params = accès direct aux éléments utiles aux validations. *
* cflags = altérations de traitement à respecter. *
* skip = détermine si l'analyse est différée. [OUT] *
* *
* Description : Transforme les correspondances locales en trouvailles. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_scan_token_node_any_check_backward(const GScanTokenNodeAny *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip)
{
ScanTokenNodeFlags flags; /* Particularités du noeud */
#ifndef NDEBUG
bool forced; /* Inclusion dans un scan ? */
#endif
match_area_t *area; /* Correspondance à valider */
match_area_t *next; /* Correspondance suivante */
phys_t before; /* Espace disposible avant */
phys_t min_start; /* Début le plus proche trouvé */
phys_t max_start; /* Début le plus distant trouvé*/
bool updated; /* Existence de correspondance */
size_t rcount; /* Quantité de bornes présentes*/
const node_offset_range_t *ranges; /* Bornes d'espace à parcourir */
size_t r; /* Boucle de parcours */
phys_t updated_edge; /* Nouvelle bordure de motif */
match_area_t *new_area; /* Copie de correspondance */
if (0x0) printf("=================== CHECK :: %s (skip? %d)\n", __FUNCTION__, *skip);
if (*skip)
return;
/**
* En lecture à rebourd, au moins un noeud a été solicité pour analyse (lors
* du sens de lecture normal). Donc l'initialisation a déjà dû avoir lieu.
*/
assert(params->initialized);
flags = g_scan_token_node_get_flags(G_SCAN_TOKEN_NODE(node));
/**
* Si les recherches associées au noeud ont été forcées, alors les traitements
* liés ont déjà été effectués, et l'appel de cette fonction aurait dû être sauté.
*/
#ifndef NDEBUG
forced = (flags & STNF_MAIN);
assert(!forced);
#endif
/**
* Les considérations pour l'extension des espaces en place sont identiques
* à celles formulées dans la fonction g_scan_token_node_any_check_forward().
*/
extend_node_search_offset(¶ms->offset, node->min, node->max, node->has_max);
/**
* Si un décalage enregistré ne peut être consommé par un noeud, les
* résultats sont étendus ici à minima ou maxima.
*/
if (flags & STNF_FIRST)
{
assert(offsets_exist(¶ms->offset));
if (0x0) printf(" LIST : %p (sz = %zu)\n", params->main_areas, params->main_count);
for_each_match_area_safe(area, ¶ms->main_areas, next)
{
assert(params->content_start <= area->start);
before = area->start - params->content_start;
if (0x0) printf("---------- iter @ %u -> %u\n", (unsigned int)area->start, (unsigned int)area->end);
min_start = params->content_start;
max_start = params->content_end;
updated = false;
ranges = get_node_search_offset_ranges_2(¶ms->offset, &rcount);
for (r = 0; r < rcount; r++)
{
if (ranges[r].min > before)
continue;
updated_edge = area->start - ranges[r].min;
if (updated_edge > min_start)
min_start = updated_edge;
if (ranges[r].has_max)
{
if (ranges[r].max > before)
updated_edge = params->content_start;
else
updated_edge = area->start - ranges[r].max;
if (updated_edge < max_start)
max_start = updated_edge;
}
updated = true;
}
if (updated)
{
/**
* Si seuls les rejets sont d'intérêt, les correspondances établies
* ne se voient pas mises à jours ni retirées.
*/
if ((cflags & TNCF_KEEP_DISCARDED) == 0)
{
if (cflags & TNCF_UPDATE_IN_PLACE)
area->start = (1 /* greedy */ ? min_start : max_start);
else if (cflags & TNCF_CREATE_NEW)
{
new_area = g_umem_slice_alloc(params->allocator);
*new_area = *area;
new_area->start = (1 /* greedy */ ? min_start : max_start);
add_tail_match_area(new_area, ¶ms->created_areas);
params->created_count++;
}
#ifndef NDEBUG
else
assert(false);
#endif
}
}
else
{
/**
* Si la liste principale doit être mise à jour...
*/
if (cflags & TNCF_UPDATE_IN_PLACE)
{
del_match_area(area, ¶ms->main_areas);
assert(params->main_count > 0);
params->main_count--;
}
/**
* Au cas où le rejet est d'intérêt, l'absence de correspondance
* est conservée dans une liste dédiée.
*/
if (cflags & TNCF_KEEP_DISCARDED)
{
if (cflags & TNCF_UPDATE_IN_PLACE)
{
add_tail_match_area(area, ¶ms->kept_areas);
params->kept_count++;
}
else if (cflags & TNCF_CREATE_NEW)
{
new_area = g_umem_slice_alloc(params->allocator);
*new_area = *area;
new_area->start = (1 /* greedy */ ? min_start : max_start);
add_tail_match_area(new_area, ¶ms->kept_areas);
params->kept_count++;
}
#ifndef NDEBUG
else
assert(false);
#endif
}
}
}
disable_all_ranges_in_node_search_offset(¶ms->offset);
}
}