the optemizing beast, that thing is too much for me

[StoneColdCrazy]

I am poor at implemention efficient algorithms, I can write almost anything, but that anything isn't always fast enough. <br><br>Can someone help me to understand how to make things faster?<br><br>Here is a flipping-the-image algorithms I wrote a year ago, don't use it anymore, so I won't benifit from improved version.  It's C++, but most of C guys today know C++ well.<br><br>// typedef unsigned char BYTE;<br>// typedef unsigned short int WORD;<br><br>// class TBitmap<br>//   {<br>//     WORD width;<br>//     WORD height;<br>//     BYTE *data;     // data eventually newed to<br>//   };                // data[width*height]<br><br>//---------------------------------------------------------<br>void TBitmap::FlipHorizontal()<br>  {<br>    WORD mid = width/2;<br>    WORD offset = 0;<br>    BYTE temp;<br><br>    for(WORD i=0, x; i<height; ++i)<br>      {<br>        for(x=0; x<=mid; ++x)<br>          {<br>            temp = data[offset+x];<br>            data[offset+x] = data[offset+width-x];<br>            data[offset+width-x] = temp;<br>          }<br><br>        offset += width;<br>      } <br>  }<br><br><br>the 486 assembly code produced for this function is almost 1 page long, there have to be a shorter and faster way..<br><br>~al<br><br><br>

 

[sachindn]

Instead of dividing width by 2 go for bitshift.<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;As dividing instruction ultimatley breaks down into a set of bitshifts.<br><br>&nbsp;&nbsp;&nbsp;Istead of using temp for swapping use this logic:<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a=a+b;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b=a-b;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a=a-b;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;

 

[shail]

hi,

this problem particularly interests me for i have similar issues in my crypto codes.. so here's my 2 bits..

1. sachindn's soln will have bits over flow for (a+b) larger than (2^32 -1) another method could be:
to swap a and b
a=a XOR b
b=b XOR a .... (b XOR (a XOR b) is a)
a=a XOR b .... ((a XOR b) XOR b is b) thus swapped

2. secondly in s/w implementations it is possible to improve speed at the cost of memory. u need always to flip ..90, 180, 270 degrees.. these represent four quadrants.
can u maintain coordinates in 2 arrays and values in a single array.

coordinate array A points at all coordinates in +ve x and +ve y direction (quadrant 1) and array B points to -ve x and -ve direction (quadrant 3). keeping all this as pointers pointing to same values array one in forward direction and one -ve direction... now no need for ur flipping function.. just set a flag and read the correct coordinates. like for 1st, 2nd, 3rd and 4th quadrant for 0, 90, 180, 270 degrees flip..

hope it make sense..

afaik,
shail