Defined the first steps towards new graph renderings.

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

1 files changed, 413 insertions, 0 deletions

diff --git a/src/analysis/disass/rank.c b/src/analysis/disass/rank.c
new file mode 100644
index 0000000..6f12f31
--- /dev/null
+++ b/src/analysis/disass/rank.c
@@ -0,0 +1,413 @@
+
+/* OpenIDA - Outil d'analyse de fichiers binaires
+ * rank.c - classement des blocs d'instructions
+ *
+ * Copyright (C) 2013 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 "rank.h"
+
+
+#include "../blocks/flow.h"
+#include "../blocks/virtual.h"
+
+
+#if 0
+/* Marque la profondeur d'un bloc d'instructions. */
+static void rank_flow_block_content(GFlowBlock *, const GInstrBlock *);
+
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : block = bloc d'instructions démarrant la visite.             *
+*                list  = ensemble des blocs basiques à parcourir.             *
+*                                                                             *
+*  Description : Marque la profondeur d'un bloc d'instructions.               *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void rank_flow_block_content(GFlowBlock *block, const GInstrBlock *list)
+{
+    GArchInstruction *last;                 /* Dernière instruction du bloc*/
+    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 k;                               /* Boucle de parcours #1       */
+    size_t i;                               /* Boucle de parcours #2       */
+    vmpa_t addr;                            /* Adresse de la destination   */
+    GInstrBlock *next;                      /* Bloc suivant à visiter      */
+    bool loop;                              /* Détection de rebouclage     */
+    //unsigned int old_rank;                  /* Rang avant intervention     */
+
+    g_flow_block_get_boundary(block, NULL, &last);
+    dcount = g_arch_instruction_get_destinations(last, &dests, &types, NULL);
+
+    for (k = 0; k < 2; k++)
+        for (i = 0; i < dcount; i++)
+            switch (types[i])
+            {
+                case ILT_EXEC_FLOW:
+                case ILT_JUMP:
+                case ILT_CASE_JUMP:
+                case ILT_JUMP_IF_TRUE:
+                case ILT_JUMP_IF_FALSE:
+
+                    g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
+                    next = g_instr_block_find_by_addr(list, addr, true);
+
+                    /**
+                     * On traite en premier les liens qui conduisent à un rebouclage,
+                     * afin d'avoir des indices importants à offrir pour les autres liens
+                     * par la suite.
+                     */
+                    loop = g_flow_block_is_looping_to(G_FLOW_BLOCK(next), list, block);
+                    //if (loop != (k == 0)) continue;
+
+                    if (loop)
+                    printf("next :: %u (i=%zu k=%zu)\n", g_flow_block_get_next_rank(block), i, k);
+
+
+                    if (loop == (k == 0))
+                    {
+                    g_flow_block_set_rank(G_FLOW_BLOCK(next), g_flow_block_get_next_rank(block));
+
+                    rank_flow_block_content(G_FLOW_BLOCK(next), list);
+                    }
+                    break;
+
+                case ILT_LOOP:
+                    g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
+                    next = g_instr_block_find_by_addr(list, addr, true);
+
+
+                    /**
+                     * On traite en premier les liens qui conduisent à un rebouclage,
+                     * afin d'avoir des indices importants à offrir pour les autres liens
+                     * par la suite.
+                     */
+                    loop = g_flow_block_is_looping_to(G_FLOW_BLOCK(next), list, block);
+                    //if (loop != (k == 0)) continue;
+
+
+                    if (loop == (k == 0))
+                    {
+                        printf("loop next :: %u (i=%zu k=%zu)\n", g_flow_block_get_next_rank(block), i, k);
+
+
+                    g_flow_block_set_next_rank(G_FLOW_BLOCK(next),
+                                               g_flow_block_get_next_rank(block));
+
+                    }
+
+                    break;
+
+                default:
+                    break;
+
+            }
+
+
+
+
+
+
+
+#if 0
+    /**
+     * Si un bloc contient un retour sur lui même, on définit l'indice pour les
+     * blocs suivants découlant de cette boucle avant de traiter ces blocs suivants.
+     */
+    for (i = 0; i < dcount; i++)
+        switch (types[i])
+        {
+            case ILT_LOOP:
+                g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
+                next = g_instr_block_find_by_addr(list, addr, true);
+                g_flow_block_set_next_rank(G_FLOW_BLOCK(next), g_flow_block_get_next_rank(block));
+                break;
+
+            default:
+                break;
+
+        }
+
+    for (i = 0; i < dcount; i++)
+        switch (types[i])
+        {
+            case ILT_EXEC_FLOW:
+            case ILT_JUMP:
+            case ILT_CASE_JUMP:
+            case ILT_JUMP_IF_TRUE:
+            case ILT_JUMP_IF_FALSE:
+
+                g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
+                next = g_instr_block_find_by_addr(list, addr, true);
+
+                old_rank = g_flow_block_get_rank(G_FLOW_BLOCK(next));
+                g_flow_block_set_rank(G_FLOW_BLOCK(next), g_flow_block_get_next_rank(block));
+
+                /* Si un traitement n'a pas déjà été fait... */
+                if (old_rank == 0 || 1)
+                    rank_flow_block_content(G_FLOW_BLOCK(next), list);
+
+            default:
+                break;
+
+        }
+#endif
+
+}
+
+#endif
+
+
+
+
+/* Classe le contenu d'un bloc d'instructions exécutées. */
+static unsigned int rank_flow_block(GFlowBlock *, const GInstrBlock *, unsigned int);
+
+/* Classe le contenu d'un bloc d'instructions virtuel. */
+static unsigned int rank_virtual_block(GVirtualBlock *, const GInstrBlock *, unsigned int);
+
+/* Classe le contenu d'un bloc d'instructions quelconque. */
+static unsigned int rank_instructions_block(GInstrBlock *, const GInstrBlock *, unsigned int);
+
+
+
+
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : block = bloc d'instructions concerné par la visite.          *
+*                list  = ensemble des blocs basiques à parcourir.             *
+*                rank  = rang courant du classement en courant.               *
+*                                                                             *
+*  Description : Classe le contenu d'un bloc d'instructions exécutées.        *
+*                                                                             *
+*  Retour      : Rang pour les blocs suivants.                                *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static unsigned int rank_flow_block(GFlowBlock *block, const GInstrBlock *list, unsigned int rank)
+{
+    unsigned int result;                    /* Rang suivant à retourner    */
+    GInstrBlock *links;                     /* Blocs liés au bloc courant  */
+    GArchInstruction *last;                 /* Dernière instruction du bloc*/
+    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 k;                               /* Boucle de parcours #1       */
+    size_t i;                               /* Boucle de parcours #2       */
+    vmpa_t addr;                            /* Adresse de la destination   */
+    GInstrBlock *next;                      /* Bloc suivant à visiter      */
+    bool loop;                              /* Détection de rebouclage     */
+
+    /* On traite le bloc courant */
+
+    result = rank;
+    g_flow_block_set_rank(block, result++);
+
+    /* Viennent ensuite les blocs rattachés */
+
+    links = g_instr_block_get_links_block(G_INSTR_BLOCK(block));
+
+    if (links != NULL)
+    {
+        g_flow_block_get_boundary(block, NULL, &last);
+        dcount = g_arch_instruction_get_destinations(last, &dests, &types, NULL);
+
+        for (k = 0; k < 2; k++)
+            for (i = 0; i < dcount; i++)
+                switch (types[i])
+                {
+                    case ILT_CASE_JUMP:
+                    case ILT_JUMP_IF_TRUE:
+                    case ILT_JUMP_IF_FALSE:
+
+                        g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
+
+                        next = g_instr_block_find_by_addr(links, addr, true);
+
+                        /**
+                         * En cas d'une branche unique, l'adresse peut ne pas être trouvée
+                         * dans les sous-blocs ; logiquement, elle sera traitée plus tard,
+                         * dans la continuité de ce bloc.
+                         */
+                        if (next == NULL) break;
+
+                        /**
+                         * On traite en premier les liens qui conduisent à un rebouclage,
+                         * afin d'avoir des indices importants à offrir pour les autres liens
+                         * par la suite.
+                         */
+                        loop = g_flow_block_is_looping_to(G_FLOW_BLOCK(next), list, block);
+                        if (loop != (k == 0)) continue;
+
+                        next = g_instr_block_find_by_addr(links, addr, false);
+                        result = MAX(rank_instructions_block(next, list, rank + 1), result);
+
+                        break;
+
+                    default:
+                        break;
+
+                }
+
+    }
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : block = bloc d'instructions concerné par la visite.          *
+*                list  = ensemble des blocs basiques à parcourir.             *
+*                rank  = rang courant du classement en courant.               *
+*                                                                             *
+*  Description : Classe le contenu d'un bloc d'instructions virtuel.          *
+*                                                                             *
+*  Retour      : Rang pour les blocs suivants.                                *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static unsigned int rank_virtual_block(GVirtualBlock *block, const GInstrBlock *list, unsigned int rank)
+{
+    unsigned int result;                    /* Rang suivant à retourner    */
+    size_t max;                             /* Borne du parcours           */
+    size_t i;                               /* Boucle de parcours          */
+    GInstrBlock *child;                     /* Sous-bloc à traiter         */
+
+    result = rank;
+
+    max = g_virtual_block_count_children(block);
+
+    for (i = 0; i < max; i++)
+    {
+        child = g_virtual_block_get_child(block, i);
+        if (!G_IS_FLOW_BLOCK(child)) continue;
+
+        result = rank_instructions_block(child, list, result);
+
+    }
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : block = bloc d'instructions concerné par la visite.          *
+*                list  = ensemble des blocs basiques à parcourir.             *
+*                rank  = rang courant du classement en courant.               *
+*                                                                             *
+*  Description : Classe le contenu d'un bloc d'instructions quelconque.       *
+*                                                                             *
+*  Retour      : Rang pour les blocs suivants.                                *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static unsigned int rank_instructions_block(GInstrBlock *block, const GInstrBlock *list, unsigned int rank)
+{
+    unsigned int result;                    /* Rang suivant à retourner    */
+
+    if (G_IS_VIRTUAL_BLOCK(block))
+        result = rank_virtual_block(G_VIRTUAL_BLOCK(block), list, rank);
+
+    else if (G_FLOW_BLOCK(block))
+        result = rank_flow_block(G_FLOW_BLOCK(block), list, rank);
+
+    else
+        result = rank;
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : routine = routine à traiter.                                 *
+*                                                                             *
+*  Description : Classe les blocs d'une routine donnée.                       *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void rank_routine_blocks(GBinRoutine *routine)
+{
+    GInstrBlock *list;                      /* Ensemble des blocs d'instr. */
+    //vmpa_t start;                           /* Adresse de départ           */
+    //GFlowBlock *first;                      /* Premier bloc de la routine  */
+
+    list = g_binary_routine_get_basic_blocks(routine);
+
+    rank_instructions_block(list, list, 0);
+
+    /*
+    start = g_binary_routine_get_address(routine);
+    first = G_FLOW_BLOCK(g_instr_block_find_by_addr(list, start, true));
+
+    rank_flow_block_content(first, list);
+    */
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  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 : Classe les blocs des routines.                               *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void rank_routines_blocks(GBinRoutine **routines, size_t count, GtkExtStatusBar *statusbar, guint id)
+{
+    size_t i;                               /* Boucle de parcours          */
+
+    for (i = 0; i < count; i++)
+        rank_routine_blocks(routines[i]);
+
+}