Optimized the search of instructions a little bit using routine coverages.

git-svn-id: svn://svn.gna.org/svn/chrysalide/trunk@587 abbe820e-26c8-41b2-8c08-b7b2b41f8b0a

5 files changed, 243 insertions, 5 deletions

diff --git a/ChangeLog b/ChangeLog
index 436411a..b98dfce 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,15 @@
 15-10-06  Cyrille Bagard <nocbos@gmail.com>
 
+	* src/arch/processor.c:
+	* src/arch/processor-int.h:
+	Optimize the search of instructions a little bit using routine coverages.
+
+	* src/arch/vmpa.c:
+	* src/arch/vmpa.h:
+	Extend the functions dealing with memory ranges.
+
+15-10-06  Cyrille Bagard <nocbos@gmail.com>
+
 	* src/analysis/disass/loop.c:
 	Optimize loop detections using bit fields.
 
diff --git a/src/arch/processor-int.h b/src/arch/processor-int.h
index f4562f6..fcd7a52 100644
--- a/src/arch/processor-int.h
+++ b/src/arch/processor-int.h
@@ -61,6 +61,20 @@ typedef GArchInstruction * (* decode_instruction_fc) (const GArchProcessor *, GP
 typedef GArchInstruction * (* disass_instr_fc) (const GArchProcessor *, GProcContext *, const GBinContent *, vmpa2t *);
 
 
+
+/* Couverture d'un groupe d'instructions */
+typedef struct _instr_coverage
+{
+    mrange_t range;                         /* Couverture du groupement    */
+
+    size_t start;                           /* Indice de départ            */
+    size_t count;                           /* Quantité d'inclusions       */
+
+} instr_coverage;
+
+
+
+
 /* Définition générique d'un processeur d'architecture (instance) */
 struct _GArchProcessor
 {
@@ -77,6 +91,10 @@ struct _GArchProcessor
     size_t instr_allocated;                 /* Taille de la liste allouée  */
     size_t instr_count;                     /* Taille de la liste aplatie  */
 
+    instr_coverage *coverages;              /* Liste de couvertures        */
+    size_t cov_allocated;                   /* Taille de la liste allouée  */
+    size_t cov_count;                       /* Taille de la liste utilisée */
+
 };
 
 
diff --git a/src/arch/processor.c b/src/arch/processor.c
index 7e2ecec..c70d586 100644
--- a/src/arch/processor.c
+++ b/src/arch/processor.c
@@ -63,13 +63,26 @@ static void g_arch_processor_init(GArchProcessor *);
 
 
 
+/* ------------------ MANIPULATIONS DES INSTRUCTIONS DESASSEMBLEES ------------------ */
+
+
+/* Démarre la définition d'un nouveau groupe d'instructions. */
+static void g_arch_processor_add_new_coverage(GArchProcessor *, GArchInstruction *, size_t);
+
+/* Termine la définition d'un nouveau groupe d'instructions. */
+static void g_arch_processor_finish_last_coverage(GArchProcessor *, GArchInstruction *, size_t);
+
+/* Recherche un groupe d'instruction d'après son adresse. */
+static bool g_arch_processor_find_coverage_by_address(const GArchProcessor *, const vmpa2t *, size_t *, size_t *);
+
+
+
 
 
 /* Indique le type défini pour un processeur d'architecture. */
 G_DEFINE_TYPE(GArchProcessor, g_arch_processor, G_TYPE_OBJECT);
 
 
-
 /******************************************************************************
 *                                                                             *
 *  Paramètres  : klass = classe à initialiser.                                *
@@ -102,6 +115,9 @@ static void g_arch_processor_class_init(GArchProcessorClass *klass)
 
 static void g_arch_processor_init(GArchProcessor *proc)
 {
+    proc->coverages = NULL;
+    proc->cov_allocated = 0;
+    proc->cov_count = 0;
 
 }
 
@@ -307,6 +323,131 @@ GArchInstruction *g_arch_processor_disassemble(const GArchProcessor *proc, GProc
 
 /******************************************************************************
 *                                                                             *
+*  Paramètres  : proc  = architecture à comléter par la procédure.            *
+*                first = première instruction d'un nouveau groupe.            *
+*                start = indice de cette instruction dans l'ensemble global.  *
+*                                                                             *
+*  Description : Démarre la définition d'un nouveau groupe d'instructions.    *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void g_arch_processor_add_new_coverage(GArchProcessor *proc, GArchInstruction *first, size_t start)
+{
+    instr_coverage *coverage;               /* Couverture à définir        */
+    const mrange_t *irange;                 /* Couverture de l'instruction */
+
+    /* Mise à disposition de d'avantage d'espace */
+    if (proc->cov_allocated == proc->cov_count)
+    {
+        proc->cov_allocated += INSTR_ALLOC_BLOCK;
+
+        proc->coverages = (instr_coverage *)realloc(proc->coverages,
+                                                    proc->cov_allocated * sizeof(instr_coverage));
+
+    }
+
+    coverage = &proc->coverages[proc->cov_count++];
+
+    irange = g_arch_instruction_get_range(first);
+
+    init_mrange(&coverage->range, get_mrange_addr(irange), 0);
+
+    coverage->start = start;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : proc = architecture à comléter par la procédure.             *
+*                last = dernière instruction d'un nouveau groupe.             *
+*                end  = indice de cette instruction dans l'ensemble global.   *
+*                                                                             *
+*  Description : Termine la définition d'un nouveau groupe d'instructions.    *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void g_arch_processor_finish_last_coverage(GArchProcessor *proc, GArchInstruction *last, size_t end)
+{
+    instr_coverage *coverage;               /* Couverture à définir        */
+    const mrange_t *irange;                 /* Couverture de l'instruction */
+    phys_t diff;                            /* Ecart entre les extrémités  */
+
+    coverage = &proc->coverages[proc->cov_count - 1];
+
+    irange = g_arch_instruction_get_range(last);
+
+    diff = compute_vmpa_diff(get_mrange_addr(&coverage->range), get_mrange_addr(irange));
+    diff += get_mrange_length(irange);
+
+    set_mrange_length(&coverage->range, diff);
+
+    coverage->count = end - coverage->start + 1;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : proc  = processeur recensant diverses instructions.          *
+*                addr  = position en mémoire ou physique à chercher.          *
+*                start = indice de départ du groupe concerné trouvé. [OUT]    *
+*                end   = indice de fin du groupe d'instructions visées. [OUT] *
+*                                                                             *
+*  Description : Recherche un groupe d'instruction d'après son adresse.       *
+*                                                                             *
+*  Retour      : Bilan de la recherche menée.                                 *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static bool g_arch_processor_find_coverage_by_address(const GArchProcessor *proc, const vmpa2t *addr, size_t *start, size_t *count)
+{
+    bool result;                            /* Bilan à retourner           */
+    void *ptr;                              /* Résultat des recherches     */
+
+    int search_for_coverage_by_addr(const vmpa2t *a, const instr_coverage *c)
+    {
+        int status;                         /* Bilan d'une comparaison     */
+
+        status = cmp_mrange_with_vmpa(&c->range, a);
+
+        return status;
+
+    }
+
+    ptr = bsearch(addr, proc->coverages, proc->cov_count,
+                  sizeof(instr_coverage), (__compar_fn_t)search_for_coverage_by_addr);
+
+    if (ptr != NULL)
+    {
+        result = true;
+        *start = ((instr_coverage *)ptr)->start;
+        *count = ((instr_coverage *)ptr)->count;
+    }
+    else
+        result = false;
+
+    return result;
+
+}
+
+
+
+
+
+
+/******************************************************************************
+*                                                                             *
 *  Paramètres  : proc = architecture visée par la procédure.                  *
 *                list = liste des instructions désassemblées.                 *
 *                                                                             *
@@ -320,11 +461,14 @@ GArchInstruction *g_arch_processor_disassemble(const GArchProcessor *proc, GProc
 
 void g_arch_processor_set_disassembled_instructions(GArchProcessor *proc, GArchInstruction *list)
 {
+    GArchInstruction *last;                 /* Dernière instruction traitée*/
     GArchInstruction *iter;                 /* Boucle de parcours          */
 
     /* TODO : vider une éventuelle liste existante */
     /* TODO : incrémenter les références (cf. code Python) */
 
+    last = NULL;
+
     ainstr_list_for_each(iter, list)
     {
         /* Mise à disposition de d'avantage d'espace */
@@ -337,10 +481,26 @@ void g_arch_processor_set_disassembled_instructions(GArchProcessor *proc, GArchI
 
         }
 
+        /* Constitution des groupes */
+        if (last == NULL || g_arch_instruction_get_flags(iter) & AIF_ROUTINE_START)
+        {
+            if (last != NULL)
+                g_arch_processor_finish_last_coverage(proc, last, proc->instr_count - 1);
+
+            g_arch_processor_add_new_coverage(proc, iter, proc->instr_count);
+
+        }
+
+        /* Enregistrement */
         proc->instructions[proc->instr_count++] = iter;
 
+        last = iter;
+
     }
 
+    if (last != NULL)
+        g_arch_processor_finish_last_coverage(proc, last, proc->instr_count - 1);
+
 }
 
 
@@ -383,6 +543,8 @@ GArchInstruction *g_arch_processor_get_disassembled_instructions(const GArchProc
 GArchInstruction *g_arch_processor_find_instr_by_address(const GArchProcessor *proc, const vmpa2t *addr)
 {
     GArchInstruction *result;               /* Trouvaille à retourner      */
+    size_t cov_start;                       /* Début d'un groupe ciblé     */
+    size_t cov_count;                       /* Nombre d'éléments à tester  */
     void *ptr;                              /* Résultat des recherches     */
 
     int search_for_instr_by_addr(const vmpa2t *a, const GArchInstruction **b)
@@ -395,10 +557,17 @@ GArchInstruction *g_arch_processor_find_instr_by_address(const GArchProcessor *p
 
     }
 
-    ptr = bsearch(addr, proc->instructions, proc->instr_count,
-                  sizeof(GArchInstruction *), (__compar_fn_t)search_for_instr_by_addr);
 
-    result = (ptr != NULL ? *((GArchInstruction **)ptr) : NULL);
+    if (g_arch_processor_find_coverage_by_address(proc, addr, &cov_start, &cov_count))
+    {
+        ptr = bsearch(addr, &proc->instructions[cov_start], cov_count,
+                      sizeof(GArchInstruction *), (__compar_fn_t)search_for_instr_by_addr);
+
+        result = (ptr != NULL ? *((GArchInstruction **)ptr) : NULL);
+
+    }
+    else
+        result = NULL;
 
     return result;
 
diff --git a/src/arch/vmpa.c b/src/arch/vmpa.c
index 5030562..4c2b4cf 100644
--- a/src/arch/vmpa.c
+++ b/src/arch/vmpa.c
@@ -790,6 +790,42 @@ int cmp_mrange(const mrange_t *a, const mrange_t *b)
 
 /******************************************************************************
 *                                                                             *
+*  Paramètres  : a = première définition à analyser.                          *
+*                b = seconde définition à analyser.                           *
+*                                                                             *
+*  Description : Compare une couverture mémoire avec une localisation simple. *
+*                                                                             *
+*  Retour      : Bilan de la comparaison : -1, 0 ou 1 (-1 par défaut).        *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+int cmp_mrange_with_vmpa(const mrange_t *a, const vmpa2t *b)
+{
+    int result;                             /* Bilan à retourner           */
+    phys_t diff;                            /* Espace entre deux adresses  */
+
+    result = cmp_vmpa(b, &a->addr);
+
+    if (result >= 0)
+    {
+        diff = compute_vmpa_diff(&a->addr, b);
+
+        if (diff < a->length)
+            result = 0;
+        else
+            result = 1;
+
+    }
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
 *  Paramètres  : range = zone mémoire à consulter.                            *
 *                sub   = éventuelle sous-région à valider.                    *
 *                                                                             *
@@ -840,7 +876,7 @@ bool mrange_contains_addr(const mrange_t *range, const vmpa2t *addr)
 
     ret = cmp_vmpa(&range->addr, addr);
 
-    if (ret <= -1)
+    if (ret < 0)
     {
         diff = compute_vmpa_diff(&range->addr, addr);
 
diff --git a/src/arch/vmpa.h b/src/arch/vmpa.h
index 8881ac1..50a02a2 100644
--- a/src/arch/vmpa.h
+++ b/src/arch/vmpa.h
@@ -174,6 +174,8 @@ typedef struct _mrange_t
 #define get_mrange_addr(r) &(r)->addr
 #define get_mrange_length(r) (r)->length
 
+#define set_mrange_length(r, l) (r)->length = l
+
 
 /* Initialise une plage dans l'espace mémoire/physique. */
 void init_mrange(mrange_t *, const vmpa2t *, phys_t);
@@ -184,6 +186,9 @@ void copy_mrange(mrange_t *, const mrange_t *);
 /* Compare deux couvertures mémoire selon leurs propriétés. */
 int cmp_mrange(const mrange_t *, const mrange_t *);
 
+/* Compare une couverture mémoire avec une localisation simple. */
+int cmp_mrange_with_vmpa(const mrange_t *, const vmpa2t *);
+
 /* Indique si une zone en contient une autre ou non. */
 bool mrange_contains_mrange(const mrange_t *, const mrange_t *);