Saturday, May 14, 2011

Loading and executing a binary on Android

While attempting to get the hidd running on Android, I noticed that this is not easy to to. There are some barriers in place to prevent something like this:
  • The SD Card is mounted noexec
  • The System memory is read-only (NAND in my case)
  • Apps cannot write outside their folder (except for SD card)
The first thing you need to do is to get the executable onto the device. This can be done by placing the executable in the "raw" folder, which packages the file as a binary resource. Once your app starts, you can then open the binary resource for reading, and write it into the filesystem:
private void CopyRawToFile(int resourceId, String filename) throws IOException {
InputStream input = m_context.getResources().openRawResource(resourceId);
OutputStream output = m_context.openFileOutput(filename, Context.MODE_PRIVATE);

byte[] buffer = new byte[1024 * 4];
int a;
while((a = input.read(buffer)) > 0)
output.write(buffer, 0, a);

input.close();
output.close();
}
Once the file is loaded you can then make it executable by invoking chmod:
private String MakeExecutable(String filename) {
//First get the absolute path to the file
File folder = m_context.getFilesDir();

String filefolder = folder.getCanonicalPath();
if (!filefolder.endsWith("/"))
filefolder += "/";

String fullpath = filefolder + filename;

Runtime.getRuntime().exec("chmod 770 " + fullpath).waitForExit();

return fullpath;
}


After this, you should be able to execute the binary the same way you would with any system binary. Hopefully this will save you some time avoiding the painful JNI wrapper approach.

This does not compromise the security of the Android OS. Because the binary is executed as the app user, and thus has the same restrictions as the app itself. In other words, this does not allow you to execute operations with root privileges on a non-rooted device.

Friday, March 4, 2011

Unexpected rounding errors with the C# compiler

I've recently discovered a small problem in the C# compiler that can cause unexpected precision loss when working with floating point numbers. The basic function looks like this:
double sum(double[] elements)
{
double sum = 0;
foreach(float f in elements)
sum += f;
return sum;
}

The problem is that the loop variable f is of type float rather than type double. The reason that this is a problem is that I expect the foreach statement to be semantically equivalent to a standard for loop when used on an array. In other words, it should do the same as this code:
double sum(double[] elements)
{
double sum = 0;
for(int i = 0; i < elements.Length; i++)
{
float f = elements[i];
sum += f;
}
return sum;
}


If you try to compile the above code, the compiler will give the error:
Cannot implicitly convert type 'double' to 'float'. An explicit conversion exists (are you missing a cast?).
This error is indeed correct, as the conversion from the array element to the loop variable f will cause a loss of precision.

You could argue that the assignment is redundant and that the sum variable could be updated without assigning anything to the loop variable. But inspecting the the CIL output of the compilation reveals that it does indeed convert it to single precision before using the variable (line 11+12, label L_0016 + L_0017):

0 L_0000: nop
1 L_0001: ldc.r8 0
2 L_000a: stloc.0
3 L_000b: nop
4 L_000c: ldarg.0
5 L_000d: stloc.3
6 L_000e: ldc.i4.0
7 L_000f: stloc.s V_4
8 L_0011: br.s 23 -> ldloc.s V_4
9 L_0013: ldloc.3
10 L_0014: ldloc.s V_4
11 L_0016: ldelem.r8
12 L_0017: conv.r4

13 L_0018: stloc.1
14 L_0019: ldloc.0
15 L_001a: ldloc.1
16 L_001b: conv.r8
17 L_001c: add
18 L_001d: stloc.0
19 L_001e: ldloc.s V_4
20 L_0020: ldc.i4.1
21 L_0021: add
22 L_0022: stloc.s V_4
23 L_0024: ldloc.s V_4
24 L_0026: ldloc.3
25 L_0027: ldlen
26 L_0028: conv.i4
27 L_0029: clt
28 L_002b: stloc.s V_5
29 L_002d: ldloc.s V_5
30 L_002f: brtrue.s 9 -> ldloc.3
31 L_0031: ldloc.0
32 L_0032: stloc.2
33 L_0033: br.s 34 -> ldloc.2
34 L_0035: ldloc.2
35 L_0036: ret


The explanation for this is that I have a common misconception about what the foreach loop does, as it actually inserts typecasts as well, meaning that the foreach loop gets expanded to:
double sum(double[] elements)
{
double sum = 0;
for(int i = 0; i < elements.Length; i++)
{
float f = (float)elements[i];
sum += f;
}
return sum;
}


Which explains the conversion and the lack of compile time errors. This does allow some more flexibility in the type system, but it also allows you to do completely unsafe things, such as declare the input type as object[] elements and the program will compile anyway. This is probably an issue that made the use of ArrayList more bearable back when generics were not yet implemented, so it seemed like a good idea at the time.

For me, this means that the compact notation that is given by foreach is now trumped by its drawbacks. The only remedy for now seems to be to use the var keyword in all foreach loops to ensure that the automatic type conversion is removed. Unfortunately this solution is only available for C# 3.0 and newer.

Friday, February 25, 2011

Floating point rounding errors visualized

If you have been working with computer programming, you should have heard about floating point rounding errors. If not, you should read up on it, but I will give a short recap here.
Since a computer can only work with a finite range of values, there will be a limit to the kind of numbers that it can represent. If you are working with integers, you probably know the limits: 16bit = 65535, 32bit = 2147483647 * 2.


Now what if you want to work with real numbers, i.e. numbers that have decimals? You could represent all numbers, say divided by ten, that would give you two decimal places and is called fixed (decimal) point. But what if you need four digit precision? Then you are limited to values smaller than 200000 for 32bit. To solve this, computers use floating point numbers. Floating point numbers are represented with a mantissa (e.g. 1.5) and an exponent (e.g. 6), such as 1.5 * 10^6 = 1500000. This enables floating point number to represent very large numbers and very small numbers, at the cost of precision. Large numbers have less precision that small numbers, which is acceptable for most problems.


The problem with floating point numbers, is that rounding errors occurs when a computer performs calculations based on these numbers. Because a floating point number carries a slight imprecision, this imprecision accumulates with each calculation. To visualize what happens, I have produced a small animated GIF that shows the rotation of a rectangle. There are two rectangles, a red and a green one. The green rectangle is rotated with an angle that is calculated based on the time passed, where the red one is rotated with an angle that is gradually incremented. If there were no floating point rounding errors, the two would always be on top of each other.




After around 600000 operations, the rounding errors start to mean a difference of a whole degree and the drift between the two rectangles starts to appear. After this it just gets worse and worse.

If this was a real world scenario, e.g. an animation, it would appear to look fine, but after a while it would start to run out of sync with other animations.

If this was for a physics or chemistry simulation, it would produce correct results for short test samples, but incorrect results for long simulations. And if this was for a finance application, e.g. stock trading .... ouch!

And this demonstration only accumulates errors by addition, if you use multiplication it just explodes (well multiplies actually). The only way to avoid this is either to not use floating point operations or ensure that the values are not accumulated.

Friday, January 28, 2011

Zeemote controller on Android

This blog post is about Bluez IME for Android.

I have recently purchased a Zeemote JS 1 controller from Amazon. I wanted to use it with my HTC Desire phone, which is running Android 2.2.

Unfortunately the Zeemote came with no drivers, probably because it was priced at £3 and was shipped in a bubble wrap envelope :). This was a bit weird, because the Zeemote website claims that Android 1.6 to 2.0+.

Looking at the Android market, I could find two drivers. One was called something like Zeemote JS1, and did not work on the HTC Desire (it appears to have been removed). The other is called GamePro, and did work, but costs $10, which is more than twice the price of the controller itself. Besides, the whole purchase seems a bit dodgy with only a forum for a webpage. I also believe that this is not allowed due to Android Market publisher agreements 3.3.

So I set out figuring out how to implement a working Zeemote driver. First block in the road is that Android prevents emulated hardware keypresses for security reasons. This can be handled by creating a custom Input Method Editor (IME), which can then send key press events.

Next block was that I got no manual of any kind, so I could only pair with the device. Fortunately, there was a post here that explained how to connect to the Zeemote with Android Bluetooth, and it works for HTC Desire.

Upon connection, the device starts dumping some data, probably describing the device and its capabilities. After this, there is no communication until you activate the device. By looking at the transmitted data, I was able to guess the format. Doing this took about 3 hours, plus 2 hours for implementing the IME, so a total of 5 hours for getting a working Zeemote driver.

I then figured that others would probably have the same issues as I did, so I spent a few more hours, creating a settings interface.

I have also purchased a Bluetooth keyboard, which I am hoping to get working under the same framework, but no luck so far. The code is flexible enough to allow other devices to be supported.

Then I realized that if you search Android Market for Zeemote, most of the results are games claiming to support Zeemote. This seems to indicate that a lot of people have been through the same ordeal as me, and likely have to update their app to support whatever changes there are.

I then spent a few more hours isolating the core of the application as a service. The cool thing about this is that other apps can freely activate the service, and register for events. In effect, any app can support Zeemote just by invoking the service (provided that it is installed), and all updates can be done within the driver itself.

I have packaged the app up and published it on Android Market for free, just search for Bluez IME.

As always, I have released the source under LGPL. If you are interested in the source code, visit the android-bluez-ime site. You can also download the package from there but I recommend using Market if possible, as that will ensure that you are automatically updated.

On the android-bluez-ime site, you can also see the source code for a test application that uses the Bluez IME service. Note that the test application does not require Bluetooth permissions, as that is handled by the driver.

If you have questions or comments related to Bluez IME, please create an issue on the website.

Friday, January 14, 2011

How to not match a string with regular expressions

Regular expressions are a robust method for matching strings, and finding patterns in text. But it takes some time to learn, for instance, consider extracting all strings in quotations from this text:
a "sample" text "fragment".

The initial attempt is something like this:
".*"

But since regular expressions use greedy matching, it will match:
"sample" text "fragment"

The fix for this would be to change any character (.) to match any character except " ([^"]):
"[^"]*"

And this solution works, but what if the delimiter is a string and not just a single character? For example:
a <!--sample--> text <!--fragment-->.

You cannot use any character except, you need a any character except one that is followed by, and this is called negative lookahead.

To match any character except one that is followed by --> you can use the following expression:
(.(?!-->))*

Applying this on the sample text matches all text except the e and t in sample and fragment respectively. If we want the entire inner text matched, we need to add the excluded character:
(.(?!-->))*.

This will match the entire text, so now we can apply the delimiters:
<!--(.(?!-->))*.-->

Derek Slager has an online regular expression tester.

Monday, January 10, 2011

TortoiseSVN for Linux

I'm usually working cross-platform, and there are a few killer-apps that I am missing on Linux. One of the most annoying things were the absence of a TortoiseSVN like application.

If you have never heard of TortoiseSVN, it is an application that integrates into the windows explorer and shows overlays that indicate the SVN state of files. Compared to other SVN applications, this gives a really great overview of the current state. It is very fast to identify which files and folders that contains changes.

It also contains a number of context menus, so you can easily view the changes, revert them and so on.

On Linux I have used the commandline SVN tools, but it gives no overview. For instance, you cannot easily see which files that are not added to SVN. And just executing "svn add" will possibly add a number of files you do not want, and you have to revert it and so on.

There are some standalone apps, such as PySVN Workbench and RapidSVN which I have found quite a few bugs in. But even if those bugs were fixed, it is not integrated with the shell, and will always miss some option, eg. thumbnail view, permissions, copy actions, etc., and will never feel like an integrated part of the system.

But last week I discovered RabbitVCS (previously named NautiliusSVN). It does pretty much the same as TortoiseSVN, and places emblems on files and folders in Nautilus. There are some RabbitVCS screenshots here.

I have not used it extensively yet, so I am not sure how stable it is, but it looks REALLY promising. The RabbitVCS about page is a but outdated and states that only SVN and Nautilus are supported.

Unlike TortoiseSVN, there is a actually support for multiple VCS in the application, and I can confirm that it works just as well with Git, making it a replacement for TortoiseGit as well.

Looking at the code it seems that thunar is supported as well.

Monday, January 3, 2011

Java Grievances part 3

The previous Java posts were about the library, this post is about Java classes missing properties. This means that you have to write code like this in Java:
float adjustX = 0.5;
for(int i = 0; i < some_object.getRectangle().getPoints().size(); i++)
some_object.getRectangle().getPoints().get(i).setX(
some_object.getRectangle().getPoints().get(i).getX() +
adjustX
);
Where properties can make the same code much more readable:
float adjustX = 0.5;
for(int i = 0; i < some_object.Rectangle.Points.Size; i++)
some_object.Rectangle.Points[i].X += adjustX;

This can actually be implemented without changing the Java bytecode, simply by adopting a standard syntax, eg.:
public property X {
float getX() { return m_x; }
void setX(float value) { m_x = value; }
}

The compiler is then free to emit code without the property part. This will make this feature just as useless as generics currently are, unless the compiler also assumes that the common getX/setX function pairs can be used as a property. This means that all those old libraries will suddenly appear to have properties when they have not.

Such a syntactic sugar model doesn't break anything, not even reflection, as the methods are there just as they should be.

This is in fact how they are implemented in C#/VB and others, and allows interoperability with languages that have no property features. Unfortunately some people confuse properties with instance variables, which they are not. Properties are NOT a way to get out of proper class encapsulation. Properties are also more expensive than variables as they can validate the input/output, cause events etc. so you would still need both.