New stuff

March 7, 2010

Over christmas (it’s March, the perfect time to post your new year’s post! Happy new year, BTW!) I finally sat down and re-made www.openstreetmap.pl, the site about OpenStreetMap in Polish, similar to what you can find at the other openstreetmap sites under country-level domains.  It’s nothing spectacular but the remake was long overdue.  While at it I also launched a blog where any high-level news or propaganda about freeing geospatial information and about OpenStreetMap itself, relevant to Poland (or not), can be posted in Polish.  I think there was a need for a place like this even though there isn’t a whole lot to post there yet and not a whole lot of interest either (yet).  The openstreetmap diaries at the main site collect all kind of small and big news and user comments, so I missed a place that’s like the OpenGeoData blog in English.  If you have anything relevant to share, you can post it on blog.openstreetmap.pl now.

Second new (to me) thing in the last months was the internet’s reaction to the disaster that was the Haiti earthquake January 12.  It caused a great range of destruction and chaos and when the humanitarian relief teams rushed there it became apparent that lots of IT resources available for other places were not available for that area.  This is where people all over internet tried to help and their reaction was somethign I had never seen before, a whole new experience.  The leading by CrisisCommons and the crisis camps organised as soon as January 15 where people met to code new needed services, give ideas or just collect data.  On one day we saw more than 20 people from different crisis camps around the world joining the OpenStreetMap IRC channel asking if there was anything urgent for them to work on right now, and everyone planning how to best use their time resources.  Needless to say the advancement in terms of data quality the Port-au-Prince area was huge, much bigger than in the case of the Gaza strip initiative a year ago and than perhaps any other moment in OSM history.  Other very cool projects like this also sprung up really quickly.  A very interesting experience alltogether, one that also exposed the OSM project in a new use case / situation.  OSM proved extra valuable in it and this is always a gain for the project at the same time, now that it became part of the official FEMA resources, International Red Cross’s as well as US navy’s and got some more mainstream media attention than usually.  Now the newly created HOT or Humanitarian OpenStreetMap Team is gearing up for helping Chile overcome the damages resulting from the recent quake and is already providing accurate maps of the flooded Albanian regions.

Wikipedia overlay

October 6, 2009

Last week I’ve set up an overlay for OSM that displays Wikipedia links completely obstructing the view of the map.  I explained it in more detail in this mailing list posting, but other people have blogged about it so I probably should too.

It’s not like the Google wikipedia layer because it display links from OpenStreetMap entities to Wikipedia, not the other way.  At the low zoom levels you’ll only see dots but if you zoom in to an interesting place there will be roads, rivers, polygon areas etc all linking to respective Wikipedia pages.  Only Firefox is supported because I’m not using OpenLayers (but some WebKit-based browsers seem to work some of the times, and a commercial browser starting with O).

The goal of this is to get more people using the wikipedia= tag in OSM — if you’ve been making applications with OpenStreetMap data you’ve surely noticed that people much more often map features that get visualised somewhere in some way.  It’s also an experiment in a couple of directions: it’s a tiled GeoJSON layer (as opposed to bitmap tiles) — this gets us browser caching and seems to be much faster than an area query like OpenStreetBrowser uses.  The tiles can be retrieved using JSON-P in addition to xhr, I also have added a kind of “kinetic” zoom — the base map widget is based on Bernhard Zwischenbrugger’s excellent zoom zoom zoom map in place of OpenLayers, meaning it’s also 20 times smaller in terms of lines of code.  Also zoom beyond mapnik tile levels is supported, this may be good accessibility wise even though it’s a bad workaround for the default mapnik style rendering names in a pretty small font.

I’ve also set up a http redirect for wikipedia interwiki links and images that saves you one click, it’s fully described at the OSM forums but in short, if you only know the german title of a wikipedia page referring to something, you can type http://wp.openstreetmap.pl/de:Bananen and you’ll be redirected to a page about bananas in the language configured in your browser.  http://es.wp.openstreetmap.pl/de:Bananen in turn will send you to the Spanish page about bananas, i.e. http://es.wikipedia.org/wiki/Musa_×_paradisiaca

Morton numbers

August 3, 2009

Long time no posting, but I have excuses (also I’m posting some at openstreetmap user diaries).

So anyway here’s a cheap trick I came up with but which you might already know.  If you’re indexing any georeferenced data, such as when doing any fun stuff with OpenStreetMap data, you’ve probably wanted to index by location among other things, and location is two or three dimensional (without loss of generality assume two as in GIS).  So obviously you can combine latitude and longitude as one key and index by that but that’s only good for searching for exact pairs of values.  If your index is for a hash table then you can’t hope for anything more but if it’s for sorting of an array you can do a little better (well, here’s my trick): convert the two numbers to fixed point and interleave their bits to make one number.  This is better because two positions that are close to each other in an array sorted by this number probably are close to each other on the map.  You could probably use floating point too if you stuff the exponent in the most significant bits and get a result similar to some degree.  With fixed point you can then compare only the top couple of bits when searching in the array to locate something with a desired accuracy.

Converting to and from the interleaved bits form is straight forward and you can easily come up with a O(log(number of bits)) procedure (5 steps for 32 bit lat / lon) or use lookup tables as suggested by the Bit Twiddling Hacks page, where I learnt they’re called Morton numbers.  32-bit lat/lon will give you a 64-bit number and that should be accurate enough for most uses if you map the whole -90 – 90 / -180 – 180 deg range to integers.  Even 20-bit lat/lon (5 bytes for the index) gives you 0.0003 deg accuracy.

So what else can you do with this notation? Obviously you can compare two numbers and use bisection search in arrays or the different kinds of trees.  You  can not add or subtract them directly (or rather, you won’t get useful results) but you can add / subtract individual coordinates without converting to normal notation and back, here’s how:

First separate latitude from longitude by masking:

uint64_t x = a & 0x5555555555555555;
uint64_t y = a & 0xaaaaaaaaaaaaaaaa;

Now you can subtract two numbers directly, you’ll notice that the carry flags are correctly carried over the unused bits, you’ll just need to mask them out of the result:

uint64_t difference(uint64_t a, uint64_t b)
{
	...
	return ((ax - bx) & 0x5555555555555555) |
		((ay - by) & 0xaaaaaaaaaaaaaaaa);
}

(you can also use this Masked Merge hack from the page I linked earlier).

The result is signed two’s complement with two sign bits in the top bits.

Now something much less obvious is that if you want to calculate absolute difference, you can call abs() directly on the result of subtraction and only mask out the unused bits afterwards.  How does this work?  The top bit in (ax - bx) always equals the sign bit even if ax and bx only use even bits (top bit is odd), so this part is ok.  Now, if the number is positive then there’s nothing to do with it.  If it’s negative, then abs negates it again (strips the minus).  Conveniently -x equals ~(x - 1) in two’s complement, so let’s see what these two operations do to a negative (ax - bx)~ or bitwise negation just works because it inverts all bits including the ones we’re interested in.  The x – 1 part also works because it flips all the bits until the first 1 bit starting from lowest bit, and you’ll find, although it may be tricky to see, that the first bit set in (ax - bx) is always even (or always odd).

uint64_t distance(uint64_t a, uint64_t b)
{
	...
	return (llabs(ax - bx) & 0x5555555555555555) |
		(llabs(ay - by) & 0xaaaaaaaaaaaaaaaa);
}

Addition requires a little trick for the carry flags to work: just set all unused bits in either ax or bx:

uint64_t sum(uint64_t a, uint64_t b)
{
	uint64_t ax = a & 0x5555555555555555;
	uint64_t ay = a & 0xaaaaaaaaaaaaaaaa;
	uint64_t bx = b | 0xaaaaaaaaaaaaaaaa;
	uint64_t by = b | 0x5555555555555555;

	return ((ax + bx) & 0x5555555555555555) |
		((ay + by) & 0xaaaaaaaaaaaaaaaa);
}

Python stack in GDB

February 9, 2009

I’m sure everyone already knows about this, but it’s such a nice feature I’ll post it anyway.

There’s a set of macros for gdb, described in a comment on this page, that will let you attach to a running python program using gdb and inspect its python call stack and python objects using the familiar interface of gdb.   I’m a complete stranger to python and couldn’t figure out how to enable the python debugger, and it would get me lost even if I managed to enable it. Additionally I was trying to find out when and why a python program uses a particular syscall and I’m not sure the python debugger can help with this.  For the record that python program blocks all signals so I couldn’t just send it a signal and have it print the stack.

I’m wondering if you can do the same thing with Java, and who’ll be the first to implement the gdb macros.  I’ve not coded java for years but it makes me want to have a look at it again considering there’s source code for it now (I just wish I had the time). How about swi-prolog?

Practical note: For this to work you will need to rebuild python with debug information in. If you’re on Gentoo, whose default package manager uses python, and if you still have python2.4 installed, if you screw up your python2.5 installation, you can revive emerge by running it implicitly with python2.4 (python2.4 /usr/bin/emerge blah blah).  To rebuild python with custom options, edit /usr/portage/dev-lang/python/python-2.5.2-r8.ebuild to add –with-pydebug, and run ebuild /usr/portage/dev-lang/python/python-2.5.2-r8.ebuild digest unpack, then edit /var/tmp/portage/dev-lang/python-2.5.2-r8/work/Python-2.5.2/Objects/unicodeobject.c to remove the assert on line 372, which seems to be a typo, and then ebuild /usr/portage/dev-lang/python/python-2.5.2-r8.ebuild compile install qmerge to let it finish.  You may need to re-emerge some of the packages that have installed into /usr/lib/python2.5/site-packages) for your program to work again.

Get kiva.org credit from MTV

February 1, 2009

MTV gives away $25 gift certificates for lending on kiva.org (you’ll need to register)

Public transport season is on

January 4, 2009

All the times it snowed this winter it first looked like it was going to stop me from biking through the city but was followed by a soon change in weather and the snow melted before I actually needed to go anywhere.  Today I’ll need to make a small trip and the streets are covered with enough snow that melting it in the time left until I’m leaving would require an amount of energy to radiate that would be dangerous to forms of life, so I think it’s the end of the biking season finally.

Accelerating in my pocket

June 8, 2008

I started poking at the SMedia Glamo chip in the GTA02 this week. First I played with the Linux framebuffer driver and later with decoding MPEG in hardware, and now I have some code ready. I was challenged by messages like this on the Openmoko lists. Contrary to the opinion spreading accross these messages, we’re not doomed and we still have a graphics accelerator in a phone (which is coolness on its own). And it’s a quite hackable one.

I first had a look at libglamo code – a small library written some time ago by Chia-I Wu (olv) and Harald Welte (laf0rge) for accessing some of the Glamo’s submodules (engines). I asked the authors if I could use their code and release it under GPL and they liked the idea, so I stitched together libglamo and mplayer and added the necessary glue drivers. This wasn’t all straight forward because mplayer isn’t really prepared for doing decoding in hardware, even though some support was present. Today I uploaded my mplayer git tree here – see below what it can and cannot do. There’s lots more that can be improved but the basic stuff is there and seems to work. To clone, do this:

cg-clone git://repo.or.cz/mplayer/glamo.git

The Glamo fact sheet claims it can do MPEG-4 and H-263 encoding/decoding at 352×288, 30fps max and 640×480 at 12fps max. Since it also does all the scaling/rotation in hardware, I hoped I would be able to play a 352×288 video scaled to 640×480 at full frame-rate but this doesn’t seem to be the case. The decoding is pretty fast but the scaling takes a while and rotation adds another bit of overhead. That said, even if mplayer is not keeping up with the video’s frame-rate it still shows 0.0% CPU usage in top. There are still many obvious optimisations that can be done (and some less obvious that I don’t know about not being much into graphics). Usage considerations:

  • Pass “-vo glamo” to use the glamo driver. The driver should probably be a VIDIX subdriver in mplayer’s source but that would take much more work as VIDIX is very incomplete now, so glamo is a separate output driver (in particular vidix seems to support only “BES” (backend scaler?) type of hw acceleration, which the Glamo also does, but it does much more too). Like vidix, it requires root access to run (we should move the driver to the kernel once there exists a kernel API for video decoders – or maybe to X).
  • It only supports MPEG-4 videos, so you should recode if you want to watch something on the phone without using much CPU. H-263 would probably only require some trivial changes in the code. For completeness – MPEG-4 is not backwards compatible with MPEG1 or 2, it’s a separate codec. It’s the one used by most digital cameras and it can be converted to/from with Fabrice Bellard’s ffmpeg. A deblocking filter is supported by the Glamo but the driver doesn’t yet support it. For other codecs, “-vo glamo” will try to help in converting the decoded frames from YUV to RGB (untested), which is normally the last step of decoding.
  • The “glamo” driver can take various parameters. Add “:rotate=90” to rotate (or 180 or 270) – the MPEG engine doesn’t know about the xrandr rotation and they won’t work together. Add “:nosleep” to avoid sleeping in mplayer – this yields slightly better FPS but takes up all your CPU, spinning.
  • Supports the “xover” output driver, pass “-vo xover:glamo” to use that (not very useful with a window manager that makes all windows full-screen anyway).
  • Only works with the 2.6.22.5 Openmoko kernels. There were some changes in openmoko 2.6.24 patches that disabled access to the MPEG engine but since we don’t have a bisectable git tree I can’t be bothered. UPDATE: A 2.6.24 patch here – note that it can eat your files, no responsibility assumed. I guess it can also be accounted for in mplayer, will check. My rant about lack of changes history in git is still valid – while I loved the switch to git, the SVN was being maintained better in this regard.
  • In the mplayer git tree linked above I enabled anonymous unmoderated push access so improvements are welcome and easy to get in.

With respect to the linux framebuffer poking, I wanted to see how much of the text console rendering can be moved to the hardware side and it seems the hw is not lacking anything (scrolling, filling rectagles, cursor) compared to the other accelerated video cards, and even the code already exists in Dodji Seketeli’s Xglamo. I’m sure sooner or later we’ll have it implemented in the kernel too. For now I got the framebuffer to use hardware cursor drawing (alas still with issues).

Bricked! lol

May 28, 2008

Somewhat related to the Phoenix probe landing, I found in the Viking mission page on wikipedia (the exams are here again and I’m looking up things on WP and then getting stuck reading completely unrelated stuff and consequently failing exams) an amazing bit of information. The mission started in 1975 when it sent to Mars two NASA rockets carrying four spacecraft, each having on-board a computer based on the RCU1802 chip (that was a legitimate computer at that time). All four vessels successfully carried out their missions but each one failed years later in a different way. Three computers were shut down in appropriate ways worth a space travel (physical damage) but the last operating one has this failure reason: Human error during software update.  Sounds so contemporary.

It’s amazing that a board that left Earth in 1975 could be updated from 100,000,000 km away (some vendors still don’t get it about updates). Even more amazing is that the discussion of whether (and how) to protect software from the user is still not resolved. FIC GTA phones evolve a pattern of writable and read-only memories to become “un-brickable”. I’m sure that’s partially because it becomes less clear who is a user and who is the developer (like in a NASA mission). It’s clear that nobody wants their mission to end this way, “a lorry ran over my phone” somehow sounds much better.

Gazpacho a lo guiri

May 19, 2008

Background: I try lots of new things when I make my food and while most of my experiments fail miserably, there are cases that come out well enough that I even repeat them, so I thought I can share (open-source) one of these results, and this is an attempt. But, open-sourcing food, strangely, isn’t so easy because the “code-base” is very ugly – everything is an undocumented hack (or “spaghetti code”), and needs to be documented. My optimisation flags are always set for minimising the number of dishes to wash and ingredients cost.

Gazpacho: gazpacho is a Spanish dish (or drink) originating from Andalusia. It’s made of mainly vegetables, is almost liquid, is consumed cold and doesn’t involve cooking. It’s eaten in the summer only, especially on hot days. (At higher latitudes than Spain, I found the added practical argument is that vegetables are about 3 times cheaper in the summer).

There are a zillion types of gazpacho and some Spanish are very religious about preparing it, especially those who make cookbooks. Every region has its own type, but there’s also the generic type that you can buy in supermarkets or in McDonald’s.

Now, I’m not Spanish and I allow myself to break some of the rules. If you’re Spanish, stop reading here because you’ll find that I’m committing various terrible crimes against the mediterranean cuisine.

The recipe: today I completed a quest for all the ingredients and made a gazpacho again and it turned out eatable again, so it must not be extremely difficult, here’s the list.

  • 0.5 to 1kg of tomatoes (canned tomatoes will also do, even a box of juice – here’s where I commit the first crime).
  • 2 red peppers/paprikas, optionally add one green.
  • 2 or so slices of bread.
  • one half bulb of garlic (maybe less).
  • a medium-size onion.
  • a cucumber.
  • 1tbs or so of salt, some pepper (or none).
  • half a glass of oil (here’s my second crime: use any oil – it really really doesn’t matter that much. It appears that if you’re Spanish a single drop of oil that is not the absolute highest quality immediately spoils your dinner. You will never ever see or hear the word oil (aceite) go alone when you’re in Spain – it is in 100% cases accompanied by the words virgen and extra, as in aceite de oliva virgen extra – it might equally well just be a single word in the vocabulary because it always appears together, I don’t think anyone is even able to pronounce aceite alone).
  • 4tbs or so of vinagre and half glass of water.

Place the bread in a plate with water and let it dissolve a bit. Cut all the vegetables into pieces of sizes that will make your electric blender happy. The peppers and tomatoes are fine as they are (another crime!) – in a real gazpacho recipe they tell you to peel them and remove the seeds, but the seeds are the best part, they’ll get blended anyway and they’ll just make the texture nicer, and peeling is just too much work. Blend the bread, vegetables, and water until liquid. Then throw in the oil, vinagre and salt and mix again until the oil can’t be seen.

The colour is between orange and pink and is most influenced by the red peppers. The taste is most affected by the salt and vinagre and you need to adjust their amounts but it will probably be a lot of vinagre and a lot of salt. Too much onion or garlic makes the gazpacho spicy but at some point the smell is too strong.

When it’s done, just store in a fridge and serve cold optionally with pieces of toasted bread.

Unscientific GPS note

April 28, 2008

Last week I charged the different batteries and took a GTA01 Neo, a GTA02 Neo and a Nokia N810 with me to enable their GPSes on my way home from school. Then I saved the traces they logged and loaded into JOSM to have a look (GTA01, GTA02, N810 – gpx files converted using gpsbabel from nmea)

The devices made respectively 11.28km, 12.12km and 11.07km routes (sitting in the same bag the whole time).

All in all I like the GTA01 accuracy the most although all three sometimes have horrible errors. They all three have accuracy about near the bottom line of usability for OSM mapping for a city, so if you get a GPS with that in mind, it may be slightly disappointing. All three are quite good at keeping the fix while indoor but everytime there’s not enough real input available they will invent their own rather than admit (if you had physics experiments at high-school and had to prove theories that way, you know how this works), resulting in run-offs to alternative realities – especially the N810 likes to make virtual trips. They all three apparently do advanced extrapolation and most of the time get things right, but the GTA01 GPS (the hammerhead) very notably assumes in all the calculations that the vehicle in which you move has a certain inertia and treats tight turns as errors. I’m on a bike most of the time and can turn very quickly and it feels as if the firmware was made for a car (SpeedEvil thinks rather a supertanker).

It’s suprising how well they all three can determine the direction in which they’re pointing even when not moving (the GTAs more so). The firmwares seem to rely on that more than on the actual position data sometimes. This results in a funny effect that the errors they make are very consistent even if very big – once the GPS thinks it’s on the other side of a river from you (or worse in the middle), it will stay there as long as you keep going along the river.

I’m curious to see what improvement the galileo system brings over GPS.

UPDATE: I was curious about the precision with which the altitude is reported, which can’t be seen in JOSM.  First I found that the $GPGGA sentences on my GTA01 have always 000.0 in the elevation field, but the field before it (normally containing HDOP) has a value that kind of makes sense as an altitude, so I swapped the two fields (HDOP value should be < 20.0 I believe?).  Then I loaded the data into gnuplot to generate this chart:

The horizontal axis has longitude and vertical the elevation in metres above mean sea level.  Err, sure?  I might have screwed something up but I checked everything twice.  Except the GTA01 which might be a different value completely – but the is some correlation.  I’m not sure which one to trust now.