Archive for November, 2007

Python: Converting Signedness

Friday, November 30th, 2007

Many times I encounter Python modules that were written in C/C++ which when you use them you get to a really annoying problem. Integers that that module returns are all unsigned. That’s really a problem, because Python longs are (potentially) inifinite (they are digit-strings) AFAIK, unlike C/C++ integers that have a limit of, usually, 32 or 64 bits.

If you pass back -1 to Python and format it as unsigned long, you will get 2**32-1. Now suppose you really want to treat the number inside your Python code as signed integer, you will have to convert 2**32-1 to -1 somehow. Most solutions I saw to this problem was to use struct in the following manner:

import struct
struct.unpack(“l”, struct.pack(“>L”, 2**32-1))[0]

 Packs an unsigned long value of 0xffffffff to (signed) long -1 (using little endian, but I don’t care now about it).

You might want to use unsigned long long – that’s 64 bits integers in order to convert a bigger number. So you can do one of two things, convert your 32 bits integer to 64 bits integer by sign extending (and that’s another whole challenge) it and stuff it into unpack/pack of 64 bits, or test the size of the integer (by how many bits it takes) and call the correct unpack/pack pair.

It was then that I realized why I shouldn’t use this ugly trick. It simply doesn’t support Python’s longs. As I said earlier they are infinite and using this trick you are capped to 64 bits. So I thought of a better way, and not using any stdlib module at all, leaving it pure Python code…

The way we know to change the signedness of an integer is by negating it, which is NOTing all bits of that number and incrementing it by 1, right? (2’s complement) Well true and that should work:

(Say we work with 8 bits integers)

0xfb = -5

>>> ~0xfb
-252
>>> ~0xfb+1
-251
>>> 256-251
5
>>> 0-5
-5

The way it works is: -(256 + (~x+1)) where x is a byte. For every integer we need to scan for its most significant bit… We can do it the other way around with the following formula (x – NEXT_MSB(x)):

>>> 0xfb – 0x100
-5

This way it’s like we changed the sign bit of the integer and fixed the number as well. Both formulas can work for all integers’ sizes. But the key here is to find the MSB. I prefered to stick to the latter formula rather than the former, since it seems to be shorter. But it doesn’t really matter, both work.

So now we have to code it, and as you should know me already – in one-liner device! The first challenge is to find the MSB, something like this should suffice in C(!):

for (int i = 7; i >= 0; i–)
  if (x & (1 << i)) break;

This will work for a byte integer, and note that we must start from the end towards the start. Otherwise we won’t find the MSB but the LSB. The problem in Python is that we don’t know the size of the longs we mess with and we need to come up with a trick to find its MSB.

The lame trick I used for converting a number into decimal ASCII string, will be used here too and it goes like this:

for i in xrange(2**32):
 if (i / (1 << i)):
  break

We try to divide the input number by 2, 4, 8, 16, 32, … and when the result is 0, we know that we are out of bits. I said it’s lame because we use division, which is slow. If you got any other idea write to me please.

Another drawback is the limit of the numbers we scan, we are limited to 2**32, this is huge enough and I guess you will never reach that, or I will be dead first prolly :o. Using Erez’s trick (see here), we can make it a bit more elegant and stop as soon as the MSB was found.

I am not sure whether you noticed, but supplying an input of a negative number isn’t a smart move, we will have to check for it specifically. Eventually this is the code I came up with:

(Note that the input “bits-stream” can be any size)

def signed(n):
 return n if n < 0 else n – [i for i in (2**j if n/(2**(j-1)) else iter(()).next() for j in xrange(2**31-1))][-1]

>>> signed(0xb)
-5
>>> signed(0xfb)
-5
>>> signed(0xffffb)
-5
>>> signed(0xffffffffffffffffffffffffb)
-5L 

GZ-LN

Posted in Algorithms, Python | 3 Comments »

Delegators #3 – The ATL Way

Saturday, November 24th, 2007

The Active-Template Library (or ATL) is very useful. I think that if you code in C++ under Windows it’s even a must. It will solve your great many hours of work. Although I have personally found a few bugs in this library, the code is very tight and does the work well. In this post I’m going to focus on the CWindow class, although there are many other classes which do the delegations seamlessly for the user, such as: CAxDialogImpl, CAxWindow, etc. CWindow is the main one and so we will examine it.

I said in an earlier post that ATL uses thunks to call the instance’s window-procedure. A thunk is a mechanism to convert a function invocation between callee and caller. Look it up in Wiki for more info… To be honest, I was somewhat surprised to see that the mighty ATL uses Assembly to implement the thunks. As I was suggesting a few ways myself to avoid Assembly, I don’t see a really good reason to use Assembly here. You can say that the the ways I suggested are less safe, but if a window is choosing to be malicious you can make everything screwed anyway, so I don’t think it’s for this reason they used Assembly. Another reason I can think of is because their way, they don’t have to look-up for the instance’s ‘this’ pointer, they just have it, wheareas you will have to call GetProp or GetWindowLong. But come on… so if you got any idea let me know. I seriously have no problem with Assembly, but as most people thought that delegations must be implemented in Assembly, I showed you that’s not true. The reason it’s really surprised me is that the Assembly code is not portable among processors as you know; and ATL is very popular and used library. So if you take a look at ATL’s thunks code, you will see that they support x86 (obviously), AMD64, MIPS, ARM and more. And I ask, why the heck?when you can avoid it all? Again, for speed? Not sure it’s really worth it. The ATL guys know what they do, I doubt they didn’t know they could have done it without Assembly.

Anyhow, let’s get dirty, it’s all about their _stdcallthunk struct in the file atlstdthunk.h. The struct has a few members, that their layout in memory will be the same as it was in the file, that’s the key here. There is an Init function which constructs the members. These members are the byte code of the thunk itself, that’s why their layout in memory is important, because they are get to ran later by the processor. The Init function gets the ‘this’ pointer and the window procedure pointer. And then it will initialize the members to form the following code:

mov dword ptr [esp+4], this
jmp WndProc

Note that ‘this’ and ‘WndProc’ are member values that their values will be determined in construction-time. They must be known in advance, prior to creation of the thunk. Seeing [esp+4] we know they override the first argument of the instance’s window-procedure which is hWnd. They could have pushed another argument for the ‘this’ pointer, but why should they do it if they can recover the hWnd from the ‘this’ pointer anyway…? And save a stack-access? :)

Since the jmp instruction is relative in its behaviour, that is, the offset to the target address is not absolute but rather relative to the address of the jmp instruction itself, upon initialization the offset is calculated as well, like this:

DWORD((INT_PTR)proc – ((INT_PTR)this+sizeof(_stdcallthunk)));

Note that the ‘this’ here is the address of the thunk itself in memory (already allocated).
Now that we know how the thunk really looks and what it does, let’s see how it’s all get connected, from the global window procedure to the instance’s one. This is some pseudo code I came up with (and does not really reflect the ATL code, I only wanna give you the idea of it):

CWindow::CreateWindow:

WndProcThunk = AllocThunk((DWORD)this.WndProc, (DWORD)this);
m_hWnd = CreateWindow (…);
SetWindowLong(m_hWnd, GWL_WNDPROC, WndProcThunk);

This is not all yet, although in reality it’s a bit more complicated in the way they bind the HWND with its thunk…Now when the window will be sent a message, the stack will contain the HWND, MESSAGE, WPARAM and LPARAM arguments for the original window procedure, but then the thunk will change the HWND to THIS and immediately transfer control to the global window procedure, but this time they got the context of the instance!

CWindow::WindowProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
 CWindowImplBaseT< TBase, TWinTraits >* pThis = (CWindowImplBaseT< TBase, TWinTraits >*)hWnd;
 pThis->ProcessWindowMessage(pThis->m_hWnd, uMsg, wParam, lParam, lRes, 0);
}

And there we go. Notice the cast from hWnd to the ‘this’ pointer and the call with the context of the instance, at last, mission accomplished ;)

More information can be found here.

 A new problem now arises, I will mention it in the next post in this chain, but in a couple of words, here’s a hint: NX bit.

Posted in Assembly, C++, Win32 | 1 Comment »

Delegators #2 – C++ & Win32

Saturday, November 17th, 2007

Last post I was talking about using SetProp/GetProp to link between an HWND and an instance to a class that encapsulates the window widget. There’s another way to do it.

The first time you are taught how to create a window in Win32, they tell you that you have to fill in all fields in the WNDCLASS structure, but they always keep on saying to ignore some of the advanced fields. One of the fields inside that structure is cbWndExtra, this one says to the windows manager how many bytes to allocate after the original windows manager’s structure. So suppose all we need is to save the ‘this’ pointer, it means we will need 4 bytes, in 32bits environment system, of course. So we can set cbWndExtra to 4, and then we have a DWORD we can access to as much as we like with the SetWindowLong/GetWindowLong API.

Something like this would suffice:

WNDCLASS wc;
wc. fields = …
wc.lpszClassName = “myclass”;
wc.cbWndExtra = 4;
RegisterClass(&wc);
HWND hWnd = CreateWindow(“myclass”, …)
SetWindowLong(hWnd, 0, this);
ShowWindow(…);
…
..

And later on in the window-procedure, you can do this:

LRESULT WINAPI MyWindow::WndProc(HWND hWnd, UINT message, WPARAM wparam, LPARAM lparam)
{
 MyWindow* pThis = (MyWindow*)GetWindowLong(hWnd, 0);
 if (pThis != 0) return pThis->WndProc(message, wparam, lparam);
 return DefWindowProc(hWnd, message, wparam, lparam);
}

 And there you go. There are a few problems with this technique though. You can’t handle the WM_CREATE message inside the instance’s WndProc, that’s because before CreateWindow returns, the global WndProc will get called with this message, and you didn’t have the chance to set the ‘this’ pointer…

The second problem is that this technique is good only for windows you create yourself, because you control the WNDCLASS… You can use pre-created window-classes of the system by changing their fields in your application only, I think this will create a copy of the pre-created classes only for your process.

Anyhow, to solve the first problem, I saw implementation that create the instance of the object when they receive the WM_CREATE inside the global WndProc. This is really a matter of design, but this way you can call an initializer of the instance once WM_CREATE was received. I can’t come up with another way at the moment if the instance is already created. Maybe just call the initializer on the first message the window gets? Well it’s a bit cracky.

Posted in C++, Win32 | 3 Comments »

Delegators #1 – C++ & Win32

Wednesday, November 14th, 2007

In the technical point of view a Delagator is a call-forwarder, as simple as that. But in the designing aspect it is a technique where an object outwardly expresses certain behaviour but in reality delegates responsibility for implementing that behavior… And thanks for Wiki for sparing me the ugly explanation. :)

The reason I came up to want to implement delegators as seamlessly as possible in C++ was because I got to a situation where I wanted to write a pure OOP wrapper for windows objects (CreateWindow). Now let me get into the juicy details before you raise your eyebrows. And even before that – yes, something like ATL but only for windows. So say you have a class that is responsible for creating a window and controling it by handling its messages and stuff. Sounds legitimate, right? It would look something like:

class Window {
public:
Window(const cstring& name) { m_hWnd = CreateWindow(…) }
void Show () { ShowWindow(m_hWnd, SW_SHOW); }
 …
 ..
private:
 HWND m_hWnd;
};

And you get the notion. It looks ok and it is right, but let’s get further and hit the problem. When we create a window we need to pass the name of the window-class, that is some structure that contains more general info about the class itself, like the background color, mouse cursor and other stuff, but the most important one of them is wndproc pointer. The wndproc pointer is a pointer to a callback function that handles the messages of the windows that belong to this window-class. I assume you know how Win32 Windows system works. Now, can you spot the problem already?

Well, since it asks for a pointer to a function, and we want to have an instance of our Window object per window, there is no way to bind between the two. (OK, I lie, but continue reading please). In our case we would like to have the method of our message-handler being called and not a global function. If you’re not sure why, then think that each window has some private members in its instance that tells special things about that window. So we gotta find a way to link between our instance and our “window-procedure” method.

This is a start:

class Window
private:
LRESULT WINAPI WndProc(HWND hWnd, UINT message, WPARAM wparam, LPARAM lparam)
{
 switch (message)
 {
  …
  ..
 }
 return DefWindowProc(hWnd, message, wparam, lparam);
}
public:
static LRESULT WINAPI WndProc(HWND hWnd, UINT message, WPARAM wparam, LPARAM lparam)
{
 // Delegate to the instance’s window procedure.
 return g_window.WndProc(hWnd, message, wparam, lparam);
}

So now the window-class structure will point to the static function WndProc which when called will delegate its parameters to the internal (private) WndProc that can access the members. It’s almost a good solution. But now we are allowed to have only one window and a global instance that contains it. The good thing is that a static public function can call a private method of the same class, so we can hide the core of it. The bad thing is we still expose an internal function we don’t want to in the first place.

The problem is now to find a way to link between a real window object and our instance. The ID of a window is its HWND (or Handle to Window). So we could hold a list with all HWND’s we created and look it up before delegation and then make the right call to the correct instance. This is too much hassle for nothing. There ought to be a way to store some private data on the window object itself, right? At least I would suspect so. Eventually, after reading some MSDN and searching the net, I found a savior function which is called SetProp (and GetProp ofc). Exmaining their prototypes:
BOOL SetProp(HWND hWnd, LPCTSTR lpString, HANDLE hData);
HANDLE GetProp(HWND hWnd, LPCTSTR lpString);
We actually have a kind of dictionary, we give a string and store a pointer (to anything we’re upto). Afterwards, we can retrieve that pointer by using GetProp. Let’s work it out again:

ctor:
m_hWnd = CreateWindow(…);
SetProp(m_hWnd, “THIS_POINTER”, (HANDLE)this); // Ah ha!

What we did was to link the HWND with the this pointer. The window procedure will look like this now:

static LRESULT WINAPI WndProc(HWND hWnd, UINT message, WPARAM wparam, LPARAM lparam)
{
 Window* pThis = (Window*)GetProp(m_hWnd, “THIS_POINTER”); // Some magic?
 if (pThis != NULL) return pThis->WndProc(…); // Forward the call to the correct instance.
 …
 …
 return DefWindowProc(…);
}

 Well, as for the code here, I don’t handle errors, and I use C casts, so sue me :). I merely wanna show you the mechanism. And if you really wanna get dirty, you will have to RemoveProp when you get WM_NCDESTROY, etc…

After I got this code really working, I still was wondering how ATL does this binding. So I took a look at their code… It seems to have a global linked list with all instances of the windows that ATL created. And then when the global window procedure is get called, it looks it up on that list. In reality it is much more complex then my explanation, since they need to synchronize accesses among threads, make sure the window belongs to the same thread, etc… All that for only the first time call of the window-procedure. Then it sets the REAL ‘window-procedure’ method of the instance itself, and there it uses Assembly, muwahaha. That will be covered next time.

BTW – SetWindowLong cannot work since all you can do is changing the window-class fields. Although, maybe there is some undocumented field you can play with to store anything you like. Never know? :)

Posted in Assembly, C++, Win32 | 3 Comments »

About DIV, IDIV and Overflows

Thursday, November 8th, 2007

The IDIV instruction is a divide operation. It is less popular than its counterpart DIV. The different between the two is that IDIV is for signed numbers wheareas DIV is for unsigned numbers. I guess the “i” in IDIV means Integer, thus implying a signed integer. Sometimes I still wonder why they didn’t name it SDIV, which is much readable and self explantory. But the name is not the real issue here. However, I would like to say that there is a difference between signed and unsigned division. Otherwise they wouldn’t have been two different instructions in the first place, right? :) What a smart ass… The reason it is necessary to have them both is because signed division is behaving differently than unsigned division. Looking at a finite string of bits (i.e, unsigned char) which has a value of -2 and trying to unsigned divide that by -1, will result in 0, since if we take a look at the numbers as unsigneds – 0xfe and 0xff. And naively asking how many times 0xff is contained inside 0xfe, will result in 0. Now that’s a shame because we would like to treat the division as signed. For that, the algorithm is a bit more complex. I am really not a Math guy. So I don’t wanna get into dirty details of how the signed division works. I will leave that algorithm for the BasicOps column of posts… Anyway, I can just say that if you have an unsigned division you can use it to do a signed division of the same operands size.

Some processors only have signed division instructions. So for doing an unsigned division, one might convert the operands to the next bigger size and then do the signed division. Which means the high half of the operand is zero, which makes the division work as expected.

With x86, luckily we don’t have to do some nifty tricks, we have them straight away, DIV and IDIV, for our use. Unlike multiplication, when there is an overflow in division, a division overflow will be raised, wheareas in multiplication only the CF and OF flags will be set. If we like it or not this is the situation. Therefore it’s necessary to convert the numbers before doing the operation. Sign extension or zero extension (depending on the signedness of operands) and only then do the division operation.

What I really wanted to talk about is the way the overflow is detected by the processor. I am interested in that behavior since I write a simple x86 simulator as part of the diStorm3 project. So truly, my code is the “processor” or should I say the virtual machine…Anyhow, the Intel documentation for the IDIV instruction shows some psuedo algorithm:

temp  = AX / src; // Signed division by 8bit
if (temp > 0x7F) or (temp < 0x80)
// If a positive result is greater than 7FH or a negative result is less than 80H
then #DE; // Divide error

src is a register/immediate or a memory indirection, which results in a 8bits value that will be signed extended to 16bits and only then will be signed divided by AX. So far so good, nothing special.

Then comes some stupid looking if statement. Which on the first look says, that if temp is 0x7f or 0x80 then bam, raise the exception. So you ask yourself how these special values have anything to do with overflowing.

Reading on the next comment makes things clearer, since for 8bits input, the division is done on 16bits, and the result is stored inside 8bits that are signed values, the result can vary from -128 to 127. Thus, if the result is positive, and the value is above 127, there is an overflow, because then the value will be treated as a negative number, which is a no no. And same for negative results: if the result is negative and the value is below 128 there is an overflow. Since the negative number cannot be represented in 8bits and as a signed number.

It is vital to understand that overflow means that a resulting value cannot be stored inside its destination because it’s too low or too big to be represented in that container. Don’t confuse it with carry [flag].

So how do we know if the result is positive or negative? If we take a look at temp as a byte sized, we can’t really know. But that’s why we got temp as 16bits. That extra half of temp (high byte) is really the hint for the sign of the whole value. If the high byte is 0xff, we know the result is negative, otherwise the result is positive. Well I’m not 100% accurate it, but let’s keep things simple for matter of conversation. Anyway, it is enough to examine the most significant bit of temp to know its sign. So let’s take a look at the if statement again now that we have more knowledge about the case.

if temp[15] == 0 and temp > 127 : raise overflow

Suddenly it makes sense, huh? Because we assure the number is positive (doesn’t have the sign bit set) and the result is yet higher than 127, and thus cannot be represented as a sign value in a 8bits container.

Now, let’s examine its counterpart guard for negative numbers:

if temp[15] == 1 and temp < 128: raise overflow

Ok, I tried to fool here. We have a problem. Remember that temp is 16bits long? It means that if, for example, the result of temp after the division is -1 (0xffff), our condition is still true and will raise an overflow exception, where the result is really valid (0xff represents -1 in 8bits as well). The problem origin is in the signed comparison. By now, you should understood that the first if statement for a positive number uses an unsigned comparison as well, although temp is a signed value.

We are left with one option since we are forced to use unsigned comparisons, (my virtual processor supports only unsigned comparisons), then we have to convert the signed 128 value into a 16bits unsigned value, which is 0xff80. As easy as that, just signed extend it…

So taking that value and putting it in its place we get the following if statement:

if temp[15] == 1 and temp < 0xff80: raise exception

We know by now that temp is being compared to as an unsigned number. Therefore, if the result was a negative number (must be above 0x8000) and yet it was below 0xff80, then we cannot represent that value in a 8bits signed container, and we have to raise the division error exception.

Eventually we want to merge both if statements to be one, sparing some basic boolean algebra, we end up with:

if (temp > 0x7f) && ((temp < 0x8000) || (temp > 0xff80)):

    then raise exception…

Posted in Algorithms, Assembly, diStorm | 3 Comments »