path: root/src/analysis/scan/patterns/tokens/nodes/any.c

/* 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, &params->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(&params->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(&params->offset));

            if (0x0) printf(" LIST : %p (sz = %zu)\n", params->main_areas, params->main_count);

            for_each_match_area_safe(area, &params->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(&params->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, &params->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, &params->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, &params->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, &params->kept_areas);
                            params->kept_count++;

                        }

#ifndef NDEBUG
                        else
                            assert(false);
#endif

                    }

                }

            }

            disable_all_ranges_in_node_search_offset(&params->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(&params->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(&params->offset));

        if (0x0) printf(" LIST : %p (sz = %zu)\n", params->main_areas, params->main_count);

        for_each_match_area_safe(area, &params->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(&params->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, &params->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, &params->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, &params->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, &params->kept_areas);
                        params->kept_count++;

                    }

#ifndef NDEBUG
                    else
                        assert(false);
#endif

                }

            }

        }

        disable_all_ranges_in_node_search_offset(&params->offset);

    }

}