Tuesday, March 3, 2009

Jaro-Winkler implementation in Ruby for User-Agent matching

Working in the mobile web, it's hard to keep up with the constant glut of devices on the market and their rapidly evolving capabilities. Of course, progressive enhancement is key; the markup you use in a mobile site should be minimal and look good without any CSS, JavaScript, or images, which is the worst-case. But we don't want to stop there; we want our sites to look as good as they can on as many mobile devices as possible.

WURFL is here to help with that. A crowd-sourced database of mobile devices, updated regularly, WURFL gives you detailed information on the capabilities of over 10,000 mobile devices indexed by user-agent string and grouped by manufacturer. It's relatively straightforward to set up a cronjob for a rake task that downloads an updated WURFL file and stores it in a table in your database; using an ActiveRecord model, you can then query the data provided by WURFL to get all the details for any device which has a user-agent string in the database.

But device makers throw a wrench in these efforts: user-agent strings are frequently updated or modified from their canonical form without rhyme or reason.

Fortunately, we have the Jaro-Winkler distance algorithm, which gives us a quick-and-dirty matching algorithm for strings that are mostly the same but may vary in arbitrary ways. Using this algorithm, we can run indexed queries for exact matches, then pull in some subset (perhaps matching the first 20 characters of the mystery UA string), iterate over these devices, and find the best match to return. Failing to find any implementation of the Jaro-Winkler algorithm in Ruby, I had to cobble together my own; I hope you find it useful.

module JaroWinkler

    def self.distance(str1, str2)

      if str1 == str2
        return 1

      # str2 should be the longer string
      if str1.length > str2.length
        tmp = str2
        str2 = str1
        str1 = tmp

      lmax = str2.length

      # arrays to keep track of positions of matches
      found1 = Array.new(str1.length, false)
      found2 = Array.new(str2.length, false)

      midpoint = ((str1.length / 2) - 1).to_i

      common = 0

      for i in 0..str1.length
        first = 0
        last = 0
        if midpoint >= i
            first = 1
            last = i + midpoint
            first = i - midpoint
            last = i + midpoint

        last = lmax if last > lmax

        for j in first..last
          if str2[j] == str1[i] and found2[j] == false
            common += 1
            found1[i] = true
            found2[j] = true

      last_match = 1
      tr = 0
      for i in 0..found1.length
        if found1[i]
          for j in (last_match..found2.length)
            if found2[j]
              last_match = j + 1
              tr += 0.5 if str1[i] != str2[j]

      onethird = 1.0/3
      if common > 0
        return [(onethird * common / str1.length) +
                (onethird * common / str2.length) +
                (onethird * (common - tr) / common), 1].min
        return 0


This will return a value such that 0 <= value <= 1. Matches near the beginning of the strings are weighted more heavily than matches near the end, making this a good algorithm to use with user-agent strings which are typically long and have minor variations toward the end.

That said, this isn't necessarily the optimal method to detect user-agent strings, and since it can easily give false positives in cases where a desktop and a mobile version of the same browser exist, it should be used in conjunction with a whitelist of known desktop browsers (which, though substantial, is much shorter than the list of all mobile browsers). So I offer this code with the disclaimer that Jaro-Winkler may not be the most effective algorithm for user-agent string matching.

By the way, I'm just learning Ruby, so if I'm doing anything atrocious here please let me know.

Wednesday, February 25, 2009

Asynchronous Image Caching with the iPhone SDK

Coming from the web world, I'm used to not having to think about all the functionality implicit in the humble HTML <img> tag, including client-side resource caching and asynchronous loading. In fact, the browser will cache any resource sent with the appropriate HTTP response headers, but by far the most common use of this cache behavior on most websites is images of all kinds.

So in building a couple of simple iPhone apps recently that display a list of search results retrieved from a server call, one piece that was missing was an asynchronous image loader that retrieves and displays thumbnail images in UITableViewCells.

[UIImage imageWithData:[NSData dataWithContentsOfURL:url]] gives you default iPhone HTTP caching behavior using NSURLCache, but it turns out that's not good enough: NSURLCache only stores URL contents in memory for the duration of the use of the application. We also need a URL cache that writes results to disk so that frequently-accessed responses only, and it also needs to manage its capacity. After that, we need an image loader that will abstract away the work of downloading images asynchronously, so that when a cell needs an image, it can request the image from the CachedImageLoader, and the CachedImageLoader will call back with the image, whether loaded from cache or remotely. Let's start with the data cache, DiskCache, which simply caches NSData objects in files in the application's file path:

extern const NSUInteger kMaxDiskCacheSize;

@interface DiskCache : NSObject {
        NSString *_cacheDir;
        NSUInteger _cacheSize;
        NSUInteger _diskCapacity;

@property (nonatomic) NSUInteger diskCapacity;
@property (nonatomic, readonly) NSString *cacheDir;
@property (nonatomic, readonly) NSUInteger size;

+ (DiskCache *)sharedCache;

- (NSData *)dataInCacheForURLString:(NSString *)urlString;
- (void)cacheData:(NSData *)data
                  request:(NSURLRequest *)request
                 response:(NSURLResponse *)response;
- (void)clearCachedDataForRequest:(NSURLRequest *)request;


The implementation for this one will be pretty straightforward: it's a singleton class that obscures as much activity as possible, including the cache path and file naming scheme (the implementation actually just uses the original URL filename, though this is potentially brittle when resources with the same name are located in different paths). One detail that I find interesting is determining folder size, which is less straightforward than I expected under Cocoa. To determine the size of all files in a given directory, you have to walk the directory and add up their sizes:

- (NSUInteger)size {
    NSString *cacheDir = [self cacheDir];
    if (_cacheSize <= 0 && cacheDir != nil) {
        NSArray *dirContents = [[NSFileManager defaultManager]
        NSString *file;
        NSDictionary *attrs;
        NSNumber *fileSize;
        NSUInteger totalSize = 0;

        for (file in dirContents) {
            if ([[file pathExtension] isEqualToString:@"jpg"]) {
                attrs = [[NSFileManager defaultManager]

                fileSize = [attrs objectForKey:NSFileSize];
                totalSize += [fileSize integerValue];

        _cacheSize = totalSize;
        DLog(@"cache size is: %d", _cacheSize);
    return _cacheSize;

Here, I'm only interested in files with the "jpg" extension, though this is the only hard-coded reference to images in the entire implementation and could easily be changed. Note the Objective-C syntax

for (NSString *file in dirContents)

which is known as fast enumeration and gets compiled down into pointer arithmetic, much faster than indexing using NSArray's objectForKey: method. Perhaps there's a more concise way to perform this task, but I haven't run across it yet.

While we're here, it's also worth taking a look at the mechanism for trimming the old files out of the disk cache when it reaches capacity. This involves first filtering the directory contents, then sorting the filtered contents by date modified; welcome to the wonderful world of NSArray sort functions:

NSInteger dateModifiedSort(id file1, id file2, void *reverse) {
    NSDictionary *attrs1 = [[NSFileManager defaultManager]
    NSDictionary *attrs2 = [[NSFileManager defaultManager]

    if ((NSInteger *)reverse == 0) {
        return [[attrs2 objectForKey:NSFileModificationDate]
                compare:[attrs1 objectForKey:NSFileModificationDate]];

    return [[attrs1 objectForKey:NSFileModificationDate]
            compare:[attrs2 objectForKey:NSFileModificationDate]];

- (void)trimDiskCacheFilesToMaxSize:(NSUInteger)targetBytes {
    targetBytes = MIN([self diskCapacity], MAX(0, targetBytes));
    if ([self size] > targetBytes) {
        NSArray *dirContents = [[NSFileManager defaultManager]
                                directoryContentsAtPath:[self cacheDir]];

        NSMutableArray *filteredArray = [NSMutableArray 
                                arrayWithCapacity:[dirContents count]];
        for (NSString *file in dirContents) {
            if ([[file pathExtension] isEqualToString:@"jpg"]) {
                [filteredArray addObject:[[self cacheDir]

        NSInteger reverse = 1;
        NSMutableArray *sortedDirContents = [NSMutableArray arrayWithArray:
        while (_cacheSize > targetBytes && [sortedDirContents count] > 0) {
            id file = [sortedDirContents lastObject];
            NSDictionary *attrs = [[NSFileManager defaultManager]
            _cacheSize -= [[attrs objectForKey:NSFileSize] integerValue];
            [[NSFileManager defaultManager] removeItemAtPath:file
            [sortedDirContents removeLastObject];

Next, we take a look at the CachedImageLoader, which uses a protocol ImageConsumer to for its clients; this keeps us from being locked into any particular image renderer (such as UITableViewCells or what have you); in fact, it's used in a few different places in the GoTime apps:

@protocol ImageConsumer <NSObject>
- (NSURLRequest *)request;
- (void)renderImage:(UIImage *)image;

@interface CachedImageLoader : NSObject {
        NSOperationQueue *_imageDownloadQueue;

+ (CachedImageLoader *)sharedImageLoader;

- (void)addClientToDownloadQueue:(id<ImageConsumer>)client;
- (UIImage *)cachedImageForClient:(id<ImageConsumer>)client;

- (void)suspendImageDownloads;
- (void)resumeImageDownloads;
- (void)cancelImageDownloads;


Again, this is a singleton class, which is basically a wrapper for NSOperationQueue, which is a really handy high-level threading implementation. (There are reports that NSOperationQueue is broken on OS X Leopard, but the single-core chip architecture on the iPhone avoids the cause of this bug, so it can be safely used; indeed, I haven't had any problems with it.) NSOperationQueue allows you to add NSOperations, which get run FIFO on a number of threads specified in maxConcurrentOperationCount. I've found that a single image download thread is sufficient, even on edge networks: the network speed is always the bottleneck, not lack of concurrency. This allows the implementation of CachedImageLoader to be single threaded (counting the operation thread) and use synchronous downloading. A image consumer needing an image implements the ImageConsumer protocol, then calls addClientToDownloadQueue: passing itself as the argument:

- (void)addClientToDownloadQueue:(id<ImageConsumer>)client {
    UIImage *cachedImage;
    if (cachedImage = [self cachedImageForClient:client]) {
        [client renderImage:cachedImage];
    } else {
        NSOperation *imageDownloadOp = [[[NSInvocationOperation alloc] 
                                object:client] autorelease];
        [_imageDownloadQueue addOperation:imageDownloadOp];

- (void)loadImageForClient:(id<ImageConsumer>)client {
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];

    if (![self loadImageRemotelyForClient:client]) {
        [self addClientToDownloadQueue:client];

    [pool release];

In cachedImageForClient, CachedImageLoader uses both the in-memory NSURLCache as well as our DiskCache class above, in turn. Failing to find the image in the cache, the loader creates an NSInvocationOperation which, in turn, gets called on our download thread; we create an autorelease pool and download the image synchronously, caching the image data when we have it (in both DiskCache and NSURLCache.)

So there you have it, most of an implementation of an asynchronous, caching image downloader for iPhone.

UPDATE 11/26/2009: The complete source code for the cache is available here.

Tuesday, February 24, 2009

Cracking Supercollider

SuperCollider is an amazing language, if you are in the super genius club who can understand the extensive documentation or pursue graduate studies at CCRMA. I've been out of audio synth for a while, but recently found myself needing to apply a recursive delay line to an audio recording I'm working on for my music project, Midday Veil.

SuperCollider dates from the mid-90's, and is thus a peer to Ruby, sharing influences like Smalltalk and Lisp. As languages go, it's pretty nice, though the compiler leaves something to be desired - inexplicably, variables must be declared before use at the top of a function, much like in C. Other than minor gripes like that, it's a pretty nifty package: functions as first-class objects, native arrays and maps, garbage collection, dynamic typing, and classical OOP features to boot. However, there's a lot more to the platform than just the language, and the learning curve is quite steep. Much like Ruby, some of the syntax is "optional" or has multiple ways to express the same thing; functions need a "value" message sent to them to be executed. Also, most of even the basic language-level concepts are mixed in with advanced platform-specific concepts like OSC messaging, client-server internals, audio buffers, and so on, so getting your feet wet takes a lot of immersion in the concepts to understand SuperCollider's terse yet expressive syntax and impressive power. Getting started with Processing, which uses a much uglier language, is a cakewalk by comparison.

It doesn't help that the "introductory tutorial" launches first thing into a detailed description of how to use the platform to send OSC messages over the Internet, then SynthDefs, then SynthDescLibs, and then instantiating both them and their UDP equivalents, none of which, it turns out, are required to get started, when you really just want to figure out how to play a sound file from your hard disk and feed it through some reverb. Oh no, you don't get to that until you've drudged through page after page of detailed docs, explaining each concept in depth before moving on to the next incremental step. Memo to documentation writers: people (especially people making music) need to be able to sit down and play something after their first lesson. You don't come home from your first piano lesson with a stack of reading on Cristofori and the development of the modern soundboard, told that maybe you can start playing after you've written a 200-page treatise on the inner mechanics of the thing. Oh sure, that's all useful to understand before too long, but to start off you want to learn just enough of a subset of the thing to feel like you can begin to be creative with it. For an example of just how jargony the whole thing feels, I treat you to an excerpt from page 3 of the docs:

When notated as code in client programs, the engines have two essential parts: a name and a function. In the jargon of SuperCollider, the function is called a ugenGraphFunc. The term ugenGraphFunc derives from the notion of a graph, which is the data structure that SuperCollider uses to organize unit generators. SuperCollider constructs the graph for you from the code it finds in your function which means that don't have to know how a graph works or that it even exists.

Ok, so basically it's a parse tree with a funny name. I assumed something like that was under the hood, but if I don't have to know this, why the hell are you telling me on page 3 of the documentation?

With that in mind, I present to you my first hard-won miniature piece of software in SuperCollider, which I wrote from scratch with scant help from the docs:

 r = { |input, gain, decayTime = 0.5, decayFactor = 0.9|
 var output, buf;
 if (gain > 0.1, {
         buf = Buffer.alloc(s, 44100, 2);
         output = input + r.(BufDelayC.ar(
             ), gain * decayFactor)
     }, {
         output = 0

 var filepath = "remember-pans-cropped.aiff";
 var synth = Buffer.cueSoundFile(s, filepath, 0, 2);
 r.value(DiskIn.ar(2, synth), 1, 0.5, 0.9);

Ok, it ain't much, but it's mine and I'm proud of it. I'll probably look at that example a few months from now and cringe knowing all the mistakes I just made, but know what? Hell with it. This is music, and if you leak a bit of memory here or there on your own machine before you learn how to fix it, well, that's not too steep a price for some wicked tunes. Start with what you want, then learn just enough to get yourself there.