diff options
Diffstat (limited to 'src/common/bits.c')
| -rw-r--r-- | src/common/bits.c | 414 |
1 files changed, 383 insertions, 31 deletions
diff --git a/src/common/bits.c b/src/common/bits.c index a037078..3d0004c 100644 --- a/src/common/bits.c +++ b/src/common/bits.c @@ -38,7 +38,9 @@ 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 */ @@ -47,6 +49,10 @@ struct _bitfield_t }; +/* 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); @@ -73,18 +79,20 @@ static bool test_state_within_bit_field(const bitfield_t *, size_t, const bitfie 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; @@ -140,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; @@ -183,7 +191,45 @@ 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); } @@ -204,7 +250,7 @@ void copy_bit_field(bitfield_t *dest, const bitfield_t *src) void resize_bit_field(bitfield_t **field, size_t length) { bitfield_t *_field; /* Commodité d'accès */ - size_t requested; /* Nombre de mots à allouer */ + 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é */ @@ -217,18 +263,18 @@ void resize_bit_field(bitfield_t **field, size_t length) { /* Redimensionnement */ - requested = length / (sizeof(unsigned long) * 8); - if (length % (sizeof(unsigned long) * 8) != 0) requested++; - - base = sizeof(bitfield_t) + requested * sizeof(unsigned long); + needed = length / (sizeof(unsigned long) * 8); + if (length % (sizeof(unsigned long) * 8) != 0) needed++; - *field = realloc(_field, base); - _field = *field; + 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); @@ -245,7 +291,7 @@ void resize_bit_field(bitfield_t **field, size_t length) } - for (i = last; i < requested; i++) + for (i = last; i < needed; i++) { if (_field->default_state) _field->bits[i] = ~0ul; @@ -258,7 +304,9 @@ void resize_bit_field(bitfield_t **field, size_t length) /* Actualisation des tailles */ _field->length = length; - _field->requested = requested; + + _field->allocated_words = needed; + _field->used_words = needed; } @@ -326,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; @@ -366,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)); } @@ -385,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)); } @@ -483,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]; } @@ -508,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]; } @@ -545,14 +593,13 @@ void or_bit_field_at(bitfield_t *dest, const bitfield_t *src, size_t first) remaining = (first + src->length) % (sizeof(unsigned long) * 8); if ((first + src->length) % (sizeof(unsigned long) * 8) > 0) - last_iter = src->requested; + last_iter = src->used_words; else - last_iter = src->requested - 1; - + last_iter = src->used_words - 1; for (i = 0; i <= last_iter; i++) { - if (i < src->requested) + if (i < src->used_words) word = src->bits[i] << offset; else word = 0; @@ -603,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. * @@ -736,7 +819,7 @@ static bool test_state_within_bit_field(const bitfield_t *field, size_t first, c else finalcut = (1lu << remaining) - 1; - for (i = 0; i < mask->requested && result; i++) + for (i = 0; i < mask->used_words && result; i++) { windex = start + i; @@ -746,7 +829,7 @@ static bool test_state_within_bit_field(const bitfield_t *field, size_t first, c else { word = field->bits[windex] >> offset; - if ((windex + 1) < field->requested) + if ((windex + 1) < field->used_words) word |= field->bits[windex + 1] << (sizeof(unsigned long) * 8 - offset); } @@ -756,7 +839,7 @@ static bool test_state_within_bit_field(const bitfield_t *field, size_t first, c test &= bitmask; - if ((i + 1) == mask->requested) + if ((i + 1) == mask->used_words) { bitmask &= finalcut; test &= finalcut; @@ -824,6 +907,223 @@ bool test_ones_within_bit_field(const bitfield_t *field, size_t first, const bit /****************************************************************************** * * * 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. * * * @@ -844,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]; @@ -866,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 |