summaryrefslogtreecommitdiff
path: root/src/common/bits.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/common/bits.c')
-rw-r--r--src/common/bits.c649
1 files changed, 634 insertions, 15 deletions
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
generated by cgit v0.11.2-87-g4458 at 2024-04-28 11:57:24 (GMT)