Cut instructions flow into blocks (to be continued).

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

4 files changed, 449 insertions, 0 deletions

diff --git a/src/analysis/disass/Makefile.am b/src/analysis/disass/Makefile.am
index ce27d15..854c726 100644
--- a/src/analysis/disass/Makefile.am
+++ b/src/analysis/disass/Makefile.am
@@ -6,6 +6,7 @@ libanalysisdisass_la_SOURCES =			\
 	fetch.h fetch.c						\
 	limit.h limit.c						\
 	links.h links.c						\
+	macro.h macro.c						\
 	output.h output.c
 
 libanalysisdisass_la_LDFLAGS = 
diff --git a/src/analysis/disass/disassembler.c b/src/analysis/disass/disassembler.c
index 6d0bd61..ee56043 100644
--- a/src/analysis/disass/disassembler.c
+++ b/src/analysis/disass/disassembler.c
@@ -35,6 +35,7 @@
 #include "fetch.h"
 #include "limit.h"
 #include "links.h"
+#include "macro.h"
 #include "output.h"
 #include "../../decomp/lang/asm.h"
 #include "../../format/format.h"
@@ -267,6 +268,18 @@ static void g_delayed_disassembly_process(GDelayedDisassembly *disass, GtkExtSta
 
     /* Quatrième étape */
 
+    id = gtk_extended_status_bar_push(statusbar, _("Grouping routines instructions..."), true);
+
+    qsort(routines, routines_count, sizeof(GBinRoutine *), (__compar_fn_t)g_binary_routine_rcompare);
+
+    group_routines_instructions(*disass->instrs, routines, routines_count, statusbar, id);
+
+    gtk_extended_status_bar_remove(statusbar, id);
+
+    run_plugins_on_binary(disass->binary, PGA_BINARY_GROUPED);
+
+    /* Cinquième étape */
+
     id = gtk_extended_status_bar_push(statusbar, _("Printing disassembled code..."), true);
 
     qsort(routines, routines_count, sizeof(GBinRoutine *), (__compar_fn_t)g_binary_routine_compare);
diff --git a/src/analysis/disass/macro.c b/src/analysis/disass/macro.c
new file mode 100644
index 0000000..fc5d8dc
--- /dev/null
+++ b/src/analysis/disass/macro.c
@@ -0,0 +1,397 @@
+
+/* OpenIDA - Outil d'analyse de fichiers binaires
+ * macro.c - vue macroscopique des liens entre blocs d'instructions
+ *
+ * Copyright (C) 2012 Cyrille Bagard
+ *
+ *  This file is part of OpenIDA.
+ *
+ *  OpenIDA 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.
+ *
+ *  OpenIDA 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 "macro.h"
+
+
+#include <string.h>
+
+
+#include "../blocks/flow.h"
+#include "../blocks/virtual.h"
+
+
+
+/* Indications sur une branche */
+typedef struct _branch_info
+{
+    vmpa_t *jumps;                          /* Jalons de la branche        */
+    size_t count;                           /* Quantité de ces jalons      */
+
+} branch_info;
+
+
+/* Indique si une adresse est retenue comme point de passage. */
+static bool is_addr_in_branch(const branch_info *, const vmpa_t *, bool);
+
+/* Identifie les différents points de passage d'une branche. */
+static void find_next_jumps(GArchInstruction *, vmpa_t, vmpa_t, branch_info *);
+
+/* Retrouve le point de ralliement entre deux branches. */
+static vmpa_t compute_first_common_addr(branch_info *, branch_info *);
+
+/* Procède à la définition de bloc regroupant des instructions. */
+static GInstrBlock *build_instruction_block(GArchInstruction *, vmpa_t, vmpa_t, vmpa_t);
+
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : info = informations à consulter.                             *
+*                addr = adresse à rechercher.                                 *
+*                fast = autorise une recherche rapide.                        *
+*                                                                             *
+*  Description : Indique si une adresse est retenue comme point de passage.   *
+*                                                                             *
+*  Retour      : true si le jalon est déjà dans la liste, false sinon.        *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static bool is_addr_in_branch(const branch_info *info, const vmpa_t *addr, bool fast)
+{
+    bool result;                            /* Bilan à retourner           */
+    size_t i;                               /* Boucle de parcours          */
+    void *ptr;                              /* Résultat des recherches     */
+
+    result = false;
+
+    if (!fast)
+        for (i = 0; i < info->count && !result; i++)
+            result = (info->jumps[i] == *addr);
+
+    else
+    {
+        ptr = bsearch(addr, info->jumps, info->count, sizeof(vmpa_t), (__compar_fn_t)compare_vmpa);
+        result = (ptr != NULL);
+    }
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : instrs = ensemble des instructions d'assemblage.             *
+*                start  = adresse de début du bloc.                           *
+*                end    = adresse de fin du bloc (exclusive).                 *
+*                count  = nombre de sauts détectés. [OUT]                     *
+*                                                                             *
+*  Description : Identifie les différents points de passage d'une branche.    *
+*                                                                             *
+*  Retour      : Jalons dans le flot d'exécution.                             *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void find_next_jumps(GArchInstruction *instrs, vmpa_t start, vmpa_t end, branch_info *info)
+{
+    GArchInstruction *iter;                 /* Boucle de parcours #1       */
+    GArchInstruction **dests;               /* Instr. visée par une autre  */
+    InstructionLinkType *types;             /* Type de lien entre lignes   */
+    size_t dcount;                          /* Nombre de liens de dest.    */
+    size_t i;                               /* Boucle de parcours #2       */
+    vmpa_t addr;                            /* Adresse de la destination   */
+
+    /* On évite de boucler... */
+    if (is_addr_in_branch(info, &start, false))
+        return;
+
+    info->jumps = (vmpa_t *)realloc(info->jumps, ++(info->count) * sizeof(vmpa_t));
+    info->jumps[info->count - 1] = start;
+
+    /* On suit le flot jusqu'à la prochaine bifurcation */
+    for (iter = g_arch_instruction_find_by_address(instrs, start, true);
+         iter != NULL;
+         iter = g_arch_instruction_get_next_iter(instrs, iter, end))
+    {
+        if (g_arch_instruction_is_return(iter))
+        {
+            iter = NULL;
+            break;
+        }
+
+        if (!g_arch_instruction_has_destinations(iter))
+            continue;
+
+        dcount = g_arch_instruction_get_destinations(iter, &dests, &types);
+
+        for (i = 0; i < dcount; i++)
+            switch (types[i])
+            {
+                case ILT_EXEC_FLOW:
+                case ILT_JUMP:
+                case ILT_JUMP_IF_TRUE:
+                case ILT_JUMP_IF_FALSE:
+                    g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
+                    find_next_jumps(instrs, addr, end, info);
+                    break;
+
+                default:
+                    break;
+
+            }
+
+        break;
+
+    }
+
+    /* Si on termine... */
+    if (iter != NULL && !is_addr_in_branch(info, &end, false))
+    {
+        info->jumps = (vmpa_t *)realloc(info->jumps, ++(info->count) * sizeof(vmpa_t));
+        info->jumps[info->count - 1] = end;
+    }
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : a = premier ensemble de jalons à parcourir.                  *
+*                b = second ensemble de jalons à parcourir.                   *
+*                                                                             *
+*  Description : Retrouve le point de ralliement entre deux branches.         *
+*                                                                             *
+*  Retour      : Adresse commune à deux branches.                             *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static vmpa_t compute_first_common_addr(branch_info *a, branch_info *b)
+{
+    vmpa_t result;                          /* Adresse trouvée à retourner */
+    size_t i;                               /* Boucle de parcours          */
+
+    /* Valeur conceptuellement impossible à renvoyer */
+    result = VMPA_MAX;
+
+    //qsort(a->jumps, a->count, sizeof(vmpa_t), (__compar_fn_t)compare_vmpa);
+    //qsort(b->jumps, b->count, sizeof(vmpa_t), (__compar_fn_t)compare_vmpa);
+
+    for (i = 0; i < a->count && result == VMPA_MAX; i++)
+        if (is_addr_in_branch(b, &a->jumps[i], false))
+            result = a->jumps[i];
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : instrs = ensemble des instructions d'assemblage.             *
+*                start  = adresse de début du bloc.                           *
+*                end    = adresse de fin du bloc (exclusive).                 *
+*                stop   = adresse d'arrêt en cas de saut ou VMPA_MAX.         *
+*                                                                             *
+*  Description : Procède à la définition de bloc regroupant des instructions. *
+*                                                                             *
+*  Retour      : Bloc créé et enregistré, ou NULL si erreur.                  *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static GInstrBlock *build_instruction_block(GArchInstruction *instrs, vmpa_t start, vmpa_t end, vmpa_t stop)
+{
+    GInstrBlock *result;                    /* Regroupement à retourner    */
+    GArchInstruction *first;                /* Première instruction        */
+    GArchInstruction *last;                 /* Dernière instruction        */
+    GArchInstruction *iter;                 /* Boucle de parcours          */
+    vmpa_t addr;                            /* Adresse de la destination   */
+    GArchInstruction **dests;               /* Instr. visée par une autre  */
+    InstructionLinkType *types;             /* Type de lien entre lignes   */
+    size_t dcount;                          /* Nombre de liens de dest.    */
+    size_t i;                               /* Boucle de parcours          */
+    GInstrBlock *block;                     /* Nouveau bloc mis en place   */
+    branch_info true_branch;                /* Branche 'condition vraie'   */
+    branch_info false_branch;               /* Branche 'condition fausse'  */
+    vmpa_t next_addr;                       /* Prochaine instruction visée */
+
+    result = NULL;
+
+    first = NULL;
+    last = NULL;
+
+    printf("[+] blocking 0x%08llx -> 0x%08llx... stop @ 0x%08llx\n", start, end, stop);
+
+    for (iter = g_arch_instruction_find_by_address(instrs, start, true);
+         iter != NULL;
+         )
+    {
+        g_arch_instruction_get_location(iter, NULL, NULL, &addr);
+        if (addr == stop) break;
+
+        if (first == NULL)
+            first = iter;
+
+        last = iter;
+
+        /* On s'arrêter si l'instruction est déjà décompilée */
+        if (g_object_get_data(G_OBJECT(iter), "decomp_done") != NULL) break;
+        g_object_set_data(G_OBJECT(iter), "decomp_done", iter);
+
+        /* 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, end);
+            continue;
+        }
+
+        /* Adaptations en fonction du type de bifurcation */
+
+        dcount = g_arch_instruction_get_destinations(iter, &dests, &types);
+
+        next_addr = 0;
+        memset(&true_branch, 0, sizeof(branch_info));
+        memset(&false_branch, 0, sizeof(branch_info));
+
+        for (i = 0; i < dcount; i++)
+            switch (types[i])
+            {
+                case ILT_EXEC_FLOW:
+                case ILT_JUMP:
+
+                    if (result == NULL)
+                        result = g_virtual_block_new();
+
+                    block = g_flow_block_new(instrs, first, iter);
+                    g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);
+                    first = NULL;
+
+                    g_arch_instruction_get_location(dests[i], NULL, NULL, &next_addr);
+
+                    break;
+
+                case ILT_JUMP_IF_TRUE:
+                    g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
+                    find_next_jumps(instrs, addr, end, &true_branch);
+                    break;
+
+                case ILT_JUMP_IF_FALSE:
+                    g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
+                    find_next_jumps(instrs, addr, end, &false_branch);
+                    break;
+
+                default:
+                    next_addr = VMPA_MAX;
+                    break;
+
+            }
+
+        if (next_addr == VMPA_MAX)
+        {
+            iter = g_arch_instruction_get_next_iter(instrs, iter, end);
+            continue;
+        }
+
+        else if (true_branch.count > 0 || false_branch.count > 0)
+        {
+            next_addr = compute_first_common_addr(&true_branch, &false_branch);
+            next_addr = MIN(next_addr, end);
+
+            if (result == NULL)
+                result = g_virtual_block_new();
+
+            block = g_flow_block_new(instrs, first, iter);
+            g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);
+            first = NULL;
+
+            block = build_instruction_block(instrs, true_branch.jumps[0], end, next_addr);
+            g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);
+
+            block = build_instruction_block(instrs, false_branch.jumps[0], end, next_addr);
+            g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);
+
+            free(true_branch.jumps);
+            free(false_branch.jumps);
+
+            if (next_addr == end) break;
+
+        }
+
+        /* Détermination du prochain point de chute */
+        iter = g_arch_instruction_find_by_address(instrs, next_addr, true);
+
+    }
+
+    if (first != NULL && last != NULL)
+    {
+        block = g_flow_block_new(instrs, first, last);
+
+        if (result == NULL)
+            result = block;
+        else
+            g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);
+
+    }
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : list      = ensemble d'instructions à relier.                *
+*                routines  = prototypes existants à insérer.                  *
+*                count     = quantité de ces prototypes.                      *
+*                statusbar = barre de statut avec progression à mettre à jour.*
+*                id        = identifiant du message affiché à l'utilisateur.  *
+*                                                                             *
+*  Description : Regroupe les instructions par blocs.                         *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void group_routines_instructions(GArchInstruction *list, GBinRoutine **routines, size_t count, GtkExtStatusBar *statusbar, guint id)
+{
+    size_t i;                               /* Boucle de parcours          */
+    vmpa_t start;                           /* Adresse de départ           */
+    vmpa_t end;                             /* Adresse de fin              */
+    GInstrBlock *block;                     /* Regroupement d'instructions */
+
+    for (i = 0; i < count; i++)
+    {
+        start = g_binary_routine_get_address(routines[i]);
+        end = start + g_binary_routine_get_size(routines[i]);
+
+
+        printf("==== %s ====\n", g_binary_routine_to_string(routines[i]));
+
+
+        block = build_instruction_block(list, start, end, VMPA_MAX);
+
+        gtk_extended_status_bar_update_activity(statusbar, id, (i + 1) * 1.0 / count);
+
+    }
+
+}
diff --git a/src/analysis/disass/macro.h b/src/analysis/disass/macro.h
new file mode 100644
index 0000000..64df785
--- /dev/null
+++ b/src/analysis/disass/macro.h
@@ -0,0 +1,38 @@
+
+/* OpenIDA - Outil d'analyse de fichiers binaires
+ * macro.h - prototypes pour la vue macroscopique des liens entre blocs d'instructions
+ *
+ * Copyright (C) 2012 Cyrille Bagard
+ *
+ *  This file is part of OpenIDA.
+ *
+ *  OpenIDA 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.
+ *
+ *  OpenIDA 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/>.
+ */
+
+
+#ifndef _ANALYSIS_DISASS_MACRO_H
+#define _ANALYSIS_DISASS_MACRO_H
+
+
+#include "../routine.h"
+#include "../../gtkext/gtkextstatusbar.h"
+
+
+
+/* Regroupe les instructions par blocs. */
+void group_routines_instructions(GArchInstruction *, GBinRoutine **, size_t, GtkExtStatusBar *, guint);
+
+
+
+#endif  /* _ANALYSIS_DISASS_MACRO_H */