Optimized loop detections using bit fields.

git-svn-id: svn://svn.gna.org/svn/chrysalide/trunk@586 abbe820e-26c8-41b2-8c08-b7b2b41f8b0a

3 files changed, 551 insertions, 0 deletions

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 */