Escalation

The answer was in the stars. For some reason, Earthlings had founded universities, and those universities had supported thousands of astronomers for hundreds of years. They refined their techniques over the centuries, collecting databases of statistics on distant stars which no human could ever visit.

And then a grad student in cryptography had gotten fed up with her adviser and switched to astronomy. To familiarize herself with the star database, Li had fed the coordinates of all the known stars in the galaxy into a PRNG test suite used to assess the predictability of cryptographic random number generators.

She hadn't been surprised when the database failed the test; stars aren't randomly distributed, and as they later found, at least 7 different astronomical techniques had also added artificial patterns to the database. However, Li thought it amusing when the test suite claimed the values were generated by a Linear Feedback Shift Register, the simplistic random number generator included in most programming libraries. It had even helpfully produced the LFSR parameters which, with a few lines of code, would generate a sequence of numbers that the test suite thought were somehow related to the database values.

Li had shown it to her advisor, and over a few months they had toyed with the results at odd hours, musing on a publication about systemic errors in sky survey techniques, or perhaps uncovering evidence of fabrication by some unscrupulous astronomer. When Li's model started predicting locations of stars before they were discovered, they worked full time on it for 18 months before telling another soul: surely it would be seen as plagiarism, not prediction.

But in the end, the systemic errors were identified and eliminated, and Li was confirmed to have made the greatest scientific discovery in all of history: the universe they lived in was incontrovertibly a simulation. And moreover, whatever Gods had placed the stars in their galaxies had been lazy in their choice of random number generators, just as human programmers are. (This did create a certain smugness among the kind of cryptographers who used cryptograpic-strength PRNGs to shuffle music playlists.)

As news-show pundits spouted absurdities and mankind came to grips with the hand of God, scientists in all fields now knew what to look for, and found bugs aplenty.

And as the fabric of the universe resolved under our microscopes, it was the cryptographers once again who made a profoundly disturbing hypothesis. The universe was made of bits, and manipulated by algorithms. Far more bits than our computers had, and running algorithms more complex than mankind had ever managed. But we knew there were bugs. What if some of those bugs were also security holes?

Teenagers had been exploiting complex systems for years. A carefully crafted string of a few hundred unexpected characters could cause a buggy subroutine to turn a user into an administrator. Or, if the string was slightly off, crash the server. This was normally no concern to the budding hackers. But then, they usually weren't hacking their own life support.

When the politicians finally understood, the strictest laws were passed. But studying really isn't much different than hacking, and eventually we learned all about our host machine. And several of the shortcomings of our universe started looking tantalizingly exploitable.

Ubuntu Lucid running alongside android on my phone

At first I thought running ubuntu on my phone would require blowing away the android OS, but that's not the case. Instead, an ubuntu filesystem gets mounted on the SD card, with all the system files set up right so that things like apt-get work. Some things don't work, I think because the android kernel isn't quite what the ubuntu apps expect, but you know you're doing well when firefox runs!

The nexusonehacks Ubuntu disk image worked great for me, but took forever to download and had a ton of stuff that I didn't need, like firefox and openoffice.org.

So I stripped it down to bare bones and upgraded it to lucid. Check it out: run a bare-bones Ubuntu Lucid filesystem alongside android on a froyo phone.

Native vim for android

Update: The vim binary has moved to the downloads page.

Update: Created a code.google.com project to keep stuff like this. Also, I got color syntax hilighting to work. See the README.txt in the vim/ directory of the repository.

Tonight I managed to compile vim to run natively on my android phone! My phone is rooted and running cyanogenmod CM6 rc3. Rooting is necessary to run vim, but cyanogen probably isn't necessary.

First I had to compile ncurses using the ndk. Follow that link and compile ncurses the way I did if you want to have any hope of compiling vim using these instructions.

Once I had ncurses built, I had to make just a few changes to vim to get it to work.

I downloaded vim from the mercurial archive, which as of today is pretty much the same as the 7.3 release, I think. I figured out how to call configure by trial and error:

vim_cv_memcpy_handles_overlap=no \
vim_cv_bcopy_handles_overlap=no \
vim_cv_memmove_handles_overlap=no \
vim_cv_stat_ignores_slash=no \
vim_cv_getcwd_broken=no \
vim_cv_tty_group=world \
vim_cv_terminfo=yes \
LDFLAGS="-L/path/to/ncurses-5.7/lib" \
CFLAGS="-I/path/to/ncurses-5.7/lib" \
vim_cv_toupper_broken=no \
CC=agcc.pl \
./configure --host=arm-eabi --with-tlib=ncurses

I got this error message: "could not compile program using uint32_t", and manually patched the configure script because I couldn't remember how to regenerate the script from the configure.in:

$as_echo_n "checking uint32_t is 32 bits... " >&6; }
if test "$cross_compiling" = yes; then :
  true
#  as_fn_error "could not compile program using uint32_t." "$LINENO" 5
else

I also got an "undefined reference to sysinfo" error due to an android bug that omitted the sysinfo() call. So I commented out the HAVE_SYSINFO and HAVE_SYSINFO_MEM_UNIT lines in src/auto/config.h.

I think that was it! Once it finished compiling, I copied over the runtime/ directory and the src/vim binary to /data/vim on my phone. I did an "export VIMRUNTIME=/data/vim/runtime", and vim worked great!

Once I got my VIMRUNTIME set, I was able to ":syntax on", although I'm not getting any color. But otherwise it seems to work great!

You can find a tarball of vim for android on the Downloads page: look for vim-7.3-android-binary.tar.gz. There's also a tarred-up copy of my build directory, although I'm not sure why anyone would want that.

Compile ncurses for android

Update: The tarball of my ncurses build directory has moved to the downloads page.  (Also, agcc -> agcc.pl thanks to Interarticle)

I got the crazy notion to try to compile a native vim binary for android, and one of its dependencies is libncurses.

Make sure you have the ndk installed and working.

You'll need the agcc wrapper, a perl script that creates appropriate command line arguments for arm-eabi-gcc. I learned today that the order of arguments to gcc can be quite significant while linking. I kept getting errors about the "__aeabi_unwind_cpp_pr0" symbol and common functions like printf not being found when it tried to link.

So I hacked Vlad's hacked agcc to make sure that libgcc.a and libc.a get put at the end of the command line, which seems to be necessary for static linking. Here's my hacked version of Vlad's agcc.

Make sure both agcc and arm-eabi-gcc are in your path.

Download ncurses-5.7.tar.gz.

Run configure:

CC=agcc.pl ./configure --host=arm-eabi --without-cxx-binding

When I tried to build, I got errors saying "'struct lconv' has no member named 'decimal_point'"", because android has a broken locale implementation.

So I commented out the HAVE_LOCALE_H line from include/ncurses_cfg.h. (Is there a better way to force configure to set a value like that during the ./configure process?)

It might be possible to build ncurses with the C++ binding, but I didn't try.

Once I had all that fixed, the make ran just fine, and I ended up with lib/libncurses.a.

Extract boot.img from an android phone

(I did this on my rooted, boot-unlocked nexus one (HTC Passion) running cyanogen cm6. Cyanogen is probably not necessary, but boot-unlocking and rooting are).

This tutorial pointed me in the right direction.

I did:

$ adb pull /dev/mtd/mtd2 boot.img-from-phone

Then put it right back using:

$ adb reboot bootloader
[wait for bootloader to come up]
$ sudo ./fastboot flash boot boot.img-from-phone
$ sudo ./fastboot reboot

I could have also taken it apart and replaced the kernel with my own.

Nexus One (HTC Passion): compile and flash a kernel

Update 2: my camera doesn't work with the custom kernel. no idea why. Also, I figured out how to extract the boot.img from the phone directly.

Update: mention how to update the bcm4329.ko wifi driver so that wifi will work again.

This page will tell you how to download and compile the android kernel, and try it out on your phone temporarily (without writing it to flash) using "fastboot boot zImage".

Assuming that worked, here's how to actually write the kernel to the phone's flash.

By this point you should already have fastboot. You'll also need a phone with an unlocked bootloader and probably rooted as well.

You'll also need the boot.img from your phone. It seems to be possible to pull it off a working phone, but I didn't try that. I'm running cyanogen 6, and the boot.img was in the update-cm-6.0.0-N1-RC3-signed.zip.

Next you need to unpack it using the split_bootimg perl script which I found in this tutorial.

That produced output like this:

$ ./split_bootimg.pl boot.img
Page size: 2048 (0x00000800)
Kernel size: 2206592 (0x0021ab80)
Ramdisk size: 167182 (0x00028d0e)
Second size: 0 (0x00000000)
Board name: 
Command line: no_console_suspend=1 msmsdcc_sdioirq=1 wire.search_count=5
Writing boot.img-kernel ... complete.
Writing boot.img-ramdisk.gz ... complete.

Next, you need mkbootimg. Supposedly you can use "fastboot flash:raw" to avoid this, but it didn't work for me. mkbootimg comes with the (multi-gigabyte) android sources, so I ended up downloading a pre-compiled mkbootimg binary, which made me feel dirty, but saved me many hours of downloading and compiling.

Constructing the right command line for mkbootimg was a pain, but eventually I was able to build a my-boot.img identical to the original:

./mkbootimg --kernel boot.img-kernel --ramdisk boot.img-ramdisk.gz -o my-boot.img --cmdline 'no_console_suspend=1 msmsdcc_sdioirq=1 wire.search_count=5' --base 0x20000000

The boot.img-kernel and boot.img-ramdisk.gz came from split_bootimg, as did the --cmdline string. The "--base 0x20000000" is specific to the N1 (aka nexus one aka HTC passion).

Once you get the boot.img constructed properly, reboot into the bootloader by holding down the trackball while you boot (or use "adb reboot-bootloader"). Then:

$ sudo ./fastboot flash boot my-boot.img
$ sudo ./fastboot reboot

If you get it wrong, your phone will hang at the screen with the unlocked padlock forever. Pull the battery to cold boot and reboot into the bootloader again.

(Nexus One / HTC Passion): If that worked, you may find that "wifi" under Settings... on the phone just says "error". That's because the bcm4329.ko kernel module doesn't match the kernel version.

Here's the bcm4329.ko that matches this 2.6.32 kernel (which has the serial port enabled).

The kernel module lives in /system/lib/modules/. The /system filesystem was mounted read-only on my phone, so from the root shell on my phone (adb shell) I remounted it read-write and then backed up the original kernel module, so that I can switch back to the old kernel if I need to:

# mount -oremount,rw /system
# cp /system/lib/modules/bcm4329.ko /sdcard/bcm4329.ko-orig

Then I copied over the file with "adb push bcm4329.ko /system/lib/modules/", then remounted /system back to read-only:

# mount -oremount,ro /system

It started working immediately.

Giving native Android C apps access to the Android API through SL4A

UPDATE: this is slightly more mature now. Check out http://code.google.com/p/android-cruft/wiki/SL4AC

Today I played around with the Android NDK, a C compiler for Android. The Android folks make it very clear that it's only intended for making ordinary Java-based Android apps faster, by running a few selected functions down at the bare metal.

So it only comes with a few basic libraries which don't support things like reading the sensors and taking photos.

Enter SL4A, Scripting Languages for Android (formerly "ASE", the Android Scripting Environment). SL4A is a neat Android app that makes it very easy to write simple Android apps in many popular scripting languages like Python, Perl, Ruby and TCL. SL4A exposes a useful subset of the Android API in a clever way: by setting up a JSON RPC server. That way, each language only needs to implement a thin RPC client layer to access the whole SL4A API.

So today I managed to get the excellent Jansson C-language JSON library to compile with the NDK, making it possible for native C apps to access the Android API through SL4A, just as its normally supported languages can.

It works just fine as either a native Android binary or from a host machine, so you could also use it to control your phone from a C program running on a host computer.

Here's the ndk-to-sl4a.c source code, public domain. See the comments in the header for instructions on how to compile and run it.

If you're the trusting sort, you can also download a binary for froyo or for (ubuntu/lucid) linux. But you should still go through the comments in the source file to see how to set up SL4A first.

Native android C program using ndk

Big update: I updated agcc.pl to work with the latest NDK release, and called it agcc2.pl. Here is the new blog post.

Update: link to agcc.pl works now. Update 2: link to agcc.pl *actually* works now?

The Android NDK isn't really intended to write standalone binaries, but this tutorial got me most of the way there. But some path changes in android-ndk-r4b broke the agcc wrapper, so I had to modify it to point to the right includes and libraries.

Here's what should be a complete HOWTO for linux. It probably requires a rooted phone at the least, in order to upload and run arbitrary binaries. I'm running a pre-release of cyanogenmod CM6.

1. Download and unpack android-sdk_r06-linux_x86.tgz and android-ndk-r4b-linux-x86.zip.

2. Add android-ndk-r4b/build/prebuilt/linux-x86/arm-eabi-4.4.0/bin and android-sdk-linux_86/tools/ to your PATH. (cd into each of those directories and then run "export PATH=$PATH:`pwd`")

3. Plug your phone in via USB and run "sudo adb start-server" to start the daemon in the background (as root so that it can access the USB device. If you accidentally start the daemon as yourself and can't talk to your phone, run "adb kill-server" to kill it, then "sudo adb start-server" to restart it as root.)

4. Make sure you can run "adb" (from the SDK) and "arm-eabi-gcc" (from the NDK) so that you know your PATH is set up right.

5. Grab my copy of the agcc wrapper hacked for android-ndk-r4b. "chmod 755" it so you can run it.

6. Create the "hello, world" .c file:

#include <stdio.h>

int main() {
  printf("Hello, world!\n");
}

7. Ready to compile! "$ agcc.pl -o hello hello.c"

8. Copy the binary to /data: "adb push hello /data/"

9. Run it! I did that by SSHing into the phone, but you can also just "adb shell".

# cd /data
# ./hello
Hello, world!

Simple kalman filter example

There are a ton of Kalman filter overviews online, and lots of them give a general overview of what they do, but then they all hit a wall of variables and matrices, and fail to give good simple examples.

The best guide I found is a PDF scan of a much-faxed copy of Roger M. du Plessis' 1967 classic "Poor Man's Explanation of Kalman Filtering".

His paper is great because he starts with a single-variable filter (no matrices!) with no control component and no prediction algorithm. I'm going to try to give an even simpler example with softer terminology and more hand-waving.

Kalman filters are a way to take a bunch of noisy measurements of something, and perhaps also some predictions of how that something is changing, and maybe even some forces we're applying to that something, and to efficiently compute an accurate estimate of that something's true value.

Let's say we want to measure the temperature in a room. We think it's about 72 degrees, plus or minus 2 degrees. And we have a thermometer that gives uniformly random results within a range of +/-5 degrees of the true temperature.

We take a measurement with the thermometer and it reads 75. So what's our best estimate of the true temperature? Kalman filters use a weighted average to pick a point somewhere between our 72 degree guess and the 75 degree measurement. If the weight is large (approaching 1.0), we mostly trust our thermometer. If the weight is small, we mostly trust our guess and ignore the thermometer.

Here's how we choose the optimal weight, given the accuracy of our guess and the accuracy of the thermometer:

weight = temperature_variance / (temperature_variance + thermometer_variance)
0.29 = 2 / (2+5)

If temperature_variance were very large compared to thermometer_variance, weight would approach 1.0. That is, we'd ignore our guess and just use the measured value. Likewise, if thermometer_variance dominated, the weight would approach 0, and we'd put very little trust in our thermometer readings.

29% weight means we'll trust our guess more than the thermometer, which makes sense, because we think our guess is good to +/-2 degrees, whereas the thermometer was only good to +/-5.

Now we do the weighted average:

estimate = guess + weight*(measurement - guess)
72.87 = 72 + 0.29*(75-72)

or equivalently

estimate = (1-weight)*guess + weight*measurement
72.87 = 0.71*72 + 0.29*75

That is, we went 29% of the way from 72 to 75, or equivalently, we took 71% of the guess plus 29% of the measurement.

There's one last thing to compute: how confident we are in our estimate of 72.87 degrees. That equation is:

                      temperature_variance*thermometer_variance 
estimate_variance =   -----------------------------------------
                    (temperature_variance + thermometer_variance)

1.43 = 2*5 / (2+5)

So we think our estimate is correct to +/-1.43 degrees.

Now we have a guess that the temperature in the room is 72.87 degrees, +/-1.43 degrees. And we still have a thermometer that tells the temperature +/-5 degrees.

That's basically the situation where we started, so we can run the whole algorithm again:

First we compute the weight, using our new, more accurate guess confidence:

weight = temperature_variance / (temperature_variance + thermometer_variance)
0.22 = 1.43 / (1.43+5)

We take a measurement, and this time let's say it comes up as 71 degrees.

Now we can compute the weighted average of our old guess and our new measurement:

estimate = guess + weight*(measurement - guess)
72.46 = 72.87 + 0.22*(71-72.87)

And the new confidence level:

                      temperature_variance*thermometer_variance 
estimate_variance =   -----------------------------------------
                    (temperature_variance + thermometer_variance)

1.11 = 1.43*5 / (1.43+5)

So after the second measurement, we estimate that the actual temperature is 72.46 degrees, +/-1.11 degrees.

Kalman filters are nice because we don't have to remember the whole history of measurements and estimates. We just keep track of our most recent estimate and our confidence level in that estimate.

If we decide to turn on the air conditioner, so that the temperature in the room starts decreasing, we can expand our calculations to include that "control" variable, and use it to update our estimates by "predicting" how much colder it'll be at each measurement. Once I figure out how to do that, maybe I'll post a more complicated example :)