patchblock-sha1: more good unaligned memory access candidates

In addition to X86, PowerPC and S390 are capable of unaligned memory accesses.

Signed-off-by: Nicolas Pitre <nico@cam.org>

On Thu, 13 Aug 2009, Nicolas Pitre wrote:

Ack on all your patches (1-3 + this). Looks fine to me.

I do wonder if we should try to do basically "per-architecture hack header-files", and then have for each architecture a small trivial 'hack-x86.h' kind of thing that just does

	/* x86 hacks */
	#define get_be32(p)	ntohl(*(unsigned int *)(p))
	#define put_be32(p, v)	do { *(unsigned int *)(p) = htonl(v); } while (0)
	#define setW(x, val)	(*(volatile unsigned int *)&W(x) = (val))

	#define SHA_ASM(op, x, n) ({ unsigned int __res; __asm__(op " %1,%0":"=r" (__res):"i" (n), "0" (x)); __res; })
	#define SHA_ROL(x,n)   SHA_ASM("rol", x, n)
	#define SHA_ROR(x,n)   SHA_ASM("ror", x, n)

and then we'd have each architecture separated out. Add a few "generic helpers":

 - be32-generic.h:

	#define get_be32(p)    ( \
		(*((unsigned char *)(p) + 0) << 24) | \
		(*((unsigned char *)(p) + 1) << 16) | \
		(*((unsigned char *)(p) + 2) <<  8) | \
		(*((unsigned char *)(p) + 3) <<  0) )

	#define put_be32(p, v) do { \
		unsigned int __v = (v); \
		*((unsigned char *)(p) + 0) = __v >> 24; \
		*((unsigned char *)(p) + 1) = __v >> 16; \
		*((unsigned char *)(p) + 2) = __v >>  8; \
		*((unsigned char *)(p) + 3) = __v >>  0; } while (0)

 - rotate-generic.h:

	#define SHA_ROT(X,l,r)  (((X) << (l)) | ((X) >> (r)))
	#define SHA_ROL(X,n)    SHA_ROT(X,n,32-(n))
	#define SHA_ROR(X,n)    SHA_ROT(X,32-(n),n)

that architectures could use when they want to use some particular portable version. Then, add a final "hack-generic.h" with the fallback cases that just does

	#include "be32-generic.h"
	#include "rotate-generic.h"
	#define setW(x,val) (W(x) = (val))

and you'd have all the hacks separated out and fairly easily used by different architectures.. (ie the ARM version would just look like

 - hack-arm.h:

	#include "be32-generic.h"  
	#include "rotate-generic.h"
	#define setW(x, val) do { W(x) = (val); __asm__("":::"memory"); } while (0)

and you'd be all done.

Hmm? I don't know if this kind of generalization is strictly needed, so I'm just throwing it out as an idea.

		Linus

On Thu, 13 Aug 2009, Linus Torvalds wrote:

Well... first I don't think there are much else we can do with that code, i.e. there is probably not so many more hacks to add if any. With my last patch I consider this ready for general consumption.

And given that the only user is this very sha1 implementation then there is not much value in abstracting them in header files.

And the point of patch 2/3 was to move hack variants for the same purpose together making it easier to document and understand (and possibly modify) them. Your suggestion would go in the opposite direction entirely.

As it is now, I was about to suggest:

	git mv block-sha1/sha1.[ch] .
	rmdir block-sha1
	rm -r mozilla-sha1
	rm -r arm
	rm -r ppc 

and remove support for openssl's SHA1 usage, making this implementation unconditional. After all it is faster, or so close to be faster than the alternatives, that we should probably cut on the extra dependency and simplify portability issues at the same time.

Nicolas

Nicolas Pitre <nico@cam.org> writes:

Wow.  Is it now faster than the arm/ and ppc/ hand-tweaked assembly?

On Thu, 13 Aug 2009, Junio C Hamano wrote:

For the good cases, yes.

For POWER, with gcc-4.4, the C code apparently outperforms the asm code on POWER6. The asm code is scheduled for POWER4, and I think outperforms the C code there. Also, when compiling in 64-bit mode (with "-m64"), at least some versions of gcc seem to do some stupid things and add extra zero extension stuff, and that performed suboptimally at least on a PPC G5.

So it's certainly not a clear case of "the C code outperforms the asm code", but in BenH's tests, the best numbers really did come from the C version. With some silly cases of at least some versions gcc screwing up (not reload, but zero extension), and making it noticeably slower.

IOW, the PPC situation really isn't that different from x86. 

			Linus

On Thu, 13 Aug 2009, Junio C Hamano wrote:

It is indeed faster than the ARM assembly version by far, and faster than all the alternative implementations too, but with a 7x increase in compiled code size. In the context of Git I think this is a good compromize. Making the assembly version faster than the C version could be possible, but that would require quite some work and I don't expect the gain to be significant, certainly not worth the trouble.

Furthermore the C version can be used to generate ARM Thumb code while the asm version cannot without yet more work.

Nicolas

From: Brandon Casey <drafnel@gmail.com>

Some compilers produce errors when arithmetic is attempted on pointers to void. So cast to uintptr_t when performing arithmetic on void pointers.

Signed-off-by: Brandon Casey <casey@nrlssc.navy.mil>
---

This, on top of Nico's last patch "block-sha1: more good unaligned memory access candidates", allows this series to compile and run successfully on Sun Sparc and IRIX MIPS for me.

It produces no differences on Linux using gcc. gcc 3.4.6 and 4.1.2 produce an identical binary for me on x86 and x86-64 with and without this change. Any conceivable negative effects on other arch's?

-brandon

 block-sha1/sha1.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

Hi,

On Fri, 14 Aug 2009, Brandon Casey wrote:

I am confused. Is sizeof(*(uintptr_t)NULL) not larger than 1, and as a consequence ((uintptr_t)p)+1 not different from ((void *)p)+1?

Ciao, Dscho

On Sat, 15 Aug 2009, Johannes Schindelin wrote:

You can't do that. "uintptr_t" isn't actually a pointer. It's just a unsigned integer value large enough to contain a pointer.

So it's _not_ a "pointer to uint". It's "uint that can contain all the bits of a poitner".

No, they're the same.

That said, I suspect it might as well be cast to "const char *", and then hopefully you only need one cast.

So maybe it could be written as

	data = (const char *) data + len;

instead, and avoid the second cast (because the assignment should be ok, since it's assigning back to a "const void *").

		Linus

Linus Torvalds wrote:

Yep, that's enough. It produces an identical binary on all platforms except Solaris x86 using SUNWspro compiler.

-brandon

Brandon Casey <casey@nrlssc.navy.mil> writes:

Casting to "const char *" to tell compilers that we are interested in byte address differences/increments makes sense to me, but I do not know how to interpret your last comment.

Do you mean that SUNWspro compiler misbehave with the "cast to char *" and do you meed your "casting to uintptr_t to explicitly compute byte addresses as int" to make it behave?

Junio C Hamano wrote:

Yes, I agree.

No, sorry, the SUNWspro compiler produces a working binary with any of the three versions: the original, cast to uintptr_t, or cast to const char*. Though it emits a warning with the original.

I was just pointing out that the SUNWspro compiler does not produce an identical binary on x86 for each of the three versions like the GNU compiler does.

Sorry for the confusion. Linus's suggestion of casting to "const char*" should be adopted.

-brandon

Brandon Casey <casey@nrlssc.navy.mil> writes:

Ah, I see.  Thanks.

Let's queue this, then.

-- >8 --
From: Brandon Casey <drafnel@gmail.com>
Date: Fri, 14 Aug 2009 17:52:15 -0500
Subject: [PATCH] block-sha1/sha1.c: silence compiler complaints by casting void * to char *

Some compilers produce errors when arithmetic is attempted on pointers to void. We want computations done on byte addresses, so cast them to char * to work them around.

Signed-off-by: Brandon Casey <casey@nrlssc.navy.mil>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 block-sha1/sha1.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

On Fri, 14 Aug 2009, Junio C Hamano wrote:

Unnecessary outer parentheses, but ack anyway.

		Linus

Johannes Schindelin wrote:

If you try this:

   printf("NULL + 1: %u\n", (void*)NULL + 1);

the MIPSpro compiler complains like:

   The expression must be a pointer to a complete object type.

        printf("NULL + 1: %u\n", (void*)NULL + 1);
                                 ^

   1 error detected in the compilation of "test.c".

Compilers other than gcc at least issue a warning, if they do not also fail.

-brandon