summaryrefslogtreecommitdiff
path: root/src/common/array.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/common/array.c')
-rw-r--r--src/common/array.c434
1 files changed, 434 insertions, 0 deletions
diff --git a/src/common/array.c b/src/common/array.c
new file mode 100644
index 0000000..a4b55f4
--- /dev/null
+++ b/src/common/array.c
@@ -0,0 +1,434 @@
+
+/* Chrysalide - Outil d'analyse de fichiers binaires
+ * array.c - manipulation optimisée de tableaux au niveau de l'empreinte mémoire
+ *
+ * Copyright (C) 2017 Cyrille Bagard
+ *
+ * This file is part of Chrysalide.
+ *
+ * Chrysalide 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.
+ *
+ * Chrysalide 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 "array.h"
+
+
+#include <assert.h>
+#include <endian.h>
+#include <glib.h>
+#include <malloc.h>
+#ifndef NDEBUG
+# include <stdbool.h>
+#endif
+#include <string.h>
+
+
+
+/**
+ * L'expression du besoin d'une gestion optimisée des tableaux se base sur la
+ * structure usuelle et naïve suivante :
+ *
+ * {
+ * void **array;
+ * size_t count;
+ * }
+ *
+ * Déjà, size_t mesure la taille d'un long sur 64 bits. Ensuite, si le tableau
+ * renvoie effectivement vers des pointeurs, un tableau à un seul élément va
+ * allouer 8 octets (sur 64 bits) pour stocker ce seul élément. Cela fait donc
+ * 16 octets inutiles.
+ *
+ * Le jeu des alignements fait que la structure définie ici devrait être alignée
+ * sur 8 octets.
+ *
+ * Cela laisse donc 3 bits toujours nuls à disposition pour conserver quelques
+ * informations utiles.
+ *
+ * Cf. http://www.catb.org/esr/structure-packing/
+ *
+ * Pour les notions de verrouillage, la consommation mémoire peut vite augmenter :
+ * GRWLock pèse par exemple 16 octets pour offrir la distinction entre consultation
+ * et modification.
+ *
+ * Dans le même temps, des solutions plus légères existent : la GLib propose
+ * incidemment les fonctions portables g_bit_lock() / g_bit_unlock().
+ *
+ * Cependant, elles ne fonctionnent que sur des gint. Donc il faut s'adapter pour
+ * les architectures en grand boutisme. Comment il est peu vraisemblable que le
+ * bit de poids fort habituellement associé à l'espace noyau se retrouve dans des
+ * adresses utilisateurs manipulées ici, on l'utilise pour le verrou au besoin.
+ */
+
+#if __BYTE_ORDER == __LITTLE_ENDIAN
+
+# define FLAT_ARRAY_LOCK_BIT 0
+# define FLAT_ARRAY_LOCK_MASK (1 << 0)
+
+#elif __BYTE_ORDER == __BIG_ENDIAN
+
+# define FLAT_ARRAY_LOCK_BIT 31
+# define FLAT_ARRAY_LOCK_MASK (1 << (__WORDSIZE - 1))
+
+#else
+
+# error "Unknown byte order"
+
+#endif
+
+#define FLAT_ARRAY_INDEX_MASK (1 << 1)
+
+#define FLAT_ARRAY_USED_MASK (FLAT_ARRAY_INDEX_MASK | FLAT_ARRAY_LOCK_MASK)
+
+
+/* Tableau compressé à 2 éléments ou plus */
+typedef struct _ext_flat_array_t
+{
+ void *items; /* Tableau d'éléments */
+ size_t count; /* Quantité d'éléments */
+
+} ext_flat_array_t;
+
+
+#define FLAT_ARRAY_IS_LOCKED(a) (((unsigned long)a) & FLAT_ARRAY_LOCK_MASK)
+
+#define FLAT_ARRAY_IS_EMPTY(a) ((((unsigned long)a) & ~FLAT_ARRAY_USED_MASK) == 0)
+
+#define FLAT_ARRAY_HAS_NO_INDEX(a) ((((unsigned long)a) & FLAT_ARRAY_INDEX_MASK) == 0)
+
+#define FLAT_ARRAY_SET_INDEX(a) *((unsigned long *)&a) |= FLAT_ARRAY_INDEX_MASK
+
+#define GET_LONELY_ITEM(a) (void *)(((unsigned long)a) & ~FLAT_ARRAY_USED_MASK)
+
+#define EXTENDED_ARRAY(a) (ext_flat_array_t *)(((unsigned long)a) & ~FLAT_ARRAY_USED_MASK)
+
+
+
+/******************************************************************************
+* *
+* Paramètres : array = tableau compressé à modifier. [OUT] *
+* *
+* Description : Verrouille l'accès à un tableau compressé. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void lock_flat_array(flat_array_t **array)
+{
+ g_bit_lock((gint *)array, FLAT_ARRAY_LOCK_BIT);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : array = tableau compressé à modifier. [OUT] *
+* *
+* Description : Déverrouille l'accès à un tableau compressé. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void unlock_flat_array(flat_array_t **array)
+{
+ g_bit_unlock((gint *)array, FLAT_ARRAY_LOCK_BIT);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : array = tableau compressé à consulter. *
+* *
+* Description : Indique la quantité d'éléments présents dans le tableau. *
+* *
+* Retour : Nombre d'éléments attachés. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+size_t count_flat_array_items(const flat_array_t *array)
+{
+ size_t result; /* Quantité à retourner */
+ ext_flat_array_t *extended; /* Version de tableau étendue */
+
+ assert(FLAT_ARRAY_IS_LOCKED(array));
+
+ if (FLAT_ARRAY_IS_EMPTY(array))
+ result = 0;
+
+ else
+ {
+ if (FLAT_ARRAY_HAS_NO_INDEX(array))
+ result = 1;
+
+ else
+ {
+ extended = EXTENDED_ARRAY(array);
+ result = extended->count;
+ }
+
+ }
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : array = tableau compressé à mettre à jour. [OUT] *
+* item = adresse de l'élément à rajouter. *
+* size = taille de ce nouvel élément. *
+* *
+* Description : Ajoute un élément supplémentaire à un tableau. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void add_item_to_flat_array(flat_array_t **array, void *item, size_t size)
+{
+ ext_flat_array_t *extended; /* Version de tableau étendue */
+
+ assert(FLAT_ARRAY_IS_LOCKED(*array));
+
+ if (FLAT_ARRAY_IS_EMPTY(*array))
+ {
+ *array = malloc(size);
+ memcpy(*array, item, size);
+
+ lock_flat_array(array);
+
+ }
+
+ else
+ {
+ if (FLAT_ARRAY_HAS_NO_INDEX(*array))
+ {
+ extended = (ext_flat_array_t *)malloc(sizeof(ext_flat_array_t));
+
+ extended->items = malloc(2 * size);
+ extended->count = 2;
+
+ memcpy(extended->items, GET_LONELY_ITEM(*array), size);
+ memcpy(((char *)extended->items) + size, item, size);
+
+ FLAT_ARRAY_SET_INDEX(extended);
+
+ *array = (flat_array_t *)extended;
+
+ lock_flat_array(array);
+
+ }
+
+ else
+ {
+ extended = EXTENDED_ARRAY(*array);
+
+ extended->count++;
+ extended->items = realloc(extended->items, extended->count * size);
+
+ memcpy(((char *)extended->items) + (extended->count - 1) * size, item, size);
+
+ }
+
+ }
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : array = tableau compressé à mettre à jour. *
+* index = indice de l'élément à remplacer. *
+* new = adresse de l'élément à rajouter. *
+* size = taille de ce nouvel élément. *
+* *
+* Description : Remplace un élément d'un tableau compressé par un autre. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void rpl_item_in_flat_array(flat_array_t *array, size_t index, void *new, size_t size)
+{
+ ext_flat_array_t *extended; /* Version de tableau étendue */
+
+ assert(FLAT_ARRAY_IS_LOCKED(array));
+
+ assert(!FLAT_ARRAY_IS_EMPTY(array));
+
+ if (FLAT_ARRAY_HAS_NO_INDEX(array))
+ {
+ assert(index == 0);
+
+ memcpy(GET_LONELY_ITEM(array), new, size);
+
+ }
+
+ else
+ {
+ extended = EXTENDED_ARRAY(array);
+
+ assert(index < extended->count);
+
+ memcpy(((char *)extended->items) + index * size, new, size);
+
+ }
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : array = tableau compressé à mettre à jour. [OUT] *
+* index = indice de l'élément à retirer. *
+* size = taille de ce nouvel élément. *
+* *
+* Description : Retire un élément existant d'un tableau. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void rem_item_from_flat_array(flat_array_t **array, size_t index, size_t size)
+{
+ size_t count; /* Nombre d'éléments présents */
+ ext_flat_array_t *extended; /* Version de tableau étendue */
+ void *new; /* Nouveau tableau à jour */
+
+ assert(FLAT_ARRAY_IS_LOCKED(*array));
+
+ count = count_flat_array_items(*array);
+
+ switch (count)
+ {
+ case 0:
+ assert(false);
+ break;
+
+ case 1:
+
+ assert(FLAT_ARRAY_HAS_NO_INDEX(*array));
+ assert(index == 0);
+
+ free(GET_LONELY_ITEM(*array));
+
+ *array = NULL;
+
+ lock_flat_array(array);
+
+ break;
+
+ case 2:
+
+ assert(!FLAT_ARRAY_HAS_NO_INDEX(*array));
+ assert(index == 0 || index == 1);
+
+ extended = EXTENDED_ARRAY(*array);
+
+ new = malloc(size);
+
+ if (index == 1)
+ memcpy(new, extended->items, size);
+ else
+ memcpy(new, ((char *)extended->items) + size, size);
+
+ free(extended);
+
+ *array = new;
+
+ lock_flat_array(array);
+
+ break;
+
+ default:
+
+ assert(!FLAT_ARRAY_HAS_NO_INDEX(*array));
+ assert(index < count);
+
+ extended = EXTENDED_ARRAY(*array);
+
+ if ((count - index - 1) > 0)
+ memmove(((char *)extended->items) + index * size,
+ ((char *)extended->items) + (index + 1) * size,
+ (count - index - 1) * size);
+
+ extended->count--;
+ extended->items = realloc(extended->items, extended->count * size);
+
+ break;
+
+ }
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : array = tableau compressé à consulter. *
+* index = indice de l'élément à retrouver *
+* size = taille de ce nouvel élément. *
+* *
+* Description : Fournit un élément présent dans un tableau compressé. *
+* *
+* Retour : Elément du tableau visé par la procédure. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void *get_flat_array_item(flat_array_t *array, size_t index, size_t size)
+{
+ void *result; /* Trouvaille à retourner */
+ ext_flat_array_t *extended; /* Version de tableau étendue */
+
+ assert(FLAT_ARRAY_IS_LOCKED(array));
+
+ assert(!FLAT_ARRAY_IS_EMPTY(array));
+
+ if (FLAT_ARRAY_HAS_NO_INDEX(array))
+ {
+ assert(index == 0);
+
+ result = GET_LONELY_ITEM(array);
+
+ }
+
+ else
+ {
+ extended = EXTENDED_ARRAY(array);
+
+ assert(index < extended->count);
+
+ result = (void *)(((char *)extended->items) + index * size);
+
+ }
+
+ return result;
+
+}
generated by cgit v0.11.2-87-g4458 at 2024-05-01 22:46:51 (GMT)