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


#include "loop.h"



/* Matérialise les liens de retour arrière en tant que boucles. */
static void detect_back_edges(dragon_node *, size_t);



/******************************************************************************
*                                                                             *
*  Paramètres  : nodes = liste de noeuds détectés dans une routine.           *
*                count = taille de cette liste de noeuds à traiter.           *
*                                                                             *
*  Description : Matérialise les liens de retour arrière en tant que boucles. *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void detect_back_edges(dragon_node *nodes, size_t count)
{
    size_t k;                               /* Boucle de parcours #1       */
    dragon_node *node;                      /* Noeud à traiter             */
    const bitfield_t *dominators;           /* Liste de dominateurs        */
    GArchInstruction *last;                 /* Instruction finale de noeud */
    instr_link_t *dests;                    /* Instr. visées par une autre */
    size_t dcount;                          /* Nombre de liens de dest.    */
    size_t i;                               /* Boucle de parcours #2       */
    dragon_node *target;                    /* Noeud référence à tester    */
    size_t id;                              /* Indice du bit associé       */

    for (k = 0; k < count; k++)
    {
        node = get_dragon_node(nodes, k);

        dominators = get_domination_bits(node);

        get_dragon_node_bounding_instructions(node, NULL, &last);

        g_arch_instruction_wlock_dest(last);
        dcount = g_arch_instruction_get_destinations(last, &dests);

        for (i = 0; i < dcount; i++)
            switch (dests[i].type)
            {
                case ILT_EXEC_FLOW:
                case ILT_JUMP:
                case ILT_CASE_JUMP:
                case ILT_JUMP_IF_TRUE:
                case ILT_JUMP_IF_FALSE:

                    target = find_node_for_instruction(nodes, count, false, dests[i].linked);
                    if (target == NULL) break;

                    id = get_dragon_node_index(nodes, target);

                    if (test_in_bit_field(dominators, id, 1))
                    {

                        /*
                        printf("BACKEDGE :: 0x%08lx -> 0x%08lx\n",
                               (unsigned int)g_arch_instruction_get_range(last)->addr.virtual,
                               (unsigned int)g_arch_instruction_get_range(dests[i])->addr.virtual);
                        */

                        /* status = */g_arch_instruction_change_link(last, dests[i].linked, dests[i].type, ILT_LOOP);


                    }

                    break;

                default:
                    break;

            }

        g_arch_instruction_wunlock_dest(last);

    }

}


/******************************************************************************
*                                                                             *
*  Paramètres  : knight = informations quant à la complexité gérée du code.   *
*                                                                             *
*  Description : Détecte les boucles dans du code machine.                    *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void detect_loops_in_code(dragon_knight *knight)
{
    dragon_node *nodes;                     /* Liste des noeuds détectés   */
    size_t count;                           /* Taille de cette liste       */

    get_dragon_knight_content(knight, &nodes, &count);

    compute_all_dominators(nodes, count);

    detect_back_edges(nodes, count);

}