Dangerous UDP Checksum code ?!?

[Skybuck Flying]

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:

http://www.netfor2.com/udpsum.htm

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 ?

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

It reads:

"
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.

 

[Skybuck Flying]

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.

 

[Stephen Sprunk]

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 ?

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

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

 

[Skybuck Flying]

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.

 

[Phil Carmody]

[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

 

[David Schwartz]

 // 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 ?!

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

 

[Casper H.S. Dik]

// 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;

Then the compiler has a bug.

According to wikipedia the instruction order is not specified ?

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

Casper

 

[Default User]

[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.

Which one? It's posted to three.


Brian

 

[Keith Thompson]

Posting only to comp.lang.c.

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.

That invokes undefined behavior, since sum is modified multiple times
between sequence points. The compiler is free to do anything it
likes, including replacing the whole thing with
puts("undefined behavior");

A better example would be
sum += foo() + bar();
where foo and bar are functions with side effects. The side effects
can occur in either order.

[...]

 

[Skybuck Flying]

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

 

[David Schwartz]

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 !

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

 

[Eric Sosman]

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.

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."