TLDR: DEFLATE decompressor in 3K of RAM

For a Pebble app I've been writing, I need to send images from the phone to the watch and cache them in persistent storage on the watch. Since the persistent storage is very limited (and the Bluetooth connection is relatively slow) I need these to be as small as possible, and so my original plan was to use the PNG format and gbitmap_create_from_png_data(). However, I discovered that this function is not supported on the earlier firmware used by the Pebble Classic. Since PNGs are essentially DEFLATE compressed bitmaps, my next approach was to manually compress the bitmap data. This meant that I needed a decompressor implementation ("inflater") on the watch.

The constraint

The major constraint for Pebble watchapps is memory. On Pebble Classic apps have 24K of RAM available for the compiled code (.text), global and static variables (.data and .bss) and heap (malloc()). There is an additional 2K for the stack (local variables). The decompressor implementation needed to have both small code size and variable usage. I discovered tinf which seemed to fit the bill, and tried to get it working.

Initially, trying to decompress something simply crashed the app. It took some debug prints to determine that code in tinf_uncompress() wasn't even being executed, and I realised that it was exceeding the 2K stack limit. I changed the TINF_DATA struct to be allocated on the heap to get past this. At this stage it was using 1.2K of .text, 1.4K of .bss, 1K of stack, and 1.2K of heap (total 4.8K). I set about optimising the implementation for memory usage.

Huffman trees

Huffman coding is a method to represent frequently used symbols with fewer bits. It uses a tree (otherwise referred to as a dictionary) to convert symbols to bits and vice versa. DEFLATE can use Huffman coding in two modes: dynamic and fixed. In dynamic mode, the compressor constructs an optimal tree based on the data being compressed. This results in the smallest representation of the actual input data; however, it has to include the computed tree in the output in order for a decompressor to know how to decode the data. In some cases the space used to serialise the tree negates the improvement in the input representation. In this case the compressor can used fixed mode, where it uses a static tree defined by the DEFLATE spec. Since the decompressor knows what this static tree is, it doesn't need to be serialised in the output.

The original tinf implementation builds this fixed tree in tinf_init() and caches it in global variables. Whenever it encounters a block using the fixed tree it has the tree immediately available. This makes sense when you have memory to spare, but in this case we can make another tradeoff. Instead we can store the fixed tree in the same space used for the dynamic tree, and rebuild it every time it is needed. This saves 1.2K of .bss at the expense of some additional CPU usage.

The dynamic trees are themselves serialised using Huffman encoding (yo dawg). tinf_decode_trees() needs to first build the code tree used to deserialise the dynamic tree, which the original implementation loads into a local variable on the stack. There is an intermediate step between the code tree and dynamic tree however (the bit length array), and so we can borrow the space for the dynamic instead of using a new local variable. This saves 0.6K of stack.

The result

With the stack saving I was able to move the heap allocation back to the stack. (Since the stack memory can't be used for anything else it's kind of free because it allows the non-stack memory to be used for something else.) The end result is 1.2K of .text, 0.2K of .bss and 1.6K of stack (total 3.0K), with only 1.4K counting against the 24K limit. That stack usage is pretty tight though (trying to use app_log() inside tinf causes a crash) and is going to depend on the caller using limited stack. My modified implementation will allocate 1.2K on the heap by default, unless you define TINF_NO_MALLOC. Using zlib or gzip adds 0.4K of .text. You can find the code on bitbucket.

I recently bought a Raspberry Pi, which is a credit card sized computer with an ARM processor. I'm using it as my TV frontend, running Raspbian and XBMC. I'm building my own packages for XBMC since it requires the latest development version.

I initially installed my Pi with the foundation image, but found that it included a lot of packages which I didn't need. Since I have a slight obsession about doing things as efficiently as possible, I decided to build my own image with XBMC from scratch.

I implemented a script in Bash, mkraspbianxbmc.sh which does this. It uses debootstrap to install a minimal Raspbian system in a chroot. It then installs XBMC and a couple extra packages, and does some necessary configuration. Finally it creates an image file with the necessary partitions, creates the filesystems, and copies the installation into the image file. The resultant image fits onto a 1GiB SD card. You can download a pre-built image from this page.

The script can be modified to build images with different packages, or even a very minimal image which fits onto a 512MiB SD card.

Extracting specific track segments from a track

I have an i-Blue 747A+ GPS logger which I use to track my runs (amongst other things). Afterwards I use BT747 to retrieve the data from the device and create a GPX file of the run, which I then upload to Endomondo which gives me nice graphs and statistics.

I need to modify the GPX file slightly before I can do so however: I use the button on the device to mark the beginning and end of the run, which appear as waypoints in the GPX file. BT747 creates separate track segments (within a single track) between each waypoint, but Endomondo ignores these. I therefore need to extract the single track segment covering the actual run and create a new GPX file with just that segment. I therefore wrote a script in Python, splittrack.py, to do this. It uses the gpxdata library to parse the input file, locates any track segment which match a set of time, distance, displacement and speed criteria¹, and outputs a new GPX file with just those.

% splittrack.py mgorven-20121015_0109.gpx > run-20121014.gpx
Reading mgorven-20121015_0109.gpx
<TrackSegment (23 points)> covers 21m over 0:00:22 at 1.0m/s average speed with 4m displacement
<TrackSegment (904 points)> covers 3018m over 0:15:03 at 3.3m/s average speed with 8m displacement
Adding <TrackSegment (904 points)>
<TrackSegment (4 points)> covers 3m over 0:00:03 at 1.3m/s average speed with 3m displacement

Integrating heart rate data

I then recently bought an Oregon Scientific WM100 heart rate logger. It listens to the broadcasts from a heart rate strap² and records the measurements every 2 seconds. I retrieve the data using the wm100 driver for Linux which writes a CSV file like this:

Name,2012-10-14T18:08:27
Description,
Date,10/14/2012
Time,18:08:27
SamplingRate,2
HeartRate
,80
,78
,76
,75

In order to get this data into Endomondo, I needed to combine the GPS trace with the HRM data into a single file format which Endomondo accepts. I initially started implementing a library for the TCX format³, but then discovered that there is a GPX extension for including heart rata data which Endomondo accepts. So I wrote a script in Python, wm100gpx.py, which reads the input GPX and CSV files, merges the heart rate measurements into the GPX records, and outputs a new GPX file.

% wm100gpx.py 2012-10-14T18:08:27.csv < mgorven-20121015_0109.gpx > run-20121014.gpx

The entries look like this:

<trkpt lat="37.392051" lon="-122.090240">
  <ele>-44.400761</ele>
  <time>2012-10-15T01:20:13Z</time>
  <extensions>
     <gpxtpx:TrackPointExtension>
         <gpxtpx:hr>175</gpxtpx:hr>
     </gpxtpx:TrackPointExtension>
    </extensions>
</trkpt>

I recently got a Raspberry Pi, which is an ARM based device which runs Linux. My goal is to use this as my HTPC running XBMC, so that I can move the fileserver out the lounge.

Edit: I've moved the latest information and updates about these packages to this page.

Building

I installed Raspbian on my RPi, which is basically a rebuild of Debian Wheezy specifically for the RPi (targeting the ARMv6 architecture with hard float). I found various instructions on how to build XBMC for Raspbian, but none of them were in the form of deb packages, and installing software without packages just makes me queezy. So I went off and built it myself.

Since the RPi is relatively low powered, I built the package on my laptop using qemu-user, which emulates binaries with a different architecture. I based the packaging on the XBMC package in Wheezy, and the source is from the xbmc-rbp branch on GitHub. I made the modifications to the source as per this forum post and added an initscript so that it can automatically start at bootup.

Installing

The easiest way to install the package is to add my archive to your system. To do this, store the following in /etc/apt/sources.list.d/mene.list:

deb http://archive.mene.za.net/raspbian wheezy contrib

and then import the archive signing key:

sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-key 5243CDED

You can then install it as you would with any other package, for example, with apt-get:

sudo apt-get install xbmc

(If you don't want to configure my archive you can download the packages manually, but you'll have to deal with all the dependencies. Note that it requires a newer libcec package which is also in my archive.)

The user which you're going to run XBMC as needs to be a member of the following groups:

audio video input dialout plugdev

Running

To run XBMC, run xbmc-standalone from a VT (i.e. not under X). XBMC accesses the display directly and not via Xorg.

If you want XBMC to automatically start when the system boots, edit /etc/default/xbmc and change ENABLED to 1:

ENABLED=1

You also need to set the user which XBMC should run as (the xbmc user is not automatically created at the moment). Run sudo service xbmc start to test this.

Configuration

The following settings in advancedsettings.xml decreases the CPU usage while showing the UI. Disabling the RSS feeds also helps with this.

<advancedsettings>
    <gui>
        <algorithmdirtyregions>3</algorithmdirtyregions>
        <nofliptimeout>0</nofliptimeout>
    </gui>
</advancedsettings>

Rebuilding

If you want to rebuild this package with a different source (e.g. a later Git revision), you need to prepare the source by running ./bootstrap before creating the orig.tar.gz. You obviously need all the build dependencies (which should be listed in the packaging), as well as the VideoCoreIV libraries in /opt. You probably want to set DEB_BUILD_OPTIONS=nocheck parallel=4 to disable the tests (they failed to build for me), and speed up the build by using more than one core. You can find the packaging in my archive or my Bazaar repository.

My wife recently got a Samsung Exhibit II 4G Android phone to replace her aging Nokia E63. Migrating her contacts was accomplished fairly easily by exporting them to CSV with Nokia PC Suite and then importing them into Google Contacts. Migrating SMSes was not so trivial however.

Other approaches

There are a couple methods floating around the web, but none were suitable. This one uses Gammu to retrieve the SMSes from the Nokia, and then a script to convert them to an XML format readable by SMS Backup & Restore. It turns out that Gammu doesn't work on Symbian S60v3 devices however. This script can convert SMSes exported by the MsgExport app to XML for SMS Backup & Restore, but I didn't feel like paying for it or dealing with the Ovi Store. VeryAndroid is a Windows application which can convert SMSes from Nokia PC Suite CSV format and sync them directly to an Android device, and Nokia2AndroidSMS can convert SMSes from the OVI Suite database to XML for SMS Backup & Restore. I didn't want to deal with more Windows software though, so I just decided to write my own.

Formats

I already had the Nokia PC Suite installed and was using it to migrate contacts, so I decided to work with the CSV output it generates for messages. A received SMS looks like this:

sms,deliver,"+16501234567","","","2012.06.13 19:13","","Leaving now"

and a sent SMS looks like this:

sms,submit,"","+16501234567","","2012.06.13 19:11","","Where are you?"

The fields are:

• 0: "sms" for SMSes (MMS is presumably different)
• 1: "deliver" for received messages, "submit" for sent messages
• 2: Sender's phone number (blank for sent messages)
• 3: Recipient's phone number (blank for received messages)
• 5: Date and time in "YYYY.MM.DD HH:MM" format and local timezone
• 7: Message body

Fields 4 and 6 are always empty for SMSes (they are probably used for MMSes, one being the message subject).

I also decided to generate XML for the SMS Backup & Restore app. The XML format looks like this:

<?xml version='1.0' encoding='UTF-8' standalone='yes' ?>
<?xml-stylesheet type="text/xsl" href="sms.xsl"?>
<smses count="1">
  <sms
    protocol="0"
    address="+16501234567"
    date="1341025384351"
    type="1"
    subject="null"
    body="Leaving now"
    toa="null"
    sc_toa="null"
    service_center="+12063130025"
    read="1"
    status="-1"
    locked="0"
    date_sent="null"
    readable_date="Jun 29, 2012 8:03:04 PM"
    contact_name="(Unknown)"
  />
</smses>

but can be reduced down to this:

<?xml version="1.0" encoding="UTF-8"?>
<smses count="1">
    <sms
        protocol="0"
        address="+16501234567"
        date="1341025384351"
        type="1"
        body="Leaving now"
        read="1"
        status="-1"
    />
</smses>

The attributes of the <sms> element are:

• protocol: Always "0" (possibly different for MMS)
• address: Sender or recipient phone number
• date: Date and time in milliseconds since 1 January 1970
• type: "1" for received message, "2" for sent messages
• body: Message body
• read: "1" if the message has been read
• status: Always "-1"

The script

I implemented a script called [nokia2android.py] in [Python] to convert one or more CSV files to this XML format.

./nokia2android.py received.csv sent.csv > android.xml

The XML file can then be transferred to the Android device (using USB or Bluetooth) and stored in /sdcard/SMSBackupRestore. It will then be presented as an option after selecting the Restore button in the app.

Apple trackpads don't have separate buttons, the entire trackpad is itself a clickable button. The default OS X behaviour is to treat clicking the pad with two fingers as the right button, and clicking the pad with three fingers as the middle button. Enabling tap to click (i.e. touching the trackpad but not actually clicking it) tends to result in false positives since the trackpad is so big. I therefore setup this behaviour under Ubuntu Oneiric.

When I upgraded to Ubuntu Precise two finger clicks started registering as the left button. (Three finger clicks still worked.) It turns out that this is due to the new clickpad support in Precise. The solution is to disable the ClickPad attribute. My Synaptics configuration now looks like this:

TapButton1              = 0
TapButton2              = 0
TapButton3              = 0
ClickFinger1            = 1
ClickFinger2            = 3
ClickFinger3            = 2
ClickPad                = 0

I recorded some presentations at work recently using a Canon Vixia HF R21 video camera, and needed to encode the videos to lower resolution. It took me longer to figure this out than I expected, so I thought that I'd document the details.

Input

The camera exposes an MTP interface when plugged in using USB, and the video files are stored under /AVCHD/BDMV/STREAM/. The M2TS container format is used, but the camera splits a single stream into multiple files such that each file is no bigger than 2GiB. These files need to be concatenated together before playing or re-encoding. Video is encoded using H.264 at an anamorphic resolution of 1440x1080 (i.e. it must actually be displayed at 1920x1080). The frames are interlaced at 50.96fps¹. The bitrate can be set at 5, 7, 12, 17 or 24mbps. Audio is encoded using AAC with 2 channels at 48kHz, with a bitrate of 256kbps.

Encoding

The best codecs in terms of storage space efficient seem to be H.264 and AAC, so that's what I chose to encode the output in. I wanted a good quality version at 720p, and a lower quality version at 480p. Since these were presentations, single channel audio is sufficient. I tried using both libav (previously ffmpeg) and mencoder and had trouble with both, but eventually got libav working.

Good quality

The command I used for good quality was:

avconv -i "$INFILE" \
    -acodec libfaac -ab 128k -ac 1 -coder ac \
    -vcodec libx264 -filter yadif -r 29.97 -s 1280x720 -aspect 16:9 \
    "$OUTFILE"

Audio is reduced to mono and encoded in AAC at 128kbps. Video is resized to 1280x720, deinterlaced, and encoded in H.264 with the default quality settings. To adjust the quality one can use the --crf parameter (which defaults to a value of 23). At 30 the quality loss was easily noticeable.

On my Intel Core2 Duo P8600 this encoded at 10fps with a video bitrate of 700kbps and audio bitrate of 83kbps. This puts an hour of video at 339MiB. Adding -threads 2 allows both cores to be used, at the expense of slightly worse motion compensation. If this is too slow, one can select a faster x264 preset using the -pre parameter.

Low quality

The command I used for low quality was:

avconv -i "$INFILE" \
    -acodec libfaac -ab 128k -ac 1 -coder ac \
    -vcodec libx264 -filter yadif,crop=848:480 -r 29.97 -s 854x480 -aspect 53:30 \
    "$OUTFILE"

Audio is encoded the same as above. Video is resized to 848x480, deinterlaced and encoded in H.264. Apparently codecs are more efficient when the resolutions are a multiple of 16 which is why the video is resized to 854 and then reduced to 848.

This encoded at 20fps with a video bitrate of 300kbps and audio bitrate of 83kbps. This puts an hour of video at 165MiB.

After over a year of development, we have finally released Ibid. Ibid is a general purpose chat bot written in Python. We've suffered from a bit of feature creep, so despite being a 0.1 release it can talk 7 messaging protocols and has over 100 features provided by plugins. I think we also have an excellent architecture and very developer friendly plugin API. The 0.1.0 release can be downloaded from Launchpad or installed from our PPA.

SuperGenPass and Password Composer are password generators, which generate different passwords for each site you use based on a single master password. This gives you the convenience of only remembering one password as well as the security of using different (and strong) passwords for each site. This means that you won't have all your accounts compromised when¹ one of them is compromised.

Most password generators are implemented as browser extensions or bookmarklets, since they are most frequently needed in a web browser. I've been wanting to start using a password generator, but I wanted to be sure that I could access my accounts even if I didn't have a web browser accessible. The two situations I could think of were a command line only system (e.g. SSH) and my cellphone².

Surprisingly, I couldn't find a command line implementation of SuperGenPass, so I wrote one in Python. I also couldn't find any J2ME or Symbian implementations, and so wrote my own one in J2ME. They both support subdomain stripping and configurable password lengths. They don't support salted passwords.

I chose SuperGenPass over Password Composer because it uses a better scheme. Password Composer only uses hex characters, whereas SuperGenPass uses a base64 encoded hash. SuperGenPass also hashes the password multiple times (which would slow down a brute force attack to find the master password) and imposes complexity requirements on the generated password (which reduces the chances that the generated password can be brute forced).

Following on from yesterday's post, I decided to try implement proper content negotiation. After a fair amount of time spent getting to grips with [Lua][], I got a [script][] which works very nicely. It implements [server driven][] content negotiation for [media types][mime].

The basic idea of content negotiation is that a resource (e.g., this [graph][]) exists in multiple formats (in this case, [SVG][graph-svg], [PNG][graph-png] and [GIF][graph-gif]). When a user agent requests the resource, it indicates which formats it understands by listing them in the Accept header. The server compares these to the available formats and sends the best one. So a browser which can display [SVG][] will receive the diagram in SVG format, while a browser which can't will receive it in [PNG][] (or [GIF][]) format.

(The following description assumes knowledge of the Accept header format.)

The script works by searching the directory for files with the requested name but with an additional extension (each of which is a variant). The [media type][mime] is inferred from the extension using /etc/mime.types, and the quality of the type is set by a hardcoded table in the script. Each variant is checked against the acceptable types sent by the user agent, and the overall quality calculated by multiplying the quality with the q parameter in the Accept header. The variant with the highest overall quality is then chosen.

Some browsers include wildcard entries such as image/* and */* in the Accept header without specifying a q parameter. This parameter defaults to 1 (the highest value), which means that no preference is actually indicated. The script implements the same [hack][] that [Apache][] does in order to compensate for this. It also handles directory index files by defaulting to files named "index".

To install the [script][], download and save it somewhere (such as /etc/lighttpd/). Then add the following to the site definition.

magnet.attract-physical-path-to = ("/etc/lighttpd/negotiate.lua")