test-bitrotate.c missing test cases

test-bitrotate.c missing test cases

[Jeffrey Walton]

Hi Everyone,

It looks like test-bitrotate.c is missing test cases. It is missing
the 32-bit rotl and rotr of 0-bits.

The 0-bit rotate should tickle undefined behavior.

If you want to clear the undefined behavior, then use this code. It is
recognized by Clang, GCC, ICC. It will be compiled down to a single
instruction on platforms like IA-32. I can find the mailing list
messages for a citation, if needed.

BITROTATE_INLINE uint32_t
rotl32 (uint32_t x, int n)
{
  return ((x << n) | ( x>>(-n&31));
}

BITROTATE_INLINE uint32_t
rotr32 (uint32_t x, int n)
{
  return ((x >> n) | ( x<<(-n&31));
}

Ditto for the other rotates, like rotl64 and rotr64. The 64-bit
rotates should use a mask of 63 instead of 31.

Jeff

Re: test-bitrotate.c missing test cases

[Jeffrey Walton]

[-- Attachment #1: Type: text/plain, Size: 608 bytes --]

On Sun, Mar 29, 2020 at 5:00 AM Jeffrey Walton <noloader@gmail.com> wrote:
>
> It looks like test-bitrotate.c is missing test cases. It is missing
> the 32-bit rotl and rotr of 0-bits.
>
> The 0-bit rotate should tickle undefined behavior.
>
> If you want to clear the undefined behavior, then use this code. It is
> recognized by Clang, GCC, ICC. It will be compiled down to a single
> instruction on platforms like IA-32. I can find the mailing list
> messages for a citation, if needed.

Cleared on the bit rotate branch at
https://github.com/noloader/gnulib/tree/bitrotate.

The patch is attached.

Jeff

[-- Attachment #2: bitrotate.diff --]
[-- Type: text/x-patch, Size: 8730 bytes --]

diff --git a/lib/bitrotate.h b/lib/bitrotate.h
index 59827e274..cafa1d99e 100644
--- a/lib/bitrotate.h
+++ b/lib/bitrotate.h
@@ -15,6 +15,7 @@
    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
 
 /* Written by Simon Josefsson <simon@josefsson.org>, 2008. */
+/* Updated for 128-bit types by Jeffrey Walton <noloader@gmail.com>, 2020 */
 
 #ifndef _GL_BITROTATE_H
 #define _GL_BITROTATE_H
@@ -33,40 +34,40 @@ _GL_INLINE_HEADER_BEGIN
 
 #ifdef UINT64_MAX
 /* Given an unsigned 64-bit argument X, return the value corresponding
-   to rotating the bits N steps to the left.  N must be between 1 and
+   to rotating the bits N steps to the left.  N must be between 0 and
    63 inclusive. */
 BITROTATE_INLINE uint64_t
 rotl64 (uint64_t x, int n)
 {
-  return ((x << n) | (x >> (64 - n))) & UINT64_MAX;
+  return ((x << n) | (x >> (-n&63)));
 }
 
 /* Given an unsigned 64-bit argument X, return the value corresponding
-   to rotating the bits N steps to the right.  N must be between 1 to
+   to rotating the bits N steps to the right.  N must be between 0 to
    63 inclusive.*/
 BITROTATE_INLINE uint64_t
 rotr64 (uint64_t x, int n)
 {
-  return ((x >> n) | (x << (64 - n))) & UINT64_MAX;
+  return ((x >> n) | (x << (-n&63)));
 }
 #endif
 
 /* Given an unsigned 32-bit argument X, return the value corresponding
-   to rotating the bits N steps to the left.  N must be between 1 and
+   to rotating the bits N steps to the left.  N must be between 0 and
    31 inclusive. */
 BITROTATE_INLINE uint32_t
 rotl32 (uint32_t x, int n)
 {
-  return ((x << n) | (x >> (32 - n))) & UINT32_MAX;
+  return ((x << n) | (x >> (-n&31)));
 }
 
 /* Given an unsigned 32-bit argument X, return the value corresponding
-   to rotating the bits N steps to the right.  N must be between 1 to
+   to rotating the bits N steps to the right.  N must be between 0 to
    31 inclusive.*/
 BITROTATE_INLINE uint32_t
 rotr32 (uint32_t x, int n)
 {
-  return ((x >> n) | (x << (32 - n))) & UINT32_MAX;
+  return ((x >> n) | (x << (-n&31)));
 }
 
 /* Given a size_t argument X, return the value corresponding
@@ -75,7 +76,8 @@ rotr32 (uint32_t x, int n)
 BITROTATE_INLINE size_t
 rotl_sz (size_t x, int n)
 {
-  return ((x << n) | (x >> ((CHAR_BIT * sizeof x) - n))) & SIZE_MAX;
+  enum {mask = (CHAR_BIT * sizeof x) -1};
+  return ((x << n) | (x >> (-n&mask)));
 }
 
 /* Given a size_t argument X, return the value corresponding
@@ -84,54 +86,68 @@ rotl_sz (size_t x, int n)
 BITROTATE_INLINE size_t
 rotr_sz (size_t x, int n)
 {
-  return ((x >> n) | (x << ((CHAR_BIT * sizeof x) - n))) & SIZE_MAX;
+  enum {mask = (CHAR_BIT * sizeof x) -1};
+  return ((x >> n) | (x << (-n&mask)));
 }
 
 /* Given an unsigned 16-bit argument X, return the value corresponding
-   to rotating the bits N steps to the left.  N must be between 1 to
-   15 inclusive, but on most relevant targets N can also be 0 and 16
-   because 'int' is at least 32 bits and the arguments must widen
-   before shifting. */
+   to rotating the bits N steps to the left.  N must be between 0 to
+   15 inclusive. */
 BITROTATE_INLINE uint16_t
 rotl16 (uint16_t x, int n)
 {
-  return (((unsigned int) x << n) | ((unsigned int) x >> (16 - n)))
-         & UINT16_MAX;
+  return ((x << n) | (x >> (-n&15)));
 }
 
 /* Given an unsigned 16-bit argument X, return the value corresponding
-   to rotating the bits N steps to the right.  N must be in 1 to 15
-   inclusive, but on most relevant targets N can also be 0 and 16
-   because 'int' is at least 32 bits and the arguments must widen
-   before shifting. */
+   to rotating the bits N steps to the right.  N must be between 0 to
+   to 15 inclusive. */
 BITROTATE_INLINE uint16_t
 rotr16 (uint16_t x, int n)
 {
-  return (((unsigned int) x >> n) | ((unsigned int) x << (16 - n)))
-         & UINT16_MAX;
+  return ((x >> n) | (x << (-n&15)));
 }
 
 /* Given an unsigned 8-bit argument X, return the value corresponding
-   to rotating the bits N steps to the left.  N must be between 1 to 7
-   inclusive, but on most relevant targets N can also be 0 and 8
-   because 'int' is at least 32 bits and the arguments must widen
-   before shifting. */
+   to rotating the bits N steps to the left.  N must be between 0 to 7
+   inclusive. */
 BITROTATE_INLINE uint8_t
 rotl8 (uint8_t x, int n)
 {
-  return (((unsigned int) x << n) | ((unsigned int) x >> (8 - n))) & UINT8_MAX;
+  return ((x << n) | (x >> (-n&7)));
 }
 
 /* Given an unsigned 8-bit argument X, return the value corresponding
-   to rotating the bits N steps to the right.  N must be in 1 to 7
-   inclusive, but on most relevant targets N can also be 0 and 8
-   because 'int' is at least 32 bits and the arguments must widen
-   before shifting. */
+   to rotating the bits N steps to the right.  N must be between 0 to 7
+   inclusive. */
 BITROTATE_INLINE uint8_t
 rotr8 (uint8_t x, int n)
 {
-  return (((unsigned int) x >> n) | ((unsigned int) x << (8 - n))) & UINT8_MAX;
+  return ((x >> n) | (x << (-n&7)));
+}
+
+/* Some GCC, Clang, ICC and XLC support 128-bit integers.       */
+/* https://gcc.gnu.org/legacy-ml/gcc-help/2015-08/msg00185.html */
+
+#if __SIZEOF_INT128__ >= 16
+/* Given an unsigned 128-bit argument X, return the value corresponding
+   to rotating the bits N steps to the left.  N must be between 0 to 127
+   inclusive. */
+BITROTATE_INLINE __uint128_t
+rotl128 (__uint128_t x, int n)
+{
+  return ((x << n) | (x >> (-n&127)));
+}
+
+/* Given an unsigned 128-bit argument X, return the value corresponding
+   to rotating the bits N steps to the right.  N must be between 0 to 127
+   inclusive. */
+BITROTATE_INLINE __uint128_t
+rotr128 (__uint128_t x, int n)
+{
+  return ((x >> n) | (x << (-n&127)));
 }
+#endif
 
 _GL_INLINE_HEADER_END
 
diff --git a/tests/test-bitrotate.c b/tests/test-bitrotate.c
index 0007d1c33..8e0346af5 100644
--- a/tests/test-bitrotate.c
+++ b/tests/test-bitrotate.c
@@ -15,6 +15,7 @@
    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
 
 /* Written by Simon Josefsson <simon@josefsson.org>, 2008.  */
+/* Updated for 128-bit types by Jeffrey Walton <noloader@gmail.com>, 2020 */
 
 #include <config.h>
 
@@ -81,6 +82,7 @@ main (void)
   ASSERT (rotr16 (43981, 15) == 22427);
   ASSERT (rotr16 (43981, 16) == 43981);
 
+  ASSERT (rotl32 (2309737967U, 0) == 2309737967U);
   ASSERT (rotl32 (2309737967U, 1) == 324508639U);
   ASSERT (rotl32 (2309737967U, 2) == 649017278U);
   ASSERT (rotl32 (2309737967U, 3) == 1298034556U);
@@ -113,6 +115,7 @@ main (void)
   ASSERT (rotl32 (2309737967U, 30) == 3798659963U);
   ASSERT (rotl32 (2309737967U, 31) == 3302352631U);
 
+  ASSERT (rotr32 (2309737967U, 0) == 2309737967U);
   ASSERT (rotr32 (2309737967U, 1) == 3302352631lU);
   ASSERT (rotr32 (2309737967U, 2) == 3798659963lU);
   ASSERT (rotr32 (2309737967U, 3) == 4046813629lU);
@@ -146,6 +149,7 @@ main (void)
   ASSERT (rotr32 (2309737967U, 31) == 324508639lU);
 
 #ifdef UINT64_MAX
+  ASSERT (rotl64 (16045690984503098046ULL, 0) == 16045690984503098046ULL);
   ASSERT (rotl64 (16045690984503098046ULL, 1) == 13644637895296644477ULL);
   ASSERT (rotl64 (16045690984503098046ULL, 2) == 8842531716883737339ULL);
   ASSERT (rotl64 (16045690984503098046ULL, 3) == 17685063433767474678ULL);
@@ -210,6 +214,7 @@ main (void)
   ASSERT (rotl64 (16045690984503098046ULL, 62) == 13234794782980550319ULL);
   ASSERT (rotl64 (16045690984503098046ULL, 63) == 8022845492251549023ULL);
 
+  ASSERT (rotr64 (16045690984503098046ULL, 0) == 16045690984503098046ULL);
   ASSERT (rotr64 (16045690984503098046ULL, 1) == 8022845492251549023ULL);
   ASSERT (rotr64 (16045690984503098046ULL, 2) == 13234794782980550319ULL);
   ASSERT (rotr64 (16045690984503098046ULL, 3) == 15840769428345050967ULL);
@@ -275,5 +280,27 @@ main (void)
   ASSERT (rotr64 (16045690984503098046ULL, 63) == 13644637895296644477ULL);
 #endif /* UINT64_MAX */
 
+  /* Hack ahead because GCC does not provide a way to initialize uint128_t */
+  /* https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html              */
+  #if __SIZEOF_INT128__ >= 16
+  {
+    const __uint128_t v  = (((__uint128_t)(0xffffffffffffffffULL)) << 64) | 0x00ffffffffffff00ULL;
+    const __uint128_t xl = v;
+    const __uint128_t xr = v;
+
+    ASSERT (rotl128 (v, 0) == xl);
+    ASSERT (rotr128 (v, 0) == xr);
+  }
+
+  {
+    const __uint128_t v  = (((__uint128_t)(0xffffffffffffffffULL)) << 64) | 0x00ffffffffffff00ULL;
+    const __uint128_t xl = (((__uint128_t)(0xffffffffffffff00ULL)) << 64) | 0xffffffffffff00ffULL;
+    const __uint128_t xr = (((__uint128_t)(0x00ffffffffffffffULL)) << 64) | 0xff00ffffffffffffULL;
+
+    ASSERT (rotl128 (v, 8) == xl);
+    ASSERT (rotr128 (v, 8) == xr);
+  }
+  #endif
+
   return 0;
 }

Re: test-bitrotate.c missing test cases

[Bruno Haible]

Hi Jeffrey,

> It looks like test-bitrotate.c is missing test cases. It is missing
> the 32-bit rotl and rotr of 0-bits.
> 
> The 0-bit rotate should tickle undefined behavior.
> 
> If you want to clear the undefined behavior, then use this code. ...

The functions are specified in bitrotate.h, e.g. like this:

/* Given an unsigned 64-bit argument X, return the value corresponding
   to rotating the bits N steps to the left.  N must be between 1 and
   63 inclusive. */
BITROTATE_INLINE uint64_t
rotl64 (uint64_t x, int n)

I think it is on purpose that N = 0 and N = 64 are not allowed. Namely,
when N = 0 or N = 64, you would have a different, more efficient code
branch anyway.

> It will be compiled down to a single instruction on platforms like IA-32.

Yes, this is the intent. And we should help the compiler produce good
code, for example by adding statements like
   assume (n > 0 && n < 64);
Allowing N = 0 or N = 64 goes backwards, because on some platforms it
will prevent the compiler from choosing the best possible instruction.

Bruno

Re: test-bitrotate.c missing test cases

[Jeffrey Walton]

On Sun, Mar 29, 2020 at 8:53 AM Bruno Haible <bruno@clisp.org> wrote:
>
> Hi Jeffrey,
>
> > It looks like test-bitrotate.c is missing test cases. It is missing
> > the 32-bit rotl and rotr of 0-bits.
> >
> > The 0-bit rotate should tickle undefined behavior.
> >
> > If you want to clear the undefined behavior, then use this code. ...
>
> The functions are specified in bitrotate.h, e.g. like this:
>
> /* Given an unsigned 64-bit argument X, return the value corresponding
>    to rotating the bits N steps to the left.  N must be between 1 and
>    63 inclusive. */
> BITROTATE_INLINE uint64_t
> rotl64 (uint64_t x, int n)
>
> I think it is on purpose that N = 0 and N = 64 are not allowed. Namely,
> when N = 0 or N = 64, you would have a different, more efficient code
> branch anyway.
>
> > It will be compiled down to a single instruction on platforms like IA-32.
>
> Yes, this is the intent. And we should help the compiler produce good
> code, for example by adding statements like
>    assume (n > 0 && n < 64);
> Allowing N = 0 or N = 64 goes backwards, because on some platforms it
> will prevent the compiler from choosing the best possible instruction.

Forgive my ignorance... No'oping 0 leaks timing information, and
no'oping 64 is undefined behavior. (And in the current implementation
No'oping 0 is also undefined behavior).

Is that what is desired?

I also don't think developers are going to write a rotate like:

    if (n != 0)
        x = rotr32(x, n);

Or maybe, I have never seen a shift or rotate written like that.

Jeff

Re: test-bitrotate.c missing test cases

[Bruno Haible]

Jeffrey,

> Forgive my ignorance... No'oping 0 leaks timing information

There are only few algorithms where leaking timing information is an
issue. For most of the code we deal with, the developer wants to get
optimal performance.

> I also don't think developers are going to write a rotate like:
> 
>     if (n != 0)
>         x = rotr32(x, n);

Sure they will. Here's an example from lib/vasnprintf.c, where a shift
count of 0 is treated specially:


      /* Copy a, shifting it left by s bits, yields r.
         Memory layout:
         At the beginning: r = roomptr[0..a_len],
         at the end: r = roomptr[0..b_len-1], q = roomptr[b_len..a_len]  */
      r_ptr = roomptr;
      if (s == 0)
        {
          memcpy (r_ptr, a_ptr, a_len * sizeof (mp_limb_t));
          r_ptr[a_len] = 0;
        }
      else
        {
          const mp_limb_t *sourceptr = a_ptr;
          mp_limb_t *destptr = r_ptr;
          mp_twolimb_t accu = 0;
          size_t count;
          for (count = a_len; count > 0; count--)
            {
              accu += (mp_twolimb_t) *sourceptr++ << s;
              *destptr++ = (mp_limb_t) accu;
              accu = accu >> GMP_LIMB_BITS;
            }
          *destptr++ = (mp_limb_t) accu;
        }


Bruno

Re: test-bitrotate.c missing test cases

[Jeffrey Walton]

On Sun, Mar 29, 2020 at 11:40 AM Bruno Haible <bruno@clisp.org> wrote:
>
> Jeffrey,
>
> > Forgive my ignorance... No'oping 0 leaks timing information
>
> There are only few algorithms where leaking timing information is an
> issue. For most of the code we deal with, the developer wants to get
> optimal performance.
>
> > I also don't think developers are going to write a rotate like:
> >
> >     if (n != 0)
> >         x = rotr32(x, n);
>
> Sure they will. Here's an example from lib/vasnprintf.c, where a shift
> count of 0 is treated specially:
>
>
>       /* Copy a, shifting it left by s bits, yields r.
>          Memory layout:
>          At the beginning: r = roomptr[0..a_len],
>          at the end: r = roomptr[0..b_len-1], q = roomptr[b_len..a_len]  */
>       r_ptr = roomptr;
>       if (s == 0)
>         {
>           memcpy (r_ptr, a_ptr, a_len * sizeof (mp_limb_t));
>           r_ptr[a_len] = 0;
>         }
>       else
>         {
>           const mp_limb_t *sourceptr = a_ptr;
>           mp_limb_t *destptr = r_ptr;
>           mp_twolimb_t accu = 0;
>           size_t count;
>           for (count = a_len; count > 0; count--)
>             {
>               accu += (mp_twolimb_t) *sourceptr++ << s;
>               *destptr++ = (mp_limb_t) accu;
>               accu = accu >> GMP_LIMB_BITS;
>             }
>           *destptr++ = (mp_limb_t) accu;
>         }

Let me try again.

The C standard says a shift and rotate is well defined over [0, N-1]
inclusive. 0 is _not_ undefined, and N is undefined.

The current rotate does not provide an implementation that abstracts
the C standard. It has undefined behavior for the element 0. It
requires special handling of element 0 which introduces a branch. (The
current implementation does not even do that; it pushes the
technological debt onto users). The current implementation makes
spurious claims about N being well defined when it is not; it is
clearly undefined behavior.

The current rotate is not portable; in fact it is dangerous. Folks
using it have been merely getting lucky because the implementation
cannot guarantee a rotate of N will not be removed by the compiler.
Looking at the self tests, luck ran out on a rotate of 0. The current
rotate could not pass a complete set of self tests.

The updated implementation provides a complete abstraction of the C
standard by providing a means to rotate over [0, N-1] without
branches. According to the Clang, GCC and ICC compiler teams, the
pattern used by the updated implementation is recognized by the
compiler and will be compiled down to 1 rotate instruction when the
hardware supports it.

There is no risk with the updated implementation. There is
considerable risk with the existing implementation. In fact, the fact
that the existing implementation omits tests cases for element 0
should tell you how broken the current implementation is. The current
implementation does not work in practice.

Jeff