Learning codec coding

[Principher]

More for fun than anything else, I would like to try implementing a video codec.
I am wondering what would be a good start, should I go with a simple existing one (clearly the most useful strategy) or would a better strategy be to make the different parts (DCT, Quant, VLC) and integrate them into my own format.
Please note that I am fairly proficient in programming (C++), and work with Directshow on a daily basis. I just have never had an excuse to implement my own codec :).
If the best strategy is to implement an already defined codec, which one would be good? I have the h261 specification laying around somewhere, is that a good start or is there some even simpler codec?

Oh and just so you do not hold your breath till it is finished. I do not expect to release the codec since it is more of a self-test and probably will not be useful to anyone but me.

[Manao]

If you just want to play, it's better to start with mpeg1/h261. Once you've implemented a simple working encoder / decoder, then you can modify it according to your tastes, without following the standard anymore.

Newer standards ( mpeg2, mpeg4, h264 ) are only more complicated refinements of mpeg1, but once you've implemented mpeg1, you've basically seen it all, which seems to be what you're searching for.

[Principher]

Thanks for the reply Manao, I will start reading the h261 specfication when I have time and then start designing and implementing. Now all I need is time... :)

[imcold]

Hi,
I had the idea of implementing my own video codec some time ago too. I'm taking the opposite way - not following any standard (maybe make it mpeg1 compliant after it'll be fully functional), and beginning with all functions from scratch - there are no video codecs written in pascal anyways (I use freepascal as my programming platform), though other codecs serve me as an inspiration for general codec layout, structs & datatypes (I can read some C, although I don't use it).
As a first milestone, I've written a still frame codec, much like jpeg (dct, mpeg1 intra quantization equation, simple vlc for coeffs- no huffman tables: zero length and coeff size are merged into one byte, then additional bits for coeff). Few days back I was playing with effects of different quant matrices on image quality and size, and tried to use 4x4 DCT instead of 8x8 (didn't worked very well...).
I'm going to do P-frame coding next . So far I've made a yuv player that searches and displays motion vectors (for standard 16x16 sized macroblocks) based on lowest SAD (psadbw and assembly rocks... it's darned slow in plain pascal). Due to preferring the lowest SAD the mv-s are sometimes rather random though. Now I need to do motion compensation & substractig of mcomp frame and real frame and hack it all together.
It won't be any useful to real applications, but I found it useful for education (at least for mine). As soon as P-frames will work and it'll be able to encode some videos, I plan to put the code online, together with documentation explaining how it works. I don't expect it to be soon, school will probably keep me pretty busy and I'm not fast nor efficient anyways. And I probably will have some questions coming ;)
Good luck, Principher :)

[Principher]

Also thanks to you imcold :) That most certainly is also a possible approach, and has the advantage that I will not have to make a "complete" codec before I can test it. Good thing I have not started, now I will "just" have to decide which approach to take.

[Guest]

When you say a "codec" are you talking about a VFW codec or a DirectShow one?

[imcold]

I have to correct myself: there is one mpeg1 decoder/player written in pascal, that I'm aware of. And with 'codec' I mean a library used through a cli program, communicating through a pretty basic api: set a struct with options/frame dimensions/pointer to frame pics -> init -> encode/decode frame -> free. Good to begin with, I think.

[Principher]

My definition of codec, at the moment (at some time I will probably port it to DirectShow), is also more of a command-line tool which encodes / decodes the data, written in standard C++. This is mostly due to that fact that I change between Windows and Linux machines and would like to develop on both.

[imcold]

Ok, I hacked something together :P Not very impressive yet, takes yuv or y4m input, compresses only luma plane and then decompresses the luma frames(Y8 is the name for it I guess?). Compression ratio varies from about 5:1 to 20:1 (a lot of motion, low qp - less motion, higher qp), until it starts getting ugly. No scenechange detection, no blocktypes - first motion vectors (whole-pel, if that term does exist) for 16x16 pel areas are found and saved to bitstream, then the whole residual is encoded like I-frame - no skips, intra blocks... I guess I can begin hacking some more advanced tools on this soon, the code needs some polishing first.
If someone is interested, I can upload the binary somewhere, the code will be published a bit later, as the bitstream writing/reading is currently a mess - not to mention it was hard to debug, I had to use synchronization markers to keep track where decoding broke, and a lot of debug output...
And it's slow - fdct and idct takes the most time, when motion estimation range is small: video 720x304 image size, me range 8: 4/8 fps en/decoding. I have some ideas for speedup though: use asm optimized dct functions, probably from xvid, and some real me algo with (much) lower number of SAD calls.
It's fun to do and see it working nevertheless ^_^.

[Manao]

SAD in asm is 5x faster than SAD in c, so it also gives a huge speedup. XviD or x264's SAD functions are a good starting point.

[imcold]

I already had a sse2 SAD, though more straightforward (fewer registers used) I did a crude comparison between mine, xvid's and x264's SAD speed. I had to modify x264's sad, I use only one stride. Mine was slowest (of course), but only by a few percents. Fastest was xvid's with a little modification. Slight instr. reorder and removal of the two lea instructions at end gave it a 2% boost on my AMD Sempron 2800+ (K8, 1600 Mhz). Well I don't think it will make any spottable difference if it'll be used in xvid, and it may be faster only on K8. I'll benchmark it with xvid later.
%macro SAD_16x16_SSE2 0
movdqu xmm0, [edx]
movdqu xmm1, [edx+ecx]
movdqa xmm2, [eax]
movdqa xmm3, [eax+ecx]
lea edx,[edx+2*ecx]
psadbw xmm0, xmm2
psadbw xmm1, xmm3
lea eax,[eax+2*ecx]
paddusw xmm6,xmm0
paddusw xmm6,xmm1
%endmacro

%macro SAD_16x16_SSE2_F 0
movdqu xmm0, [edx]
movdqu xmm1, [edx+ecx]
movdqa xmm2, [eax]
movdqa xmm3, [eax+ecx]
psadbw xmm0, xmm2
psadbw xmm1, xmm3
paddusw xmm6,xmm0
paddusw xmm6,xmm1
%endmacro

sad16_sse2:
mov eax, [esp+ 4] ; cur (assumed aligned)
mov edx, [esp+ 8] ; ref
mov ecx, [esp+12] ; stride

pxor xmm6, xmm6 ; accum

SAD_16x16_SSE2
SAD_16x16_SSE2
SAD_16x16_SSE2
SAD_16x16_SSE2
SAD_16x16_SSE2
SAD_16x16_SSE2
SAD_16x16_SSE2
SAD_16x16_SSE2_F

pshufd xmm5, xmm6, 00000010b
paddusw xmm6, xmm5
pextrw eax, xmm6, 0
ret
On another note, I want to do a half-pel mv refine, just I'm not quite sure how I should do that: would be upsampling the currently processed block (for which I already have the whole-pel mvs) and comparing it to the stored and upsampled reference picture (to eight positions around whole-pel displacement) a good way to do that or is there a simpler way to do that?

[Manao]

IIRC, on Sempron/Athlon, an ISSE-only SAD is faster than a SSE2 one ( though not by much ).

For the halfpel, there's a ISSE/SSE2 instruction that does (x + y + 1) / 2 ( pavgb ), which is exactly what you need. Now, you can either compute the half pels on the fly during the SAD, or interpolate the whole frame once and for all and to the SAD using the four hpel planes in parallel.

[imcold]

Indeed, XviD has been slightly faster with SSE2 disabled when I tested it two or three years back. I didn't know why back then.
Thanks for the pavgb tip, that'll be handy. I think I'll store the interpolated picture and use it, looks easier to implement. Thanks again!

[imcold]

I cleaned up the code a bit and made a sf project page: http://sourceforge.net/projects/evk, the code is in release or in svn repo (not that it'll be particularly pretty, but I hope a C programmer can read it too). I used the ffmpeg's mmx fdct and simple idct from xvid. It gave me a huge speed increase (about by a factor of 4), the former f/idct code is just too slow.
If anyone feels like experimenting a bit, here are some notes: Takes yuv or y4m input and encodes it to evk stream file. For details and options run "evk_cli -h". It works on luma plane only and has intra/inter frames.
I hope it won't crash (a lot), it's quite fragile regarding the input - expects planar yuv420, although it doesn't encode the uv planes, and width and height to be multiples of 16.

[akupenguin]

On a related note, I started a simple codec for experiments a while ago. Due to the experiments my latest version is no longer simple, but a tarball from before I started adding stuff is at http://akuvian.org/src/x264/xlsc-33.tar.bz2

[imcold]

Wow, thanks Loren! I'm going to have a look at it :)

[imcold]

I have one design related question. In encoder/decoder contexts (x264, xvid etc.) there are pointers to arch specific functions, which are set in context initialization function to refer either to plain C function or to MMX/SSE etc. optimized one. What would be the disadvantage, if I moved the pointers out of the context struct and declare them as global?

[Manao]

You wouldn't support several instances of your codec at the same time in the same software. Basically, were you to instanciate one encoder, start encoding with it, then instanciate another one, you would risk, during its instanciation, to modify a function pointer while this one is actually being used by the first one, leading in a potential crash.

Global variables are usually evil, and should be avoided excepted in some very rare cases (library with a static_initialize)

[imcold]

Thanks Manao. So, if I moved the initialization of function pointers to some init_lib(cpuflags) function, I'll be fine.