summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/common/asm.c98
-rw-r--r--src/common/asm.h6
-rw-r--r--src/common/bits.c50
-rw-r--r--src/common/bits.h3
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 */