diff options
Diffstat (limited to 'src/gtkext/graph/cluster.c')
| -rw-r--r-- | src/gtkext/graph/cluster.c | 1330 |
1 files changed, 1330 insertions, 0 deletions
diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c new file mode 100644 index 0000000..4c92718 --- /dev/null +++ b/src/gtkext/graph/cluster.c @@ -0,0 +1,1330 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * cluster.c - mise en place de graphiques + * + * Copyright (C) 2016 Cyrille Bagard + * + * This file is part of Chrysalide. + * + * 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 "cluster.h" + + +#include <assert.h> +#include <malloc.h> +#include <string.h> + + +#include "../gtkblockview.h" +#include "../gtkbufferview.h" +#include "../gtkviewpanel.h" +#include "../../common/sort.h" + + + +/* Définition du tracé d'un lien */ +typedef struct _link_def +{ + InstructionLinkType type; /* Complexité du tracé */ + + GdkPoint y; /* Position des décrochages */ + + GdkPoint end; /* Point d'arrivée final */ + + GGraphEdge *edge; /* Lien complet en préparation */ + +} link_def; + +/* Découpage vertical */ +typedef struct _graph_rank +{ + unsigned int level; /* Niveau des blocs */ + + GGraphCluster **clusters; /* Ensembles de blocs */ + size_t count; /* Nombre de ces ensembles */ + +} graph_rank; + +/* Mise en disposition de blocs en graphique (instance) */ +struct _GGraphCluster +{ + GObject parent; /* A laisser en premier */ + + + //////////////////////////////////////// + gint top_margin[2]; /* Espaces gauches et droites */ + gint left_margin; /* Espaces remontant à gauche */ + gint right_margin; /* Espaces remontant à droite */ + //////////////////////////////////////// + + + link_def **top_anchors; /* Accroches supérieures */ + size_t ta_count; /* Quantité de ces accroches */ + + GBasicBlock *block; /* Bloc d'origine représenté */ + GtkWidget *view; /* Vue graphique associée */ + GtkAllocation alloc; /* Emplacement final du bloc */ + + GdkPoint **bottom_anchors; /* Accroches inférieures */ + size_t ba_count; /* Quantité de ces accroches */ + + graph_rank *ranks; /* Répartition verticale */ + size_t ranks_count; /* Nombre de divisions */ + +}; + +/* Mise en disposition de blocs en graphique (classe) */ +struct _GGraphClusterClass +{ + GObjectClass parent; /* A laisser en premier */ + +}; + + +/* Espace minimal horizontal entre les blocs */ +#define HORIZONTAL_MARGIN 20 + +/* Espace minimal vertical entre les blocs */ +#define VERTICAL_MARGIN 30 + +/* Espace minimal entre les liens */ +#define LINK_MARGIN 10 + + +/* Initialise la classe des mises en disposition graphique. */ +static void g_graph_cluster_class_init(GGraphClusterClass *); + +/* Initialise une mise en disposition de blocs en graphique. */ +static void g_graph_cluster_init(GGraphCluster *); + +/* Supprime toutes les références externes. */ +static void g_graph_cluster_dispose(GGraphCluster *); + +/* Procède à la libération totale de la mémoire. */ +static void g_graph_cluster_finalize(GGraphCluster *); + +/* Complète un graphique avec un sous-ensemble de blocs. */ +static void g_graph_cluster_add_sub(GGraphCluster *, GGraphCluster *, GBasicBlock *); + +/* Organisation la disposition d'un ensemble de blocs basiques. */ +static void g_graph_cluster_dispatch_x(GGraphCluster *); + +/* Détermine une position pour un ensemble de blocs basiques. */ +//static void g_graph_cluster_set_x(GGraphCluster *, gint); + +/* Décalle vers la droite un ensemble de blocs basiques. */ +static void g_graph_cluster_offset_x(GGraphCluster *, gint); + +/* Décalle vers le bas un ensemble de blocs basiques. */ +static void g_graph_cluster_set_y(GGraphCluster *, gint); + + + + + +/* Recherche le bloc basique à l'extrémité d'un lien. */ +//static GGraphCluster *g_graph_cluster_find_lower_dest_cluster(const GGraphCluster *, const GArchInstruction *); + +/* Met en place les embryons de liens nécessaires. */ +static void g_graph_cluster_define_links(GGraphCluster *, GHashTable *); + +/* Détermine les positions de tous les liens en place. */ +static void g_graph_cluster_compute_link_positions(GGraphCluster *); + +/* Applique les positions calculées pour chaque lien graphique. */ +static void g_graph_cluster_resolve_links(const GGraphCluster *); + + + + + + +/* Indique le type définit par la GLib pour les mises en disposition graphique. */ +G_DEFINE_TYPE(GGraphCluster, g_graph_cluster, G_TYPE_OBJECT); + + +/****************************************************************************** +* * +* Paramètres : klass = classe à initialiser. * +* * +* Description : Initialise la classe des mises en disposition graphique. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_class_init(GGraphClusterClass *klass) +{ + GObjectClass *object; /* Autre version de la classe */ + + object = G_OBJECT_CLASS(klass); + + object->dispose = (GObjectFinalizeFunc/* ! */)g_graph_cluster_dispose; + object->finalize = (GObjectFinalizeFunc)g_graph_cluster_finalize; + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = instance à initialiser. * +* * +* Description : Initialise une mise en disposition de blocs en graphique. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_init(GGraphCluster *cluster) +{ + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = instance d'objet GLib à traiter. * +* * +* Description : Supprime toutes les références externes. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_dispose(GGraphCluster *cluster) +{ + g_object_unref(G_OBJECT(cluster->block)); + g_object_unref(G_OBJECT(cluster->view)); + + G_OBJECT_CLASS(g_graph_cluster_parent_class)->dispose(G_OBJECT(cluster)); + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = instance d'objet GLib à traiter. * +* * +* Description : Procède à la libération totale de la mémoire. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_finalize(GGraphCluster *cluster) +{ + G_OBJECT_CLASS(g_graph_cluster_parent_class)->finalize(G_OBJECT(cluster)); + +} + + +/****************************************************************************** +* * +* Paramètres : binary = binaire charger dont le code est à représenter.* +* list = ensemble de blocs basiques à manipuler. * +* index = indice du bloc principal à mettre en place. * +* highlighted = gestionnaire de surbrillance pour segments. * +* * +* Description : Construit un graphique à partir de blocs basiques. * +* * +* Retour : Adresse de la structure mise en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +GGraphCluster *g_graph_cluster_new(GLoadedBinary *binary, const GBlockList *list, size_t index, segcnt_list *highlighted) +{ + GGraphCluster *result; /* Structure à retourner */ + vmpa2t first; /* Début d'un groupe de lignes */ + vmpa2t last; /* Fin d'un groupe de lignes */ + GCodeBuffer *buffer; /* Tampon brut à découper */ + GBufferView *view; /* Partie affichée du tampon */ + GtkRequisition requisition; /* Taille à l'écran actuelle */ + + result = g_object_new(G_TYPE_GRAPH_CLUSTER, NULL); + + /* Encapsulation du bloc d'entrée */ + + result->block = g_block_list_get_block(list, index); + g_object_ref(G_OBJECT(result->block)); + + result->view = gtk_block_view_new(); + + gtk_widget_show(result->view); + gtk_view_panel_attach_binary(GTK_VIEW_PANEL(result->view), binary, BVW_GRAPH); + + gtk_view_panel_show_border(GTK_VIEW_PANEL(result->view), true); + + /* Restriction au bloc basique */ + + g_basic_block_get_boundary_addresses(result->block, &first, &last); + + buffer = g_loaded_binary_get_disassembled_buffer(binary); + + view = g_buffer_view_new(buffer, highlighted); + g_buffer_view_restrict(view, &first, &last); + gtk_buffer_view_attach_buffer(GTK_BUFFER_VIEW(result->view), view); + + /* Détermination d'une position initiale centrée */ + + gtk_widget_get_preferred_size(result->view, NULL, &requisition); + + result->alloc.x = -requisition.width / 2; + result->alloc.y = 0; + + result->alloc.width = requisition.width; + result->alloc.height = requisition.height; + + printf("BLOCK INIT :: %d <> %d\n", result->alloc.x, result->alloc.width); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à compléter. * +* sub = sous-ensemble à intégrer. * +* block = bloc basique de départ du sous-ensemble. * +* * +* Description : Complète un graphique avec un sous-ensemble de blocs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub, GBasicBlock *block) +{ + unsigned int level; /* Niveau du nouvel ensemble */ + size_t i; /* Boucle de parcours */ + graph_rank new; /* Nouvel étage à insérer */ + graph_rank *rank; /* Nouvel étage à compléter */ + + level = g_basic_block_get_rank(block); + + for (i = 0; i < cluster->ranks_count; i++) + if (cluster->ranks[i].level == level) + break; + + if (i == cluster->ranks_count) + { + new.level = level; + + new.clusters = (GGraphCluster **)calloc(1, sizeof(GGraphCluster *)); + new.count = 1; + + new.clusters[0] = sub; + + int cmp_graph_rank(const graph_rank *a, const graph_rank *b) + { + if (a->level < b->level) + return -1; + + else if (a->level > b->level) + return 1; + + else + return 0; + + } + + cluster->ranks = qinsert(cluster->ranks, &cluster->ranks_count, + sizeof(graph_rank), (__compar_fn_t)cmp_graph_rank, &new); + + } + + else + { + rank = &cluster->ranks[i]; + + rank->count++; + rank->clusters = (GGraphCluster **)realloc(rank->clusters, + sizeof(GGraphCluster *) * rank->count); + + rank->clusters[rank->count - 1] = sub; + + } + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à manipuler. * +* * +* Description : Organisation la disposition d'un ensemble de blocs basiques. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_dispatch_x(GGraphCluster *cluster) +{ + size_t k; /* Boucle de parcours #1 */ + size_t rcount; /* Nombre d'ensembles présents */ + size_t mid; /* Position centrale de départ */ + gint start; /* Position initiale de départ */ + + void place_sub(GGraphCluster **iter, size_t loop, gint base, int dir) + { + size_t i; /* Boucle de parcours #2 */ + GtkAllocation needed; /* Taille requise */ + + assert(dir == -1 || dir == 1); + + for (i = 0; i < loop; i++, iter += dir) + { + g_graph_cluster_dispatch_x(*iter); + + g_graph_cluster_compute_needed_alloc(*iter, &needed); + + if (dir > 0) + g_graph_cluster_offset_x(*iter, base - needed.x); + else + g_graph_cluster_offset_x(*iter, base - needed.x - needed.width); + + base += dir * (needed.width + HORIZONTAL_MARGIN); + + } + + } + + + + + for (k = 0; k < cluster->ranks_count; k++) + { + rcount = cluster->ranks[k].count; + + if (rcount % 2 == 1) + { + if (rcount > 1) + { + mid = rcount / 2; + + start = cluster->ranks[k].clusters[mid]->alloc.x - HORIZONTAL_MARGIN; + + place_sub(cluster->ranks[k].clusters + mid - 1, mid, start, -1); + + start *= -1; + + place_sub(cluster->ranks[k].clusters + mid + 1, mid, start, 1); + + } + + } + + else + { + mid = rcount / 2 - 1; + + start = - HORIZONTAL_MARGIN / 2; + + place_sub(cluster->ranks[k].clusters + mid, mid + 1, start, -1); + + start *= -1; + + place_sub(cluster->ranks[k].clusters + mid + 1, mid + 1, start, 1); + + } + + } + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à actualiser. * +* x = position finale sur l'axe des abscisses. * +* * +* Description : Détermine une position pour un ensemble de blocs basiques. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ +/* +static void g_graph_cluster_set_x(GGraphCluster *cluster, gint x) +{ + g_graph_cluster_offset_x(cluster, -cluster->alloc.x); + + g_graph_cluster_offset_x(cluster, x); + +} +*/ + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à actualiser. * +* offset = décallage à appliquer. * +* * +* Description : Décalle vers la droite un ensemble de blocs basiques. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_offset_x(GGraphCluster *cluster, gint offset) +{ + size_t i; /* Boucle de parcours #1 */ + size_t j; /* Boucle de parcours #2 */ + + cluster->alloc.x += offset; + + for (i = 0; i < cluster->ranks_count; i++) + for (j = 0; j < cluster->ranks[i].count; j++) + g_graph_cluster_offset_x(cluster->ranks[i].clusters[j], offset); + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à actualiser. * +* base = position ordonnée à appliquer. * +* * +* Description : Décalle vers le bas un ensemble de blocs basiques. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_set_y(GGraphCluster *cluster, gint base) +{ + size_t i; /* Boucle de parcours #1 */ + gint max; /* Hauteur maximale rencontrée */ + size_t j; /* Boucle de parcours #2 */ + GGraphCluster *sub; /* Sous-ensemble traité */ + GtkAllocation alloc; /* Allocation courante */ + + cluster->alloc.y = base; + + base += cluster->alloc.height; + + for (i = 0; i < cluster->ranks_count; i++) + { + base += VERTICAL_MARGIN; + + max = 0; + + for (j = 0; j < cluster->ranks[i].count; j++) + { + sub = cluster->ranks[i].clusters[j]; + + g_graph_cluster_set_y(sub, base); + + g_graph_cluster_compute_needed_alloc(sub, &alloc); + + if ((alloc.y + alloc.height) > max) + max = alloc.y + alloc.height; + + } + + base = max; + + } + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = encapsulation à consulter. * +* alloc = emplacement idéal pour l'affichage. * +* * +* Description : Détermine l'emplacement requis d'un ensemble de blocs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void g_graph_cluster_compute_needed_alloc(const GGraphCluster *cluster, GtkAllocation *alloc) +{ + GtkAllocation needed; /* Taille requise */ + size_t i; /* Boucle de parcours */ + size_t rcount; /* Nombre d'ensembles présents */ + + *alloc = cluster->alloc; + + for (i = 0; i < cluster->ranks_count; i++) + { + rcount = cluster->ranks[i].count; + + switch (rcount) + { + case 1: + + g_graph_cluster_compute_needed_alloc(cluster->ranks[i].clusters[0], &needed); + + if (needed.x < alloc->x) + { + alloc->width += (alloc->x + needed.x); + alloc->x = needed.x; + } + + if ((needed.x + needed.width) > (alloc->x + alloc->width)) + alloc->width += needed.x + needed.width - alloc->x - alloc->width; + + /* La hauteur maximale n'est présente qu'avec le dernier morceau */ + if ((i + 1) == cluster->ranks_count) + { + if ((needed.y + needed.height) > (alloc->y + alloc->height)) + alloc->height += needed.y + needed.height - alloc->y - alloc->height; + } + + break; + + default: + + assert(rcount >= 2); + + g_graph_cluster_compute_needed_alloc(cluster->ranks[i].clusters[0], &needed); + + if (needed.x < alloc->x) + { + alloc->width += (alloc->x + needed.x); + alloc->x = needed.x; + } + + /* La hauteur maximale n'est présente qu'avec le dernier morceau */ + if ((i + 1) == cluster->ranks_count) + { + if ((needed.y + needed.height) > (alloc->y + alloc->height)) + alloc->height += needed.y + needed.height - alloc->y - alloc->height; + } + + g_graph_cluster_compute_needed_alloc(cluster->ranks[i].clusters[rcount - 1], &needed); + + if ((needed.x + needed.width) > (alloc->x + alloc->width)) + alloc->width += needed.x + needed.width - alloc->x - alloc->width; + + /* La hauteur maximale n'est présente qu'avec le dernier morceau */ + if ((i + 1) == cluster->ranks_count) + { + if ((needed.y + needed.height) > (alloc->y + alloc->height)) + alloc->height += needed.y + needed.height - alloc->y - alloc->height; + } + + break; + + } + + } + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = encapsulation à traiter. * +* view = support de destination finale. * +* * +* Description : Dispose chaque noeud sur la surface de destination donnée. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void g_graph_cluster_place(GGraphCluster *cluster, GtkGraphView *view) +{ + size_t i; /* Boucle de parcours #1 */ + size_t j; /* Boucle de parcours #2 */ + + g_object_ref(G_OBJECT(cluster->view)); + gtk_graph_view_put(view, cluster->view, &cluster->alloc); + + for (i = 0; i < cluster->ta_count; i++) + { + g_object_ref(G_OBJECT(cluster->top_anchors[i]->edge)); + gtk_graph_view_add_edge(view, cluster->top_anchors[i]->edge); + } + + for (i = 0; i < cluster->ranks_count; i++) + for (j = 0; j < cluster->ranks[i].count; j++) + g_graph_cluster_place(cluster->ranks[i].clusters[j], view); + +} + + + + + + + + +////////////////////////////////////////////////////////// + + + + + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à consulter ou remonter. * +* first = première instruction du bloc basique recherché. * +* * +* Description : Recherche le bloc basique à l'extrémité d'un lien. * +* * +* Retour : Bloc graphique de destination pour un lien ou NULL si échec. * +* * +* Remarques : - * +* * +******************************************************************************/ +#if 0 +static GGraphCluster *g_graph_cluster_find_lower_dest_cluster(const GGraphCluster *cluster, const GArchInstruction *first) +{ + GGraphCluster *result; /* Trouvaille à retourner */ + size_t i; /* Boucle de parcours #1 */ + const graph_rank *rank; /* Confort d'accès */ + size_t j; /* Boucle de parcours #2 */ + GArchInstruction *instr; /* Instruction à comparer */ + + result = NULL; + + for (i = 0; i < cluster->ranks_count && result == NULL; i++) + { + rank = &cluster->ranks[i]; + + for (j = 0; j < rank->count && result == NULL; j++) + { + g_basic_block_get_boundary(rank->clusters[j]->block, &instr, NULL); + + if (instr == first) + result = rank->clusters[j]; + + } + + } + + return result; + +} +#endif + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à actualiser. * +* all = table regroupant tous les groupes créés. * +* * +* Description : Met en place les embryons de liens nécessaires. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all) +{ + 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 i; /* Boucle de parcours #1 */ + GGraphCluster *target; /* Bloc ciblé par un lien */ + GdkPoint *start; /* Point de départ d'un lien */ + link_def *end; /* Définitions d'arrivée */ + size_t j; /* Boucle de parcours #2 */ + + /* Au niveau du bloc courant */ + + g_basic_block_get_boundary(cluster->block, NULL, &last); + + g_arch_instruction_rlock_dest(last); + dcount = g_arch_instruction_get_destinations(last, &dests, &types, NULL); + + 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: + + target = G_GRAPH_CLUSTER(g_hash_table_lookup(all, dests[i])); + assert(target != NULL); + + /* Point de départ */ + + start = (GdkPoint *)calloc(1, sizeof(GdkPoint)); + + cluster->bottom_anchors = (GdkPoint **)realloc(cluster->bottom_anchors, + ++cluster->ba_count * sizeof(GdkPoint *)); + cluster->bottom_anchors[cluster->ba_count - 1] = start; + + /* Point d'arrivée */ + + end = (link_def *)calloc(1, sizeof(link_def)); + + target->top_anchors = (link_def **)realloc(target->top_anchors, + ++target->ta_count * sizeof(link_def *)); + target->top_anchors[target->ta_count - 1] = end; + + /* Etablissement d'un embryon de lien */ + + end->type = types[i]; + + if (types[i] == ILT_JUMP_IF_TRUE) + end->edge = g_graph_edge_new_true(start, &end->y, &end->end); + + else if (types[i] == ILT_JUMP_IF_FALSE) + end->edge = g_graph_edge_new_false(start, &end->y, &end->end); + + else + end->edge = g_graph_edge_new(start, &end->y, &end->end); + + break; + + + case ILT_LOOP: + + /* TODO */ + assert(false); + + break; + + default: + break; + + } + + g_arch_instruction_runlock_dest(last); + + /* Propagation de la mise en place */ + + for (i = 0; i < cluster->ranks_count; i++) + for (j = 0; j < cluster->ranks[i].count; j++) + g_graph_cluster_define_links(cluster->ranks[i].clusters[j], all); + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à actualiser. * +* * +* Description : Détermine les positions de tous les liens en place. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_compute_link_positions(GGraphCluster *cluster) +{ + gint mid_x; /* Abscisse centrale */ + size_t half; /* Indice de répartition égale */ + gint y; /* Ordonnée d'application */ + + size_t i; /* Boucle de parcours #1 */ + GdkPoint *pt; /* Point à actualiser */ + size_t j; /* Boucle de parcours #2 */ + + + + mid_x = cluster->alloc.x + (cluster->alloc.width / 2); + + /* Du côté des départs... */ + + if (cluster->ba_count > 0) + { + half = cluster->ba_count / 2; + + y = cluster->alloc.y + cluster->alloc.height; + + if (cluster->ba_count % 2 == 1) + { + for (i = half; i > 0; i--) + { + pt = cluster->bottom_anchors[i - 1]; + + pt->x = mid_x - (half - i + 1) * LINK_MARGIN; + pt->y = y; + + } + + pt = cluster->bottom_anchors[half]; + + pt->x = mid_x; + pt->y = y; + + for (i = half + 1; i < cluster->ba_count; i++) + { + pt = cluster->bottom_anchors[i]; + + pt->x = mid_x + (i - half) * LINK_MARGIN; + pt->y = y; + + } + + } + + else + { + for (i = half; i > 0; i--) + { + pt = cluster->bottom_anchors[i - 1]; + + pt->x = mid_x - LINK_MARGIN / 2 - (half - i) * LINK_MARGIN; + pt->y = y; + + } + + for (i = half; i < cluster->ba_count; i++) + { + pt = cluster->bottom_anchors[i]; + + pt->x = mid_x + LINK_MARGIN / 2 + (half - i) * LINK_MARGIN; + pt->y = y; + + } + + } + + } + + /* Du côté des arrivées... */ + + if (cluster->ta_count > 0) + { + half = cluster->ta_count / 2; + + y = cluster->alloc.y; + + if (cluster->ta_count % 2 == 1) + { + for (i = half; i > 0; i--) + { + pt = &cluster->top_anchors[i - 1]->end; + + pt->x = mid_x - (half - i + 1) * LINK_MARGIN; + pt->y = y; + + } + + pt = &cluster->top_anchors[half]->end; + + pt->x = mid_x; + pt->y = y; + + for (i = half + 1; i < cluster->ta_count; i++) + { + pt = &cluster->top_anchors[i]->end; + + pt->x = mid_x + (i - half) * LINK_MARGIN; + pt->y = y; + + } + + } + + else + { + for (i = half; i > 0; i--) + { + pt = &cluster->top_anchors[i - 1]->end; + + pt->x = mid_x - LINK_MARGIN / 2 - (half - i) * LINK_MARGIN; + pt->y = y; + + } + + for (i = half; i < cluster->ta_count; i++) + { + pt = &cluster->top_anchors[i]->end; + + pt->x = mid_x + LINK_MARGIN / 2 + (half - i) * LINK_MARGIN; + pt->y = y; + + } + + } + + + + + + + + + for (i = 0; i < cluster->ta_count; i++) + cluster->top_anchors[i]->y.y = cluster->top_anchors[i]->end.y - 18; + + + + + + + + } + + /* Propagation des déterminations */ + + for (i = 0; i < cluster->ranks_count; i++) + for (j = 0; j < cluster->ranks[i].count; j++) + g_graph_cluster_compute_link_positions(cluster->ranks[i].clusters[j]); + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à consulter. * +* * +* Description : Applique les positions calculées pour chaque lien graphique. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_resolve_links(const GGraphCluster *cluster) +{ + size_t i; /* Boucle de parcours #1 */ + size_t j; /* Boucle de parcours #2 */ + + for (i = 0; i < cluster->ta_count; i++) + g_graph_edge_resolve(cluster->top_anchors[i]->edge); + + for (i = 0; i < cluster->ranks_count; i++) + for (j = 0; j < cluster->ranks[i].count; j++) + g_graph_cluster_resolve_links(cluster->ranks[i].clusters[j]); + +} + + + + + + + + + + + + + + + + +/* Liste de blocs restants à traiter */ +typedef struct _pending_blocks +{ + size_t count; /* Taille de la liste */ + GBasicBlock *list[0]; /* Liste de blocs à traiter */ + +} pending_blocks; + + + + + +/* Met en place un ensemble de blocs sous forme graphique. */ +static GGraphCluster *setup_graph_clusters(GLoadedBinary *, const GBlockList *, size_t , segcnt_list *, pending_blocks *, GHashTable *); + + + + + +/****************************************************************************** +* * +* Paramètres : binary = binaire charger dont le code est à représenter.* +* list = ensemble de blocs basiques à manipuler. * +* index = indice du bloc principal à mettre en place. * +* highlighted = gestionnaire de surbrillance pour segments. * +* pending = liste de blocs restant à traiter. [OUT] * +* all = table regroupant tous les groupes créés. * +* * +* Description : Met en place un ensemble de blocs sous forme graphique. * +* * +* Retour : Ensemble de blocs mis en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static GGraphCluster *setup_graph_clusters(GLoadedBinary *binary, const GBlockList *list, size_t index, segcnt_list *highlighted, pending_blocks *pending, GHashTable *all) +{ + GGraphCluster *result; /* Instance nouvelle à renvoyer*/ + GBasicBlock *block; /* Bloc à manipuler */ + GArchInstruction *first; /* Première instruction du bloc*/ + GArchInstruction *last; /* Dernière instruction du bloc*/ +#ifndef NDEBUG + gboolean new; /* Bloc déjà traité ? */ +#endif + 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 #1 */ + GBasicBlock *target; /* Bloc ciblé par un lien */ + size_t j; /* Boucle de parcours #2 */ + bool changed; /* Un ajout a été effectué ? */ + const bitfield_t *dominators; /* Blocs dominant ce même bloc */ + size_t next; /* Indice du prochain bloc */ + GGraphCluster *sub; /* Sous-ensemble à intégrer */ + + result = g_graph_cluster_new(binary, list, index, highlighted); + + block = g_block_list_get_block(list, index); + + g_basic_block_get_boundary(block, &first, &last); + +#ifndef NDEBUG + new = g_hash_table_insert(all, first, result); + assert(new); +#else + g_hash_table_insert(all, first, result); +#endif + + /* Détermination des blocs suivants */ + + g_arch_instruction_rlock_dest(last); + dcount = g_arch_instruction_get_destinations(last, &dests, &types, NULL); + + printf(" ... block=%p dest=%zu\n", block, dcount); + + 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: + + target = g_block_list_find_by_starting_instr(list, dests[i]); + + /** + * Les sauts ne se font pas toujours à l'intérieur d'une même fonction. + * Par exemple sous ARM : + * + * 00008358 <call_gmon_start>: + * .... + * 8362: f7ff bfcf b.w 8304 <_init+0x38> + * .... + * + */ + + printf(" NEW BLK :: %d -> %p\n", types[i], target); + + if (target != NULL) + { + for (j = 0; j < pending->count; j++) + if (pending->list[j] == target) + break; + + if (j == pending->count) + { + assert((pending->count + 1) < g_block_list_count_blocks(list)); + pending->list[pending->count++] = target; + printf(" --push-- %d -> %p\n", types[i], target); + } + + do + { + size_t k; + printf(" --stack-- "); + for (k = 0; k < pending->count; k++) + printf("%p ", pending->list[k]); + printf("\n"); + } + while (0); + + + + } + + break; + + default: + break; + + } + + g_arch_instruction_runlock_dest(last); + + /* Intégration de tous les blocs en attente */ + + do + { + changed = false; + + for (i = 0; i < pending->count && !changed; i++) + { + block = pending->list[i]; + dominators = g_basic_block_get_domination(block); + + if (test_in_bit_field(dominators, index, 1)) + { + /* Dépilement */ + + changed = true; + + if ((i + 1) < pending->count) + memmove(&pending->list[i], &pending->list[i + 1], + (pending->count - i - 1) * sizeof(GBasicBlock *)); + + pending->count--; + + /* Intégration */ + + next = g_block_list_get_index(list, block); + assert(next < g_block_list_count_blocks(list)); + + printf(" --pop-- block=%p index=%zu\n", block, next); + + sub = setup_graph_clusters(binary, list, next, highlighted, pending, all); + + g_graph_cluster_add_sub(result, sub, block); + + } + + } + + } + while (changed); + + return result; + +} + + + + + +/****************************************************************************** +* * +* Paramètres : blocks = ensemble des blocs basiques déjà découpés. * +* views = morceaux de code à afficher de façon organisée. * +* count = quantité de ces morceaux de code. * +* * +* Description : Construit un graphique à partir de blocs basiques. * +* * +* Retour : Adresse de la structure mise en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *list, segcnt_list *highlighted) +{ + GGraphCluster *result; /* Structure à retourner */ + GHashTable *all; /* Collection des créations */ + size_t count; /* Taille de la liste de blocs */ + pending_blocks *pending; /* Suivi des blocs à traiter */ + GtkAllocation needed; /* Taille requise */ + + + all = g_hash_table_new(NULL, NULL); + + count = g_block_list_count_blocks(list); + + pending = (pending_blocks *)calloc(1, sizeof(pending_blocks) + count * sizeof(GBasicBlock *)); + + + + + do + { + size_t i; + GBasicBlock *block; + const bitfield_t *domination; + + printf("DBG // count : %zu\n", count); + + for (i = 0; i < count; i++) + { + block = g_block_list_get_block(list, i); + domination = g_basic_block_get_domination(block); + + printf("DBG // block [%zu] : 0x%08lx -- rank = %u\n", + i, gfw(domination), g_basic_block_get_rank(block)); + + } + + fflush(NULL); + + } + while (0); + + + + + + result = setup_graph_clusters(binary, list, 0, highlighted, pending, all); + + free(pending); + + g_graph_cluster_define_links(result, all); + + /* Positionnements dans l'espace */ + + g_graph_cluster_dispatch_x(result); + + g_graph_cluster_set_y(result, 0); + + /* Réajustement vers la droite */ + + g_graph_cluster_compute_needed_alloc(result, &needed); + + g_graph_cluster_offset_x(result, -needed.x); + + /* Application finale sur les liens */ + + g_graph_cluster_compute_link_positions(result); + + g_graph_cluster_resolve_links(result); + + + + + g_hash_table_unref(all); + + + return result; + + +} |