Older blog entries for fzort (starting at number 96)

30 Dec 2007 (updated 2 Jan 2008 at 11:20 UTC) »

Merry solstice, everyone.

Beowulf Movie

Soulless two hour-long videogame cutscene. Avoid.

Coroutines in C

Ran into a design issue while working on this programming problem.

I'm storing words in a trie:


struct trie_node {
        const char *key;
        struct trie_node children[NCHILDREN];
};

... and the procedure that enumerates all words in the trie that correspond to a given sequence of digits is naturally recursive:


static const char *digit_to_char[] = {
        "oqz",
        "ij",   "abc",  "def",
        "gh",   "kl",   "mn",
        "prs",  "tuv",  "wxy"
};
 
/* print out all words in the trie that match a sequence
   of digits */
void find_matches(const struct trie_node *node,
  const char *digits)
{
  const char d = *digits;
 
  if (node->key)
    puts(node->key);
 
  if (d != '\0') {
    const char *p;
 
    for (p = digit_to_char[d - '0']; *p != '\0'; ++p) {
      int next = *p - 'a';
      if (node->children[next] != NULL)
        find_matches(node->children[next], digits + 1);
    }
  }
}

Now, we don't want to simply print out the words, we want to use them to solve the problem, so they must be passed to the problem solving code somehow. We have many options here (mixing the problem solving code with the trie-traversing code does not count as an option):

  • Pass a pointer to a callback function to find_matches; where it now prints out the match, it would call this function for every word it found. This is the C way of doing things.
  • Turn the function find_matches into an iterator - we'd have a struct to store the search state, and a "method" to return the next match (I actually went with this approach in my solution, and it was accepted). Unfortunately, this means turning our clean recursive code into a stack-based state machine monster.

Another, perhaps less well-known, alternative would involve co- routines. Where find_matches now prints out a result, it would return the result back to the caller; when it gets called again, the state of find_matches is restored to how it was before the return.

While in Scheme we could do this with call-with-current-continuation, there doesn't seem to be a portable or easy way to do something like this in C. Simon Tatham presents a clever trick using Duff's device, but, alas, it doesn't help us in this case, since find_matches is recursive. There are also a couple of co-routine libraries for C out there. I had a bit of fun with bi over ICQ yesterday fixing this one to make it work with newer versions of gcc (bi sent a patch to the author).

Anyway, here are two solutions to the original problem - one of them uses an iterator, and another one uses a co-routine hack built on top of pthreads, inspired by this article (pretend the cr_* stuff at the beginning of the source file is hidden in a library, and the user is not even aware that threads are involved).

Represent.

The point that mathematics is the only way is controversial. People say that this does not apply to software. But you could not possibly write software to build airplanes without mathematics. You cannot write software that does 3D graphics without it. You cannot write database software without mathematics. You cannot write a compiler without mathematics. What kind of programs are not mathematical? Programs that are insecure, programs that crash, programs that cannot be easily modified are examples of non-mathematical software. There is, of course, a solid economic reason for producing such programs: they assure world domination on a large scale and job security on a small scale.
-- Alexander Stepanov, "Foundations of Programming" course notes
12 Dec 2007 (updated 21 Apr 2009 at 21:02 UTC) »

[elided]

On other news, started working on a game last weekend, based on a bizarre concept had while daydreaming in a bus stuck in a traffic jam (screenshot). It's sort of playable. All that's missing are more attractive graphics, music, sound effects, some text, a better user interface, and variable difficulty levels. Piece of cake.

23 Nov 2007 (updated 23 Nov 2007 at 10:40 UTC) »

Released vulcan version 0.9, fixing, among other things, an embarrassing Makefile bug. (Sorry for that. At work, on lunch breaks, I develop and test it on Cygwin running X, with Mesa. Apparently you don't have to link to libm to use sin, cos and the like in that environment.)

Decided to work again on a shoot-em-up game I started a while ago (screenshot, code so far). Being a shoot-em-up, it will have to eventually include things to shoot at.

This programming thing is fun.

21 Nov 2007 (updated 21 Nov 2007 at 14:42 UTC) »

vulcan 0.8 released. The next version will look nicer, I promise.

This Linux spoof (linked by Nymia) of Apple's ads is pretty funny. "Switch to, uh, whatever the hell you want."

Google wants me to install a "spyware remover" on Linux. I get this crap every time I try to use it from home. I've been using Yahoo for web searches exclusively there.

15 Nov 2007 (updated 15 Nov 2007 at 12:14 UTC) »

Please keep your images out of Advogato's recentlog. I'm sooooo interested in the 18 pictures of whatever you had for lunch in your trip to Disney World.

Speaking of bandwidth, the Moon images and videos taken from Kaguya's HDTV camera look incredible. The "Earth-set" video is so beautiful.

On other news, I haven't had a lot of hacking time lately, been studying for a stupid Oracle certificate in my scarce non-work hours. Stupid, but hopefully it will make my resume more sellable.

14 Nov 2007 (updated 21 Apr 2009 at 21:02 UTC) »

[elided]

8 Nov 2007 (updated 8 Nov 2007 at 11:22 UTC) »

Yay. A google search suggests that my little project was packaged for at least four obscure linux distributions.

ingvar: stay away from ProjectEuler. It's made of evil! (I'm mpersano there. Solved 110 problems. I'm clean now, though.)

New version of vulcan released. Live long and prosper, or something.

5 Nov 2007 (updated 5 Nov 2007 at 10:22 UTC) »

I'm adding some gratuitous eye candy to vulcan. This makes things even more confusing than they already are, but I've been meaning to experiment with that stuff for a while. It will make screenshots for sites such as freshmeat look a bit nicer, but I'll probably make it an option that will be turned off by default.

More importantly, I replaced the 3d models with free ones, taken from the xscreensaver mode "endgame" (which, in turn, took the 3d models from glChess). Not only are these models free, but they also look much nicer than the ones I was using.

New version to be released Real Soon Now.

87 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!