Problems with for speed optimized code 
Author Message
 Problems with for speed optimized code

-----BEGIN PGP SIGNED MESSAGE-----

Hi,

  I have a problem with a short piece of code if I choose
 the option "Optimize Speed" when compiling.
 The code is an implementation of the en/decryption algorithm
 RC4. If I do not optimize the program for speed I get another
 (correct) output as when I optimize for speed (though the
 speed optimization would be VERY important for this code!)

 Here is the code, and an example of the output for both
 optimized and not optimized versions:

int clsRC4::crypt(char *buffer, unsigned long length)
{
 unsigned long i = 0, j = 0, t, x;

 if (!(buffer && length)) {     return ERR_NODATA;      }

 for (x = 0; x < length; x++)
 {
  i = (i + 1) % 256;
  j = (j + state[i]) % 256;
  swap8(state[i], state[j]);
  t = (state[i] + state[j]) % 256;
  *((unsigned char *)buffer+x) ^= state[t];
 }

 return 0;

Quote:
}

If I encrypt this plaintext:     00 00 00 00
with this en/decryption key:     00 00 00 00 00 00 00 00
I get this (correct) ciphertext: DE 18 89 41

If I use speed optimization and encrypt the same plaintext with
the same key as above I get this (different and incorrect)
ciphertext: 0A 0F 11 1A

I'd highly appreciate any help which would help me to solve this problem!

(If anyone would like the full source code for testing or whatever just send
me an email and I'll send you a copy.)

 thanks in advance! -Max

~~~
This PGP signature only certifies the sender and date of the message.
It implies no approval from the administrators of nym.alias.net.
Date: Mon Mar 22 18:28:39 1999 GMT

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQEVAwUBNvaL2U5NDhYLYPHNAQFSCAf8Di+6CLn+cPNhdP7tBBhB4YmJb14yaa12
elNhqKPem33MQzav5ftCA5OGFWtzq3Al9Gxwf1vOhNmzI4q3K1hxY+UUaazRZNkb
imKl1gR2rascbKpaF6+cOgrgboWaSohnOE4on1KzEE6DY9YY7u22eFBHywJEYuwh
Sm8cAwL0ep2Yl4gvPJaQBkkP2wWqECxZfnBHrs6HmGt2VaG2MmpekFIgResEqXJ3
XKP7ofdvBMfyEYpt42rc1CkDKr22bn4hJkfUt5uR9Fr1xceLtkDg6Qx9I7v0VyNj
Z0ZNB8BBcjrMbeya5pESeXTHL1HSVlUr+dAZC9PKlDpa6gvPmZjUqQ==
=GJPS
-----END PGP SIGNATURE-----



Fri, 07 Sep 2001 03:00:00 GMT  
 Problems with for speed optimized code

Quote:
>  I have a problem with a short piece of code if I choose
> the option "Optimize Speed" when compiling.

Which version of the compiler are you using?

Do you have a small self contained example that will compile and allow
someone to try to reproduce the problem?

Dave
----
Address is altered to discourage junk mail.
Please post responses to the newsgroup thread,
there's no need for follow up email copies.
http://www.bj.co.uk



Sat, 08 Sep 2001 03:00:00 GMT  
 Problems with for speed optimized code
It's also not uncommon for different behaviour with the optimizer on to be
a symptom of an underlying bug in your code - I have seen many latent bugs
show themselves when the optimizer is enabled.

The advice about comparing the assembly output of the smallest sample that
shows the problem is good advice. Try to minimize the optimizer setting
differences while still making the bug appear in one case and not in another.

Quote:

> I don't know of a single piece of production software that is released with
> all the "optimize for speed" options in the Microsoft compilers (from MSC v
> 5 to MSVC 6).  The optimizer is pretty agressive and the default options
> include a lot of assumptions that few programs can live up to.  Most of the
> time, we disable the more troublesome assumtions, optimize for space, or
> hand optimize it.

> I'd suggest that you generate the assembly for the two passes (optimized and
> not) and compare them.  Perhaps a run through the code in disassembly (and
> comparing the results between the runs) will tell you what part the
> optimization is messing up.

> In all likelihood, you'll identify a particular code construct for which the
> optimizer  won't correctly generate the code. Then you'll have to report it
> to MS, disable the optimization and wait for a fix.

> --
> Bryan Donaldson - IMS HEALTH Strategic Technologies


> >-----BEGIN PGP SIGNED MESSAGE-----

> >Hi,

> >  I have a problem with a short piece of code if I choose
> > the option "Optimize Speed" when compiling.
> > The code is an implementation of the en/decryption algorithm
> > RC4. If I do not optimize the program for speed I get another
> > (correct) output as when I optimize for speed (though the
> > speed optimization would be VERY important for this code!)

> > Here is the code, and an example of the output for both
> > optimized and not optimized versions:

> >int clsRC4::crypt(char *buffer, unsigned long length)
> >{
> > unsigned long i = 0, j = 0, t, x;

> > if (!(buffer && length)) { return ERR_NODATA; }

> > for (x = 0; x < length; x++)
> > {
> >  i = (i + 1) % 256;
> >  j = (j + state[i]) % 256;
> >  swap8(state[i], state[j]);
> >  t = (state[i] + state[j]) % 256;
> >  *((unsigned char *)buffer+x) ^= state[t];
> > }

> > return 0;
> >}

> >If I encrypt this plaintext:     00 00 00 00
> >with this en/decryption key:     00 00 00 00 00 00 00 00
> >I get this (correct) ciphertext: DE 18 89 41

> >If I use speed optimization and encrypt the same plaintext with
> >the same key as above I get this (different and incorrect)
> >ciphertext: 0A 0F 11 1A

> >I'd highly appreciate any help which would help me to solve this problem!

> >(If anyone would like the full source code for testing or whatever just
> send
> >me an email and I'll send you a copy.)

> > thanks in advance! -Max

> >~~~
> >This PGP signature only certifies the sender and date of the message.
> >It implies no approval from the administrators of nym.alias.net.
> >Date: Mon Mar 22 18:28:39 1999 GMT

> >-----BEGIN PGP SIGNATURE-----
> >Version: 2.6.2

> >iQEVAwUBNvaL2U5NDhYLYPHNAQFSCAf8Di+6CLn+cPNhdP7tBBhB4YmJb14yaa12
> >elNhqKPem33MQzav5ftCA5OGFWtzq3Al9Gxwf1vOhNmzI4q3K1hxY+UUaazRZNkb
> >imKl1gR2rascbKpaF6+cOgrgboWaSohnOE4on1KzEE6DY9YY7u22eFBHywJEYuwh
> >Sm8cAwL0ep2Yl4gvPJaQBkkP2wWqECxZfnBHrs6HmGt2VaG2MmpekFIgResEqXJ3
> >XKP7ofdvBMfyEYpt42rc1CkDKr22bn4hJkfUt5uR9Fr1xceLtkDg6Qx9I7v0VyNj
> >Z0ZNB8BBcjrMbeya5pESeXTHL1HSVlUr+dAZC9PKlDpa6gvPmZjUqQ==
> >=GJPS
> >-----END PGP SIGNATURE-----

--
.Bruce Dawson, Cavedog Entertainment.
Makers of Total Annihilation - http://www.cavedog.com


Sat, 08 Sep 2001 03:00:00 GMT  
 Problems with for speed optimized code
-----BEGIN PGP SIGNED MESSAGE-----

Quote:
>>  I have a problem with a short piece of code if I choose
>> the option "Optimize Speed" when compiling.

>Which version of the compiler are you using?

I'm using VC++ 5

Quote:
>Do you have a small self contained example that will compile and allow
>someone to try to reproduce the problem?

yes, i just uploaded it to a friends server (outside the usa because of
crypto export restrictions): http://www.ooenet.at/user/spooky/index.html

Please don't critisize the c++ code, i just started converting the C
functions to C++, optimizations will be made soon ;-)

 thanks,
 //iLLusIOn

~~~
This PGP signature only certifies the sender and date of the message.
It implies no approval from the administrators of nym.alias.net.
Date: Wed Mar 24 00:16:41 1999 GMT

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQEVAwUBNvgvFU5NDhYLYPHNAQFIkwf9F5DcoIhcsFgemJm/zwIG4yap0ZGpbJDV
riNDHQV36LQ0N7johi0V2JHXU4BPqy0o3n4k8KWrEgzKu15vDLm0EUK/Ssun2r+P
hkaTns7R42WRYBlMspKWaEplcFAYxlfsD7uUkncWlFaUiuGMHZSRlCzwCf3oopCO
6zeyiReHM5iMENkJtr4gtSIecE4P6M5viQHKYIImEdYzXZiYKBWHMyuGmXFJ40Js
EPUlmLEaj/gPy7X+KBsMbgVaBlt2gALICsrEYsv58pqBOfVTu2Tvbo3nMLHZb7qs
bFo44nXQx09me6WCAwBPVJTWAXEky56ACkn2/KP1dhwrw+YbSdsUtA==
=XTra
-----END PGP SIGNATURE-----



Sun, 09 Sep 2001 03:00:00 GMT  
 Problems with for speed optimized code
-----BEGIN PGP SIGNED MESSAGE-----

  Thanks for all the answers I have got, I have now (right now)
 solved the problem, though its not a very good solution.
 Here is the (Assembler/C) code, any comments/suggestions?

This is the old version, the one which didn't compile correctly
when optimized for size. It should fill an array of 256 unsigned
char's with the numbers from 0 to 255. But instead, it is filling
it with the numbers 1, 2, 3, ..., 255, 0

C:
           unsigned char state[256];
           for (i = 0; i < 256; i++)
             state[i] = i;

Assembler:
004014ED   xor         eax, eax                      // i = 0;
004014EF   mov         ecx,dword ptr [ebp]           // ecx = state;
004014F2   inc         eax                           // i++ (TOO EARLY!)
004014F3   cmp         eax,100h                      // i < 256 ?
004014F8   mov         byte ptr [ecx+eax-1],al       // state[i] = i (TOO LATE!)
004014FC   jb          clsRC4::init(0x004014ef)+2Fh  // i < 256 ? yes, next for

and here is the version which is compiling correctly, even with
speed optimization. What I did here is to add a do-nothing instruction,
j = i + j;
look at the assembler code, it solved the problem of increasing 'i' too
early. Though I do not like this method, it is short, yet wastes some
speed and makes the code look very bad.

C:
           unsigned char state[256];
           for (i = 0; i < 256; i++)
           {
               state[i] = i;
               j = i + j;
           }

Assembler:
004014ED   mov         ecx,dword ptr [esp+18h]       // ecx = j
004014F1   xor         eax,eax                       // i = 0
004014F3   mov         edx,dword ptr [ebp]           // edx = state
004014F6   add         ecx,eax                       // j = j + i;
004014F8   mov         byte ptr [edx+eax],al         // state[i] = i; (right, now it adds
                                                                       'i' to state[i]
                                                                       before it increases
                                                                       i!)
004014FB   inc         eax                           // i++
004014FC   cmp         eax,100h                      // i < 256?
00401501   jb          clsRC4::init(0x004014f3)+33h  // yes, next for

  Is this a known bug? I did not install any patches for VC++ 5 (are there any? where
 could I get them exactly?).
 Maybe someone could try to reproduce this bug in VC++ 6? If it still exists in
 version 6 I'd send a bug report to MS.
 However, any ideas how I could get rid of this j = i + j, yet keeping the routine
 functioning with speed optimization??

  thanks!
  //iLLusIOn

~~~
This PGP signature only certifies the sender and date of the message.
It implies no approval from the administrators of nym.alias.net.
Date: Thu Mar 25 19:43:40 1999 GMT

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQEVAwUBNvqR705NDhYLYPHNAQFDDwf+LLAqo7f9bP1lGR35JpNgLUCItuaDI46a
NG4wqkv2AZqIOQ4QpYFl/NoXP1WSP4xJbIofZNRxuCqIx4zbvYggog5lIzfBqN5P
Kf6NKq/fTA8JjGgFThon+xDyfXP4R/+DnIebXg1JarExIGhsrnMQjNkOn8nreSSM
Ik77mngDHEzydUGWAhdZTRXOkiZRPlRhlMaGoNT4igPooPeNuskqIrZAaSJLU9tS
AtV0pGp1SsyvZZhaTcjhplg7/8pFyX5GFsNYi/kTxxYd79RjgpltE4ywsNt05m57
cVNra//SE5fMzP2FVJe0eTzBlDfAA8qa9rO52KJQSvaLjwUgc+0/BQ==
=ERMr
-----END PGP SIGNATURE-----



Mon, 10 Sep 2001 03:00:00 GMT  
 Problems with for speed optimized code
There are patches for VC++ 5.0. Install service pack 3 and see if that fixes
the problem.

Also, if you want people to try to reproduce your bug, on VC++ 5.0 or
VC++ 6.0, you need to supply a complete program. Just wrap your code
in main() and declare all the variables and make sure you document all the
switches you are using to compile with. This has two useful purposes:

1) It makes sure that people have some chance of reproducing your
problem.
2) Probably half of the time the process of simplifying down to a postable
example (must be VERY small) will allow you to find the problem.

However in this case I think it is because you are not using the latest
version of VC++ 5.0.

Finally, the best way to work around compiler bugs  is to use #pragma
optimize to disable the problematic optimizations for a single function.
It's clearer and more reliable than adding meaningless variables.

Quote:

> -----BEGIN PGP SIGNED MESSAGE-----

>   Thanks for all the answers I have got, I have now (right now)
>  solved the problem, though its not a very good solution.
>  Here is the (Assembler/C) code, any comments/suggestions?

> This is the old version, the one which didn't compile correctly
> when optimized for size. It should fill an array of 256 unsigned
> char's with the numbers from 0 to 255. But instead, it is filling
> it with the numbers 1, 2, 3, ..., 255, 0

> C:
>            unsigned char state[256];
>            for (i = 0; i < 256; i++)
>              state[i] = i;

--
.Bruce Dawson, Cavedog Entertainment.
Makers of Total Annihilation - http://www.cavedog.com


Mon, 10 Sep 2001 03:00:00 GMT  
 
 [ 6 post ] 

 Relevant Pages 

1. Problems with for speed optimized code

2. Bad Address from Speed Optimized Code

3. How to optimize execution speed of code ??

4. How to speed optimize c/c++ code

5. how to optimize this code for speed

6. Problem with Optimize for speed in VC++ 5.0

7. Optimizing random number generator (was Re: Optimizing code for tests)

8. Throwing exceptions in ATL dll with optimize for SPEED causes Access Violation

9. Speed/safety optimizing recomendation.

10. Optimizing C compiler(speed)

11. optimized code problem

12. Optimizing speed using inline assembly fails - Why?

 

 
Powered by phpBB® Forum Software