diff options
Diffstat (limited to 'src/common')
| -rw-r--r-- | src/common/Makefile.am | 24 | ||||
| -rw-r--r-- | src/common/bits.c | 649 | ||||
| -rw-r--r-- | src/common/bits.h | 31 | ||||
| -rw-r--r-- | src/common/cpp.h | 2 | ||||
| -rw-r--r-- | src/common/cpu.c | 100 | ||||
| -rw-r--r-- | src/common/cpu.h | 50 | ||||
| -rw-r--r-- | src/common/dllist.c | 195 | ||||
| -rw-r--r-- | src/common/dllist.h | 34 | ||||
| -rw-r--r-- | src/common/extstr.c | 147 | ||||
| -rw-r--r-- | src/common/extstr.h | 9 | ||||
| -rw-r--r-- | src/common/itoa.c | 135 | ||||
| -rw-r--r-- | src/common/itoa.h | 34 | ||||
| -rw-r--r-- | src/common/sort.c | 147 | ||||
| -rw-r--r-- | src/common/sort.h | 12 | ||||
| -rw-r--r-- | src/common/szstr.h | 112 |
15 files changed, 1659 insertions, 22 deletions
diff --git a/src/common/Makefile.am b/src/common/Makefile.am index 28e5459..1a8f8c4 100644 --- a/src/common/Makefile.am +++ b/src/common/Makefile.am @@ -9,7 +9,7 @@ libcommon_la_SOURCES = \ bits.h bits.c \ compression.h compression.c \ cpp.h \ - curl.h curl.c \ + cpu.h cpu.c \ dllist.h dllist.c \ endianness.h endianness.c \ environment.h environment.c \ @@ -17,6 +17,7 @@ libcommon_la_SOURCES = \ hex.h hex.c \ ibuf.h ibuf.c \ io.h io.c \ + itoa.h itoa.c \ fnv1a.h fnv1a.c \ leb128.h leb128.c \ macros.h \ @@ -27,20 +28,29 @@ libcommon_la_SOURCES = \ shuffle.h shuffle.c \ sort.h sort.c \ sqlite.h sqlite.c \ + szstr.h \ utf8.h utf8.c \ xdg.h xdg.c \ xml.h xml.c -libcommon_la_LDFLAGS = $(LIBGTK_LIBS) $(LIBXML_LIBS) $(LIBCURL_LIBS) +if BUILD_CURL_SUPPORT +libcommon_la_SOURCES += \ + curl.h curl.c -devdir = $(includedir)/chrysalide/$(subdir:src/%=core/%) +endif -dev_HEADERS = $(libcommon_la_SOURCES:%c=) +cpu.lo: CFLAGS += -mavx512f + +libcommon_la_CFLAGS = $(TOOLKIT_CFLAGS) $(LIBXML_CFLAGS) + +if BUILD_CURL_SUPPORT +libcommon_la_CFLAGS += $(LIBCURL_CFLAGS) -AM_CPPFLAGS = $(LIBGTK_CFLAGS) $(LIBXML_CFLAGS) $(LIBCURL_CFLAGS) +endif -AM_CFLAGS = $(DEBUG_CFLAGS) $(WARNING_FLAGS) $(COMPLIANCE_FLAGS) -SUBDIRS = +devdir = $(includedir)/chrysalide/$(subdir:src/%=core/%) + +dev_HEADERS = $(libcommon_la_SOURCES:%c=) diff --git a/src/common/bits.c b/src/common/bits.c index a450bb2..3d0004c 100644 --- a/src/common/bits.c +++ b/src/common/bits.c @@ -38,19 +38,30 @@ struct _bitfield_t { size_t length; /* Nombre de bits représentés */ - size_t requested; /* Nombre de mots alloués */ + + size_t allocated_words; /* Nombre de mots alloués */ + size_t used_words; /* Nombre de mots utilisés */ + + bool default_state; /* Etat d'initialisation */ unsigned long bits[0]; /* Mémoire d'accès associée */ }; +/* Taille des mots intégrés */ +#define BF_WORD_SIZE (sizeof(unsigned long) * 8) + + /* Crée un champ de bits initialisé à zéro. */ static bitfield_t *_create_bit_field(size_t); /* Détermine si un ensemble de bits est homogène dans un champ. */ static bool test_state_in_bit_field(const bitfield_t *, size_t, size_t, bool); +/* Teste l'état de bits selon un masque de bits. */ +static bool test_state_within_bit_field(const bitfield_t *, size_t, const bitfield_t *, bool); + /****************************************************************************** @@ -68,18 +79,20 @@ static bool test_state_in_bit_field(const bitfield_t *, size_t, size_t, bool); static bitfield_t *_create_bit_field(size_t length) { bitfield_t *result; /* Création à retourner */ - size_t requested; /* Nombre de mots à allouer */ + size_t needed; /* Nombre de mots à allouer */ size_t base; /* Allocation de base en octets*/ - requested = length / (sizeof(unsigned long) * 8); - if (length % (sizeof(unsigned long) * 8) != 0) requested++; + needed = length / (sizeof(unsigned long) * 8); + if (length % (sizeof(unsigned long) * 8) != 0) needed++; - base = sizeof(bitfield_t) + requested * sizeof(unsigned long); + base = sizeof(bitfield_t) + needed * sizeof(unsigned long); result = (bitfield_t *)malloc(base); result->length = length; - result->requested = requested; + + result->allocated_words = needed; + result->used_words = needed; return result; @@ -105,6 +118,8 @@ bitfield_t *create_bit_field(size_t length, bool state) result = _create_bit_field(length); + result->default_state = state; + if (state) set_all_in_bit_field(result); else @@ -133,7 +148,7 @@ bitfield_t *dup_bit_field(const bitfield_t *field) result = _create_bit_field(field->length); - memcpy(result->bits, field->bits, result->requested * sizeof(unsigned long)); + memcpy(result->bits, field->bits, result->used_words * sizeof(unsigned long)); return result; @@ -176,7 +191,124 @@ void copy_bit_field(bitfield_t *dest, const bitfield_t *src) { assert(dest->length == src->length); - memcpy(dest->bits, src->bits, dest->requested * sizeof(unsigned long)); + memcpy(dest->bits, src->bits, dest->used_words * sizeof(unsigned long)); + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à modifier. [OUT] * +* length = nouveau nombre de bits du champ à représenter. * +* * +* Description : Réduit ou étend la taille d'un champ en évitant l'allocation.* +* * +* Retour : - * +* * +* Remarques : Les éventuels bits supplémentaires ou disparus ne sont pas * +* (ré)initialisés. * +* * +******************************************************************************/ + +void truncate_bit_field(bitfield_t **field, size_t length) +{ + bitfield_t *_field; /* Commodité d'accès */ + size_t needed; /* Nombre de mots à allouer */ + + _field = *field; + + needed = length / (sizeof(unsigned long) * 8); + if (length % (sizeof(unsigned long) * 8) != 0) needed++; + + if (needed <= _field->allocated_words) + { + _field->length = length; + + _field->used_words = needed; + + } + + else + resize_bit_field(field, length); + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à modifier. [OUT] * +* length = nouveau nombre de bits du champ à représenter. * +* * +* Description : Redimensionne un champ de bits. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void resize_bit_field(bitfield_t **field, size_t length) +{ + bitfield_t *_field; /* Commodité d'accès */ + size_t needed; /* Nombre de mots à allouer */ + size_t base; /* Allocation de base en octets*/ + size_t remaining; /* Nombre de derniers bits */ + size_t last; /* Dernier mot utilisé */ + unsigned long mask; /* Masque d'initialisation */ + size_t i; /* Boucle de parcours */ + + _field = *field; + + if (_field->length != length) + { + /* Redimensionnement */ + + needed = length / (sizeof(unsigned long) * 8); + if (length % (sizeof(unsigned long) * 8) != 0) needed++; + + base = sizeof(bitfield_t) + needed * sizeof(unsigned long); + + /* Initialisation, si nécessaire */ + + if (_field->length < length) + { + *field = realloc(_field, base); + _field = *field; + + last = _field->length / (sizeof(unsigned long) * 8); + remaining = _field->length % (sizeof(unsigned long) * 8); + + if (remaining != 0) + { + mask = (1ul << remaining) - 1; + + if (_field->default_state) + _field->bits[last] |= ~mask; + else + _field->bits[last] &= mask; + + last++; + + } + + for (i = last; i < needed; i++) + { + if (_field->default_state) + _field->bits[i] = ~0ul; + else + _field->bits[i] = 0ul; + } + + } + + /* Actualisation des tailles */ + + _field->length = length; + + _field->allocated_words = needed; + _field->used_words = needed; + + } } @@ -242,12 +374,12 @@ int compare_bit_fields(const bitfield_t *a, const bitfield_t *b) else final = (1 << final) - 1; - for (i = 0; i < a->requested && result == 0; i++) + for (i = 0; i < a->used_words && result == 0; i++) { val_a = a->bits[i]; val_b = b->bits[i]; - if ((i + 1) == a->requested) + if ((i + 1) == a->used_words) { val_a &= final; val_b &= final; @@ -282,7 +414,7 @@ int compare_bit_fields(const bitfield_t *a, const bitfield_t *b) void reset_all_in_bit_field(bitfield_t *field) { - memset(field->bits, 0u, field->requested * sizeof(unsigned long)); + memset(field->bits, 0u, field->used_words * sizeof(unsigned long)); } @@ -301,7 +433,7 @@ void reset_all_in_bit_field(bitfield_t *field) void set_all_in_bit_field(bitfield_t *field) { - memset(field->bits, ~0u, field->requested * sizeof(unsigned long)); + memset(field->bits, ~0u, field->used_words * sizeof(unsigned long)); } @@ -399,7 +531,7 @@ void and_bit_field(bitfield_t *dest, const bitfield_t *src) assert(dest->length == src->length); - for (i = 0; i < dest->requested; i++) + for (i = 0; i < dest->used_words; i++) dest->bits[i] &= src->bits[i]; } @@ -424,7 +556,7 @@ void or_bit_field(bitfield_t *dest, const bitfield_t *src) assert(dest->length == src->length); - for (i = 0; i < dest->requested; i++) + for (i = 0; i < dest->used_words; i++) dest->bits[i] |= src->bits[i]; } @@ -432,6 +564,61 @@ void or_bit_field(bitfield_t *dest, const bitfield_t *src) /****************************************************************************** * * +* Paramètres : dest = champ de bits à modifier. * +* src = champ de bits à utiliser pour l'opération. * +* first = point de départ pour l'opération à réaliser. * +* * +* Description : Réalise une opération OU logique entre deux champs de bits. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void or_bit_field_at(bitfield_t *dest, const bitfield_t *src, size_t first) +{ + size_t start; /* Mot de départ dans le champ */ + size_t offset; /* Décalage des mots à basculer*/ + size_t remaining; /* Taille du dernier tronçon */ + size_t last_iter; /* Dernière itération à mener */ + size_t i; /* Boucle de parcours */ + unsigned long word; /* Mot reconstituté à tester */ + + assert((first + src->length) <= dest->length); + + start = first / (sizeof(unsigned long) * 8); + offset = first % (sizeof(unsigned long) * 8); + + remaining = (first + src->length) % (sizeof(unsigned long) * 8); + + if ((first + src->length) % (sizeof(unsigned long) * 8) > 0) + last_iter = src->used_words; + else + last_iter = src->used_words - 1; + + for (i = 0; i <= last_iter; i++) + { + if (i < src->used_words) + word = src->bits[i] << offset; + else + word = 0; + + if (i > 0 && offset > 0) + word |= src->bits[i - 1] >> (sizeof(unsigned long) * 8 - offset); + + if (i == last_iter && remaining > 0) + word &= (1ul << remaining) - 1; + + dest->bits[start + i] |= word; + + } + +} + + +/****************************************************************************** +* * * Paramètres : field = champ de bits à consulter. * * n = indice du bit à traiter. * * * @@ -463,6 +650,42 @@ bool test_in_bit_field(const bitfield_t *field, size_t n) /****************************************************************************** * * +* Paramètres : field = champ de bits à consulter. * +* n = indice du bit à traiter. * +* * +* Description : Détermine si un bit est à 1 dans un champ puis le définit. * +* * +* Retour : true si le bit correspondant était déjà à l'état haut. * +* * +* Remarques : - * +* * +******************************************************************************/ + +bool test_and_set_in_bit_field(bitfield_t *field, size_t n) +{ + bool result; /* Valeur retrouvée à renvoyer */ + size_t index; /* Cellule de tableau visée */ + size_t remaining; /* Nombre de bits restants */ + unsigned long *bits; /* Accès mis en commun */ + + assert(n < field->length); + + index = n / (sizeof(unsigned long) * 8); + remaining = n % (sizeof(unsigned long) * 8); + + bits = field->bits + index; + + result = *bits & (1ul << remaining); + + *bits |= (1ul << remaining); + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : field = champ de bits à modifier. * * first = indice du premier bit à traiter. * * count = nombre de bits à marquer. * @@ -556,6 +779,350 @@ bool test_all_in_bit_field(const bitfield_t *field, size_t first, size_t count) /****************************************************************************** * * +* Paramètres : field = champ de bits à modifier. * +* first = indice du premier bit à traiter. * +* mask = second champ de bits à tester logiquement. * +* state = état global à retrouver idéalement. * +* * +* Description : Teste l'état de bits selon un masque de bits. * +* * +* Retour : true si les bits visés sont tous à l'état indiqué. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static bool test_state_within_bit_field(const bitfield_t *field, size_t first, const bitfield_t *mask, bool state) +{ + bool result; /* Bilan à retourner */ + size_t start; /* Mot de départ dans le champ */ + size_t offset; /* Décalage des mots à testter */ + size_t remaining; /* Taille du dernier tronçon */ + unsigned long finalcut; /* Limitation du mot final */ + size_t i; /* Boucle de parcours */ + size_t windex; /* Indice du mot courant */ + unsigned long word; /* Mot reconstituté à tester */ + unsigned long bitmask; /* Masque à appliquer */ + unsigned long test; /* Valeur résultante du test */ + + result = true; + + assert((first + mask->length) <= field->length); + + start = first / (sizeof(unsigned long) * 8); + offset = first % (sizeof(unsigned long) * 8); + + remaining = mask->length % (sizeof(unsigned long) * 8); + + if (remaining == 0) + finalcut = ~0lu; + else + finalcut = (1lu << remaining) - 1; + + for (i = 0; i < mask->used_words && result; i++) + { + windex = start + i; + + if (offset == 0) + word = field->bits[windex]; + + else + { + word = field->bits[windex] >> offset; + if ((windex + 1) < field->used_words) + word |= field->bits[windex + 1] << (sizeof(unsigned long) * 8 - offset); + } + + bitmask = mask->bits[i]; + + test = word ^ bitmask; + + test &= bitmask; + + if ((i + 1) == mask->used_words) + { + bitmask &= finalcut; + test &= finalcut; + } + + result = (state ? test == 0 : test == bitmask); + + } + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à modifier. * +* first = indice du premier bit à traiter. * +* mask = second champ de bits à tester logiquement. * +* * +* Description : Teste l'état à 0 de bits selon un masque de bits. * +* * +* Retour : true si les bits visés sont à l'état bas. * +* * +* Remarques : - * +* * +******************************************************************************/ + +bool test_zeros_within_bit_field(const bitfield_t *field, size_t first, const bitfield_t *mask) +{ + bool result; /* Valeur retrouvée à renvoyer */ + + result = test_state_within_bit_field(field, first, mask, false); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à modifier. * +* first = indice du premier bit à traiter. * +* mask = second champ de bits à tester logiquement. * +* * +* Description : Teste l'état à 1 de bits selon un masque de bits. * +* * +* Retour : true si les bits visés sont à l'état haut. * +* * +* Remarques : - * +* * +******************************************************************************/ + +bool test_ones_within_bit_field(const bitfield_t *field, size_t first, const bitfield_t *mask) +{ + bool result; /* Valeur retrouvée à renvoyer */ + + result = test_state_within_bit_field(field, first, mask, true); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à consulter. * +* prev = indice rapporté avec une itération précédente. * +* * +* Description : Recherche un prochain bit défini dans un champ de bits. * +* * +* Retour : Position d'un bit à 1 ou taille du champ si plus aucun. * +* * +* Remarques : - * +* * +******************************************************************************/ + +size_t find_next_set_in_bit_field(const bitfield_t *field, const size_t *prev) +{ + size_t result; /* Indice à retourner */ + size_t i; /* Boucle de parcours */ + unsigned long word; /* Espace de travail courant */ + size_t last_pos; /* Position précédente locale */ + int found; /* Bian de recherche locale */ + + /* Travaux sur le premier mot, nécessitant potentiellement un masque */ + + if (prev == NULL) + { + i = 0; + word = field->bits[0]; + } + else + { + i = *prev / BF_WORD_SIZE; + + if (i >= field->used_words) + { + result = field->length; + goto nothing_to_do; + } + + word = field->bits[i]; + + last_pos = *prev % BF_WORD_SIZE; + + if ((last_pos + 1) == BF_WORD_SIZE) + goto next_word; + + word &= ~((1lu << (last_pos + 1)) - 1); + + } + + found = __builtin_ffsl(word); + + if (found > 0) + { + result = i * BF_WORD_SIZE + found - 1; + goto done; + } + + /* Extension aux autres mots suivantes au besoin */ + + next_word: + + result = field->length; + + for (i++; i < field->used_words; i++) + { + found = __builtin_ffsl(field->bits[i]); + + if (found > 0) + { + result = i * BF_WORD_SIZE + found - 1; + + /** + * Validation des bornes finales, pour le dernier mot. + */ + if (result > field->length) + result = field->length; + + goto done; + + } + + } + + /* Sortie */ + + done: + + nothing_to_do: + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à consulter. * +* extra = champ de bits à placer. * +* first = mémorisation d'un point de départ entre appels. [OUT]* +* * +* Description : Recherche l'indice idéal pour placer un champ dans un autre. * +* * +* Retour : Position du premier bit à insérer. * +* * +* Remarques : - * +* * +******************************************************************************/ + +size_t find_interleaving_index_for_acism(const bitfield_t *field, const bitfield_t *extra, size_t *first) +{ + size_t result; /* Dimension à retourner */ + size_t i; /* Boucle de parcours #1 */ + const unsigned long *bits; /* Itérateurs sur les bits */ + size_t init_k; /* Point de départ optimal */ + size_t k; /* Boucle de parcours #2 */ + unsigned long mask; /* Valeur à comparer */ + size_t j; /* Boucle de parcours #3 */ + + /** + * La procédure s'appuie sur deux particularité du contexte d'exécution (scan ACISM) : + * - il y a toujours au moins 257 bits (taille maximale du champs "extra") libres + * en fin de champs "field" ; + * - le premier bit du champ "extra" est toujours fixé à 1. + */ + + result = 0; + + for (i = *first; i < field->used_words; i++) + { + /* S'il ne reste plus aucune place */ + if (field->bits[i] != ~0lu) + break; + } + + *first = i; + + bits = field->bits + i; + + for (; i < field->used_words; i++, bits++) + { + /* S'il ne reste plus aucune place */ + if (*bits == ~0lu) + continue; + + init_k = __builtin_ffsl(~*bits) - 1; + + for (k = init_k; k < __WORDSIZE; k++) + { + /** + * Le champs de bits à placer ne comporte pas forcément au moins + * 32/64 bits, mais les bits non comptabilisés du mot sont toujours + * initialisés à zéro. + * + * Aucune prise en compte particulière d'un champ de petite taille + * n'est donc à réaliser ici. + */ + + mask = (extra->bits[0] << k); + + /* Si tous les bits nécessaires au début sont libres... */ + if ((*bits & mask) == 0) + { + for (j = 1; j < extra->used_words; j++) + { + if (k == 0) + mask = extra->bits[j]; + + else + { + /* Portion du mot courant */ + mask = (extra->bits[j] << k); + + /* Relicat du mot précédent */ + mask |= (extra->bits[j - 1] >> (__WORDSIZE - k)); + + } + + if (mask == 0) + continue; + + if ((bits[j] & mask) != 0) + break; + + } + + if (j == extra->used_words) + { + /* Eventuelle dernière bribe débordant sur un dernier mot ? */ + if (k > 0) + { + mask = (extra->bits[j - 1] >> (__WORDSIZE - k)); + + if ((bits[j] & mask) != 0) + continue; + + } + + result = i * __WORDSIZE + k; + goto found; + + } + + } + + } + + } + + found: + + assert(result > 0); + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : field = champ de bits à consulter. * * * * Description : Détermine le nombre de bits à 1 dans un champ. * @@ -577,7 +1144,7 @@ size_t popcount_for_bit_field(const bitfield_t *field) remaining = field->length; - for (i = 0; i < field->requested; i++) + for (i = 0; i < field->used_words; i++) { value = field->bits[i]; @@ -599,3 +1166,55 @@ size_t popcount_for_bit_field(const bitfield_t *field) return result; } + + +#if 0 + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à consulter. * +* * +* Description : Imprime sur la sortie standard la valeur représentée. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void output_bit_field(const bitfield_t *field) +{ + size_t i; /* Boucle de parcours #1 */ + unsigned long value; /* Valeur masquée à traiter */ + size_t k; /* Boucle de parcours #2 */ + + printf("[len=%zu] \n", field->length); + +#define MAX_BITS (sizeof(unsigned long) * 8) + + for (i = 0; i < field->used_words; i++) + { + value = field->bits[i]; + + if (i > 0) + printf("| "); + + for (k = 0; k < MAX_BITS; k++) + { + if ((i * MAX_BITS + k) >= field->length) + break; + + printf("%c", value & (1lu << k) ? '1' : '.'); + + if ((k + 1) % 8 == 0) + printf(" "); + + } + + } + + printf("\n"); + +} + +#endif diff --git a/src/common/bits.h b/src/common/bits.h index 96ea06a..608db39 100644 --- a/src/common/bits.h +++ b/src/common/bits.h @@ -45,6 +45,12 @@ void delete_bit_field(bitfield_t *); /* Copie un champ de bits dans un autre. */ void copy_bit_field(bitfield_t *, const bitfield_t *); +/* Réduit ou étend la taille d'un champ en évitant l'allocation. */ +void truncate_bit_field(bitfield_t **, size_t); + +/* Redimensionne un champ de bits. */ +void resize_bit_field(bitfield_t **, size_t); + /* Indique la taille d'un champ de bits donné. */ size_t get_bit_field_size(const bitfield_t *); @@ -69,18 +75,43 @@ void and_bit_field(bitfield_t *, const bitfield_t *); /* Réalise une opération OU logique entre deux champs de bits. */ void or_bit_field(bitfield_t *, const bitfield_t *); +/* Réalise une opération OU logique entre deux champs de bits. */ +void or_bit_field_at(bitfield_t *, const bitfield_t *, size_t); + /* Détermine si un bit est à 1 dans un champ de bits. */ bool test_in_bit_field(const bitfield_t *, size_t); +/* Détermine si un bit est à 1 dans un champ puis le définit. */ +bool test_and_set_in_bit_field(bitfield_t *, size_t); + /* Détermine si un ensemble de bits est à 0 dans un champ. */ bool test_none_in_bit_field(const bitfield_t *, size_t, size_t); /* Détermine si un ensemble de bits est à 1 dans un champ. */ bool test_all_in_bit_field(const bitfield_t *, size_t, size_t); +/* Teste l'état à 0 de bits selon un masque de bits. */ +bool test_zeros_within_bit_field(const bitfield_t *, size_t, const bitfield_t *); + +/* Teste l'état à 1 de bits selon un masque de bits. */ +bool test_ones_within_bit_field(const bitfield_t *, size_t, const bitfield_t *); + +/* Recherche un prochain bit défini dans un champ de bits. */ +size_t find_next_set_in_bit_field(const bitfield_t *, const size_t *); + +/* Recherche l'indice idéal pour placer un champ dans un autre. */ +size_t find_interleaving_index_for_acism(const bitfield_t *, const bitfield_t *, size_t *); + /* Détermine le nombre de bits à 1 dans un champ. */ size_t popcount_for_bit_field(const bitfield_t *); +#if 0 + +/* Imprime sur la sortie standard la valeur représentée. */ +void output_bit_field(const bitfield_t *); + +#endif + #endif /* _COMMON_BITS_H */ diff --git a/src/common/cpp.h b/src/common/cpp.h index b1606ed..39e7676 100644 --- a/src/common/cpp.h +++ b/src/common/cpp.h @@ -46,6 +46,8 @@ #define SIZE_T_MAXLEN strlen(XSTR(LONG_MAX)) +#define ULLONG_MAXLEN (sizeof(XSTR(ULLONG_MAX)) + 1) + /** * Emprunt au noyau Linux (cf. include/linux/bug.h) pour les vérifications à la compilation. diff --git a/src/common/cpu.c b/src/common/cpu.c new file mode 100644 index 0000000..968def5 --- /dev/null +++ b/src/common/cpu.c @@ -0,0 +1,100 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * cpu.c - obtention d'indications de fonctionnalités liées au CPU + * + * Copyright (C) 2022 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 Chrysalide. If not, see <http://www.gnu.org/licenses/>. + */ + + +#include "cpu.h" + + + +/****************************************************************************** +* * +* Paramètres : - * +* * +* Description : Indique les capacités de calculs parallèles anticipées. * +* * +* Retour : Fonctionnalités disponibles lors de la compilation. * +* * +* Remarques : - * +* * +******************************************************************************/ + +CPUSMIDFeature get_supported_cpu_smid_feature(void) +{ + CPUSMIDFeature result; /* Indications à retourner */ + + result = CSF_NONE; + + /** + * $ gcc -mavx512f -dM -E - < /dev/null | grep AVX + * #define __AVX512F__ 1 + * #define __AVX__ 1 + * #define __AVX2__ 1 + */ + +#ifdef __AVX2__ + result |= CSF_AVX2; +#endif + +#ifdef __AVX512F__ + result |= CSF_AVX512; +#endif + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : - * +* * +* Description : Indique les capacités de calculs parallèles sollicitables. * +* * +* Retour : Fonctionnalités disponibles dans l'environnement. * +* * +* Remarques : - * +* * +******************************************************************************/ + +CPUSMIDFeature get_avalaible_cpu_smid_feature(void) +{ + CPUSMIDFeature result; /* Indications à retourner */ + + result = CSF_NONE; + + /** + * Cf. Documentations suivantes : + * - https://www.intel.com/content/dam/develop/external/us/en/documents/how-to-detect-new-instruction-support-in-the-4th-generation-intel-core-processor-family.pdf + * - https://gcc.gnu.org/onlinedocs/gcc/x86-Built-in-Functions.html + */ + + __builtin_cpu_init(); + + if (__builtin_cpu_supports("ssse3")) + result |= CSF_AVX2; + + if (__builtin_cpu_supports("avx512f")) + result |= CSF_AVX512; + + return result; + +} diff --git a/src/common/cpu.h b/src/common/cpu.h new file mode 100644 index 0000000..58e53bd --- /dev/null +++ b/src/common/cpu.h @@ -0,0 +1,50 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * cpu.h - prototypes pour l'obtention d'indications de fonctionnalités liées au CPU + * + * Copyright (C) 2022 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 Chrysalide. If not, see <http://www.gnu.org/licenses/>. + */ + + +#ifndef _COMMON_CPU_H +#define _COMMON_CPU_H + + + +/* Indication de capacité de calculs parallèles */ +typedef enum _CPUSMIDFeature +{ + CSF_NONE = (0 << 0), /* Absence d'indication */ + + CSF_AVX2 = (1 << 0), /* Advanced Vector Extensions */ + CSF_AVX512 = (1 << 1), /* Advanced Vector Extensions */ + + CSF_ALL = ((1 << 2) - 1), + +} CPUSMIDFeature; + + +/* Indique les capacités de calculs parallèles anticipées. */ +CPUSMIDFeature get_supported_cpu_smid_feature(void); + +/* Indique les capacités de calculs parallèles sollicitables. */ +CPUSMIDFeature get_avalaible_cpu_smid_feature(void); + + + +#endif /* _COMMON_CPU_H */ diff --git a/src/common/dllist.c b/src/common/dllist.c index a953ad0..1ee7b0d 100644 --- a/src/common/dllist.c +++ b/src/common/dllist.c @@ -24,6 +24,17 @@ #include "dllist.h" +#include <assert.h> + + + +/* Découpe une liste en deux parties. */ +static void split_dl_lists(dl_list_head, dl_list_head *, dl_list_head *); + +/* Trie une liste chaînée en supprimant les éléments identiques. */ +static dl_list_head sort_and_merge_dl_lists_no_dup(dl_list_head *, dl_list_head *, size_t *, __dl_item_compar_fn_t, dl_list_head *); + + /****************************************************************************** * * @@ -79,3 +90,187 @@ void __dl_list_del(dl_list_item *item, dl_list_head *head) } } + + +/****************************************************************************** +* * +* Paramètres : list = liste à découper. * +* part1 = première partie constituée. [OUT] * +* part2 = seconde partie constituée. [OUT] * +* * +* Description : Découpe une liste en deux parties. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void split_dl_lists(dl_list_head list, dl_list_head *part1, dl_list_head *part2) +{ + dl_list_item *iter_slow; /* Boucle de parcours #1 */ + dl_list_item *iter_fast; /* Boucle de parcours #2 */ + + *part1 = list; + + iter_slow = list; + iter_fast = _dl_list_next(iter_slow, list); + + while (iter_fast != NULL) + { + iter_fast = _dl_list_next(iter_fast, list); + + if (iter_fast != NULL) + { + iter_slow = _dl_list_next(iter_slow, list); + iter_fast = _dl_list_next(iter_fast, list); + } + + } + + *part2 = _dl_list_next(iter_slow, list); + + /* Réalisation d'une coupure */ + + if (*part2 != NULL) + { + (*part2)->prev = (*part1)->prev; + (*part2)->prev->next = (*part2); + } + + iter_slow->next = *part1; + (*part1)->prev = iter_slow; + +} + + +/****************************************************************************** +* * +* Paramètres : head = tête de la liste à trier. * +* length = taille de la liste fournie. * +* compar = méthode de comparaison des éléments. * +* duplicated = liste des éléments présents en double. [OUT] * +* * +* Description : Trie une liste chaînée en supprimant les éléments identiques.* +* * +* Retour : Nouvelle liste obtenue. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static dl_list_head sort_and_merge_dl_lists_no_dup(dl_list_head *a, dl_list_head *b, size_t *length, __dl_item_compar_fn_t compar, dl_list_head *duplicated) +{ + dl_list_head result; /* Liste fusionnée à renvoyer */ + int ret; /* Bilan d'une comparaison */ + dl_list_head next; /* Maillons de liste suivants */ + + if (dl_list_empty(*a)) + result = *b; + + else if (dl_list_empty(*b)) + result = *a; + + else + { + ret = compar(*a, *b); + + if (ret < 0) + { + result = *a; + __dl_list_del(result, a); + DL_LIST_ITEM_INIT(result); + + next = sort_and_merge_dl_lists_no_dup(a, b, length, compar, duplicated); + assert(!dl_list_empty(next)); + _dl_list_merge(result, next); + + } + + else if (ret == 0) + { + result = *a; + __dl_list_del(result, a); + DL_LIST_ITEM_INIT(result); + + if (length != NULL) + (*length)--; + + if (duplicated != NULL) + { + /** + * L'élément est ici ajouté à la liste sans respect d'un ordre particulier. + */ + + if (dl_list_empty(*duplicated)) + *duplicated = result; + else + __dl_list_add(result, duplicated, (*duplicated)->prev, *duplicated); + + } + + result = *b; + __dl_list_del(result, b); + DL_LIST_ITEM_INIT(result); + + next = sort_and_merge_dl_lists_no_dup(a, b, length, compar, duplicated); + if (!dl_list_empty(next)) + _dl_list_merge(result, next); + + } + + else + { + result = *b; + __dl_list_del(result, b); + DL_LIST_ITEM_INIT(result); + + next = sort_and_merge_dl_lists_no_dup(a, b, length, compar, duplicated); + assert(!dl_list_empty(next)); + _dl_list_merge(result, next); + + } + + } + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : head = tête de la liste à trier. * +* length = taille de la liste fournie. * +* compar = méthode de comparaison des éléments. * +* duplicated = liste des éléments présents en double. [OUT] * +* * +* Description : Trie une liste chaînée en notant les éléments identiques. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void sort_dl_list_no_dup(dl_list_head *head, size_t *length, __dl_item_compar_fn_t compar, dl_list_head *duplicated) +{ + dl_list_head part1; /* Première moitiée à traiter */ + dl_list_head part2; /* Seconde moitiée à traiter */ + + /* S'il y a réellement quelque chose à faire */ + if (!dl_list_empty(*head) && !_dl_list_is_last(*head, *head)) + { + /* Découpage en deux sous-listes */ + split_dl_lists(*head, &part1, &part2); + + /* Tri des deux listes obtenues */ + sort_dl_list_no_dup(&part1, length, compar, duplicated); + sort_dl_list_no_dup(&part2, length, compar, duplicated); + + /* Fusion des deux listes triées */ + *head = sort_and_merge_dl_lists_no_dup(&part1, &part2, length, compar, duplicated); + + } + +} diff --git a/src/common/dllist.h b/src/common/dllist.h index 111843b..1fb010a 100644 --- a/src/common/dllist.h +++ b/src/common/dllist.h @@ -62,6 +62,12 @@ void __dl_list_del(dl_list_item *, dl_list_head *); #define dl_list_empty(head) \ ((head) == NULL) +#define _dl_list_is_last(item, head) \ + ((item)->next == head) + +#define dl_list_is_last(item, head, member) \ + item->member.next == &head->member + #define dl_list_last(head, type, member) \ (dl_list_empty(head) ? NULL : (type *)container_of(head->member.prev, type, member)) @@ -108,6 +114,17 @@ void __dl_list_del(dl_list_item *, dl_list_head *); } \ while(0) +#define _dl_list_merge(head1, head2) \ + do \ + { \ + dl_list_item *mid = head1->prev; \ + mid->next = head2; \ + head1->prev = head2->prev; \ + head2->prev->next = head1; \ + head2->prev = mid; \ + } \ + while(0) + #define dl_list_merge(head1, head2, type, member) \ do \ { \ @@ -134,6 +151,16 @@ void __dl_list_del(dl_list_item *, dl_list_head *); _result; \ }) +#define _dl_list_next(iter, head) \ + ({ \ + dl_list_item *__next; \ + __next = iter->next; \ + if (__next == head) \ + __next = NULL; \ + __next; \ + }) + + #define dl_list_next_iter(iter, head, type, member) \ (iter->member.next == &head->member ? \ NULL : container_of(iter->member.next, type, member)) @@ -164,5 +191,12 @@ void __dl_list_del(dl_list_item *, dl_list_head *); pos = dl_list_prev_iter(pos, (head), type, member)) +/* Prototype pour un comparateur d'éléments */ +typedef int (*__dl_item_compar_fn_t) (const dl_list_item *, const dl_list_item *); + +/* Trie une liste chaînée en notant les éléments identiques. */ +void sort_dl_list_no_dup(dl_list_head *, size_t *, __dl_item_compar_fn_t, dl_list_head *); + + #endif /* _COMMON_DLLIST_H */ diff --git a/src/common/extstr.c b/src/common/extstr.c index 9142bd9..ac93f5d 100644 --- a/src/common/extstr.c +++ b/src/common/extstr.c @@ -24,9 +24,12 @@ #include "extstr.h" +#include <ctype.h> #include <malloc.h> #include <regex.h> +#include <stdio.h> #include <string.h> +#include <stdarg.h> @@ -96,6 +99,47 @@ char *strnadd(char *str1, const char *str2, size_t n) /****************************************************************************** * * * Paramètres : str1 = chaîne de caractères à compléter. * +* fmt = description de la forme de la chaîne complémentaire. * +* ... = éléments associés au format à construire. * +* * +* Description : Complète une chaîne de caractères avec une chaîne à formater.* +* * +* Retour : Chaîne de caractères complétée, à libérer de la mémoire. * +* * +* Remarques : - * +* * +******************************************************************************/ + +char *straddfmt(char *str1, const char *fmt, ...) +{ + char *result; /* Chaîne à renvoyer */ + va_list ap; /* Liste des arguments */ + char *tmp; /* Conservation temporaire */ + int ret; /* Bilan intermédiaire */ + + va_start(ap, fmt); + + ret = vasprintf(&tmp, fmt, ap); + + if (ret != -1) + { + result = stradd(str1, tmp); + free(tmp); + } + + else + result = str1; + + va_end(ap); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : str1 = chaîne de caractères à compléter. * * str2 = chaîne de caractères à ajouter. * * * * Description : Fait précéder une chaîne de caractères par une autre. * @@ -522,3 +566,106 @@ bool _endswith(const char *str, const char *suffix, const char **end) return result; } + + +/****************************************************************************** +* * +* Paramètres : haystack = botte de foin composant l'espace de recherche. * +* haystacklen = taille de cet espace. * +* needle = aiguille visée, cible des recherches. * +* needlelen = taille de l'aiguille à rechercher. * +* * +* Description : Recherche une séquence d'octets dans un ensemble de données. * +* * +* Retour : Adresse de l'éventuelle trouvaille ou NULL. * +* * +* Remarques : - * +* * +******************************************************************************/ + +const void *memcasemem(const void *haystack, size_t haystacklen, const void *needle, size_t needlelen) +{ + const void *result; /* Trouvaille à renvoyer */ + const char *_haystack; /* Autre version de la botte */ + const char *_needle; /* Autre version de l'aiguille */ + size_t i; /* Boucle de parcours #1 */ + size_t k; /* Boucle de parcours #2 */ + int c1; /* Caractère de la chaîne #1 */ + int c2; /* Caractère de la chaîne #2 */ + + result = NULL; + + if (needlelen > haystacklen) + goto done; + + _haystack = (const char *)haystack; + _needle = (const char *)needle; + + for (i = 0; i <= (haystacklen - needlelen); i++, _haystack++) + { + for (k = 0; k < needlelen; k++) + { + c1 = toupper(_haystack[k]); + c2 = toupper(_needle[k]); + + if (c1 != c2) + break; + + } + + if (k == needlelen) + { + result = _haystack; + break; + } + + } + + done: + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : s1 = première séquence d'octets à consulter. * +* s2 = second séquence d'octets à consulter. * +* n = quantité d'octets à comparer. * +* * +* Description : Compare sans casse deux série d'octets entre elles. * +* * +* Retour : Status de la comparaison des séries d'octets. * +* * +* Remarques : - * +* * +******************************************************************************/ + +int memcasecmp(const void *s1, const void *s2, size_t n) +{ + int result; /* Statut à retourner */ + size_t i; /* Boucle de parcours */ + const char *_s1; /* Séquence avec taille #1 */ + const char *_s2; /* Séquence avec taille #2 */ + int c1; /* Caractère de la chaîne #1 */ + int c2; /* Caractère de la chaîne #2 */ + + result = 0; + + _s1 = (const char *)s1; + _s2 = (const char *)s2; + + for (i = 0; i < n; i++) + { + c1 = toupper(_s1[i]); + c2 = toupper(_s2[i]); + + result = c1 - c2; + if (result != 0) break; + + } + + return result; + +} diff --git a/src/common/extstr.h b/src/common/extstr.h index 1c39603..a2293be 100644 --- a/src/common/extstr.h +++ b/src/common/extstr.h @@ -37,6 +37,9 @@ char *stradd(char *, const char *); /* Complète une chaîne de caractères avec une autre. */ char *strnadd(char *, const char *, size_t); +/* Complète une chaîne de caractères avec une chaîne à formater. */ +char *straddfmt(char *, const char *, ...); + /* Fait précéder une chaîne de caractères par une autre. */ char *strprep(char *, const char *); @@ -76,6 +79,12 @@ bool _endswith(const char *, const char *, const char **); #define startswith(str, prefix) _startswith(str, prefix, NULL) #define endswith(str, suffix) _endswith(str, suffix, NULL) +/* Recherche une séquence d'octets dans un ensemble de données. */ +const void *memcasemem(const void *, size_t, const void *, size_t); + +/* Compare sans casse deux série d'octets entre elles. */ +int memcasecmp(const void *, const void *, size_t); + #endif /* _COMMON_EXTSTR_H */ diff --git a/src/common/itoa.c b/src/common/itoa.c new file mode 100644 index 0000000..56fc638 --- /dev/null +++ b/src/common/itoa.c @@ -0,0 +1,135 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * itoa.c - conversion d'un nombre en chaîne de caractères + * + * Copyright (C) 2023 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 Chrysalide. If not, see <http://www.gnu.org/licenses/>. + */ + + +#include "itoa.h" + + +#include <assert.h> +#include <malloc.h> +#include <math.h> + + + +/****************************************************************************** +* * +* Paramètres : n = nombre à transformer. * +* base = base à considérer pour la sortie. * +* * +* Description : Convertit une valeur en une forme textuelle. * +* * +* Retour : Chaîne de caractères mises en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +char *itoa(long long n, unsigned char base) +{ + char *result; /* Texte à retourner */ + size_t size; /* Taille de chaîne en sortie */ + char *iter; /* Tête d'écriture */ +#ifndef NDEBUG + size_t counter; /* Décompte des impressions */ +#endif + long long rem; /* Unité à transposer */ + + /** + * Préparation du stockage de la chaîne finale. + */ + + if (n == 0) + size = 1; + + else if (n < 0) + { + size = (size_t)(log(-n) / log(base) + 1); + size++; + } + else + size = (size_t)(log(n) / log(base) + 1); + + /* '\0' final */ + size++; + + result = malloc(size); + if (result == NULL) goto exit; + + /** + * Remplissage avec la valeur textuelle correspondant à la valeur fournie. + */ + +#ifndef NDEBUG + counter = 0; +#endif + + if (n < 0) + { + result[0] = '-'; +#ifndef NDEBUG + counter++; +#endif + + n *= -1; + + } + + iter = result + size - 1; + + *iter-- = '\0'; +#ifndef NDEBUG + counter++; +#endif + + if (n == 0) + { + *iter-- = '0'; +#ifndef NDEBUG + counter++; +#endif + } + + else + while (n > 0) + { + rem = n % base; + + if (rem >= 10) + *iter-- = 'a' + (rem - 10); + else + *iter-- = '0' + rem; + +#ifndef NDEBUG + counter++; +#endif + + n = n / base; + + } + + assert(counter < size); + + exit: + + return result; + +} diff --git a/src/common/itoa.h b/src/common/itoa.h new file mode 100644 index 0000000..4608a50 --- /dev/null +++ b/src/common/itoa.h @@ -0,0 +1,34 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * itoa.h - prototypes pour la conversion d'un nombre en chaîne de caractères + * + * Copyright (C) 2023 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 Chrysalide. If not, see <http://www.gnu.org/licenses/>. + */ + + +#ifndef _COMMON_ITOA_H +#define _COMMON_ITOA_H + + + +/* Convertit une valeur en une forme textuelle. */ +char *itoa(long long, unsigned char); + + + +#endif /* _COMMON_ITOA_H */ diff --git a/src/common/sort.c b/src/common/sort.c index 32a7457..d79d71a 100644 --- a/src/common/sort.c +++ b/src/common/sort.c @@ -97,6 +97,68 @@ int sort_unsigned_long(unsigned long a, unsigned long b) * Paramètres : a = premier élément à consulter et comparer. * * b = second élément à consulter et comparer. * * * +* Description : Compare une valeur avec une autre. * +* * +* Retour : Bilan de la comparaison. * +* * +* Remarques : - * +* * +******************************************************************************/ + +int sort_signed_long_long(signed long long a, signed long long b) +{ + int result; /* Bilan à renvoyer */ + + if (a < b) + result = -1; + + else if (a > b) + result = 1; + + else + result = 0; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : a = premier élément à consulter et comparer. * +* b = second élément à consulter et comparer. * +* * +* Description : Compare une valeur avec une autre. * +* * +* Retour : Bilan de la comparaison. * +* * +* Remarques : - * +* * +******************************************************************************/ + +int sort_unsigned_long_long(unsigned long long a, unsigned long long b) +{ + int result; /* Bilan à renvoyer */ + + if (a < b) + result = -1; + + else if (a > b) + result = 1; + + else + result = 0; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : a = premier élément à consulter et comparer. * +* b = second élément à consulter et comparer. * +* * * Description : Compare une valeur de 64 bits avec une autre. * * * * Retour : Bilan de la comparaison. * @@ -370,6 +432,91 @@ void *qinsert_multi(void *base, size_t *nmemb, size_t size, __compar_fn_t compar /****************************************************************************** * * +* Paramètres : base = adresse du tableau à parcourir. * +* nmemb = nombre d'éléments présents au total. [OUT] * +* allocated = taille déjà allouée pour le tableau. [OUT] * +* size = taille de chaque élément du tableau. * +* new = nouvel élément à insérer. * +* index = indice du point d'insertion. * +* * +* Description : Ajoute à l'endroit indiqué un élément dans un tableau. * +* * +* Retour : Nouvel emplacement du tableau agrandi. * +* * +* Remarques : - * +* * +******************************************************************************/ + +void *_qinsert_managed(void *base, size_t *nmemb, size_t *allocated, size_t size, void *new, size_t index) +{ + void *result; /* Tableau trié à retourner */ + + if (*nmemb == *allocated) + { + if (*allocated == 0) + *allocated = 1024 * 8; + else + *allocated *= 2; + + result = realloc(base, *allocated * size); + + } + else + result = base; + + if (index < *nmemb) + memmove((char *)result + (index + 1) * size, (char *)result + index * size, (*nmemb - index) * size); + + (*nmemb)++; + + memcpy((char *)result + index * size, new, size); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : base = adresse du tableau à parcourir. * +* nmemb = nombre d'éléments présents au total. [OUT] * +* allocated = taille déjà allouée pour le tableau. [OUT] * +* size = taille de chaque élément du tableau. * +* compar = méthode de comparaison entre éléments. * +* new = nouvel élément à insérer. * +* * +* Description : Ajoute au bon endroit un élément dans un tableau trié. * +* * +* Retour : Nouvel emplacement du tableau agrandi. * +* * +* Remarques : - * +* * +******************************************************************************/ + +void *qinsert_managed(void *base, size_t *nmemb, size_t *allocated, size_t size, __compar_fn_t compar, void *new) +{ + void *result; /* Tableau trié à retourner */ +#ifndef NDEBUG + bool found; /* Présence de partage existant*/ +#endif + size_t index; /* Indice du point d'insertion */ + +#ifndef NDEBUG + found = bsearch_index(new, base, *nmemb, size, compar, &index); + assert(!found); +#else + bsearch_index(new, base, *nmemb, size, compar, &index); +#endif + + result = _qinsert_managed(base, nmemb, allocated, size, new, index); + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : base = adresse du tableau à parcourir. * * nmem = nombre d'éléments présents au total. [OUT] * * size = taille de chaque élément du tableau. * diff --git a/src/common/sort.h b/src/common/sort.h index fbdecec..39a6f33 100644 --- a/src/common/sort.h +++ b/src/common/sort.h @@ -37,6 +37,12 @@ int sort_boolean(bool, bool); /* Compare une valeur avec une autre. */ int sort_unsigned_long(unsigned long, unsigned long); +/* Compare une valeur avec une autre. */ +int sort_signed_long_long(signed long long, signed long long); + +/* Compare une valeur avec une autre. */ +int sort_unsigned_long_long(unsigned long long, unsigned long long); + /* Compare une valeur de 64 bits avec une autre. */ int sort_uint64_t(uint64_t, uint64_t); @@ -58,6 +64,12 @@ void *qinsert(void *, size_t *, size_t, __compar_fn_t, void *); /* Ajoute au bon endroit un élément dans un tableau trié. */ void *qinsert_multi(void *, size_t *, size_t, __compar_fn_t, void *); +/* Ajoute à l'endroit indiqué un élément dans un tableau. */ +void *_qinsert_managed(void *, size_t *, size_t *, size_t, void *, size_t); + +/* Ajoute au bon endroit un élément dans un tableau trié. */ +void *qinsert_managed(void *, size_t *, size_t *, size_t, __compar_fn_t, void *); + /* Supprime un élément dans un tableau trié. */ void *_qdelete(void *, size_t *, size_t, size_t); diff --git a/src/common/szstr.h b/src/common/szstr.h new file mode 100644 index 0000000..406a9f1 --- /dev/null +++ b/src/common/szstr.h @@ -0,0 +1,112 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * szstr.h - prototypes pour une manipulation de chaînes issues de Flex/Bison + * + * Copyright (C) 2023 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 Chrysalide. If not, see <http://www.gnu.org/licenses/>. + */ + + +#ifndef _COMMON_SZSTR_H +#define _COMMON_SZSTR_H + + +#include <string.h> +#include <sys/types.h> + + +#include "sort.h" +#include "../arch/archbase.h" + + + +/* Structure associant une chaîne et sa taille */ +typedef struct _sized_string_t +{ + union { + + const char *static_data; /* Données non modifiées */ + char *data; /* Chaîne de caractères */ + + const bin_t *static_bin_data; /* Données brutes non modifiées*/ + bin_t *bin_data; /* Données brutes */ + + }; + + size_t len; /* Taille correspondante */ + +} sized_string_t; + + +typedef sized_string_t sized_binary_t; + + +#define init_szstr(s) \ + do \ + { \ + (s)->data = NULL; \ + (s)->len = 0; \ + } \ + while (0) + +#define szstrdup(dst, src) \ + do \ + { \ + (dst)->data = malloc((src)->len); \ + memcpy((dst)->data, (src)->data, (src)->len); \ + (dst)->len = (src)->len; \ + } \ + while (0) + +#define copy_szstr(d, s) (d) = (s); + +#define exit_szstr(s) \ + do \ + { \ + if ((s)->data != NULL) \ + { \ + free((s)->data); \ + init_szstr(s); \ + } \ + } \ + while (0) + +#define szstrcmp(s1, s2) \ + ({ \ + int __ret; \ + size_t __n; \ + __n = (s1)->len < (s2)->len ? (s1)->len : (s2)->len; \ + __ret = strncmp((s1)->data, (s2)->data, __n); \ + if (__ret == 0) \ + __ret = sort_unsigned_long_long((s1)->len, (s2)->len); \ + __ret; \ + }) + +#define szmemcmp(s1, s2) \ + ({ \ + int __ret; \ + size_t __n; \ + __n = (s1)->len < (s2)->len ? (s1)->len : (s2)->len; \ + __ret = memcmp((s1)->data, (s2)->data, __n); \ + if (__ret == 0) \ + __ret = sort_unsigned_long_long((s1)->len, (s2)->len); \ + __ret; \ + }) + + + +#endif /* _COMMON_SZSTR_H */ |