C / C++ / MFC

Bob Stanneveld5-Jul-05 0:25

5-Jul-05 0:25

Behind every great black man...
... is the police. - Conspiracy brother

Blog[^]

LiYS5-Jul-05 0:04

LiYS

5-Jul-05 0:04

Later I found out that
doing swap without the temporary object with

void inplace_swap(int *x, int *y)<br />
{<br />
	 *x = *x ^ *y; /* x = x + y */<br />
	 *y = *x ^ *y; /* y = x - y */<br />
	 *x = *x ^ *y; /* x = x - y */<br />
}

is exactly the same with the three statements above that were commented!
So the question is boil down to when will '^' do the subtraction and when addition!

...always look on the <blink>bright
side of life...
(Whistle)

Bob Stanneveld5-Jul-05 0:31

5-Jul-05 0:31

Why doing such an easy operation so difficult?

Try the following:

void inplace_swap(int* pX, int *pY)
{
    // validate pointers here

    *x = *x + *y;
    *y = *x - *y;
}

This solution is not perfect in the sense that it can cause integer overflow problems. My assembler is rusty, but you could get around this problem by substracting with carry or something..

Behind every great black man...
... is the police. - Conspiracy brother

Blog[^]

Bob Stanneveld5-Jul-05 0:36

5-Jul-05 0:36

If I believe that I'm correct, the version with the temporary object, generates less assembler instructions than this version.

If you take a look at the generated machine code, you'll see that what you are trying to do results in less optimal code!

Behind every great black man...
... is the police. - Conspiracy brother

Blog[^]

toxcct5-Jul-05 1:02

toxcct

5-Jul-05 1:02

why don't you do it that way :

void inplace_swap(int *x, int *y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

TOXCCT >>> GEII power
[toxcct][VisualCalc]

Bob Stanneveld5-Jul-05 2:09

5-Jul-05 2:09

He doesn't want to use the temporary object. I think that the most efficient way is to use the temporary object, but for some reasons, he doesn't want it.. Confused | :confused:

Behind every great black man...
... is the police. - Conspiracy brother

Blog[^]

Toby Opferman5-Jul-05 8:32

Toby Opferman

5-Jul-05 8:32

I think he just wanted the theory[^] behind the XOR swap.

On smaller processors the XOR swap would actually be faster than a temp variable or having to use a 3rd register if registers were already limited. However, you are correct that the optimization of a temp variable can be faster than the generated XOR swap from a C compiler (and using a modern processor).

void SwapXor(UINT *a, UINT *b)
{
	*a = *a ^ *b;
	*b = *a ^ *b;
	*a = *a ^ *b;
}

image00400000+0x1000:
00401000 8b4c2408         mov     ecx,[esp+0x8] ; ecx = b
00401004 8b442404         mov     eax,[esp+0x4] ; eax = a
00401008 56               push    esi
00401009 8b11             mov     edx,[ecx]     ; edx = *b
0040100b 8b30             mov     esi,[eax]     ; esi = *a
0040100d 33f2             xor     esi,edx       ; temp = *a ^ *b
0040100f 8930             mov     [eax],esi     ; *a = esi(temp)
00401011 8bd6             mov     edx,esi       ; edx = *a
00401013 8b31             mov     esi,[ecx]     ; esi = *b
00401015 33f2             xor     esi,edx       ; temp = *b ^ *a
00401017 8931             mov     [ecx],esi     ; *b = esi (temp)
00401019 8b10             mov     edx,[eax]     ; edx = *a
0040101b 8bce             mov     ecx,esi       ; ecx = *b
0040101d 5e               pop     esi
0040101e 33d1             xor     edx,ecx       ; temp = *a ^ *b
00401020 8910             mov     [eax],edx     ; *a = edx(temp)
00401022 c3               ret

void SwapTemp(UINT *a, UINT *b)
{
	UINT Temp;

	Temp = *a;
	*a = *b;
	*b = Temp;
}

00401030 8b542408         mov     edx,[esp+0x8] ; edx = b
00401034 8b442404         mov     eax,[esp+0x4] ; eax = a
00401038 56               push    esi
00401039 8b32             mov     esi,[edx]     ; esi = *b
0040103b 8b08             mov     ecx,[eax]     ; ecx = *a
0040103d 8930             mov     [eax],esi     ; *a  = esi
0040103f 890a             mov     [edx],ecx     ; *b  = ecx
00401041 5e               pop     esi
00401042 c3               ret

1 million XOR Swap = Milliseconds = 10.569012
1 million Temp Swap = Milliseconds = 4.846916

Generally, it's not the number of instructions that make the difference it's how the assembly is structured. This has no bearing in this case though because you get more instructions and you get slower code as well.

You notice that the memory is read multiple times as well as saved multiple times unnesscarily in the code path. You also notice that there was no "true" temp variable ever generated for the other code so even if you eliminate most of the code it's still not an optimal solution.

So, yes while it may look in C that you are being optimal by not using a "temp" variable, if your compiler is smart enough this doesn't matter and does generate faster code as Bob said. If you are working with embedded systems and are coding the direct assembly, an "xor" approach may work better depending on the situation. It could also work if you hand code assembly for different pipelines where 2 instructions may be executed at the same time. This depends though on if a simple "XCHG" instruction would cause a problem with a pipe "stall" or not.

However, in C I think you can rely on the compiler to optimize with the temp variable rather than atempting to do what is considered a lower level optimization in a higher level language (This is not to say that an "xor" swap is always nessecary in smaller CPUs at all, it's just a possible consideration for certain code optimizations which may or may not be useful. Generally XOR is faster to "set a register to 0" as the most common optimization, XOR EAX, EAX back when a "mov" "MOV EAX, 0" was considered a slow operation. I don't think that's the case any more on newer processors).

8bc7c0ec02c0e404c0cc0680f7018827ebee

David Crow5-Jul-05 5:05

David Crow

5-Jul-05 5:05

After step 1, *x contains (*x ^ *y). After step 2, *y contains (*y ^ (*x ^ *y)), which is just *x. After step 3, *x contains ((*x ^ *y) ^ *x), which is *y. Make sense? Any number XORed with itself is 0.

"Ideas are a dime a dozen. People who put them into action are priceless." - Unknown

Toby Opferman5-Jul-05 6:45

Toby Opferman

5-Jul-05 6:45

The logic is this:

A = A (operation) B
B = A (operation Inverse) B
A = A (operation Inverse) B

If you do one operation and then two inverse operations you will have swapped the numbers. The "xor" operator is actually the inverse of itself, so that's why it works the way it does.

For example if you use +, - is the inverse:
A = 10, B = 20
A = A + B (10 + 20 = 30)
B = A - B (30 - 20 = 10)
A = A - B (30 - 10 = 20)
A = 20, B = 10

A = 10, B = 20
A = A * B (10*20 = 200)
B = A / B (200/20 = 10)
A = A / B (200/10 = 20)
A = 20, B = 10

A = 10, B = 20
A = A ^ B (10 ^ 20 = 30)
B = A ^ B (30 ^ 20 = 10)
A = A ^ B (30 ^ 10 = 20)
A = 20, B = 10

xor is also communiative, so it didn't matter the order you have A or B when doing ^. This XOR swap was generally used by small processors which memory operations were slow, so 3 XOR instructions could be faster. That actually used to be the method of setting registers to 0 as well, XOR reg, reg as it was faster than a MOV reg, 0.

8bc7c0ec02c0e404c0cc0680f7018827ebee

Toby Opferman5-Jul-05 6:50

Toby Opferman

5-Jul-05 6:50

So you can think of it as:

1. Combine the numbers together and store in one of the values.

Combined = A + B for example 10 + 20 = 30. In +. But any operation will combine numbers.

2. Inverse, thus if two numbers are combined you will get the opposite number of what you inverse.

Original1 = Combined - B, for example, 30 - 20 = 10. You get the original number.

3. Using the opposite number, now you use the combined number to get the original.

Original2 = Combined - Original1 So you do the inverse again on the new number to get the original.

You can see that if you combine two numbers, you can use those numbers in inverse operations to get the original numbers.

8bc7c0ec02c0e404c0cc0680f7018827ebee

To delete (remove) wizard created functions via IDE of VC++ 2003 ?

PJ Arends5-Jul-05 9:02

PJ Arends

5-Jul-05 9:02

The Stupid XOR Trick[^]

"You're obviously a superstar." - Christian Graus about me - 12 Feb '03

"Obviously ??? You're definitely a superstar!!!" - mYkel - 21 Jun '04

"There's not enough blatant self-congratulatory backslapping in the world today..." - HumblePie - 21 Jun '05

Within you lies the power for good - Use it!

Maxwell Chen4-Jul-05 22:29

Maxwell Chen

4-Jul-05 22:29

Is there any method found in the IDE of Visual C++ 2003 to remove functions seen in "Class View"? (other than manually delete text in .cpp and .h.)

Thanks!

Maxwell Chen

changing color of my form in vc++

smartymanav4-Jul-05 21:45

smartymanav

4-Jul-05 21:45

Hii alll

how can i change the background of my form????in vc++

thanks

Re: changing color of my form in vc++

Alex Korchemniy4-Jul-05 21:54

Alex Korchemniy

4-Jul-05 21:54

You can read up on WM_CTLCOLORDLG[^] or you can set it when you register the window class.

Alex Korchemniy

Re: changing color of my form in vc++

David Spain5-Jul-05 18:43

David Spain

5-Jul-05 18:43

Look in the CFrame, CMDIFrame, CView, or a class derived from one of these, for some methods to do this. Those classes perform the drawing of the windows and their background. There may be some public members that can be directly set also. My personal guess is a CFrame derived class. I don't remember completely, but you may have to use some API functions to get the pointers to the objects that would need to be changed.

The form background should not be in the App class or the Doc class, since these have to do with running the program and storing the data. I know this does not provide all the answer, but just gives somewhere to start.

David Spain, C++ Applications Programmer

Context menu on Tree

--------------------------------4-Jul-05 21:21

--------------------------------

4-Jul-05 21:21

Hi,

I want add a context menu on a tree (hosted in MFC Dialog), everything wotrk fine unless I do not get the menu draw (only a little strip).

So what's wrong in my code :

CMenu menu;
POINT pp;

GetCursorPos(&pp);

if (menu.LoadMenu(IDR_MENU_TREE))
{

menu.TrackPopupMenu(TPM_LEFTALIGN | TPM_RIGHTBUTTON,
pp.x, pp.y,
AfxGetMainWnd()); // use main window for cmds
}

Thanks in advance ...

Re: Context menu on Tree

Bert [Otherside82] Derijckere5-Jul-05 0:31

Bert [Otherside82] Derijckere

5-Jul-05 0:31

You are trying to show a top-level menu as a popup menu which is not possible.

You will need to get a submenu of IDR_MENU_TREE, like this:

menu.LoadMenu(IDR_MENU_TREE);
CMenu* pSubMenu = menu.GetSubmenu(0);//Get first submenu
if (pSubMenu != NULL)
{
  pSubMenu.TrackPopupMenu(TPM_LEFTALIGN | TPM_RIGHTBUTTON,
    pp.x, pp.y, AfxGetMainWnd()); //use main window for cmds
}

Hope this helps

creating modeless dialog box

sayup4-Jul-05 20:41

sayup

4-Jul-05 20:41

hello,
i need to know steps to create a modeless dialog box in a parent SDI application.I know that a CreateDialog function is to be used;but how?
please guide

thanks

2249174-Jul-05 20:57

224917

4-Jul-05 20:57

m_pDlg = new CMyDialog;
m_pDlg->Create (IDD_MYDIALOG);
m_pDlg->ShowWindow (SW_SHOW);

Note:Modeless dialog boxes are dismissed by calling DestroyWindow, not End-Dialog. You mustn't allow CDialog::OnOK or CDialog::OnCancel to be called on a modeless dialog box, because both call EndDialog.
Also create it on the heap always.

suhredayan
There is no spoon.

Cedric Moonen4-Jul-05 20:59

Cedric Moonen

4-Jul-05 20:59

It is a little long to explain how to use moldeless dialogs so I'll point you to an article: here[^] is a good article that explains the basis of modeless dialogs.

And, BTW, what do you mean by 'dialog box in a parent SDI application' ? The difference between modal and modeless dialogs is just that the dialog isn't 'blocking' (that means the parent window will still be active with a modeless dialog). The modeless dialog is not 'embedded' in the parent window.

2249174-Jul-05 21:05

224917

4-Jul-05 21:05

cedric moonen wrote:
And, BTW, what do you mean by 'dialog box in a parent SDI application' ?

I think the second parameter below was meant by the parent.
explicit CDialog(
LPCTSTR lpszTemplateName,
CWnd* pParentWnd = NULL
);

suhredayan
There is no spoon.

Cedric Moonen4-Jul-05 21:24

Cedric Moonen

4-Jul-05 21:24

Yes of course I know that you can set a parent to a modeless dialog but I think what he really wants to do (as seen also in his previous post) is a dialog which is 'included' in the parent. So, that is a dialog that has no title bar and that is pasted on the parent. But I'm not sure so that's why I asked for some details.