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 needed to resize the ext4 filesystem of the /data partition on my Android phone and spent ages looking for a prebuilt binary of resize2fs (since it isn't included in ROMs or recovery). I didn't find one and so spent ages trying to build it myself. To save others the trouble, here are the binaries.

Just the main ones (mke2fs, resize2fs, tune2fs, fsck): tar.xz 630K or zip 1.5M
Everything tar.xz 1.6M or zip 5.8M

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.

My fiancée and I recently bought our first property, which was an interesting experience. It is a fairly complicated process, and many people don't understand how it works or the costs associated with it. So I thought that I would document it to help anyone else looking to purchase property for the first time.

Deciding what you need

The first thing I suggest you do is decide what you need and what you want. Make a list of hard requirements, and another list of nice-to-haves. Consider things like: number of rooms, secure parking and garages, automatic gates, baths and showers, flat or townhouse or freestanding, garden, pool, balcony and appliance space.

Determining what you can afford

Work out how much of your income you could put into a bond each month, and use an online calculator to calculate the loan amount which that represents. Note that the maximum monthly repayment is usually limited to 30% of your income. If you are buying with your partner, your combined income can be used. Interest rates are usually linked to the prime lending rate set by the Reserve Bank. When we applied for our bond we were offered +1.2%, +0.2%, +0.05% and -0.62%, so I'd suggest working with an interest rate of prime or slightly above.

Work out what deposit you can afford, which is payable when your offer is accepted. Bear in mind that there are significant other costs which you will also need to cover (up to 5% of the purchase price). Your deposit will affect the strength of your offer, as well as your bond applications. Aim for at least 5%, and ideally 10%.

Estate agents

Most properties are sold through estate agents. The seller will approach one or more estate agents and grant them mandates to try to sell the property. The estate agent will usually perform a valuation and help the seller to choose an asking price. If (and only if) the agent manages to sell the property, the seller pays them a commission. The going rate seems to be 7.5% of the selling price (excluding VAT).

Visiting properties

The best way to discover properties still seems to be the property section of the newspaper, although some of the estate agents have semi-decent website listings. We spent four Sundays visiting showhouses listed in the newspaper, as well as a few others which we made appointments to see. We probably visited about 25 properties in total, which is fairly good going. I would suggest visiting at least 10 properties before putting an offer in — it takes a while to be able to judge the value of a property.

Inspection

When you find a property you really like and are seriously considering putting in an offer, I suggest that you go back for a more detailed inspection. I'm not suggesting that all these conditions be met, but that they should be considered when determining how much the property is worth to you.

• How much cupboard space do the bedrooms have?
• What state is the bathroom in?
• How old is the geyser?
• What's the water pressure like?
• Do the taps work properly?
• How big is the kitchen?
• How many appliances is there space for (washing machine, tumble dryer, dishwasher)?
• What state are the oven and hob in?
• What state are the kitchen and bedroom cupboards in?
• How new is the distribution board, plugs and light fittings?
• Is the electricity prepaid?
• Is there an alarm?
• Do all the windows have burglar guards?
• What condition are the doors and windows in?
• Are there security gates on the doors?
• What condition is the wall and ceiling paint in?
• What condition is the roof in?

Ask why the owner is selling, and what crime in the area is like. Check what the monthly rates are (preferably get a copy of the latest rates statement).

Sectional title

Check how many units there are (the fewer the better), and how many have live-in owners versus tenants (more live-in owners is better). Ask what the body corporate is like and how effectively it operates. Get the latest financial statements of the body corporate and check that they are financially sound. Get and read the conduct rules of the scheme (are pets allowed?). Get the latest levies statement and check what the levies are¹. Ideally get the sectional title plan (a diagram showing the units) and check that the unit number is correct.

Making an offer

Once you've found a property you want to buy, you make an offer to the seller. This is a formal process where you draw up an Offer to Purchase which sets out the details and conditions of the offer. The seller will have a certain amount of time in which to accept the offer (usually about 2 days), and once they have signed the document it becomes the Agreement of Sale. The seller could also come back with a counter offer.

Remember that the asking price is simply a guide, and also that the agent wants to sell the property for as much as possible (since their commission is linked to the selling price). You need to decide how much the property is worth to you. In most cases it's worth starting with a lower offer and raising it if it's rejected.

The offer defines when occupation is handed over, either on a specific date, or when transfer goes through (i.e. when you legally own the property). If occupation is handed over before or after transfer, then the party with occupation will owe the owner an occupational levy (rent, basically).

Applying for a bond

Once your offer is accepted you will need to apply for a bond. It's worth applying to multiple lending institutions in order to get the best deal. The recent trend is to use a mortgage originator, who applies to numerous institutions on your behalf. They earn commission from the institution if a bond is accepted, so theoretically² there's no cost to you. What we did was apply directly to the bank which we bank with, and got the mortgage originator to apply to the other institutions. This process usually takes about 2 weeks.

The lending institution charges an initiation fee on the bond, and there is usually a monthly service charge as well. The institution will require that the building is insured, although with sectional titles this is done by the body corporate.

Conveyancing

Conveyancing is the process of transferring ownership of the property, and is performed by a legal firm. The buyer is usually liable for the attorneys' fees³, as well as various costs they incur (rates clearance certificate from the municipality, levy clearance certificate from the body corporate, and deeds office fee). The conveyancers also collect transfer duty from the buyer, which is a tax levied by the government. The legal firms agree on a recommended fee structure for their services, but are not obligated to stick to it. This process usually takes about 8 weeks.

Traditionally the conveyancers are chosen by the seller, which is a pretty stupid system since the buyer pays them. You may get a better deal if you shop around for conveyancers before hand and nominate them in your Offer to Purchase.

Bond registration

The mortgage bond needs to be registered against the property, and this is also done by a legal firm. Similar to the conveyancers, the buyer is liable for the attorneys' fees and associated costs. The bond attorneys are usually nominated by the lending institution. Like the conveyancing, there is a standard fee structure, but firms are not obligated to actually use it.

Transfer

The conveyancers and bond attorneys lodge the various papers at the deeds office simultaneously, and it then takes a week or two to process the transfer. All in all the whole process should take about 3 months to complete. You will be liable for all rates and levies from the date of transfer.

Tools

Ooba have an affordability calculator to calculate what bond you can afford, and a bond and transfer costs calculator to estimate the purchase costs. Fin24 have a good bond calculator which graphs the capital and interest components of the bond.

I have also written my own purchase costs calculator and bond calculator, which should give similar answers.