0xFE - 11111110b - 0376 - 254 - b9#9

More K-Means Clustering Experiments on Images

2012-01-02T13:34:00.000-05:00

I spent a little more time experimenting with k-means clustering on images and realized that I could use these clusters to recolor the image in interesting ways.

I wrote the function save_recolor to replace pixels from the given clusters (replacements) with new ones of equal intensity, as specified by the rgb_factors vector. For example, the following code will convert pixels of the first two clusters to greyscale.


> save_recolor("baby.jpeg", "baby_new.jpg", replacements=c(1,2),
               rgb_factors=c(1/3, 1/3, 1/3))

It's greyscale because the rgb_factors distributes the pixel intensity evenly among the channels. A factor of c(20/100, 60/100, 20/100) would make pixels from the cluster 60% more green.

Let's get to some examples. Here's an unprocessed image, alongside its color clusters. I picked k=10. You can set k by specifying the palette_size parameter to save_recolor.

Here's what happens when I remove the red (the first cluster).


> save_recolor("baby.jpeg", "baby_new.jpg", replacements=1)

In the next image, I keep the red, and remove everything else.


> save_recolor("baby.jpeg", "baby_new.jpg", replacements=2:10)

Below, I replace the red cluster pixels, with green ones of corresponding intensity.


> save_recolor("baby.jpeg", "baby_new.jpg", replacements=1,
               rgb_factors=c(10/100, 80/100, 10/100))

And this is a fun one: Get rid of everything, keep just the grass.


> save_recolor("baby.jpeg", "baby_new.jpg", replacements=c(1,3:10))

I tried this on various images, using different cluster sizes, replacements, and RGB factors, with lots of interesting results. Anyhow, you should experiment with this yourselves and let me know what you find.

I should point out that nothing here is novel or new -- it's all well known in image processing circles. It's still pretty impressive what you can do when you apply simple machine learning algorithms to other areas.

Okay, as in all my posts, the code is available in my GitHub repository:

https://github.com/0xfe/experiments/blob/master/r/recolor.rscript

Happy new year!

K-Means Clustering and Art

2011-12-31T10:27:00.000-05:00

Cross posted from Google+.

My coworker at Google, Tony Rippy, has for a while been working on a fascinating problem. Take all the pixels of a photograph, and rearrange them so that the final image looks like an artist's palette -- something to which you can take a paintbrush and recreate the original image.

He's got some really good looking solutions which he might post if you ask him nicely. :-)

This turns out to be a tricky problem, and its hard to come up with an objective measure of the quality of any given solution. In fact, the quality is very subjective.

Anyhow, while studying the K-means clustering algorithm from ml-class, it struck me that k-means could be used to help with extracting a small palette of colors from an image. For example, by using each of the RGB channels as features, and euclidian distance as the similarity metric, one could run stock k-means to generate clusters of similar colors.

I coded up a quick R script to test this and got some interesting results. Here is an example of an image with its potential palette. Recall that the second image is simply the first image with the pixels rearranged.

I experimented with various values of k (number of clusters) for the different images. It turns out that it's pretty hard to algorithmically pre-determine this number (although there are various techniques that do exist.) The water villa pic above has 15 clusters, the nursery pic below has 20, and the cartoon has 6.

Note that this is only one subproblem of the original one; there is also the subproblem of placement, which I skirted around by simply arranging the colors in vertical bands across the final image. I'm pretty sure no artist's palette looks like this.

Also, these palettes aren't very "clean". Since the original pictures themselves are noisy, some of this noise arbitrarily creep into the various clusters. Working with a filtered version of the picture would be cheating, so we won't do that. But we might be able to extract the noisy pixels, put them in a special cluster, and run k-means on the remaining pixels.

Okay, enough talk. Here's the code: https://github.com/0xfe/experiments/blob/master/r/palette.rscript

First install cclust and ReadImages packages from CRAN, and try out the algorithm in an R console:


> source('/path/to/palette.rscript')
> plot_palette('/path/to/some/image.jpg')

This will produce a plot with the original image and the transformed one next to each other, like the attached pics below. It uses 10 clusters by default, for a palette of 10 colors. You can change this by passing the cluster count as the second parameter to plot_palette.


> plot_palette('/path/to/some/image.jpg', 20)

That's all folks!

A Web Audio Spectrum Analyzer

2011-08-21T11:15:00.000-04:00

In my last post, I went over some of the basics of the Web Audio API and showed you how to generate sine waves of various frequencies and amplitudes. We were introduced to some key Web Audio classes, such as AudioContext, AudioNode, and JavaScriptAudioNode.

This time, I'm going to go take things a little further and build a realtime spectrum analyzer with Web Audio and HTML5 Canvas. The final product plays a remote music file, and displays the frequency spectrum overlaid with a time domain graph.

The demo is here: JavaScript Spectrum Analyzer. The code for the demo is in my GitHub repository.

The New Classes

In this post we introduce three new Web Audio classes: AudioBuffer, AudioBufferSourceNode, and RealtimeAnalyzerNode.

An AudioBuffer represents an in-memory audio asset. It is usually used to store short audio clips and can contain multiple channels.

An AudioBufferSourceNode is a specialization of AudioNode that serves audio from AudioBuffers.

A RealtimeAnalyzerNode is an AudioNode that returns time- and frequency-domain analysis information in real time.

The Plumbing

To begin, we need to acquire some audio. The API supports a number of different formats, including MP3 and raw PCM-encoded audio. In our demo, we retrieve a remote audio asset (an MP3 file) using AJAX, and use it to populate a new AudioBuffer. This is implemented in the RemoteAudioPlayer class (js/remoteaudioplayer.js) like so:


RemoteAudioPlayer.prototype.load = function(callback) {
  var request = new XMLHttpRequest();
  var that = this;
  request.open("GET", this.url, true);
  request.responseType = "arraybuffer";
  request.onload = function() {
    that.buffer = that.context.createBuffer(request.response, true);
    that.reload();
    callback(request.response);
  }

  request.send();
}

Notice that the jQuery's AJAX calls aren't used here. This is because jQuery does not support the arraybuffer response type, which is required for loading binary data from the server. The AudioBuffer is created with the AudioContext's createBuffer function. The second parameter, true, tells it to mix down all the channels to a single mono channel.

The AudioBuffer is then provided to an AudioBufferSourceNode, which will be the context's audio source. This source node is then connected to a RealTimeAnalyzerNode, which in turn is connected to the context's destination, i.e, the computer's output device.


var source_node = context.createBufferSource();
source_node.buffer = audio_buffer;

var analyzer = context.createAnalyser();
analyzer.fftSize = 2048; // 2048-point FFT
source_node.connect(analyzer);
analyzer.connect(context.destination);

To start playing the music, call the noteOn method of the source node. noteOn takes one parameter: a timestamp indicating when to start playing. If set to 0, it plays immediately. To start playing the music 0.5 seconds from now, you can use context.currentTime to get the reference point.


// Play music 0.5 seconds from now
source_node.noteOn(context.currentTime + 0.5);

It's also worth noting that we specified the granularity of the FFT to 2048 by setting the analyzer.fftSize variable. For those unfamiliar with DSP theory, this breaks the frequency spectrum of the audio into 2048 points, each point representing the magnitude of the n/2048th frequency bin.

The Pretty Graphs

Okay, it's now all wired up -- how do I get the pretty graphs? The general strategy is to poll the analyzer every few milliseconds (e.g., with window.setInterval), request the time- or frequency-domain data, and then render it onto a HTML5 Canvas element. The analyzer exports a few different methods to access the analysis data: getFloatFrequencyData, getByteFrequencyData, getByteTimeDomainData. Each of these methods populate a given ArrayBuffer with the appropriate analysis data.

In the below snippet, we schedule an update() function every 50ms, which breaks the frequency-domain data points into 30 bins, and renders a bar representing the average magnitude of the points in each bin.


canvas = document.getElementById(canvas_id);
canvas_context = canvas.getContext("2d");

function update() {
  // This graph has 30 bars.
  var num_bars = 30;

  // Get the frequency-domain data
  var data = new Uint8Array(2048);
  analyzer.getByteFrequencyData(data);

  // Clear the canvas
  canvas_context.clearRect(0, 0, this.width, this.height);

  // Break the samples up into bins
  var bin_size = Math.floor(length / num_bars);
  for (var i=0; i < num_bars; ++i) {
    var sum = 0;
    for (var j=0; j < bin_size; ++j) {
      sum += data[(i * bin_size) + j];
    }

    // Calculate the average frequency of the samples in the bin
    var average = sum / bin_size;

    // Draw the bars on the canvas
    var bar_width = canvas.width / num_bars;
    var scaled_average = (average / 256) * canvas.height;

    canvas_context.fillRect(i * bar_width, canvas.height, bar_width - 2,
                         -scaled_average);
}

// Render every 50ms
window.setInterval(update, 50);

// Start the music
source_node.noteOn(0);

A similar strategy can be employed for time-domain data, except for a few minor differences: Time-domain data is usually rendered as waves, so you might want to use lot more bins and plot pixels instead of drawing bars. The code that renders the time and frequency domain graphs in the demo is encapsulated in the SpectrumBox class in js/spectrum.js.

The Minutiae

I glossed over a number of things in this post, mostly with respect to the details of the demo. You can learn it all from the source code, but here's a summary for the impatient:

The graphs are actually two HTML5 Canvas elements overlaid using CSS absolute positioning. Each element is used by its own SpectrumBox class, one which displays the frequency spectrum, the other which displays the time-domain wave.

The routing of the nodes is done in the onclick handler to the #play button -- it takes the AudioSourceNode from the RemoteAudioPlayer, routes it to node of the frequency analyzer, routes that to the node of the time-domain analyzer, and then finally to the destination.

Bonus: Another Demo

That's all folks! You now have the knowhow to build yourself a fancy new graphical spectrum analyzer. If all you want to do is play with the waves and stare at the graphs, check out my other demo: The Web Audio Tone Analyzer (source). This is really just the same spectrum analyzer from the first demo, connected to the tone generator from the last post.

References

As a reminder, all the code for my posts is available at my GitHub repository: github.com/0xfe.

The audio track used in the demo is a discarded take of Who-Da-Man, which I recorded with my previous band Captain Starr many many years ago.

Finally, don't forget to read the Web Audio API draft specification for more information.

Enjoy!

Generating Tones with the Web Audio API

2011-08-13T20:58:00.005-04:00

The Web Audio API is a W3C draft standard interface for building in-browser audio applications. Although the draft is well specified, it is almost impossible to find useful documentation on building applications with it.

In my quest to deeper understand HTML5 audio, I spent some time figuring out how the API works, and decided to write up this quick tutorial on doing useful things with it.

We will build a sine wave tone-generator entirely in JavaScript. The final product looks like this: Web Audio Tone Generator.

The full code is available in my GitHub repository: https://github.com/0xfe/experiments/tree/master/www/tone

Caveats

The Web Audio API is draft, is likely to change, and does not work on all browsers. Right now, only the latest versions of Chrome and Safari support it.

Onwards We Go

Getting started making sounds with the Web Audio API is straightforward so long as you take the time to study the plumbing, most of which exists to allow for real-time audio processing and synthesis. The complete specification is available on the W3C Web Audio API page, and I'd strongly recommend that you read it thoroughly if you're interested in building advanced applications with the API.

To produce any form of sound, you need an AudioContext and a few AudioNodes. The AudioContext is sort of like an environment for audio processing -- it's where various attributes such as the sample rate, the clock status, and other environment-global state reside. Most applications will need no more than a single instance of AudioContext.

The AudioNode is probably the most important component in the API, and is responsible for synthesizing or processing audio. An AudioNode instance can be an input source, an output destination, or a mid-stream processor. These nodes can be linked together to form processing pipelines to render a complete audio stream.

One kind of AudioNode is JavaScriptAudioNode, which is used to generate sounds in JavaScript. This is what what we will use in this tutorial to build a tone generator.

Let us begin by instantiating an AudioContext and creating a JavaScriptAudioNode.

var context = new webkitAudioContext();
var node = context.createJavaScriptNode(1024, 1, 1);

The parameters to createJavaScriptNode refer to the buffer size, the number of input channels, and the number of output channels. The buffer size must be in units of sample frames, i.e., one of: 256, 512, 1024, 2048, 4096, 8192, or 16384. It controls the frequency of callbacks asking for a buffer refill. Smaller sizes allow for lower latency and higher for better overall quality.

We're going to use the JavaScriptNode as the source node along with a bit of code to create sine waves. To actually hear anything, it must be connected to an output node. It turns out that context.destination gives us just that -- a node that maps to the speaker on your machine.

The SineWave Class

To start off our tone generator, we create a SineWave class, which wraps the AudioNode and wave generation logic into one cohesive package. This class will be responsible for creating the JavaScriptNode instances, generating the sine waves, and managing the connection to the destination node.

SineWave = function(context) {
  var that = this;
  this.x = 0; // Initial sample number
  this.context = context;
  this.node = context.createJavaScriptNode(1024, 1, 1);
  this.node.onaudioprocess = function(e) { that.process(e) };
}

SineWave.prototype.process = function(e) {
  var data = e.outputBuffer.getChannelData(0);
  for (var i = 0; i < data.length; ++i) {
    data[i] = Math.sin(this.x++);
  }
}

SineWave.prototype.play = function() {
  this.node.connect(this.context.destination);
}

SineWave.prototype.pause = function() {
  this.node.disconnect();
}

Upon instantiation, this class creates a JavaScriptAudioNode and attaches an event handler to onaudioprocess for buffer refills. The event handler requests a reference to the output buffer for the first channel, and fills it with a sine wave. Notice that the handler does not know the buffer size in advance, and gets it from data.length.

The buffer is of type ArrayBuffer which is a JavaScript Typed Array. These arrays allow for high throughput processing of raw binary data. To learn more about Typed Arrays, check out the Mozilla Developer Documentation on Typed Arrays.

To try out a quick demo of the SineWave class, add the following code to the onload handler for your page:

var context = new webkitAudioContext();
var sinewave = new SineWave(context);
sinewave.play();

Notice that sinewave.play() works by wiring up the node to the AudioContext's destination (the speakers). To stop the tone, call sinewave.pause(), which unplugs this connection.

Generating Specific Tones

So, now you have yourself a tone. Are we done yet?

Not quite. How does one know what the frequency of the generated wave is? How does one generate tones of arbitrary frequencies?

To answer these questions, we must find out the sample rate of the audio. Each data value we stuff into the buffer in out handler is a sample, and the sample rate is the number of samples processed per second. We can calculate the frequency of the tone by dividing the sample rate by the length of a full wave cycle.

How do we get the sample rate? Via the getSampleRate() method of AudioContext. On my machine, the default sample rate is 44KHz, i.e., 44100 samples per second. This means that the frequency of the generated tone in our above code is:

freq = context.getSampleRate() / 2 * Math.PI

That's about 7KHz. Ouch! Lets use our newfound knowledge to generate less spine-curdling tones. To generate a tone of a specific frequency, you can change SineWave.process to:

SineWave.prototype.process = function(e) {
  var data = e.outputBuffer.getChannelData(0);
  for (var i = 0; i < data.length; ++i) {
    data[i] = Math.sin(this.x++ / (this.sample_rate / 2 * Math.PI * this.frequency));
  }
}

Also make sure you add the following two lines to SineWave's constructor:

this.sample_rate = this.context.getSampleRate();
this.frequency = 440;

This initializes the frequency to pitch standard A440, i.e., the A above middle C.

The Theremin Effect

Now that we can generate tones of arbitrary frequencies, it's only natural that we connect our class to some sort of slider widget so we can experience the entire spectrum right in our browsers. Turns out that JQueryUI already has such a slider, leaving us only a little plumbing to do.

We add a setter function to our SineWave class, and call it from our slider widget's change handler.

SineWave.prototype.setFrequency = function(freq) {
  this.next_frequency = freq;
}

A JQueryUI snippet would look like this:

$("#slider").slider({
    value: 440,
    min: 1,
    max: 2048,
    slide: function(event, ui) { sinewave.setFrequency(ui.value); }
});

Going up to Eleven

Adding support for volume is straightforward. Add an amplitude member to the SineWave constructor along with a setter method, just like we did for frequency, and change SineWave.process to:

SineWave.prototype.process = function(e) {
  var data = e.outputBuffer.getChannelData(0);
  for (var i = 0; i < data.length; ++i) {
    data[i] = this.amplitude * Math.sin(this.x++ / (this.sample_rate / 2 * Math.PI * this.frequency));
  }
}

Folks, we now have a full fledged sine wave generator!

Boo Hiss Crackle

But, we're not done yet. You've probably noticed that changing the frequency causes mildly annoying crackling sounds. This happens because when the frequency changes, discontinuity occurs in the wave, causing a high-frequency pop in the audio stream.

Discontinuity when Changing Frequencies

We try to eliminate the discontinuity by only shifting frequencies when the cycle of the previous frequency completes, i.e., the sample value is (approximately) zero. (There are better ways to do this, e.g., windowing, LPFs, etc., but these techniques are out of the scope of this tutorial.)

Although this complicates the code a little bit, waiting for the cycle to end significantly reduces the noise upon frequency shifts.

SineWave.prototype.setFrequency = function(freq) {
  this.next_frequency = freq;
}

SineWave.prototype.process = function(e) {
  // Get a reference to the output buffer and fill it up.
  var data = e.outputBuffer.getChannelData(0);

  // We need to be careful about filling up the entire buffer and not
  // overflowing.
  for (var i = 0; i < data.length; ++i) {
    data[i] = this.amplitude * Math.sin(
        this.x++ / (this.sampleRate / (this.frequency * 2 * Math.PI)));

    // This reduces high-frequency blips while switching frequencies. It works
    // by waiting for the sine wave to hit 0 (on it's way to positive territory)
    // before switching frequencies.
    if (this.next_frequency != this.frequency) {
      // Figure out what the next point is.
      next_data = this.amplitude * Math.sin(
        this.x / (this.sampleRate / (this.frequency * 2 * Math.PI)));

      // If the current point approximates 0, and the direction is positive,
      // switch frequencies.
      if (data[i] < 0.001 && data[i] > -0.001 && data[i] < next_data) {
        this.frequency = this.next_frequency;
        this.x = 0;
      }
    }
  }
}

The End

As mentioned in the beginning of this tutorial, a demo of the full code is available at http://0xfe.muthanna.com/tone/ and the entire source code is available at https://github.com/0xfe/experiments/tree/master/www/tone.

Do check out the W3C Web Audio API specification. Do check out the Mozilla document on JavaScript Typed Arrays.

Comments, criticism, and error reports welcome. Enjoy!

I'm on Google+

2011-06-30T11:23:00.001-04:00

And I'm quite digging it.

Yes, it isn't lost on me that as a Googler, I'm biased.

You can add me to your circles -- I'm right here.

To make up for this post's utter lack of content, I have you a haiku:

in my machine world,
all the digits of my toes,
are ones and zeroes.

I should stick to what I know.

A Music Theory API

2011-03-31T13:50:00.000-04:00

Most of my work last week consisted of writing music theory code. VexFlow now has a neat little music theory API, that gives you answers to questions like the following:

What note is a minor 3rd above a B?
What are the scale tones of a Gb Harmonic Minor?
What relation is the C# note to an A Major scale? (Major 3rd)
What accidentals should be displayed for the perfect 4th note of a G Major scale?
etc.

The API is part of VexFlow, and can be used independently of the rendering API. Take a look at music.js in the VexFlow GitHub repository for the complete reference. There's also a handy key management library for building scores in keymanager.js.

I'm currently working on updating the VexFlow Tutorial with a quickstart on the music theory API, but meanwhile, here are some teasers (pulled straight out of the tests).

// What does C note consist of?
var parts = music.getNoteParts("c");
equals(parts.root, "c");
equals(parts.accidental, null);

// What does C# note consist of?
var parts = music.getNoteParts("c#");
equals(parts.root, "c");
equals(parts.accidental, "#");

// What is a flat-5th above C?
var value = music.getRelativeNoteValue(music.getNoteValue("c"),
                                       music.getIntervalValue("b5"));
equals(value, music.getNoteValue("gb");
equals(value, music.getNoteValue("f#");

// What is the C quality of a Db?
equals(music.getRelativeNoteName("c", music.getNoteValue("db")), "c#");

// What are the tones of a C major scale?
var c_major = music.getScaleTones(
      music.getNoteValue("c"), Vex.Flow.Music.scales.major);
// result: ["c", "d", "e", "f", "g", "a", "b"]

// What is the interval between a C and a D?
equals(music.getCanonicalIntervalName(music.getIntervalBetween(
     music.getNoteValue("c"), music.getNoteValue("d"))), "M2");

Thanks to the theory support, we now have smarter Accidentals in the standard notation stave that VexTab generates.

Smarter Accidentals

Notice how the accidentals are correctly picked according to the rules of standard notation? Yep, so do I.

We also have lots more tests -- over 750 of them! Try running them on your browser and tell me how long it takes.

That's all folks!

Prettier Tablature

2011-03-27T14:48:00.000-04:00

Spot the difference:

Before

After

Still can't tell? Let me help you out. We have:

Slightly greater spacing between the tablature stave lines. This makes it more consistent in appearance with printed tablature.
Stave lines are cleared before fret numbers are rendered, vastly improving readability.
Font sizes for fret numbers and annotations are bigger.
Associated notation and tablature staves are connected with a vertical bar on the left.
Micro-changes in spacing between fret numbers, effects, annotations, etc.

All these changes have been incorporated into TabDiv, and pushed to GitHub. See more on the VexTab Tutorial page. Enjoy!

The VexFlow Tutorial (...and other goodies)

2011-03-24T16:44:00.000-04:00

Finally... finally... finally... we have the humble beginnings of what could be considered "documentation".

I present to you The VexFlow Tutorial.

Although still in its infancy, the tutorial covers everything you need to start using VexFlow in your own code. My plan for the next few weeks is to make this document as comprehensive as possible, and write up a separate API reference.

I hope that this tutorial will help developers understand VexFlow better, and enable them to build new and interesting libraries, parsers, and applications.

The entire tutorial is stored in the Git repo; feel free to send me your corrections or other updates.

About time, I know.

In other news, we have had a few contributions to both VexFlow and VexTab. A big thanks to airfrog, wiseleyb, and adamf for getting these done.

First, we have the ability to render dotted notes.

Dotted Notes

Then we have key signatures.

Key Signatures

We also have time signatures.

Time Signatures

This includes the really crazy time signatures too.

Whacky Time Signatures

Finally, we have support for different types of clefs.

Alternate Clefs

But wait... there's more. All of this is supported in VexTab by way of new tabstave parameters. Take a look at the updated VexTab Tutorial for the details.

Editing XML and HTML in Vim

2011-03-23T13:26:00.000-04:00

I just discovered the Vim xmledit plugin.

With features like tag-completion, auto-wrapping and unwrapping, quick navigation, etc., it has, in a matter of minutes, measurably decreased my level of frustration while editing markup in Vim.

Installation

The quickest way to install the plugin is by downloading the latest .vba from the plugin site, and run the following commands:

$ vim xmledit.vba
:so %

You also need to edit your .vimrc and add the following:

filetype plugin on

This installs the plugin into your .vim/ftplugin directory, and enables it for .xml files. To enable it for other file types, create a link to the file with the new extension name in the same directory. (Copying the file also works.)

$ cd ~/.vim/ftplugin
$ ln -s xml.vim html.vim
$ ln -s xml.vim xhtml.vim

Usage

The plugin supports the various Vim modes in interesting ways.

In insert mode, when you finish a tag (with the > character), it will be autocompleted and the cursor placed in-between the tags.

If you immediately type another >, it will close the tag on its own line, and place the cursor on a new line right in between.

The % key jumps between the start and end of a tag.

The \% combination jumps between opening and closing tags. (Note that backslash is the default key-prefix for scripts and plugins to use. You can change this prefix with the mapleader setting.)

If you select text (for example with v), and type \x, it will prompt you to wrap the text with a custom tag.

Typing in \d unwraps surrounding tags from the cursor.

Learning More

Type :help xml-plugin for help and more information.

Yay for another awesome Vim plugin. You can see my entire Vim profile in my Evil Tomato GitHub Repository.

On Twitter

2011-03-20T08:43:00.000-04:00

It turns out I'm on twitter. I have absolutely no idea what I'm going to do with it.

Maybe I'll tweet every time time the compiler yells at me... or when my kernel panics... or when my browser frowns.

Whatever it is, I'm on twitter: twitter.com/11111110b

That's seven ones and a zero, followed by a bee.

Regex Substitution in Haskell

2010-09-13T11:03:00.000-04:00

I'm shocked and appalled at the fact that there is no generic regex substitution function in the GHC libraries. All I'm looking for is a simple function equivalent to perl's s/.../.../ expression.

After digging around a bit, I found subRegex in regex-compat. While this works well, it does not use PCRE, and as far as I can tell, there's no support for ByteStrings.

Grrr.

Anyhow, I took the subRegex implementation from regex-compat and mangled it slightly to work with Text.Regex.PCRE. I also added the (=~$) function which feels a bit more familiar to perl users. For example:

Prelude PCRESub> "me boo" =~$ ("(me) boo", "he \\1")
"he me"

The above is equivalent to perl's:

$text = "me boo";
$text =~ s/(me) boo/he $1/;

(~=$) is implemented with reSub (which is also exported by PCRESub). reSub allows you to provide your own CompOption and ExecOption options.

Here's the PCRESub module:

-- PCRE-based Regex Substitution
-- Mohit Muthanna Cheppudira
--
-- Based off code by Chris Kuklewicz from regex-compat library.
--
-- Requires Text.Regex.PCRE from regex-pcre.

module PCRESub(
  (=~$),
  reSub
) where

import Data.Array((!))
import Text.Regex.PCRE

subRegex :: Regex                          -- ^ Search pattern
         -> String                         -- ^ Input string
         -> String                         -- ^ Replacement text
         -> String                         -- ^ Output string
subRegex _ "" _ = ""
subRegex regexp inp repl =
  let compile _i str [] = \ _m ->  (str++)
      compile i str (("\\",(off,len)):rest) =
        let i' = off+len
            pre = take (off-i) str
            str' = drop (i'-i) str
        in if null str' then \ _m -> (pre ++) . ('\\':)
             else \  m -> (pre ++) . ('\\' :) . compile i' str' rest m
      compile i str ((xstr,(off,len)):rest) =
        let i' = off+len
            pre = take (off-i) str
            str' = drop (i'-i) str
            x = read xstr
        in if null str' then \ m -> (pre++) . ((fst (m!x))++)
             else \ m -> (pre++) . ((fst (m!x))++) . compile i' str' rest m
      compiled :: MatchText String -> String -> String
      compiled = compile 0 repl findrefs where
        bre = makeRegexOpts defaultCompOpt execBlank "\\\\(\\\\|[0-9]+)"
        findrefs = map (\m -> (fst (m!1),snd (m!0))) (matchAllText bre repl)
      go _i str [] = str
      go i str (m:ms) =
        let (_,(off,len)) = m!0
            i' = off+len
            pre = take (off-i) str
            str' = drop (i'-i) str
        in if null str' then pre ++ (compiled m "")
             else pre ++ (compiled m (go i' str' ms))
  in go 0 inp (matchAllText regexp inp)

-- Substitue re with sub in str using options copts and eopts.
reSub :: String -> String -> String -> CompOption -> ExecOption -> String
reSub str re sub copts eopts = subRegex (makeRegexOpts copts eopts re) str sub

-- Substitute re with sub in str, e.g.,
--
-- The perl expression:
--
--   $text = "me boo";
--   $text =~ s/(me) boo/he $1/;
--
-- can be written as:
--
--   text = "me boo" =~$ ("(me) boo", "he \\1")
--
(=~$) :: String -> (String, String) -> String
(=~$) str (re, sub) = reSub str re sub defaultCompOpt defaultExecOpt

Example usage:

import PCRESub

main = do
  let text = "me boo" =~$ ("(me) boo", "he \\1")
  print text

Paste this code in, or browse the source at my GitHub repo: PCRESub.hs

Someone please make this work across all the regex backends (and add support for ByteStrings)!

VexFlow Google Group

2010-09-12T12:24:00.000-04:00

I've been out of touch for a while, and it took me way too long to set this up; but hey - better late than never. :-)

After looking into various options for the VexFlow mailing list, I eventually decided to use Google Groups. It's super easy to setup and manage, and has all the features I'll ever need.

If you're interested in hacking, discussing, or simply keeping up with VexFlow, sign up here:

http://groups.google.com/group/vexflow

Unfortunately, I haven't had the time lately to hack on VexFlow, but I assure you that it's only temporary. I have a bunch of partial changes in the works, along with some interesting ideas floating around. More later.

VexFlow is Open Source

2010-08-03T18:04:00.000-04:00

That's right folks! All the VexFlow code is now available in the VexFlow GitHub Repository.

It's distributed under the OSI approved MIT License, so feel free to tinker, tweak, hack, fix, fork, and redistribute it.

A lot of the core infrastructure (e.g., contexts, formatting, etc.) is ready and stable, and most of the work that needs to be done is adding support for various types of modifiers, effects, and annotations. I've worked on some of the trickier ones, like accidentals and beams, and have left the easier ones out so interested coders can learn by contributing.

This said, algorithms-enthusiasts need not feel left out - there are some hard problems to solve as well :-)

Here's where I would like help from the community:

Dots (Easy)
Trills (Easy)
Grace Notes (Moderate)
Slurs (Easy)
Glyphs for time signatures (Easy)
Key signature (Easy if you reuse the accidental placement code from accidentals.js)
Guitar effects: Palm Muting, Scratches, Whammy, Harmonics, etc. (Easy)
Chord Stave with Rhythm Slashes (Moderate to Hard)
Lyrics (Easy)

Here's what I'm working on right now (and also wouldn't mind some help with):

Tuplets / Triplets
VexTab parser support for rests, alternate keys, and multiple voices.
Alternate tunings and support for arbitrary-string instruments.

There isn't much developer documentation right now, but a good place to start is by going through the code for the tests. You may notice that some files are commented better than others - a great way to help is by adding better comments along with more thorough tests.

If you're not a coder and would like to help, you can do so by testing and reporting bugs, helping with documentation, spending $7 on a TabDiv license, or simply spreading the word.

Thanks for all the support and help over the past few months. Dive in and enjoy!

More Durations and Better Beaming

2010-07-20T21:54:00.000-04:00

I finally got most of the duration and beaming support worked out last weekend, and I gotta say that the generated scores by VexFlow (and VexTab) are starting to look pretty good.

In VexTab notation, you can now set the duration of the subsequent notes using the colon (:) character. By default, note durations are set to eighth notes.

Here's an example of a line that generates a half-note followed by two quarter-notes.

Basic Duration Support

Valid duration values (currently) are: w, h, q, 8, 16, and 32. Support for dots and tuplets/triplets is not yet implemented.

Durations can be specified inside slides, bends, and other types of ties by prefixing the fret with the duration value enclosed within colon characters.

Durations within Ties

Also, I spent time working on some of the tricker beam configurations, where notes with varying durations are beamed.

Crazy Beaming

In VexTab, you can create beams by enclosing your notes within brackets (separated by spaces).

Beaming in VexTab

Anyhow, I've pushed out the latest revision, with support for standard notation, durations, and beaming to the TabDiv website. Feel free to toy with it and report any issues you come across.

Here's a screenshot of a bluesy guitar lick written in VexTab.

A Blues Lick in VexTab

That's all for this week, folks! There are a lot more interesting things coming up. Check out the VexTab tutorial to play around in the sandboxes, and stay in touch.

Migrating VexFlow to SCons

2010-07-14T11:51:00.000-04:00

I love tools. Tools keep my projects predictable and smooth. Tools help me code fast and release fast.

VexFlow has gone through many iterations of design, implementation, and deployment, and I couldn't have brought it this far so quickly without my tools. (Well, automated testing had a lot to do with it too, but that's for another post.)

Yesterday, I added a new tool to my toolbox - SCons. I migrated all my building, packaging, test driving, and deployment code to SCons. Compared to the ugly shell scripts I previously used, SCons is a lot cleaner, a lot faster, and significantly easier to manage.

I chose SCons for two reasons:

Simplicity. It's Python-based and super-easy to work with.
Familiarity. I've used it before, so already know my way around it.

Since I use the Google Closure Compiler to build and minimize my JavaScript code, I had to write a new builder for SCons. That turned out to be pretty straightforward to implement.

def js_builder(target, source, env):
  """ A JavaScript builder using Google Closure Compiler. """

  cmd = env.subst(
      "$JAVA -jar $JS_COMPILER --compilation_level $JS_COMPILATION_LEVEL");

  # Add defines to the command
  for define in env['JS_DEFINES'].keys():
    cmd += " --define=\"%s=%s\"" % (define, env['JS_DEFINES'][define])

  # Add the source files
  for file in source:
    cmd += " --js " + str(file)

  # Add the output file
  cmd += " --js_output_file " + str(target[0])

  # Log the command and run
  print env.subst(cmd)
  os.system(env.subst(cmd))

I also needed a new builder to stamp my output with the relevant build information. So, I created a Stamper, which is just a builder that runs some string substitution on files with sed. The stamper looks like this:

def vexflow_stamper(target, source, env):
  """ A Build Stamper for VexFlow """

  cmd =  "sed "
  cmd += " -e s/__VEX_BUILD_PREFIX__/$VEX_BUILD_PREFIX/"
  cmd += " -e s/__VEX_VERSION__/$VEX_VERSION/"
  cmd += ' -e "s/__VEX_BUILD_DATE__/${VEX_BUILD_DATE}/"'
  cmd += " -e s/__VEX_GIT_SHA1__/`git rev-list --max-count=1 HEAD`/ "
  cmd += ("%s > %s" % (source[0], target[0]))

  print env.subst(cmd)
  os.system(env.subst(cmd))

Before you can use these builders, you need to add them to your environment:

env.Append(BUILDERS = {'JavaScript': Builder(action = js_builder),
                       'VexFlowStamp': Builder(action = vexflow_stamper)})

Once this is done, you can add build JavaScript targets with the JavaScript command.

env['JAVA'] = "/usr/bin/java"
env['JS_COMPILER'] = "support/compiler.jar"
env['JS_DEFINES' ] = {
  "Vex.Debug": "true",
  "Vex.LogLevel": "4"
}

sources = ["src1.js", "src2.js", "src3.js"]

env.JavaScript("src.min.js", sources)

This really is just scratching the surface. There's a lot more you can do with SCons to automate and streamline your builds. To learn more, take a look at the user guide.

I added support for testing, packaging, and deployment (of the web pages and demos) to my SCons scripts in a matter of hours, and finally purged all my nasty shell scripts from the VexFlow codebase.

Give it a try. I guarantee you'll be happier.

Durations, Code, and Posters

2010-07-12T14:50:00.000-04:00

The last few weeks have been relatively quiet on the VexFlow side. I've been vacationing in Cape Cod with my wife and 3-month-old.

Obviously, vacation is never fun without a few good coding sprints. I started work on incorporating standard notation into VexTab.

The first thing I needed to do was create a class to convert fret-string pairs to notes. In order to support alternate tunings, I created a Tuning class, whose sole responsibility is to return the correct note for a given fret-string pair, based on the instrument type and tuning.

So, to convert the fret-string pair "5/2" on a 5-string bass to standard notation, all I need to do is:

var tuning = new Vex.Flow.Tuning("G/4,D/4,A/3,E/3,B/2");
var note = tuning.getNoteForFret(5, 2);

The next part was augmenting the language to render standard notation when requested. I modified tabstave to accept key=value parameters, and added a parameter called notation. When set to true, it renders standard notation above the guitar tab.

VexTab with Standard Notation

I also started work on basic duration support and auto-beaming. I don't have much to show for this yet, because they're currently a bit intertwined, and automatic beaming is harder than I anticipated (yet again!)

In other news, I open sourced the VexTab parser, so you can learn more about the language or use it in your own rendering engines. It is currently slightly coupled to VexFlow, but pretty trivial to decouple. (I'm going to fully decouple it as this project progresses.)

The parser is licensed under the MIT license, and is available on GitHub at: http://github.com/0xfe/vex/tree/master/vextab/.

Finally, some readers who liked my previous Chrome Poster from Source Code post requested posters for other open-source projects. I generated posters for Firefox, Linux, and FreeBSD, and made them available on my other side project: Wicked Mean Posters.

Firefox Poster from Source Code

More next time!

Encrypted Incremental Backups to S3

2010-06-25T17:25:00.000-04:00

I spent some time this week trying to get secure online backups working for all my machines.

So far, I've been managing most of my data and workspaces with replicated Git repositories. I have scripts that allow me to maintain roaming profiles across my machines (almost) seamlessly, and these scripts try to ensure that these profiles are consistently replicated. My profiles include things like dot files (.vimrc, .screenrc, etc.), startup scripts, tools, workspaces, repositories, and other odds and ends.

Because I tend to be ultra-paranoid about security and reliability, the replicas are encrypted and distributed across different machines in different locations. For encryption, I use ecryptfs on Linux machines, and FileVault on the Mac.

Anyhow, this week I lost my Mac to a hardware failure, and my co-located Linux machine to a service-provider dismantling. That left me with one replica... just waiting to fail.

I decided that I needed another replica, but didn't want to pay for, or have to setup another co-located server. After spending some time researching various online-backup providers, I decided to go with Amazon's S3 service.

I chose S3 because - it's cheap, it's tried and tested, it's built on an internal distributed and replicated database, and there are some great tools that work with it.

Brackup

Brackup, by Brad Fitzpatrick, is one of those tools. It allows you to make encrypted incremental backups to S3, without a lot of hair-pulling or teeth-gnashing.

To get Brackup running on your machine, you need to have GPG, Perl 5, and the Net::Amazon::S3 Perl module installed. On the Mac, you also need to get MacPorts.

Installation

Most modern distributions come with Perl 5 pre-installed, but not with GPG. The package name you want on both MacPorts and Ubuntu, is gnupg.

The first thing you need to do, if you don't already have a GPG key, is to generate one.

$ gpg --gen-keys

If you need to backup multiple machines, export your public key to a text file, and import it on the other machines.

hostA$ gpg --export -a "User Name" > public.key
hostA$ scp public.key hostB:/tmp
hostB$ gpg --import /tmp/public.key

Remember that all your backups will be encrypted with your public key, so if you lose your private key, the only thing you can do with your backups is generate white noise. Export your private key and save it in a safe place. (I suggest VexCrypto.)

$ gpg --export-secret-key -a "User Name" > private.key

Now that you have your keys setup, download and install Brackup. The easiest way to do this is by using the cpan tool.

$ sudo cpan Net::Amazon::S3
$ sudo cpan Brackup

Note that it's better (and way faster) to use your distribution's package for Net::Amazon::S3. On Ubuntu the package is libnet-amazon-s3-perl, and on MacPorts, the package is p5-amazon-s3.

Configuration

Once this is done, you can generate a template configuration file by typing in brackup on the command line. This file is stored in $HOME/.brackup.

$ brackup
Error: Your config file needs tweaking.  I put a commented-out template at: /home/muthanna/.brackup.conf

brackup --from=[source_name] --to=[target_name] [--output=]
brackup --help

Edit the configuration file and create your sources and targets. You will likely have multiple sources, and one target. Here's a snip of my configuration:

[TARGET:amazon]
type = Amazon
aws_access_key_id  = XXXXXXXXXXX
aws_secret_access_key = XXXXXXXXXXXXXX
keep_backups = 10

[SOURCE:mac_repos]
path = /Users/0xfe/Local
chunk_size = 5m
gpg_recipient = 79E44165
ignore = ^.*\.(swp|swo|hi|o|a|pyc|svn|class|DS_Store|Trash|Trashes)$/

[SOURCE:mac_desktop_books]
path = /Users/0xfe/Desktop/Books
gpg_recipient = 79E44165
ignore = ^.*\.(swp|swo|hi|o|a|pyc|svn|class|DS_Store|Trash|Trashes)$/

[SOURCE:mac_desktop_workspace]
path = /Users/0xfe/Desktop/Workspace
gpg_recipient = 79E44165
ignore = ^.*\.(swp|swo|hi|o|a|pyc|svn|class|DS_Store|Trash|Trashes)$/

The configuration keys are pretty self explanatory. I should point out that gpg_recipient is your public key ID, as shown by gpg --list-keys.

$ gpg --list-keys
/Users/0xfe/.gnupg/pubring.gpg
-----------------------------------
pub   2048R/79E44165 2010-06-24
uid                  My Username <snip@snip.com>
sub   2048R/43AD4B72 2010-06-24

For more details on the various parameters, see The Brackup Manual.

Start a Backup

To backup one of your sources, use the brackup command, as so:

$ brackup -v --from=mac_repos --to=amazon

If you now take a look at your AWS Dashboard, you should see the buckets and chunks created for your backup data.

Notice that brackup creates an output file (with the extension .brackup) in the current directory. This file serves as an index, and maintains pointers to the S3 chunks for each backed-up file. You will need this file to locate and restore your data, and a copy of it is maintained on S3.

Restoring

"Test restores regularly." -- a wise man.

To restore your Brackup backups, you will need to have your private key handy on the machine that you're restoring to. Brackup accesses your private key via gpg-agent.

$ sudo port install gpg-agent
$ eval $(gpg-agent --daemon)

The brackup-restore command restores a source tree to a path specified on the command line. It makes use of the output file that brackup generated during the initial backup to locate and restore your data. If you don't have a local copy of the output file, you can use brackup-target to retrieve a copy from S3.

$ brackup-restore -v --from=mac_repos-20100624.brackup \
  --to=/Users/0xfe/temp/mac_repos --all

You will be prompted for you AWS key, your AWS secret key, and your GPG private key passphrase. Make sure that that the restore completed successfully and correctly. Comparing the SHA1 hashes of the restored data with those of the original data is a good way to validate correctness.

Garbage Collection

You will need to prune and garbage collect your data regularly to keep backups from piling up and using up space in S3. The following commands delete old backed up chunks based on the keep_files configuration value of the target.

$ brackup-target amazon prune
$ brackup-target amazon gc

That's all folks! Secure, on-line, off-site, incremental, buzz-word-ridden backups. Code safely!

On Parsing and Licenses

2010-06-21T14:12:00.000-04:00

So I spent this weekend rewriting the VexTab parser. The original version, though it served its purpose as a quick prototype for the language, was severely limited due to it being built primarily out of regular expressions.

The new parser uses a recursive-descent algorithm, and fully supports the original grammar. Adding new syntactic elements to the language is now simple, as is adding support for more complex grammars.

Some new features I added to the language are support for slides, hammer-ons, pull-offs, and tapping. Here's a blues lick written in VexTab:

Blues Lick in VexTab

Some readers have asked me about durations and how to specify rhythms in VexTab. Although the VexFlow core has full support for durations and timing, I still need a good way to represent them in the language. I'm open to ideas here if you have any.

Enter TabDiv

I also spent this weekend working on the release of the first VexFlow-based product: TabDiv. TabDiv lets you easily embed guitar tablature into your website or blog.

After you've included the TabDiv .js and .css files in your HTML document (or blog template), you can add tabs by simply creating DIV elements and setting the class to vex-tabdiv.

You can get TabDiv here: http://vexflow.com/tabdiv/index.html.

Why not Open-Source?

I'm no stranger to open-source. I've been writing, maintaining, and contributing to open-source software for over a decade.

Although I hope to eventually open-source all the VexFlow source code, I'm going to hold off on it until I figure out where I want to take this product. I've invested a lot of time and effort into making VexFlow a fast high-quality renderer, and I'd like to find a way to cater to both a commercial-audience, and the open-source community.

So, how does one find and maintain this delicate balance? Do I completely open-source it? Should I keep it closed and charge for it? Dual-license maybe?

Benchmarking VexFlow

2010-06-17T15:01:00.000-04:00

I have about 340 tests now for VexFlow, and one of the things I find really impressive is the speed at which browsers currently load, execute, and render web-pages.

Since the code exercises the browser on a few different dimensions (heavy JavaScript, lots of DOM manipulation, a few new HTML5 features), I decided to pit the major browsers against each other and run a few benchmarks.

Test Suite on Chrome 5.0.375

I ran the 340 tests in a loop a 1000 times on each browser, and calculated the mean runtime in milliseconds. Here are the results:

Chrome 5.0.375: 754ms
Safari 4.0.4: 1118ms
Opera 10.53: 1511ms
Firefox 3.6.3: 3209ms

The difference between the Chrome and Firefox numbers is quite surprising.

I also ran some SVG vs. Canvas benchmarks and found that SVG was about 3 times slower than Canvas. This factor increased significantly as the number of elements in the SVG image grew. That said, SVG rendered much more consistently across the different browsers.

The test machine used was a dual-core MacBook Pro with a 2.53 GHz Intel Core 2 Duo processor and 4GB of DDR3 RAM.

Fonts, Tablature, SVG, and a Demo

2010-06-13T21:37:00.000-04:00

This was a pretty productive weekend. I got a lot working, and a lot to show off.

First, a credit to Simon Tatham, who created the awesome Gonville font, which I use for the renderer. Before finding Gonville, I tried to draw many of the glyphs myself and suffice to say, it didn't work out too well.

Gonville by Simon Tatham

Thank you Simon for creating this brilliant work of art!

This week was all about the tablature. First, I added support for bend-and-release.

Then, I added support for soft and harsh vibratos.

I added support for custom note annotations.

There are a lot of things you can do with note annotations.

I also added full support for SVG. Yep, full support. With a little help from raphael.js, it was actually pretty straightforward to implement. I created a RaphaelContext class that implements the HTML5 Canvas API, and delegates all the drawing calls to Raphael. So now, the library uses HTML5 Canvas by default, unless you explicitly include the Raphael JavaScript library in your script sources.

I created the beginnings of simple tablature language to render guitar tab. It's called VexTab and it's very very alpha. Here's an example:

Anyhow, all this while you've been seeing screenshots of rendered notation, and no real HTML5-based demos. So, this time, I put up a new demo. All JavaScript. All SVG. Here it is:

A VexFlow Demo: The VexTab Tutorial Page

Hope you like it, and keep those comments coming.

On Beams

2010-06-07T13:37:00.000-04:00

Beams are interesting. Engraving rules for beams are extremely inconsistent. In essence, the ideal rendering involves striking a balance between the direction of the music, the angle of the beam, and the length of the stems. You don't want beams whose absolute slopes are too high, and you also don't want to compromise on the slopes too much by making the stems too long.

There is one well-known rule, however: Never shorten a stem.

Beams on Both Voices

The algorithm I currently use to render beams seems to work pretty well. I use an approach where I iteratively update the slope and y-shift of the beam, based on the height of each stem.

In retrospect, this algorithm seems pretty obvious, but I really had to experiment a fair bit to derive it. The first few beams were just all over the place.

Beam Confusion

More Beam Confusion

My debugging code places colored dots at various control points to help me visualize the errors better. It took me a bit of effort before I got to the rendering below. The beams still aren't shifted far enough to both accommodate for the stem heights.

Close... But Still Wrong!

After ironing out the iterative algorithm, I got this:

Decently Rendered Beams

Perfect! The stems are only extended where necessary, and the angles of the beams adequately reflect the direction of the music.

Thanks to the context-based architecture, note-modifiers such as accidentals don't disturb beam positioning.

Beam With Accidentals

That said, something about the above rendering does not look right to me. The group of eighth notes don't look like they're positioned very evenly. If anyone knows how to render beamed notes with accidentals correctly, please let me know.

Anyhow, I also got slides and ties working again. These were gone after the rewrite, and I had to work them in using the new framework.

Tab Slides

Hammer-Ons

These actually make use of annotation-contexts which help determine the position of the annotation text above the stave.

Random Annotation

I'm still a bit unsure of how to render ties across different note steps, with accidentals. What I have now looks like this:

Chord Ties

Although this is a really uncommon case, it would be nice if there were a generic way to deal with it. Thoughts? Ideas?

That's all for now folks, and thanks very much for the comments. Keep 'em coming!

The Thing about Accidentals...

2010-05-23T17:40:00.000-04:00

...is that they can be a real pain.

Last weekend, I mentioned that I threw away most of the layout and formatting code, which I started rewriting from scratch. Well, this weekend I threw away everything else, and started abstracting away many of the general properties that are shared between different types of notation.

Testing Note-Head Displacement

One of the big design flaws in the previous version was the coupling of notes and tabs. I essentially had a single Note class that encapsulated everything about a specific note, including the string/fret information, attached lyrics, attached accidentals, and other modifiers. This class had a big render() method that drew everything (the tabs, the accidentals, etc.) in one go.

This made the code hard to follow, hard to test, and very hard to add features to.

In the new version, I have different classes for different types of staves, notes, accidentals, and other modifiers, which are managed by a hierarchy of contexts. This means that adding support for a new type of instrument, say a Didgeridoo, is a matter of creating a new DidgeridooStave class to render its stave, and maybe a DidgeridooNote class to render any Didgeridoo notational symbols.

Yes, even the tests were rewritten. I wrote about 150 tests. All new, all fresh. It wasn't much fun, but I do have a significant level of confidence in the code.

So what did I gain from all of this? Just the following...

Accidentals are tricky. In the image below, notice how the flat is nicely shifted to make room for the flat.

Rendering Accidentals

And this is how it deals with a chord on steroids.

Accidentals Line Up Correctly

I tried hard to break it.

Whoa there, Fella!

It gets a bit confused when you bring in a second voice, but still quite respectable.

Accidentals with Multiple Voices

The formatter doesn't just work with accidentals. It works with all kinds of modifiers, such as bends. Last week, I showed you how the modifier handled multiple bent notes on the same chord. Below, notice how full and half bends share the text annotation area. (This excited me a wee bit.)

Bends with Text Annotations

The new layout code allows for justification. Below, the top stave is rendered without justification, while the bottom two are justified to different widths.

Layout Justification

The justification works across staves too, so you can have multiple staves playing different parts, all lined up in the notation.

Justification across Staves

That's all I have to show for this week, folks! Since this is all new code, there are a few things that I lost support for, in particular: beams and ties. Hopefully it'll all be back next week.

Cleaning up the Cruft

2010-05-16T21:53:00.000-04:00

I spent most of this weekend cleaning up the HTML5 music notation code - tests, refactoring, style fixes, etc. While doing this, I threw away lots of cruft, and started rewriting almost all the layout and formatting code. After looking at and studying lots of scores and tabs, it turned out that I really had to rethink the architecture of the layout management pieces, to allow for the correct formatting and placement of modifiers, accidentals, multi-voice note-heads etc.

Hammer-ons

I now have a much nicer design that should accommodate for these intricacies nicely, and am part way through implementing it. The design involves maintaining separate contexts for groups of Tickables (which is an abstraction for anything with a duration, such as notes, tabs, lyric-pieces, or chords) and Modifiers (an abstraction which includes accidentals, dots, bends, etc.) Higher-level formatters can be plugged in that work within these contexts to size, kern, and position the glyphs.

On the testing front, I have about 75 tests in, which its still barely enough to test the different scenarios and edge cases that occur in musical notation. I tend to add the tests for different components as I have a clearer picture of what the API looks like, primarily to avoid having to incessantly rejiggle the test code. One thing's for sure - I love QUnit, which is jQuery's JavaScript unit-testing suite. It's functional, elegant, and extremely simple to use.

All you need to do is write your tests, and QUnit takes care of managing, running, and reporting.

Anyhow, I do have a few things to show for all of this. First, is the support for note bends in tablature. Notice how the lower bend is pushed further to the right? This is because they're in the same ModifierContext.

String Bends

I also added slides, hammerons, and pulloffs.

Slides

I fixed the size of the accidentals. (I hope this is correct.)

And finally, note-heads are correctly displaced for notes that are right next to each other.

Displaced Note Heads

That's all for this week, folks!

A Question of Formats

2010-05-12T08:13:00.000-04:00

Firstly, a big Thank You to everyone for the comments and advice to my previous post.

I went through almost all of the links that were posted, and glanced over the various options for languages, rendering, and formatting.

Question 1. Canvas or SVG?

This is actually a no-brainer. The library was designed such that alternate rendering backends could be easily plugged in. I went over some of the SVG specification documents, and it appears (at first glance) that I could add SVG support pretty trivially.

So, the answer to this is: Yes, there will be SVG support.

Now, that said, I had two primary goals for this project. One was the ability to render pleasing-to-the-eye musical scores, and the other was to be able to support interactive scores (to allow for building tools such as score editors.)

These goals are potentially conflicting, because certain aspects of rendering perfect scores are actually computationally expensive, requiring multiple passes on the notation. This could affect the snappy-factor of interactive scores. There's also the question of whether SVG is flexible enough for animations and interactive graphics.

Anyhow, I'll dig into this some more and report my findings. Worst case, SVG will be used for rendering static scores, and Canvas for interactivity.

Question 2. MusicXML or ABC Notation or JSON or Lilypond?

I eschew XML. It's clunky. It's difficult to parse. It's difficult to read. It makes my head hurt. So I'll let someone else build a MusicXML importer for the API. (Yes, I do realize that SVG is XML too, but generating XML is far simpler than parsing it.)

ABC Notation. Love it. It's going in. I'll have to figure out a way to lump in easy tablature support.

JSON. This is a good idea in theory, but getting the schema right is the tricky part. I'm going to hold off on this for now and defer to the API.

Lilypond. Although the generated scores are beautiful, I'm not particularly a fan of the TeX-based language. Like I mentioned before, I'd like to be accessible to non-geeks.

Nevertheless, I'm working on cleaning up the API such that it is friendly to compiler-writers, and interested parties can write their own front-ends. A fringe benefit of a compiler-friendly API is the ability to run layout and positioning algorithms on top of generated scores to fine tune the presentation. Kind of like a -O3 for music notation.

Note that these opinions aren't very strong (except for maybe the MusicXML one), and I'm open to other thoughts and suggestions you may have. So... suggest away.

Music Notation with HTML5 Canvas

2010-05-11T14:16:00.001-04:00

I spent a few weekends trying to scratch an itch. While looking for online tools to create and render music notation, I was mildly disappointed. The only real options were crummy flash based sites or clumsy server-side image renderers. Neither of these were particularly appealing.

So I pulled up my sleeves, and cooked up a full-fledged JavaScript API to engrave musical notation directly in the browser with the HTML5 Canvas element.

Here's a demo: HTML5 Music Notation Demo

The library has no external dependencies, and all the glyphs, scores, beams, ties, etc. are positioned and rendered entirely in JavaScript.

One of the cool things about this is that I can now build interactive music sheets that respond to user events like score editors.

So here are all the features I have so far.

1. Basic staff and chord support.

2. Accidentals and beams.

3. Support for all note values with correct rhythmic positioning.

4. Support for rests, ties, and multiple voices. (Note the positioning of the notes.)

5. Support for guitar tablature.

6. Multiple voices in both staff and tab scores.

7. Broken bars, odd-timings, custom glyphs, basic interactivity, and a full suite of unit tests (I love QUnit).

I have a fair bit of work to do before I can make it available. In particular, I want to build a simple language that allows users to easily create scores. Something along the lines of the following:

score {
  title: Hip Tune
  artist: Hip Person

  bar { v8 C4 D4 E4 F4 (C4 E4 G4) } 
  bar { v8 C4 D4 E4 F4 (C4 E4 G4) } repeat 3
}

The above is just an idea - I haven't really given it much thought. But the intent is to make the language easy to read and accessible to non-geeks. I'm open to suggestions related to what the language should look like.

Let me know what you think.

Desktop Notifications with WebKit

2010-04-21T10:50:00.006-04:00

Chrome now supports desktop notifications using WebKit's webkitNotifications API. (Try the demo.)

Why is this awesome? Because it gives online tools like e-mail clients, calendering software, task managers, monitoring systems, etc. an elegant and consistent way to notify users without having to resort to annoying and invasive hacks like window.alert.

Stacked Desktop Notifications

Although the API is sparsely documented, it is simple and flexible and supports features such as domain based permissions, stacking of notification windows, embedded HTML, etc.

To use desktop notifications in your applications, you need the following three API calls:

window.webkitNotifications.requestPermission(callback) - Request access to Desktop Notifications for this domain.
window.webkitNotifications.checkPermission() - Returns 0 if this domain has Desktop Notification access.
window.webkitNotifications.createNotification - Returns a popup notification instance, which you can display by calling show() on it.

A straightforward way to check for Desktop Notification support is by testing if window.webkitNotifications is defined. Take a look at Notifier.HasSupport() in the API wrapper below.

When you request permission with requestPermission(callback), Chrome slides out a small permissions dialog immediately above the page. (Click the image below to magnify.)

Permissions Dialog for Desktop Notifications

In the above image, licking "Allow" tells Chrome that all pages hosted on 0xfe.muthanna.com can send notifications to the desktop. You can remove this access by clicking the "Options" link on any notification from a site.

Here's a simple wrapper to the API (which is embedded in the demo below):

function Notifier() {}

// Returns "true" if this browser supports notifications.
Notifier.prototype.HasSupport = function() {
  if (window.webkitNotifications) {
    return true;
  } else {
    return false;
  }
}

// Request permission for this page to send notifications. If allowed,
// calls function "cb" with "true" as the first argument.
Notifier.prototype.RequestPermission = function(cb) {
  window.webkitNotifications.requestPermission(function() {
    if (cb) { cb(window.webkitNotifications.checkPermission() == 0); }
  });
}

// Popup a notification with icon, title, and body. Returns false if
// permission was not granted.
Notifier.prototype.Notify = function(icon, title, body) {
  if (window.webkitNotifications.checkPermission() == 0) {
    var popup = window.webkitNotifications.createNotification(
      icon, title, body);
    popup.show();
    return true;
  }

  return false;
}

Take a look at the WebKit Desktop Notification Demo for a working demo. [ View Source ]

My Coding Font

2010-04-16T10:51:00.000-04:00

A few readers have asked me what coding font I use. It's Inconsolata and it's wickedly awesome.

Inconsolata

Mad props to Raph Levien for this elegant, easy-on-the-eyes, monospaced, beauty.

Inconsolata is distributed under the Open Font License, and is available for download on Raph's Inconsolata font page.

Improved Git-enabled Shell Prompt

2010-04-15T00:31:00.002-04:00

In my previous post, I wrote about how you could bolster your shell prompt with Git status information.

Today, I added two more Git indicators that I find extremely useful while working on shared code.

The first is unmerged branches, which is the list of local branches that are not yet merged into the current branch.

# Returns "|unmerged:N" where N is the number of unmerged local and remote
# branches (if any).
function parse_git_unmerged {
  local unmerged=`expr $(git branch --no-color -a --no-merged | wc -l)`
  if [ "$unmerged" != "0" ]
  then
    echo "|unmerged:$unmerged"
  fi
}

The second is unpushed branches, which is the list of remote branches that are not synced to the local HEAD.

# Returns "|unpushed:N" where N is the number of unpushed local and remote
# branches (if any).
function parse_git_unpushed {
  local unpushed=`expr $( (git branch --no-color -r --contains HEAD; \
    git branch --no-color -r) | sort | uniq -u | wc -l )`
  if [ "$unpushed" != "0" ]
  then
    echo "|unpushed:$unpushed"
  fi
}

I now have the perfect git-enabled shell prompt!

Git-enabled Shell Prompt

The code to the full prompt is available here: prompt.sh (also see evilgit.sh for the git support functions). Enjoy!

Adding Git Status Information to your Terminal Prompt

2010-04-13T14:41:00.001-04:00

If you're a heavy git user, you'll find this simple prompt customization quite useful. It adds the name of the current branch to the shell prompt along with an asterisk as a dirty indicator. It also displays the number of states you have stashed away with git stash.

Start by defining the following functions and placing it into your shell profile (e.g., .bashrc).

# Returns "*" if the current git branch is dirty.
function parse_git_dirty {
  [[ $(git diff --shortstat 2> /dev/null | tail -n1) != "" ]] && echo "*"
}

# Returns "|shashed:N" where N is the number of stashed states (if any).
function parse_git_stash {
  local stash=`expr $(git stash list 2>/dev/null| wc -l)`
  if [ "$stash" != "0" ]
  then
    echo "|stashed:$stash"
  fi
}

# Get the current git branch name (if available)
git_prompt() {
  local ref=$(git symbolic-ref HEAD 2>/dev/null | cut -d'/' -f3)
  if [ "$ref" != "" ]
  then
    echo "($ref$(parse_git_dirty)$(parse_git_stash)) "
  fi
}

Then customize your prompt by adding $(git_prompt) to the PS1 environment variable, for example:

export PS1="\u@\h:\w $(git_prompt)$ "

Here's what my prompt looks like in action:

And, here is the code to my prompt. (It relies on the functions defined above.)

# A fancy colorful prompt
function color_prompt
{
  local none="\[\033[0m\]"

  local black="\[\033[0;30m\]"
  local dark_gray="\[\033[1;30m\]"
  local blue="\[\033[0;34m\]"
  local light_blue="\[\033[1;34m\]"
  local green="\[\033[0;32m\]"
  local light_green="\[\033[1;32m\]"
  local cyan="\[\033[0;36m\]"
  local light_cyan="\[\033[1;36m\]"
  local red="\[\033[0;31m\]"
  local light_red="\[\033[1;31m\]"
  local purple="\[\033[0;35m\]"
  local light_purple="\[\033[1;35m\]"
  local brown="\[\033[0;33m\]"
  local yellow="\[\033[1;33m\]"
  local light_gray="\[\033[0;37m\]"
  local white="\[\033[1;37m\]"

  local current_tty=`tty | sed -e "s/\/dev\/\(.*\)/\1/"`

  local u_color=$purple
  id -u > /dev/null 2>&1 &&           #Cross-platform hack.

  if [ `id -u` -eq 0 ] ; then
    local u_color=$yellow
  fi

  PS1="$light_blue> $current_tty $u_color\u$brown@${purple}\
    \h$brown:$light_blue\w\n$light_blue> $light_red\$\
    ? $cyan\$(git_prompt)$brown"'\$'"$none "

  PS2="$dark_gray>$none "
}

That's all folks! I'm interested in hearing about any useful shell prompt customizations that you have.

My Vim Configuration

2010-04-12T19:44:00.002-04:00

I've posted a number of articles on configuring Vim, and a few readers have asked me to post my complete .vimrc file.

My configuration includes:

Incremental search
Status bar at the bottom of the screen
Code folding based on indentation level
Syntax highlighting
Spell checking
Digraphs for whitespace characters
Signature abbreviations
Incremental search
MacVim customizations
... and more.

So, without further ado.

" VIM Configuration - Mohit Muthanna

" Enable syntax highlighting.
syntax on

" Do awesome stuff on MacVim
if has("gui_macvim")
" Disable toolbar on MacVim
set go-=T

" MacVim font and color scheme
set guifont=Inconsolata:h13
colorscheme torte
endif

" Enable spell checking. For source code, it only checks comments.
" set spell spelllang=en_us

" Set title on X window
set title

" Hide buffer instead of abandoning when unloading
set hidden ruler wmnu

" Set GUI font and options
" set guifont=Monospace 8
" set guioptions=agimrLt
" set imi=0

" I'm usually on a light-on-dark terminal
set background=dark

" Live incremental search
set incsearch

" Highlight current line (Vim 7)
" set cursorline

" Tabs and indentation. Yes, I like 2-space tabs.
set tabstop=2
set shiftwidth=2
set expandtab
set autoindent
filetype indent on

" Allow extended digraphs
set encoding=utf-8

" Show status line (help statusline)
set statusline=%<%2*%f%h%1*%m%2*%r%h%w%y\ %*%{&ff}\ %=\ col:%c%V\ asc:%B\ pos:%o\ lin:%l\,%L\ %P
set laststatus=2

" Set status line colors
highlight ModeMsg cterm=bold ctermfg=cyan ctermbg=black
highlight StatusLine cterm=bold ctermfg=brown ctermbg=blue
highlight StatusLineNC cterm=bold ctermfg=black ctermbg=green

" Filename in white.
highlight User2 cterm=bold ctermfg=gray ctermbg=blue

" Modified flag on statusline.
highlight User1 ctermfg=red ctermbg=blue

" Highlight trailing whitespace and tab characters. Note that the foreground
" colors are overridden here, so this only works with the "set list" settings
" below.
autocmd ColorScheme * highlight ExtraWhitespace ctermfg=red guifg=red
highlight ExtraWhitespace ctermfg=red guifg=red cterm=bold gui=bold
match ExtraWhitespace /\s\+$\|\t/

" Show tabs and trailing spaces.
" Ctrl-K >> for »
" Ctrl-K .M for ·
" Ctrk-K 0M for ●
" Ctrk-K sB for ▪
" (use :dig for list of digraphs)
set list listchars=tab:»»,trail:·

" I like to stick to lines under 80 columns
au BufWinEnter * let w:m2=matchadd('ErrorMsg', '\%>80v.\+', -1)

" Enable folding by indentation
" Use: zc, zo, zC, zO, zR, zM
" Ctrl-K .3 for ⋯
set foldmethod=indent
highlight Folded ctermfg=red
highlight FoldColumn ctermfg=white
set fillchars=fold:⋯

" My information
iab xdate =strftime("%Y/%m/%d %H:%M:%S")
iab xname Mohit Muthanna Cheppudira
iab xsigp Mohit Muthanna Cheppudira 
iab xsigw Mohit Muthanna Cheppudira 

" Strip trailing whitespace in whole file
func! StripTrailingWS()
%s/\s\+$//
endfunc
command! StripTrailingWS call StripTrailingWS()

This file is continually evolving, and you can always get the latest version here: .vimrc.

Digraphs in Vim

2010-04-11T09:46:00.007-04:00

Ever wondered how to use digraphs to insert characters such as ⇐ or ⅛ into text files with Vim?

Simple - use the key combination Ctrl-K followed by the two-letter digraph code directly in insert mode.

For example, Ctrl-K DE generates ∆ and Ctrl-K 23 generates ⅔.

For a list of all the available digraphs and their key codes, use the command ":dig".

Sample Digraph Codes

The ability to insert digraphs directly into the editor opens up a lot of possibilities for customization. For example, to make tabs and trailing whitespace characters visible in code, you can add something like this to your .vimrc.

" Show tabs and trailing spaces.
" Ctrl-K >> for »
" Ctrl-K .M for ·
" (use :dig for list of digraphs)
set list listchars=tab:»»,trail:·

Here's what it looks like:

Using Digraphs to see Whitespace Characters

Digraphs are fun. Vim is fun. Digraphs + Vim = ∏☺♣☆は℞ψ. For more on digraphs in Vim, visit the vim digraph page.

MacVim is Plain Awesome

2010-04-04T09:32:00.003-04:00

Every once in a while, dissatisfied with my current editor, I start scouring the web for an editor more Mac friendly. You know - an editor that respects conventional keyboard shortcuts, an editor that works predictably with the native copy-paste buffers, an editor that works with the mouse (even though I rarely use the mouse).

I want an editor that just feels right on the Mac.

And usually, after exploring popular editors like TextMate, TextWrangler, and jEdit, for the umpteenth time my dissatisfaction inevitably leads me back to Vim.

Not this time.

It's been about three months since I've been using MacVim, and I have two words for it - Awesome. Major kudos go out to Bjorne Winckler and the MacVim team for getting the Mac environment and releasing such a fantastic product.

What's so great about MacVim? Oh, only the following:

A full Vim implementation, that fully supports my .vimrc (including all my crazy plugins.)
Native support for tabs with conventional key-bindings (Cmd-T, Cmd-W, etc.) for managing and navigating tabs.
Supports the native OS X paste-buffer. You can select with the mouse, and copy it into the native paste-buffer with Cmd-C. You can also use Cmd-V to paste into the editor without losing formatting and without requiring "set paste".
"mvim filename" on the commandline spawns a new MacVim session (within an existing process, if any) in background mode. This helps you save significantly on superfluous terminal or screen sessions.
Supports the scroll-wheel and native pagination keys.
Shift-Cmd-F for fullscreen mode is the shyza.
The toolbar is simple and customizable, and the application menus simplify the process of spell-checking, code-folding, visual-diffing, etc.
The Print menu-item (or pressing Cmd-P) converts the current buffer to a PDF document, and brings it up in Preview.
It's pretty to look at and extremely usable.

Gratuitous screenshot:

You can get MacVim at http://code.google.com/p/macvim. Install it, toy with it, and tell me what you think.

Meditation Timer

2010-02-28T13:08:00.004-05:00

For a while now, I've been relying on audio files for use as meditation timers. These files essentially consist of a recorded bell in the beginning, followed by a duration of silence, and another bell at the end. There are many of these available on the web, and are not bad. The problem is that you're limited to the duration of the files available, i.e., if you want to meditate for 45 minutes, then you need a 45-minute long audio file.

Mildly frustrated by this, I spent some time this morning writing an on-line meditation timer. Simply set the duration, and click Start. You should hear a bell when the timer begins and ends.

Here it is: Online Meditation Timer.

Using Google App Engine and JQuery, it took me about 45 minutes to build this. That includes the time it took to prettify the site and type in this blog post. Gotta love simple, well-designed application frameworks!

The Mandelbrot Set in JavaScript

2009-12-26T16:56:00.009-05:00

JavaScript turns out to be a great language for toying with graphics and visualization. This morning, I spent a few hours learning about the Mandelbrot set and trying to code up a working implementation. The link below is one of the fruits of my labor:

Mandelbrot Set Generator

Mathematically, the Mandelbrot set is the set of points in the complex plane generated by iterating through the formula z = z^2 + c. For different initial values of c, the iteration can either produce a bounded sequence, or tend to infinity. Plotting the graph is a matter of placing a black dot for the values that generate a bounded sequence.

The next part of the problem is figuring out how to test for unbounded sequences. A good approximation can be reached by running through n iterations and quitting if the magnitude of z exceeds 2. The magnitude of a complex number with real part a and imaginary part b is sqrt(a^2 + b^2). For simple graphs, a reasonable value for n is 100.

Here's what a simple Mandelbrot set grapher in JavaScript looks like:

for (var x = 1; x < this.width; x++) {
    for (var y = 1; y < this.height; y++) {
      var count = 0;
      var size = 0;
      var cx = xcorner + ((x * zoom) / this.width);
      var cy = ycorner + ((y * zoom) / this.height);

      var zx = 0;
      var zy = 0;

      while (count < 100 && size <= 4) {
        count += 1;
        temp = (zx * zx) - (zy * zy);
        zy = (2 * zx * zy) + cy
        zx = temp + cx;
        size = (zx * zx) + (zy * zy);
      }

      this.Plot(x, y, count); // count serves as a good color hint.
    }
  }

By setting the xcorner, ycorner, and zoom variables, the above code allows you to pan across and zoom into various points in the set. To accommodate for pretty visualizations, you can use count to determine the color of the pixel.

A barebones implementation is available here: mandelbrot.js. Although it is not a very efficient implementation, it is very simple, and if you squint hard enough, you can see how the code relates to the visualization.

The Mandelbrot Set Generator is a harness I built with mandelbrot.js. Play with the parameters and let me know if you find anything interesting. It also turns out to be a good browser speed test.

To learn more about the Mandelbrot Set, see the Wikipedia article on the Mandelbrot Set.

Google Chrome Poster from Source Code

2009-12-24T11:56:00.008-05:00

This holiday weekend, I decided to compose the Google Chrome logo using the browser's own source code. I used a combination of Ruby, ImageMagick, and a heavily hacked PDF library to generate this poster.

This is the icon that I used:

Here's what it looks like zoomed in:

And zoomed in some more:

Download the PDF in all it's vectorized glory. (Approx 1.5MB. Please don't link directly to the poster.)

Take it to your favourite print shop. Since it is based on vector graphics, it can be scaled up trivially without losing quality.

Happy Holidays!

P.S. If you ask me nicely, I might send you a 24-page letter-sized split of the poster so you can print it at home. (At nearly 50MB, it's too big for me to host here.)

Vex Crypto

2009-10-26T17:59:00.003-04:00

So, I was looking a place to store some of my private data, such that I could access it conveniently when I needed to. By "conveniently", I mean over a web browser at a friend's place, or in an Internet cafe.

It turns out that outside of setting up an encrypted filesystem on a remote server (or doing something similarly convoluted), there really aren't any other options.

The type of information that I need to store is usually of the personal kind, e.g., passport numbers, emergency contacts, financial or health information, etc. Basically, I'd like to have easy access to any information that comes in handy during an emergency but can't be easily carried around.

I also really wanted to do something cool with Google App Engine and jQuery.

So, I wrote this: Vex Crypto (you need a Google account to log in.)

Vex Crypto allows you to store snippets of encrypted text in the Google "cloud". It performs all the encryption and decryption in JavaScript (inside the browser), so that no plain-text information is stored on disk or transferred over the wire.

This essentially means that even people who have access to the stored data will not be able to decode it without the "decryption password".

Try it out and let me know what you think.

Everybody Loves Colors

2009-09-25T19:46:00.005-04:00

Colors on terminal scripts are fun. They're also easy.

class Colors:
  ESC = "\033["
  PURPLE = ESC + "95m"
  GREEN = ESC + "92m" 
  YELLOW = ESC + "93m"
  RESET = ESC + "0m"

print Colors.YELLOW + "Warning: Colors enabled."
print Colors.RESET

Abbreviations in Vim

2009-04-11T19:09:00.005-04:00

There are a few bits of text that are common to almost every file I edit with Vim. One of them is, of course, my name. The others are my e-mail address, and the date.

Vim allows you to define simple text abbreviations to make entering such strings super-easy. Here's a snip of my .vimrc.

" Some handy abbreviations.
"
" Insert date.
iab xdate =strftime("%Y/%m/%d %H:%M:%S")

" What's my name?
iab xname Mohit Muthanna Cheppudira

" My personal sig.
iab xsigp Mohit Muthanna Cheppudira 

" My work sig.
iab xsigw Mohit Muthanna Cheppudira

With the above in my Vim configuration, the text xdate gets auto-replaced to today's date.

Slick.

Simple Code Folding in Vim

2009-04-05T11:12:00.006-04:00

I've been on a Vim customization frenzy the last few days, and I just discovered an uber-cool feature: code folding. Folding is the process of rolling up a block of lines in the buffer, to a single line.

Here's what folded code looks like:

So, to unfold a block, simply move the cursor to the block and hit "zO". (All the fold commands begin with "z"). Here's what an unfolded block looks like:

There are many ways to fold code, but the simplest way to enable it is by setting the foldmethod option to indent. This folds code based on its indentation.

If you're looking for syntax-aware folding, you can set fold-method to syntax. This generally takes a little more tweaking to get the right fold behaviour.

Add the following to your .vimrc, to get simple straightforward indentation-based code folding:

" Enable folding by indentation
" Use: zc, zo, zC, zO, zR, zM
" Ctrl-K .3 for ⋯
set foldmethod=indent
highlight Folded ctermfg=red
highlight FoldColumn ctermfg=white
set fillchars=fold:⋯

For more information about code folding, and to get a list of all the commands, see http://www.vim.org/htmldoc/usr_28.html.

Generating Circular Primes

2009-03-29T20:12:00.015-04:00

I've been having way too much fun with Project Euler (and Haskell) lately. Below is a listing of my solution to problem 35: "How many circular primes are there below a million?"

It solves in about 2 seconds on my laptop (using -O2). This isn't great, but not bad given that the only optimizations in the code are: a memoized prime number generator, and the use of Data.Set for quick primality tests.

-- Project Euler: Problem 35
--
-- The number, 197, is called a circular prime because all rotations of the
-- digits: 197, 971, and 719, are themselves prime.
--
-- There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37,
-- 71, 73, 79, and 97.
--
-- How many circular primes are there below one million?

import Data.Set (Set)
import qualified Data.Set as Set
import System (getArgs)

-- How many circular primes do you want?
limit = 1000000

-- Memoized prime number generator.
primes :: [Integer]
primes = 2 : 3 : 5 : filter (not . hasFactor) [7..]
  where hasFactor n = any (divides n) $ takeWhile (<= lowestFactor n) primes
        divides n m = n `mod` m == 0
        lowestFactor = ceiling . sqrt . fromIntegral

-- Given an integer, return the number of digits in it.
digits :: Integer -> Int
digits n = ceiling $ logBase 10 $ fromIntegral (n + 1)

-- Rotate number right:
--   rotate 456 = 645
--   rotate 3498 = 8349
--
-- Note that this does not work for numbers that have zeroes in them. But
-- that's okay because any number with a zero in it is not a circular prime.
-- Also, right rotation catches the zero before it disappears into the 
-- significant digit.
rotate :: Integer -> Integer
rotate n = strip_last_digit + (last_digit * tens_place)
  where last_digit = n `mod` 10
        strip_last_digit = (n - last_digit) `div` 10
        tens_place = (10 ^ (digits n - 1))

-- Set of million primes. This enables fast lookup in isCircularPrime.
primeSet :: Set Integer
primeSet = Set.fromList $ takeWhile (< limit) primes

-- Returns True if number is prime.
isPrime :: Integer -> Bool
isPrime n = Set.member n primeSet

-- Returns True if the number is a circular prime.
isCircularPrime :: Integer -> Bool
isCircularPrime n = all isPrime $ take (digits n) $ iterate rotate n

-- Go.
main :: IO ()
main = print $ length $ filter isCircularPrime $ takeWhile (< limit) primes

So... how can I optimize this some more?

Project Euler

2009-03-28T17:30:00.001-04:00

I can't believe I never knew about this before. Project Euler is very addictive. You've been warned.

Tackling the Awkward Squad

2008-10-17T13:30:00.002-04:00

It's been a long time since I've blogged a new post.

Some of the time it's because I start a topic, and never finish it, leaving behind a mess of draft posts. But most of the time, it's because I have nothing interesting to say.

Today, I have something interesting to say:

Haskell is full of lazy-sugary-pure-functional goodness.

There. I said it.

If you have never used Haskell, now would be a great time to start. I'm not going to pimp it too much, because there's a huge community out there who are already doing that quite well.

Haskell will bend your mind. Haskell will make you feel young again. Haskell will save the cheerleader.

And if you have already been learning Haskell, and plan to do serious work with it, you need to know how to tackle the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls.

I'll defer to Simon Peyton Jones from Microsoft Research, Cambridge in his awesomely awesome paper: Tackling the Awkward Squad.

Scheduling on SMP Hardware

2007-02-10T14:50:00.008-05:00

Ever wondered how the Linux scheduler schedules a job on another processor, after the idle task has halted the CPU?

On x86 systems, the answer lies in InterProcessor Interrupts (IPI). An IPI is a type of custom interrupt that can be sent from one processor to another, using an Advanced Programmable Interrupt Controller (APIC).

One of the customers of IPIs happens to be the OS task scheduler, where a processor can be woken up after a task is added to it's per-processor run queue.

Let me add some context.

On a uni-processor machine, the idle task is scheduled when the OS has absolutely nothing to do. The main purpose of this task is to shut down the CPU by first making sure that interrupts are enabled, and then sending the hlt instruction. This happens in the default_idle() function within arch/i386/process.c, via a call to safe_halt().


100 void default_idle(void)
101 {
102         local_irq_enable();
103
104         if (!hlt_counter && boot_cpu_data.hlt_works_ok) {
105                 clear_thread_flag(TIF_POLLING_NRFLAG);
106                 smp_mb__after_clear_bit();
107                 while (!need_resched()) {
108                         local_irq_disable();
109                         if (!need_resched())
110                                 safe_halt();
111                         else
112                                 local_irq_enable();
113                 }
114                 set_thread_flag(TIF_POLLING_NRFLAG);
115         } else {
116                 while (!need_resched())
117                         cpu_relax();
118         }
119 }

The safe_halt() function, is not really a function, but a preprocessor macro that calls the sti and hlt instructions, and is defined in include/asm-i386/system.h.

#define safe_halt()             __asm__ __volatile__("sti; hlt": : :"memory")

Of course, since interrupts are enabled, the CPU is immediately woken up when an interrupt is received. This could be from any IO device, the timer, or even another processor. On an idle machine, the timer interrupt vector gates into the scheduler, which may examine it's per-processor run-queues, and try to find a task to execute. If nothing is found, the idle task gets rescheduled.

This works well on uniprocessor systems, but on an SMP system, the timer interrupt only wakes up the primary CPU. So what happens when a new task is forked, and the scheduler decides that it needs to run on another CPU?

The answer lies within the scheduler code (kernel/sched.c), in the resched_task() function.


820 #ifdef CONFIG_SMP
821 static void resched_task(task_t *p)
822 {
823         int cpu;
824
825         assert_spin_locked(&task_rq(p)->lock);
826
827         if (unlikely(test_tsk_thread_flag(p, TIF_NEED_RESCHED)))
828                 return;
829
830         set_tsk_thread_flag(p, TIF_NEED_RESCHED);
831
832         cpu = task_cpu(p);
833         if (cpu == smp_processor_id())
834                 return;
835
836         /* NEED_RESCHED must be visible before we test POLLING_NRFLAG */
837         smp_mb();
838         if (!test_tsk_thread_flag(p, TIF_POLLING_NRFLAG))
839                 smp_send_reschedule(cpu);
840 }
841 #else
842 static inline void resched_task(task_t *p)
843 {
844         assert_spin_locked(&task_rq(p)->lock);
845         set_tsk_need_resched(p);
846 }
847 #endif

As you can see there are two versions of this function, one for uniprocessor systems, and the other for SMP systems. On a uniprocessor, the task is rescheduled by setting the TIF_NEED_RESCHED flag, via a call to set_tsk_need_resched().

On a multiprocessor system, the same flag is set, and a check is made to see if the task should be running on a different processor from the current one. If not, it just returns, and lets the scheduler take care of rescheduling the task. Otherwise, it wakes up the target processor by calling the smp_send_reschedule() function.

The smp_send_reschedule() function (defined in arch/i386/kernel/smp.c) simply sends an IPI to the specified processor, by calling send_IPI_mask().


472 /*
473  * This function sends a 'reschedule' IPI to another CPU.
474  * it goes straight through and wastes no time serializing
475  * anything. Worst case is that we lose a reschedule ...
476  */
477 void smp_send_reschedule(int cpu)
478 {
479         WARN_ON(cpu_is_offline(cpu));
480         send_IPI_mask(cpumask_of_cpu(cpu), RESCHEDULE_VECTOR);
481 }

The send_IPI_mask() function uses the APIC to fire an interrupt off to the target processor. It calls send_IPI_mask_bitmask(), which in-turn programs the APIC using the functions in include/asm-i386/apic.h.


160 void send_IPI_mask_bitmask(cpumask_t cpumask, int vector)
161 {
162         unsigned long mask = cpus_addr(cpumask)[0];
163         unsigned long cfg;
164         unsigned long flags;
165
166         local_irq_save(flags);
167         WARN_ON(mask & ~cpus_addr(cpu_online_map)[0]);
168         /*
169          * Wait for idle.
170          */
171         apic_wait_icr_idle();
172                
173         /*
174          * prepare target chip field
175          */
176         cfg = __prepare_ICR2(mask);
177         apic_write_around(APIC_ICR2, cfg);
178                
179         /*
180          * program the ICR
181          */
182         cfg = __prepare_ICR(0, vector);
183                        
184         /*
185          * Send the IPI. The write to APIC_ICR fires this off.
186          */
187         apic_write_around(APIC_ICR, cfg);
188
189         local_irq_restore(flags);
190 }

The specific IPI-gate is defined as RESCHEDULE_VECTOR, and is installed by the smp_intr_init() function in arch/i386/kernel/smpboot.c.


1454 void __init smp_intr_init(void)
1455 {
1456         /*
1457          * IRQ0 must be given a fixed assignment and initialized,
1458          * because it's used before the IO-APIC is set up.
1459          */
1460         set_intr_gate(FIRST_DEVICE_VECTOR, interrupt[0]);
1461
1462         /*
1463          * The reschedule interrupt is a CPU-to-CPU reschedule-helper
1464          * IPI, driven by wakeup.
1465          */
1466         set_intr_gate(RESCHEDULE_VECTOR, reschedule_interrupt);
1467
1468         /* IPI for invalidation */
1469         set_intr_gate(INVALIDATE_TLB_VECTOR, invalidate_interrupt);
1470
1471         /* IPI for generic function call */
1472         set_intr_gate(CALL_FUNCTION_VECTOR, call_function_interrupt);
1473 }

These gates are installed at boot time, and are responsible for handling the various interrupts on multiprocessor systems. An APIC is required on all SMP systems for various reasons, and scheduling is one of them.

There is one small detail that I left out. You may have wondered about the TIF_POLLING_NRFLAG scattered about in the code. If you provide "idle=poll" as a kernel parameter at boot time, the idle function points to poll_idle(), instead of default_idle().

The poll_idle() function does not halt the processor, but spins around checking to see if a task is ready to run. As you may have guessed, although performance may improve, it's not very power-friendly. You certainly don't want this on your laptop.


124 /*
125  * On SMP it's slightly faster (but much more power-consuming!)
126  * to poll the ->work.need_resched flag instead of waiting for the
127  * cross-CPU IPI to arrive. Use this option with caution.
128  */
129 static void poll_idle (void)
130 {
131         local_irq_enable();
132
133         asm volatile(
134                 "2:"
135                 "testl %0, %1;"
136                 "rep; nop;"
137                 "je 2b;"
138                 : : "i"(_TIF_NEED_RESCHED), "m" (current_thread_info()->flags));
139 }

If you go back and read the resched_task() function, you will notice that the IPI is only sent if TIF_POLLING_NRFLAG is not set. Since the CPU is already running, it is not necessary to interrupt it.

A final word about IPIs. Waking up a halted processor is not all that it is used for. It is also used in the memory management code, to maintain cache coherency, in certian synchronization code, and many other places in the scheduler.

If you found this interesting and want to learn more, listed below are a few places you can go digging around. Happy hacking!

Note: All file paths are relative to the base of the Linux kernel source tree. The code snippets in this article are from version 2.6.20 of the kernel.

kernel/sched.c
kernel/cpu.c
arch/i386/kernel/smp.c
arch/i386/kernel/smpboot.c
arch/i386/kernel/process.c
arch/i386/kernel/head.S
include/asm-i386/apic.h
Intel APIC Architecture

The Game of Life in JavaScript

2007-02-04T15:43:00.000-05:00

I just discovered the canvas tag. <canvas> is a HTML element used for embedding vector graphics within your web pages. It was first introduced by Apple for Dashboard Widgets, and was later implemented in Safari.

It is now supported by most major browsers, except Internet Explorer. Fortunately, Google has a compatibility layer called ExplorerCanvas that brings the canvas tag to IE.

To learn more about <canvas>, Mozilla has a very good tutorial.

Anyhow, for a quick demo of what it can do, check out my interpretation of John Conway's Game of Life, in JavaScript, aptly named Game of Death. I coded it on a Saturday afternoon, slightly hungover, to teach myself JavaScript and familiarize myself with <canvas>.

Here's the source code. Warning: No fancy algorithms within.

Why I Like Working for Google

2006-09-14T20:47:00.000-04:00

I don't really care for the free food, the toys, the microkitchens, or the ridculously-massively-distributed infrastructure. It's not the pay, the on-site massages, the flexible work hours, or the free books. Guido van Rossum, Vint Cerf and Rob Pike are great, but they're no Angelina Jolie.

It's the business cards... they really are quite cool.

Q&A: How OS X Executes Applications

2006-03-28T09:17:00.001-05:00

After writing my previous article, How OS X Executes Applications, I received quite a few comments and e-mails with some good questions. I will attempt to answer some of them here, and continue to update this entry as questions arise.

Question 1. What is libSystem.B.dylib?

evil:~/Temp mohit$ otool -L /bin/ls
/bin/ls:
        /usr/lib/libncurses.5.4.dylib (compatibility version 5.4.0, current version 5.4.0)
        /usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 88.0.0)

The System library, found in /usr/lib/libSystem.dylib, is simply a collection of core libraries that are used by most Darwin applications. A few libraries worth mentioning that are in libSystem.dylib are:

libc : The standard C library.
libdl : The dynamic loader library.
libm : The math library.
libpthread : The POSIX threads library.
libinfo : The NetInfo library.

To get a complete list of modules and symbols within the library, use the -Tv switch of the otool command.

Question 2. Is there an objdump for OS X?

Yes there is, and it supports Mach-O binaries. It's just not distributed with Darwin / OS X. This link on this site, tells you what systems objdump is distributed with.

Question 3. Are executable code and readonly data in the same _TEXT segment? If so, how can they mark part of it executable and part not executable (normal security practice nowadays)?

I actually updated the article with the answer to this, but its a good question, and I'll answer it here again.

Segments may be sub-divided into sections. Within the __TEXT segment, only certain sections, e.g., __text, or __picsymbol_stub, can contain executable code.

To determine which sections contain executable code, use the -lv parameter with otool, and look at the attribute named attributes.

evil:~/Temp mohit$ otool -lv /bin/ls | egrep '(sectname|attributes)'
  sectname __text
attributes PURE_INSTRUCTIONS SOME_INSTRUCTIONS
  sectname __picsymbol_stub
attributes PURE_INSTRUCTIONS
  sectname __symbol_stub
attributes PURE_INSTRUCTIONS
  sectname __picsymbolstub1
attributes PURE_INSTRUCTIONS SOME_INSTRUCTIONS
  sectname __cstring
attributes (none)
  sectname __symbol_stub1
attributes PURE_INSTRUCTIONS SOME_INSTRUCTIONS
  sectname __literal8
attributes (none)
  sectname __eh_frame
attributes NO_TOC STRIP_STATIC_SYMS LIVE_SUPPORT
  sectname __data
attributes (none)
  sectname __nl_symbol_ptr
attributes (none)
  sectname __la_symbol_ptr
attributes (none)
  sectname __dyld
attributes (none)
  sectname __common
attributes (none)
  sectname __bss
attributes (none)

The sections with attributes set to PURE_INSTRUCTIONS contain executable code.

Question 4. How do I dechipher the constants in the otool output?

There are two ways to do this: One way is to examine the header files in /usr/include/mach and /usr/include/mach-o; and the other, simpler, way is to just add -v to your otool commands.

evil:~/Temp mohit$ otool -vh /bin/ls      
/bin/ls:
Mach header
      magic cputype cpusubtype   filetype ncmds sizeofcmds      flags
   MH_MAGIC     PPC        ALL    EXECUTE    11       1608   NOUNDEFS DYLDLINK TWOLEVEL

Question 5. What are Two-Level Namespaces?

It is a feature included since OS X 10.1, that prevents collisions with symbol names in dynamic libraries. It works by associating library names with symbol names at compile time.

Suppose you have an application that is linked against libfirst and libsecond. libfirst exports a function called dothis(). At a later time, a new version of libsecond comes out with its own dothis() function. Now, the application may execute whichever dothis() function it loads first, which may not be the one that was intended.

With two-level namespaces (enabled by default), the linker associates dothis() with libfirst at compile time. This prevents the chances of symbol collisions in future versions of linked libraries.

Question 6. Is Steve Jobs going to have you executed for reverse engineering this information?

Yes he is.

Seriously though, all this information is public knowledge. I did not "reverse engineeer" anything. All I did was put together the most relevant parts of the documents mentioned at the end of the article. And I would suggest reading them for a deeper understanding of the OS X runtime environments.

How OS X Executes Applications

2006-03-26T10:16:00.004-05:00

Being a long-time UNIX user, I generally have a common set of tools that I work with while trying to troubleshoot system problems. More recently, I have been developing software that adds Apple's OS X to the list of supported operating systems; and unlike traditional UNIX variants, OS X does not support many of the tools that relate to loading, linking and executing programs.

For example, when I come across library relocation problems, the first thing I do is run ldd on the executable. The ldd tool lists the dependent shared libraries that the executable requires, along with their paths if found.

On OS X though, here's what happens when you try to run ldd.

evil:~ mohit$ ldd /bin/ls
-bash: ldd: command not found

Not Found? But it's on all the common UNIX flavours. I wonder if objdump works.

$ objdump -x /bin/ls
-bash: objdump: command not found

Command not found. What's going on?

The problem is that unlike Linux, Solaris, HP-UX, and many other UNIX variants, OS X does not use ELF binaries. In addition, OS X is not part of the GNU project, which is home to tools like ldd and objdump.

In order to get a list of dependencies for an executable on OS X, you need to use otool.

evil:~ mohit$ otool /bin/ls
otool: one of -fahlLtdoOrTMRIHScis must be specified
Usage: otool [-fahlLDtdorSTMRIHvVcXm] object_file ...
        -f print the fat headers
        -a print the archive header
        -h print the mach header
        -l print the load commands
        -L print shared libraries used
        -D print shared library id name
        -t print the text section (disassemble with -v)
        -p   start dissassemble from routine name
        -s   print contents of section
        -d print the data section
        -o print the Objective-C segment
        -r print the relocation entries
        -S print the table of contents of a library
        -T print the table of contents of a dynamic shared library
        -M print the module table of a dynamic shared library
        -R print the reference table of a dynamic shared library
        -I print the indirect symbol table
        -H print the two-level hints table
        -v print verbosely (symbolicly) when possible
        -V print disassembled operands symbolicly
        -c print argument strings of a core file
        -X print no leading addresses or headers
        -m don't use archive(member) syntax
evil:~ mohit$ otool -L /bin/ls
/bin/ls:
        /usr/lib/libncurses.5.4.dylib (compatibility version 5.4.0, current version 5.4.0)
        /usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 88.0.0)

Much better. I can see that /bin/ls references two dynamic libraries. Though, the filename extensions don't look at all familiar.

I'm quite sure that many UNIX / Linux users have had similar experiences while working on OS X systems, so I decided to write a little on what I have learnt so far about OS X executable files.

The OS X Runtime Architecture

A runtime environment is a framework for code execution on OS X. It consists of a set of conventions that define how code is loaded, managed and executed. When an application is launched, the relevant runtime environment loads the program into memory, resolves references to external libraries, and prepares the code for execution.

OS X supports three runtime environments:

Dyld Runtime Environment: The preferred runtime environment based on the dyld library manager.
CFM Runtime Environment: A legacy environment inherited from OS 9. This is really designed for applications that want to use some of the newer OS X features, but have not been completely ported to dyld yet.
The Classic Environment: This environment makes it possible for unmodified OS 9 (9.1 or 9.2) applications to run on OS X.

This article will primarily focus on the Dyld Runtime Environment.

The Mach-O Executable File Format

In OS X, almost all files containing executable code, e.g., applications, frameworks, libraries, kernel extensions etc., are implemented as Mach-O files. Mach-O is a file format and an ABI (Application Binary Interface) that describes how an executable is to be loaded and run by the kernel. To be more specific, it tells the OS:

Which dynamic loader to use.
Which shared libraries to load.
How to organize the process address space.
Where the function entry-point is, and more.

Mach-O is not new. It was originally designed by the Open Software Foundation (OSF) for their OSF/1 operating system, which was based on the Mach microkernel. It was later adapted to x86 systems with OpenStep.

To support the Dyld Runtime Environment, all files must be built using the Mach-O executable format.

How Mach-O Files are Organized

Mach-O files are divided into three regions: a header, a load commands region, and the raw segment data. The header and load commands regions describe the features, layout and other characteristics of the file, while the raw segment data region contains ranges of bytes that are referenced by the load commands.

To investigate and examine the various parts of Mach-O files, OS X comes with a useful program called otool located in /usr/bin.

In the following sections, we will use otool to learn more about how Mach-O files are organized.

The Header

To view the the Mach-O header of a file, use the -h parameter of the otool command.

evil:~ mohit$ otool -h /bin/ls
/bin/ls:
Mach header
      magic cputype cpusubtype   filetype ncmds sizeofcmds      flags
 0xfeedface      18          0          2    11       1608 0x00000085

The first thing specified in the header is the magic number. The magic number identifies the file as either a 32-bit or a 64-bit Mach-O file. It also identifies the endianness of the CPU that it was intended for. To decipher the magic number, have a look at /usr/include/mach-o/loader.h.

The header also specifies the target architecture for the file. This allows the kernel to ensure that the code is not run on a processor-type that it was not written for. For example, in the above output, cputype is set to 18, which is CPU_TYPE_POWERPC, as defined in /usr/include/mach/machine.h.

From these two entries alone, we can infer that this binary was intended for 32-bit PowerPC based systems.

Sometimes binaries can contain code for more than one architecture. These are known as Universal Binaries, and generally begin with an additional header called the fat_header. To examine the contents of the fat_header, use the -f switch of the otool command.

The cpusubtype attribute specifies the exact model of the CPU, and is generally set to CPU_SUBTYPE_POWERPC_ALL or CPU_SUBTYPE_I386_ALL.

The filetype signifies how the file is to be aligned and used. It usually tells you if the file is a library, a standard executable, a core file etc. The filetype above equates to MH_EXECUTE, which signifies a demand paged executable file. Below is a snip from /usr/include/mach-o/loader.h that lists the different file-types as of this writing.

#define MH_OBJECT 0x1   /* relocatable object file */
#define MH_EXECUTE  0x2   /* demand paged executable file */
#define MH_FVMLIB 0x3   /* fixed VM shared library file */
#define MH_CORE   0x4   /* core file */
#define MH_PRELOAD  0x5   /* preloaded executable file */
#define MH_DYLIB  0x6   /* dynamically bound shared library */
#define MH_DYLINKER 0x7   /* dynamic link editor */
#define MH_BUNDLE 0x8   /* dynamically bound bundle file */
#define MH_DYLIB_STUB 0x9   /* shared library stub for static */
          /*  linking only, no section contents */

The next two attributes refer to the load commands section, and specify the number and size of the commands.

And finally, we have flags, that specify various features that the kernel may use while loading and executing Mach-O files.

Load Commands

The load commands region contains a list of commands that tell the kernel how to load the various raw segments within the file. They basically describe how each segment is aligned, protected and laid out in memory.

To see a the list of load commands within a file, use the -l switch of the otool command.

evil:~/Temp mohit$ otool -l /bin/ls
/bin/ls:
Load command 0
      cmd LC_SEGMENT
  cmdsize 56
  segname __PAGEZERO
   vmaddr 0x00000000
   vmsize 0x00001000
  fileoff 0
 filesize 0
  maxprot 0x00000000
 initprot 0x00000000
   nsects 0
    flags 0x4
Load command 1
      cmd LC_SEGMENT
  cmdsize 600
  segname __TEXT
   vmaddr 0x00001000
   vmsize 0x00006000
  fileoff 0
 filesize 24576
  maxprot 0x00000007
 initprot 0x00000005
   nsects 8
    flags 0x0
Section
  sectname __text
   segname __TEXT
      addr 0x00001ac4
      size 0x000046e8
    offset 2756
     align 2^2 (4)
    reloff 0
    nreloc 0
     flags 0x80000400
 reserved1 0
 reserved2 0

[ ___SNIPPED FOR BREVITY___ ]

Load command 4
          cmd LC_LOAD_DYLINKER
      cmdsize 28
         name /usr/lib/dyld (offset 12)
Load command 5
          cmd LC_LOAD_DYLIB
      cmdsize 56
         name /usr/lib/libncurses.5.4.dylib (offset 24)
   time stamp 1111407638 Mon Mar 21 07:20:38 2005
      current version 5.4.0
compatibility version 5.4.0
Load command 6
          cmd LC_LOAD_DYLIB
      cmdsize 52
         name /usr/lib/libSystem.B.dylib (offset 24)
   time stamp 1111407267 Mon Mar 21 07:14:27 2005
      current version 88.0.0
compatibility version 1.0.0
Load command 7
     cmd LC_SYMTAB
 cmdsize 24
  symoff 28672
   nsyms 101
  stroff 31020
 strsize 1440
Load command 8
            cmd LC_DYSYMTAB
        cmdsize 80
      ilocalsym 0
      nlocalsym 0
     iextdefsym 0
     nextdefsym 18
      iundefsym 18
      nundefsym 83
         tocoff 0
           ntoc 0
      modtaboff 0
        nmodtab 0
   extrefsymoff 0
    nextrefsyms 0
 indirectsymoff 30216
  nindirectsyms 201
      extreloff 0
        nextrel 0
      locreloff 0
        nlocrel 0
Load command 9
     cmd LC_TWOLEVEL_HINTS
 cmdsize 16
  offset 29884
  nhints 83
Load command 10
        cmd LC_UNIXTHREAD
    cmdsize 176
     flavor PPC_THREAD_STATE
      count PPC_THREAD_STATE_COUNT
    r0  0x00000000 r1  0x00000000 r2  0x00000000 r3   0x00000000 r4   0x00000000
    r5  0x00000000 r6  0x00000000 r7  0x00000000 r8   0x00000000 r9   0x00000000
    r10 0x00000000 r11 0x00000000 r12 0x00000000 r13  0x00000000 r14  0x00000000
    r15 0x00000000 r16 0x00000000 r17 0x00000000 r18  0x00000000 r19  0x00000000
    r20 0x00000000 r21 0x00000000 r22 0x00000000 r23  0x00000000 r24  0x00000000
    r25 0x00000000 r26 0x00000000 r27 0x00000000 r28  0x00000000 r29  0x00000000
    r30 0x00000000 r31 0x00000000 cr  0x00000000 xer  0x00000000 lr   0x00000000
    ctr 0x00000000 mq  0x00000000 vrsave 0x00000000 srr0 0x00001ac4 srr1 0x00000000

The above file has 11 load commands located directly below the header, numbered 0 to 10.

The first four commands (LC_SEGMENT), numbered 0 to 3, define how segments within the file are to be mapped into memory. A segment defines a range of bytes in the Mach-O binary, and can contain zero or more sections. We will talk more about segments later.

Load command 4 (LC_LOAD_DYLINKER) specifies which dynamic linker to use. This is almost always set to /usr/lib/dyld, which is the default OS X dynamic library linker.

Commands 5 and 6 (LC_LOAD_DYLIB) specify the shared libraries that this file links against. These are loaded by the dynamic loader specified in command 4.

Commands 7 and 8 (LC_SYMTAB, LC_DYNSYMTAB) specify the symbol tables used by the file and the dynamic linker respectively. Command 9 (LC_TWOLEVEL_HINTS) contains the hint table for the two-level namespace.

And finally, command 10 (LC_UNIXTHREAD), defines the initial state of the main thread of the process. This command is only included in executable files.

Segments and Sections

Most of the load commands mentioned above make references to segments within the file. A segment is a range of bytes within a Mach-O file that maps directly into virtual memory by the kernel and the dynamic linker. The header and load commands regions are considered as the first segment of the file.

An typical OS X executable generally has five segments:

__PAGEZERO : Located at virtual memory address 0 and has no protection rights. This segment occupies no space in the file, and causes access to NULL to immediately crash.
__TEXT : Contains read-only data and executable code.
__DATA : Contains writable data. These sections are generally marked copy-on-write by the kernel.
__OBJC : Contains data used by the Objective C language runtime.
__LINKEDIT : Contains raw data used by the dynamic linker.

The __TEXT and __DATA segments may contain zero or more sections. Each section consists of specific types of data, e.g., executable code, constants, C strings etc.

To see the contents of a section, use the -s option with the otool command.

evil:~/Temp mohit$ otool -sv __TEXT __cstring /bin/ls
/bin/ls:
Contents of (__TEXT,__cstring) section
00006320 00000000 5f5f6479 6c645f6d 6f645f74 
00006330 65726d5f 66756e63 73000000 5f5f6479 
00006340 6c645f6d 616b655f 64656c61 7965645f 
00006350 6d6f6475 6c655f69 6e697469 616c697a 
__SNIP__

To disassemble the __text section, use the -tv switch.

evil:~/Temp mohit$ otool -tv /bin/ls
/bin/ls:
(__TEXT,__text) section
00001ac4        or      r26,r1,r1
00001ac8        addi    r1,r1,0xfffc
00001acc        rlwinm  r1,r1,0,0,26
00001ad0        li      r0,0x0
00001ad4        stw     r0,0x0(r1)
00001ad8        stwu    r1,0xffc0(r1)
00001adc        lwz     r3,0x0(r26)
00001ae0        addi    r4,r26,0x4
__SNIP__

Within the __TEXT segment, there are four major sections:

__text : The compiled machine code for the executable.
__const : General constants data.
__cstring : Literal string constants.
__picsymbol_stub : Position-independent code stub routines used by the dynamic linker.

This keeps the executable and non-executable code clearly separated within the segment.

Running an Application

Now that we know what a Mach-O file looks like, let us see how OS X loads and runs an application.

When you run an application, the shell first calls the fork() system call. Fork creates a logical copy of the calling process (the shell) and schedules it for execution. This child process then calls the execve() system call providing the path of the program to be executed.

The kernel loads the specified file, and examines its header to verify that it is a valid Mach-O file. It then starts interpreting the load commands, replacing the child process's address space with segments from the file.

At the same time, the kernel also executes the dynamic linker specified by the binary, which proceeds to load and link all the dependent libraries. After it binds just enough symbols that are necessary for running the file, it calls the entry-point function.

The entry-point function is usually a standard function statically linked in from /usr/lib/crt1.o at build time. This function initializes the kernel environment and calls the executable's main() function.

The application is now running.

The Dynamic Linker

The OS X dynamic linker, /usr/lib/dyld, is responsible for loading dependent shared libraries, importing the various symbols and functions, and binding them into the current process.

When the process is first started, all the linker does is import the shared libraries into the address space of the process. Depending on how the program was built, the actual binding may be performed at different stages of its execution.

Immediately after loading, as in load-time binding.
When a symbol is referenced, as in just-in-time binding.
Before the process is even executed, an optimization technique known as pre-binding

If a binding type is not specified, the just-in-time binding is used.

An application can only continue to run when all the required symbols and segments from all the different object files can be resolved. In order to find libraries and frameworks, the standard dynamic linker, /usr/bin/dyld, searches a predefined set of directories. To override these directories, or to provide fallback paths, the DYLD_LIBRARY_PATH or DYLD_FALLBACK_LIBRARY_PATH environment variables can be set a colon-separated list of directories.

Finally

As you can see, executing a process in OS X is a complex affair, and I have tried to cover as much as is necessary for a useful debugging session.

To learn more about Mach-O executables, otool, and the OS X kernel in general, here are a list of references that I would recommend:

Mac OS X ABI Mach-O File Format Reference
Executing Mach-O Files
Overview of Dynamic Libraries
The otool man page
The dyld man page
/usr/include/mach/machines.h
/usr/include/mach-o/loader.h

Updates

2006/03/28 - Looks like this article was Slashdotted and Dugg. It has been slightly modified since, thanks to a few readers who pointed out errors and typos within.

2006/03/28 - I have answered some of your questions and comments regarding this article here: Q&A: How OS X Executes Applications.

Using Spotlight from the OS X Commandline

2006-03-22T07:05:00.001-05:00

One significant productivity-enhancing feature that arrived with Tiger was Spotlight. On its own, it changed the way some (if not most) Mac users use their desktops. A simple command-space pops up the Spotlight window, where you can enter a query string, and in a matter of seconds, get a list of files matching your query.

Spotlight has many advantages over traditional file-searching tools. For one thing, it's not a tool. It is a complete indexing and search framework that is tightly integrated into the Operating System. In addition to filenames and paths, it also indexes by file metadata and content. So Spotlight returns query results based on what's inside the file.

Spotlight benefits can also be enjoyed on the commandline, and this article explains how you can take full advantage of it from inside the OS X Terminal window.

The Old Way

Most commandline users are familiar with the ubiquitous find command.

evil:~/Desktop mohit$ find / -name '*Rails*'
/Applications/TextMate.app/Contents/SharedSupport/Bundles/Rails.tmbundle
/Applications/TextMate.app/Contents/SharedSupport/Bundles/Rails.tmbundle/Syntaxes/HTML (Rails).plist
/Applications/TextMate.app/Contents/SharedSupport/Bundles/Rails.tmbundle/Syntaxes/Ruby on Rails.plist
/Applications/TextMate.app/Contents/SharedSupport/Bundles/Rails.tmbundle/Syntaxes/SQL (Rails).plist

Find is old-school. You give it a search path, and it begins its search by tediously recursing directories and finding matches to the query string. On even an average-sized filesystem, find can take a frustratingly long time.

Then there's the locate tool. Locate is much faster because it maintains a periodically-updated index of filenames and their locations.

evil:~/Desktop mohit$ locate Rails
/Applications/TextMate.app/Contents/SharedSupport/Bundles/Rails.tmbundle
/Applications/TextMate.app/Contents/SharedSupport/Bundles/Rails.tmbundle/Commands
/Applications/TextMate.app/Contents/SharedSupport/Bundles/Rails.tmbundle/Commands/Open test-case.plist
/Applications/TextMate.app/Contents/SharedSupport/Bundles/Rails.tmbundle/info.plist
/Applications/TextMate.app/Contents/SharedSupport/Bundles/Rails.tmbundle/Snippets
/Applications/TextMate.app/Contents/SharedSupport/Bundles/Rails.tmbundle/Snippets/170 eruby forin.plist

The problem with locate is that the index is not updated dynamically. On OS X systems, it is updated weekly by code residing in /etc/weekly. Also, locate does not index the contents of the files, nor does it know anything about file metadata.

Enter Spotlight

Spotlight consists of a metadata-store and a content index that is dynamically updated by various importer plugins within the system.

The metadata that Spotlight maintains can be very application-specific. For example, images can contain metadata such as, "Dimensions" and "Color Space". Or music files can contain metadata such as, "Genre", "Bit-Rate" or "Encoding".

Spotlight indexes data by way of various importer plugins. These plugins know how to handle various kinds of data, such as iChat Transcripts, iTunes Music, e-mail etc.

Below is a snippet of the top processes on my PowerBook.

 1352 top         10.4%  0:01.41   1    18    22   620K   416K  1.05M  27.0M 
 1337 mdimport     0.0%  0:00.45   4    62    55  1.06M  3.98M  3.15M  39.9M
 1294 mdimport     0.0%  0:00.21   3    61    46   776K  2.82M  2.28M  38.9M
 1283 mdimport     0.0%  0:00.35   3    61    47   748K  3.19M  2.36M  39.4M
 1281 lookupd      0.0%  0:00.17   2    34    39   440K   912K  1.20M  28.5M
 1258 iTunes       2.4%  2:32.63   4   226   376  17.0M  26.8M  41.7M   227M

Notice the three mdimport processes. The mdimport daemon is responsible for working with the importer plugins and updating the Spotlight index.

Example 1. A Basic Spotlight Query

The commandline version of Spotlight is mdfind. Simply provide your search query as a parameter and let it run.

evil:~/Desktop mohit$ mdfind Rails
/Users/mohit/Documents/Rails4Days.pdf
/Users/mohit/Documents/Agile Development with Rails.pdf
/Users/mohit/Library/Mail/POP-foobar@mail.snip.com/INBOX.mbox/Messages/20455.emlx
/Users/mohit/Local/rails
/opt/local/lib/ruby/gems/1.8/cache/rails-1.0.0.gem
/opt/local/lib/ruby/gems/1.8/gems/rails-1.0.0
/opt/local/lib/ruby/gems/1.8/gems/rails-1.0.0/bin/rails
/opt/local/lib/ruby/gems/1.8/gems/rails-1.0.0/builtin/controllers/rails_info_controller.rb
/opt/local/lib/ruby/gems/1.8/gems/rails-1.0.0/html/index.html
/opt/local/lib/ruby/gems/1.8/gems/rails-1.0.0/html/images/rails.png

The files that are listed also include files with content and metadata that matches the query expression.

Example 2. Limiting Your Search to a Specific Directory

The -onlyin parameter limits the scope of the search to the directory specified.

evil:~/Desktop mohit$ mdfind -onlyin ~/Desktop Rails
/Users/mohit/Desktop/Downloads/Linux/Documents/Work/Verizon Data/Tekelec/Tekelec_Alarm_Docs.pdf
/Users/mohit/Desktop/Projects/Client/nABLE Event Manager - High Level Architecture.doc
/Users/mohit/Desktop/Projects/Client/nABLE EM.doc
/Users/mohit/Desktop/Projects/Client/to-timesheet-2006-01.pdf

Example 3. Displaying File Metadata

Earlier, I mentioned that Spotlight also indexes file metadata. The mdls tool lets you examine the metadata for a specified file.

evil:~/Desktop/Projects/Tierone mohit$ mdls SomeDocument.doc 
nABLE EM.doc -------------
kMDItemAttributeChangeDate     = 2006-01-23 08:12:42 -0500
kMDItemAuthors                 = ("Homer Simpson")
kMDItemContentCreationDate     = 2006-01-23 08:12:40 -0500
kMDItemContentModificationDate = 2006-01-23 08:12:40 -0500
kMDItemContentType             = "com.microsoft.word.doc"
kMDItemContentTypeTree         = ("com.microsoft.word.doc", "public.data", "public.item")
kMDItemDisplayName             = "SomeDocument.doc"
kMDItemFSContentChangeDate     = 2006-01-23 08:12:40 -0500
kMDItemFSCreationDate          = 2006-01-23 08:12:40 -0500
kMDItemFSCreatorCode           = 1297307460
kMDItemFSFinderFlags           = 0
kMDItemFSInvisible             = 0
kMDItemFSIsExtensionHidden     = 0
kMDItemFSLabel                 = 0
kMDItemFSName                  = "SomeDocument.doc"
kMDItemFSNodeCount             = 0
kMDItemFSOwnerGroupID          = 20
kMDItemFSOwnerUserID           = 501
kMDItemFSSize                  = 92160
kMDItemFSTypeCode              = 1463304782
kMDItemID                      = 2821259
kMDItemKind                    = "Microsoft Word document"
kMDItemLastUsedDate            = 2006-01-23 08:12:40 -0500
kMDItemTitle                   = "Document:"
kMDItemUsedDates               = (2006-01-23 08:12:40 -0500)

The metadata consists of various attributes specific to the file. These attributes can be used with mdfind to limit the scope of your search.

A good reference for these metadata attributes can be found at the Apple Developer Connection site.

Example 4. Finding Files by a Specific Author

This time, we limit our search to all files by a given author. The attribute we use is kMDItemAuthors.

evil:~ mohit$ mdfind "kMDItemAuthors == '*Homer*'"
/Users/mohit/Documents/SomeDocument.doc
/Users/mohit/Documents/Microsoft User Data/AutoRecovery save of SomeDocument.doc

Notice that the query was double quoted, while the text-pattern was single quoted.

Example 5. Finding Music by Artist

The Spotlight query expressions can be quite sophisticated. It allows for various kinds of conditional operators and patterns. Below, we search for all music by John Scofield.

evil:~ mohit$ mdfind "kMDItemAuthors == 'John Scofield' && kMDItemContentType == 'public.mp3'"
/Users/mohit/Music/iTunes/iTunes Music/John Scofield/A Go Go/07 Green Tea.mp3
/Users/mohit/Music/iTunes/iTunes Music/John Scofield/A Go Go/06 Kubrick.mp3

Great! But I seem to be missing some files. Where are my AACs?

Spotlight organizes ContentTypes within ContentTypeTrees, so in this case, public.mp3 falls under public.audio.

Knowing this, lets refine our search query to include all audio files.


evil:~ mohit$ mdfind "kMDItemAuthors == 'John Scofield' && kMDItemContentTypeTree == 'public.audio'"
/Users/mohit/Music/iTunes/iTunes Music/John Scofield/A Go Go/07 Green Tea.mp3
/Users/mohit/Music/iTunes/iTunes Music/John Scofield/A Go Go/06 Kubrick.mp3
/Users/mohit/Music/iTunes/iTunes Music/John Scofield/That's What I Say_ John Scofield Plays The Music of Ray Charles/01 Busted.m4a
/Users/mohit/Music/iTunes/iTunes Music/John Scofield/That's What I Say_ John Scofield Plays The Music of Ray Charles/02 What'd I Say.m4a

Much better. But how did I know what to search for?

This is where mdls comes in handy again.


evil:~ mohit$ mdls "/Users/mohit/Music/iTunes/iTunes Music/John Scofield/A Go Go/02 Chank.mp3"
/Users/mohit/Music/iTunes/iTunes Music/John Scofield/A Go Go/02 Chank.mp3 -------------
kMDItemAlbum                   = "A Go Go"
kMDItemAttributeChangeDate     = 2005-11-26 22:00:00 -0500
kMDItemAudioBitRate            = 128
kMDItemAudioChannelCount       = 2
kMDItemAudioSampleRate         = 44100
kMDItemAuthors                 = ("John Scofield")
kMDItemComment                 = "Created by Grip"
kMDItemContentCreationDate     = 2003-10-28 20:34:30 -0500
kMDItemContentModificationDate = 2003-10-28 20:34:35 -0500
kMDItemContentType             = "public.mp3"
kMDItemContentTypeTree         = (
    "public.mp3", 
    "public.audio", 
    "public.audiovisual-content", 
    "public.data", 
    "public.item", 
    "public.content"
)
kMDItemDisplayName             = "02 Chank.mp3"
kMDItemDurationSeconds         = 406
kMDItemFSContentChangeDate     = 2003-10-28 20:34:35 -0500
kMDItemFSCreationDate          = 2003-10-28 20:34:30 -0500
kMDItemFSCreatorCode           = 0
kMDItemFSFinderFlags           = 0
kMDItemFSInvisible             = 0
kMDItemFSIsExtensionHidden     = 0
kMDItemFSLabel                 = 0
kMDItemFSName                  = "02 Chank.mp3"
kMDItemFSNodeCount             = 0
kMDItemFSOwnerGroupID          = 20
kMDItemFSOwnerUserID           = 501
kMDItemFSSize                  = 6511095
kMDItemFSTypeCode              = 0
kMDItemID                      = 208222
kMDItemKind                    = "MP3 Audio File"
kMDItemLastUsedDate            = 2003-10-28 20:34:35 -0500
kMDItemMediaTypes              = (Sound)
kMDItemMusicalGenre            = "Jazz"
kMDItemRecordingYear           = 1998
kMDItemTitle                   = "Chank"
kMDItemTotalBitRate            = 128
kMDItemUsedDates               = (2003-10-28 20:34:35 -0500)

Looking at kMDContentTypeTree, we can tell that public.mp3 falls under public.audio.

We could have also searched by kMDItemMediaTypes, or kMDItemKind, or even a '*mp3' pattern in kMDItemDisplayName.

Example 6. Finding Other Content

You can find images by querying for files with kMDContentTypeTree set to public.image.

$ mdfind "kMDItemContentTypeTree == 'public.image'"

How about we refine that to only images within our iPhoto library.

$ mdfind -onlyin ~/Pictures "kMDItemContentTypeTree == 'public.image'"

Much Better.

Looking for Word documents?

$ mdfind "kMDItemContentType == 'com.microsoft.word.doc'"

Or maybe just PDFs?

$ mdfind "kMDItemContentType == 'com.adobe.pdf'"

Or Both?

$ mdfind "kMDItemContentType == 'com.microsoft.word.doc' || kMDItemContentType == 'com.adobe.pdf'"

Lets stick to plain-text.

$ mdfind "kMDItemContentTypeTree == 'public.text"

Example 7. Looking for Source Code

Finding all Ruby scripts.

$ mdfind "kMDItemContentType == 'public.ruby-script'"

Finding all kinds of scripts (Python, Bash, Ruby etc.)

$ mdfind "kMDItemContentTypeTree == 'public.shell-script'"

Finding everything except Python scripts.

$ mdfind "kMDItemContentTypeTree == 'public.shell-script' && kMDItemContentType != 'public.python-script'"

Finding Source Code (not scripts).

$ mdfind "kMDItemContentTypeTree == 'public.source-code"

Example 8. Using "kind" Keywords (Added 24/Mar/06)

Commandline Spotlight also supports the "kind:" keyword. This is simpler than filtering with kMDItemContentType.

evil:/ mohit$ mdfind "kind:pdf Calculus"
/Users/mohit/Documents/Elementary Calculus.pdf
/Users/mohit/.Trash/marktoberdorf.pdf
/Users/mohit/.Trash/FoundInfsmlCalc.pdf

Spotlight "kind" Keyword list.

Applications  kind:application, kind:applications, kind:app
Contacts      kind:contact, kind:contacts
Folders       kind:folder, kind:folders
Email         kind:email, kind:emails, kind:mail message, kind:mail messages
iCal Events   kind:event, kind:events
iCal To Dos   kind:todo, kind:todos, kind:to do, kind:to dos
Images        kind:image, kind:images
Movies        kind:movie, kind:movies
Music         kind:music
Audio         kind:audio
PDF           kind:pdf, kind:pdfs
Preferences   kind:system preferences, kind:preferences
Bookmarks     kind:bookmark, kind:bookmarks
Fonts         kind:font, kind:fonts
Presentations kind:presentations, kind:presentation

Example 9. Using "date" Keywords (Added 24/Mar/06)

Files can also be filtered based on date related information.

evil:/ mohit$ mdfind "kind:pdf date:this week"
/Users/mohit/Desktop/chapter_1a.pdf
/Users/mohit/Documents/Elementary Calculus.pdf
/Users/mohit/Desktop/13.pdf
/Users/mohit/Desktop/Internet_map_labels.pdf

The date ranges that can be specified are:

date:this month
date:this week
date:this year
date:today
date:yesterday
date:tomorrow
date:next month
date:next week
date:next year

Note that the future ranges (tomorrow, next week, etc.) are for Calendar appointments.

Finally

As you can see, Spotlight is great for commandline junkies too. It is a fast, flexible alternative to the UNIX find command, and in many respects, more powerful than find.

But it is by no means a replacement. There are some things that Spotlight's mdfind just cannot do. UNIX find has a much richer set of options, and when it comes to digging deep into the system, there is no alternative.

For most purposes though, Spotlight works very well. Rewriting your shell scripts to use mdfind instead of find, will make them far more responsive (and far less portable). So here's another case where OS X's UNIX underpinnings have made for a useful tool that is usable, both from the GUI and from the Commandline.

Troubleshooting UNIX Systems with Lsof

2006-03-12T09:04:00.001-05:00

One of the least-talked-about tools in a UNIX sysadmin's toolkit is lsof. Lsof lists information about files opened by processes. But that's really an understatement.

Most people forget that, in UNIX, (almost) everything is a file. The OS makes hardware available to applications by way of files in /dev. Kernel, system, memory, device etc. information in made available inside files in /proc. TCP/UDP sockets are sometimes represented internally as files. Even directories are really just files containing other filenames.

Lsof works by examining kernel data-structures and provides a variety of information related to files, pipes, sockets and more.

Lsof is installed by default on most Linux distributions, BSD distributions and OS X. Binary packages for Solaris, AIX, HP-UX, *cough*SCO OpenServer*cough* and many other UNIXes (Unices?) are available on the web.

So, just how useful is lsof?

Deciphering its Output

Switch to root, and type lsof on the commandline.

linux# lsof
COMMAND     PID     USER   FD      TYPE     DEVICE     SIZE       NODE NAME
init          1     root  cwd       DIR       3,65     4096          2 /
init          1     root  rtd       DIR       3,65     4096          2 /
init          1     root  txt       REG       3,65    29556     172317 /sbin/init
init          1     root  mem       REG       3,65  1166880      93908 /lib/libc-2.3.5.so
init          1     root  mem       REG       3,65   103053      93909 /lib/ld-2.3.5.so
init          1     root   10u     FIFO       3,65               48438 /dev/initctl
ksoftirqd     2     root  cwd       DIR       3,65     4096          2 /
ksoftirqd     2     root  rtd       DIR       3,65     4096          2 /
ksoftirqd     2     root  txt   unknown                                /proc/2/exe
events/0      3     root  cwd       DIR       3,65     4096          2 /
events/0      3     root  rtd       DIR       3,65     4096          2 /
events/0      3     root  txt   unknown                                /proc/3/exe

...SNIP...

syslog-ng  6529     root  txt       REG       3,69   114132      84690 /usr/sbin/syslog-ng
syslog-ng  6529     root  mem       REG       3,65  1166880      93908 /lib/libc-2.3.5.so
syslog-ng  6529     root  mem       REG       3,65    64568      93943 /lib/libresolv-2.3.5.so
syslog-ng  6529     root  mem       REG       3,65    75176      93924 /lib/libnsl-2.3.5.so
syslog-ng  6529     root  mem       REG       3,65   103053      93909 /lib/ld-2.3.5.so
syslog-ng  6529     root    0u      CHR        1,3               47320 /dev/null
syslog-ng  6529     root    1u      CHR        1,3               47320 /dev/null
syslog-ng  6529     root    2u      CHR        1,3               47320 /dev/null
syslog-ng  6529     root    3u     unix 0xdea00e00              672127 /dev/log

...SNIP...

asterisk   7001     root   10u     IPv4       6015                 TCP localhost:5038 (LISTEN)
asterisk   7001     root   11r     FIFO       3,70                 306 /var/run/asterisk/autod
ial.ctl
asterisk   7001     root   12u     IPv4       6834                 UDP *:5060 
asterisk   7001     root   13r     FIFO        0,5                6019 pipe
asterisk   7001     root   14u     IPv4       6016                 TCP localhost:5038->localho
st:32768 (ESTABLISHED)
asterisk   7001     root   15u     IPv4       6835                 UDP *:2727 
asterisk   7001     root   16u     IPv4       6861                 UDP *:4569 
asterisk   7001     root   17u      REG       3,70        0     593222 /var/lib/asterisk/astdb
asterisk   7001     root   18r     FIFO        0,5                6883 pipe
asterisk   7001     root   19u      REG       3,70    39402      32066 /var/tmp/iaxy.bin-19098
89093 (deleted)
asterisk   7001     root   20w     FIFO        0,5                6883 pipe

...LOTS MORE SNIPPED...

What you will be presented with is a very long list of open files, which you might want to pipe through your favourite pager.

By default (on Linux), lsof displays the following information about each open file:

COMMAND: The name of the UNIX command associated with the process.

PID: The Process ID.

USER: The user ID or login name of the user to whom the process belongs.

FD: The file descriptor number of the file or a code representing more information about the structure. See manual page for details.

TYPE: The type of the node associated with the file. E.g. REG signifies a regular file, IPv4 or IPv6 signifies an IP socket, DIR a directory, "unix" a UNIX domain socket, etc.

DEVICE: Usually contains major and minor device numbers for the files, or addresses/references for other structures.

SIZE: The size of the file or the file offset, in bytes. (If available.) In the case of files that don't have true sizes (eg., sockets, pipes), lsof displays the size of the content their kernel buffer descriptors.

NODE: Node number / inode / Internet protocol type (TCP) etc.

NAME: The name of the file / mount point / device / Internet address / etc.

For a comprehensive description of these fields, refer the lsof manual page.

Since lsof works by examining kernel memory, you will need root access to be able to fully utilize it. A non-root user will not have access to information that belongs to other users.

Common Usage

Lsof is usually run with one or more of the following options:

/path/to/file: List processes, owners and open file descriptors that are currently using the specified file.

-i [46][protocol][@hostname|hostaddr][:service|port]: List Internet files / sockets.

-u name: List files owned by user.

-p pid: List files open by specified process.

-t: Terse output. No headers, only PIDs. Useful within scripts.

-n: Disable resolving of network names.

-N: List NFS files

These options are ORed by default.

Display all internet files OR files opened by user "foobar".

# lsof -u foobar -i

To display all internet files that are opened by foobar, you need to apply the AND (-a) condition between the switches.

# lsof -u foobar -a -i

The following recipes demonstrate how lsof can be used to troubleshoot real-world problems.

Recipe #1: Finding Port Hogs

Your web-server is refusing to come up because port 80 is in use by another process. How do you track down the offending process?


# lsof -i

... SNIP ...

asterisk   7554     root   16u  IPv4   6861       UDP *:4569 
postmaste  7688 postgres    5u  IPv4   5955       UDP localhost:32768->localhost:32768 
postmaste  7689 postgres    5u  IPv4   5955       UDP localhost:32768->localhost:32768 
sshd      27038     root    3u  IPv4 677971       TCP reddwarf:ssh->CPE.xxxx.com:61702 (ESTABLISHED)
sshd      27043    mohit    3u  IPv4 677971       TCP reddwarf:ssh->CPE.xxxx.com:61702 (ESTABLISHED)

... SNIP ...

Nice. A list of open Internet sockets, along with the processes, addresses and owners. Also note that (similar to netstat), the TCP states are displayed. Above, we can see two established ssh sessions in progress.

Let's add a port filter and find exactly what we're looking for.


# lsof -i TCP:80
COMMAND   PID     USER   FD   TYPE DEVICE SIZE NODE NAME
lighttpd 7356 lighttpd    3u  IPv4   6409       TCP *:http (LISTEN)

Okay, so lighttpd is the reason why Apache won't run. That's probably a good thing.

Recipe #2: Finding Processes Within a Given Port Range

You need to find a range of free ports for your new multimedia application.


# lsof -i TCP:5000-5200
COMMAND   PID USER   FD   TYPE DEVICE SIZE NODE NAME
asterisk 7001 root   10u  IPv4   6015       TCP localhost:5038 (LISTEN)
asterisk 7001 root   14u  IPv4   6016       TCP localhost:5038->localhost:32768 (ESTABLISHED)
asterisk 7002 root   10u  IPv4   6015       TCP localhost:5038 (LISTEN)
asterisk 7002 root   14u  IPv4   6016       TCP localhost:5038->localhost:32768 (ESTABLISHED)
asterisk 7039 root   10u  IPv4   6015       TCP localhost:5038 (LISTEN)
asterisk 7039 root   14u  IPv4   6016       TCP localhost:5038->localhost:32768 (ESTABLISHED)
asterisk 7040 root   10u  IPv4   6015       TCP localhost:5038 (LISTEN)
asterisk 7040 root   14u  IPv4   6016       TCP localhost:5038->localhost:32768 (ESTABLISHED)
asterisk 7041 root   10u  IPv4   6015       TCP localhost:5038 (LISTEN)
asterisk 7041 root   14u  IPv4   6016       TCP localhost:5038->localhost:32768 (ESTABLISHED)
asterisk 7042 root   10u  IPv4   6015       TCP localhost:5038 (LISTEN)
asterisk 7042 root   14u  IPv4   6016       TCP localhost:5038->localhost:32768 (ESTABLISHED)
asterisk 7044 root   10u  IPv4   6015       TCP localhost:5038 (LISTEN)
asterisk 7044 root   14u  IPv4   6016       TCP localhost:5038->localhost:32768 (ESTABLISHED)
perl     7046 root    3u  IPv4   6054       TCP *:5100 (LISTEN)
perl     7046 root    4u  IPv4   6055       TCP *:5101 (LISTEN)
perl     7046 root    6u  IPv4   6056       TCP localhost:32768->localhost:5038 (ESTABLISHED)
asterisk 7073 root   10u  IPv4   6015       TCP localhost:5038 (LISTEN)
asterisk 7073 root   14u  IPv4   6016       TCP localhost:5038->localhost:32768 (ESTABLISHED)
asterisk 7504 root   10u  IPv4   6015       TCP localhost:5038 (LISTEN)
asterisk 7504 root   14u  IPv4   6016       TCP localhost:5038->localhost:32768 (ESTABLISHED)

Recipe #3: Listing User Files

What files do users "foobar" and "apache" have open?

# lsof -u foobar,apache

List UDP ports in use by user "mohit".

# lsof -i UDP -a -u mohit

Who's responding to "who"?

# lsof -i UDP:who

Recipe #4: Unmounting a Disk or Filesystem

Sometimes you need to track down the user or process that's blocking you from unmounting a disk.

# umount /opt
umount: /opt: device is busy
umount: /opt: device is busy
# mount | grep "/opt"
/dev/hdb9 on /opt type ext3 (rw,noatime)
# lsof /dev/hdb9
COMMAND    PID     USER   FD   TYPE DEVICE    SIZE    NODE NAME
perl      7046     root    2w   REG   3,73     111 1376386 /opt/local/paynacea/var/state/callmanager.pid.err
perl      7046     root    5w   REG   3,73    6783 1376385 /opt/local/paynacea/var/log/callmanager.log
# kill 7046
# umount /opt

Or the simpler:

# kill `lsof -t /opt`

Recipe #5: Finding Device Hogs

Who's using the audio manager?

# lsof /dev/audio

Why can't I start my alternate logger?

# lsof /dev/log

Why doesn't my CD eject?

# lsof /dev/cdrom

Recipe #6: Using Exclusions

The '^' (negated) modifier can prefix the User or Process ID parameters to exclude them from the resulting list. Since they represent exclusions, they are applied without ORing or ANDing and take effect before any other selection criteria are applied.

List all Internet files/sockets open by non-root users.

# lsof -i -u^root

Recipe #7: Recursing Directories

The '+D' option causes lsof to search for open files within a specified directory, recursing down to its complete depth.

List all processes that have files open in /tmp.

# lsof +D /tmp

The '+d' option does the same thing, but does _not_ descend the directory tree.

Recipe #8: Matching by Process Name

List all files open by processes beginning with the letters mpg.

# lsof -c mpg

Using a regular-expression.

# lsof -c '/post.*er/'

Recipe #9: Examining Suspicious Processes

Lsof can be used along with strace to examine and monitor the operation of viruses, worms or spyware.

What files are opened by PID 14554?

# lsof -p 14554

Who's looking at the password file?

# lsof /etc/passwd

Recipe #10: Repeat Mode

The -r switch puts lsof in repeat mode. It delays every 15 seconds (unless specified), and displays another listing.

Watching a user's open files every 5 seconds:

 # lsof -u badcop -r5

Monitoring the password file:

# lsof /etc/passwd -r 2

Recipe #11: Finding Deleted Open Files

This recipe was added on 26/Mar/06 after an anonymous poster left a comment regarding deleted files.

One of the most annoying problems is a file-system quickly running out of space, without a hint of what file is responsible for it. This happens when a file (usually a log-file), gets deleted while it's still being written to. When you delete an open file, the kernel unlinks the file from the directory, but cannot remove the inode, since it's still open.

This causes the file to continue to grow, with no trace of its existance anywhere. Well... almost anywhere.

Lsof provides the +L parameter to list the number of link counts an open file has. When followed by a number, lsof only displays files with link counts less thatn the specified number.

mohit@reddwarf ~ $ lsof +L3
COMMAND   PID  USER   FD   TYPE DEVICE    SIZE NLINK      NODE NAME
sshd    11540 mohit  mem    REG   3,69  303448     1     85869 /usr/sbin/sshd
sshd    11540 mohit  mem    REG   3,65   35404     1     94075 /lib/libnss_nis-2.3.5.so
sshd    11540 mohit  mem    REG   3,65   30928     1     94086 /lib/libnss_compat-2.3.5.so
sshd    11540 mohit  mem    REG   3,65   35236     1     93958 /lib/libnss_files-2.3.5.so
sshd    11540 mohit  mem    REG   3,65   28444     1     94094 /lib/libcrack.so.2.8.0

A deleted file has zero links. So the following command displays deleted-but-open files on a system.

$ lsof +L1

Display a list of deleted-but-open files within a specific filesystem.

$ lsof +aL1 /tmp

Finally

We barely scratched the surface with the above recipes, but as you can see, lsof is a powerful troubleshooting tool. I'd be interested in learning what other users do with lsof. Toy with it, tinker with it, use it and let me know how it has helped you.

Tailing Multiple Log Files with Twisted

2006-03-09T08:29:00.001-05:00

In my last entry, I described a mechanism to follow a growing log file using the Twisted framework. Now, what if you wanted to follow multiple log files simultaneously?

You could try something like this:

#!/usr/bin/env python

from twisted.internet import reactor
from Support.followtail import FollowTail

def lineReceived_file1( line ):
  print "FILE1: " + line

def lineReceived_file2( line ):
  print "FILE2: " + line

if __name__ == "__main__":
  tailer1 = FollowTail( "/home/mohit/var/log/access-log" )
  tailer2 = FollowTail( "/home/mohit/var/log/error-log" )

  tailer1.lineReceived = lineReceived_file1
  tailer2.lineReceived = lineReceived_file2

  tailer1.start()
  tailer2.start()

  reactor.run()

Sure, that works fine. But there's a scaling issue above. What if you wanted to follow an unknown number of files, and track which file each line came from? Since a function callback is required for each file, it's quite difficult to use FollowTail for more "dynamic" applications.

Here's a simple solution: Subclass FollowTail, and override lineReceived to have it supply the filename along with the line.

#!/usr/bin/env python

from twisted.internet import reactor
from Support.followtail import FollowTail

import sys

class MultiFollowTail( FollowTail ):
  def lineReceived( self, line ):
    self.onFileLine( self.filename, line )

  def onFileLine( self, filename, line ):
    pass

def lineReceived( filename, line ):
  print filename + ": " + line

if __name__ == "__main__":
  for arg in sys.argv[1:]:
    print "Monitoring: " + arg
    tailer = MultiFollowTail( arg )
    tailer.onFileLine = lineReceived
    tailer.start()

  if len( sys.argv ) > 1:  
    reactor.run()

Above, we created a new MultiFollowTail to do just that. Since the filename is included with each callback, we only need a single function to monitor multiple files.

And there you have it, a simple easy-to-use mechanism to monitor multiple logfiles with Python.

Following a Log File with Twisted

2006-03-07T09:21:00.001-05:00

Another POE component that I dearly miss in Twisted is POE::Wheel::FollowTail. FollowTail lets you monitor a growing log file, spewing events when new lines are received. It also gracefully handles log-rotated files by reopening it when it resets.

After some searching, I found a post in the Kragen-hacks mailing list that does something similar to the POE wheel.

I took that code, added line-buffering, wrapped it in a class, and added events for errors and file resets.

Here's the result:

# Twisted FollowTail
# Mohit Muthanna 
#
# A Twisted version of POE::Wheel::FollowTail. Adapted from
# a post by Kragen Sitaker on the Kragen-hacks mailing list.
#
# http://lists.canonical.org/pipermail/kragen-hacks/2005-June/000413.html

from twisted.internet import reactor
from twisted.protocols import basic
import os, stat

class FollowTail:
  from os import linesep as newline
  __line_buffer = ""

  def __init__( self, filename = None, seekend = True, delay = 1 ):
    self.filename = filename
    self.delay = delay
    self.seekend = seekend
    self.keeprunning = False

  def fileIdentity( self, struct_stat ):
    return struct_stat[stat.ST_DEV], struct_stat[stat.ST_INO]

  def start( self ):
    self.keeprunning = True
    self.followTail()

  def stop( self ):
    self.keeprunning = False

  def followTail( self, fileobj = None, fstat = None ):
    if fileobj is None:
      fileobj = open( self.filename )
      if self.seekend: fileobj.seek( 0, 2 )

    line = fileobj.read()

    if line: self.dataReceived( line )

    if fstat is None: fstat = os.fstat( fileobj.fileno() )

    try: stat = os.stat( self.filename )
    except: stat = fstat

    if self.fileIdentity( stat ) != self.fileIdentity( fstat ):
      fileobj = open( self.filename )
      fstat = os.fstat( fileobj.fileno() )
      self.fileReset()

    
    if self.keeprunning: 
      reactor.callLater( self.delay, lambda: self.followTail( fileobj, fstat ) )
  
  def dataReceived( self, data ):
    # Fill buffer
    self.__line_buffer += data
    
    # Split lines
    lines = self.__line_buffer.splitlines()
    
    if not data.endswith( self.newline ):
      self.__line_buffer = lines.pop()
    else:
      self.__line_buffer = ""
    
    for line in lines:
      self.lineReceived( line )
  
  def lineReceived( self, line ):
    """Override This"""
  
  def fileReset( self ):
    """Override This"""

Usage is quite straightforward. The FollowTail constructor has three parameters:

filename: Full path to file.

seekend: If set to "False", starts from beginning of file. Default "True".

delay: How often (in seconds) the file should be polled. Default 1 second.

When a new line is received, FollowTail calls the method "lineReceived" and supplies the line string. If the file has been rotated, it calls "fileReset". Both methods can be overridden in your program.

Here's some sample code that uses this class.

#!/usr/bin/env python

from twisted.internet import reactor
from followtail import FollowTail

def onLine( line ):
  print "Line: " + line

def onReset():
  print "File Rotated."

filename = "/home/mohit/var/log/access-log"
tailer = FollowTail( filename )
tailer.lineReceived = onLine
tailer.resetFile = onReset
tailer.start()

reactor.run()

Download: followtail.py.

Line Filtering With Twisted

2006-03-03T15:21:00.001-05:00

Unlike POE, the Twisted framework does not allow for generic stream filters.

This means that in order to pre- or post-process certain data-streams, one cannot reuse processing code used by other classes. I stumbled across this while trying to parse the output of a running process.

Take the following code for example. It listens on a socket, and when a connection is received, it spawns a process and redirects its output to the socket.

# test1.py
from twisted.internet import protocol, reactor
import sys

class TestProcessProtocol( protocol.ProcessProtocol ):
  def outReceived( self, data ):
    self.lineReceived( data )
      
  def lineReceived( self, line ):
    """Override This"""

class AdminServerProtocol( protocol.Protocol ):
  def connectionMade( self ):
    p = TestProcessProtocol()
    p.lineReceived = self.lineReceived
    p.outConnectionLost = self.transport.loseConnection
    reactor.spawnProcess( p, "./sample_module.py", ["sample_module.py"] )

  def lineReceived( self, line ):
    self.transport.write( "GOT LINE: " + line )

f = protocol.Factory()
f.protocol = AdminServerProtocol

reactor.listenTCP( 1079, f )
reactor.run()

Here's the spawned program.

# sample_module.py

import sys

for y in range(5):
  print "line 1"
  print "line 2"
  print "line 3"
  print "line 4"

  # Flush STDOUT. Added for clarity.
  sys.stdout.flush()

Let's see what happens when I run test1.py and connect to it.

$ telnet localhost 1079
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
GOT LINE: line 1
line 2
line 3
line 4
GOT LINE: line 1
line 2
line 3
line 4
GOT LINE: line 1
line 2
line 3
line 4
GOT LINE: line 1
line 2
line 3
line 4
GOT LINE: line 1
line 2
line 3
line 4
Connection closed by foreign host.

Hmmm... not quite what we expected. It would be nice to receive the data line-by-line instead of the whole buffer when it's flushed. Now, we could modify the spawned process to flush at every line, but sometimes we don't have that luxury. Also, if the process was rapidly spewing out data, or very long lines, we could end-up with partial (incomplete) lines.

Unlike POE, we can't just apply a filter to the stream and let loose. And unfortunately, protocol.LineReceiver can't help use because it only works with sockets.

The solution would be to subclass ProcessProtocol, and use that as our parent class.

from twisted.internet import protocol, reactor
import sys

class LineProcessProtocol( protocol.ProcessProtocol ):
  from os import linesep as newline
  __out_line_buffer = ""

  def outReceived( self, data ):
    # Fill buffer
    self.__out_line_buffer += data

    # Split lines
    lines = self.__out_line_buffer.splitlines()

    if not data.endswith( self.newline ):
      self.__out_line_buffer = lines.pop()
    else:
      self.__out_line_buffer = ""

    for line in lines:
      self.lineReceived( line )

  def lineReceived( self, line ):
    """Override This"""

  def writeLine( self, data ):
    self.transport.write( data + self.newline )


class TestProcessProtocol( LineProcessProtocol ):
  pass

class AdminServerProtocol( protocol.Protocol ):
  def connectionMade( self ):
    p = TestProcessProtocol()
    p.lineReceived = self.lineReceived
    p.outConnectionLost = self.transport.loseConnection
    reactor.spawnProcess( p, "./sample_module.py", ["sample_module.py"] )

  def lineReceived( self, line ):
    self.transport.write( "GOT LINE: " + line + "\n")

f = protocol.Factory()
f.protocol = AdminServerProtocol

reactor.listenTCP( 1079, f )
reactor.run()

Above, we inheret LineProcessProtocol from ProcessProtocol, and create a string-buffer. Everytime data is received, we fill the string buffer and split up the lines. We then feed any complete lines to lineReceived, while leaving only incomplete lines in the string buffer.

Let's see what we get.

$ telnet localhost 1079
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
GOT LINE: line 1
GOT LINE: line 2
GOT LINE: line 3
GOT LINE: line 4
GOT LINE: line 1
GOT LINE: line 2
GOT LINE: line 3
GOT LINE: line 4
GOT LINE: line 1
GOT LINE: line 2
GOT LINE: line 3
GOT LINE: line 4
GOT LINE: line 1
GOT LINE: line 2
GOT LINE: line 3
GOT LINE: line 4
GOT LINE: line 1
GOT LINE: line 2
GOT LINE: line 3
GOT LINE: line 4
Connection closed by foreign host.

Perfect! We can now use our LineProcessProtocol instead of the stock ProcessProtocol to parse process output.

Now the question is, how easy is it to use Twisted's component architecture to create an interface (ILineReceiver), and adapters for the various classes?

Or better still, how easy would it be to implement a generic stream framework within Twisted, making all this unnecessary, while still enjoying some POE goodness?

Gentoo Emerge Issues

2006-03-02T13:52:00.001-05:00

Last night I was unfortunate enough to break one of my staging servers during an emerge world.

Access Violations

First was the dreaded "ACCESS VIOLATION SUMMARY" error. Portage builds packages inside a virtual sandbox, and uses it to ensure that ebuilds don't do anything bad.

That said, sometimes not-fully-tested ebuilds get into the portage tree and make life a little more complicated.

The right thing to do would be to file a bug-report, with details related to you environment, packages, etc. etc. But then, some of us just want to get things done a little quicker.


$ FEATURES="-sandbox" emerge application

The above command temporarily disables the sandbox during the emerge. Do NOT do this with emerge world, as at that point, you'll just be testing fate.

What you need to do is, first proceed with a normal emerge. Go through the logs and find out why exactly the access-violations occured (chmod, unlink etc.) If you're comfortable with what you see then disable the sandbox for the broken application only.

Masking Packages

Portage also tried to upgrade postgres from v7 to v8. No no. This won't do.

This means that I would need v8 bindings for ruby, perl and python. Not to mention framework support for things like rails and twisted.

Not going there.

The solution to this is really quite simple. Add the following line to /etc/portage/package.mask.


>dev-db/postgresql-8.0.0

No DevFS

As close to the metal as Gentoo is, sometimes it does try and get ahead of itself. Like automatic /dev management detection. Within /etc/conf.d/rc, there's a new option called RC_DEVICES. It's set to "auto". This means that it tries to automatically detect if you're using devfs, udev or static device links.

My kernel was compled with devfs support, but I wasn't using it. Gentoo detected it and assumed that devfs was my preference. Ugh.

Now I had a system that wouldn't boot. You can imagine what it was like trying to figure this out.

Anyhow, to get out of this mess you need to rebuild the kernel without DevFS support.

Bummer.

The Lesson

Do _NOT_ use "emerge world". Instead, use "emerge -pv world", find the packages that need to be upgraded, and emerge them individually.

Always use "-pv" to verify what portage is going to do before the real emerge.

Working at Google

2006-02-28T10:36:00.000-05:00

So yesterday I accepted the job offer from Google. I will be working with their Site Reliability Engineering team in Manhattan, NY.

I know, I know, I should've picked California.

Anyhow, I first got an e-mail from Google last September about working there. I never really wanted to leave Toronto, but the opportunity sounded intriguing. I expressed my interest and the recruiter began to explain the screening and interview process to me.

I then went through three technical phone-interviews, each about 45-minutes long. They covered everything from algorithms to networks to operating systems. I had to write programs in various languages over the phone. That's right, "for open-parenthesis x equals 1 semicolon x less-than er no greater-than er yeah... blah blah".

Ofcourse, since I'm in Canada, I had to do extra phone interviews just so that they could be sure about flying me down for the real interview (or atleast that's what they told me).

There I was at the GooglePlex in Mountain View, CA. Six back-to-back interviews scheduled. All of which were very technical, and very detailed. We discussed search algorithms, bandwidth throttling, optimization, bottleneck-finding, and wrote lots of quasi-code.

It was as brutal as it was fun. By the end of it, I was exhausted. I initially wanted to tour and take pics of the campus (no pics allowed inside); but by the end of it, I just wanted to go home.

Anyhow, a few weeks later, they told me that I got the job. Unfortunately, at the time I wasn't able to legally work in the U.S. without an H1-B. I had to wait until I got my Canadian citizenship, before I could start.

Now I'm a Citizen, got my passport; and am starting with Google on the 27th of March.

To anyone else who's interviewing at Google: don't sweat it. There's a lot of posts on the web where people talk about Google interviews being outrageously difficult, and something only Ph.D.s can get through; but that's just blown way out of proportion.

They're not easy, but if you know your stuff, and enjoy what you do, you'll do good.

So... I'm off by the end of March; I've got lots of stuff for sale; and after five years of being a Canadian resident, am once again going to be an American resident.

Finding New Music with Google Sets

2006-02-25T09:32:00.000-05:00

So here's something cool. Google Labs has this online set completion tool called Google Sets.

Basically, you give it a list of items, and it finds you other similar items. For example, sending it "Beef" and "Pork", brings up "Poultry", "Chicken", "Seafood", "Lamb" etc.

It appears that they harness their massive search history database, and use some kind of Bayesian or LSI classification system to produce results. But then again, it's Google, and likely way more complicated than that.

Since I'm a big jazz fan, and jazz is a hugely unpopular genre among the masses, finding new artists is not very easy.

So let's see what happens when I plug in the names of two popular jazz guitarists, "Pat Metheney" and "John Scofield".

*type*type*click*

Bill Frissel, Charlie Haden, Lyle Mays, Dave Holland, and many more.

Okay, so they're not all guitarists, but they're jazz; and I did find some new interesting names.

I wonder what happens if I add a few more names to the initial list: "Scott Henderson" and "Wayne Krantz".

*type*type*click*

Awesome! Mike Stern, Al DiMeola, Larry Coryell,
John McLaughlin, Allan Holdsworth, Robben Ford, Pat Martino, Larry Carlton, and on and on and on.

Just what I need. Some of them were even in the Fusion sub-genre of Jazz, like the names in the original list (well, except Metheney).

BTW, you'll yield much better results by enclosing multi-word search queries (like ours above) within double-quotes.

4 Steps to Telephone Authentication

2006-02-16T07:59:00.004-05:00

This article explains how you can use the telephone to authenticate users, using the TeleAuth web-service.

TeleAuth provides an API that allows you to call a user and request a numeric secret in real-time. It can be used within web-based applications, console apps, or for network services.

It can also be used with online shopping sites to do things like collecting credit-card information, or delivering pass-codes.

Step 1. Sign Up

Visit http://www.teleauth.com and sign up for a beta account.

Step 2. Create an API Key

Log into your account, and click the "Add New Key" link. A new API key will be generated for you to use in your SOAP or XML-RPC requests.

Step 3. Test It

Expand the "Test Call" tab, and select an API Key. Then, enter a North American phone number, and select a prompt. The prompts are what the receiver hears when he/she receives a call (e.g., "Enter PIN code", or "Enter your credit-card number").

Click "Place Call" to initiate the phone call. The call status is updated in real-time on the page.

The phone should receive a call in a matter of seconds. Answer it, and enter some digits on the dial-pad. As soon as you hit the "#" key, you should see the result on the page.

Step 3. Try Some Code

Here's a simple Ruby program that calls a phone number and requests a PIN code:

#!/usr/bin/env ruby

require 'soap/wsdlDriver'
require 'cgi'

WSDL_URL = "http://teleauth.com/phone/service.wsdl"
soap_client = SOAP::WSDLDriverFactory.new(WSDL_URL).create_rpc_driver

# Log SOAP request and response
soap_client.wiredump_file_base = "soap-log.txt"

# Place the phone call
response = soap_client.getSecret( "SKJDekqQ4wUBiJEGFpkgA8Ph0bkkAXb",
    "15556673323", "pin")

# Display reponse
puts response.result, " / ", response.secret, " / ", response.message

Above, we use the SOAP WSDL-schema from http://teleauth.com/phone/service.wsdl, and call the "GetSecret" method. The parameters we provide are: the API key, a phone number, and a voice-prompt.

The return values are:

result: The result code. Usually "OK", or "ERROR".
secret: The digits dialed on the key-pad (PIN code, credit-card number).
message: An error message, if the result was "ERROR".

Step 4. Use It

And there we have it. TeleAuth supports both SOAP and XML-RPC. Use it with Rails. Use it with Java. Use it with Z80 Assembler if you wish.

The service is currently in beta, and is currently looking for testers.

Enjoy.

Useful OS X Shortcuts

2006-01-07T09:10:00.000-05:00

When you spend 99% of your time on the terminal, it's nice not to have to use the mouse... _at all_. And this is quite close.

OS X has a feature called "Full Keyboard Access", that needs to be enabled before the following will work.

Ctrl-F1 Enable/Disable Full Keyboard Access
Ctrl-F2 Access Menubar
Ctrl-F2 Access Dock
Ctrl-F7 Navigate controls in current dialog

More full-access shortcuts at the Apple Support Page.