The best kittens, technology, and video games blog in the world.

Wednesday, June 28, 2006

apt-get install feta

I've found this one out by accident. Debian packaging system has so many layers it can get confusing sometimes. Feta is a simple shell script that provides a common interface to all the layers.

They are often in a bit nicer format. Most commands seem to work the same way whether with .deb package file or with a package name.

Some common commands:

TaskTraditionalfeta
Installing a package filedpkg -i ~/foo.debfeta install ~/foo.deb
Installing a packageapt-get install foofeta install foo
Searching package descriptionsapt-cache search foofeta search foo
Which package contains filedpkg -S /bin/foofeta find /bin/foo
List of files in a packagedpkg -L foofeta contents foo

Tuesday, June 27, 2006

Robots


Last Saturday I've been on an MPI tour to Dagstuhl Castle. The main atraction were the robots.

Well, the robots were mostly playing football instead of more roboting activities like fighting aliens or killing all humans. The humanoid robots really sucked at it, the dogbots' (Microsoft Hellhounds) game was much more dynamic and interesting.

And there was a "robot girl" Lara. The point was to use some Nickel-Titanium memory metal instead of motors. That way it can be very light compared to traditional robots. And very energy-inefficient, so it's not like it's replacing traditional robots anytime soon. Because of energy problems Lara wasn't walking around too much, it just kicked a ball a few time, stuff like that.

Oh yeah, and there was a castle and some old ruins and some modern art gallery (including a few pieces of art made of vibrators), stuff like that.

Thursday, June 22, 2006

Network hacks

The usual Linux penguins are not cute enough, so we have a cuter polar animal for this post. So, I did some truly evil things to my network yesterday. :-D

Physical setup
The main computer is runs Ubuntu Linux and has two 100MBit ethernet interfaces, eth0 and eht1. eth0 is connected to the laptop, eth1 is connected to the router. Laptop runs Windows XP, and is connected to the main computer. The router is overfirewalled in a particularly fascist way and is beyond my control. This was the reason why I did the whole hack thing. Somewhere on the Internet there are HTTP Tunnel servers. Everyone can connect to them using encrypted connections to port 80, for greater anonymity or simply to get around stupid firewalls.
Layer 1
The first layer of the setup was just a normal network. Router gives the main computer IP through DHCP. Desktop-laptop connection is statically set up, I may change it to use DHCP later, but it's more convienient to leave it static during frequent reconfiguration time. Desktop is NATing laptop, and is getting NATed by router, nothing unusual:
ifconfig eth0 192.168.1.1
echo 1 >/proc/sys/net/ipv4/ip_forward
iptables -t nat -A POSTROUTING -j MASQUERADE -o eth1
Layer 2
Now let's get to the funny things. The unfortunate thing is that HTTP Tunnel client runs only on Windows. If it wasn't for that, there would be no need to have a setup as elaborate as this. So I installed HTTP Tunnel on the laptop. It provides SOCKS4/5 server on 192.168.1.2:1080. Now it is possible to anonymously use the Internet from either the laptop or the desktop, at least from the apps that support SOCKS4/5. However, configuring SOCKS4/5 in every single app isn't very convenient, so...
Layer 3
And now the fun part. I configured iptables so that it lets connection on the local network and to whitelisted ports through without:
/sbin/iptables -t nat -A OUTPUT -o lo -j RETURN
/sbin/iptables -t nat -A OUTPUT -d 127.0.0.1 -j RETURN
/sbin/iptables -t nat -A OUTPUT -d 192.168.0.0/16 -j RETURN
/sbin/iptables -t nat -A OUTPUT -p tcp --dport 22 -j RETURN # SSH
/sbin/iptables -t nat -A OUTPUT -p tcp --dport 80 -j RETURN # HTTP
/sbin/iptables -t nat -A OUTPUT -p tcp --dport 443 -j RETURN # HTTPS
/sbin/iptables -t nat -A OUTPUT -p udp --dport 53 -j RETURN # DNS
And to forward all other connections to transocks server:
/sbin/iptables -t nat -A OUTPUT -p tcp --syn -j DNAT --to-destination 127.0.0.1:1211
So connections to slashdot.org:80 goes straight, while connections to irc.freenode.net:6667 get redirected to 127.0.0.1:1211. This is almost the right thing, however you can probably see a little problem here - how the heck does transocks know where the user wanted to get connected. That's the best part. Kernel remembers the original destination and we can get to it using:
getsockopt(clientfd, SOL_IP, SO_ORIGINAL_DST, (struct sockaddr *)&dstaddr, &dstlen);
Now transocks connects to the specified SOCKS4/5 server (configuration in /etc/socks.conf), and the server connects to the right website through a tunnel.
In the end
So the complete path the connection goes through is:
  • An application on desktop tries to connect to irc.freenode.net:6667
  • iptables redirect connection to transocks desktop:1211
  • transocks on desktop reads the original destination using getsockopt
  • transocks connects to SOCKS4/5 server (HTTP tunnel client) on laptop - 192.168.1.1:1080
  • HTTP Tunnel client on laptop tries to connect to HTTP Tunnel servers
  • desktop NATs the connection and lets it through
  • router NATs the connection again and lets it through
  • HTTP Tunnel server connects to irc.freenode.net:6667, wow :-D
The transocks trick also works perfectly with SSH tunneling (ssh -D 1080 fred@your.shell.account). Oh and by the way, compiling transocks is not trivial, just contact me if you need some support here :-)

Tuesday, June 20, 2006

ANTLR


Everybody hates writing parsers, right ? Just admit it, you'd much rather write 1000 lines of cryptic regular expressions than a "real" parser (and if you don't know yet how to use regular expressions, drop everything you're doing and learn them right now).

Well, there's a good reason to hate writing parsers. If you write them by hand they're going to take a lot of time to write, be very hard to debug, and the error messages are going to suck. If you use some parser generator tool like lex+yacc, it's going to be slightly faster, slightly easier to debug, and the error messages are going to suck even more. All you're going to get is "Syntax error, go away". Oh, and that's assuming the grammar is actually LALR. If not, better just write the whole parser by hand.

Now here's a tool that makes parser writing suck a bit less (ANTLR). How does it differ from lex+yacc ? The most important thing, it is top-down parser, not a bottom-up one. And because it works from the top, it always know what was it expecting. So instead of "Syntax error, go away", you're getting error messages like: syntax error: unexpected symbol at line 2 (column 12): ";" for free. And you can place semantic actions pretty much everywhere. Unfortunately there's a price, grammars for ANTLR are slightly more difficult to write than for yacc. It also needs some serious getting used to and Python documentation is somewhat lacking compared to (great) Java docs.

ANTLR 2 is available for Java and Python. There's also an experimental version ANTLR 3, but it's for Java-only so far (a few ports are in progress). The Python version feel somewhat Java-ish. Apparently ANTLR 3 is supposed to be less Java-ish overall, like using actual arrays instead of silly linked lists in its default AST, but we'll have to wait for that one.

So maybe ANTLR doesn't make parser writing a particularly fun activity, but at least it sucks a lot less than lex+yacc and generates sane error messages for free. You may want to take a look at it the next time you have to parse something.

Monday, June 19, 2006

Docking assembly

Ligand-Receptor docking: Canis lupus familiaris molecule docked into Triticum aestivum bun's binding pocket What a funny day it was, playing with x86 FPU assembly :-D The problem was inspired by docking, or molecular force field computations. The thing is - there is a commonly-held belief among bioinformaticians that exponential function is very expensive, so they're going to great lengths to avoid it even when the physics suggests it might be a good idea to use it. Unfortunately x86 FPU provides plenty of evidency for this, as it can only evaluate exponential function at extended (80 bit) precision, even though we'd much rather use single (32 bit) precision. Of course such excessive precision make it very very slow, so nobody uses it. Did you even know that you can lower precision of some other operations on your FPU ? :-D

#include  <fpu_control.h>

void set_single_precision() {
   int cw = 0;
   _FPU_GETCW(cw);
   cw = (cw &~ 0x300) | 0x000;
   _FPU_SETCW(cw);
}

void set_double_precision() {
   int cw = 0;
   _FPU_GETCW(cw);
   cw = (cw &~ 0x300) | 0x200;
   _FPU_SETCW(cw);
}

void set_extended_precision() {
   int cw = 0;
   _FPU_GETCW(cw);
   cw = (cw &~ 0x300) | 0x300;
   _FPU_SETCW(cw);
}
Anyway, it only works for division and square root computation, which get about twice faster in the lowest precision, but pretty much nothing else. Now we could simply wait for the hardware guys to provide us with faster hardware, or we could become evil and implement fast exponentiation in fast assembly :-D The way x86 FPU implements normal exp function is:
  • split x into integer part and fractional part
  • evaluate 2fractional part of x
  • multiply the result by 2integer part of x, simply by adding to the floating point exponent

       fld     %st(0)          # Duplicate
       frndint                 # Round
       fsubr   %st, %st(1)     # Subtract
       fxch    %st(1)          # Exchange top two values on the stack
       f2xm1                   # 2^(fractional part) - 1
       fadd    %st(3), %st     # Add 1, so we get 2(fractional part)
       fscale                  # Multiply by 2(integer part)
       fstp    %st(1)          # Clean-up
The first and the last part are very fast, unfortunately the second one is horribly slow. So, how about we throw it away and replace by some approximation ? The only reason we can reasonably do that is because the argument is already guaranteed to be a fractional part, that is -1/2 to +1/2 (surprisingly not 0 to 1, as we're rounding to nearest integer, not down). Anyway, even a very simple 2-term Taylor expansion is pretty effective. Oh and in addition to x86 FPU assembly, let's try interfacing it with gcc by some magic :-D
// The worst relative error is smaller than 1%
inline float fast_exp2_t2(float x)
{
   float res;
   asm (
       "fld %%st(0) \n\t"    // x x 0.5
       "frndint \n\t"        // r(x) x 0.5
       "fsubr %%st, %%st(1) \n\t" // r(x) f(x)=y 0.5
       "fxch   %%st(1) \n\t"      // y r(x) 0.5

// Instead of doing f2xm1 ...

       "fldln2 \n\t" // ln2 y r(y) 0.5
       "fmulp \n\t"  // ln2*y r(y) 0.5
       "fld %%st(0) \n\t" // ln2*y ln2*y r(y) 0.5
       "fmul %%st(3) \n\t" // ln2*y/2 ln2*y r(y) 0.5
       "fld1 \n\t"         // 1 ln2*y/2 ln2*y r(y) 0.5
       "faddp \n\t"         // (1+ln2*y/2) ln2*y r(y) 0.5
       "fmulp \n\t"         // (1+ln2*y/2)*ln2*y r(y) 0.5

       "fld1 \n\t"
       "faddp \n\t"
       "fscale \n\t"
       "fstp    %%st(1)\n\t"
       :"=t"(res)
       :"0"(x), "u"(0.5)
   );
   return res;
}
gcc inlines that, so it's almost as effective as if it actually knew what it's doing. Anyway, the results were really striking, the normal exp function was 160% slower than traditional bioinfo trickery, however with this low-precision exponential the slowdown was only 35% ! Of course it's all pretty much toyish and probably has about zero actual uses. At the same time, it's really cool and evil, isn't it :-D ?

Saturday, June 17, 2006

Evangelion rip-off



This is not an Evangelion



This is not an angel

I'm just watching a really fun anime - Soukyuu no Fafner: Dead Aggressor.

The anime itself is kinda cool, but one thing that is really striking is how much they ripped off Neon Genesis Evangelion.

So we have:

  • Evangelions (or Evangelion-looking huge robots)
  • and their teenage pilots
  • angels (or angel-looking huge angels)
  • NERV (or NERV-looking huge secret organization fighting angel-looking huge angels using Evangelion-looking huge robots piloted by teenagers)
  • one of the teenagers who pilot the robots is son of the boss
  • cabalistic symbolics
  • traditional military trying to fight the angels and getting their ass kicked even though they knew perfectly there's no point is using traditional military for that purpose
  • even those weird insect sounds in the background
  • probably a lot more stuff like that
So far there haven't been any pet penguins, but the series is just taking off ;-)

Don't get me wrong - it's a cool anime, and not everything in it is Evangelion rip-off ;-)

Tuesday, June 13, 2006

A crash

I got hit by a car when I was cycling home from the university. The old bike is pretty much dead, with the frame and rear wheel requiring a replacement, so I got myself a new one.

I'm all right of course. It takes much more than a car to damage me :-D

Monday, June 12, 2006

People have to be paid to be evil


Don't worry, I'm not working for Microsoft yet ;-)

I've just found a great computer game - FarCry. It's a first person shooter where you try to escape from a mad scientists' island. And to do that you have to shoot a couple thousand mercenary soldiers, a few hundred mutants, blow up dozens of jeeps, motorboats, some helicopters, plenty of smaller and larger buildings.

There are two really cool things about the game. First the graphics is really really sweet. Of course not so much on computer, which is hopelessly slow, but on a real machine it's an eye candy ;-)

And of course the gameplay :-D

In FarCry major parts of the island are accessible all the time, and they're actually used for game, not just staying there empty. You usually have a single clear objective, so you don't have to wander aimlessly trying to guess what the heck game makers wanted you to do right now, or looking for keys or switches like in so many other FPS games. The enemy soldiers are doing all kind of fun things like fishing, training, gossiping, or engagind in serious philosophical discussions when they don't yet know you are around :-D (People are good for free, they have to be paid to be evil comes from one of those discussions).

While the objective is usually pretty clear, there are often many ways of achieving it. You can jump out with a P90 submachine gun, and simply shot everyone, you can snipe the enemies from far distance, or use a jeep-mounted rocket launcher, or try to sneak undetected, or kill them one by one using hit and run strategy and get back to the jungle, or even get the enemies kill each other. Usually two or more strategies work for any given objective, and which one you take is simply matter of your preferences (and the available ammo, which is plentiful for the common weapons but sniper ammo and the fancy stuff like rockets usually run low).

Of course the reason this is so much fun is a decent AI. The enemies won't sit idly waiting for you to shoot them one by one, sometimes they can be really cause you a lot of troubles. It's a real fun when someone is shooting at you but you don't really know where are the shots coming from :-D Or when you know where the guy is, but he's lying in the bush with a sniper rifle and you have no way to approach him without being hit.

Most of the common annoyances have been avoided:

  • There are few and very easy keycards/switches
  • You always know what is your objective
  • Losing stealth won't make you restart the level, as it does in so many really annoying games. Raising an alarm often means a lot more enemies are coming, but you can deal with it, right ?
  • Ammo for the basic weapons like M4 and P90 is plentiful. It kinda makes sense - you're killing the enemies by hundreds and robbing their armories all the time. I wouldn't mind more sniper ammo though. 5 shots from each killed sniper (no other way to get it) is kinda low.
  • There is plenty of medikits and body armour between the fights. So you rarely have to fight with low life and low ammo, like in so many other games.
  • There are no magically spawning enemy soldiers. If you clear some area, it's clear. Unless they come there but an actual chopter, but you can always shot the chopter :-)
  • The game saves automatically at checkpoints (no manual saving). The checkpoints are sane enough, I rarely had to replay more than a minute of shoting. This is rather convenient.
The most annoying thing about the game was the difficulty level. It starts real easy, and gets a lot harder later. Well, most of the games do, but it would be nicer to make it somewhat more consistent :-)

Thursday, June 08, 2006

iPod-last.fm bridge

("How to get your iPod nano terribly scratched in just a few days" picture, from ArsTechnica. Don't try this at home.)
Woot, I wrote a script that takes info about what I played on an iPod and sends it to last.fm.

Now my last.fm charts can be more accurate. :-D Of course, Sylver is still on the top.

Some people were kind enough to reverse engineer iPod binary database format, that made the work much easier. Audioscrobbler (last.fm backend) protocol is also reasonably documented. Well, at least the general overview is documented, and AmaroK's scrobbler.cpp is not that bad for the details :-)

The script is available here. If you need help getting it running, just tell me :-)

Wednesday, June 07, 2006

last.fm strikes back


I've just found that last.fm also has a personalized Internet radio. Before that, I only used last.fm for pretty charts like the one you can see here.

The last.fm radio works quite well, probably because it already knows a lot about my music preferences. Another cool feature is that it takes a lot less CPU than Pandora, which runs inside a browser. Too bad it won't give you cool explanations like my favourite Pandora's "You like this track because it has romantic lyrics" ;-)

Another cool thing - it's apparently possible to hack iPod to send the tracks you played to last.fm. Of course there's no way it couldn't change the first place on the TOP 10 list, I simply like that too much :-D

Xgl

Modern graphic cards consist of 90% 3D hardware and 10% 2D, just for the sake of backward compatibility, but so far only the games used the 3D hardware !

Here comes Xgl. Instead of having boring 2D windows, it uses full 3D to achieve a lot of cool effects, some of them ever actually useful:

  • multidesktop cube
  • real transparency (alt+mouse wheel over any window), if you have too many windows open
  • instant zooming by mouse wheel (so useful for webcomics that have small fonts)
  • and of course plenty of eye candy :-D
The cool stuff can't be presented on a screenshot, you simply have to try it on your own. Or at least watch a movie.

Unfortunately, Xgl is still quite difficult to configure. The solution is, as usual, downloading a LiveCD. Kororaa LiveCD comes with preconfigured Xgl, it should work on most ATI, nVidia and even some Intel graphic cards. Enjoy :-)

Tuesday, June 06, 2006

py2exe

Probably the most commonly requested feature for jrpg was making the installation easier. Now all in one zip packages are available, thanks to py2exe. py2exe wasn't that hard, I simply had to prepare a Python script like that:


from distutils.core import setup
import py2exe, glob

setup(windows=["jrpg.py"],
data_files=[
 ("maps", [
   "maps/world.map",
 ]),
 ("data", [
   "data/demons-kana.txt",
   "data/demons-kanawords.txt",
   "data/demons-kanji.txt",
 ]),
 ("images", [
   "images/angband.png",
 ]),
 ("images", glob.glob("images/bg-*.jpg")),
 "kochi-gothic.ttf",
]
)
Unfortunately I cannot cross-package, I need to use a Windows machine to make py2exe zips, I can't do that from Linux :-(

Sunday, June 04, 2006

Flame hair and red-hot eyes

Some recently watched stuff:

  • Shakugan no Shana - cute red-haired girls with swords. Is it not a reason enough to watch the series ? Oh well, I guess I may have a bit of a cute-red-haired-girls-with-swords thing. And the main character dies in the first episode, because a series with an alive main character would be so 1990s.
  • Stellvia of the Universe - a bunch of high schoolers piloting mecha to save the world. In the mean time, hacking into space station's servers, trying to erase the logs, and having this kind of fun. One of the funnier things - they tried to get the physics right, now the one trying to destroy the Earth is a supernova explosion, instead of the typical stuff like aliens, demons and vast right-wing conspiracies.
  • Plone Propaganda - because not only Ruby-on-Railers can bash Java. 35 minutes of real fine J2EE bashing for download. Or you can watch the Rails propaganda instead.
Some older movies reviewed: here (Full Metal Panic Fumoffu...), here (Ed Wood...) and here (Bowling for Columbine...).

Saturday, June 03, 2006

Romanticism hidden in my soul

I played a bit more with music discovery services. LivePlasma lets you explore the galaxy of music. Starting from one artist you can see all similar artists, with more similar artists closer to each other, and more popular (I guess) artists represented by bigger planets. The interface is really wonderful, unfortunately their library is rather smallish (come on, no Vanilla Ninja again, is it some kind of RIAA conspiracy ?).

So I tried to use it together with Pandora. 4 Strings was a big planet close to Sylver, so I tried making a 4 Strings radio on Pandora. It worked quite well. Some of the music was to be expected stuff like Lasgo, Ian Van Dahl, Milk Inc., but pretty quickly it also found cool music that I had no idea about, like Reina, Theresa Owens, Denny Tsettos, and loads of artists I would have never known about. So count me as sold ;-)

The funniest things are the explanations. It seems that the best predictors of the kind of music I like are disco influences and romantic lyrics. /me totally blushes :-D.

So the ideal discovery music service would have:

  • Big library, personalized charts and music player integration like last.fm
  • Streaming radio and explanations of musical taste like Pandora
  • Artistic neighbourhood exploration like LivePlasma
  • Integrated P2P like the late AudioGalaxy ! Mostly for listening to the music on an MP3 player, "owning" music is so 1980s after all. Well, or at least some sort of streaming to MP3 player hack, it can probably be done legally enough somehow.
It would also be fun to try similar services for other media someday ^_^.

Friday, June 02, 2006

Pandora


As /. have been recently comparing different music suggestion engines, and I'm a big fan of this kind of Internet websites, and a very satisfied user of last.fm, I decided to give Pandora a try.

I took a look at my favourite songs at last.fm, because I never remember what I really like if I don't have it all on a nice list ;-), for something that I liked but didn't quite knew many songs like it. I would be totally sold if Pandora found something cool and new in the first few tries.

First I tried "Bruised" by Sugababes. I figured they'd at least know a lot about Pop. Their proposals were kinda ok, but nothing exceptional. On the other hand the explanations were really funny, like this one for "I Love Rock'N'Roll" by Britney Spears:

Based on what you've told us so far, we're playing this track because it features a subtle use of vocal harmony, mild rhythmic syncopation, a vocal-centric aesthetic, minor key tonality and many other similarities identified in the music genome project.
Wow :-)

Well, it's probably hard to find good propositions based on so little information. Anyway, I moved further, trying to start from "Purunematu" by Vanilla Ninja. Pandora didn't know about it, or about anything else by Vanilla Ninja for that matter. Oh well, so trying "Shallow Water" by Sylver instead maybe ? Oh it sure knows "Shallow Water", it's a country song by Randy Travis. Darn ;-)

A few more tries. Groove Coverage ? No. Alizee ? No. I was almost going to go back to last.fm at this point, but at least it knew Ayumi Hamasaki. Well, a few more tries just out of curiosity - it doesn't know Closterkeller or Special D, but it knows Lisa Loeb and Rammstein. So the selection is weak but maybe not fatally weak. I suppose it's all just labels politics, meh.

I wasn't sold on the interface either. I couldn't figure how to rate a song that just finished playing, it seemed that one can only rate one that's being played right now. (Finally I got it, apparently the right thing is clicking on album cover pic, not on the song title.)

So to sum it up, if you want some nice music recommendations, try last.fm. If you're bored and want to see something differnt than user clustering, you may also give Pandora a try, but don't expect too much. User clustering is still pretty much state of the art in 2006. ;-)

Dapper Drake


This is one of the chicks from the original Ubuntu Calendar. It's not updated any more, sorry ;-)

I've been using Ubuntu Dapper Drake betas for a couple of days now, and finally it got released.

I usually hate everything ;-), but I think Dapper Drake is the best distribution of Linux ever. Even the default GNOME (which you can change to KDE with just a few clicks in Synaptic) isn't that annoying in the recent versions as it used to be.

Things to expect:

  • Really cool LiveCD-style installer. You simply have to see this one.
  • Everything more or less just working out of the box.
  • Software upgrades working almost automatically. It can even download new upgrades in background as soon as they're published, simply waiting for you to click the Upgrade button.
  • Full sudo rights for the first registered user, no root password. I think this is really great, the old Unix system of accounts and permissions is seriously braindamaged.
  • Loads of packages. You must enable universe and multiverse in the package managers, because most of the extras are not "officially supported".
  • For anything weird, like installing Radeon 3d drivers ;-), there's usually a quick help page on Ubuntu Wiki.
So just get Ubuntu LiveCD installer, and have some fun :-D