Date: Tue, 17 Nov 2009 10:40:29 -0800 (PST)
From: Linus Torvalds <torvalds@linux-foundation.org>
To: Michael Buesch <mb@bu3sch.de>
cc: =?ISO-8859-15?Q?Uwe_Kleine-K=F6nig?= 
	<u.kleine-koenig@pengutronix.de>,
       linux-kernel@vger.kernel.org, Peter Zijlstra <a.p.zijlstra@chello.nl>,
       Andrew Morton <akpm@linux-foundation.org>
Subject: Re: [PATCH] strcmp: fix overflow error
In-Reply-To: <200911171916.41727.mb@bu3sch.de>
Message-ID: <alpine.LFD.2.01.0911171026010.9384@localhost.localdomain>
References: <1258476700-21323-1-git-send-email-u.kleine-koenig@pengutronix.de> <alpine.LFD.2.01.0911170922190.9384@localhost.localdomain> <200911171916.41727.mb@bu3sch.de>
User-Agent: Alpine 2.01 (LFD 1184 2008-12-16)
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 2115
Lines: 59


On Tue, 17 Nov 2009, Michael Buesch wrote:
> 
> Well, that doesn't actually return the difference at all. Is that allowed?

It's in fact the common implementation. Returning -1/0/1 is kind of 
polite, since it means that the sign now fits in a minimal type (ie you 
can save the end result in a "signed char" and it will _work_, even 
though it's not guaranteed by the standard.

Returning any negative or positive number is certainly _allowed_ by the 
standard, but I just checked, and glibc does the "polite" -1/0/1 thing. I 
suspect many other libraries do too, and it's not like it costs you 
anything more.

In fact, the written-out-with-unsigned-char-variables version is also 
likely to generate better code than the "clever" one that does just one 
subtract, because now the code can do all the comparisons in just 
'unsigned char' and never needs to sign-extend the result to 'int'.

Not that it likely matters.

I double-checked, and the code generated from my patch looks sane.

	strcmp:
	        pushq   %rbp    #
	        movq    %rsp, %rbp      #,
	.L52:
	        movb    (%rdi), %al     #* cs, c1
	        movb    (%rsi), %dl     #* ct, c2
	        incq    %rdi    # cs
	        incq    %rsi    # ct
	        cmpb    %dl, %al        # c2, c1
	        je      .L49    #,
	        sbbl    %eax, %eax      # D.13150
	        orl     $1, %eax        #, D.13150
	        jmp     .L51    #
	.L49:
	        testb   %al, %al        # c1   
	        jne     .L52    #,
	        xorl    %eax, %eax      # D.13150
	.L51:
	        leave
	        ret

which is not horrible (of course, depending on whether you expect to find 
differences early or late you might want to have make the "L49" case be 
the fallthrough etc).

[ Using sbb+or is a standard x86 trick to get -1/1. You'll also find 
  "sbb+and" to get 0/value, or "sbb+add" to get value/value+1 ]

		Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/