# [PATCH] block-sha1: more good unaligned memory access candidates 15 messages from 2009-08-13 to 2009-08-15. Participants: Nicolas Pitre, Linus Torvalds, Junio C Hamano, Brandon Casey, Johannes Schindelin. Thread: https://gitlist.dev/t/20568 ## Nicolas Pitre, 2009-08-13 04:29 Subject: [PATCH] block-sha1: more good unaligned memory access candidates Message-ID: URL: https://gitlist.dev/e/alpine.LFD.2.00.0908130017080.10633%40xanadu.home ``` In addition to X86, PowerPC and S390 are capable of unaligned memory accesses. Signed-off-by: Nicolas Pitre diff --git a/block-sha1/sha1.c b/block-sha1/sha1.c index d3121f7..e5a1007 100644 --- a/block-sha1/sha1.c +++ b/block-sha1/sha1.c @@ -67,7 +67,10 @@ * and is faster on architectures with memory alignment issues. */ -#if defined(__i386__) || defined(__x86_64__) +#if defined(__i386__) || defined(__x86_64__) || \ + defined(__ppc__) || defined(__ppc64__) || \ + defined(__powerpc__) || defined(__powerpc64__) || \ + defined(__s390__) || defined(__s390x__) #define get_be32(p) ntohl(*(unsigned int *)(p)) #define put_be32(p, v) do { *(unsigned int *)(p) = htonl(v); } while (0) ``` ## Linus Torvalds, 2009-08-13 16:45 Subject: Re: [PATCH] block-sha1: more good unaligned memory access candidates Message-ID: URL: https://gitlist.dev/e/alpine.LFD.2.01.0908130934400.28882%40localhost.localdomain In-Reply-To: ``` On Thu, 13 Aug 2009, Nicolas Pitre wrote: > > In addition to X86, PowerPC and S390 are capable of unaligned memory > accesses. > > Signed-off-by: Nicolas Pitre 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 ``` ## Nicolas Pitre, 2009-08-13 17:23 Subject: Re: [PATCH] block-sha1: more good unaligned memory access candidates Message-ID: URL: https://gitlist.dev/e/alpine.LFD.2.00.0908131304520.10633%40xanadu.home In-Reply-To: ``` On Thu, 13 Aug 2009, Linus Torvalds wrote: > > > On Thu, 13 Aug 2009, Nicolas Pitre wrote: > > > > In addition to X86, PowerPC and S390 are capable of unaligned memory > > accesses. > > > > Signed-off-by: Nicolas Pitre > > 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. 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 ``` ## Junio C Hamano, 2009-08-13 19:33 Subject: Re: [PATCH] block-sha1: more good unaligned memory access candidates Message-ID: <7v63crbja2.fsf@alter.siamese.dyndns.org> URL: https://gitlist.dev/e/7v63crbja2.fsf%40alter.siamese.dyndns.org In-Reply-To: ``` Nicolas Pitre writes: > 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. Wow. Is it now faster than the arm/ and ppc/ hand-tweaked assembly? ``` ## Linus Torvalds, 2009-08-13 19:54 Subject: Re: [PATCH] block-sha1: more good unaligned memory access candidates Message-ID: URL: https://gitlist.dev/e/alpine.LFD.2.01.0908131246300.28882%40localhost.localdomain In-Reply-To: <7v63crbja2.fsf@alter.siamese.dyndns.org> ``` On Thu, 13 Aug 2009, Junio C Hamano wrote: > > Wow. Is it now faster than the arm/ and ppc/ hand-tweaked assembly? 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 ``` ## Nicolas Pitre, 2009-08-13 20:13 Subject: Re: [PATCH] block-sha1: more good unaligned memory access candidates Message-ID: URL: https://gitlist.dev/e/alpine.LFD.2.00.0908131603240.10633%40xanadu.home In-Reply-To: <7v63crbja2.fsf@alter.siamese.dyndns.org> ``` On Thu, 13 Aug 2009, Junio C Hamano wrote: > Nicolas Pitre writes: > > > 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. > > Wow. Is it now faster than the arm/ and ppc/ hand-tweaked assembly? 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 ``` ## Brandon Casey, 2009-08-14 22:52 Subject: [PATCH] block-sha1/sha1.c: silence compiler complaints by casting void* to uintptr_t Message-ID: <_-0l9qI_nKm-VVtKlL5hzen4bhcyRmiZ1z4jSmKK1LwECXueziRDzSTyacEehOkoqsfYIaEUlds@cipher.nrlssc.navy.mil> URL: https://gitlist.dev/e/_-0l9qI_nKm-VVtKlL5hzen4bhcyRmiZ1z4jSmKK1LwECXueziRDzSTyacEehOkoqsfYIaEUlds%40cipher.nrlssc.navy.mil In-Reply-To: ``` From: Brandon Casey 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 --- 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(-) diff --git a/block-sha1/sha1.c b/block-sha1/sha1.c index e5a1007..ccaba9e 100644 --- a/block-sha1/sha1.c +++ b/block-sha1/sha1.c @@ -246,14 +246,14 @@ void blk_SHA1_Update(blk_SHA_CTX *ctx, const void *data, unsigned long len) memcpy(lenW + (char *)ctx->W, data, left); lenW = (lenW + left) & 63; len -= left; - data += left; + data = (const void*) ((uintptr_t) data + left); if (lenW) return; blk_SHA1_Block(ctx, ctx->W); } while (len >= 64) { blk_SHA1_Block(ctx, data); - data += 64; + data = (const void*) ((uintptr_t) data + 64); len -= 64; } if (len) -- 1.6.4 ``` ## Johannes Schindelin, 2009-08-15 00:08 Subject: Re: [PATCH] block-sha1/sha1.c: silence compiler complaints by casting void* to uintptr_t Message-ID: URL: https://gitlist.dev/e/alpine.DEB.1.00.0908150207270.8306%40pacific.mpi-cbg.de In-Reply-To: <_-0l9qI_nKm-VVtKlL5hzen4bhcyRmiZ1z4jSmKK1LwECXueziRDzSTyacEehOkoqsfYIaEUlds@cipher.nrlssc.navy.mil> ``` Hi, On Fri, 14 Aug 2009, Brandon Casey wrote: > Some compilers produce errors when arithmetic is attempted on pointers to > void. So cast to uintptr_t when performing arithmetic on void pointers. 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 ``` ## Linus Torvalds, 2009-08-15 00:19 Subject: Re: [PATCH] block-sha1/sha1.c: silence compiler complaints by casting void* to uintptr_t Message-ID: URL: https://gitlist.dev/e/alpine.LFD.2.01.0908141714040.3162%40localhost.localdomain In-Reply-To: ``` On Sat, 15 Aug 2009, Johannes Schindelin wrote: > > I am confused. Is sizeof(*(uintptr_t)NULL) not larger than 1 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". > and as a consequence ((uintptr_t)p)+1 not different from ((void *)p)+1? 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 ``` ## Brandon Casey, 2009-08-15 00:44 Subject: Re: [PATCH] block-sha1/sha1.c: silence compiler complaints by casting void* to uintptr_t Message-ID: <5HEgWEs64y4Ty7FnekstRP8Q71pNi_FTweLbMhYWc6zoZBA4jkJqpQ@cipher.nrlssc.navy.mil> URL: https://gitlist.dev/e/5HEgWEs64y4Ty7FnekstRP8Q71pNi_FTweLbMhYWc6zoZBA4jkJqpQ%40cipher.nrlssc.navy.mil In-Reply-To: ``` Linus Torvalds wrote: > 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 *"). Yep, that's enough. It produces an identical binary on all platforms except Solaris x86 using SUNWspro compiler. -brandon ``` ## Brandon Casey, 2009-08-15 00:52 Subject: Re: [PATCH] block-sha1/sha1.c: silence compiler complaints by casting void* to uintptr_t Message-ID: URL: https://gitlist.dev/e/qZXfoQ5Gp5jKnRfKM6ee07YVX-hyS2HsJmQwAYdPVHw92cOuUcufJA%40cipher.nrlssc.navy.mil In-Reply-To: ``` Johannes Schindelin wrote: > Hi, > > On Fri, 14 Aug 2009, Brandon Casey wrote: > >> Some compilers produce errors when arithmetic is attempted on pointers to >> void. So cast to uintptr_t when performing arithmetic on void pointers. > > 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? 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 ``` ## Junio C Hamano, 2009-08-15 01:46 Subject: Re: [PATCH] block-sha1/sha1.c: silence compiler complaints by casting void* to uintptr_t Message-ID: <7v8whl7ss9.fsf@alter.siamese.dyndns.org> URL: https://gitlist.dev/e/7v8whl7ss9.fsf%40alter.siamese.dyndns.org In-Reply-To: <5HEgWEs64y4Ty7FnekstRP8Q71pNi_FTweLbMhYWc6zoZBA4jkJqpQ@cipher.nrlssc.navy.mil> ``` Brandon Casey writes: > Linus Torvalds wrote: >> 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 *"). > > Yep, that's enough. It produces an identical binary on all platforms > except Solaris x86 using SUNWspro compiler. 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? ``` ## Brandon Casey, 2009-08-15 02:34 Subject: Re: [PATCH] block-sha1/sha1.c: silence compiler complaints by casting void* to uintptr_t Message-ID: URL: https://gitlist.dev/e/MecVLMUB15cEJQiZpwSBg9ysnmFSB1QYZfIQuSOStnFx2KoeScNXGQ%40cipher.nrlssc.navy.mil In-Reply-To: <7v8whl7ss9.fsf@alter.siamese.dyndns.org> ``` Junio C Hamano wrote: > Brandon Casey writes: > >> Linus Torvalds wrote: >>> 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 *"). >> Yep, that's enough. It produces an identical binary on all platforms >> except Solaris x86 using SUNWspro compiler. > > Casting to "const char *" to tell compilers that we are interested in byte > address differences/increments makes sense to me, Yes, I agree. > 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? 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 ``` ## Junio C Hamano, 2009-08-15 03:16 Subject: Re: [PATCH] block-sha1/sha1.c: silence compiler complaints by casting void* to uintptr_t Message-ID: <7v63cp22cc.fsf@alter.siamese.dyndns.org> URL: https://gitlist.dev/e/7v63cp22cc.fsf%40alter.siamese.dyndns.org In-Reply-To: ``` Brandon Casey writes: > 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. Ah, I see. Thanks. Let's queue this, then. -- >8 -- From: Brandon Casey 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 Signed-off-by: Junio C Hamano --- block-sha1/sha1.c | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) diff --git a/block-sha1/sha1.c b/block-sha1/sha1.c index e5a1007..464cb25 100644 --- a/block-sha1/sha1.c +++ b/block-sha1/sha1.c @@ -246,14 +246,14 @@ void blk_SHA1_Update(blk_SHA_CTX *ctx, const void *data, unsigned long len) memcpy(lenW + (char *)ctx->W, data, left); lenW = (lenW + left) & 63; len -= left; - data += left; + data = ((const char *)data + left); if (lenW) return; blk_SHA1_Block(ctx, ctx->W); } while (len >= 64) { blk_SHA1_Block(ctx, data); - data += 64; + data = ((const char *)data + 64); len -= 64; } if (len) ``` ## Linus Torvalds, 2009-08-15 18:43 Subject: Re: [PATCH] block-sha1/sha1.c: silence compiler complaints by casting void* to uintptr_t Message-ID: URL: https://gitlist.dev/e/alpine.LFD.2.01.0908151142470.3162%40localhost.localdomain In-Reply-To: <7v63cp22cc.fsf@alter.siamese.dyndns.org> ``` On Fri, 14 Aug 2009, Junio C Hamano wrote: > > From: Brandon Casey > 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 > Signed-off-by: Junio C Hamano Unnecessary outer parentheses, but ack anyway. Linus ```