GBuffer.net

A while back I was looking for a good way to create a very strong password for my KeePass Password Safe. If I was going to put all my passwords in to one database, it better be protected by a good password – a very good one, one which I would not be able to remember. Of course this does not mean I do something stupid like write it on a piece of paper. Duh!

• A USB stick? Ah too simple.
• YubiKey? Sounded very cool initially, but only can work with one password at a time and another device to take care of. And it was USB – too much friction if I had to enter the password 5-10 times a day.
• My phone: Ah perfect, it’s very personal. I never leave anywhere without it. WHich means it won’t be forgotten in my USB port when I’m out. And yeah, it’s got bluetooth (no shoving stuff in to usb ports).

So I set out to make a bluetooth app that could exchange keys with KeePass. Head on to the KeyXchanger page to get more info and download it.

The stand alone password exchanger

Even if you do not use KeePass, you can still use Key Xchanger. The download contains a stand alone application that allows your computer to exchange passwords with your phone. Some features of Key Xchanger are…

• All passwords are stored on your phone encrypted.
• Passwords on the phone are encrypted and can only be decrypted by an authorized computer
• Your password is not compromised even if you loose your phone, since one needs to attack both your phone and computer. This is extremely unlikely to happen.
• Passwords are never stored on the PC and are discarded immediately after being used.
• You can enter passwords in to almost any application on windows

Due to the large number of phones out there I would appreciate it if you could tell me if the application worked for you.

Recently when automating certain tasks, I came across the need for a command line app that would close windows applications in a clean way. After a lot of searching I was surprised not to find something to do this simple task. Yes there a lot of tools to kill an application, but that was not what I was looking for.

Why?
Well, a lot of applications perform a lot of important tasks before they close. These range from saving settings, asking you to save files, releasing hooks. Whatever the task may be, if you killing an application stop it dead in it’s tracks and the app does not have a chance to perform these tasks.

So TerminateApp is the result of this necessity.
You can specify the process by it’s name or by it’s process ID. If you really are impatient, you can even kill the application if the application refuses to terminate within a given amount of time.

How does it work?
TerminateApp sends a WM_QUIT message to all window handles within a specified process. So it will only work for applications that process the WM_QUIT message. This worked fine for the several applications I tested it on, but I cannot guarantee it works on all the apps out there. This would depend on the way the app has been written.

[ Download TerminateApp]
[ Download Source Code]

It’s been some time since anything technical has been posted here. Been spending my time building up a stronger base since the top seemed a little wobbly.

Got a new demo out today. It’s something that some people (including me) call vector textures. A very interesting technique that uses the existing texture resizing methods implemented on the GPU. These days it’s hard to find graphics techniques that manage really makes use of everything the GPU provides us with. What’s even nicer is that this technique could improve existing methods of rendering things like text and could even be extended to rendering blades of grass or leaves on a tree where the possibility of zooming in to a leaf is very real.

Go ahead, read more about it and download the demo here

Water you can swim in… Well only virtually This is my very first graphical demo built on a excellent open source framework called G3D.

Demo is based on two chapters in the ShaderX book.
“Rendering Ocean Water”
by John Isidoro, Alex Vlachos, Chris Brennan
And
“Rippling Refractive and Reflective Water”
by Alex Vlachos, John Isidoro and Chris Oat

Features include

1. Realtime vertex displacement
2. Full control over speed, wave direction, amplitude and frequency
3. Additional detailing via two normal maps
4. Fake refractions that look real
5. Real time reflections or reflections via environment maps
6. Fully configurable water color via texture maps

A few months back, I was given an interesting project to work on in an interview test. The test required me to build a small particle system for the Nintendo DS, using the homebrew tool chain. Well I don’t know if I was stupid or just plain blind, but I was unable to find a sqrt in their standard math.h include file. Posting questions on a forum resulted in no replies and time was running short. I had only about a week to make my submission. So I decided to write my own implementation. After all I remember doing this in high scool.

The old school method…

As usual I headed over to google and after a little searching I found it on this website. Well this was exactly what I was looking for, but unfortunately it required too much guessing at every step. Now as we all know computers are not good at guessing. All hopes of implementing a square root function quickly evaporated.

Next day in office, with some help from my coleague Ashwini Kumar, we came up with a very promising solution.

We found something interesting about the patterns a square root takes

sqrt(1.0) = 1.0
sqrt(10.0) = 3.1622
sqrt(100.0) = 10.0
sqrt(1000.0) = 31.622

Now for those of you who have not realized yet, sqrt(1000.0) = sqrt(10.0) * 10.0

Well this could work pretty well and all we needed to do then is just generate a look up table of the first 100 numbers and then just do a multiplication based on it’s 10th power. So I came up with this code…

// LUT for square roots below 100. Takes 396 bytes

const static float SQRT_LUT[] =
{
       1.000000f,      1.414214f,      1.732051f,      2.000000f,
       2.236068f,      2.449490f,      2.645751f,      2.828427f,
       3.000000f,      3.162278f,      3.316625f,      3.464102f,
       3.605551f,      3.741657f,      3.872983f,      4.000000f,
       4.123106f,      4.242640f,      4.358899f,      4.472136f,
       4.582576f,      4.690416f,      4.795832f,      4.898980f,
       5.000000f,      5.099020f,      5.196152f,      5.291502f,
       5.385165f,      5.477226f,      5.567764f,      5.656854f,
       5.744563f,      5.830952f,      5.916080f,      6.000000f,
       6.082763f,      6.164414f,      6.244998f,      6.324555f,
       6.403124f,      6.480741f,      6.557438f,      6.633250f,
       6.708204f,      6.782330f,      6.855655f,      6.928203f,
       7.000000f,      7.071068f,      7.141428f,      7.211102f,
       7.280110f,      7.348469f,      7.416198f,      7.483315f,
       7.549834f,      7.615773f,      7.681146f,      7.745967f,
       7.810250f,      7.874008f,      7.937254f,      8.000000f,
       8.062258f,      8.124039f,      8.185352f,      8.246211f,
       8.306623f,      8.366600f,      8.426149f,      8.485281f,
       8.544003f,      8.602325f,      8.660254f,      8.717798f,
       8.774964f,      8.831760f,      8.888194f,      8.944272f,
       9.000000f,      9.055386f,      9.110434f,      9.165152f,
       9.219544f,      9.273619f,      9.327379f,      9.380832f,
       9.433981f,      9.486833f,      9.539392f,      9.591663f,
       9.643651f,      9.695360f,      9.746795f,      9.797959f,
       9.848858f,      9.899495f,      9.949874f,
} ;

float SqrtLUT(const float fNum)
{
     int      nIdx ;
     int      nApproxLog = 0 ;
     float    fCopy = fNum ;
     float    fMultiplier = 1.0f, fDivider = 0.1f ;

     if (fNum < 100.0f && fNum >= 1.0f) // Use LUT

     {
         nIdx = static_cast<int>(fNum) ;
         if (nIdx)
         {
             --nIdx ;
             return SQRT_LUT[nIdx] ;
         }
     }

     // Number is above 100, bring it down and just multiply the answer

     if (fNum >= 100.0f)
     {
         while (fCopy > 1.0f)
         {
             fCopy *= 0.1f ;

             if ((nApproxLog & ~3) && (nApproxLog & 1))
             {
                 fMultiplier *= 10.0f ;
                 fDivider *= fDivider ;
             }

             ++nApproxLog ;
         }
     }
     // Number is below 1. Bring it with in the 1-100 range

     else
     {
         // ...
         // Something very similar to the if block above
         // ...
     }

     return GuessSqrt(fNum * fDivider) * fMultiplier ;
}

This worked really well for numbers under 10^3, but as the numbers grew larger the errors started growing larger and larger. Even a LUT of doubles instead of floats just offset the errors to a slightly larger numbers.

Time to look for a new solution…

The Babylonian Method

A quick recap of old college textbooks revealed a suprising simple method. This method only produces an estimate, but the accuracy of the estimate grows rapidly on every iteration. For those of you who need a quick recap of the algorithm, here is a recap from http://pballew.net/oldsqrt.htm

1) Guess a number for the square root
2) Divide the number by the guess
3) Average the original guess and the new guess
4) make this average value your new guess and
5) Go back to step 2 if the accuracy of the result is not satifactory…

The problem with this method is that it still requires a guess like the old scool method, but this requires a guess only once and the rest of the guesses are relatively small calculations which don’t need any sort of loop. Besides with our LUT method we can now provde a fairly accurate guess relatively fast. So the initial implementation looked something like this…

const static int gIterations 20 ;

float mSqrt(const float fNum)
{
 float x1 ;

 x1 = GuessSqrt(fNum) ; // Just uses the LUT function mentioned above

 for (int i=0; i<gIterations; ++i)
 {
 x1 = ( ( fNum / x1 ) + x1 ) * 0.5f ;
 }
}

After a little trial and error I decided the the number of iterations are best kept at 12.

The end result

Turns out it aint that bad. On my old 1.6Ghz system this implementation is only 0.002 seconds (approximately) slower than sqrt() when calculating 10000 square roots.

My implementation (available in the attachment below) has a much more complicated implentation that does a loop unwind using C++ templates. How else can I justify spending large amounts of time spent trying to understand Andrei’s book, Modern C++ design . As of now that book has become my latest programming fad.

You can download the VS.Net 2005 project of my implementation (Attached at the end of this blog entry). The .cpp file has code to check the speed and accuaracy of the results against the standard CRT sqrt function. Most of the code that you should be interested in, is in main.cpp. If you want to use the function in your own project, just copy everything except the main function in main.cpp

Until next time

So, yesterday I was getting down to watch a relaxing movie and I realized that (yet again), that the SubRip file was not properly synced with the video. I decided that I've had enough of this. It's happened far too many times. So I opened up the .srt file in TextPad and realized everything is right there in plain text. That's probably because M$ or the MPAA did not have a say in the matter. Anyway, so instead of spending 30 mins searching for a new subtitle file on DivxSubtitles or OpenSubtitles I decided to write my own app that will offset the timings in an srt file.

For those of you in a similar situation, I'll save you 30 mins of searching or writing a quick script.
Just click here and follow the instructions on the following page. You should be done in under a minute.

Yesterday I finally found a use for compile time checking. I remembered reading this up in Andrei's book 'Modern C++ Design'. So I got down to implementing it in VS.NET 2005.

His code (code below) seemed to work well in theory, but knowing MS, that's as far it goes.

template<bool> struct CompileTimeChecker
{
     CompileTimeChecker(...);
};
template<> struct CompileTimeChecker<false> { };
#define STATIC_CHECK(expr, msg)
     {
          class ERROR_##msg {};
          (void)sizeof(CompileTimeChecker<(expr) != 0>((ERROR_##msg())));
     }

Turns out that MS VS.Net had some complaints about the code above…

error C2066: cast to function type is illegalerror C2070: 'CompileTimeChecker (main::ERROR_ONE_NOT_EQUAL_TO_ONE (__cdecl *)(void))': illegal sizeof operand

At first I thought I’d take the easy way out and just throw an error using a #pragma. But then that would beat the very purpose of the code being compiler independent. After some 30 mins of trial and error, managed to get the same code (code below) working with a few minor modifications.

template<bool> struct CompileTimeChecker
{
     CompileTimeChecker(...){};
};

template<> struct CompileTimeChecker<false> { };

#define STATIC_CHECK(expr, msg)
{
     class ERROR_##msg {};
     ERROR_##msg y ;
     (void)sizeof(CompileTimeChecker<(expr) != 0>((y)));
}

Now calling something like…

STATIC_CHECK(sizeof(char)>sizeof(int), SIZEOF_CHAR_NOT_GT_SIZEOF_INT) ;

will result in a compile time error that looks something like this…

error C2440: '<function-style-cast>' : cannot convert from 'main::ERROR_SIZEOF_CHAR_NOT_GT_SIZEOF_INT' to 'CompileTimeChecker'> No constructor could take the source type, or constructor overload resolution was ambiguous

Until next time, happy coding!

This coding ‘best practice’ is the first in the series of many posts that I will be making. Many of them have been introduced to me only recently, so it’s unlikely you will see this in my old code. I am making these posts as I think they are essential to every C++ programmer.

Lets get started on the first one…
Some may call this an opinion, but I call this a good programming practice.
Don’t declare a macro unless you cannot do without them. Below I have presented some problems plaguing macros and some workarounds.

1. Macros modify the code before the compiler sees it. This makes it harder for you to debug your program, step into code and find bugs.

2. Macros don't obey scoping rules. So the following example

// The macro below could very well be in another header file
// that you never seen or totally forgot about
#define width 20

// And then you name a variable the same name,
// forgetting there was a macro with the same name
// It’s than you think to forget, especially if the macro is
// hidden in one of those header files
void RenderRect(int height, int width) // …

Workarounds
Below are some workarounds for some common uses you might have for macros

// 1 //// Global strings
// macro:
#define SZ_HELLO "Hello world"
// workaround:
char const szHello[] = "Hello world";

// 2 //// Global setting
// macro:
#define NMAX 5
// workaround:
const int nMax = 5;

// 3 //// Generic functions
// macro:
#define SQUARE( x ) ((x)*(x))
// workaround:
template<typename T>
T inline square(T &x)
{
  return x * x ;
}

End note

Of course there are some places where only a macro can get the job done. In these cases go ahead and use a macro, but follow a strict naming convention for your macros so you will not confuse them with a standard variable later on.

"You're bound to be unhappy if you optimize everything"
– Donald Knuth

As with every new programmer I would spend endless hours trying to squeeze optimization out of every small piece of code on my engine . I wanted it to be the fastest. I always thought that writing every line of code in assembly would make a super fast engine, not knowing that the compiler would probably optimize my code better. I would spend long hours studying SSE instructions. Well one advantage is that I am no longer afraid of ASM , but I was generally unhappy that my engine was not be super optimized and nearly as fast as a commercial game, even though it was probably doing only 25% of the tasks. Colleagues (just as inexperienced as me at the time) would come up to me and say 'Hey, you know this guy, he wrote a whole OS in assembly'. And we would all think that this guy wrote the best OS in the world. But hey, wait a minute. Then why are over 80% of the desktops still using Windows?

Well, it's been a long time since I have added anything more than pictures to my blog.

A lot has happened since I first started this blog.

The most important realization being that my old programming style is utterly junky.
The main problem is that I always sit down and start coding without any design and planning what so ever. And finally when I hit a road block I change the code. In fact the engine that I wrote went through so many changes, it's impossible to say it follows any solid programming style.
To a large extent I knew my programming style was quite crappy, but just didn't know any alternate way. I was always against C++ inheritance and was always for a static program structure, but really didn't know any proper implementation technique. Luckily for me, I discovered a whole new world of templates. Boy are they great!!! I think inheritance should be left at college level just so that we pass our exams.
Anyway this means that my precious project is a whole pile of binary junk. And now I have to start over. Oh well. Better late than never.
And then I learn that a whole bunch of other techniques are actually a big no-no. Some of which I am still quite hesitant to give up.

Luckily for me I met a really talented guy and he explained some good programming practices and I soon realized I was breaking most of them. There are one or two I don't agree with him on, but those don't make such a big difference in any case IMHO. On the other hand I was quite happy to realize that my basic priciples like having static code and getting the compiler to do as much work for me were the best principles to follow. It's just that I had no idea or techniue of how to do these things. (I'm actually making excuses for bad programming here)
I plan to write out the good programming practices that were told to me, so that everyone can start writing better code in future.

I also seem to have a decent amount of exposure to Unreal Engine 2.0 and learned a lot of new tricks in the trade. One thing I was surprised to learn is how well they followed most/all the good programming practices. It's amazing. I always knew that they were doing it right. This also means that my precious project is junk overnight and I have to start over. I have no idea if I am going to and if so when. I am thinking of keeping it small and simple and making just a rendering framework to test shaders and other things I write. Besides I still have another project that I'd like to release. I really need to open this one up and see how badly it has been contaminated by my bad planning and poor programming practices.

Other than that I put up an article that I wrote a long time back. I tried submitting it to DevMaster.net and gamedev.net. Both still haven't put it even after nearly 6 months after initial submission was made. DevMater.net showed interest in putting it up strangely. I got tired of waiting and put it up on my own site. At least it is out there, and boy I am happy I did not put any code in to the article. In any case part 2 will be coming soon. Just need to get some formatting done on it.