Marco’s blog

This is already my second post for this day. The previous post was getting too long already and I decided to split it up.

Besides my work on Summer of Code, which will be my main focus during the summer, I will try to work a bit on networking support for GRUB 2 in my spare time. I have some networking code that is not cleaned up and not full features and well designed on my harddisk already. Last week I sent in a patch to add Ethernet support to GRUB2. No drivers (actually, I am not interested in drivers), but mainly interface related code. This patches was not really cleaned up,it only was sent in to get some feedback on the interfaces. Although many people told me they were (even code wise) interested in networking support, no one replied to my post. This disappointed me a bit. Perhaps I should wait a bit longer, clean up the patch and resend it…

Related to GRUB, Robert Millan mentioned on the GRUB Development mailinglist that GRUB was used in a Marvel comic. Although this is unfortunately not GRUB 2, I find it amazing to see a project I greatly care about and work on mentioned in a comic!

Inter frame decoding decodes frames by applying changes to certain reference frames. To support inter frame decoding I need to implement a few features in my decoder. The first step is unpacking the motion compensation parameters. The second step is unpacking the motion compensation data (mainly motion vectors). This is now finished in the current code.

For each inter frame, Dirac can have either zero, one or two reference frames. In the case it has reference frames, the frames are divided into overlapping blocks. For each of these blocks, when used, a motion vector is available. To decode the frame, you have to use these vectors that express the displacement within a frame to calculate a new frame.

This displacement won’t yield a perfect image. One reason for this that the video data is sampled and have a limited resolution. Although subpixel motion compensation is available in Dirac, it will not compensate for every situation. Besides that, lighting can change, etc. For that reason the encoder subtracts the motion compensated picture from the actual image. The result is a sparse image which is used to compensate the imperfections of motion compensation. This is called the residue.

To decode the residue I had to made some changes to my code, because coefficient unpacking works differently in some situations for inter frames. These changes are small, like some other defaults for the dequantizer, size of codeblocks, etc. The IDWT used for the residue is by default the Legall(5, 3) wavelet. I added this transform. There are a lot of transforms that I haven’t added yet. These are not used by default by the reference implementation. But a full implementation of the decoder should eventually support this.

So the only thing left is the actual motion compensation. The code as it is in subversion now just shows the residue (see the picture above to see what this looks like). When I add motion compensation the decoder will be fully capable of decoding the samples I created using the reference implementation. So now I will start working on this. At first it will be just like described int the specification. After that I will try to properly integrate this into the OBMC support of FFmpeg.

Yesterday I went to the cinema to see the movie Transformers. It was sort of what I expected of it. Lots of action and simple entertainment. Usually this is not exactly my kind of movie, but I had fun :-). Compared to other movies like this which I have seen (Spiderman 2, X-Men 3), this movie was way better in my opinion.

But usually I prefer other kinds of movies, like The Butterfly Effect, Twelve Monkeys, Eternal Sunshine of the Spotless Mind, etc. While I was thinking of good movies, I wondered if there was actually a system like last.fm. This website, to which I am subscribed has a list of the music you listen to (sent to the website by my music player) and has the same information for other users. It uses this information to build a list of similar music, this way you can get recommendations of other music you might like.

Information about movies you watch is a bit harder to collect, but not impossible. You will need a plugin for your movie player instead of for your music player. I already have the IMDB numbers of all my movies in MythTv, so information is quite reliable for me. Although some of my movies/series are not (yet) in IMDB.

The next question is: which domainname should they choose? Usually .tv is used for television related websites. I tried last.tv and it actually exists! Their favicon.ico is the same as that of last.fm, so it might even become used. I typed in this address in google and found lasttv. It uses your last.fm account to fetch youtube videos related to your musical taste. I don’t have flashplayer so I can’t and won’t test it, but it is interesting nevertheless. I wonder if anyone reading this have tried this.

Finally intra frame decoding works! Today I found some bugs in my code which I fixed. I found some more bugs in the spec. But finally my code works and is able to decode intra frames. See for yourself:

There are still some things I am not really happy with. First the IDWT, it is slow and contains some weird hacks. Perhaps I misunderstood the spec, but like it is now doesn’t seem right. But it matches the reference implementation and you can see it works perfectly. Until now I tested my code with two samples. The other sample makes the decoder hang at some point, I have to look into this.

This code is still not optimized a lot, but before that I want to clean it up, add comments and continue with decoding of motion compensated frames. I rather have a full decoder first, before even thinking of optimizing. I hope that isn’t a silly idea :-).

I am very happy with this result. I am not sure how complex motion compensation is, but I guess I am quite positive about getting a functional decoder in not too much time. Although I ignored some issues: no implementation of the low delay syntax and just one IDWT so far. I wonder how important the low delay syntax would be, or if I can better focus on other issues instead.

Sometimes you do not realize how important something is, until it is not available. This happened to me. Last weekend I visited my parents. When I came back Monday and decided to wash my dishes, I noticed there was no warm water. The weird thing about this problem was that my neighbors had warm water.

The next morning I called to the company responsible for this (Essent). That’s when it all started. They asked me for my address and tried to look it up. The strange thing was, that I was not in their database. This surprised me, I do pay my bills to essent!. The person who I had on the phone forwarded me to one of their daughter companies, which also offer the same service. I called them: Same problem, I was not in their database. So I called essent again. At the end they agreed to send someone to me to see what is going on and to fix my problem.

In the afternoo, still no phonecall from the plumber to make an appointment for a visit. So I called again. They told me they had forwarded my problem to a plumber and I would be called. They would try to contact them again. Of course nothing happened…

Wednesday (3th day without warm water). I called to essent… again. Something went wrong and they would call the plumber again. In the afternoon I STILL didn’t get a phone call from the plumber. In the afternoon I called them again. They told me that more people from my apartment (also from the same level) had called and someone is underway to fix the problem. In the evening I should get warm water again. I checked with my neighbors and they all had warm water so they haven’t called. And still no warm water…

Thursday… still no warm water (day 4). I called and finally someone actually apologized and promised me it would be fixed today. Finally someone actually made a hard promise! About two hours later I was called by the plumber, they told me someone would come here to fix my problem later that day. And finally the plumber came here and fixed the problem. The actual problem was not in my house. The problem was that the pressure difference for the entire neighborhood was too low. The plumber called, they changed the pressure difference and I had warm water again!

The plumber told me he heard about my phone call when he was driving back to his house Wednesday late in the afternoon. I can’t blame him, but I surely can blame the bureaucrats of essent. Too bad I am stuck with them. And the nice thing is that I am still not in their system, just like most of my neighbors. I wonder if they will notice if I stop paying them ;-).

The first thing I worked on today was unpacking the coefficients of the other two components and quantization. Something else that was high on my todo list was integrating golomb decoding into FFmpeg. Dirac uses interleaved exponential golomb codes. It’s useful to encode small values, in that case you need less bits. But it remains possible to encode bigger values.

The basic idea is that instead of writing one bit, you write to bits to the bitstream. The first bit is “0 “when more bits follow, otherwise it is set to “1″. The second bit is the actual data. This is a bit simplified, actually you do not store the first “1″ in the bitstream so when decoding you start with a “1″ in the buffer. When you finished decoding, you have to subtract “1″.

Example:

001b => 10b = 2

You have to substract 1, so the actual value is 1.

So you have to loop over all bits. To decode 8 bits, you have to loop 4 times. By using two lookup tables, you can actually decode 8 bits at a time. The first lookup table determines the resulting value that should be added to the decoded value. The second lookup table determines the length of the bitstring that was read and thus should be skipped. It can also be used to determine the size of the decoded bits. One optimization I added is setting the length to 9, if the decoded data doesn’t end in the current byte.

Hopefully this all makes sense, it is a bit hard to explain how it works, without showing the actual code. The code is committed to SVN, so please have a look. For generating the lookup tables, I wrote a small C program. If someone cares about it, I can commit this as well.

Last days I have been working like crazy on the Dirac decoder for FFmpeg. First of all, I was unsure if my arithmetic decoding actually worked. In order to test this, I used Schrodinger (a dirac decoder/encoder). It contains two utilities to check arithmetic coding. The first is arith_encode, which encodes a file. The other is arith_decode, which can decode this file. Unfortunately both tools didn’t work and I had to fix them. I sent a patch to the maintainers. Using the output of these tools I tested and fixed the arithmetic decoder I wrote.

The last two days I worked hard on unpacking the coefficients from the bitstream. I was slowed down a bit because at some points the spec was not clear to me. I found several problems in the specification and submitted them to the Dirac people from the BBC. I am positively surprised by their prompt reply. I am still waiting for them to explain why parent is set to one for certain subbands, instead of setting it to zero like I understood from the specification. So this is either a bug in the specification or reference implementation, or I am misunderstanding something.

Despite of all this, I managed to finish coefficient unpacking for a single component. Adding more components and quantization is not a lot of work. Currently the decoder output the coefficients of intra frames. I checked the output of my decoder with that of the reference implementation and they are exactly the same! :-). The output of the decoder looks like this:

You can compare this with the actual image:

In order to get this image on the screen, I have to finish a couple of things. First of all, I need to make sure all the 3 components are unpacked and quantized. Of course I also need to implement the IDWT, to transform the subbands to an actual image.

Now I will start working on quantization, adding the other components, cleaning up the code and adding comments. Especially cleaning up is important now. The golomb and arithmetic coding code is based on the psuedocode from the specification. I think this can be improved by using functionality that already exists in FFmpeg.

This is the first blog entry I wrote. I am not exactly sure what I will write on this blog and what I will add to this website. So you will have to see what happens!

The main topic of this blog during the summer will be my Summer of Code project. My project is adding a dirac decoder/encoder to ffmpeg. Development didn’t go as fast as I hoped before, but now I have all the time to work on this :-).

I will also use this blog to write about other projects I work on. For example GRUB 2, for which I am a maintainer. I also have some small pet projects I work on, I will also write about those

And of course I will write about myself, things I do, my opinion about certain things, etc