[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: bitrotate
From: |
Simon Josefsson |
Subject: |
Re: bitrotate |
Date: |
Mon, 01 Sep 2008 09:29:02 +0200 |
User-agent: |
Gnus/5.110011 (No Gnus v0.11) Emacs/22.2 (gnu/linux) |
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
- Re: bitrotate,
Simon Josefsson <=
- Re: bitrotate, Paolo Bonzini, 2008/09/01
- Re: bitrotate, Bruno Haible, 2008/09/01
- Re: bitrotate, Simon Josefsson, 2008/09/01
- Re: bitrotate, Simon Josefsson, 2008/09/01
- Re: bitrotate, Ben Pfaff, 2008/09/01
- Re: bitrotate, Bruno Haible, 2008/09/01
- Re: bitrotate, Simon Josefsson, 2008/09/02
- Re: bitrotate, Eric Blake, 2008/09/02
- Re: bitrotate, Simon Josefsson, 2008/09/02