Re: [PATCH] strcmp: fix overflow error

From: Linus Torvalds
Date: Tue Nov 17 2009 - 13:41:05 EST




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@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/