Extended the bitfield operations and their Python bindings.

4 files changed, 157 insertions, 0 deletions

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 */