diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/common/asm.c | 98 | ||||
| -rw-r--r-- | src/common/asm.h | 6 | ||||
| -rw-r--r-- | src/common/bits.c | 50 | ||||
| -rw-r--r-- | src/common/bits.h | 3 |
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 */ |