Archive for the ‘Software’ Category

Import Symbols by Ordinals in Link-Time (using VS)

Thursday, August 7th, 2008

I bet some of you have always wanted to use a system dll file which has a few exported functions, though by ordinal numbers only. Yesterday it happenned to me. I had a dll which exported many a function by ordinal. For instance, you can take a look yourself at ws2_32.dll to learn quickly using dependency walker or another tool the exports of this file. Sometimes you have a 3rd party dll file which you lack both the header file (.h) and a .lib file. And let’s say that you know which functions (their ordinals) you want to use and their prototypes (which is a must). There are several approaches to use the dll in that case.

1) Use LoadLibrary and GetProcAddress programmatically to control the load and pointers retrieval for the functions you’re interested in. This is like the number one guaranteed way to work. I don’t like this idea, because sometimes you are bound to use the library as it is already linked to the file at link-time. Another disadvantage I find important is that you have to change your code in order to support that 3rd party dll functinoality. And for me this is out of question. The code should stay as it is nevertheless the way I use outsider dlls. And besides, why to bother add extra code for imported functions when the linker should do it for you?

2) Use delay-load dll’s, but you will still have to use some helper functions in order to import a function by its ordinal. If you ask me, this is just lame, and probably you don’t need a lazy load anyway.

3) Patching your PE file manually to use ordinals instead of function names. But there’s a catch here, how can you compile your file, if you can’t resolve the symbols? Well, that depends on the support your 3rd party dll has. For example, you might have a .lib file for one version of the 3rd party dll and then everything is splendid. But with a newer version of that dll, all symbols are exported by ordinals. So you can still compile your code using the older .lib, but then you will have to patch the PE. Well, this is the way I did it the first time yesterday, only to witness that everything works well. But even if you change your code slightly and recompile it you will have to fix the PE again and again. This is out of question. And besides you don’t solve a solution with atomic bomb when you can use a small missle, even if you have the skills to do that, something it’s possibly wrong and you should look for a different way, I believe this is true for most things in life anyway.

4) Using IMPORTS statement in your .def file. Which there you tell the linker how to resolve the symbols and everything. Well, this sounds like the ultimate solution, but unforetunately, you will get a linker warning: “warning LNK4017: IMPORTS statement not supported for the target platform; ignored”. Now you ask yourself what target platform are you on? Of course, x86, although I bet the feature is just not supported, so don’t go that way. The thing is that even Watcom C supports this statement, which is like the best thing ever. It seems that Visual C has supported it for sometime, but no more. And you know what’s worse? Delphi: procedure ImportByOrdinal; external MyLib index Ordinal; When I saw that line I freaked out that VS doesn’t have support for such a thing as well, so cruel you say. ;)

5) And finally the real way to do it. Eventually I couldn’t manage to avoid the compiler tools of VS anymore and I decided to give them a try. Which I gotta say was a pleasant move, because the tools are all easy to use and in 10 mins I finished hacking the best solution out there, apparently…

It all comes down to the way you export and import functions. We all know how to export functions, we can use both dllspec(dllexport) or use a .def file which within we state which symbols to export, as simple as that. Of course, you could have used dllspec(dllimport) but that is only when you got a symbolic name for your import.

So what you have to do is this, write a new .def file which will export (yes, export) all the functions you want to import! but this time it’s a bit more tricky since you gotta handle specially the symbolic names of the imports, I will get to that soon. An example of a .def file that will import from ‘ws2_32.dll’ is this:

LIBRARY ws2_32.dll


    MyAnonymousWSFunction @ 555

That’s it. We have a function name to use in our code to access some anonymous function which is exported by the ordinal 555. Well but that ain’t enough, you still need to do one more thing with this newly created .def file and that is to create a .lib file out of it using a tool named  ‘lib’: lib /DEF:my.def /OUT:my.lib

Now you got a new .lib file which describes the imports you want to use in your original PE file. You go back to that code and add this new ‘my.lib’ file in the linker options and you’re done.

Just as a tip, you can use ‘dumpbin /exports ida.lib’ in order to verify your required symbols.

We can now understand that in order to import symbols, VS requires a .lib file (and in order to export you need a .def file). The nice thing about it is that we can create one on our own. However, as much as we wish to use a .def file to import symbols too, it’s impossible.

One or two more things you should know. The linker might shout at you that a symbol __imp__blabla is not found. That does NOT mean you have to define your symbol with a prefix of __imp__. Let’s stick to demangled names, since I haven’t tried it on C++ names and it’s easier sticking to a simple case.

For cdecl calling convention you add a prefix of ‘_’ to your symbol name. For stdcall calling convention you don’t add any prefix nor suffix. But again, for stdcall you will have to instruct the linker how many bytes on stack the function requires (according to the prototype), so it’s as simple as the number of params multiplied by 4. Thus if you got a prototype of ‘void bla(int a, int* b);’ You will define your symbol as ‘bla@8 @ 555′. Note that the first number after the @ is the number of bytes, and the second one is the ordinal number, which is the most important thing around here.

And one last thing you should know, if you want to import data (no cdecl nor stdcall that is) you have to end the symbol’s line with ‘DATA’. Just like this: ‘MyFunc @ 666 DATA’.

I am positive this one gonna save some of you guys, good luck.

Context of Execution (Meet Pyda)

Tuesday, August 5th, 2008

While I was writing an interactive console Python plugin for IDA pro I stumbled in a very buggy problem. The way a plugin works in IDA is that you supply 3 callbacks, init, run, term. You can guess which is called when. I just might put in that there are a few types of plugins and each type can be loaded in different times. I used, let’s say, a UI plugin which gets to run when you hit a hotkey. At that moment my run() function executes in the context of IDA’s thread. And only then I’m allowed to use all other data/code from IDA’s SDK. This is all good so far, and as it should be from such a plugin interface. So what’s wrong? The key idea behind my plugin is that it is an interactive Python console. Means that you have a console window which there you enter commands which eventually will be executed by the Python’s interpreter. Indirectly, this means that I create a thread with a tight loop that waits for user’s input (it doesn’t really matter how it’s being done at the moment). Once the user supplies some input and presses the enter key I get the buffer and run it. Now, it should be clear that the code which Python runs is in that same thread of the console, which I created. Can you see the problem? Ok, maybe not yet.

Some of the commands you can run are wrappers for IDA commands, just like the somewhat embedded IDC scripting in IDA, you have all those functions, but this time in Python. Suppose that you try to access an instruction to get its mnemonic from Python, but this time you do it from a different thread while the unspoken contract with IDA plugin is that whatever you do, you do it in run() function time, and unforetunately this is not the case, and cannot be the case ever, since it is an interactive console that waits for your input and should be ready anytime. If you just try to run SDK commands from the other (console) thread then you experience mysterious crashes and unexplained weird bugs, which is a big no no, and cannot be forgiveable for a product like this, of course.

Now that we know the problem we need to hack a solution. I could have done a very nasty hack, that each time the user runs something in Python, I simulate the hotkey for the plugin and then my plugin’s run() will be called from IDA’s context and there I will look at some global info which will instruct me what to run, and later on I need to marshal back the result to the Python’s (console) thread somehow. This is all possible, but com’on this is fugly.

I read the SDK upside down to find some way to get another callback, which I can somehow trigger whenever I want, in order to run from IDA’s context, but hardly I found something good and at the end nothing worked properly and it was too shakey as well.

Just to note that if you call a function from the created thread, most of the times it works, but when you have some algorithm running heavily, you get crashes after a short while. Even something simple like reading some info of an instruction in a busy loop and at the same time scrolling the view might cause problems.

Then I decided it’s time to do it correctly without any hacks at all. So what I did was reading in MSDN and looking for ways to run my own code at another thread’s context. Alternatively, maybe I could block IDA’s thread while running the functions from my own thread, but it doesn’t sound too clever, and there’s no really easy way to block a thread. And mind you that I wanted a simple and clean solution as much as possible, without crafting some Assembly code, etc. ;)

So one of the things that jumped into my mind was APC, using the function QueueUserAPC, which gets among other params an HTHREAD, which is exactly what I needed. However, the APC will get to run on the target thread only when it is in an alertable state. Which is really bad, because most UI threads are never in that state. So off I went to find another idea. Though this time I felt I got closer to the solution I wanted.

Later on a friend tipped me to check window messages. Apparently if you send a message to another window, which was created by the target thread (if the thread is a UI one and has windows, of course we assume that in IDA’s case and it’s totally ok), the target thread will dispatch that window’s window-procedure in its own context. But this is nothing new for me or you here, I guess. The thing was that I could create a window as a child of IDA’s main window and supply my own window-procedure to that window. And whenever a message is received at this window, its window-procedure gets to run in IDA’s thread’s context! (and rather not the one which created it). BAM mission accomplished. [Oh and by the way, timers (SetTimer) work the same way, since they are implemented as messages after all.]

After implementing this mechanism for getting to run in original’s IDA’s context, just like the contract wants, everything runs perfectly. To be honest, it could easily have not worked because it’s really dependent on the way IDA works and its design, but oh well. :)

About this tool, I am going to release it (as a source code) in the upcoming month. It is called Pyda, as a cool abbreviation for Python and IDA. More information will be available when it is out.

SOAP Is So Tricksy

Friday, January 11th, 2008

I started to code in .Net at work a while ago, yes yes have a laugh at me, I still kick your ass in Assembly ;) Anyway, we use SOAP heavily and it is really wrapped well in C#, you invoke the remote methods seamlessly as if they were a local interface/methods to use. We wanted to see the performance of our server, so I wrote some simple stress tests in C#, of course. I configured my IIS to work with my SOAP libraries and started running the tests. Then after a long long while, an exception is thrown from the server notifying me that the session is null. Needless to say, our service needs authentication and stores some info about it (it requires a login before usage). I wasn’t sure why the session is dropped, because all other connections kept on working and invoking methods on the server. So something here was fishy. I googled for ‘dropped sessions’ and all the stuff I could find about .Net, IIS and Sessions. They gave tips like check the Event Viewer for logs that the server is recycling etc. Looking at the Event Viewer of the server I didn’t find anything special nor any indication that something happened to the server. And no, the server wasn’t recycling cause otherwise all the other connections would have dropped at the same time as well as that one I saw, therefore I eliminated options like the files in the virtual directory of the services were changed or scanned… (Some weird feature of the ASP.Net Web Service, go figure). Eventually I sniffed my own network with WireShark and since I was stress-testing the server I gathered loads of packets in a jiffy, realizing it’s not the way to go. However I managed to catch the exception while sniffing the connections (while restarting the sniffing every few seconds… :) ) and analyzing the data yielded that the client (that is, my test app) used out of the blue some session id that I didn’t see earlier in the same log I captured (mind you I didn’t have the full log). Spooky something. I did the test again, and got same results. Then I thought why not to change the session time of my webservice in IIS to 1 min. You guessed it right, it so happened that the problem occurred more frequently, so now I was sure the problem is in my code and not something wrong configured with the server or the client uses random sessions ids for some reason… never know with bugs, you know, especially when you stress-test. hihi

The next thing I was doing, since I didn’t want to sniff the whole session of the connection(s) was to add some code for logging the time of last method-invocation and when that null session exception is thrown to see how many seconds have elapsed since that last invocation. Immediately it showed that some invocation happened after 1 minute, meaning the session at the server is already expired and yet the client would still use that same session id it got from the beginning. Every connection was made from a different thread, and each thread could talk to a few webservices at the same time. When the exception is thrown I know which webservice/method raised it and to that function I added the last time thingy.

In the end, I had some ‘if random(100) < 1’ that resulted in true only after some time in a while, the bug didn’t surface up from the beginning cause everytime that it did the invocation of the remote method, the session time out will be reset, but some rare times, the invocation hasn’t occurred for more than the default session time-out (20 mins)  and thus the exception and dropped connection.

The solution was simple, though we had two options: To add cookies to the client side so we don’t need a session at the server, and even if the session is expired the server will still recognize our cookie and serve us well. The other solution, which was simpler now, was to call the login method again to re-initialize the authentication, which really creates the Session at the server side and everything works better now.

I had this stupid bug because SOAP is wrapped so nicely in .Net that you don’t ‘feel’ it, nor even remember that you use a server here, I really mean it guys. So why in the world should I call login after I did it once in the initialization?! Now I got a reason, apparently :)

A C Tidbit

Wednesday, December 12th, 2007

Yeah well, the title is a bit weird… So I’ve been reading the C standard for fun (get a girl?) and I was interested in two things actually. First of all, while I was reading it a friend asked me a question if the layout of local (auto) variables in the scope of a function have any special order. The short answer is no. And I won’t extend this one much. Although nothing is mentioned about the “stack” and how variables are supposed to be in memory in this case. Now this is a bit confusing because in structures (and unions) what you define is how they lie in memory. But this only sounds normal because if you need to read something from hardware in a way, you really care about the order of the members of the structure… Though as it happened to me while I was reversing I saw lots of variables-recycling. Means the compiler uses a variable (which is in the stack) and afterwards went it’s out of scope it re-uses the same memory place for another variable in the same function. Or it might be the coder sucked so much that he used the same variable a few times…:P which I doubt since for once the dword was used as a byte. So the only thing you know about the stack of the function is its layout according to that same function’s code of that specific version and only after compilation (assembly listing is good too).

The other thing I was curious about is the pointer arithmetic that is mixed with integer expressions:

char *p = 0;
p + 5

We all know that it will evaluate to 5. But what about:

long *p = 0;
p + 5 ?

This one will evalute to 20, 5 * sizeof(type)…

Actually the compiler translates the operator [], array subscript, such that p[i] = *(p + i). Nothing is special here as well, unless you didn’t mess with C for a long while… Now it becomes really powerful when you can cast from one pointer type to another and use the indirection operator, so for example, say you want to scan for a dword in a memory block:

long *p = <some input>;
for (int i = 0; i < 1000; i++)
   if (p[i] == value) found…

 But in this case, you can miss that dword since we didn’t scan in byte alignment, so we have two options, either changing the type of pointed p to be a char, or to make a cast… In both ways we need to fix the limit of scan, of course.

So now it becomes:

if (*(dword*) ( ((char*)p) +i) == value) found…

This way p is scanned in byte units, because i is multiplied by sizeof(char). And we take that pointer to char, which is incremented by 1 every iteration and cast it to a dword and then derference that… I think you cannot avoid the use of a cast (or maybe automatic conversion) in the matter of getting this task completed.

Now it might be obvious to most of you, but I doubt it, since I fell in this trap as well:

long a[4] = {0};
printf(“%d”, &a[1] – &a[0]);

What will this code print when executed? I thought 4, as the sizeof of ‘a’ element is a 4 (denoted from the ‘long’ type), but to my surprise ‘1’ was printed; as it will do it as if the subscripts were the operands, however the result will be signed integer. Thus 1 – 0.

The bottom line is that p[i] is *((char*)p + i*sizeof(p[0])) and p[i] – p[j] is ((char*)&p[i] – (char*)&p[j])/sizeof(p[0]). Well the latter is less useful, but if you thought the printf above will return the sizeof the element then you are wrong :)

SQL: Setting NOCOUNT Programmatically

Friday, December 7th, 2007

As I mess with SQL at work, I learnt about some feature which is called, NOCOUNT. This feature tells the server to return the number of affected rows after each query a client does, thus most of the times wasting bandwidth for unused/unwanted data. I was interested in setting this option server-wide. Although, some people will say it’s a bad move, because if you later have more DB’s on the server which need this feature, bla bla… But I know what I want and that’s what I will do.

The problem was how to set it programatically, I searched the inet for a bit, but didn’t come up with anything useful. So I decided to write that snippet on my own. It’s a bit tricky, but once you see it, it looks ok.

USE master;
DECLARE @CurrentValue AS INT;
CREATE TABLE #tmp (v VARCHAR(50), w INT, x INT, y INT, z INT);
      EXEC sp_configure 'User Options';
SELECT @CurrentValue = y FROM #tmp;
SET @CurrentValue = @CurrentValue | 512; -- 512=NOCOUNT
EXEC sp_configure 'User Options', @CurrentValue;

The trick was how to get the results from the EXEC sp_configure so you can read them yourself, the solution was to create a temporary table which you instruct SQL to insert the results of sp_configure into that table. Later on, you can simply read from this table and do whatever you’re up to. This way we can preserve the original value and in addition set the NOCOUNT flag (512, as a bit field…).

Say No to Redundant Checks

Wednesday, August 29th, 2007

I had a long argument with a friend about some check that I don’t do in diStorm. He only said that apparently I don’t do that check (if statement to test some value.) But if it was not important enough he wouldn’t have said that in the first place, right? :) And I told him that he is right – I don’t, because it is absolutely not necessary. Soon I will let you judge yourself. Eventually we got nothing with that argument, probably both sides are mad (at least I was pissed off) and the code left the same.

Now let me show you an example where I will ask you if you do an (extra?) test of the result or not. Since I’m a Win32 guy, here we go:

char buf[256];
int length = GetWindowText(HWND, buf, 256);
if (length == 0) return ; // No string for some reason, though I don’t care why.

memcpy(DST, buf, length+1); // Include null termination char.
Well, that’s a useless code, but still good enough for the sake of conversation. So I get the caption of some window and copy it into another destination buffer. Did you notice that I did not check the length before copying to DST?! (And yes, DST is the same size as buf). Oh no!! Am I doomed now? Of course not, it is guaranteed that the length will be less than 256 for sure. Because otherwise the API is broken. Now we can start another flaming about who’s fault it is, but spare me this, please. So if the API is broken, it will be probably a bug, and will break other applications which use it. But that’s not the point. Say the API is fine, why don’t I check the length before I memcpy? Am I doing anything wrong? I will say it shortly: NO. My code is just fine (as long as DST size is at least buf’s size, of course). So his accusations were that I should be a code-monkey-freak and consistent. And then he said something like “And what if in the future the API changes?”, Well, bammer, all other API’s users are now broken as well. If it was for that question, I would have to pad all my code with extra unnecessary IF’s. No thanks. Besides if I won’t trust my API’s what should I trust? They are the basis for every appliaction.

Now in diStorm the case is the almost the same, there is some internal function that you call with lots of parameters, one of them is an output param that receives the size which was written to some buffer you supply as well as a maximum size of that buffer. So I examine the return code and see whether I can use the data in the buffer or not, and then I know that the size of written entries in my buffer cannot exceed the maximum size I supplied. So why the heck should I check that writtenEntriesCount < MaximumEntries? Tell me, please!

The only rational I can see is to make an assertion (and only in debug mode) that everything is correct. But that’s not a must, and not doing that won’t even let you the possibility to say that I am a bad coder. The thing is, that both the internal function and its caller were written by me, and both are internal only (not exported in any way) so as long as one of them (probably the called) guarantees that the written entries don’t exceed the maximum size. Everyone are is happy. If it wasn’t the case, I should have had a crash (buffer overflow, access violation), just something nasty, that will hint of the buggy function. Now we can get into the philosophical issue of whether the callee or caller should make that test, or both. But for me, as I see it, it’s better be put inside the called function since it must work well for the interface it supplies. And I always think ahead and ask myself “…and what if someone will call that function and forgets(/doesn’t know -) to add the extra check?”

Don’t get me wrong assertions are really useful devices, I really suggest you use them. It just happened that diStorm doesn’t have them. Maybe I should add them. And yet, it’s not a must.

Lib hell (or DLL hell)

Tuesday, August 21st, 2007

In the last few months I got many emails regarding diStorm compilation, usually for different compilers and platforms. So now I’ve been working in the last week to make diStorm compileable for all those compilers. Some of them are in DOS (OpenWatcom/DJGPP/DMC), some of them are for Linux (mostly GCC) for its varying distributions and the rest are for Windows (MSVS, Mingw, TCC, etc…).

The problem begins with the one and only function of the diStorm library, called distorm_decode. This function gets a lot of parameters, the first one is the offset of the code as if it was loaded in the memory (AKA virtual address). For example, you would feed it with 0x100 for .COM binary files (that is, DOS). This very parameter’s type is varying according your compiler and environment, it might be a 32bits integer or, prefereably, a 64bits integer (unsigned long long/__uint64). If you have a compiler that can generate 64bits integer code, then you would prefer it to 32 bits code. So when you disassembler 64bits code you will be able to set any 64bits offset you just like. Otherwise, you will be limited to 32bit offsets.

So I got a special config.h file for diStorm, where there you configure the relevant macros so your compiler will be able to compile diStorm. The config.h is eventually there for all portable macros. There you also set if you would like to use the 64bit offsets or not.

Now the distorm_decode function uses that integer type which is dependent on your decision (which will probably be derived from the support for 64bit integers by your compiler). To simplify the matter, the diStorm interface is a function with the following declaration:

#ifdef SUPPORT64
void distorm_decode(unsigned long long offset);
void distorm_decode(unsigned long offset);

Now, this function is actually exported by the library, so a caller project will be able to use it. And as you can see, the declaration of this function may change. What I did till now was to have this macro (SUPPORT64) defined twice, once for the library itself when it’s compiled and once for the caller project, so when it uses the library, it will know the size of integers it should use. So far, I didn’t get any problems with it. But then since many compilers (say, for DOS) don’t support 64bit integers, it is a pain in the ass to change these two different files. I couldn’t come up with the same header file for the sake of the caller project, since it might get only a compiled version, and then what? Do trial and error until it finds the correct size of the integer? I can’t allow things to be so loosy.

Things could get really nasty, if the library was compiled with 32bit integers, and then the caller project will use it with 64bit integers. Stack is unbalanced, it will probably crash somewhere when trying to use some pointer…soon or later you will notice it. And then you will have to know to comment out the macro on the caller project.

After I got this complaint from one of the diStorm users, I decided to try and put an end to this lib hell. I tried to think of a different ways. It would be the best way if I had a reflection in C, or if I had a scripting language which in there I could determine the size of the integer in runtime and know how to invoke distorm_decode. Unfortunately, this is not the case. Starting to think of COM out there, or SXS and other not really helpful ways to solve DLL hell. I sense it’s the wrong way. Since it is a library after all, and I don’t have the luxory of running code, I mean, it could be really solved with running code and asking the library (or rather the DLL actually) what interface should I use… reminds me of QueryInterface somewhat. But alas, I can’t do that either, since it’s compile time we’re talking about. So all I got is this lousy idea:

The exported function name will be determined according to the size of the integer it was compiled with. It would look like this:

#ifdef SUPPORT64
void distorm_decode64(unsigned long long offset);
#define distorm_decode distorm_decode64
#else … you get the idea

But we are still stuck with the SUPPORT64 macro for the caller project, which I think there is no option and we will have to stick with it to the bitter end…

Then what did we earn from this change? Well pretty much a lot, let’s see:

1) The actual code of existing projects don’t need to be changed at all, the macro substitution will do the work for it automatically.

2)The application now won’t get to crash, since if you got the wrong integer size, means you won’t find the exported symbol.

3)Now it becomes a linker time error rather than runtime crash/error. So before the caller project will get to fully be linked, you will know to change the SUPPORT64 macro (whether to add it or drop it).

4)The code as it was before could lead you to a crash, since you could manually enable/disable the macro.

Well, I still feel it’s not the best idea out there, but hey, I really don’t want to write some code in the caller project that will determine the interface in runtime and only then know which function to use…it’s simply ugly and not right, because you can do it earlier and cleaner.

I would like to hear how would you do it? I am still not committing my code… so hurry up :)

FAT Bastard

Monday, June 25th, 2007

Hey, sorry for being so quiet for the last week… been busy.

 Anyways, this is an interesting thing that happened to me a couple of weeks a go. My father bought some IPod nano thingy, I wouldn’t call it fake, but it has its advantages, radio, video and it even lets you delete files directly. Don’t get me wrong, I myself have the IPod nano which is really cool and prolly enough for most of my needs. But it is pretty expensive for a 2gb disk… oh well. So I was uploading songs to my father’s player. I was kinda lazy and decided to dump all songs in the root directory. After a while I got some message while trying to copy more songs, something like “Cannot create a file or directory”. It really annoyed me, I thought it might be something with the unicode file names, so I even tried to rename them to English alphabetic, just in case, but for no avail. At this moment, I wanted to give up. I was lacking any idea of what the problem might be. I almost thought the player is broken in some way and should be replaced…who knows.

The day after I sat with my friends from work, telling them this issue, no one had any idea what it might be. (And they are people like me who should have the faintest idea.. but nothing). So I told them that the only crazy idea I had in mind is that I can’t copy the songs because the player is formatted with FAT16. Which if you know or not, has a static size (of sectors) for the root directory. It means that if you allocate all these sectors, the root directory is full and you can’t continue creating a directory or copying a new file onto it. I even wrote a sample that shows how to parses FAT12 (FAT16 is easier to parse, because the size of a chain pointer is a whole 2 bytes, not 1.5…but both are piece of cakes compared to todays FS’s). Anyways, I got back home, formatted the player’s disk, for some reason it got crazy and did directory loops (recursively linking to the same directory) ??? I didn’t know what was going on. And to be honest, really didn’t care. Later on, I decided that now that I think I know what was the problem, I must create directories. Now, in FAT the sub-directories are not limited in any way (as opposed to the root directory). Creating directories and uploading songs, finally, I could easily upload songs and use the whole disk.

I bet that even the support team of the company who invented this player has no idea about this limitation. Funny enough I later noticed that is also supports FAT32 (which doesn’t suffer from the root directory limitation), but it seemed like the player got problems browsing the directories… aargh.

 I think this is a really cool example that shows that your low-level knowledge might help you for real high-level stuff… Knowledge is power. :)

 P.S: When saying “disk” as the player’s storage, I meant a flash storage…but it doesn’t really have anything with my post.

Here is more info about FAT16 vs FAT32.

Focusing on the Focus

Thursday, June 7th, 2007

Sometimes you want to create a pop up window that won’t steal the focus. It seems that even a simple ShowWindow(SW_SHOW); instructs the windows manager to set the focus and activate that window. But what if you want a tooltip ? After all, even a tooltip is a window. So no need to invent the wheel again, you can just use SW_SHOWNA which means – hey, show my window but don’t activate it.

If the window is already activated, thus having the focus, specifying SHOWNA won’t help it, because it’s already got the focus. So you are doomed, and have to wait until some other window takes the focus or when your window is destroyed the window manager will automatically giev the focus to the former window. But that won’t be good enough for a tooltip-like window. So you have to be careful with it. Even if you want to reposition the window using SetWindowPos you will have to set the SWP_NOACTIVATE flag, so it won’t get the focus. That’s true also in a case where the window is hidden, which sounds a bit stupid to me (why activate a hidden window?). But who said it’s perfect? and not to mention the dialog manager…pffft.

After seeing myself that many people have this problem, I decided it’s worth a post. :)

Recursive Data-Structures

Saturday, June 2nd, 2007

For the sake of simplicity a linked list structure is a recursive one, it points to itself.

struct Node {
 int data;

 Node* next;

This case is easy to follow because no matter what, you always end up with accessing a Node structure.

The problem arises when you have recursive data-structures and terminals. I treat a terminal as a data structure which stops the recursion of the recursive data-structure. Unlike the above linked list structure, which stops when the ‘next’ pointer is NULL, the ‘next’ in the complex data-structure might point to either itself or a terminal.

 struct TerminalNode {

 int data;


 struct Node {

 int data;

 Node* next;


Now you might find yourselves asking why would one make the ‘next’ point to a TerminalNode, but that’s a common data-structure layout. For example, an expression tree can represent arithmetic operations in a recursive way, but the values are the terminals – Add(5, Sub(3, 2)).

In a structured layout, it looks something like this (where children is an array of pointers to ‘next’ nodes):

0: ExpressionNode: (type) Add, (children) 1, 2

1: ExpressionNode: (type) Value 5, (children) NULL

2: ExpressionNode: (type) Sub, (children) 3, 4

3: ExpressionNode: (type) Value 3, (children) NULL

4: ExpressionNode: (type) Value 2, (children) NULL

So you can see that in this case an ExpressionNode of ‘Value’ type is a TerminalNode whereas the ExpressionNode is a recursive one.

This type of data-structure is not rare: To be honest, I have this situation in both diStorm64 and diStorm3. In diStorm64 the TerminalNode is actually the Instruction-Info structure which describes the instruction, its mnemonic, its operand types, etc… and in diStorm3, it’s the above ExpressionNode thingy, but much more complex, of course…

Everything is good and nice, but finally I can get to my point in this topic – How do you distinguish between a recursive node and a terminal node? That is, how do you know where the “tree” terminals?

So there are many solutions to this one, I chose to cover two of them. The simplest one is to change your structures by adding another flag which states, “I’m a terminal” or “I’m a recursive node”. But then, it means you have to pay at least another extra byte for both structures. And then examining the flag only after you accessed its structure. Not mentioning, it takes more memory space.

The other solution, which seems to be more common, is to set the LSB (least-significant-bit) in the ‘next’ pointer, thus, if the bit is set, you know you reached a terminal node, even before you accessed it. And seeing the LSB is cleared, you know you continue normally with a recursive node. This is also good for caching, because the structures are compact.

But what happens, if you have 4 types of terminal structures? Well, in a 32 bits environment all structures are (usually/99%) aligned to a 4 bytes boundary, so it means you can easily use the two LSBs, which represent 4 different terminals…

So accessing a single terminal structure is as simple as:

if (pNode->next & 1) {

 pTerminal = (TerminalNode*)(pNode & -1);

 // Use pTerminal here…

} else {

 pNode &= -1;

 // Continue with another node…


You should have noticed by now that a terminal structure doesn’t have a ‘next’ pointer. So a NULL is out of question for terminals, but it’s still OK for recursive nodes, which means “dead-end”, rather than a terminal to mark something bad happened…