path: root/src/analysis/disass/macro.c

/* Chrysalide - Outil d'analyse de fichiers binaires
 * macro.c - vue macroscopique des liens entre blocs d'instructions
 *
 * Copyright (C) 2012-2013 Cyrille Bagard
 *
 *  This file is part of Chrysalide.
 *
 *  OpenIDA is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  OpenIDA is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with Foobar.  If not, see <http://www.gnu.org/licenses/>.
 */


#include "macro.h"


#include <assert.h>
#include <malloc.h>
#include <stdlib.h>


#include "../blocks/flow.h"
#include "../blocks/virtual.h"



/* ------------------------ COUVERTURE D'UNE ZONE A DECOUPER ------------------------ */


/* Bornes d'une zone à couvrir */
typedef struct _code_coverage
{
    bool initial;                           /* Couverture racine ?         */

    mrange_t range;                         /* Couverture totale           */

    vmpa2t start;                           /* Position butoir de début    */

    vmpa2t *ends;                           /* Positions butoir de fin     */
    size_t ends_count;                      /* Quantité de fins possibles  */

    unsigned long *processed;               /* Octets traités dans la zone */
    size_t allocated;                       /* Taille de la cartographie   */

} code_coverage;


/* Met en place les délimitations d'une zone de code. */
static code_coverage *create_code_coverage(const mrange_t *);

/* Crée une copie d'une couverture de zone de code. */
static code_coverage *dup_code_coverage(const code_coverage *, const vmpa2t *);

/* Détruit des délimitations d'une zone de code. */
static void delete_code_coverage(code_coverage *);

/* Précise la position de départ courante pour une analyse. */
static const vmpa2t *get_code_coverage_start_addr(const code_coverage *);

/* Indique si une adresse est hors zone ou non. */
static bool code_coverage_stop_here(const code_coverage *coverage, const vmpa2t *);

/* Ajoute une adresse butoir pour la zone à couvrir. */
static bool add_ending_address_code_coverage(code_coverage *, const vmpa2t *);

/* Indique si une zone donnée n'a jamais été traitée ou non. */
static bool is_range_processed_in_coverage(const code_coverage *, const mrange_t *);

/* Marque une série d'octets comme ayant été traités. */
static void mark_range_as_processed_in_coverage(code_coverage *, const GArchInstruction *);



/* ------------------------- SUIVI DES FLOTS D'INSTRUCTIONS ------------------------- */


/* Indications sur une branche */
typedef struct _branch_info
{
    vmpa2t *hops;                           /* Jalons de la branche        */
    size_t count;                           /* Quantité de ces jalons      */

    vmpa2t entry;                           /* Valeur du jalon d'entrée    */

} branch_info;


/* Initialise le suivi d'une branche de flot d'exécution. */
static void init_branch_info(branch_info *);

/* Acte la fin d'un suivi d'une branche de flot d'exécution. */
static void clean_branch_info(branch_info *);

/* Indique si une adresse est retenue comme point de passage. */
static bool is_addr_in_branch(const branch_info *, const vmpa2t *);

/* Ajoute un nouveau jalon dans l'exécution d'une branche. */
static bool add_hop_into_branch(branch_info *, const vmpa2t *);

/* Retourne le premier point d'exécution d'une branche donnée. */
static const vmpa2t *get_entry_to_branch(const branch_info *);

/* Identifie les différents points de passage d'une branche. */
static void find_next_hops(GArchProcessor *, const vmpa2t *, const code_coverage *, branch_info *);

/* Retrouve le point de ralliement entre deux branches. */
static bool compute_first_common_addr(const branch_info *, const branch_info *, vmpa2t *);


/* Groupement de branches et d'indications */
typedef struct _branch_group
{
    branch_info *branches;                  /* Liste des branches          */
    size_t count;                           /* Taille de cette liste       */

} branch_group;


/* Initialise le suivi d'un ensemble de branches. */
static void init_branch_group(branch_group *);

/* Acte la fin d'un suivi d'un ensemble de branches. */
static void clean_branch_group(branch_group *);

/* Ajoute une branche à un ensemble de branches en place. */
static branch_info *extend_branch_group(branch_group *);

/* Retrouve le point de ralliement entre un groupe de branches. */
static bool compute_first_common_addr_in_group(const branch_group *, vmpa2t *);



/* --------------------------- DECOUPAGE EN BLOCS DE CODE --------------------------- */


/**
 * Procédure d'ajout de blocs : pour le premier, on conserve le bloc en mémoire
 * et on attend. Si rien ne suit, il constitura l'unique retour. Sinon, on
 * l'ajoute à partir de la sauvegarde, et le reste suit.
 */
#define DELAYED_BLOCK_ADDING(res, cache, blk)                               \
    do                                                                      \
    {                                                                       \
        if (res == NULL)                                                    \
        {                                                                   \
            if (cache == NULL)                                              \
                cache = blk;                                                \
            else                                                            \
            {                                                               \
                res = g_virtual_block_new();                                \
                g_virtual_block_add_child(G_VIRTUAL_BLOCK(res), cache);     \
            }                                                               \
        }                                                                   \
                                                                            \
        if (res != NULL)                                                    \
            g_virtual_block_add_child(G_VIRTUAL_BLOCK(res), blk);           \
                                                                            \
    }                                                                       \
    while (0)


/* Procède à la création d'un bloc d'instructions simple. */
static GInstrBlock *build_instruction_block_simple(GArchProcessor *, code_coverage *, GArchInstruction **, GArchInstruction *);

/* Procède à la définition d'un bloc d'instructions selectif. */
static GInstrBlock *build_instruction_blocks_case(GArchProcessor *, code_coverage *, const branch_group *, vmpa2t *);

/* Procède à la définition d'un bloc d'instruction if/then/else. */
static GInstrBlock *build_instruction_blocks_ite(GArchProcessor *, code_coverage *, const branch_info *, const branch_info *, vmpa2t *);

/* Procède à la définition d'un bloc d'instructions d'exception. */
static void add_instruction_blocks_except(GInstrBlock **, GInstrBlock **, GArchProcessor *, code_coverage *, const branch_group *, const branch_info *);

/* Procède à la définition de bloc regroupant des instructions. */
static GInstrBlock *build_instruction_blocks(GArchProcessor *, code_coverage *);



/* ---------------------------------------------------------------------------------- */
/*                          COUVERTURE D'UNE ZONE A DECOUPER                          */
/* ---------------------------------------------------------------------------------- */


/******************************************************************************
*                                                                             *
*  Paramètres  : range = définition de la zone à couvrir.                     *
*                                                                             *
*  Description : Met en place les délimitations d'une zone de code.           *
*                                                                             *
*  Retour      : Couverture d'une zone de code.                               *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static code_coverage *create_code_coverage(const mrange_t *range)
{
    code_coverage *result;                  /* Couverture à retourner      */
    phys_t length;                          /* Taille de la zone couverte  */
    size_t requested;                       /* Nombre de mots à allouer    */

    result = (code_coverage *)calloc(1, sizeof(code_coverage));

    result->initial = true;

    copy_mrange(&result->range, range);

    copy_vmpa(&result->start, get_mrange_addr(range));

    result->ends = (vmpa2t *)calloc(1, sizeof(vmpa2t));
    result->ends_count = 1;

    compute_mrange_end_addr(range, &result->ends[0]);

    length = get_mrange_length(range);

    requested = length / sizeof(unsigned long);
    if (length % sizeof(unsigned long) != 0) requested++;

    result->processed = (unsigned long *)calloc(requested, sizeof(unsigned long));
    result->allocated = requested;

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : src = informations de couverture à consulter.                *
*                new = nouvelle position de début, plus profonde.             *
*                                                                             *
*  Description : Crée une copie d'une couverture de zone de code.             *
*                                                                             *
*  Retour      : Couverture d'une zone de code copiée.                        *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static code_coverage *dup_code_coverage(const code_coverage *src, const vmpa2t *new)
{
    code_coverage *result;                  /* Couverture à retourner      */
    size_t i;                               /* Boucle de parcours          */

    result = (code_coverage *)calloc(1, sizeof(code_coverage));

    result->initial = false;

    copy_mrange(&result->range, &src->range);

    copy_vmpa(&result->start, new);

    result->ends = (vmpa2t *)calloc(src->ends_count, sizeof(vmpa2t));
    result->ends_count = src->ends_count;

    for (i = 0; i < result->ends_count; i++)
        copy_vmpa(&result->ends[i], &src->ends[i]);

    /**
     * Les blocs produits par le découpage sont à accès global, et ne sont donc pas
     * la propriété d'une branche particulière.
     * Il ne faut donc pas créer deux blocs identiques à partir de deux chemins
     * différents ; aussi on partage la couverture de code plutôt que la copier.
     * Et, par ailleurs, c'est plus simple & efficace.
     */

    result->processed = src->processed;

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : coverage = structure à libérer de la mémoire.                *
*                                                                             *
*  Description : Détruit des délimitations d'une zone de code.                *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void delete_code_coverage(code_coverage *coverage)
{
    free(coverage->ends);

    if (coverage->initial)
        free(coverage->processed);

    free(coverage);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : coverage = informations de couverture à consulter.           *
*                                                                             *
*  Description : Précise la position de départ courante pour une analyse.     *
*                                                                             *
*  Retour      : Position de départ pour une analyse d'une portion de zone.   *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static const vmpa2t *get_code_coverage_start_addr(const code_coverage *coverage)
{
    return &coverage->start;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : coverage = informations de couverture à consulter.           *
*                addr     = localisation à tester.                            *
*                                                                             *
*  Description : Indique si une adresse est hors zone ou non.                 *
*                                                                             *
*  Retour      : true si l'adresse ne doit pas être couverte, false sinon.    *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static bool code_coverage_stop_here(const code_coverage *coverage, const vmpa2t *addr)
{
    void *ptr;                              /* Résultat des recherches     */

    if (!mrange_contains_addr(&coverage->range, addr))
        return true;

    ptr = bsearch(addr, coverage->ends, coverage->ends_count,
                  sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa);

    return (ptr != NULL);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : coverage = informations de couverture à compléter.           *
*                addr     = localisation à ajouter.                           *
*                                                                             *
*  Description : Ajoute une adresse butoir pour la zone à couvrir.            *
*                                                                             *
*  Retour      : true si une insertion a été effectuée, false sinon.          *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static bool add_ending_address_code_coverage(code_coverage *coverage, const vmpa2t *addr)
{
    bool result;                            /* Bilan à retourner           */

    result = !code_coverage_stop_here(coverage, addr);

    if (result)
    {
        coverage->ends = (vmpa2t *)realloc(coverage->ends, ++coverage->ends_count * sizeof(vmpa2t));

        copy_vmpa(&coverage->ends[coverage->ends_count - 1], addr);

        qsort(coverage->ends, coverage->ends_count, sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa);

    }

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : coverage = informations de couverture à consulter.           *
*                range    = zone à interroger.                                *
*                                                                             *
*  Description : Indique si une zone donnée n'a jamais été traitée ou non.    *
*                                                                             *
*  Retour      : true si l'aire visée est vierge, false sinon.                *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static bool is_range_processed_in_coverage(const code_coverage *coverage, const mrange_t *range)
{
    bool result;                            /* Bilan à renvoyer            */
    phys_t diff;                            /* Décalage à appliquer        */
    size_t index;                           /* Cellule de tableau visée    */
    unsigned int remaining;                 /* Nombre de bits restants     */

    diff = compute_vmpa_diff(get_mrange_addr(&coverage->range), get_mrange_addr(range));
    assert(diff < get_mrange_length(&coverage->range));

    index = diff / (sizeof(unsigned long) * 8);
    remaining = diff % (sizeof(unsigned long) * 8);

    result = ((coverage->processed[index] & (1ul << remaining)) != 0);

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : coverage = informations de couverture à consulter.           *
*                instr    = instruction couvrant la zone à interroger.        *
*                                                                             *
*  Description : Marque une série d'octets comme ayant été traités.           *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void mark_range_as_processed_in_coverage(code_coverage *coverage, const GArchInstruction *instr)
{
    const mrange_t *range;                  /* Emplacement d'instruction   */
    phys_t diff;                            /* Décalage à appliquer        */
    size_t index;                           /* Cellule de tableau visée    */
    unsigned int remaining;                 /* Nombre de bits restants     */

    range = g_arch_instruction_get_range(instr);

    diff = compute_vmpa_diff(get_mrange_addr(&coverage->range), get_mrange_addr(range));
    assert(diff < get_mrange_length(&coverage->range));

    index = diff / (sizeof(unsigned long) * 8);
    remaining = diff % (sizeof(unsigned long) * 8);

    coverage->processed[index] |= (1ul << remaining);

}



/* ---------------------------------------------------------------------------------- */
/*                           SUIVI DES FLOTS D'INSTRUCTIONS                           */
/* ---------------------------------------------------------------------------------- */


/******************************************************************************
*                                                                             *
*  Paramètres  : info = informations à initialiser.                           *
*                                                                             *
*  Description : Initialise le suivi d'une branche de flot d'exécution.       *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void init_branch_info(branch_info *info)
{
    memset(info, 0, sizeof(branch_info));

}


/******************************************************************************
*                                                                             *
*  Paramètres  : info = informations à nettoyer.                              *
*                                                                             *
*  Description : Acte la fin d'un suivi d'une branche de flot d'exécution.    *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void clean_branch_info(branch_info *info)
{
    if (info->hops != NULL)
        free(info->hops);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : info = informations à consulter.                             *
*                addr = position à rechercher.                                *
*                                                                             *
*  Description : Indique si une adresse est retenue comme point de passage.   *
*                                                                             *
*  Retour      : true si le jalon est déjà dans la liste, false sinon.        *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static bool is_addr_in_branch(const branch_info *info, const vmpa2t *addr)
{
    void *ptr;                              /* Résultat des recherches     */

    ptr = bsearch(addr, info->hops, info->count,
                  sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa);

    return (ptr != NULL);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : info = informations de flot à compléter.                     *
*                addr = localisation à ajouter.                               *
*                                                                             *
*  Description : Ajoute un nouveau jalon dans l'exécution d'une branche.      *
*                                                                             *
*  Retour      : true si une insertion a été effectuée, false sinon.          *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static bool add_hop_into_branch(branch_info *info, const vmpa2t *addr)
{
    bool result;                            /* Bilan à retourner           */

    result = !is_addr_in_branch(info, addr);

    if (result)
    {
        if (info->count == 0)
            copy_vmpa(&info->entry, addr);

        info->hops = (vmpa2t *)realloc(info->hops, ++info->count * sizeof(vmpa2t));

        copy_vmpa(&info->hops[info->count - 1], addr);

        qsort(info->hops, info->count, sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa);

    }

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : info = informations de flot à consulter.                     *
*                                                                             *
*  Description : Retourne le premier point d'exécution d'une branche donnée.  *
*                                                                             *
*  Retour      : Point de départ d'une branche.                               *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static const vmpa2t *get_entry_to_branch(const branch_info *info)
{
    return &info->entry;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : proc     = ensemble des instructions d'assemblage.           *
*                start    = position du début de bloc.                        *
*                coverage = liste des adresses de fin butoir.                 *
*                count    = nombre de sauts détectés. [OUT]                   *
*                                                                             *
*  Description : Identifie les différents points de passage d'une branche.    *
*                                                                             *
*  Retour      : Jalons dans le flot d'exécution.                             *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void find_next_hops(GArchProcessor *proc, const vmpa2t *start, const code_coverage *coverage, branch_info *info)
{
    GArchInstruction *iter;                 /* Boucle de parcours #1       */
    const mrange_t *range;                  /* Emplacement d'instruction   */
    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 #2       */
    size_t not_handled;                     /* Nombre d'éléments écartés   */

    printf(" ---- FN [ %p ] ---------------------------\n", info);


    printf("CONTAINS ? %d\n", mrange_contains_addr(&coverage->range, start));

    /* Si la position est déjà présente, on évite de boucler... */
    if (!add_hop_into_branch(info, start))
    {
        printf("  ++ !add 0x%08x\n", (unsigned int)start->virtual);
        return;
    }
    else
        printf("  ++ add 0x%08x\n", (unsigned int)start->virtual);

    /* On suit le flot jusqu'à la prochaine bifurcation */
    for (iter = g_arch_processor_find_instr_by_address(proc, start);
         iter != NULL;
         iter = g_arch_processor_get_next_instr(proc, iter))
    {
        range = g_arch_instruction_get_range(iter);


        if (code_coverage_stop_here(coverage, get_mrange_addr(range)))
            printf("  ++ stop here 0x%08x\n", (unsigned int)range->addr.virtual);

        if (code_coverage_stop_here(coverage, get_mrange_addr(range)))
            break;


        if (g_arch_instruction_has_sources(iter))
            add_hop_into_branch(info, get_mrange_addr(range));



        if (g_arch_instruction_get_flags(iter) & AIF_RETURN_POINT)
            printf("  ++ return 0x%08x\n", (unsigned int)range->addr.virtual);

        if (g_arch_instruction_get_flags(iter) & AIF_RETURN_POINT)
        {
            iter = NULL;
            break;
        }

        /*
        if (!g_arch_instruction_has_destinations(iter))
            printf("  ++ no dest 0x%08x\n", (unsigned int)range->addr.virtual);
        */

        if (!g_arch_instruction_has_destinations(iter))
            continue;


        printf("  ++ dcount 0x%08x\n", (unsigned int)range->addr.virtual);

        dcount = g_arch_instruction_get_destinations(iter, &dests, &types, NULL);

        not_handled = 0;

        for (i = 0; i < dcount; i++)
        {
            range = g_arch_instruction_get_range(dests[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:
                    find_next_hops(proc, get_mrange_addr(range), coverage, info);
                    break;

                case ILT_LOOP:
                    add_hop_into_branch(info, get_mrange_addr(range));
                    break;

                default:
                    not_handled++;
                    break;

            }

        }

        if (not_handled < dcount)
            break;

    }

    /* Si on termine... */
    if (iter != NULL) add_hop_into_branch(info, get_mrange_addr(range));

    printf(" ------- [ %p ] ---\n", info);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : a = premier ensemble de jalons à parcourir.                  *
*                b = second ensemble de jalons à parcourir.                   *
*                c = éventuelle adresse commune à deux branches.              *
*                                                                             *
*  Description : Retrouve le point de ralliement entre deux branches.         *
*                                                                             *
*  Retour      : true si une position commune a pu être trouvée, false sinon. *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static bool compute_first_common_addr(const branch_info *a, const branch_info *b, vmpa2t *c)
{
    bool result;                            /* Bilan à retourner           */
    size_t i;                               /* Boucle de parcours          */

    result = false;


    printf("....................\n");

    printf(" A :: ");
    for (i = 0; i < a->count; i++)
        printf("0x%08x ", a->hops[i].virtual);
    printf("\n");

    printf(" B :: ");
    for (i = 0; i < b->count; i++)
        printf("0x%08x ", b->hops[i].virtual);
    printf("\n");


    for (i = 0; i < a->count && !result; i++)
        if (is_addr_in_branch(b, &a->hops[i]))
        {
            result = true;
            copy_vmpa(c, &a->hops[i]);
        }

    if (result)
        printf(" N :: 0x%08x\n", (unsigned int)c->virtual);
    else
        printf(" N :: ----\n");

    printf("....................\n");

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : group = informations à initialiser.                          *
*                                                                             *
*  Description : Initialise le suivi d'un ensemble de branches.               *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void init_branch_group(branch_group *group)
{
    memset(group, 0, sizeof(branch_group));

}


/******************************************************************************
*                                                                             *
*  Paramètres  : group = informations à nettoyer.                             *
*                                                                             *
*  Description : Acte la fin d'un suivi d'un ensemble de branches.            *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void clean_branch_group(branch_group *group)
{
    size_t i;                               /* Boucle de parcours          */

    for (i = 0; i < group->count; i++)
        clean_branch_info(&group->branches[i]);

    if (group->branches != NULL)
        free(group->branches);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : group = liste d'ensembles de jalons à agrandir.              *
*                                                                             *
*  Description : Ajoute une branche à un ensemble de branches en place.       *
*                                                                             *
*  Retour      : Nouvel élément rajouté et initialisé.                        *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static branch_info *extend_branch_group(branch_group *group)
{
    branch_info *result;                    /* Nouveauté à retourner       */

    group->branches = (branch_info *)realloc(group->branches,
                                             ++group->count * sizeof(branch_info));

    result = &group->branches[group->count];

    init_branch_info(result);

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : group  = liste d'ensembles de jalons à parcourir.            *
*                common = éventuelle adresse commune à branches.              *
*                                                                             *
*  Description : Retrouve le point de ralliement entre un groupe de branches. *
*                                                                             *
*  Retour      : true si une position commune a pu être trouvée, false sinon. *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static bool compute_first_common_addr_in_group(const branch_group *group, vmpa2t *common)
{
    vmpa_t result;                          /* Adresse trouvée à retourner */
    branch_info *list;                      /* Raccourci de confort        */
    size_t i;                               /* Boucle de parcours #1       */
    bool keep;                              /* Candidate à garder ?        */
    size_t j;                               /* Boucle de parcours #2       */

    result = false;

    list = group->branches;

    for (i = 0; i < list[0].count && !result; i++)
    {
        keep = true;

        for (j = 1; j < group->count && keep; j++)
            keep = is_addr_in_branch(&list[j], &list[0].hops[i]);

        if (keep)
            copy_vmpa(common, &list[0].hops[i]);

    }

    return result;

}



/* ---------------------------------------------------------------------------------- */
/*                             DECOUPAGE EN BLOCS DE CODE                             */
/* ---------------------------------------------------------------------------------- */


/******************************************************************************
*                                                                             *
*  Paramètres  : proc     = ensemble des instructions d'assemblage.           *
*                coverage = délimitations de la zone à couvrir.               *
*                first    = première instruction d'un bloc préliminaire.      *
*                cur      = instruction courante dans le traitement.          *
*                                                                             *
*  Description : Procède à la création d'un bloc d'instructions simple.       *
*                                                                             *
*  Retour      : Bloc créé ou NULL.                                           *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/
#include "../../arch/instruction-int.h"
static GInstrBlock *build_instruction_block_simple(GArchProcessor *proc, code_coverage *coverage, GArchInstruction **first, GArchInstruction *cur)
{
    GInstrBlock *result;                    /* Regroupement à retourner    */
 
    if (*first != NULL)
    {
        result = g_flow_block_new(proc, *first, cur);

        mark_range_as_processed_in_coverage(coverage, *first);

        *first = NULL;

    }
    else result = NULL;

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : proc     = ensemble des instructions d'assemblage.           *
*                coverage = délimitations de la zone à couvrir.               *
*                cases    = branches conditionnelles des situations.          *
*                next     = localisation de l'instruction de reprise.         *
*                                                                             *
*  Description : Procède à la définition d'un bloc d'instructions selectif.   *
*                                                                             *
*  Retour      : Bloc créé et enregistré, ou NULL si erreur.                  *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static GInstrBlock *build_instruction_blocks_case(GArchProcessor *proc, code_coverage *coverage, const branch_group *cases, vmpa2t *next)
{
    GInstrBlock *result;                    /* Regroupement à retourner    */
    bool has_common;                        /* Fin commune ?               */
    size_t i;                               /* Boucle de parcours #1       */
    code_coverage *sub_coverage;            /* Couverture pour les suivants*/
    size_t j;                               /* Boucle de parcours #2       */
    GInstrBlock *block;                     /* Nouveau bloc mis en place   */

    has_common = compute_first_common_addr_in_group(cases, next);
    if (!has_common) return NULL;

    result = g_virtual_block_new();

    for (i = 0; i < cases->count; i++)
    {
        sub_coverage = dup_code_coverage(coverage, get_entry_to_branch(&cases->branches[i]));

        add_ending_address_code_coverage(sub_coverage, next);

        for (j = 0; j < cases->count; j++)
            add_ending_address_code_coverage(sub_coverage, get_entry_to_branch(&cases->branches[j]));

        block = build_instruction_blocks(proc, sub_coverage);

        if (block != NULL)
            g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);

        delete_code_coverage(sub_coverage);

    }

    if (g_virtual_block_count_children(G_VIRTUAL_BLOCK(result)) == 0)
    {
        g_object_unref(G_OBJECT(result));
        result = NULL;
    }

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : proc         = ensemble des instructions d'assemblage.       *
*                coverage     = délimitations de la zone à couvrir.           *
*                true_branch  = branche conditionnelle correspondant à true.  *
*                false_branch = branche conditionnelle correspondant à false. *
*                next         = localisation de l'instruction de reprise.     *
*                                                                             *
*  Description : Procède à la définition d'un bloc d'instruction if/then/else.*
*                                                                             *
*  Retour      : Bloc créé et enregistré, ou NULL si erreur.                  *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static GInstrBlock *build_instruction_blocks_ite(GArchProcessor *proc, code_coverage *coverage, const branch_info *true_branch, const branch_info *false_branch, vmpa2t *next)
{
    GInstrBlock *result;                    /* Regroupement à retourner    */
    bool has_common;                        /* Fin commune ?               */
    GInstrBlock *block;                     /* Nouveau bloc mis en place   */

    has_common = compute_first_common_addr(true_branch, false_branch, next);


    if (!has_common)
    {
        code_coverage *_sub_coverage;        /* Couverture pour les suivants*/


        result = g_virtual_block_new();


        /* Branche 'true' */

        _sub_coverage = dup_code_coverage(coverage, get_entry_to_branch(true_branch));

        block = build_instruction_blocks(proc, _sub_coverage);

        delete_code_coverage(_sub_coverage);

        printf("===> !TRUE_BRANCH = %p\n", block);

        if (block != NULL)
            g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);

        /* Branche 'false' */

        _sub_coverage = dup_code_coverage(coverage, get_entry_to_branch(false_branch));

        block = build_instruction_blocks(proc, _sub_coverage);

        delete_code_coverage(_sub_coverage);

        printf("===> !FALSE_BRANCH = %p\n", block);

        if (block != NULL)
            g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);

        /* Conclusion */

        if (g_virtual_block_count_children(G_VIRTUAL_BLOCK(result)) == 0)
        {
            g_object_unref(G_OBJECT(result));
            result = NULL;
        }

        return result;




    }

    assert(has_common);

    if (!has_common) printf("   === nothing in common\n");
    if (!has_common) return NULL;

    result = g_virtual_block_new();

    /**
     * Encapsulation des branches conditionnelles.
     */

    GInstrBlock *build_instr_block_bi(GArchProcessor *proc, const code_coverage *coverage, const branch_info *br0, const branch_info *br1, const vmpa2t *next)
    {
        GInstrBlock *result;                /* Bloc construit à renvoyer   */
        code_coverage *sub_coverage;        /* Couverture pour les suivants*/

        result = NULL;

        if (br0->count > 0)
        {
            sub_coverage = dup_code_coverage(coverage, get_entry_to_branch(br0));

            add_ending_address_code_coverage(sub_coverage, next);

            if (br1->count > 0)
                add_ending_address_code_coverage(sub_coverage, get_entry_to_branch(br1));

            result = build_instruction_blocks(proc, sub_coverage);

            delete_code_coverage(sub_coverage);

        }

        return result;

    }

    /* Branche 'true' */

    block = build_instr_block_bi(proc, coverage, true_branch, false_branch, next);

    printf("===> TRUE_BRANCH = %p\n", block);

    if (block != NULL)
        g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);

    /* Branche 'false' */

    block = build_instr_block_bi(proc, coverage, false_branch, true_branch, next);

    printf("===> FALSE_BRANCH = %p\n", block);

    if (block != NULL)
        g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);

    /* Conclusion */

    if (g_virtual_block_count_children(G_VIRTUAL_BLOCK(result)) == 0)
    {
        g_object_unref(G_OBJECT(result));
        result = NULL;
    }

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : result      = liste générale résultante du découpage. [OUT]  *
*                cached      = emplacement pour le cache des résultats. [OUT] *
*                proc        = ensemble des instructions d'assemblage.        *
*                coverage    = délimitations de la zone à couvrir.            *
*                exceptions  = branche conditionnelle correspondant à true.   *
*                main_branch = branche principale avec son flot d'exécution.  *
*                                                                             *
*  Description : Procède à la définition d'un bloc d'instructions d'exception.*
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void add_instruction_blocks_except(GInstrBlock **result, GInstrBlock **cached, GArchProcessor *proc, code_coverage *coverage, const branch_group *exceptions, const branch_info *main_branch)
{
    size_t i;                               /* Boucle de parcours          */
    vmpa2t stop_addr;                       /* Adresse de fin de bloc      */
    bool has_stop;                          /* Fin commune ?               */
    code_coverage *sub_coverage;            /* Couverture pour les suivants*/
    GInstrBlock *block;                     /* Nouveau bloc mis en place   */

    for (i = 0; i < exceptions->count; i++)
    {
        has_stop = compute_first_common_addr(main_branch, &exceptions->branches[i], &stop_addr);
        if (!has_stop) continue;

        sub_coverage = dup_code_coverage(coverage, get_entry_to_branch(&exceptions->branches[i]));
        add_ending_address_code_coverage(sub_coverage, &stop_addr);

        block = build_instruction_blocks(proc, sub_coverage);

        if (block != NULL)
            DELAYED_BLOCK_ADDING(*result, *cached, block);

        delete_code_coverage(sub_coverage);

    }

}


/******************************************************************************
*                                                                             *
*  Paramètres  : proc     = ensemble des instructions d'assemblage.           *
*                coverage = délimitations de la zone à couvrir.               *
*                                                                             *
*  Description : Procède à la définition de bloc regroupant des instructions. *
*                                                                             *
*  Retour      : Bloc créé et enregistré, ou NULL si erreur.                  *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/
#include "../../arch/instruction-int.h"
static GInstrBlock *build_instruction_blocks(GArchProcessor *proc, code_coverage *coverage)
{
    GInstrBlock *result;                    /* Regroupement à retourner    */
    GInstrBlock *result_cached;             /* Temporisation pour unicité  */
    branch_info main_branch;                /* Flot d'exécution complet    */
    GArchInstruction *first;                /* Première instruction        */
    GArchInstruction *last;                 /* Dernière instruction        */
    GArchInstruction *iter;                 /* Boucle de parcours          */
    const mrange_t *range;                  /* Emplacement d'instruction   */
    const vmpa2t *addr;                     /* Adresse de la destination   */
    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       */
    GInstrBlock *block;                     /* Nouveau bloc mis en place   */
    GInstrBlock *group;                     /* Regroupement de blocs       */
    size_t not_handled;                     /* Quantité de liens non gérés */
    vmpa2t next_addr;                       /* Prochaine instruction visée */
    branch_group  cases_branches;           /* Branches d'un aiguillage    */
    branch_info true_branch;                /* Branche 'condition vraie'   */
    branch_info false_branch;               /* Branche 'condition fausse'  */
    branch_group excep_branches;            /* Branches d'exceptions       */
    branch_info *branch;                    /* Branche à suivre            */

    result = NULL;
    result_cached = NULL;

    first = NULL;
    last = NULL;

    init_branch_info(&main_branch);
    find_next_hops(proc, get_code_coverage_start_addr(coverage), coverage, &main_branch);


    printf("//////////////////////////\n");
    printf("/// Cutting for 0x%08x -> %p\n",
           get_code_coverage_start_addr(coverage)->virtual,
           g_arch_processor_find_instr_by_address(proc, get_code_coverage_start_addr(coverage)));
    printf("//////////////////////////\n");


    for (iter = g_arch_processor_find_instr_by_address(proc, get_code_coverage_start_addr(coverage));
         iter != NULL;
         )
    {
        range = g_arch_instruction_get_range(iter);
        addr = get_mrange_addr(range);

        if (code_coverage_stop_here(coverage, addr)) break;

        /* On s'arrête si l'instruction est déjà décompilée */
        if (is_range_processed_in_coverage(coverage, range)) break;

        if (first == NULL)
            first = iter;

        last = iter;

        /**
         * On s'arrête également en fin de procédure.
         * L'expérience montre qu'il peut y avoir plusieurs fins dans une routine,
         * et donc des fins en milieu de couverture de cette même routine.
         */
        if (g_arch_instruction_get_flags(iter) & AIF_RETURN_POINT) break;

        /* On n'approfondit que les chemins qui se séparent */
        if (!g_arch_instruction_has_destinations(iter))
        {
            iter = g_arch_processor_get_next_instr(proc, iter);
            continue;
        }

        /* Adaptations en fonction du type de bifurcation */

        dcount = g_arch_instruction_get_destinations(iter, &dests, &types, NULL);

        not_handled = 0;
        init_vmpa(&next_addr, VMPA_NO_PHYSICAL, VMPA_NO_VIRTUAL);

        init_branch_group(&cases_branches);
        init_branch_info(&true_branch);
        init_branch_info(&false_branch);
        init_branch_group(&excep_branches);

        for (i = 0; i < dcount; i++)
        {
            branch = NULL;

            switch (types[i])
            {
                case ILT_EXEC_FLOW:
                case ILT_JUMP:


                    //break;
                {
                    GArchInstruction *_saved0;

                    _saved0 = first;

                    block = build_instruction_block_simple(proc, coverage, &first, iter);
                    printf(" -- simple block JMP -- @ 0x%08x <-> 0x%08x\n",
                           (unsigned int)(_saved0 ? _saved0->range.addr.virtual : ~0),
                           (unsigned int)iter->range.addr.virtual);
                    fflush(NULL);
                }
                    DELAYED_BLOCK_ADDING(result, result_cached, block);

                    /**
                     * La prochaine adresse d'analyse est celle visée par l'instruction !
                     * Pour les sauts naturels, ça ne change rien ; ce n'est pas le cas
                     * pour les sauts explicites.
                     */
                    range = g_arch_instruction_get_range(dests[i]);
                    copy_vmpa(&next_addr, get_mrange_addr(range));

                    first = NULL;

                    break;

                case ILT_LOOP:
                    /**
                     * Lorsque l'on désassemble un flot d'instructions et que l'on rencontre
                     * une amorce de boucle, il y a deux cas de figure :
                     *
                     *    - soit il s'agit d'un ancien JUMP, et la reprise du désassemblage
                     *      se fera à partir de l'adresse ciblée.
                     *
                     *    - soit il s'agit d'un branchement conditionnel dont une des branches
                     *      conduit à un rebouclage. Le désassemblage s'arrête alors pour la
                     *      partie en boucle car il n'y a plus d'adresse commune pour la suite.
                     *
                     * Il reste donc à forcer une coupure dans le cas suivant :
                     *
                     *       ...
                     *       jmp xxxx
                     *    loc:
                     *       ...
                     *
                     * Il suffit de ne pas initialiser 'next_addr' et de laisser la main à d'éventuelles
                     * autres destinations voisines.
                     */
                     break;

                case ILT_CASE_JUMP:
                    branch = extend_branch_group(&cases_branches);
                    break;

                case ILT_JUMP_IF_TRUE:
                    printf("FIND TRUE BRANCH @ 0x%08x\n", (unsigned int)iter->range.addr.virtual);
                    branch = &true_branch;
                    break;

                case ILT_JUMP_IF_FALSE:
                    printf("FIND FALSE BRANCH @ 0x%08x\n", (unsigned int)iter->range.addr.virtual);
                    branch = &false_branch;
                    break;

                case ILT_CATCH_EXCEPTION:
                    branch = extend_branch_group(&excep_branches);

                    /**
                     * Les deux cas sont les seuls à ne pas conduire à une définition de
                     * next_addr, donc on les comptabilise sur un pied d'égalité !
                     */
                    /* break; */

                default:
                    not_handled++;
                    break;

            }

            /* Si on a une branche à compléter... */
            if (branch != NULL)
            {
                range = g_arch_instruction_get_range(dests[i]);
                addr = get_mrange_addr(range);

                printf("\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
                printf("BUILD @ 0x%08x\n", (unsigned int)addr->virtual);
                find_next_hops(proc, addr, coverage, branch);
                printf("<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n\n");

            }

        }

        /* Post-traitements de ILT_CASE_JUMP */
        if (cases_branches.count > 0)
        {
            block = build_instruction_block_simple(proc, coverage, &first, iter);
            DELAYED_BLOCK_ADDING(result, result_cached, block);

            group = build_instruction_blocks_case(proc, coverage, &cases_branches, &next_addr);

            if (group != NULL)
            {
                DELAYED_BLOCK_ADDING(result, result_cached, group);
                g_instr_block_set_links_block(block, group);
            }

        }

        /* Post-traitements de ILT_JUMP_IF_TRUE / ILT_JUMP_IF_FALSE */
        else if (true_branch.count > 0 || false_branch.count > 0)
        {
            block = build_instruction_block_simple(proc, coverage, &first, iter);

            GArchInstruction *_saved1;

            _saved1 = first;



            printf(" -- branches -- %d vs %d\n", (int)true_branch.count, (int)false_branch.count);

            printf(" -- simple block ITE -- @ 0x%08x <-> 0x%08x\n",
                   (unsigned int)(_saved1 ? _saved1->range.addr.virtual : ~0),
                   (unsigned int)iter->range.addr.virtual);
            fflush(NULL);
            DELAYED_BLOCK_ADDING(result, result_cached, block);

            group = build_instruction_blocks_ite(proc, coverage, &true_branch, &false_branch, &next_addr);

            printf(" --> group = %p  -  next = 0x%08x\n", group, next_addr.virtual);

            if (group != NULL)
            {
                DELAYED_BLOCK_ADDING(result, result_cached, group);
                g_instr_block_set_links_block(block, group);
            }

        }

        /* Post-traitements de ILT_CATCH_EXCEPTION */
        if (excep_branches.count > 0)
        {
            block = build_instruction_block_simple(proc, coverage, &first, iter);
            if (block != NULL) DELAYED_BLOCK_ADDING(result, result_cached, block);

            add_instruction_blocks_except(&result, &result_cached, proc, coverage,
                                          &excep_branches, &main_branch);

        }

        clean_branch_group(&cases_branches);
        clean_branch_info(&true_branch);
        clean_branch_info(&false_branch);
        clean_branch_group(&excep_branches);

        /* Détermination du prochain point de chute */

        if (not_handled == dcount)
            iter = g_arch_processor_get_next_instr(proc, iter);
        else
            iter = g_arch_processor_find_instr_by_address(proc, &next_addr);

    }

    if (first != NULL && last != NULL)
    {
        range = g_arch_instruction_get_range(first);

        if (!is_range_processed_in_coverage(coverage, range))
        {
            block = build_instruction_block_simple(proc, coverage, &first, last);
            DELAYED_BLOCK_ADDING(result, result_cached, block);
        }

    }

    clean_branch_info(&main_branch);

    return (result != NULL ? result : result_cached);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : proc      = processeur rassemblant les instructions à relier.*
*                routines  = prototypes existants à insérer.                  *
*                count     = quantité de ces prototypes.                      *
*                statusbar = barre de statut avec progression à mettre à jour.*
*                id        = identifiant du message affiché à l'utilisateur.  *
*                                                                             *
*  Description : Regroupe les instructions par blocs.                         *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void group_routines_instructions(GArchProcessor *proc, GBinRoutine **routines, size_t count, GtkExtStatusBar *statusbar, bstatus_id_t id)
{
    size_t i;                               /* Boucle de parcours          */
    const mrange_t *range;                  /* Emplacement de routine      */
    code_coverage *coverage;                /* Couverture de zone de code  */
    GInstrBlock *block;                     /* Regroupement d'instructions */

    for (i = 0; i < count; i++)
    {
        range = g_binary_routine_get_range(routines[i]);

        printf("===== BLOCK(S) for 0x%08x ======\n", range->addr.virtual);

        coverage = create_code_coverage(range);

        block = build_instruction_blocks(proc, coverage);
        g_binary_routine_set_basic_blocks(routines[i], block);


        bool visit_block(GInstrBlock *blk, BlockVisitOrder order, int *indent)
        {
            int i;

            switch (order)
            {
                case BVO_IN:
                case BVO_PENDING:

                    for (i = 0; i < *indent; i++)
                        printf("   ");

                    printf("%p '%s'", blk, G_OBJECT_TYPE_NAME(blk));

                    if (G_IS_FLOW_BLOCK(blk))
                    {
                        vmpa2t start;
                        vmpa2t end;

                        g_flow_block_get_boundary_addresses(G_FLOW_BLOCK(blk), &start, &end);

                        printf("  0x%08x -> 0x%08x",
                               (unsigned int)start.virtual,
                               (unsigned int)end.virtual);

                    }

                    printf("\n");

                    if (order == BVO_IN) (*indent)++;
                    break;

                case BVO_OUT:
                    (*indent)--;
                    break;

            }

            return true;

        }

        g_instr_block_visit(block, (instr_block_visitor_cb)visit_block, (int []){ 0 });

        printf("\n");



        delete_code_coverage(coverage);

        gtk_extended_status_bar_update_activity(statusbar, id, (i + 1) * 1.0 / count);

    }

}