From c0b4029475158f16f683e4c46a86b28f7a146a1c Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Tue, 7 Mar 2017 21:52:48 +0100 Subject: Created arrays with low memory footprint. --- ChangeLog | 18 ++ plugins/pychrysa/arch/instruction.c | 99 ++++++-- src/arch/instruction-int.h | 5 +- src/arch/instruction.c | 91 +++++--- src/arch/instruction.h | 2 +- src/arch/raw.c | 31 ++- src/common/Makefile.am | 1 + src/common/array.c | 434 ++++++++++++++++++++++++++++++++++++ src/common/array.h | 59 +++++ 9 files changed, 675 insertions(+), 65 deletions(-) create mode 100644 src/common/array.c create mode 100644 src/common/array.h diff --git a/ChangeLog b/ChangeLog index 1fd61f8..6fcb38a 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,21 @@ +17-03-07 Cyrille Bagard + + * plugins/pychrysa/arch/instruction.c: + Update the Python API. + + * src/arch/instruction-int.h: + * src/arch/instruction.c: + * src/arch/instruction.h: + * src/arch/raw.c: + Update code. + + * src/common/Makefile.am: + Add the 'array.[ch]' files to libcommon_la_SOURCES. + + * src/common/array.c: + * src/common/array.h: + New entries: create arrays with low memory footprint. + 17-03-06 Cyrille Bagard * plugins/androhelpers/params.c: diff --git a/plugins/pychrysa/arch/instruction.c b/plugins/pychrysa/arch/instruction.c index 8ebdef0..67e3a6b 100644 --- a/plugins/pychrysa/arch/instruction.c +++ b/plugins/pychrysa/arch/instruction.c @@ -61,6 +61,9 @@ static PyObject *py_arch_instruction_get_keyword(PyObject *, void *); +/* Fournit tous les opérandes d'une instruction. */ +static PyObject *py_arch_instruction_get_operands(PyObject *, void *); + @@ -78,18 +81,18 @@ static PyObject *py_arch_instruction_get_keyword(PyObject *, void *); /* Fournit les origines d'une instruction donnée. */ -static PyObject *py_arch_instruction_get_sources(PyObject *, PyObject *); +static PyObject *py_arch_instruction_get_sources(PyObject *, void *); /* Fournit les destinations d'une instruction donnée. */ -static PyObject *py_arch_instruction_get_destinations(PyObject *, PyObject *); +static PyObject *py_arch_instruction_get_destinations(PyObject *, void *); /****************************************************************************** * * -* Paramètres : self = instruction d'architecture à manipuler. * -* args = liste d'arguments non utilisée ici. * +* Paramètres : self = instruction d'architecture à manipuler. * +* unused = adresse non utilisée ici. * * * * Description : Fournit les origines d'une instruction donnée. * * * @@ -99,7 +102,7 @@ static PyObject *py_arch_instruction_get_destinations(PyObject *, PyObject *); * * ******************************************************************************/ -static PyObject *py_arch_instruction_get_sources(PyObject *self, PyObject *args) +static PyObject *py_arch_instruction_get_sources(PyObject *self, void *unused) { PyObject *result; /* Instance à retourner */ GArchInstruction *instr; /* Version native */ @@ -112,6 +115,8 @@ static PyObject *py_arch_instruction_get_sources(PyObject *self, PyObject *args) instr = G_ARCH_INSTRUCTION(pygobject_get(self)); + g_arch_instruction_rlock_src(instr); + count = g_arch_instruction_get_sources(instr, &sources); result = PyTuple_New(count); @@ -126,6 +131,8 @@ static PyObject *py_arch_instruction_get_sources(PyObject *self, PyObject *args) } + g_arch_instruction_runlock_src(instr); + return result; } @@ -133,8 +140,8 @@ static PyObject *py_arch_instruction_get_sources(PyObject *self, PyObject *args) /****************************************************************************** * * -* Paramètres : self = instruction d'architecture à manipuler. * -* args = liste d'arguments non utilisée ici. * +* Paramètres : self = instruction d'architecture à manipuler. * +* unused = adresse non utilisée ici. * * * * Description : Fournit les destinations d'une instruction donnée. * * * @@ -144,7 +151,7 @@ static PyObject *py_arch_instruction_get_sources(PyObject *self, PyObject *args) * * ******************************************************************************/ -static PyObject *py_arch_instruction_get_destinations(PyObject *self, PyObject *args) +static PyObject *py_arch_instruction_get_destinations(PyObject *self, void *unused) { PyObject *result; /* Instance à retourner */ GArchInstruction *instr; /* Version native */ @@ -157,6 +164,8 @@ static PyObject *py_arch_instruction_get_destinations(PyObject *self, PyObject * instr = G_ARCH_INSTRUCTION(pygobject_get(self)); + g_arch_instruction_rlock_dest(instr); + count = g_arch_instruction_get_destinations(instr, &dests); result = PyTuple_New(count); @@ -171,6 +180,8 @@ static PyObject *py_arch_instruction_get_destinations(PyObject *self, PyObject * } + g_arch_instruction_runlock_dest(instr); + return result; } @@ -284,6 +295,58 @@ static PyObject *py_arch_instruction_get_keyword(PyObject *self, void *unused) +/****************************************************************************** +* * +* Paramètres : self = objet représentant une instruction. * +* unused = adresse non utilisée ici. * +* * +* Description : Fournit tous les opérandes d'une instruction. * +* * +* Retour : Valeur associée à la propriété consultée. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static PyObject *py_arch_instruction_get_operands(PyObject *self, void *unused) +{ + PyObject *result; /* Instance à retourner */ + GArchInstruction *instr; /* Version native */ + size_t count; /* Nombre d'opérandes présents */ + size_t i; /* Boucle de parcours */ + GArchOperand *operand; /* Opérande à manipuler */ + PyObject *opobj; /* Version Python */ + int ret; /* Bilan d'une écriture d'arg. */ + + instr = G_ARCH_INSTRUCTION(pygobject_get(self)); + + g_arch_instruction_lock_operands(instr); + + count = _g_arch_instruction_count_operands(instr); + + result = PyTuple_New(count); + + for (i = 0; i < count; i++) + { + operand = _g_arch_instruction_get_operand(instr, i); + + opobj = pygobject_new(G_OBJECT(operand)); + + ret = PyTuple_SetItem(result, i, Py_BuildValue("O", opobj)); + assert(ret == 0); + + } + + g_arch_instruction_unlock_operands(instr); + + return result; + +} + + + + + @@ -308,14 +371,6 @@ static PyObject *py_arch_instruction_get_keyword(PyObject *self, void *unused) PyTypeObject *get_python_arch_instruction_type(void) { static PyMethodDef py_arch_instruction_methods[] = { - { "get_sources", py_arch_instruction_get_sources, - METH_NOARGS, - "get_sources(, /)\n--\n\nProvide the instructions list driving to the current instruction." - }, - { "get_destinations", py_arch_instruction_get_destinations, - METH_NOARGS, - "get_destinations(, /)\n--\n\nProvide the instructions list following the current instruction." - }, { NULL } }; @@ -328,6 +383,18 @@ PyTypeObject *get_python_arch_instruction_type(void) "keyword", (getter)py_arch_instruction_get_keyword, (setter)NULL, "Give le name of the assembly instruction.", NULL }, + { + "operands", (getter)py_arch_instruction_get_operands, (setter)NULL, + "Provide the list of instruction attached operands.", NULL + }, + { + "sources", (getter)py_arch_instruction_get_sources, (setter)NULL, + "Provide the instructions list driving to the current instruction." + }, + { + "destinations", (getter)py_arch_instruction_get_destinations, (setter)NULL, + "Provide the instructions list following the current instruction." + }, { NULL } }; diff --git a/src/arch/instruction-int.h b/src/arch/instruction-int.h index 8dbdd18..beb6b50 100644 --- a/src/arch/instruction-int.h +++ b/src/arch/instruction-int.h @@ -27,6 +27,7 @@ #include "archbase.h" #include "instruction.h" +#include "../common/array.h" @@ -54,9 +55,7 @@ struct _GArchInstruction const GBinContent *content; /* Contenu binaire global */ mrange_t range; /* Emplacement en mémoire */ - GArchOperand **operands; /* Liste des opérandes */ - size_t operands_count; /* Nbre. d'opérandes utilisées */ - gint operands_lock; /* Verrouillage des accès */ + flat_array_t *operands; /* Liste des opérandes */ /** * Il existe le besoin indéniable d'un verrou pour les accès aux instructions diff --git a/src/arch/instruction.c b/src/arch/instruction.c index 339364f..a86509c 100644 --- a/src/arch/instruction.c +++ b/src/arch/instruction.c @@ -145,7 +145,7 @@ static void g_arch_instruction_class_init(GArchInstructionClass *klass) static void g_arch_instruction_init(GArchInstruction *instr) { - instr->operands_lock = 0; + instr->operands = NULL; instr->from_count = 0; instr->to_count = 0; @@ -472,7 +472,7 @@ void g_arch_instruction_get_rw_registers(const GArchInstruction *instr, GArchReg void g_arch_instruction_lock_operands(GArchInstruction *instr) { - g_bit_lock(&instr->operands_lock, 0); + lock_flat_array(&instr->operands); } @@ -491,7 +491,7 @@ void g_arch_instruction_lock_operands(GArchInstruction *instr) void g_arch_instruction_unlock_operands(GArchInstruction *instr) { - g_bit_unlock(&instr->operands_lock, 0); + unlock_flat_array(&instr->operands); } @@ -513,10 +513,7 @@ void g_arch_instruction_attach_extra_operand(GArchInstruction *instr, GArchOpera { g_arch_instruction_lock_operands(instr); - instr->operands_count++; - instr->operands = (GArchOperand **)realloc(instr->operands, instr->operands_count * sizeof(GArchOperand *)); - - instr->operands[instr->operands_count - 1] = operand; + add_item_to_flat_array(&instr->operands, &operand, sizeof(GArchOperand *)); g_arch_instruction_unlock_operands(instr); @@ -537,9 +534,11 @@ void g_arch_instruction_attach_extra_operand(GArchInstruction *instr, GArchOpera size_t _g_arch_instruction_count_operands(const GArchInstruction *instr) { - assert(instr->operands_lock != 0); + size_t result; /* Décompte à retourner */ + + result = count_flat_array_items(instr->operands); - return instr->operands_count; + return result; } @@ -560,11 +559,11 @@ size_t _g_arch_instruction_count_operands(const GArchInstruction *instr) GArchOperand *_g_arch_instruction_get_operand(const GArchInstruction *instr, size_t index) { GArchOperand *result; /* Opérande à retourner */ + GArchOperand **ptr; /* Adresse dans le tableau */ - assert(instr->operands_lock != 0); + ptr = get_flat_array_item(instr->operands, index, sizeof(GArchOperand *)); - if (index >= instr->operands_count) result = NULL; - else result = instr->operands[index]; + result = *ptr; /* TODO : incrémenter la référence ! */ @@ -587,29 +586,34 @@ GArchOperand *_g_arch_instruction_get_operand(const GArchInstruction *instr, siz * * ******************************************************************************/ -void _g_arch_instruction_replace_operand(GArchInstruction *instr, GArchOperand *new, const GArchOperand *old) +void _g_arch_instruction_replace_operand(GArchInstruction *instr, GArchOperand *new, GArchOperand *old) { + size_t count; /* Nombre d'opérandes en place */ size_t i; /* Boucle de parcours */ + GArchOperand *op; /* Opérande à manipuler */ - assert(instr->operands_lock != 0); + count = _g_arch_instruction_count_operands(instr); + + for (i = 0; i < count; i++) + { + op = _g_arch_instruction_get_operand(instr, i); - for (i = 0; i < instr->operands_count; i++) - if (instr->operands[i] == old) + if (op == old) break; - if (i < instr->operands_count) - { - g_object_unref(G_OBJECT(instr->operands[i])); - instr->operands[i] = new; } + rpl_item_in_flat_array(instr->operands, i, &new, sizeof(GArchOperand *)); + + g_object_unref(G_OBJECT(old)); + } /****************************************************************************** * * -* Paramètres : instr = instance à mettre à jour. * -* opererand = instruction à venir dissocier. * +* Paramètres : instr = instance à mettre à jour. * +* target = instruction à venir dissocier. * * * * Description : Détache un opérande liée d'une instruction. * * * @@ -619,22 +623,26 @@ void _g_arch_instruction_replace_operand(GArchInstruction *instr, GArchOperand * * * ******************************************************************************/ -void _g_arch_instruction_detach_operand(GArchInstruction *instr, GArchOperand *operand) +void _g_arch_instruction_detach_operand(GArchInstruction *instr, GArchOperand *target) { + size_t count; /* Nombre d'opérandes en place */ size_t i; /* Boucle de parcours */ + GArchOperand *op; /* Opérande à manipuler */ + + count = _g_arch_instruction_count_operands(instr); - assert(instr->operands_lock != 0); + for (i = 0; i < count; i++) + { + op = _g_arch_instruction_get_operand(instr, i); - for (i = 0; i < instr->operands_count; i++) - if (instr->operands[i] == operand) + if (op == target) break; - if ((i + 1) < instr->operands_count) - memmove(&instr->operands[i], &instr->operands[i + 1], - (instr->operands_count - i - 1) * sizeof(GArchOperand *)); + } + + rem_item_from_flat_array(&instr->operands, i, sizeof(GArchOperand *)); - instr->operands_count--; - instr->operands = (GArchOperand **)realloc(instr->operands, instr->operands_count * sizeof(GArchOperand *)); + g_object_unref(G_OBJECT(target)); } @@ -1178,7 +1186,9 @@ static void _g_arch_instruction_print(GArchInstruction *instr, GBufferLine *line { const char *key; /* Mot clef principal */ size_t klen; /* Taille de ce mot clef */ + size_t count; /* Nombre d'opérandes en place */ size_t i; /* Boucle de parcours */ + GArchOperand *op; /* Opérande à manipuler */ g_buffer_line_fill_vmpa(line, get_mrange_addr(&instr->range), MDS_32_BITS_UNSIGNED, MDS_32_BITS_UNSIGNED); @@ -1191,21 +1201,32 @@ static void _g_arch_instruction_print(GArchInstruction *instr, GBufferLine *line g_buffer_line_append_text(line, BLC_ASSEMBLY_HEAD, key, klen, RTT_INSTRUCTION, NULL); - if (instr->operands_count > 0) + /* Liste des opérandes */ + + g_arch_instruction_lock_operands(instr); + + count = _g_arch_instruction_count_operands(instr); + + if (count > 0) { - g_arch_operand_print(instr->operands[0], line, 0/*syntax*/); + op = _g_arch_instruction_get_operand(instr, 0); + g_arch_operand_print(op, line, 0/*syntax*/); - for (i = 1; i < instr->operands_count; i++) + for (i = 1; i < count; i++) { g_buffer_line_append_text(line, BLC_ASSEMBLY, ",", 1, RTT_PUNCT, NULL); g_buffer_line_append_text(line, BLC_ASSEMBLY, " ", 1, RTT_RAW, NULL); - g_arch_operand_print(instr->operands[i], line, 0/*syntax*/); + op = _g_arch_instruction_get_operand(instr, i); + + g_arch_operand_print(op, line, 0/*syntax*/); } } + g_arch_instruction_unlock_operands(instr); + } diff --git a/src/arch/instruction.h b/src/arch/instruction.h index fad6c72..9299f8c 100644 --- a/src/arch/instruction.h +++ b/src/arch/instruction.h @@ -147,7 +147,7 @@ size_t _g_arch_instruction_count_operands(const GArchInstruction *); GArchOperand *_g_arch_instruction_get_operand(const GArchInstruction *, size_t); /* Remplace un opérande d'une instruction par un autre. */ -void _g_arch_instruction_replace_operand(GArchInstruction *, GArchOperand *, const GArchOperand *); +void _g_arch_instruction_replace_operand(GArchInstruction *, GArchOperand *, GArchOperand *); /* Détache un opérande liée d'une instruction. */ void _g_arch_instruction_detach_operand(GArchInstruction *, GArchOperand *); diff --git a/src/arch/raw.c b/src/arch/raw.c index f22645f..9d9b8de 100644 --- a/src/arch/raw.c +++ b/src/arch/raw.c @@ -464,10 +464,12 @@ static void g_raw_instruction_print(GRawInstruction *instr, GBufferLine *line, s phys_t max_displayed_len; /* Quantité de code affichée */ const char *key; /* Mot clef principal */ size_t klen; /* Taille de ce mot clef */ + size_t count; /* Nombre d'opérandes en place */ char *string; /* Chaîne reconstituée */ size_t iter; /* Tête d'écriture */ bool first; /* Mémorise une énumération */ size_t i; /* Boucle de parcours */ + GArchOperand *op; /* Opérande à manipuler */ char byte; /* Octet à afficher (ou pas) */ bool status; /* Bilan d'une récupération */ @@ -505,18 +507,22 @@ static void g_raw_instruction_print(GRawInstruction *instr, GBufferLine *line, s else if (instr->is_string) { - string = (char *)calloc(base->operands_count + 3, sizeof(char)); + g_arch_instruction_lock_operands(base); + + count = _g_arch_instruction_count_operands(base); + + string = (char *)calloc(count + 3, sizeof(char)); strcpy(string, "\""); iter = 1; first = true; - g_arch_instruction_lock_operands(base); - - for (i = 0; i < base->operands_count; i++) + for (i = 0; i < count; i++) { - status = g_imm_operand_get_value(G_IMM_OPERAND(base->operands[i]), MDS_8_BITS, &byte); + op = _g_arch_instruction_get_operand(base, i); + + status = g_imm_operand_get_value(G_IMM_OPERAND(op), MDS_8_BITS, &byte); assert(status); /* Si le caractère doit apparaître en hexadécimal... */ @@ -551,7 +557,7 @@ static void g_raw_instruction_print(GRawInstruction *instr, GBufferLine *line, s else first = false; - g_arch_operand_print(base->operands[i], line, 0/*, syntax*/); + g_arch_operand_print(op, line, 0/*, syntax*/); } @@ -587,16 +593,21 @@ static void g_raw_instruction_print(GRawInstruction *instr, GBufferLine *line, s { g_arch_instruction_lock_operands(base); - if (base->operands_count > 0) + count = _g_arch_instruction_count_operands(base); + + if (count > 0) { - g_arch_operand_print(base->operands[0], line, 0/*syntax*/); + op = _g_arch_instruction_get_operand(base, 0); + g_arch_operand_print(op, line, 0/*syntax*/); - for (i = 1; i < base->operands_count; i++) + for (i = 1; i < count; i++) { g_buffer_line_append_text(line, BLC_ASSEMBLY, ",", 1, RTT_PUNCT, NULL); g_buffer_line_append_text(line, BLC_ASSEMBLY, " ", 1, RTT_RAW, NULL); - g_arch_operand_print(base->operands[i], line, 0/*syntax*/); + op = _g_arch_instruction_get_operand(base, i); + + g_arch_operand_print(op, line, 0/*syntax*/); } diff --git a/src/common/Makefile.am b/src/common/Makefile.am index b4d1a5b..94faa59 100755 --- a/src/common/Makefile.am +++ b/src/common/Makefile.am @@ -2,6 +2,7 @@ lib_LTLIBRARIES = libcommon.la libcommon_la_SOURCES = \ + array.h array.c \ asm.h asm.c \ bconst.h \ bits.h bits.c \ 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 . + */ + + +#include "array.h" + + +#include +#include +#include +#include +#ifndef NDEBUG +# include +#endif +#include + + + +/** + * 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; + +} diff --git a/src/common/array.h b/src/common/array.h new file mode 100644 index 0000000..33558ee --- /dev/null +++ b/src/common/array.h @@ -0,0 +1,59 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * array.h - prototypes pour la 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 . + */ + + +#ifndef _COMMON_ARRAY_H +#define _COMMON_ARRAY_H + + +#include + + + +/* Type déclaratif de tableau compressé, à 0 ou 1 élément */ +typedef void *flat_array_t; + + +/* Verrouille l'accès à un tableau compressé. */ +void lock_flat_array(flat_array_t **); + +/* Déverrouille l'accès à un tableau compressé. */ +void unlock_flat_array(flat_array_t **); + +/* Indique la quantité d'éléments présents dans le tableau. */ +size_t count_flat_array_items(const flat_array_t *); + +/* Ajoute un élément supplémentaire à un tableau. */ +void add_item_to_flat_array(flat_array_t **, void *, size_t); + +/* Remplace un élément d'un tableau compressé par un autre. */ +void rpl_item_in_flat_array(flat_array_t *, size_t, void *, size_t); + +/* Retire un élément existant d'un tableau. */ +void rem_item_from_flat_array(flat_array_t **, size_t, size_t); + +/* Fournit un élément présent dans un tableau compressé. */ +void *get_flat_array_item(flat_array_t *, size_t, size_t); + + + +#endif /* _COMMON_ARRAY_H */ -- cgit v0.11.2-87-g4458