Accidentally installing Grub to /dev/sda on a Mac OS X machine

I managed to accidentally install GRUB to /dev/sda when setting up my MacBookPro to boot Ubuntu, WinXP and Mac OS X. I knew I shouldn't have, but I wasn't paying attention to the installer when it asked me. In my defence I was also slightly rushed as I wanted to get the installation running before I went to the pub...

Anyway after much hunting and not being able to boot Linux or Windows XP, I finally discovered the solution in this blog post. The author had, like me, managed to ignore all the warnings. Luckily recovery is just a simple case of sticking in the Mac OS X install CD, booting off it and running "fdisk -u /dev/rdisk0" in terminal. This will then restore the Mac OS X MBR to it's proper state.

I did get a warning about not being able to find an MBR file, but it still let me update the MBR and it all seems to be working anyway. As well as fixing Linux and Windows XP booting (which previously would just sit there with a blinking cursor in the top left) it also fixed the slightly annoying issue of rEFIT having a 'Boot Linux from HD' option which I couldn't get rid of.

Packing is Hard

Recently there has been some talk about a computer science problem and a, possible, proof that P doesn't equal NP. The proof of if P and NP are the same is one which I think that every computer science student must have a vague suspicion that they could prove when they first hear about it in their computational complexity course. Perhaps as a consequence of this, undergrads are told that they're not going to work it out as "lots of very clever people have tried to show it and failed".



As an aside, the work around showing P and NP being different or the same is a great example of the scientific method at it's best: all the experts generally agree that P isn't the same as NP, but that doesn't stop them from going through any proof which concurs with that belief with a fine-tooth comb. There is a such a clear separation of believe and the need for formal proof that there's a $1 million dollar prize available for a proof that shows P is the same as or different to NP.



Given that few of us are likely to win that prize, why should everyday people care about if P is the same as NP. The simple answer is that it is applicable to many everyday problems, such as packing a bag. NP stands for 'nondeterministic polynomial time' which is a very complex way of saying that, when given a solution to an NP problem, you can easily show it is a correct solution to the problem. In the case of packing a bag this is as simple as seeing that they've fitted all the items into the bag.

A problem which is 'P' is a 'polynomial time problem', which is to say that finding a solution from scratch is as easy to find as showing that a solution is correct to an NP problem. So if it was to be shown that P problems are not the same as NP problems then it would confirm that it really is sometimes easier to solve a problem when you've got the solution.

On the other hand, showing that P isn't the same as NP doesn't help practical everyday computing. The vast majority of polynomial time problems still take too long to solve with current computing technology, so all a proof would show is that there are very very hard problems as well as very hard problems. Most importantly, showing P isn't the same as NP certainly won't stop your word processor crashing when you've forgotten to save for 10 minutes.

Last.fm on Ubuntu Lucid Lynx (10.04)

Having recently got a nice shiny new netbook (an HP/Compaq 311c) I was trying to get last.fm to compile on it. My netbook was running a reasonably fresh install of Ubuntu Lucid Lynx (10.04).

So I downloaded the source for last.fm-1.4.2.58240 and unzipped it into my source directory. Knowing that it needed qt4 I then ran:
sudo apt-get install libqt4-dev

With that all installed I tried running ./configure in the source directory and it said everything was fine, so I went ahead and typed make.

After waiting while it compiled I was then greeted by the following error:
make[1]: Entering directory `/home/marvin/src/last.fm-1.4.2.58240/src/libFingerprint/fplib/pro_qmake'
g++ -c -pipe -O2 -w -fPIC -DNBREAKPAD -DLINUX -DNDEBUG -I/usr/share/qt4/mkspecs/linux-g++ -I. -I../../../../src -I../../../../build -I../../../libMoose -I../../../libUnicorn -I../include -I../src -I../../libs/fftw/src/api -I../../../../res/libsamplerate -o ../../../../build/fplib/release/FingerprintExtractor.o ../src/FingerprintExtractor.cpp
../src/FingerprintExtractor.cpp: In member function ‘bool fingerprint::FingerprintExtractor::process(const short int*, size_t, bool)’:
../src/FingerprintExtractor.cpp:445: error: ‘memcpy’ was not declared in this scope
make[1]: *** [../../../../build/fplib/release/FingerprintExtractor.o] Error 1
make[1]: Leaving directory `/home/marvin/src/last.fm-1.4.2.58240/src/libFingerprint/fplib/pro_qmake'
make: *** [sub-src-libFingerprint-fplib-pro_qmake-fplib-pro-make_default-ordered] Error 2
marvin@Anjie:~/src/last.fm-1.4.2.58240$


Knowing that memcpy is part of the standard C library I thought this seemed a little strange. So I opened up last.fm-1.4.2.58240/src/libFingerprint/fplib/src/FingerprintExtractor.cpp and added the following line in bold:
#include <cmath>
#include <string.h>

Then recompiled.

The next error was the following:
g++ -c -pipe -O2 -w -fPIC -DNBREAKPAD -DLINUX -DNDEBUG -I/usr/share/qt4/mkspecs/linux-g++ -I. -I../../../../src -I../../../../build -I../../../libMoose -I../../../libUnicorn -I../include -I../src -I../../libs/fftw/src/api -I../../../../res/libsamplerate -o ../../../../build/fplib/release/OptFFT.o ../src/OptFFT.cpp
../src/OptFFT.cpp: In constructor ‘fingerprint::OptFFT::OptFFT(size_t)’:
../src/OptFFT.cpp:262: error: ‘exit’ was not declared in this scope
make[1]: *** [../../../../build/fplib/release/OptFFT.o] Error 1
make[1]: Leaving directory `/home/marvin/src/last.fm-1.4.2.58240/src/libFingerprint/fplib/pro_qmake'
make: *** [sub-src-libFingerprint-fplib-pro_qmake-fplib-pro-make_default-ordered] Error 2
marvin@Anjie:~/src/last.fm-1.4.2.58240$


Which I fixed by editing last.fm-1.4.2.58240/src/libFingerprint/fplib/src/OptFFT.cpp to include the line in bold:
#include <iostream>
#include <memory.h> // for memcopy
#include <stdlib.h>

And then once again ran make.

The next error was:
g++ -c -pipe -O2 -w -D_REENTRANT -fPIC -DNBREAKPAD -DLINUX -DQT_NO_DEBUG -DQT_SQL_LIB -DQT_XML_LIB -DQT_GUI_LIB -DQT_NETWORK_LIB -DQT_CORE_LIB -DQT_SHARED -I/usr/share/qt4/mkspecs/linux-g++ -I. -I/usr/include/qt4/QtCore -I/usr/include/qt4/QtNetwork -I/usr/include/qt4/QtGui -I/usr/include/qt4/QtXml -I/usr/include/qt4/QtSql -I/usr/include/qt4 -I../../src -I../../build -I../libMoose -I../libUnicorn -Ifplib/include -I../src/ -I../../res/mad -I../../build/LastFmFingerprint/release -o ../../build/LastFmFingerprint/release/MP3_Source_Qt.o MP3_Source_Qt.cpp
MP3_Source_Qt.cpp: In function ‘short int f2s(mad_fixed_t)’:
MP3_Source_Qt.cpp:70: error: ‘SHRT_MAX’ was not declared in this scope
MP3_Source_Qt.cpp:72: error: ‘SHRT_MAX’ was not declared in this scope
MP3_Source_Qt.cpp: In member function ‘virtual void MP3_Source::skipSilence(double)’:
MP3_Source_Qt.cpp:379: error: ‘abs’ was not declared in this scope
MP3_Source_Qt.cpp:385: error: ‘abs’ was not declared in this scope
make[1]: *** [../../build/LastFmFingerprint/release/MP3_Source_Qt.o] Error 1
make[1]: Leaving directory `/home/marvin/src/last.fm-1.4.2.58240/src/libFingerprint'
make: *** [sub-src-libFingerprint-make_default-ordered] Error 2


So I opened last.fm-1.4.2.58240/src/libFingerprint/MP3_Source_Qt.cpp and added the lines in bold:
#include <cassert>
#include <stdexcept>
#include <stdlib.h>
#include <limits.h>


And ran make once more.

This time it was a linking error:
g++ -Wl,-O1 -shared -Wl,-soname,libLastFmFingerprint.so.1 -o libLastFmFingerprint.so.1.0.0 ../../build/LastFmFingerprint/release/Sha256File.o ../../build/LastFmFingerprint/release/Sha256.o ../../build/LastFmFingerprint/release/MP3_Source_Qt.o ../../build/LastFmFingerprint/release/Fingerprinter2.o ../../build/LastFmFingerprint/release/FingerprintCollector.o ../../build/LastFmFingerprint/release/FingerprintQueryer.o ../../build/LastFmFingerprint/release/moc_Fingerprinter2.o ../../build/LastFmFingerprint/release/moc_FingerprintCollector.o ../../build/LastFmFingerprint/release/moc_FingerprintQueryer.o -L/home/marvin/src/last.fm-1.4.2.58240/bin -L/home/marvin/src/last.fm-1.4.2.58240/build/LastFmFingerprint/../fplib -L/usr/lib -lMoose -L/home/marvin/src/last.fm-1.4.2.58240/bin -lLastFmTools /home/marvin/src/last.fm-1.4.2.58240/build/fplib/libfplib.a -lsamplerate -lfftw3f -lQtSql -lQtXml -lQtGui -lQtNetwork -lQtCore -lpthread
/usr/bin/ld: cannot find -lsamplerate
collect2: ld returned 1 exit status
make[1]: *** [../../bin/libLastFmFingerprint.so.1.0.0] Error 1
make[1]: Leaving directory `/home/marvin/src/last.fm-1.4.2.58240/src/libFingerprint'
make: *** [sub-src-libFingerprint-make_default-ordered] Error 2
marvin@Anjie:~/src/last.fm-1.4.2.58240$


So I ran sudo apt-get install libsamplerate0 libsamplerate0-dev libfftw3-dev libfftw3-3 libmad0-dev libmad0 libgpod-dev libgpod4 libasound2-dev and then ran make again.

If you're wondering how I came up with all the libraries above, it was just from running make several times and then using apt-cache search to search for the missing libraries. I didn't include these steps as they're a bit tedious.

Having done all that it's possible to run last.fm with bin/last.fm.sh.

Not all equals are born equal

The relationship between two things is something that we learn early in life. It's quite an important thing to know about, especially for understanding the world we live in.

However the question of 'are these the same' or 'are these equal' is surprisingly tricky. It might immediately seem rather obvious, but in actual fact there is a surprising amount of complex mathematics to do with equality and how you define it. As it turns out there are quite a few ways of saying that things are the same, leading to a description of all the different ways of comparing things being called an Equivalence relationship.

Equivalence relationships have three key properties:

• Reflexive - That everything is equal to itself.
• Symmetric - That if object A is equal to thing B then thing B must be equal to object A.
• Transitive - That if A equals B and B equals C then A must equal C.

All of which might seem rather obvious, but mathematicians like to flip-flop between stating the massively obvious and the painfully complex.

For example consider the following:

=

Quite clearly, for most sensible definitions of equality these will be the same; mostly due to them being identical.

Where it starts to get tricky is if there is some variation between the two things being compared. Initially the answer to this might appear to be "no, they aren't equal", but consider the following:

=

If you took a poll of people to ask if these two were equal you'd probably come up with the following options in some proportion:

• Yes, it's the same image.
• Yes, apart from one is a bit distorted.
• No, they look different.

All of which are acceptable answers, it just depends on how you define equality. The first answer assumes the comparison is about the contents of the image rather than how it's presented. The second answer is the middle ground, acknowledging that the images are the same but that there is a different in how they a presented. The final answer is the other extreme, the pictures aren't the same so they're not equal.

This all ties in very deeply with one of the foundations of computer science; the distinction between comparing the concept represented by some data and the data itself. A clearer example of the distinction here would be to use two pictures where the idea of equality is even more fuzzy.

=

As before the answer to if these two are equal is yes and also no. If the question being asked is "are these the same cat?" then the answer is yes; if the question is instead "are these photos the same?" then the answer is no. Usually it's obvious which of these questions is being asked from the context and generally the question is phrased in the more explicit way.

Computers are no different. Ever since Ada Lovelace realised that numbers could be used to represent ideas, concepts and physical objects there has been the need to distinguish between the two types of equality. It's necessary to explicitly tell the computer if you're asking if the numbers are the same (asking if the photos are the same for the above example) or asking if the thing the numbers represent are the same (asking if it's the same cat).

This distinction between the values and what the values are meant to represent occurs frequently in computer languages. For example in the Java language the operator '==' is used to compare the number representing the object, where as the 'equals()' method is used to compare the concept/item that the object represents.

Some languages complicate this further, such as JavaScript where there is the '==' equality operator and the '===' strict equality operator. The need for this arises because when JavaScript first came into existence the '==' operator was defined in such a way that the number 5 was equal to a sequence of text which is the character 5. This is a little confusing, but for various reasons computers choose to represent the character/digit of 5 as the number 53.

This distinction between a character/digit of 5 and the number 5 (which you get from adding 2 and 3) might seem a little strange, but consider the phrase "I ate 5 strawberries". It's necessary for there to be some way to represent each character/letter as a number and the method of representation that has become standard has the digit 5 represented by the number 53.

Coming back to the difference between '==' and '===', the former will say that "5" is equal to 5, where as the latter will say that they are not equal (due to the internal representation being different). This can be a little confusing when first coming to JavaScript and is the main reason for writing this post. I discovered the difference and thought I should share.

So the next time you're trying to work out if two things are the same, just remember to think what you are wanting to compare.

Adventures in S60 Web Runtime - Part 2

This is the second installment in a series on writing an S60 Web Runtime widget, here's the first.

As I said in my last post, feedback is very important if you want to stay motivated. As well as being important for setting goals, this is very important for the actual writing of the code. To possibly state the obvious, software development follows a series or steps:

1. Think about the problem.
2. Think up a possible solution.
3. Write code expressing that solution.
4. Build the code you've written.
5. Test your built code.
6. Repeat from step 1.

The astute programmers among you will have realised that this is a never ending loop as there is no termination condition such as "On the 100th try give up and go home". The non-programmers will have thought that was a rather obvious implicit step. You're both write, it's a never ending cycle of improvement but every so often you have to stop and do something else.

One of the key steps in this list is step 4 ("Build the code you've written"). This is the process of asking the computer to translate your program from the human programmer readable code to something the computer can run. It also includes packaging up the built code in a way which means you can actually run it. It's roughly equivalent to taking the plans for a building (step 3) and building the house before you can live in it (step 5). It's very important to keep this step as short as possible, as if it takes more than a few seconds the programmer will lose focus, start thinking about if they need to buy more bread and milk on the way home and forget the intricate details of their solution from step 2.

Compiler by Luiscdiaz

S60 Web Runtime widgets are essentially an interpreted language. This means that the computer can go straight from the code you've written to running it. This is different from a compiled language which requires translating your textual code (saying something such as "add 1 to count of people") to numbers that the computer can run (such as "07 A4 7E 1F"). By being interpreted, a large part of step 4 is removed. However there is still the need to bundle up all the files in your program into one file and to install the application onto something that you can test it with. This can take a surprisingly long amount of time while also being tedious and dull.

Luckily several people have worked to make this easier. A glance at the quick start guide from the Symbian Foundation showed that there were several useful tools for speeding up this process. The one that they focus on (due to it being free) is Aptana. Aptana is an Integrated Development Environment (IDE) which means that it tries to have as many easy to use tools all integrated together in one place as possible.

The big feature of Aptana which made me want to use it is that it makes it possible to go straight from writing code to testing it in one click (going from the "Source" view to the "Nokia Web Runtime (WRT)" view). This was going to make development much more streamlined and, most importantly, more fun.



So with Aptana installed and tested to check that it was working (by following the rest of the quick start guide) I now had to get down to writing the actual code. In actual fact that's a bit of a lie as I first of all had a look at some of the example code and noticed that it was written in an apparently non-optimal way.

Anyone who has used a WRT widget on a phone might have noticed that they're a bit slow to start-up. When programming for web pages it's common to put code which does complex things (and therefore takes a while) at the end of the page. This means that the user can at least see most of the page and start reading things while the computer is doing the complex things. This does require a bit of extra work, as you must divide the things you need to do into things you have to do now and things you can do later (further details on this can be found in the Episodes pattern in this book).

However the example code wasn't doing this, instead of:

1. Perform just enough calculations for the first view.
2. Display the first view.
3. Do the other calculations.

The example code was doing:

1. Calculate everything and get it all set-up and ready to go.
2. Display the first view.

By doing the non-essential work first, the example application was unnecessarily slowing down the start-up of the application. After all, why do something now that you can put off doing until later!

Adventures in S60 Web Runtime - Part 1

The further parts in this series of posts can be found here: part 2

To celebrate/commiserate (delete as appropriate) moving on from four and a half years of employment at Symbian and then Nokia I've decided to try my hand at writing a mobile application.

The first step in writing an application is deciding what to write. This is harder than it sounds as there are already quite a range of applications out there, both for the Symbian platform and for other mobile platforms. While there is nothing wrong with creating an application which has already been done, especially if you have a new and unique take on it, but you do have to ask yourself if the world really needs another glass of beer simulator.

After some thought I realised that I wanted to try to create a simple persistence of vision (PoV) application. The basic idea with PoV is that in trying to make sense of the world, your brain merges together what your eyes see over a short period of time. This has been exploited to write messages in empty space.

This is typically done with a row of LEDs (as in the above example) and a small micro-controller like an Arduino such as in the example above or like this.

While I have dabbled in hardware before, I'm primarily a software person and as I was looking for a small mobile application to try writing, I thought a PoV application would be an ideal starting point. It's a fairly simple application which using a mobile phone has some extra possibilities, such as higher resolution (so better quality images) and more colours. I don't, however, foresee any practical use for it aside from perhaps using it to send multi-colour messages across a dark and noisy room.

Doing a PoV application also had the advantage that I could start small and add new features easily. This is very important for all software projects, whether developed as part of your job or just for fun. If it takes you a year of writing to create something which you would be proud to show people then you are quickly going to lose motivation and stop caring. Put simply, I wanted regular and meaningful milestones (or key points) where I could point at something that I could be pleased to have created. I think that this is an important aspect for any project, be it software or building a shed in your garden, human beings seem to work best when they have regular goals which they get clear feedback when they've achieved.

In my mind two lists formed as a consequence of this. The first list was a list of things that I'd need to do to get the first version done. This list needs to be short so that I can easily achieve it. The second list was a list of possible future ideas. This list needs to be long enough for me to have some interesting features to add to the application.
First version features:

• Take some text as input.
• Display it in a set time period.

Future ideas:

• Accelerometer support - so it knows when to start displaying the message.
• Colour selection - more than the plain LED red of hardware PoV.
• Multi-coloured messages - because rainbow text would be awesome.
• Image painting - is it possible to paint more than a single line of text in the air?

Happily the PoV application idea satisfied both criteria, having only two things to do in the first version and a number of varied things to do in the future.

So that's is the first hurdle passed in software development; but knowing what I was going to write was worthless if it didn't have a name. Names are very important, especially for software projects. Some schools of thought subscribe to the theory that the name is the most important thing about a project. I wouldn't go that far, but a good name is the first step in creating a good application. It's also a case with naming that thinking about it for too long, or being too clever about it, leads to a worse name. Not wanting to pick on Google in particular, but the first example of this that came to my mind was when Google decided to rename 'Froogle' to 'Google Product Search'. They renamed it as the pun on the word frugal in the name wasn't obvious.

Immediately I decided that using the term PoV was a big no-no. I always read PoV as Point of View unless something about the context indicates that it's probably Persistence of Vision. If I, as someone who knows and understand the term, doesn't find it immediately conjuring up visions of text in the air then what hope has anyone else got? So my thought turned to other names and one which lead on almost directly from the anti-PoV viewpoint was to call it 'SkyWriter'.

The name SkyWriter does almost exactly what it says on the tin and so seemed like a good name. Before getting too excited though, I wanted to check that there weren't any connotations for the name that I wasn't aware of. The easiest way to do this was to just do a web search for it, using my favourite search engine. Sadly it turns out that there is already a mobile application called SkyWriter for plane pilots and I wouldn't want to confuse pilots and be responsible for them crashing!

So I tried AirWriter and discovered, to my horror, that someone had already created a PoV application called AirWriter. Slightly disheartened I tried a few other combinations and finally decided to settle on AirText.

With all that decided I had to decide what devices and what programming language I would write AirText in. The device question was easy to answer, 'my current mobile'. I currently own a Nokia 5800 Xpressmusic. The choice of what language took only slightly longer; I'd been wanting to try writing an S60 Web Runtime (WRT) for a while now and this seemed like the perfect chance.

Another reason, and probably the most significant if I'm honest with myself, is that I've spent over four years dealing with C++ code and using the simpler language of HTML and JavaScript of WRT was very appealing. HTML and JavaScript are the languages used for web-pages and let you concentrate on describing what goes where on the screen. This makes it easier to use than C++, which requires dealing with all the complexities involved in controlling all the parts of the computer to do what you want.

With that decision made, my final step in this instalment was therefore to go over the Forum Nokia and to read up on their quick start guide for widgets.

In other news I've finally worked out that I'll keep this blog as a blog of interesting things that I've done. I realised that I do spend quite a bit of time working out how to do things with technology or reading up on some information and that it'd be good to share. I can't promise regular posting, but I will try to keep the posts here as journal entries that are hopefully an interesting read.