lkml.org 
[lkml]   [2007]   [Dec]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [Security] Signed divides vs shifts (Re: /dev/urandom uses uninit bytes, leaks user data)


On Mon, 17 Dec 2007, Eric Dumazet wrote:
>
> while
>
> long *mid(long *a, long *b)
> {
> return ((a - b) / 2u + a);
> }

This is exactly what I'm talking about. That "2u" is TOTALLY POINTLESS.
It's an "unsigned int", but since (a-b) will be of type ptrdiff_t, and is
*wider* on a 64-bit architecture (it's the same as "long" on x86-64), then
the 2u will just be converted to "long", and be signed again!

So you thought that you did an unsigned divide, but you did no such thing.

If you change the "2u" to a "2ul", it works again, and you get

mid:
movq %rdi, %rax
subq %rsi, %rax
sarq %rax
andq $-8, %rax
addq %rdi, %rax
ret

which is the code you wanted. But quite frankly, you could just have
written it with a shift to start with, and avoided the subtle type issue,
although gcc then generates

movq %rdi, %rax
subq %rsi, %rax
sarq $4, %rax
leaq (%rdi,%rax,8), %rax
ret

instead. Of course, this all *does* still have subtle sign issues, because
the "a-b" part implies a signed divide in itself, which is why you see
that "sarq" in he first place (rather than a "shrq").

Signed divides are hard. The "a-b" pointer subtraction is actually cheaper
than a general signed divide by sizeof, since the compiler can then assume
that the two pointers are mutually aligned, which is why gcc can generate
just a single "sarq" instead of having to do an extra "add negative bit"
thing to get the rounding right.
[ So Al, when you said that

(a-b)

is equivalent to

((char *)a-(char *)b)/4

for a "int *" a and b, you're right in the sense that the *result* is
the same, but the code generation likely isn't. The "a-b" thing can (and
does) allow the compiler to avoid the whole "align up for signed
numbers" thing, and the difference in code generation is clear:

subq %rsi, %rdi
sarq $2, %rdi

vs

subq %rsi, %rdi
leaq 3(%rdi), %rax
testq %rdi, %rdi
cmovs %rax, %rdi
sarq $2, %rdi

exactly because the first case *knows* that the low two bits have to be
zero, and thus there is no rounding issue. ]

Linus


\
 
 \ /
  Last update: 2007-12-17 19:35    [from the cache]
©2003-2011 Jasper Spaans