From e97dda4a993713aea7452a604086c9e4f0ebdd7e Mon Sep 17 00:00:00 2001
From: Cyrille Bagard <nocbos@gmail.com>
Date: Wed, 17 Apr 2024 22:56:39 +0200
Subject: Create a function to search for the next set bit in bit field.
---
plugins/pychrysalide/common/bits.c | 56 +++++++++++++++++++++
src/common/bits.c | 99 ++++++++++++++++++++++++++++++++++++++
src/common/bits.h | 3 ++
tests/common/bitfield.py | 29 +++++++++++
4 files changed, 187 insertions(+)
diff --git a/plugins/pychrysalide/common/bits.c b/plugins/pychrysalide/common/bits.c
index 9275996..a127251 100644
--- a/plugins/pychrysalide/common/bits.c
+++ b/plugins/pychrysalide/common/bits.c
@@ -98,6 +98,9 @@ static PyObject *py_bitfield_test_zeros_with(PyObject *, PyObject *);
/* Teste l'état à 1 de bits selon un masque de bits. */
static PyObject *py_bitfield_test_ones_with(PyObject *, PyObject *);
+/* Recherche un prochain bit défini dans un champ de bits. */
+static PyObject *py_bitfield_find_next_set(PyObject *, PyObject *);
+
/* Indique la taille d'un champ de bits donné. */
static PyObject *py_bitfield_get_size(PyObject *, void *);
@@ -891,6 +894,58 @@ static PyObject *py_bitfield_test_ones_with(PyObject *self, PyObject *args)
/******************************************************************************
* *
+* Paramètres : self = champ de bits à consulter. *
+* args = arguments fournis pour la conduite de l'opération. *
+* *
+* 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 : - *
+* *
+******************************************************************************/
+
+static PyObject *py_bitfield_find_next_set(PyObject *self, PyObject *args)
+{
+ PyObject *result; /* Bilan à faire remonter */
+ unsigned long prev; /* Indice d'un bit à écarter */
+ int ret; /* Bilan de lecture des args. */
+ py_bitfield_t *bf; /* Instance à manipuler */
+ size_t found; /* Indice de bit trouvé */
+
+#define BITFIELD_FIND_NEXT_SET_METHOD PYTHON_METHOD_DEF \
+( \
+ find_next_set, "$self, /, prev=None", \
+ METH_VARARGS, py_bitfield, \
+ "Find the index of the next set bit in the bit field.\n"\
+ "\n" \
+ "If provided, the *prev* argument is the position of" \
+ " a previously found bit, which gets discarded for the" \
+ " current call.\n" \
+ "\n" \
+ "The result is a integer value: a valid index inside" \
+ " the bit field, or the bit field size if no set bit" \
+ " is found." \
+)
+
+ prev = (unsigned long)-1;
+
+ ret = PyArg_ParseTuple(args, "|k", &prev);
+ if (!ret) return NULL;
+
+ bf = (py_bitfield_t *)self;
+
+ found = find_next_set_in_bit_field(bf->native, prev == (unsigned long)-1 ? NULL : (size_t []) { prev });
+
+ result = PyLong_FromSize_t(found);
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
* Paramètres : self = classe représentant une instruction. *
* closure = adresse non utilisée ici. *
* *
@@ -998,6 +1053,7 @@ PyTypeObject *get_python_bitfield_type(void)
BITFIELD_TEST_ALL_METHOD,
BITFIELD_TEST_ZEROS_WITH_METHOD,
BITFIELD_TEST_ONES_WITH_METHOD,
+ BITFIELD_FIND_NEXT_SET_METHOD,
{ NULL }
};
diff --git a/src/common/bits.c b/src/common/bits.c
index 0e5afc8..3d0004c 100644
--- a/src/common/bits.c
+++ b/src/common/bits.c
@@ -49,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);
@@ -903,7 +907,102 @@ 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. *
* *
diff --git a/src/common/bits.h b/src/common/bits.h
index cd71681..608db39 100644
--- a/src/common/bits.h
+++ b/src/common/bits.h
@@ -96,6 +96,9 @@ 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 *);
diff --git a/tests/common/bitfield.py b/tests/common/bitfield.py
index aff5de6..75dfb6e 100644
--- a/tests/common/bitfield.py
+++ b/tests/common/bitfield.py
@@ -231,6 +231,35 @@ class TestBitFields(ChrysalideTestCase):
self.assertNotEqual(bf_a, bf_b)
+ def testSearchOfSetBit(self):
+ """Find the next set bit in a bit field."""
+
+ size = 128
+ bf = BitField(size, 0)
+
+ bits = [ 0, 1, 50, 63, 64, 65, 111 ]
+
+ for b in bits:
+ bf.set(b, 1)
+
+ prev = None
+ found = []
+
+ while prev is None or prev < size:
+
+ if prev is None:
+ f = bf.find_next_set()
+ else:
+ f = bf.find_next_set(prev)
+
+ if f < size:
+ found.append(f)
+
+ prev = f
+
+ self.assertEqual(found, bits)
+
+
def testRealCase00(self):
"""Test bits in bitfields against other bitfields in a real case (#02)."""
--
cgit v0.11.2-87-g4458