Lair Of The Multimedia Guru

I guess most developers have once or more than once run into the question of, “which PRNG should one use”. The awnser, or more precissely my awnser to this, would be it really depends on for what one plans to use it.
There is no perfect generator, there are fast ones, and there are good ones, but the best arent the fastest. One has to choose depending on ones needs

• If one wants to generate white noise for a human listener then the best generator simply is the fastest that produces perfectly sounding white noise, it really doesnt matter if it has some statistical defects or not.
• If one wants to use the random numbers for cryptographic purposes, a perfect generator that has been extensively tested and no flaws found is needed.
• If one wants to test a scientific theory by simulation, one needs a generator that doesnt cause a wrong result from the simulation, but as the correct result isnt known, one cant easily pick based on this criteria. Thus one has little alternative to picking a generator that has few statistical defects and is fast enough for the amount of numbers needed. Or better even run the simulation 2-3 times with very different generators

So which generators are there and what defects do they have? This actually is rather easy to awnser, or then maybe not ;) well, there is George Marsaglias Diehard and Pierre L’Ecuyers
TestU01 both contain code to test PRNGs, later also contains a paper describing the results of these tests for most recent and popular PRNGs.

In an ideal world one would just have to look at the TestU01 paper And pick a generator that has the amount of defects and speed one wants. At least thats what i thought before testing a few generators myself, more precissely i took a few of the generators that passed all tests in TestU01 and run 2 (to me obvious) tests against them

1. Use a gaussian like algorithm to find out if any bits in the output are just a linear (mod 2) combination of previous output bits
2. Use a gaussian like algorithm to find out if any scalars in the output are just a linear (mod maxoutput+1) combination of previous output scalars
3. Use a gaussian like algorithm to find out if any bits (only considering the least significant of each scalar) in the output are just a linear (mod 2) combination of previous such output bits

The first 2 of these tests in the way i implemented them only consider outputs surrounding a scalar with 20 zero LSBs, though as far as i tested it this 20bit trick only made a difference for the additative LFG with only the 32MSB used, but i did not test all without this 20bit check

Failing either of these tests makes the PRNG at least unsuitable for linear algebra under the same modulo, so its certainly a statistical defect. All linear congruential generators have to fail at least the test that works in their own modulo, after all they are linear, but actually all i tested failed both tests. Lagged fibonacci generators based on addition or xor similarly must fail and do. All multiplicative Lagged fibonacci generators fail as well due to linear dependancies in their lower bits. All linear feedback shift register based generators like the mersene twister very obviously have to fail too, i did not test any of them though as none passed TestU01.

The actual generators that passed TestU01 and failed mine where:
superduper64, Marsa-lfib4, DX-47-3, MRGk5_93, Lfib(2^64,55,24,*), brent-xor4096s

The actual generators that passed TestU01 and passed mine where:
brent-xor4096s, MRG31k3p, CombMRG96, ran2, CLCG4, KISS99

Note1, there are more generators that passed TestU01 but i did not test them

Note2, The first 2 tests where only searching for linear dependancies within 512 consecutive scalars, that is 32kbit for a 64bit PRNG, the 3rd test was considering 32kbit of LSBs

In addition to that, limiting the output to just 32MSB of 64 made the multiplicative LFG 2^64,55,24,* pass mine while the same trick with a additative one was not helping, KISS99 also passed when SHR3 or CONG was droped but not when both or MWC alone was droped

No source code this time though because i randomly copied PRNGs from various places, but if there is interrest i could throw all but my own code out and post that

To be continued when iam less tired … ;)

As the little reverse engeneering puzzle has been solved, we need some prize …

flour, olive oil, half a teaspoon sugar, dry yeast and water. No thats not yet the price ^^; And probably not even a half correct pizza dough but i like it and am too lazy to look up what is “correct”.

After rescaling the x,y and z transformation vectors of the dough it becoms flat and roun hmm square?! (… i guess ill file a bugreport about that one later) adding tomato puree and tuna.

Adding gouda cheese and oregano, i should probably have added more cheese but transforming a block of cheese into these stripes is boring and the ready made pizza cheese from supermarket could be more accurately be described by milk+yellow color and thickening agent so that stuff was not an option.

After ~15min at ~493 kelvin

And at last, the pizza was turned into a virtual pizza, which i herein officially give to chrono! The real counterpart has for saftey reasons been quickly ea ehm i mean destroyed, to avoid paradoxes.

There are SVQ3 files that ffmpeg cannot decode yet, the ones iam speaking of contain a image or watermark, often a logo in a global header (extradata in ffmpeg, QT has its own funky terminology for it). The binary decoder displays this watermark over the actually decoded video.

FFmpeg is in principle fully capable to decode these videos (and of course without these watermarks), the only problem is that 32bit of the header and following bitstream are modified by xoring them with a per file constant. Our problem is we do not know how the binary decoder calculates this constant. A example SVQ3 video and the corresponding constant of 0xA2A2A2A2 for this file as well as a bugreport on our tracker exist as well

The puzzle is to figure out how the binary decoder finds the constant, its likely not very hard for one knowing how to use a debugger, hint: memory breakpoint at the input data and a cup of coffee or tea or a can with cola.

Its really high time to update by blog before it starts rotting. So here are a few words about the modified discrete cosine transform. The reason why iam writing this, is that most docs about the MDCT ive seen are quite obfuscated so i thought maybe i could do better (or worse ;)). Note ive made no attempt to write formal proofs for sake of readability, but they are all very trivial.

Basis functions of the normal DCT

Basis functions of the MDCT

Both of the transforms have orthogonal basis functions, that is the forward transform is simply the series of dot products of the input and the basis functions. While the inverse transform is the sum of the basis functions each scaled by the dot product from the forward transform. This can also be said in a dozen different ways …

What makes the MDCT special, is that it has half as many basis functions as it has inputs. Thus performing the MDCT and then IMDCT on a single block will generally not result in the original. The magic with the MDCT is that it can be overlapped by 50% and then suddenly doing the MDCTs and IMDCTs leads to perfect reconstruction of the original. One can see such lapped transform as a single non lapped transform of infinite length if one wants.

To proof that simply applying the MDCT and then the IMDCT on each block i, which is 50% lapped over block i-1 leads to the original, one really only has to proof that all basis functions are orthogonal (have a mutual dot product = 0). We already assumed that the basis functions of a single MDCT are orthogonal (that can easily be proofen by trigonometric identities if someone is bored). We also know that non adjacent blocks can only have mutually orthogonal basis functions as they do not overlap. Whats left are the adjacent blocks. The proof for their orthogonality is very trivial, if one looks at the graph above, it is immedeatly obvious that there are 2 symmetries one at 0.25 and one at 0.75 in all basis functions. So they behave as (…, c, b, a, -a, -b, -c, …, x, y, z, z, y, x, …). Thus the dot product of 2 basis functions of 2 adjacent blocks is …
… c*x + b*y + a*z – a*z – b*y – c*x … which is obviously 0.

I also should mention that because of these 2 symmetries mentioned above one really just needs to calculate 50% of the IMDCT as the rest is identical up to the sign

The above is still missing one detail, that is that normally the (I)MDCT is used with a window to smoothly get the basis functions down to 0 at their ends. An example with sine window is below

The obvious question is, are the basis functions still orthogonal? The blocks which are not adjacent of course still have to be because their basis functions dont overlap. The basis functions from adjacent blocks assuming a symmetric window
(…c*w_-2, b*w_-1, a*w₀, -a*w₁, -b*w₂, -c*w₃, …, x*w₃, y*w₂, z*w₁, z*w₀, y*w_-1, x*w_-2, …) now have a dot product of …c*w_-2*x*w₃ + b*w_-1*y*w₂ + a*w₀*z*w₁ – a*w₁*z*w₀ – b*w₂*y*w_-1 – c*w₃*x*w_-2 … which is still 0 thus to our “big surprise” any symmetric window maintains orthogonality between 2 adjacent blocks. Whats left are the basis functions within a block. For them the dot product looks like
… c*C*w_-2² + b*B*w_-1² + a*A*w₀² + a*A*w₁² + b*B*w₂² + c*C*w₃² … + x*X*w₃² + y*Y*w₂² + z*Z*w₁² + z*Z*w₀² + y*Y*w_-1² + x*X*w_-2² …
or reordered and common stuff factored out:
… c*C*(w_-2²+w₃²) + b*B*(w_-1²+w₂²) + a*A*(w₀²+ w₁²) +
… x*X*(w₃²+w_-2²) + y*Y*(w₂²+w_-1²) + z*Z*(w₁² + w₀²)
If we now choose a window for which w_i² + w_1-i² = 2 then the dot product equals what it is without the window, thus our windowed MDCT is still orthogonal and thus easy invertible

Another week has passed in the ffmpeg universe.

• Mans added -Bsymbolic, everyone wonders why this isnt default and what the ELF designers were smoking. Shared libav* becomes smaller, faster and more secure due to this change.
• Mike fixes a security issue in the mov/mp4 demuxer. Noone writes a security advisory, like always.
• Dave Yeo restores OS/2 support
• RV30/40 work by kostya
• VC1 improvments by kostya
• removing globals used in API by me and mans (due to issues with -Bsymbolic)
• export sha1 implementation in libavutil to the world (actually we just forgot to install the header) by Diego Pettenò
• Various h264 fixes by jeff
• Make mov useable over http by elupus and baptiste
• Support overriding codec id for input files by me
• Generic global header support for mov by baptiste
• User adjustable dynamic range compression for AC3 by justin
• djgpp support by Michael Kostylev
• PC Paintbrush PCX image decoder by ivo
• Sun Rasterfile decoder by ivo
• Extract aspect ratio from ODML-avis by me
• TechnoTrend PVA Demuxer by ivo
• support removing elements from the AVL tree in libavutil and make it independant of malloc() by me
• improve CRC API and install crc.h (another forgotten header) by aurel
• various request_channels related fixes by justin
• Linux Media Labs MPEG-4 (LMLM4) demuxer by ivo
• support for libdc1394 v.2 by Alessandro Sappia
• Do not install rtp.h (which should have never been part of the public API) by luca#1
• User specifyable maximum amount of memory to use for the index. by paul kelly
• libav-user was created by root
• Add support for H.264 video in the RTP muxer by luca#1
• ugly hack to support multicodec stsd in mov by me
• subtitle support in mov improvmets by me and reimar
• support for Matroska attachments by eugeni stepanov
• ICC support by reimar
• SMPTE 421 Annex L format demuxer by kostya
• The monthly flames, accusations and insults, a vote about fixing warnings and me, baptiste and many others fixing many. Some gcc bugs in -Werror being found, all decoders being changed to have const input by me …
• support for ogg text subtitles by reimar
• mbaff spatial direct support by loren
• many optimizations by loren
• parallel regression tests by mans
• various nut fixes by oded
• support for speex in ogg by reimar
• The first parts of libavfilter hit svn by bobby and vitor
• MANY bugfixes, ive ignored most due to lazyness and i think its not that interresting for most readers anyway
• Lots of cleanup by various people
• myself loosing the ability to reliably capitalize words correctly as i move toward the end of this entry, also note, nothing has been spellchecked as its almost 6 in the morning here …

Random pictures from around midnight 2007-12-31 / 2008-01-01. Downscaled a little so wordpress autogenerates thumbnails and doesnt randomly refuse the uploads

Being a little bored and too lazy to do any meaningfull work. Ive looked at wikis main page and on that the Paradox of choice caught my eye, thinking its some interresting thing about math like the Axiom of choice is.

After reading the article iam puzzled why something like that is on wikipedia at all. Not to mention how things like that get linked from the front page.

Psychology has together with astrology always been a little astray from science and logic. But that article is really missing the point. Consumers dont have a problem with too many choices, they have a problem with making choices based on lack of information, wrong and irrelevant information (as presented in advertisements).
If one has a small set of products to choose from at the supermarkt one can try them all or at least a significant fraction of them and then in the future choose the best (considering quality, taste, price, …). With more products trying a significant fraction becomes impossible, one has to rely on other means of comparission. With many products thats still dead easy, for example after trying 3 differnt brands of noodles one realzes they all taste the same. So simply choosing the cheapest is the ideal choice. The same is true in a sense for green tea. None of the green teas from supermarkets i tried tastes as good as a random one from a real tea shop. It gets a lot trickier with these frozen, refrigerated, canned or dried, ready made foods there are far too many to try them all. Theres no obvious trend of taste vs. price, not even a reliable taste vs. brand trend. Only thing which has been always true is that cooked by my (grand)mother or myself tastes better :). I think supermarkets really should add some “number of packs sold per month” and “average customer rating” to their price tags.

Supperior (no frozen and dried crap), half finished, yesterday:

Finished (still yesterday)

What has happened in the last ehm week since the previous weekly news, well alot …

• some ffserver-IPv6-linux fix by Nicolas George
• some ffserver-IPv6-macosx fix by Ronald S. Bultje
• flv files with invalid headers work again after a fix by me
• a vorbis decoder crash after “floor0 dec: booknumber too high” has been fixed by me
• make ffmpeg stop if writing fails instead of continuing by me
• split adx into adxenc.c and adxdec.c by aurel
• improvements to the mpeg-ps detection which fix several mp3 files which where misdetected as mpeg-ps, by me
• make the NellyMoser decoder use our generic mdct, finding out how to do this and doing it by fabrice
• Electronic Arts XAS ADPCM decoder by peter ross and aurel
• Electronic Arts .cdata demuxer by peter ross and aurel
• RICE2 entropy coding and variable block size for flac support by Josh Coalson
• reorder codec registration to prefer native implementations by diego
• Warn user if bitrate parameter is too low by ramiro (using 100 instead of 100k was a pretty common cause of silly bug reports …)
• List enabled code in configure output by ramiro
• Remove libvorbis Vorbis decoding support by diego (our vorbis decoder IS bugfree :) at least as far as we know)
• fix interlaced_frame flag for h.264 by jeff downs and Reinhard Nissl
• dont send hundreads of RTCP packets by luca abeni
• adpcm-ima encoder bugfix by Timofei V. Bondarenko
• some of the MMS patches by Björn Axelsson hit svn, still quite a few to go
• various h.264 fixes by Jeff Downs
• Musepack SV8 demuxer and decoder by kostya
• a-law/mu-law/16bit PCM support in SDP by luca abeni
• ipv6/ipv4 udp cleanup by luca abeni
• MPEG2 in RTP muxer support by luca abeni
• split audio and video grabbing code into libavdevice by luca abeni
• split wmv2 in its own files by aurel
• intrax8 decoder by “someone”, now finally we can decode all wmv2 files
• export top_field_first flag for h.264 by Reinhard Nissl
• our own ogg muxer written by Baptiste, now finally you can store your music and videos in the worst container ever designed without having to depend on libogg
• remove libogg support by Baptiste
• 44.1kHz support and various other small improvements for our nellymoser decoder by alex
• flv v9 32bit pts support by alex
• remove important functions from snow by diego
• mpegts demuxer segfault fix by jeff
• Optimize memory management and some cleanup of the rm demuxer by roberto
• remove perror() usage and take meassures against its reintroduction by luca abeni
• dynamically allocate ByteIOContext in AVFormatContext so changes to it dont break the ABI by Björn Axelsson
• VC-1 MMX DSP functions by Christophe GISQUET
• part of the RV30/RV40 patchset from kostya hit svn, the rest should likely hit svn soon as well assuming i and kostya arent too lazy
• pcm_s16le_planar support for electronicarts files by aurel
• some stuff needed for OS/2 support by Dave Yeo
• split vc1dsp_mmx out into its own compilation unit by aurel
• MLP/TrueHD parser by Ian Caulfield
• pause/play/seek support for the protocol API by Björn Axelsson
• wma sound artefact fix by reimar
• change british english to amerikan by diego and others, yes we all hate british english :)
• make our rm muxer generate files playable by realplayer by kostya, i guess this once worked already in the past …
• dnxhd 720p encoding and decoding support by baptiste
• improvments to the mp3 detection by me
• fix asf muxer so that asf files work better on win ce by me
• Adpcm_swf regressions tests by benjamin
• several segfault fixes in the mov demuxer by baptiste and takis
• Many small fixes by various people ive been too lazy to list

Missing things, duplicated entries and wrong entries as well as spelling errors are unintended, if you find anything missing/wrong/duplicated tell me and ill fix it, dont bother telling me that every second word contains a typo i do know that already :)

Well after lots of looking around, reading reviews and all that, i finally realized that all compact cameras which are available currently suck. So my choices where down to getting an old analog camera or a DSLR, now “analog” film is just too inconvenient for my lazy self so i choose a DSLR, more precissely the EOS 400D, thats also what mans recommanded though mans recommandition was not really why i choose it. The EOS 400D is certainly not perfect but there arent many options, many cameras are just too expensive for my taste and then there are: sony alpha (crappy noisy sensor) pentax (non functional IS and IS is the only advantage over cannon), olympus (too small sensor), nikon (lens compatibility with their cheap DSLRs is no good and no real advantage over canon)

So is the EOS400D good? Well its not bad, it could be smaller and lighter, its viewfinder could be bigger and brighter, at least ive no problem using the viewfinder with glasses but manual focus at large apertures is not possible with it because the viewfinder limits the view to f/4 or so . I wonder if one of these 3rd party focusing screen replacements would help here?

The EOS400D also sadly doesnt have live view, that is viewing what you shoot on the LCD, but there arent many DSLRs which do, the 40D being one but its too large, heavy and expensive for this small extra feature, and note the only reason why i care about live view would be better manual focus ability

Lenses, well, getting a good lens for my DSLR turned out so far to be quite a bit more tricky than i thought. First lenses are expensive, it seems they are all sold at 10 times their production cost. Second you cant just read reviews and buy a lens based on that, the lenses provided to reviewers seem handpicked and perfectly adjusted by the manufactors, what you buy in a shop is not. But i didnt know that or rather i underestimated the sample variation some people claimed exists with lenses so i bought a 18-250mm f/3.5-6.3 Tamron lens, according to reviews and images there (as well as other reviews) this lens has better image quality than for example canons 17-85 IS USM and it of course has a much larger focalength range though its not that good at the larger focal lengths but then having all that range in a single lens seemed quite convenient. Well to make a long story short the 18-250 lens i got was so bad it went back where it came from at the first oppertunity. At 100mm one side was so much more blurry than the other it was immedeately vissible at 1024×786, there was no need to zoom in and look at pixels 1:1

Luckily i also bought a 50mm f/1.8 lens from canon, one of canons cheapest lenses but still vastly outperforming the 6 times as expensive crap 18-250 tamron i received, so the sample images below are all shot with that 50mm lens. Also note that i had to recompress the images to lower quality as wordpress refused the files due to their filesize

For a long time that flower was on my balcony, now its in my grandmothers garden, and it doesnt seem to do that well as you can see :(

Strange tiny tree, we bought a while ago, its needles are completely soft instead of sharp and it doesnt seem to grow

Some random weed i think

One of my grandmothers unique plants, this one is quite representative for many of them though not all, some are breathtakingly beautifull like her roses …
My mother said its a oleander, my grandmother disagreed, i dont remember if she said what it is

Birds, overexposed IMO, it was very dark and rainy, also they dont look good at f/1.8 aperture

second try at f/4, sadly most birds where gone already, also the image looks worse then the origial before the recompression needed to make wordpress happy filesize wise

My mother wanted to take a (few) picture(s) as well, well, she tried, and tried but it didnt work, half pressing the shutter button, waiting for the autofocus and then full pressing it apparently isnt that easy, so the above image was taken by my mother with manual focus. What i learned out of that, well the EOS400D shutter button is very well build as it still worked after my mother was finished.

After you fight your way through thickets you find in a corner of the garden some firewood perfectly protected from rain to dry, currently my grandmothers only means to heat her house as her more modern heaters broke down (not counting electricity based ones). Somehow i suspect the firewood will still be there in the spring and the heaters will still be broken and the electricity bill will be near 0. In normal houses you need to wear warm closes when you leave in my grandmothers house you need warm clothes when you enter.

Tasty looking apples (emphasis here is on looking)

My mother identified it as parasol mushroom and said its edible, my grandmother said its poissionous (thats what my grandmother says about all mushrooms), i tried to convice them to try it ;)
btw, iam a little curious what it is, i am almost certain its not a parasol

White roses (in the rain like everything else on that day)

After the extreemly popular recent changes in ffmpeg blog post, here are the next news, precissely 1 well something ;) afterwards

Note, errors and ommissions are unintended and if you spot any tell me and ill fix them (except spelling and grammer i wont bother fixing these)

• More work and patches by ronald and luca to get the IPv6 related code closer to being functional
• diego removed Metrowerks Codewarrior support due to it being unmaintained, broken and making the code more ugly (also not a single person complained so there is likely no one using it)
• Altivec runtime detection fix/cleanup and messup
• The remaining H.264 PAFF patches from jeff downs hit svn, sadly this also caused a slowdown of the decoder, so this needs more work to prevent this slowdown
• reimar removed the extreemly broken SIGILL based cpu extension detection code, the SIGILL code should have never been commited in the first place …
• luca barbato added support for a user specifyable maximum number of frames per RTP packet
• a optimized VP3 IDCT for blackfin by marc hoffman
• mans changed configure to use pr instead of cat -n as later is not standard, this will likely cause some minor annoyance to some users of non standard systems well fix your system, dont expect every lib and application to workaround it!
• a DNxHD (SMPTE VC-3) encoder by baptiste
• DNxHD 10 bit depth and 36mbit decoding support by baptiste
• user specifyable zlib compression level for PNG by reimar
• ogg seeking simplification and bugfix by reimar
• a very small part of the MMS patch hit svn
• some minor h.264 optimization by jeff downs
• infinite loop and negtive memcpy in the ac3 and aac parser fix by myself
• RC4, DES and encrypted asf support by reimar
• VP6 with huffman encoded blocks support by aurel
• deblocking for H.264 PAFF fix by Martin Zlomek
• nellymoser ASAO decoder by a840bda5870ba11f19698ff6eb9581dfb0f95fa5, 539459aeb7d425140b62a3ec7dbf6dc8e408a306, 520e17cd55896441042b14df2566a6eb610ed444
  Loic Minier and Benjamin Larsson
• support for electronic arts demuxer and decoders by aurel and peter ross
• speling, gramer and warning fixed by diego
• streaming to XBox360 fix by patric stout
• a regression fix related to url_split() by ronald
• display and sample aspect ratios display by michel
• WMV3 FASTTX=0 fix by kostya
• AVProgram API to export mpeg ts program information to the user app by nico
• rm demuxer changed to output frames instead of slices by kostya and roberto, this simplifies alot of related code
• Beam Software SIFF demuxer and video decoder by kostya
• support for reading duration from Xing and VBRI tag in mp3 files by andreas
• more flac encoding optimizations by loren
• moving the framecrc muxer to its own file by aurel
• and theres a patch for a MLP/TrueHD decoder by Ian Caulfield on ffmpeg-dev which i should review
• many other things ive missed …