Secrets to Optimization - Function Pointers

Let me present you with a bit of code which you might find quite commonly in a program:

void function_1(type a, type b)
{
  if (complex_formula())
  {
    method_a(a, b);
  }
  else
  {
    method_b(a, b);
  }
}
...
void function_2(type *a, type *b, size_t ab_len)
{
  while (ab_len--)
  {
    function_1(*a++, *b++);
  }
}

I see this quite often in all kinds of situations. Where some repetitive action keeps calling a function which uses a static calculation which in turn does one of two things. Since this action is making many calls to a function which is doing the exact same sub action on this set of data, it really is a waste to redetermine which sub action we're dealing with for every element of data.

Imagine if a program has an option to approximate fractions from floating point using algorithm A or algorithm B, if the program repeatedly has to check which algorithm it's supposed to be using on each floating point number in a set, it is wasting time that could be spent on actually working on these numbers.

The most obvious way to speed this process up is to setup a variable which contains the result of complex_formula(), so complex_formula() itself doesn't have to be recalculated again and again, and instead we just do something like "method = complex_formula()" once, and just check "method" each time. However if we have a case where we have multiple methods, we'd have to turn this into a switch(). Once we have several methods, we'll be wasting a bit of minor but cumulative CPU cycles for every time we need to perform this action.

In order to bypass any overhead, or make the overhead insignificant, we make use of a sometimes neglected feature - function pointers. Let's rewrite the prior example:

void (*function_1)(type a, type b) = method_a;
...
void function_2(type *a, type *b, size_t ab_len)
{
  while (ab_len--)
  {
    function_1(*a++, *b++);
  }
}

With this new bit of code, method_a will be used each time. If we want to recalculate which method to use because an option was changed. then we can do something like this when need be:

function_1 = complex_formula() ? method_a : method_b;

But this complex_formula() won't have to be rechecked for each element of an array, or even overhead for comparison and jumping if we did ifs/switch on a variable.

I've looked into the difference of calling a function directly or via a pointer, and on the CPUs I looked at, the overhead was 1 cycle or even 0, meaning the overhead is negligible if any. Either way, it's less than that of a comparison and jump, and surely several of them.

If you remember some posts back where I was talking about quick sorting, I setup a sorting testing frame work like so:

struct qsorters
{
  char *name;
  void (*func)(void *, size_t, size_t, int(*)(const void *, const void *));
};

static struct qsorters qsorters[] = {{"AT&T", qsort_att},
                                     {"BSD 1983", qsort_bsd2},
                                     {"BSD 1990", qsort_bsd3},
                                     {"BSD 1993", qsort_bsd},
                                     {"diet libc", qsort_dietc},
                                     {"DJGPP", qsort_djgpp},
                                     {"glibc", qsort_gnu},
                                     {"IBM", qsort_ibm},
                                     {"Linux", qsort_linux},
                                     {"Microsoft", qsort_microsoft},
                                     {"Sun", qsort_solaris},
                                     {"Syslinux", qsort_syslinux},
                                     {"uClibc", qsort_uclibc},
                                     {"insane", qsort_insane},
                                     {"Simple", qsort_simple},
                                    };

Now my sorting framework simply looped through the array and did the sorting tests on qsorters[i].func() instead of it needing to setup some kind of switch system to translate names into the function to call. If you want table driven methods to apply to functions, this is the way to do it. Imagine how much slower my testing framework would've been if I had to use a switch on this. This also makes the code simpler to read and write, just like arrays make more sense than x1. x2. x3. etc...

Function pointers are a wonderful thing to use whenever you have multiple functions which are the same black box, which when on the same input offer the same output, just use different methods internally.

This also extends well to when mixing with other kinds of optimizations. Quite often people try to optimize critical sections of their code using hand tuned assembly. Now on the x86 platform, there exists several instruction sets which can be used for optimization that not every CPU has, for example, MMX, 3DNow!, SSE, SSE2, etc...
If one wanted to offer good assembly optimizations for something, I all to often see scattered across programs code like this:

void func()
{
  if (detect_sse2())
  {
    func_sse2();
  }
  else if (detect_3dnow())
  {
    func_3dnow();
  }
  else if (detect_mmx())
  {
    func_mmx();
  }
  else
  {
    func_i386();
  }
}

If func() is called say 10,000 times a frame in a video processing program, it really lowers the overall FPS that could be processed if instead the following method was used:

void (*func) = func_i386;
void (*func2) = func2_i386;
etc...

void instructions_detect()
{
  if (detect_sse2())
  {
    func = func_sse2;
    func2 = func2_sse2;
  }
  else if (detect_3dnow())
  {
    func = func_3dnow;
    func2 = func2_3dnow;
  }
  else if (detect_mmx())
  {
    func = func_mmx;
    func2 = func_mmx;
  }
}

With this, instruction_detect() can be called when the program is started, or the library is initialized, and since the instruction set is not going to change in the middle, you just call this once and forget about it. With this, you can achieve optimal speed for any given processor in a program, without wasting any speed for overhead, aside from an initial call.

The Sorry State of Sound in Linux

Lets start with some background.
Back in the old days, if you had a PC, there was only one card called "the sound card", which of course was the Sound Blaster 16. If you were playing any of the popular games back then, many of them only supported the SB16 for sound. Other companies who wanted to start releasing sound cards had to include Sound Blaster emulation if they wanted to get any kind of real sales. Sometimes this emulation was buggy, but you wouldn't know that until after you bought it. For this reason, people who wanted sound took no short cuts and only bought SB16s.

Thus back when Linux was first starting out, which was on the PC for the 3x86, there was only one sound card which demanded immediate support. Understandably, Sound Blaster support was completed and done very well rather early on for Linux. Since the API was good, as well as that most Linux programs which provided sound targeted this API, people who wanted to provide drivers for their sound card made their sound drivers use the same API. At this point, the API for the Sound Blaster became known as the Linux sound API, and all the various sound card drivers got merged into one neat little package, this later became the Open Sound System or OSS for short.

Since OSS was UNIX oriented and rather good, the other UNIX OSs starting up at that time such as FreeBSD and NetBSD wanted sound support too, and OSS was ported to them as well. Today OSS runs on virtually every UNIX OS except Mac OS X, but Linux, *BSD, Solaris, are covered, as well as even AIX and HP-UX and more.

Now from a developer standpoint, if you wanted to create a simple application with sound output, and you wanted it to work on the various UNIXs available today, the choice was simple, you write the code for OSS, and it's all nice and portable.

However, there was one major drawback perceived with OSS, and that was mixing. Say you want to listen to music while listening to the news. Not exactly that hard to setup if the music is soft and the news is loud. However when OSS was originally designed, it let the sound card handle 'mixing' which would allow multiple sound outputs be mixed together. But more modern sound cards decided to follow the path of modems and became mostly software. Once this happened, all features of a sound card had to be written up in software to work properly, and mixing wasn't always a focus, nor is it always a simple matter. Therefore many newer sound cards would lack mixing under OSS.

Therefore two new sound systems came into existence, aRts and ESD which were used mostly by KDE and Enlightenment/GNOME respectively. They used new APIs which did mixing before sending sound to OSS. They intended that new programs would use these APIs. Now I looked at both aRts and ESD, aRts seems pretty easy to use, even easier than OSS, and I wrote up a sound player in less than 5 minutes with aRts. ESD on the other hand looks like it might have more features than aRts to use, but also looks much more complex than aRts. With programs written to use one of these two, you could run multiple applications which use one of these sound systems at the same time and get sound out of both of them.

The problem with aRts or ESD though is that there are two of them, so while many KDE or GTK apps will use one or the other, you can't run both of them at the same time, as you can only have one of them work with OSS at one time because of the 'mixing' problem. It's even more problematic that you still have native OSS applications that don't go through another system. To solve many of these problems, library wrappers were invented.

First we have the Simple DirectMedia Layer (SDL) which wraps around OSS, aRts, ESD, and even sound systems on Windows and Mac OS X. Sounds good for portability, since it works everywhere, and you can have it use whichever sound engine on UNIXs so everything can play nice together. Unfortunately though, SDL uses sound only via a callback interface. While this is fine for many applications, it can get annoying sometimes, and in some applications which generate audio on the fly, not only can it be complicated to do properly, it might even be impossible to maintain proper sound sync.

Another nice competitor which I like is libao which wraps around OSS, aRts, ESD, and several other UNIX specific sound engines. The API for libao is also really easy to use, quite similar to that of aRts, and I managed to whip up sound applications with libao in no time at all. Unfortunately libao hasn't been updated in some time, and certain wrappers it has seem to be a bit buggy. libao also only supports blocking audio, which makes it complicated to write certain applications where the audio is generated while it's playing, forcing the program to use threads, hope one doesn't fall asleep while the other is working, and use semaphores and mutexes.

Because the general idea of libao was good, the MPlayer team took libao, fixed several limitations, updated it, fixed bugs, added many more sound wrappers, even two for Windows and one for Mac OS X, and dubbed their creation libao2. With MPlayer, you can change which sound wrapper to use with the param -ao and specify which system to use, or set permanently via the config file. I even took some libao2 DirectSound code, used it in a Windows application, and a Microsoft developer who I know looked at it and told me the code looked really good, which goes to show the quality of the underlying wrappers. Unfortunately though libao2 is bound to MPlayer, it has all kinds of MPlayer library calls within it meaning a major dissecting operation is needed to use it in another application. Perhaps some MPlayer or library developers can get together and separate the two, add on any needed features, and then we application developers can finally have a portable sound library to use, while potentially also allowing MPlayer to get better sound output on more obscure drivers because a developer who doesn't use MPlayer but another sound program might fix it.

Now while application developers are all worrying about their precious libraries, the developers of the portable UNIX sound system - OSS, decided to go closed source and offer extra features (which regular users don't need) to paying customers. This of course created an uproar, and some Linux developers decided to create a new solution.

Now instead of just rewriting OSS at the core, or using a wrapper (which understandably doesn't fix the underlying mixer problem), or updating the existing open source OSS at its base, some developers for some absurd reason decided they needed a whole new system and API to go with it. This is known as the Advanced Linux Sound Architecture or ALSA for short. This new API is huge, mostly undocumented, incredibly complicated and completely different than OSS. Which means various sound card drivers have to be rewritten for ALSA, and all applications have to be rewritten (or have more sound system support like SDL and libao) in order to use ALSA.

Other advantages of ALSA is that they included a software mixer (which doesn't always work). But as should be apparent, applications aren't magically overnight going to start switching over to ALSA. And as ALSA isn't portable, people who want to support BSD and Solaris will of course be using OSS. Meaning to support ALSA would mean needing to support OSS and ALSA. Since OSS exists on Linux, why even bother? Realizing this, the ALSA developers programmed OSS emulation into ALSA, so sane developers can just program for OSS. But the big embarrassment here for ALSA is that using ALSA via its OSS emulation is usually better than using ALSA directly. I've heard from many users of SDL or libao powered programs that telling those wrappers to use OSS (which ends up being used via ALSA's OSS emulation) works better with less gaps (or other problems) in the audio than using ALSA directly by those wrappers.

But for some really stupid reason, ALSA's OSS emulation doesn't support mixing. Which in the end really defeats the purpose of ALSA in the first place. I also have two sound cards which work both under OSS and ALSA and find OSS to just work better. Even more shocking is that I found in cards that have hardware mixers installed, they don't seem to be used by ALSA's OSS emulation, leaving such users without mixing in OSS apps. However, for some reason, I'm seeing a lot of propaganda lately that I have to make all my new applications use ALSA and not OSS because OSS is deprecated. I really doubt that because Advanced Linux Sound Architecture now exists that suddenly FreeBSD has deprecated OSS. How can something portable be deprecated just because one really near sighted OS can't figure out how to deal with life? Using non portable APIs is what is deprecated. I've smartly been forwarding all such ALSA propaganda to /dev/null, but it does bother me that my laptop's internal sound card only has support by ALSA in Linux. And with all the propaganda, I am worried what if ALSA makes more headway? It's already annoying that some Linux distros for example ship SDL without the OSS bindings installed, and it could get worse.

Now a friend of mind recently decided to switch to Linux because he noticed how much better it is than Windows in ways that are important to him. Since he has a newish laptop, the only drivers he could find for it are ALSA. Now for some reason, sound is really scratchy for him, and he has very limited volume controls, making him want to go back to Windows where sound works properly.

Earlier this week, another friend of mine informed me that the closed OSS has been constantly worked on since the last open sourced OSS was put into Linux years ago, can be downloaded and installed from from their website for free, and is superior to ALSA as well. It even offers ALSA emulation. This sounded interesting to me, and I headed over to the OSS website to install OSS on my friend's laptop to see if it would fix his sound problems. And lo and behold, sound is now crystal clear for him, he has much more finely tuned controls of volume, and can raise it higher than ALSA was able to. I put some research into the closed sourced OSS, and I see it has software mixing, and even software resampling which works very well. I proceeded to install it on my laptop, and now got much better sound support there as well. Only thing is that the ALSA emulation isn't working for me too well, but as I only currently have one app which is ALSA exclusive, I don't mind much, but it is annoying knowing that the previous version of this app supported OSS.

All this shows me is that ALSA is truly garbage, and a very bad idea from the ground up. If you want good sound support under Linux, the best, and sometime the only feasible option is to install the closed source OSS. With this, you always get mixing (even using the hardware mixer which ALSA doesn't always do), support for a dozen UNIX OSs, and finely tuned controls. They also made some API improvements to make it easier for application developers to do more advanced things with their audio. It's also nice to see spdif support, and even be able to send AC3 and other audio formats directly to OSS without needing to decode it first.

The real problem here being that it's closed source which makes many people for some reason step away from it. But being that the best video drivers for Linux are the closed source nVidia ones, excellent closed source sound drivers being the best doesn't surprise me. Being that I want the best possible use of my computer, and don't care for any dumb ideals, I'll take closed source drivers if they work well and don't do anything they shouldn't be doing. But this makes many distro packagers shy away from bundling or supporting the close source drivers in any way. Now while in the case of nVidia or ATI drivers, developers write apps for OpenGL or X11 which the closed source drivers support well, and it's the same API being developed for either way, we don't have to worry much if the distros don't support them. But in the case of OSS, if the distros package a completely different incompatible interface, and provide SDL and friends with everything but OSS support, we can't use the closed source drivers even if we wanted to, taking away our freedom, forcing us to put up with garbage, and defeating good portability.

We need to make a stance and stop this ALSA propaganda in its tracks, and produce many good applications with no ALSA support whatsoever and telling the propaganda spewers to go wake up. We must get the distros to keep supporting OSS. If they want a new sound system, it should be using the same API as the old one and be what every other UNIX OS uses for native sound.

Now I wish OSS would be opened sourced again, and perhaps we should be talking to 4Front about that, or recreating a full open source up to date equivalent of the closed source one, but there is no reason that we should be diverting all our efforts into a broken, incompatible, unusable, knock off.

Read here for more information about the latest closed source version of OSS and why we should be using it .

To recap, if you have sound issues, try installing the official OSS, start getting recognition going that OSS is what we're supposed to be using and that ALSA is garbage. Make sure to tell your distros that ALSA is garbage, and they should not be removing OSS support, and we should have the freedom to use a closed source driver if we want to. Tell application developers that you demand OSS support. Tell users of your application that want ALSA that ALSA is garbage, and point them to the closed source OSS if they have troubles with the open sourced one. We should also see about talking to 4Front about reopening source or updating the old open source implementation (or rewrite if need be). We should also see about making libao2 more of a library. If we took these steps, I think the state of sound in Linux, and other UNIX OSs by extension would be better off. If we took these necessary steps, UNIX sound apps wouldn't look like the laughing stock of the sound application community.

Can you trust your security application?

Let me begin with a nice mathematical problem.

Say you have a divorced couple that are currently discussing over the phone how to divide up their possessions. They pretty much split everything equally, till they reach their car. They know they won't get nearly as much as it's worth by selling it, so they'd prefer if one of them would just keep it, but they can't agree to which one. They don't want to meet and they don't want to get another party involved. How can they determine which one should get the car?

They can flip a coin on it, but since this is over the phone, both parties won't be able to see it and agree. Ideally one side would decide what heads and tails means, and the other would say if it is heads or tails, but they need a secure method to transfer these secrets to each other, without either end fearing of some sort of compromise.

This problem is what today's public/private key secure communication technology is based upon, and we have come up with a solution.

One party would take two very large prime numbers, and multiply them and transfer this number to the other party. The first party keeps the two factors as a secret, the other party has no reasonable way to determine the two factors without months of computation. The first party then informs the second party that once the coin is flipped, they will take the larger factor, and look at it's fifth digit from a particular end. If that digit is odd it means the first party chose heads and the other tails, and if it is even, the winning conditions will reverse. Now the second party can flip the coin and report the status back to the first party.

At this point, everything needed to determine the winner has been transferred securely, now the secret can be transferred to decode who the winner was. The first party will tell the second what the two factors were, and they will have reached an agreement on who will retain the car.

Now provided that the duration of this transaction (phone call) was shorter than the time it would take for the second party to factor, and everything was done in the proper order, this entire exchange should be 100% secure. However, what if the second party happened to know that number already, and had the factors on hand? That party could cheat, and tamper with the exchange of information, rendering the transaction insecure.

Now when we look at secure communication technology today, they generally have each side come up with their own variation of the prime number examples above, and each side sends the other a "public key" to match with their own secret "private key". The private key can't be easily derived from the public key, but one will decode data encrypted with the other. Then when transferring, each side encodes and decodes data with their private and the other's public keys. An attacker can't jump in the middle, because it would need to get the private key which is never distributed in order to decode or impersonate one of them.

This security falls apart when the keys in use are older than their cryptographically secure time frame, or when the application doesn't follow the proper procedures. If keys are long and strong enough, and always replaced before their safe time frame limit approaches, and connections aren't opened indefinitely, one should be safe in relying upon the keys. However, a chain is only as strong as it's weakest link. If the application doesn't follow the proper procedures for key exchange, or has errors in its authentication and validation routines, it could be leaving it's users and their data compromisable.

If your security application is closed source, there is the chance that there is a backdoor programmed into it that will go unnoticed. When a company has few employees in comparison to the sheer amount of code it has in its products, there is little to stop one rouge employee to stick a tiny bit of code into a complex bit of security related code. When the amount of code greatly outnumbers the coders, very few people will bother to look and try to envision all the circumstances a bit of tricky code will have to handle and how it will end up handling it.

Consider how someone hacked into the Linux server and tried to embed a backdoor into the source that would later make up Linux releases around the world, read about it here. They inserted a bit of code that if two rare options were used together, an unprivileged user would gain administrator capabilities on that machine. Such a thing would go unnoticed if the person had the ability to modify the source at will without raising any eyebrows.

Let me offer an example. The SSH program allows a user to connect to a computer running an SSH server. When one wishes to connect to the other, they have to supply a user name and password, as well as tell SSH which modes to use.

Here are two existing options:

-1 Forces ssh to try protocol version 1 only.
-2 Forces ssh to try protocol version 2 only.

No person would normally consider to force SSH to try everything it was going to try anyway. Imagine if the developer of an SSH server stuck in a bit of code that if the client only wanted protocol version 1 and only wanted protocol version 2, to grant access even if the password was incorrect. This rouge developer could then gain access to every machine running his SSH server, and no one the wiser. Once this developer knows few at his company will see his work, he has nothing to lose to add such code. If he happens to be caught, and if the code was in a confusing section, he can say he was trying to handle an invalid case, and apparently didn't do it right, it was only an accident.

When your security program is closed source, do you really want to lay the security of your data in the hands of a disgruntled employee somewhere? Can you really trust the protection of walls that you can't see and has no outside review process? Many internal reviews miss things in tricky sections, especially when the group in question takes pride in their work. I'm reviewing code, and thinking to myself, hey we wrote this, we're world class programmers, we're good at what we do, this code is too tricky to really sit down with a fine tooth comb, I'm sure it's right.

Keep in mind though, just because something is open source, doesn't mean something can't be snuck in either. It's just less likely for that malicious code to remain there for too long if the application/library in question is popular and has enough people reviewing it.

But despite something being open source, malicious code can be snuck in without anyone ever noticing, read this paper for background. Now while the attack described where one edits the compiler to recognize certain security code and handle it in a malicious manner is a bit far fetched, similar attacks a bit closer to home are quite possible. If you're using a Linux distro which offers binary packages, what really stops a package maintainer from compiling a modified application and putting that in the distro's repositories? Those running a secure environment may want to consider compiling certain packages themselves and not trusting binaries that we really have no clue what is in them.

But based on this paper, do we have to worry that the compiler or the OS or other libraries would produce the proper binary when we compile this security application ourselves?

Lucky for us, despite what newbie programmers want, our programming languages aren't made up of a series of very high level functions such as compile(), handle_security(), and the like. Such would make it much easier for someone to make the compiler or the library do something malicious when it encounters such a request in the source. In order for such an attack to be really successful, it would have to understand every bit of code it's compiling to make sure the resulting program won't be able to detect the trojan, which is extremely tricky if not near impossible for a compiler to do. Not using a high level compiler or virtual machine gives us a layer of security in that it would be harder for one to pass out an "evil compiler" that would understand what the developer was trying to do and instead have it do something malicious.

But if such an attack were to take place, we'd have to pull out hex editors and disassemblers to see that such code has been snuck in (something which we must do with closed source applications). Take this a step further, it is theoretically possible if the OS were affected, or if the compiler was so smart that it intimately understood that it was compiling a hex editor or disassembler and the like to stick in code that would subvert file reading on executables and libraries to mask such malicious code even in the binary.

Now while some clever guy out there is thinking to himself: "Oh I'm going to do that, it'll be completely undetectable", such a course of action is much much easier said than done. I would be amazed if even a whole team of programmers would be able to pull such a monumental task off. I wouldn't worry too much that such magical wool has been invented to pull over our eyes when we try to decode a binary in a safe environment.

But I would worry if the application or the libraries it depends on are closed source. And even if we have the source, I would question where the binary we happen to be using comes from. If you're using even an open sourced application in something critical, I would advise to have your binary for your application and related libraries examined in a safe environment just to be sure. I just hope no one subverted an OS out there to alter non executable reading and writing on executable files, and have the OS strip/readd code when executable files are transfered.

File Dialogs - Take 2

My previous article on file dialogs generated much feedback, and I got varied responses from all kinds of people. I'll go over the feedback I got, more data I've received, and what ramifications the last discussion produced.

In my previous article, I didn't discuss Windows Vista at all, as I don't have a copy of it, however several people contacted me with screenshots, and described the system a bit.

Lets take a first look:


There is a lot going on here. Up on top, we have a crumbs based directory browser stolen out of GTK, but of course this dialog is better than what GTK offers. It also provides a refresh button, and has a recent directory drop down. You also get a back and forward button to jump all over when looking for something. A nice addition though is a search box. Not sure where the file is? Then search for it! A nice new intuitive feature (taken from Mac OS X though).

Below this we have options to change what's shown, and the style it's presented in. The new directory button is also plainly visible. Then on the left, we have a quick location list like former versions of Windows had, but now in Windows 6, you can add and delete them to your heart's content. I'm not sure if you can rename them though, readers please write in regarding this. We then have the standard files listing from Windows 4+, with the ability to change the view like we expected. And of course to round it off nicely, we have the file input box to jump to files names quickly, and of course type in a path to move to like us power users want. File management features are also available.

But wait, we're not done yet, check this out:

As you can see, the "Folders" section on the left can be expanded to offer a tree view to browse your system. This borrows on the directory only browser (along side a file browser) from Windows 3, but offered in a more robust tree view. It seems a bit weird to see directories in both the directory and file browsers, but this should keep everyone happy. Many people were annoyed with Microsoft for combining the two in Windows 4+, as it was harder to navigate directories, and had to jump past directories to find files.

It seems like with this new version, Microsoft is trying to please everyone, offering every type of browsing possible, and I applaud them for that. I'd be interested to know if you can turn off the directory display in the main file list pane. If anyone knows, please write in.

I'd like to personally play with this to see how it stacks up against KDE 3.5's file dialog, but this looks really solid. The only problem seems to be they stills stuck with some of their virtual directory nonsense, such that you'll see Desktop/User and Desktop/Documents, when the actual tree is Users/User/Desktop and Users/User/Documents. Guess we can't have everything.

Next up, we'll be revisiting GTK. All the responses except for one to my last article agreed with me as to how bad GTK was. Some even wrote in offering demonstrations showing how it was worse than even I knew.

The one person who wrote in disagreeing offered some interesting data. No, he wasn't a developer telling me GNOME/GTK folks were improving it, and he didn't actually disagree with what I described as being bad. He wrote in to say that he has a completely different dialog!

Let us look at our first screenshot:


As you can see, a location bar is provided along with everything else we were familiar with, so one can quick jump, and this happens to work well. The quick locations on the left are also combined into one, so you can add and remove even the built in ones. Not sure about renaming though. But wait there's more!


As the above shows, it also has sane auto complete, instead of an auto complete where you write /usr and end up with /usr/src. I asked for the source of these changes, if perhaps it was from a new or in development version of GTK or GNOME. I was told that he had these dialogs since he setup his PC years ago, and that it was from a usability patch that he had installed. Unfortunately though, he wasn't sure where he got them from, so I guess I'm still stuck trying to replace FireFox and GAIM on my machine.

Let us take a moment to ponder though that there are usability patches out there to vastly improve GTK/GNOME, but we still have no hint of them making their way into the official versions. Perhaps if we start boycotting GTK apps, we'll see the developers do something sane for once. It'd also be nice if it wasn't as slow as molasses.

Next, we come to the Qt file open dialog. Last time, I showed a preview of what Qt 4.3 was going to offer. It seems I got no limit to the responses thanking me for alerting them to the impending disaster.

A friend of mine who has a neat app he wrote using GTK told me how he recently added file browsing support and was very annoyed at how he had to spend a lot of time writing a new file open dialog from scratch because of how utterly atrocious the built in one was. He told me he was considering switching over to Qt because he heard how superior it is, and how he won't have to put up with such stupidity as it has sane stuff built in. However when he saw what Qt 4.3 was planning, he promptly dropped any considerations he had, as he didn't feel like he needed to switch to a GTK knock off and reimplement the file open dialog again. Let us remember that GTK originally ripped Qt off and we don't need to go flip the tables, and pay attention to the $0.02 we get from developers who can't even figure out how to write a sane file dialog.

Another good friend of mine also took it upon himself to spread the word as much as possible. He mentioned it in #qt on Freenode, an IRC channel with many Qt developers. I'm told they were furious when they saw what changes were being planned.

Apparently all this criticism made its way back to Trolltech, and Ben Meyer quickly went to work to rectify the situation.

Here's what was in Qt 4.3's repository as of this past Friday:

As you can see, we're basically back to what Qt 4 had, except with quick locations added to the left. The quick locations allow adding and removing, and settings are saved. Unfortunately, no renaming though, so I'll likely end up with many directories labled "src" confusing me. Also, when using the file name box to browse, the bug from the former Qt 4.3's file save name box is here. If I enter "/usr/src", it'll switch to that path, but the name box will end up stupidly containing "src". Seems like someone forgot to do an S_ISDIR(st_mode) on stat(path) before blindly filling the box with basename(path) when enter is pressed.
I have great faith in the Trolltech guys though, these guys care, and fix things promptly. Lets hope they notice this and fix it before 4.3 is ready. One neat thing about the new version though is that you never need to refresh, as the dialog monitors the directory for changes. But don't worry, the thing is lightening quick, and doesn't seem to lag for anything. I even threw it against a directory with 20,000 files, and it displayed it instantly.

Finally, regarding the KDE 3.5 dialog, I wrote last time how it was the best thing I reviewed, my only disappointment was no renaming. However I was informed that you can rename with it. When you right click on a file, the rename option is labeled "properties". Once the properties come up, you can immediately rename, however the additional benefit here is that you can also click check boxes to change the permissions on a file too! I never thought to look in properties before, as I figured it would just give me info on the file, not actually allow me to change anything. Perhaps there should be some better naming go on over there to make it more intuitive, but it is now apparent that the KDE 3.5 dialog is definitely the superior dialog I have actually reviewed.

I really like the idea of adding a search feature though, and crumb supports usefulness is debatable. So I'll toss it up between Windows 6 and KDE 3.5 as to which is the best till I get a chance to get my hands on Vista.
However, KDE 4 will probably add a search to their file open, and I expect the clever guys at Trolltech to improve further if they receive enough feedback.

If you want developers of your favorite API/OS/Desktop Environment to improve, why not point them to this and the previous file dialog reviews. The guys at Trolltech are definitely open to feedback. Just make sure you're ready for rejection if you try talking to the GTK/GNOME guys, they don't care about anything.

Quicksort

Sorting is something most programs have to do on some occasion. Quicksort is accepted as the best in-practice general purpose sorting algorithm available today. Standard C offers a built in Quicksort under the function name qsort(), with the following prototype:

void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *));

Now while it may be built in, each C library implements it differently. Also, it's designed to work with any kind of type/structure, however one can generally optimize it a bit more for the kind that they're dealing with. Since sorting is important, and can take a while with many items, one generally wants their sorting to be optimized as much as possible.

I've looked at several implementations for various C libraries out there, however they all have one thing in common - messy. One I looked at didn't even implement Quicksort, but a Shakersort.

I'm wondering perhaps if some of the clever people who read this blog can come up with a clean but fast implementation.

To start off, here's a mostly unoptimized simple implementation of the standard qsort():

static void swap_internal(char *a, char *b, size_t size)
{
  if (a != b)
  {
    char t;
    while (size--)
    {
      t = *a;
      *a++ = *b;
      *b++ = t;
    }
  }
}

static void qsort_internal(char *begin, char *end, size_t size, int(*compar)(const void *, const void *))
{
  if (end > begin)
  {
    char *pivot = begin;
    char *l = begin + size, *r = end;

    while (l < r)
    {
      if (compar(l, pivot) <= 0)
      {
        l += size;
      }
      else
      {
        r -= size;
        swap_internal(l, r, size);
      }
    }
    l -= size;
    swap_internal(begin, l, size);
    qsort_internal(begin, l, size, compar);
    qsort_internal(r, end, size, compar);
  }
}

void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *))
{
  qsort_internal((char *)base, (char *)base+nmemb*size, size, compar);
}

Note, this implementation is ~40 lines and can be improved. It can be improved with a better pivot selection, removing the recursion, and throwing in an insertion sort for certain cases.

I'm challenging my readers to give me a good clean implementation, which is under 80 lines (bad indentation doesn't count, I'll be running submitted code through my formatter), compliant, and isn't a total wreck. Creating some helper functions to make it clearer is a good idea too. Almost every implementation I've seen makes use of gotos to all over the place, and has returns smack in the middle of the function.

It'd be nice to bring something so useful into the new millennium, instead of using messy or slow implementations from the 70s.

If I get some nice implementations in, I'll do another piece on how to optimize Quicksort for sorting certain types/structures.