Unscientific GPS note

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.

Panoramic photos revisited

Every some time there’s a place that would look great on a panoramic picture but I only have a plain touristic camera with me and decide to take a series of photos in all directions from one point with a plan to later glue them together to get something real. Then I forget it completely or sometimes I load Gimp and glue the pictures together. This can take an hour or two and gets boring, but the result is often ok (digital example, analog camera example). This time I decided to try to get my PC to do the gluing for me and use one of the tools that appeared in gentoo’s portage tree. This didn’t go faster than I would have done it manually (perhaps five x longer) but knowing about all the quirks, it may actually go faster next time, and the result is comparable with manual stitching. So let me just write down the things I wish I had known when I started. The package that is now in most distro’s repositories and that I used, is libpano12 and various tools associated with it.

First part is selecting the individual pictures and telling the computer how they are oriented in relation to each other so it knows how to glue them. Hugin (a GUI frontend for libpano) lets you select the shots and input the data necessary for libpano to make sense of the individual pictures, which is a list of common points on the overlapping parts of the photos. This part quite intuitive. Remember to build the latest hugin and latest wxGTK or hugin will segfault. Before loading pictures into hugin rotate them in Gimp to be at least more or less straight (if they aren’t). Have 2GB of free disc space. Choose one of the rectangular projection types because the fancy ones are not supported by the other tools we’ll need to use. The picking of common points can be done automatically by autopano-sift but this has mono and other heavy packages as dependencies so I avoided it. When you’re done placing the points and playing with all the other parameters in hugin, hugin will want to generate a script for the stitching program that will do the heavy work. Hugin knows about two such programs: PTstitcher (part of panotools) which sucks because it’s closed-source and only works on one arch. The second one is nona which sucks because it doesn’t support most of the format, projections, blending, auto adjusting. So we will choose “multiple TIFF” as the output format, set all the other parameters, save the project, tell hugin to generate the script to a text file and quit hugin. Now we have one other program to do the stitching: PTmender, an opensource replacement for PTstitcher, also part of panotools - this one supports the formats we want and some automatic colour balance / exposure correction but if you choose any of the plain bitmap output formats, it won’t blend them nicely together because it’s not supported yet. If you in turn want a format with the individual pieces on separate layers (XCF not supported yet, so PSD) to do the merging in Gimp, PTmender will segfault in some doubly-linked-list code. So we choose the “multiple TIFF” output format and get TIFFs that are ready to merge except they don’t have any transparency mask set. We could now use Gimp’s “alpha to selection” and “feather selection”, but there’s a program, enblend, that will do just this merging, and does it really well (using multi-resolution splines). It only operates on TIFFs, and seems to get all the parameters right if you don’t give any.

You may need to repeat some part of the process if you see something really bad in the enblend output, and if not then you just need to load it in Gimp and rotate / crop / scale the picture. To load TIFFs in Gimp you may need to rebuild with USE=”tiff” if you’re on Gentoo.

Trip

So I went to Brazil last month but had no time to put any pictures online, now I uploaded them here. Also uploaded some pictures from a trip to Spain that was just before that.

Brazil cities reminded me a lot of Peru, which was the only place I had seen in America (this comparison must seem awfully ignorant to anyone who lives in some place between Brazil and Peru). We spent one week in Ceará region seeking out best places for paragliding. One of the spots was the launch pad near Nossa Senhora Imaculada sanctuary near Quixada where “Sol” group (Brazil) took off last year and set the current world record in straight distance paraglider flight landing over 460km away. (Obviously this was a different season and incomparable weather conditions.)  I made an attempt to adapt my Neo1973 Linux phone to dub as a variometer using the altitude data from built-in GPS.  Impressively the measures are somewhere on the edge of being accurate enough for that purpose, but time resolution is way too low (normal variometers use air pressure changes rather than GPS).  The speaker is loud enough to emit the familiar beeping of a variometer (so good enough for showing off even if inaccurate).  The GTA02 should be much better with its 3D accelerometers, but I didn’t have time to play with it yet.

The second week the group split and I went Bossa ‘08 conference that was in a fantastic setting and from where I brought home a collection of five geeky t-shirts.

I could’ve written a novel with all the keystrokes

In other words if you printed all the vim commands I typed, on Earth’s equator in 15pt font, you would get a very repetitive string printed on Earth’s equator line (which could no way be seen from outer space).

$ history | awk '{a[$2]++ } END{for(i in a){print a[i] ” ” i}}’ | sort -rn | head
2673 vim
1475 cd
694 screen
632 make
475 man
329 ls
261 grep
231 cg-diff
161 aoss
149 cg-patch

The numbers sum to > 1000 because I use HISTSIZE=”10000″ and HISTCONTROL=”ignoredups” in my bashrc.

OMAP3 resources opened

Texas Instruments OMAP series of mobile CPUs have for some time had okay Linux support with parts of the code coming from community, parts from TI and parts from Nokia, one of the vendors. This month we start seeing results of TI’s recent efforts on making this support better by opening various technical resources that were available only to the vendors earlier. Yesterday the announcement of their DSP-bridge framework release under GPL was posted to the linux-omap list, and as of this week you can download the entire TRMs (35MB PDF each) for various OMAP3 CPUs from ti.com. Added to this are various types of manuals, example code and that covers also the recently announced 35xx models.

I had an occasion to be at TI’s Rishi Bhattacharya’s talk at BossaConference last month with a sneak peek on the process of opening OMAP3 related resources that had been ongoing internally for some time. Apparently more releases are planned including among other things some GPLed sources (and some freeware binaries) of DSP codecs for use on OMAP. This also should make life a fair bit easier. One of the interesting points was also the evaluation board for the new processors which looks a bit more like a final product than previously made evaluation boards. It’s called Zoom MDK and it’s sold by a third party. It includes a modem, optional battery and a neat case so it can potentially be used as a (only slightly oversize for today’s standards) phone, and comes equipped with a full Linux SDK. One of the points is also to make it more affordable so that individual developers are not excluded (currently only available through a beta programme but the final price was said to be aiming at below $900). There’s an effort to have Openmoko running on the thing. Looking forward to that and to the rest of the releases from TI.

Need more freedom, more freedom!

After some discussion it was agreed that the freedoms guaranteed by free / open-source software were no freedom at all and that we need to add more freedoms.  The proposed fifth freedom is the freedom of choosing the implementation you want to use.  To spread the idea the Multi-source Software Foundation is hereby established, MSS being the proposed short-hand for the body of software that comes with more than one source representations of the program, letting you choose the source you wanna compile.  Among our flagship projects are such fundamental programs as hello world, pacman, tetris, netcat.

Nomadic C162

…is a regular smartphone (don’t confuse with Nomadik). I’m only posting about it because I found completely no information about it on the intarwebs when trying to answer the simple question of whether Linux could be ported to it, so that if anybody else wants its specs they don’t have to take the device apart anymore. I got one such phone this week and today disassembled it and collected the list of chips it features, complete with pictures. All chips on the PCB have metal covers on them, some of the covers have to be ripped out by force. There’s nothing special about the phone except that it’s a CDMA phone (uses the CDMA2000 standard in the 850MHz range) and that local calls are free, but the network only exists in Warsaw, outside this area it becomes an mp3 player/camera with four hours running time (in constant use, so not terribly bad). The manufacturer of the C162 is a Chinese company called TechFaith. They have several similar models on their website but no mention of C162 or C161c in particular. The Polish operator Sferia seems to be the only operator using these models. Here’s the obligatory generic diagram of the OS structure of TechFaith devices.

The specs I collected are in this text file. I uploaded some pictures of the C162 intestines here, together with some pics of my new GTA02.

The answer to my original question seems to be that the C162 can’t run Linux because the CPU is from the MSM6k series by Qualcomm which features ARM7TDMI cores (i.e. no mmu), so the best you can get is uClinux, but then it seems Qualcomm doesn’t make the documentation accessible. There exists a working kernel tree for the MSM7k series maintained by the Google Android project, probably some drivers would be reusable.

4: OABI spec

Bad news, I’m gonna talk about OABI again.  I just want to write down what I found about it before I forget, so that it gets indexed and a person needing to know something can find it on google.

I was told by a gcc hacker that it was based on the APCS32 ABI whose specification can be found here.  The specification is however very vague about some parts, and other parts are simply different from OABI, so I’ll point these out and refer to APCS32 in other places, and compare with EABI also.

Control arrival. One thing that is not specified at all in either APCS32 or EABI is the program entry point requirements. These may be system-specific but the Linux Standard Base has no mention of ARM entry point either.  The only reference thus is the Linux kernel code. Qemu-arm code is based on it. The requirements don’t seem to have changed between OABI and EABI and they’re also pretty much identical to the x86 entry point requirements which can be found in the SysVr4 docs, modulo some of the tags put on the stack before entry. They can be found in Linux or qemu and I’m not gonna list them here.

APCS Variants.  The APCS32 document specifies 16 incompatible variants based on four different properties that can have two possible values each.  Linux OABI is the 32-bit case (as opposed to 26), with implicit stack-limit checking (as opposed to done in software), floating-point arguments/return values passed in registers and on stack (i.e. FPU registers are not used for that) and is non-reentrant (except libraries).

Arguments passing.  Register have the same meanings as in APCS32 with first four words of argument list passed in registers and the rest on stack, with the possibility of a single argument split between the two.

Floating-point values.  There’s no mention of their encoding in APCS32 but it seems to be the standard IEEE 754 encoding - with a small caveat… Doubles and long doubles have their first 32-bit word swapped with the second word, when compared to EABI or x86. The same applies to both of the individual doubles inside a double _Complex and inside long double _Complex.

Return values.  Here we have the same three variants as in APCS32: no return value, return value in register(s) and return value in an implicit pointer passed as arg0.  There is a very tricky difference from APCS32 though: when is the second variant chosen and when is it the third one.  APCS32 recognises something it calls simple types which it defines as anything that fits in four bytes.  Anything bigger is returned through a pointer.  In OABI there seems to be a similar idea except the simple type is defined differently: All C basic types are simple, even if they exceed the word width.  In addition to this a struct seems to be considered simple as long as it has only a single member whose type is simple (possibly a struct) and not larger than one word.  Arrays are never simple and unions are simple if all their fields are simple.

The $100 question is how do you return an object of a simple type wider than one word in a register?  APCS32 allows only r0 to be used for that, but gcc doesn’t mind using also r1, r2 and r3.  So a long long int, double, long double, int _Complex or a float _Complex will all be returned in the r0-r1 pair, while double _Complex and long double _Complex get returned in r0-r3.

Alignment.  Pointers have to be word-aligned only and this applies also to the stack pointer on call.  This is nothing special but if you want to mix OABI and EABI it becomes a major caveat because EABI requires the stack to be aligned on 8-bytes in inter-linking-unit calls.  If you forget about it and call and an EABI function from OABI context you will get the strangest and extremely hard to debug results, such as glibc sprintf() returning a wrong value, which can very painful.

Another change that happened at the same time as the OABI to EABI switch in Linux was a switch from setjmp/longjmp based C++ exceptions (the generic, cross-platform way) to a new, faster model (EABI does specify how exceptions should be handled and how stack unwinding works, while APCS doesn’t - this aspect is known as C++ personality across the docs and code).  I am not describing it here.

If something of the above is wrong, please lemme know.

3: Getting gllin to run

I was going to make a small trip this weekend but I missed my plane and have to wait until next week. But that means I already have a good excuse for not spending the weekend studying for this week’s exams and I have finally put the time into making gllin behave under Schwartz.

Gllin is a closed-source driver for the Global Locate (now Broadcomm?) GPS known as Hammerhead and it’s been said it didn’t work when the folks compiled it for ARM EABI (i.e. what is used on most ARMs currently) so they only released the OABI binary (the ad-hoc ABI that was used on Linux until ARM came up with a standard ABI and hired people to implement it). So the downloadable gllin package comes with an OABI rootfs which will run under chroot if you have OABI support in your kernel. It seemed wrong to me to have a second rootfs on my phone to run a single program, and it has several other drawbacks.

With the Schwartz loader/linker you can run OABI-compiled programs natively on Linux systems that use different ABIs. This is achieved through translation of library calls that I mentioned previously. Schwartz is by no means complete, and more than anything it’s a proof-of-concept, but it seems to be usable and today my Neo1973 had an actual 3d fix and gave me real coordinates as well as satellite time/date and other info. I took my Neo for an excursion to the shopping mall (not so much to show off, but) to make my first GPS trace for OpenStreetMap. It ran quite stably for the whole 2h and I uploaded the trace here. So here’s how to use it.

Download the schwartz binary from here or here (minimal version). The sources are in this git tree, but building them is not exactly straight-forward. Upload the file to your Neo1973 (or qemu-neo1973). Upload also the gllin binary if you don’t have it there already. In the openmoko package the binary is named gllin.real because gllin is a wrapper script that runs the whole chroot thing. You only need the “.real” binary. You can also safely leave out OABI support from your kernel. Next, make the named pipe for your NMEA data, same way the openmoko package does. After that we’re ready to run gllin and then your favourite gps software.

 $ mknod /tmp/nmeaNP p
 $ cat /tmp/nmeaNP | gzip >> /home/root/gps.gz &
 $ ./ld4 --depnofail --weakdummies --settargetname --noinit gllin -low 5
 $ ./ld4 --depnofail --weakdummies --settargetname --noinit gllin -periodic 2

You can modify the scripts from the package to do all that. ld4 is quite verbose and will print lots of stuff tot he console, which just shows how far it is from completeness. The minimal ld4 differs from the full binary in that the “strace” code is not compiled in. With the full binary, if you append –trick-strace to the cmdline options you will get a strace-like (but more pretty!) log of all functions being called and their parameters. This may potentially be useful for the folks reverse engineering the Hammerhead protocol but I’m not really sure. In the ld4 output you can see a lot of debugging messages and other, that gllin doesn’t normally print out. I have not noticed any anomalies when running gllin under Schwartz but it’s totally possible that the floating-point precision is reduced or something else is broken. gllin is a pretty tough test case for the ABI translation thing for various reasons: all the floating-point arithmetics, heavy usage of memory/files/sockets, C++ libraries, C++ exceptions, real-time constraints and more.

Among other things schwartz enables you to do is running gllin without root privileges (chroot normally requires those). Also an interesting thing to do is compare the strace (the real traditional strace) output of gllin running under a chroot with OABI compiled libc, and the strace output of the same gllin running under schwartz and using EABI libc. You’ll see two different sequences of syscalls being made, but having pretty much the same end effect.

I probably won’t have time to hack schwartz further but improvements from others are welcome. I just wish I had the thing running earlier - ironically I already have a GTA02 on my desk, and GTA02 has a different GPS chip in it which needs no driver on the OS side. There’s very little time left till the mass-production and selling of GTA02 starts and gllin slides into oblivion. (It seems that the TomTom Go’s using the same or a similar driver though).

2: ABI translation

First, why would we want to do that? Most architectures have a single popular ABI accepted by the kernel and supported by the binutils, on Linux this is usually the System V R4 defined ABI. This is the case of i386. X86-64 also has a single standard ABI based on the i386 ABI but it’s not a System V standard because System V doesn’t seem to have one for x86-64 yet. The ARM case is different because there are more than one ABIs in use and you can get a mismatch when pairing user-space and kernel images or libraries for a program. The older and unstandardised one is called OABI and Schwartz can (attempt to) translate between OABI calls issued by an OABI-compiled program and whatever ABI the host uses. This will be enabled automatically if an OABI executable is detected, no command line switch needed.

Why it seems this hasn’t been done before? Because it’s non-trivial. Currently people resort to using an entire OABI rootfs sitting in a subdirectory of the host rootfs and chrooting to it, if they need to run a OABI binary in a system that uses EABI.

Why is it non-trivial and how does Schwartz do it? In a nutshell if an executable is compiled with a different ABI than the host, we need to translate everything that’s being passed between the program and the libraries it uses (this is assuming the executable is dynamically linked and issues no syscalls directly - otherwise only the syscalls would have to be translated but that cannot be done in user-space so we’re not concerned with this) and the format of this interaction is precisely what ABIs define. Two types of interaction occur that I know of: through data and control. The control is always passed to and from libraries in the same way, through jumps aka. branches, and there isn’t any space for differences between ABIs so we’ll concentrate on the data. Data is passed on various occasions. I will divide all the data interaction into three parts:

1. static chunks of data shared between program and library. This means mainly global variables in terms of a C program or other. The format of a variable depends on it’s type and the ABI. The most basic types are encoded always the same way, while data types which are constructed of sub-elements, like structs, have a format governed by the ABI. The ABI usually specifies how elements are packed inside an object and there may be important differences between ABIs. Fortunately global objects are not usually shared by libraries, and those that are, are almost always simple types, so we don’t perform any translation. In addition it would be very difficult because we would have to react to every access to such variables, and in some cases completely impossible, for example for C union types, because the data has more than one interpretation in such cases, and we can’t tell which interpretation is used in which access.
2. on program entry. Entry happens only once, when the control is passed to the program at start and is accompanied by some data being passed too (for example the command line arguments). This part is easy because we can have a separate entry for each ABI, and some ABIs just don’t specify any requirements for the entry point (this is the case of OABI and EABI, and the Linux implementation is exactly identical for both of them). So currently there’s only one main() call per architecture in Schwartz.
3. on function calls. This is responsible for the biggest part of ABI translation in Schwartz. A function call between a program and a library is accompanied by data being passed both ways, from caller to callee in call arguments, and from callee to caller in the return value. We will see below that a library can be both a callee and a caller, for different functions. Function parameters as well as their return values can be passed differently depending on the ABI. The ABI usually specifies when and which parameter values (or parts of them) are passed in registers (of the CPU or FPU) and which are marshalled on stack, and possibly which are passed as pointers. They can also have different types, ranging from simple to compound, where the packing is important again, as it was in 1.

How does Schwartz handle function calls to different ABIs? We simply make a wrapper for every library function that we suspect may be used, and we resolve function symbols to our wrappers instead of the original functions. Again this is not a generic solution if we want to load arbitrary executables but practically is good enough. If there is an executable that uses symbols we haven’t a wrapper for, we can easily add information about the new function and recompile. The information is generated automatically based on system headers and a list of symbol names (and the list is extracted automatically from a list of executables). Such wrapper will accept parameters in the program’s ABI format, adapt them to the library ABI if needed and call the real function passing the same parameters but in the library’s ABI again. The same has to be done with the return value, just in the reverse order.

But here’s the trick: a function pointer is also a data type, so it can be passed as a parameter or a return value from a library function, and we have to handle it very carefully. Example library functions that take a function pointer as parameter are signal(), qsort() or __libc_start_main() (specified in Linux Standard Base). Example function that returns a function pointer is signal() again. So how do we handle translation of the function pointer data type? We have to generate a wrapper for every value passed that is a function pointer, and since there may be different such values passed in successive calls to the same function as parameters, we have to do it dynamically in the run-time, for every value separately. Fortunately there’s only a finite number of such values because the only valid values are those that point at functions in the program (plus optionally NULL, which we pass intact) and there is a finite number of functions, they aren’t generated dynamically. Now the wrappers will be of two types: those for parameters and those for return values. To see the difference between these two, let’s look at what the callee can do with the value it is passed in a parameter and a value a caller gets when it is returned from a call. It can do two things:

1. It can make a call to the function pointed to by the function pointer. If we’re a callee and we got a function pointer in a parameter we will want to make the call in our ABI, while the function was passed from the caller so it expects parameters in the caller’s ABI, so we need translation again. But this time the callee (we) becomes a caller and the target of the call is a function passed from the other ABI, so the translation needs to be in reverse direction. If we are the library and the caller was the program, we now need a wrapper that translates from library ABI to program’s ABI. The converse case is easier: we’re now the caller, we called a function and it returned another function pointer. The function which is pointed at will expect parameters in the callee’s ABI so the translation occurs in the “same direction” as before.
2. It can remember the value somewhere and the value can later be returned or passed as a parameter back to the other side. Since the function pointer is a value we got in return or in a parameter, we know that it is already wrapped appropriately by Schwartz. But we are now passing it back to the other side, precisely where it came from. If we follow the logic from 1. we will be unnecessarily wrapping it again (wrapping the wrapper) in a translator of opposite direction. Schwartz has to notice the double wrapping and “annihilate” the two translators and just pass the original pointer, in order to inhibit the possibility of DoS’ing ourselves by generating an infinite serie of wrappers. To see this better here’s an example of when this happens in a C piece:
   

   sighandler_t *original_handler;         /* Function pointer */
   ...
   /* Let's setup a handler for SIGUSR1 */
   original_handler = signal(SIGUSR1, &my_sigusr1_handler);
                                           /* External function is being returned,
                                              it is wrapped in an ABI translator,
                                              so that we can safely call it (but
                                              we don't in this example).  */
   ...
   /* Let's restore the original handler */
   signal(SIGUSR1, original_handler);      /* The wrapped external function is
                                              being passed as parameter, normally
                                              it would be wrapped again so that the
                                              callee can safely call it.  But
                                              instead we "unwrap" it and we get the
                                              same effect.  */

The bottom line in 1. is that if we decide to do ABI translation from ABI X to Y, we also have to translate from Y to X occasionally, so they are tied together, and we have to be able to do both things dynamically. In 2. the bottom line is that we need to cache pointers to untranslated functions also. If we add to this the fact that pointers can point to functions which also have function pointers as parameters or return types (see man xdr_union(3)), and that struct or array elements can be function pointers too, and that there can be a variable number of parameters of unknown types, we get a pretty complex task.

There’s another case of functions like dlsym() that return a-void-pointer-but-we-know-it’s-a-lie, for which we need a totally custom translator, but this is more easily doable.