Add optimized SHA-1 implementations for x86 and x86_64

The following 3-part series adds assembly implementations of the SHA-1 transform for x86 and x86_64. For x86_64 the optimized code is always selected; on x86 it is selected if the kernel is compiled for i486 or above (since the code needs BSWAP). These changes primarily improve the performance of the CryptoAPI SHA-1 module and of /dev/urandom. I've included some performance data from my test boxes below.

This version incorporates feedback from Herbert Xu. Andrew, I'm sending this to you because of the (admittedly tiny) intersection with arm and s390 in part 1.

-

tcrypt performance tests:

=== Pentium IV in 32-bit mode, average of 5 trials ===

Test#  Bytes/  Bytes/  Cyc/B  Cyc/B  Change
        block  update    (C)  (asm)
    0      16      16    229    114     50%
    1      64      16    142     76     46%
    2      64      64     79     35     56%
    3     256      16     59     34     42%
    4     256      64     44     24     45%
    5     256     256     43     17     60%
    6    1024      16     51     36     29%
    7    1024     256     30     13     57%
    8    1024    1024     28     12     57%
    9    2048      16     66     30     55%
   10    2048     256     31     12     61%
   11    2048    1024     27     13     52%
   12    2048    2048     26     13     50%
   13    4096      16     49     30     39%
   14    4096     256     28     12     57%
   15    4096    1024     28     11     61%
   16    4096    4096     26     13     50%
   17    8192      16     49     29     41%
   18    8192     256     27     11     59%
   19    8192    1024     26     11     58%
   20    8192    4096     25     10     60%
   21    8192    8192     25     10     60%

=== Intel Core 2 in 64-bit mode, average of 5 trials ===

Test#  Bytes/  Bytes/  Cyc/B  Cyc/B  Change
        block  update    (C)  (asm)
    0      16      16    112     81     28%
    1      64      16     55     39     29%
    2      64      64     42     27     36%
    3     256      16     35     25     29%
    4     256      64     24     14     42%
    5     256     256     22     12     45%
    6    1024      16     31     22     29%
    7    1024     256     17      9     47%
    8    1024    1024     16      9     44%
    9    2048      16     30     22     27%
   10    2048     256     16      8     50%
   11    2048    1024     16      8     50%
   12    2048    2048     16      8     50%
   13    4096      16     29     21     28%
   14    4096     256     16      8     50%
   15    4096    1024     15      8     47%
   16    4096    4096     15      7     53%
   17    8192      16     29     22     24%
   18    8192     256     16      8     50%
   19    8192    1024     15      7     53%
   20    8192    4096     15      7     53%
   21    8192    8192     15      7     53%

I've also done informal tests on other boxes, and the performance improvement has been in the same ballpark.

On the aforementioned Pentium IV, /dev/urandom throughput goes from 3.7 MB/s to 5.6 MB/s with the patches; on the Core 2, it increases from 5.5 MB/s to 8.1 MB/s.

Make sha_init() a static inline in cryptohash.h rather than an (unexported) function in lib/sha1.c, in preparation for making sha1.c optional. This also allows some cleanups:

- Modular code can now use sha_init() rather than reimplementing it

- The optimized implementation of SHA-1 for ARM no longer needs to reimplement sha_init() in assembly

---

 arch/arm/lib/sha1.S          |   16 ----------------
 arch/s390/crypto/sha1_s390.c |    6 +-----
 drivers/crypto/padlock-sha.c |    8 ++------
 include/linux/cryptohash.h   |   14 +++++++++++++-
 lib/sha1.c                   |   14 --------------
 5 files changed, 16 insertions(+), 42 deletions(-)

index ff6ece4..5be800c 100644
@@ -188,19 +188,3 @@ ENTRY(sha_transform)
 .L_sha_K:
 	.word	0x5a827999, 0x6ed9eba1, 0x8f1bbcdc, 0xca62c1d6
 
-
-/*
- * void sha_init(__u32 *buf)
- */
-
-.L_sha_initial_digest:
-	.word	0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476, 0xc3d2e1f0
-
-ENTRY(sha_init)
-
-	str	lr, [sp, #-4]!
-	adr	r1, .L_sha_initial_digest
-	ldmia	r1, {r1, r2, r3, ip, lr}
-	stmia	r0, {r1, r2, r3, ip, lr}
-	ldr	pc, [sp], #4
-

index af4460e..fed9a2e 100644
@@ -42,11 +42,7 @@ static void sha1_init(struct crypto_tfm *tfm)
 {
 	struct s390_sha1_ctx *sctx = crypto_tfm_ctx(tfm);
 
-	sctx->state[0] = 0x67452301;
-	sctx->state[1] = 0xEFCDAB89;
-	sctx->state[2] = 0x98BADCFE;
-	sctx->state[3] = 0x10325476;
-	sctx->state[4] = 0xC3D2E1F0;
+	sha_init(sctx->state);
 	sctx->count = 0;
 }
 

index a781fd2..b47d708 100644
@@ -107,12 +107,8 @@ static void padlock_do_sha1(const char *in, char *out, int count)
 	char buf[128+16];
 	char *result = NEAREST_ALIGNED(buf);
 
-	((uint32_t *)result)[0] = 0x67452301;
-	((uint32_t *)result)[1] = 0xEFCDAB89;
-	((uint32_t *)result)[2] = 0x98BADCFE;
-	((uint32_t *)result)[3] = 0x10325476;
-	((uint32_t *)result)[4] = 0xC3D2E1F0;
- 
+	sha_init((uint32_t *)result);
+
 	asm volatile (".byte 0xf3,0x0f,0xa6,0xc8" /* rep xsha1 */
 		      : "+S"(in), "+D"(result)
 		      : "c"(count), "a"(0));

index c118b2a..a172401 100644
@@ -4,7 +4,19 @@
 #define SHA_DIGEST_WORDS 5
 #define SHA_WORKSPACE_WORDS 80
 
-void sha_init(__u32 *buf);
+/**
+ * sha_init - initialize the vectors for a SHA1 digest
+ * @buf: vector to initialize
+ */
+static inline void sha_init(__u32 *buf)
+{
+	buf[0] = 0x67452301;
+	buf[1] = 0xefcdab89;
+	buf[2] = 0x98badcfe;
+	buf[3] = 0x10325476;
+	buf[4] = 0xc3d2e1f0;
+}
+
 void sha_transform(__u32 *digest, const char *data, __u32 *W);
 
 __u32 half_md4_transform(__u32 buf[4], __u32 const in[8]);

index 4c45fd5..815816f 100644
@@ -79,17 +79,3 @@ void sha_transform(__u32 *digest, const char *in, __u32 *W)
 	digest[4] += e;
 }
 EXPORT_SYMBOL(sha_transform);
-
-/**
- * sha_init - initialize the vectors for a SHA1 digest
- * @buf: vector to initialize
- */
-void sha_init(__u32 *buf)
-{
-	buf[0] = 0x67452301;
-	buf[1] = 0xefcdab89;
-	buf[2] = 0x98badcfe;
-	buf[3] = 0x10325476;
-	buf[4] = 0xc3d2e1f0;
-}
-

Add x86-optimized implementation of the SHA-1 hash function, taken from Nettle under the LGPL. This code will be enabled on kernels compiled for 486es or better; kernels which support 386es will use the generic implementation (since we need BSWAP).

We disable building lib/sha1.o when an optimized implementation is available, as the library link order for x86 (and x86_64) would otherwise ignore the optimized version. The existing optimized implementation for ARM does not do this; the library link order for that architecture appears to favor the arch/arm/ version automatically. I've left this situation alone since I'm not familiar with the ARM code, but a !ARM condition could be added to CONFIG_SHA1_GENERIC if it makes sense.

The code has been tested with tcrypt and the NIST test vectors.

---

 arch/i386/kernel/i386_ksyms.c |    5 +
 arch/i386/lib/Makefile        |    1 
 arch/i386/lib/sha1.S          |  299 +++++++++++++++++++++++++++++++++++++++++
 include/linux/cryptohash.h    |    9 +
 lib/Kconfig                   |   13 ++
 lib/Makefile                  |    3 
 6 files changed, 328 insertions(+), 2 deletions(-)

index e3d4b73..812bc4e 100644
@@ -1,4 +1,5 @@
 #include <linux/module.h>
+#include <linux/cryptohash.h>
 #include <asm/checksum.h>
 #include <asm/desc.h>
 

@@ -28,3 +29,7 @@ EXPORT_SYMBOL(__read_lock_failed);
 #endif
 
 EXPORT_SYMBOL(csum_partial);
+
+#ifdef CONFIG_SHA1_X86
+EXPORT_SYMBOL(sha_transform);
+#endif

index 22d8ac5..69f4845 100644
@@ -6,6 +6,7 @@
 lib-y = checksum.o delay.o usercopy.o getuser.o putuser.o memcpy.o strstr.o \
 	bitops.o semaphore.o
 
+lib-$(CONFIG_SHA1_X86) += sha1.o
 lib-$(CONFIG_X86_USE_3DNOW) += mmx.o
 
 obj-$(CONFIG_SMP)	+= msr-on-cpu.o

index a172401..0da331c 100644
@@ -1,8 +1,15 @@
 #ifndef __CRYPTOHASH_H
 #define __CRYPTOHASH_H
 
+#include <linux/linkage.h>
+
 #define SHA_DIGEST_WORDS 5
+
+#if defined(CONFIG_SHA1_X86)
+#define SHA_WORKSPACE_WORDS 0
+#else
 #define SHA_WORKSPACE_WORDS 80
+#endif
 
 /**
  * sha_init - initialize the vectors for a SHA1 digest

@@ -17,7 +24,7 @@ static inline void sha_init(__u32 *buf)
 	buf[4] = 0xc3d2e1f0;
 }
 
-void sha_transform(__u32 *digest, const char *data, __u32 *W);
+asmlinkage void sha_transform(__u32 *digest, const char *data, __u32 *W);
 
 __u32 half_md4_transform(__u32 buf[4], __u32 const in[8]);
 

index 2e7ae6b..69fdb64 100644
@@ -124,4 +124,17 @@ config HAS_DMA
 	depends on !NO_DMA
 	default y
 
+#
+# Optimized SHA-1 support is autoconfigured
+#
+config SHA1_X86
+	bool
+	depends on (X86 || UML_X86) && !64BIT && X86_BSWAP
+	default y
+
+config SHA1_GENERIC
+	bool
+	depends on !SHA1_X86
+	default y
+
 endmenu

index c8c8e20..f67be29 100644
@@ -5,10 +5,11 @@
 lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 rbtree.o radix-tree.o dump_stack.o \
 	 idr.o int_sqrt.o bitmap.o extable.o prio_tree.o \
-	 sha1.o irq_regs.o reciprocal_div.o
+	 irq_regs.o reciprocal_div.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o
+lib-$(CONFIG_SHA1_GENERIC) += sha1.o
 
 lib-y	+= kobject.o kref.o kobject_uevent.o klist.o
 

Whoops, I had thought I had gotten that right. I'll get updates for parts 2 and 3 sent out on Monday.

Thanks
--Benjamin Gilbert

I'm sending the corrected parts 2 and 3 as replies to this email. The UTF-8 fix is the *only* thing that has changed. The patches themselves are moot in their current form, but I wanted to make sure they were archived with the correct attribution.

--Benjamin Gilbert

Add x86-optimized implementation of the SHA-1 hash function, taken from Nettle under the LGPL. This code will be enabled on kernels compiled for 486es or better; kernels which support 386es will use the generic implementation (since we need BSWAP).

We disable building lib/sha1.o when an optimized implementation is available, as the library link order for x86 (and x86_64) would otherwise ignore the optimized version. The existing optimized implementation for ARM does not do this; the library link order for that architecture appears to favor the arch/arm/ version automatically. I've left this situation alone since I'm not familiar with the ARM code, but a !ARM condition could be added to CONFIG_SHA1_GENERIC if it makes sense.

The code has been tested with tcrypt and the NIST test vectors.

---

 arch/i386/kernel/i386_ksyms.c |    5 +
 arch/i386/lib/Makefile        |    1 
 arch/i386/lib/sha1.S          |  299 +++++++++++++++++++++++++++++++++++++++++
 include/linux/cryptohash.h    |    9 +
 lib/Kconfig                   |   13 ++
 lib/Makefile                  |    3 
 6 files changed, 328 insertions(+), 2 deletions(-)

index e3d4b73..812bc4e 100644
@@ -1,4 +1,5 @@
 #include <linux/module.h>
+#include <linux/cryptohash.h>
 #include <asm/checksum.h>
 #include <asm/desc.h>
 

@@ -28,3 +29,7 @@ EXPORT_SYMBOL(__read_lock_failed);
 #endif
 
 EXPORT_SYMBOL(csum_partial);
+
+#ifdef CONFIG_SHA1_X86
+EXPORT_SYMBOL(sha_transform);
+#endif

index 22d8ac5..69f4845 100644
@@ -6,6 +6,7 @@
 lib-y = checksum.o delay.o usercopy.o getuser.o putuser.o memcpy.o strstr.o \
 	bitops.o semaphore.o
 
+lib-$(CONFIG_SHA1_X86) += sha1.o
 lib-$(CONFIG_X86_USE_3DNOW) += mmx.o
 
 obj-$(CONFIG_SMP)	+= msr-on-cpu.o

index a172401..0da331c 100644
@@ -1,8 +1,15 @@
 #ifndef __CRYPTOHASH_H
 #define __CRYPTOHASH_H
 
+#include <linux/linkage.h>
+
 #define SHA_DIGEST_WORDS 5
+
+#if defined(CONFIG_SHA1_X86)
+#define SHA_WORKSPACE_WORDS 0
+#else
 #define SHA_WORKSPACE_WORDS 80
+#endif
 
 /**
  * sha_init - initialize the vectors for a SHA1 digest

@@ -17,7 +24,7 @@ static inline void sha_init(__u32 *buf)
 	buf[4] = 0xc3d2e1f0;
 }
 
-void sha_transform(__u32 *digest, const char *data, __u32 *W);
+asmlinkage void sha_transform(__u32 *digest, const char *data, __u32 *W);
 
 __u32 half_md4_transform(__u32 buf[4], __u32 const in[8]);
 

index 2e7ae6b..69fdb64 100644
@@ -124,4 +124,17 @@ config HAS_DMA
 	depends on !NO_DMA
 	default y
 
+#
+# Optimized SHA-1 support is autoconfigured
+#
+config SHA1_X86
+	bool
+	depends on (X86 || UML_X86) && !64BIT && X86_BSWAP
+	default y
+
+config SHA1_GENERIC
+	bool
+	depends on !SHA1_X86
+	default y
+
 endmenu

index c8c8e20..f67be29 100644
@@ -5,10 +5,11 @@
 lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 rbtree.o radix-tree.o dump_stack.o \
 	 idr.o int_sqrt.o bitmap.o extable.o prio_tree.o \
-	 sha1.o irq_regs.o reciprocal_div.o
+	 irq_regs.o reciprocal_div.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o
+lib-$(CONFIG_SHA1_GENERIC) += sha1.o
 
 lib-y	+= kobject.o kref.o kobject_uevent.o klist.o
 

Add optimized implementation of the SHA-1 hash function for x86_64, ported from the x86 implementation in Nettle (which is LGPLed).

The code has been tested with tcrypt and the NIST test vectors.

---

 arch/x86_64/kernel/x8664_ksyms.c |    3 
 arch/x86_64/lib/Makefile         |    2 
 arch/x86_64/lib/sha1.S           |  281 ++++++++++++++++++++++++++++++++++++++
 include/linux/cryptohash.h       |    2 
 lib/Kconfig                      |    7 +
 5 files changed, 293 insertions(+), 2 deletions(-)

index 77c25b3..bc641ab 100644
@@ -3,6 +3,7 @@
 
 #include <linux/module.h>
 #include <linux/smp.h>
+#include <linux/cryptohash.h>
 
 #include <asm/semaphore.h>
 #include <asm/processor.h>

@@ -60,3 +61,5 @@ EXPORT_SYMBOL(init_level4_pgt);
 EXPORT_SYMBOL(load_gs_index);
 
 EXPORT_SYMBOL(_proxy_pda);
+
+EXPORT_SYMBOL(sha_transform);

index c943271..6c8110b 100644
@@ -9,5 +9,5 @@ obj-$(CONFIG_SMP)	+= msr-on-cpu.o
 
 lib-y := csum-partial.o csum-copy.o csum-wrappers.o delay.o \
 	usercopy.o getuser.o putuser.o  \
-	thunk.o clear_page.o copy_page.o bitstr.o bitops.o
+	thunk.o clear_page.o copy_page.o bitstr.o bitops.o sha1.o
 lib-y += memcpy.o memmove.o memset.o copy_user.o rwlock.o copy_user_nocache.o

index 0da331c..b3b14a3 100644
@@ -7,6 +7,8 @@
 
 #if defined(CONFIG_SHA1_X86)
 #define SHA_WORKSPACE_WORDS 0
+#elif defined(CONFIG_SHA1_X86_64)
+#define SHA_WORKSPACE_WORDS 16
 #else
 #define SHA_WORKSPACE_WORDS 80
 #endif

index 69fdb64..23a84ed 100644
@@ -132,9 +132,14 @@ config SHA1_X86
 	depends on (X86 || UML_X86) && !64BIT && X86_BSWAP
 	default y
 
+config SHA1_X86_64
+	bool
+	depends on (X86 || UML_X86) && 64BIT
+	default y
+
 config SHA1_GENERIC
 	bool
-	depends on !SHA1_X86
+	depends on !SHA1_X86 && !SHA1_X86_64
 	default y
 
 endmenu

Have you benchmarked this against lib/sha1.c? Please post the results. Until then, I'm frankly skeptical that your unrolled version is faster because when I introduced lib/sha1.c the rolled version therein won by a significant margin and had 1/10th the cache footprint.

Mathematics is the supreme nostalgia of our time.

Yes. And it also depends on the CPU as well. Testing on a server-class x86 CPU (often with bigger L2, and perhaps even L1, cache) will produce different result than from popular but less-capable "value" CPUs.

Jeff

In particular, any optimization made for "486+" CPUs is highly suspect on any machine which runs the core at >1x the memory bus speeds.

Mathematics is the supreme nostalgia of our time.

See the benchmark tables in patch 0 at the head of this thread. Performance improved by at least 25% in every test, and 40-60% was more common for the 32-bit version (on a Pentium IV).

It's not just the loop unrolling; it's the register allocation and spilling. For comparison, I built SHATransform() from the drivers/char/random.c in 2.6.11, using gcc 3.3.5 with -O2 and SHA_CODE_SIZE == 3 (i.e., fully unrolled); I'm guessing this is pretty close to what you tested back then. The resulting code is 49% MOV instructions, and 80% of *those* involve memory. gcc4 is somewhat better, but it still spills a whole lot, both for the 2.6.11 unrolled code and for the current lib/sha1.c.

In contrast, the assembly implementation in this patch only has to go to memory for data and workspace (with one small exception in the F3 rounds), and the workspace has a fifth of the cache footprint of the default implementation.

Good point. I benchmarked the 32-bit assembly code on a couple more boxes:

=== AMD Duron, average of 5 trials ===

Test#  Bytes/  Bytes/  Cyc/B  Cyc/B  Change
        block  update    (C)  (asm)
    0      16      16    104     72     31%
    1      64      16     52     36     31%
    2      64      64     45     29     36%
    3     256      16     33     23     30%
    4     256      64     27     17     37%
    5     256     256     24     14     42%
    6    1024      16     29     20     31%
    7    1024     256     20     11     45%
    8    1024    1024     19     11     42%
    9    2048      16     28     20     29%
   10    2048     256     19     11     42%
   11    2048    1024     18     10     44%
   12    2048    2048     18     10     44%
   13    4096      16     28     19     32%
   14    4096     256     18     10     44%
   15    4096    1024     18     10     44%
   16    4096    4096     18     10     44%
   17    8192      16     27     19     30%
   18    8192     256     18     10     44%
   19    8192    1024     18     10     44%
   20    8192    4096     17     10     41%
   21    8192    8192     17     10     41%

=== Classic Pentium, average of 5 trials ===

Test#  Bytes/  Bytes/  Cyc/B  Cyc/B  Change
        block  update    (C)  (asm)
    0      16      16    145    144      1%
    1      64      16     72     61     15%
    2      64      64     65     52     20%
    3     256      16     46     39     15%
    4     256      64     39     32     18%
    5     256     256     36     29     19%
    6    1024      16     40     33     18%
    7    1024     256     30     23     23%
    8    1024    1024     29     23     21%
    9    2048      16     39     32     18%
   10    2048     256     29     22     24%
   11    2048    1024     28     22     21%
   12    2048    2048     28     22     21%
   13    4096      16     38     32     16%
   14    4096     256     28     22     21%
   15    4096    1024     28     21     25%
   16    4096    4096     27     21     22%
   17    8192      16     38     32     16%
   18    8192     256     28     22     21%
   19    8192    1024     28     21     25%
   20    8192    4096     27     21     22%
   21    8192    8192     27     21     22%

The improvement isn't as good, but it's still noticeable.

--Benjamin Gilbert

Wait, your benchmark is comparing against the unrolled code?

How big is the -code- footprint?

Whoa. We've regressed something horrible here:

http://groups.google.com/group/linux.kernel/msg/fba056363c99d4f9?dmode=source&hl=en

In 2003, I was getting 17MB/s out of my Athlon. Now I'm getting 2.7MB/s. Were your tests with or without the latest /dev/urandom fixes? This one in particular:

http://git.kernel.org/?p=linux/kernel/git/stable/linux-2.6.21.y.git;a=commitdiff;h=374f167dfb97c1785515a0c41e32a66b414859a8

Mathematics is the supreme nostalgia of our time.

No, it's comparing the current lib/sha1.c to the optimized code in the patch. I was just pointing out that the unrolled code you were likely testing against, back then, may not have been very good. (Though I assumed that you were talking about the unrolled code in random.c, not the code in CryptoAPI, so that might change the numbers some. It appears from the post you linked below that the unrolled CryptoAPI code still beat the rolled version?)

About 3700 bytes for the 32-bit version of sha_transform().

I'm not in front of that machine right now; I can check tomorrow. For what it's worth, I've seen equivalent performance (a few MB/s) on a range of fairly-recent kernels.

--Benjamin Gilbert

That predates lib/sha1.c by a while.

lib/sha1.c's footprint is... 621 bytes today. Huh. That's up from 466 bytes when it was introduced and no one's touched it:

http://search.luky.org/ML/linux-kernel.2005/msg06648.html

Stupid compilers.

But anyway. Cache footprint matters. The two big users of SHA1 in the kernel are /dev/random and IPSec, both of which typically operate on small chunks of data.

Mathematics is the supreme nostalgia of our time.

With. I just tried 2.6.11 (the oldest that will boot) on the Pentium IV box and got 3.7 MB/s, so if it's a regression it's been around for a while.

--Benjamin Gilbert

I would always suggest to benchmark such functions with forced cold i/d caches

(memset(x, 0, 5*1024*1024) and running some very large generated function every few iterations of the benchmark)

-Andi

Add optimized implementation of the SHA-1 hash function for x86_64, ported from the x86 implementation in Nettle (which is LGPLed).

The code has been tested with tcrypt and the NIST test vectors.

---

 arch/x86_64/kernel/x8664_ksyms.c |    3 
 arch/x86_64/lib/Makefile         |    2 
 arch/x86_64/lib/sha1.S           |  281 ++++++++++++++++++++++++++++++++++++++
 include/linux/cryptohash.h       |    2 
 lib/Kconfig                      |    7 +
 5 files changed, 293 insertions(+), 2 deletions(-)

index 77c25b3..bc641ab 100644
@@ -3,6 +3,7 @@
 
 #include <linux/module.h>
 #include <linux/smp.h>
+#include <linux/cryptohash.h>
 
 #include <asm/semaphore.h>
 #include <asm/processor.h>

@@ -60,3 +61,5 @@ EXPORT_SYMBOL(init_level4_pgt);
 EXPORT_SYMBOL(load_gs_index);
 
 EXPORT_SYMBOL(_proxy_pda);
+
+EXPORT_SYMBOL(sha_transform);

index c943271..6c8110b 100644
@@ -9,5 +9,5 @@ obj-$(CONFIG_SMP)	+= msr-on-cpu.o
 
 lib-y := csum-partial.o csum-copy.o csum-wrappers.o delay.o \
 	usercopy.o getuser.o putuser.o  \
-	thunk.o clear_page.o copy_page.o bitstr.o bitops.o
+	thunk.o clear_page.o copy_page.o bitstr.o bitops.o sha1.o
 lib-y += memcpy.o memmove.o memset.o copy_user.o rwlock.o copy_user_nocache.o

index 0da331c..b3b14a3 100644
@@ -7,6 +7,8 @@
 
 #if defined(CONFIG_SHA1_X86)
 #define SHA_WORKSPACE_WORDS 0
+#elif defined(CONFIG_SHA1_X86_64)
+#define SHA_WORKSPACE_WORDS 16
 #else
 #define SHA_WORKSPACE_WORDS 80
 #endif

index 69fdb64..23a84ed 100644
@@ -132,9 +132,14 @@ config SHA1_X86
 	depends on (X86 || UML_X86) && !64BIT && X86_BSWAP
 	default y
 
+config SHA1_X86_64
+	bool
+	depends on (X86 || UML_X86) && 64BIT
+	default y
+
 config SHA1_GENERIC
 	bool
-	depends on !SHA1_X86
+	depends on !SHA1_X86 && !SHA1_X86_64
 	default y
 
 endmenu

OFFSET(i) is defined as 4*(i), so they don't actually overlap. (Arguably that macro should go away.)

SHA-1 fundamentally wants to work with 32-bit quantities. It might be possible to use quad operations for some things, with sufficient cleverness, but I doubt it'd be worth the effort.

That seems to be the consensus. I'll see if I can find some time to try [email protected]'s suggestion and report back.

I don't think, though, that cache footprint is the *only* thing that matters. Leaving aside /dev/urandom, there are cases where throughput matters a lot. This patch set came out of some work on a hashing block device driver in which SHA is, by far, the biggest CPU user. One could imagine content-addressable filesystems, or even IPsec under the right workloads, being in a similar situation.

Would it be more palatable to roll the patch as an optimized CryptoAPI module rather than as a lib/sha1.c replacement? That wouldn't help /dev/urandom, of course, but for other cases it would allow the user to ask for the optimized version if needed, and not pay the footprint costs otherwise.

--Benjamin Gilbert

With which gcc version and compiler flags?

And why is the C code slower?
Problems in the C code?
gcc problems?

Generally, I'd really prefer one C implementation that works good on all platforms over getting dozens of different assembler implemenations, each potentially with different bugs.

cu
Adrian

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed