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