CMake and C++ “Compile Time” Polymorphism

For a recent project of mine, I wanted to use what some people call “Compile Time Polymorphism” in C++. Here’s how I implemented it.

Polymorphism in the context of programming computers usually refers to the ability to tread objects of a different data type through the same interface. In C++, this is often implemented through class inheritance and the use of virtual functions. The text book example of this concept is two classes, Cat and Dog, that inherit from a common super class Animal. Animal has a method makeSound() that is implemented by each subclass accordingly. In real software projects, polymorphism is used to hide multiple implementations behind a uniform interface. Here’s an example of how this concept is usually used in C++.

class Animal {
public:
 void makeSound(void) = 0;
};

class Cat : public Animal {
public:
 void makeSound(void);
};

class Dog : public Animal {
public:
 void makeSound(void);
};

The issue with this code is that it requires the use of virtual functions which means you need a vtable for the concrete subclasses. Usually, as a programmer, you don’t need to worry about vtables as the compiler takes care of that for you. But let’s take a look at how this works anyways. A vtable is basically a table of function pointers. For each of the concrete classes shown above, the vtable contains a pointer to the respective makeSound method. Also, each object carries a pointer to the vtable. At runtime, when a virtual method of an object is called, the pointer to the vtable is resolved to the actual vtable. From there, the address of the method is loaded and the call to it is made indirectly. So the use of virtual methods not only increases the size of your code, but also the size of your objects. In addition to that, it forces the compiler to use indirect function calls through pointers which are usually slower than direct function calls. Again, the compiler takes care of all of that, so this is purely informational.

All of the above is okay and in fact required if you don’t know the concrete type of an object until the software actually runs. Also, in most software projects, the drawbacks don’t matter and aren’t even noticeable. But there are situations where you may not want to pay the price of virtual methods, e.g. in a resource limited embedded system.

Also, there are situations where it is known at compile time what the concrete implementation of an interface will be. This is true for example when you have an abstraction of an interface that is specific to a certain operating system: When you compile the software, you already know what the target operating system will be, so you can simply use and link to the right implementation of the interface, instead of post-poning the decision to runtime.

So how would you use polymorphism in C++ without the use of virtual methods?

Here’s how you could do it:

typedef enum OperatingSystemImpl {
 Darwin,
 FreeBSD,
 Linux
} OperatingSystemImpl_t;

template struct OperatingSystemChoice;

class DarwinImpl;
class FreeBSDImpl;
class LinuxImpl;

template<> struct OperatingSystemChoice {
 typedef DarwinImpl m_type;
};

template<> struct OperatingSystemChoice {
 typedef FreeBSDImpl m_type;
};

template<> struct OperatingSystemChoice {
 typedef LinuxImpl m_type;
};


struct OperatingSystemService {
 typedef OperatingSystemChoice< ... >::m_type m_type;
};

Of course, the ellipsis must be expanded, but more on that later. What’s important is how software using this construct would use the code:

OperatingSystemService::m_type OsServiceObj;

The snipped above would create an object of the correct type, dependend on what the ellipsis expands to. The neat thing is that the template compiler ensures that the ellipsis is expanded to a valid “type” as defined in enum OperatingSystemImpl. Also, it is made sure that the actual, underlying class is declared, e.g. class DarwinImpl.

In other words: If you tried to compile the software with the ellipsis expanded to Windows, you’d get a compilation error. If you had implemented this using classic polymorphism, you’d probably have some code that dynamically created the right object depending on what input is given. That means, you have to test your compiled code, feeding it an invalid type. This mean you must run your software. I’m convinced that finding problems earlier is better, so finding an issue when code is compiled is better than finding issues when code is run.

So back to how the ellipsis is expanded. Here’s how CMake, a build system, comes into play. CMake uses input files that describe how the software needs to be compiled. Those input files, as with other build systems, are able to define compiler flags. Also, CMake defines a variable that contains the operating system’s name. I suspect it’s the output of uname. So here’s what I added to my top level CMakeList.txt file:

add_definitions("-DOPERATING_SYSTEM=${CMAKE_SYSTEM_NAME}")

This makes the OPERATING_SYSTEM macro known to the pre-processor. So the code with the ellipsis can be re-written like this:

struct OperatingSystemService {
 typedef OperatingSystemChoice::m_type m_type;
};

Et voilà, the right type is picked when the code is compiled.

Here are the nice things about this: There is no need for virtual methods, eliminating the need for vtables. Also, invalid or unsupported operating system types will be found at compile time vs. at runtime while the code for all supported operating systems will still be always compiled (just not used).

One downside may seem that you no longer have an enforced interface like when using purely virtual classes, i.e. the compiler may not tell you that you forgot to implement a newly added method to one of your implementation classes. However, this is more of a minor issue: You will still get a compilation error in that case, but only if you’re compiling for the target system where you forgot to implement the newly added method.

TianoCore and coreboot, again

It has been over two years since the last time I worked on TianoCore for coreboot. These days I had some free time to spend and I used it to continue the project. I updated my code to the latest versions of coreboot and TianoCore and got it to work again in QEMU.

Here’s a "screenshot" and a few words on what it’s all about.

ImageMagick, libjpeg, etc. on Mac OS X

Here’s how I got ImageMagick with JPEG support to compile and run on Mac OS X 10.6 (Intel).

First, I got the ImageMagick Source Code via Subversion, per the instructions from http://www.imagemagick.org/script/subversion.php. Short version:

$ svn co  
https://www.imagemagick.org/subversion/ImageMagick/branches/ImageMagick-6.6.5  
ImageMagick-6.6.5

Then, I pulled libjpeg from the Independent JPEG Group. I had to extract the source code to a subdirectory of the ImageMagick directory called jpeg, i.e. /path/to/ImageMagick-6.6.5/jpeg.

Before I could compile any of the source code, I had to set three environment variables per this thread on the ImageMagick forums:

$  export CFLAGS="-isysroot /Developer/SDKs/MacOSX10.6.sdk 
  -arch ppc -arch i386"
$ export CXXFLAGS="-isysroot /Developer/SDKs/MacOSX10.6.sdk 
  -arch ppc -arch i386"
$  export LDFLAGS="-Wl,-syslibroot,/Developer/SDKs/MacOSX10.6.sdk 
  -arch ppc -arch i386"

Then, I compiled libjpeg via the via the standard ./configure and make dance. I used these commands:

$ cd jpeg
$ ./configure --prefix=/opt --disable-shared 
  --disable-dependency-tracking
$ make -j 16

Now, I was able to configure ImageMagick:


Be aware that the LDFLAGS path is different than the include path! If everything went well, you can now go on to build the imagemagick suite:

$ ./configure --prefix=/opt --without-x --without-perl --with-jpeg 
   --disable-shared --disable-dependency-tracking 
   --enable-delegate-build --enable-osx-universal-binary
$ make -j 16

This gave me statically linked binaries of the ImageMagick tools I was able to run on my Mac. I also tried to build dynamically linked binaries but failed. Because I don’t need the dynamically linked version, I gave up after a while.

Testing with Google’s C++ Test Framework (gtest)

The other day I was playing around with Google’s C++ Testing Framework (a.k.a. gtest). I tried to build the Code with Visual Studio 2008 Express and got some strange linker errors. I was able to solve the errors thanks to this site. In essence, I had to change the “Runtime Library” Setting in the C/C++ Code Generation options to “Multi-Threaded” for a release build and to “Multi-Threaded Debug” for a debug build.

Linker Sets

Reminder: When placing something in a dedicated section using __attribute__((section("foobar"))), the GNU toolchain will automatically add a symbol __start_foobar at the beginning and a symbol __stop_foobar at the end of the section.

However, you will need a reference to that symbol in order to prevent the linker from optimizing the symbol away. In other words, you need to declare something like extern void *__start_foobar; and use it.

When using the Microsoft toolchain, the symbols need to be added explicitly. To do that, one can make use of the fact that when the Microsoft linker encounters several sections with a “$_” in their name, it will merge the contents into one final output section. The name of the output section will be the common prefix of the declared sections. The beauty is that the contents are in the order of the section names.

Here’s an example: Supposed you placed something into a section called “foobar$_something”. You can then add a variable __start_foobar into a section “foobar$_a” and a variable __stop_foobar into a section “foobar$_z”. The resulting binary will have one section “foobar” with the contents of variable __start_foobar placed at the beginning, followed the contents of everything in section “foobar$_something” and the contents of the variable __stop_foobar at the end.

Fix Windows Full Text search

I’ve recently noticed that using the Windows full text search may not always turn up the expected results. Apparently, Windows requires a program to install a search filter for a given file type. There is some plain text filter available by default, but it’s only registered for some endings. Source code files, e.g. Groovy files, will not be included, even though they contain nothing but plain ASCII text. Anyways, there’s a fix available, but it’s nowhere near intuitive…

Building qfsm on Ubuntu 8.04

I just tried to build qfsm on Ubuntu 8.04. The only dependencies listed by qfsm are CMake and Qt 4.3.x – both of which are available through the Ubuntu packet manager.

However, when I followed the instructions provided along with the qfsm source code, I encountered this error message:

[ 41%] Building CXX object CMakeFiles/qfsm.dir/src/ExportAHDLDlgImpl.o
In file included from qfsm-0.51.0-Source/src/ExportAHDLDlgImpl.h:21,
                 from qfsm-0.51.0-Source/src/ExportAHDLDlgImpl.cpp:21:
qfsm-0.51.0-Source/src/ui_ExportAHDLDlg.h:27: error: expected constructor, 
  destructor, or type conversion before ‘class’
make[2]: *** [CMakeFiles/qfsm.dir/src/ExportAHDLDlgImpl.o] Error 1
make[1]: *** [CMakeFiles/qfsm.dir/all] Error 2
make: *** [all] Error 2

It turns out that the definition of the QT_BEGIN_NAMESPACE macro was nowhere to be found on my system. Luckily, removing the corresponding lines in the qfsm source code allowed me to build the code just fine. I used this one-liner to remove the offending lines:

$ for file in `grep -R QT_BEGIN_NAMESPACE * | awk -F : '{ print $1; }'` ; 
  do sed -i -e '/QT_.*NAMESPACE/d' $file ; done

Follow-Up

A quick follow-up to "Parallels" for Linux. I’ve managed to run the Windows XP Partition on my Laptop inside KVM-88 like this:

#!/bin/sh

export SDL_VIDEO_X11_DGAMOUSE=0
sudo qemu-system-x86_64 -hda /dev/sda -net nic -net user -m 1024 -cdrom fixntldr.iso -boot d -usb -usbdevice tablet -monitor stdio

To send Ctrl+Alt+Del, I needed to enter this at the QEMU shell:

sendkey ctrl-alt-delete

Edit (Jul 30th, 2009): Here is a link to the QEMU console commands.