HTML5 video playback: Ogg/Theora or MPEG4/H264 (and a GIF story)

Do you remember GIF? You see some pictures on the web from time to time, rarely. The GIF format was pretty good for its time - it had lossless image compression (pretty good I might say), it had animations, transparency - pretty much anything you might want from an image on the web. And it was widely used in the '90s websites. And then, came Unisys, who remembered that, well, it had patents on the GIF compression method, and they wanted some money from those who used it. Just remember this campaign: Burn all gifs.

Their patent expired in 2003/2004, but some threats still linger. And nobody will use GIFs now, because, well, they were bested by the PNG format (and the lesser used MNG format). And even if I am old enough to remember the story, and yet I'm only 30, nobody seems to remember this story.


And the story happens again.This time it's not images, it's videos. And it's not like we have to make up an alternative FAST, like we did with the PNG format. The alternative is here, it's called Theora. Yes. I'm talking about the H264 standard used nowadays by Google or Vimeo to stream video over the internet, and that is now being pushed as 'HTML5' (although the HTML5 didn't specify the precise codec for the video playback). Ok, so what's the problem (aside from the fact that Mozilla won't support HTML5 H264 rendering?) Well, the problem is that soon enough, if you'll have a site and you want show some videos on it, you might be forced to pay for the use of the codec. Probably not what you have in mind.

A clearer article about this issue you can read from here; please also sign the petition addressed to Google to support in Ogg/Theora in youtube.

Linked list complexity redivivus

Because fast doesn't always mean simpler, sometimes we have to get very very dirty.

Yesterday we left the problem of the memory allocation in suspense. Today we will try to get deeper in the muddy waters of O(1) allocation. And then, some unicorns.

Since we know that we cannot dream of constant time memory allocation (unless unicorns are involved) the best idea would be to preallocate the items in a single batch. So, let's say that we need maximum 10.000 elements, we allocate space for those maximum 10.000 elements from the beginning with a single malloc.

Good, but how do we actually take from that memory pool elements in constant time? Well... Theory has it that we could use a linked list for that ;)

Nobody tells us that the creation time has to be small, right? So when we allocate the space for those elements we can link together those elements, right?

node *mem_pool_create (int maxelem)

{

   node *head = malloc (sizeof (node)*maxelem);

   int i;

   if (!head) return NULL;

   for (i=0; i= 1 */

      head[i]->next = head+(i+1);

   head[maxelem-1]->next = NULL;

   return head;

}

/* bingo! Constant time! */

node *mem_pool_extract (node **pool_head)

{

   node *ptr;

   if (!pool_head || !*pool_head) return NULL;

   ptr = *pool_head;

   *pool_head = ptr->next;

   return ptr;

}

/* by re-adding the node in front we make sure the nodes

 * won't get too scattered in memory - and we might take

 * advantage of the processor cache */

void mem_pool_retake (node **pool_head, node *ptr)

{

   if (!ptr || !pool_head) return;

   ptr->next = *pool_head;

   *pool_head = ptr;

}

Use these calls instead of malloc/free. When memory gets thin... well, that's a discussion for tomorrow, maybe. :)

What we could do is see how we can optimize the memory pool creation. A simple idea could be used: Instead of writing the next pointer for all the elements in the beginning, we can keep a mark of 'how much we have written so far', in the pool definition. One example of such modification below:

typedef struct {

   node *initial_head;

   node *head;

   int maxelem;

   int maxused;

} mem_pool_t;

mem_pool_t *mem_pool_create (int maxelem)

{

   mem_pool_t *pool;

   int i;

   pool = (mem_pool_t *)malloc (sizeof (mem_pool_t));

   pool->head = (node *)malloc (sizeof (node)*maxelem);

   pool->initial_head = pool->head;

   pool->maxelem = maxelem;

   pool->maxused = 0;

   if (!pool->head) {

      free (pool);

      return NULL;

   }

   pool->head->next = pool->head + 1;

   return pool;

}

node *mem_pool_extract (mem_pool_t *pool)

{

   node *ptr;

   if (!pool_head || !*pool_head) return NULL;

   ptr = pool->head;

   pool->head = ptr->next;

   ptr->next = NULL;

   if (pool->head && pool->head - pool->initial_head >= pool->maxused) {

      pool->maxused ++;

      if (pool->maxelem>pool->maxused)

         pool->head->next = pool->head + 1;

      else

         pool->head->next = NULL;

   }

   return ptr;

}

void mem_pool_retake (mem_pool_t *pool, node *ptr)

{

   if (!ptr || !pool) return;

   ptr->next = pool->head;

   pool->head = ptr;

}

Update: I got a bit sloppier with the retake, updated the right code :)

A question of execution time

We all know that the complexity of algorithms we use influences a lot the performance of our programs.The difference between having linear time algorithms and having constant time algorithms is seen quite soon, after the first hundreds of items.

So here's a simple question. What's the complexity of adding an element at the end of a linked list? The naive answer usually is 'constant time'. But let's check the usual implementations.

Let's assume we have the structure:

typedef struct _node {

  int value;

  struct _node *next;

} node;

Implementation 1:

void add (node **head, int value)

{

   node *new_node, *ptr;

   if (!head) return;

   new_node = (node *)malloc (sizeof (node));

   new_node->next = NULL;

   new_node->value = value;

   ptr = *head;

   while (ptr && ptr->next) ptr = ptr->next;

   if (ptr)

      ptr->next = new_node;

   else

      *head = new_node;

}

This implementation is clearly NOT in constant time because, well, we have to start from the head, get all the way to the end of the list and add the element there. Time: O(n). At least. More later.

The obvious fix would be to also have the tail of the list. To make the tail available as well. So let's expand our data structures with a 'list' structure that will contain the head and the tail.

typedef struct {

   node *head;

   node *tail;

} list;

Implementation 2:

void add (list *l, int value)

{

   node *new_node, *ptr;

   if (!l) return;

   new_node = (node *)malloc (sizeof (node));

   new_node->next = NULL;

   new_node->value = value;

   if (l->tail) {

       l->tail->next = new_node;

       l->tail = new_node;

   } else {

       l->head = l->tail = new_node;

   }

}

Great! Problem solved! We have constant time for adding. Don't we? Begginer's luck, we're safe at bay!

...

...

Oh wait...

...

...

What is the execution time of malloc?

Oh sh**.

Good, now that we found out that it's not so easy to do that, we can say goodbye to the idea that a dynamically allocated linked list does not have the possibility to add an element in O(1) simply because we have to allocate the element. In academia it's a good and nice O(1) solution, in RealLife™ it's not. So what do we do?

The solutions I found so far are not perfect by far. First solution would be to have something like a smart pool that will give us the elements in a more or less constant time (one idea would be to have a buffer of more node structures, and then one could perform a circular search from the last 'allocated' node). Another solution would be to not do dynamic allocation at all, but that defeats the purpose of having a linked list in the first place.

One reminder. Never forget that just because you have a one liner doesn't mean that the execution time for that line is constant. And memory allocation can be one of the most critical operation for the performance of your program

.bin/.cue to ISO or CDR (audio tracks)

Coming from the windows world, a lot of applications ;) come as .bin/.cue archives instead of the classical .iso format that we all love. Fortunately there is a simple solution called bchunk that will allow you to easily transform the bin/cue archive into an ISO archive. Invokation is simple:
bchunk file.bin file.cue file - and it will output file.format (ISO/UGH) or CDR audio tracks. :)
See the manual page for more infos. Nice tool, simple and effective. Loved it.

(k)ubuntu StarCraft

I haven't played the game in quite a long while, and I said I should give it a shot, now that there's the new year and some time to waste.

The only way to do it cleanly on Linux is, of course, to use WINE, the other option being a virtual instance of Windows (which is not as fun as people might think. So I mounted the Starcraft CDs (Broodwar as well) installed them and played them.

First problem: no sound. After restarting with OSS checked as the default for wine in winecfg, the sound worked again - but unfortunately, I can't reproduce the reasons why the sound didn't work (this really sucks, does anyone listen?).

Second problem: after a short while, the mouse moved incredibly sluggish and it was a very unpleasant experience to play the game. This problem is a known problem among the WINE users, and after checking the winedb informations, I found out that you need to create the following registry entry:
HKEY_CURRENT_USER/Software/Wine/Direct3D , string entry: DirectDrawRenderer, value "opengl" (without the quotes). To edit this entry, run regedit. After running again the game, it worked smoothly.

Third problem: the disk kept spinning in my drive, and I really, really hate that. Actually, one thing I hate about the games I buy is that they force me to use their disk (with the notable exception of Guild Wars, which has an internet authentication, thus it doesn't need to do that). This was so annoying I had to search a no-cd patch for Starcraft. And I found it. Offered by Blizzard. It seems that if you apply the patch for version 1.15.2 or later (1.16.1 was the version I used) they let the game work without the CD - you just have to copy the file install.exe from the StarCraft original CD as the file "StarCraft.mpq" in the Starcraft installation folder, and the file install.exe from the BroodWar CD to the file "BroodWar.mpq". Again, no quotes.

One problem, and an annoying one, if you ask me. The patch will automatically close your session and throw you in the login screen. I don't understand why, so if possible (internet available) make sure that you patch your game via Battlenet rather than running the patch. :)

Run it, and it works. No CD, and smooth, just as you wanted it. En taro adun, Executor!

Now I wonder... Does Blizzard have a no-cd patch for Warcraft II as well? :)

PS: for Warcraft II you have to mount the disk by hand. My solution after I made the disk image was to have a script as such:
#!/bin/bash
sudo mount -o loop "$HOME/Games/Warcraft II BNE/war2bne.iso" "$HOME/Games/Warcraft II BNE/CD/"
pushd $HOME/Games/Warcraft\ II\ BNE
./Warcraft\ II\ BNE.exe