Hi Bruno,
> Le 9 mars 2019 à 20:37, Bruno Haible <br...@clisp.org> a écrit :
>
> Hi Akim,
>
> This one I have not fixed:
>
> lib/bitset/table.c:784:54: runtime error: shift exponent 87 is too large for
> 64-bit type 'long unsigned int'
>
> To reproduce: Use gcc 8.2.0 and CC="gcc -fsanitize=undefined".
Thanks for the report! Here is my proposal, in three patches.
commit 6f8b57537eb47418a432b672cbb240713f005a6a
Author: Akim Demaille <akim.demai...@gmail.com>
Date: Thu Mar 14 08:31:54 2019 +0100
bitset: style changes
* lib/bitset/table.c: Use NULL, not 0, for pointers.
Formatting changes.
(tbitset_list): Reduce scopes.
diff --git a/ChangeLog b/ChangeLog
index 544d69d4b..2352520a5 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2019-03-14 Akim Demaille <a...@lrde.epita.fr>
+
+ bitset: style changes.
+ * lib/bitset/table.c: Use NULL, not 0, for pointers.
+ Formatting changes.
+ (tbitset_list): Reduce scopes.
+
2019-03-14 Bruno Haible <br...@clisp.org>
isatty: Make it return true in Cygwin consoles on native Windows.
diff --git a/lib/bitset/table.c b/lib/bitset/table.c
index 8351cf784..a129c8712 100644
--- a/lib/bitset/table.c
+++ b/lib/bitset/table.c
@@ -300,7 +300,7 @@ tbitset_elt_find (bitset bset, bitset_bindex bindex,
abort ();
case EBITSET_FIND:
- return 0;
+ return NULL;
case EBITSET_CREATE:
if (eindex >= size)
@@ -588,8 +588,8 @@ tbitset_list_reverse (bitset bset, bitset_bindex *list,
/* Find list of up to NUM bits set in BSET starting from and including
- *NEXT and store in array LIST. Return with actual number of bits
- found and with *NEXT indicating where search stopped. */
+ *NEXT and store in array LIST. Return with actual number of bits
+ found and with *NEXT indicating where search stopped. */
static bitset_bindex
tbitset_list (bitset bset, bitset_bindex *list,
bitset_bindex num, bitset_bindex *next)
@@ -607,17 +607,14 @@ tbitset_list (bitset bset, bitset_bindex *list,
if (bitno % EBITSET_ELT_BITS)
{
/* We need to start within an element. This is not very common. */
-
tbitset_elt *elt = elts[eindex];
if (elt)
{
- bitset_windex woffset;
bitset_word *srcp = EBITSET_WORDS (elt);
+ bitset_windex woffset = eindex * EBITSET_ELT_WORDS;
- bitset_windex windex = bitno / BITSET_WORD_BITS;
- woffset = eindex * EBITSET_ELT_WORDS;
-
- for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
+ for (bitset_windex windex = bitno / BITSET_WORD_BITS;
+ (windex - woffset) < EBITSET_ELT_WORDS; windex++)
{
bitset_word word = srcp[windex - woffset] >> (bitno %
BITSET_WORD_BITS);
commit f4a85b4ffa59650c36227fc94e4c5973e6449d48
Author: Akim Demaille <akim.demai...@gmail.com>
Date: Sat Mar 16 17:16:48 2019 +0100
bitset: fix bitset overflows
Reported by Bruno Haible.
https://lists.gnu.org/archive/html/bug-gnulib/2019-03/msg00017.html
* lib/bitset/table.c (tbitset_test): last_bit is the position of
the bit in the array of bitset_word, so be sure to take its modulo
number-of-bits-in-bitset-word (i.e., EBITSET_ELT_WORDS).
* lib/bitset/list.c (lbitset_unused_clear): Likewise.
diff --git a/ChangeLog b/ChangeLog
index 2352520a5..0e7a74a10 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2019-03-16 Akim Demaille <a...@lrde.epita.fr>
+
+ bitset: fix bitset overflows.
+ Reported by Bruno Haible.
+ https://lists.gnu.org/archive/html/bug-gnulib/2019-03/msg00017.html
+ * lib/bitset/table.c (tbitset_test): last_bit is the position of
+ the bit in the array of bitset_word, so be sure to take its modulo
+ number-of-bits-in-bitset-word (i.e., EBITSET_ELT_WORDS).
+ * lib/bitset/list.c (lbitset_unused_clear): Likewise.
+
2019-03-14 Akim Demaille <a...@lrde.epita.fr>
bitset: style changes.
diff --git a/lib/bitset/list.c b/lib/bitset/list.c
index f42edb8ea..fe1b52869 100644
--- a/lib/bitset/list.c
+++ b/lib/bitset/list.c
@@ -859,7 +859,8 @@ lbitset_unused_clear (bitset dst)
bitset_word *srcp = elt->words;
bitset_windex windex = n_bits / BITSET_WORD_BITS;
- srcp[windex - elt->index] &= ((bitset_word) 1 << last_bit) - 1;
+ srcp[windex - elt->index]
+ &= ((bitset_word) 1 << (last_bit % BITSET_WORD_BITS)) - 1;
windex++;
for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
diff --git a/lib/bitset/table.c b/lib/bitset/table.c
index a129c8712..9cac96469 100644
--- a/lib/bitset/table.c
+++ b/lib/bitset/table.c
@@ -778,7 +778,8 @@ tbitset_unused_clear (bitset dst)
bitset_windex windex = n_bits / BITSET_WORD_BITS;
bitset_windex woffset = eindex * EBITSET_ELT_WORDS;
- srcp[windex - woffset] &= ((bitset_word) 1 << last_bit) - 1;
+ srcp[windex - woffset]
+ &= ((bitset_word) 1 << (last_bit % BITSET_WORD_BITS)) - 1;
windex++;
for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
srcp[windex - woffset] = 0;
commit 4c8a35ed125e1b87a11d6aecd0b7b216384552bb
Author: Akim Demaille <akim.demai...@gmail.com>
Date: Sat Mar 16 17:36:22 2019 +0100
bitset: a bit (...) more tests
* tests/test-bitset.c (check_attributes): Check zero and ones.
diff --git a/ChangeLog b/ChangeLog
index 0e7a74a10..db23ee898 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2019-03-16 Akim Demaille <a...@lrde.epita.fr>
+
+ bitset: a bit (...) more tests
+ * tests/test-bitset.c (check_attributes): Check zero and ones.
+
2019-03-16 Akim Demaille <a...@lrde.epita.fr>
bitset: fix bitset overflows.
diff --git a/tests/test-bitset.c b/tests/test-bitset.c
index 032865095..f4502d1d6 100644
--- a/tests/test-bitset.c
+++ b/tests/test-bitset.c
@@ -32,12 +32,18 @@ void assert_bitset_equal (bitset bs1, bitset bs2)
ASSERT (bitset_test (bs1, i) == bitset_test (bs2, i));
}
+static
void bitset_random (bitset bs)
{
for (bitset_bindex i = 0; i < bitset_size (bs); ++i)
bitset_set (bs, RANDOM (2));
}
+
+/* Check various operations on random bitsets with two different
+ implementations. */
+
+static
void compare (enum bitset_attr a, enum bitset_attr b)
{
const int nbits = RANDOM (256);
@@ -62,10 +68,17 @@ void compare (enum bitset_attr a, enum bitset_attr b)
bitset_copy (bsrc3, asrc3);
bitset bdst = bitset_create (nbits, b);
+ /* not */
+ bitset_not (adst, asrc0);
+ bitset_not (bdst, bsrc0);
+ assert_bitset_equal (adst, bdst);
+
+ /* not */
bitset_not (adst, asrc0);
bitset_not (bdst, bsrc0);
assert_bitset_equal (adst, bdst);
+ /* and */
bitset_and (adst, asrc0, asrc1);
bitset_and (bdst, bsrc0, bsrc1);
assert_bitset_equal (adst, bdst);
@@ -73,6 +86,7 @@ void compare (enum bitset_attr a, enum bitset_attr b)
== bitset_and_cmp (bdst, bsrc0, bsrc1));
assert_bitset_equal (adst, bdst);
+ /* andn */
bitset_andn (adst, asrc0, asrc1);
bitset_andn (bdst, bsrc0, bsrc1);
assert_bitset_equal (adst, bdst);
@@ -80,6 +94,7 @@ void compare (enum bitset_attr a, enum bitset_attr b)
== bitset_andn_cmp (bdst, bsrc0, bsrc1));
assert_bitset_equal (adst, bdst);
+ /* or */
bitset_or (adst, asrc0, asrc1);
bitset_or (bdst, bsrc0, bsrc1);
assert_bitset_equal (adst, bdst);
@@ -87,6 +102,7 @@ void compare (enum bitset_attr a, enum bitset_attr b)
== bitset_or_cmp (bdst, bsrc0, bsrc1));
assert_bitset_equal (adst, bdst);
+ /* xor */
bitset_xor (adst, asrc0, asrc1);
bitset_xor (bdst, bsrc0, bsrc1);
assert_bitset_equal (adst, bdst);
@@ -94,6 +110,7 @@ void compare (enum bitset_attr a, enum bitset_attr b)
== bitset_xor_cmp (bdst, bsrc0, bsrc1));
assert_bitset_equal (adst, bdst);
+ /* and_or */
bitset_and_or (adst, asrc0, asrc1, asrc2);
bitset_and_or (bdst, bsrc0, bsrc1, bsrc2);
assert_bitset_equal (adst, bdst);
@@ -101,6 +118,7 @@ void compare (enum bitset_attr a, enum bitset_attr b)
== bitset_and_or_cmp (bdst, bsrc0, bsrc1, bsrc2));
assert_bitset_equal (adst, bdst);
+ /* andn_or */
bitset_andn_or (adst, asrc0, asrc1, asrc2);
bitset_andn_or (bdst, bsrc0, bsrc1, bsrc2);
assert_bitset_equal (adst, bdst);
@@ -108,6 +126,7 @@ void compare (enum bitset_attr a, enum bitset_attr b)
== bitset_andn_or_cmp (bdst, bsrc0, bsrc1, bsrc2));
assert_bitset_equal (adst, bdst);
+ /* or_and */
bitset_or_and (adst, asrc0, asrc1, asrc2);
bitset_or_and (bdst, bsrc0, bsrc1, bsrc2);
assert_bitset_equal (adst, bdst);
@@ -115,6 +134,16 @@ void compare (enum bitset_attr a, enum bitset_attr b)
== bitset_or_and_cmp (bdst, bsrc0, bsrc1, bsrc2));
assert_bitset_equal (adst, bdst);
+ /* ones */
+ bitset_ones (adst);
+ bitset_ones (bdst);
+ assert_bitset_equal (adst, bdst);
+
+ /* zero */
+ bitset_zero (adst);
+ bitset_zero (bdst);
+ assert_bitset_equal (adst, bdst);
+
bitset_free (bdst);
bitset_free (bsrc3);
bitset_free (bsrc2);
@@ -127,6 +156,11 @@ void compare (enum bitset_attr a, enum bitset_attr b)
bitset_free (asrc0);
}
+
+/* Check various operations against expected values for a bitset
+ having attributes ATTR. */
+
+static
void check_attributes (enum bitset_attr attr)
{
enum { nbits = 32 };
