Lair Of The Multimedia Guru

2008-12-11

Love, death and a bunch of stalkers

Following is a true story of various odd events the happened a few years ago in my life, taken alone most and especially the begin would not be worth mentioning or writing about but together they might be.

Introduction, the begin until autumn 2003

I guess most people have someone who is important to them or who they love. In my case its Nadja, we’ve been in the same class in school which was indeed a long time ago. Somehow our paths parted, i always wanted to call her, but i didnt, and neither did she, nor have i heared anything from or about her, and neither did i ask. Well why should i have asked, iam not the kind that sniffs behind peoples backs about their lives, i always hated it when my mother did and wouldnt want to be treating others that way. Not that i had much contact to anyone i could have easily asked …

summer/autumn 2003

I was still living with my mother in her appartment, my father had bought his own appartment and left (IIRC) a year or so earlier. Without my father around, i was the only one left for my mother to talk to/blame/annoy. Now dont misunderstand me, my mother isnt evil (hmm or maybe she is ;) but i simply couldnt stand it anymore and left too. I also had a strange feeling that something wasnt right with Nadja … Being in my new appartment and not having my mother stand behind me all day long, i finally called Nadja, i still had the number from school time, to my dismay the number did not work. And to make it worse the phone company also had noone in their lists with a matching family name and street address, and that includes people that arent listed in the public phone book. Internet search engines also where a dead end, like they had been in previous years when i tried to find an email address of her. Being not too lucky with finding anything, i thought, “my phone number is in the phone book, my email is easy to find, if Nadja needs something she could find me easily…”, not that i was too happy about it but for whatever reason i temporarly gave up searching her. There where also many other things to do in my new appartment and my feeling that something was wrong, well i couldnt have known, i had to be imagining things.

2004

I think it was spring, though i cant say that for certain, i was on my way to the supermarket around the corner, when i run into my grandmother. What was she doing here i wondered, well she told me that my other grandmother called her and said that my stove was broken and i couldnt make tea so she wanted to bring me a electrical heater plate thingy so i could make tee. Well, my stove wasnt broken and i didnt call either of my grandmothers. This thing left all of us a little puzzled, it seems someone with a male and young voice called my grandmother (the one from my fathers side) and pretended to be me (her phone number was in the phone book), telling her the story of a broken stove and tea, she didnt know the address of my new appartment so she called my mother and as she didnt reach her my other grandmother who then came to help.

2005.02.16 17:53 my phone rings …

IIRC the person said something like the following (in german)
“Iam [cant remember] from kurier, daily newpaper, could i speak with [name of my mother]”
I think for a moment and then tell him that, iam sorry but i do not know anyone by that name. He accepts that though apparently not very happily and we hang up. Not too surprissingly noone from “kurier” which actually is a pretty large newspaper here ever calls my mother.

2005.03.05

It wouldnt be worth mentioning, where it not in relation to the following events, not that the other things at the begin of 2005 would be, but on this day mike melanson told me a little joke by email, something like “After the conference Diego, myself and the other multimedia hackers in attendance will coordinate an austrian road trip and locate you and see what happens when you are exposed to sunshine :)”
this was in relpy to myself declining the suggestion to meet everyone at linuxtag.

2005.03.29 9:36 another odd phone call

Some female claiming to be from lotto and wanting to speak with “frau michael niedermayer”, i mildly enraged tell her “herr niedermayer”, not too successfull she continues with calling me “frau michael niedermayer” which is somethinbg like “mrs./miss michael niedermayer” so i hang up. It has to be noted that she had no odd dialect and thus likely could speak german well enough to know the difference. According to my notes her phone number was “+43 6648194927”
Besides these calls, there was no lack of others who wanted to just ask a few questions for various statistics, and interviews in 2005.

2005 march or april

As iam on my way home from supermarket, some guy in the street where my appartment is maybe he was 20-30 years old, wearing shorts. He said “Wast du schon an der sonne” which in english means “did you where already in the sun”. I ignored him and kept walking.
After that ive seen him many times sitting in the park, though never with a notebook or other normal hacker toy. Its also interresting to note that the last time ive seen him in the park was not too long prior to the next odd event.
(also neither diego nor mike look like him nor could they explain it when i asked)

2005.06.02 evening maybe 20-21 o clock

I was in the park, spoke there on my mobile with my mother and then went home, on the way home, someone (female vioce) called “michi” from behind, not recognizing the voice nor expecting anyone I ignored it, the person didnt call a second time that day. 2 Days later same place same time, i was waiting for the traffic light to turn green when i spotted 2 girls diagonally across the crossroads, i didnt recognize either of them, though lets call them girl A and B for the sake of referring to them. The light turtned green and a little while after they where behind and out of sight someone from their direction called “niedermayer”, for some reason i ignored it, they didnt call again.
In the following 2 and a half months ive run across girl A (or at least i think it was her) several dozen times at random places. She always starred at me as if iam supposed to know her but i apparently didnt, at least i didnt recognize her. She was wearing something like jeans, tshirt and green sport shoes. I was thinking it must be someone from my school class, but i simply couldnt match her up with anyone, either way it wasnt Nadja so i really didnt care who she was or what she wanted, especially as she could have said what she wanted instead of just staring and IIRC once saying “hello”, well this reasoning shall turn out to have been possibly too naive.

2005.07.23 16-17 o clock

As i walk home, just as iam entering the house, a guy maybe 10 meters before me on the street takes a photo of me, he appeared nervous, theres also nothing there, not even a trashcan that would be worthy of a picture.

2005.08.24

As iam waiting at mc donalds for my 2 cheesburgers, someone to my right a few meters away is called by the name Nadja several times, she is or looks like girl B wearing a long black dress. She does remind me of someone from my school class but not Nadja, she doesnt look into my direction but the look on her face makes it very obvious that she is feeling very uncomfortable almost as if she wanted to do anything but being there playing Nadja which really is what she was doing. She also said no word at all.
Being somewhat confused and having received the 2 cheesburgers, i paid and left.
About 2 weeks later, again at mc donalds, as iam leaving, straight ahead along the street on its left side where a park is, i see an ambulance with blue blinking lights. I enter the park at its close corner and watch from quite some distance. I see someone looking like girl B walking together with several other people and ambulance man/doctors over the meadow to the ambulance. They dont seem to be in a hurry, neither is the ambulance after they reached it. I walk through the rest of the park and round the ambulance and then turn and walk home, the ambulance still standing at the same spot, still blinking blue.
After now seeing someone apparently knowning my name, being called Nadja and entering an ambulance i felt rather uncomfortable, that Nadja might not be ok, that i maybe didnt recognize her, I didnt really care who the weird people playing street theater where or why there where doing this, but i had to find Nadja.
The phone book, all phone companies, and google lead to nothing, but i found Marta, another one from my class, she could not explain who the weird people where but she could tell me what is with Nadja, Marta said Nadja died 2 years ago in 2003.
She did not know any details, but said that she is certain about it.
I did not want to belive this, and kept asking others i knew and ones i did not knew, as well as the official sources. Everyone who knew something confirmed that Nadja died in 2003.
Now if this was a fictional story then the death of Nadja, one of the best, most honest, righteous and selfless people i knew, would be the end. She was not the kind that pretended to be good while doing evil things, rather the opposite. Besides she is/was the most important one in my life. But reality is cold and mercyless, so the story cannot end here yet …
More weird people appear and watch me, they follow me around, watch what i buy in the supermarket, where i walk to, …

2005.10.04

As iam on my way from the supermarket to my appartment, as i enter the house, seconds after passing a male thin guy, he behind me, says “niedermayer comes now” (in german).
I quickly rush to my appartment, but find nothing touched except maybe a chest of drawers moved a little, its top drawer is rather hard to move without moving the whole thing …

2005.10.05 15:30-16:30

I buy a more secure lock and exchange the old against it.

2005.10.07 7:00

My doorbell rings, iam in bed, sleeping. Tired i put on some clothes and stumble to the door. After opening it, i see a not too big guy with a woolen cap/hood. He very politely asks if he woke me, theres a somehow wicked smile on his face. He says he is searching for someone with the name “altendorfer” to renovate their appartment. I tell him politely that i dont know anyone by that name. He leaves and i head back to bed.

2005.10.07 night, shortly before i want to go to bed

I walk by the entrance door of my appartment, noticing to my dismay that it is partly disassembled, more precissely the little hole with lenses through which you can look out is nicely taken appart and the metal plate in whichs center it is is very loose, to the point that there is a 10cm long and narrow hole one can look straight through to the outside, it was too narrow to stick ones finger through but a thick wire easily would have. To my further dismay both my keys and the security card needed to get replacement keys officially where placed at spots somewhat different from where i put them. The keys where hanging where the coats are hanging, though one was standing out straight horizontally from the keyring, a thing practically impossible to happen were they hanged there normally, but someone trying to be silent who was trying to return a single key quickly might very well place it like that.
The card, it was before and afterwards in my wallet, but now it was standing out, before, i had it sticked in as deep as possible as i knew i would not need it any time soon. Did i lock the door? When i was away: always, when i was at home: never.
Realizing that whoever was it, was long gone, i decided to block the door and go to sleep (a surely unwise choice, like never locking the door when i was at home …)
Next day in the morning i call the police, one of them, he looks like the average not too bright varity appears, he writes everything down, though as no real damage has been done and nothing stolen his interrest is low. he refuses to attempt to take fingerprints of the door pretending it was not possible to take fingerprints of smooth surfaces. I later file a complaint about this.

2005.10.09

A sunday, being convinced that someone could have made a duplicate key to my appartment, i replace the lock again, thanks here go to my mother for buying a lock and bringing it to me on a sunday where most shops are closed.

2005.10.15

I meet attila kinali, he having heared from all the mess here, jumped on a train to visit me. My appartment being a mess, ive offered/made no food for him. I was still far too confused about nadjas death to treat guests properly …

2005.10.16 9:00

My mother tells me that someone has broken in, in my fathers office, his replacement keys, portable phone, a cammera, a harddisk and some money of a colleague has been stolen.

2005 exact day unknown

It is late in the evening, i go out for a walk, its dark, the ground is littered with fallen leafes. There are no people on the street except that every time i walk through some leafes a little while later i hear footsteps behind me stepping into leafes as well. I see no shadow from him, its clear he keeps enough distance not to cast any shadow too far ahead. I walk for maybe half an hour with him following me all the time, until i try to discreetly look back at a crossroads, but i was not discreet enough, he turns around and walks away at that very crossroads.
On many other days similar things happen, most of the time though there are several guys that switch positions, also they often waited at a future crossroads instead of litterally following behind.

2005 exact day unknown

I hear noises at the my appartments entrance door, as if someone was trying to open it. Walking there and looking through the repaired peep hole thingy, i only see someones back standing bend over in front. My first thought was that its some old neighbor or a relative of one who went to the wrong floor, but then a few moments later i decide to double check this, but too late, when i look again he is gone.
Gone far too quick and silent for an old neighbor …

2005.11.08 15:00

The doorbell from the house door rings, i pick up the receiver and say “yes”, the awnser “police”. I press the open button, moments later 2 policemen, they dont look like the average dumb varity stand before me. They tell me that they came because of the break in a month ago. They ask many questions, look in all rooms, and listen to the various things i remember. They suspect that my mother is behind things.

2005 unknown day

I talk with my mother on the phone, and tell her that the guys watching/stalking me are always starring at me. Next day i find several people standing with their backs toward me standing at various points along the way i normally walk. They where quite noticeably starring in the air in random other directions …

2005 unknown day

I decide to do various random things and see how they react …

2005.11.17 17:00

Iam on my way to a large shop (baumax), just before the shop i run into my grandmother (from my fathers side) she tries to convince me to come to her house. I decline explaining that it is too cold at her house and the shop is heated. She accepts that and leaves.
I buy a rope and one of these stick with a rubber pump thingies to clean the drain of a wasching basin, whatever its called in englisha plunger, so i have a seperate one for my bathroom and toilet. After i leave, while waiting for the traffic light to turn green so i could cross the street to reach the tram, someone behind me says “Nadja hat ihren job verlohren, die mussten eben den headcount reduzieren” (in english, “nadja lost her job, they just had to reduce the headcount”). I turn around but there where too many people to identify who said that.

2005 end november begin december

For the duration of a week or 2 they follow me around missing no day, i always favored one supermarket during that time, at the end i see a couple in that supermarket, the woman i suspect was supposed to look like Nadja, she had similar “Ausstrahlung” (someone translate this to english)aura like Nadja. She also had thick hands, and i mean not that she was thick or her arms, just the hands, Nadja did not had thick hands. I guess its hard to find people looking like Nadja that are willing to play street theater. I guess they where also supposed to do something but they didnt, he just said a word or 2 to her, maybe something like “Lets leave” but i dont remember exactly. After that i notice fewer people watching/following me around. This could of course also have been a coincidence but its odd why they followed me around so carefully for 1-2 weeks and then just stopped.

2005 12.13

I send nadjas mother a letter, hoping she would tell me something else than that Nadja is dead and hoping that maybe she has a clue who is behind that group following me around.
I didnt sent the letter sooner as several people like marta told me by email that i should leave nadjas mother alone and not ask.

2005.12.14 10-11 o clock

The bell from the house door rings, i get out of bed stumble to the door, expecting the postman (there was a packet i was waiting for), i pick up the receiver and say “yes”, and wait, but noone awnsers, so i press the door open button anyway. A little later i realize it might be nadjas mother and put on some clothes and walked down to check but i see noone, so i walk around the block hoping to spot someone, again no luck.

2006.01.01 10 o clock

I hear 2 woman talking a floor or 2 below me, i only catch a few phrases of the conversation, X: “… my daughter …”, Y:”… Michi … before 14-15 o clock few chances … many woman”, X:”MANY WOMAN?! …. is someone watching him?” Y:”A woman maybe”
X:”… frau [nadjas family name]”, After that, X left who possibly was nadjas mother, sadly i did not realize this quick enough. Who was Y? i dont know, Why was nadjas mother talking with a neighbor of mine instead of me? i neither know that.

2006.01.11

The doorbell rings, its the postman, bringing back my letter that i sent to nadjas mother, unopened, it seems it was laying at the post office and nadjas mother did not take it from the postman or was not at home nor picked it up from the post office after that.

2006.01.16

Not having heared anything from any neighbor yet about the whole, i go through the ones likely knowing and ask, its clear my suspicion is correct but they pretend not to know who had talked with nadjas mother, just trying to explain how she confused a few people who where looking at an appartment to rent at the floor above me with many woman coming to me. (and iam sure none of the ones i directly spoke with was Y)

somewhen 2006

Having heared various stories from members of my family and people from my class about other school comrades who died, i realize that alot more young people die than i would have guessed. So i decide to write a will, just in case …
Making sure my grave would be close to nadjas and not too close to people of my family (nothing against them but its called rest in peace for a reason). And that my computer stuff would end in the hands of some FOSS people. As well as for the very unlikely case that Nadja still is alive that she would get everything, not that i have much …

2007.07.19

I receive an SMS
Its text is: “Happy birthday ALLES GUTE ZUM GEBURTSTAG wünschen Tanja und Mädels”
in english litterally: “Happy birthday everything good for (your) birthday wish tanja and girls”
Whats special on this, well its the day nadja died, exactly 4 years before. I also should mention that i have fewer SMS than i have fingers on one hand if i dont count advertisements and stuff from people i know. And its of course not even close to my birthday.

Short of that and a few other oddities, things normallized with the end of 2005. Comparing things its like counting oddities per week or day in 2005 while afterwards it was rather per month or year. So they are either gone or worked more discreetly after 2005.

Also note, the list of events above is intentionally not complete lacking things that iam sure are unrelated to the group following me around as well as a few things to prevent them from knowing what i missed.

How did Nadja die? There are many contradicting rumors, and after excluding what is clearly false, that whats left still leaves an accident, suicide and murder open. I dont belive it was an accident, she would have had to be stupid or unlucky, but she was very intelligent, but then i cant exclude that it might have been an accident. And iam certain it was not suicide, also noone suggested to me that it might have been suicide.

Who where the poeple following me around? Ultimately i do not know, at the top of the list though are private investigators hired by the copyright mafiaa, if it wasnt them some parts could be explained by 2 girls from my class and an unknown 3rd person hireing some private investigators. That 3rd person could be one of my parents, someone who knew nadja or some woman interrested in the ffmpeg maintainer. Motives could have been from just annoying me to finding information about me or Nadja.
Good arguments exist against most, it appears the person had difficulty identifying me at first, that would exclude my parents. But then its possible that not all events were caused by the same people …
Someone wanting to find information about nadja would have just asked, maybe pretending to be someone else than she was, but they wouldnt have done this kind of theater, the whole was just too much work for the return of no information at all, actually this text likely would tell such a person more than what they found out by their activity
Someone wanting to annoy/terrorize me really could have done more than the street theater they played, but then maybe it is hard to find people doing that “harder” kind of activity when one lacks contacts to the real mafia.
Gathering informatiuon about me, well i guess they did, not too much correct information once i realized that there are not just 1-2 girls from my class who i failed to recognize but even wrong information is information i guess

Note, if you send me any questions or comments by email, GPG encrypted&signed is strongly preferred!

Filed under: Uncategorized — Michael @ 16:46

Coverity

Its a little while ago that i made that screenshot, anyway, i thought its funny so iam posting it here

Filed under: Uncategorized — Michael @ 15:51

2008-11-30

Pseudo random number generators 2

After the little bit of analysing PRNGs in the last blog post, which PRNGs exactly seem good?

Fastest PRNGs

If one either needs a very fast PRNG or one has some means to easily test that the output is good enough (like looking to see if a noise filter produces no vissible aritifacts) then folllowing could be considered.
Linear congruential generators, Additative lagged fibbonacci generators or even just an array of random numbers that gets used repeatedly, …
Each of these has its serious flaws, LCGs have very poorly performing LSBs, that is the lowest n bits never have a period larger than 2n. ALFGs contain number triplets (the ones spaced like the taps used in the PRNG) that when used as coordinates in a cube would all fall in a single plane. Still these generators are often good enough, and have been used for a long time and are widespread, that is all C libs ive seen use either of them for rand() for examle.

Good and fast PRNGs

If one wants a generator free of big flaws and that is still reasonably fast then the number of choices goes down, first there is
4 tap additative LFG (xi = xi-55 + xi-119 + xi-179 + xi-256 mod 2n) this one passed all of testu01 but has a obvious linear dependancy between its values.
Combined generators, these generators combine the output of several simple generators and generally pass all tests, many of them though are slow like CLCG4 which combines 4 LCGs, combined generators like fi = gi + hi also have the flaw that fi – fi+p = hi – hi+p when p is the period of g. This also means that fi – fi+p – (fi+q – fi+p+q) = 0 when p and q are the periods of h and g. Thus all combined generators which are made of constituent generators with “bruteforceable periods” are cryptographically likely very weak. A combined generator that is reasonable fast is KISS99.
Multiplicative lagged fibonacci generators, like for example (xi = xi-55 * xi-24 mod 2n) these generators also tend to pass all tests as long as only the most significant bits are used, that is for example the top 32 bit of a 64 bit generator. The least significant bit of such a generator is always 1, its next bit behaves like a LFSR identically to the least significant of an additative or xor based LFG. One trick to get rid of the least significant bit without ending up with just 31 or 63 bits is to use 2*a*b+a+b instead of a*b, this works because a and b are (have to be) odd in a normal MLFG and (2*A+1)(2*B+1) = 4AB + 2A + 2B + 1

Best but slow PRNGs

“Anything” based on AES, SHA-1, MD5, …

Bad PRNGs

These are PRNGs that are both slower and worse in terms of their output than others, examples are
Mersene twister, becuase its output is purely based on the XOR of previous bits thus being not nearly as good as some pretend it to be while it also isnt nearly as fast compared to other properly implemented PRNGs.
Combined generators with lots of modulo by non power of 2, these are slow …
Weak generators from which many output values are thrown away, again these are slow …

Filed under: Cryptanalysis,Pseudo random number generators — Michael @ 02:08

2008-11-22

Pseudo random number generators

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 … ;)

Filed under: Cryptanalysis,Pseudo random number generators — Michael @ 01:56

2008-10-28

Pizza

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

img_2801pp.jpg

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”.

img_2815pp.jpg

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.

img_2818pp.jpg

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.

img_2824pp.jpg

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.

Filed under: Cooking,Off Topic,Pictures — Michael @ 00:18

2008-08-15

Little Reverse engeneering puzzle

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.

Filed under: FFmpeg,Reverse Engineering — Michael @ 22:10

2008-06-09

MDCT

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
dct.gif

Basis functions of the MDCT
mdct.gif

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
winmdct.gif

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*w0, -a*w1, -b*w2, -c*w3, …, x*w3, y*w2, z*w1, z*w0, y*w-1, x*w-2, …) now have a dot product of …c*w-2*x*w3 + b*w-1*y*w2 + a*w0*z*w1 – a*w1*z*w0 – b*w2*y*w-1 – c*w3*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-22 + b*B*w-12 + a*A*w02 + a*A*w12 + b*B*w22 + c*C*w32 … + x*X*w32 + y*Y*w22 + z*Z*w12 + z*Z*w02 + y*Y*w-12 + x*X*w-22
or reordered and common stuff factored out:
… c*C*(w-22+w32) + b*B*(w-12+w22) + a*A*(w02+ w12) +
… x*X*(w32+w-22) + y*Y*(w22+w-12) + z*Z*(w12 + w02)
If we now choose a window for which wi2 + w1-i2 = 2 then the dot product equals what it is without the window, thus our windowed MDCT is still orthogonal and thus easy invertible

Filed under: DCT — Michael @ 03:34

2008-02-11

FFmpeg weekly news #4

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 …
Filed under: FFmpeg — Michael @ 05:44

2008-01-04

New Years Eve Fireworks

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

img_2388-med.jpgimg_2418-med.jpgimg_2449-med.jpg
img_2486-med.jpgimg_2497-med.jpgimg_2517-med.jpg
img_2525-med.jpgimg_2533-med.jpgimg_2535-med.jpg
img_2540-med.jpgimg_2555-med.jpgimg_2571-med.jpg

Filed under: Off Topic,Pictures — Michael @ 01:43

Powered by WordPress