Re: undefined behaviour findings in bitset

[Akim Demaille <akim@lrde.epita.fr>]

Hi Bruno,

> Le 9 mars 2019 à 20:37, Bruno Haible <bruno@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.demaille@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  <akim@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  <bruno@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.demaille@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  <akim@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  <akim@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.demaille@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  <akim@lrde.epita.fr>
+
+	bitset: a bit (...) more tests
+	* tests/test-bitset.c (check_attributes): Check zero and ones.
+
 2019-03-16  Akim Demaille  <akim@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 };