23 Apr 08 Pigs do fly, Apple buys P.A. Semi!

According to this Forbes article Apple just bought P.A. Semi.

I was really sad when I found out that we weren’t going to see a PowerBook with a PWRficient chip. At the time I pretty much gave up on the idea of a powerful computer reaching home users anytime soon. I doubt we are going to see a PowerBook or PowerMac for that matter based on the PWRficient but at least they reignited the dream again.

21 Apr 08 Simple Buffer Parsing With C99

A friend of mine asked some questions relating to socket programming which spurred me to create a simple example based on an application I wrote a while back. It’s pretty basic stuff but I decided to post it here in case anyone has any feedback to offer.

I use flexible arrays where suitable so warm up your C99-compilers. There is virtually no error checking done in the example so be vary, also I didn’t compile it.

static const uint32_t PROTOCOL_MAGIC=0xdead001;
struct HelloHeader {
    uint32_t magic;
    uint32_t version;
};

enum Command {
    Command_NONE,
    Command_FILE_LIST,
    Command_GET_FILE,
};

struct CmdHeader {
    uint32_t cmd;
};

struct File {
    char name[256];
    uint64_t size;
};

struct FileList {
    uint32_t numFiles;
    File[] files;
};

struct GetFile {
    uint64_t len;
    /* null-terminated filename followed by data */
    char[256] name;
    char[] data;
};

uint64_t ntohll(uint64_t n)
{
#ifdef BIG_ENDIAN
    return n;
#else
    return (((uint64_t) ntohl(n)) << 32) + ntohl(n >> 32);
#endif
}

char* processCommand000301(char* buffer, size_t bufferLen)
{
    /* ... */
}

char* processCommand010000(char* buffer, size_t bufferLen)
{
    char* ptr = buffer;

    struct CmdHeader* commandHeader = (struct CmdHeader*) ptr;
    commandHeader->cmd = ntohl(commandHeader->cmd);
    ptr += sizeof(struct CmdHeader);
    switch (commandHeader->cmd) {
        case Command_FILE_LIST: {
            struct FileList* fileList = (struct FileList*) ptr;
            fileList->numFiles = ntohl(fileList->numFiles);
            ptr += sizeof(struct FileList);
            for (int i = 0; i < fileList.numFiles; ++i) {
                fileList.files[i].size = ntohll(fileList.files[i].size);
                printf("%s %lld\n", fileList.files[i].name, fileList.files[i].size);
                ptr += sizeof(struct File);
            }
            break;
        }

        case Command_GET_FILE: {
            struct GetFile* getFile = (struct GetFile*) ptr;
            getFile->len = ntohll(getFile->len);
            FILE* file = fopen(getFile.name, "w");
            fwrite(ptr, 1, getFile.len, file);
            ptr += getFile.len;
            fclose(file);
            break;
        }

        default:
            /* Unrecognized command! */
            return NULL;
    }

    return ptr;
}

int processBuffer(char* buffer, size_t bufferLen)
{
    char* ptr = buffer;

    struct HelloHeader* helloHeader = (struct HelloHeader*) buffer;
    helloHeader->magic = ntohl(helloHeader->magic);
    helloHeader->version = ntohl(helloHeader->version);
    if (helloHeader->magic != PROTOCOL_MAGIC) {
        /* Invalid header! */
        return -1;
    }
    ptr += sizeof(struct HelloHeader);

    while (ptr < (buffer + bufferLen)) {
        switch (helloHeader->version) {
            case 0x00010000:
                /* version 1.0.0 */
                ptr = processCommand010000(buffer, (size_t) ptr - buffer);
                break;

            case 0x00000301:
                /* version 0.3.1 */
                ptr = processCommand000301(buffer, (size_t) ptr - buffer);
                break;

            default:
                /* Unsupported version! */
                return -1;
        }
    }
    return 0;
}

P.S. I’m impressed by WordPress’ ability to consistently botch preformatted text when using the WYSIWYG editor. D.S.

07 Apr 08 Terrain rendering in Ada

A while ago I added another old project of mine to the projects page but I neglected to post about it.

The project is based on an old school project of mine from the university. It’s a terrain rendering engine written in Ada which was intended to be capable of handling very large terrains of very high detail, +/- 1 meter at the maximum zoom level if I recall correctly.

Since at the time the few OpenGL-bindings that existed for Ada were highly outdated and of varying quality I quickly decided I had to remedy the situation myself. It resulted in the AdaOpenGL project which to this very day, even though I haven’t updated it in over four years, still has a significant amount of downloads (according to SourceForge statistics). People have even tracked me down and called me personally about it, which was a first for me. For these very reasons I often have a guilty conscience for not bringing the project up to date. Two developers have offered to assist but neither of them every produced any releases.

After I had a viable OpenGL-binding I started on the terrain engine itself. As you might suspect I spent a lot of time on the binding and based on the little time I had left I decided to only implement a basic scene graph for the terrain engine. The idea was that someone else would pick up where I left off but as it turned out the company I did the project with never asked for my source code, which I found rather weird considering their initial enthusiasm.

I gave the project the name AdaTerrainEngine as I cannot recall what I initially named it. The data files belong to the company which I did the project with so I cannot release them. I don’t really remember how useful the source code is but at least it should provide a basic foundation for anyone who is doing OpenGL work in Ada.
The terrain engine is LGPL-licensed and AdaOpenGL is BSD-licensed.

P.S. I blatantly stole the design for the AdaOpenGL-site from an awesome CSS tutorial. After I finished the page I realized I forgot to credit the original author and I couldn’t find the site again. If you have any idea who did this please let me know! D.S.

14 Mar 08 Threadable C++ objects

I maintain a couple of objects at work which implement various behavior that requires a separate thread of execution. Since recently there were really only two of them but now they have multiplied beyond that so I realized that it would be appropriate to design a reusable framework in order to reduce unnecessary code duplication. The design I came up with is based around an interface which defines the API of any “threadable” object and an abstract implementation which provides the means to synchronize the threads. Threads in our systems tend to have a very long life span and we avoid any kind of resource allocation (including launching threads) which are soon thereafter released as that can lead to fragmentation.

Although I’m fairly satisfied with this implementation there is at least one flaw in it. I’ll leave it to my readers to find it.

The interface is fairly simple and provides three methods. kill() which is used to signal thread termination, running() which is used to query whether the thread is actually up and running and finally the actual thread function implemented as operator()().

class IThreadable {
public:
    virtual ~IThreadable() throw() { }

    virtual void kill() = 0;
    virtual bool running() const = 0;
    virtual void operator()() throw() = 0;
};

The AbstractThreadable object implements the kill() and running() methods which should look the same across all kinds of threadable objects. It also implements two protected methods which must be called in the threadable object to signal that it has enter or exited its thread function, these are known as signalThreadRunning() and signalThreadExit().

I’m using a tristate variable to keep track of the threads current state of execution. The reason behind this is that I want to differentiate between a thread that has not yet been started. If someone calls kill() and never actually launches the thread the kill() method will block on the semaphore unless we can detect this state.

enum ThreadState {
    ThreadState_NONE,
    ThreadState_RUNNING,
    ThreadState_KILLED,
};

class AbstractThreadable : public IThreadable {
public:
    AbstractThreadable() : m_state(ThreadState_NONE) { }

    virtual void kill() {
        scoped_lock stateLock(m_stateMutex);
        if (m_state != ThreadState_KILLED) {
            ThreadState prevState(m_state);
            m_state = ThreadState_KILLED;
            stateLock.unlock();
            if (prevState == ThreadState_RUNNING) {
                m_threadExitSemaphore.p();
            }
        }
    }

    virtual bool running() const {
        if (scoped_lock(m_stateMutex), m_state != ThreadState_KILLED) {
            return true;
        }
        return false;
    }

    virtual void operator()() throw() = 0;

protected:
    virtual void signalThreadEnter() {
        scoped_lock stateLock(m_stateMutex);
        m_state = ThreadState_RUNNING;
    }

    virtual void signalThreadExit() {
        m_threadExitSemaphore.v();
    }

private:
    ThreadState m_state
    mutable mutex m_stateMutex;
    semaphore m_threadExitSemaphore;
};

Finally I will present a simple object using the above implementation in order to implement a threadable object which just sleeps until someone signals it to terminate via kill(). Notice how signalThreadRunning() and signalThreadExit() are used in order to notify the AbstractThreadable implementation of the current thread state.
Note: Calling running() requires locking a mutex so if the thread loop is very tight it might be wise to unroll it.

class Sleeper : public AbstractThreadable {
public:
    void operator()() throw() {
        signalThreadEnter();
        while (running()) {
            sleep(1);
        }
        signalThreadExit();
    }
};

This is a simple example showing how to use the sleeper thread. I’m using Boost to create the thread. thread is a thread object and ref makes sure the sleeper object is passed by ref rather than being copied.

int main(int argc, char **argv)
{
    Sleeper sleeper;
    thread sleeperThread(ref(sleeper));
    ...
    sleeper.kill();
    return sleeperThread.join();
}

29 Feb 08 sed stupidity or ampersand magic?

We were reformatting some code at work the other day using find and sed and stumbled upon a very weird case when using the ampersand (&) character. We accidentally expanded all boolean and expressions in our C++-code (&&) to “& &” when applying a rule to modify “<type> & <variable>” to “<type>& <variable>”. In order to change them back we ran a “find . -type f | xargs sed -i -e ’s:& &:&&:g’” which resulted in all the expression becoming “& && &”?!

After some fiddling around it turns out the ampersands in the resulting string had to be escaped to reach the desired result. As far as I know ampersands are not part of the regular expression syntax and I’ve never before had to escape anything in the resulting string.

In the end the following syntax yielded the correct result.

echo " & & " | sed -e 's:& &:\&\&:g'

 &&

I don’t know if this is a bug or feature and if anyone else does please let me know.

21 Feb 08 “Kristian’s Model”

We’ve been confronted with the problem of working with a poorly documented API at work, again. The samples are overly complex and the simplest to the most advanced still link with and use functions from the same files making it very difficult to figure out what each individual part of it actually does and why it’s needed. I’ve had to deal with this issue before but this time around it’s definitely worse. In order to break down this API we have decided to apply a method known as “Kristian’s Model” which allows you to quickly gain an understanding to complex samples.

Kristian’s Model is a five step process which I will try to explain below. The original author has requested to remain anonymous.

1. Design comp.sh

If the existing build system is working against you quickly have it replaced by a simple build script that will compile exactly the application which you are trying to break down .. no more, no less. I like GNU Make as much as the next guy but when developers have too much spare time they have a tendency to abuse the more powerful features of GNU Make in order to concoct Makefiles which are almost more difficult to understand than the application itself. By running a make -n <target> you’ll quickly and painfully be able to extract the necessary commands to build your target. Put these commands into comp.sh and prune them when you need to.

2. Replace function calls with their actual code

Now that the build system is out of the way we can move on to the more interesting part, the actual code.

Breaking up large functions into smaller parts and putting these parts into functions with descriptive names is a very important quality to have in a programmer but sadly this seems to be somewhat of a lost art in the world of API-developers using C. It’s not at all uncommon to see functions spanning pages upon pages of unrelated code which would be a prime candidate for being broken up in any sane developers mind. An example from one of the simpler (!) samples I have to work with is a main function which spans a whopping 1150 lines. It’s bad enough to see this in a regular application but seeing it in a sample application which is meant to show how to use a moderately complex API makes me want to peel someone eyes out.

What makes things matters is that someone, probably management, realized that having single functions span more pages than your average datasheet was a bad idea and forced the inexperienced programmers to break up their functions. This had the unfortunate result that instead of having one humongous main function where at least execution flow was largely obvious the code was broken up into, still very large functions, with generic names such as initialize_options (which initializes maybe 100 variables stored in one enormous struct) and apply_options which used a way too small set of sub functions to apply this large number of options. When they ran out of generic function names they decided to use the next best thing, obscure names such as refresh_soft_cc and set_cp_bit (and no, they don’t make sense even if you know the context).

The second step goes against everything any good programmer should know. Replace all non-stdc calls in your main function with the actual code used in those functions. Iterate until you have nothing but stdc and API calls. You will end up with one very large main but at least code flow will now be painstakingly obvious. This step will aid you in your next venture, step 3.

3. Code reduction

Now that all code is nicely packed into one large bundle start removing anything that doesn’t affect the result of application execution in a negative way. My personal favorite is using #if 0 .. #endif since you can quickly enable/disable code to analyze its effect. I also use this method a lot in step 2 where I add an #else case with my replacement code until I can ascertain that it works like the original function call.

Once you have reduced the remaining code to a bare minimum of functionality you can finally start wrapping your brain around it.

4. Objectify

Not all people like object oriented development but to me it’s one of the most powerful tools I have as a programmer. It allows me to hide away functionality behind clearly understandable concepts such as somePath.parent() and FileUtils::isDirectory(..) which in effect means that you can break large complex problems into smaller and smaller objects. Sometimes I’ve even been known to design prototypes in high order object oriented languages only to make the actual implementation in regular C, without using fancy struct constructs.

It should be obvious by now but the fourth step is to divide your large lump of code into small understandable units of objects. This process will help you to gain a deeper understanding of what is actually going on behind the scenes while at the same time generating objects which you can use more or less unmodified in your applications.

5. Implement all possible features

The last and final step could be considered optional but it is helpful if you want to make sure that no stone is left unturned. By now you should also be close to the peak of total understanding of the system which you are breaking down and now is probably the best time to wrap as much as possible of the API in easy to understand objects. Try to implement features which will exercise all capabilities of the API even if you don’t need it now or any time soon.

Conclusion

By now you should have a pretty complete understanding of the system which you have to work with. Reading the remaining samples should be easier since you should be fairly familiar with domain specific concepts and terminology. Hopefully from hereon you will find it easier to read the remaining code samples as you know what most or maybe even all of the API calls do.

You’ve walked down a long and winding path but in your heart you know it had to be done. Try not to think of the long and tedious process when you start out and instead focus on the end results of your hard labor. I’ve tried having one or two highly interesting side projects to jump to whenever it feels like you are trapped in a dark pit but my experience is that it is better to grab the bull by the horns and just do it as distractions will only cause you to lose focus.

My kudos goes out to the guy who formalized this model which in turn made it much more quantifiable as a legitimate project task.

21 Feb 08 Yet another engine switch

I switched back to WordPress again. Movable Type had some really cool features but the admin interface was just waay too slow. It could take anywhere from 30-60 seconds to switch page or save a blog entry which was simply unbearable. I tried getting the FastCGI interface to work but it refused to run and documentation was scarce to say the least.

20 Jan 08 AmiScrobbler

I uploaded the latest source drop from my old CVS of AmiScrobbler to the projects page. I finally found it so now you can stop bugging me about making the latest source available.

The main difference between this version and the latest released version is that it fixed a bug with AmiNetRadio. Since I haven’t worked on this in a long time I don’t know if it will still work with the latest ANR release or even last.fm.

19 Jan 08 Projects page update

I have started going through the backups I recovered from my old server in order to publish some of the more interesting projects on this site. The first two source drops are CrabOS and Loader.

Check out my projects page for more information.

19 Jan 08 Wordpress Magic

In an act of pure magic I managed to recover most, if not all, of my old posts from an old SQL dump I found on an even older disk. All the time I expected there to be a full database backup on my old server which I meant to restore just as soon as I had access to the machine. As it turns out my backups were all located on the disk that died, the very same disk where the live database was located. Sometimes I scare myself..

Luckily though I had a slightly older dump available on the surviving hard drive and after creating a sandbox Wordpress installation I was able to export my old blog and import it into this one so in the end it all turned out fine anyway.