Shadowlessness

Where there were twenty-something, now there is one less.

I don’t know if I’ve written about the sorry status of digital video (in web sites and other places) before or not (I think I have, but it’s almost 11AM and I haven’t slept yet, so forgive me if I’m misremembering!)
Anyways, the state of things up to a few months back was that we had quite good standards for WORM media distribution (Blurays and whatnot) but who actually uses those anymore?! If you wanted to rip video and archive them, you had a few choices.
You could go with MPEG4 (Xvid) and MP3 or AC3 inside AVI, to get the best compatibility (noob-owned PCs, standalone video players, etc.) but Xvid is not the most advanced technology these days and AVI is plain obsolete; not to mention the fact that support for AVI and said codecs is very limited on handheld and portable devices.
You could pick stupid and unwieldy containers like MP4, which might or might not be playable on this or that device. You could throw all your data down a bottomless well of Microsoft’s (or another corporation’s) fancy sounding but virtually unusable formats (codecs and containers) which I won’t even mention here.
You could go with cool and quite free containers like MKV (or OGG) which are (currently) only playable on PCs (with non-noob owners!) This fact is really sad, because and MKV file with x264 and AC3 is a mighty force to be reckoned with, for storing all kinds of video, from small to UD (Ultra Definition, whenever that in invented and becomes trendy!)

On the web, the situation is quite simpler and more equal. Everybody were being fucked by Adobe Flash (and still are.) With occasional fingers thrust in by Windows Media and Apple Quicktime. All these have their own codecs (or variations of codecs) and all are proprietary. (If I had gods, I would thank them for making RealMedia defunct!)

But HTML5 has its own audio and video support, and HTML5 is being picked up by virtually every browser maker (yes, even Microsoft, but I can’t imagine why anybody still uses their piece of shit, except to download Firefox or Opera or Chrome or SeaMonkey or Safari. The really cool guys don’t even do that and FTP down the usable browsers directly!) The problem with HTML5 standard is that it doesn’t (didn’t?) mandate the container format and codecs (video or audio) that should be used! Obviously, this is not good for anybody. Of course, the situation could have been worse if the standard had specified a patent-laden or proprietary format, but still this under-specification means Morphy’s Law applies and web-developers and web site administrators get fucked even more than usual. Not to mention lusers.

A viable option for free audio and video was (and always is) of course Vorbis and Theora, and I quite like them, but people might argue that they (specially Theora) are not state-of-the-art codecs (not out-dated though, just not quite on the bleeding edge.)

Anyways, a few months back Google bought a company named On2 which held (presumably and hopefully) all the patents for a video codec (format) named VP8. At the time many people (including me) speculated and hoped that Google would put the patents in public domain (or whatever the term is that means make the use of the technology available to everyone, everywhere without charge and limitations for all time.) A couple of months back Google did the exact same thing and the WebM project was born. It’s defines a container format that hosts VP8 video and Vorbis audio, with no applicable patents in private control and liberal opensource-compatible licenses on all the software and libraries. Already most relevant browser makers have declared support for WebM (Mozilla, Opera, Google (obviously) and I think even Microsoft (but these days they just have to do anything the leaders of industry do, because they are not part of them anymore!)) and there are 3rd-party implementations of it. In short, I think the state of video on the web is starting to look good.

(This post has no links and it needs 100. I apologize for the inconvenience of having to copy+paste.)

Recursion is a fascinating and essential idea in mathematics, programming and design (among other things.) As a programmer, if you don’t understand this very simple idea (and I mean really understand it) you are pretty much done for. While it’s not a hard concept for any half-intelligent person to grasp, I don’t exactly know how many of us really do grasp it. But it’s not what I’m going to bitch about today.

In programming courses, one of the first examples used to introduce the idea of recursion is the Fibonacci sequence. You know, the series of integers starting with 0 and 1, where every next number is the sum of the two previous ones. (OK, I know that you do know. I was just covering all my bases.)

Anyways, the most simple and elegant introductory way of implementing a function that returns the nth number in the Fibonacci series goes something like this:

1
2
3
4
5
6
7

// Just making things clear!
typedef unsigned long long Integer;
 
Integer Fib (unsigned n)
{
	return n < 2 ? n : Fib(n - 2) + Fib(n - 1);
}

And every half-descent programmer knows that that’s probably one of the worst ways you can implement the idea. I’m not kidding. The teachers just throw this at the students, and the brighter of the students see the elegance and simple beauty of it and it will take years for most of them to realize the problems with this particular implementation. Some of them never do. This implementation performs very poorly for even the small values of n, which of course should be apparent when you contemplate its time complexity and recursion tree (I won’t go into space considerations, because they are not much of a problem until n goes into (many) thousands, at which point the value of the function becomes larger than you can store naively in most languages, which means you should have already given space considerations a serious thought.)

But even later, when the students learn about complexity analysis and Big O notation and crap like that, more often than not, they fail to apply the newly acquired knowledge to the old beliefs. If the teacher is good, and the student is bright and lucky enough, they walk out of their algorithm and data structure course with the new belief that bubble sort is bad, hash tables are good, and disk seek times dominate everything else (all of which are obviously bullshit in the absolute sense.)

For the more astute reader, I need to clarify that the badness of the mentioned implementation stems from the fact that most common languages (including C++) are mainly side-effect-driven languages, in that they rely mostly on the side-effects of expressions and statements to get the intended job done (the usage of the term “statement” is a clear sign of that.) Otherwise, you wouldn’t see so much assignment in our code. A functional and side-effect-free programming language (or more accurately, programming model) could easily cache the result of each invocation of the Fib function for any particular n (because the function call would be without side effects and therefore time-invariant) and would not need to evaluate any Fib(n) more than once. This is something that is being done in some of the better implementations of functional languages, AFAIK.

To emulate this behavior in this case, one can use a hand-coded version of what is known as Memoization, a la:

1
2
3
4
5
6
7
8
9
10
11
12
13

Integer Fib (unsigned n)
{
	static std::vector<integer> Mem;
	if (n < Mem.size() && 0 != Mem[n]) return Mem[n];  // The second condition is redundant, right?
 
	Integer ret = n < 2 ? n : Fib(n - 1) + Fib(n - 2);
 
	if (n >= Mem.size()) Mem.resize (n + 1, 0);
	Mem[n] = ret;
 
	return ret;
}
</integer>

This is not a bad implementation. It does have some issues in multithreaded applications, but I'm willing to overlook that for now. This implementation is linear in both time and space, and it can be faster than simple non-recursive implementations because it never calculates any Fib(n) more than once over the whole lifetime of the process. But it's not pretty (it has its charms, though!) and this way of doing things is error-prone (because you are adding memory and bookkeeping to a mathematical construct that is otherwise free of this stuff.) Not to mention that it is basically impossible to use as an introductory example; because it needs knowledge from all over the map.

A better implementation might be:

1
2
3
4
5
6
7
8
9
10
11
12
13

std::pair<integer , Integer> _fib (unsigned n)
{
	if (n < 2) return std::make_pair(n, 0);
 
	std::pair<Integer, Integer> Fn_1 = _fib(n - 1);
	return std::make_pair(Fn_1.first + Fn_1.second, Fn_1.first);
}
 
Integer Fib (unsigned n)
{
	return _fib(n).first;
}
</integer>

Of course, the meat of this implementation (such as it is) is the _fib function. The other one is just there to present a nicer and more consistent interface. Let me be the first one to say that there are more ways to implement a better Fibonacci and still stay essentially recursive. This is just one way, and not a particularly great one. But it's not bad either.

Now, how come no programming instructor ever teaches the likes of this implementation? Not the ones I studied under, at least. Are they afraid that their students' heads are going to explode? PROGRAMMING IS HARD PEOPLE! If a programmer can't handle a substantial improvement over a bad implementation of a simple idea, they are in for a big (and not at all nice) surprise. I hereby beg any teachers, instructors, professors and whatnot that have anything to do with teaching starting programmers to quit treating them like idiots, because idiots won't make good programmers. The idiots are not going to understand what they need anyways, so why take the chance of profound understanding from those who have the capacity to learn, but might not if you treat them like babies?

For the sake of completeness, here's a non-recursive implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13

Integer Fib (unsigned n)
{
	if (0 == n) return 0;
 
	Integer last = 1, penultimate = 0;
	for (unsigned i = 1; i < n; ++i)
	{
		penultimate += last;
		std::swap (last, penultimate);
	}
 
	return last;
}

This is the fastest of implementations offered here, with the exception of the memoizing one (and only in amortized sense.) But nothing prevents us from applying the memoization technique to an iterative implementation as well, albeit not in a general and automatic way. It might not be apparent or significant in such a simple sample, but for some class of problems, recursive solutions are usually easier to devise and understand, and therefore easier to get right. In any case, nothing is clear-cut when it comes to programming, and I'm almost offended when people (specially people who should know better) behave as if almost everything is.

I have changed the theme of my blog (as you can see, unless you are syndicating) from Barthelme to something called Fluid Blue. It was mostly out of boredom, and I’m not sure about the result yet.

In other news, I have decided to drop Google Analytics usage on my blog; mostly as a statement in support of privacy activism. I really like Google, and most of the time they do the Right Thing, so I’m not really worried about them stockpiling and misusing our data. However, why should you guys (my less-than-a-handful of readers) trust Google with your data for my benefit?! That’s certainly an attitude I want other people to have toward me, so I’m gonna start from myself and scrap Google Analytics and I don’t think I would use any kind of 3rd-party user tracking system unless their handling and storage of the data is completely and provably secure, anonymous and temporary.

An obvious side effect of this is that I can no longer know how many people are reading my blog. I’d appreciate if you guys (I know there are at least two, so my sentence is syntactically and semantically correct) would be more active, comment-wise!

Iff[sic] you are a programmer, if you don’t do anything else even if you don’t eat and even if you don’t shower, please please please please please watch this presentation.

The presenter is Dr. Cliff Click, and the topic is an in-depth view of modern code execution architecture. The talk is from 2009, and it has been on my to{do} list for almost 6 months. It is the best thing I have seen in the last year (and I played God of War III!) if not in many years. The guy is obviously very knowledgeable and he talks extremely fast, which just means that he packs an incredible amount of invaluable information into this 50+ minute talk.

I can’t stress this enough. Take an hour to watch this. Please! If you are a game developer, or any programmer with a conscience, you have to watch it right now! I’m not kidding here. Watch this through.

On an ego-boosting note, I just watched this talk and I already knew almost all of it (I have to brush up on the newer cache-coherency protocols though; those have also been on my to{do} list for some time now!) It did have some eye-opening “Aha!” moments for me. I may write about them later.

What are you doing still reading my shithead rant?! GO WATCH THIS!Cliff Click’s Crash Course in Modern Hardware (hosted locally.)

I learned C# in 2000, when the compiler and tools were still in beta (I think. I know I was working with the beta, but maybe the finals were released unbeknownst to me (hehehe! The Firefox spellchecker does not recognize “unbeknownst”!))

I remember that I liked the language. It was clean and relatively compact, it had a largish and useful library, it was like C++ and Java (benefit? really?) and it had a command-line compiler. My impression at the time was that it was more suitable for small and quick programs, and very suitable for teaching programming. I even suggested it to my teachers at university as a replacement for Pascal, which was then thought as the first language to CE students (this was maybe 4 years before I met Lisp, or better yet, Python.) This was also before the whole .NET fucked-up-ness happened with all the WinForms and ASP.NET and whatever other shit they are peddling these days. In those days, .NET and C# produced console applications, unless you ventured into the river of diarrhea output that is the Win32 GUI API; but that was pretty much what you generally had, back then.

Anyways, my shallow and brief delving into the world of .NET was barely deep enough for me to familiarize myself with the inner workings of MSIL and the JIT compiler and the virtual machine. I learned little about these, and I have not kept up with the new developments in .NET, and I have no regrets there. I generally hate GUIs and network technologies that aim to solve all problems on all levels for everybody. They may suit some, and I have absolutely no doubt that many .NET-based applications wouldn’t have been as easy-to-write for other libraries and runtimes¹. But I don’t generally like .NET and this opinion (I suspect) would be very hard to change.

The most obvious reason for this obvious dislike is the one I mentioned above. .NET is the champion of the all-for-all thoughtcrime. More than anything else that I have seen, it tries to do all for everyone and everything; without giving them an inkling of what the hell is really going on on any level below the most superficial. This may suit some, but it shouldn’t.

I seriously believe that every programmer needs to know what’s going on under the hood. Total abstractions almost never work beyond the most simple and trivial cases². If you don’t know jackshit about your platform and your programs seem to have worked so far, you are just lucky. Let me give you an analogy. If you don’t know anything about how cars work and you drive one, when your cars breaks down in the middle of nowhere and you have no means of communication, the you are royally fucked. The fact that this has not happened so far, it just means that the Random Number Gods have smiled upon you so far. It may never happen, but it just as well might. That’s the way it is with programming. Except that the level of quality discrepancies among software and hardware products that you use is much wider.

All programming languages abstract the platform in some form and manner. But as some languages hide not much and what they hide, they do with much shame and much apologies (Assembly, C, etc.) others do as much as they can to distance you from the hardware. They even boast this feature!

In short, every good programmer that I know and I know of knows the whole stack of software and hardware underneath deeply and intimately. In fact, it might even be true that the better they know this mess, the better they are³.

Let me conclude now. I am not saying that technologies like .NET and Java and all those “high-level” languages are useless. I’m just saying they make it harder to be conscious about the actual platform and the rest that lies under your code. I’m pretty certain that the best .NET programmers can pretty much generate the MSIL code and the machine code that their compiler and the JIT compiler generate for any given part of their code. Maybe you should too.

This should be no news to anybody who has anything to do with writing and distributing C/C++ applications on Windows, but Microsoft has finally decided to drop the fucking SxS shit for Visual C++ 2010 CRT and go back to the sweet old days of plain, distributed-alongside-your-application DLL files! (Read here if you don’t believe me! I don’t know how far one can trust MSDN and how long that link will stay valid (I mean, how hard is that?! Keep your stupid fucking links valid, you idiot douche bags!) but there it is for now, and I have verified it on VC2010 RTM.)

How fucking twisted is that?! I’m actually rejoicing because we are going back to DLL Hell! But after experiencing the abyss of WinSxS Hell, I would happily crawl back to the open and only mildly tormenting depths of the good old DLL Hell. This means that I will (hopefully!) never ever have to mess around with ass-busting manifests and colossally subtle version conflicts and hunting down every single gods-damned version of every single fucking-gods-damned CRT component that might or might not have been subject to some whimsical patch by the morons at Microsoft in the past year, in one or other version of Windows. This means that I will just distribute the fucking version of the CRT that seems to barely work alongside my applications (that is, in the same directory) and it will probably (say 30% instead of 1e-10%) work, and no one will be able to override their usage behind the poor hapless user’s back (using conventional methods; that is. Everybody knows how easy it is to hijack a function call into a DLL in Windows; which I have to say is not necessarily a bad thing.)

And don’t anyone dare ask me why I link to CRT as a DLL in the first place, instead of a statically linked LIB!

P.S. I have decided to write as I think (regarding the usage of curse words.) So no more fraks and friggins and butts and backsides. Deal with it.

I found this person who was looking for a place to put up a blog. I gave that person space and here is the result. In my opinion, it is definitely worth a read. It contains mostly scraps of fiction with a theme of fantasy, some dark poetry and the like.
You know how the world is for a new blogger! Go and have a look, and leave a comment or two even if it is a one liner. Encourage the blogger if you like it at all.

I saw my left hand burning tonight. It was engulfed in blue and yellowish flames of naphtha. I would have watched and enjoyed the sight much more if my right hand hadn’t been aflame before with my Zippo in it and I hadn’t thrown it into a glass of water!
You see kids, there is actually no way of putting out a Zippo if it’s out of the case, say for refueling. I would really have liked to stop and take a picture for demonstration purposes, but saving a drowning Zippo is much more important.

Fanafzar Game Studios, the company I work for and the makers of Garshasp with the help of CGArt.ir society and several notable others are orchestrating a 3D modeling competition for aspiring and experienced game artists. You can read every thing about it over here.

The reason’s for holding such an event is at least three-fold. First is to show how many talented artist live and work in Iran. Second is to get them into a challenge that will benefit all of them as they work towards a common goal with each other. The third one is to find a few really talented and driven modelers and persuade them to come and work with us on our upcoming projects!

Oh, I forgot to say that the first prize is a PS3 bundled with Uncharted 2: Among Thieves! (I wish I was a 3D artist! No one gives such prizes to game programmers!)

So, even if you are not interested yourselves, please spread the word around.

http://adeli.ir/blog/?p=122

Back in the old days of the net, even before I was born, people did implement TCP/IP stacks. And since there weren’t much of a solid and standard specification (not to mentions decades of engineering experience in implementation and maintenance of network stacks,) these implementations tended to be buggy, unstable and non-conforming. To test these various TCP/IP implementations (such as they were,) people used to come together and just test them against each other and compare their functions. These sessions and discussions and reviews were called “TCP and IP bake offs”. It has been said that as a result of these discussions, the specifications were as likely to change as the implementations!

These dudes pretty much built the whole frakking Internet without the bureaucracy and the 3000-page conformance guidelines and the 2-million line test suit or the 12 years worth of committee meetings. Their procedures, and much more importantly their attitudes is quite concisely demonstrated in RFC 1025.

I had a perfect nightmare
on a starry torrid sea:

I am cast to prison at a
crippled demon’s plea.

The demon has 3 faces
all are laughing down at me.

The Banker with his filthy lucre
sets the game astride.

The General with raging might
lets forth a battle cry.

The Judge locks now the metal
tomb where I’m meant to die.

… But vengeance is
a brutal beast
not held by any cell

My wit is steeled
My blade is wet
So sound the Reaper’s bell.

Banker, General and Judge!
You all shall burn in Hell.

– From The Dishwasher: Vampire Smile‘s debut trailer.