From 72b1c890ed19ebd7780e634d4874d12a619f259e Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Tue, 19 Jun 2018 22:23:30 +0200 Subject: Extended the bitfield operations and their Python bindings. --- plugins/pychrysalide/common/bits.c | 152 ++++++++++++++++++++++++++++++++++++- src/common/asm.c | 98 ++++++++++++++++++++++++ src/common/asm.h | 6 ++ src/common/bits.c | 50 ++++++++++++ src/common/bits.h | 3 + tests/common/bitfield.py | 30 +++++++- 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 +#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) -- cgit v0.11.2-87-g4458