/* Chrysalide - Outil d'analyse de fichiers binaires * flow.c - encapsulation graphique des blocs d'exécution * * Copyright (C) 2013 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 . */ #include "flow.h" #include "../layout.h" #include "../node-int.h" /* Type d'un accrochage pour lien */ struct _node_slot_t { GArchInstruction *instr; /* Instruction liée */ size_t group_index; /* Rang dans le grp d'origine */ InstructionLinkType type; /* Type de lien à représenter */ size_t slot_index; /* Position dans l'accroche */ gint x; /* Abscisse graphique du rendu */ }; /* Encapsulation graphique d'un bloc d'exécution (instance) */ struct _GFlowNode { GGraphNode parent; /* A laisser en premier */ GFlowBlock *block; /* Bloc d'exécution associé */ GtkBufferView *view; /* Représentation graphique */ node_slot_t *entries; /* Positions des pts d'entrées */ size_t entries_count; /* Nombre de ces points */ node_slot_t *exits; /* Positions des pts de sorties*/ size_t exits_count; /* Nombre de ces points */ }; /* Encapsulation graphique d'un bloc d'exécution (classe) */ struct _GFlowNodeClass { GGraphNodeClass parent; /* A laisser en premier */ }; #define SPACE_BETWEEN_SLOT 15 /* Initialise la classe des encapsulations de bloc d'exécution. */ static void g_flow_node_class_init(GFlowNodeClass *); /* Initialise une encapsulation de bloc d'exécution. */ static void g_flow_node_init(GFlowNode *); /* Supprime toutes les références externes. */ static void g_flow_node_dispose(GFlowNode *); /* Procède à la libération totale de la mémoire. */ static void g_flow_node_finalize(GFlowNode *); /* Fournit le rang du noeud dans le graphique. */ static unsigned int g_flow_node_get_rank(const GFlowNode *); /* Organise le contenu du noeud selon l'axe des abscisses. */ static void g_flow_node_prepare_x_line(GFlowNode *, GGraphNode *); /* Parcourt tous les blocs d'instructions dans un ordre donné. */ static bool g_flow_node_visit_flow_nodes(GFlowNode *, graph_node_visitor_cb, void *); /* ------------------------ GESTION DES ACCROCHES D'UN NOEUD ------------------------ */ /* Prépare les points d'entrées du noeud. */ static void g_flow_node_setup_entry_slots(GFlowNode *); /* Prépare les points de sorties du noeud. */ static void g_flow_node_setup_exit_slots(GFlowNode *); /* Etablit un lien entre deux noeuds graphiques. */ static node_slot_t *g_flow_node_get_slot(const GFlowNode *, bool, GArchInstruction *, size_t); /* Localise un point d'accroche à un noeud graphique. */ static gint g_flow_node_get_slot_offset(const GFlowNode *, bool, const node_slot_t *); /* Indique le type définit par la GLib pour l'encapsulation d'un bloc d'exécution. */ G_DEFINE_TYPE(GFlowNode, g_flow_node, G_TYPE_GRAPH_NODE); /****************************************************************************** * * * Paramètres : klass = classe à initialiser. * * * * Description : Initialise la classe des encapsulations de bloc d'exécution. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_flow_node_class_init(GFlowNodeClass *klass) { GObjectClass *object; /* Autre version de la classe */ object = G_OBJECT_CLASS(klass); object->dispose = (GObjectFinalizeFunc/* ! */)g_flow_node_dispose; object->finalize = (GObjectFinalizeFunc)g_flow_node_finalize; } /****************************************************************************** * * * Paramètres : node = instance à initialiser. * * * * Description : Initialise une encapsulation de bloc d'exécution. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_flow_node_init(GFlowNode *node) { GGraphNode *base; /* Version basique */ base = G_GRAPH_NODE(node); base->get_rank = (get_node_rank_fc)g_flow_node_get_rank; base->prepare_x = (node_prepare_x_fc)g_flow_node_prepare_x_line; base->visit = (visit_flow_nodes_fc)g_flow_node_visit_flow_nodes; } /****************************************************************************** * * * Paramètres : node = instance d'objet GLib à traiter. * * * * Description : Supprime toutes les références externes. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_flow_node_dispose(GFlowNode *node) { size_t i; /* Boucle de parcours */ g_object_unref(G_OBJECT(node->block)); g_object_unref(G_OBJECT(node->view)); for (i = 0; i < node->entries_count; i++) g_object_unref(G_OBJECT(node->entries[i].instr)); for (i = 0; i < node->exits_count; i++) g_object_unref(G_OBJECT(node->exits[i].instr)); G_OBJECT_CLASS(g_flow_node_parent_class)->dispose(G_OBJECT(node)); } /****************************************************************************** * * * Paramètres : node = instance d'objet GLib à traiter. * * * * Description : Procède à la libération totale de la mémoire. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_flow_node_finalize(GFlowNode *node) { if (node->entries != NULL) free(node->entries); if (node->exits != NULL) free(node->exits); G_OBJECT_CLASS(g_flow_node_parent_class)->finalize(G_OBJECT(node)); } /****************************************************************************** * * * Paramètres : block = bloc d'exécution représenté graphiquement. * * view = morceau d'affichage à représenter. * * * * Description : Encapsule graphiquement un bloc d'exécution. * * * * Retour : Adresse de la structure mise en place. * * * * Remarques : - * * * ******************************************************************************/ GGraphNode *g_flow_node_new(GFlowBlock *block, GtkBufferView *view) { GFlowNode *result; /* Structure à retourner */ GtkRequisition requisition; /* Taille à l'écran actuelle */ result = g_object_new(G_TYPE_FLOW_NODE, NULL); g_object_ref(G_OBJECT(block)); g_object_ref(G_OBJECT(view)); result->block = block; result->view = view; gtk_widget_size_request(GTK_WIDGET(result->view), &requisition); G_GRAPH_NODE(result)->alloc.width = requisition.width; G_GRAPH_NODE(result)->alloc.height = requisition.height; g_flow_node_setup_entry_slots(result); g_flow_node_setup_exit_slots(result); return G_GRAPH_NODE(result); } /****************************************************************************** * * * Paramètres : node = noeud graphique à consulter. * * * * Description : Fournit le rang du noeud dans le graphique. * * * * Retour : Indice supérieur ou égal à zéro. * * * * Remarques : - * * * ******************************************************************************/ static unsigned int g_flow_node_get_rank(const GFlowNode *node) { return g_flow_block_get_rank(node->block); } /****************************************************************************** * * * Paramètres : node = noeud d'encapsulation à traiter. * * nodes = ensemble des noeuds en place. * * * * Description : Organise le contenu du noeud selon l'axe des abscisses. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_flow_node_prepare_x_line(GFlowNode *node, GGraphNode *nodes) { GGraphNode *base; /* Autre vision de l'instance */ GArchInstruction *last; /* Dernière instr. du noeud */ GFlowNode *target; /* Bloc visé par le lien */ node_slot_t *dest_slot; /* Accrochage d'arrivée */ pending_position pos; /* Position à transmettre */ GFlowNode *target_a; /* Bloc visé par le lien #a */ GFlowNode *target_b; /* Bloc visé par le lien #b */ unsigned int rank_a; /* Indice du rang associé #a */ unsigned int rank_b; /* Indice du rang associé #b */ GGraphNode *container; /* Conteneur à positionner */ base = G_GRAPH_NODE(node); g_flow_block_get_boundary(node->block, NULL, &last); switch (node->exits_count) { case 0: break; case 1: if (node->exits[0].type == ILT_LOOP) break; target = G_FLOW_NODE(find_node_for_instruction(nodes, node->exits[0].instr)); dest_slot = g_flow_node_get_slot(target, true, last, node->exits[0].group_index); pos.direct_x = g_flow_node_get_slot_offset(target, true, dest_slot); pos.direct_x = (G_GRAPH_NODE(target)->alloc.width / 2) - pos.direct_x; if (target->entries_count == 1) g_graph_node_set_pending_position(G_GRAPH_NODE(target), PPF_DIRECT_X, pos, base); break; case 2: target_a = G_FLOW_NODE(find_node_for_instruction(nodes, node->exits[0].instr)); target_b = G_FLOW_NODE(find_node_for_instruction(nodes, node->exits[1].instr)); rank_a = g_flow_node_get_rank(target_a); rank_b = g_flow_node_get_rank(target_b); if (rank_a == rank_b) break; /* Alignement d'un bloc lié */ if (rank_a > rank_b) { /* Seuil vertical pour un côté */ container = g_graph_node_find_container_at_same_level(nodes, G_GRAPH_NODE(node), G_GRAPH_NODE(target_b)); if (container == NULL) container = G_GRAPH_NODE(target_b); pos.left_margin = g_flow_node_get_slot_offset(node, false, &node->exits[0]); g_graph_node_set_pending_position(container, PPF_LEFT_MARGIN, pos, base); /* Trait vertical de l'autre côté... */ pos.direct_x = pos.left_margin; dest_slot = g_flow_node_get_slot(target_a, true, last, node->exits[0].group_index); pos.direct_x -= g_flow_node_get_slot_offset(target_a, true, dest_slot); g_graph_node_set_pending_position(G_GRAPH_NODE(target_a), PPF_DIRECT_X, pos, base); } else { /* Seuil vertical pour un côté */ container = g_graph_node_find_container_at_same_level(nodes, G_GRAPH_NODE(node), G_GRAPH_NODE(target_a)); if (container == NULL) container = G_GRAPH_NODE(target_a); pos.right_margin = g_flow_node_get_slot_offset(node, false, &node->exits[1]); g_graph_node_set_pending_position(container, PPF_RIGHT_MARGIN, pos, base); /* Trait vertical de l'autre côté... */ pos.direct_x = pos.right_margin; dest_slot = g_flow_node_get_slot(target_b, true, last, node->exits[1].group_index); pos.direct_x -= g_flow_node_get_slot_offset(target_b, true, dest_slot); g_graph_node_set_pending_position(G_GRAPH_NODE(target_b), PPF_DIRECT_X, pos, base); } break; } } /****************************************************************************** * * * Paramètres : node = noeud graphique démarrant la visite. * * callback = ensemble de blocs à parcourir. * * data = donnée utilisateur à associer au parcours. * * * * Description : Parcourt tous les blocs d'instructions dans un ordre donné. * * * * Retour : true si le parcours a été jusqu'à son terme, false sinon. * * * * Remarques : - * * * ******************************************************************************/ static bool g_flow_node_visit_flow_nodes(GFlowNode *node, graph_node_visitor_cb callback, void *data) { return callback(G_GRAPH_NODE(node), GVS_NODE, data); } /****************************************************************************** * * * Paramètres : node = noeud graphique à consulter. * * instr = instruction à considérer. * * * * Description : Précise si le noeud a pour première instruction celle donnée.* * * * Retour : true si la première instruction du noeud est celle indiquée. * * * * Remarques : - * * * ******************************************************************************/ bool g_flow_node_start_with(const GFlowNode *node, GArchInstruction *instr) { GArchInstruction *first; /* Première instr. du noeud */ g_flow_block_get_boundary(node->block, &first, NULL); /* do { vmpa_t a1, a2; g_arch_instruction_get_location(instr, NULL, NULL, &a1); g_arch_instruction_get_location(first, NULL, NULL, &a2); printf(" -- compare %p (0x%08lx) vs %p (0x%08lx)\n", instr, a1, first, a2); } while (0); */ return (first == instr); } /****************************************************************************** * * * Paramètres : node = noeud graphique à consulter. * * ranks = classement à mettre à jour. * * * * Description : Précise la hauteur minimale requise pour un noeud. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ void g_flow_node_register_rank(const GFlowNode *node, GGraphRanks *ranks) { unsigned int index; /* Indice du rang associé */ index = g_flow_node_get_rank(node); g_graph_ranks_set_min_height(ranks, index, G_GRAPH_NODE(node)->alloc.height); } /****************************************************************************** * * * Paramètres : node = noeud graphique à mettre à jour. * * ranks = classement à consulter. * * * * Description : Définit l'ordonnée de l'espace attribué à un noeud. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ void g_flow_node_apply_rank(GFlowNode *node, GGraphRanks *ranks) { unsigned int index; /* Indice du rang associé */ index = g_flow_node_get_rank(node); G_GRAPH_NODE(node)->alloc.y = g_graph_ranks_get_y_for_rank(ranks, index); } /****************************************************************************** * * * Paramètres : node = noeud graphique à mettre à jour. * * layout = disposition globale du graphique. * * nodes = ensemble des noeuds en place. * * * * Description : Etablit les liaison entre un noeud et ses suivants. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ void g_flow_node_link(GFlowNode *node, GGraphLayout *layout, GGraphNode *nodes) { GArchInstruction *last; /* Dernière instr. du noeud */ size_t i; /* Boucle de parcours */ GFlowNode *target; /* Bloc visé par le lien */ node_slot_t *dest_slot; /* Accrochage d'arrivée */ EdgeColor color; /* Couleur du lien à créer */ GGraphEdge *edge; /* Lien à mettre en place */ g_flow_block_get_boundary(node->block, NULL, &last); for (i = 0; i < node->exits_count; i++) { target = G_FLOW_NODE(find_node_for_instruction(nodes, node->exits[i].instr)); dest_slot = g_flow_node_get_slot(target, true, last, node->exits[i].group_index); switch (node->exits[i].type) { case ILT_JUMP_IF_TRUE: color = EGC_GREEN; break; case ILT_JUMP_IF_FALSE: color = EGC_RED; break; case ILT_LOOP: color = EGC_BLUE; break; case ILT_CATCH_EXCEPTION: color = EGC_DASHED_GRAY; break; default: color = EGC_DEFAULT; break; } edge = g_graph_edge_new(node, &node->exits[i], target, dest_slot, color); g_graph_layout_add_edge(layout, edge); } } /****************************************************************************** * * * Paramètres : node = intermédiaire à consulter. * * view = support de destination. * * * * Description : Place un noeud sur son support final. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ void g_flow_node_place(const GFlowNode *node, GtkGraphView *view) { printf("[put] %p (%d ; %d) - (%d ; %d)\n", node, G_GRAPH_NODE(node)->alloc.x, G_GRAPH_NODE(node)->alloc.y, G_GRAPH_NODE(node)->alloc.width, G_GRAPH_NODE(node)->alloc.height); gtk_graph_view_put(view, GTK_WIDGET(node->view), &G_GRAPH_NODE(node)->alloc); } /* ---------------------------------------------------------------------------------- */ /* GESTION DES ACCROCHES D'UN NOEUD */ /* ---------------------------------------------------------------------------------- */ /****************************************************************************** * * * Paramètres : node = intermédiaire à compléter. * * * * Description : Prépare les points d'entrées du noeud. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_flow_node_setup_entry_slots(GFlowNode *node) { GArchInstruction *first; /* Première instr. du noeud */ GArchInstruction **instrs; /* Instr. visée par une autre */ InstructionLinkType *types; /* Type de lien entre lignes */ size_t icount; /* Nombre de liens de dest. */ size_t i; /* Boucle de parcours */ g_flow_block_get_boundary(node->block, &first, NULL); icount = g_arch_instruction_get_sources(first, &instrs, &types); node->entries = (node_slot_t *)calloc(icount, sizeof(node_slot_t)); node->entries_count = icount; for (i = 0; i < icount; i++) { g_object_ref(instrs[i]); node->entries[i].instr = instrs[i]; node->entries[i].type = types[i]; node->entries[i].group_index = g_arch_instruction_compute_group_index(&instrs[i], instrs, icount); node->entries[i].slot_index = i; } } /****************************************************************************** * * * Paramètres : node = intermédiaire à compléter. * * * * Description : Prépare les points de sorties du noeud. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_flow_node_setup_exit_slots(GFlowNode *node) { GArchInstruction *last; /* Dernière instr. du noeud */ GArchInstruction **instrs; /* Instr. visée par une autre */ InstructionLinkType *types; /* Type de lien entre lignes */ size_t icount; /* Nombre de liens de dest. */ size_t i; /* Boucle de parcours */ g_flow_block_get_boundary(node->block, NULL, &last); icount = g_arch_instruction_get_destinations(last, &instrs, &types, NULL); node->exits = (node_slot_t *)calloc(icount, sizeof(node_slot_t)); node->exits_count = icount; for (i = 0; i < icount; i++) { g_object_ref(instrs[i]); node->exits[i].instr = instrs[i]; node->exits[i].type = types[i]; node->exits[i].group_index = g_arch_instruction_compute_group_index(&instrs[i], instrs, icount); node->exits[i].slot_index = i; } } /****************************************************************************** * * * Paramètres : node = noeud graphique à consulter. * * entry = indique le type d'accrochage recherché. * * instr = instruction visée. * * index = indice de groupe pour départager au besoin. * * * * Description : Etablit un lien entre deux noeuds graphiques. * * * * Retour : Lien graphique mis en place. * * * * Remarques : - * * * ******************************************************************************/ static node_slot_t *g_flow_node_get_slot(const GFlowNode *node, bool entry, GArchInstruction *instr, size_t index) { node_slot_t *result; /* Emplacement à retourner */ node_slot_t *list; /* Liste à parcourir */ size_t count; /* Taille de cette liste */ size_t i; /* Boucle de parcours */ if (entry) { list = node->entries; count = node->entries_count; } else { list = node->exits; count = node->exits_count; } for (i = 0; i < count; i++) { result = list + i; if (result->instr == instr/* && result->group_index == index*/) break; } return (i == count ? NULL : result); } /****************************************************************************** * * * Paramètres : node = noeud graphique à consulter. * * entry = indique le type d'accrochage recherché. * * slot = accroche dont l'emplacement est à définir. * * * * Description : Localise un point d'accroche à un noeud graphique. * * * * Retour : Décallage relatif pour l'accroche fournie. * * * * Remarques : - * * * ******************************************************************************/ static gint g_flow_node_get_slot_offset(const GFlowNode *node, bool entry, const node_slot_t *slot) { gint result; /* Valeur à retourner */ node_slot_t *slots; /* Accroches à parcourir */ size_t count; /* Nombre de ces points */ gint slots_width; /* Largeur des accroches */ gint slots_left; /* Abscisse de la première */ size_t index; /* Indice de l'accroche visée */ if (entry) { slots = node->entries; count = node->entries_count; } else { slots = node->exits; count = node->exits_count; } slots_width = (count - 1) * SPACE_BETWEEN_SLOT; slots_left = (G_GRAPH_NODE(node)->alloc.width - slots_width) / 2; index = (slot - slots); /* BUG_ON(index >= count); */ result = slots_left + index * SPACE_BETWEEN_SLOT; return result; } /****************************************************************************** * * * Paramètres : node = noeud graphique à consulter. * * entry = indique le type d'accrochage recherché. * * slot = accroche dont l'emplacement est à définir. * * * * Description : Localise un point d'accroche à un noeud graphique. * * * * Retour : Emplacement réservé pour l'accroche fournie. * * * * Remarques : - * * * ******************************************************************************/ GdkPoint g_flow_node_get_point_from_slot(const GFlowNode *node, bool entry, const node_slot_t *slot) { GGraphNode *base; /* Accès rapides */ GdkPoint result; /* Position à retourner */ node_slot_t *slots; /* Accroches à parcourir */ size_t count; /* Nombre de ces points */ gint slots_width; /* Largeur des accroches */ gint slots_left; /* Abscisse de la première */ size_t index; /* Indice de l'accroche visée */ base = G_GRAPH_NODE(node); if (entry) { result.y = base->alloc.y; slots = node->entries; count = node->entries_count; } else { result.y = base->alloc.y + base->alloc.height; slots = node->exits; count = node->exits_count; } slots_width = (count - 1) * SPACE_BETWEEN_SLOT; slots_left = base->alloc.x + (base->alloc.width - slots_width) / 2; index = (slot - slots)/* / sizeof(node_slot_t)*/; /* BUG_ON(index >= count); */ result.x = slots_left + index * SPACE_BETWEEN_SLOT; #if 0 slots_width = (count - 1) * SPACE_BETWEEN_SLOT; slots_left = base->alloc.x + (base->alloc.width - slots_width) / 2; index = (slot - slots)/* / sizeof(node_slot_t)*/; /* BUG_ON(index >= count); */ result.x = slots_left + index * SPACE_BETWEEN_SLOT; #endif return result; }