/* Chrysalide - Outil d'analyse de fichiers binaires * cluster.c - mise en place de graphiques * * Copyright (C) 2016-2017 Cyrille Bagard * * This file is part of Chrysalide. * * Chrysalide 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. * * Chrysalide 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 Chrysalide. If not, see . */ #include "cluster.h" #include #include #include #include #include "../gtkblockdisplay.h" #include "../gtkbufferdisplay.h" #include "../gtkdisplaypanel.h" #include "../../common/sort.h" #include "../../glibext/gloadedpanel.h" /* ------------------------- LIEN SORTANT D'UN BLOC DE CODE ------------------------- */ /* Détails sur le départ d'un lien */ typedef struct _leaving_link_t { GGraphCluster *owner; /* Propriétaire du lien */ GdkPoint start[2]; /* Point de départ d'un lien */ size_t index; /* Indice sur ligne de départ */ } leaving_link_t; /* Crée un point d'attache pour un lien sortant. */ static leaving_link_t *create_leaving_link(GGraphCluster *, size_t); /* Détruit un point d'attache pour un lien sortant. */ static void delete_leaving_link(leaving_link_t *); /* Calcule l'abscisse d'un lien à son départ d'un bloc. */ static gint compute_leaving_link_position(const leaving_link_t *); /* ------------------------- LIEN ENTRANT D'UN BLOC DE CODE ------------------------- */ /* Définition du tracé d'un lien */ typedef struct _incoming_link_t { GGraphCluster *owner; /* Propriétaire du lien */ InstructionLinkType type; /* Complexité du tracé */ const size_t *hslot; /* Couche horizontale réservée */ GdkPoint end[2]; /* Point d'arrivée final */ GGraphEdge *edge; /* Lien complet en préparation */ leaving_link_t *other; /* Autre extrémité du lien */ } incoming_link_t; /* Crée un point d'attache pour un lien entrant simple. */ static incoming_link_t *create_incoming_link(GGraphCluster *, InstructionLinkType, leaving_link_t *); /* Crée un point d'attache pour un lien entrant de boucle. */ static incoming_link_t *create_incoming_loop_link(GGraphCluster *, const GdkPoint *, leaving_link_t *); /* Détruit un point d'attache pour un lien entrant. */ static void delete_incoming_link(incoming_link_t *); /* Compare deux liens entrants. */ static int cmp_incoming_links(const incoming_link_t **, const incoming_link_t **); /* ------------------------ ENCADREMENTS D'ESPACES VERTICAUX ------------------------ */ /* Réservations d'espaces latéraux */ typedef struct _vspace_booking_t { leaving_link_t *from; /* Bloc de départ du lien */ incoming_link_t *to; /* Bloc d'arrivée du lien */ GdkPoint *pts; /* Coordonnées des points */ } vspace_booking_t; /* Réservations d'espaces latéraux */ typedef struct _vspace_manager_t { vspace_booking_t *pending; /* Besoins exprimés */ size_t pending_count; /* Nombre de ces besoins */ vspace_booking_t **left; /* Lignes disposées à gauche */ size_t left_count; /* Quantité de ces lignes */ vspace_booking_t **right; /* Lignes disposées à droite */ size_t right_count; /* Quantité de ces lignes */ } vspace_manager_t; /* Initialise les réservations liens verticaux. */ static void init_vspace_manager(vspace_manager_t *); /* Termine les réservations liens verticaux. */ static void exit_vspace_manager(vspace_manager_t *); /* Inscrit une nouvelle réservation d'espace latéral. */ static void extend_vspace_manager(vspace_manager_t *, leaving_link_t *, incoming_link_t *, GdkPoint *); /* Détermine l'emplacement requis pour les espaces latéraux. */ static void compute_vspace_manager_needed_alloc(const vspace_manager_t *, GtkAllocation *); /* Réorganise au besoin les liens de boucle entre blocs. */ static void sort_incoming_links_for_vspace_manager(vspace_manager_t *); /* Détermine les abscisses de tous les liens en place. */ static void compute_loop_link_x_with_vspace_manager(vspace_manager_t *, GGraphCluster *); /* Détermine les ordonnées de tous les liens en place. */ static void compute_loop_link_y_with_vspace_manager(vspace_manager_t *, GGraphCluster *); /* ---------------------- DESCENDANTS DIRECTS CLASSES PAR RANG ---------------------- */ /* Réservation pour les lignes horizontales */ typedef struct _hspace_booking { gint start; /* Abscisse de départ de ligne */ size_t index; /* Indice de rangée verticale */ } hspace_booking; /* Prépare une réservation d'espace pour ligne horizontale. */ static hspace_booking *create_hspace_booking(gint); /* Compare deux réservations d'espace. */ static int cmp_hspace_booking_r2l(const hspace_booking **, const hspace_booking **); /* Compare deux réservations d'espace. */ static int cmp_hspace_booking_l2r(const hspace_booking **, const hspace_booking **); /* Découpage vertical */ typedef struct _graph_rank_t { hspace_booking **right2left; /* Réservations de D -> G */ size_t r2l_count; /* Quantité de ces réservations*/ hspace_booking **left2right; /* Réservations de G -> D */ size_t l2r_count; /* Quantité de ces réservations*/ GGraphCluster **clusters; /* Ensembles de blocs */ size_t count; /* Nombre de ces ensembles */ } graph_rank_t; /* Initialise la gestion d'un ensemble de blocs de même rang. */ static void init_graph_rank(graph_rank_t *, GGraphCluster *); /* Termine la gestion d'un ensemble de blocs de même rang. */ static void exit_graph_rank(graph_rank_t *); /* Assigne à un ensemble de blocs un emplacement initial. */ static void reset_graph_rank_allocation(const graph_rank_t *); /* Fournit le rang d'un ensemble de blocs. */ static size_t get_graph_rank(const graph_rank_t *); /* Etend un ensemble de blocs de même rang. */ static void extend_graph_rank(graph_rank_t *, GGraphCluster *); /* Compare deux rangées de blocs de code. */ static int cmp_graph_rank(const graph_rank_t *, const graph_rank_t *); /* Etend un ensemble de blocs de même rang. */ static void extend_graph_rank(graph_rank_t *, GGraphCluster *); /* Détermine l'emplacement requis d'un ensemble de blocs. */ static void compute_graph_rank_needed_alloc(const graph_rank_t *, bool, GtkAllocation *); /* Affine l'abscisse d'un ensemble de blocs de même rang. */ static void _place_graph_rank_clusters(GGraphCluster **, size_t, gint, int); /* Organise la disposition d'un ensemble de blocs basiques. */ static void dispatch_x_graph_rank(const graph_rank_t *); /* Réorganise au besoin les liens entrants un ensemble de blocs. */ static void sort_graph_rank_incoming_links(const graph_rank_t *); /* Décale vers la droite un ensemble de blocs basiques. */ static void offset_x_graph_rank(const graph_rank_t *, gint); /* Décale vers le bas un ensemble de blocs basiques. */ static void set_y_for_graph_rank(const graph_rank_t *, gint *); /* -------------------------- DEFINITION D'UN CHEF DE FILE -------------------------- */ /* Mise en disposition de blocs en graphique (instance) */ struct _GGraphCluster { GObject parent; /* A laisser en premier */ GGraphCluster *owner; /* Ensemble lié parent */ size_t *parent_index; /* Indice du lien au départ */ //////////////////////////////////////// gint top_margin[2]; /* Espaces gauches et droites */ gint left_margin; /* Espaces remontant à gauche */ gint right_margin; /* Espaces remontant à droite */ //////////////////////////////////////// incoming_link_t **top_anchors; /* Accroches supérieures */ size_t ta_count; /* Quantité de ces accroches */ GCodeBlock *block; /* Bloc d'origine représenté */ GtkWidget *display; /* Vue graphique associée */ GtkAllocation alloc; /* Emplacement final du bloc */ leaving_link_t **bottom_anchors; /* Accroches inférieures */ size_t ba_count; /* Quantité de ces accroches */ bool has_straight; /* Présence d'une ligne droite */ size_t straight_level; /* Rang atteint en ligne droite*/ size_t straight_index; /* Indice du lien vertical */ graph_rank_t *ranks; /* Répartition verticale */ size_t ranks_count; /* Nombre de divisions */ vspace_manager_t vspaces; /* Gestion des liens latéraux */ }; /* 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 15 /* 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 *); /* Assigne à un bloc et son ensemble un emplacement initial. */ static void g_graph_cluster_reset_allocation(GGraphCluster *); /* Complète un graphique avec un sous-ensemble de blocs. */ static void g_graph_cluster_add_sub(GGraphCluster *, GGraphCluster *); /* Etablit les connexions entre blocs selon les rangs. */ static void g_graph_cluster_setup_link_for_target(GGraphCluster *, GGraphCluster *, leaving_link_t *); /* Met en place les embryons de liens nécessaires. */ static void g_graph_cluster_define_links(GGraphCluster *, GHashTable *); /* Organise la disposition d'un ensemble de blocs basiques. */ static void g_graph_cluster_dispatch_x(GGraphCluster *); /* Réorganise au besoin les liens entrants d'un bloc. */ static void g_graph_cluster_sort_incoming_links(GGraphCluster *); /* Retrouve l'indice d'un lien entrant donné pour un bloc. */ static size_t g_graph_cluster_find_incoming_link(const GGraphCluster *, const leaving_link_t *); /* Décale vers la droite un ensemble de blocs basiques. */ static void g_graph_cluster_offset_x(GGraphCluster *, gint); /* Décale vers le bas un ensemble de blocs basiques. */ static void g_graph_cluster_set_y(GGraphCluster *, gint); /* Calcule l'abscisse d'un lien pour un bloc. */ static gint _g_graph_cluster_compute_link_position(const GGraphCluster *, size_t, size_t, bool); /* Calcule l'abscisse d'un lien à son départ d'un bloc. */ static gint g_graph_cluster_compute_leaving_link_position(const GGraphCluster *, size_t); /* Calcule l'abscisse d'un lien à son arrivée à un bloc. */ static gint g_graph_cluster_compute_incoming_link_position(const GGraphCluster *, size_t); /* Détermine les abscisses des liens de boucle en place. */ static void g_graph_cluster_compute_loop_link_x_positions(GGraphCluster *); /* Détermine les abscisses de tous les liens en place. */ static void g_graph_cluster_compute_link_x_positions(GGraphCluster *); /* Réserve de l'espace vertical pour les lignes horizontales. */ static void g_graph_cluster_book_hspace_for_links(GGraphCluster *); /* Détermine les ordonnées de tous les liens en place. */ static void g_graph_cluster_compute_link_y_positions(GGraphCluster *); /* Applique les positions calculées pour chaque lien graphique. */ static void g_graph_cluster_resolve_links(const GGraphCluster *); /* ------------------------- CALCUL DE REPARTITION DE BLOCS ------------------------- */ /* Liste de blocs restants à traiter */ typedef struct _pending_blocks { size_t count; /* Taille de la liste */ GCodeBlock *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 *); /* ---------------------------------------------------------------------------------- */ /* LIEN SORTANT D'UN BLOC DE CODE */ /* ---------------------------------------------------------------------------------- */ /****************************************************************************** * * * Paramètres : owner = propriétaire du bloc de rattachement. * * index = indice dans les liens de sortie. * * * * Description : Crée un point d'attache pour un lien sortant. * * * * Retour : Structure mise en place. * * * * Remarques : - * * * ******************************************************************************/ static leaving_link_t *create_leaving_link(GGraphCluster *owner, size_t index) { leaving_link_t *result; /* Structure à retourner */ result = malloc(sizeof(leaving_link_t)); result->owner = owner; result->index = index; return result; } /****************************************************************************** * * * Paramètres : link = structure à libérer de la mémoire. * * * * Description : Détruit un point d'attache pour un lien sortant. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void delete_leaving_link(leaving_link_t *link) { free(link); } /****************************************************************************** * * * Paramètres : link = information sur un lien à consulter. * * * * Description : Calcule l'abscisse d'un lien à son départ d'un bloc. * * * * Retour : Abscisse à attribuer à un départ de lien. * * * * Remarques : - * * * ******************************************************************************/ static gint compute_leaving_link_position(const leaving_link_t *link) { gint result; /* Position à retourner */ result = g_graph_cluster_compute_leaving_link_position(link->owner, link->index); return result; } /* ---------------------------------------------------------------------------------- */ /* LIEN ENTRANT D'UN BLOC DE CODE */ /* ---------------------------------------------------------------------------------- */ /****************************************************************************** * * * Paramètres : owner = propriétaire du bloc de rattachement. * * type = type de lien simple attendu. * * other = point de départ du lien formé. * * * * Description : Crée un point d'attache pour un lien entrant simple. * * * * Retour : Structure mise en place. * * * * Remarques : - * * * ******************************************************************************/ static incoming_link_t *create_incoming_link(GGraphCluster *owner, InstructionLinkType type, leaving_link_t *other) { incoming_link_t *result; /* Structure à retourner */ GCodeBlock *src; /* Bloc d'origine du lien */ GCodeBlock *dst; /* Bloc de destination du lien */ result = malloc(sizeof(incoming_link_t)); result->owner = owner; result->type = type; src = other->owner->block; dst = owner->block; if (type == ILT_JUMP_IF_TRUE) result->edge = g_graph_edge_new_true(src, dst, &other->start[0], &other->start[1], &result->end[0], &result->end[1]); else if (type == ILT_JUMP_IF_FALSE) result->edge = g_graph_edge_new_false(src, dst, &other->start[0], &other->start[1], &result->end[0], &result->end[1]); else result->edge = g_graph_edge_new(src, dst, &other->start[0], &other->start[1], &result->end[0], &result->end[1]); result->other = other; return result; } /****************************************************************************** * * * Paramètres : owner = propriétaire du bloc de rattachement. * * other = point de départ du lien formé. * * * * Description : Crée un point d'attache pour un lien entrant de boucle. * * * * Retour : Structure mise en place. * * * * Remarques : - * * * ******************************************************************************/ static incoming_link_t *create_incoming_loop_link(GGraphCluster *owner, const GdkPoint *midpts, leaving_link_t *other) { incoming_link_t *result; /* Structure à retourner */ GCodeBlock *src; /* Bloc d'origine du lien */ GCodeBlock *dst; /* Bloc de destination du lien */ result = malloc(sizeof(incoming_link_t)); result->owner = owner; result->type = ILT_LOOP; src = other->owner->block; dst = owner->block; result->edge = g_graph_edge_new_loop(src, dst, &other->start[0], &other->start[1], &midpts[0], &midpts[1], &result->end[0], &result->end[1]); result->other = other; return result; } /****************************************************************************** * * * Paramètres : link = structure à libérer de la mémoire. * * * * Description : Détruit un point d'attache pour un lien entrant. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void delete_incoming_link(incoming_link_t *link) { free(link); } /****************************************************************************** * * * Paramètres : a = premier lien entrant à comparer. * * b = second lien entrant à comparer. * * * * Description : Compare deux liens entrants. * * * * Retour : Bilan de comparaison. * * * * Remarques : - * * * ******************************************************************************/ static int cmp_incoming_links(const incoming_link_t **a, const incoming_link_t **b) { int result; /* Bilan à retourner */ gint pos_a; /* Point de départ pour A */ gint pos_b; /* Point de départ pour B */ pos_a = compute_leaving_link_position((*a)->other); pos_b = compute_leaving_link_position((*b)->other); if (pos_a < pos_b) result = -1; else if (pos_a > pos_b) result = 1; else result = 0; return result; } /* ---------------------------------------------------------------------------------- */ /* ENCADREMENTS D'ESPACES VERTICAUX */ /* ---------------------------------------------------------------------------------- */ /****************************************************************************** * * * Paramètres : manager = structure à initialiser. * * * * Description : Initialise les réservations liens verticaux. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void init_vspace_manager(vspace_manager_t *manager) { manager->pending = NULL; manager->pending_count = 0; manager->left = NULL; manager->left_count = 0; manager->right = NULL; manager->right_count = 0; } /****************************************************************************** * * * Paramètres : manager = structure à vider. * * * * Description : Termine les réservations liens verticaux. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void exit_vspace_manager(vspace_manager_t *manager) { size_t i; /* Boucle de parcours */ for (i = 0; i < manager->pending_count; i++) free(manager->pending[i].pts); if (manager->pending != NULL) free(manager->pending); if (manager->left != NULL) free(manager->left); if (manager->right != NULL) free(manager->right); } /****************************************************************************** * * * Paramètres : manager = structure à compléter. * * from = point de départ du lien concerné. * * to = point d'arrivée du lien concerné. * * pts = points intermédiaires du tracé complet final. * * * * Description : Inscrit une nouvelle réservation d'espace latéral. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void extend_vspace_manager(vspace_manager_t *manager, leaving_link_t *from, incoming_link_t *to, GdkPoint *pts) { vspace_booking_t *new; /* Réservation à constituer */ manager->pending = realloc(manager->pending, ++manager->pending_count * sizeof(vspace_booking_t)); new = &manager->pending[manager->pending_count - 1]; new->from = from; new->to = to; new->pts = pts; } /****************************************************************************** * * * Paramètres : manager = gestion des espaces latéraux à consulter. * * alloc = emplacement idéal pour l'affichage. [OUT] * * * * Description : Détermine l'emplacement requis pour les espaces latéraux. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void compute_vspace_manager_needed_alloc(const vspace_manager_t *manager, GtkAllocation *alloc) { gint width; /* Largeur supplémentaire */ /* Extension de la largeur */ width = 0; width += manager->left_count * LINK_MARGIN; width += manager->right_count * LINK_MARGIN; alloc->x -= width / 2; alloc->width += width; /* Extension de la hauteur */ alloc->height += manager->pending_count * VERTICAL_MARGIN; } /****************************************************************************** * * * Paramètres : manager = gestion d'espaces latéraux à manipuler. * * * * Description : Réorganise au besoin les liens de boucle entre blocs. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void sort_incoming_links_for_vspace_manager(vspace_manager_t *manager) { size_t i; /* Boucle de parcours */ vspace_booking_t *pending; /* Elément traité */ gint x1; /* Abscisse de départ de lien */ size_t idx; /* Indice du lien entrant */ gint x2; /* Abscisse d'arrivée de lien */ for (i = 0; i < manager->pending_count; i++) { pending = &manager->pending[i]; x1 = g_graph_cluster_compute_leaving_link_position(pending->from->owner, pending->from->index); idx = g_graph_cluster_find_incoming_link(pending->to->owner, pending->from); x2 = g_graph_cluster_compute_incoming_link_position(pending->to->owner, idx); if (x1 < x2) { manager->left = realloc(manager->left, ++manager->left_count * sizeof(vspace_booking_t *)); manager->left[manager->left_count - 1] = pending; } else { manager->right = realloc(manager->right, ++manager->right_count * sizeof(vspace_booking_t *)); manager->right[manager->right_count - 1] = pending; } } } /****************************************************************************** * * * Paramètres : manager = structure à consulter. * * cluster = graphique de blocs sur lequel s'appuyer. * * * * Description : Détermine les abscisses de tous les liens en place. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void compute_loop_link_x_with_vspace_manager(vspace_manager_t *manager, GGraphCluster *cluster) { GtkAllocation needed; /* Espace nécessaire et alloué */ size_t i; /* Boucle de parcours */ vspace_booking_t *booking; /* Réservation à traiter */ gint x; /* Position à appliquer */ GGraphCluster *container; /* Parent direct à décaler */ g_graph_cluster_compute_needed_alloc(cluster, &needed); for (i = 0; i < manager->left_count; i++) { booking = manager->left[i]; x = i * LINK_MARGIN; booking->pts[0].x = needed.x + x; booking->pts[1].x = needed.x + x; } if (manager->left_count > 0) { x = manager->left_count * LINK_MARGIN; /** * Si la routine est une boucle sans fin, * alors la boucle peut renvoyer vers le premier bloc. */ if (cluster->owner != NULL) { container = cluster->owner; /** * On recherche le plus haut propritétaire bénéficiant d'une chaîne * de liens directs et droits, histoire de transmettre le décalage * et de garder ces liens bien verticaux. */ while (container->owner != NULL) { if (!container->owner->has_straight) break; if (container->owner->straight_index != *container->parent_index) break; container = container->owner; } g_graph_cluster_offset_x(container, x); } } for (i = 0; i < manager->right_count; i++) { booking = manager->right[i]; x = (i + 1) * LINK_MARGIN; booking->pts[0].x = x; booking->pts[1].x = x; } } /****************************************************************************** * * * Paramètres : manager = structure à consulter. * * cluster = graphique de blocs sur lequel s'appuyer. * * * * Description : Détermine les ordonnées de tous les liens en place. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void compute_loop_link_y_with_vspace_manager(vspace_manager_t *manager, GGraphCluster *cluster) { GtkAllocation needed; /* Espace nécessaire et alloué */ size_t i; /* Boucle de parcours */ vspace_booking_t *booking; /* Réservation à traiter */ g_graph_cluster_compute_needed_alloc(cluster, &needed); for (i = 0; i < manager->pending_count; i++) { booking = &manager->pending[i]; /** * On corrige le raccourci pris sans distinction de type de lien dans * la fonction g_graph_cluster_compute_link_y_positions(). */ booking->from->start[1].y = needed.y + needed.height; /* Définition de l'ordonnée des points du lien */ booking->pts[0].y = booking->from->start[1].y; booking->pts[1].y = booking->to->end[0].y; } } /* ---------------------------------------------------------------------------------- */ /* DESCENDANTS DIRECTS CLASSES PAR RANG */ /* ---------------------------------------------------------------------------------- */ /****************************************************************************** * * * Paramètres : start = abscisse de départ de ligne. * * * * Description : Prépare une réservation d'espace pour ligne horizontale. * * * * Retour : Structure mise en place pour la conservation d'informations. * * * * Remarques : - * * * ******************************************************************************/ static hspace_booking *create_hspace_booking(gint start) { hspace_booking *result; /* Structure à retourner */ result = malloc(sizeof(hspace_booking)); result->start = start; return result; } /****************************************************************************** * * * Paramètres : a = première réservation d'espace à comparer. * * b = seconde réservation d'espace à comparer. * * * * Description : Compare deux réservations d'espace. * * * * Retour : Bilan de comparaison. * * * * Remarques : - * * * ******************************************************************************/ static int cmp_hspace_booking_r2l(const hspace_booking **a, const hspace_booking **b) { int result; /* Bilan à retourner */ if ((*a)->start > (*b)->start) result = -1; else if ((*a)->start < (*b)->start) result = 1; else { assert(false); result = 0; } return result; } /****************************************************************************** * * * Paramètres : a = première réservation d'espace à comparer. * * b = seconde réservation d'espace à comparer. * * * * Description : Compare deux réservations d'espace. * * * * Retour : Bilan de comparaison. * * * * Remarques : - * * * ******************************************************************************/ static int cmp_hspace_booking_l2r(const hspace_booking **a, const hspace_booking **b) { int result; /* Bilan à retourner */ if ((*a)->start < (*b)->start) result = -1; else if ((*a)->start > (*b)->start) result = 1; else { assert(false); result = 0; } return result; } /****************************************************************************** * * * Paramètres : grank = structure à initialiser. [OUT] * * cluster = chef de file d'un ensemble de blocs. * * * * Description : Initialise la gestion d'un ensemble de blocs de même rang. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void init_graph_rank(graph_rank_t *grank, GGraphCluster *cluster) { grank->right2left = NULL; grank->r2l_count = 0; grank->left2right = NULL; grank->l2r_count = 0; grank->clusters = malloc(sizeof(GGraphCluster *)); grank->count = 1; grank->clusters[0] = cluster; } /****************************************************************************** * * * Paramètres : grank = structure à vider. * * * * Description : Termine la gestion d'un ensemble de blocs de même rang. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void exit_graph_rank(graph_rank_t *grank) { size_t i; /* Boucle de parcours */ for (i = 0; i < grank->r2l_count; i++) free(grank->right2left[i]); if (grank->right2left != NULL) free(grank->right2left); for (i = 0; i < grank->l2r_count; i++) free(grank->left2right[i]); if (grank->left2right != NULL) free(grank->left2right); assert(grank->clusters != NULL); free(grank->clusters); } /****************************************************************************** * * * Paramètres : grank = ensemble de même rang à consulter. * * * * Description : Assigne à un ensemble de blocs un emplacement initial. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void reset_graph_rank_allocation(const graph_rank_t *grank) { size_t i; /* Boucle de parcours */ for (i = 0; i < grank->count; i++) g_graph_cluster_reset_allocation(grank->clusters[i]); } /****************************************************************************** * * * Paramètres : grank = ensemble de même rang à consulter. * * * * Description : Fournit le rang d'un ensemble de blocs. * * * * Retour : Rang d'un ensemble de blocs de même rang. * * * * Remarques : - * * * ******************************************************************************/ static size_t get_graph_rank(const graph_rank_t *grank) { size_t result; /* Rang à retourner */ result = g_code_block_get_rank(grank->clusters[0]->block); return result; } /****************************************************************************** * * * Paramètres : a = premier ensemble de même rang à comparer. * * b = second ensemble de même rang à comparer. * * * * Description : Compare deux rangées de blocs de code. * * * * Retour : Bilan de comparaison. * * * * Remarques : - * * * ******************************************************************************/ static int cmp_graph_rank(const graph_rank_t *a, const graph_rank_t *b) { int result; /* Bilan à retourner */ size_t level_a; /* Niveau de l'ensemble A */ size_t level_b; /* Niveau de l'ensemble B */ level_a = get_graph_rank(a); level_b = get_graph_rank(b); if (level_a < level_b) result = -1; else if (level_a > level_b) result = 1; else result = 0; return result; } /****************************************************************************** * * * Paramètres : grank = structure à compléter. * * cluster = chef de file d'un ensemble de blocs. * * * * Description : Etend un ensemble de blocs de même rang. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void extend_graph_rank(graph_rank_t *grank, GGraphCluster *cluster) { grank->count++; grank->clusters = realloc(grank->clusters, sizeof(GGraphCluster *) * grank->count); grank->clusters[grank->count - 1] = cluster; } /****************************************************************************** * * * Paramètres : grank = ensemble de descendants d'un même rang. * * last = indique s'il s'agit du dernier étage de l'ensemble. * * alloc = emplacement idéal pour l'affichage. [OUT] * * * * Description : Détermine l'emplacement requis d'un ensemble de blocs. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void compute_graph_rank_needed_alloc(const graph_rank_t *grank, bool last, GtkAllocation *alloc) { GtkAllocation needed; /* Taille requise */ switch (grank->count) { case 1: g_graph_cluster_compute_needed_alloc(grank->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 (last) { if ((needed.y + needed.height) > (alloc->y + alloc->height)) alloc->height += needed.y + needed.height - alloc->y - alloc->height; } break; default: assert(grank->count >= 2); g_graph_cluster_compute_needed_alloc(grank->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 (last) { 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(grank->clusters[grank->count - 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 (last) { if ((needed.y + needed.height) > (alloc->y + alloc->height)) alloc->height += needed.y + needed.height - alloc->y - alloc->height; } break; } } /****************************************************************************** * * * Paramètres : iter = début de la boucle de parcours. * * loop = nombre d'itérations à mener. * * base = position de base sur l'axe des abscisses. * * dir = direction du parcours. * * * * Description : Affine l'abscisse d'un ensemble de blocs de même rang. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void _place_graph_rank_clusters(GGraphCluster **iter, size_t loop, gint base, int dir) { size_t i; /* Boucle de parcours */ 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); } } /****************************************************************************** * * * Paramètres : grank = ensemble de blocs de même rang à manipuler. * * * * Description : Organise la disposition d'un ensemble de blocs basiques. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void dispatch_x_graph_rank(const graph_rank_t *grank) { size_t mid; /* Position centrale de départ */ gint start; /* Position initiale de départ */ if (grank->count % 2 == 1) { if (grank->count > 1) { mid = grank->count / 2; start = grank->clusters[mid]->alloc.x - HORIZONTAL_MARGIN; _place_graph_rank_clusters(grank->clusters + mid - 1, mid, start, -1); start *= -1; _place_graph_rank_clusters(grank->clusters + mid + 1, mid, start, 1); } else g_graph_cluster_dispatch_x(grank->clusters[0]); } else { mid = grank->count / 2 - 1; start = - HORIZONTAL_MARGIN / 2; _place_graph_rank_clusters(grank->clusters + mid, mid + 1, start, -1); start *= -1; _place_graph_rank_clusters(grank->clusters + mid + 1, mid + 1, start, 1); } } /****************************************************************************** * * * Paramètres : grank = ensemble de blocs de même rang à actualiser. * * * * Description : Réorganise au besoin les liens entrants un ensemble de blocs.* * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void sort_graph_rank_incoming_links(const graph_rank_t *grank) { size_t i; /* Boucle de parcours */ for (i = 0; i < grank->count; i++) g_graph_cluster_sort_incoming_links(grank->clusters[i]); } /****************************************************************************** * * * Paramètres : grank = ensemble de blocs de même rang à actualiser. * * offset = décalage à appliquer. * * * * Description : Décale vers la droite un ensemble de blocs basiques. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void offset_x_graph_rank(const graph_rank_t *grank, gint offset) { size_t i; /* Boucle de parcours */ for (i = 0; i < grank->count; i++) g_graph_cluster_offset_x(grank->clusters[i], offset); } /****************************************************************************** * * * Paramètres : grank = ensemble de blocs de même rang à actualiser. * * base = position ordonnée à appliquer. * * * * Description : Décale vers le bas un ensemble de blocs basiques. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void set_y_for_graph_rank(const graph_rank_t *grank, gint *base) { gint max; /* Hauteur maximale rencontrée */ size_t i; /* Boucle de parcours */ GGraphCluster *sub; /* Sous-ensemble traité */ GtkAllocation alloc; /* Allocation courante */ /* On ajoute l'espace vertical pour les lignes horizontales */ if (grank->r2l_count > grank->l2r_count) max = grank->r2l_count; else max = grank->l2r_count; *base += VERTICAL_MARGIN; /** * Comme les liens purement verticaux n'entrainent pas de réservation, * il n'y a potentiellement pas toujours d'espace à ajouter. */ if (max > 0) { *base += ((max - 1) * LINK_MARGIN); *base += VERTICAL_MARGIN; } /* On ajoute l'espace requis pour l'affichage des blocs */ max = 0; for (i = 0; i < grank->count; i++) { sub = grank->clusters[i]; 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; } /* ---------------------------------------------------------------------------------- */ /* DEFINITION D'UN CHEF DE FILE */ /* ---------------------------------------------------------------------------------- */ /* Indique le type défini 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) { init_vspace_manager(&cluster->vspaces); } /****************************************************************************** * * * 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_clear_object(&cluster->block); g_clear_object(&cluster->display); 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) { size_t i; /* Boucle de parcours */ for (i = 0; i < cluster->ta_count; i++) delete_incoming_link(cluster->top_anchors[i]); if (cluster->top_anchors != NULL) free(cluster->top_anchors); for (i = 0; i < cluster->ba_count; i++) delete_leaving_link(cluster->bottom_anchors[i]); if (cluster->bottom_anchors != NULL) free(cluster->bottom_anchors); for (i = 0; i < cluster->ranks_count; i++) exit_graph_rank(&cluster->ranks[i]); if (cluster->ranks != NULL) free(cluster->ranks); exit_vspace_manager(&cluster->vspaces); G_OBJECT_CLASS(g_graph_cluster_parent_class)->finalize(G_OBJECT(cluster)); } /****************************************************************************** * * * Paramètres : block = premier bloc du groupe. * * highlighted = gestionnaire de surbrillance pour segments. * * binary = binaire charger dont le code est à représenter.* * * * Description : * * * * Retour : Adresse de la structure mise en place. * * * * Remarques : - * * * ******************************************************************************/ GGraphCluster *g_graph_cluster_new(GCodeBlock *block, segcnt_list *highlighted, GLoadedBinary *binary) { GGraphCluster *result; /* Structure à retourner */ GBufferView *view; /* Partie affichée du tampon */ result = g_object_new(G_TYPE_GRAPH_CLUSTER, NULL); /* Encapsulation du bloc d'entrée */ result->block = block; g_object_ref(G_OBJECT(block)); view = g_code_block_get_view(result->block, highlighted); result->display = gtk_block_display_new(view); gtk_widget_show(result->display); g_loaded_panel_set_content(G_LOADED_PANEL(result->display), G_LOADED_CONTENT(binary)); gtk_block_display_override_view_index(GTK_BLOCK_DISPLAY(result->display), BVW_GRAPH); gtk_display_panel_show_border(GTK_DISPLAY_PANEL(result->display), true); g_graph_cluster_reset_allocation(result); return result; } /****************************************************************************** * * * Paramètres : cluster = graphique de blocs à compléter. * * * * Description : Assigne à un bloc et son ensemble un emplacement initial. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_graph_cluster_reset_allocation(GGraphCluster *cluster) { GtkRequisition requisition; /* Taille à l'écran actuelle */ size_t i; /* Boucle de parcours */ /* Détermination d'une position initiale centrée */ gtk_widget_get_preferred_size(cluster->display, NULL, &requisition); cluster->alloc.x = -requisition.width / 2; cluster->alloc.y = 0; cluster->alloc.width = requisition.width; cluster->alloc.height = requisition.height; /* Propagation aux sous-blocs */ for (i = 0; i < cluster->ranks_count; i++) reset_graph_rank_allocation(&cluster->ranks[i]); } /****************************************************************************** * * * Paramètres : cluster = graphique de blocs à compléter. * * sub = sous-ensemble à intégrer. * * * * Description : Complète un graphique avec un sous-ensemble de blocs. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub) { size_t level; /* Niveau du nouvel ensemble */ size_t i; /* Boucle de parcours */ graph_rank_t new; /* Nouvel étage à insérer */ level = g_code_block_get_rank(sub->block); for (i = 0; i < cluster->ranks_count; i++) if (get_graph_rank(&cluster->ranks[i]) == level) break; if (i == cluster->ranks_count) { init_graph_rank(&new, sub); cluster->ranks = qinsert(cluster->ranks, &cluster->ranks_count, sizeof(graph_rank_t), (__compar_fn_t)cmp_graph_rank, &new); } else extend_graph_rank(&cluster->ranks[i], sub); sub->owner = cluster; } /****************************************************************************** * * * Paramètres : grank = ensemble de descendants d'un même rang. * * source = bloc courant ou NULL pour limiter les calculs. * * target = bloc ciblé pour l'arrivée d'un lien. * * leaving = représentation d'un lien sortant. * * * * Description : Etablit les connexions entre blocs selon les rangs. * * * * Retour : true si la cible a été rencontrée. * * * * Remarques : - * * * ******************************************************************************/ static void g_graph_cluster_setup_link_for_target(GGraphCluster *source, GGraphCluster *target, leaving_link_t *leaving) { size_t level; /* Niveau du nouvel ensemble */ size_t target_level; /* Rang du bloc ciblé */ target->parent_index = &leaving->index; if (source != NULL) { level = g_code_block_get_rank(source->block); target_level = g_code_block_get_rank(target->block); /* Est-ce un lien qui doit être vertical ? */ if (target_level > (level + 1) && target_level > source->straight_level) { source->has_straight = true; source->straight_level = target_level; source->straight_index = source->ba_count - 1; } } } /****************************************************************************** * * * 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) { size_t dcount; /* Nombre de liens de dest. */ block_link_t *links; /* Liens associés au bloc */ size_t i; /* Boucle de parcours #1 */ block_link_t *dest; /* Bloc visé par un autre */ GGraphCluster *target; /* Bloc ciblé par un lien */ leaving_link_t *leaving; /* Point de départ d'un lien */ incoming_link_t *incoming; /* Définitions d'arrivée */ GdkPoint *midpts; /* Points intermédiaires */ size_t j; /* Boucle de parcours #2 */ /* Au niveau du bloc courant */ links = g_code_block_get_destinations(cluster->block, &dcount); for (i = 0; i < dcount; i++) { dest = &links[i]; switch (dest->type) { 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, dest->linked)); assert(target != NULL); /* Point de départ */ leaving = create_leaving_link(cluster, cluster->ba_count); cluster->bottom_anchors = realloc(cluster->bottom_anchors, ++cluster->ba_count * sizeof(leaving_link_t *)); cluster->bottom_anchors[cluster->ba_count - 1] = leaving; /* Point d'arrivée */ incoming = create_incoming_link(target, dest->type, leaving); target->top_anchors = realloc(target->top_anchors, ++target->ta_count * sizeof(incoming_link_t *)); target->top_anchors[target->ta_count - 1] = incoming; /* Etablissement d'un embryon de lien */ g_graph_cluster_setup_link_for_target(cluster, target, leaving); break; case ILT_LOOP: target = G_GRAPH_CLUSTER(g_hash_table_lookup(all, dest->linked)); assert(target != NULL); /* Point de départ */ leaving = create_leaving_link(cluster, cluster->ba_count); cluster->bottom_anchors = realloc(cluster->bottom_anchors, ++cluster->ba_count * sizeof(leaving_link_t *)); cluster->bottom_anchors[cluster->ba_count - 1] = leaving; /* Point d'arrivée */ midpts = malloc(2 * sizeof(GdkPoint)); incoming = create_incoming_loop_link(target, midpts, leaving); target->top_anchors = realloc(target->top_anchors, ++target->ta_count * sizeof(incoming_link_t *)); target->top_anchors[target->ta_count - 1] = incoming; /* Réservation d'un espace latéral */ extend_vspace_manager(&target->vspaces, leaving, incoming, midpts); /* Etablissement d'un embryon de lien */ g_graph_cluster_setup_link_for_target(NULL, target, leaving); break; default: break; } unref_block_link(dest); } if (links != NULL) free(links); /* Doit-on forcer un lien strictement vertical ? */ if (cluster->ba_count == 1 && !cluster->has_straight) { /** * Attention : les boucles aussi ont un seul lien sortant ! * * S'il n'y a qu'un seul lien, on peut s'appuyer sur la variable 'incoming' * manipulée dans la boucle : c'est forcément elle qui a été mise en place. * * Même chose pour 'target'. */ if (incoming->type != ILT_LOOP) { cluster->has_straight = true; cluster->straight_level = g_code_block_get_rank(target->block); cluster->straight_index = 0; } } /* Déplacement d'un éventuel lien central en position centrale */ if (cluster->has_straight) { size_t center; leaving_link_t *tmp; if (cluster->ba_count % 2 == 0) center = cluster->ba_count / 2 - 1; else center = cluster->ba_count / 2; if (cluster->straight_index < center) { tmp = cluster->bottom_anchors[cluster->straight_index]; memmove(cluster->bottom_anchors + cluster->straight_index, cluster->bottom_anchors + cluster->straight_index + 1, (center - cluster->straight_index) * sizeof(leaving_link_t *)); cluster->bottom_anchors[center] = tmp; for (i = cluster->straight_index; i <= center; i++) cluster->bottom_anchors[i]->index = i; cluster->straight_index = center; } else if (cluster->straight_index > center) { tmp = cluster->bottom_anchors[cluster->straight_index]; memmove(cluster->bottom_anchors + center + 1, cluster->bottom_anchors + center, (cluster->straight_index - center) * sizeof(leaving_link_t *)); cluster->bottom_anchors[center] = tmp; for (i = center; i <= cluster->straight_index ; i++) cluster->bottom_anchors[i]->index = i; cluster->straight_index = center; } } /* 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 à manipuler. * * * * Description : Organise 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 */ const graph_rank_t *rank; /* Accès confortable au rang */ size_t j; /* Boucle de parcours #2 */ gint start; /* Position initiale de départ */ GGraphCluster *target; /* Unique sous-bloc visé */ size_t idx; /* Indice du lien entrant */ gint end; /* Position initiale d'arrivée */ /** * Il est désormais temps de placer tous les blocs de code inférieurs. */ for (k = 0; k < cluster->ranks_count; k++) { rank = &cluster->ranks[k]; /* Répartition autour d'une ligne verticale */ if (cluster->has_straight) { start = g_graph_cluster_compute_leaving_link_position(cluster, cluster->straight_index); if (get_graph_rank(rank) < cluster->straight_level) { /* Répartition à gauche du lien */ for (j = rank->count; j > 0; j--) if (*rank->clusters[j - 1]->parent_index < cluster->straight_index) break; start -= HORIZONTAL_MARGIN / 2; _place_graph_rank_clusters(rank->clusters, j, start, -1); /* Répartition à droite du lien */ for (j = 0; j < rank->count; j++) if (*rank->clusters[j]->parent_index > cluster->straight_index) break; start += HORIZONTAL_MARGIN; _place_graph_rank_clusters(rank->clusters + j, rank->count - j, start, 1); } else if (get_graph_rank(rank) == cluster->straight_level) { /** * Si le bloc pointé en direct a plus d'un lien en entrée (comme * dans le cas d'un bloc qui assure un début de boucle par exemple), * le lien direct n'est pas centré sur le milieu de ce bloc pointé. * * On corrige ici le léger décalage. */ assert(rank->count == 1); target = rank->clusters[0]; idx = g_graph_cluster_find_incoming_link(target, cluster->bottom_anchors[cluster->straight_index]); end = g_graph_cluster_compute_incoming_link_position(target, idx); g_graph_cluster_offset_x(target, start - end); dispatch_x_graph_rank(rank); } else dispatch_x_graph_rank(rank); } /* Répartition homogène */ else dispatch_x_graph_rank(rank); } } /****************************************************************************** * * * Paramètres : cluster = graphique de blocs à manipuler. * * * * Description : Réorganise au besoin les liens entrants d'un bloc. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_graph_cluster_sort_incoming_links(GGraphCluster *cluster) { size_t i; /* Boucle de parcours */ qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_link_t *), (__compar_fn_t)cmp_incoming_links); for (i = 0; i < cluster->ranks_count; i++) sort_graph_rank_incoming_links(&cluster->ranks[i]); sort_incoming_links_for_vspace_manager(&cluster->vspaces); } /****************************************************************************** * * * Paramètres : cluster = graphique de blocs à consulter. * * incoming = adresse de l'autre bout du lien concerné. * * * * Description : Retrouve l'indice d'un lien entrant donné pour un bloc. * * * * Retour : Indice à priori toujours valide. * * * * Remarques : - * * * ******************************************************************************/ static size_t g_graph_cluster_find_incoming_link(const GGraphCluster *cluster, const leaving_link_t *leaving) { size_t result; /* Indice à retourner */ for (result = 0; result < cluster->ta_count; result++) if (cluster->top_anchors[result]->other == leaving) break; assert(cluster->ta_count); return result; } /****************************************************************************** * * * Paramètres : cluster = graphique de blocs à actualiser. * * offset = décalage à appliquer. * * * * Description : Décale 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 */ cluster->alloc.x += offset; for (i = 0; i < cluster->ranks_count; i++) offset_x_graph_rank(&cluster->ranks[i], offset); } /****************************************************************************** * * * Paramètres : cluster = graphique de blocs à actualiser. * * base = position ordonnée à appliquer. * * * * Description : Décale 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 */ cluster->alloc.y = base; base += cluster->alloc.height; for (i = 0; i < cluster->ranks_count; i++) set_y_for_graph_rank(&cluster->ranks[i], &base); } /****************************************************************************** * * * 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) { size_t i; /* Boucle de parcours */ *alloc = cluster->alloc; for (i = 0; i < cluster->ranks_count; i++) compute_graph_rank_needed_alloc(&cluster->ranks[i], (i + 1) == cluster->ranks_count, alloc); compute_vspace_manager_needed_alloc(&cluster->vspaces, alloc); } /****************************************************************************** * * * Paramètres : cluster = encapsulation à consulter. * * * * Description : Fournit le composant graphique principal du groupe. * * * * Retour : Composant graphique principal utilisé. * * * * Remarques : - * * * ******************************************************************************/ GtkWidget *g_graph_cluster_get_widget(GGraphCluster *cluster) { GtkWidget *result; result = cluster->display; g_object_ref(G_OBJECT(result)); return result; } /****************************************************************************** * * * Paramètres : cluster = encapsulation à traiter. * * display = support de destination finale. * * * * Description : Dispose chaque noeud sur la surface de destination donnée. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ void g_graph_cluster_place(GGraphCluster *cluster, GtkGraphDisplay *display) { size_t i; /* Boucle de parcours #1 */ size_t j; /* Boucle de parcours #2 */ g_object_ref(G_OBJECT(cluster->display)); gtk_graph_display_put(display, cluster->display, &cluster->alloc); for (i = 0; i < cluster->ta_count; i++) { g_object_ref(G_OBJECT(cluster->top_anchors[i]->edge)); gtk_graph_display_add_edge(display, 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], display); } /****************************************************************************** * * * Paramètres : cluster = graphique de blocs à consulter. * * index = indice du lien à considérer. * * half = moitié du nombre de liens en présence. * * odd = le nombre de liens considérés est-il impair ? * * * * Description : Calcule l'abscisse d'un lien pour un bloc. * * * * Retour : Abscisse à attribuer au lien. * * * * Remarques : - * * * ******************************************************************************/ static gint _g_graph_cluster_compute_link_position(const GGraphCluster *cluster, size_t index, size_t half, bool odd) { gint result; /* Position à retourner */ gint mid_x; /* Abscisse centrale */ mid_x = cluster->alloc.x + (cluster->alloc.width / 2); if (odd) { if (index < half) result = mid_x - (half - index) * LINK_MARGIN; else if (index == half) result = mid_x; else result = mid_x + (index - half) * LINK_MARGIN; } else { if (index < half) result = mid_x - LINK_MARGIN / 2 - (half - index - 1) * LINK_MARGIN; else result = mid_x + LINK_MARGIN / 2 + (index - half) * LINK_MARGIN; } return result; } /****************************************************************************** * * * Paramètres : cluster = graphique de blocs à consulter. * * index = indice du lien à considérer. * * * * Description : Calcule l'abscisse d'un lien à son départ d'un bloc. * * * * Retour : Abscisse à attribuer à un départ de lien. * * * * Remarques : - * * * ******************************************************************************/ static gint g_graph_cluster_compute_leaving_link_position(const GGraphCluster *cluster, size_t index) { gint result; /* Position à retourner */ size_t half; /* Indice de répartition égale */ bool odd; /* Partité du nombre de liens */ assert(index < cluster->ba_count); half = cluster->ba_count / 2; odd = (cluster->ba_count % 2 == 1); result = _g_graph_cluster_compute_link_position(cluster, index, half, odd); return result; } /****************************************************************************** * * * Paramètres : cluster = graphique de blocs à consulter. * * index = indice du lien à considérer. * * * * Description : Calcule l'abscisse d'un lien à son arrivée à un bloc. * * * * Retour : Abscisse à attribuer à une arrivée de lien. * * * * Remarques : - * * * ******************************************************************************/ static gint g_graph_cluster_compute_incoming_link_position(const GGraphCluster *cluster, size_t index) { gint result; /* Position à retourner */ size_t half; /* Indice de répartition égale */ bool odd; /* Partité du nombre de liens */ assert(index < cluster->ta_count); half = cluster->ta_count / 2; odd = (cluster->ta_count % 2 == 1); result = _g_graph_cluster_compute_link_position(cluster, index, half, odd); return result; } /****************************************************************************** * * * Paramètres : cluster = graphique de blocs à actualiser. * * * * Description : Détermine les abscisses des liens de boucle en place. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_graph_cluster_compute_loop_link_x_positions(GGraphCluster *cluster) { size_t i; /* Boucle de parcours #1 */ size_t j; /* Boucle de parcours #2 */ /* Liens de boucle */ compute_loop_link_x_with_vspace_manager(&cluster->vspaces, cluster); /* 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_loop_link_x_positions(cluster->ranks[i].clusters[j]); } /****************************************************************************** * * * Paramètres : cluster = graphique de blocs à actualiser. * * * * Description : Détermine les abscisses de tous les liens en place. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_graph_cluster_compute_link_x_positions(GGraphCluster *cluster) { gint mid_x; /* Abscisse centrale */ size_t i; /* Boucle de parcours #1 */ size_t half; /* Indice de répartition égale */ 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) for (i = 0; i < cluster->ba_count; i++) { pt = &cluster->bottom_anchors[i]->start[0]; pt->x = g_graph_cluster_compute_leaving_link_position(cluster, i); cluster->bottom_anchors[i]->start[1].x = pt->x; } /* Du côté des arrivées... */ if (cluster->ta_count > 0) { half = cluster->ta_count / 2; if (cluster->ta_count % 2 == 1) { for (i = half; i > 0; i--) { pt = &cluster->top_anchors[i - 1]->end[1]; pt->x = mid_x - (half - i + 1) * LINK_MARGIN; } cluster->top_anchors[half]->end[1].x = mid_x; for (i = half + 1; i < cluster->ta_count; i++) { pt = &cluster->top_anchors[i]->end[1]; pt->x = mid_x + (i - half) * LINK_MARGIN; } } else { for (i = half; i > 0; i--) { pt = &cluster->top_anchors[i - 1]->end[1]; pt->x = mid_x - LINK_MARGIN / 2 - (half - i) * LINK_MARGIN; } for (i = half; i < cluster->ta_count; i++) { pt = &cluster->top_anchors[i]->end[1]; pt->x = mid_x + LINK_MARGIN / 2 + (half - i) * LINK_MARGIN; } } } for (i = 0; i < cluster->ta_count; i++) cluster->top_anchors[i]->end[0].x = cluster->top_anchors[i]->end[1].x; /* 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_x_positions(cluster->ranks[i].clusters[j]); } /****************************************************************************** * * * Paramètres : cluster = graphique de blocs à traiter. * * * * Description : Réserve de l'espace vertical pour les lignes horizontales. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_graph_cluster_book_hspace_for_links(GGraphCluster *cluster) { size_t i; /* Boucle de parcours #1 */ graph_rank_t *rank; /* Rangée à manipuler */ size_t j; /* Boucle de parcours #2 */ GGraphCluster *sub; /* Bloc inférieur à manipuler */ size_t k; /* Boucle de parcours #3 */ gint x1; /* Abscisse de départ de lien */ gint x2; /* Abscisse d'arrivée de lien */ hspace_booking *new; /* Nouvelle réservation */ for (i = 0; i < cluster->ranks_count; i++) { rank = &cluster->ranks[i]; /* Enregistrement des besoins */ for (j = 0; j < rank->count; j++) { sub = rank->clusters[j]; for (k = 0; k < sub->ta_count; k++) { g_graph_edge_get_x_borders(sub->top_anchors[k]->edge, &x1, &x2); new = create_hspace_booking(x1); sub->top_anchors[k]->hslot = &new->index; if (x1 > x2) rank->right2left = qinsert(rank->right2left, &rank->r2l_count, sizeof(hspace_booking *), (__compar_fn_t)cmp_hspace_booking_r2l, &new); else if (x1 < x2) rank->left2right = qinsert(rank->left2right, &rank->l2r_count, sizeof(hspace_booking *), (__compar_fn_t)cmp_hspace_booking_l2r, &new); else sub->top_anchors[k]->hslot = NULL; } } /* Définition des couches */ for (j = 0; j < rank->r2l_count; j++) rank->right2left[j]->index = j; for (j = 0; j < rank->l2r_count; j++) rank->left2right[j]->index = j; /* Propagation des déterminations */ for (j = 0; j < rank->count; j++) g_graph_cluster_book_hspace_for_links(rank->clusters[j]); } } /****************************************************************************** * * * Paramètres : cluster = graphique de blocs à actualiser. * * * * Description : Détermine les ordonnées de tous les liens en place. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_graph_cluster_compute_link_y_positions(GGraphCluster *cluster) { gint y; /* Ordonnée d'application */ size_t i; /* Boucle de parcours #1 */ incoming_link_t *incoming; /* Raccourci pour le confort */ size_t j; /* Boucle de parcours #2 */ /* Du côté des départs... */ if (cluster->ba_count > 0) { y = cluster->alloc.y + cluster->alloc.height; for (i = 0; i < cluster->ba_count; i++) cluster->bottom_anchors[i]->start[0].y = y; } /* Du côté des arrivées... */ if (cluster->ta_count > 0) { y = cluster->alloc.y; for (i = 0; i < cluster->ta_count; i++) { incoming = cluster->top_anchors[i]; incoming->end[1].y = y; incoming->end[0].y = incoming->end[1].y - VERTICAL_MARGIN; if (incoming->hslot != NULL) incoming->end[0].y -= *incoming->hslot * LINK_MARGIN; incoming->other->start[1].y = incoming->end[0].y; } } /* Définition des liens de boucle */ compute_loop_link_y_with_vspace_manager(&cluster->vspaces, cluster); /* 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_y_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]); } /* ---------------------------------------------------------------------------------- */ /* CALCUL DE REPARTITION DE BLOCS */ /* ---------------------------------------------------------------------------------- */ /****************************************************************************** * * * 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*/ GCodeBlock *block; /* Bloc à manipuler */ #ifndef NDEBUG gboolean new; /* Bloc déjà traité ? */ #endif size_t dcount; /* Nombre de liens de dest. */ block_link_t *links; /* Liens associés au bloc */ size_t i; /* Boucle de parcours #1 */ block_link_t *dest; /* Bloc visé par un autre */ 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 */ block = g_block_list_get_block(list, index); result = g_graph_cluster_new(block, highlighted, binary); #ifndef NDEBUG new = g_hash_table_insert(all, block, result); assert(new); #else g_hash_table_insert(all, block, result); #endif /* Détermination des blocs suivants */ links = g_code_block_get_destinations(block, &dcount); for (i = 0; i < dcount; i++) { dest = &links[i]; switch (dest->type) { case ILT_EXEC_FLOW: case ILT_JUMP: case ILT_CASE_JUMP: case ILT_JUMP_IF_TRUE: case ILT_JUMP_IF_FALSE: for (j = 0; j < pending->count; j++) if (pending->list[j] == dest->linked) break; if (j == pending->count) { /** * Il faut vérifier ici si la destination n'a pas déjà été * empruntée, sauf peine de faire réagir l'assertion plus * haut au moment de l'insertion. * * Le type de code à problème est le suivant : * * ... * if (...) * ... * ... * * Le code suivant le bloc conditionnel a deux origines, * qui vont chacune poursuivre le traitement vers ce code * commun. * * Et comme les origines ne sont pas dominantes, on utilise * la table globale. */ if (!g_hash_table_contains(all, dest->linked)) { g_object_ref(G_OBJECT(dest->linked)); assert((pending->count + 1) < g_block_list_count_blocks(list)); pending->list[pending->count++] = dest->linked; } } break; default: break; } unref_block_link(dest); } if (links != NULL) free(links); g_object_unref(G_OBJECT(block)); /* 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_code_block_get_domination(block); if (test_in_bit_field(dominators, index)) { /* Dépilement */ changed = true; if ((i + 1) < pending->count) memmove(&pending->list[i], &pending->list[i + 1], (pending->count - i - 1) * sizeof(GCodeBlock *)); pending->count--; /* Intégration */ next = g_code_block_get_index(block); assert(next < g_block_list_count_blocks(list)); sub = setup_graph_clusters(binary, list, next, highlighted, pending, all); g_graph_cluster_add_sub(result, sub); } g_object_ref(G_OBJECT(block)); } } while (changed); return result; } /****************************************************************************** * * * Paramètres : binary = binaire charger dont le code est à représenter.* * list = ensemble de blocs basiques à manipuler. * * highlighted = gestionnaire de surbrillance pour segments. * * * * 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 */ /* Création des éléments */ all = g_hash_table_new(NULL, NULL); count = g_block_list_count_blocks(list); pending = malloc(sizeof(pending_blocks) + count * sizeof(GCodeBlock *)); pending->count = 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); /** * A ce point, tous les blocs sont placés. * On est donc en mesure de réorganiser les points d'arrivée * des liens afin d'éviter les croisements : un lien qui vient * de la gauche ne doit pas arriver tout à droite ! * * Cette consigne est valable pour les liens de boucle également, dont * l'origine est toujours dans un bloc inférieur au bloc de destination. * Le premier étant traité après le second, cela oblige à appeler * g_graph_cluster_dispatch_x() deux fois donc, car on ne peut effectuer * le tri des liens au début de cette fonction comme c'était fait * dans les premières versions du code. */ g_graph_cluster_sort_incoming_links(result); g_graph_cluster_reset_allocation(result); g_graph_cluster_dispatch_x(result); /* 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 */ /** * Comme g_graph_cluster_offset_x() n'agit que sur les abscisses et non sur * les largeurs, on ne peut pas définir les positions pour les liens de boucle * en amont et les décaler ensuite. * * Et comme la mise en place de ce type de lien peut déplacer le bloc parent, * ses repères pour ses propres liens peuvent être décaler. Il faut ainsi * une procédure distincte de g_graph_cluster_compute_link_x_positions(). * * On définit donc l'abscisse de ces liens ici, en redécalant encore un peu * les blocs au besoin. */ g_graph_cluster_compute_loop_link_x_positions(result); g_graph_cluster_compute_link_x_positions(result); g_graph_cluster_book_hspace_for_links(result); g_graph_cluster_set_y(result, 0); g_graph_cluster_compute_link_y_positions(result); g_graph_cluster_resolve_links(result); /* Sortie propre */ g_hash_table_unref(all); return result; }