Re: test-bitrotate.c missing test cases

[Jeffrey Walton <noloader@gmail.com>]

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