Hello guys,
Sorry if I'm coming back to you after so long. I was cleaning up my secondary email accounts and I found recent inquiries about the GBA Caimans codec. A quick search took me here, so I thought I would spend some time to answer your questions.
But first I have to say that, as most of you probably understood, I've been away from the GBA for quite some years, so please forgive me if some memories are blurred. Caimans codec was born out of an experiment and my will to learn how to develop for the GBA. It evolved into a commercial project, but the drive behind it never ceased to be the same one that brings you guys here: to have some fun. It was probably the last time I had so much fun developing something, and I have fond, albeit distant memories of it.
I eventually sold my IP to Activision (in 2007, I think) and thus I cannot release the encoder (not that I would know where to find the source code any more). The websites are still up an running as a form of nice memory, but really the service is no more.
That said, after all these years, I think it's fine to give a very high level description of the techniques that were used. I'm really grateful that you are still talking about this codec after so many years, but it really was nothing fancy and I'm sure that you guys can now do much better than that humble Italian bedroom coder.
There really existed 3 versions of Caimans codec: The caimans codec, the caimans codec pro and the caimans codec for DS.
Caimans Codec / Caimans codec 2:
http://www.caimans.net/gbavideo/demos2.shtml
This first version was extremely simple: it used fixed 4x4 pixels codebooks. On the encoder side, each frame is converted to the YUV12 colorspace, divided in static blocks of 8x8 pixels (so you get up to 30x20 blocks on a GBA screen). A first pass of the encoder finds out the "scene changes", or frames that differer for more than a certain % from the previous one. Scene changes are called I-frames. If more than a certain number of frames go by without any scene change, an I-frame is forced anyway.
For all the frames in between two I-frames -we call then P-Frames- the encoder would then identify a set of codebooks that it could use to approximate all the blocks of all those frames. I think I used 20-30 kbytes sets, depending on the target quality. The search for the optimal set of codebook was done with k-mean algorithm and each block could be encoded with a single entry or a set of 4 entries in the codebook table (more on this later), or with a special code "zero", which means "do not update this block from the previous frame". Since codebooks are 4x4 pixels and blocks are 8x8 pixels, a block can be either a single codebook entry which is X and Y doubled at playtime, or a set of 4 codebooks. This simple tweak made it possible to encode sequences where some objects zooms in or out quite effectively.
That's it for the encoder.
At play time, the player simply gets an I-frame and a set of codebooks. It displays the I-frame then proceeds to decode the p-frames using a timer driven irq (I think). Each call just updates the blocks that need to be updated reading from the codebook table. This until a new I-frame is reached and a new codebook table is fetched.
Seek was possible as each I-frame is completely independent. So the rom had a table with the offset of the I-frames and the player could simply jump to that offset.
I remember that I frames, including all the codebooks, ended up being huge, so the codebooks were not physically stored together with the I-frame, but each of them was "streamed" together with the P-frame that was first using it.
The first implementation was done in C and it was a mess but I managed to circulate a couple of proof of concepts around. I had no plans other than that. But one day Activision calls me to use it in Spiderman 2! They asked me if it was usable as a library. I said "yes!", but of course it wasn't :-). A few sleepless night followed that email (I had a proper job to do during the day) during which I rewrote a lot of the code in assembler, I made a library out of the player and I was able to send it to them. I remember that, because of the simplicity of the encoding technique, it was extremely fast. I remember I could run it at 60 fps if I wanted, and the whole player core was only few KB and would fit entirely in the on-chip memory, or whatever it was called (sorry, I forgot the GBA-terminology).
I also developed a very simple audio codec based on ADPCM, but to be honest, although some of the demos on the website use it, it was never used in commercial videogames: the bitrate required for the video was so high (I think that it was 50-70Kbytes/sec) that saving few kbytes on a 16Khz 8-bit PCM mono track was totally pointless.
Caimans Codec Pro:
http://www.caimans.net/gbavideo/demos.shtml
After the codec appeared in Spiderman 2 and in a number of other games, I got calls from other developers who wanted to store more video. I developed the caimans codec pro for the purpose, which further expanded the original idea. This time I used the YUV9 color space, but the main difference is that it added variable size and non-square codebooks. Again, a block is always 8x8, but codebooks can be one of the following sizes:
8x8
8x4
4x4
4x2
A block is encoded and decoded recursively: if a good 8x8 approximation is found, then go with it. Otherwise break the block into two 8x4 and go down recursively. you could end up with a block that had the upper half encoded with a single entry, the lower half encoded with 4 entries, or 6 or whatever.
On the top of that, I added a very basic form of motion compensation. A block could also be "shifted" (only entire pixels, no fancy qpel or halfpel) in the predicted frame. It really did something for the compression rate, but it killed the efficiency at playtime (more on this later)
I kept the k-mean algorithm as the foundation of the encoder, but due to the complexity of the new algorithm, the codebook search was painfully slow. I remember that it took a good 30 minutes to encode less than 1 minute of video on my pentium 3. It would have been trivial to improved the encoder, but I never really liked to work on that part, I was so much more into optimizing the player :-).
speaking of it, I did any trick I could come up with, I optimized my code as much as I could, but I never managed to push it beyond 15fps. Which was enough though. The video quality was only ok imho, but the bitrate could go down to few kbytes per second. It was only used commercially in a couple of products. One of them, A Lizzy Mcguire title, contained a full episode of the show (I think it was 24 minutes). I remember the producers only gave me 10 megabytes to store the entire episode. It was painful to hand tweak sequences to save up to the last bit, and the result didn't look very nice, but kids liked it. Go figure.
Caimans Codec DS:
www.ds-video.com
This started as an experiment after I had given my GBA IP to Activision (they never used the encoder after that though... go figure). I started toying with the DS to see if I could repeat that experience. The GBA was fading away anyway...
At first I ported the GBA caimans codec pro, which was quite easy to do and would play at much higher frame rate due to the faster CPU (there might still be some demo on the website). But I wanted to do better so I started thinking of a full featured mpeg4 decoder. I remember I started downloading the source code of the reference mpeg4 Simple Profile player and hammered it until I had it compile for the DS (which took a long time). Finally it does, and plays video. Yeah, B/W footage at 0.5 fps :-).
But that was a starting point, so I started profiling the player, rewriting everything from scratch and moving to assembler for the the critical parts. I added a lot of tables to speed up computation, I got rid completely of Floating Point math and so on. I got some 8-12 fps on regular mpeg SP streams and I felt I could not do better than that. So what I did was I started tweaking the mpeg4 encoder until it would bias the encoding towards those elements of the mpeg4 framework that I knew I could decode faster (codebooks) and using less and less of what I could decode very slowly (half pel, all kind of motion vectors etc). So, the player is technically playing mpeg4, but the encoder is encoding a stream that is meant to be a bit easier to decode. This had a minimal impact on the quality, but allowed me go past the 15 fps barrier that I considered the minimum acceptable quality.
But everyday life, the job etc were starting to be more demanding, so I never really pursued that interest any more. I remember I released a dragon's lair prototype, but that was it.
Thanks for bringing back those epic times, and good luck with your efforts!
Perhaps you have a bright future in hardware engineering, 9 out of 10 times it's the other way around - people tend to be more accustomed with higher-level languages (not that C is very high level - it's pretty much as low as you can go before you hit Assembly).
