summaryrefslogtreecommitdiff
path: root/src/analysis/scan/matches/pending.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/analysis/scan/matches/pending.c')
-rw-r--r--src/analysis/scan/matches/pending.c677
1 files changed, 677 insertions, 0 deletions
diff --git a/src/analysis/scan/matches/pending.c b/src/analysis/scan/matches/pending.c
new file mode 100644
index 0000000..c653257
--- /dev/null
+++ b/src/analysis/scan/matches/pending.c
@@ -0,0 +1,677 @@
+
+/* Chrysalide - Outil d'analyse de fichiers binaires
+ * pending.c - consolidation de correspondances partielles
+ *
+ * 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 "pending.h"
+
+
+#include <malloc.h>
+#include <stdlib.h>
+#include <string.h>
+
+
+#include "../../../common/sort.h"
+
+
+
+
+
+/* ------------------------- MEMORISATION D'UNE ZONE BORNEE ------------------------- */
+
+
+/* Compare deux couvertures bornées de correspondances. */
+static int compare_match_area(const match_area_t *, const match_area_t *);
+
+
+
+/* -------------------- CONSERVATION DE CORRESPONDANCES ETABLIES -------------------- */
+
+
+#define PENDING_ALLOC_SIZE 10
+
+
+
+
+
+/* ---------------------------------------------------------------------------------- */
+/* MEMORISATION D'UNE ZONE BORNEE */
+/* ---------------------------------------------------------------------------------- */
+
+
+/******************************************************************************
+* *
+* Paramètres : allocator = allocateur dédié à l'ensemble de zones. *
+* start = point de départ d'une nouvelle correspondance. *
+* length = taille de la zone couverte. *
+* *
+* Description : Crée une nouvelle structure de suivi de correspondance. *
+* *
+* Retour : Structure initialisée mise en place. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static match_area_t *create_match_area(GUMemCache *allocator, phys_t start, phys_t length)
+{
+ match_area_t *result; /* Zone à retourner */
+
+ result = g_umem_cache_alloc(allocator);
+
+ DL_LIST_ITEM_INIT(&result->link);
+
+ result->start = start;
+ result->end = start + length;
+
+ assert(matches->content_start <= result->start);
+ assert(result->end <= matches->content_end);
+
+ result->ttl = 1;
+
+ result->has_mod_path = false;
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : allocator = allocateur dédié à l'ensemble de zones. *
+* start = point de départ d'une nouvelle correspondance. *
+* length = taille de la zone couverte. *
+* index = indice de construction pour le motif concerné. *
+* *
+* Description : Crée une nouvelle structure de suivi de correspondance. *
+* *
+* Retour : Structure initialisée mise en place. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static match_area_t *create_match_area_with_path(GUMemCache *allocator, phys_t start, phys_t length, size_t index)
+{
+ match_area_t *result; /* Zone à retourner */
+
+ result = g_umem_cache_alloc(allocator);
+
+ DL_LIST_ITEM_INIT(&result->link);
+
+ result->start = start;
+ result->end = start + length;
+
+ assert(matches->content_start <= result->start);
+ assert(result->end <= matches->content_end);
+
+ result->ttl = 1;
+
+ result->mod_path_index = index;
+ result->has_mod_path = true;
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : area = zone de suivi à supprimer. *
+* allocator = allocateur dédié à l'ensemble de zones. *
+* *
+* Description : Supprime une structure de suivi de correspondance. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void delete_match_area(match_area_t *area, GUMemCache *allocator)
+{
+ // TODO : assert(alone)
+
+ g_umem_cache_free(allocator, area);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : a = pointeur vers la première zone à analyser. *
+* b = pointeur vers la seconde zone à analyser. *
+* *
+* Description : Compare deux couvertures bornées de correspondances. *
+* *
+* Retour : Bilan de la comparaison. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static int compare_match_area(const match_area_t *a, const match_area_t *b)
+{
+ int result; /* Bilan à renvoyer */
+
+ result = sort_unsigned_long_long(a->start, b->start);
+
+ if (result == 0)
+ result = sort_unsigned_long_long(a->end, b->end);
+
+ if (result == 0)
+ result = sort_unsigned_long_long(a->ttl, b->ttl);
+
+ if (result == 0)
+ result = sort_unsigned_long_long(a->has_mod_path, b->has_mod_path);
+
+ if (result == 0)
+ result = sort_unsigned_long_long(a->mod_path_index, b->mod_path_index);
+
+ return result;
+
+}
+
+
+
+/* ---------------------------------------------------------------------------------- */
+/* CONSERVATION DE CORRESPONDANCES ETABLIES */
+/* ---------------------------------------------------------------------------------- */
+
+
+/******************************************************************************
+* *
+* Paramètres : matches = suivi de correspondances à initialiser. *
+* start = première position du contenu (souvent 0). *
+* end = position de fin du contenu. *
+* *
+* Description : Initialise une structure de consolidation de correspondances.*
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void init_pending_matches(pending_matches_t *matches, const phys_t *start, const phys_t *end)
+{
+ matches->content_start = *start;
+ matches->content_end = *end;
+
+ matches->allocator = NULL;
+ matches->areas = NULL;
+ matches->allocated = 0;
+ matches->used = 0;
+
+ matches->initialized = false;
+
+ matches->abort = false;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : dest = suivi de correspondances à initialiser. [OUT] *
+* src = suivi de correspondances à copier. *
+* *
+* Description : Copie une structure de consolidation de correspondances. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void copy_pending_matches(pending_matches_t *dest, const pending_matches_t *src)
+{
+ dest->content_start = src->content_start;
+ dest->content_end = src->content_end;
+
+ dest->areas = malloc(src->used * sizeof(match_area_t));
+ dest->allocated = src->used;
+ dest->used = src->used;
+
+ memcpy(dest->areas, src->areas, src->used * sizeof(match_area_t));
+
+ dest->initialized = src->initialized;
+
+ dest->abort = src->abort;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : dest = suivi de correspondances à initialiser. [OUT] *
+* src = suivi de correspondances à copier. *
+* *
+* Description : Fusionne une structure de consolidation avec une autre. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void merge_pending_matches(pending_matches_t *dest, const pending_matches_t *src)
+{
+ if ((dest->used + src->used) > dest->allocated)
+ {
+ dest->allocated += src->used;
+
+ dest->areas = realloc(dest->areas, dest->allocated * sizeof(match_area_t));
+
+ }
+
+ memcpy(&dest->areas[dest->used], src->areas, src->used * sizeof(match_area_t));
+
+ dest->used += src->used;
+
+ dest->initialized |= src->initialized;
+
+ dest->abort |= src->abort;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : matches = suivi de correspondances à purger. *
+* *
+* Description : Libère la mémoire utilisée par une consolidation. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void exit_pending_matches(pending_matches_t *matches)
+{
+ if (matches->areas != NULL)
+ free(matches->areas);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : matches = suivi de correspondances à consulter. *
+* *
+* Description : Dénombre les correspondances établies jusque là. *
+* *
+* Retour : Quantité de correspondances complètes jusqu'à présent. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+size_t count_pending_matches(const pending_matches_t *matches)
+{
+ size_t result; /* Quantité à renvoyer */
+
+ result = matches->used;
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : matches = suivi de correspondances à consulter. *
+* count = nombre de correspondances en attente. [OUT] *
+* *
+* Description : Fournit la liste des correspondances établies à présent. *
+* *
+* Retour : Liste de correspondances en lecture seule. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+match_area_t * const *get_all_pending_matches(const pending_matches_t *matches, size_t *count)
+{
+ match_area_t * const *result; /* Série à renvoyer */
+
+ result = &matches->areas;
+
+ *count = matches->used;
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : matches = suivi de correspondances à compléter. *
+* start = point de départ d'une nouvelle correspondance. *
+* length = taille de la zone couverte. *
+* *
+* Description : Ajoute au suivi la définition d'une nouvelle correspondance. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void add_pending_match(pending_matches_t *matches, phys_t start, phys_t length)
+{
+ match_area_t *area; /* Nouvelle zone à intégrer */
+
+ area = create_match_area(matches->allocator, start, length);
+
+ dl_list_add_tail(area, &matches->areas, match_area_t, link);
+ matches->used++;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : matches = suivi de correspondances à compléter. *
+* start = point de départ d'une nouvelle correspondance. *
+* length = taille de la zone couverte. *
+* index = indice de construction pour le motif concerné. *
+* *
+* Description : Ajoute au suivi la définition d'une nouvelle correspondance. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void add_pending_match_with_path(pending_matches_t *matches, phys_t start, phys_t length, size_t index)
+{
+ match_area_t *area; /* Nouvelle zone à intégrer */
+
+ area = create_match_area_with_path(matches->allocator, start, length, index);
+
+ dl_list_add_tail(area, &matches->areas, match_area_t, link);
+ matches->used++;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : matches = suivi de correspondances à compléter. *
+* target = indice de la zone de correspondance concernée. *
+* start = nouvelle position initiale de la zone couverte. *
+* *
+* Description : Etend une zone couverte dans le suivi des correspondances. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void extend_pending_match_beginning(pending_matches_t *matches, size_t target, phys_t start)
+{
+ match_area_t *area; /* Zone à actualiser */
+
+ assert(target < matches->used);
+
+ area = &matches->areas[target];
+
+ if (area->ttl == 0)
+ {
+ assert(matches->content_start <= start);
+
+ area->start = start;
+
+ area->ttl = 1;
+
+ }
+ else
+ {
+ assert(area->ttl == 1);
+
+ add_pending_match(matches, start, area->end - start);
+
+ }
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : matches = suivi de correspondances à compléter. *
+* target = indice de la zone de correspondance concernée. *
+* length = taille de la zone couverte supplémentaire. *
+* *
+* Description : Etend une zone couverte dans le suivi des correspondances. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void extend_pending_match_ending(pending_matches_t *matches, size_t target, phys_t end)
+{
+ match_area_t *area; /* Zone à actualiser */
+
+ assert(target < matches->used);
+
+ area = &matches->areas[target];
+
+ if (area->ttl == 0)
+ {
+ assert(end <= matches->content_end);
+
+ area->end = end;
+
+ area->ttl = 1;
+
+ }
+ else
+ {
+ assert(area->ttl == 1);
+
+ add_pending_match(matches, area->start, end - area->start);
+
+ }
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : matches = suivi de correspondances à modifier. *
+* *
+* Description : Réinitialisation à 0 tous les TTL de correspondances. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void reset_pending_matches_ttl(pending_matches_t *matches)
+{
+ size_t i; /* Boucle de parcours */
+
+ assert(matches->initialized);
+
+ for (i = 0; i < matches->used; i++)
+ matches->areas[i].ttl = 0;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : matches = suivi de correspondances à modifier. *
+* *
+* Description : Retire toutes les correspondances sans issue pour l'analyse. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void purge_pending_matches(pending_matches_t *matches)
+{
+ match_area_t *del_start; /* Départ d'une zone morte */
+ match_area_t *del_end; /* Fin d'une zone morte */
+ size_t del_remaining; /* Nombre de valides ensuite */
+ size_t del_count; /* Nombre d'éléments à effacer */
+ size_t i; /* Boucle de parcours */
+
+ assert(matches->initialized);
+
+ /**
+ * Note : le code original était le suivant :
+ *
+
+ * for (i = matches->used; i > 0; i--)
+ * if (matches->areas[i - 1].ttl == 0)
+ * {
+ * memmove(&matches->areas[i - 1], &matches->areas[i], (matches->used - i) * sizeof(match_area_t));
+ * matches->used--;
+ * }
+ *
+ * Pour éviter les appels à memmove(), un déplacement par blocs est désormais visée.
+ */
+
+ del_start = NULL;
+ del_end = NULL;
+ del_count = 0;
+ del_remaining = 0;
+
+ /* Suppression en bloc si possible */
+
+ for (i = matches->used; i > 0; i--)
+ {
+ if (matches->areas[i - 1].ttl == 0)
+ {
+ del_start = &matches->areas[i - 1];
+
+ if (del_end == NULL)
+ {
+ del_end = del_start;
+ del_remaining = matches->used - i;
+ }
+
+ del_count++;
+
+ }
+ else
+ {
+ if (del_start != NULL)
+ {
+ assert(&matches->areas[i] == del_start);
+
+ if (del_remaining > 0)
+ memmove(del_start, del_end + 1, del_remaining * sizeof(match_area_t));
+
+ assert(matches->used > del_count);
+ matches->used -= del_count;
+
+ del_start = NULL;
+ del_end = NULL;
+ del_count = 0;
+ del_remaining = 0;
+
+ }
+
+ }
+
+ }
+
+ /* Dernier traitement au besoin */
+
+ if (del_start != NULL)
+ {
+ assert(&matches->areas[0] == del_start);
+
+ if (del_remaining > 0)
+ memmove(del_start, del_end + 1, del_remaining * sizeof(match_area_t));
+
+ assert(matches->used >= del_count);
+ matches->used -= del_count;
+
+ }
+
+ /* Bilan */
+
+ matches->abort = (matches->used == 0);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : matches = suivi de correspondances à finaliser. *
+* *
+* Description : Trie les correspondances et retire tous les doublons. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void sort_and_filter_pending_matches(pending_matches_t *matches)
+{
+ match_area_t *last; /* Dernière zone conservée */
+ size_t i; /* Boucle de parcours */
+ match_area_t *cur; /* Zone courante dans l'analyse*/
+
+ if (matches->used > 0)
+ {
+ qsort(matches->areas, matches->used, sizeof(match_area_t), (__compar_fn_t)compare_match_area);
+
+ last = &matches->areas[0];
+
+ for (i = 1; i < matches->used; i++)
+ {
+ cur = &matches->areas[i];
+
+ if (last->start != cur->start || last->end != cur->end)
+ {
+ if ((cur - last) > 1)
+ {
+ memmove(last + 1, cur, (matches->used - i) * sizeof(match_area_t));
+ matches->used -= (cur - last + 1);
+ }
+
+ last = cur;
+
+ }
+
+ }
+
+ cur = &matches->areas[matches->used - 1];
+
+ if (last != cur)
+ matches->used = last - matches->areas + 1;
+
+ }
+
+}
generated by cgit v0.11.2-87-g4458 at 2024-04-27 14:25:27 (GMT)