add MIPS assembler version of twofish crypto algorithm

Hi,

this patch adds a MIPS assembler version of the twofish cipher algorithm. x86(_64) had an assembler version of twofish for some time now, giving it an "unfair" advantage against the not so common architectures.

The code wast put through various tests and benchmarks in a user-space testbench, testing its correctness (also via qemu) for 32bit vs. 64bit and big vs. little endian MIPS.

http://mosquito.dyndns.tv/freesvn/trunk/linux/twofish-mips/

Also the same code backported to a 2.6.39 kernel (64bit) has been working flawlessly on my loongson-2f machine (with a twofish dm-crypt root) for a few weeks now.

Performance gain for the pure crypto code in 32-bit mode is about 15% on both Ingenic Xburst and Loongson-2f. With 64-bit it is 24-29%, as the C code suffers from 32->64 bit type conversions inserted by gcc. The code uses less unrolling than the C version, and should be smaller by at least a factor of 8. Full results in file Benchres.txt at the SVN URL given above.

---
 arch/mips/Kbuild                    |    2 +
 arch/mips/crypto/Makefile           |    7 +
 arch/mips/crypto/twofish-mips-asm.S |  346 +++++++++++++++++++++++++++++++++++
 arch/mips/crypto/twofish_glue.c     |   97 ++++++++++
 arch/mips/kernel/asm-offsets.c      |    8 +
 crypto/Kconfig                      |   16 ++
 6 files changed, 476 insertions(+), 0 deletions(-)
 create mode 100644 arch/mips/crypto/Makefile
 create mode 100644 arch/mips/crypto/twofish-mips-asm.S
 create mode 100644 arch/mips/crypto/twofish_glue.c

index 7dd65cf..fc88443 100644
@@ -17,3 +17,5 @@ obj- := $(platform-)
 obj-y += kernel/
 obj-y += mm/
 obj-y += math-emu/
+
+obj-y += crypto/

new file mode 100644
index 0000000..6069354
@@ -0,0 +1,7 @@
+#
+# Arch-specific CryptoAPI modules.
+#
+
+obj-$(CONFIG_CRYPTO_TWOFISH_MIPS) += twofish-mips.o
+
+twofish-mips-y := twofish-mips-asm.o twofish_glue.o

index 6b30fb2..9d91a6d 100644
@@ -15,6 +15,7 @@
 #include <linux/interrupt.h>
 #include <linux/kbuild.h>
 #include <linux/suspend.h>
+#include <linux/crypto.h>
 #include <asm/ptrace.h>
 #include <asm/processor.h>
 

@@ -339,3 +340,10 @@ void output_pbe_defines(void)
 	BLANK();
 }
 #endif
+
+void output_crypto_defines(void)
+{
+	COMMENT(" Linux crypto API offsets. ");
+	OFFSET(crypto_tfm_ctx_offset, crypto_tfm, __crt_ctx);
+	BLANK();
+}

index ae27b753..fa1b2b2 100644
@@ -793,6 +793,22 @@ config CRYPTO_TWOFISH_X86_64
 	  See also:
 	  <http://www.schneier.com/twofish.html>
 
+config CRYPTO_TWOFISH_MIPS
+	tristate "Twofish cipher algorithm (MIPS)"
+	depends on MIPS
+	select CRYPTO_ALGAPI
+	select CRYPTO_TWOFISH_COMMON
+	help
+	  Twofish cipher algorithm (MIPS).
+
+	  Twofish was submitted as an AES (Advanced Encryption Standard)
+	  candidate cipher by researchers at CounterPane Systems.  It is a
+	  16 round block cipher supporting key sizes of 128, 192, and 256
+	  bits.
+
+	  See also:
+	  <http://www.schneier.com/twofish.html>
+
 comment "Compression"
 
 config CRYPTO_DEFLATE

1.7.4.1

Lots of trailing whitespace in that patch. scripts/checkpatch.pl would have warned about those …

+#if __mips64
+# define HAVE_64BIT
+#endif

s/HAVE_64BIT/CONFIG_64BIT/

+#if _MIPS_SZPTR == 32
+# define PTRADD addu
+# warning "detected pointer-size as 32-bit"
+#else

+#  ifndef HAVE_64BIT
+#  error "something is broken: detected pointer size > GPR size"
+#  endif
+#  define PTRADD daddu
+#  warning "detected pointer-size as 64-bit"

+#endif

PTR_ADDU from <asm/asm.h> does the same thing as PTRADDU so the entire ifdefery above can go away.

Finally the use of register names starting with $ is a bit obscure. Kernel code needs to build for N64 and O32 but of those only N64 has registers called $ta0 .. $ta3 which are the equivalent to registers $8 .. $11.

And in O32 registers $t0 ... $t3 also aliases for $8 .. $11. I haven't fully analyzed the code to ensure that there is no register conflict arising from that.

I was surprised that gas assembles the code at all. $ta0 .. $ta3 are N32 / N64 register names and consider gas permitting the use of these registers in O32 a bug - but see my other posting to the binutils list for that.

Improvment suggestion for le32_fromto_cpu - MIPS 32/64 R2 CPUs can use the wsbh instruction to faster endianess swapping:

static inline __attribute_const__ __u32 __arch_swab32(__u32 x)

{
        __asm__(
        "       wsbh    %0, %1                  \n"
        "       rotr    %0, %0, 16              \n"
        : "=r" (x)
        : "r" (x));

        return x;
}

#define __arch_swab32 __arch_swab32

This code fragment is from <asm/swab.h>.

+ /* if we turned this into 64-bit ops, we get endianess issues on
+ big-endian mips, plus alignment problems */

Some CPUs (Cavium Octeon) handle unaligned loads in hardware, on others a combination of LDL / LDR and SDL / SDR could be used to handle the unaligned loads and DSBH / DSHD (see __arch_swab64 in swab.h) could be used on MIPS64 R2 CPUs to handle the alignment issues. Or a rotate - have to think about it.

Ralf

On Wed, Sep 28, 2011 at 03:32:41PM +0200, Ralf Baechle wrote:

Ah, also we unfortunately still support assemblers older than binutils 2.18 but and support for the software names of the registers was introduced in 2.18, so <asm/mipsregs.h> should be used to get the definitions for the register names.

Another advantage of doing this is that we get rid of the ugly $ prefix of register names.

Cheers,

Ralf

Thought that patch went unnoticed and almost forgot about it myself... Nice to see that it didn't slip through, and thanks for taking the time to review.

About your comments:

[..]

[..]

Good point, that'll neatly clean the patch up.

Didn't find another way to make the code work with O32 and N64. $ta0..$ta3 can replace registers $t4..$t7 that are missing on N64 to make room for additional argument registers $a4..$a7. This works as long as $a4..$a7 aren't used as well.

Looking at asm/regdef.h I see that #define ta0 etc. is missing for O32, making that trick impossible. Maybe we should add them there as well?

Yes, that feature may be obscure, had to grep through binutil sources to find out about it...

[..]

I completely missed the wsbh opcode. Knew about rotr, but given that even the recent Loongson-2f doesn't support it, I was reluctant to add code for it (plus i won't be able to benchmark it anyways).

There is an alignmask field in the crypto_alg struct, that might prevent alignment issues. Didn't have an in-depth look at how that works though. Still there would be endianess issues, given that twofish is designed to work on words of 32-bit.

I think the load/store code of the crypto routine does not have much influence on performance, as it is outside the main loop (including the endianess conversion). There is a rotation operation within the loop, that could be sped up using rotr opcode, giving maybe 2% performance gain. Not sure whether that's worth another round of #ifdefs and twice the testing.

What'd be the best way to check for rot opcode support? Use CONFIG_CPU_MIPSR2? Check gcc define __mips>=32 && __mips_isa_rev>=2 (grepping through kernel asm files, I don't find any asm sources that include kconfig.h)?

I'm currently a little swamped with work, btw, might take me a few days to prepare an updated patch.

cheers,

David

GnuPG public key: http://dvdkhlng.users.sourceforge.net/dk.gpg
Fingerprint: B17A DC95 D293 657B 4205  D016 7DEF 5323 C174 7D40