Archive for August, 2004

Fixing computers / Dynamic linking

Monday, August 30th, 2004

Who says you can’t fix things any more? (more photos here).

Sitting at work waiting for our C++ application to link reminds me that just because your language can do lots of stuff at compile time doesn’t mean you necessarily want it to do so. Usually with a C++, the linker goes through your code figuring out what address each function will live at, and making each function-call jump to that address. You do almost all the linking work upfront. In contrast, other languages are lazier – they don’t bother doing any work until it’s actually needed, which makes for faster edit/compile cycles because you’re not doing the work upfront. Actually, often these languages forced into being lazy because the information isn’t available at compile time. But contrapositive doesn’t apply: if you have the information you don’t have to be eager. A C++ compiler could delay figuring out which function to call until the first time the function was called. You’d also need to keep all the type information around until runtime, but you’re probably already doing that for debugging purposes anyway. You’d be moving one phase of the compiler from compile-time to run-time.

You might think it would all be much easier to do this stuff by starting with a more dynamic language. but then with “dynamic-C++” you still maintain the benefit of having static typing checking for silly mistakes. Which brings me full circle to a paper which was on LtU recently which discusses this very topic (and which I have yet to read!).

Ah, dynamic languages vs. static languages. Here I am again.

X11 and maps

Wednesday, August 25th, 2004

X11R6.8 is set to be released soon, bringing some welcome technology improvements to X11 along with lots of pretty eye-candy.

Completely unrelatedly, for a while now I’ve been thinking about how to make a free-as-in-freedom map of Edinburgh. Not just the kind of map which you look at, but also a semantic map which computers could process. It would allow route-finding applications – not just finding routes for cars, but also for cyclists who want to avoid busy roads and hills. Another application could tell you where the nearest ATM or pub was. There are hundreds of useful applications, all of which need high-quality semantically-rich maps. But, as far as I can tell, in the UK all of the commonly used maps are derived from Ordnance Survey data which, despite being a sort-of public body, charge royalties for the data.

Now, on one hand, that’s quite reasonable because it takes a lot of effort to make good maps. But, on the other hand, I have a strong feeling that somehow this information ought to be in the public domain. Local people and companies could use this data in all sorts of ways. It ought to be a shared community resource.

So, I’m left wondering how I can use technology to map Edinburgh. Maybe a combination of a digital camera, GPS and a bicycle would be a good way of grabbing useful raw datapoints? Finding existing public domain map data would be a really useful start – satellite images and photos from aircraft. And there was a recent conference about open-source mapping tools. I think I need to do some basic reading about map-making, because quite honestly I don’t know where to start.

MD5/SHA collisions cont

Wednesday, August 18th, 2004

Now that the updated paper has been published, here is how to see the collisions for yourself:

1. Create messageA.pl, containing the following:

#!/usr/bin/perl
my $p = 
"d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89" .
"55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b" .
"d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0" .
"e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70";
print pack("H*", $p);

2. Also create messageB.pl containing the following:

#!/usr/bin/perl
my $p = 
"d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89" .
"55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b" .
"d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0" .
"e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70";
print pack("H*", $p);

3. Download md5.pl from here

4. Verify it works by doing “echo -n abc | md5.pl”. You should get 900150983cd24fb0d6963f7d28e17f72

5. Run “messageA.pl | md5.pl” and “messageB.pl | md5.pl” and you should get the same hash value (79054025255fb1a26e4bc422aef54eb4)

MD5/SHA collisions

Tuesday, August 17th, 2004

Today has been a somewhat unusual day in the crypto world. Some people have found collisions in some of the major hash algorithms used today. In itself, it’s interesting but not earthshaking – after all, by their very nature, hash functions contain collisions. But a method for finding collisions in some restricted case could well lead to more general methods, which would get exciting.

Being a cynic, I tried to verify the results in the paper using the funky MD5 in 8 lines of perl, but I couldn’t recreate their results. That was a bit unnerving. However, this page explains the discrepencies. Once the paper has been presented, presumably all will become clear.

Double-press instead of shift

Tuesday, August 10th, 2004

Here’s a keyboard idea, which I’m writing up here on the off-chance that MS hasn’t already patented it. I was trying to figure out a better way of entering left-parenethesis and right-parenthesis on my keyboard (since I used them all the time when I’m writing code (and also when writing blog entries)). Currently, I have to do the shift-9 combination which is poor because I have to move my fingers off their home keys, and also involves a nasty stretch. However, there doesn’t look like many better alternatives since I use all of the non-shifted keys regularly – I’d find it inconvienient if they got remapped to ‘(‘ and ‘)’. So if there’s no unshifted keys left then it looks like I’m always going to have to use some kind of shift key?

No, we can take inspiration from the mouse. I suggest using double-clicks on the keyboard as a way of entering indicating alternative inputs. So, two presses on the ’9′ key in rapid succession would mean left-parenthesis and two presses in rapid succession on the ’0′ key would mean right-parenthesis. Obviously this impacts on my ability to type “99″ and “00″ quickly, but in an average day I typed hundred of parentheses and hardly ever need to type “99″ or “00″. On the rare occasion that I need to type them, I can simply leave a little pause (sufficient to exceed the double-click timeout) just like you do when you’re sending txts on a mobile phone without predictive texting.

Alternatively, you could use the length of time which the key was held down for to indicate an alternative input mode. Currently, almost all the keys will just auto-repeat when held down. How often is auto-repeat useful? For delete and the cursor keys it is often useful, but for the other hundred or so keys, it is less useful. So why not hijack that behaviour for more useful purposes?

Finally, we can use “chords” to indicate a whole different set of behaviour. Currently, if you hold down, say, “f” and “j” at the same time the computer will act as if you pressed “f” followed by “j” (or vice versa). It doesn’t notice that you deliberately pressed them both at the same time. If we make the computer respond differently to multiple simultaneous keypresses, we open up yet another set of possibilities for keyboard input without removing our fingers from the home keys. Effectively, we’re using the keys “a” to “z” as shift keys themselves. Clearly, you’d want to minimize the chances of triggering them accidentally whilst typing normal text so you may want to choose unlikely combinations (such as f+j) which are unlikely to occur in your normal typing (unless you write about fjords lots).

This gets rid of the need to move my hands off the home keys, and also gets rid of the awkward stretches caused by shift/ctrl combinations (although putting ctrl in the place where caps lock usually lives helps a lot too). Once I have figured out a way to get X11 to handle these cases, I’ll post it up. I also think it’s likely that keyboards from older computers used these tricks and more, but have been forgotten in the passage of time. Certainly the Spectrum used to minimize keystrokes whilst programming by automatically switching between modes as you typed, which was confusing to the uninitiated but quite efficient once mastered.