blog.c0la.se

Någon gång i slutet av sommaren förra året så regnade det väldigt mycket i Trollhättan. Det var under perioden då jag precis hade flyttat ifrån Stockholm, men ännu inte fått min nya lägenhet i Uppsala, så därför stod min utvecklingsserver som den här bloggen ligger på hos mina föräldrar i Trollhättan. Dessvärre ligger deras hus i en dal, och jag hade varit smart nog att ställa den på golvet i källaren. Slutresultatet var en väldigt blöt server.

Mirakulöst nog så överlevde båda hårddiskarna att bli dränkta, så jag förlorade ingen data. Eftersom jag var i USA när det inträffade så tog det dock några veckor innan jag hade möjlighet att åka och hämta grejerna och konstatera det. Efter det så tänkte jag att det här kunde vara ett bra tillfälle att överge min egen bloggplattform och gå över till Wordpress. Den tanken hade jag i huvudet i nästan ett halvår, innan jag slutligen insåg att jag aldrig skulle få tummen ur och lade upp den gamla bloggen i befintligt skick.

Så. Jag ber om ursäkt för att det tog sådan tid, men nu är den i alla fall tillbaks. Förmodligen kommer jag fortsätta på samma linje som jag gjorde när den gick ned förra gången, dvs. skriva olika inlägg om mina nuvarande (privata) projekt snarare än guider och nybörjarartiklar. Jag har generellt sett tappat intresset för PHP, och fokus kommer nog ligga på andra språk framöver.

A friend asked me the other day if I knew of a way to retrieve the currently playing song in Spotify so that it could be displayed in an irc client such as irssi. I in turn asked Emil at Spotify if there was a supported way of doing this. Apparently they've discussed it, but there is no time plan for when it might be implemented. Today I had some spare time, so I decided that it would be a good excercise to hack together something that could be used in the mean time.

I used WinSpy++ to check the window class of Spotify and then implemented a simple win32 application that detects the currently playing song simply by checking the title of Spotify window. The relevant (simplified) code looks like this:

HWND hWnd;
TCHAR szTitle[1024];
DWORD dwRead;

hWnd = FindWindow(_T("SpotifyMainWindow"), NULL);
dwRead = GetWindowText(hWnd, szTitle, sizeof(szTitle)/sizeof(TCHAR));

Since you'll generally run Irssi in a remote shell, I also had to make the application network transparent. I decided to do this by posting the currently playing song to an url on a webserver. The end result is a simple win32 application that runs in the background and uploads the title of the currently playing song whenever it detects a change. The source is of course also available.

I also implemented a simple php application that handles the web server part. There's also a demo that you can use freely. The demo page also describes how you can access the data from irssi.

Jag är lite smått pervers när det gäller böcker. Av någon anledning så kan jag inte låta bli att impulsköpa varje bok jag ens känner mig lite intresserad av, och när det gäller datorfacklitteratur i ännu högre grad än vanligt. Till skillnad från min goda vän Johan så har jag dock besudlat mina böcker genom att fotografera dem.

Två hyllor kanske inte verkar så mycket, men det är trots allt ganska många böcker och ganska många tusen kronor i den här hyllan. Här är en närbild på övre plan:

Och en på undre:

Snabba rekommendationer:

• Java Cookbook
• Javascript, the definitive guide
  
• The Art of SQL
• C# 3.0 in a Nutshell
• Python in a Nutshell
• JAVA in a Nutshell
• High Performance MySQL, 2nd edition
• Lucene in Action
• Code Complete
• Software Requirements
• Effective Java
• The Pragmatic Programmer

Jag avråder ifrån:

• Learning C# 2005
• Advanced PHP Programming
• C++-programmering

Bästa boken i hyllan: Javascript, the definitive guide. Någon liknande referens finns faktiskt inte på nätet. Kostar 200kr och är helt ovärderlig.

Nu ska jag bara bekämpa skuldkänslorna för att ha kränkt mina böckers integritet på detta vis också. Julle, tror du att de någonsin kommer kunna förlåta mig?

Nobody that has followed my experiments for a while can have avoided to notice that I have a certain fascination for dynamic image manipulation. If you have, just take a look at the past two posts.

During the past year I've expanded this interest to the manipulation of sound. At some point I discovered that the regular wave format actually is rather straight forward, and wrote a few simple programs that dealt with them. These were simple c-programs and the first one simply analyzed a wav-file and outputted the header meta data. I also wrote a simple sine wave generator. They can be compiled using gcc -o progname progname.c -lm.

Manipulating sound is somewhat more complex than manipulating images since it requires an mathematical understanding of waves. Basic trigonometry and algebra is pretty much required, although you doesn't necessarily need a very advanced understanding. If you know how to manipulate the frequency of a sine wave, you can get a long way.

It's been almost a year since the past experiments, but yesterday I decided to try out an idea I've had for a while. This idea was to store regular binary data on an audio tape. I figured that it could be done the same way that a modem translates binary data and transmits it across a phone line - by converting digital data to sinewaves of different frequencies. Since the capacity of audio tapes are rather limited and the media itself is quite impratical I also thought that I would try to make it sound cool too.

Unfortunately my knowledge in digital signal processing is rather limited, and it's been almost three years since I took a basic course in fourier analysis. Also, since the math class I attended back then was meant for chemists it didn't really cover discrete analysis of waves. I did however feel rather certain that the Discrete Fourier Transform was the right tool for the job. As such I downloaded the numpy library for python and started experimenting with taking the DFT of various super positioned sine waves. The sheer coolness blew me away.

What I did was this: I implemented a simple python script that generated a sampled data series of a sine wave. The result looked something like this:

The graph represents four combined waves with the frequencies 5hz, 11hz, 17hz and 31hz with different amplitudes (see the script for details). The script also took the fourier transform of the same data series.

0    90000000.0000000000
1    0.0000000024
....
4    0.0000000023
5    12000000.0000000000
6    0.0000000027
....
10    0.0000000006
11    5999999.9999999925
12    0.0000000004
...
15    0.0000000109
16    0.0000000008
17    3000000.0000000009
18    0.0000000012
....
30    0.0000000255
31    24000000.0000000000
32    0.0000000268
..... (8000 additional data points)

The left column represents the frequency and the right column represents the absolut value of the complex number returned by the transform. The frequencies with high values is exactly those that made up the sine wave I used to generate the sample data. This will of course be old news for anyone that has actually taken a course in fourier analysis, but it wasn't to me. :)

Thus I decided to use my new knowledge to actually encode binary data as audio. I translated my old sine wave generator to python, and made a few choices about the actual encoding I'd use. I decided that I'd use two quick tones to represent a single byte. This reduces the number of distinct frequencies needed to 16, since 4 bits corresponds to the number 0 to 15. The code below can be used to split a byte into two halfs:

a = myByte & 0xF

b = myByte >> 4

I then picked 16 common musical notes from three different octaves. In order to make it easier to locate the start of the data stream I added a 3 second pure A (440hz) at the beginning of the file.

The actual encoder turned out to be rather easy to implement in this manner. I have also uploaded a sample encoding of a 196 byte source file. If you're curious about what I've encoded you'll have to use the decoder below.. ;)

Even before I started this project I knew that the decoder would be the hard part, and of course I was right. It took me several hours before everything worked as intended. The decoder uses the DFT mentioned above to decode the actual frequencies. Of course, that's a bit unnecessary in a controlled environment, and a simpler algorithm would have done the same job quicker. However, since I wanted to try transferring the data using actual audio equipment I thought the fourier transform would be more fault tolerant. It's my belief that it will be able handle higher levels of background noise. My quick and dirty DFT decoder routine looks like this:

def get_maxfrequency(samples, norm, maxAcceptable = 1200):
    samplesArr = numpy.numarray.array(samples)
    transformedSamples = numpy.fft.fft(samplesArr)
   
    maxFreq = 0
    maxI = 0
    for i, freq in enumerate(transformedSamples):
        j = int(norm * i)
        a = math.sqrt(freq.real**2 + freq.imag**2)
        if a > maxFreq and i > 0 and j < maxAcceptable:
            maxFreq = a
            maxI = j
           
    return maxI

It ain't beutiful, but it does work. The entire decoder is also available. This script successfully decodes the files generated by the encoder. I also tried introducing _a lot_ of disturbances by playing the sound file on my laptop, recording it on my mobile phone, transferring it back to my computer and running it through the decoder. The output was garbled but quite a few characters was actually recognizable.

All of this is of course nothing more than rather primitive and naive experiments but I'm a determined bastard, so if I can find the time and energy this might just turn in to something more than a crappy proof of concept. I wouldn't bet on it though...

BTW! If you like what I write, please vote on the posts. It's all I ask. :)

Every now and then I get an idea that sort of settles in and then stays in my brain, no matter how many years pass by. "I want to write my own tetris clone!", "I should write an IRC server in C!", and so on. One of these ideas was that I wanted to implement my own application to generate image mosaic. Before I go any further it might be a good idea to actually explain what image mosaic is, as I imagine that some of you might be wondering. Lets take a look:

Image mosaic is an image that consists of many, many small images. I'm quite sure that all of you have seen images like this before, but for some reason the actual term isn't very established.

As I said, I've been thinking that I wanted to implement an application to generate such images for many years, and I've always been rather confident that it wouldn't be very hard either. It turns out that I was right. I was able to implement a prototype in about two hours, and I'm not even very fluent in C.

In continuation of my proud tradition to release everything I do freely, I present to you: Mosaic 0.1.

Now, of course this has been done before, and there are far more advanced and capable programs for this, including a couple of open source options. These generally include support for non-square tiles and other good-to-have-stuff. Still, my version is less then 700 lines of c-code, so I imagine that it might be easier to follow than the more advanced versions.

In order to compile this program you'll need libgd. On ubuntu you can install the necessary files using:

apt-get install libgd2-xpm-dev

If you're using another dist you're on your own, but I would guess that it's similarly named regardless of system. That should be the only dependency, though, so when you have installed gd all you have to do is to unpack the source (tar zxvf mosaic-0.1-src.tar.gz) and type make. Just type ./mosaic and the program will output some example usage. Bear in mind that the more tiles you use, the better the results. The sample images I've posted here uses a library of more than 2000 images.

The algorithm it self is actually really, really simple. First of all the program builds a library of tiles. These tiles are small square images of a specified size (the standard is 50x50 pixels). It also calculates the average color of these tiles, and stores this average in memory.

Next it loads the actual image to convert, and processes it chunkwise. The default chunk measures 25x25 pixels, which means that if you don't change any settings the output will be twice the size of the source image. It then repeats the process from above and calculates the average of this chunk.

Then it's time for the actual magic. After calculating the average of this chunk it proceeds to search tiles library for a tile with a color average that matches the average of the chunk. Of course there's generally not an exact match, so what it actually does is to pick the one closest. It does this by calculating the euclidean distance between the chunk and the tiles. This is done with the formula:

D(chunk, tile) = ((r_chunk - r_tile)² + (g_chunk - g_tile)² + (b_chunk - g_tile)²)^1/2

Most of you will probably recognize this as the Pythagorean theorem. The rational for this is to consider the chunk as well as the tile as two points in three dimensional space - where the x coordinate is the red channel, the y coordinate is the blue channel and the z coordinate is the green channel. This type of thinking, with a mathematical solution that can be more easily understood through geometry is very common in mathematics, and especially so in certain fields of computer science, such as search engines and information retrieval.

Have you ever wondered how to generate simple color gradients? Such as this one:

If you answered yes, we have something in common. However, I've only thought about it in passing, and never had a reason to actually try to figure it out for real. That changed today when I suddenly needed it for a project that I'll talk about a lot in later posts.

In this case I needed a scale that went from cold to hot, and after a few seconds of thought it occured to me that overlapping second grade functions probably would do the trick. It looks like this if you plot them as a graph:

This graph is almost exactly the same as the one that I sketched up in my notebook. The colors here in the opposite order compared to the gradient above, but that isn't really important here. You can plot the colors in any order. All I had to do now was to determine the parameters of the graphs. This is really easy with even basic math. First of all. The functions in the graph can be written on the form:

f(t) = k * (t₀ - t) * (t₁ - t)

t₀ and t₁ represents the points the the function is zero, and k is a normalizing constant that makes sure that the maximum value is what we want (in this case 2⁸=255, which is the maximum value for a single color channel). The range of t can be chosen to be whatever we desire, but in this case I use t=[0,1000]. Here's the actual values we want for these functions which we'll denote R(t), G(t) and B(t):

Red:

R(0)=0

R(250)=255

R(500)=0

Green:

G(250)=0

G(500)=255

G(750)=0

Blue:

B(500)=0

B(750)=255

B(1000)=0

We already know t₀ and t₁ for each of these functions. However, we still have to calculate k. How do we do that? Simple: Since k is the only unknown, all we have to do is to solve the equation for k and insert the other values:

f(t) = k * (t₀ - t) * (t₁ - t)

=> k = f(t) / ((t₀ - t) * (t₁ - t))

Let's apply this for the green function:

t₀ = 250

t₁ = 750

k = 255 / ((250 - 500) * (750 - 500)) = -.00408

G(t) = -0.00408 * (250 - t) * (750 - t)

That's it!

Of course I've implemented a generalized example of this, that allows any width, and not just 1000. If you still think that programmers don't need to know any math, think again. 

Snabbt länktips bara: Math for programmers

Jag kan vittna om att han har rätt. Man vet inte vad man missat hela tiden förens efter att man lärt sig.

I have spent the evenings this week playing Red Alert 3. The RA-branch of the command&conquer-series has been one of my favourite games for many years, and I was happy to see that RA3 met my expectations. One of the most entertaining aspects of the RA-series is that it has always included some really wellmade filmed movies - with wonderfully bad acting - that plays between the games and moves the plot forward.

The reason I'm writing about this here is that I earlier tonight started wondering if it was possible to watch these movies outside of the game. It turns out that the movies themselves are easily available in VP6-format (VP6 is the coder) in the game folder. However, the audio is located in separate files, and these audio-files are stored in a compound file format. The compound files are called .big. This doesn't seem to be a standardized format, and thus it sparked my interest.

I fired up my HexEditor (I use HexEdit, from catch22. That site also has incredible win32 tutorials.) and started investigating. It turns out that it's a really simple archival format, so I wrote a simple decoder in python. Afterwards I discovered that someone else had already written a decoder, but that one was closed source so I figured that I'd publish my own as well. When I had a working decoder I started wondering if this format was used by other games, and since I had "command & conquer: the first decade" installed, I checked. Appearently C&C Generals: Zero Hour also uses this format, but C&C Generals doesn't. I would guess that C&C3: Kane's wrath uses it as well, since it came out after ZH but before RA3. From what I've read it seems it's also used by some other new EA Games, but not all of them. Mirror's Edge is a rather new game that doesn't use it, but this isn't that surprising since it's developed by another EA branch.

I find the formats used a bit intriguing. From what I've read VP6 is a codec, not a container. Therefore it's a bit interesting that the files use .vp6 as file extension. Some links on the internet indicated that the container is actually flv, but this seems unlikely and is probably only true when the files are used in together with flash. Luckily, VLC could play the files without trouble, so I didn't investigate further. Whatever it is it's something that libavformat (part of ffmpeg) can demux.

The audio format provided more trouble. The audio is stored as .snd-files. I'm not familiar with the .snd container format, but it seems that vlc was able to demux it, since it could tell me meta data such as the bit rate and the number of channels. It also told me that the FOURCC was "undf". This is the code for something called Voxware Metaaudio. Unfortunately VLC can't decode it, and the only thing I could find that worked was the eaconv-utility provided together with the other decoder I mentioned. This utility converts the audio to regular wav-files, and can also convert .vp6 video files to .avi. The difference is that the audio-conversion actually decodes the encoded audio into raw pcm wav-files, while the video-conversion just switches container. I believe that I could have written the video conversion routine, but the audio conversion... Maybe the Voxware codec isn't as advanced as I think.

This is the end of the problems, because when you have an avi and a wav-file, it's trivial to convert them into a single avi using VirtualDub.

Also, this was the first time that I manipulated binary data in Python. It was really easy, but then, so is everything in Python.

DN släppte i dagarna en ny version av sin site, och med det trasade de slutligen sönder det fulhack som jag använt för att följa seriestrippen Nemi via RSS. Det trevliga med det gamla systemet var att stripparna helt enkelt bara hette det datum som de publicerades och alltså behövde man inte crawla sidan för att få fram stripparna. Det räckte att spotta ut ett nytt datum varje dag. Jag löste det med ett enkelt php-script.

Tyvärr så fungerar som sagt inte den lösningen längre, eftersom de nya bild-url:erna även innehåller något random id-nummer. Lyckligtvis så är det ganska trivialt att helt enkelt tanka index-sidan och plocka ut dessa id-nummer med ett enkelt regexp. 

/polopoly_fs/(.*?)!image/(.*?).gif_gen/derivatives/teaser-small/(.*?).gif

Eftersom jag blir allt mer såld på python så bestämde jag mig för att använda det istället för PHP, och hade efter 20 minuter fått ihop en ny fungerande lösning. Den är något långsamare eftersom den måste hämta en sida från dn.se, och därför lade jag den som ett cronjob istället för att generera feeden i realtid som jag gjorde med den förra lösningen.

Det slutgiltiga resultat blev såhär. Eftersom jag är så generös så kommer jag dock inte tvinga er att sätta upp en egen kopia, utan ni får gärna använda min feed.

Själva serien Nemi är i mitt tycke en av de absolut bästa serierna som syndikeras i gammelmedia. De lyckas ofta vara genuint roliga, vilket är chockerande sällsynt bland serier nuförtiden. Normalt sett återfinns äkta underhållning enbart i webcomics. Min enda reservation mot Nemi är att den är lite för vänstervriden för en liberal som jag själv, men det kan jag stå ut med. :)

Förövrigt är det här inlägg nummer 100 på den här bloggen. Wooh. Tog mig 5 år, men det gick till slut...

screamer ~ # time ./genprimes 10000000 | wc -l

664579

real    0m0.884s

user    0m0.880s

sys     0m0.030s

 

screamer ~ # time ./genprimes2 10000000 | wc -l

664579

real    0m0.331s

user    0m0.350s

sys     0m0.000s

För att kompilera dem kör man lämpligen:

gcc -o genprimes genprimes.c

gcc -o genprimes2 genprimes2.c -lm

Tänk på att genprimes.c förbrukar limit bytes, och genprimes2.c förbrukar limit/2 bytes. Om du beräknar alla primtal under en miljon kommer de alltså kräva lite drygt 1mb respektive 0,5mb. Detta riskerar bli ett problem om du mot förmodan skulle vilja beräkna alla primtal under en biljon, och inte har en terabyte ram tillgängligt. :)