Optimized loop detections using bit fields.

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

1 files changed, 19 insertions, 157 deletions

diff --git a/src/analysis/disass/loop.c b/src/analysis/disass/loop.c
index 88b997f..30265c9 100644
--- a/src/analysis/disass/loop.c
+++ b/src/analysis/disass/loop.c
@@ -29,155 +29,13 @@
 #include <string.h>
 
 
+#include "../../common/bits.h"
 
-/* Suivi du flot d'exécution */
-typedef struct _exec_flow
-{
-    vmpa2t *steps;                          /* Jalons dans l'exécution     */
-    size_t count;                           /* Quantité de ces points      */
-
-} exec_flow;
-
-
-/* Initialise un flot d'exécution. */
-static exec_flow *create_exec_flow(void);
-
-/* Réalise la copie d'un flot d'exécution. */
-static exec_flow *dup_exec_flow(const exec_flow *);
-
-/* Efface de la mémoire un flot d'exécution. */
-static void delete_exec_flow(exec_flow *);
 
-/* Recherche si le chemin d'exécution a déjà mené à une adresse. */
-static bool is_new_exec_flow(const exec_flow *, const vmpa2t *);
-
-/* Ajoute une adresse jalon dans un flot d'exécution. */
-static void add_step_into_exec_flow(exec_flow *, const vmpa2t *);
 
 /* Suit un flot d'exécution à la recherche de boucles. */
-static void track_loops_in_code(const GArchProcessor *, const mrange_t *, const vmpa2t *, exec_flow *);
-
-
-
-/******************************************************************************
-*                                                                             *
-*  Paramètres  : -                                                            *
-*                                                                             *
-*  Description : Initialise un flot d'exécution.                              *
-*                                                                             *
-*  Retour      : Flot d'exécution nouveau.                                    *
-*                                                                             *
-*  Remarques   : -                                                            *
-*                                                                             *
-******************************************************************************/
-
-static exec_flow *create_exec_flow(void)
-{
-    exec_flow *result;                      /* Flot vierge à retourner     */
-
-    result = (exec_flow *)calloc(1, sizeof(exec_flow));
-
-    return result;
-
-}
-
-
-/******************************************************************************
-*                                                                             *
-*  Paramètres  : src = jalons de l'exécution à dupliquer.                     *
-*                                                                             *
-*  Description : Réalise la copie d'un flot d'exécution.                      *
-*                                                                             *
-*  Retour      : Flot d'exécution copié.                                      *
-*                                                                             *
-*  Remarques   : -                                                            *
-*                                                                             *
-******************************************************************************/
+static void track_loops_in_code(const GArchProcessor *, const mrange_t *, const vmpa2t *, memfield_t *);
 
-static exec_flow *dup_exec_flow(const exec_flow *src)
-{
-    exec_flow *result;                      /* Copie à retourner           */
-
-    result = (exec_flow *)calloc(1, sizeof(exec_flow));
-
-    result->steps = (vmpa2t *)malloc(src->count * sizeof(vmpa2t));
-    memcpy(result->steps, src->steps, src->count * sizeof(vmpa2t));
-
-    result->count = src->count;
-
-    return result;
-
-}
-
-
-/******************************************************************************
-*                                                                             *
-*  Paramètres  : flow = jalons de l'exécution à supprimer.                    *
-*                                                                             *
-*  Description : Efface de la mémoire un flot d'exécution.                    *
-*                                                                             *
-*  Retour      : -                                                            *
-*                                                                             *
-*  Remarques   : -                                                            *
-*                                                                             *
-******************************************************************************/
-
-static void delete_exec_flow(exec_flow *flow)
-{
-    if (flow->steps != NULL)
-        free(flow->steps);
-
-    free(flow);
-
-}
-
-
-/******************************************************************************
-*                                                                             *
-*  Paramètres  : flow = ensemble des jalons de l'exécution du code.           *
-*                addr = adresse d'un nouvel embranchement.                    *
-*                                                                             *
-*  Description : Recherche si le chemin d'exécution a déjà mené à une adresse.*
-*                                                                             *
-*  Retour      : true si l'instruction est visitée pour la première fois.     *
-*                                                                             *
-*  Remarques   : -                                                            *
-*                                                                             *
-******************************************************************************/
-
-static bool is_new_exec_flow(const exec_flow *flow, const vmpa2t *addr)
-{
-    void *ret;                              /* Conclusion d'une recherche  */
-
-    ret = bsearch(addr, flow->steps, flow->count,
-                  sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa);
-
-    return (ret == NULL);
-
-}
-
-
-/******************************************************************************
-*                                                                             *
-*  Paramètres  : flow = jalons de l'exécution du code à compléter.            *
-*                addr = adresse d'un nouvel embranchement.                    *
-*                                                                             *
-*  Description : Ajoute une adresse jalon dans un flot d'exécution.           *
-*                                                                             *
-*  Retour      : -                                                            *
-*                                                                             *
-*  Remarques   : -                                                            *
-*                                                                             *
-******************************************************************************/
-
-static void add_step_into_exec_flow(exec_flow *flow, const vmpa2t *addr)
-{
-    flow->steps = (vmpa2t *)realloc(flow->steps, ++flow->count * sizeof(vmpa2t));
-    copy_vmpa(&flow->steps[flow->count - 1], addr);
-
-    qsort(flow->steps, flow->count, sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa);
-
-}
 
 
 /******************************************************************************
@@ -195,7 +53,7 @@ static void add_step_into_exec_flow(exec_flow *flow, const vmpa2t *addr)
 *                                                                             *
 ******************************************************************************/
 
-static void track_loops_in_code(const GArchProcessor *proc, const mrange_t *range, const vmpa2t *start, exec_flow *flow)
+static void track_loops_in_code(const GArchProcessor *proc, const mrange_t *range, const vmpa2t *start, memfield_t *flow)
 {
     bool exit_track;                        /* Détermine la fin du parcours*/
     GArchInstruction *iter;                 /* Boucle de parcours          */
@@ -205,9 +63,9 @@ static void track_loops_in_code(const GArchProcessor *proc, const mrange_t *rang
     size_t dcount;                          /* Nombre de liens de dest.    */
     size_t i;                               /* Boucle de parcours          */
     const vmpa2t *addr;                     /* Prochaine adresse de saut   */
-    exec_flow *next_flow;                   /* Suite de l'exécution        */
+    memfield_t *next_flow;                  /* Suite de l'exécution        */
 
-    add_step_into_exec_flow(flow, start);
+    set_in_mem_field(flow, start);
 
     exit_track = false;
 
@@ -236,8 +94,8 @@ static void track_loops_in_code(const GArchProcessor *proc, const mrange_t *rang
         {
             addr = get_mrange_addr(irange);
 
-            if (is_new_exec_flow(flow, addr))
-                add_step_into_exec_flow(flow, addr);
+            if (!test_in_mem_field(flow, addr))
+                set_in_mem_field(flow, start);
 
         }
 
@@ -261,9 +119,9 @@ static void track_loops_in_code(const GArchProcessor *proc, const mrange_t *rang
                     irange = g_arch_instruction_get_range(dests[i]);
                     addr = get_mrange_addr(irange);
 
-                    next_flow = create_exec_flow();
+                    next_flow = create_mem_field_from(flow);
                     track_loops_in_code(proc, range, addr, next_flow);
-                    delete_exec_flow(next_flow);
+                    delete_mem_field(next_flow);
 
                     break;
 
@@ -280,16 +138,20 @@ static void track_loops_in_code(const GArchProcessor *proc, const mrange_t *rang
                     exit_track = true;
 
                     irange = g_arch_instruction_get_range(dests[i]);
+
+                    if (!mrange_contains_mrange(range, irange))
+                        break;
+
                     addr = get_mrange_addr(irange);
 
-                    if (!is_new_exec_flow(flow, addr))
+                    if (test_in_mem_field(flow, addr))
                         /* status = */g_arch_instruction_change_link(iter, dests[i], types[i], ILT_LOOP);
 
                     else
                     {
-                        next_flow = dup_exec_flow(flow);
+                        next_flow = dup_mem_field(flow);
                         track_loops_in_code(proc, range, addr, next_flow);
-                        delete_exec_flow(next_flow);
+                        delete_mem_field(next_flow);
                     }
 
                     break;
@@ -324,15 +186,15 @@ void detect_loops_in_code(const GArchProcessor *proc, GBinRoutine **routines, si
 {
     size_t i;                               /* Boucle de parcours          */
     const mrange_t *range;                  /* Couverture d'une routine    */
-    exec_flow *flow;                        /* Flot d'exécution à suivre   */
+    memfield_t *flow;                       /* Flot d'exécution à suivre   */
 
     for (i = 0; i < count; i++)
     {
         range = g_binary_routine_get_range(routines[i]);
 
-        flow = create_exec_flow();
+        flow = create_mem_field(range);
         track_loops_in_code(proc, range, get_mrange_addr(range), flow);
-        delete_exec_flow(flow);
+        delete_mem_field(flow);
 
         gtk_extended_status_bar_update_activity(statusbar, id, (i + 1) * 1.0 / count);