Subject: Re: tr/xdiff-fast-hash generates warnings and breaks tests

From: René Scharfe <[email-masked]>
Date: Thu, 17 May 2012 20:40:12 +0200

Am 17.05.2012 18:23, schrieb Junio C Hamano:
> René Scharfe<[email-masked]>  writes:
>> On Ubuntu 12.04 x86, t0020 fails for me as well when I compile with
>> XDL_FAST_HASH explicitly set (it's off by default).
>
> OK.  So does that indicate at least breakage in the Makefile that
> attempts to set XDL_FAST_HASH only on x86_64, mistakenly triggering
> on Øyvind's x86 32-bit userland, or did Øyvind manually flipped the
> feature on?

It's turned on by default if uname -m says x86_64, which it does for 
Øyvind (64-bit kernel).  His userland is a 32-bit one, though.

> It is a separate issue that XDL_FAST_HASH code does not work on 32-bit
> systems, even though it is advertised that it only needs to be on
> little-endian.

Indeed.

>> It succeeds after reverting 6f1af02, though, strangely enough.
>
> It is strange.  I do not see anything glaringly wrong in the conversion
> in that commit.  The only difference I see is that count_masked_bytes in
> the original used to take unsigned long on 64-bit archs but the updated
> one takes signed long, but that on 32-bit archs the function takes
> signed long in both versions so it cannot be it.  Stumped...

The assembly differs in two instructions:

	--- master/xdiff/xutils.s
	+++ reverted/xdiff/xutils.s
	@@ -733,7 +733,7 @@
	 	shrl	$7, %ebx
	 	leal	-256(%ebx), %ecx
	 	movl	%ebx, %edi
	-	shrl	$23, %ecx
	+	sarl	$23, %ecx
	 	andl	$1, %edi
	 	leal	1(%ecx,%edi), %ecx
	 	addl	%ecx, %esi
	@@ -934,7 +934,7 @@
	 	jmp	.L123
	 .L153:
	 	movl	$__PRETTY_FUNCTION__.4151, 12(%esp)
	-	movl	$374, 8(%esp)
	+	movl	$380, 8(%esp)
	 	movl	$.LC1, 4(%esp)
	 	movl	$.LC2, (%esp)
	 	call	__assert_fail

The second one is just a line number of an assert() that is moved around 
a bit.  The first one means that master is doing a logical shift right 
(shr) while with 6f1af02 reverted, an arithmetic shift right (sar) is 
performed in the same place.

While sar keeps the sign bit of the operand intact, shr shifts it to the 
right like the other bits.  The code seems to rely on arithmetic shift 
being done.  It's implementation-defined for signed numbers, but that's 
not that much of a problem, as we turn on the feature only on selected 
architectures anyway (modulo detection problems, as above ;).

The real issue seems to be that the shifted number is unsigned:

		long a = (mask - 256) >> 23;

For unsigned values, a logical shift right is done, always. Not sure why 
wrapping it  in "if (sizeof(long) == 8)" would make a difference at all, 
though.

The following patch on top of master makes the compiler put a sarl in my 
build, and "make -j4 XDL_FAST_HASH=1 test" passes.

Øyvind, does this oneliner help in your case as well?

-- >8 --
Subject: xdiff: signed right shift for 32-bit case of XDL_FAST_HASH

In the 32-bit branch of count_masked_bytes(), the compiler uses a
logical right shift on mask, because it is unsigned.  We want it to
be an arithmetic right shift, however (keeping negative numbers
negative instead of shifting the sign bit as well).

There is no way to specify it in C, but we can at least cast mask to
signed long.  This will make the compiler use an arithmetic right shift
on certain implementations, but that's OK because we only turn on
XDL_FAST_HASH in the Makefile for known-good architectures, and at least 
gcc 4.6.3 and clang 3.0 do what we want on the most interesting one (x86).

Signed-off-by: Rene Scharfe <[email-masked]>
---
  xdiff/xutils.c |    2 +-
  1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/xdiff/xutils.c b/xdiff/xutils.c
index 1b3b471..29df57e 100644
--- a/xdiff/xutils.c
+++ b/xdiff/xutils.c
@@ -311,7 +311,7 @@ static inline long count_masked_bytes(unsigned
  		 * (a+b+1) gives us
  		 *   correct 0-3 bytemask count result
  		 */
-		long a = (mask - 256) >> 23;
+		long a = ((long)mask - 256) >> 23;
  		long b = mask & 1;
  		return a + b + 1;
  	}
-- 
1.7.10.2