Create a function to search for the next set bit in bit field.HEADmaster

4 files changed, 187 insertions, 0 deletions

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)."""