Qt Quick hates me

I haven’t blogged since a while, because I do not do much KDE hacking lately, but today I’ve got around to playing with QML again.

The goal was to build something like a breadcrumb navigation widget, where the current directory is indicated by its name being written in a larger font. Here’s what I arrived at after a few minutes:

import QtQuick 1.1

Rectangle {
    width: 800
    height: 100
    color: "black"

    Row {
        anchors.horizontalCenter: parent.horizontalCenter
        anchors.top: parent.top
        spacing: 10

        Repeater {
            id: repeater
            property int currentIndex: 4
            model: ["/home", "/username", "/some", "/pseudo", "/path"]

            Text {
                text: modelData
                font.pixelSize: index == repeater.currentIndex ? 40 : 20
                color: "white"
            }
        }
    }
}

Close enough. Just adjust that alignment:

...
Text {
    ...
    height: 60
    verticalAlignment: Text.AlignBottom
}
...

Gah! Can you see it? The baselines are misaligned. Usually, you lay out text such that all letters “sit” on an even line (the baseline).

The documentation does not mention any type baseline alignment in a Row element (or any type of vertical alignment in a Row element, for that matter).

I then tried to hack around this problem by dropping the Row element and laying out the Text elements manually, but the elements in the repeater won’t anchor to each other. That’s probably a problem with the elements not being fully initialized when the anchor property is evaluated, but at this point I give up.

This has been my second experience with Quick. When I tried it for the first time, my goal was a Quick version of the Planarity game. I got stuck when I noticed that Qt Quick 1 does not have any kind of line or ellipse primitive (only rectangles and images). Really?!?

So, while I understand very well and appreciate the idea behind Qt Quick, I have come to the conclusion that Qt Quick hates me. Or I have a talent of hitting a roadblock within ten minutes, regardless of the general direction.

P. S. Turns out the WordPress WYSIWYG editor hates me, too. (Well, either me or the combination of <pre> and images.)

Introducing obs-tools: Doing away with ugly repository URLs on openSUSE

While I like openSUSE’s approach of ordering extra packages into addon repositories on their Build Service, I hate those ugly repository URLs. GUI users may just use the one-click install links on the package search, but command-line enthusiasts are out of luck.

To solve the problem, I’ve written two small Python scripts. obs-addrepo wraps zypper addrepo for Build Service repos:

# before
$ sudo zypper addrepo http://download.opensuse.org/repositories/Application:/Geo/openSUSE_12.1/ Application:Geo
# after
$ sudo obs-addrepo Application:Geo

obs-quickinstall is the 1-click installer for command-line users:

# before
$ sudo zypper addrepo http://download.opensuse.org/repositories/Application:/Geo/openSUSE_12.1/ temp
$ sudo zypper refresh temp
$ sudo zypper install --from temp josm
$ sudo zypper removerepo temp
# after
$ sudo obs-quickinstall Application:Geo josm

Both tools are now available as the obs-tools package (Git repo). Packages are currently building on the Build Service, the project page has installation instructions.

Bug of the day: How ConfigParser ruined my calculations

For my thesis, I have implemented a series of numerical applications. The core application (written in C++) uses simple INI-like configuration files for reading system parameters. For example:


[system]
name=example2
r1=1.0
r2=1.5
V1=-0.05
V2=0.1
[...]


Nothing exciting there, reading this is a breeze with QSettings. Now I needed to do some symbolic calculations, for which I chose Python and the excellent SymPy module. To read the system configuration, I chose the standard ConfigParser module.


parser = ConfigParser.RawConfigParser()
parser.read("scatttd.conf")
sysType = parser.get("system", "name")
# read system parameters
sysParams = dict()
for key, value in parser.items("system"):
    if value != "name":
        sysParams[key] = float(value)


That reads the “system/name” key, and puts all other keys (which are assumed to be floats) into a dictionary, so the system-specific code does not need to deal with the ConfigParser object.


r1, r2 = params.get("r1", 1.0), params.get("r2", 1.0)
V1, V2 = params.get("V1", -0.1), params.get("V2", +0.1)


This code gets the parameters in the system-specific code. Nothing exciting here. Except, stuff doesn’t work. The results of the following calculations suddenly don’t match my expectations (or the predictions made by my other programs).

Since the code after the snippet above is about 30 lines of SymPy magic (accumulating expressions that print dozens of lines onto my terminal), I suspected that some error occurred there. After about two days of searching for the problem there, and calculating everything by hand, something occurred to me when I looked at the debug output:


DEBUG V1 = -0.1


Didn’t the configuration file say “V1=-0.05”? Let’s have a look at the parameter dict:


{'v1': -0.05, 'v2': 0.1, 'r1': 1.0, 'r2': 1.5}


See the problem? “v1” has a lower-case “v”, so params.get("V1", -0.1) fails and returns the default value (-0.1). One glimpse at the documentation says that


parser.optionxform = str


solves the problem. Gah!

Lost for words

commit 740673c11aee9762987e3a205443ce1dec11aee8
Author: Stefan Majewsky <majewsky@gmx.net>
Date:   Sat Nov 5 00:11:37 2011 +0100

    lolwut?

diff --git a/tagaro/interface/board.cpp b/tagaro/interface/board.cpp
index 199c007..17dbdfc 100644
--- a/tagaro/interface/board.cpp
+++ b/tagaro/interface/board.cpp
@@ -42,7 +42,6 @@ Tagaro::Board::~Board()
 
 Tagaro::Board::Private::~Private()
 {
-       QList<Tagaro::SpriteObjectItem*> m_items;
        for(QList<Tagaro::SpriteObjectItem*>::const_iterator a = m_items.constBegin(); a != m_items.constEnd(); ++a)
                (*a)->d->unsetBoard();
 }

Introducing the Raven Music Server

While I was on my quest of reducing the memory footprint of a freshly launched KDE session, I found that the process which uses most memory just after startup is Amarok, which contributes over 80 MiB to 300 MiB total RAM usage. Now of course, Amarok has its reasons for a high memory usage: For example, its collection is backed by a MySQL/Embedded database. This memory footprint is justified by the plethora of features Amarok offers. But still, 80 MiB RAM usage is quite a lot when all I want to do (99% of the time) is to listen to some music files on the local disk. (My collection has 818 tracks at this very moment.)

Can we improve on that?

Looking at my desktop, I see the “Now Playing” applet. It shows the current track from Amarok, and has the basic media player controls (pause/stop/previous/next + seek slider + volume slider). Again, this is about all I need for an user interface while my playlist is filled. I remember that the nowplaying applet communicates with Amarok via DBus using the MPRIS (Media Player Remote Interface Specification) standard.

With all these impressions in mind, my target is clear: I want a headless media player which runs in the background and offers an MPRIS-compliant control interface on DBus. Something with a smaller memory footprint.

Intensive searches on the internet did not turn up anything of interest. Of course there are command-line music players (e.g. MPlayer), but those expect to be connected to a terminal for control. They cannot be run in the background, and there’s no nice GUI for them (like with the nowplaying applet). It looks like I need to do it myself yet again.

So here is the Raven Music Server (called ravend for short, as it is a daemon), which is now publicly available at git://anongit.kde.org/scratch/majewsky/raven. It currently implements the basic interfaces mandated by MPRIS version 2 (unfortunately the “Now Playing” applet supports MPRIS 1 only). The biggest missing piece is support for editing the track list, so at the moment you need to restart the process to change the playlist.

I have been productively using ravend for two weeks now, since one day after its inception, and I’m quite satisfied with it. And now that it is in a public Git repo, you can, too! Provided that you find pleasure in controlling your mediaplayer with commands like

qdbus org.mpris.MediaPlayer2.ravend /org/mpris/MediaPlayer2 org.mpris.MediaPlayer2.Player.PlayPause

Convenient user interfaces will become available, eventually. Even then, the Raven Music Server will probably not be interesting for end users. Power users may find this project interesting if they like to keep an eye on their system’s memory footprint, or want to have their playback continue even when the X server is terminated, or want to run a full-fledged media player on a headless system.

$ echo “A clear sign of madness”

What’s a clear sign that I’m a command-line addict? Not only do I have a custom prompt. My prompt is generated by a Python program, which has already grown to over 200 lines. My prompt detects Git and SVN repos, my custom build directory hierarchy, deleted directories at or above $PWD, common usernames and hostnames, shell type and shell level; and it’s still missing some features. What do you think: Is this madness? Does anyone else here use fully custom prompts?

A new take on autogenerated passwords

Today’s XKCD got me thinking about the strength of my own passwords again. Some time ago, XKCD already hit on the topic of password reuse.

A major argument for reusing passwords is that one can’t remember dozens of passwords for all services one uses. The typical counter-argument then is that one can use a password storage, be it a local application like KWallet or an online service. Such services allow you to protect multiple different passwords with one master password, which is the only one which you have to remember.

I am personally a user of KWallet, and must agree that it’s a great relief to have a backup for this crucial data available anytime. (Currently, KWallet stores over 200 passwords on my notebook alone, and there are probably unmerged passwords over at my desktop.)

But alas, both kinds of password storage solutions have a big problem: KWallet and friends are useless when you don’t have the wallet file around on the computer which you are currently using, you’re stuck. If the only computer carrying the wallet file gets broken, you’re totally lost. On the other hand, online storage solutions require a big deal of trust towards the provider running the service. As we saw earlier this year with LastPass, this trust is in general not justified.

So what can be done? I just had an idea which I did not see before anywhere. (Might be that I did not look closely enough. Please tell me if this idea has already existed before.)

If we don’t want to store passwords (because that requires both the availability of the storage and trust with a provider of this available storage), we need to generate them based on an algorithm. In other words,

#!/usr/bin/env python2

import base64, getpass, hashlib, subprocess, sys

def doHash(x):
    return base64.b64encode(hashlib.sha512(x).digest())

def sendToXClipboard(x):
    subprocess.Popen(["xsel", "-i"], stdin=subprocess.PIPE).stdin.write(x)

try:
    site = sys.argv[1]
except IndexError:
    sys.stderr.write("Usage: %s [domain]\n" % sys.argv[0])
else:
    masterPassword = getpass.getpass("Password: ")
    sitePassword = doHash(doHash(site) + doHash(masterPassword)) # variant 1
    sitePassword = doHash(site + masterPassword)                 # variant 2
    sendToXClipboard(sitePassword)

This Python script reads the name of a website, and prompts for a master password. It then combines both using a considered-secure hashing algorithm (SHA-512 in this case), and sends the Base64-encoded result of that to the X clipboard (so the password won’t be displayed on screen). Base64 is the best compromise between printability and string size.

The code shows two incompatible variants of obtaining the sitePassword. I won’t debate over which is better. The extra hashes in variant 1 are, strictly speaking, security by obscurity, as they don’t help when the attacker knows the algorithm. However, that’s not the main security feature. As far as I can see, this algorithm relies solely on the strength of the SHA-512 algorithm, which is (as of August 11, 2011) considered secure, and (if the attacker is brute-forcing) on the strength of your master password. So don’t choose “correcthorsebatterystaple”. 😀

Case study: Porting and modularizing an in-house Python application

Is it just a feeling, or has the number of technical posts decreased on the Planet? I definitely need to change that! (Update: The post got quite long, so I’ve shortened the syndicated version.)

These days, I’m usually working on my Diplomarbeit at the Institute of Theoretical Physics at the Technical University here in Dresden. (A Diplomarbeit is about comparable to a master’s thesis, though preparation time is one year since there was no bachelor’s thesis before it.) Our working group has an in-house application for inspecting iterated functions, which is quite intuitively called Iterator. Like many scientific applications, it has on one hand a very sharp functional objective, but contains tons of different tools and plugins.

As a part-time project besides my usual work, I’m working on a Qt port of the Iterator, which is currently based on wxWidgets. Of course, a port offers the opportunity to refactor badly engineered parts of the application. It clearly shows that all involved developers are first and foremost physicists which have not received any formal training in software design. Many antipatterns can be observed in the code. The most interesting is the existence of a god class called IteratorApp.

Implicit cast quirks

I thought I let you know why I just had to throw away three days worth of computation data.

double importantPrefactor(bool freeEvolution);

void multistep(bool freeEvolution, /* ... */)
{
    /* ... */
    const double pre = importantPrefactor(free);
    /* ... */
}

Yes, I used the wrong identifier inside the multistep function. Still it compiles and runs without error (except for the garbage data that comes out), because there’s a goddamn implicit cast from void(*)(void*) to bool. If you don’t believe this, try this:

qDebug() << "Is there a goddamn cast?" << ((bool) ::free);

Of course the conversion gives true because the function pointer is not null. Argh!

Optimization tricks: Fast sqrt(x^2 + y^2)

[Before I get to the boring (hah!) numerics stuff, some news: In order to test KDE Games on a touchscreen, and because I’ve wanted a tablet for a long time now, and because I want a 3G device, I’ve now ordered a WeTab 2. More news on this coming up soon when I have it in my hands.]

I’ve been optimizing my favorite jigsaw puzzle game Palapeli lately. Today, I looked at the bevelmap generation algorithm which renders the nice three-dimensional shadows atop the jigsaw pieces. There are a lot of norm computations in there, i.e. sqrt(x^2+y^2). All bells are ringing: There must be a way to optimize this.

Now nearly everyone who has to do with numerics and programming probably knows about the fast inverse square root which approximates 1/sqrt(x) very efficiently and sufficiently precise (about 1% maximum error). Using the inverse of this fast inverse square root does not really give an improvement, though. After all, the formula 1/InvSqrt(x*x+y*y) contains at least four floating-point operation plus everything that happens in InvSqrt.

This approach is especially inefficient because, in my special case, x and y are integers, and the result is also needed as an integer. Looking around the interwebs, I’ve found this lovely page on square root calculation, which also has a special algorithm for norms.

It all starts with two approximations to sqrt(x^2+y^2). The first one is max(abs(x), abs(y)), the second one is 1/sqrt(2)*(abs(x) + abs(y)). We need both because they are good for different values of x and y. To understand this, consider the unit circles of these approximations, that is: the set of x/y points where the approximation is 1. (You will probably make a sketch as you follow the discussion. I would have done one if it wasn’t so late already.) The unit circle for the first approximation is an upright square, while the second approximation’s unit circle is diamond-shaped (i.e. turned around by 45° compared to the first one).

An approximation is good when the unit circle comes nearby or touches the actual unit circle. For the first approximation, this happens when either x or y vanishes. The second approximation, on the other hand, is good when x and y are approximately equal. Now one can show that, at these conditions, the better approximation is always bigger than the other one. This means that we can define a third approximation by taking the maximum of both approximations. The unit circle for this approximation is a regular octagon, whose inscribed circle is the actual unit circle.

The approximation is thus always too big, except for the eight touching points of octagon and real unit circle, where approximation and exact result are identical. However, one can find a factor z such that the octagon, scaled by 1/z, is inside the circle. Scaling the approximation by (1+1/z)/2 thus distributes the approximational error to both the negative and positive side. Taking all these considerations into account, I’ve arrived at the following implementation:

template<typename T> struct fastnorm_helper { typedef T fp; };
template<> struct fastnorm_helper<int> { typedef qreal fp; };

//Approximates sqrt(x^2 + y^2) with a maximum error of 4%.
//Speedup on my machine is 30% for unoptimized and up to 50% for optimized builds.
template<typename T> inline T fastnorm(T x, T y)
{
    //need absolute values for distance measurement
    x = qAbs<T>(x); y = qAbs<T>(y);
    //There are two simple approximations to sqrt(x^2 + y^2):
    //  max(x, y) -> good for x >> y or x << y          (square-shaped unit circle)
    //  1/sqrt(2) * (x + y) -> good for x = y (approx.) (diamond-shaped unit circle)
    //The worse approximation is always bigger. By taking the maximum of both,
    //we get an octagon-shaped upper approximation of the unit circle. The
    //approximation can be refined by a prefactor (called a) below.
    typedef typename fastnorm_helper<T>::fp fp;
    static const fp a = (1 + sqrt(4 - 2 * qSqrt(2))) / 2;
    static const fp b = qSqrt(0.5);
    const T metricOne = qMax<T>(x, y);
    const T metricTwo = b * (x + y);
    return a * qMax(metricOne, metricTwo);
    //idea for this function from http://www.azillionmonkeys.com/qed/sqroot.html
    //(though the equations there have some errors at the time of this writing)
}

[License: I grant any entity the right to use the above code snippet for any purpose, without any conditions, unless such conditions are required by law. (This is the best approximation to placing the code in the public domain, which is not possible in my jurisdiction.)]

I have tested this function successfully on random input with T = double, float, int32_t. For integer types, this function needs only two floating-point multiplications, and thus runs much much faster than the trivial implementation and the InvSqrt-based solution. So please take this as my contribution towards Green IT, and reduce the time your computer spends calculating norms.

P.S. The extension of the above function for three-dimensional coordinates remains as an exercise to the reader. The only hurdle is to calculate the new prefactor z.

Update: As correctly pointed out by the commenters, if all you want is to compare the norm to some radius, e.g. sqrt(x*x + y*y) > r*r, the easiest solution is to avoid the square root and test for x*x + y*y > r*r instead.