Stigmergy in programming

Ants are known to leave invisible pheromones on their paths in order to inform both themselves and their fellow ants where to go to find food or signal that a path leads to danger. In biology, this phenomenon is known as stigmergy: the act of modifying your environment to manipulate the future behaviour of yourself or others. From the Wikipedia article:

Stigmergy (/ˈstɪɡmərdʒi/ STIG-mər-jee) is a mechanism of indirect coordination, through the environment, between agents or actions. The principle is that the trace left in the environment by an individual action stimulates the performance of a succeeding action by the same or different agent. Agents that respond to traces in the environment receive positive fitness benefits, reinforcing the likelihood of these behaviors becoming fixed within a population over time.

For ants in particular, stigmergy is useful as it alleviates the need for memory and more direct communication; instead of broadcasting a signal about where a new source of food has been found, you can instead just leave a breadcrumb trail of pheromones that will naturally lead your community to the food.

We humans also use stigmergy in a lot of ways: most notably, we write things down. From post-it notes posted on the fridge to remind ourselves to buy more cheese to writing books that can potentially influence the behaviour of a whole future generation of young people.

Let's face it: We don't have infinite brains and we need to somehow alleviate the need to remember everything. If you remember the movie Memento, the protagonist Leonard has lost his ability to form new long-term memories and relies on stigmergy to inform his future actions; everything that's important he writes down in a place he's sure to come across it again when needed. His most important discoveries he turns into tattoos that he cannot lose or avoid seeing when he wakes up in the morning.

Perhaps a biologist would object and say this is stretching the definition of stigmergy, but I contest that it fits: leaving a trace in the environment in order to stimulate a future action.

For stigmergy to be effective, it must be placed in the right location so that whoever comes across it will perform the correct action at that time. If we return briefly to the shopping list example, we typically keep the list close to the fridge because that is often where we are when we need to write something down -- or when we go to check what we need to buy.

Let's take an example from computing: Have you ever seen a line at the top of a file that says "AUTOMATICALLY GENERATED; DON'T MODIFY THIS"? Well, that's stigmergy. Somebody made sure that line would be there in order to influence the behaviour of whomever came across that file. A little note from the past placed in the environment to manipulate future actions.

In programming, stigmergy mainly manifests as comments scattered throughout the code -- the most common form is perhaps leaving a comment to explain what a piece of code is there to do, where we know somebody will find it and, hopefully, be able to make use of it. Another one is leaving a "TODO" comment where something isn't quite finished -- you may not know that a piece of code isn't handling some corner case just by glancing at it, but a "TODO" comment stands out and may even contain enough information to complete the implementation. In other cases, we see the opposite: "here be dragons"-type comments instructing the reader not to change something, perhaps because the code is known to be complicated, complex, brittle, or prone to breaking.

Stigmergy is a powerful idea, and once you are aware of it you can consciously make use of it to help yourself and others down the line. We're not robotic ants and we can make deliberate choices regarding when, where, and how we modify our environment in order to most effectively influence future behaviour.

Writing a reverb filter from first principles

WARNING/DISCLAIMER: Audio programming always carries the risk of damaging your speakers and/or your ears if you make a mistake. Therefore, remember to always turn down the volume completely before and after testing your program. And whatever you do, don't use headphones or earphones. I take no responsibility for damage that may occur as a result of this blog post!

Have you ever wondered how a reverb filter works? I have... and here's what I came up with.

Reverb is the sound effect you commonly get when you make sound inside a room or building, as opposed to when you are outdoors. The stairwell in my old apartment building had an excellent reverb. Most live musicians hate reverb because it muddles the sound they're trying to create and can even throw them off while playing. On the other hand, reverb is very often used (and overused) in the studio vocals because it also has the effect of smoothing out rough edges and imperfections in a recording.

We typically distinguish reverb from echo in that an echo is a single delayed "replay" of the original sound you made. The delay is also typically rather large (think yelling into a distant hill- or mountainside and hearing your HEY! come back a second or more later). In more detail, the two things that distinguish reverb from an echo are:

1. The reverb inside a room or a hall has a much shorter delay than an echo. The speed of sound is roughly 340 meters/second, so if you're in the middle of a room that is 20 meters by 20 meters, the sound will come back to you (from one wall) after (20 / 2) / 340 = ~0.029 seconds, which is such a short duration of time that we can hardly notice it (by comparison, a 30 FPS video would display each frame for ~0.033 seconds).
2. After bouncing off one wall, the sound reflects back and reflects off the other wall. It also reflects off the perpendicular walls and any and all objects that are in the room. Even more, the sound has to travel slightly longer to reach the corners of the room (~14 meters instead of 10). All these echoes themselves go on to combine and echo off all the other surfaces in the room until all the energy of the original sound has dissipated.

Intuitively, it should be possible to use multiple echoes at different delays to simulate reverb.

We can implement a single echo using a very simple ring buffer:

    class FeedbackBuffer {
    public:
        unsigned int nr_samples;
        int16_t *samples;

        unsigned int pos;

        FeedbackBuffer(unsigned int nr_samples):
            nr_samples(nr_samples),
            samples(new int16_t[nr_samples]),
            pos(0)
        {
        }

        ~FeedbackBuffer()
        {
            delete[] samples;
        }

        int16_t get() const
        {
            return samples[pos];
        }

        void add(int16_t sample)
        {
            samples[pos] = sample;

            /* If we reach the end of the buffer, wrap around */
            if (++pos == nr_samples)
                pos = 0;
        }
    };

The constructor takes one argument: the number of samples in the buffer, which is exactly how much time we will delay the signal by; when we write a sample to the buffer using the add() function, it will come back after a delay of exactly nr_samples using the get() function. Easy, right?

Since this is an audio filter, we need to be able to read an input signal and write an output signal. For simplicity, I'm going to use stdin and stdout for this -- we will read 8 KiB at a time using read(), process that, and then use write() to output the result. It will look something like this:

    #include <cstdio>
    #include <cstdint>
    #include <cstdlib>
    #include <cstring>
    #include <unistd.h>

    int main(int argc, char *argv[])
    {
        while (true) {
            int16_t buf[8192];
            ssize_t in = read(STDIN_FILENO, buf, sizeof(buf));
            if (in == -1) {
                /* Error */
                return 1;
            }
            if (in == 0) {
                /* EOF */
                break;
            }

            for (unsigned int j = 0; j < in / sizeof(*buf); ++j) {
                /* TODO: Apply filter to each sample here */
            }

            write(STDOUT_FILENO, buf, in);
        }

        return 0;
    }

On Linux you can use e.g. 'arecord' to get samples from the microphone and 'aplay' to play samples on the speakers, and you can do the whole thing on the command line:

    $ arecord -t raw -c 1 -f s16 -r 44100 |\
        ./reverb | aplay -t raw -c 1 -f s16 -r 44100

(-c means 1 channel; -f s16 means "signed 16-bit" which corresponds to the int16_t type we've used for our buffers; -r 44100 means a sample rate of 44100 samples per second; and ./reverb is the name of our executable.)

So how do we use class FeedbackBuffer to generate the reverb effect?

Remember how I said that reverb is essentially many echoes? Let's add a few of them at the top of main():

    FeedbackBuffer fb0(1229);
    FeedbackBuffer fb1(1559);
    FeedbackBuffer fb2(1907);
    FeedbackBuffer fb3(4057);
    FeedbackBuffer fb4(8117);
    FeedbackBuffer fb5(8311);
    FeedbackBuffer fb6(9931);

The buffer sizes that I've chosen here are somewhat arbitrary (I played with a bunch of different combinations and this sounded okay to me). But I used this as a rough guideline: simulating the 20m-by-20m room at a sample rate of 44100 samples per second means we would need delays roughly on the order of 44100 / (20 / 340) = 2594 samples.

Another thing to keep in mind is that we generally do not want our feedback buffers to be multiples of each other. The reason for this is that it creates a consonance between them and will cause certain frequencies to be amplified much more than others. As an example, if you count from 1 to 500 (and continue again from 1), and you have a friend who counts from 1 to 1000 (and continues again from 1), then you would start out 1-1, 2-2, 3-3, etc. up to 500-500, then you would go 1-501, 2-502, 3-504, etc. up to 500-1000. But then, as you both wrap around, you start at 1-1 again. And your friend will always be on 1 when you are on 1. This has everything to do with periodicity and -- in fact -- prime numbers! If you want to maximise the combined period of two counters, you have to make sure that they are relatively coprime, i.e. that they don't share any common factors. The easiest way to achieve this is to only pick prime numbers to start with, so that's what I did for my feedback buffers above.

Having created the feedback buffers (which each represent one echo of the original sound), it's time to put them to use. The effect I want to create is not simply overlaying echoes at fixed intervals, but to have the echos bounce off each other and feed back into each other. The way we do this is by first combining them into the output signal... (since we have 8 signals to combine including the original one, I give each one a 1/8 weight)

    float x = .125 * buf[j];
    x += .125 * fb0.get();
    x += .125 * fb1.get();
    x += .125 * fb2.get();
    x += .125 * fb3.get();
    x += .125 * fb4.get();
    x += .125 * fb5.get();
    x += .125 * fb6.get();
    int16_t out = x;

...then feeding the result back into each of them:

    fb0.add(out);
    fb1.add(out);
    fb2.add(out);
    fb3.add(out);
    fb4.add(out);
    fb5.add(out);
    fb6.add(out);

And finally we also write the result back into the buffer. I found that the original signal loses some of its power, so I use a factor 4 gain to bring it roughly back to its original strength; this number is an arbitrary choice by me, I don't have any specific calculations to support it:

    buf[j] = 4 * out;

That's it! 88 lines of code is enough to write a very basic reverb filter from first principles. Be careful when you run it, though, even the smallest mistake could cause very loud and unpleasant sounds to be played.

If you play with different buffer sizes or a different number of feedback buffers, let me know if you discover anything interesting :-)

Comparing objects in C++

The standard C++ pattern for comparing and ordering objects is to overload operator<() for your class. This function is what all the standard containers (std::set, std::priority_queue, etc.) and algorithms (std::sort, std::binary_search, etc.) use for comparing objects.

So if you have a class that you would like to put in a standard container, you have to overload operator<(). Your class usually has more than one member, and you usually want to order your objects first by the value of one member, then by the value of another member, and so on. For example, if you have a class person with string members firstname and lastname, and you would like a "phone book" ordering, you would order by lastname first, then by firstname, e.g.:

Anderson, Clive
Anderson, Lucy
Anderson, Thomas
Armstrong, Lance
Armstrong, Neil
...

To achieve this using operator<(), implemented only in terms of std::string::operator<(), you could do something like this:

struct person
{
    std::string firstname;
    std::string lastname;

    bool operator<(const person &other) const
    {
        /* Order first by lastname */
        if (lastname < other.lastname)
            return true;
        if (other.lastname < lastname)
            return false;

        /* The lastnames were equal, so try to order by firstname instead */
        return firstname < other.firstname;
    }
};

This code is not optimal. To see why, consider a case where you have two persons with the same lastname. The first check will fall through (lastname < other.lastname is false); so will the second (other.lastname < lastname is also false). Each check had to loop over the lastname when a single loop should have sufficed.

Fortunately, std::string happens to implement a member function compare() which returns an int. The semantics are similar to C's strcmp(a, b), which also returns an int. The return value is less than 0 if a < b, 0 if they are equal, or greater than 0 if a > b. Using this function, we can implement a much more efficient operator<():

struct person
{
    std::string firstname;
    std::string lastname;

    bool operator<(const person &other) const
    {
        int d = lastname.compare(other.lastname);
        if (d < 0)
            return true;
        if (d > 0)
            return false;

        /* The lastnames were equal, so try to order by firstname instead */
        return firstname < other.firstname;
    }
};

To see the difference in running time, we can implement a simple loop which inserts the same element many times to a multiset:

int main(int argc, char *argv[])
{
    std::multiset<person> persons;

    for (unsigned int i = 0; i < 1000000; ++i)
        persons.insert(person("Thomas", "Anderson with a rather long last name for the sake of the argument"));
}

We exaggerate the number of elements and the length of the lastname in order to amplify the difference. Running this on my laptop, it takes approximately 3.9 seconds to run the original code and 2.9 seconds to run the new version.

This is all well and good, but the actual problem runs a bit deeper than this. What if our code uses other compound data types than strings? Take e.g. std::pair. It is hopelessly broken, precisely because it doesn't implement a compare() function! std::pair only implements operator<() and only expects its elements to implement operator<() too. Have a look at the libstdc++ implementation (simplified):

template<class _T1, class _T2>
inline bool operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
{
    return __x.first < __y.first
        || (!(__y.first < __x.first) && __x.second < __y.second);
}

Can you spot the performance bug? Yep, it calls checks both __x.first < __y.first and __y.first < __x.first in the worst case. This also means that std::pair<std::string, std::string> has exactly the same problem as our first implementation of struct person.

In order to show just how bad this really is, consider the case where we have nested pairs:

typedef std::pair<int, int> p1; // 2 elements
typedef std::pair<p1, p1> p2;   // 4 elements
typedef std::pair<p2, p2> p3;   // 8 elements
// ...
typedef std::pair<p5, p5> p6;   // 64 elements

This is not a realistic example per se, but it illustrates very well how big the problem really is. Let's assume we have an object x6 constructed in the following way:

p1 x1(0, 0);
p2 x2(x1, x1);
// ...
p6 x6(x5, x5);

What happens when you try to compare x6 to itself like this?

if (x6 < x6)
    /* ... */;

Let's take a step back. x6 has 64 int elements, which can be reached in the following ways:

x6.first.first.first.first.first.first
x6.first.first.first.first.first.second
x6.first.first.first.first.second.first
x6.first.first.first.first.second.second
...

Intuitively, we should only need to perform 128 comparisons in the worst case (two comparisons for each pair of corresponding elements from the two objects). If we had two arrays of 64 ints, we would do it like this:

int compare(const int a[64], const int b[64])
{
    for (unsigned int i = 0; i < 64; ++i) {
        if (a[i] < b[i])
            return -1;
        if (b[i] < a[i])
            return 1;
    }

    return 0;
}

In order to answer the question posed ("How many comparisons between two ints are we actually making when we compare x6 against itself?"), we can simply program it using a wrapper class for int that counts the number of comparisons:

static unsigned int nr_comparisons = 0;

struct myint
{
    int value;

    myint()
    {
    }

    myint(int v):
        value(v)
    {
    }

    bool operator<(const myint &other) const
    {
        ++nr_comparisons;
        return value < other.value;
    }
};

Now we just have to change the definition of p1 from

typedef std::pair<int, int> p1;

to

typedef std::pair<myint, myint> p1;

and finally print nr_comparisons. The answer? 729.

Because std::pair has three comparisons in the worst case, instead of just two (which would have been sufficient), the complexity of comparing nested pairs has just climbed from 2^n (where n is the number of levels of pairs) to 3^n. That's pretty bad!

Part of the solution, as employed by std::string and our improved struct person, is to define the most fundamental comparison between objects as a function that can tell you whether a < b, a == b, or a > b in a single call rather than determine this using two calls. It is clear that the two are semantically equivalent (you can both define operator<() in terms of compare() and the other way around), but one is computationally superior for compound objects.

This is still not the full story, however. We wouldn't get any performance improvement from std::set if we changed it to call compare() instead of operator<() — because it doesn't need to compare both ways! In fact, if we changed it, we would now find that std::set<int> operations take more time, since calling compare() on an int would have to check both a < b and b < a even when std::set only needs to know the result of one of them! (This is of course tighly coupled to the std::set implementation — implemented as a tree, lookups would typically traverse the tree by comparing the element that is searched for with the current node, and update the current node depending on the result of the comparison.)

The real solution, therefore, seems to be to implement both operator<() and compare() for all types. std::pair's would look something like this:

bool operator<(const pair &other) const
{
    int d = first.compare(other.first);
    if (d < 0)
        return true;
    if (d > 0)
        return false;

    return second < other.second;
}

int compare(const pair &other) const
{
    int d = first.compare(other.first);
    if (d != 0)
        return d;

    return second.compare(other.second);
}

Now containers and algorithms can use the most efficient one — std::set would still use operator<() on its elements, but std::pair::operator<() would now use compare() (for its first element), and so on.

Maybe we could adopt Perl's <=> operator for the next version of C++?

Space invaders?

After my exams in December, I relaxed by writing a sort of space game using C++/SDL/OpenGL:



I ripped the sprites from Space Invaders and Galaga/Galaxian, please forgive me. If whoever wants to play/hack, the source code can be found here:

http://github.com/vegard/spaceinv

The video is a bit poor, mostly because the frame rate is supposed to be 60 FPS, but the Ogg/Theora capture was 25 FPS while the actual gameplay was probably closer to ~10 while doing the capture. Need to fix that. It looks better when playing.

First Jato release

So I somewhat promised to say something more on my project for the Google Summer of Code.

I participated for the first time, and it was really a great experience. This is the first time I've been paid to do what I would probably have done in either case (because I immensely enjoy it), namely to work on an interesting free software project. So this time it was Jato, a new implementation of the Java Virtual Machine.

Jato is written in C and aims to be a JIT-only compiler/VM. So before the summer started, it wouldn't run a lot of Java programs. It couldn't even run the trivial "Hello World", but more about that later. It could do a few things like (java.lang.)String operations, but that was mostly because it was riding piggyback on another VM, Jam VM, which would load classes and interpret a lot of the library code (i.e. most of the standard Java API implemented by GNU Classpath).

My own project was to replace the parts that were borrowed from Jam VM with completely new, shiny code. Well, in fact, I had already worked on a standalone library called cafebabe, which would parse the Java .class file and present it to C programs using a very thin layer of structs -- the idea was to do as little as possible with the actual data and just make it easily accessible, e.g. so cafebabe doesn't do any verification of the bytecode or make sure that a class is its own superclass.

So we linked this library with Jato, and that worked pretty well. (I believe strongly in modularisation; with the class loader in a separate library, there's no way to do stupid things like making the class loader itself depend on the rest of the VM for functioning properly.) There were problems, of course, the biggest being that after developing in my own private branch for a couple of weeks, the rest of the project with its three other GSoC student participants was moving ahead too quickly for me to keep up; I had to "fix" just about every new mainline commit, since most of the VM data structures (classes, methods, fields) now had different names, different fields, etc.

At around this point, we started to notice that Jam VM wasn't being used for nearly as little as just class loading. In fact, static initializers (the "<clinit>" methods) and their calls were all being interpreted and executed by Jam VM, not the JIT compiler of Jato. And of course, once we started using Jato for those methods which had previously been executed by Jam VM, we found tons of bugs everywhere: The core VM (mostly my code replacing that of Jam VM), including improperly implemented Java semantics, missing bytecode instruction handlers, and the compiler (instruction selection, liveness analysis, register allocation). But it was fun, and extremely educative.

Did you know that a simple System.out.println() will make a whopping 650550 Java-method calls? That's using GNU Classpath for the Java API.

So we had to implement a lot of stuff just to make that work. In fact, we have so much infrastructure that we can even run a few other programs. And thus it was decided that it was time to make a release. The version 0.0.1 announcement:

http://thread.gmane.org/gmane.comp.java.vm.jato.devel/1725

The "next big" missing feature is garbage collection. I expect that'll be version 0.0.2. In other words, if you're interested in Java, garbage collection, or just compilers in general, you're welcome to join us...

Our team consisted of:

• Pekka Enberg; Original creator, project manager and mentor.
• Tomek Grabiec; His original project proposal included implementing exception handling, but he ended up somwhat like Ingo Molnar of the Linux kernel; Tomek also implemented a generic radix tree, implemented the basic threading support (java.lang.Thread), rewrote large parts of the register allocator, wrote the VM side of the JNI interface from scratch, and also did a lot of other core-VM work. Tons of other things too, including a lot of debugging.
• Arthur Huillet; Floating-point support, register allocator fixes, other missing bytecodes, also a lot of debugging. Various other things.
  
• Eduard-Gabriel Munteanu; Ported Jato mostly to x86-64. A tough task, since the i386 parts were moving at close to light speed.
  

kmemcheck in mainline

First of all, I should say that on April 22, I went to Denmark to give a talk on kmemcheck. I was invited to DIKU (Datalogisk Institut på Københavns Universitet) by Julia Lawall, who held a workshop on Coccinelle (or, more generally, "finding bugs in operating system software"). It was really nice to be there, not (just) because I got a chance to talk about kmemcheck, but because I learned so much from all the other talks! Feel free to check out my slides.

I had asked my university (the University of Oslo) beforehand to sponsor the trip in exchange for a trip report, but I got no reply to my e-mail. I guess they don't see any value in collaboration with universities abroad.

And now, for the news: Yesterday, kmemcheck was merged in mainline Linux! It is quite an incredible feeling after having spent so much time to make it work properly... (Not to mention the rebase marathon that ensued after Linus initially rejected it)

I had also asked Redpill Linpro (a Norwegian/Swedish open source developer) beforehand to sponsor my work on kmemcheck for the summer, but they apparently weren't interested. At least I got a polite reply. (Instead, I got a stipend from Google for working on Jato for the summer, but more on that in a later post!)

Hiragana tutor

An evening spent with Unicode charts, HTML, CSS, and JavaScript resulted in this:

The online Hiragana tutor

If you find any errors, please tell me.

LADSPA

Hurrah for LADSPA.

I started (yet another) project, this time it's a sort of audio synthesisizer and sequencer library. I've always been fascinated with digital audio, since there are so many cool things we can do with it! Like e.g. create and apply filters, warp the sound waves any way we want, add cool effects, and generally do things that I can't otherwise do. Not to mention that I like music... but who doesn't? :-)

My program isn't revolutionary in any way; in fact, the short story is that the program tries to "simulate" the way real, analogue audio components can be put together, as e.g. an effect rack (the guitar connects into a distortion module, which connects into a reverb module, which connects to the amplifier, which connects to a mixer board, which connects to the speakers, etc.). I stole most of the concepts from an existing non-free (but very nice) program called Reason [http://www.propellerheads.se/]. I'm sure there are also free programs that do what I'm trying to do (but part of the fun is doing it myself).

One really nice thing is that there exist a lot of free plugins that do most of the work when it comes to synthesizing instruments and applying effects. These plugins are implemented using a free library, called LADSPA (Linux Audio Developer's Simple Plugin API) [http://www.ladspa.org/], which is the interface between host programs (such as the one I'm making, but also others, like Audacity) and the plugins.

So the plugins form a directed, acyclic graph, where the nodes with no outgoing edges are the speakers (or, well, sound card), and the leaf nodes are typically synthesizers (instruments). Arranging the plugins in this way is a really nice thing, because it ensures that there are no vicious feedback cycles (if we really want some kind of feedback, like reverb, we can implement it as a plugin!) It also means that we can do a topological sort to find the order in which the plugins are to be "run".

Anyway, I've implemented these plugins for my program: A LADSPA plugin wrapper, so we can load any LADSPA plugin as a plugin for my program. An ALSA playback plugin for playing audio in real time. A WAV playback plugin for streaming to disk using libsndfile, which supports a few more formats beside WAV, by the way. A MIDI input sequencer, which reads MIDI files and presents the notes as "control output" to the synthesizer plugins. A mixer plugin, which simply combines several inputs into one output.

It would probably be possible to create an ALSA capture plugin for capturing audio in real time as well. That would be pretty cool, and we'd have a software guitar amp in no time. There seems to be a problem with using blocking ALSA streams, though, because the application sleeps while the sound card is playing the data, and we're left with almost no CPU-time to actually synthesize the sound. This can probably be solved using threads, though.

Anyway, I made something cool (I think, anyway), by hooking the CMT organ [http://www.ladspa.org/cmt/] to a plate reverb [http://plugin.org.uk/], and feeding some classical pieces into the MIDI sequencer (which now supports polyphonic songs!):

• Mozart's "Rondo Alla Turca"
• Bach's "Toccata et Fuga"
  

Will probably work some more on this, try to write some plugins (I have a few ideas), actually implement error handling (oops), and try to add the missing fundamental features (like reading the correct MIDI tempo, stop output at the end of the MIDI file, etc.).

One of the goals of the library is to be small and efficient, and not accept inferior solutions because they're easier to implement (some trade-offs are allowed). The next major feature will probably be to add multi-core support using pthreads, so that all CPU cores can be utilized.

The code itself can be found at github (as usual): http://github.com/vegard/trick2

Chipmunk experiments

I've been playing with Chipmunk lately. It is a C library that simulates physics in two dimensions, and is intended for use in games. It's quite easy to use, but there is a bit of overhead in setting up graphics since I have to do that on my own. I'm using OpenGL through the SDL library, and it works quite smoothly. Here is the result of today's dabbling:



There are two important fundamental concepts in Chipmunk: Bodies and collision shapes. What is the difference? A body has the usual properties like mass, position, velocity, etc. However, a body does not have an area (a shape). That is the purpose of collision shapes. A collision shape does not have any of the properties of a body, it merely defines a shape (such as a circle or a rectangle). The relationship between these two concepts is that multiple shapes can be attached to a body. Only shapes can collide; bodies do not collide by themselves.

The balls in the video above were constructed using one collision shape (a circle shape) for each of the three bodies. They were rendered using an 8x8 OpenGL 2D texture (loaded from a PNG image) on a quadrilateral (GL_QUADS). Easy as pie.

The rope was more difficult to make. For a long time, the rope would either disintegrate slowly (because it was being pulled apart by gravity), or explode (the line segments would vibrate quite violently).

When making the rope, we need another fundamental Chipmunk object: The joint. Joints are used as constraints in the simulation. A constraint is something that keeps an object from moving freely. There are different kinds of joints: Pin joints, slide joints, pivot joints, and groove joints. For example, the pin joint simply stitches together two bodies at certain offsets from the body's centre. When one body moves, the joint will cause the other to follow.

My rope uses slide joints. The only difference from a normal pin joint is that the joint allows a certain flexibility: The "stitch" can be given a minimum and a maximum length, so that the bodies can get closer together or further apart before the joint's constraint takes effect. We can easily imagine the maximum length property as that of a string connecting two objects. The string will keep the objects from getting too far apart, but it will also bend if the objects are closer together than the length of the string.

The slide joints connect the line segments of the rope. Each line segment consists of four collision shapes attached to a single body. The four collision shapes are all circles, laid out side by side. These four circles have fixed positions with regards to each other. They're not actually drawn as circles, but as solid rectangles (GL_QUADS). The rope has 30 such line segments, so that's 30 bodies and 120 collision shapes.

Finally, we have two fixed bodies at either end of the rope. These bodies have infinite mass, are not affected by gravity, and have no collision shapes. (Actually, they're not added to the Chipmunk space, so they are not affected by any forces at all.) This is what keeps the rope in place. And to my great surprise, the way in which these bodies are connected to the rope seems to be what determines the quality of the simulation. At first, I was using pin joints to connect these stationary bodies to the endpoints of the rope. It wasn't until I replaced them with slide joints that the rope actually got as smooth as it is in the video above.

I'm currently toying with the idea of putting a cart with wheels on the thread and controlling the wheels with the arrow keys. If that works, I think it could make for a nice game element as a variation on the paddle of e.g. Breakout.

Update:

Recursive type definitions in C

Hi,

It's been a while -- I've been mostly busy with university. Maybe I won't try to follow four classes next year. In other news, we didn't make it (with kmemcheck) for 2.6.28 either. Oh well. We did at least make an impression by discovering two more bugs in 2.6.28-rc.

Now for the topic of this post: Recursive type definitions in C. More specifically, the types I want to write about are not structs, but function pointers. We may use typedefs to define types which refer to function pointers:

typedef void (*funcpointer_t)();

Not strictly necessary to make it a new named type, but it helps readability. This is all well and good; we can declare variables that hold function pointers, declare functions that take function pointers as parameters, or even declare functions that return function pointers (to functions with this specific signature):

funcpointer_t x;

void do_a(funcpointer_t f);

funcpointer_t do_b(void);

Now, what I really wanted to do was to create a parser in C where a variable would hold the next function to call, and where the function itself returned a (function) pointer to the next function to call (i.e. the next state of the parser). It would look something like this:

funcpointer_t init_state(const char *token) {
   /* ... */
   return &some_other_state;
}

funcpointer_t some_other_state(const char *token) {
   /* ... */
   return &some_other_state;
}

void parse() {
   funcpointer_t state = &init_state;

   while (token = read_token())
       state = state(token);
}

Okay, so this looks quite good. But how do we define funcpointer_t? Defining structs that have pointers of the same type is quite easy, since the compiler already knows about the type as soon as you start defining it. The most obvious example is the linked list:

struct list_node {
   struct list_node *next;
   /* ... */
};

Another possibility includes forward declarations, where we simply declare that a type exists, without defining it:

struct a;
struct b {
   struct a *x;
};

The same goes for functions. They can refer to themselves, since we must provide their name at the start of their definition, or declare them beforehand. But how can we do this with function pointers?


Vegard

"Scribe" and cross-compiling for Windows

Hi,

First of all: Scribe. That is my new pet project. Actually, I don't know how serious it is yet. But I've made a Project out of it; maybe somebody else who is interested will come along and help. We'll see.

But what is it? Well, it's really just a demo so far. A demo of a "3D pixel engine". It started out as an experiment to see how the graphics from "The Legend of Zelda: Link's awakening" would look in 3D. So I took the Link sprites and some desert tiles and wrote a C++ program that used OpenGL to render it in perspective. And it looked quite good. Well, I must admit that I'm a huge fan of pixel art. It's just so incredible how much spirit and soul you can put into a 16x16 bitmap! And most 3D games out there use high-resolution textures with bilinear filtering and who knows what else to try to make it look halfway realistic...

I actually wrote this code around the end of October 2007 (just before I started working on kmemcheck), and it's been lying in my "programming" folder ever since. I recovered it the other day and thought that I should publish it as an open source/free software program, simply because I have no reason not to. I probably won't have that much time to develop this further, but maybe somebody else will find it interesting and pick it up. It's open source, these things do happen!

There was one major hitch, though. I can't distribute the Zelda graphics. And copyright law has to be upheld! (As an open source/free software programmer, what other position can I take?)

I decided to look around the net for some free graphics, and free graphics I found! In particular, I found bubble league, the website of Alan Trullinger. Apparently he had planned to make some RPG game and had spent a summer making the graphics for it. Apparently, the game was also never released, so he gave away all the graphics for free (distributed under the Creative Commons license). This is how my program looks using his files:



That's not too bad, is it? The little guy can walk around and jump. (The animation is an incredible piece of work, with 8 frames worth of animation in each direction!)

(Of course, nothing beats the Zelda graphics, but that's a different story.)

Are you interested in trying it out? Perhaps you are even interested in contributing something to it? In either case, I've created a git repository for the project at http://github.com/vegard/scribe/.

(Side note: GitHub is a really nice place. I haven't used it that much yet, but everything there is easy and pleasant and just works. It's really worth trying out if you're looking for git hosting. End of note.)

All right. On to the second part of this post: Cross-compiling programs for Windows on Linux. Did you ever try to build MinGW on Linux, only to discover after hours of compiling the compiler, that it doesn't really work? (I don't remember exactly what went wrong, maybe it was missing Windows headers, or missing Windows libraries, or something. I must have suppressed the memories.) Well, there is a solution to that problem too.

Use Wine! I installed Dev-C++ on my Fedora Linux using Wine. Then I created a project inside Dev-C++, imported my source code, installed a few Devpaks, and... it worked. A slight (but only slight) elaboration of this process can be found in the Win32 build instructions for "Scribe".

The only problem I had was that the program wouldn't link unless the linker directives were put in the right order. But that's shame on me for being spoiled with shared libraries (I built with -static to avoid DLL hell).

Notes on source code preprocessing

(This post contains some reflections on the hypothetical design of an ideal programming language...)

Don't use or support the use of preprocessing source code. Preprocessing means that all the tools which operate on the source code (including editors, compilers, static analyzers, etc.) will necessarily need to either support preprocessing themselves, or call the preprocessor before operating on the resultant source code.

Consider, for example, a simple tool that parses C code and searches for a given text in all the literal strings found in that code. If the source code needs to be preprocessed, then certain parts of the code may not be searched if the part in question is contained within the equivalent of a C-preprocessor #ifdef/#endif block. On the other hand, if we want our tool to also find strings inside these sections, then we can no longer use a C parser because #ifdef and #endif are not recognized by the C parser proper.

(The solution to the problem might include using regular expressions as a kind of heuristic to determine where the strings are, and then do concatenations, etc. However, this is only an approximate solution, and is in general not entirely satisfying. What about the more complex task of looking for specific variable or function declarations? In fact, a number of such tools have had to deal with variations of this problem; see for example LXR and Coccinelle.)

Multiple, different types of preprocessors also don't mix very well. For example, as an extension to many programming languages, the source code is preprocessed so that SQL queries are substituted with the (possibly verbose) support code which would otherwise be needed to prepare and execute the query in question. Now we have exactly the same problem as mentioned above, which is that support tools (editors, compilers, etc.) will have to either support the preprocessor language or (more likely) always operate on already-preprocessed source code, with all the aforementioned drawbacks. In some cases, the order of preprocessing will also become significant, or different preprocessor languages might be incompatible.

Another practical aspect of preprocessing is that the code which is inside such #ifdef blocks will be compiled only conditionally; the compiler might not even look at it. This means that the compiler is a lot less useful than it could be. It is one of the main tasks of the compiler to inform the programmer when he/she is writing something which is internally inconsistent, such as calling a function with the wrong argument types. (This is entirely possible if there is a caller of the function inside an #ifdef block and the definition of the function was later changed to take different arguments.)

In conclusion, I think C/C++ could have done a lot better in this area. On the other hand, a lot of other programming languages did get it right. But maybe the need for alternative compilation is greater in the lower-level languages and it's really just a trade-off between performance and usability.