# Dangerous UDP Checksum code ?!?

• 11-08-2008, 12:16 AM
unix
Dangerous UDP Checksum code ?!?
Hi,

Right now I am trying to implement some udp checksum code.

The idea which I am trying out is located on this web page:

[url]http://www.netfor2.com/udpsum.htm[/url]

The idea seems to be to use a 32 bit integer to do the summing with.

Therefore all the carries are collected into the high order word.

Apperently these carries need to be added to the summation.

(
I am not exactly sure why these carries need to be added ?

Does it have something to do with one complement ?

Or does it have to do something with the way one complement computers work
?
)

Anyway the following code on the website seems dangerous to me:

// keep only the last 16 bits of the 32 bit calculated sum and add the
carries
while (sum>>16)
sum = (sum & 0xFFFF)+(sum >> 16);

Especially the last line.

If the compiler translates this into the following instruction sequence:

1. sum = sum & 0xFFFF;

and then:

2. sum = sum + (sum >> 16);

then the carries will have been lost ?!

According to wikipedia the instruction order is not specified ?

[url]http://en.wikipedia.org/wiki/C_(programming_language[/url])

"
Expressions can use a variety of built-in operators (see below) and may
contain function calls. The order in which operands to most operators, as
well as the arguments to functions, are evaluated is unspecified;
"

What you make of this... dangerous or not dangerous ?

(Also I am translating this code to Delphi... but now I am getting some
serious doubts ! ;))

Bye,
Skybuck.

• 11-08-2008, 12:25 AM
unix
Re: Dangerous UDP Checksum code ?!?
Well anyway...

I think the idea can still work.

Assuming the maximum value for each word is: 65535.

And assuming a packet is maximum of 65535 words then multiple these two
should give the number of carries in the high word
correctly... so no overflows will occur... I checked that yesterday ! ;)

So to be on the safe side the code could be altered a little bit like so:

Carries := Sum shr 16;
Sum := Sum and \$FFFF;
while Carries > 0 do
begin
Sum := Sum + Carries;
Carries := Sum shr 16;
Sum := Sum and \$FFFF;
end;

Or alternatively (probably shorter, less intuitive though):

Carries := 0;
repeat
Sum := Sum + Carries;
Carries := Sum shr 16;
Sum := Sum and \$FFFF;
until Carries = 0;

Bye,
Skybuck.

• 11-08-2008, 12:43 AM
unix
Re: Dangerous UDP Checksum code ?!?
Skybuck Flying wrote:[color=blue]
> Anyway the following code on the website seems dangerous to me:
>
> // keep only the last 16 bits of the 32 bit calculated sum and add the
> carries
> while (sum>>16)
> sum = (sum & 0xFFFF)+(sum >> 16);
>
> Especially the last line.
>
> If the compiler translates this into the following instruction sequence:
>
> 1. sum = sum & 0xFFFF;
>
> and then:
>
> 2. sum = sum + (sum >> 16);
>
> then the carries will have been lost ?!
>
> According to wikipedia the instruction order is not specified ?
>
> [url]http://en.wikipedia.org/wiki/C_(programming_language[/url])[/color]

The order of evaluation is not specified because this:

sum = (sum & 0xFFFF) + (sum >> 16);

is equivalent to:

sum = (sum >> 16) + (sum & 0xFFFF);

So it's perfectly legal for the compiler to do this:

A = (sum & 0xFFFF);
B = (sum >> 16);
sum = A + B; /* ( or B + A) */

And it doesn't matter whether A or B is calculated first -- or they can
be done at the same time.

However, the compiler is NOT allowed to translate it to the sequence you
specify, because that would change the result. C compilers are only
allowed to perform optimizations that give the same result as the
original code. Your sequence doesn't, therefore it is not allowed.

S
• 11-08-2008, 03:32 AM
unix
Re: Dangerous UDP Checksum code ?!?
Actually the maximum number of words in a packet is probably more close to
65535 div 2...

So that's about 32767 carries or so...in the maximum case...

So 32 bits more than enough to catch any possible carries ;)

Bye,
Skybuck.

• 11-08-2008, 12:30 PM
unix
Re: Dangerous UDP Checksum code ?!?
"Skybuck Flying" <BloodyShame@hotmail.com> writes:
[SNIP - usual crap]

You're a useless troll in every other programming group I've
ever encountered. I'm dismayed to see you've discovered this one
as well.

Phil
--
We must respect the other fellow's religion, but only in the sense and to the
extent that we respect his theory that his wife is beautiful and his children
smart. -- Henry Louis Mencken (1880-1956), American editor and critic
• 11-08-2008, 02:09 PM
unix
Re: Dangerous UDP Checksum code ?!?
On Nov 7, 4:16*pm, "Skybuck Flying" <BloodySh...@hotmail.com> wrote:
[color=blue]
> *// keep only the last 16 bits of the 32 bit calculated sum and add the
> carries
> * * *while (sum>>16)
> * sum = (sum & 0xFFFF)+(sum >> 16);
>
> Especially the last line.
>
> If the compiler translates this into the following instruction sequence:
>
> 1. sum = sum & 0xFFFF;
> and then:
> 2. sum = sum + (sum >> 16);
>
> then the carries will have been lost ?![/color]

How can the compiler, whether by optimization, order of operations, or
any other possible mechanism, turn one assignment into two
assignments? There is only one '=', so there is no conceivable way to
turn it into two assignments.

You are correct that the order of operations is unspecified, but the
*NATURE* of the operations is. The nature of the original statement is
that it has one assignment to 'sum'.

The compiler could do:

temp=sum;
sum=sum+temp&0xffff;
sum=sum+temp>>16;

Here there are two assignments to 'sum', but there's no change to the
result.

Compilers can make two types of optimizations:

1) Those that change the result, but are permitted by the standard.
For example:
sum+=(sum++)+(--sum);
Here, the order of operations can change the result, but the standard
specifically says the order of operations is unspecified.

2) Those that do not change the result. For example:
temp=sum;
sum=sum+temp&0xffff;
sum=sum+temp>>16;

A type '1' is allowed, changing the order in which the two halves of
the + are calculated, but since neither calculation changes
'sum' (unlike my example above) that has no effect on the result. The
'optimization' you discussed is not a type '1'. Nowhere does the
standard say that one assignment can become two.

A type '2' optimization is allowed, but it can't change the result, so
who cares.

DS
• 11-08-2008, 02:13 PM
unix
Re: Dangerous UDP Checksum code ?!?
"Skybuck Flying" <BloodyShame@hotmail.com> writes:
[color=blue]
> // keep only the last 16 bits of the 32 bit calculated sum and add the
>carries
> while (sum>>16)
> sum = (sum & 0xFFFF)+(sum >> 16);[/color]
[color=blue]
>Especially the last line.[/color]
[color=blue]
>If the compiler translates this into the following instruction sequence:[/color]
[color=blue]
>1. sum = sum & 0xFFFF;[/color]

Then the compiler has a bug.
[color=blue]
>According to wikipedia the instruction order is not specified ?[/color]

Yes, but storing "sum & 0xffff" was not legal; and if the compiler does so,
it is broken.

Casper
--
Expressed in this posting are my opinions. They are in no way related
to opinions held by my employer, Sun Microsystems.
Statements on Sun products included here are not gospel and may
be fiction rather than truth.
• 11-08-2008, 05:06 PM
unix
Re: Dangerous UDP Checksum code ?!?
Phil Carmody wrote:
[color=blue]
> "Skybuck Flying" <BloodyShame@hotmail.com> writes:
> [SNIP - usual crap]
>
> You're a useless troll in every other programming group I've
> ever encountered. I'm dismayed to see you've discovered this one
> as well.[/color]

Which one? It's posted to three.

Brian
• 11-08-2008, 11:46 PM
unix
Re: Dangerous UDP Checksum code ?!?
I think I've been redcoding a bit too much ;)

In redcode there is no such thing as temporarely variables created by the
compiler... ;)

So in recode any operation is done directly on whatever was specified ;)

So I guess I got a bit worried that direct operations could happen in high
level languages as well ;)

At least the solution I posted could be easily ported to for example
redcode/asm without any doubts/problems ;) :) So I am sticking with my
solution ! ;)

Bye,
Skybuck =D

• 11-09-2008, 10:14 PM
unix
Re: Dangerous UDP Checksum code ?!?
On Nov 8, 3:46*pm, "Skybuck Flying" <BloodySh...@hotmail.com> wrote:
[color=blue]
> At least the solution I posted could be easily ported to for example
> redcode/asm without any doubts/problems ;) :) So I am sticking with my
> solution ! ;)[/color]

If you want to spend the rest of your life writing mind-numbingly dumb
code, knock yourself out. For for the rest of us sane people, if this
is pretty gosh darned simple:

sum = (sum & 0xFFFF)+(sum >> 16);

Frankly, it's a miracle that anyone was able to misunderstand it. But
then, you never cease to impress.

DS
• 11-10-2008, 01:59 AM
unix
Re: Dangerous UDP Checksum code ?!?
David Schwartz wrote:[color=blue]
> On Nov 8, 3:46 pm, "Skybuck Flying" <BloodySh...@hotmail.com> wrote:
>[color=green]
>> At least the solution I posted could be easily ported to for example
>> redcode/asm without any doubts/problems ;) :) So I am sticking with my
>> solution ! ;)[/color]
>
> If you want to spend the rest of your life writing mind-numbingly dumb
> code, knock yourself out. For for the rest of us sane people, if this
> is pretty gosh darned simple:
>
> sum = (sum & 0xFFFF)+(sum >> 16);
>
> Frankly, it's a miracle that anyone was able to misunderstand it. But
> then, you never cease to impress.[/color]

Skybly has made a multi-year career of Usenet vandalism.
On each newsgroup where I have seen hir, the pattern has been
the same: A few semi-reasonable posts to provide adequate
lubrication, followed by an affirmation of the surname (with
the obvious edit). The suggested remedy is to update your
killfiles; would that it were possible to set them on something
stronger than "Stun."

--
Eric Sosman
[email]esosman@ieee-dot-org.inva[/email]lid