attack of the clones (or PictureFlow-ing a phone, a set-top box, and an iPod)

Cover Flow effect for Greenphone

Trolltech Greenphone is a smartphone for Qtopia-based mobile-platform development. Although not available anymore, developing Greenphone is useful to learn Qtopia, and vice versa. You can still learn Qtopia/Greenphone without the real device using the Greenphone SDK within VMWare trick, which what I used to test my PictureFlow code some time ago.

But of course running a program inside an emulator is different than in a real 3-d device. Seeing is believing. Jonas Hurrelmann was very nice to check PictureFlow on Greenphone, as evidenced from his YouTube video. As expected, the performance is quite satisfactory. Kudos to Jonas!

Cover Flow effect for Dreambox

Dreambox is a satellite set-top box running Linux. Because it runs Linux and can be modified, it is popular among hackers. In case you miss it, few weeks ago Brad Hughes compiled and built Qt for his Dreambox DM 7000. Check his demo video...

...and wait 41 seconds and see what is shown. Does that look familiar to you? (Hint: read this blog post again from top)

Cover Flow effect for iPod

Huh? Doesn't "Cover Flow for iPod" sounds too Zen-like? Didn't His Steveness show it before?

Well, this one is different. Jonas Hurrelmann (yes, the same Jonas, kudos to him again) ported the PictureFlow code to Rockbox and then ran it on the iPod 5.5G. The obligatory video is his YouTube clip:

Careful readers might notice that it should be a Rockbox plugin (for those who live under the rock, Rockbox is the ultimate firmware replacement for many music players and it is completely open-source). Since Rockbox can support not only Apple iPod, but also Archos Jukebox, Sandisk Sansa, Cowon and many other popular MP3 players, this opens the possibility that those devices might enjoy CoverFlow-effect as well. Let's wait for Jonas (and perhaps others) for further development.

More attacks are still needed....

Update: check also PictureFlow attacking other mobile devices.

looking for simple but fast 32-bit microcontroller

Dear Lazyweb,

It's been a while since I have been doing microcontroller-related projects. Now it's time to get my feet wet again. For an exciting new project, I'm a looking for an evaluation/development kit for an affordable but high-performance (best-bang-for-the-buck) microcontroller. Preferred is 32-bit, but 16-bit is manageable. Important here is the availability of the I/O ports, I don't care much for USB or Ethernet or even wireless support. Power is also not important. Built-in ADC will be a bonus, but not necessary. The program will be lightweight enough so no need for megabytes of memory.

Surprisingly, I have difficulties finding such a board/microcontroller. Seems that 32-bit microcontrollers todays are geared more toward multimedia solution (image+audio processing), portable networked device, or automotive/industrial applications with different (and confusing) bus types. All I want to do is relatively simple but fast processing of some data. Unfortunately, I can't stick with 8-bit system anymore because of the nature of the application. So what I am searching is rather a bare-bone, blazing-fast microcontroller with tons of digital I/O. The good old 8051 on steroids.

The closest I could find so far is Microchip PIC32 (though I wish it had more input output pins) with its $50 Starter Kit. However, I'm sure there are loads of similar stuff. Where are they?

PS: I'm quite proficient with FPGA so I guess the fallback solution will be a soft-processor in an FPGA, but I would like to stay with the plain microcontroller if I have the choice.

q.o.t.d

Open source is a radical idea itself. I think you either get open source or you don't.

-- Donald Rosenberg, on The secret to Red Hat's success

Fun with rotations

The following puzzle might be trivial if you study physics and deal with lots of optics. Or, if you are simply good enough with math, especially with geometry.

First, visualize a 3-d Euclidean space where x-y plane is the "floor" and z points "upward". You are somewhere in this space.

Now assume you have two rotation operators denoted as Q and H. The idea is: both have fixed rotation angle but freely chosen rotation axis.

The common thing of both operators is that the rotation axis can be anything but it must lie on the x-y plane (i.e. the floor), so you can have [1 0 0]^T or [0 1 0]^T as the rotation vector but not [0 0 1]^T. This way, the rotation vector can also be specified by its angle with the x axis. If we denote the angles as a and b for the rotation vectors of Q and H, we write the rotation operators as Q(a) and H(b). Hint: the rotation vector of Q(a) is thus [cos(a) sin(a) 0]^T.

Next comes the difference. The rotation angle for Q is 90 degrees, while the rotation angle for H is 180 degrees.

Here is the quiz. Supposed you have a point at [0 0 1]^T. This point is first rotated by Q(a). The result is then rotated again by H(b). The questions are:

1. What will be the locus of the final result?
(Hint: find the result as function of a and b).

2. Can you replace the whole transformation (for the point at [0 0 1]^T only) by just one Q operator? If yes, determine the rotation vector of this Q.
(Hint: compare the answer to first question with the transformation result by only one Q).

Spoiler Warning: if you have passion for puzzles, go away and solve this one by yourself first. Then come back again here and compare it with the following analysis.

Remark

Although at a glance it looks complicated, the questions are quite easy to solve. It is a matter of doing rotation (couldn't be simpler!). The standard 3x3 transformation matrix will do the job, but usually you can do it much faster if you are familiar with quaternion. For convenience, here are the quaternions for Q and H:

Q(a) = 1 + i*cos(a) + j*sin(a)
H(b) = i*cos(b) + j*sin(b)

(Exercise: normalize the above quarternions)

Then, use the quarternions to find the rotation result with the usual quaternion algebra.

Answer to question #1

After rotated by Q(a), the point [0 0 1]^T will become [sin(a) -cos(a) 0]. Transform it with H(b) and you will get [-sin(2*b-a) cos(2*b-a) 0]^T.

Note: what you get is actually [x y 0]^T with:

x = cos(b)*sin(a-b) - sin(b)*cos(a-b)
y = cos(b)*cos(a-b) + sin(b)*sin(a-b)

which could be simplified using some trigonometric relations.

For the trained eyes, [-sin(2*b-a) cos(2*b-a) 0]^T is the equation for a circle because sin(2*b-a)^2+cos(2*b-a)^2 = 1. The z coordinate is 0, means the circle is on the floor.

So, the answer to the first question: the locus will be a unit circle on the x-y plane.

Answer to question #2

After rotated by Q(p), the point [0 0 1]^T will become [sin(p) -cos(p) 0]^T. This is also a unit circle. It means, direct transformation of [0 0 1]^T by Q(p) will also give a circle. That's the answer: yes, rotation by Q(a) followed by H(b), for the point at [0 0 1]^T, can be replaced by one Q operator.

But how to find p in Q(p)? Recall [-sin(2*b-a) cos(2*b-a) 0]^T from the answer to the first question. Comparing it with [sin(p) -cos(p) 0]^T yields p = pi - a + 2*b.

Or, you can specify the rotation vector of Q(p) directly as [-cos(2*b-a) -sin(2*b-a) 0]^T.

Not too difficult, isn't it?

three is the magic number

The best thing about cooking is: there is no right or wrong. It means, you will not make any mistake.

After some experiments, I found that adding some extra stuff when preparing mie goreng (a.k.a fried noodles) gives it a distinctive and unique taste. It's not like the common fried noodles anymore. Here I share the secret: basil leaves cut into pieces, few slices of ginger, and a bit of curry powder. Like a charm.

Aller guten Dinge sind drei.

iPhone in Germany

In Germany, iPhone is sold with a price tag of 399 euros. But then you must sign a 24 months exclusive contract with T-Mobile, with a minimum plan of 49 euros monthly fee. This means (ignoring depreciation) at least you'll lose 1575 euros in total. With one time activation fee, that makes it 1600 euros. On top of that, if you want to actually make a call, be ready to face the 39 cents/minute rate, which is (insanely) expensive compared to other offers. The fact that it is T-Mobile is also interesting, I don't know whether it means a bless or a disaster.

Due to a move from Vodafone, T-Mobile is also forced to sell an unlocked iPhone. So you can pick your favorite provider but only if you're ready to shell out 999 euros for that. Might be better, but 999 euros? You can get 21 Motorola w205 with that amount of money :-) Or do/buy other sensible stuff.

Usually I am not that skeptical. But this does not sound like a success recipe at all.

SpeedCrunch: "Nona" edition

SpeedCrunch version 0.9 has just been released. The improvements are not really user visible, but check the ChangeLog and fixed bugs, nevertheless. Also, this release is available in 17 languages (and contributions are welcomed).

Source tarball and Windows installer are ready for consumption. Go to http://code.google.com/p/speedcrunch/ and get it while it's hot. Binary packages for major Linux distributions usually follow soon.

And now that the first ever release of KDE 4 is on the horizon, it's time to think to start enabling KDE integration in SpeedCrunch.

Note: Nona is nine ninth in Portuguese.

extraordinary

The only extraordinary thing about me is that I am just an ordinary man.

(on thinking about myself)

Random number 1..5 to 1..7

The task is to solve this puzzle:

Given a function which produces a random day Kliwon, Legi, Paing, Pon, Wage, write a function which produces a random day Sunday to Saturday

OK, I modified the question a bit. Read about Anno Javanico if the names of the day sound strange to you. Originally, it says:

Given a function which produces a random integer in the range of 1 to 5, write a function which produces a random integer in the range of 1 to 7

This is well-known as one of the so called Microsoft/Google interview questions. There are million ways to solve it. Here is my take. Bear in my mind that my math skill is mediocre and I never studied computer science, so don't be surprised if the next few paragraphs look bogus and stupid.

Spoiler warning: If you have passion for puzzles, go away and solve it and then come back again later. Don't let this blog entry spoils the fun for you.

First, let's assume the random number 1..5 is generated by the following (the randomness, or lack thereof, of stdlib's rand() doesn't play any significant role here):

#include <stdlib.h>
int rand5()
{
 return 1 + rand() % 5;
}

Now we must write rand7() which gives an integer between 1 and 7 and which is allowed to call only the above rand5().

The trivial solution, which you should have in mind in a fraction of seconds, is:

int rand7()
{
  return rand5();
}

because nowhere it says that the original nor the new function must give a random number following a specific distribution, e.g. uniform distribution. Of course this can or can't be the real answer, depends on how you look at it.

The next logical step is assuming that the return value of rand7() must have a uniform distribution. The probability to get one of the number in the range of 1..7 is therefore approximately 0.143.

So what comes to mind is to reduce 1/5 probability from rand5() to 1/35, then increase it again to 5/35, which equals to 1/7. The former can be done by calling rand5() several times and treating the first result as 1..5, the second as 6..11 and so on until 31..35. The latter is easier, it's just a modulus operator. The code for this idea (which is shorter than the explanation above):

int rand7()
{
 static int c = 0;
 int x = rand5() + c;
 c = (c + 5) % 35;

 return (x % 7)+1;
}

(I know static variables can be evil, but that's another chapter...)

The disadvantage is obvious, the result is not completely random. For example, the first call will not yield 1 or 7 at all. Another variant is then by making c a bit random, though now that requires two calls to rand():

int rand7()
{
 static int c = 0;
 int x = rand5() + c;
 c = (c + 5*rand5()) % 35;

 return (x % 7)+1;
}

Another nice solution is by using rejection sampling, similar to the famous Box-Muller transform. Here we expand the range of 1...5 to 1..25 and reject anything larger than 7. The code is:

int rand7()
{
 int x = 8;
 while( x > 7)
  x = rand5() + 5*rand5() - 5;
 return x;
}

Pity that we throw away 8..25. It can be improved by reducing the rejection range to 22..25, IOW we would take anything in the range 1..21:

int rand7()
{
 int x = 22;
 while( x > 21)
  x = rand5() + 5*rand5() - 5;
 int r = 1 + (x % 7);
 return r;
}

(or, further by going to 1...125 and rejecting 120..125).

Modulus of 7 can be "optimized" by hand, this is because 7 is a Mersenne prime. For the details, see what I wrote before on modulus with Mersenne prime. This looks useless and even obfuscates the code, but it's harmless and you can tease your interviewer :-)

int rand7()
{
 int x = 25;
 while( x > 21)
  x = rand5() + 5*rand5() - 5;

 int r = (x >> 3) + (x & 7);
 r = (r >= 7) ? r - 6 : r + 1;
 return r;
}

Care to share your solutions?

PictureFlow on another real device (or Cover Flow for HTC Touch)

Update: see also PictureFlow running on different mobile devices.

HTC Touch is a touch-screen smartphone running Windows Mobile 6.0. It is armed with 200 MHz 32bit Texas Instruments OMAP 850 processor and 2.8 inch color transflective 240 x 320 screen. Like other Windows Mobile devices, HTC Touch is interesting because Qt runs also there, using Qt/WinCE.

After Chumby, HTC Touch is another real device that enjoys Apple-like Cover Flow effect, of course by using PictureFlow. Espen recently showed PictureFlow running on his HTC Touch, as can be seen in his YouTube video:

"Awesome", according to him. We trust you, Espen :-)

Now I know that someone must have tried this on the Greenphone. Can anyone give a video or even a picture?

(Picture from HTC Touch product page)

deja vu

long weekend

Downtown is like a dead city.

Today is Allerheiligen (All Saint's day) and it's public holiday in some states in Germany (Baden-Württemberg, Bayern, Nordrhein-Westfalen, Rheinland-Pfalz und Saarland).

Of course, like many others, wisely I take vacation on Friday, thereby giving me a very nice and enjoyable long weekend.