X11 and maps

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

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

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

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.

Hacking on USB

I like all-in-one chips. The BCM2040 is an all-in-one bluetooth keyboard/mouse solution. Connect it to a plain ‘ol keyboard matrix and hey-presto you have a bluetooth keyboard. I’m thinking about attempting to mod my twiddler chord keyboard into a bluetooth device using one of these, if I can get my hands on them.

Whilst on the subject of hardware, I notice that the Microchip PIC range now includes a couple of devices with USB support. This is cool because it means that it’ll be relatively easy to make my soon-to-be-built keyboard foot pedals into a USB device.