Extended the bitfield operations and their Python bindings.

6 files changed, 337 insertions, 2 deletions

diff --git a/plugins/pychrysalide/common/bits.c b/plugins/pychrysalide/common/bits.c
index 33f81c3..065f32e 100644
--- a/plugins/pychrysalide/common/bits.c
+++ b/plugins/pychrysalide/common/bits.c
@@ -52,6 +52,12 @@ static PyObject *py_bitfield_nb_and(PyObject *, PyObject *);
 /* Effectue une opération de type 'or' avec le type 'bitfield'. */
 static PyObject *py_bitfield_nb_or(PyObject *, PyObject *);
 
+/* Indique la taille de la séquence correspondant à un champ. */
+static Py_ssize_t py_bitfield_sequence_length(PyObject *);
+
+/* Fournit un élément de la séquence correspondant à un champ. */
+static PyObject *py_bitfield_sequence_item(PyObject *, Py_ssize_t);
+
 /* Effectue une comparaison avec un objet Python 'bitfield'. */
 static PyObject *py_bitfield_richcompare(PyObject *, PyObject *, int);
 
@@ -76,6 +82,12 @@ static PyObject *py_bitfield_test_none(PyObject *, PyObject *);
 /* Détermine si un ensemble de bits est à 1 dans un champ. */
 static PyObject *py_bitfield_test_all(PyObject *, PyObject *);
 
+/* Indique la taille d'un champ de bits donné. */
+static PyObject *py_bitfield_get_size(PyObject *, void *);
+
+/* Détermine le nombre de bits à 1 dans un champ. */
+static PyObject *py_bitfield_popcount(PyObject *, void *);
+
 
 
 /******************************************************************************
@@ -228,6 +240,70 @@ static PyObject *py_bitfield_nb_or(PyObject *o1, PyObject *o2)
 
 /******************************************************************************
 *                                                                             *
+*  Paramètres  : self = champ de bits à consulter.                            *
+*                                                                             *
+*  Description : Indique la taille de la séquence correspondant à un champ.   *
+*                                                                             *
+*  Retour      : Taille du champ de bits.                                     *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static Py_ssize_t py_bitfield_sequence_length(PyObject *self)
+{
+    Py_ssize_t result;                      /* Taille à retourner          */
+    py_bitfield_t *bf;                      /* Instance à manipuler        */
+
+    bf = (py_bitfield_t *)self;
+
+    result = get_bit_field_size(bf->native);
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : self = champ de bits à consulter.                            *
+*                i    = indice de l'élément à retourner.                      *
+*                                                                             *
+*  Description : Fournit un élément de la séquence correspondant à un champ.  *
+*                                                                             *
+*  Retour      : Valeur booléenne.                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static PyObject *py_bitfield_sequence_item(PyObject *self, Py_ssize_t i)
+{
+    PyObject *result;                       /* Elément à retourner         */
+    py_bitfield_t *bf;                      /* Instance à manipuler        */
+    bool state;                             /* Etat du bit ciblé           */
+
+    bf = (py_bitfield_t *)self;
+
+    if (i < 0 || i >= (Py_ssize_t)get_bit_field_size(bf->native))
+        result = NULL;
+
+    else
+    {
+        state = test_in_bit_field(bf->native, i);
+
+        result = state ? Py_True : Py_False;
+        Py_INCREF(result);
+
+    }
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
 *  Paramètres  : a  = premier object Python à consulter.                      *
 *                b  = second object Python à consulter.                       *
 *                op = type de comparaison menée.                              *
@@ -502,6 +578,66 @@ static PyObject *py_bitfield_test_all(PyObject *self, PyObject *args)
 
 /******************************************************************************
 *                                                                             *
+*  Paramètres  : self    = classe représentant une instruction.               *
+*                closure = adresse non utilisée ici.                          *
+*                                                                             *
+*  Description : Indique la taille d'un champ de bits donné.                  *
+*                                                                             *
+*  Retour      : Taille du champ de bits.                                     *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static PyObject *py_bitfield_get_size(PyObject *self, void *closure)
+{
+    PyObject *result;                       /* Conversion à retourner      */
+    py_bitfield_t *bf;                      /* Instance à manipuler        */
+    size_t size;                            /* Taille du champs de bits    */
+
+    bf = (py_bitfield_t *)self;
+
+    size = get_bit_field_size(bf->native);
+
+    result = PyLong_FromSize_t(size);
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : self    = classe représentant une instruction.               *
+*                closure = adresse non utilisée ici.                          *
+*                                                                             *
+*  Description : Détermine le nombre de bits à 1 dans un champ.               *
+*                                                                             *
+*  Retour      : Valeur positive ou nulle.                                    *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static PyObject *py_bitfield_popcount(PyObject *self, void *closure)
+{
+    PyObject *result;                       /* Conversion à retourner      */
+    py_bitfield_t *bf;                      /* Instance à manipuler        */
+    size_t count;                           /* Quantité de bits à 1        */
+
+    bf = (py_bitfield_t *)self;
+
+    count = popcount_for_bit_field(bf->native);
+
+    result = PyLong_FromSize_t(count);
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
 *  Paramètres  : -                                                            *
 *                                                                             *
 *  Description : Fournit un accès à une définition de type à diffuser.        *
@@ -517,10 +653,15 @@ PyTypeObject *get_python_bitfield_type(void)
     static PyNumberMethods py_bitfield_nb_proto = {
 
         .nb_and = py_bitfield_nb_and,
-        .nb_or = py_bitfield_nb_or
+        .nb_or  = py_bitfield_nb_or
 
     };
 
+    static PySequenceMethods py_bitfield_sequence_proto = {
+        .sq_length = py_bitfield_sequence_length,
+        .sq_item   = py_bitfield_sequence_item
+    };
+
     static PyMethodDef py_bitfield_methods[] = {
         {
             "dup", py_bitfield_dup,
@@ -566,6 +707,14 @@ PyTypeObject *get_python_bitfield_type(void)
     };
 
     static PyGetSetDef py_bitfield_getseters[] = {
+        {
+            "size", py_bitfield_get_size, NULL,
+            "Provide the size of the bitfield.", NULL
+        },
+        {
+            "popcount", py_bitfield_popcount, NULL,
+            "Get the number of bits set to 1 in the bitfield.", NULL
+        },
         { NULL }
     };
 
@@ -577,6 +726,7 @@ PyTypeObject *get_python_bitfield_type(void)
         .tp_basicsize   = sizeof(py_bitfield_t),
 
         .tp_as_number   = &py_bitfield_nb_proto,
+        .tp_as_sequence = &py_bitfield_sequence_proto,
 
         .tp_flags       = Py_TPFLAGS_DEFAULT,
 
diff --git a/src/common/asm.c b/src/common/asm.c
index 692256f..645bd6a 100644
--- a/src/common/asm.c
+++ b/src/common/asm.c
@@ -36,6 +36,34 @@ static const unsigned int _bval[16] = {
 };
 
 
+/**
+ * Nombre de bits à 1 dans un octet.
+ *
+ * python3 -c "print(', '.join([ str(bin(n).count('1')) for n in range(256) ]))" | sed -re 's/(.{48})/\1\n/g' | sed 's/ $//'
+ */
+
+static const unsigned int _bcount[256] = {
+
+    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
+    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
+
+};
+
+
 
 /******************************************************************************
 *                                                                             *
@@ -111,3 +139,73 @@ bool msb_64(uint64_t v, unsigned int *p)
     return true;
 
 }
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : v = valeur quelconque sur 32 bits.                           *
+*                                                                             *
+*  Description : Détermine le nombre de bits à 1 dans une valeur de 32 bits.  *
+*                                                                             *
+*  Retour      : Nombre de bits à 1.                                          *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+unsigned int popcount_32(uint32_t v)
+{
+    unsigned int result;                    /* Valeur à retourner          */
+
+    /**
+     * Il existe de nombreuses méthodes pour obtenir le résultat attendu
+     * sans recourir à des extensions GCC ou à des instructions d'assembleur :
+     *
+     *  - http://gurmeet.net/puzzles/fast-bit-counting-routines/
+     *
+     * On chosit un bon compromis entre efficacité et lecture.
+     *
+     */
+
+    result = _bcount[v & 0xff]
+           + _bcount[(v >>  8) & 0xff]
+           + _bcount[(v >> 16) & 0xff]
+           + _bcount[(v >> 24) & 0xff];
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : v = valeur quelconque sur 64 bits.                           *
+*                                                                             *
+*  Description : Détermine le nombre de bits à 1 dans une valeur de 64 bits.  *
+*                                                                             *
+*  Retour      : Nombre de bits à 1.                                          *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+unsigned int popcount_64(uint64_t v)
+{
+    unsigned int result;                    /* Valeur à retourner          */
+
+    /**
+     * Cf. popcount_32().
+     */
+
+    result = _bcount[v & 0xff]
+           + _bcount[(v >>  8) & 0xff]
+           + _bcount[(v >> 16) & 0xff]
+           + _bcount[(v >> 24) & 0xff]
+           + _bcount[(v >> 32) & 0xff]
+           + _bcount[(v >> 40) & 0xff]
+           + _bcount[(v >> 48) & 0xff]
+           + _bcount[(v >> 56) & 0xff];
+
+    return result;
+
+}
diff --git a/src/common/asm.h b/src/common/asm.h
index 3e52925..d8436b8 100644
--- a/src/common/asm.h
+++ b/src/common/asm.h
@@ -36,6 +36,12 @@ bool msb_32(uint32_t, unsigned int *);
 /* Détermine l'indice du premier bit à 1, côté gauche. */
 bool msb_64(uint64_t, unsigned int *);
 
+/* Détermine le nombre de bits à 1 dans une valeur de 32 bits. */
+unsigned int popcount_32(uint32_t v);
+
+/* Détermine le nombre de bits à 1 dans une valeur de 64 bits. */
+unsigned int popcount_64(uint64_t v);
+
 
 
 #endif  /* _COMMON_ASM_H */
diff --git a/src/common/bits.c b/src/common/bits.c
index 5533293..cdcef85 100644
--- a/src/common/bits.c
+++ b/src/common/bits.c
@@ -30,6 +30,9 @@
 #include <string.h>
 
 
+#include "asm.h"
+
+
 
 /* Champ de bits simple */
 struct _bitfield_t
@@ -549,3 +552,50 @@ bool test_all_in_bit_field(const bitfield_t *field, size_t first, size_t count)
     return result;
 
 }
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : field = champ de bits à consulter.                           *
+*                                                                             *
+*  Description : Détermine le nombre de bits à 1 dans un champ.               *
+*                                                                             *
+*  Retour      : Valeur positive ou nulle.                                    *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+size_t popcount_for_bit_field(const bitfield_t *field)
+{
+    size_t result;                          /* Quantité à renvoyer         */
+    size_t remaining;                       /* Nombre de bits restants     */
+    size_t i;                               /* Boucle de parcours          */
+    unsigned long value;                    /* Valeur masquée à traiter    */
+
+    result = 0;
+
+    remaining = field->length;
+
+    for (i = 0; i < field->requested; i++)
+    {
+        value = field->bits[i];
+
+        if (remaining < (8 * sizeof(unsigned long)))
+            value &= 1 << (remaining - 1);
+
+#if __WORDSIZE == 64
+        result += popcount_64(value);
+#elif __WORDSIZE == 32
+        result += popcount_32(value);
+#else
+#   error "Unkown word size"
+#endif
+
+        remaining -= 8 * sizeof(unsigned long);
+
+    }
+
+    return result;
+
+}
diff --git a/src/common/bits.h b/src/common/bits.h
index 02f75e9..c6a300a 100644
--- a/src/common/bits.h
+++ b/src/common/bits.h
@@ -78,6 +78,9 @@ bool test_none_in_bit_field(const bitfield_t *, size_t, size_t);
 /* Détermine si un ensemble de bits est à 1 dans un champ. */
 bool test_all_in_bit_field(const bitfield_t *, size_t, size_t);
 
+/* Détermine le nombre de bits à 1 dans un champ. */
+size_t popcount_for_bit_field(const bitfield_t *);
+
 
 
 #endif  /* _COMMON_BITS_H */
diff --git a/tests/common/bitfield.py b/tests/common/bitfield.py
index ec61291..cb82580 100644
--- a/tests/common/bitfield.py
+++ b/tests/common/bitfield.py
@@ -2,7 +2,7 @@
 # -*- coding: utf-8 -*-
 
 
-# Tests minimalistes pour valider la construction de chemins relatifs et absolus.
+# Tests pour valider la manipulation des champs de bits.
 
 
 from chrysacase import ChrysalideTestCase
@@ -21,6 +21,10 @@ class TestBitfields(ChrysalideTestCase):
 
         self.assertEqual(bf, bf2)
 
+        self.assertEqual(bf.size, bf2.size)
+
+        self.assertEqual(bf.popcount, bf2.popcount)
+
 
     def testBitfieldValues(self):
         """Evaluate bitfields basic values."""
@@ -38,6 +42,8 @@ class TestBitfields(ChrysalideTestCase):
 
         self.assertEqual(bf_a, bf_b)
 
+        self.assertEqual(bf_a.popcount, bf_b.popcount)
+
         bf_a = bitfield(75, 1)
         bf_a.reset_all()
 
@@ -45,6 +51,8 @@ class TestBitfields(ChrysalideTestCase):
 
         self.assertEqual(bf_a, bf_b)
 
+        self.assertEqual(bf_a.popcount, bf_b.popcount)
+
 
     def testBitfieldLogicalOperations(self):
         """Perform logical operations on bitfields."""
@@ -53,14 +61,20 @@ class TestBitfields(ChrysalideTestCase):
 
         bf_b = bitfield(75, 0)
 
+        self.assertEqual(bf_a.size, bf_b.size)
+
         bf_f = bf_a & bf_b
 
         self.assertEqual(bf_f, bf_b)
 
+        self.assertEqual(bf_f.popcount, bf_b.popcount)
+
         bf_f = bf_a | bf_b
 
         self.assertEqual(bf_f, bf_a)
 
+        self.assertEqual(bf_f.popcount, bf_a.popcount)
+
 
     def testBitfieldSwitch(self):
         """Switch various bits in bitfields."""
@@ -76,11 +90,15 @@ class TestBitfields(ChrysalideTestCase):
 
         self.assertEqual(bf_t, bf_1)
 
+        self.assertEqual(bf_t.popcount, bf_1.popcount)
+
         for i in range(75):
             bf_t.reset(i, 1)
 
         self.assertEqual(bf_t, bf_0)
 
+        self.assertEqual(bf_t.popcount, bf_0.popcount)
+
 
     def testBitfieldBits(self):
         """Test bits in bitfields."""
@@ -104,3 +122,13 @@ class TestBitfields(ChrysalideTestCase):
         self.assertFalse(bf.test_all(0, 54))
 
         self.assertTrue(bf.test_none(0, 54))
+
+
+    def testPopCountForBitfield(self):
+        """Count bits set to 1 in bitfield."""
+
+        bf = bitfield(65, 1)
+
+        self.assertEqual(bf.size, 65)
+
+        self.assertEqual(bf.popcount, 65)