Re: [PATCH 1/12] random pt4: Create new rol32/ror32 bitops

Re: [PATCH 1/12] random pt4: Create new rol32/ror32 bitops

[Chuck Ebbert]

On Sat, 22 Jan 2005 at 20:13:24 -0800 Matt Mackall wrote:

> So I think tweaks for x86 at least are unnecessary. 

 So the compiler looks for that specific sequence of instructions:

        (a << b) | (a >> (sizeof(a) * 8 - b)

and recognizes that it means rotation?  Wow.


Chuck

Re: [PATCH 1/12] random pt4: Create new rol32/ror32 bitops

[H. Peter Anvin]

Followup to:  <200501230247_MC3-1-93FA-7A4E@compuserve.com>
By author:    Chuck Ebbert <76306.1226@compuserve.com>
In newsgroup: linux.dev.kernel
>
> On Sat, 22 Jan 2005 at 20:13:24 -0800 Matt Mackall wrote:
> 
> > So I think tweaks for x86 at least are unnecessary. 
> 
>  So the compiler looks for that specific sequence of instructions:
> 
>         (a << b) | (a >> (sizeof(a) * 8 - b)
> 
> and recognizes that it means rotation?  Wow.
> 

You know, there is a LOT of instructions like that.  x86 has a single
instruction to do:

	a = b + (c << 3) + 3600;

(Assuming a, b and c are in eax, ebx, and ecx, respecively, the
instruction is "leal 3600(%ebx,%ecx,3),%eax".)

The C compiler really needs to recognize these kinds of idioms, not
just in the source, but that occur natually as a result of code
generation and optimizations.  The compiler lingo for this is
"peephole optimization."

	-hpa

Re: [PATCH 1/12] random pt4: Create new rol32/ror32 bitops

[Chuck Ebbert]

On Fri, 21 Jan 2005 at 15:41:06 -0600 Matt Mackall wrote:

> Add rol32 and ror32 bitops to bitops.h

Can you test this patch on top of yours?  I did it on 2.6.10-ac10 but it
should apply OK.  Compile tested and booted, but only random.c is using it
in my kernel.

x86-64 could use this too...

Add i386 bitops for rol32/ror32:
Signed-off-by: Chuck Ebbert <76306.1226@compuserve.com>

--- 2.6.10-ac10/include/linux/bitops.h~orig     2005-01-22 11:31:20.130239000 -0500
+++ 2.6.10-ac10/include/linux/bitops.h  2005-01-22 11:34:55.740239000 -0500
@@ -129,6 +129,7 @@
        return sizeof(w) == 4 ? generic_hweight32(w) : generic_hweight64(w);
 }
 
+#ifndef __HAVE_ARCH_ROTATE_32
 /*
  * rol32 - rotate a 32-bit value left
  *
@@ -150,5 +151,6 @@
 {
        return (word >> shift) | (word << (32 - shift));
 }
+#endif /* ndef __HAVE_ARCH_ROTATE_32 */
 
 #endif
--- 2.6.10-ac10/include/asm-i386/bitops.h~orig  2004-08-24 05:08:39.000000000 -0400
+++ 2.6.10-ac10/include/asm-i386/bitops.h       2005-01-22 11:42:12.010239000 -0500
@@ -431,6 +431,41 @@
 #define hweight16(x) generic_hweight16(x)
 #define hweight8(x) generic_hweight8(x)
 
+#define __HAVE_ARCH_ROTATE_32
+/*
+ * rol32 - rotate a 32-bit value left
+ *
+ * @word: value to rotate
+ * @shift: bits to roll
+ */
+static inline __u32 rol32(__u32 word, int shift)
+{
+       __u32 res;
+
+       asm("roll %%cl,%0"
+           : "=r" (res)
+           : "0" (word), "c" (shift)
+           : "cc");
+       return res;
+}
+
+/*
+ * ror32 - rotate a 32-bit value right
+ *
+ * @word: value to rotate
+ * @shift: bits to roll
+ */
+static inline __u32 ror32(__u32 word, int shift)
+{
+       __u32 res;
+
+       asm("rorl %%cl,%0"
+           : "=r" (res)
+           : "0" (word), "c" (shift)
+           : "cc");
+       return res;
+}
+
 #endif /* __KERNEL__ */
 
 #ifdef __KERNEL__

Chuck

Re: [PATCH 1/12] random pt4: Create new rol32/ror32 bitops

[Matt Mackall]

On Sat, Jan 22, 2005 at 09:10:40PM -0500, Chuck Ebbert wrote:
> On Fri, 21 Jan 2005 at 15:41:06 -0600 Matt Mackall wrote:
> 
> > Add rol32 and ror32 bitops to bitops.h
> 
> Can you test this patch on top of yours?  I did it on 2.6.10-ac10 but it
> should apply OK.  Compile tested and booted, but only random.c is using it
> in my kernel.

If I recall correctly from my testing of this about a year ago,
compilers were already generating the appropriate rol/ror
instructions. Have you checked the disassembly and found it wanting?

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 1/12] random pt4: Create new rol32/ror32 bitops

[Andi Kleen]

On Sat, Jan 22, 2005 at 09:10:40PM -0500, Chuck Ebbert wrote:
> On Fri, 21 Jan 2005 at 15:41:06 -0600 Matt Mackall wrote:
> 
> > Add rol32 and ror32 bitops to bitops.h
> 
> Can you test this patch on top of yours?  I did it on 2.6.10-ac10 but it
> should apply OK.  Compile tested and booted, but only random.c is using it
> in my kernel.

Does random really use variable rotates? For constant rotates 
gcc detects the usual C idiom and turns it transparently into
the right machine instruction.

If that's the case I would use it because it'll avoid some messy 
code everywhere.

-Andi

Re: [PATCH 1/12] random pt4: Create new rol32/ror32 bitops

[Matt Mackall]

On Sun, Jan 23, 2005 at 04:19:21AM +0100, Andi Kleen wrote:
> On Sat, Jan 22, 2005 at 09:10:40PM -0500, Chuck Ebbert wrote:
> > On Fri, 21 Jan 2005 at 15:41:06 -0600 Matt Mackall wrote:
> > 
> > > Add rol32 and ror32 bitops to bitops.h
> > 
> > Can you test this patch on top of yours?  I did it on 2.6.10-ac10 but it
> > should apply OK.  Compile tested and booted, but only random.c is using it
> > in my kernel.
> 
> Does random really use variable rotates? For constant rotates 
> gcc detects the usual C idiom and turns it transparently into
> the right machine instruction.

Nope, random doesn't. The only thing I converted in my sweep that did
were CAST5 and CAST6, which are fairly unique in doing key-based
rotations. On the other hand:

typedef unsigned int __u32;

static inline __u32 rol32(__u32 word, int shift)
{
        return (word << shift) | (word >> (32 - shift));
}

int foo(int val, int rot)
{
        return rol32(val, rot);
}

With 2.95:

   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   8b 4d 0c                mov    0xc(%ebp),%ecx
   6:   8b 45 08                mov    0x8(%ebp),%eax
   9:   d3 c0                   rol    %cl,%eax
   b:   c9                      leave
   c:   c3                      ret

With 3.3.5:

   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   8b 45 08                mov    0x8(%ebp),%eax
   6:   8b 4d 0c                mov    0xc(%ebp),%ecx
   9:   5d                      pop    %ebp
   a:   d3 c0                   rol    %cl,%eax
   c:   c3                      ret

With gcc-snapshot:

   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   8b 45 08                mov    0x8(%ebp),%eax
   6:   8b 4d 0c                mov    0xc(%ebp),%ecx
   9:   d3 c0                   rol    %cl,%eax
   b:   5d                      pop    %ebp
   c:   c3                      ret

So I think tweaks for x86 at least are unnecessary. 

-- 
Mathematics is the supreme nostalgia of our time.

[PATCH 0/12] random pt4: Moving and sharing code

[Matt Mackall]

This series focuses on moving and sharing code in
/drivers/char/random.c. It applies on top of -mm2 which contains my
earlier patches.

New bitop:
1  Create new rol32/ror32 bitops
2  Use them throughout the tree

Share SHA code in lib:
3  Kill the SHA1 variants
4  Cleanup SHA1 interface
5  Move SHA1 code to lib/
6  Replace SHA1 with faster version
7  Update cryptolib to use SHA1 from lib

Share halfmd4 hash:
8  Move halfMD4 to lib
9  Kill duplicate halfMD4 in ext3 htree

Move network random bits:
10 Simplify and shrink syncookie code
11 Move syncookies to net/
12 Move other tcp/ip bits to net/

[PATCH 1/12] random pt4: Create new rol32/ror32 bitops

[Matt Mackall]

Add rol32 and ror32 bitops to bitops.h

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: rnd2/drivers/char/random.c
===================================================================
--- rnd2.orig/drivers/char/random.c	2005-01-19 22:59:59.000000000 -0800
+++ rnd2/drivers/char/random.c	2005-01-20 09:18:47.000000000 -0800
@@ -374,11 +374,6 @@
 static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
 static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
 
-static inline __u32 rol32(__u32 word, int shift)
-{
-	return (word << shift) | (word >> (32 - shift));
-}
-
 #if 0
 static int debug = 0;
 module_param(debug, bool, 0644);
Index: rnd2/include/linux/bitops.h
===================================================================
--- rnd2.orig/include/linux/bitops.h	2005-01-19 22:57:54.000000000 -0800
+++ rnd2/include/linux/bitops.h	2005-01-20 09:20:24.641660815 -0800
@@ -134,4 +134,26 @@
 	return sizeof(w) == 4 ? generic_hweight32(w) : generic_hweight64(w);
 }
 
+/*
+ * rol32 - rotate a 32-bit value left
+ *
+ * @word: value to rotate
+ * @shift: bits to roll
+ */
+static inline __u32 rol32(__u32 word, int shift)
+{
+	return (word << shift) | (word >> (32 - shift));
+}
+
+/*
+ * ror32 - rotate a 32-bit value right
+ *
+ * @word: value to rotate
+ * @shift: bits to roll
+ */
+static inline __u32 ror32(__u32 word, int shift)
+{
+	return (word >> shift) | (word << (32 - shift));
+}
+
 #endif

Re: [PATCH 1/12] random pt4: Create new rol32/ror32 bitops

[Denis Vlasenko]

On Friday 21 January 2005 23:41, Matt Mackall wrote:
> --- rnd2.orig/include/linux/bitops.h	2005-01-19 22:57:54.000000000 -0800
> +++ rnd2/include/linux/bitops.h	2005-01-20 09:20:24.641660815 -0800
> @@ -134,4 +134,26 @@
>  	return sizeof(w) == 4 ? generic_hweight32(w) : generic_hweight64(w);
>  }
>  
> +/*
> + * rol32 - rotate a 32-bit value left
> + *
> + * @word: value to rotate
> + * @shift: bits to roll
> + */
> +static inline __u32 rol32(__u32 word, int shift)
> +{
> +	return (word << shift) | (word >> (32 - shift));
> +}
> +
> +/*
> + * ror32 - rotate a 32-bit value right
> + *
> + * @word: value to rotate
> + * @shift: bits to roll
> + */
> +static inline __u32 ror32(__u32 word, int shift)
> +{
> +	return (word >> shift) | (word << (32 - shift));
> +}
> +
>  #endif

gcc generates surprisingly good assembly for this,
I coudn't beat it for 32bit rotations. Cool!

So you are absolutely right here with not trying
to asm optimize it.

OTOH 64bit gcc rol is worse.
--
vda