From e97dda4a993713aea7452a604086c9e4f0ebdd7e Mon Sep 17 00:00:00 2001 From: Cyrille Bagard 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