summaryrefslogtreecommitdiff
path: root/src/analysis/scan/matches
diff options
context:
space:
mode:
Diffstat (limited to 'src/analysis/scan/matches')
-rw-r--r--src/analysis/scan/matches/pending.c279
-rw-r--r--src/analysis/scan/matches/pending.h36
2 files changed, 263 insertions, 52 deletions
diff --git a/src/analysis/scan/matches/pending.c b/src/analysis/scan/matches/pending.c
index 9d1037d..03cf3f2 100644
--- a/src/analysis/scan/matches/pending.c
+++ b/src/analysis/scan/matches/pending.c
@@ -24,18 +24,80 @@
#include "pending.h"
-#include <assert.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 : 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);
+
+ 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.*
* *
@@ -45,14 +107,84 @@
* *
******************************************************************************/
-void init_pending_matches(pending_matches_t *matches)
+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->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;
+
}
@@ -112,11 +244,11 @@ size_t count_pending_matches(const pending_matches_t *matches)
* *
******************************************************************************/
-const match_area_t *get_all_pending_matches(const pending_matches_t *matches, size_t *count)
+match_area_t * const *get_all_pending_matches(const pending_matches_t *matches, size_t *count)
{
- match_area_t *result; /* Série à renvoyer */
+ match_area_t * const *result; /* Série à renvoyer */
- result = matches->areas;
+ result = &matches->areas;
*count = matches->used;
@@ -156,8 +288,15 @@ void add_pending_match(pending_matches_t *matches, phys_t start, phys_t length)
area->start = start;
area->end = start + length;
+ assert(matches->content_start <= area->start);
+ assert(area->end <= matches->content_end);
+
area->ttl = 1;
+ printf("[i] new match: from %llx to %llx\n",
+ (unsigned long long)area->start,
+ (unsigned long long)area->end);
+
}
@@ -165,7 +304,7 @@ void add_pending_match(pending_matches_t *matches, phys_t start, phys_t length)
* *
* 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. *
+* start = nouvelle position initiale de la zone couverte. *
* *
* Description : Etend une zone couverte dans le suivi des correspondances. *
* *
@@ -175,17 +314,19 @@ void add_pending_match(pending_matches_t *matches, phys_t start, phys_t length)
* *
******************************************************************************/
-void extend_pending_match(pending_matches_t *matches, size_t target, phys_t end)
+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[matches->used++];
+ area = &matches->areas[target];
if (area->ttl == 0)
{
- area->end = end;
+ assert(matches->content_start <= start);
+
+ area->start = start;
area->ttl = 1;
@@ -194,7 +335,7 @@ void extend_pending_match(pending_matches_t *matches, size_t target, phys_t end)
{
assert(area->ttl == 1);
- add_pending_match(matches, area->start, end - area->start);
+ add_pending_match(matches, start, area->end - start);
}
@@ -203,11 +344,11 @@ void extend_pending_match(pending_matches_t *matches, size_t target, phys_t end)
/******************************************************************************
* *
-* Paramètres : matches = suivi de correspondances à consulter. *
+* Paramètres : matches = suivi de correspondances à compléter. *
* target = indice de la zone de correspondance concernée. *
-* pos = position à tester. *
+* length = taille de la zone couverte supplémentaire. *
* *
-* Description : Détermine si une correspondance se termine à une position. *
+* Description : Etend une zone couverte dans le suivi des correspondances. *
* *
* Retour : - *
* *
@@ -215,50 +356,40 @@ void extend_pending_match(pending_matches_t *matches, size_t target, phys_t end)
* *
******************************************************************************/
-bool has_pending_match_ending_at(const pending_matches_t *matches, size_t target, phys_t pos)
+void extend_pending_match_ending(pending_matches_t *matches, size_t target, phys_t end)
{
- bool result; /* Statut à retourner */
- match_area_t *area; /* Couverture visée */
+ match_area_t *area; /* Zone à actualiser */
assert(target < matches->used);
area = &matches->areas[target];
- result = (area->end == pos);
-
- return result;
-
-}
+ if (area->ttl == 0)
+ {
+ assert(end <= matches->content_end);
+ printf(" -- extend same (%llu - %llu) -> new end: %llu\n",
+ (unsigned long long)area->start,
+ (unsigned long long)area->end,
+ (unsigned long long)end);
-/******************************************************************************
-* *
-* Paramètres : matches = suivi de correspondances à consulter. *
-* target = indice de la zone de correspondance concernée. *
-* pos = position à tester. *
-* min = borne inférieure de l'espace à considérer. *
-* max = borne supérieure de l'espace à considérer. *
-* *
-* Description : Détermine si une correspondance se situe dans une plage. *
-* *
-* Retour : - *
-* *
-* Remarques : - *
-* *
-******************************************************************************/
+ area->end = end;
-bool has_pending_match_ending_between(const pending_matches_t *matches, size_t target, phys_t pos, phys_t min, phys_t max)
-{
- bool result; /* Statut à retourner */
- match_area_t *area; /* Couverture visée */
+ area->ttl = 1;
- assert(target < matches->used);
+ }
+ else
+ {
+ assert(area->ttl == 1);
- area = &matches->areas[target];
+ printf(" -- extend (%llu - %llu) -> new end: %llu\n",
+ (unsigned long long)area->start,
+ (unsigned long long)area->end,
+ (unsigned long long)end);
- result = ((area->end + min) <= pos && pos <= (area->end + max));
+ add_pending_match(matches, area->start, end - area->start);
- return result;
+ }
}
@@ -279,6 +410,8 @@ 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;
@@ -305,6 +438,8 @@ void purge_pending_matches(pending_matches_t *matches)
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 :
*
@@ -378,4 +513,60 @@ void purge_pending_matches(pending_matches_t *matches)
}
+ /* 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;
+
+ }
+
}
diff --git a/src/analysis/scan/matches/pending.h b/src/analysis/scan/matches/pending.h
index 0a1fe5c..6df01c9 100644
--- a/src/analysis/scan/matches/pending.h
+++ b/src/analysis/scan/matches/pending.h
@@ -25,6 +25,7 @@
#define _ANALYSIS_SCAN_MATCHES_PENDING_H
+#include <assert.h>
#include <stdbool.h>
@@ -45,17 +46,28 @@ typedef struct _match_area_t
/* Suivi de correspondances */
typedef struct _pending_matches_t
{
+ phys_t content_start; /* Point de début du contenu */
+ phys_t content_end; /* Point de fin du contenu */
+
match_area_t *areas; /* Zones couvertes */
size_t allocated; /* Nombre d'allocations */
size_t used; /* Nombre de zones */
bool initialized; /* Etat du suivi */
+ bool abort; /* Inutilité d'une poursuite */
+
} pending_matches_t;
/* Initialise une structure de consolidation de correspondances. */
-void init_pending_matches(pending_matches_t *);
+void init_pending_matches(pending_matches_t *, const phys_t *, const phys_t *);
+
+/* Copie une structure de consolidation de correspondances. */
+void copy_pending_matches(pending_matches_t *, const pending_matches_t *);
+
+/* Fusionner une structure de consolidation avec une autre. */
+void merge_pending_matches(pending_matches_t *, const pending_matches_t *);
/* Libère la mémoire utilisée par une consolidation. */
void exit_pending_matches(pending_matches_t *);
@@ -69,26 +81,34 @@ void exit_pending_matches(pending_matches_t *);
size_t count_pending_matches(const pending_matches_t *);
/* Fournit la liste des correspondances établies à présent. */
-const match_area_t *get_all_pending_matches(const pending_matches_t *, size_t *);
+match_area_t * const *get_all_pending_matches(const pending_matches_t *, size_t *);
/* Ajoute au suivi la définition d'une nouvelle correspondance. */
void add_pending_match(pending_matches_t *, phys_t, phys_t);
/* Etend une zone couverte dans le suivi des correspondances. */
-void extend_pending_match(pending_matches_t *, size_t, phys_t);
+void extend_pending_match_beginning(pending_matches_t *, size_t, phys_t);
-/* Détermine si une correspondance se situe dans une plage. */
-bool has_pending_match_ending_between(const pending_matches_t *, size_t, phys_t, phys_t, phys_t);
-
-/* Détermine si une correspondance se termine à une position. */
-bool has_pending_match_ending_at(const pending_matches_t *, size_t, phys_t);
+/* Etend une zone couverte dans le suivi des correspondances. */
+void extend_pending_match_ending(pending_matches_t *, size_t, phys_t);
/* Réinitialisation à 0 tous les TTL de correspondances. */
void reset_pending_matches_ttl(pending_matches_t *);
+#define keep_pending_match(p) \
+ do \
+ { \
+ assert(p->ttl == 0); \
+ p->ttl = 1; \
+ } \
+ while (0);
+
/* Retire toutes les correspondances sans issue pour l'analyse. */
void purge_pending_matches(pending_matches_t *);
+/* Trie les correspondances et retire tous les doublons. */
+void sort_and_filter_pending_matches(pending_matches_t *);
+
#endif /* _ANALYSIS_SCAN_MATCHES_PENDING_H */