OpenAL - sounds good!

For getting sound to work on the iPhone, I needed to acquaint myself with the OpenAL sound system. OpenAL is also particularly interesting because it is a 3D sound system. You set the position of a sound source, and OpenAL will take care of getting the volume just right, as well as the "position" of the sound where you are perceiving it to be coming from, when you hear it played on your surround set. It can also do cool things like the doppler effect. While I do not need 3D sound and just have started using OpenAL, it would certainly be cool to get some simple stereo sound effects in my game. This is something that SDL_mixer can not do.

OpenAL tutorials and ALUT

There are some nice tutorials on the web, and they all use ALUT. It turns out that ALUT had some (simple to resolve!) bugs in it, and some guys decided to mark it as deprecated. When standard C code gets marked as deprecated, gcc won't compile it anymore. So, now all those nice online tutorials don't work anymore. ALUT had two functions that were really convenient: alutInit() and alutLoadWAVFile(). Writing my own WAV loader took some time, but I managed, and initializing OpenAL properly takes some magic sequence, but read below about how that works.

Ubuntu Linux suxxors

First a sidestep from writing code; getting your system to work, and be able to produce sound at all. My favorite development platform is still Linux. For some reason, Ubuntu decided to break sound in version 8.10 (Intrepid) and I've been hassling with it for days to get some audio output out of my programs. At it turns out, Ubuntu Intrepid mixes asound (ALSA), esnd, and PulseAudio, with an apparent preference for PulseAudio, except that it's not properly integrated or set up or whatever, it just doesn't work in all cases. That's right, one program seems to work, while others don't. The solution: I removed all PulseAudio packages from my system, and installed their ALSA counterparts. (In fact, I compiled the mpd music player daemon by hand, because Ubuntu's version tried to use PulseAudio anyway). After taking these drastic measures, my sound programs produced audio output, hurray!!

Initializing OpenAL

As said, we are going to have to do without ALUT. OpenAL needs to be initialized by creating a "context" and selecting the audio device, otherwise you will get nothing but errors. In some tutorials, I found that you may select "DirectSound3D" as a device, but that obviously only works on Windows. I have no clue what devices are available on Linux, MacOS X, or whatever other platform you may think of. Luckily, there is a way to get the default device.

I'll share The Code with you:

#include "al.h"

#include "alc.h"

int init_openal(void) {

ALCcontext *context;

ALCdevice *device;

const ALCchar *default_device;

default_device = alcGetString(NULL,

ALC_DEFAULT_DEVICE_SPECIFIER);

printf("using default device: %s\n", default_device);

if ((device = alcOpenDevice(default_device)) == NULL) {

fprintf(stderr, "failed to open sound device\n");

return -1;

}

context = alcCreateContext(device, NULL);

alcMakeCurrentContext(context);

alcProcessContext(context);

/* you may use alcGetError() at this point to see if everything is still OK */

atexit(atexit_openal);

/* allocate buffers and sources here using alGenBuffers() and alGenSources() */

/* ... */

alGetError(); /* clear any AL errors beforehand */

return 0;

}

First a remark about the includes. Including the files "al.h" and "alc.h" is much more portable than using <AL/al.h> and <AL/alc.h>, and it saves you from resorting to "#ifdef PLATFORM_SO_AND_SO" constructs.

Using the default device may not always be the best choice. There should be an option in the program to let the user decide on what device to use.

Note the atexit() call; OpenAL will complain loudly when you exit the program without having cleaned up properly. It has a right to complain too; you've allocated some valuable hardware resources and it may be well possible that the operating system is not exactly babysitting this hardware, meaning that when you exit the program without releasing the allocated hardware buffers, they will remain as marked 'in use' until the computer is rebooted (!).

A good atexit() handler frees the allocated resources and closes the sound device.

#include "al.h"

#include "alc.h"

int init_openal(void) {

ALCcontext *context;

ALCdevice *device;

const ALCchar *default_device;

default_device = alcGetString(NULL,

ALC_DEFAULT_DEVICE_SPECIFIER);

printf("using default device: %s\n", default_device);

if ((device = alcOpenDevice(default_device)) == NULL) {

fprintf(stderr, "failed to open sound device\n");

return -1;

}

context = alcCreateContext(device, NULL);

alcMakeCurrentContext(context);

alcProcessContext(context);

/* you may use alcGetError() at this point to see if everything is still OK */

atexit(atexit_openal);

/* allocate buffers and sources here using alGenBuffers() and alGenSources() */

/* ... */

alGetError(); /* clear any AL errors beforehand */

return 0;

}

Mind the order in which to call OpenAL in the atexit handler, always first stop the sound, delete the sound sources, and then delete the buffers. Then move on to the context, and finally close the device. If you don't do it in this order, the sound system will not be properly de-initialized.

Loading .WAV files

Loading WAV sound files is easy, although there is one big gotcha to it: it is a binary format, stored in little endian format. The intel x86 line of processors are all little endian, so no problem there. However, I like to write portable code, so this is a bit of fun. I have the pleasure of having access to a big endian machine, so I could test my WAVE loader code there, too. I came up with a very simple test too see if a machine is big or little endian:

#include <stdint.h>

int is_big_endian(void) {

unsigned char test[4] = { 0x12, 0x34, 0x56, 0x78 };

return *((uint32_t *)test) == 0x12345678;

}

The is_little_endian() function is left as an exercise to the reader.

Back to the WAVE loader, what I do is simply read the whole file into

memory and then map a struct that represents the WAV header over it. Then I do the integer fixups (read as little endian values), and then perform some basic checks on whether this really was a good WAV file. For a music player, you should do these checks before loading the music data, but for my game code, I was happy with simply loading the file all at once.

You can find good information about the structure of a WAV file header on the web. Note how a WAVE loader is really a RIFF loader, and in my case, also a PCM sound loader.

There is a gotcha when blindly pouring the WAV header information into a struct, which is alignment. The compiler may mess around with the size of your struct ... use pragma pack to

instruct the compiler to refrain from doing that:

#pragma pack(1)

typedef struct {

uint32_t Chunk_ID;

uint32_t ChunkSize;

...

uint16_t AudioFormat;

...

} WAV_header_t;

#pragma pack()

I've noticed that there are quite a few WAV files out there that have little mistakes in the

headers, in particular the final field data_size (or subchunk2_size), which represents the length of the music data, is often wrong. The correct value is file size minus header size, and note that you can now 'repair' the WAV file.

Now that we've succeeded in loading the .WAV file, feed this data into alBufferData() and we're ready to make some noise.

Closing remarks

In this blog entry I've shown how you can survive without ALUT. Although SDL_mixer happily handles .mp3s, and many other formats, it doesn't give you the stereo and 3D sound that OpenAL does. For OpenAL, you will need to write your own sample loader. Painful as it seems, it is really just a good exercise in handling data formats.

In the devmaster OpenAL tutorials they show how to stream Ogg Vorbis files through OpenAL. Be sure to read all their tutorials, they're pretty straightforward once you've gotten through lesson 1. Also note how they rely on ALUT ... forget about ALUT. Use OpenAL, it sounds good.

Porting an OpenGL demo to iPhone

You may read this blog entry as "a beginners guide to OpenGL ES". Like many others, I wanted to write a cute little app for the iPhone. Also, like many others, I know nothing about MacOS X programming (the Cocoa API), so I quickly found myself lost in the woods. I do have experience with SDL and OpenGL, however, so I decided to port the infamous "WHYz!" demo to iPhone, using Apple's Xcode and iPhone simulator.

History of the WHYz! demo

The WHYz! demo is a story by itself. It is included here as background information and for the sake of story-telling. Skip this section if you are interested in the OpenGL ES code only.

Way back in them good old days, 1996, I wrote the first WHYz! demo on an 33 MHz 486 PC. It was meant as an electronic birthday card. During a dark night of coding, I rewrote the whole thing in 100% assembly code, hoping to squeeze a few extra frames out.

In 1997, I ported the C version to Linux using svgalib. I also played around with Qt around that time, but I don't think I ever made a Qt port of the WHYz! demo.

In early 2006, I was first trying out SDL and made an SDL implementation of the WHYz! demo.

In 2007, I made a completely new rewrite in SDL/GL. This version is different from the original, but demonstrates the same kind of wave effect.

Now the wavy WHYz! demo comes to the iPhone with OpenGL ES.

Taking the first hurdle: Objective-C

The iPhone's operating system closely resembles MacOS X. In MacOS X, applications are typically written in Objective-C. This is an object-oriented dialect of C. When you see Objective-C code for the first time in your life, your stomach will turn and your eyes won't know where to look and you will feel dizzy. Remember this: Objective-C is much like C++, only with a different syntax. Readers of this blog may know I have already expressed my aversion of C++, well, Objective-C is even less prettier on the outside. On the other hand, the first impression is not everything. Objective-C seems to come with a very nice API, that is going to cost time and dedication to master. At this very moment, life is too short to spend valuable time on this, so lucky for us, it is possible to mix standard C with Objective-C, just like it is possible to write "C++" code in standard C, and only benefit from the handy "// comment" C++ syntax.

So, we will have Xcode generate the startup code for the main application for us, and call our good old standard C code from there. Cheating? No, just not rewriting working code in a dialect that I don't speak.

Taking the second hurdle: SDL for iPhone

As my existing code is all SDL/GL, I really need SDL for iPhone. How else would we setup the screen, handle input events from the operating system, play sound, and finally, render out OpenGL scene? As of yet, the answer is ... you don't. Maybe I didn't look hard enough, but I did not find a SDL library for iPhone. It appears to be in development. For this demo, I managed to do without SDL, but things will be much harder when trying to port a full blown game.

For setting up the screen: Let Xcode generate an EAGLView.m for you. Insert your own init_gl() routine to setup the viewport, and reset the projection and model view matrices.

Input events: The demo doesn't need input, but I'm sure Apple has some neat CoreInput or whatever framework for this.

Play sound: Not used in the demo, but they say you should use OpenAL, which sounds nice. OpenAL is portable and doesn't look hard to use.

Render OpenGL scene: Insert your own draw_scene() code into the EAGLView drawView() method.

All done? NO, the best is yet to come. Hit the "Build and go" button in Xcode and you will get a ton of errors on OpenGL calls.

Hurdle #3: The limitations of OpenGL ES

OpenGL ES stands for "OpenGL, Embedded Systems". Mobile devices are always relatively slow, simple, low-power computers. In the beginning, there would not even be a FPU. If your mobile device has no FPU and therefore only implements OpenGL ES 1.0, you are stuck with fixed point calculations. Lucky for us, modern mobile devices like the iPhone are capable of doing floating point calculations in hardware.

The graphics chips in mobile devices are also real simple compared their mean big brothers in gaming PCs. The OpenGL ES API has been slimmed down to mirror this.

Just to annoy developers, the great creators have altered a fundamental concept of OpenGL, only to force people into writing more efficient code. Shocking news: in OpenGL ES, there is no glBegin()/glEnd(). There is no glVertex(). There is no glTexCoord(). Argh!

There are only glDrawArrays() and glDrawElements().

(By the way, remember my OpenGL optimization lesson? Use glDrawArrays() to speed things up a little).

There is not even glFrustum() and glOrtho(), but their callings have been made more consistent with the rest of the API; call glFrustumf() and glOrthof().

There is no polygon mode, so no more cool debugging in wireframe (my absolute favorite polygon drawing mode). Well, you can do it, but not through glPolygonMode().

There are no quads, only GL_TRIANGLE and GL_TRIANGLE_STRIP remain.

There are no display lists, use a subroutine as workaround.

You can not push/pop attributes. The programmer should be knowing what the state is at all times, and he should be knowing what he's doing anyway. Just like in the real world.

There is no full set of color manipulation routines, only glColor4f().

There is no GLuint, only GLfloat.

Oh yeah, and you have to find the right include somewhere, too.

This leaves you with a rather big mess of cool OpenGL standard code, that just doesn't work in OpenGL ES. I guess you could write a set of macros that converts existing code to ES, but I'd rather stay away from this headache. Nothing remains but to go through the code and do the tedious work of converting each and every block of OpenGL code to ES.

Taking hurdles: Converting existing OpenGL code

Converting the existing code is mostly looking for glBegin()s and putting all glVertex()s into a vertex array. Finally, call glDrawArrays(). I will give a 2D example for the sake of simplicity:

/* old code, in some kind of orthogonal coordinate system */

#include "SDL_opengl.h"

glBegin(GL_TRIANGLE_STRIP);

glTexCoord2i(0, 0);

glVertex2i(-1, 1);

glTexCoord2i(0, 1);

glVertex2i(-1, -1);

glTexCoord2i(1, 0);

glVertex2i(1, 1);

glTexCoord2i(1, 1);

glVertex2i(1, -1);

glEnd();

New:

#include <OpenGLES/ES1/gl.h>

GLfloat vertex_arr[8] = {

-1.0f, 1.0f,

-1.0f, -1.0f,

1.0f, 1.0f,

1.0f, -1.0f

};

GLfloat tex_arr[8] = {

0.0f, 0.0f,

0.0f, 1.0f,

1.0f, 0.0f,

1.0f, 1.0f,

};

glEnableClientState(GL_VERTEX_ARRAY);

glEnableClientState(GL_TEXTURE_COORD_ARRAY);

glVertexPointer(2, GL_FLOAT, 0, vertex_arr);

glVertexPointer(2, GL_FLOAT, 0, tex_arr);

glDrawArrays(GL_TRIANGLE_STRIP, 0, 4);

I was lucky that my code already used triangle strips ...

If you use display lists, convert those to subroutines. You will lose the performance benefit that glCallLists() has. My guess is that mobile devices lack the GL "compiler" and cache memory that are needed for display lists.

Simply delete calls that set the polygon mode. If you need to draw lines ... pass GL_LINES to glDrawArrays().

Finally, search your source for "glColor" and replace all by glColor4f().

glColor3ub(0xff, 0x80, 0);

becomes:

glColor4f(1.0f, 0.5f, 0.0f, 1.0f);

The final hurdle: Reaching the finish line

When I finally got the code to compile, it still did not work. One of the problems was, the textures did not load. The thing is, on MacOS X, applications and data files are part of a bundle. If you want to load a texture, you have to access the bundle using the NSBundle class in the Cocoa library. Since my code is based on fopen(), I chose to cheat and not use the NSBundle class. At startup, I do a chdir(dirname(argv[0])) and find my texture files there. This is quite ugly, as it manipulates argv[0].

I had another caveat that was pretty obvious after I figured it out ... I deleted the SDL resize_window() code from the source. This routine also (re)initialized OpenGL in the proper way ... so I was trying to start out without having set the right coordinate system (oops).

When this was fixed, I could now happily enjoy watching the WHYz! demo in the iPhone simulator. (Yeah, it's time to go buy a real iPhone ...)

Networking, routing, and bit masks

Last week I got funny little assignment through a colleague of the Networking department. They've got a huge set of routes set in a major internet exchange machine in Amsterdam, and wanted to have a program to optimize the routes. Optimizing the routes is not only important for performance reasons, but also because of money — some connections are more expensive than others.

This assignment is interesting for a number of reasons:

• I feel like I haven't coded anything useful for ages
• I will not be writing the code, but designing it together with a co-worker, who will do the actual implementation
• Someone will actually be using this
• This will save the boss money (we could've been rich ...!)
• The internet might benefit from this, implicitly pleasing many people (the good folks at home)
• It involves some good old-fashioned bit-mucking about (and I love it!)

So, what does an internet route look like? Well, you've got the network address in an IPv4 decimal dotted quad notation, and the destination to route to also in IPv4 decimal dotted quad notation. So:

Network address Destination

10.0.1.0/24 172.16.3.91

10.0.2.0/22 172.16.4.1

10.0.0.0/16 192.168.2.2

Let's call these three routes A, B, and C. Now, let's pretend that using route A is more expensive than using route C. Anyone can see in this (pretty bad) example, that route C is such a large network, that it encompasses both A and B — the network address ranges of A and B both fit in C. Therefore, route A and B can be eliminated and we can cheaply use route C.

To be able to do this programmatically, one must realize that IPv4 addresses are 4 bytes. The decimal dotted quad 10.0.1.0 translates to 4 bytes (hexidecimal notation): 0A 00 01 00, or the 32 bit word 0A000100.

I like writing this in hexadecimal because the network range '/24' translates to a bit mask; '/24' means the first 24 bits of the 32 bit word are 1s, giving a bit mask of FFFFFF00. Likewise, a /22 gives FFFFFC00 and /16 is FFFF0000.

Why is this important? Well, it shows how the internals of the internet work, and why it is so fast. For example, a source IP address of 10.0.1.18 is bitwise AND masked with its network address, and it will match route A in the routing table. The packet is consequently sent to the configured destination (in this case, 172.16.3.91).

Finding the cheapest route now only breaks down to this:

• Find a route that has a smaller bitmask, but still matches the address
• The route has to be cheaper in terms of cost, we don't like spending more money

We can see that route C fits these criteria for A and B:

10.0.1.0/24 => 0A000100 AND FFFFFF00

10.0.2.0/22 => 0A000200 AND FFFFFF00

10.0.0.0/16 => 0A000000 AND FFFF0000

0A000100 AND FFFF0000 == 0A000000, so route A fits in C

If we would have a route D like 10.10.0.0/16, it would not fit in C:

10.10.0.0/16 => 0A0A0000

0A0A0000 != 0A000000, so route D does not fit in C.

As you can see, routing is just simply bitmasking and using a lookup table (the "routing table"). If there is one thing that hardware can do fast, it's bitwise AND operations.

I came up with a funny statement that creates the bitmask from the slash-notation:

((1 SHIFTLEFT (32 - numbits)) - 1) XOR FFFFFFFF

This is overly complicated. It is possible to look at it in another way; e.g. with a /16 all the left-hand side bits are set, and all the right-hand side bits are clear. So it is possible to start with all bits set, and shift the clear bits in from right to left:

FFFFFFFF SHIFTLEFT (32 - numbits)

Be mindful that this works only for 32 bit registers, otherwise the mask will overflow. You can prevent this be explicitly selecting the least 32 bits:

(FFFFFFFF SHIFTLEFT (32 - numbits)) AND FFFFFFFF

We can do even better than this. There is a cool operation named arithmetic shift right which is ideal for the job, but it is not present in all programming languages. The arithmetic shift right copies the highest bit into the next bit, which is exactly what we want:

80000000 ARITHMETICSHIFTRIGHT (numbits - 1)

Just for the fun of it, I thought about implementing this in assembly language. There are many implementations possible, depending on what CPU you are programming. Just for the kick of it, I picked a 32 bits ARM processor. You have to be a bit clever with the bit operations, especially on this system.

@

@ first solution, using (-1 SHL (32 - numbits))

@

LDR R0, numbits

MOV R1, #32

SUB R1, R1, R0 @ R1 is (32 - numbits)

MVN R0, #0 @ R0 is FFFFFFFF

MOV R0, R0, LSL R1 @ R0 becomes the bitmask

@

@ second solution, using an arithmetic shift right

@

MOV R0, #1

MOV R0, R0, LSL #31 @ R0 has only highest bit set

LDR R1, numbits

SUB R1, R1, #1 @ R1 is (numbits - 1)

MOV R0, R0, ASR R1 @ R0 becomes the bitmask

Note that the routing theory holds true for IPv6 as well, except that for IPv6, you have to work with 64 bits addresses rather than with 32 bits addresses.

Parallel programming with pthreads

Today, we had a little conversation about pthreads programming in the office. Every now and then the topic of pthreads seems to come up. Surprisingly, I'm one of very few who actually has had some hands-on experience with it. I remember that learning pthreads was difficult because there were no easy tutorials around, and I didn't really know where to start. There is a certain learning curve to it, especially when you don't really know what your doing or what it is you'd want to be doing with this pthread library.

A thread is a "light-weight process", and that doesn't really explain what it is, especially when they say that the Linux kernel's threads are just as "fat" as the processes are.

You should consider a thread a single (serialized) flow of instructions that is executed by the CPU. A process is a logical context in the operating system that says what memory is allocated for a running program, what files are open, and what threads are running on behalf of this process. Now, not only can the operating system run multiple processes simultaneously (1), a single process can also be multi-threaded.

The cool thing about this multi-threadedness is that the threads within a process share the same memory, as the memory is allocated to the process that the threads belong to. Having shared memory between threads means that you can have a global variable and access and manipulate that variable from multiple threads simultaneously. Or, for example, you can allocate an array and have multiple threads operate on segments of the array.

Programming with pthreads can be hard. The pthread library is a fairly low-level library, and it usually requires some technical insight to be able to use it effectively. After having used pthreads for a while, you are likely to sense an urge to write wrapper-functions to make the API somewhat more high-level.

While there are some synchronization primitives like mutexes and condition variables available in the library, it is really up to the programmer to take proper advantage of these — as is often the case with powerful low-level APIs, the API itself doesn't do anything for you; it is you who has to make it all work.

Programming pthreads is often also hard for another reason; the library enables you to write programs that preempt themselves all the time, drawing you into a trap of writing operating system-like code. This kind of parallelism in code is incredibly hard to follow, and therefore also incredibly hard to debug and develop. The programmer, or developer, if you will, should definitely put some effort into making a decent design beforehand, preferably including a schematic of the communication flow that should occur between the threads. The easiest parallel programs do not communicate at all; they simply divide the data to be processed among the threads, and take off.

It should be clear that the pthread library is powerful, and that the code's complexity is really all the programmer's fault.

While the shared memory ability of pthreads is powerful, it does have the drawback that when the programmer cocks up and a single thread generates a dreadful SIGSEGV, the whole process bombs (2).

Also, as already described above, pthreads has the tendency of luring you into a trap of creating parallelism that is not based on communication, creating overly complex code flows.

The automatic shared memory has the drawback that you may not always want to share data among all threads, and that the code is not thread-safe unless you put mutex locks in crucial spots. It is entirely up to the programmer to correctly identify these spots and make sure that the routines are fully thread-safe.

It is for these reasons that communication libraries like MPI, PVM, and even fork()+socket based code are still immensely popular. The latest well-known example of a forking multi-threaded application is the Google Chrome browser, in which a forked-off "thread" may crash, but will not take the entire application down.

This blog entry has gotten too long to include some useful code examples. Therefore I will provide you with a useful link:

ptheads programming tutorial

Skip right to the examples, unless of course you wish to learn some more on the theory of threads...  Note how this tutorial covers all you need to know, and cleverly stays away from the more advanced features of the pthread library, that you are not likely to need to know anyway.

If the C programming language is not your thing, try using the Python threading module. Although not truly concurrent threads, Python's threading threads appear very similar in use and behavior to pthreads.

Another interesting topic related to parallel programming is that of deadlock and starvation, and the "dining philosophers" problem. See this online computer science class material for more.

---

1. Multiple processes or threads of execution can run concurrently on multi-processor or multi-core machines. On uniprocessor machines, they are scheduled one after another in a time-shared fashion.
2. There are (or have been, in the past?) implementations of UNIX in which it's unclear what thread receives the UNIX signal. I believe Linux sends it to the main thread, ie. the first thread that was started when the process was created. For this reason, it's wise to keep the main thread around during the lifetime of the process.