diff options
| -rw-r--r-- | ChangeLog | 12 | ||||
| -rw-r--r-- | src/analysis/disass/loop.c | 176 | ||||
| -rwxr-xr-x | src/common/Makefile.am | 1 | ||||
| -rw-r--r-- | src/common/bits.c | 464 | ||||
| -rw-r--r-- | src/common/bits.h | 86 |
5 files changed, 582 insertions, 157 deletions
@@ -1,3 +1,15 @@ +15-10-06 Cyrille Bagard <nocbos@gmail.com> + + * src/analysis/disass/loop.c: + Optimize loop detections using bit fields. + + * src/common/bits.c: + * src/common/bits.h: + New entries: define bit fields. + + * src/common/Makefile.am: + Add the new 'bits.[ch]' files into libcommon_la_SOURCES. + 15-10-04 Cyrille Bagard <nocbos@gmail.com> * src/format/mangling/demangler.c: diff --git a/src/analysis/disass/loop.c b/src/analysis/disass/loop.c index 88b997f..30265c9 100644 --- a/src/analysis/disass/loop.c +++ b/src/analysis/disass/loop.c @@ -29,155 +29,13 @@ #include <string.h> +#include "../../common/bits.h" -/* Suivi du flot d'exécution */ -typedef struct _exec_flow -{ - vmpa2t *steps; /* Jalons dans l'exécution */ - size_t count; /* Quantité de ces points */ - -} exec_flow; - - -/* Initialise un flot d'exécution. */ -static exec_flow *create_exec_flow(void); - -/* Réalise la copie d'un flot d'exécution. */ -static exec_flow *dup_exec_flow(const exec_flow *); - -/* Efface de la mémoire un flot d'exécution. */ -static void delete_exec_flow(exec_flow *); -/* Recherche si le chemin d'exécution a déjà mené à une adresse. */ -static bool is_new_exec_flow(const exec_flow *, const vmpa2t *); - -/* Ajoute une adresse jalon dans un flot d'exécution. */ -static void add_step_into_exec_flow(exec_flow *, const vmpa2t *); /* Suit un flot d'exécution à la recherche de boucles. */ -static void track_loops_in_code(const GArchProcessor *, const mrange_t *, const vmpa2t *, exec_flow *); - - - -/****************************************************************************** -* * -* Paramètres : - * -* * -* Description : Initialise un flot d'exécution. * -* * -* Retour : Flot d'exécution nouveau. * -* * -* Remarques : - * -* * -******************************************************************************/ - -static exec_flow *create_exec_flow(void) -{ - exec_flow *result; /* Flot vierge à retourner */ - - result = (exec_flow *)calloc(1, sizeof(exec_flow)); - - return result; - -} - - -/****************************************************************************** -* * -* Paramètres : src = jalons de l'exécution à dupliquer. * -* * -* Description : Réalise la copie d'un flot d'exécution. * -* * -* Retour : Flot d'exécution copié. * -* * -* Remarques : - * -* * -******************************************************************************/ +static void track_loops_in_code(const GArchProcessor *, const mrange_t *, const vmpa2t *, memfield_t *); -static exec_flow *dup_exec_flow(const exec_flow *src) -{ - exec_flow *result; /* Copie à retourner */ - - result = (exec_flow *)calloc(1, sizeof(exec_flow)); - - result->steps = (vmpa2t *)malloc(src->count * sizeof(vmpa2t)); - memcpy(result->steps, src->steps, src->count * sizeof(vmpa2t)); - - result->count = src->count; - - return result; - -} - - -/****************************************************************************** -* * -* Paramètres : flow = jalons de l'exécution à supprimer. * -* * -* Description : Efface de la mémoire un flot d'exécution. * -* * -* Retour : - * -* * -* Remarques : - * -* * -******************************************************************************/ - -static void delete_exec_flow(exec_flow *flow) -{ - if (flow->steps != NULL) - free(flow->steps); - - free(flow); - -} - - -/****************************************************************************** -* * -* Paramètres : flow = ensemble des jalons de l'exécution du code. * -* addr = adresse d'un nouvel embranchement. * -* * -* Description : Recherche si le chemin d'exécution a déjà mené à une adresse.* -* * -* Retour : true si l'instruction est visitée pour la première fois. * -* * -* Remarques : - * -* * -******************************************************************************/ - -static bool is_new_exec_flow(const exec_flow *flow, const vmpa2t *addr) -{ - void *ret; /* Conclusion d'une recherche */ - - ret = bsearch(addr, flow->steps, flow->count, - sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa); - - return (ret == NULL); - -} - - -/****************************************************************************** -* * -* Paramètres : flow = jalons de l'exécution du code à compléter. * -* addr = adresse d'un nouvel embranchement. * -* * -* Description : Ajoute une adresse jalon dans un flot d'exécution. * -* * -* Retour : - * -* * -* Remarques : - * -* * -******************************************************************************/ - -static void add_step_into_exec_flow(exec_flow *flow, const vmpa2t *addr) -{ - flow->steps = (vmpa2t *)realloc(flow->steps, ++flow->count * sizeof(vmpa2t)); - copy_vmpa(&flow->steps[flow->count - 1], addr); - - qsort(flow->steps, flow->count, sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa); - -} /****************************************************************************** @@ -195,7 +53,7 @@ static void add_step_into_exec_flow(exec_flow *flow, const vmpa2t *addr) * * ******************************************************************************/ -static void track_loops_in_code(const GArchProcessor *proc, const mrange_t *range, const vmpa2t *start, exec_flow *flow) +static void track_loops_in_code(const GArchProcessor *proc, const mrange_t *range, const vmpa2t *start, memfield_t *flow) { bool exit_track; /* Détermine la fin du parcours*/ GArchInstruction *iter; /* Boucle de parcours */ @@ -205,9 +63,9 @@ static void track_loops_in_code(const GArchProcessor *proc, const mrange_t *rang size_t dcount; /* Nombre de liens de dest. */ size_t i; /* Boucle de parcours */ const vmpa2t *addr; /* Prochaine adresse de saut */ - exec_flow *next_flow; /* Suite de l'exécution */ + memfield_t *next_flow; /* Suite de l'exécution */ - add_step_into_exec_flow(flow, start); + set_in_mem_field(flow, start); exit_track = false; @@ -236,8 +94,8 @@ static void track_loops_in_code(const GArchProcessor *proc, const mrange_t *rang { addr = get_mrange_addr(irange); - if (is_new_exec_flow(flow, addr)) - add_step_into_exec_flow(flow, addr); + if (!test_in_mem_field(flow, addr)) + set_in_mem_field(flow, start); } @@ -261,9 +119,9 @@ static void track_loops_in_code(const GArchProcessor *proc, const mrange_t *rang irange = g_arch_instruction_get_range(dests[i]); addr = get_mrange_addr(irange); - next_flow = create_exec_flow(); + next_flow = create_mem_field_from(flow); track_loops_in_code(proc, range, addr, next_flow); - delete_exec_flow(next_flow); + delete_mem_field(next_flow); break; @@ -280,16 +138,20 @@ static void track_loops_in_code(const GArchProcessor *proc, const mrange_t *rang exit_track = true; irange = g_arch_instruction_get_range(dests[i]); + + if (!mrange_contains_mrange(range, irange)) + break; + addr = get_mrange_addr(irange); - if (!is_new_exec_flow(flow, addr)) + if (test_in_mem_field(flow, addr)) /* status = */g_arch_instruction_change_link(iter, dests[i], types[i], ILT_LOOP); else { - next_flow = dup_exec_flow(flow); + next_flow = dup_mem_field(flow); track_loops_in_code(proc, range, addr, next_flow); - delete_exec_flow(next_flow); + delete_mem_field(next_flow); } break; @@ -324,15 +186,15 @@ void detect_loops_in_code(const GArchProcessor *proc, GBinRoutine **routines, si { size_t i; /* Boucle de parcours */ const mrange_t *range; /* Couverture d'une routine */ - exec_flow *flow; /* Flot d'exécution à suivre */ + memfield_t *flow; /* Flot d'exécution à suivre */ for (i = 0; i < count; i++) { range = g_binary_routine_get_range(routines[i]); - flow = create_exec_flow(); + flow = create_mem_field(range); track_loops_in_code(proc, range, get_mrange_addr(range), flow); - delete_exec_flow(flow); + delete_mem_field(flow); gtk_extended_status_bar_update_activity(statusbar, id, (i + 1) * 1.0 / count); diff --git a/src/common/Makefile.am b/src/common/Makefile.am index 1ab4768..7a35813 100755 --- a/src/common/Makefile.am +++ b/src/common/Makefile.am @@ -4,6 +4,7 @@ lib_LTLIBRARIES = libcommon.la libcommon_la_SOURCES = \ asm.h asm.c \ bconst.h \ + bits.h bits.c \ cpp.h \ dllist.h dllist.c \ endianness.h endianness.c \ diff --git a/src/common/bits.c b/src/common/bits.c new file mode 100644 index 0000000..1bd90f4 --- /dev/null +++ b/src/common/bits.c @@ -0,0 +1,464 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * bits.c - manipulation d'un champ de bits quelconque + * + * Copyright (C) 2015 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 "bits.h" + + +#include <assert.h> +#include <malloc.h> +#include <string.h> + + + +/* ----------------------------- CHAMPS DE BITS SIMPLES ----------------------------- */ + + +/* Champ de bits simple */ +struct _bitfield_t +{ + size_t length; /* Nombre de bits représentés */ + + void *tail; /* Limite du tableau de bits */ + + unsigned long bits[0]; /* Mémoire d'accès associée */ + +}; + + +/* Crée un champ de bits initialisé à zéro. */ +static bitfield_t *_create_bit_field(size_t, size_t); + +/* Crée une copie de champ de bits initialisé à zéro. */ +static bitfield_t *_create_bit_field_from(const bitfield_t *, size_t); + +/* Crée une copie d'un champ de bits classique. */ +static bitfield_t *_dup_bit_field(const bitfield_t *, size_t); + + + +/* ---------------------------------------------------------------------------------- */ +/* CHAMPS DE BITS SIMPLES */ +/* ---------------------------------------------------------------------------------- */ + + +/****************************************************************************** +* * +* Paramètres : length = nom de bits du champ à représenter. * +* extra = espace mémoire supplémentaire à ajouter au final. * +* * +* Description : Crée un champ de bits initialisé à zéro. * +* * +* Retour : Champ de bits mis en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static bitfield_t *_create_bit_field(size_t length, size_t extra) +{ + bitfield_t *result; /* Création à retourner */ + size_t requested; /* Nombre de mots à allouer */ + size_t base; /* Allocation de base en octets*/ + + requested = length / sizeof(unsigned long); + if (length % sizeof(unsigned long) != 0) requested++; + + base = sizeof(bitfield_t) + requested * sizeof(unsigned long); + + result = (bitfield_t *)malloc(base + extra); + + result->length = length; + + result->tail = ((char *)result) + base; + + memset(result->bits, 0, requested * sizeof(unsigned long)); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : length = nom de bits du champ à représenter. * +* * +* Description : Crée un champ de bits initialisé à zéro. * +* * +* Retour : Champ de bits mis en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +bitfield_t *create_bit_field(size_t length) +{ + return _create_bit_field(length, 0); + +} + + +/****************************************************************************** +* * +* extra = espace mémoire supplémentaire à ajouter au final. * +* Paramètres : length = nom de bits du champ à représenter. * +* * +* Description : Crée une copie de champ de bits initialisé à zéro. * +* * +* Retour : Champ de bits mis en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static bitfield_t *_create_bit_field_from(const bitfield_t *field, size_t extra) +{ + return _create_bit_field(field->length, extra); + +} + + +/****************************************************************************** +* * +* Paramètres : length = nom de bits du champ à représenter. * +* * +* Description : Crée une copie de champ de bits initialisé à zéro. * +* * +* Retour : Champ de bits mis en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +bitfield_t *create_bit_field_from(const bitfield_t *field) +{ + return _create_bit_field_from(field, 0); + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à effacer. * +* * +* Description : Supprime de la mémoire un champ de bits donné. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void delete_bit_field(bitfield_t *field) +{ + free(field); + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à dupliquer. * +* extra = espace mémoire supplémentaire à ajouter au final. * +* * +* Description : Crée une copie d'un champ de bits classique. * +* * +* Retour : Champ de bits mis en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static bitfield_t *_dup_bit_field(const bitfield_t *field, size_t extra) +{ + bitfield_t *result; /* Copie à retourner */ + size_t requested; /* Nombre de mots à allouer */ + + result = _create_bit_field(field->length, extra); + + requested = field->length / sizeof(unsigned long); + if (field->length % sizeof(unsigned long) != 0) requested++; + + memcpy(result->bits, field->bits, requested * sizeof(unsigned long)); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à dupliquer. * +* * +* Description : Crée une copie d'un champ de bits classique. * +* * +* Retour : Champ de bits mis en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +bitfield_t *dup_bit_field(const bitfield_t *field) +{ + return _dup_bit_field(field, 0); + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à modifier. * +* first = indice du premier bit à traiter. * +* count = nombre de bits à marquer. * +* * +* Description : Bascule à 1 une partie d'un champ de bits. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void set_in_bit_field(bitfield_t *field, size_t first, size_t count) +{ + size_t last; /* Point d'arrêt de la boucle */ + size_t i; /* Boucle de parcours */ + size_t index; /* Cellule de tableau visée */ + size_t remaining; /* Nombre de bits restants */ + + last = first + count; + + assert(last <= field->length); + + for (i = first; i < last; i++) + { + index = i / (sizeof(unsigned long) * 8); + remaining = i % (sizeof(unsigned long) * 8); + + field->bits[index] |= (1ul << remaining); + + } + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à modifier. * +* first = indice du premier bit à traiter. * +* count = nombre de bits à marquer. * +* * +* Description : Détermine si un bit est à 1 dans un champ de bits. * +* * +* Retour : true si le bit correspondant est à l'état haut. * +* * +* Remarques : - * +* * +******************************************************************************/ + +bool test_in_bit_field(bitfield_t *field, size_t first, size_t count) +{ + bool result; /* Valeur retrouvée à renvoyer */ + size_t last; /* Point d'arrêt de la boucle */ + size_t i; /* Boucle de parcours */ + size_t index; /* Cellule de tableau visée */ + size_t remaining; /* Nombre de bits restants */ + + last = first + count; + + assert(last <= field->length); + + result = true; + + for (i = first; i < last && result; i++) + { + index = i / (sizeof(unsigned long) * 8); + remaining = i % (sizeof(unsigned long) * 8); + + result = field->bits[index] & (1ul << remaining); + + } + + return result; + +} + + + +/* ---------------------------------------------------------------------------------- */ +/* CHAMPS LIES À UNE ZONE MEMOIRE */ +/* ---------------------------------------------------------------------------------- */ + + +/****************************************************************************** +* * +* Paramètres : range = espace mémoire à couvrir. * +* * +* Description : Crée un champ de bits couvrant une zone mémoire. * +* * +* Retour : Champ de bits mis en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +memfield_t *create_mem_field(const mrange_t *range) +{ + bitfield_t *result; /* Création à retourner */ + + result = _create_bit_field(get_mrange_length(range), sizeof(vmpa2t)); + + copy_vmpa((vmpa2t *)result->tail, get_mrange_addr(range)); + + return (memfield_t *)result; + +} + + +/****************************************************************************** +* * +* Paramètres : range = espace mémoire à couvrir. * +* * +* Description : Crée une copie de champ de bits couvrant une zone mémoire. * +* * +* Retour : Champ de bits mis en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +memfield_t *create_mem_field_from(const memfield_t *field) +{ + bitfield_t *result; /* Création à retourner */ + + result = _create_bit_field_from((bitfield_t *)field, sizeof(vmpa2t)); + + copy_vmpa((vmpa2t *)result->tail, (vmpa2t *)field->tail); + + return (memfield_t *)result; + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à effacer. * +* * +* Description : Supprime de la mémoire un champ de bits donné. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void delete_mem_field(memfield_t *field) +{ + delete_bit_field((bitfield_t *)field); + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à dupliquer. * +* * +* Description : Crée une copie d'un champ de bits couvrant une zone mémoire. * +* * +* Retour : Champ de bits mis en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +memfield_t *dup_mem_field(const memfield_t *field) +{ + bitfield_t *result; /* Création à retourner */ + + result = _dup_bit_field((bitfield_t *)field, sizeof(vmpa2t)); + + copy_vmpa((vmpa2t *)result->tail, (vmpa2t *)field->tail); + + return (memfield_t *)result; + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à modifier. * +* addr = emplacement en mémoire à traiter. * +* * +* Description : Bascule à 1 un bit d'un champ de bits. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void set_in_mem_field(memfield_t *field, const vmpa2t *addr) +{ + vmpa2t *start; /* Adresse de début */ + phys_t offset; /* Décallage de départ */ + + start = (vmpa2t *)field->tail; + + assert(cmp_vmpa(start, addr) <= 0); + + offset = compute_vmpa_diff(start, addr); + + set_in_bit_field((bitfield_t *)field, offset, 1); + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à modifier. * +* addr = emplacement en mémoire à tester. * +* * +* Description : Détermine si un bit est à 1 dans un champ de bits. * +* * +* Retour : true si le bit correspondant est à l'état haut. * +* * +* Remarques : - * +* * +******************************************************************************/ + +bool test_in_mem_field(memfield_t *field, const vmpa2t *addr) +{ + bool result; /* Valeur retrouvée à renvoyer */ + vmpa2t *start; /* Adresse de début */ + phys_t offset; /* Décallage de départ */ + + start = (vmpa2t *)field->tail; + + assert(cmp_vmpa(start, addr) <= 0); + + offset = compute_vmpa_diff(start, addr); + + result = test_in_bit_field((bitfield_t *)field, offset, 1); + + return result; + +} diff --git a/src/common/bits.h b/src/common/bits.h new file mode 100644 index 0000000..6eeb19c --- /dev/null +++ b/src/common/bits.h @@ -0,0 +1,86 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * bits.h - prototypes pour la manipulation d'un champ de bits quelconque + * + * Copyright (C) 2015 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/>. + */ + + +#ifndef _COMMON_BITS_H +#define _COMMON_BITS_H + + +#include "../arch/vmpa.h" + + + +/* ----------------------------- CHAMPS DE BITS SIMPLES ----------------------------- */ + + +/* Champ de bits simple */ +typedef struct _bitfield_t bitfield_t; + + +/* Crée un champ de bits initialisé à zéro. */ +bitfield_t *create_bit_field(size_t); + +/* Crée une copie de champ de bits initialisé à zéro. */ +bitfield_t *create_bit_field_from(const bitfield_t *); + +/* Supprime de la mémoire un champ de bits donné. */ +void delete_bit_field(bitfield_t *); + +/* Crée une copie d'un champ de bits classique. */ +bitfield_t *dup_bit_field(const bitfield_t *); + +/* Bascule à 1 une partie d'un champ de bits. */ +void set_in_bit_field(bitfield_t *, size_t, size_t); + +/* Détermine si un bit est à 1 dans un champ de bits. */ +bool test_in_bit_field(bitfield_t *, size_t, size_t); + + + +/* ------------------------- CHAMPS LIES À UNE ZONE MEMOIRE ------------------------- */ + + +/* Champ de bits couvrant une mémoire */ +typedef struct _bitfield_t memfield_t; + + +/* Crée un champ de bits couvrant une zone mémoire. */ +memfield_t *create_mem_field(const mrange_t *); + +/* Crée une copie de champ de bits couvrant une zone mémoire. */ +memfield_t *create_mem_field_from(const memfield_t *); + +/* Supprime de la mémoire un champ de bits donné. */ +void delete_mem_field(memfield_t *); + +/* Crée une copie d'un champ de bits couvrant une zone mémoire. */ +memfield_t *dup_mem_field(const memfield_t *); + +/* Bascule à 1 un bit d'un champ de bits. */ +void set_in_mem_field(memfield_t *, const vmpa2t *); + +/* Détermine si un bit est à 1 dans un champ de bits. */ +bool test_in_mem_field(memfield_t *, const vmpa2t *); + + + +#endif /* _COMMON_BITS_H */ |