All posts by Andrew

Original provided by WikiMedia:

ARM Assembly: Binary Heaps

I got a Raspberry Pi for Christmas and I’ve been teaching myself ARM assembly. It’s my first time working with assembly language, as I didn’t take an systems architecture or OS fundamentals class in college.

I’m slowly working on a Huffman Encoder, trying to use only native Linux system calls without making calls to other external libraries.

This will be the first in a series of posts about this topic.

The posts probably won’t be very long, the stuff I’m doing isn’t revolutionary, so there’s not a lot to discuss.

Today I’m here to talk about binary heaps. When I learned about binary heaps in my data structures class I didn’t really understand the usefulness of them. I knew that you could use them to implement heapsort, and to make priority queues, but because they’re simpler than red-black trees and other binary search trees, they can’t be used for easy ordered traversal. Working in higher level languages I never really had a need to implement a heap for anything.

However, I am now in need of a priority queue, and I am trying to work in a static memory footprint because I’m trying not to allocate any additional memory beyond the initial memory footprint of the application. Suddenly binary heaps make a whole lot of sense. (Before you ask, yes, I did realize afterwards that I could solve the same problem using the same space and time complexity with a binary search tree, which is what I will implement next.)

The code I wrote to work with heaps is designed to be used for a priority queue. As such it stores a 2-word (64 bit) value in the heap. The first word (32 bits) of the value is the “key” or “priority”, used to sort the entry within the heap. The second word (32 bits) is the “value”. The value is actually optional, so one could use this same code for sorting an array of integers, for example, although with a few tweaks it could be made more more efficient for that purpose. Also, when removing an element I ought to swap it with the last element rather than just copying the last element into the first spot. That would make the algorithm effectively do a heapsort out-of-the-box. Maybe in v2. The code also stores the current size of the heap and the maximum size of the heap in the first two words of the heap’s memory space so that those values don’t need to be passed around by hand.

I am still learning assembly, but hopefully someone will find this useful.

The code is located here:
The test code is here:

Adding Certificates to Ubuntu and GitLab


I recently set up GitLab and Mattermost on an Ubuntu 14.04 server at work using the GitLab Community Edition Omnibus installer. Overall the process was incredibly easy and I highly recommend these products. However, I ran into some hiccups when I tried to run the applications under SSL. Since it took me a little while to figure out how to work through the issues, I thought it might be helpful to document what I did to get it working properly.

Continue reading Adding Certificates to Ubuntu and GitLab

Cleaning Out Old Ubuntu Kernels

One of the problems I often run into when administering Linux servers running the Ubuntu distribution is discovering that the /boot partition has become full and new kernels can no longer be installed.

The reason this happens is that apt-get (rightfully) doesn’t want to remove existing kernels when installing a new kernel. This is a Good Idea™ for two reasons:

  1. The package manager shouldn’t remove the files for the kernel you are currently running.
  2. Once you reboot and are running the new kernel, the old kernel should stick around so that you can rollback if problems are found with the new kernel.

However, thanks to the easy-to-use administration tools found in Ubuntu these days, many new Linux users don’t know how to clean up those old kernels once they’re running on the new ones. I’ve run into this problem often enough that I finally just wrote a script to do it for me.

The current version of this script is located here:

The script works like this:

  1. First, it figure out what kernel you are currently running by calling out to the uname tool.
  2. Second, it queries the list of installed kernels using dpkg.
  3. Finally, it generates an apt-get command that removes all kernel versions that are lower than the one you are currently running.

For example, let’s say that we have 3.19.0-30, 3.19.0-31, and 3.19.0-32 currently installed, but we are running on the middle version: 3.19.0-31. Running the script will uninstall 3.19.0-30 but will leave 3.19.0-31 and 3.19.0-32 in place. Rebooting will boot us into 3.19.0-32, at which point we can run the script again to remove 3.19.0-31.

I hope that others will find this script useful. Let me know if you have any questions or concerns about it.

A MUSH Written in Racket (Scheme)

I’ve been working on a project for the past couple days to learn the Racket programming language. Racket is based on Scheme, which is in turn based on Lisp. Racket includes a compiler that will produce a native binary on Mac OSX, Linux, or Windows as well.

The project I’m working on is a simple MUSH (Multi-User Shared Hallucination). The code is on my GitHub page if you want to take a look at it. It doesn’t do much yet, but I’ll keep adding to it as I have time to do so. The initial code base is around 260 lines of code and it allows players to chat with each other, look at the room they are in, and see who is online. It also contains the necessary data structures to allow users to move from one room to another and to have objects in their inventories, but the code to make use of those structures hasn’t been written yet.

Part of my goal with this project is to have a simple in-game environment for creating rooms, objects, and commands on-the-fly. The codebase still needs a long term storage mechanism before it will be useful though, as everything is currently stored in memory.

Regular Expression Magic and ViM

Every now and then I have an editing task for which Eclipse is just not up to the job. Usually it involves making a lot of changes all at once. (I realize that Eclipse has regex find/replace, but I feel much better working in ViM in these cases.)

Here is an example: I have a block of Java enum code that I want to split out into an enum and two maps.

Here is the regular expression I use to parse the enum declaration:


Here is an example of an enum declaration that matches this regular expression:

FACEBOOK(Constants.FACEBOOK, "fbconnect://success", "fbconnect://success?error_reason"),

I then run three s// commands on the input:

%s//callbackMap.put(Provider.\1, \3);/g
%s//cancelMap.put(Provider.\1, \4);/g

After each command I copy the buffer and paste it back into Eclipse, then hit ‘u’ to undo my changes so that I can run the next command on the original buffer contents.

Here’s what I get (these aren’t meant to be used in isolation like this, of course):

callbackMap.put(Provider.FACEBOOK, "fbconnect://success");
cancelMap.put(Provider.FACEBOOK, "fbconnect://success?error_reason");

For complete examples, check behind the cut.

Continue reading Regular Expression Magic and ViM

Skype Problems on Ubuntu 13.04 64bit

I’ve been having problems getting Skype to work properly on Ubuntu 13.04. When Skype was running properly the other audio applications on the box wouldn’t work. If I started Skype while other audio applications were running then I’d have to audio in Skype. Ubuntu uses the PulseAudio audio server for its audio services and so does Skype, so things should have been working. However, when I went into the Skype options panel PulseAudio wasn’t listed as a possible audio device. It turns out the problem has to do with me using a 64bit version of Ubuntu. The Skype binary is 32bit and it is linked against a 32bit version of GStreamer, but the 32bit version of the PulseAudio client isn’t installed by default. This is easily fixed by running:

$ sudo apt-get install libpulse0:i386

Hopefully this will save somebody else some time trying to debug this issue!

Fixing Column Span Issues in IE7 With Dojo

I’m currently working on a Dojo/Dijit based web application.  The HTML for this app is very minimal: just a div tag that is used as a connection point.  The rest of the HTML is generated on the fly by the Dijit libraries.

Here is an example:

var table = new dojox.layout.TableContainer({
    cols: 2,
    spacing: "5px"
    new dijit.form.TextBox({
        id: "textbox", 
        name: "textbox", 
        label: "Text Box:", 
        title: "Enter your text here!",
        colspan: 2

In most browsers this works just fine, but I’ve had several problems related to Internet Explorer 7.  One of these is that column spanning doesn’t work the way it should in tables.  This is happening because IE7 uses the attribute “colSpan” to set the column span on a TD element.  However, all the other browsers I test with use “colspan”.  (Notice the capitalization!)  The Dijit code is building the HTML by modifying the dom nodes directly instead of using the innerHtml attribute.  This means that it is calling code that looks like this:

element.colspan = x;

When it needs to be calling code like this:

element.colSpan = x;

To get around this I used the dojo.query method to get a list of all elements with a colspan attribute and then set the colSpan attribute to match here.

Here is my fix:

dojo.addOnLoad(function() {
    if(dojo.isIE > 0) {"Fixing IE colSpan issue.");
        // Fix colSpan attributes
        dojo.forEach(dojo.query("[colspan]"), function(tag) {
            tag["colSpan"] = tag.colspan;  

This fix isn’t needed for IE 8 or IE 9, but it doesn’t hurt to leave the code in for those as well. You could change the if condition to check for dojo.isIE > 0 && dojo.isIE < 8 if you don’t want to run the code on IE 8 or newer.

Editing Percent Values Using Dijit’s NumberTextBox

Dijit is a web UI toolkit built on top of the Dojo framework. One of its widgets is called NumberTextBox. This widget allows you to show and edit formatted numbers easily.

For example, I can create an instance of CurrencyTextBox (a subclass of NumberTextBox) and call set(“value”,  2589632).  This will display the value as follows (assuming that my locale is set to en_US):

If I click in the box to edit the value, it changes back to just numbers and looks like this:

Exiting the field will reformat the displayed value to match my locale’s number formatting guidelines.  However, when I call the get(“value”) method on the widget, I will get back the number 2589632 instead of the formatted string.  This makes it easily to implement locale sensitive number formatting for web applications.

The problem I’ve been having is that percents aren’t handled quite right. Setting the “type” constraint to “percent” will properly display percent values so that setting the value of the widget to “0.02” will display the string “2.00%”.

However, When the user clicks on the box to edit the value, the “2.00%” is replaced by it’s real value: “0.02”.

This causes two problems:

  1. The user is expecting to enter a percentage, not a decimal value.  Users are often confused when the value they were expecting to see suddenly changes.  Also, a user might enter “2” in the field, expecting it to show “2.00%”.  Instead it will show “200.00%”.
  2. Truncation can occur when the number being edited has too many decimal places. Setting the “places” constraint on the widget to “2” will display the value “0.0256” as “2.56%”. However, when you edit the value it truncates back to 2 decimal places, showing you only “0.02”. Those extra two decimal places are now lost forever.

There is an open defect for this issue, but I couldn’t wait for them to fix it in the main dojo code.  To get around these issues I started digging into the NumberTextBox code and found that I can replace the parse() method on the NumberTextBox object to get around the problem. This solution also appends a percent symbol to the end of the string if one was left off, making it easier for a user to simply enter “10” and have that converted to “10.00%” when they move to the next field.

Here is my solution:

function createPercentTextBox(name, title, extraParams) {
    if(!dojo.isObject(extraParams)) {
        extraParams = {};

    var parseFunction = function(expression, options) {
        if(dojo.isString(expression)) {
            expression = dojo.trim(expression);
            var i = expression.lastIndexOf("%");
            if(i == -1) {
                expression = expression + "%";
        var value = dojo.number.parse(expression, { pattern: '0%' });
        return value;

    var params = {
        id: name,
        name: name,
        label: title ? title + ":" : "",
        title: title ? title : "",
        constraints: {
            type: 'percent',
            places: 2
        editOptions: {
            pattern: "##0.00%"
        parse: parseFunction

    dojo.mixin(params, extraParams);

    return new dijit.form.NumberTextBox(params);

Note: I’m using Dojo 1.6 for this example. Future versions of Dojo may resolve this issue more elegantly.

A Simple Esperanto Keyboard for iPhone

Klavaro de Esperanto

Today I wrote a simple Esperanto keyboard for the iPhone. It’s really just a little HTML page with some JavaScript and CSS to make it look like an iPhone app when you view it from an iPhone. It looks pretty bad if you view it outside of an iPhone though, because the buttons don’t line up right. Maybe I’ll make it more fully featured on non-iPhone browsers, but there are better tools out there for that already.