Insane Coding

Progression and Regression of Desktop User Interfaces

2011-12-14T07:58:00.000-08:00

As this Gregorian year comes to a close, with various new interfaces out now, and some new ones on the horizon, I decided to recap my personal experiences with user interfaces on the desktop, and see what the future will bring.

When I was younger, there were a few desktop environments floating around, and I've seen a couple of them at school or a friend's house. But the first one I had on my own personal computer, and really played around with was Windows 3.

Windows 3 came with something called Program Manager. Here's what it looked like:

The basic idea was that you had a "start screen", where you had your various applications grouped by their general category. Within each of these "groups", you had shortcuts to the specific applications. Now certain apps like a calculator you only used in a small window, but most serious apps were only used maximized. If you wanted to switch to another running app, you either pressed the alt+tab keyboard shortcut to cycle through them, or you minimized everything, where you then saw a screen listing all the currently running applications.

Microsoft also shipped a very nice file manager, known as "File Manager", which alone made it useful to use Windows. It was rather primitive though, and various companies released various add-ons for it to greatly enhance its abilities. I particularly loved Wiz File Manager Pro.

Various companies also made add-ons for Program Manager, such as to allow nested groups, or shortcuts directly on the main screen outside of a group, or the ability to change the icons of selected groups. Microsoft would've probably built some of these add-ons in if it continued development of Program Manager.

Now not everyone used Windows all the time back then, but only selectively started it up when they wanted something from it. I personally did everything in DOS unless I wanted to use a particular Windows app, such as file management or painting, or copying and pasting stuff around. Using Windows all the time could be annoying as it slowed down some DOS apps, or made some of them not start at all due to lack of memory and other issues.

In the summer of 1995, Microsoft released Windows 4 to the world. It came bundled with MS-DOS 7, and provided a whole new user experience.

Now the back-most window, the "desktop", no longer contained a list of the running programs (in explorer.exe mode), but rather you could put your own shortcuts and groups and groups of groups there. Rather running programs would appear at the bottom of the screen in a "taskbar". The taskbar now also contained a clock, and a "start menu", to launch applications. Some always running applications which were meant to be background tasks appeared as a tiny icon next to the clock in an area known as a "tray".

This was a major step forward in usability. Now, no matter which application you were currently using, you could see all the ones that were currently running on the edge of your screen. You could also easily click on one of them to switch to it. You didn't need to minimize all to see them anymore. Thanks to the start menu, you could also easily launch all your existing programs without needing to minimize all back down to Program Manager. The clock always being visible was also a nice touch.

Now when this came out, I could appreciate these improvements, but at the same time, I also hated it. A lot of us were using 640x480 resolutions on 14" screens back then. Having something steal screen space was extremely annoying. Also with how little memory systems had back at the time (4 or 8 MB of RAM), you generally weren't running more than 2 or 3 applications at a time and could not really appreciate the benefits of having an always present taskbar. Some people played with taskbar auto-hide because of this.

The start menu was also a tad ridiculous. Lots of clicks were needed to get anywhere. The default appearance also had too many useless things on it.

Did anyone actually use help? Did most people launch things from documents? Microsoft released a nice collection of utilities called "PowerToys" which contained "TweakUI" which you could use to make things work closer to how you want.

The default group programs installed to within the start menu was quite messy though. Software installers would not organize their shortcuts into the groups that Windows came with, but each installed their apps into their own unique group. Having 50 submenus pop out was rather unwieldy, and I personally organized each app after I installed it. Grouping into "System Tools", "Games", "Internet Related Applications", and so on. It was annoying to manually do all this though, as when removing an app, you had to remove its group manually. On upgrades, one would also have to readjust things each time too.

Windows 4 also came with the well known Windows Explorer file manager to replace the older one. It was across the board better than the vanilla version of File Manager that shipped with Windows 3.

I personally started dual booting MS-DOS 6.22 + Windows for Workgroups 3.11 and Windows 95 (and later tri-booted with OS/2 Warp). Basically I used DOS and Windows for pretty much everything, and Windows 95 for those apps that required it. Although I managed to get most apps to work with Windows 3 using Win32s.

As I got a larger screen and more RAM though, I finally started to appreciate what Windows 4 offered, and started to use it almost exclusively. I still exited Windows into DOS 7 though for games that needed to use more RAM, or ran quicker that way on our dinky processors from back then.

Then Windows 4.10 / Internet Explorer 4 came out which offered a couple of improvements. First was "quick launch" which allowed you to put shortcuts directly on your taskbar. You could also make more than one taskbar and put all your shortcuts on it. I personally loved this feature, I put one taskbar on top of my screen, and loaded it with shortcuts to all my common applications, and had one on the bottom for classical use. Now I only had to dive into the start menu for applications I rarely used.

It also offered a feature called "active desktop" which made the background of the desktop not just an image, but a web page. I initially loved the feature, as I edited my own page, and stuck in an input line which I would use to launch a web browser to my favorite search engine at the time (which changed monthly) with my text already searched for. After a while active desktop got annoying though, as every time IE crashed, it disabled it, and you had to deal with extra error messages, and go turn it on manually.

By default this new version also made every Windows Explorer window have this huge sidebar stealing your precious screen space. Thankfully though, you could turn it off.

All in all though, as our CPUs got faster, RAM became cheaper, and large screens more available, this interface was simply fantastic. I stopped booting into other OSs, or exiting Windows itself.

Then Windows 5 came out for consumers, and UI wise, there weren't really any significant changes. The default look used these oversized bars and buttons on each window, but one could easily turn that off. The start menu got a bit of a rearrangement to now feature your most used programs up front, and various actions got pushed off to the side. Since I already put my most used programs on my quick launch on top, this start menu was a complete waste of space. Thankfully, it could also be turned off. I still kept using Windows 98 though, as I didn't see any need for this new Windows XP, and it was just a memory hog in comparison at the time.

What was more interesting to me however was that at work, all our machines ran Linux with GNOME and KDE. When I first started working there, they made me take a course on how to use Emacs, as every programmer needs a text editor. I was greatly annoyed by the thing however, where was my shift highlight with shift+delete and shift+insert or ctrl+x and ctrl+v cut and paste? Thankfully though I soon found gedit and kedit which was like edit/notepad/wordpad but for Linux.

Now I personally don't use a lot of windowsy type software often. My primary usage of a desktop consists of using a text editor, calculator, file manager, console/terminal/prompt, hex editor, paint, cd/dvd burner, and web browser. Only rarely do I launch anything else. Perhaps a PDF, CHM, or DJVU reader when I need to read something.

After using Linux with GNOME/KDE at work for a while, I started to bring more of my work home with me and wanted these things installed on my own personal computer. So dual booting Windows 98 + Linux was the way to go. I started trying to tweak my desktop a bit, and found that KDE was way more capable than GNOME, as were most of their similar apps that I was using. KDE basically offered me everything that I loved about Windows 98, but on steroids. KWrite/KATE was notepad/wordpad but on steroids. The syntax highlighting was absolutely superb. KCalc was a fine calc.exe replacement. Konqueror made Windows Explorer seem like a joke in comparison.

Konqueror offered network transparency, thumbnails of everything rather quickly, even of text files (no pesky thumbs.db either!). An info list view which was downright amazing:
This is a must have feature here. Too often are documents distributed under meaningless file names. With this, and many other small features, nothing else I've seen has even come close to Konqueror in terms of file management.

Konsole was just like my handy DOS Prompt, except with tab support, and better maximizing, and copy and paste support. KHexEdit was simply better than anything I had for free on Windows. KolourPaint is mspaint.exe with support for way more image formats. K3b was also head and shoulders above Easy CD Creator or Nero Burning ROM. For Web Browsers, I was already using Mozilla anyway on Windows, and had the same option on Linux too.

For the basic UI, not only did KDE have everything I liked about Windows, it came with an organized start menu. Which also popped out directly, instead from a "programs" submenu.

The taskbar was also enhanced that I could stick various applets on it. I could stick volume control directly on it. Not a button which popped out a slider, the sliders themselves could appear on the taskbar. Now for example, I could easily adjust my microphone volume directly, without popping up or clicking on anything extra. There was an eyedropper which you could just push to find out the HTML color of anything appearing on the screen - great for web developers. Another thing which I absolutely love, I can see all my removable devices listed directly on my taskbar. If I have a disk in my drive, I see an icon for that drive appearing directly on my taskbar, and I can browse it, burn to it, eject it, whatever. With this, everything I need is basically at my finger tips.

Before long I found myself using Linux/KDE all the time. On newer machines I started to dual boot Windows XP with Linux/KDE, so I could play the occasional Windows game when I wanted to, but for real work, I'd be using Linux.

Then KDE 4 comes out, and basically half the stuff I loved about KDE was removed. No longer is it Windows on steroids. Now KDE 4.0 was not intended for public consumption. Somehow all the distros except for Debian seemed to miss that. Everyone wants to blame KDE for miscommunicating this, but it's quite clear 4.0 was only for developers if you watched the KDE 4 release videos. Any responsible package maintainer with a brain in their skull should've also realized that 4.0 was not ready for prime time. Yet it seems the people managing most distros are idiots that just need the "latest" version of everything, ignoring if it's better or not, or even stable.

At the time, all these users were upset, and all started switching to GNOME. I don't know why anyone who truly loved the power KDE gave you would do that. If KDE 3 > GNOME 2 > KDE 4, why did people migrate to GNOME 2 when they could just not "upgrade" from KDE 3? It seems to me that people never really appreciated what KDE offers in the first place if they bothered moving to GNOME instead of keeping what was awesome.

Nowadays people tell me that KDE 4 has feature parity with KDE 3, but I have no idea what they're talking about. The Konqueror info list feature that I described above still doesn't seem to exist in KDE 4. You can no longer have applets directly on your taskbar. Now I have to click a button to pop up a list of my devices, and only then can I do something with them. No way to quickly glance to see what is currently plugged in. Konsole's tabs now stretch to the full width of your screen for some pointless reason. If you want to switch between tabs with your mouse, prepare for carpal tunnel syndrome. Who thought that icons should grow if they can? It's exactly like those idiotic theoretical professors who spout that CPU usage must be maximized at all times, and therefore use algorithms that schedule things for maximum power draw, despite that in normal cases performance does not improve by using these algorithms. I'd rather pack in more data if possible, having multiple columns of information instead of just huge icons.

KHexEdit has also been completely destroyed. No longer is the column count locked to hex (16). I can't imagine anyone who seriously uses a hex editor designed the new version. For some reason, KDE now also has to act like your mouse only has one button, and right click context menus vanished from all over the place. It's like the entire KDE development team got invaded by Mac and GNOME users who are too stupid to deal with anything other than a big button in the middle of the screen.

Over in the Windows world. Windows 6 (with 6.1 comically being consumerized as "Windows 7") came out with a bit of a revamp. The new start menu seems to fail basic quality assurance tests for anything other than default settings. Try to set things to offer a classic start menu, this is what you get:

If you use extra large icons for your grandparents, you also find that half of the Control Panel is now inaccessible. Ever since Bill Gates left, it seems Windows is going down the drain.

But hardly are problems solely for KDE and Windows, GNOME 3 is also a major step back according to what most people tell me. Many of these users are now migrating to XFCE. If you like GNOME 2, why are you migrating to something else for? And what is it with people trying to fix what isn't broken? If you want to offer an alternate interface, great, but why break or remove the one you already have?

Now a new version of Windows is coming out with a new interface being called "Metro". They should really be calling it "Retro". It's Windows 3 Program Manager with a bunch of those third party add-ons, with a more modern look to it. Gone is the Windows 4+ taskbar so you can see what was running, and easily switch applications via mouse. Now you'll need to press the equivalent of a minimize all to get to the actual desktop. Another type of minimize to get back to Program Manager to launch something else, or "start screen" as they're now calling it.

So say goodbye to all the usability and productivity advantages Windows 4 offered us, they want to take us back to the "dark ages" of modern computing. Sure a taskbar-less interface makes sense on handheld devices with tiny screens or low resolution, but on modern 19"+ screens? The old Windows desktop+taskbar in the upcoming version of Windows is now just another app in their Metro UI. So "Metro" apps won't appear on the classic taskbar, and "classic" applications won't appear on the Metro desktop where running applications are listed.

I'm amazed at how self destructive the entire market became over the last few years. I'm not even sure who to blame, but someone has to do something about it. It's nice to see that a small group of people took KDE 3.5, and are continuing to develop it, but they're rebranding everything with crosses everywhere and calling it "Trinity" desktop. Just what we need, to bring religious issues now into desktop environments. What next? The political desktop?

Reading in an entire file at once in C++, part 2

2011-11-29T12:26:00.001-08:00

Last week I discussed 6 different methods on how to quickly get an entire file into a C++ string.

The conclusion was that the straight forward method was the ideal method, this was verified across several compilers. Since then, people asked me a number of questions.

What if I want to use a vector instead of a string, are the speeds different?
Forget C++ containers, what about directly into a manually allocated buffer?
What about copying into a buffer via mmap?
What do these various cases say about compilers or their libraries? Can this indicate what they're good or bad at compiling?

So to establish some baseline numbers, I created an application which reads the same files the same amount of times using the fastest method possible. It directly creates a buffer aligned to the partition's blocking factor, informs the OS to do the fastest possible sequential read, and then reads the file directly into the buffer. I also tested the suggested method to mmap a file, and copy the contents from there to an allocated buffer. The times achieved for these were 5 and 9 respectively. The latter is slower because of the extra memcpy() required, you want to read directly into your destination buffer whenever possible. The fastest time I now achieved should more or less be the fastest theoretical limit I'm able to get with my hardware. Both GCC and LLVM got the exact same times. I did not test with VC++ here as it doesn't support POSIX 2008.

Now regarding our 6 methods from last time, all of them except the Rdbuf method are possible with std::vector, since there is no std::vector based std::istream.

An interesting thing to note is that C++ string implementations vary greatly from implementation to implementation. Some offer optimizations for very small strings, some offer optimizations for frequent copies, by using reference counting. Some always ensure the string ends with a 0 byte so you can immediately pass them as a C string. In this latter case, operations which operate on strings as a range are rather quick, as the data is copied, then a 0 is appended. Whereas a loop which constantly pushes bytes on the back will have to needlessly set the extra trailing byte to 0 each time. Vector implementations on the other hand don't need to worry about a trailing 0 byte, and generally don't try to internally use all kinds of elaborate storage methods. So if std::vector works for you, you may want to use that.

Let's review times for the 5 applicable methods with our various compilers.

GCC 4.6 with a vector:

Method	Duration
C	23.5
C++	22.8
Iterator	73
Assign	81.8
Copy	68

Whereas with a string:

Method	Duration
C	24.5
C++	24.5
Iterator	64.5
Assign	68
Copy	63

We see that with a vector, the basic methods became a bit faster, but interestingly enough, the others got slower. However, which methods are superior to the others have remained the same.

Now for LLVM 3 with a vector:

Method	Duration
C	8
C++	8
Iterator	860
Assign	1328
Copy	930

Versus for string:

Method	Duration
C	7.5
C++	7.5
Iterator	110
Assign	102
Copy	97

With LLVM, everything is slower with a vector, and for the more complex solutions, much much slower. There's two interesting things we can see about LLVM though. For more straight forward logic, their compiler's optimizations are extremely smart. The speeds approach the theoretical best. I did some profiling on GCC and LLVM, as they're using the same C and C++ libraries, and found that in the straight C/C++ methods for my test program, GCC made 300 memory allocations, but LLVM made only 200. LLVM apparently is smart enough to see inside the various allocations, skip the ones that aren't needed, and place the data directly into the output buffer. But for complex code, LLVM's optimizations aren't that great. In the case of vectors and iterators, downright awful. Someone should file some bug reports with them.

Now for Visual C++ 2010 using vector:

Method	Duration
C	17.8
C++	18.7
Iterator	180.6
Assign	159.5
Copy	165.6

And string:

Method	Duration
C	16.5
C++	20.4
Iterator	224.4
Assign	222.8
Copy	320

We see here that the Copy method, which uses push_back() got a huge performance improvement. This seems to indicate that the STL implementation adds a 0 at the end of each operation, especially push_back(), instead of just when c_str() is called. Otherwise, string is faster.

It's also sad to see that GCC while winning all the cases where iterators were involved, was significantly slower in all the straight forward cases. This seems to indicate that GCC has the smartest optimizations, but fails to optimize well when the logic is straightforward. Someone should look into that.

It seems if you're trying to hold a collection of bytes, or whatever your wchar_t is, but don't care about the specialties of any particular container, as long as you don't push_back() a lot, string seems to be faster.

Finally, here's a table of all the compilers and methods I tested ordered by speed:

Method	Duration
POSIX	5
LLVM 3.0 s C/C++	7.5
LLVM 3.0 v C/C++	8
MMAP	9
VC 2010 s C	16.5
VC 2010 v C	17.8
VC 2005 s C	18.3
VC 2010 v C++	19.7
VC 2010 s C++	20.4
VC 2005 s C++	21
GCC 4.6 v C++	22.8
GCC 4.6 v C	23.5
VC 2005 v C	24
GCC 4.6 s C/C++	24.5
VC 2005 v C++	26
LLVM 3.0 s Rdbuf	31.5
GCC 4.6 s Rdbuf	32.5
GCC 4.6 s Copy	63
GCC 4.6 s Iterator	64.5
GCC 4.6 s Assign	68
GCC 4.6 v Copy	68
GCC 4.6 v Iterator	73
GCC 4.6 v Assign	81.8
LLVM 3.0 s Copy	97
LLVM 3.0 s Assign	102
LLVM 3.0 s Iterator	110
VC 2010 v Assign	159.5
VC 2010 v Copy	165.6
VC 2005 v Copy	172
VC 2010 s Rdbuf	176.2
VC 2010 v Iterator	180.6
VC 2005 s Rdbuf	199
VC 2005 s Iterator	209.3
VC 2005 s Assign	221
VC 2010 s Assign	222.8
VC 2010 s Iterator	224.4
VC 2010 s Copy	320
VC 2005 v Iterator	370
VC 2005 v Assign	378
VC 2005 s Copy	483.5
LLVM 3.0 v Iterator	860
LLVM 3.0 v Copy	930
LLVM 3.0 v Assign	1328

How to read in a file in C++

2011-11-22T15:27:00.001-08:00

So here's a simple question, what is the correct way to read in a file completely in C++?

Various people have various solutions, those who use the C API, C++ API, or some variation of tricks with iterators and algorithms. Wondering which method is the fastest, I thought I might as well put the various options to the test, and the results were surprising.

First, let me propose an API that we'll be using for the function. We'll send a function a C string (char *) of a filename, and we'll get back a C++ string (std::string) of the file contents. If the file cannot be opened, we'll throw an error why that is so. Of course you're welcome to change these functions to receive and return whatever format you prefer, but this is the prototype we'll be operating on:

std::string get_file_contents(const char *filename);

Our first technique to consider is using the C API to read directly into a string. We'll open a file using fopen(), calculate the file size by seeking to the end, and then size a string appropriately. We'll read the contents into the string, and then return it.

#include <string>
#include <cstdio>
#include <cerrno>

std::string get_file_contents(const char *filename)
{
  std::FILE *fp = std::fopen(filename, "rb");
  if (fp)
  {
    std::string contents;
    std::fseek(fp, 0, SEEK_END);
    contents.resize(std::ftell(fp));
    std::rewind(fp);
    std::fread(&contents[0], 1, contents.size(), fp);
    std::fclose(fp);
    return(contents);
  }
  throw(errno);
}

I'm dubbing this technique "method C". This is more or less the technique of any proficient C++ programmer who prefers C style I/O would look like.

The next technique we'll review is basically the same idea, but using C++ streams instead.

#include <fstream>
#include <string>
#include <cerrno>

std::string get_file_contents(const char *filename)
{
  std::ifstream in(filename, std::ios::in | std::ios::binary);
  if (in)
  {
    std::string contents;
    in.seekg(0, std::ios::end);
    contents.resize(in.tellg());
    in.seekg(0, std::ios::beg);
    in.read(&contents[0], contents.size());
    in.close();
    return(contents);
  }
  throw(errno);
}

I'm dubbing this technique "method C++". Again, more or less a straight forward C++ implementation based on the same principals as before.

The next technique people consider is using istreambuf_iterator. This iterator is designed for really fast iteration out of stream buffers (files) in C++.

#include <fstream>
#include <streambuf>
#include <string>
#include <cerrno>

std::string get_file_contents(const char *filename)
{
  std::ifstream in(filename, std::ios::in | std::ios::binary);
  if (in)
  {
    return(std::string((std::istreambuf_iterator<char>(in)), std::istreambuf_iterator<char>()));
  }
  throw(errno);
}

This method is liked by many because of how little code is needed to implement it, and you can read a file directly into all sorts of containers, not just strings. The method was also popularized by the Effective STL book. I'm dubbing the technique "method iterator".

Now some have looked at the last technique, and felt it could be optimized further, since if the string has an idea in advance how big it needs to be, it will reallocate less. So the idea is to reserve the size of the string, then pull the data in.

#include <fstream>
#include <streambuf>
#include <string>
#include <cerrno>

std::string get_file_contents(const char *filename)
{
  std::ifstream in(filename, std::ios::in | std::ios::binary);
  if (in)
  {
    std::string contents;
    in.seekg(0, std::ios::end);
    contents.reserve(in.tellg());
    in.seekg(0, std::ios::beg);
    contents.assign((std::istreambuf_iterator<char>(in)), std::istreambuf_iterator<char>());
    in.close();
    return(contents);
  }
  throw(errno);
}

I will call this technique "method assign", since it uses the string's assign function.

Some have questioned the previous function, as assign() in some implementations may very well replace the internal buffer, and therefore not benefit from reserving. Better to call push_back() instead, which will keep the existing buffer if no reallocation is needed.

#include <fstream>
#include <streambuf>
#include <string>
#include <algorithm>
#include <iterator>
#include <cerrno>

std::string get_file_contents(const char *filename)
{
  std::ifstream in(filename, std::ios::in | std::ios::binary);
  if (in)
  {
    std::string contents;
    in.seekg(0, std::ios::end);
    contents.reserve(in.tellg());
    in.seekg(0, std::ios::beg);
    std::copy((std::istreambuf_iterator<char>(in)), std::istreambuf_iterator<char>(), std::back_inserter(contents));
    in.close();
    return(contents);
  }
  throw(errno);
}

Combining std::copy() and std::back_inserter(), we can achieve our goal. I'm labeling this technique "method copy".

Lastly, some want to try another approach entirely. C++ streams have some very fast copying to another stream via operator<< on their internal buffers. Therefore, we can copy directly into a string stream, and then return the string that string stream uses.

#include <fstream>
#include <sstream>
#include <string>
#include <cerrno>

std::string get_file_contents(const char *filename)
{
  std::ifstream in(filename, std::ios::in | std::ios::binary);
  if (in)
  {
    std::ostringstream contents;
    contents << in.rdbuf();
    in.close();
    return(contents.str());
  }
  throw(errno);
}

We'll call this technique "method rdbuf".

Now which is the fastest method to use if all you actually want to do is read the file into a string and return it? The exact speeds in relation to each other may vary from one implementation to another, but the overall margins between the various techniques should be similar.

I conducted my tests with libstdc++ and GCC 4.6, what you see may vary from this.

I tested with multiple megabyte files, reading in one after another, and repeated the tests a dozen times and averaged the results.

Method	Duration
C	24.5
C++	24.5
Iterator	64.5
Assign	68
Copy	62.5
Rdbuf	32.5

Ordered by speed:

Method	Duration
C/C++	24.5
Rdbuf	32.5
Copy	62.5
Iterator	64.5
Assign	68

These results are rather interesting. There was no speed difference at all whether using the C or C++ API for reading a file. This should be obvious to us all, but yet many people strangely think that the C API has less overhead. The straight forward vanilla methods were also faster than anything involving iterators.

C++ stream to stream copying is really fast. It probably only took a bit longer than the vanilla method due to some reallocations needed. If you're doing disk file to disk file though, you probably want to consider this option, and go directly from in stream to out stream.

Using the istreambuf_iterator methods while popular and concise are actually rather slow. Sure they're faster than istream_iterators (with skipping turned off), but they can't compete with more direct methods.

A C++ string's internal assign() function, at least in libstdc++, seems to throw away the existing buffer (at the time of this writing), so reserving then assigning is rather useless. On the other hand, reading directly into a string, or a different container for that matter, isn't necessarily your most optimal solution where iterators are concerned. Using the external std::copy() function, along with back inserting after reservation is faster than straight up initialization. You might want to consider this method for inserting into some other containers. In fact, I found that std::copy() of istreambuf_iterators with back inserter into an std::deque to be faster than straight up initialization (81 vs 88.5), despite a Deque not being able to reserve room in advance (nor does such make sense with a Deque).

I also found this to be a cute way to get a file into a container backwards, despite a Deque being rather useless for working with file contents.

std::deque<char> contents;
std::copy((std::istreambuf_iterator<char>(in)), std::istreambuf_iterator<char>(), std::front_inserter(contents));

Now go out there and speed up your applications!

If there's any demand, I'll see about performing these tests with other C++ implementations.

Making modconf work with Linux 3

2011-11-19T12:18:00.001-08:00

If you want a nice curses based GUI to add and remove modules from Linux on the fly, you probably used modconf. They say it's deprecated, but they still haven't made anything to replace it.

I noticed that it stopped working on Linux 3.

The problem is as follows, the configuration scripts that come with modconf generally look to see if you're using Linux 2.0 - 2.4 and do one thing, and do another for 2.5 and up. They generally check just the second digit, so now with Linux "3.0" it thinks you're using 2.0 and does something for <2.5 when it should be using the >=2.5 method.

Edit /usr/share/modconf/params
Look for:

case "$(uname -r | cut -f2 -d.)" in
  0|1|2|3|4)
  CFGFILE=$Target/etc/modules.conf
  MODUTILSDIR=$Target/etc/modutils
  ;;
  *)
  CFGFILE=$Target/etc/modprobe.d
  MODUTILSDIR=$Target/etc/modprobe.d
  ;;
esac

Replace it with:

CFGFILE=$Target/etc/modprobe.d
MODUTILSDIR=$Target/etc/modprobe.d

Edit /usr/share/modconf/util
Look for:

  case "$(uname -r | cut -f2 -d.)" in
     0|1|2|3|4)
     modsuffix=".o"
     using_mit=1
     ;;
     *)  modsuffix=".ko" ;;
  esac

Replace it with:

modsuffix=".ko"

And that's all there is to it!

A stronger C/C++ Preprocesser

2011-10-25T18:24:00.000-07:00

Ever felt you needed some preprocessing to generate some C/C++ code for you, but the C preprocesssor is too lacking? Say for example you wanted to include part of another file, or include output from an application. Perhaps the compile should be based on some data found on a remote server? Well, there are stronger preprocessors which work for C/C++, such as PHP.

Here's an example:


/tmp> php test.cpp.php | g++ -x c++ -Wall -o test -
/tmp> ./test
Hello 0
Hello 1
Hello 2
Hello 3
Hello 4
/tmp> cat test.cpp.php
#include <iostream>
int main()
{
  <?php for ($i = 0; $i < 5; ++$i) { echo 'std::cout << "Hello ', $i, '" << std::endl;'; } ?>
  return(0);
}
/tmp>

Here's a more interesting example:


/tmp> php weather_example.c.php | gcc -x c -Wall -o weather_example -
/tmp> ./weather_example
Hi, when I was compiled, the weather here in New York City was 57F
/tmp> cat weather_example.c.php
<?php
$w = file_get_contents('http://www.google.com/ig/api?weather=New+York+City');
$f = '<temp_f data="';
echo '#define __WEATHER__ ', (int)substr($w, strpos($w, $f)+strlen($f)), 'U', "\n";
?>
#include <stdio.h>
int main()
{
  printf("Hi, when I was compiled, the weather here in New York City was %uF\n", __WEATHER__);
  return(0);
}
/tmp>

Goodbye Google

2011-10-16T06:26:00.000-07:00

Google announced they're shutting down Code Search.

I found Google Code Search to be invaluable in the kind of work I do. I saved tons of time by being able to find existing code for something tricky already invented. Or I could compare multiple implementations for things to learn about what different techniques there are for various operations and learn immensely from their pros and cons. If you're reimplementing something yourself, it's also nice to be easily able to find tests cases and other things with Google Code Search.

Now all that is going away. Are there any feasible alternatives? Do we need to start a competing search engine? What are programmers to do when Google cuts the number one online tool for researching code?

C++ 2011 and non rectangular arrays

2011-06-20T06:33:00.001-07:00

Ever wanted to make a non rectangular array? Meaning for example, some multidimensional array where a[0] has 3 members and a[1] has 5 members, and so on.

You could do it with first building up the outermost array, and then add on each subarray separately, but you can't do it all in one shot at initialization time.

But enter C++ 2011 with initializer lists. You can initialize vectors of vectors with as many members at each level you want.

This works:


vector<vector<int>> a
(
  {
    { 1, },
    { 1, 2, },
    { 1, 2, 3, },
    { 1, 2, 3, 4, 5, 6, 7, },
    { 1, 2, },
  }
);

a.size() is 5, a[0].size() is 1, a[1].size() is 2, and so on.

Here's a complete example:

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> a
(
  {
    { 1, },
    { 1, 2, },
    { 1, 2, 3, },
    { 1, 2, 3, 4, 5, 6, 7, },
    { 1, 2, },
  }
);

void print(int t)
{
  cout << t << ", ";
}

template<typename T>
void print(const T &t)
{
  for (auto i = t.begin(); i != t.end(); ++i)
  {
    print(*i);
  }
  cout << '\n';
}

int main()
{
  print(a);
  return(0);
}

Output:


/tmp> g++-4.4 -Wall -o test test.cpp -std=c++0x
/tmp> ./test
1,
1, 2,
1, 2, 3,
1, 2, 3, 4, 5, 6, 7,
1, 2,

/tmp>

C++ 2011 and func

2011-06-20T05:22:00.000-07:00

So what happens to __func__ in different scopes? How about GCC's extension for pretty function names?

#include <iostream>
using namespace std;

namespace
{
  void f()
  {
    auto func = []()->const char *{ return(__func__); };
    auto func2 = []()->const char *{ return(__PRETTY_FUNCTION__); }; //GCC extension

    cout << func() << '\n'
         << func2() << '\n'
         << __func__ << '\n'
         << __PRETTY_FUNCTION__ << endl;
  }
}

int main()
{
  f();
  cout << __func__ << '\n'
       << __PRETTY_FUNCTION__ << endl;

  return(0);
}

Output:


/tmp> g++-4.5 -Wall -o test test.cpp -std=c++0x
/tmp> ./test
operator()
<unnamed>::f()::<lambda()>
f
void<unnamed>::f()
main
int main()
/tmp>


/tmp> g++-4.6 -Wall -o test test.cpp -std=c++0x
/tmp> ./test
operator()
{anonymous}::f()::<lambda()>
f
void {anonymous}::f()
main
int main()
/tmp>

The failure of fragmented security

2011-04-09T11:41:00.000-07:00

With recent attacks against SSL/TLS and certificates, everyone has been thinking a lot about security. What can we do to prevent security problems in the future?

The problem really stems from the fact that our different security components are separate from one another, and don't entirely see eye to eye, leaving gaps for attackers to walk right on through. The current certificate system for certifying the identity of a website is flawed in theory, and in its implementation in many browsers.

The current system works as follows: An entity submits proof of ownership of the domain(s) it owns to one of hundreds of certificate authorities out there, who follow some kind of verification process, and then proceed to give a certificate identifying the site to that entity. This certificate is digitally signed by the certificate authority itself using their private unknown keys. Since no one but the certificate authority itself has their private keys, they're the only ones able to sign certificates in their own name. Browsers ship with a certificate bundle identifying the certificate authorities they trust. In this way, when you see a site with a certificate signed by a known certificate authority, you know it's the site you intended to visit.

Except there's some flaws with this idea. If terrorists wanted to, they could attack a certificate authority's physical headquarters and steal their private keys from their server and sign whatever they want for whichever domain they wish. Or, hackers could hack into machines remotely and perhaps get lucky and find some private keys on them. Or, anyone could start their own certificate authority. It really isn't that hard. Once your new authority becomes trusted by the various browsers, you can proceed to generate certificates for any domain desired.

This entire system has multiple points of failure. Further compounding the issue is that several "trusted" certificate authorities also are in themselves ISPs or run various links in the vast internet. Having both components in your control allow you to impersonate any site for any information passing through your systems. America Online for example is both a trusted certificate authority and an ISP, and anyone who works there and has access to their infrastructure and private keys can view all HTTPS encrypted data passing through their network as unencrypted. Want to buy something with your credit card online? You might want to traceroute your connection first and ensure no one along the way is also a certificate authority your browser trusts.

In order to mitigate a certificate authority signing something it shouldn't have, they invented Certificate Revocation Lists. Where an authority can revoke specific certificates it once signed, since every certificate also has an ID number associated with it. But, some browsers don't even bother checking these lists. Further, some browsers which make use of CRLs and their friends, resume as if nothing happened if they couldn't access a CRL for some reason. Further, these CRLs are subject to the same security problems just described for domains in general. How do I know this is indeed the real CRL? Also, browsers themselves don't have CRLs for the root certificates they ship with, so they are unable to revoke a certificate of a rogue CA if they need to.

But in reality, this entire system is flawed from the ground up. It's so flawed, it doesn't even make the slightest bit of sense. Imagine the following scenario where my boss asks me to inform him of all purchasing details for our web presence needs, and explain why they're needed.

<Me> Okay, we're going to need $35 a year to register all the domains we want for our company, such as company.com and company.net and so on.
<Him> Sure, that's fine, what else?
<Me> Then we're going to need $200 a year for each domain for certificates.
<Him> Why do we need these certificates?
<Me> To prove that we own the domain in question.
<Him> Prove it? Why?
<Me> Browsers like Internet Explorer and Firefox won't realize when they visit our domain that its really our domain, and not some hacker out there trying to impersonate us.
<Him> So if we don't buy these certificates, hackers will be able to get the domain names registered as their own instead of ours?
<Me> No, the domain names are protected by a central authority, they know that we own them, and we tell them to point the domains at our servers, but hackers in between our customer's browser and our server can hijack the connection and make believe they're us without a certificate.
<Him> I don't get it, why can't our customer's browser just check the domain registry and make sure the server they reach is the one we told the domain registry about? Why do we need to buy something from a 3rd party?

This seems strange to you? He's absolutely right. Why can't the hierarchy for domain management also distribute the public keys for our servers? The systems will need to be modified to combine several components and have encryption at each level, but does anything else make an ounce of sense?

Imagine you wanted to buy some property. You have your lawyer, accountant, realtor, and other people directly related to the purchase. After everything is taken care of, and you submit forms to city hall and everything else, you then go down to Joe's House of Fine Refrigerators and have him give you a signed deed that you indeed own the property in question. Makes a lot of sense, right?

Now you call a construction company down to work on your new property, say to merge it with the property next door to it. They want proof you own both properties before beginning. What do you do? You pull out your deed from Joe's House of Fine Refrigerators.

This is the exact state of internet security today. This problem is even pervasive down to every level of infrastructure we use.

Take cookies for example, the system it uses to match domain names runs completely counter to how the domain name system works. It's actually impossible for any browser to properly know for every set of domains in existence whether they're paired or not when it comes to handling cookies for them. It will either fail to submit cookies to some sites that it should, or submit cookies to some sites it shouldn't. Some browsers try to solve this problem with a massive hack, a list of domains that cookies should know are or aren't paired together, which is also incomplete, and needs never ending updates. Without the list, the only difference is that the browser is just wrong more often than without it.

Really, if the hackers were out there, we'd be in big trouble.

C++ Serialization Anyone?

2010-11-25T14:51:00.001-08:00

Today I had one of the most amazing programming experiences that I've ever had, from my entire exciting career. I'm still a bit stunned that this happened. I fully thought what happened was completely impossible till now.

At work, we use a lot of different languages to create our software. It's not odd for us to be working on a project which somehow ends up using a dozen languages. Between server code, client code, databases, communication, mark up, styling, pre-processing, dynamic code generation, and other commonality, it's rather easy actually.

Between all these different programming languages, quite often, we need some sort of data interchange format. There's many to choose from, ranging from something custom to something well known like XML. Using these formats, we can pass data from one segment of our application stack to another. Even when they use two different programming languages. Or to save some data, and load it back up later.

When it comes to these things, soft typed functional languages are generally easier to work with than hard typed. Soft typed languages are very good at building objects from data on the fly, thanks to their ability to not care much about what types they're looking at. Is it a number or a string? Doesn't matter to the soft typed language, as they store it all the same way.

When dealing with database access from hard typed languages, the popular method is to create some sort of catch all or convert to anything type. For some, terms like "QVariant" or "boost::any" are always on their lips. The intent of these and similar constructs is to ease things when dealing with data in an unknown type. Although such constructs generally require building a switch block which needs to check some enumeration method to figure out how to handle the data within the rest of the program. Such code is just downright annoying.

At work some time back, thanks to a lot of the new features C++-201x has been adding, we've been able to build a database access library which can handle data without any of these old kludges. Essentially, database access for us in C++ is now just as easy as it is in PHP (or perhaps even easier!).

Now database communication is great, but there's still the issue of data interchange between two programs, which aren't using a database as an intermediary. Many soft typed or functional languages can have a simple encode() or decode() function, pass it any object, and have a nice string representation of it which can be sent off, or saved to a file for later. C++ and related languages always had the nightmare of needing to iterate manually over every data type, or over a hierarchy to work with something like XML, or similar data formats.

There's those that have created workarounds of course. Such as adding a serialize() function for every type you have to work with individually. Or create some serializable objects that one copies data to or from, and which handle all the serialization work internally. Or one of my personal favorites, write a separate parser which can read a description of a format, and generate the C++ objects and code needed to serialize or deserialize it.

Well, today a coworker and I were putting our heads together on how to deal with a certain project. I wrote code some time back which can serialize/deserialize to and from an std::map which contains numbers, strings, or a mix thereof. We were using this data interchange format between two programs. However, now we need to deal with much more complex data, and a series of key pairs just won't cover it. One end of the equation is C++, the other end is a soft typed language which could pretty easily work with whatever we came up with.

We first thought about the option of using a classic method such as XML or JSON, and use some kind of hierarchical writer from C++, and have the soft typed language just read it directly into an object with one of its built in language features. Till my friend had a brilliant realization. The hierarchy of language containers and their children is recursive, as is any serialization that can encode an infinite amount of data stacked in a hierarchy. Then we started discussing if we could make a serialize() function in C++ which could take any C++ type and work, even when not knowing everything about it in advance. It'd be easy for plain old data types, but gets more complicated once we start dealing with containers of those, and containers of containers.

Of course this is where most conversations along these lines end. But then I brought up template meta programming, and some new features C++ is now adding (and already in GCC), and this discussion went on much further than usual, till the point we were talking code. Well, we got into it, and two hours and two hundred lines of code later, we now have a function with the following prototype:

template<typename T>
std::string serialize(const T &t);

It is able to take any type that exists in C++, and well, serialize it. Have some type which contains some types which contains a few more types which contains some other types? It's all serializeable with this function. No pre-processing, dynamic code generation, compiler hacks, or clumsy per program hierarchical parsing required. It just works^TM.

Now next week, we'll have to write the deserializer function to pull that magic in reverse. Using the same idea, it shouldn't be a problem. If the data matches the supplied structure, parse it in, otherwise, throw an error. But currently, our project is done, as we are now able to have our C++ applications send very complex data to our soft typed languages rather easily.

Looking over the code with my coworker, it all seems extremely obvious. Why the heck didn't we think of this 20 years ago? Now am I getting all excited over something that has been done before? Anyone familiar with anything like this?

Question is, what to do now that we know this? File for a patent? (Yes, I'm evil!) Or perhaps ignore this, as no one cares about this topic anyway?

This just in, 20% of enterprises and most IT people are idiots

2010-10-30T16:29:00.000-07:00

So, who still runs Internet Explorer 6? I do, because sometimes, I'm a web developer.
Along with IE 6, I also run later versions of IE, as well as Firefox, Opera, Chrome, Safari, Arora, Maxthon, and Konqueror. So do my web developer friends and coworkers.

The reason why we do is simple. We want to test our products with every browser with any sort of popularity. Or is a browser that comes with some sort of OS or environment with any sort of popularity. Same goes for browsers with a specific engine.

By playing with so many browsers, we get a feel for things which seem to not be well known (even when documented well), or completely missed by the "pros" who write the most noise on the subject at hand. After work, sometimes my coworkers and I like to get together and joke about how Google security researchers put out a security memo on IE, citing no recourse, while the solution is clearly documented on MSDN, or any similar scenario.

Perhaps we're bad guys for not writing lengthy articles on every subject, and keeping knowledge to ourselves. On the other hand, we get to laugh at the general population on a regular basis. Something which I'm sure every geek at heart revels in.

Here's a small sampling of popular beliefs that we snicker at:

Internet Explorer 6 can't properly display transparent PNGs without resorting to fancy CSS+JS hacks.

JavaScript event handling code can't receive the event handle with IE.

Menus are required to be written in JavaScript to work with all browsers.

IE is unable to receive multiple cookies in a single Set-Cookie field.

Cookies is the (only) proper way to store HTTP state.

IE is not the most advanced browser when it comes to text and typography (because it is, by far).

SSL/TLS can never be used with multiple virtual hosts.

Common examples of how to write proper cross browser code is accurate. (Such as common methods to support embedded fonts for IE and other browsers break Konqueror, when supporting all of them is a piece of cake. Or use embed tags for flash.)

HTTP doesn't have native authentication abilities.

JavaScript should be included in HTML head.

SQL query parameters should be escaped.

Faith in standards committees, large corporations, open source projects, or security researchers.

That multiple versions of IE can't be run on Windows easily, especially older versions of IE on newer versions of Windows.

That last one is actually what prompted this article. 20% of enterprises say they can't upgrade to newer versions of Windows because they need to use IE 6. On top of this, almost every IT guy who had anything to say about this believe in this situation or mentions virtualization as an out. Heck, even Microsoft themselves are saying you need a special XP mode in Windows 7 for IE 6, as is every major article site on the net who comment on this situation.

Hilarious considering that you can install and run IE 6 just fine in Windows 7. There's plenty of solutions out there besides that one too. They've also been around for several years.

Anyways, experts, pros, designers, IT staff and average Internet surfers out there, just keep on being clueless on every single topic, some of us are having a real laugh.

Programming manuals for those who "get it"

2010-10-24T06:12:00.000-07:00

Top secret official programming manuals for certain popular hand held devices have now been uploaded to the usual public document repositories. Some have been around for a while to those who get it, some are new.

Optimizing your file dialog

2010-09-19T04:59:00.000-07:00

Recently, someone asked me why is it that the custom file dialogs in some programs I wrote are able to load a file list so much faster than the so called "native file dialogs" on those operating systems. The answer is that I optimized many areas of loading a file list, and displaying it. Today we'll look at some optimizations that can be performed, instead of using the most obvious approaches to most of the process.

Know your system calls for reading directory entries

You'll want to create some sort of library around the native directory functions in order to use the most efficient path on each operating system. Operating systems vary widely in what they they provide.

Sometimes you have multiple APIs, or a single API with many options you can turn on and off. Unless the provided API is in itself doing everything as efficiently as possible (such as efficiently returning the file names in a sorted matter), you'll want to use the lowest level API, or turn off all options it provides.

If bidirectional or scanning options are provided, turn them off, as you'll want forward only. The overhead for some of these features can significantly slow down the process of obtaining a file list. Same goes for anything else that adds overhead.

Be aware of what information is provided other than file names. Some OSs will return a structure which may also contain file size or file permissions alongside each file. If you're filtering by any of these, use the information directly there, instead of using an additional call to stat() or similar.

In addition to the above, if you need to filter by file size or file permissions, and the API does not provide that information directly, avoid the need for concatenating strings to get your information. A call to stat() would require concatenating a file name onto the directory name if it's not in the current directory. If your OS provides for it, use fstatat() or similar instead (see "OpenGroup Extended API Set Part 2").

Process file names in an optimized manner

Once you start getting back file name(s), before anything, determine the length of a file name, as all other operations will need to know the length. Pretty much every operating system / file system limits the length of a file name to 255 bytes, the length of that can fit in a single byte. Compute the length (if need be) and keep reusing this cache.

If you want to do extension filtering, now is the time to do so. Do not use strrchr(), or anything of the sort to find where the extension begins (searching for a period). Functions like strrchr() will first travel to the end then look back, effectively being O(2N). Since you already know the length of the string, use an O(N) function to look back from the end. Perhaps even using one which can scan multiple bytes (whole CPU words) at a time.

For extension filtering, the most common method is generally one that breaks down to a series of compares. Put a little more thought into your algorithm usage! Either sort your list of extensions and binary search it for a match, or use perfect hashing. In either case, make sure the sorting or hashing phase is performed just once.

For copying the files names you want elsewhere, use memcpy() instead of strcpy() and similar. Don't forget to pass around the length for other uses too.

Use efficient data structures efficiently

The next question is how to keep track of your list of files. The most two common ideas are to use a vector and just keep adding to it, or use a linked list. Both those solutions are wrong.

A vector while great in theory, has some performance and memory issues. When a vector can no longer contain what is being added to it, it doubles in size. The doubling in size can cause up to 99% more allocation than is actually needed during the growing process, which also comes with a lot of copying around. This may suit many workloads, but won't always suit the file list workload well.

A linked list on the other hand is one of the worst possible data structures you can use. Every entry has 100-200% extra overhead for pointers, and often means many series of allocations. Many small allocations leads to performance issues, and a lot of memory fragmentation.

The solution I would recommend is either a tweaked vector, or a combination of a vector plus linked list. Tweaking a vector starts off with reserving a set amount of space up front. Have your vector by default start with room for say 512 entries, and only then grow as needed. When you see your vector is full, instead of doubling in size, reserve another 512 entries. Smaller requests are more likely to be fulfilled for a realloc() in the same location, than a doubling in size. Very large directories beyond this point also becomes increasingly rarer at each new milestone. On top of all this, have your program remember how many files were in each of the past 10 or so directories it looked in (with filtering options of course). Then when loading a directory you recently loaded in the past, you can allocate an amount which is usually just what you need, or only needs one more chunk allocated onto it. Keep in mind that most users will keep using the same few directories over and over again with each application.

The combination of the vector and linked list would instead build a structure out of the two ideas combined. Create your array of 512 entries, along with a fill pointer and and linked list pointers. When your array is full, allocate another block of this structure as the next chain in the linked list. This ensures no need to ever reallocate, or copy data around during the growing phase. Of course keep a global pointer to the current link being filled, instead of iterating to it each time you add a new entry.

Which of these two options you use depends on how you want to sort and display your files. Each data structure has pros and cons for different use cases. Before we get into that, know how to store your file names themselves.

The above description was for the pointers to the arrays holding the file names, the file names should NOT have a separate block of allocated memory for each. That's inefficient. Instead allocate large chunks of memory, say 16KB each. Store your file names in this memory pool. Forget the silly trailing null if you can, store the length before the name itself. The two data structures explained above for containing lists of files will point into these pools. If a pool can't contain another entry you're about to add, allocate another 16KB chunk, point to it from the previous one, and start allocating in this new one. If the need for a new one was for a rare overly large file, say 230 bytes, when 200 bytes were free, you can implement an algorithm to save some overhead by seeing if the next couple of files fit into the end of any previous pools. The pools in general will probably waste less than your OSs malloc() for small file names, and you'll certainly get better performance. Deallocation will also be a quick (backwards) traversal for large chunks instead of many small ones.

Sort efficiently

The first part of sorting is comparison. strcmp()/strncmp() is not the function to use. You want something based on memcmp() as that works faster thanks to having the length of the file name already cached. Of course that's only if you want standard sorting.

If you want case insensitive sorting, other methods will have to be used. If you're only dealing with ASCII file names, and you're not worried about file names containing control characters or some symbols end up being of equal value, you can compare 4 bytes at a time or'ing each with 0x20202020 (0x2020202020202020 for 8 bytes at a time). You're probably out of luck otherwise for case insensitive, unless someone knows of any good tricks to use.

If you need "natural sorting", where numbers are compared to each other, so file1 precedes file15, and file2 follows file1 not file15, there's a few implementations floating around online and most are just copies of one another. Sadly, the most popular one I see, which is present in two operating systems, and the native implementation in a particular programming language, happens to incorrectly handle numbers past a certain magnitude (did anyone even test the implementations or just accept them at face value?), and has a worse case of O(3N). So beware of what you use or base your code off of.

I'd recommend something along these lines:
```
int strnatbase(const char *s1, const char *s2)
{
  for (; *s1; ++s1, ++s2) //No need to check s2, as we compare it to s1, and it won't equal if it's null
  {
    if (isdigit(*s1) && isdigit(*s2)) //If they're both digits, use this special handling
    {
      while (*s1 == '0') { ++s1; } while (*s2 == '0') { ++s2; } //First skip leading zeros

      register bool d1 = isdigit(*s1), d2 = isdigit(*s2); //Are we still in a run of digits for both strings?
      if (d1 != d2) { return(d1-d2); } //If for only one of them, return that as the difference

      for (; d1 && (*s1 == *s2); ++s2) { d1 = isdigit(*++s1); } //Keep going while we have matching digits

      d2 = isdigit(*s2); //If we broke the above loop because a single string ran out of digits
      if (d1 != d2) { return(d1-d2); } //Return that as the difference

      for (const char *p1 = s1, *p2 = s2; d1; ) //Otherwise, difference in the digits themselves, clarify magnitude
      {
        d1 = isdigit(*++p1); d2 = isdigit(*++p2); //First string to run out of digits first
        if (d1 != d2) { return(d1-d2); } //Will lose right here
      } //If loop breaks, both strings are out of digits, the difference found above will be handled below
    }
   if (NOT_EQUAL(*s1, *s2)) { break; } //In all other cases, fall through with difference in current position - if any
  }
  return(*s1-*s2);
}
```
Modify as necessary for unicode, and replace NOT_EQUAL() with your function (or macro) of choice for comparing two letters (accounting for case differences if you want).

As for the sort functions themselves, it will depend on which data structure you chose. You'll probably want Quicksort for the vector. Make sure your Quicksort sorts the pointers to the data and not the data itself! Same for any sorting algorithm sorting this. Swapping pointers is quick and easy. For the latter structure, you might want Merge sort, or perhaps Smoothsort. What you choose can depend on several factors.

You may or may not want to utilize threading. Depending on how you filter, the OS may be giving you mostly sorted file names which can also play a role in the algorithm you choose. In the case of the linked lists of arrays, you might want to sort each array with one algorithm, then sort the whole. If you're utilizing threading, you can begin sorting the array(s) as you're still obtaining files from the operating system, as disk reads are slower than memory reads (when the current directory contents is not (yet) cached by the OS).

Display directly

This point is rather simple. Have your file dialog display entries directly from whichever data structure you chose, without copying anything around. Know that most existing file dialog routines provided by various libraries will not be compatible with the data structures described above. So roll your own, or choose structures which can be passed directly to your library.

Another possibility is to copy entries as they fit in the dialog window. The dialog is unable to show an infinite amount of entries at once, so convert from your structure to its structure just for the current files being viewed. Update as scrolling is performed.

Search efficiently

Many file dialogs provide the option to type in some characters, and the file dialog jumps to the first file that begins with those characters. Since your file dialog is sorted, use binary search. Some people don't realize this, but binary search can find more than just an exact match, binary search can also be used to find the transition from entries "less than" to "first equal match" (in other words, binary search can also be used to find the transition between entries before the first match and the first match itself). Use this to find the first matching file in O(log(N)).

This basically wraps up this discussion on how to optimize file dialogs. I once was annoyed that loading up a directory with 20,000 files in it on a particular OS with a particular file browser took a good torturesome 20-30 seconds. Now using my own, I can load a directory with 100,000 files in 1-2 seconds on the same setup.

Thoughts, improvements, complaints, and every other kind of comment is welcome. Be sure to comment if you take of these ideas to optimize your library or application. I'd love to hear about it.

Simplifying bootstrapping for virtual constructors

2010-07-24T10:53:00.000-07:00

Last week I demonstrated a solution to the virtual constructor problem. My solution avoids many issues with the factory function solution. Yet it did require some bootstrapping to use.

The bootstrapping required a new function to be created for every single derived class that needs to be virtualized. When working with many derived classes, this becomes unacceptable. It's bad enough to solve this problem we need to generate a map, should we have to create additional functions as well? Each time a new derived class is added, should I go out of my way with two steps?

Turns out, making use of templates, we can combine the define and function generation step.


static compress *compress_zip::construct() { return new compress_zip; }
static compress *compress_gzip::construct() { return new compress_gzip; }
static compress *compress_7zip::construct() { return new compress_7zip; }

Instead of creating the above, and using it as follows:


std::map<COMPRESS_TYPES, compress *(*)()> compress_factory;
compress_factory[COMPRESS_ZIP] = compress_zip::construct;
compress_factory[COMPRESS_GZIP] = compress_gzip::construct;
compress_factory[COMPRESS_7ZIP] = compress_7zip::construct;

First create a single construct template function:


template <typename T>
compress *compress_construct()
{
  return new T;
}

This has to be done only once.

Now when adding to the map, we can do the following:


std::map<COMPRESS_TYPES, compress *(*)()> compress_factory;
compress_factory[COMPRESS_ZIP] = compress_construct<compress_zip>;
compress_factory[COMPRESS_GZIP] = compress_construct<compress_gzip>;
compress_factory[COMPRESS_7ZIP] = compress_construct<compress_7zip>;

If some new type now comes along, simply add it with a single line. A new function will be generated on use by the template, so you no longer have to. Now we have truly managed to map a type directly to an identifier.

Of course no tutorial would be complete without a self contained example:


#include <iostream>
#include <map>
#include <string>

class base
{
  std::string n;

  protected:
  base(const std::string &n) : n(n) {}

  public:
  base() : n("base") {}
  std::string name() { return(n); }
};

struct derived : public base
{
  derived() : base("derived") {}
};

template <typename T>
base *construct()
{
  return new T;
}

int main(int argc, const char *const *const argv)
{
  std::map<std::string, base *(*)()> factory;
  factory["b"] = construct<base>;
  factory["d"] = construct<derived>;

  try
  {
    //Instantiate based on run-time variables
    base *obj = factory.at(argv[1])();

    //Output
    std::cout << obj->name() << std::endl;

    //Cleanup
    delete obj;
  }
  catch (const std::exception &e) { std::cout << "Error occured: " << e.what() << std::endl; }

  return 0;
}

Output:


/tmp> g++-4.4 -Wall -o factory_test factory_test.cpp
/tmp> ./factory_test b
base
/tmp> ./factory_test d
derived
/tmp>

Now that this problem has been solved nice and neatly. What about solving it for multiple constructors? Also known as the abstract factory problem. What if each class has multiple constructors, and we want a collection of them mapped to a single identifier? Can we do it without repeating a lot of code over and over?

With some minor bootstrapping, the answer is again yes! There's multiple solutions to this problem, but the following is what I found to be the nicest at the moment.

First create a pure virtual class with a function to match each constructor you'd like to virtualize. Each should of course return a base pointer.

Imagine we had 3 constructors, one taking no parameters, one taking a C string, and another taking a C++ string, we would setup the following:


struct construct_interface
{
  virtual base *operator()() const = 0;
  virtual base *operator()(const char *) const = 0;
  virtual base *operator()(const std::string &) const = 0;
};

Once we have the interface defined, we'll create a template construct function which implements and returns that interface within a singleton similar to the above construct function:


template <typename T>
const construct_interface *construct()
{
  static struct : public construct_interface
  {
    base *operator()() const { return new T; }
    base *operator()(const char *s) const { return new T(s); }
    base *operator()(const std::string &s) const { return new T(s); }
  } local;
  return &local;
}

It'd be nice to return a reference instead of a pointer, but dealing with references in std::map is kind of icky. We can use macros to cleanup any annoying pointer dereferencing issues that could arise.

Now our construct function returns a pointer to an interface which can construct a derived type using any of its constructors. We'll use it with an std::map like so:


std::map<std::string, const construct_interface *> factory;
factory["base"] = construct<base>();
factory["derived"] = construct<derived>();

Notice the map no longer tracks function pointers, but pointers to the interface. Also, when assigning to the map, we're calling the construct function to obtain the pointer. We could modify the above example to track function pointers and leave out the (), and even make the construct function return a reference to an interface instead, but then we'd need to add an extra () when creating objects. While that too can be hidden by a macro, or just ignored, as an extra () still looks rather clean, it does add extra overhead, as it is likely you'll initialize your map just once, and use it to create many objects during the lifetime of the program.

Now to use the map to create an object, the following has to be done:


//Use first constructor, the default constructor
base *obj1 = (*(factory).at(id))();

//Use second constructor, the one taking a C string
base *obj2 = (*(factory).at(id))(s);

It works nicely, but as I explained above that's rather ugly.

This macro can help simplify things:


#define VIRTUAL_NEW(factory, id) (*(factory).at((id)))

And unlike the interface class and template construction function which needs to be created for each set of classes making use of virtual constructors, the above macro can be reused for every virtual constructor collection that makes use of the above idiom.

Using the macro, the code now looks as follows:


//Use first constructor, the default constructor
base *obj1 = VIRTUAL_NEW(factory, id)();

//Use second constructor, the one taking a C string
base *obj2 = VIRTUAL_NEW(factory, id)(s);

That's it, problem solved!

Putting it all together, here's a working example:


#include <iostream>
#include <map>
#include <string>
#include <cstdlib>

class base
{
  protected:
  int x, y;

  public:
  base() : x(1), y(2) {}
  base(const char *s) : x(std::atoi(s)), y(3) {}
  base(const std::string &s) : x(std::atoi(s.c_str())), y(4) {}

  virtual int operator()() { return x+y; }
};

class derived : public base
{
  public:
  derived() {}
  derived(const char *s) : base(s) {}
  derived(const std::string &s) : base(s) {}

  virtual int operator()() { return x*y; }
};

struct construct_interface
{
  virtual base *operator()() const = 0;
  virtual base *operator()(const char *) const = 0;
  virtual base *operator()(const std::string &) const = 0;
};

template <typename T>
const construct_interface *construct()
{
  static struct : public construct_interface
  {
    base *operator()() const { return new T; }
    base *operator()(const char *s) const { return new T(s); }
    base *operator()(const std::string &s) const { return new T(s); }
  } local;
  return &local;
}

#define VIRTUAL_NEW(factory, id) (*(factory).at((id)))

int main(int argc, const char *const *const argv)
{
  std::map<std::string, const construct_interface *> factory;
  factory["b"] = construct<base>();
  factory["d"] = construct<derived>();

  if (argc == 3)
  {
    try
    {
      //Instantiate based on run-time variables
      base *obj1 = VIRTUAL_NEW(factory, argv[1])();
      base *obj2 = VIRTUAL_NEW(factory, argv[1])(argv[2]);
      base *obj3 = VIRTUAL_NEW(factory, argv[1])(std::string(argv[2]));

      //Output
      std::cout << (*obj1)() << '\n'
                << (*obj2)() << '\n'
                << (*obj3)() << '\n'
                << std::flush;

      //Cleanup
      delete obj1;
      delete obj2;
      delete obj3;
    }
    catch (const std::exception &e) { std::cout << "Error occured: " << e.what() << std::endl; }
  }

  return 0;
}

Output:


/tmp> g++-4.4 -Wall -o abstract_factory_test abstract_factory_test.cpp
/tmp> ./abstract_factory_test b 2
3
5
6
/tmp> ./abstract_factory_test b 3
3
6
7
/tmp> ./abstract_factory_test d 2
2
6
8
/tmp> ./abstract_factory_test d 3
2
9
12
/tmp>

Hopefully you should now be able to take this example and plug it in just about anywhere. Easy to add new types. No need to modify existing classes. Fully dynamic. Easy to use!

This method really shines if you dynamically load derived classes while your program is running. Just make sure your DLL uses the the template function internally, so an instance of the function for the new type is created, and dynamically add an id to the map, and presto you're done.

Now go out there and leverage the power of C++!

Time to shutdown the factory for code violations

2010-07-20T06:55:00.000-07:00

There's a common problem in software development regarding how to create an object's type dynamically in C++ and similar languages. If I have a collection of classes (they all inherit from the same base), I can use a base pointer to any instance, and perform operations as needed. The issue is generating that pointer in the first place.

Say I have an image class, with subclasses of image_png, image_jpeg, image_gif, and so on. I can use an image pointer along with its virtual functions to do an operation like image_pointer->resize(new_dimensions), and have it do whatever needs to be done for the image type in question to resize it and write the data properly.

This idea applies to all kinds of projects over and over again. Another example could be a compression class. Where I have the class compress, along with subclasses compress_zip, compress_gzip, compress_7zip, and so on. I can do compress_pointer->uncompress(in_file, out_file), and have that work appropriately with virtual functions.

However my image pointer and my compress pointer need to be pointing at the right kind of object for this to work in the first place. My image is sent over the network, I have information at runtime of image/jpeg and the binary data, and I need to load that into the correct subclass image_jpeg. My compressed file is on the hard drive, I read its type via its extension or its header, again I need my pointer to point at the appropriate subtype. I don't have this information at compile time, so how do I initialize my pointer?

In this case, the idea of virtual constructors, or factories come into play. The simplest factory would be in the form of an if/else if structure, or a switch.


image *image_factory(const char *mime_type, const uint8_t *binary_data, size_t size)
{
  image *image_pointer;
  if (!strcmp(mime_type, "image/jpeg")) { image_pointer = new image_jpeg(binary_data, size); }
  else if (!strcmp(mime_type, "image/png")) { image_pointer = new image_png(binary_data, size); }
  else if (!strcmp(mime_type, "image/gif")) { image_pointer = new image_gif(binary_data, size); }
  else { throw "Unsupported image type"; }
  return image_pointer;
}


compress *compress_factory(COMPRESS_TYPES requested_save_format)
{
  compress *compress_pointer;
  switch (requested_save_format)
  {
    case COMPRESS_ZIP: compress_pointer = new compress_zip; break;
    case COMPRESS_GZIP: compress_pointer = new compress_gzip; break;
    case COMPRESS_7ZIP: compress_pointer = new compress_7zip; break;
    default: throw std::runtime_error("Unknown enum value");
  }
  return compress_pointer;
}

Now the above functions allow us to get the base pointer initialized appropriately, but they have some drawbacks.

A single function needs to know about every type.

If which types are supported changes during runtime, perhaps based on which DLLs are found, the factory function becomes more complex, and has to be specifically tailored for each application.

If there are multiple constructors, and in some cases one is needed, and in some cases another, suddenly we need to recreate the same logic in multiple factory functions, one factory function per constructor.

This style of factory function has to be recreated for every single collection of classes present, the logic behind a factory function is not abstracted away.

Based on these drawbacks, obviously such a method is the incorrect solution, even though it is the most popular method used.

In the case where we have variables mapping to other variables, such as 1 = "Apple", 2 = "Orange", 3 = "Tomato", the obvious solution would be to setup an array or use a map. If the mapping needed is between an integer and a variable, going from integer -> variable is simply a matter of indexing into an array. When dealing with non integer types, the standard std::map fits the bill rather nicely, as it can allow any type to become an index.

So the question becomes, can we map a variable to a type itself? With a bit of bootstrapping, the answer is actually yes! What we need are function pointers to replace code logic.

We can't create a function pointer directly to a constructor, so we'll need a bit of bootstrapping. We can create function pointers to global functions, or static member functions.

In our compression case we can do the following:


static compress *compress_zip::construct() { return new compress_zip; }
static compress *compress_gzip::construct() { return new compress_gzip; }
static compress *compress_7zip::construct() { return new compress_7zip; }

We'll place a static construct() within each of our classes we'd like to be able to instantiate dynamically, and then we can use them in a map like so:


std::map<COMPRESS_TYPES, compress *(*)()> compress_factory;
compress_factory[COMPRESS_ZIP] = compress_zip::construct;
compress_factory[COMPRESS_GZIP] = compress_gzip::construct;
compress_factory[COMPRESS_7ZIP] = compress_7zip::construct;

Once we have a map in place that can be constructed at runtime, we no longer have most of our above issues. No canned function needs to be created which knows about all the supported types in advance, which needs modification for each new type. Values are only added to the map that the required DLLs were found for it, or other runtime constraints. The entire idea is also abstracted away, and we don't need to constantly recreate new factory functions for each family of objects. We simply just initialize a factory object and make use of it.

Now how exactly do we use our map? The idea which is rather popular and expounded in book after book, is to create a factory template class something similar to the following:


template <typename identifier, typename product, typename function>
struct factory
{
  void set_mapping(const identifier &id, function f) { mapping[id] = f; }
  product *construct(const identifier &id)
  {
    function f = mapping.at(id);
    return f();
  }

  private:
  std::map<identifier, function> mapping;
};

Now that we have all that encapsulated, we can do the following:


factory<COMPRESS_TYPES, compress, compress *(*)()> myfactory;
myfactory.set_mapping(COMPRESS_ZIP, compress_zip::construct);
...
compress *compress_pointer = myfactory.construct(requested_save_format);

However, such a method has a serious drawback. What if my constructor needs parameters? As it does in the image example above? Do I end up creating a new factory encapsulation class each time? One library out there solves this problem with ~800 lines of code. Basically the construct function in the factory class is overloaded a bunch of times with template parameters over and over again, for some conceivable amount of parameters a function might take.


AbstractProduct *CreateObject(const IdentifierType &id,
                              Parm1 p1, Parm2 p2, Parm3 p3, Parm4 p4, Parm5 p5, Parm6 p6, Parm7 p7, Parm8 p8)
{
  typename IdToProductMap::iterator i = associations_.find(id);
  if (i != associations_.end()) { return (i->second)(p1, p2, p3, p4, p5, p6, p7, p8); }
  return this->OnUnknownType(id);
}

The above snippet is repeated 16 times in that library with 0-15 parameters. First of all, such code commits the unforgivable sin of code repetition, and is limited to 15 parameters. What if I need more? Sin more?

The entire idea of a factory which produces an object within itself needs to be shutdown. By trying to be overly clever and encapsulate more than needed, object factories turn into nothing but bloat and horrible code.

Simplicity is king. Therefore, the map should NOT be encapsulated, nor should an object be directly produced. Our so called factory should only produce the appropriate mold needed to form our object.

In the case of images:


static image *image_jpeg::construct(const uint8_t *binary_data, size_t size)
{
  return new image_jpeg(binary_data, size);
}

static image *image_png::construct(const uint8_t *binary_data, size_t size)
{
  return new image_png(binary_data, size);
}

static image *image_gif::construct(const uint8_t *binary_data, size_t size)
{
  return new image_gif(binary_data, size);
}

std::map<std::string, image *(*)(const uint8_t *, size_t)> image_factory;
image_factory["image/jpeg"] = image_jpeg::construct;
image_factory["image/png"] = image_png::construct;
image_factory["image/gif"] = image_gif::construct;

Now to create an image, simply do the following when you want to create an image based on run time variables:


image *image_pointer = image_factory.at(mime_type)(binary_data, size);

Notice that code would take the place of:


image *image_pointer = new image_png(binary_data, size);

Now the creation of a particular object at runtime looks pretty much like creating a specific object, and can feel natural. Just like new which throws an error when it fails (which can happen here too), std::map::at() throws an error when the requested index is not found, so you can reuse the same type of exception handling you're already using when creating objects in general.

If you'd like a complete example which you can play with yourself, try this:


#include <iostream>
#include <string>
#include <map>
#include <stdexcept>
#include <cstdlib>

class Base
{
  int x, y;
  public:
  Base(int x, int y) : x(x), y(y) {}
  virtual ~Base() {};
  virtual int mult() { return x*y; }
  virtual int add() { return x+y; }

  static Base *create(int x, int y) { return new Base(x, y); }
};

class Derived : public Base
{
  int z;
  public:
  Derived(int x, int y) : Base(x, y), z(1) {}
  void setZ(int z) { this->z = z; }
  virtual int mult() { return Base::mult()*z; }
  virtual int add() { return Base::add()+z; }

  static Base *create(int x, int y) { return new Derived(x, y); }
};

int main(int argc, const char *const *const argv)
{
  //Get factory ready
  std::map<std::string, Base *(*)(int, int)> factory;

  //Add some rules
  factory["base"] = Base::create;
  factory["derived"] = Derived::create;

  try
  {
    //Instantiate based on run-time variables
    Base *obj = factory.at(argv[1])(4, 5); //Note: instead of new Base(4, 5) or new Derived(4, 5)

    //Set Z if derived and requested
    if (argc > 2)
    {
      if (Derived *d = dynamic_cast<Derived *>(obj)) { d->setZ(std::atoi(argv[2])); }
    }

    //Output
    std::cout << obj->mult() << ' ' << obj->add() << std::endl;

    //Cleanup
    delete obj;
  }
  catch (const std::exception &e) { std::cout << "Error occured: " << e.what() << std::endl; }

  return 0;
}

Here's what the output looks like:


/tmp> g++-4.4 -Wall -o factory_test factory_test.cpp
/tmp> ./factory_test
Error occured: basic_string::_S_construct NULL not valid
/tmp> ./factory_test base
20 9
/tmp> ./factory_test derived
20 10
/tmp> ./factory_test derived 6
120 15
/tmp> ./factory_test cows
Error occured: map::at
/tmp>

Basically the only issue we're left with is that for each class you want to be able to use a factory for, you have to create a static member function for each constructor you want to use with a particular factory. I don't think there is away around that. It's a minor inconvenience, but in the end offers a lot of power in a clean fashion.

This idea of combining a map with a function pointer can be expanded to other areas as well. You can use this method for calling functions in general based on any runtime input. If your class has many different member functions, each with the same parameters, but for different operations, consider creating a map to member function pointers, and use the input as an index into a map to call the appropriate member function.

Suggestions, improvements, and comments welcome.

Undocumented APIs

2010-06-03T14:19:00.000-07:00

This topic has been kicked around all over for at least a decade. It's kind of hard to read a computer programming magazine, third party documentation, technology article site, third party developer mailing list or the like without running into it.

Inevitably someone always mentions how some Operating System has undocumented APIs, and the creators of the OS are using those undocumented APIs, but telling third party developers not to use them. There will always be the rant about unfair competition, hypocrisy, and other evils.

Large targets are Microsoft and Apple, for creating undocumented APIs that are used by Internet Explorer, Microsoft Office, Safari, iPhone development, and other in-house applications. To the detriment of Mozilla, OpenOffice.org, third parties, and hobbyist developer teams.

If you wrote one of those articles/rants/complaints, or agreed with them, I'm asking you to turn in your Geek Membership card now. You're too stupid, too idiotic, too dumb, too nearsighted, and too vilifying (add other derogatory adjectives you can think of) to be part of our club. You have no business writing code or even discussing programming.

Operating Systems and other applications that communicate via APIs provide public interfaces that are supposed to be stable. If you find a function in official public documentation, that generally signifies it is safe to use the function in question, and the company will support it for the foreseeable future versions. If a function is undocumented, it's because the company doesn't think they will be supporting the function long term.

Now new versions which provide even the exact same API inevitably break things. It is so much worse for APIs which you're not supposed to be using in the first place. Yet people who complain about undocumented APIs, also complain when the new version removes a function they were using. They blame the company for purposely removing features they knew competition or hobbyists were using. That's where the real hypocrisy is.

As much as you hate a new version breaking your existing software, so does Microsoft, Apple, and others. The popularity of their products is tied to what third party applications exist. Having popular third party applications break on new versions is a bad thing. That's why they don't document APIs they plan on changing.

Now why do they use them then? Simple, you can write better software when you intimately understand the platform you're developing for, and write the most direct code possible. When issues occur because of their use, it's easy for the in-house teams to test their own software for compatibility with upcoming versions and fix them. If Microsoft sees a new version of Windows break Internet Explorer, they can easily patch the Internet Explorer provided with the upcoming version, or provide a new version altogether. But don't expect them to go patching third party applications, especially ones which they don't have the source to. They may have done so in the past, and introduced compatibility hacks, but this really isn't their problem, and you should be grateful when they go out of their way to do so.

So quit your complaining about undocumented APIs, or please go around introducing yourself as "The Dumb One".

Does anyone understand types and magnitudes?

2010-03-27T15:21:00.000-07:00

Regularly I have to work with many popular libraries out there, as well as many libraries written by coworkers and similar.

One thing which I see constantly misused over and over again is the type system used in C and C++.

I wonder if most people understand it, have bothered to contemplate it, or simply don't care if their library is misprogrammed trash.

First of all, C/C++ for integers supports both signed and unsigned types. Many programmers seem to ignore the unsigned types altogether. Maybe some education is in order.

Each base type in C consists of one or more bytes. Each byte on modern main stream systems are 8 bits to a byte. Meaning a single byte can store 2⁸ values, or in other words 256 possibilities. Two bytes can store 2¹⁶ values, or in other words 65,536 possibilities.

A type designed for integers (whole numbers) which is unsigned will operate with the meaning of its values as ranging from 0 till amount of possibilities - 1. In the case of a one byte type: 0 to 255, for a 2 byte type: 0 to 65,535.

When a value is signed (the usual default if no signed or unsigned description is applied), a single bit is used to describe whether the rest of the bits represent a positive or negative value. This effectively cuts the amount of positive values that can be represented in half. In the case of a single byte, 2⁷ values will be negative, -128 to -1, 2⁷-1 values will be distinctly positive, 1 to 127, and one value will be 0 (for a total of 256 possibilities). This same math extends to as many bytes being used in a given type.

When dealing with something which requires working with both positive and negative values such as debt (monetary balance), direction, difference, relative position, and things of a similar nature, signed values is quite natural and should of course be used.

But if you're working with something which has no meaning for negative values such as "Number of students in this class", "How old are you", "Amount of chickens in the coop", "Amount of rows in database table", or "Amount of elements in this array", or amounts of any nature really, using a signed type is one of the worst things you could possibly do. You are reserving half of your possible values for a situation which will never occur (barring mistakes in programming).

Let's take a look at some real world examples. The most popular type used for at least the past decade would have to be the 32 bit integer. 2³² gives us 4,294,967,296 different value possibilities. If that was a storage size, it would be 4GB. Effectively a 32 bit unsigned integer can store the values 0 to 4,294,967,295, or one byte less than 4GB. If it was signed, it would be able to store the values -2,147,483,648 to 2,147,483,6487, topping out at one less than 2GB.

If you have an Operating System or File System which limits you to 2GB as a max size for files, or your Digital Camera only lets you use up to 2GB flash cards, it's because the idiots that programmed it used signed values. They did this because either they were expecting files and flash cards of negative size, or because they were a bunch of idiots. Which of those two possibilities actually happened should be obvious.

The same goes for any programming library you see with a limit of 2GB. As soon as you hear anyone mention a limitation of 2GB, what should immediately register in your head is that idiots worked on this application/library/standard/device.

Now sometimes programmers try to justify their ignorance or their idiocy with remarks such as using negative values to indicate error conditions. Meaning, they write functions which return a positive value in case of success, and -1 in case of error. This is a very bad practice for two reasons. First of all, one shouldn't use a single variable to indicate two different things. It's okay to use a single variable where each bit (or sets of bits) indicate a flag for a set of flags. But it's very wrong to have a single value indicate success/failure and amount, or day of week and favorite color, or any two completely unrelated things like that. Doing so only leads to sloppy code, and should always be avoided. Second of all, you're cutting your amount of usable possibilities in half, and reserving a ton of values just for a single possibility. You can't be more wasteful than that.

If you need a way for your function to return success/failure and amount, there are cleaner and more effective ways to do so. Many times an amount of 0 is invalid. If a function is supposed to return the amount of something, 0 isn't really an amount. If I asked how many students are in my class, and I get 0, that in itself should be indicative of an error. If I asked how many rows did my SQL statement just change, and I get 0, that should be indicative of an error, or at the very least, there were no SQL rows to change. If I really need to know if the 0 means a real error, or there was no data to work with, a separate function can tell me if the last call was a success or failure. In C and in POSIX, it is common to use the global variable errno to indicate errors. If you're making your own library, you can make a function to tell you why the last value was 0. There was no data, there was an error accessing the data, and so on.

Another method would be to pass one parameter by pointer/reference to store the amount or success state, and have the other returned from the function. Another technique would be to return an enum which tells you which error condition happened or everything is okay, and use a different function to retrieve the value of that operation upon success. Lastly, C++ programmers can use std::pair<> for all their multiple return needs, or simply return the amount normally, and throw an exception on any kind of error.

Now that hopefully all my loyal readers are now more educated about the sign of their types, and various function return techniques that better libraries use, let's talk a bit about magnitude.

I see again and again libraries that don't have a clue about magnitude. The various C/C++ standards state the following about the normal built in types.

1) The amount of bytes used for the following types should be in this proportion: short <= int <= long <= long long.
2) short should be at least 2 bytes.
3) long should be at least 4 bytes.
4) long long should be at least 8 bytes;.

Which means all these scenarios are perfectly legal:
sizeof(short) == 2
sizeof(int) == 2
sizeof(long) == 4
sizeof(long long) == 8

sizeof(short) == 2
sizeof(int) == 4
sizeof(long) == 4
sizeof(long long) == 8

sizeof(short) == 2
sizeof(int) == 4
sizeof(long) == 8
sizeof(long long) == 8

sizeof(short) == 2
sizeof(int) == 4
sizeof(long) == 8
sizeof(long long) == 16

sizeof(short) == 4
sizeof(int) == 4
sizeof(long) == 8
sizeof(long long) == 16

sizeof(short) == 4
sizeof(int) == 8
sizeof(long) == 16
sizeof(long long) == 32

And so on.

In order to get types of a particular size, C99 added the header <stdint.h> and C++-201x added <cstdint>, with types such as int8_t, uint8_t, int16_t, uint16_t, int32_t, uint32_t, int64_t, uint64_t, and several others. Each of these types are the size in bits that their name indicates, with those without a u at the beginning being signed, and those with being unsigned. Using these types you can get the exact size you need.

But remember to use things appropriately. I see several popular SQL engines for example that support as many rows in a table as a uint64_t is able to contain, but if you ask them how many rows were altered by the last query, they'll report that information in a plain and simple int! You by now should realize there are two problems with such a course of action.

Now lastly, if you're writing some kind of function which takes an array, it is normal convention to pass a pointer to the array, as well as a size variable to specify how many elements or bytes are within the array.

The standard C library uses a type called size_t to deal with such values. A size_t can contain the highest amount of bytes the program is able to address, and is of course unsigned.

If you need to pass an array, your prototype should always be along the lines of:


void func(void *p, size_t size);
void func(uint8_t *p, size_t size);

If you need to return a size, for something which is addressable memory, again always use a size_t. Functions like strlen() and sizeof() return a size_t, and functions like memcpy(), memset(), or malloc() take a size_t as one of their arguments.

Let me show you a quick program to illustrate a point.


#include <cstdio.h>

#define O(x) printf(#x": %zu\n", sizeof(x))
int main()
{
  O(signed char);
  O(signed short);
  O(signed int);
  O(signed long);
  O(signed long long);
  O(signed);
  O(unsigned char);
  O(unsigned short);
  O(unsigned int);
  O(unsigned long);
  O(unsigned long long);
  O(unsigned);
  O(size_t);
  O(void *);
  O(float);
  O(double);
  O(long double);
  return(0);
}

On a 32 bit system of mine, the output is as follows:


signed char: 1
signed short: 2
signed int: 4
signed long: 4
signed long long: 8
signed: 4
unsigned char: 1
unsigned short: 2
unsigned int: 4
unsigned long: 4
unsigned long long: 8
unsigned: 4
size_t: 4
void *: 4
float: 4
double: 8
long double: 12

On a 64 bit system of mine, the output is as follows:


signed char: 1
signed short: 2
signed int: 4
signed long: 8
signed long long: 8
signed: 4
unsigned char: 1
unsigned short: 2
unsigned int: 4
unsigned long: 8
unsigned long long: 8
unsigned: 4
size_t: 8
void *: 8
float: 4
double: 8
long double: 16

Now notice for 32 bit, the void * type is 4 bytes, and on 64 bit, it is 8 bytes. This means that a void * can address any position in memory that the system is able to. In order to specify the amount, you'll notice in each case the sizeof(size_t) matches the sizeof(void *). If I were to get a 128 bit system which had a void * of 16 bytes, the size_t would also be at least 16 bytes.

There are other types which also matched the size of the void * each time around, but if you look at my earlier explanation of the relationship of the various C types, you'll notice those other types are too variable to know if they'll be good for an amount of every system you try to use your application or library on, so always stick with the size_t.

All too often I see programmers use an int for such an amount which is clearly wrong, or an unsigned int, which is better, but also wrong, especially on my 64 bit system. Some programmers I also see use the type of just unsigned by itself. I don't know who thought that up, but it's identical to an unsigned int, which is also clearly wrong. I included unsigned and signed specifically in my test above because some people are under the mistaken notion that those types become as large as possible. Every time I see code which contains one of them, I want to vomit.

If you ever have any doubt as to what size a type may be on your system, or get into an argument with someone, test things yourself with a sizeof() call, it's not hard to do, or point them to this article.

Now go out there and write some good libraries. I have too much vomit and bile on the floor here from all the horrible code I have to work with or review.

C++-201x Variadic Templates

2010-03-11T17:56:00.000-08:00

C++-201x (or C++-0x as near sighted individuals like to call it) introduced a new feature called variadic templates, which allows a template class or function to recieve multiple parameters to it of various types as you would normally achieve with "...".

You could continue to use stdarg if you wish, but a limitation of it is that you have no way of knowing what type each parameter is to use with va_arg(), unless you just hard code it to only work with a specific type, or pass a type list how the printf() family of functions do it, or something similar.

I always wanted a way to do func(integer, string, float, whatever), and interchange that with func(float, whatever, char), and now you can.

If you try to research this topic online, basically everyone is just writing and talking about how to implement a tuple class, or how to make a type safe printf. Lets try something a little more interesting and perhaps instructive, yet simple.


#include <iostream>
using namespace std;

//Output function to output any type without type specifiers like printf() family
template <typename T, typename ...P>
void output(T t, P ...p)
{
  cout << t << ' ';
  if (sizeof...(p)) { output(p...); }
  else { cout << '\n'; }
}

//Since variadic templates are recursive, must have a base case
void output() { cout << '\n'; }


//Compute sum of all parameters
template <typename T, typename ...P>
T sum(T t, P ...p)
{
  if (sizeof...(p))
  {
    t += sum(p...);
  }
  return(t);
}

//Since variadic templates are recursive, must have a base case
template <typename T>
T sum(T t) { return(t); }

//Test it
int main()
{
  output();
  output('5');
  output('5', 2);
  output('5', 2, "cows");
  output('5', 2, "cows", -1);
  output('5', 2, "cows", -1, 0.5f);
  output('5', 2, "cows", -1, 0.5f, 16.3);

  cout << endl;

  cout << sum(1) << '\n'
       << sum(1, 2) << '\n'
       << sum(1, 2, 3) << '\n'
       << sum(1, 2, 3, 4) << '\n'
       << sum(1, 2, 3, 4, 5) << '\n';

  cout << endl;

  cout << sum(0.1) << '\n'
       << sum(0.1, 0.2) << '\n'
       << sum(0.1, 0.2, 0.3) << '\n';

  cout << endl;

  return(0);
}

Here's how to compile and what the output looks like:


/tmp> g++-4.4 -Wall -o test test.cpp -std=gnu++0x
/tmp> ./test

5
5 2
5 2 cows
5 2 cows -1
5 2 cows -1 0.5
5 2 cows -1 0.5 16.3

1
3
6
10
15

0.1
0.3
0.6

/tmp>

As can be seen I achieved my desired goals of being able to pass various types, not know the types to be passed in advance, and not need a type list passed anywhere. All the other examples I've seen seem to be forgetting these important points.

As for how this works "typename ...P" defines a template type of P which will be many parameters packed into a single variable. "P ...p" receives all these parameters in a variable named "p".

However the only things I can really do is see how many parameters are in "p" using "sizeof...(p)", or split "p" up into all its parameters, to then pass to a function by using "p...". It would be nice to be able to simply iterate through the values of "p", but that's not possible at the moment.

Using standard recursion techniques, you can pass the split up parameters from "p" to a function which has enough templated parameters as "p" is currently holding, or a lesser amount, and the last parameter can be a variadic parameter to catch all the others which don't fit into the first few. Then using those first parameters, you can access the values you need, and so on ad infinitum.

Read up on recursion if you're confused.

Now if you're still wondering what this may be useful for, just consider functions which handle data serialization or something similar.

One thing to note, at least with GCC at the moment, you always need to have a separate function as a base case, even if it's never used.

Take "output('5', 2, "cows", -1, 0.5f, 16.3);", on the last leg of iteration, when the double is passed to the first parameter to be received by "t", and "p" is empty, "if (sizeof...(p)) { output(p...); }" which is the line responsible for the recursion seeing an empty "p" won't ask for "output()", but it seems the compiler still wants it to exist:


test.cpp: In function ‘void output(T, P ...) [with T = double, P = ]’:
test.cpp:8:   instantiated from ‘void output(T, P ...) [with T = float, P = double]’
test.cpp:8:   instantiated from ‘void output(T, P ...) [with T = int, P = float, double]’
test.cpp:8:   instantiated from ‘void output(T, P ...) [with T = const char*, P = int, float, double]’
test.cpp:8:   instantiated from ‘void output(T, P ...) [with T = int, P = const char*, int, float, double]’
test.cpp:8:   instantiated from ‘void output(T, P ...) [with T = char, P = int, const char*, int, float, double]’
test.cpp:33:   instantiated from here
test.cpp:8: error: no matching function for call to ‘output()’

I'm not sure though if this is required by the standard, or a bug in GCC.

As for C++-201x support in general, GCC seems to be the furthest ahead, even surpassing Comeau C++.

See a comparison of the various compilers' support of C++-201x.

Happy "Holidays" From Google

2009-12-21T04:31:00.000-08:00

If you use GMail, you probably got this message recently:

Happy Holidays from Google

Hello,

As we near the end of the year, we wanted to take a moment to thank you for the time, energy, commitment, and trust you've shared with us in 2009.

With sharing in mind, this year we've decided to do something a little different. We hope you'll find it fits the spirit of the holiday season.

We're looking forward to working with you to build lasting success in 2010.

Happy Holidays,
Your Google Team

While on the surface it seems like a nice gesture, wouldn't it be nice if these big companies actually put some thought into what they wrote?

The use of terms or "codewords" like "Happy Holidays" or "holiday season" is meant to be all inclusive of the various winter holidays celebrated by different religions or cultural groups, without singling out any one of them in particular. It's primarily meant to include minorities that celebrate Kwanzaa and Hanukkah.

But this letter was sent on December 21, after Hanukkah was already completed two days earlier. If they really wanted to be all inclusive, perhaps they should have sent it the first week in December, instead of waiting till soon after Hanukkah was over, portraying Antisemitism.

All these "codewords" used are actually born out of "Political Correctness", a practice designed to discriminate against your average white male, while not actually caring about the minorities you're trying to protect. Isn't it nice to see another big company show that they aim for Political Correctness, yet show they couldn't care less about those minorities?

On a similar note, a friend of mine tells me that he recently applied for a job at Google, and they sent him a form asking him to specify his Race on it. Wonder why?

Cryptic Linux Distro Updates

2009-12-05T12:17:00.001-08:00

We're almost in 2010, I thought by now to anyone who basically knows how to use a computer, general upgrade prompts in Linux Distros would make sense, and won't seem cryptic like "Abort, Retry, Ignore, Fail?".

Then you get something like this:

This is a new upgrade message in Debian/Ubuntu.
Here's the full text:

Various snmp software needs extracted MIBs from RFCs and IANA - which cannot be shipped - to be working as expected. These MIBs can be automatically fetched and extracted as part of installing this package.

This will take several minutes to complete, even with a fast internet connection.

Download and extract MIBs from RFCs and IANA?

Are all these acronyms really necessary? Should a user even be given such cryptic information, and instead see a prompt along the lines of: "This package requires additional components to fully function, download them?".

Even a power user who is familiar with a term like RFC, does this message even make any sense?

Seems like Linux Distros still has a long way to go.

Malicious hackers are not out there

2009-11-24T09:24:00.000-08:00

Security as it is today is an illusion. What? How could I say that, I'm not serious, am I?

Most people today do not understand what security is or is not about. As evidenced by so many works of modern fiction centering around a plot where the terrorists/foreign government/aliens "bug" a server, a cable, or a satellite. Today's technology is supposed to prevent attacks involving any layer in the middle being bugged. Besides not understanding what modern security is capable of, many who are working with it do not understand what it is not capable of.

A quick scan of source code in many projects will turn up code which fails even text book level security principals. I even see some major projects have code commented that it needs a more secure hash or nonce generator or something similar, which again could be found in modern textbooks.

It is shocking the sheer number of online services or applications one can install (forums, webmail, blog, wiki, etc...) that have insecure login. Nearly all of them take user login credentials in plain text, allowing anyone between the user's computer and the website's application to steal the passwords.

It is sad that nearly all sites use a custom login scheme that can be buggy and/or receive login credentials unencrypted, considering that HTTP - the protocol level of communication supports secure logins. HTTP login is rarely used though because it lacks a simple way to log out (why?), and can not be made to look pretty without using AJAX, which is why the vast majority of site creators avoid it.

The HTTP specifications actually describes two methods of login for "HTTP 401", one called "Basic Authentication", and another called "Digest Authentication". The former transmits login credentials in plain text, and the latter using an encryption of sorts. Most sites that avoid the worry of properly creating a custom login scheme and resort to HTTP 401 generally use Basic Authentication. Historically the reason is that most developers of HTTP servers and clients have been too stupid to figure out how to do it properly. Which is surprising considering it is such a simple scheme. IIS and IE didn't have it done properly till relatively recently. Apache historically has had issues with it. Qt's network classes handled it improperly until recently. I'm also told Google Chrome currently has some issues with it.

However, even if one used Digest as the login mechanism on their website, it can easily be subject to a
Man in the middle attack, because the HTTP spec allows for there to be the possibility of sending passwords in an unencrypted fashion.

The following diagram illustrates it:

Since requests for authentication are requested from the server and not the client, the machine in the middle can change the request to be the insecure variant.

So of course the next level up is HTTPS, which does HTTP over SSL/TLS, which is supposed to provide end to end security, preventing man in the middle attacks. This level of security makes all those fiction stories fail in their plot. It also is supposed to keep us safe, and is used by websites for processing credit card information and other sensitive material.

However, most users just type "something.muffin" into their browser, instead of prefixing it with http:// or https://, which will default to http://. Which again means the server has to initiate the secure connection. Since again this is also over a system which has both secure and insecure methods of communication, the same type of man in the middle attack as above can be performed.

The following diagram illustrates it:

Webservers are generally the one that initiates the redirection to an HTTPS page, which can be modified by the server in the middle. Any URL within a page which begins with https:// can be rewritten. For example, https://something.muffin can be changed to http://something.muffin:443 by an attacker in the middle, and then proceed with the attack as described above.

Of course users should be looking for padlocks and green labels and similar in their browser, but how many do so? Since most sites people visit aren't running in secure environments, do you expect them to really notice when some page which is supposed to be secure isn't? Do you expect users to be savvy about security when most developers aren't?

The amount of data which should be transferred securely but isn't is mind boggling. I see websites create a security token over HTTPS, but then pass that token around over HTTP, allowing anyone in the middle to steal it. I see people e-mail each other passwords to accounts on machines they manage all the time. I see database administrators login to phpMyAdmin running on servers with their root passwords sent in plain text. People working on projects together frequently send each other login credentials over forums or IRC in plain text.

Anyone managing a hub somewhere on the vast internet should be able to log tons and tons of passwords. Once a password is gotten to someone's e-mail or forum account, then that can be scanned for even more passwords. Also, I see many users save root/admin passwords in plain text files on web servers, if one managed to get into their account by nabbing their password to it, they quite often will also be able to gain root by a simple scan of the user's files. Even if not, once access is gained to a machine, privilege escalation is usually the norm as opposed to the exception, because server administrators quite often do not keep up with security updates, or are afraid to alter a server that they finally got working.

Careful pondering would show our entire infrastructure for communication is really a house of cards. It wouldn't be that hard for a small team with a bit of capital to setup free proxy servers around the world, offer free wi-fi at a bunch of hotspots, or start a small ISP. So the question we have to ask ourselves, is why are we still standing with everything in the shaky state it's in? I think the answer is simple, the malicious hackers really aren't out there. Sure there's hackers out there, and some of them do wreak a bit of havoc. But it seems no one is really interested in making trouble on a large scale.

Mostly the hackers you hear about are people in a competition, or research, or those "security hackers", which have gone legit and want to help you secure your business. It's funny the amount of times I heard a story about how some bigwig at a company goes to some sort of computer expo, and runs across a table or booth of security "gurus". The bigwig asks how the security gurus can help his business, with the response asking if the bigwig owns a website. Once the bigwig mentions the name of his site, one guru pulls out his laptop and shows the bigwig the site with it defaced in some way. The bigwig panics and immediately hires them to do a whole load of nothing. Little does he realize he was just man-in-the-middle'd.

We got excellent documentation!

2009-11-10T15:35:00.001-08:00

Ever try to work with a library you've never dealt with before? How do you approach the task? Do you try to find another program which uses the library and cannibalize it? Get someone who already knows how to use it to teach you? Find a good example? Or just trudge your way through and get something that barely works?

I personally would like to have some good documentation which tells me exactly what I need to do to get the job done. Something which I can rely on to tell me everything I need to know, and to avoid any particular pitfalls.

Except most of the time documentation is written by people who would be better off in some other profession. Like terrorist interrogators. Or perhaps the Spanish Inquisition.

Although when you talk to people about the documentation for their library, they act like the documentation is two stone tablets brought down from heaven with sacred commandments written on them. Perhaps it is. But in the same fashion, the documentation is just as mysterious to anyone who hasn't spent years studying the library to decipher its true meaning.

For many libraries, I have spent hours pouring over their documentation, to come up with like 5-10 lines of code to do what I needed to do. 10 hours for 10 lines of code? A bit much I think. Why can't people make documentation for those not familiar with the library, so they can get all the basic tasks done, and provide good reference for anything more advanced? Sometimes the documentation is so completely unhelpful, that I have to resort to the source code, or scour the internet for something to help me. This is completely unacceptable.

Lets look at some of the various types of offenders.

Doxygen equals documentation.

This is the kind of documentation written by those obnoxious programmers who don't want to write any documentation at all. They run a script on their source code which creates a set of HTML pages with a list of all the files in the library, a list of functions and classes, and all nicely interlinked. It also pulls out the comments about each function and clearly displays it. Sure it makes it easy to jump back and forth in a browser between various internals of the source. But it really gives no insight on how to use the library. If the library is written really cleanly, and commented well, perhaps this helps, but usually those creating the library didn't put any more effort into it than they put into creating their documentation.

Really, honest, there's documentation!

Then there are those that try to convince you they have documentation. You have a set of text files, or an HTML file, or a PDF or whatever which tells you how amazing the library is, and tells you all the wonderful things the library is capable of. They'll even give you notable examples of programs using their library. You'll have a great comparison chart of why this library is better than its competitors. You'll even get some design documentation, rational, and tips on how you can expand the library further. Good luck finding a single sentence which actually tells you how to use it.

We got you the bare essentials right over here, or was it over there?

Then you have the documentation which can never give you any complete idea. Sure, just use this function and pass it these six arrays all filled out. Don't worry about what to put in them, those arrays are explained on another page. Oh yeah this array can be used for a trillion different things, depending on which function you use it with, so we'll just enumerate what you may want to use it for. You may get more information looking at these data types though. Before you know it, you're looking at 20 different pages trying to figure out how to bring together the information to use a single function.

I see your warrant, and I raise you a lawyer!

This kind of documentation seems to be written by those that don't actually want you to use their library and are all evasive about it. Every time you think the documentation is going to comply and actually tell you something useful, you're faced with something that isn't what you wanted. You'll get a bunch of small 4 line examples, each that do something, but no explanation as to what they're doing exactly. You'll even be told here and there some cryptic details about what a function supposedly does. Good luck figuring how to use anything.

I see your lawyer, and I'll bury you with an army of lawyers!

This is one of the worst offenders that big companies or organizations generally pull. You'll get "complete working examples", and a lot of it. The examples will be thousands of lines long and perform a million other things besides what the library itself does, let alone the function you just looked up. Good luck finding what you need amidst all the noise. The Dietel & Dietel line of how to program books that many colleges and universities use play the same game. Create enough information overload in the simplest of cases and force you to switch to a major in marketing.

I'm sorry your honor, I didn't realize I didn't turn over the last chapter.

This kind of documentation isn't so bad. You'll get some good notes on how to do all the basic stuff the library is capable of. But any function or class with any sort of complexity is completely missing, and you'll have to refer to the source code. But I guess the authors don't know how to put the trickier things into words, at least not like the easier stuff.

I think that about sums it up. There are some libraries out there with good documentation, but usually its of the kinds described above. Anyone else feel the same way?

FatELF Dead?

2009-11-06T03:16:00.000-08:00

A while back, someone came up with a project called FatELF. I won't go into the exact details of all its trying to accomplish, but the basic idea was that like Mac OS X has universal binaries using the Mach-o object format which can run on multiple architectures, the same should be possible with software for Linux and FreeBSD, which use the ELF object format.

The creators of FatELF cite many different reasons why FatELF is a good idea, which most of us probably disagree with. But I found it could solve a pretty crucial issue today.

The x86 line of processors which is what everyone uses for their home PCs recently switched from 32-bit to 64-bit. 64-bit x86 known as x86-64 is backwards compatible with the old architecture. However programs written for the new one generally run faster.

x86-64 CPUs contain more registers than traditional x86-32 ones, so a CPU can juggle more data internally without offloading it to much slower RAM. Also, most distributions offered precompiled binaries designed for a very low common denominator, generally a 4x86 or the original Pentium. Programs compiled for these older processors can't take advantage of much of the improvements that have been done to the x86 line in the past 15 years. A distribution which targets the lowest common denominator for x86-64 on the other hand is targeting a much newer architecture, where every chip already contains MMX, SSE, similar technologies, and other general enhancements.

Installing a distribution geared for x86-64 can mean a much better computing experience for the most part. Except certain programs unfortunately are not yet 64 bit ready, or are closed source and can't be easily recompiled. In the past year or two, a lot of popular proprietary software were ported by their companies to x86-64, but some which are important for business fail completely under x86-64, such as Cisco's Webex.

x86-32 binaries can run on x86-64, provided all the libraries it needs are available on the system. However, many distributions don't provide x86-32 libraries on their x86-64 platform, or they provide only a couple, or provide ones which simply don't work.

All these issues could be fixed if FatELF was supported by the operating system. A distribution could provide an x86-64 platform, with all the major libraries containing both 32 and 64 bit versions within. Things like GTK, Qt, cURL, SDL, libao, OpenAL, and etc. We wouldn't have to worry about one of these libraries conflicting when installing two variations, or simply missing from the system.

It would make it easier on those on an x86-64 bit platform knowing they can run any binary they get elsewhere without a headache. It would also ease deployment issues for those that don't do anything special to take advantage of x86-64, and just want to pass out a single version of their software.

I as a developer have to have an x86-32 chroot on all my development systems to make sure I can produce 32 bit binaries properly, which is also a hassle. All too often I have to jump back and forth between a 32 bit shell to compile the code, and a 64 bit shell where I have the rest of my software needed to analyze it, and commit it.

But unfortunately, it now seems FatELF is dead, or on its way.

I wish we could find a fully working solution to the 32 on 64 bit problem that crops up today.

They actually want bad code

2009-11-05T13:29:00.000-08:00

So I was in this huge meeting yesterday, and I got the shock of my life.

We were discussing how we're going to go about creating and marketing a new program which will be deployed on the servers of our clients. When I suggested I be the one to take charge of the program design and creation, and handpick my team of the best programmers in the company to write the code, I was shot down. The reason? They don't want the program to be written correctly. They don't want the code written by people who know what they're doing.

That had me completely flabbergasted. I needed more details. I asked what exactly was wrong with the way I did things? With creating the program properly? Our chief executive in charge of marketing dependability and quick maintenance boiled it down for me.

The problems with me writing the code are as follows:
No matter which language(s) we choose to build the program with, whether it be C++, PHP, C#, or something else, I'm going to make sure we use the classes and functions provided by the language most fit for use in our program. Every single function will be as clear and minimalistic and self contained as possible. And this is evil in terms of dependability and quick maintenance.

If for example we used C# with .NET and I found just the perfect class out of the few thousand provided to fit the job, and it turns out down the line some issue crops up, apparently, they can't complain to Microsoft. Microsoft will tell them no one uses that class, and it is probably buggy, and they'll put it on a todo list to be looked at several months down the line.

If I use any function or class in C++ or PHP outside of the most basic 10-20 ones that dime-a-dozen programmers learn right away, they won't be able to get someone outside our group of professionals to review and fix it.

Basically, they want the program written only using classes, functions, arrays, loops, and the least amount of standard library usage. Because a random programmer most likely will barely be familiar with anything contained within the standard library.

They would prefer reinventing built in functions, and also having them written incorrectly, in terms of output correctness, and running time. Since it means a programmer will never need to look in a manual to be able to understand a piece of code and fix it. Which is important apparently, as most can only figure out what is wrong with the logic directly in front of them, and then try to brute force correct output.

But it doesn't even stop at good code making good use of the language, instead of reinventing the wheel.

Quite often in our existing projects, I go to look at a bug report, and notice some function which works incorrectly, and in the process of fixing it, I condense the logic and make the code much better. Let me give an example.

This is very similar to an existing case we had. The code was as follows:


/*
This function creates a log on Sunday, Tuesday, Thursday
It takes as input an integer with a value of 1-7, 1 being Sunday.
*/
void logEveryOtherDay(int dayOfTheWeek)
{
  if (dayOfTheWeek == 1)
  {
    logger.open();
    logger.write("Sunday");
    logger.dumpData();
    logger.close();
  }
  else if (dayOfTheWeek == 3)
  {
    logger.open();
    logger.write("-------------");
    logger.write("Tuesday");
    logger.dumpData();
    logger.close();
  }
  else if (dayOfTheWeek == 5)
  {
    logger.open();
    logger.write("-------------");
    logger.write("Thursday");
    logger.dumpData();
    logger.close();
  }
}

The problem reported was that logs from Sunday missed the ----- separator before it, and they'd want a log on Saturday too if ran then. When fixing it, the code annoyed me, and I quickly cleaned it to the following:


//This functions takes an integer and returns true if it's odd, and false if even
static bool isOdd(int i) { return(i&1); }

static const char *daysOfTheWeek[] = {
  0, //Begin with nothing, as we number the days of the week 1-7
  "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"
}

/*
This function creates a log on Sunday, Tuesday, Thursday, Saturday
It takes as input an integer with a value of 1-7, 1 being Sunday.
*/
void logEveryOtherDay(int dayOfTheWeek)
{
  if (isOdd(dayOfTheWeek)) //Logging isn't done on even days
  {
    logger.open();
    logger.write("-------------");
    logger.write(daysOfTheWeek(dayOfTheWeek));
    logger.dumpData();
    logger.close();
  }
}

I think it should be obvious my code has much cleaner logic, and should be easy for any reasonable programmer to follow. I frequently do things like this. I even once went to look at a 2000 line function which had roughly a dozen bug reports against it, was a total mess, and ran really really slowly. Instead of hunting for the cause of each issue in it, I decided to scrap it. I created 2 helper functions, one 3 lines, the other 5, and rewrote the body of the function from 2000 lines to roughly 40. Instead of many nested ifs and several loops, we now had a single if and else which did exactly what they needed to, and called one of the two helper functions as needed where the real looping was done. The new function was profiled to run an order of a magnitude faster, and it passed all the test cases we designed, where the original failed a few. It now also contained 2 new features which were sorely lacking from the original. It was now also much easier to read it for correctness, as much less was going on in any section of the code.

But as this executive continued to tell me, what I did on these occasions is evil for an average programmer.

They can't comprehend a small amount of code doing so much. They can't understand what isOdd() does or is trying to do, unless they actually see its source. Its source of "return(i&1);" is just too confusing for them, because they don't know what "&1" means, nor can they comprehend how it can return true or false without containing an elaborate body of code. They can't just take the comment at face value that it does what it says it does. They are also frightened when they review different versions of a file to try to trace a bug when they see a ton of code just disappeared at some point, yet says it does more in the commit log.

So to sum it up, they don't want me, or programmers like me working on any code that is to be deployed on a client's server. When a client from Africa, or South America calls us up with a problem, they don't want to fly one of our good programmers down there to look at it. They want to make sure they can hire someone on site in one of those places to go and look at the problem and fix it quickly. Which apparently can't happen when there's no guarantee of being able to hirer a good programmer there on short notice, and other kinds of programmers can't deal with good code or standard library/class usage.

This mentality makes me very scared, although I guess it does explain to some extent why I find the innards of many rather large open source projects which are used commercially to be filled with tons of spaghetti logic, and written in a manner which suggests the author didn't really know what they were doing, nor should they be allowed to write code.

Anyone experience anything similar? Comments?

Who still watches Television?

2009-10-28T07:09:00.000-07:00

So I know a couple of people who every night or so, sit down and watch Television. I find the very thought of it mind boggling. Why would anyone torture h[im/er]self so?

Television is all about locking yourself into someone else's timetable.

Each show comes on when your network decides it comes on.
You can't go back in case you missed something.
You can't rewatch a particular enjoyable scene.
You can't pause.
You can't stop it and continue it later.
You can't skip an annoying scene.

I find the idea of such a lack of control on the viewer's part excruciatingly painful.

People miss appointments or go to bed late because they just had to know what happens. Parents have to fight with their kids to get them to do homework, which would make them miss their favorite show.

People don't take proper care of themselves by not going to use the facilities when they need to, or getting a drink, or answering the phone. The list of problems goes on and on.

This problem was always apparent, and many people bought video cassette recorders, or other newer devices to get the same job done. But there were those that didn't, and instead preferred to torture themselves.

Okay, at first the technology may have been annoying (video cassettes), then it was too expensive. It's always another annoying peripheral in your house for the most part just taking up space. But why is this still going on today?

If you read this site often, it's quite likely you own your own computer at home and have a high speed internet connection. There's also a good chance if you bought a computer or new hard drive in the past few years, that you have gigabytes of free space that you have no idea what to do with.

If you own what I described above, why would you want to torture yourself so? Many stations are now putting their shows on their website which you can watch in mid-quality annoying flash. But ignoring that, nowadays, there are tons of people who record the show and then share that recording via Bit Torrent or file sharing websites.

Unlike traditional home recording techniques, quite often you don't even have to program your device when to record for you anymore - when using a computer. Many "Online Television" sites provide RSS feeds that you can subscribe to which would automatically download your favorite shows as each episode comes out. You don't have to screw up setting to record at 3:59, and finding out your time was three minutes behind the network, and you missed the beginning. Or instead of setting the end time to 5:01, you screwed up and selected 4:01, and recorded a grand total of two minutes of your hour long show.

These sites generally have the shows up a couple of minutes after they air in the earliest timezone showing them, and the files are of good quality, yet small enough to be downloaded in just a couple of minutes. If you happen to live in a later timezone, many times you can be finished watching a show before it even airs where you live.

So who exactly is still torturing themselves? And why?

Before you question, what would happen if everyone only started watching "Online Television", who exactly would be doing the recordings? We have to ask ourselves why aren't the companies producing these shows using the new medium available to distribute them? If they had an RSS feed with all the new shows set up to be downloaded via Bit Torrent on them (advertisements included), I'm sure many people would subscribe to them. They could even charge a few bucks a year to gain access to a private torrent, cutting out the middlemen (networks, cable companies) they use.

Distributed HTTP

2009-10-25T10:19:00.000-07:00

A couple years back, a friend of mine got into an area of research which was rather novel and interesting at the time. He created a website he hosted from his own computer, where one can read about the research, and download various data samples he made.

Fairly soon, it was apparent that he couldn't host any large data samples. So he found the best compression software available, and setup a BitTorrent tracker on his computer. When someone downloaded some data samples, they would be sharing the bandwidth load, allowing more interested parties to download at once without crushing my friend's connection. This was back at a time when BitTorrent was unheard of, but those interested in getting the data would make the effort to do so.

As time went on, his site popularity grew. He installed some forum software on his PC, so a community could begin discussing his findings. He also gave other people login credentials to his machine, so they can edit pages, and upload their own data.

The site evolved into something close to a wiki, where each project got its own set of pages describing it, and what was currently known on the topic. Each project got some images to visually provide an idea of what each data set covered before one downloaded the torrent file. Some experiments also started to include videos.

As the hits to his site kept increasing, my friend could no longer host his site on his own machine, and had to move his site to a commercial server which required payment on a monthly or yearly basis. While BitTorrent could cover the large data sets, it in no way provided a solution to hosting the various HTML pages and PNG images.

The site constantly gained popularity, and my friend was forced to keep upgrading to an increasingly more powerful server, where the hosting costs increased just as rapidly. Requests for donations, and ads on the server could only help offset costs to an extent.

I imagine other people and small communities have at times run into similar problems. I think its time for a solution to be proposed.

Every major browser today caches files for each site it visits, so it doesn't have to rerequest the same images, scripts, and styles on each page, and conditionally requests pages, only if they haven't been updated since what was in the cache. I think this already solves one third of the problem.

A new URI scheme can be created, perhaps dhttp:// that would act just like normal HTTP with a couple of exceptions. The browser would have some configurable options for Distributed HTTP, such as up to how many MB per site will it cache, how many MB overall, how many simultaneous uploads will it be willing to provide per site, as well as overall, which port it will run on, and a duration as to how long it will do so. When the browser connects via dhttp://, it'll include some extra headers providing the user's desired settings on this matter. The HTTP server will be modified to keep track of which IP addresses connected to it, and downloaded which files recently.

When a request for a file comes into the DHTTP server, it can respond with a list of perhaps five IP addresses to choose from (if available), chosen based on an algorithm designed to round robin the available browsers connecting to the site, and the preferences chosen therein. The browser can then request via a normal HTTP request the same file from one of those IP addresses it received. The browser would need a miniature HTTP server built in which would understand that requests coming to it that seem to be for a DHTTP server should be replied to from its cache. It would also know not to share files that are in the cache which did not originate from a DHTTP server.

If requests to each of those IP addresses have timed out, or responded with 404, then the browser can rerequest that file from the DHTTP server set with a timeout or unavailable header for each of those IP addresses, in which case the DHTTP server will respond with the requested file directly.

The HTTP server should also know to keep track of when files are updated, so it knows not to refer a visitor to an IP address which contains an old file. This forwarding concept should also be disabled in cases of private data (login information), or dynamic pages. However for static (or dynamic which is only generated periodically) public data, all requests should be satisfiable by this described method.

Thought would have to be put into how to handle "leach" browsers which never share from their cache, or just always request from the DHTTP server with timeout or unavailable headers sent.

I think something implemented along these lines can help those smaller communities that host sites on their own machines, and would like to remain self hosting, or would like to alleviate hosting costs on commercial servers.

Thoughts?

Blogger Spam

2009-10-23T05:52:00.001-07:00

If you remember, the other day I had a bit of a meltdown in terms of all the spam I saw piling up over here.

I only have ~30 articles here, yet I had over 300 comments which were spam, and it is quite an annoying task to go delete them one by one. Especially when a week later, I'll have to go delete them one by one yet again.

Instead of just throwing my hands up in the air, I found it was time to get insane - I went to check out Blogger's API. So looking it over, I found it's really easy to log in, and about everything else after that gets annoying.

Blogger provides a way to get a list of articles, create new articles, delete articles, and also managing their comments. But the support is kind of limited if you want to specify what kind of data you want to retrieve.

At first, I thought about analyzing each comment for spam, but I didn't want to run the risk of false positives, and figured my best bet for now is just to identify spammers. I identified 25 different spam accounts.

However, Blogger only offers deleting comments by the comment ID, and then, only one by one. The only way to retrieve the comment ID is to retrieve the comments for a particular article, which includes the comments themselves and a bunch of other data. All this data is in a rather large XML file.

It would be rather easy to delete comments if Blogger provided a function like deleteCommentsOf(userId, blogId), or getCommentIdsOf(userId, blogId), or something similar. But no, one needs 4 steps just to get an XML file which contains the comments IDs along with a lot of other unnecessary data. This has to be repeated for each article.

It seems Blogger's API is really only geared towards providing various types of news feeds of a blog, and minimal remote management to allow others to create an interface for one to interact with blogger on a basic level. Nothing Blogger provides is geared towards en masse management.

Blogger also has the nice undocumented caveat that when retrieving a list of articles for a site, it includes all draft articles not published yet, if the requester is currently logged in.

But no matter, I create APIs wrapped around network requests and parsing data for a living. So using the libraries I created and use at work for this kind of thing, and 200 lines later which includes plenty of comments and whitespace, I got an API which allows me to delete all comments from a particular user from a Blogger site. So I arm an application using my new API with the 25 users I identified, and a few minutes later, presto, they're all gone.

As of the time of this posting, there should be no spam in any of the articles here. I will have to rerun my application periodically, as well as update it with the user IDs of new spam accounts, but it shouldn't be a big deal any more.

Remember the old programming dictum: Annoyance+Laziness = Great Software. It surely beats deleting things by hand every couple of days.

Why online services suck

2009-10-19T08:39:00.000-07:00

Does anyone other than me think online services suck?

The thing that annoys me the most is language settings. Online service designers one day had this great idea to check the geographical IP address the user visited their site from, and use it to automatically set the language to the native one for the country they visited from. While this sounds nice in theory, most people only know their mother tongue, and also go on vacation now and then, or visit some other country for business purposes.

So here I am, on business in a foreign country, and I connect my laptop into the Ethernet jack in my hotel room which comes with free Internet access, so I can check my e-mail. What's the first thing I notice? The entire interface is no longer in English. Even worse is that the various menu items and buttons are moved around in this other language.

Even Google, known for being ahead of the curve when it comes to web services can't help but make the same mistakes. I'm sitting here looking at the menu on top of Blogger, wondering which one is login.

For Google this is a worse offense compared to other service providers, as I already was logged into their main site.

Google keeps their cookies set for all eternity (well, until the next time rollover disaster), and they know I always used Google in English. Now it sees me connecting from a different country than usual and thinks I want my language settings switched? Even after I set it to English on their main page, I have to figure out how to set it to English again on Blogger and YouTube?

What's really sad about all this is that every web browser sends each website as part of its request a "user agent", which tells the web server the name of the browser, a version number, operating system details, and language information. My browser is currently sending: "Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.0.11)". Notice the en-US? That tells the site the browser is in English, for the United States. If I downloaded a different version of Firefox, or installed a language package and switched Firefox to a different language, it would tell the web server that I did so. If one uses Windows in another language, Internet Explorer will also tell the web server the language Windows/Internet Explorer is in.

Why are these service providers ignoring browser information, and instead solely looking at geographical information? People travel all the times these days. Let us also not forget those in restrictive countries who use foreign proxy servers to access the internet.

However, common issues, such as annoying language support is hardly the end of the problems. In terms of online communication, virtually all of them suffer from variations of spam. Again, where is Google here? Every time I go read comments on Blogger, I see nothing but spam posts. Even when I go to cleanup my own site, the spam just fills up again a few days later.

Where's the flag as spam button? Where's the flag this user as solely a spammer button?

Sure Google as a site manager lets me block all comments on my site till I personally review them to see if they're spam, but in today's need for hi-speed communication is that really an option when you may have a hot topic on hand? Why can't readers flag posts on their own?

In terms of management, why doesn't Blogger's site management features include a list where I can check off posts and hit one mass delete, instead of having to click delete and "Yes I'm sure" on each and every spam post? Why can't I delete all posts from user X and ban that user from ever posting on my site again?

Okay, maybe this isn't so much an article why online services suck, but more about language and spam complaints, and mostly at Google for the moment. Jet-lag, and getting your E-mail interface in Gibberish does wonders for a friendly post. I'll try to come up something better for my next article.

How end users can utilize multicore processors

2009-06-21T21:52:00.000-07:00

In recent years, the average desktop/workstation computer has gone from single core to multiple cores. Those of us who do video encoding, compression, or run a lot of processes at once are absolutely loving it. Where does everyone else fit in?

Why multiple cores?

How many operations a particular CPU core could do at once has been increasing over the years. If we compare what we can do today with what were able to do a decade ago, we see we've come a long way. Our CPU cores were once doubling in speed every 18 months. However, in recent times, it seems trying to push the CPU farther and farther in how much it could do at once has been steadily getting closer and closer to the theoretical maximum. There's only so much we can do to make the various components that make up a CPU get closer together on the silicon, or work better together, with today's technology, and without making the chip catch fire. Therefore, we went to the next logical step, put more than one CPU on each CPU slab we stick in our motherboards.

Are CPUs currently fast enough?

CPUs have gotten so fast in recent years, that for normal every day usage, they're fast enough. Whether I'm browsing the web, writing an e-mail, doing some math, painting a pretty picture, listening to music, watching a video, doing my taxes, or most other common tasks, nothing about the machine's speed disappoints me. I've found 2 GHz to be fast enough. Unlike the old days, I'm not sitting in front of a machine wishing it could go faster, or subconsciously reaching for my remote to hit the fast forward button while watching a program load or complete an operation. Of course increased memory availability played a role in this too. In any event, computers made in the past 5 years or so have been fast enough for most people.

So what can multiple cores do for me?

Well, for certain applications, where large processes can be broken up into other smaller independent processes, the processes can be completed faster. For video encoding, a video frame can be broken up into quadrants, each one handled individually. For compression, a file can be broken up into chunks, and each compressed separately. You can now also run a lot of processes at once. You can have an HTTP Server, an application server, and a database server all running on a single machine without any one of them slowing the others down. Even for home users, you can run more background processes, such as your virus scanner while you're working on other projects. For programmers like myself, it's great, I can compile multiple programs at once, or have a program compiling in the background, while still doing other stuff, such as burning a DVD, listening to music, and reading CNN, with everything being really fast and responsive, and without my DVD drive spitting out a coaster. Also, if you like running multiple operating systems at once using VirtualBox or something similar, you can assign each operating system you're currently using its own CPU.

So what can't multiple cores do?

Multiple cores can't make single threaded applications work faster. If all you're doing is playing your average game, or writing a letter or something similar, you'll have one core being used to it's maximum, while the others are just sitting there doing nothing.

Why aren't more applications multi-threaded?

This is simply a matter of there's nothing to do to make them multi-threaded. In a program where every single operation is based off of the result of the previous operation, there is no way to break it up into two components, to run each in a different thread, and by extension, each in a different CPU core. Even if there are a couple of occasional segments that can be broken up, in many cases it may not be worth the overhead of doing so. Multi-threading only works well when there's large segments each containing many operations in them that can be broken up. Multi-threading fails if the two threads have to constantly sync results between them.

So why should the average user bother for 4 or 8 core processors?

This is an excellent question. Why should a business or average home user waste money on these higher end CPUs? Let me call your attention to a few other points about modern computers.

Modern desktop computers even at home and work generally come with:

6 audio jacks in the rear, 2 in the front
8 or more USB ports
A video card with two DVI connectors
A motherboard which supports 2 video cards

Now of course there's cases where you want 7.1 sound, and lots of microphones, and other devices plugged in, your cameras, gamepads, and printers (hey, printers belong attached to your network switch!), multiple screens, or lots of video cards working together on video like CPUs do in the cases similar to what I highlighted above.

Now if you realize what you have, it all seems a little too convenient.
4 cores - 4 users.
8 audio jacks - Speakers + Microphone per user for 4 users.
8 USB ports - Keyboard+Mouse per user for 4 users.
2 video cards with 2 DVI each - 4 screens.

It almost seems like the average machine you can buy for $500-$600 is asking you to use it for 4 users!

Now the great thing is, even average integrated sound cards allow each jack to receive their own programming, and plugging something in one jack doesn't force mute another. On many models, even a jack's primary use of input/output is really left up to the software, and only the average drivers force it to be one or the other.

You can buy extension cords to keep your "virtual" computers further away from each other. You can get powered USB hubs to provide as many USB ports you want to each user, or get keyboards which offer additional USB ports on them so users can plug in thier own devices such as memory sticks.

Now look back at the average home user. Who at home with only a single computer doesn't get the wife or kids nagging they want to do something? Who at home or at work wouldn't like to cut costs a bit? You already are going to have to buy several screens, speakers, keyboards, and mice. Now just buy one computer, maybe spend $100-$200 on it more than you wanted to, and perhaps another $50 on extension cords, and now you don't have to buy another 1-3 computers, which would add on $400-$2000.

Imagine even if you're a power user who does a lot of intensive projects that you need that really powerful computer for. How often are you really encoding those videos? Can you just have them queued up to be done at night while everyone is sleeping?

You can now also spend a little extra on that processor and video card to keep your son happy playing all those new games, while you get a lot more power out of your computer during normal hours while he's doing homework, and you're doing your taxes, all on the same machine, and still end up saving money. You also now only have to run that virus scanner on a single machine in the background, instead of several.

So now the question is, can we already do this? And how well can we do it?
There's some articles you can read, on how to set it up, but it seems a lot more of a hassle than one would like.

It'd be really nice to have a special multiseat optimized distro ready to be used in such a manner out of the box. Or perhaps a distro such as Ubuntu provided a special mode for it. Maybe even GNOME or KDE should have an admin setting where they can detect your current setup and offer an option turn the multiple virtual desktops they have on them into an environment suitable for multiple users with just a single click.

Of course this would probably need a lot more work done in the sound area to provide a virtual sound system to each user, and make sure the underlying drivers can work with each audio jack independently. Also would mean they'd have to understand how to sandbox each particular virtual desktop now residing on each screen to the inputs in front of it.

Thoughts?

State of sound in Linux not so sorry after all

2009-06-18T20:29:00.000-07:00

About two years ago, I wrote an article titled the "The Sorry State of Sound in Linux", hoping to get some sound issues in Linux fixed. Now two years later a lot has changed, and it's time to take another look at the state of sound in Linux today.

A quick summary of the last article for those that didn't read it:

Sound in Linux has an interesting history, and historically lacked sound mixing on hardware that was more software based than hardware.
Many sound servers were created to solve the mixing issue.
Many libraries were created to solve multiple back-end issues.
ALSA replaced OSS version 3 in the Kernel source, attempting to fix existing issues.
There was a closed source OSS update which was superb.
Linux distributions have been removing OSS support from applications in favor of ALSA.
Average sound developer prefers a simple API.
Portability is a good thing.
Users are having issues in certain scenarios.

Now much has changed, namely:

OSS is now free and open source once again.
PulseAudio has become widespread.
Existing libraries have been improved.
New Linux Distributions have been released, and some existing ones have attempted an overhaul of their entire sound stack to improve users' experience.
People read the last article, and have more knowledge than before, and in some cases, have become more opinionated than before.
I personally have looked much closer at the issue to provide even more relevant information.

Let's take a closer look at the pros and cons of OSS and ALSA as they are, not five years ago, not last year, not last month, but as they are today.

First off, ALSA.
ALSA consists of three components. First part is drivers in the Kernel with an API exposed for the other two components to communicate with. Second part is a sound developer API to allow developers to create programs which communicate with ALSA. Third part is a sound mixing component which can be placed between the other two to allow multiple programs using the ALSA API to output sound simultaneously.

To help make sense of the above, here is a diagram:

Note, the diagrams presented in this article are made by myself, a very bad artist, and I don't plan to win any awards for them. Also they may not be 100% absolutely accurate down to the last detail, but accurate enough to give the average user an idea of what is going on behind the scenes.

A sound developer who wishes to output sound in their application can take any of the following routes with ALSA:

Output using ALSA API directly to ALSA's Kernel API (when sound mixing is disabled)
Output using ALSA API to sound mixer, which outputs to ALSA's Kernel API (when sound mixing is enabled)
Output using OSS version 3 API directly to ALSA's Kernel API
Output using a wrapper API which outputs using any of the above 3 methods

As can be seen, ALSA is quite flexible, has sound mixing which OSSv3 lacked, but still provides legacy OSSv3 support for older programs. It also offers the option of disabling sound mixing in cases where the sound mixing reduced quality in any way, or introduced latency which the end user may not want at a particular time.

Two points should be clear, ALSA has optional sound mixing outside the Kernel, and the path ALSA's OSS legacy API takes lacks sound mixing.

An obvious con should be seen here, ALSA which was initially designed to fix the sound mixing issue at a lower and more direct level than a sound server doesn't work for "older" programs.

Obvious pros are that ALSA is free, open source, has sound mixing, can work with multiple sound cards (all of which OSS lacked during much of version 3's lifespan), and included as part of the Kernel source, and tries to cater to old and new programs alike.

The less obvious cons are that ALSA is Linux only, it doesn't exist on FreeBSD or Solaris, or Mac OS X or Windows. Also, the average developer finds ALSA's native API too hard to work with, but that is debatable.

Now let's take a look at OSS today. OSS is currently at version 4, and is a completely different beast than OSSv3 was.
Where OSSv3 went closed source, OSSv4 is open sourced today, under GPL, 3 clause BSD, and CDDL.
While a decade old OSS was included in the Linux Kernel source, the new greatly improved OSSv4 is not, and thus may be a bit harder for the average user to try out. Older OSSv3 lacked sound mixing and support for multiple sound cards, OSSv4 does not. Most people who discuss OSS or try OSS to see how it stacks up against ALSA unfortunately are referring to, or are testing out the one that is a decade old, providing a distortion of the facts as they are today.

Here's a diagram of OSSv4:
A sound developer wishing to output sound has the following routes on OSSv4:

Output using OSS API right into the Kernel with sound mixing
Output using ALSA API to the OSS API with sound mixing
Output using a wrapper API to any of the above methods

Unlike in ALSA, when using OSSv4, the end user always has sound mixing. Also because sound mixing is running in the Kernel itself, it doesn't suffer from the latency ALSA generally has.

Although OSSv4 does offer their own ALSA emulation layer, it's pretty bad, and I haven't found a single ALSA program which is able to output via it properly. However, this isn't an issue, since as mentioned above, ALSA's own sound developer API can output to OSS, providing perfect compatibility with ALSA applications today. You can read more about how to set that up in one of my recent articles.

ALSA's own library is able to do this, because it's actually structured as follows:

As you can see, it can output to either OSS or ALSA Kernel back-ends (other back-ends too which will be discussed lower down).

Since both OSS and ALSA based programs can use an OSS or ALSA Kernel back-end, the differences between the two are quite subtle (note, we're not discussing OSSv3 here), and boils down to what I know from research and testing, and is not immediately obvious.

OSS always has sound mixing, ALSA does not.
OSS sound mixing is of higher quality than ALSA's, due to OSS using more precise math in its sound mixing.
OSS has less latency compared to ASLA when mixing sound due to everything running within the Linux Kernel.
OSS offers per application volume control, ALSA does not.
ALSA can have the Operating System go into suspend mode when sound was playing and come out of it with sound still playing, OSS on the other hand needs the application to restart sound.
OSS is the only option for certain sound cards, as ALSA drivers for a particular card are either really bad or non existent.
ALSA is the only option for certain sound cards, as OSS drivers for a particular card are either really bad or non existent.
ALSA is included in Linux itself and is easy to get ahold of, OSS (v4) is not.

Now the question is where does the average user fall in the above categories? If the user has a sound card which only works (well) with one or the other, then obviously they should use the one that works properly. Of course a user may want to try both to see if one performs better than the other one.

If the user really needs to have a program output sound right until Linux goes into suspend mode, and then continues where it left off when resuming, then ALSA is (currently) the only option. I personally don't find this to be a problem, and furthermore I doubt it's a large percentage of users that even use suspend in Linux. Suspend in general in Linux isn't great, due to some rogue piece of hardware like a network or video card which screws it up.

If the user doesn't want a hassle, ALSA also seems the obvious choice, as it's shipped directly with the Linux Kernel, so it's much easier for the user to use a modern ALSA than it is a modern OSS. However it should be up to the Linux Distribution to handle these situations, and to the end user, switching from one to the other should be seamless and transparent. More on this later.

Yet we also see due to better sound mixing and latency when sound mixing is involved, that OSS is the better choice, as long as none of the above issues are present. But the better mixing is generally only noticed at higher volume levels, or rare cases, and latency as I'm referring to is generally only a problem if you play heavy duty games, and not a problem if you just want to listen to some music or watch a video.

But wait this is all about the back-end, what about the whole developer API issue?

Many people like to point fingers at the various APIs (I myself did too to some extent in my previous article). But they really don't get it. First off, this is how your average sound wrapper API works:

The program outputs sound using a wrapper, such as OpenAL, SDL, or libao, and then sound goes to the appropriate high level or low level back-end, and the user doesn't have to worry about it.

Since the back-ends can be various Operating Systems sound APIs, they allow a developer to write a program which has sound on Windows, Mac OS X, Linux, and more pretty easily.

Some like Adobe like to say how this is some kind of problem, and makes it impossible to output sound in Linux. Nothing could be further from the truth. Graphs like these are very misleading. OpenAL, SDL, libao, GStreamer, NAS, Allegro, and more all exist on Windows too. I don't see anyone complaining there.

I can make a similar diagram for Windows:

This above diagram is by no means complete, as there's XAudio, other wrapper libs, and even some Windows only sound libraries which I've forgotten the name of.

This by no means bothers anybody, and should not be made an issue.

In terms of usage, the libraries stack up as follows:
OpenAL - Powerful, tricky to use, great for "3D audio". I personally was able to get a lot done by following a couple of example and only spent an hour or two adding sound to an application.
SDL - Simplistic, uses a callback API, decent if it fits your program design. I personally was able to add sound to an application in half an hour with SDL, although I don't think it fits every case load.
libao - Very simplistic, incredibly easy to use, although problematic if you need your application to not do sound blocking. I added sound to a multitude of applications using libao in a matter of minutes. I just think it's a bit more annoying to do if you need to give your program its own sound thread, so again depends on the case load.

I haven't played with the other sound wrappers, so I can't comment on them, but the same ideas are played out with each and every one.

Then of course there's the actual OSS and ALSA APIs on Linux. Now why would anyone use them when there are lovely wrappers that are more portable, customized to match any particular case load? In the average case, this is in fact true, and there is no reason to use OSS or ALSA's API to output sound. In some cases, using a wrapper API can add latency which you may not want, and you don't need any of the advantages of using a wrapper API.

Here's a breakdown of how OSS and ALSA's APIs stack up.
OSSv3 - Easy to use, most developers I spoke to like it, exists on every UNIX but Mac OS X. I added sound to applications using OSSv3 in 10 minutes.
OSSv4 - Mostly backwards compatible with v3, even easier to use, exists on every UNIX except Mac OS X and Linux when using the ALSA back-end, has sound re-sampling, and AC3 decoding out of the box. I added sound to several applications using OSSv4 in 10 minutes each.
ALSA - Hard to use, most developers I spoke to dislike it, poorly documented, not available anywhere but Linux. Some developers however prefer it, as they feel it gives them more flexibility than the OSS API. I personally spent 3 hours trying to make heads or tails out of the documentation and add sound to an application. Then I found sound only worked on the machine I was developing on, and had to spend another hour going over the docs and tweaking my code to get it working on both machines I was testing on at the time. Finally, I released my application with the ALSA back-end, to find several people complaining about no sound, and started receiving patches from several developers. Many of those patches fixed sound on their machine, but broke sound on one of my machines. Here we are a year later, and my application after many hours wasted by several developers, ALSA now seems to output sound decently on all machines tested, but I sure don't trust it. We as developers don't need these kinds of issues. Of course, you're free to disagree, and even cite examples how you figured out the documentation, added sound quickly, and have it work flawlessly everywhere by everyone who tested your application. I must just be stupid.

Now I previously thought the OSS vs. ALSA API issue was significant to end users, in so far as what they're locked into, but really it only matters to developers. The main issue is though, if I want to take advantage of all the extra features that OSSv4's API has to offer (and I do), I have to use the OSS back-end. Users however don't have to care about this one, unless they use programs which take advantage of these features, which there are few of.

However regarding wrapper APIs, I did find a few interesting results when testing them in a variety of programs.
App -> libao -> OSS API -> OSS Back-end - Good sound, low latency.
App -> libao -> OSS API -> ALSA Back-end - Good sound, minor latency.
App -> libao -> ALSA API -> OSS Back-end - Good sound, low latency.
App -> libao -> ALSA API -> ALSA Back-end - Bad sound, horrible latency.
App -> SDL -> OSS API -> OSS Back-end - Good sound, really low latency.
App -> SDL -> OSS API -> ALSA Back-end - Good sound, minor latency.
App -> SDL -> ALSA API -> OSS Back-end - Good sound, low latency.
App -> SDL -> ALSA API -> ALSA Back-end - Good sound, minor latency.
App -> OpenAL -> OSS API -> OSS Back-end - Great sound, really low latency.
App -> OpenAL -> OSS API -> ALSA Back-end - Adequate sound, bad latency.
App -> OpenAL -> ALSA API -> OSS Back-end - Bad sound, bad latency.
App -> OpenAL -> ALSA API -> ALSA Back-end - Adequate sound, bad latency.
App -> OSS API -> OSS Back-end - Great sound, really low latency.
App -> OSS API -> ALSA Back-end - Good sound, minor latency.
App -> ALSA API -> OSS Back-end - Great sound, low latency.
App -> ALSA API -> ALSA Back-end - Good sound, bad latency.

If you're having a hard time trying to wrap your head around the above chart, here's a summary:

OSS back-end always has good sound, except when using OpenAL->ALSA to output to it.
ALSA generally sounds better when using the OSS API, and has lower latency (generally because that avoids any sound mixing as per an earlier diagram).
OSS related technology is generally the way to go for best sound.

But wait, where do sound servers fit in?

Sounds servers were initially created to deal with problems caused by OSSv3 which currently are non existent, namely sound mixing. The sound server stack today looks something like this:

As should be obvious, these sound servers today do nothing except add latency, and should be done away with. KDE 4 has moved away from the aRts sound server, and instead uses a wrapper API known as Phonon, which can deal with a variety of back-ends (which some in themselves can go through a particular sound server if need be).

However as mentioned above, ALSA's mixing is not of the same high quality as OSS's is, and ALSA also lacks some nice features such as per application volume control.

Now one could turn off ALSA's low quality mixer, or have an application do it's own volume control internally via modifying the sound wave its outputting, but these choices aren't friendly towards users or developers.

Seeing this, Fedora and Ubuntu has both stepped in with a so called state of the art sound server known as PulseAudio.

If you remember this:

As you can see, ALSA's API can also output to PulseAudio, meaning programs written using ALSA's API can output to PulseAudio and use PulseAudio's higher quality sound mixer seamlessly without requiring the modification of old programs. PulseAudio is also able to send sound to another PulseAudio server on the network to output sound remotely. PulseAudio's stack is something like this:

As you can see it looks very complex, and a 100% accurate breakdown of PulseAudio is even more complex.

Thanks to PulseAudio being so advanced, most of the wrapper APIs can output to it, and Fedora and Ubuntu ship with all that set up for the end user, it can in some cases also receive sound written for another sound server such as ESD, without requiring ESD to run on top of it. It also means that many programs are now going through many layers before they reach the sound card.

Some have seen PulseAudio as the new Voodoo which is our new savior, sound written to any particular API can be output via it, and it has great mixing to boot.

Except many users who play games for example are crying that this adds a TREMENDOUS amount of latency, and is very noticeable even in not so high-end games. Users don't like hearing enemies explode a full 3 seconds after they saw the enemy explode on screen. Don't let anyone kid you, there's no way a sound server, especially with this level of bloat and complexity ever work with anything approaching low latency acceptable for games.

Compare the insanity that is PulseAudio with this:

Which do you think looks like a better sound stack, considering that their sound mixing, per application volume control, compatibility with applications, and other features are on par?

And yes, lets not forget the applications. I'm frequently told about how some application is written to use a particular API, therefore either OSS or ALSA need to be the back-end they use. However as explained above, either API can be used on either back-end. If setup right, you don't have to have a lack of sound using newer version of Flash when using the OSS back-end.

So where are we today exactly?
The biggest issues I find is that the Distributions simply aren't setup to make the choice easy on the users. Debian and derivatives provide a Linux sound base package to select whether you want OSS or ALSA to be your back-end, except it really doesn't do anything. Here's what we do need from such a package:

On selecting OSS, it should install the latest OSS package, as well as ALSA's ALSA API->OSS back-end interface, and set it up.
Minimally configure an installed OpenAL to use OSS back-end, and preferably SDL, libao, and other wrapper libraries as well.
Recognize the setting when installing a new application or wrapper library and configure that to use OSS as well.
Do all the above in reverse when selecting ALSA instead.

Such a setup would allow users to easily switch between them if their sound card only worked with the one which wasn't the distribution's default. It would also easily allow users to objectively test which one works better for them if they care to, and desire to use the best possible setup they can. Users should be given this capability. I personally believe OSS is superior, but we should leave the choice up to the user if they don't like whichever is the system default.

Now I repeatedly hear the claim: "But, but, OSS was taken out of the Linux Kernel source, it's never going to be merged back in!"

Let's analyze that objectively. Does it matter what is included in the default Linux Kernel? Can we not use VirtualBox instead of KVM when KVM is part of the Linux Kernel and VirtualBox isn't? Can we not use KDE or GNOME when neither of them are part of the Linux Kernel?

What matters in the end is what the distributions support, not what's built in. Who cares what's built in? The only difference is that the Kernel developers themselves won't maintain anything not officially part of the Kernel, but that's the precise jobs that the various distributions fill, ensuring their Kernel modules and related packages work shortly after each new Kernel comes out.

Anyways, a few closing points.

I believe OSS is the superior solution over ALSA, although your mileage may vary. It'd be nice if OSS and ALSA just shared all their drivers, not having an issue where one has support for one sound card, but not the other.

OSS should get suspend support and anything else it lacks in comparison to ALSA even if insignificant. Here's a hint, why doesn't Ubuntu hire the OSS author and get it more friendly in these last few cases for the end user? He is currently looking for a job. Also throw some people at it to improve the existing volume controlling widgets to be friendlier with the new OSSv4, and maybe get stuff like HAL to recognize OSSv4 out of the box.

Problems should be fixed directly, not in a roundabout matter as is done with PulseAudio, that garbage needs to go. If users need remote sound (and few do), one should just be easily able to map /dev/dsp over NFS, and output everything to OSS that way, achieving network transparency on the file level as UNIX was designed for (everything is a file), instead of all these non UNIX hacks in place today in regards to sound.

The distributions really need to get their act together. Although in recent times Draco Linux has come out which is OSS only, and Arch Linux seems to treat OSSv4 as a full fledged citizen to the end user, giving them choice, although I'm told they're both bad in the the ALSA compatibility department not setting it up properly for the end user, and in the case of Arch Linux, requiring the user to modify the config files of each application/library that uses sound.

OSS is portable thanks to its OS abstraction API, being more relevant to the UNIX world as a whole, unlike ALSA. FreeBSD however uses their own take on OSS to avoid the abstraction API, but it's still mostly compatible, and one can install the official OSSv4 on FreeBSD if they so desire.

Sound in Linux really doesn't have to be that sorry after all, the distributions just have to get their act together, and stop with all the finger pointing, propaganda, and FUD that is going around, which is only relevant to ancient versions of OSS, if not downright irrelevant or untrue. Let's stop the madness being perpetrated by the likes of Adobe, PulseAudio propaganda machine, and whoever else out there. Let's be objective and use the best solutions instead of settling for mediocrity or hack upon hack.

Perfect sound with OSS version 4

2009-05-25T17:06:00.000-07:00

So I just happened to be keeping my eye on some packages being upgraded in Debian on dist-upgrade, and something caught my eye, the package "libasound2-plugins". I wondered what kind of plugins it provided, so I asked APT to show me what it was. Here's what came up:

Package: libasound2-plugins
Priority: optional
Section: libs
Installed-Size: 488
Maintainer: Debian ALSA Maintainers
Architecture: amd64
Source: alsa-plugins
Version: 1.0.19-2
Depends: libasound2 (>> 1.0.18), libc6 (>= 2.2.5), libjack0 (>= 0.116.1), libpulse0 (>= 0.9.14), libsamplerate0
Filename: pool/main/a/alsa-plugins/libasound2-plugins_1.0.19-2_amd64.deb
Size: 119566
MD5sum: 89efb281a3695d8c0f0d3c153ff8041a
SHA1: fdd93b68ec0b8e6de0b67b3437b9f8c86c04b449
SHA256: 7eb5b023373db00ca1b65765720a99654a0b63be741a5f5db2516a8881048aa6
Description: ALSA library additional plugins
This package contains plugins for the ALSA library that are
not included in the main libasound2 package.
.
The following plugins are included, among other:
- a52: S16 to A52 stream converter
- jack: play or capture via JACK
- oss: run native ALSA apps on OSS drivers
- pulse: play or capture via Pulse Audio
- lavcrate, samplerate and speexrate: rate converters
- upmix and vdownmix: convert from/to 2 and 4/6 channel streams
.
ALSA is the Advanced Linux Sound Architecture.
Enhances: libasound2
Homepage: http://www.alsa-project.org/
Tag: devel::library, role::plugin, works-with::audio

Now something jumped out at me, run native ALSA apps on OSS drivers?
If you read my sound article, you know I'm an advocate of OSSv4, since it seems superior where it matters.

So I looked into the documentation for the Debian (as well as Ubuntu) package "libasound2-plugins" on how this ALSA over OSS works exactly.

I edited /etc/asound.conf, and changed it to the following:

pcm.!default {
type oss
device /dev/dsp
}

ctl.!default {
type oss
device /dev/mixer
}

And presto, every ALSA application now started properly outputting sound for me. No more need to always have to fiddle with configurations for each sound layer to use OSS, because the distros don't allow auto config of them.

I could never get flash on 64 bit with sound before, even though each new OSS release says they "fixed it". Now it does work for me.

I tested the following with ALSA:
MPlayer (-ao alsa)
Firefox, flashplugin-nonfree, Homestar Runner
ZSNES (-ad alsa)
bsnes (defaults)

Oh and in case you're wondering, mixing is working perfectly. I tried running four instances of MPlayer, two set to use ALSA, the other two set to output using OSS, and I was able to hear all four at once.

Now it's great to setup each application and sound layer individually to use OSS, so there's less overhead. But just making this one simple change means you don't have to for each application where the distro defaulted to ALSA, or have to suffer incompatibility when a particular application is ALSA only.

Note that depending how you installed OSS and which version, it may have tried forcing ALSA programs to use a buggy ALSA emulation library, which is incomplete, and not bug for bug compatible with the real ALSA. If that happened to you, here's how to use the real ALSA libraries, which are 100% ALSA compatible, as it's 100% the real ALSA.

First check where everything is pointing with the following command ls -la /usr/lib/libasound.*
I get the following:

-rw-r--r-- 1 root root 1858002 2009-03-04 11:09 /usr/lib/libasound.a
-rw-r--r-- 1 root root 840 2009-03-04 11:09 /usr/lib/libasound.la
lrwxrwxrwx 1 root root 18 2009-03-06 03:35 /usr/lib/libasound.so -> libasound.so.2.0.0
lrwxrwxrwx 1 root root 18 2009-03-06 03:35 /usr/lib/libasound.so.2 -> libasound.so.2.0.0
-rw-r--r-- 1 root root 935272 2009-03-04 11:09 /usr/lib/libasound.so.2.0.0

Now as you can see libasound.so and libasound.so.2 both point to libasound.so.2.0.0. The bad emulation is called libsalsa. So if instead of seeing "-> libasound..." you see "-> libsalsa..." there, you'll want to correct the links.

You can correct with the following commands as root:

cd /usr/lib/
rm libasound.so libasound.so.2
ln -s libasound.so.2.0.0 libasound.so
ln -s libasound.so.2.0.0 libasound.so.2

If you're using Ubuntu and don't know how to switch to root, try sudo su prior to the steps above.

If you'd like to try to configure as many applications as possible to use OSS directly to avoid any unneeded overhead, see the documentation here and here which provide a lot of useful information. However if you're happy with your current setup, the hassle to configure each additional application isn't needed as long as you setup ALSA to use OSS.

Enjoy your sound!

Ancient coding ideas finally in English - Part 2

2009-05-25T01:31:00.000-07:00

What is the best way to write it? Whatever is best for the program itself and best for the programmers.
Be just as careful with with minor code as with major code, as you don't know in the end which will be more important.
Consider what you lose when not writing the code properly against its gains, and consider the benefits of a poor implementation against what it loses.
Focus on three things and you will avoid code repetition: Know what other code exists, others will review your code, the code will exist for a long time.

It's best to write code for the customer's demands, they will overlook its negative qualities.
Code that's not written for those buying it will be for naught, and improving it will lead to code repetition.
Those writing for a community should write the code for its own sake, those that came before you will help you.
You will end up getting credit for the work that gets added on as if you yourself did it.

Be wary of standards bodies or other organizations, since they only recruit people for their own agenda.
They will act like they love you when it is to their advantage, but they will not stand by you when you need it.

Desire what the community wants, and the community will want what you desire.
Do what they want instead of what you want, and other programmers will desire what you desire.

Don't alienate the community.
Don't trust code till the code is about to be recycled.
Don't judge an implementation till you try to implement it yourself.
Don't do something that is unaccepted hoping it will eventually be accepted.
Don't plan to only write it properly later, maybe you won't.

An idiot doesn't care about code repetition.
One who is unlearned will never be a hero.
One who is embarrassed will never learn.
One who is always angry and demanding can't teach.
Those who solely focus on making money will never be more than an idiot.
Wherever there is no one else to write the code, you write it.

The master who invented the above statement once looked at a hack being recycled, and stated:
Since this hack replaced an older hack, it itself got replaced, and the hack replacing it will also be replaced.

One who increases code size increases bugs.
One who increases features increases worry.
One who increases threads increases overhead.
One who increases processes increases communication layers.
One who increases the amount of code they solely enjoy increases black magic in the code.
One who increases usefulness of the code increases its lifespan.
One who increases the amount of thought put into writing the code increases its intelligence.
One who increases his own agenda only does so for himself.
One who increases usefulness for the sake of the community will earn for himself everlasting gratitude.

If you write a lot of code, don't view yourself as so special, because it is for this reason you became a programmer.

The master who invented the above statement had five students.
The first was someone who never overlooked a detail.
The second always looked to the source of the issue.
The third was a hero.
The fourth always avoided code repetition.
The fifth was always increasing his own understanding and knowledge of techniques.

The master said of his first student, if we weighed him against everyone else out there, his abilities would outweigh them all.
Another master said, if the fifth student was weighed against the other four, his abilities would outweigh them all.

The master asked his students: What is the best trait for becoming a good programmer?
The first answered: One who carefully checks his code.
The second answered: One who has a good friend to bounce ideas off of.
The third answered: One who sees the needs of those around him.
The fourth answered: One who anticipates future needs.
The fifth answered: One who desires to write the best code he can.
The master stated, the fifth answered best, as his answer includes all the others.

The master then asked his students: What should a good programmer avoid?
The first answered: Ignoring what is going on in the code.
The second answered: Idiot friends.
The third answered: A weak community.
The fourth answered: Allocating resources without freeing them.
The fifth answered: Becoming complacent in his understanding of what is best.
The master stated, the fifth answered best, as one who becomes complacent will end up with what everyone else answered.

Stick up for your fellow programmers as you would for yourself.
Don't get angry easily.
Fix the code before the problem is apparent.
Enjoy the fire of clever code, but be careful lest you be burned by it.

Bad analyzing, no desire for good code, and hating your community will all cause one's code to be thrown away.

Managing resources you allocate should be as important to you as managing the resources you already have.
Perfect your programming abilities, as this is what a programmer is.
All your code should be written for its own sake.

Be meticulous in learning about what you need to accomplish, and the tools necessary to do so.
Don't make the theory of prime importance.
Don't underestimate yourself, and don't think your work will only be minor.

Have a good answer ready for those who may find issues with your code.
Understand your customer.
Understand your employer.

The day may be short, but there's a lot of work to be done.
Programmers are lazy, even though their programs do much.
The boss is demanding.

You don't have to do all the work by yourself, you don't have to finish every last bit of it.
You however can't leave the code in disarray.
If you write a lot of good code, you'll be properly compensated for it.
Believe that those who employ you will compensate you for your effort.
Know that those who put in the effort will be compensated greatly in years to come, even if not initially.

Ancient coding ideas finally in English - Part 1

2009-05-24T00:08:00.000-07:00

Each great programmer learned programming from the master before him.
Be precise in writing code.
Teach programming to others, as you'll understand how things work better yourself when you're forced to explain it.
Put safety in your code, don't just look at what minimally works, protect yourself from careless mistakes.

Good programs depend on 3 things:
The code.
The hardware.
The presentation.

Don't write a program to get bare minimum done, and be over with it.
Rather do it for the sake of the program itself, and try to get the most out of the program.

Your code should be welcome to other good programmers.
You should pay attention to minor details of their code.
Pay attention to their ideas.

Your code should be open for improvements.
Let even simple programmers review it for mistakes.
Be minimalistic on communication layers in your code.
[The previous] refers to communicating with your own code, this applies even more so when your code has to communicate across a network or other external dependencies.
Excessive external dependencies or communication across a network only hurts your program, and worsens code quality, and you'll end up with an unmanageable program.

Declare over yourself a coding standard.
Buy yourself friends to bounce ideas off of.
Accept every new idea for consideration, no matter how ridiculous it might seem at first glance.

Stay away from bad libraries.
Don't statically link to them.
Don't give up when it's a disaster out there.

Don't make yourself a sole reviewer of large amounts of code.
When presented with two implementations, assume both of them are complete garbage until convinced otherwise.
When having to decide between two implementations you are presented with, examine the pros and cons of the situation, and what improvements can be done, and be happy when proponents of each were able to walk away being able to accept the pros and cons and reach the best implementation.

Review code in depth, and have ever changing methods to do so, otherwise a severe bug can slip by you.

Love writing code.
Hate bureaucracy.
Don't give in to status quo.

Be careful in what you to say to others, or you may create a rift in your community, the outcome of the current work will fail, and your program will be for naught.

Love peace and run after it.
Love the other programmers, and show them how to write better code.
One who only seeks to advance his own self will end up destroying himself.
One who doesn't learn what's new will end up not being able to write code with what he currently knows.
One who doesn't learn at all shouldn't be writing code.
One who doesn't use libraries the way they're supposed to be used will be lost in the end.

If you don't write the code, who is going to write it for you?
If you're always writing all the libraries yourself, what's the point?
If you don't write it today, then when exactly?

Take programming seriously.
Optimize the little bits which do the most.
Welcome all patches with a smile (even if you don't commit them all).

Make for yourself a system, and stay away from assumptions, learn about it if you're not sure.
Don't write a program based on rough estimates.

I've spent a lot of time with those who know only theory. Don't argue with them, just pay attention.
The theory isn't the main thing, but the practical. If you dwell on the theory, you'll end up being repetitious with your code.

On three things a good program depends on:
Meeting Requirements.
Correctness.
Peace with the community.

Will Linux ever be mainstream?

2009-05-12T19:45:00.000-07:00

Constantly different sites and communities always discuss the possibility of Linux becoming mainstream and when the mainstreaming will take place. Often reasons are laid out where Linux is lacking. Most reasons don't seem to be in touch with reality. This will be an attempt to go over some of those reasons, cut out the fluff from the fact, and perhaps touch on a few areas that have not been gone over yet.

One could argue with today's routers that Linux is already mainstream, but let us focus more on full blown computer Linux, which runs on servers, workstation, and home computers.

When it comes to servers, the question really is who isn't running Linux? Practically every medium sized or larger company runs Linux on a couple of their servers. What makes Linux so compelling that many companies have at least one if not many Linux servers?

Servers are a very different breed of computer than the workstation or home computer. "Desktop Linux" as it's known is the type of OS for average everyday Joe. Joe is the kind of guy who wants to sit down and do a few specific tasks. He expects those tasks to be easy to do, and be mostly the same on every computer. He doesn't expect anything about the 'tasks' to scare him. He accepts the program may crash or go haywire in the middle, at which time it's just new cup of coffee time. Except Desktop Linux isn't for every day Joe ... yet.

Servers on the other hand are designed primarily for functionality. They have to have maximum up time. It doesn't matter if the server is hard to understand, and work with, and only two guys in the whole office can make heads or tails out of it. It's okay that the company needs to hire two guys with PhDs, who are complete recluses, and never attend a single office party.

Windows servers are primarily used by those that need special Windows functionality at the office, such as ActiveDirectory, or Exchange so everyone has integrated Outlook. Some even use Windows as HTTP Servers and the like. Windows is less known for working, but being great for those specialized tasks, or servers which don't need those two PhD recluses to manage. Even guys who have never written a piece of code in their entire life can manage a Windows server - usually. Microsoft always tries to press this latter point home with all their get the facts campaigns.

The real fact is though that companies on their servers need functionality, reliability, and countability. While larger companies would prefer to replace every man with a machine which is guaranteed to last forever and not require a single ounce of maintenance, they would rather rely on personnel than hardware. Sure, when I'm a really small business, I'd rather have a server I can manage myself and have a clue what I'm doing, but if I had the money, I'd rather have expert geeky Greg who I can count on to keep our hardware setup afloat. Even when geeky Greg is a bit more expensive than laid-back Larry, I'm happier knowing that I have the best people on the job.

Windows servers while being great in their niches, are also a pain in the neck in more generalized applications. We have a Windows HTTP/FTP server at work. One day it downloads security patches from Microsoft, and suddenly HTTP/FTP stop working entirely. Our expert laid-back Larry spent a few hours looking at the machine trying to find out what changed, and mostly had to resort to using Google as opposed to any knowledge of how Windows works. Finally he sees on some site that Microsoft changed some firewall settings to be extra restrictive, and managed to fix the problem.

Another time, part of the server got hacked into, and we have to reinstall most of it. For some reason, a subsection of our site just refused to work, apparently a permission problem somewhere. On Linux/Apache, permission problems are either a setting in Apache or on the file system, easy to find. Windows on the other hand, with their oh-so-much-better fine grained permission support seem to have dozens if not hundreds of places where to look for security settings. This took our Larry close to two weeks to fix.

Yet another time, a server application which we wrote in-house ran flawlessly on both Linux and Windows XP. However, when we installed it on our Windows Server 2003 server, it inexplicably didn't work. It's no wonder companies use Linux servers for many server tasks. There's also a decent amount of server applications a company can purchase from Red Hat, IBM, Oracle, and a couple of other companies. Linux on the server clearly rocks, even various statistical sites agree.

Now let us move on to the workstation and home computer segment, where we'll see a very different picture.

On the workstation, two features are key, manageability, and usability. Companies like to make sure that they can install new programs across the board, that they can easily update across the board, and change settings on every single machine in the office from one location. Granted on Linux one can log in as root to any machine and do what they want, but how many applications are there that allow me to automate management remotely? For example, apt-get (and its derivatives) are known as one of the best package managers for Desktop Linux, yet they don't have any way to send a call to update to every single machine on a network. Sure using NFS I can have an ActiveDirectory like setup where any user can log into any machine and get their settings and files, but how exactly do I push changes to the software on the machines themselves? Every place I asked this question to seems to have their own customized setup.

One place SSHs into every single machine individually, and then paste some huge command into the terminal. Another upgrades one machine, mirrors the hard drive, then goes to each machine in turn and re-images the installed hard disk. One place which employs a decent number of programmers wrote a series of scripts which every night download a file from a server and execute it. Another, also with an excellent programming task force, wrote their own SSH based application which logs into every machine on the network and runs whichever commands the admin puts in on all of them, allowing real time pushing of updates to all the machines at once.

Is it any wonder that a large company is scared to have Linux on all their machines or that it really is expensive to maintain? We keep toting/hearing how amazing X is because of the client/server setup, or these days in regards to PulseAudio, let us start hearing it for massive remote management. And remember not to limit this just to installing packages, we need to be able to change system files remotely and simultaneously, with a method which becomes standard.

The other aspect if of course usability, and by usability I mean being able to use the kind of software the company needs. Now for some companies, documents, spreadsheets, and web browsers are the extent of the applications they need, and for that we're already there. Unless of course they also need 100% compatibility with the office suites used by other companies.

What about specialized niches though? That's where real companies have their major work done. These companies are using software to manage medical history, other clientèle meta-data, stocks (both monetary and in-store), and multitudes of other specialized fields. All these applications more or less connect to some server somewhere and do database manipulation. We're really talking about webapps in desktop form. Why is every last one of these 3rd party applications only written for Windows?

The reasons are probably threefold. If these applications worked in any standard browser, we're really providing more functionality in them than should be exposed to the user. Do you want the user to hit stop or the close button in the corner of their browser in middle of a transaction? Sure, the database should be robust and atomic enough to handle these kinds of situations, but do we want to spoon-feed these situations to the users? We also certainly don't want general system upgrades which would install a newer version of the browser to break one of the key applications being used by the company. To solve this problem requires a custom browser, bringing us back to square one when it comes to making this a desktop application.

The next reason is known as catch-22. Why should a generic company making an application bother with anything than the most popular OS by a landslide? We need way more Desktop Linux users for a company to bother, but if the companies don't bother, it's unlikely that Desktop users will switch to Linux. Also, as I've said before, portability isn't difficult in most cases, but most won't bother unless we enlighten them.

Lastly, many of these applications are old, or at least most of their code base is. There's just no incentive to rewrite them. And when one of these applications is made in-house, it'll be made for what the rest of the company is already running.

To get Linux onto the workstation then, we need the following to take place:

Creation of standardized massive management tools
Near perfect interoperability of office suites
Get ports of Linux office suites to be mainstream on Windows too
Get work oriented applications on Windows to be written portably
Make Linux more popular on the Desktop in all aspects

We have to stop being scared of Open Source on closed sourced Operating Systems, if half the offices out there used Open Office on Windows, they wouldn't mind running Open Office on Linux, and they won't have any different interoperability issues that they don't already have.

We also need to make portability excellence more the norm. These companies could benefit a lot from using Qt for example. Qt has great SQL support. Qt contains a web browser so webapps can be made without providing anything unnecessary in the interface. Qt also has great easy to use client/server support, with SSL to boot. Also, Qt applications are probably the easiest type to make multilingual, and the language can be changed on the fly, which is very important for apps used world wide, or for companies looking to save money by hiring immigrants. Lastly, Qt is easier to use than the Win32 API for these relatively basic applications. If they used 100% Qt, the majority of the time, the program would work on Linux with just a simple recompile.

For the above to happen we really need a major Qt push in the developer community. The fight between GTK, wxWidgets, and Qt is going to be hurting us here. Sure, initially Qt was a lot more closed, and we needed GTK to push Qt in the right direction. But today, Qt is LGPL, offers support/maintenance contracts, and is a good 5-10 years ahead of GTK in breadth of features supplied. Even if you like GTK better for whatever reason, it really can't stand up objectively to Qt from the big business perspective. We need developers to get behind our best development libraries. We also need to get schools to teach the libraries we use as part of the mainstream curriculum. Fracturing the community on this point is only going to hurt us in the long run.

Lastly, we come to Linux on the home computer. What do we need on a home computer exactly? They're used for personal finances, homework, surfing the web, multimedia, creativity, and most importantly, gaming.

Are the finance applications available for Linux good enough? I really have no idea, perhaps someone can enlighten me in the comments. We'll get back to this point shortly.

For homework, I'd say Linux was there already. We have Google and Wikipedia available via the world wide web. Dictionaries and Thesauruses are available too. We got calculators and documents, nothing is really missing.

For surfing the web we're definitely there, no questions asked.

Multimedia we're also there aside from a few annoyances. I'll discuss this more below.

For creativity, I'm not sure where we are. Several years back, it seems all the kids used to love making greeting cards, posters, and the like using programs such as The Print Shop Deluxe or Print Artist. Do we have any decent equivalents on Linux?

Thing is, a company would have to be completely insane to port popular home publishing software to Linux. First there's all the reasons mentioned above regarding catch-22 and the like. Then there's nutjobs like Richard Stallman out there who will crucify the company attempting to port their software to Linux. For starters, see this article which says:

Some of the most important projects on our list are replacement projects. These projects are important because they address areas where users are continually being seduced into using non-free software by the lack of an adequate free replacement.

Notice how they're trying to crush Skype for example. Basically any time a company will port their application to Linux, and it becomes popular enough on Desktop Linux, you'll have these nutjobs calling for the destruction of said program by completely reimplementing it and giving it away for free. And reimplement it they do, even if not as effectively, but adequate enough to dissuade anyone from ever buying the application. Then the free application gets ported to Windows too, effectively destroying the company's business model and generally the company itself. Don't believe they'll take it that far? Look how far they went to stop Qt/KDE. Remember all those old office suites and related applications available for Linux a decade ago? How many of them are still around or in business? When free versions of voice chatting are available on all platforms, and can even interface with standard telephones, do you think Skype will still be around?

Basically, trying to port a popular application to Linux is a great way to get yourself a death sentence. If for example Adobe ever ported Photoshop to Linux, there'd be such a massive upsurge in getting the GIMP or a clone to have a sane interface, and get in some of those last features, Photoshop would probably be dead in a year.

And unless some of these applications are ported to Linux, we'll probably never see niche applications as good as their Windows counterparts. Many programmers just don't care enough to develop these to the extent needed, and some only do so when they feel it's part of a holy war. Thus giving us a whole new dimension to the catch-22.

Finally, we come to gaming. Is Linux good enough for companies to develop for? First glance, and you think a resounding yes. A deeper look reveals otherwise. First off, there's good ol` video. For the big games today, it's all about graphics. How many video cards provide full modern OpenGL support on Linux? The problem is basically as follows. X Windows a system designed way back when with all sorts of cool ideas in mind, where the current driver API is simply not enough to take full advantage of accelerated OpenGL. You can easily search online and find tons of results on why X is really bad, but it really stands out when it comes to video.

NVidia has for several years now put out "evil drivers" which get the job done, and provide fantastic OpenGL support on top of Linux. The drivers though are viewed as evil, since they bypass the bottom 1/3 of X and talk straight to the Kernel, and don't fully follow the X driver API. And of course, they're also closed source. All the other drivers today for the most part communicate with the system via the X API, especially the open sourced drivers. Yet they'll never measure up, because X prevents them from measuring up. But they'll continue to stick to what little X does provide. NVidia keeps citing they can't open source their drivers because they'll lose their competitive advantage. Many have questioned this, as for the most part, the basic principals are the same on all cards, what is so secret in their drivers? When in reality, if they open sourced their drivers, the core functionality would probably be merged into X as a new driver API, allowing ATI and Intel to compete on equal footing, losing their competitive advantage. It's not the card per sè they're trying to hide, but the actual driver API that would allow all cards to take advantage of themselves, bypassing any stupidity in X. At the very least, ATI or Intel could grab a lot of that code and make it easier for themselves to make an X-free driver that works for X well.

When it comes down to it, as tiny as the market share is that Linux already has, it becomes even smaller if you want to release an application that needs good video support. On the other hand, those same video cards work just fine in Windows.

Next comes sound, which I have discussed before. The main sound issue for games is latency, and ALSA (the default in Linux) is really bad in that regard. This gets compounded when sound has to run through a sound server on its way to the drivers that talk to the sound card. For playing music, ALSA seems just fine to everybody, you don't notice or care that the sound starts or stops a moment or two after you press the button. For videos as well, it's generally a non-issue. In most video formats, the video takes longer to decode than it does to process sound, so they're ready at the same time. It also doesn't have to be synced for input. So everything seems fine. In the worst case scenario, you just tell your video player to alter the video/audio sync slightly, and everything is great.

When it comes to games, it's an entirely different ballpark. For the game not to appear laggy, the video has to be synced to the input. You want the gun to fire immediately after the user presses the button, without a lag. Once the bullet hits the enemy and the user sees the enemy explode, you want them to hear that enemy explode. The audio has to be synched to the video. Players will not accept having the sound a second or two late. Now means now. There's no room for all the extra overhead that is currently required.

I find it mind boggling that Ubuntu, a distribution designed for average Joe, decided to make the entire system routed through PulseAudio, and see it as a good thing. The main advantage of PulseAudio is that it has a client/server architecture so that sound generated on one machine can be output on another. How many home users know of this feature, let alone have a reason to use it? The whole system makes sound lag like crazy.

I once wrote a game with a few other developers which uses SDL or libao to output sound. Users way back when used to enjoy it. Nowadays with ALSA, and especially with PulseAudio which SDL and libao default to outputting to in Ubuntu, users keep complaining that the sound lags two or more seconds behind the video. It's amazing this somehow became the default system setup.

Next is input. This one is easy right? Linux surely supports input. Now let me ask you this, how many KDE or GNOME games have you seen that allow you to control them via a Joystick/Gamepad? The answer is quite simply, none of them do. Neither Qt nor GTK provide any input support other than keyboard or mouse. That's right, our premier application framework libraries don't even support one of the most popular inventions of the 80s and 90s for PC gamers.

Basically, here you'll be making a game and using your library to handle both keyboard and mouse support, when you want to add on joystick support, you'll have to switch to a different library, and possibly somehow merge a completely different event loop into the main one your program uses for everything else. Isn't it so much easier on Windows where they provide a unified input API which is part of the rest of the API you're already using?

Modern games tend to include a lot of sound, and more often than not, video as well. It'd be nice to be able to use standard formats for these, right? The various APIs out there, especially Phonon (part of Qt/KDE) is great at playing sound or video for you. But which formats should you be putting your media in? Which formats are you ensured will be available on the system you're deploying on? Basically all these libraries have multiple backends where support can be drastically different, and the most popular formats, such as those based on MPEG standards don't come standard on most Linux distributions, thanks to them being "non free". Next you'll think fine, let us just ship the game with uncompressed media. This actually works fine for audio, but is a mess when it comes to video. Try making a pure uncompressed AVI and running it in Xine, MPlayer, and anything else that can be used as a Phonon back end. No two video players can agree on what the uncompressed AVI format is. Some display the picture upside down, some have different visions of which byte signifies red, blue, and green, and so on.

For all of these reasons, the game market, currently the largest in home software, has difficultly designing and properly deploying games on Linux. The only companies which have managed to do it in the past are those that made major games for DOS back in the day, where there also was no good APIs or solutions for doing anything.

Now that we wrapped it all up from the actual applications side of things, let us have a look at actual usability for the home user.

We're taken back to average Joe who wants to setup his machine. He's not sure what to do. But he hears there are great Ubuntu forums where he can ask for help. He goes and asks, and gets a response similar to the following:

Open a terminal, then type:
sudo /etc/init.d/d restart
ln -s /alt/override /bin/appstart
cd /etc/app
sudo nano b.conf

Preload=yes
ctrl+x
yes

Does anyone realize how intimidating this is? Even if average Joe was really Windows Power User Joe, does he really feel safe entering commands with which he is unfamiliar?

In the Windows world, we'd tell such a user to open up Windows Explorer, navigate to certain directories, copy files, edit files with notepad and the like. Is it really so hard to tell a user to open up Nautilus or Dolphin or whatever their file manager is, and navigate to a certain location and edit a file with gedit/kwrite?

Sure, it is faster to paste a few quick commands into the terminal, but we're turning away potential users. The home user should never be told he has to open a terminal. In 98% of the cases he really doesn't and what he wants/needs can be done via the GUI. Let us start helping these users appropriately.

Next is the myth about compiling. I saw an article written recently that Linux sucks because users have to compile their own software. I haven't compiled any software on Linux in years, except for those applications that I work on myself. Who in the world is still perpetuating this myth?

It's actually sad to see some distributions out there that force users to recompile stuff. No I'm not talking about Gentoo, but Red Hat actually. We have a server running Red Hat at work, we needed mod_rewrite added to it the other day. Guess what? We had to recompile the server to add that module. On Debian based distros one just runs "a2enmod rewrite", and presto the module is installed. Why the heck are distros forcing these archaic design principals on us?

Then there's just the overall confusion, which many others point out. Do I use KDE or GNOME? Pidgin or Kopete? Firefox or Konqueror? X-Chat or Konversation? VLC or MPlayer? RPM or DEB? The question is, is this a problem? So what if we have a lot of choices.

The issue arises when the choice breaks down the field. When deploying applications this can get especially nightmarish. We need to really focus more on providing just the best solution, and improving the best solution if it's lacking in an area, as opposed to having multiple versions of everything. OSS vs. ALSA, RPM vs. DEB, and a bunch of others which are base to the system shouldn't really be around these days.

The other end of the spectrum is less important to providing a coherent system for deploying on. But it does confuse some users. When I want to help someone, do I just assume they use Krusader as a file manager? Should I try to be generic about file managers? Should I have them install Krusader so I can help them? This theme is played over in many variations on most Linux help forums.
"Oh yes, go open that in gedit."
"Gedit? What's Gedit?"
"Are you running KDE or GNOME?"
"GNOME"
"Are you sure?"
"Wait, are GNOME and XFCE the same thing?"

What's really bad though is when users understand there's multiple applications, but can't find one to satisfy them. It's easy when the choices are simple or advanced, you choose the one more suited to your tastes for that kind of application. But it gets really annoying when one of those apps tries to be like the other. Do we need two apps that behave exactly the same but are different? If you started different, and you each have your own communities, then stay different. We don't need variety when there is no real difference. KDE 4 trying to be more like GNOME is just retarded. Trying to steal GNOME's user base by making a design which appeals more to GNOME users but has a couple of flashy features isn't a way to grow your user base, it's just a way to swap one for another.

Nintendo in the past couple of years was faced with losing much of their user base to Sony. For example, back in the late 90s, all the cool RPGs for which Nintendo was known, had all sequels moved to Sony hardware. However, instead of trying to win back old gamers, they took an entirely different approach. Nintendo realized the largest market of gamers weren't those on the other systems, but those that weren't on any systems. The largest market available for targeting is generally those users not yet in the market, unless the market in question is already ubiquitous.

That said, redesigning an existing program to target those who are currently non-users can sometimes have the potential to alienate loyal users, depending on what sort of changes are necessary, so unless pulling in all the non-users is guaranteed, one should be careful with this strategy. Although a user base with non paying customers is more likely to have success with such a drastic change, as they aren't dependent on their users either way. Balance is required, so many new users are acquired while a minimal amount of existing users are alienated.

To get Linux on home computers the following needs to take place:

We need to stop fighting every company that ports a decent product to Linux
We should write good programs even if there is nothing else to compete with on Linux
We shouldn't leave programs as adequate
We need a real solution to the X fiasco
We need a real solution to the sound mixing/latency fiasco, and clunky APIs and more sound servers isn't it
We need to offer tools to the gaming market and try to capture it
Support has to be geared towards the users, not the developers
Stop the myths, and prevent new users installing distros that perpetuate them
Stop competition between almost identical programs
Let programs that are similar but very different go their own ways
Bring in users that don't use anything else
Keep as many old users as possible and not alienate them

Linux being so versatile is great, and hopefully it will break into new markets. As I said before, many routers use Linux. To be popular on the desktop though, it either has to get users to desktops that currently don't have any, or manage to steal users from other desktops while keeping the ones they have. Becoming Windows isn't the answer, as others like to point out, but competing toe to toe in all existing areas while obtaining new ones is. In some areas, we may just have to throw away existing users to an extent (possibly eliminate X), if we want to grab everyone else out there.

Speaking of versatility, has everyone seen this? Linux grown technology does in many ways have the potential to beat Windows and the rest in a large way.

Everyone remember Duke Nukem Forever? Supposedly the best game ever, since it has unprecedented levels of world operability within the game? Such as being able to go to a soda machine, put in some money, press buttons, and buy a drink. With Qt, we can provide a game with panels throughout it where a user can control many things within the game, and there'd be a rich set of controls developers can easily add. Imagine playing a game where you go checkout the enemy's computer system, the system seeming pretty normal, you can bring up videos of plans they plan on. Or notice a desktop with a web browser, where you yourself can go ahead and login and check your E-Mail within the game itself, providing a more real experience. Or the real clincher. You know those games where plot-wise you break into the enemy factory and reprogram the robots or missiles or whatever? With Qt, the "code" you're reprogramming can be actual JavaScript code used in game. If made simple enough, it can seem realistic, and really give a lot of flexibility to those that want to reprogram the enemy's design. We have the potential to provide unprecedented levels of gameplay in games. If only we could get companies to put out games using Qt+OpenGL+Phonon, which they will probably not even consider looking at until Qt has Joystick support. Even then we still need to promote Qt more, which will make it easier to get companies to port games to Linux...

I think Ubuntu has some good ideas for adopting home users, but could be improved upon in many ways. Ultimately, we need a lot of change in the area of marketing to home users. There's so much that needs to be fixed and in some areas, we're not even close.

Feel free to post your comments, arguments, and disagreements.

What the heck is a PC?

2009-05-12T12:45:00.001-07:00

So the other day a friend of mine comes over to discuss some business strategy. After chatting for a bit, he asks me if he could use one of my computers to check his E-Mail. Happily obliging, I log into one of my x86-64 machines running Linux/KDE, open up Firefox for him, and tell him to go check.

So my friend sits down, grabs for the mouse and keyboard, and starts looking at the screen with a weird expression on his face. After a couple of seconds, he clicks on the address bar, looks around a bit more, then he motions to me that he could use some help.

I asked him if he used a particular web based e-mail service, he answered in the affirmative that he uses G-Mail. So I typed in the address to G-Mail for him, which brought up the login page asking for his username and password.

He again looks at the screen, types in his username, then pauses again. He turns to me and tells me he feels really uncomfortable using this system, do I have a PC available that he can use?

This question made me completely flabbergasted. My friend is technically oriented, he's been using computers for a decade, he knows various operating systems exist, he knows various web browsers exist. He uses Firefox both at home and work. He even does some VBA scripting in his Excel spreadsheets. What in the world is scaring him about Firefox in Linux/KDE?

As the story continues, I turn to my friend and tell him this is a PC. He looks back at the screen, looks a bit startled, then seems to think for a few moments. Finally he turns to me and says, you know, Windows? So I reboot the machine into Windows XP (all my computers are minimally dual boot), and open up Firefox for him. He sits down happily and checks his E-Mail.

This experience left me thinking though. What the heck is a PC? It seems some people today have got it in their skulls that PC is a connotation for Windows. PC-DOS, PC-BSD, and other OSs must appear oxymoronish to these people if they ever saw them.

Thinking about it, I always for years viewed a PC as something IBM put together, most importantly containing an x86 processor. The basic machine changed over the years, but it was always x86. But then Apple released computers on x86 chips too recently, and they vehemently deny that they use PC hardware. Their basic difference being they don't use any classic PC BIOS.

Should we now take the term PC to mean x86+BIOS? Thinking more about it, a PC should probably be defined as a computer capable of running MS/PC DOS. Maybe even Apple decided to use their whole EFI setup just so they can classify their computers as not PCs. And thanks to dumb marketing, people are now thinking PC means running Windows.

So, do you know anyone who is scared of the same browser on a different OS? What do you think of when you hear "PC"? Has the PC definition changed? Should it change?

GPLv3 - Is it right for your family?

2008-12-17T20:33:00.000-08:00

The GPLv3 came out a while ago, with a changed outlook from v2, which upset many people, with some choosing to relabel their software from being GPLv2 or higher to GPLv2 only.

While discussing some changes with someone the other day, I looked over this section again:

A compilation of a covered work with other separate and independent
works, which are not by their nature extensions of the covered work,
and which are not combined with it such as to form a larger program,
in or on a volume of a storage or distribution medium, is called an
"aggregate" if the compilation and its resulting copyright are not
used to limit the access or legal rights of the compilation's users
beyond what the individual works permit. Inclusion of a covered work
in an aggregate does not cause this License to apply to the other
parts of the aggregate.

From what I gather, the intent of this paragraph was to define how the GPL affects hardware manufactures that embed GPL software on their products. They wanted to allow companies to ship various software together, as long as the user of the product doesn't have any legal restrictions applied to them. For example: By opening this package you forgo your rights to ever resell the contents within. Or: You agree to not use this product in order to reverse engineer it. Or the real clincher: By opening the packaging or using this product you agree to not attempt to modify it.

Basically this is done to explicitly state the GPLs new intent:

Some devices are designed to deny users access to install or run
modified versions of the software inside them, although the manufacturer
can do so. This is fundamentally incompatible with the aim of
protecting users' freedom to change the software. The systematic
pattern of such abuse occurs in the area of products for individuals to
use, which is precisely where it is most unacceptable. Therefore, we
have designed this version of the GPL to prohibit the practice for those
products. If such problems arise substantially in other domains, we
stand ready to extend this provision to those domains in future versions
of the GPL, as needed to protect the freedom of users.

Now under the GPLv3, one is unable to sell hardware with GPLv3 on it to someone which somehow limits their legal rights they had prior to owning hardware.

Now what exactly defines legal rights? One's legal rights change from location to location. One has legal rights and restrictions based on the country they live in. They also have legal restrictions added on to those by the state they live in. One who owns a domain may also limit the rights of those who wish to stay within their domain. When one lives in a domain, and violates a law of that particular domain, they may be punished by the rules of that domain, as long as the punishment isn't in conflict with the rights and restrictions provided by the domain that particular domain is contained within.

Meaning, I can establish rights and regulations within my own household that are binding to members within it, as long as it isn't in conflict with the state I live in. The state can do the same as long as it doesn't violate the laws of the country it is in.

Although not normally thought of in that sense, my home does have legal rights, restrictions, and regulations that I apply to my household. I don't allow coloring on the walls. If one does so, they know that their crayons will be taken away, and they will lose allowance for the next two weeks or perhaps certain video game privileges, depending on the age of the perpetrator.

Now in the past, if I wanted one of my children to have a computer, I'd buy/build/whatever a computer, and install all the necessary software I think they need, as well as any other software that they desire that I don't deem as contraband.

However with the GPLv3, if I compile together components for a computer, as well as various software into a nice personal computer, if any of the software is GPLv3, I can't restrict any other previous legal rights to the user of this personal computer.

Buying children expensive gifts have always been a form of negotiation and a method to apply new restrictions on troublesome issues that have recently come up. For example, if my daughter recently decided she wanted earings, but her mother and I decided we don't want her to get her ears pierced right now, we'd try to negotiate the restriction. If we knew she also wanted a nice new laptop, we'd perhaps buy her the laptop, but make a deal with her, that if she uses this nice new pink Eee PC, she no longer asks her mother and I if she can have earings until she is 16. This way she can be content about having a new computer, and wont bring up her desire for earings for a few more years.

However, if we got her an Eee PC with Linux installed with several GPLv3 apps, as opposed to the Windows preinstalled Eee PC, we would not be allowed to under the terms of the GPLv3 negotiate this agreement with our daughter.

It seems because of the GPLv3, I can't give my children anything but Windows on the computers I buy for them, if I try to use them as a bargaining chip. Before you Mac lovers pounce on me, please recall that MacBooks today come with GCC, which is GPLv3.

Thanks to the GPLv3, it seems now Windows is the only Operating System that is right for your family. Remember also to be careful which open source applications you preload with, to make sure they aren't GPLv3.

Binary Trees - Does it matter?

2008-09-09T08:14:00.000-07:00

Ever programmed a Binary Tree before? If you took computer science classes past an introductory level, you probably studied the theory before. But to what extent do decisions matter?

To review for those of you who don't quite recall what a binary tree is. You have a series of nodes, each node contains data, some or all of which is the key, up to two pointers to children nodes, and possibly other meta data. The most popular type of binary tree is the Binary Search Tree, where each node conceptually has nodes with lesser keys descending on the left, and nodes with greater keys descending on the right.

How to implement a left and right can be done with two node pointers called left and right, lesser and greater, an array of two node pointers, or any other method which makes sense to you.

All operations begin with the topmost node in the figure above, known as the root, head, or top node of the tree. To find a node with a particular key, one compares it against the current node, if it found it good, otherwise, if it's less, take the left route, otherwise the right. If there is no path left or right as requested, since there is only a null pointer there, then a node with a matching key is not in the tree. At each node reached, the same algorithm is applied. In this instance, a Binary Tree is very similar to Binary Search, each check effectively cuts the data in half, leading to very efficient searches.

Adding data to a tree is very much the same. The data is encapsulated in a node, which again goes down the tree finding where the data should belong, in this case, once a null pointer is encountered while trying to traverse the tree further, it is replaced by a pointer to the new node.

Deleting data can be a bit trickier. If a node has no children, deleting a node is quite straight forward. If the node only has a path left or right, one simply cuts out the node being deleted, and makes the pointer once pointing to it now point to the child. However, for removing a node which has two children descending from it, there's a number of methods that can be applied.

The simplest method is to make one child a replacement, and add the other child onto the child replacing, meaning add the left node to the right or the right to the left.

Look what happens when deleting the root node, which in this case has two children.

The node with a key of 50 is deleted which had two children, 25 and 100. Either 25 becomes the new root, with 100 as the rightmost of 25's descendants, or 100 becomes the new root, with 25 as the leftmost of 100's descendants.

The only problem with this algorithm is that it can quickly make the tree become unbalanced, degrading into a linked list. A tree should be as close to balanced as possible, so search or addition can be done with cutting half the tree out per each node looked at. An unbalanced tree would make each operation generally consist of looking at most of the nodes in the tree, which is inefficient.

Therefore, the generally proposed algorithm is to find the next or previous node by key, and move it to replace the node being deleted. First lest us understand tree order.

A binary tree can be processed in direct order using the following algorithm.


function process_node(Node *node)
{
  if (node->has_left()) { process_node(node->left()); }
  process_node_data(node->data());
  if (node->has_right()) { process_node(node->right()); }
}

Which is plain English means handle left, then current, then right, in a recursive fashion. Because a Binary Tree can be processed in this fashion, in addition to being a nice data structure, it can also be used as the basis of a sorting algorithm. All data is encapsulated in a node and is added to the tree, then it is traversed in order as just described, placing the data back into the original data structure, and then the tree is destroyed.

Now understanding this, the node prior to any particular node in regards to its key is always one left, and then rightmost, and the node after a particular key is one right, and then left most.

And the delete:

50 is deleted, and the previous or next one takes its place. In this case, 35 being the previous, and 75 being the next one.

Now to get to the meat of the article, does it matter? Does what matter?

First off, we didn't at all mention how to handle nodes which have equivalent keys. Back when I was in college learning computer science, we were told to just throw it down the right or the left, but be consistent about it. Also, when it comes to deleting, take the previous or the next, but again, it doesn't matter, as long as one was consistent about it. Or perhaps in this latter case, alternate sides per delete.

But the question we must ask is: "Does it matter?"

And the answer which they at the very least didn't teach me when I was in school, yes, it does matter!

When one sorts, one can do a stable or an unstable sort. Stable means that if two elements had equivalent keys, when sorting, the order of those nodes would be preserved. Meaning if we had: "50 C, 45 A, 23 C, 50 B, 75 D, 50 A", and the numbers would make up the key, but not the letters, then it would sort to: "23 C, 45 A, 50 C, 50 B, 50 A, 75 D", keeping the order of C,B,A among the elements with a key of 50. Unstable would mean that the relative order of those 50s is not guaranteed to be kept when sorting.

A binary tree can only be used as a stable sort if equal data is always placed on the right side. This is because the order of succession is left, current, right, and if it was placed on the left, it would mean the node added later came before the current node.

What not to do:

However, just putting equal data on the right isn't the end of the matter yet. Most good Binary Trees, such as a Red & Black Tree will implement some kind of self balancing system, so areas which are starting to become linked lists rotate to become balanced trees.

Looks like a linked list:

As can be seen in the diagrams, the middle node of the three becomes the new parent of the section with the first node becoming the left. This still follows the in order rules of left, center, right, because the one of the left is indeed the first node. And rotations like this, would also preserve numbering orders of the keys (otherwise a Red & Black Tree or another self balancing tree would never employ them).

Now adding another 50 on our proposed case still works with our initially stated algorithm, we traverse down till we reach our area of 50s, then place it to the right of the right most one. However, we have to slightly rewrite our find a node which matches a key algorithm. If we want our tree to always return the first node which matches a key, or in the case of deletion, delete the first node which matches a key, one can't just search until one finds a matching node, since it in fact may be the second or third node if rotations took place. Rather, one has check to see if the left contains the same value, and if so, go left most across matching keys, and return the deepest one found there.

Now after reviewing these revised rules, is your binary tree written properly? Furthermore, have you ever even seen an implementation which when searching checks left most for matching keys?

Oh, and before we leave, what about deleting, does it matter if the prior or the next node is chosen? The other night, a student of mine asked me that, and presented to me a case which we both agreed proved that to properly delete and keep a stable sort, one has to use the next node, and not the prior one to properly preserve the key order. Although, we were both tired at the time, and now when trying to recreate the case I can't seem to do it. So I do hope I was in error the other night, and am not leaving out a crucial point. If you happen to know of a case where it matters, please describe it in the comments.

Mozilla is the new Microsoft

2008-01-29T21:53:00.000-08:00

So who here loves Mozilla and their browsers such as Firefox?

I do too, but am I the only one finding Mozilla turning more into Microsoft every day?

To start off, lets point fingers at the memory issue. Notice how Windows' memory requirements have gone through the roof? Yet comparable desktop environments and windowing systems from other sources seem to be just as advanced as Microsoft's latest offering and don't use a fraction of the RAM. I'm told KDE 4 runs comfortably with only 512MB of RAM, and you can even get away with 256MB, while a friend of mine running Vista started with 1.5GB but said he had to add another 512MB so the system didn't get all slugish on him. Does Vista offer anything special that KDE 4 doesn't?

Compare that to Firefox these days. I open up Firefox with two tabs, one in a pretty ordinary text page with a single image on it, and another with some tables and a form, and it uses over 400MB of RAM. When mentioning it to Mozilla, they of course tell you it's a feature not a bug (sound familiar?). What feature exactly needs all that RAM? I'm told some nonsense about how it caches previous pages one went to, so they load quickly when you press back. Considering I just opened the browser, which pages is it caching exactly?

To further compound my bafflement of the issue, I even disabled that feature in about:config, and yet Firefox still eats a ton of RAM when I open it. I used to run Netscape Navigator on a machine with 16MB of RAM, and two whole browser windows opened, and it didn't eat a fraction of the RAM Firefox does now (and this was before Windows had virtual memory). Heck, even other web browsers such as Konqueror and Opera don't use that much.

Well, now you'll tell me, but at least Firefox started the whole standards revolution right? At least it's better than Internet Explorer, right?

While it's true that it's better than IE, I wouldn't even consider IE a browser, as it can't even get basic standards right. If you had a program which edited text files, and you have it open a file, and it comes up with paragraphs out of order, and some not even appearing, would you call it a text editor? Yet I'm starting to see Gecko (the engine powering Firefox and Seamonkey) go the same route. Try setting a background for a radio button with CSS in Firefox, it completely ignores it. Yet even IE, the non-webbrowser, can do CSS backgrounds for radio buttons (albeit it only changes the background color outside the radio button itself within its rendering square).

This gets worse when trying to couple some JavaScript with your pages in Firefox. The onchange event for select boxes only fires in Firefox when changing them with the keyboard when one presses enter. All other browsers fire the event as soon as you can see a change within the box, such as when one presses up or down. Now perhaps you'll tell me that's undefined behavior so Firefox can implement it differently than everyone else (sound like Microsoft any?), but now apply this to how it handles dynamic text. Say you want to take our example above and convert your onchange in a select box to an onkeydown, so it should fire for every up/down request in the box without the user needing to press enter. Firefox again fails completely here, since it won't update text on a page modified by JavaScript till the screen is clicked, or a button is pressed. Meaning if you have your onkeydown event for a select box call a function which changes some text on the page, to say perhaps the contents of that select box. You won't actually see those changes till you press a button, perhaps up or down again, showing you the previous value on your page from the select box, instead of the current one. Sounds like a real stellar browser, doesn't it?

Then there's the issue about how Mozilla is trying to make their browser the only platform out there. Why do most people today still use Windows, even when there's a better OS for the average person? It all boils down to the applications. Anyone who is proposed to switch asks, can I play my favorite games on this other OS? Does my digital camera's photo sorting software work on it? What about all the other applications that I use on a regular basis? As Microsoft's chief primate keeps yelling, it's all about the developers. People will be stuck using whatever runs their favorite apps.

Now of course we know that the internet in many ways is becoming the new platform out there, hence why Microsoft tried to crush it or control it all these years. So as long as your browser is standards compliant, if people develop for it, we should be okay, no?

Unfortunately it's not like that. GMail doesn't work on Konqueror unless Konqueror changes its user agent to report as Gecko. Meaning many sites lock out browsers just because they didn't test with them, not because it doesn't work for any particular reason. A similar problem exists how IIS servers gibberish to browsers reporting themself as Opera. Yet Microsoft only wants to keep it that way.

Recently Microsoft reported that the upcoming IE 8 will only go into standard compliance mode when websites include an IE8 tag in their code. Now most people who discussed this feature have totally missed the main problem. It's not about having to add an extra tag. It's that the default mode for any whacko out there writing a webpage is to render in IE 6 or IE 7 super-bug-filled-non-standards-compliant-mode, so webpages will continue to not become standardized. Of course Microsoft realizes this, they'll do everything they can to make sure the large majority of stuff coming out by the clueless masses only works on their platform.

Now I'm not talking about Mozilla making the web buggy like Microsoft is trying to (but I bet they'd like that if they could get away with it), but it's that they're trying to get people dependent on their web browser. How so? It's all about the extensions!
Mozilla invented their own language and format and ranted and raved about how everyone should be writing extensions for their browser, and how their browser is the de-facto standard of the free world.

How many of you using Firefox feel they need all kinds of extras that people write for it? How often do you sit down at someone else's Firefox and feel naked about a lack of certain features you tailored your browser back home or at work to?

Now while I could go on and on about all kinds of extensions, everyone has their own tastes, so it'd be pointless to, but I'll point out a couple of examples.

Some of the extensions I use regularly for Firefox, such as auto translations of pages in languages I don't read/speak, or user agent spoofing are built right into Konqueror, many others aren't available anywhere else, or only for certain browsers written specifically for them. I'm talking about the GMail/Yahoo/And whatever else e-mail notifiers that can tell you when you received new e-mail, or ForcastFox which can tell me mostly accurate weather info for the week for just about anywhere in the world.

Now these extensions I just mentioned are perhaps not anything to get addicted to, but what about Ad blocking? Now of course other browsers also have a Mozilla compatible ad block framework installed, how many of them allow you to install something like the "Filterset.G Updater" so you can have your blacklists automatically updated by others to hide all the new types of ads on the internet that come out, such as the "Download Firefox Ad" that appears on the right of this page?

Not only that, we can hardly forget the wide plethora of developer related things one can get for Firefox, such as JavaScript Console, DOM Inspector, and all the extensions such as the Web Developer Toolbar and who knows what else.

Am I the only one who now feels locked into Firefox and can't switch because their special browser software doesn't run elsewhere? Even when we realize what a horrible wreck Firefox is, and terrible on machines with little RAM available?

Furthermore, you know how Microsoft always forces their desires upon you? Take this picture of Bill Gates for example:

Notice how his own personal desktop is the default Windows XP background? Surely a man as technical as Bill Gates can figure out how to change it to something he enjoys, just like everyone else has.
Or perhaps Bill Gates never changed it, since the default Windows XP background was Bill Gates' personal background at the time? Of course leave it to a guy like him to force his personal desires on everyone else.

Now lets see how Mozilla does the exact same thing. Ever wondered where Firefox's logo came from? Who would think that an image of a fox conquering the world is a good logo for a browser?

Check out a picture of Mozilla's former CEO, Mitchell Baker:

Now what do you think came first, the Firefox logo? Or her ridiculous hair cut?
Still don't get what I mean? See this:

If you think you can point out how Mozilla isn't the Microsoft of the internet platform, please let me know, I'd love to hear how you came to your false conclusions.

Say goodbye to the former Qt and hello to MiniQt?

2008-01-28T00:34:00.000-08:00

So everyone knows that Nokia is looking to buy Trolltech, the company behind Qt right? If not, read the press release.
Trolltech also has up a list of what this means for everyone, as well as a letter to the open source community (rename it to .pdf).

Now after hearing all that, you're probably running in one of two directions. Either thinking that "oh no, my Qt has been taken over by an evil organization and it'll be destroyed!", or that "KDE and Trolltech have an agreement over Qt so we're safe!". The interesting point is that both are true.

What? Both are true?!?! How can that be?

First, a little background. Qt which is the foundation of KDE, and what all the pillars of KDE stand on, is pretty much irreplaceable. Not wanting to ever get bitten by developing such a massive project on such a foundation controlled by a company, KDE and Trolltech signed an agreement, and formed a new group called the "KDE Free Qt Foundation".

To put it in their own words:

To fulfill the purpose of the Foundation, an agreement between Trolltech and the Foundation was made. This gives the Foundation the right to release Qt under a BSD-style license in case Trolltech doesn't continue the development of the Qt Free Edition for any reason including, but not limited to, a buy-out of Trolltech, a merger or bankruptcy.

As for the latest agreement, you can find links to it on their site, but the primary part to worry about is this. Let me summarize. If 12 months have passed without seeing an open source release of Qt, or the open source version falls behind the closed source one in that period of time, or the board as a whole (which half is composed of by Trolltech) agrees to release Qt as BSD, then it shall take the latest open source version of Qt, and open source it under the BSD license as they will become legally able to.

Now one must wonder why is that important? The current release is under GPL2/3 anyway, why do we need to have it stuck under BSD? We can always continue using the latest release as GPL2/3.

The great thing about Qt is that they have a corporation backing it, making sure the toolkit is excellent. They pay employees to do all the dirty and annoying work in the library too. They also ensure that it remains portable on a large variety of hardware. This kind of heavy work is not something the open source community is usually able to coordinate too well. There are very few large open source projects that are fully portable, run on greatly varied setups, and cover areas that most people don't want to program for. For example, Ubuntu made a release a while back where a significant portion of printer support was broken, since it's not fun to test or fix, there's nothing really challenging about printer support (except maybe getting those annoying devices to work in the first place, and not paper jamming), and it's not cost effective to make sure it continues to work, and the "save the universe, time, and pluto" groups wouldn't like you using all that paper either.

Also, Qt is currently able to be gotten either via a proprietary license or under the GPL (with exceptions too!), so companies producing closed source software, and open source nutjobs can play on equal footing. That means when a company hires a developer to develop with Qt, it's the same Qt, so s/he can later go home and use his or her knowledge to write a cool new open source application involving giraffes e-mailing pictures of people with dyed hair around, or whatever s/he might fancy. It also means that open source developers who want to create their own startup company, can use the knowledge they already gathered to write terrific applications, since they can just go and buy some licenses, and write their new apps.

The "Poison Pill" that they signed on would put Qt under BSD, which would continue to allow the companies, and the communities to continue to work with the same software, in the event that Trolltech became evil (or by extension of being bought). It could also mean that a company could throw developers at Qt, and use stuff privately in their own products too, and not be forced to not be allowed to do anything with their own changes, since it's virally all GPL.

This all falls apart however when one considers precisely what is in the agreement. IFF ('If and only if', for those of you who missed school that day), Trolltech or the new company fails to deliver an open source version or equal to the version offered proprietarily for an extended period of time, they can BSD what they have. This is great as long as the evil company doesn't continue to offer something which is worthless to the community but not so to the companies.

To quote Nokia:

We will continue to actively develop Qt and Qtopia. We also want to underline that we will continue to support the open source community by continuing to release these technologies under the GPL

Lets step back and think for a moment what Nokia is interested in. Cell Phones, right? Meaning only Qtopia, Qt in itself is worthless to them. Also consider what Trolltech's primary business is. They advertise these applications as the coolest using Qt. How many of those applications are done by those who buy a license? Now once you figured that out, how many of those have anything other than a Windows build? Many companies use Qt, not for the portability, but because of how easy it is. Here, read what Adobe, a company who has never produced Linux software, has to say. Since companies use it for the ease of use, and speed of development time, and don't really care if it works on Linux or not, since we all know that those Linux guys don't buy anything anyway, why should Nokia bother continuing to develop the X11 port of Qt? It's just a waste of time for any normal business model.

So Nokia could continue to develop Qt for their cellphones, and for customers such as Adobe, and even release Windows only, or perhaps even Windows and Mac OS X builds of Qt both proprietary and under the GPL, but none for X11. And what can the "KDE Free Qt Foundation" do about it anyway? Their agreement is worthless as there can still be an open source version which won't be useful to most of their developers. And who in the world are they going to complain to about 'intent' of the agreement? KDE runs on Windows and Mac OS X now, right? Their petty foundation can continue making their Kool Desktop Environment as long as it's done on Windows right? No one is stopping them.

At this point, the companies and the communities can be fractured, and even worse if the library is very different one platform to the next, it will become completely worthless for the sake of portability. Having an unfunded fork off of an older Qt won't do as well either, just look at what an awful mess the crippled broken GTK is, even with it being LGPL so companies can use it - if they were drugged up enough to.

On the other hand, Qtopia does run on Linux, but isn't protected by the KDE foundation either. If Nokia for whatever reason continued releasing Qtopia under open source, and the X11 port died, but cool new features of equal footing came to the Windows/OS X/Qtopia ports, perhaps the community might get some movement in the direction of moving away from the horrible X11. Bleh, who am I kidding, the nightmare that is X11 is here to stay, right?

KDE 4 Review - Insane Style

2008-01-23T19:45:00.000-08:00

So KDE 4 is out, along with major architectural changes, a new face, and new software, as well as tweaks to what KDE 3 had.

Now if you wanted to know about all the new libraries, and new platforms supported, or kinds of other flashy changes they made, you can look elsewhere on the internet. Instead I'm going to just describe the changes to the standard file open dialog, and the ramifications of having Dolphin as the new file manager, keeping in tradition of the previous file dialog articles.

So without further babbling, here's the new file open dialog:

Now ignoring all styling issues for the time being, let us compare that to what KDE 3.5 did:

First big difference is that the KDE 4 file dialog now has a crumb view on top. The crumb view is nice, in that if you want to jump back up a few directories, you can do so in a single click, instead of pressing up multiple times.

In fact you don't even need an up button anymore, but don't worry, the design experts at KDE gave you one anyway, since space on that line isn't important. Because if it was important they might consider moving the encoding drop down elsewhere - oh wait they did do that.

You've got to love mixed messages when it comes to GUI design, they needed more room for the crumb browser so they moved the encoding elsewhere to take up a full line down below, yet leave in the up button. Also interesting to note that KDE 4 is now using Qt 4, which quite nicely offers a file system watcher for paths to tell when they get updated to automatically refresh a file view, it seems despite that, the KDE team thinks you also need a nice refresh button on top.

Now if they really wanted to manage space properly, perhaps they'd put the crumb navigation on a line by itself up top, instead of giving all that room to encoding drop down which doesn't need a fraction of the room it's getting. Maybe something along the lines of this mockup I just made in KolourPaint:

Now there's plenty of room for large paths for the crumb browser, and no ridiculously huge encoding selector.

But these obvious issues aside, we haven't even gone past the surface of how utterly useless the dialog has become.

Remember how I spoke about how Windows added annoying virtual locations? Seems KDE copied them down the last annoying detail. Now "/home/insane" appears as "Home" in the crumb viewer (and no absolute path anywhere). If I want to go up to "/home", and then "/home/spouse", it's impossible. "Home" is treated as a root path, even to the extent that the unneeded up button doesn't do anything at this point either. One has to click on the left on "Root", then select "/home". This gets worse if you're on a machine where home directories are stored several levels deep. Of course power users, can type in the full path in the location bar on the bottom, but you'd think a group as intelligent as KDE can avoid glaring Windows design flaws. Don't even get me started on what happens if you delete the Root button from the quick locations on the left. Poor users who want to find someone else's home directory now have to navigate through the root path filled with stuff like "usr", "opt", "bin", "srv", and other unintelligent gibberish to do something that once was a single button click.

And speaking of annoying locations. Why the heck is Trash a location that appears by default in the quick locations? How often do you decide that the document you need to open is in the trash? I'm glad they removed Desktop, but replacing it with Trash? What were they thinking? Give me something useful like a Media quick link, for optical drives and all kinds of USB/Firewire external memory devices. They also completely removed support for right clicking on the quick locations panel, and just adding a new quick location. Now one is forced to drag a directory's folder icon from the right to the left. I wonder how that will work if one is in some kind of virtual directory that has no parent, making it impossible to drag.

Anyways regarding other features, remember how KDE 3 gave the user a lot of power and allowed them to have something similar to the old Windows 3 split view?

For some reason this useful method to navigate your files is completely gone.
And now with the old location input bar merged into the one for files, I can't even easily edit the current location by hand, since it doesn't display the current path at all. Furthermore, entering a new path seems to make it have useless data left over in it like the last path directory component after enter is pressed.

Old KDE file browser: 10
New KDE file browser: 6

I guess making the perfect file browser, especially when you were almost there is next to impossible.

Speaking of file browsers, lets look at how the new edition of Dolphin fares, touted as being better than Konqueror for simple management of files.

Now I remember I complained to some KDE devs a while back regarding the KDE 4 betas and how Dolphin seemed to be a bit brain damaged at file management, but they assured me it would change for the final release of KDE 4.0, and change it did! For the worse.

Back in the older betas, one could click a button to bring up a full path editor instead of the crumb view, now that button is completely gone. To bring it up, one has to go browse through one of the menus on top to switch back and forth between the quick browsing methods.

Here too, they also kept the brain damaged virtual Home path. There is no way to go up. Nice to see they didn't put in a useless up button, but here again, if I want to see everyone's home directory, I have to navigate there from Root.

Also, if one switches to the classic path editor, if one wants to go up, they're forced to backspace the old path, or switch back to the crumb view, since in the KDE Dolphin developers' great vision, they couldn't stick both views in at the same time, or make an up button appear when in the classic path editor.

There's also no nice directory and file split view here like good ol' File Manager. But one can bring up a directory tree browser:

And in keeping with the new KDE 4 design goal of copying stupidity from Windows (Vista), when viewing the tree view, the file viewing pane is also filled with now redundant directory listings.

Isn't it wonderful to see how people who used to be way ahead of the curve and tried so hard to offer a really advanced product have completely fell between the cracks when it came to normal sane usability of files?

For those of you wondering if perhaps GTK got any better since the last time I reviewed it, you can rest assured that it has not. In fact, I now have a new refined hatred for how lousy GTK is. In the course of uploading some images from FireFox in an article I was writing, the GTK file menu had the file type filter locked to (*.png/*.bmp/*.gif/*.jpg/*.jpeg). Since the pictures I had were all *.JPG, none showed up, as GTK in their infinite wisdom made the extension filter case sensitive.

Seems UNIX file management is just as lousy as ever and getting worse. I'm afraid to even look at Konqueror in KDE 4, fearing they ruined it too.

Feel free to start a flame war in the comments, I got my flame retardant suit on, besides nothing you can write can make me feel worse than what a downgrade KDE went through.

Directory safety when working with paths

2007-11-11T05:30:00.001-08:00

As we discussed in our previous two articles, we run into issues of thread safety when we try changing the path during a running program. Therefor, in addition to bypassing PATH_MAX problems, working around buffer issues thanks to implementing with C++, we would also love to implement our functions without ever calling chdir() and changing the working directory. We'll now look into how we can make changes to our implementation to avoid a chdir() call, along with the pros and cons of techniques UNIX operating systems provide us, as well as what they're lacking.

If one looks back at how we implemented getcwd(), they'll notice that we call chdir("..") for each step in our loop. We need this to sanitize the location for these three calls:


opendir(".")
lstat(entry->d_name, &sb)
stat(".", &sb)

To remove the need of changing directories, we can place the ".." paths directly into our calls to opendir(), lstat(), and stat(). Thanks to C++ Strings being dynamic, it makes it easy for us to manipulate paths for these situations properly. We'll also see that being clever, we can even avoid string manipulation for some of these cases. And if our OSs supplied enough functionality, without any string manipulation at all!

Here's how we can implement getcwd() based off our previous implementation, but without calls to chdir(), with key details highlighted:


bool getcwd(std::string& path)
{
  typedef std::pair<dev_t, ino_t> file_id;

  bool success = false;
  struct stat sb;
  if (!stat(".", &sb))
  {
    file_id current_id(sb.st_dev, sb.st_ino);
    if (!stat("/", &sb)) //Get info for root directory, so we can determine when we hit it
    {
      std::vector<std::string> path_components;
      file_id root_id(sb.st_dev, sb.st_ino);
      std::string up_path("..");

      while (current_id != root_id) //If they're equal, we've obtained enough info to build the path
      {
        bool pushed = false;
        DIR *dir = opendir(up_path.c_str());
        if (dir)
        {
          dirent *entry;
          up_path += "/";
          std::string::size_type after_slash = up_path.size();
          while ((entry = readdir(dir))) //We loop through each entry trying to find where we came from
          {
            if (strcmp(entry->d_name, ".") && strcmp(entry->d_name, ".."))
            {
              up_path.replace(after_slash, std::string::npos, entry->d_name);
              if (!lstat(up_path.c_str(), &sb))
              {
                file_id child_id(sb.st_dev, sb.st_ino);
                if (child_id == current_id) //We found where we came from, add its name to the list
                {
                  path_components.push_back(entry->d_name);
                  pushed = true;
                  break;
                }
              }
            }
          }

          if (pushed && !fstat(dirfd(dir), &sb)) //If we have a reason to contiue, we update the current dir id
          {
            current_id = file_id(sb.st_dev, sb.st_ino);
            up_path.replace(after_slash, std::string::npos, ".."); //Keep recursing towards root each iteration
          }

          closedir(dir);
        }
        if (!pushed) { break; } //If we didn't obtain any info this pass, no reason to continue
      }

      if (current_id == root_id) //Unless they're equal, we failed above
      {
        //Built the path, will always end with a slash
        path = "/";
        for (std::vector<std::string>::reverse_iterator i = path_components.rbegin(); i != path_components.rend(); ++i)
        {
          path += *i+"/";
        }
        success = true;
      }
    }
  }

  return(success);
}

First of all, we removed all the code related to saving the current directory when we started, since we don't need that information anymore. Our first major change is that we created a new C++ String called up_path, we'll use this variable to keep track of the path, initializing it to "..". then for each step through the loop, make it "../..", "../../.." and so on, till we reach the root. We use this to replace our calls to opendir() to "." as we were doing before.
At this point, we'll add a slash to the path, and keep track of the spot with the variable after_slash. Now in our read directory loop, we can replace whatever is after the slash with the filename in the directory to pass to lstat(), again bypassing the need to be in the same directory as the file when making the function call.
Now for the stat() call on the directory itself, we got a little interesting. Instead of doing a path manipulation trick again, we call fstat() on the file descriptor returned from dirfd() on the already open directly handle. Notice how the call to close directory has been moved to after the block of code, so the directory is still open. And of course it's all wrapped up nicely with appending ".." after the slash.

Noticing how we eliminated path manipulation for the last part, it would be nice to eliminate more of it, especially if anyone wants to port this C++ code to C. The good news is that on Solaris and Linux we can, and as soon as the "at" functions get standardized, we can use them on the other UNIX OSs too. You can read more about them in one of our previous articles, File Descriptors and why we can't use them.

Here's how we can use the at functions to eliminate the path manipulation needed for calling lstat(), with the differences highlighted:


bool getcwd(std::string& path)
{
  typedef std::pair<dev_t, ino_t> file_id;

  bool success = false;
  struct stat sb;
  if (!stat(".", &sb))
  {
    file_id current_id(sb.st_dev, sb.st_ino);
    if (!stat("/", &sb)) //Get info for root directory, so we can determine when we hit it
    {
      std::vector<std::string> path_components;
      file_id root_id(sb.st_dev, sb.st_ino);
      std::string up_path("..");

      while (current_id != root_id) //If they're equal, we've obtained enough info to build the path
      {
        bool pushed = false;
        DIR *dir = opendir(up_path.c_str());
        if (dir)
        {
          int dir_fd = dirfd(dir);
          dirent *entry;
          while ((entry = readdir(dir))) //We loop through each entry trying to find where we came from
          {
            if (strcmp(entry->d_name, ".") && strcmp(entry->d_name, "..") && !fstatat(dir_fd, entry->d_name, &sb, AT_SYMLINK_NOFOLLOW))
            {
              file_id child_id(sb.st_dev, sb.st_ino);
              if (child_id == current_id) //We found where we came from, add its name to the list
              {
                path_components.push_back(entry->d_name);
                pushed = true;
                break;
              }
            }
          }

          if (pushed && !fstat(dir_fd, &sb)) //If we have a reason to contiue, we update the current dir id
          {
            current_id = file_id(sb.st_dev, sb.st_ino);
            up_path += "/.."; //Keep recursing towards root each iteration
          }

          closedir(dir);
        }
        if (!pushed) { break; } //If we didn't obtain any info this pass, no reason to continue
      }

      if (current_id == root_id) //Unless they're equal, we failed above
      {
        //Built the path, will always end with a slash
        path = "/";
        for (std::vector<std::string>::reverse_iterator i = path_components.rbegin(); i != path_components.rend(); ++i)
        {
          path += *i+"/";
        }
        success = true;
      }
    }
  }

  return(success);
}

As should be easily discernible, the string manipulation got easier, and mostly vanished. All the keeping track of a slash, and replaces has been replaced with only needing to append "/.." at the end of each loop.
Instead of manipulating a path string for our call to lstat(), we save the directory's file descriptor above (and subsequently use that instead of recalculating it lower down for fstat()), then use it to get the lstat() for each file in the directory, but now via fstatat().
fstatat() is the same as stat()/lstat(), but takes a directory descriptor as the first parameter to offset where the filename is relative to. The last parameter can be 0 or AT_SYMLINK_NOFOLLOW, which makes it act like stat() or lstat() respectively. fstatat() instead of a file descriptor can also take the special value AT_FDCWD to have it automatically work in the current directory.

This implementation should be much more elegant, but a bit less portable. If one would like to implement fstatat() themselves, it's not hard, here's how you can do it:


int fstatat(int dirfd, const char *pathname, struct stat *buf, int flags)
{
  int success = -1;

  if ((!flags || (flags == AT_SYMLINK_NOFOLLOW)))
  {
    int cwdfd = -1;
    if ((dirfd == AT_FDCWD) || (pathname && (*pathname == '/')) || (((cwdfd=open(".", O_RDONLY)) != -1) && !fchdir(dirfd)))
    {
      success = (!flags) ? stat(pathname, buf) : lstat(pathname, buf);
    }

    if (cwdfd != -1)
    {
      fchdir(cwdfd);
      close(cwdfd);
    }
  }
  else
  {
    errno = EINVAL;
  }

  return(success);
}

You'll also need the defines for AT_FDCWD and AT_SYMLINK_NOFOLLOW. You have to make sure that the value you choose for AT_FDCWD can't be a valid file descriptor or the normal failure return value. Therefor I chose -2 in my implementations, but choosing any negative value should be okay. AT_SYMLINK_NOFOLLOW shouldn't matter what it is, and a value of 1 or for all I care, 42, should be fine.
If your OS supports the at functions (currently Linux 2.6.16+ and recent versions of Solaris), it's better not to use a custom implementation, as this isn't thread safe, since it calls fchdir() internally, and for our example, runs counter to the whole point of using fstatat(). It would also be faster to use the original getcwd() implementation from a few days ago than using an emulated fstatat(), since there's less overhead from repeated fchdir() calls.
It's also interesting to note that glibc on Linux now, even for older than 2.6.16 implements fstatat() and the whole slew of at functions even when not supported in the Kernel. It's similar to ours, can be thread unsafe due to changing the working directory, and for some inexplicable reason, segfaulted in certain circumstances when I ran a large battery of tests on it and my implementation against the Kernel's to make sure that mine was working properly.

Anyways, with that out of the way, one can't hope but wonder if it would be possible to also eliminate the need of any path string manipulation for the call to opendir(). Mysteriously, neither Solaris nor Linux have an opendirat() call. If there was such, we could easily keep the previous directory open, till we obtained a new handle for its parent directory.
Baring having an opendirat() function, it'd be nice to implement such a thing. Some UNIX OSs I understand have a function perhaps named fopendir() or fdopendir() to promote a file descriptor to a directory handle. With such a function, we can simply write an opendirat() which calls openat(), then promotes it, but Linux doesn't have a method of promotion, although Solaris does (fdopendir()). Lets hope the people who are standardizing the new at functions for POSIX seriously consider what they're doing, otherwise we won't be able to use them.

Now that we've gotten getcwd() to be safe, we still need realpath() to be. In our realpath() implementation, the only unsafe parts was our function chdir_getcwd() which called chdir() internally as well as getcwd(). getcwd() is now taken care of, but we still need to rewrite the rest of chdir_getcwd() to not actually chdir().
To do such should now be easy, we simply do getcwd(), but with a new start path. We'd make a new function called getcwd_internal() which would take two parameters, one for the current directory, and another to initialize the up one, which we can wrap everything else around. Basically copy your favorite getcwd(), but make the modifications to the beginning like so:


bool getcwd_internal(std::string& path, const std::string& start_dir, std::string& up_path)
{
  typedef std::pair<dev_t, ino_t> file_id;

  bool success = false;
  struct stat sb;
  if (!stat(start_dir.c_str(), &sb))
  {
    file_id current_id(sb.st_dev, sb.st_ino);
    if (!stat("/", &sb)) //Get info for root directory, so we can determine when we hit it
    {
      std::vector<std::string> path_components;
      file_id root_id(sb.st_dev, sb.st_ino);

      while (current_id != root_id) //If they're equal, we've obtained enough info to build the path
--SNIP--

Now we'd turn getcwd() and chdir_getcwd() into wrappers like so:


bool getcwd(std::string& path)
{
  std::string up_path("..");
  return(getcwd_internal(path, ".", up_path));
}

bool chdir_getcwd(const std::string& dir, std::string& path)
{
  std::string up_path(dir+"/..");
  return(getcwd_internal(path, dir, up_path));
}

Note that the name of chdir_getcwd() is now misleading that it doesn't actually change directories anymore. For this reason, it's a good idea to not put any implementation details into a function name, as a user shouldn't have to know about them, and over time, it can become inaccurate.

And there you have it folks, getcwd() and realpath() implemented safely. Hopefully in the process all you loyal readers learned a couple other things too.

Other improvements over all we discussed, might be to run a smart pass over concatenated path names at key locations to remove extra slashes together "///", unneeded current directory "/./", and extra parent directories "path1/path2/.." -> "path1/", which is useful if certain functions like opendir() or the stat() family of calls have internal buffer issues. But doing such is a discussion for another time.

This wraps up our long discussion. All comments and suggestions are welcome.

Insane Coding

Progression and Regression of Desktop User Interfaces

Reading in an entire file at once in C++, part 2

How to read in a file in C++

Making modconf work with Linux 3

A stronger C/C++ Preprocesser

Goodbye Google

C++ 2011 and non rectangular arrays

C++ 2011 and __func__

The failure of fragmented security

C++ Serialization Anyone?

This just in, 20% of enterprises and most IT people are idiots

Programming manuals for those who "get it"

Optimizing your file dialog

Know your system calls for reading directory entries

Process file names in an optimized manner

Use efficient data structures efficiently

Sort efficiently

Display directly

Search efficiently

Simplifying bootstrapping for virtual constructors

Time to shutdown the factory for code violations

Undocumented APIs

Does anyone understand types and magnitudes?

C++-201x Variadic Templates

Happy "Holidays" From Google

Cryptic Linux Distro Updates

Malicious hackers are not out there

We got excellent documentation!

FatELF Dead?

They actually want bad code

Who still watches Television?

Distributed HTTP

Blogger Spam

Why online services suck

How end users can utilize multicore processors

State of sound in Linux not so sorry after all

Perfect sound with OSS version 4

Ancient coding ideas finally in English - Part 2

Ancient coding ideas finally in English - Part 1

Will Linux ever be mainstream?

What the heck is a PC?

GPLv3 - Is it right for your family?

Binary Trees - Does it matter?

Mozilla is the new Microsoft

Say goodbye to the former Qt and hello to MiniQt?

KDE 4 Review - Insane Style

Directory safety when working with paths

C++ 2011 and func