Re: bitrotate

[Simon Josefsson]

Paolo Bonzini <address@hidden> writes:

>> +/* 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. */
>> +static inline uint16_t
>> +rotl16 (uint16_t x, int n)
>> +{
>> +  return ((x << n) | (x >> (16 - n))) & 0xFFFFFFFF;
>> +}
>
> & 0xFFFF;

Thanks, fixed below.

> I'd also double-check at least on i686-pc-linux-gnu that GCC does
> generate ro{l,r}{w,l} instructions.

Hm, I tried to do this, but the computations in the self tests appears
to be computed at compile-time...  I tried a simpler code:

#include <bitrotate.h>
#include <stdio.h>
int main (int argc, char *argv[]) {
  uint16_t l = atoi(argv[1]);
  uint16_t o = rotl16(l,2);

  printf ("%s << 2 = %d\n", argv[1], o);
}

But the assembler output doesn't contain the rolw instruction:

address@hidden:~$ gcc -O2 -S foo.c -Isrc/gnulib/lib

main:
        leal    4(%esp), %ecx
        andl    $-16, %esp
        pushl   -4(%ecx)
        pushl   %ebp
        movl    %esp, %ebp
        subl    $24, %esp
        movl    %ecx, -8(%ebp)
        movl    %ebx, -4(%ebp)
        movl    4(%ecx), %ebx
        movl    4(%ebx), %eax
        movl    %eax, (%esp)
        call    atoi
        movzwl  %ax, %eax
        movl    %eax, %edx
        sarl    $14, %edx
        sall    $2, %eax
        orl     %eax, %edx
        movzwl  %dx, %edx
        movl    %edx, 8(%esp)
        movl    4(%ebx), %eax
        movl    $.LC0, (%esp)
        movl    %eax, 4(%esp)
        call    printf
        movl    -8(%ebp), %ecx
        movl    -4(%ebp), %ebx
        movl    %ebp, %esp
        popl    %ebp
        leal    -4(%ecx), %esp
        ret

I suspect the rotation part is the sarl+sall and or.  Either we could
experiment with changing the code, or we could try to make gcc detect
that this code actually is a rotate...  Possibly gcc already does that
right thing, with today's CPU architectures it can be difficult to know
which ops are the most efficient choice.

Bruno Haible <address@hidden> writes:

> Ben Pfaff wrote:
>> Since you're using the inline keyword, you should add a
>> dependency on the inline module.
>
> He's only using 'static inline'; therefore an AC_REQUIRE([AC_C_INLINE])
> is all that he needs.

Thanks, added below.

>> > +/* 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
>> > +   31 inclusive. */
>> > +static inline uint32_t
>> > +rotl32 (uint32_t x, int n)
>> > +{
>> > +  return ((x << n) | (x >> (32 - n))) & 0xFFFFFFFF;
>> > +}
>> 
>> There is no benefit to the bitwise "and" operation: a uint32_t is
>> guaranteed to have exactly 32 bits, so the conversion implied by
>> the return statement will trim off any high bits.
>
> The '& 0xFFFFFFFF' serves the purpose of clarity. When I copy & paste
> an expression from one file to another, the editor that I'm using does not
> copy the implicit conversion in the form of a cast. Since relying on
> implicit casts of return values is quite rare, I would overlook it in such
> a situation.

I tend to agree, but not strongly.  I kept it as is for now.

Bruno Haible <address@hidden> writes:

> Simon Josefsson wrote:
>> +
>> +#include <stdint.h>
>> +
>
> The module description needs to list the dependency to the 'stdint' module.

Thanks, added too.

/Simon

>From 69009347e0a41249758f65c498c16cf5a2564d8f Mon Sep 17 00:00:00 2001
From: Simon Josefsson <address@hidden>
Date: Mon, 1 Sep 2008 09:27:04 +0200
Subject: [PATCH] Fix bitrotate module.

---
 ChangeLog         |   10 ++++++++++
 lib/bitrotate.h   |    4 ++--
 modules/bitrotate |    3 ++-
 3 files changed, 14 insertions(+), 3 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index c4682c9..d085060 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2008-09-01  Simon Josefsson  <address@hidden>
+
+       * modules/bitrotate (configure.ac): Need
+       AC_REQUIRE([AC_C_INLINE]).
+       (Description): Mention stdint.h.  Reported by Bruno Haible
+       <address@hidden>.
+
+       * lib/bitrotate.h (rotr16, rotl16): Fix mask value.  Reported by
+       Paolo Bonzini <address@hidden>.
+
 2008-08-31  Bruno Haible  <address@hidden>
 
        Assume Solaris specific bi-arch conventions on Solaris systems.
diff --git a/lib/bitrotate.h b/lib/bitrotate.h
index f3b6a66..8123a5c 100644
--- a/lib/bitrotate.h
+++ b/lib/bitrotate.h
@@ -45,7 +45,7 @@ rotr32 (uint32_t x, int n)
 static inline uint16_t
 rotl16 (uint16_t x, int n)
 {
-  return ((x << n) | (x >> (16 - n))) & 0xFFFFFFFF;
+  return ((x << n) | (x >> (16 - n))) & 0xFFFF;
 }
 
 /* Given an unsigned 16-bit argument X, return the value corresponding
@@ -54,7 +54,7 @@ rotl16 (uint16_t x, int n)
 static inline uint16_t
 rotr16 (uint16_t x, int n)
 {
-  return ((x >> n) | (x << (16 - n))) & 0xFFFFFFFF;
+  return ((x >> n) | (x << (16 - n))) & 0xFFFF;
 }
 
 #endif /* _GL_BITROTATE_H */
diff --git a/modules/bitrotate b/modules/bitrotate
index df94a61..064519c 100644
--- a/modules/bitrotate
+++ b/modules/bitrotate
@@ -1,5 +1,5 @@
 Description:
-Rotate bits in 16 and 32 bit integers.
+Rotate bits in 16 and 32 bit integers using stdint.h.
 
 Files:
 lib/bitrotate.h
@@ -7,6 +7,7 @@ lib/bitrotate.h
 Depends-on:
 
 configure.ac:
+AC_REQUIRE([AC_C_INLINE])
 
 Makefile.am:
 lib_SOURCES += bitrotate.h
-- 
1.5.6.3