Improved loading speed with binary search of sorted arrays.

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

4 files changed, 68 insertions, 53 deletions

diff --git a/src/analysis/disass/area.c b/src/analysis/disass/area.c
index 2e7b46d..6ce9272 100644
--- a/src/analysis/disass/area.c
+++ b/src/analysis/disass/area.c
@@ -1553,10 +1553,25 @@ static bool insert_extra_symbol_into_mem_areas(mem_area **list, size_t *count, G
 size_t find_memory_area_by_addr(mem_area *list, size_t count, const vmpa2t *addr)
 {
     size_t result;                          /* Trouvaille à retourner      */
+    mem_area *found;                        /* Elément trouvé éventuel     */
 
-    for (result = 0; result < count; result++)
-        if (mrange_contains_addr(&list[result].range, addr))
-            break;
+    int find_mem_area(const vmpa2t *addr, const mem_area *area)
+    {
+        int status;                         /* Bilan à retourner           */
+
+        if (mrange_contains_addr(&area->range, addr))
+            status = 0;
+
+        else
+            status = cmp_vmpa(addr, get_mrange_addr(&area->range));
+
+        return status;
+
+    }
+
+    found = bsearch(addr, list, count, sizeof(mem_area), (__compar_fn_t)find_mem_area);
+
+    result = (found != NULL ? found - list : count);
 
     return result;
 
diff --git a/src/analysis/disass/disassembler.c b/src/analysis/disass/disassembler.c
index a779dd1..2b518f9 100644
--- a/src/analysis/disass/disassembler.c
+++ b/src/analysis/disass/disassembler.c
@@ -397,7 +397,7 @@ G_BIN_FORMAT(g_loaded_binary_get_format(disass->binary)
 
     //qsort(routines, routines_count, sizeof(GBinRoutine *), (__compar_fn_t)g_binary_routine_rcompare);
 
-    group_routines_instructions(*disass->instrs, routines, routines_count, statusbar, id);
+    group_routines_instructions(proc, routines, routines_count, statusbar, id);
 
     gtk_extended_status_bar_remove(statusbar, id);
 
diff --git a/src/analysis/disass/macro.c b/src/analysis/disass/macro.c
index b478c74..4e77881 100644
--- a/src/analysis/disass/macro.c
+++ b/src/analysis/disass/macro.c
@@ -111,7 +111,7 @@ static bool add_hop_into_branch(branch_info *, const vmpa2t *);
 static const vmpa2t *get_entry_to_branch(const branch_info *);
 
 /* Identifie les différents points de passage d'une branche. */
-static void find_next_hops(GArchInstruction *, const vmpa2t *, const code_coverage *, branch_info *);
+static void find_next_hops(GArchProcessor *, const vmpa2t *, const code_coverage *, branch_info *);
 
 /* Retrouve le point de ralliement entre deux branches. */
 static bool compute_first_common_addr(const branch_info *, const branch_info *, vmpa2t *);
@@ -170,19 +170,19 @@ static bool compute_first_common_addr_in_group(const branch_group *, vmpa2t *);
 
 
 /* Procède à la création d'un bloc d'instructions simple. */
-static GInstrBlock *build_instruction_block_simple(GArchInstruction *, code_coverage *, GArchInstruction **, GArchInstruction *);
+static GInstrBlock *build_instruction_block_simple(GArchProcessor *, code_coverage *, GArchInstruction **, GArchInstruction *);
 
 /* Procède à la définition d'un bloc d'instructions selectif. */
-static GInstrBlock *build_instruction_blocks_case(GArchInstruction *, code_coverage *, const branch_group *, vmpa2t *);
+static GInstrBlock *build_instruction_blocks_case(GArchProcessor *, code_coverage *, const branch_group *, vmpa2t *);
 
 /* Procède à la définition d'un bloc d'instruction if/then/else. */
-static GInstrBlock *build_instruction_blocks_ite(GArchInstruction *, code_coverage *, const branch_info *, const branch_info *, vmpa2t *);
+static GInstrBlock *build_instruction_blocks_ite(GArchProcessor *, code_coverage *, const branch_info *, const branch_info *, vmpa2t *);
 
 /* Procède à la définition d'un bloc d'instructions d'exception. */
-static void add_instruction_blocks_except(GInstrBlock **, GInstrBlock **, GArchInstruction *, code_coverage *, const branch_group *, const branch_info *);
+static void add_instruction_blocks_except(GInstrBlock **, GInstrBlock **, GArchProcessor *, code_coverage *, const branch_group *, const branch_info *);
 
 /* Procède à la définition de bloc regroupant des instructions. */
-static GInstrBlock *build_instruction_blocks(GArchInstruction *, code_coverage *);
+static GInstrBlock *build_instruction_blocks(GArchProcessor *, code_coverage *);
 
 
 
@@ -581,7 +581,7 @@ static const vmpa2t *get_entry_to_branch(const branch_info *info)
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : instrs   = ensemble des instructions d'assemblage.           *
+*  Paramètres  : proc     = ensemble des instructions d'assemblage.           *
 *                start    = position du début de bloc.                        *
 *                coverage = liste des adresses de fin butoir.                 *
 *                count    = nombre de sauts détectés. [OUT]                   *
@@ -594,7 +594,7 @@ static const vmpa2t *get_entry_to_branch(const branch_info *info)
 *                                                                             *
 ******************************************************************************/
 
-static void find_next_hops(GArchInstruction *instrs, const vmpa2t *start, const code_coverage *coverage, branch_info *info)
+static void find_next_hops(GArchProcessor *proc, const vmpa2t *start, const code_coverage *coverage, branch_info *info)
 {
     GArchInstruction *iter;                 /* Boucle de parcours #1       */
     const mrange_t *range;                  /* Emplacement d'instruction   */
@@ -619,9 +619,9 @@ static void find_next_hops(GArchInstruction *instrs, const vmpa2t *start, const
         printf("  ++ add 0x%08x\n", (unsigned int)start->virtual);
 
     /* On suit le flot jusqu'à la prochaine bifurcation */
-    for (iter = g_arch_instruction_find_by_address(instrs, start, true);
+    for (iter = g_arch_processor_find_instr_by_address(proc, start);
          iter != NULL;
-         iter = g_arch_instruction_get_next_iter(instrs, iter, VMPA_MAX))
+         iter = g_arch_processor_get_next_instr(proc, iter))
     {
         range = g_arch_instruction_get_range(iter);
 
@@ -673,7 +673,7 @@ static void find_next_hops(GArchInstruction *instrs, const vmpa2t *start, const
                 case ILT_CASE_JUMP:
                 case ILT_JUMP_IF_TRUE:
                 case ILT_JUMP_IF_FALSE:
-                    find_next_hops(instrs, get_mrange_addr(range), coverage, info);
+                    find_next_hops(proc, get_mrange_addr(range), coverage, info);
                     break;
 
                 case ILT_LOOP:
@@ -877,7 +877,7 @@ static bool compute_first_common_addr_in_group(const branch_group *group, vmpa2t
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : instrs   = ensemble des instructions d'assemblage.           *
+*  Paramètres  : proc     = ensemble des instructions d'assemblage.           *
 *                coverage = délimitations de la zone à couvrir.               *
 *                first    = première instruction d'un bloc préliminaire.      *
 *                cur      = instruction courante dans le traitement.          *
@@ -890,13 +890,13 @@ static bool compute_first_common_addr_in_group(const branch_group *group, vmpa2t
 *                                                                             *
 ******************************************************************************/
 #include "../../arch/instruction-int.h"
-static GInstrBlock *build_instruction_block_simple(GArchInstruction *instrs, code_coverage *coverage, GArchInstruction **first, GArchInstruction *cur)
+static GInstrBlock *build_instruction_block_simple(GArchProcessor *proc, code_coverage *coverage, GArchInstruction **first, GArchInstruction *cur)
 {
     GInstrBlock *result;                    /* Regroupement à retourner    */
  
     if (*first != NULL)
     {
-        result = g_flow_block_new(instrs, *first, cur);
+        result = g_flow_block_new(proc, *first, cur);
 
         mark_range_as_processed_in_coverage(coverage, *first);
 
@@ -912,7 +912,7 @@ static GInstrBlock *build_instruction_block_simple(GArchInstruction *instrs, cod
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : instrs   = ensemble des instructions d'assemblage.           *
+*  Paramètres  : proc     = ensemble des instructions d'assemblage.           *
 *                coverage = délimitations de la zone à couvrir.               *
 *                cases    = branches conditionnelles des situations.          *
 *                next     = localisation de l'instruction de reprise.         *
@@ -925,7 +925,7 @@ static GInstrBlock *build_instruction_block_simple(GArchInstruction *instrs, cod
 *                                                                             *
 ******************************************************************************/
 
-static GInstrBlock *build_instruction_blocks_case(GArchInstruction *instrs, code_coverage *coverage, const branch_group *cases, vmpa2t *next)
+static GInstrBlock *build_instruction_blocks_case(GArchProcessor *proc, code_coverage *coverage, const branch_group *cases, vmpa2t *next)
 {
     GInstrBlock *result;                    /* Regroupement à retourner    */
     bool has_common;                        /* Fin commune ?               */
@@ -948,7 +948,7 @@ static GInstrBlock *build_instruction_blocks_case(GArchInstruction *instrs, code
         for (j = 0; j < cases->count; j++)
             add_ending_address_code_coverage(sub_coverage, get_entry_to_branch(&cases->branches[j]));
 
-        block = build_instruction_blocks(instrs, sub_coverage);
+        block = build_instruction_blocks(proc, sub_coverage);
 
         if (block != NULL)
             g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);
@@ -970,7 +970,7 @@ static GInstrBlock *build_instruction_blocks_case(GArchInstruction *instrs, code
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : instrs       = ensemble des instructions d'assemblage.       *
+*  Paramètres  : proc         = ensemble des instructions d'assemblage.       *
 *                coverage     = délimitations de la zone à couvrir.           *
 *                true_branch  = branche conditionnelle correspondant à true.  *
 *                false_branch = branche conditionnelle correspondant à false. *
@@ -984,7 +984,7 @@ static GInstrBlock *build_instruction_blocks_case(GArchInstruction *instrs, code
 *                                                                             *
 ******************************************************************************/
 
-static GInstrBlock *build_instruction_blocks_ite(GArchInstruction *instrs, code_coverage *coverage, const branch_info *true_branch, const branch_info *false_branch, vmpa2t *next)
+static GInstrBlock *build_instruction_blocks_ite(GArchProcessor *proc, code_coverage *coverage, const branch_info *true_branch, const branch_info *false_branch, vmpa2t *next)
 {
     GInstrBlock *result;                    /* Regroupement à retourner    */
     bool has_common;                        /* Fin commune ?               */
@@ -1005,7 +1005,7 @@ static GInstrBlock *build_instruction_blocks_ite(GArchInstruction *instrs, code_
 
         _sub_coverage = dup_code_coverage(coverage, get_entry_to_branch(true_branch));
 
-        block = build_instruction_blocks(instrs, _sub_coverage);
+        block = build_instruction_blocks(proc, _sub_coverage);
 
         delete_code_coverage(_sub_coverage);
 
@@ -1018,7 +1018,7 @@ static GInstrBlock *build_instruction_blocks_ite(GArchInstruction *instrs, code_
 
         _sub_coverage = dup_code_coverage(coverage, get_entry_to_branch(false_branch));
 
-        block = build_instruction_blocks(instrs, _sub_coverage);
+        block = build_instruction_blocks(proc, _sub_coverage);
 
         delete_code_coverage(_sub_coverage);
 
@@ -1053,7 +1053,7 @@ static GInstrBlock *build_instruction_blocks_ite(GArchInstruction *instrs, code_
      * Encapsulation des branches conditionnelles.
      */
 
-    GInstrBlock *build_instr_block_bi(GArchInstruction *instrs, const code_coverage *coverage, const branch_info *br0, const branch_info *br1, const vmpa2t *next)
+    GInstrBlock *build_instr_block_bi(GArchProcessor *proc, const code_coverage *coverage, const branch_info *br0, const branch_info *br1, const vmpa2t *next)
     {
         GInstrBlock *result;                /* Bloc construit à renvoyer   */
         code_coverage *sub_coverage;        /* Couverture pour les suivants*/
@@ -1069,7 +1069,7 @@ static GInstrBlock *build_instruction_blocks_ite(GArchInstruction *instrs, code_
             if (br1->count > 0)
                 add_ending_address_code_coverage(sub_coverage, get_entry_to_branch(br1));
 
-            result = build_instruction_blocks(instrs, sub_coverage);
+            result = build_instruction_blocks(proc, sub_coverage);
 
             delete_code_coverage(sub_coverage);
 
@@ -1081,7 +1081,7 @@ static GInstrBlock *build_instruction_blocks_ite(GArchInstruction *instrs, code_
 
     /* Branche 'true' */
 
-    block = build_instr_block_bi(instrs, coverage, true_branch, false_branch, next);
+    block = build_instr_block_bi(proc, coverage, true_branch, false_branch, next);
 
     printf("===> TRUE_BRANCH = %p\n", block);
 
@@ -1090,7 +1090,7 @@ static GInstrBlock *build_instruction_blocks_ite(GArchInstruction *instrs, code_
 
     /* Branche 'false' */
 
-    block = build_instr_block_bi(instrs, coverage, false_branch, true_branch, next);
+    block = build_instr_block_bi(proc, coverage, false_branch, true_branch, next);
 
     printf("===> FALSE_BRANCH = %p\n", block);
 
@@ -1114,7 +1114,7 @@ static GInstrBlock *build_instruction_blocks_ite(GArchInstruction *instrs, code_
 *                                                                             *
 *  Paramètres  : result      = liste générale résultante du découpage. [OUT]  *
 *                cached      = emplacement pour le cache des résultats. [OUT] *
-*                instrs      = ensemble des instructions d'assemblage.        *
+*                proc        = ensemble des instructions d'assemblage.        *
 *                coverage    = délimitations de la zone à couvrir.            *
 *                exceptions  = branche conditionnelle correspondant à true.   *
 *                main_branch = branche principale avec son flot d'exécution.  *
@@ -1127,7 +1127,7 @@ static GInstrBlock *build_instruction_blocks_ite(GArchInstruction *instrs, code_
 *                                                                             *
 ******************************************************************************/
 
-static void add_instruction_blocks_except(GInstrBlock **result, GInstrBlock **cached, GArchInstruction *instrs, code_coverage *coverage, const branch_group *exceptions, const branch_info *main_branch)
+static void add_instruction_blocks_except(GInstrBlock **result, GInstrBlock **cached, GArchProcessor *proc, code_coverage *coverage, const branch_group *exceptions, const branch_info *main_branch)
 {
     size_t i;                               /* Boucle de parcours          */
     vmpa2t stop_addr;                       /* Adresse de fin de bloc      */
@@ -1143,7 +1143,7 @@ static void add_instruction_blocks_except(GInstrBlock **result, GInstrBlock **ca
         sub_coverage = dup_code_coverage(coverage, get_entry_to_branch(&exceptions->branches[i]));
         add_ending_address_code_coverage(sub_coverage, &stop_addr);
 
-        block = build_instruction_blocks(instrs, sub_coverage);
+        block = build_instruction_blocks(proc, sub_coverage);
 
         if (block != NULL)
             DELAYED_BLOCK_ADDING(*result, *cached, block);
@@ -1157,7 +1157,7 @@ static void add_instruction_blocks_except(GInstrBlock **result, GInstrBlock **ca
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : instrs   = ensemble des instructions d'assemblage.           *
+*  Paramètres  : proc     = ensemble des instructions d'assemblage.           *
 *                coverage = délimitations de la zone à couvrir.               *
 *                                                                             *
 *  Description : Procède à la définition de bloc regroupant des instructions. *
@@ -1168,7 +1168,7 @@ static void add_instruction_blocks_except(GInstrBlock **result, GInstrBlock **ca
 *                                                                             *
 ******************************************************************************/
 #include "../../arch/instruction-int.h"
-static GInstrBlock *build_instruction_blocks(GArchInstruction *instrs, code_coverage *coverage)
+static GInstrBlock *build_instruction_blocks(GArchProcessor *proc, code_coverage *coverage)
 {
     GInstrBlock *result;                    /* Regroupement à retourner    */
     GInstrBlock *result_cached;             /* Temporisation pour unicité  */
@@ -1199,17 +1199,17 @@ static GInstrBlock *build_instruction_blocks(GArchInstruction *instrs, code_cove
     last = NULL;
 
     init_branch_info(&main_branch);
-    find_next_hops(instrs, get_code_coverage_start_addr(coverage), coverage, &main_branch);
+    find_next_hops(proc, get_code_coverage_start_addr(coverage), coverage, &main_branch);
 
 
     printf("//////////////////////////\n");
     printf("/// Cutting for 0x%08x -> %p\n",
            get_code_coverage_start_addr(coverage)->virtual,
-           g_arch_instruction_find_by_address(instrs, get_code_coverage_start_addr(coverage), true));
+           g_arch_processor_find_instr_by_address(proc, get_code_coverage_start_addr(coverage)));
     printf("//////////////////////////\n");
 
 
-    for (iter = g_arch_instruction_find_by_address(instrs, get_code_coverage_start_addr(coverage), true);
+    for (iter = g_arch_processor_find_instr_by_address(proc, get_code_coverage_start_addr(coverage));
          iter != NULL;
          )
     {
@@ -1236,7 +1236,7 @@ static GInstrBlock *build_instruction_blocks(GArchInstruction *instrs, code_cove
         /* On n'approfondit que les chemins qui se séparent */
         if (!g_arch_instruction_has_destinations(iter))
         {
-            iter = g_arch_instruction_get_next_iter(instrs, iter, VMPA_MAX);
+            iter = g_arch_processor_get_next_instr(proc, iter);
             continue;
         }
 
@@ -1268,7 +1268,7 @@ static GInstrBlock *build_instruction_blocks(GArchInstruction *instrs, code_cove
 
                     _saved0 = first;
 
-                    block = build_instruction_block_simple(instrs, coverage, &first, iter);
+                    block = build_instruction_block_simple(proc, coverage, &first, iter);
                     printf(" -- simple block JMP -- @ 0x%08x <-> 0x%08x\n",
                            (unsigned int)(_saved0 ? _saved0->range.addr.virtual : ~0),
                            (unsigned int)iter->range.addr.virtual);
@@ -1349,7 +1349,7 @@ static GInstrBlock *build_instruction_blocks(GArchInstruction *instrs, code_cove
 
                 printf("\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
                 printf("BUILD @ 0x%08x\n", (unsigned int)addr->virtual);
-                find_next_hops(instrs, addr, coverage, branch);
+                find_next_hops(proc, addr, coverage, branch);
                 printf("<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n\n");
 
             }
@@ -1359,10 +1359,10 @@ static GInstrBlock *build_instruction_blocks(GArchInstruction *instrs, code_cove
         /* Post-traitements de ILT_CASE_JUMP */
         if (cases_branches.count > 0)
         {
-            block = build_instruction_block_simple(instrs, coverage, &first, iter);
+            block = build_instruction_block_simple(proc, coverage, &first, iter);
             DELAYED_BLOCK_ADDING(result, result_cached, block);
 
-            group = build_instruction_blocks_case(instrs, coverage, &cases_branches, &next_addr);
+            group = build_instruction_blocks_case(proc, coverage, &cases_branches, &next_addr);
 
             if (group != NULL)
             {
@@ -1375,7 +1375,7 @@ static GInstrBlock *build_instruction_blocks(GArchInstruction *instrs, code_cove
         /* Post-traitements de ILT_JUMP_IF_TRUE / ILT_JUMP_IF_FALSE */
         else if (true_branch.count > 0 || false_branch.count > 0)
         {
-            block = build_instruction_block_simple(instrs, coverage, &first, iter);
+            block = build_instruction_block_simple(proc, coverage, &first, iter);
 
             GArchInstruction *_saved1;
 
@@ -1391,7 +1391,7 @@ static GInstrBlock *build_instruction_blocks(GArchInstruction *instrs, code_cove
             fflush(NULL);
             DELAYED_BLOCK_ADDING(result, result_cached, block);
 
-            group = build_instruction_blocks_ite(instrs, coverage, &true_branch, &false_branch, &next_addr);
+            group = build_instruction_blocks_ite(proc, coverage, &true_branch, &false_branch, &next_addr);
 
             printf(" --> group = %p  -  next = 0x%08x\n", group, next_addr.virtual);
 
@@ -1406,10 +1406,10 @@ static GInstrBlock *build_instruction_blocks(GArchInstruction *instrs, code_cove
         /* Post-traitements de ILT_CATCH_EXCEPTION */
         if (excep_branches.count > 0)
         {
-            block = build_instruction_block_simple(instrs, coverage, &first, iter);
+            block = build_instruction_block_simple(proc, coverage, &first, iter);
             if (block != NULL) DELAYED_BLOCK_ADDING(result, result_cached, block);
 
-            add_instruction_blocks_except(&result, &result_cached, instrs, coverage,
+            add_instruction_blocks_except(&result, &result_cached, proc, coverage,
                                           &excep_branches, &main_branch);
 
         }
@@ -1422,9 +1422,9 @@ static GInstrBlock *build_instruction_blocks(GArchInstruction *instrs, code_cove
         /* Détermination du prochain point de chute */
 
         if (not_handled == dcount)
-            iter = g_arch_instruction_get_next_iter(instrs, iter, VMPA_MAX);
+            iter = g_arch_processor_get_next_instr(proc, iter);
         else
-            iter = g_arch_instruction_find_by_address(instrs, &next_addr, true);
+            iter = g_arch_processor_find_instr_by_address(proc, &next_addr);
 
     }
 
@@ -1434,7 +1434,7 @@ static GInstrBlock *build_instruction_blocks(GArchInstruction *instrs, code_cove
 
         if (!is_range_processed_in_coverage(coverage, range))
         {
-            block = build_instruction_block_simple(instrs, coverage, &first, last);
+            block = build_instruction_block_simple(proc, coverage, &first, last);
             DELAYED_BLOCK_ADDING(result, result_cached, block);
         }
 
@@ -1449,7 +1449,7 @@ static GInstrBlock *build_instruction_blocks(GArchInstruction *instrs, code_cove
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : list      = ensemble d'instructions à relier.                *
+*  Paramètres  : proc      = processeur rassemblant les instructions à relier.*
 *                routines  = prototypes existants à insérer.                  *
 *                count     = quantité de ces prototypes.                      *
 *                statusbar = barre de statut avec progression à mettre à jour.*
@@ -1463,7 +1463,7 @@ static GInstrBlock *build_instruction_blocks(GArchInstruction *instrs, code_cove
 *                                                                             *
 ******************************************************************************/
 
-void group_routines_instructions(GArchInstruction *list, GBinRoutine **routines, size_t count, GtkExtStatusBar *statusbar, bstatus_id_t id)
+void group_routines_instructions(GArchProcessor *proc, GBinRoutine **routines, size_t count, GtkExtStatusBar *statusbar, bstatus_id_t id)
 {
     size_t i;                               /* Boucle de parcours          */
     const mrange_t *range;                  /* Emplacement de routine      */
@@ -1478,7 +1478,7 @@ void group_routines_instructions(GArchInstruction *list, GBinRoutine **routines,
 
         coverage = create_code_coverage(range);
 
-        block = build_instruction_blocks(list, coverage);
+        block = build_instruction_blocks(proc, coverage);
         g_binary_routine_set_basic_blocks(routines[i], block);
 
 
diff --git a/src/analysis/disass/macro.h b/src/analysis/disass/macro.h
index 82185bb..2c03520 100644
--- a/src/analysis/disass/macro.h
+++ b/src/analysis/disass/macro.h
@@ -32,7 +32,7 @@
 
 
 /* Regroupe les instructions par blocs. */
-void group_routines_instructions(GArchInstruction *, GBinRoutine **, size_t, GtkExtStatusBar *, bstatus_id_t);
+void group_routines_instructions(GArchProcessor *, GBinRoutine **, size_t, GtkExtStatusBar *, bstatus_id_t);