Ben Lynn: Openly Geeky

List Comprehensions in C

2011-04-07T21:12:00.000-07:00

Some introductions to Haskell monads begin with the IO monad. After a lot of study and setting up a few functions, you can write lines of Haskell guaranteed to execute exactly once in the order of appearance, with errors handled appropriately.

Congratulations, you’ve waded through large tracts of theory only to acheive what C programmers take for granted. Monads are undoubtedly a formidable weapon for pure functional programmers battling with side-effects, but what do imperative programmers care?

On the other hand, list comprehensions impress veteran coders of all stripes due to their astounding conciseness, and hence are a more universally appealing showpiece for monads. Consider a simple example:

[(x,y) | x <- [1,2,3], y <- [1,2,3], x /= y]

which is:

[(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]

Wouldn’t it be great if C could do this? Our goal for this post is to get list comprehensions in C, preferably without learning anything about monads!

A spoonful of syntactic sugar

How do list comprehensions automatically try all combinations of x and y? Does Haskell have a special list comprehension parser that generates loops and stuff?

Kind of. There is a special parser, but it merely converts our list comprehension into:

do x <- [1,2,3]
   y <- [1,2,3]
   True <- return (x /= y)
   return (x,y)

This hardly differs: some argue it is so close to the original that list comprehension should be rarely used. There are still no signs of any list operations, nor loops. We’re no closer to solving the mystery.

On the bright side, it now resembles C enough that we can consider translating it.

Let me C

A first attempt:

BEGIN_DO;
  int a[] = { 1, 2, 3, 0 };
  int b[] = { 1, 2, 3, 0 };
  ASSIGN(x, a);
  ASSIGN(y, b);
  if (*x != *y) printf(" (%d, %d)", *x, *y);
END_DO;

We’ll figure out the macro definitions in a second. We’re taking a few shortcuts here. We’ve only translated the first two <- expressions. We terminate the arrays with 0. And instead of returning a list of tuples, we simply print them out.

If the ASSIGN macros could change the above into two nested for loops then we’d be done:

for(*x = a; *x; x++) {
  for(*y = b; *y; y++) {
    if (*x != *y) printf(" (%d, %d)", *x, *y);
  }
}

Unfortunately, the ASSIGN lines are self-contained; if we translate them to for loops they’ll stay unnested. Instead, we can use computed goto to get the same effect:

#define BEGIN_DO do { \
void *stack[128]; \
int stacki = 0; \
stack[stacki] = &&label_end

#define END_DO goto *stack[stacki]; label_end: ; } while(0)

#define ASSIGN(x, a) \
int *x, *x##next = a; \
stack[++stacki] = &&label_##x; \
label_##x: if (!*(x = x##next)) goto *stack[--stacki]; else x##next = x + 1

It looks horrible, and we needed GNU C extensions, but we’ve hidden loops in the macros, just as Haskell must be doing.

Another spoonful

It turns out Haskell’s do and <- are themselves syntactic sugar. Our example in fact expands again to:

[1,2,3] >>= (\ x -> [1,2,3] >>= (\y -> return (x/=y) >>=
   (\r -> case r of True -> return (x,y)
                    _    -> fail "")))

This is unsweetened Haskell code. Still no loops, but we’ve learned those separate lines of Haskell are really one big line: later lines are function evaluations nested within earlier lines.

Simulating nested for loops in C was on the right track after all. However, we should have used nested functions. The extra flexibility and power should help complete the conversion.

This time, we’ll build a list of elements instead of just printing them. Also, let’s replace the tuple (x,y) by the integer x+y so we can stick to integers and lists of integers; we can find a C equivalent for Haskell lists and tuples another day.

Intuition suggests all our functions should work with lists; then they’ll look alike, which should make macros easy to write. This implies we must occasionally package integers in singleton lists. We wind up with:

int *f0() {
  int a[] = { 1, 2, 3, 0 };
  int b[] = { 1, 2, 3, 0 };

  int x;
  auto int *f1();
  {
    int *r = list_0();
    for(int *p = a; (x = *p); p++) r = list_cat(r, f1());
    return r;
  }

  int y;
  auto int *f2();
  int* f1() {
    int *r = list_0();
    for(int *p = b; (y = *p); p++) r = list_cat(r, f2());
    return r;
  }

  int z;
  auto int *f3();
  int* f2() {
    int *r = list_0();
    for(int *p = list_1(x != y); (z = *p); p++) r = list_cat(r, f3());
    return r;
  }

  int* f3() {
    if (z) return list_1(x + y);
    return list_0();
  }
}

where list_0 returns an empty list of integers, list_cat concatenates two lists of integers, and list_1 creates a singleton list containing the given integer. The functions f0 and f1 take on the roles of the two nested for loops from our previous attempt, only now they also concatenate the values they compute.

Because forward-declaring functions is difficult with macros, we introduce an array of function pointers so one function can call the next. Also, since C doesn’t do pattern matching, we’ll cheat with an ad hoc macro. The full program:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BEGIN_DO ({ \
  int *(*fun[64])(int); \
  int funi = 0

#define END_DO fun[0](0); \
})

#define ASSIGN(x, a) int x; \
int *x##fun(int i) { \
  int *r = list_0(); \
  for(int *p = a; (x = *p); p++) r = list_cat(r, fun[i+1](i+1)); \
  return r; \
} \
fun[funi++] = x##fun

#define MATCH(x, a) int* match() { \
  if (x) return a; \
  return list_0(); \
} \
fun[funi++] = match

int *list_0() {
  int *r = malloc(sizeof(*r));
  *r = 0;
  return r;
}

int list_len(int *a) {
  int *x = a;
  while(*x) x++;
  return x - a;
}

int *list_cat(int *a, int *b) {
  int m = list_len(a), n = list_len(b);
  int *r = realloc(a, sizeof(*r) * (m + n + 1));
  memcpy(r + m, b, sizeof(*r) * n);
  r[m+n] = 0;
  free(b);
  return r;
}

int *list_1(int n) {
  int *r = malloc(sizeof(*r) * 2);
  *r = n;
  r[1] = 0;
  return r;
}

int main() {
  int *r = BEGIN_DO;
    int a[] = { 1, 2, 3, 0 };
    int b[] = { 1, 2, 3, 0 };
    ASSIGN(x, a);
    ASSIGN(y, b);
    ASSIGN(z, list_1(x != y));  // Memory leak.
    MATCH(z, list_1(x + y));
  END_DO;

  // Should be 3 4 3 5 4 5.
  for(int *x = r; *x; x++) printf(" %d", *x);
  putchar('\n');
  free(r);
  exit(0);
}

At last! List comprehensions in C.

Haskell’s list monad

Haskell does not need zany macros. Instead, it has:

instance Monad [] where
  return a = [a]
  xs >>= f = concat (map f xs)
  fail _ = []

Mystery solved. The >>= operator is like our ASSIGN macro: they both compute a function on each element of a list and concatenate all the results. The return function is our list_1 function, and fail is our list_0.

In both languages, we made looping over lists invisible by writing a routine that converts an integer into a list (just put it in a list of size one) and another that runs a function on lists of integers even though the function normally takes integers (just run the function on each integer in the list, then concatenate the results).

We can generalize this idea to hide other kinds of repetitive code. This is precisely what Haskell monads are, and why do notation exists. Roughly speaking, we augment the abilities of existing functions by describing how to convert a regular output into a new and improved type (monadic type) and how to get a function to operate on monadic types when it expects the regular type.

It’s cool that we can get the same effect in C. Nevertheless:

Haskell has a few lines of robust, clean code instead of fragile, ugly macros.
This design may never occur to a C programmer, while monads are ubiquitous in Haskell.
Monads mesh well with pattern matching, which C lacks.

A comprehensions compromise

Our macros were challenging to write because their combined output must be nested. It’s why we needed computed goto and a stack of labels when simulating nested for loops, and why we needed an array of function pointers when we moved to nested functions.

It would be easier if we tolerated nesting:

int* assign(int *x, int *a, int *(*fun)()) {
  int *r = list_empty();
  for(int *p = a; (*x = *p); p++) r = list_cat(r, fun());
  return r;
}

int *lamb() {
  int a[] = { 1, 2, 3, 0 };
  int b[] = { 1, 2, 3, 0 };
  int x;
  auto int *lamb();
  return assign(&x, a, lamb);
  int *lamb() {
    int y;
    auto int *lamb();
    return assign(&y, b, lamb);
    int *lamb() {
      int z;
      auto int *lamb();
      return assign(&z, list_1(x != y), lamb);
      int *lamb() {
        return z ? list_1(x + y) : list_empty();
      }
    }
  }
}
int *r = lamb();

The code is verbose, because at several points, one line declares a function, another calls it, and a third defines it. All three would coalesce into a single line if C had lambda expressions. Frustratingly, GNU C supports closely related nested functions but not anonymous functions. Why not? Even standard C++ is getting lambda expressions! However, if we tolerate one macro, we can ease the pain:

#define ASSIGN(x, a) \
  int x; \
  auto int *lamb(); \
  return assign(&x, a, lamb); \
  int *lamb()

...

  int *lamb() {
    int a[] = { 1, 2, 3, 0 };
    int b[] = { 10, 20, 30, 0 };
    ASSIGN(x, a) {
      ASSIGN(y, b) {
        ASSIGN(z, list_1(x != y)) {
          return z ? list_1(x + y) : list_empty();
        }
      }
    }
  }
  int *r = lamb();

While messier than Haskell, it is still readable. Moreover, the nested braces may aid seasoned imperative programmers, who might incorrectly think the Haskell do notation represents statements executing one after another. Here, it is unmistakeably clear we are nesting function calls.

Convert line breaks? No!

2011-04-06T10:20:00.001-07:00

When I moved my blog to this site, I left the default settings alone. Unfortunately one of them was "Convert line breaks". While harmless at first, it eventually caused headaches when editing HTML for fancier formatting. Turning off the option destroyed all paragraph breaks in older posts, so I had to leave it on for their sake.
I believe Blogger no longer has this problem: on a new test blog, flipping the switch appeared to have no effect on existing posts. However, my blog predates this change.
Googling yields many reports of trouble with this maleficent option. Some suggest a laborious method of disabling it: turn it off, then break paragraphs in old posts by hand!
Such advice was probably written before Blogger gained the export and import features, which are the key to a simpler but scarier solution:

Export the blog, from the "Basic" tab under "Settings".
In the "Edit Posts" tab under "Posting", select all posts.
Delete them all!
import the blog and publish all posts, again from "Basic" tab under "Settings".

Now you can say no to "Convert line breaks" without trashing ancient posts, though when editing new posts, you still have to select "Use <br /> tags" under "Post Options" to get the desired behaviour.
It works because the export format robustly represents line breaks with HTML tags whether or not the evil option was on when the post was written. Take care: after I exported my blog, I got distracted by the recently added "Spam" tab under "Comments", and found a non-spam comment sequestered within. I freed it, but forgot to re-export my blog, so after I deleted all posts and imported my blog, the comment was lost forever.
The export format has also given me ideas for my script that publishes HTML posts via the Blogger Data API, which has a hard time preserving formatted source code. Unfortunately, frequent experiments have temporarily barred my script:

Blog has exceeded rate limit or otherwise requires word verification for new posts

I’ll try again another day.

Permalink Pain

Unfortunately, I belatedly discovered serious manual editing is still required. Permalinks have changed; they now put the day of the month in the URL. Restoring old entries generates the new kind of permalink, invalidating all existing links to old posts.

Tagline-Oriented Programming

2011-04-03T17:07:00.001-07:00

In the land of "tl;dr", the one-liner is king. Short is sweet, and also highly contagious. A paragraph is easy to ignore, while a good tagline embeds itself in a reader’s mind against their will, spreading independently of the accompanying product.

In programming, some one-liners are equally alluring. There is only room for the bare essentials: we must distill the purest form of solutions to problems. Their brevity makes them memorable, and awe-inspiring, as shrinking code can take considerable skill; most recently, I’ve been stunned by a 1433-character chess engine in C.

Having already praised Bash one-liners, this time I’m taking a shallow look at Haskell, and in particular, a trivial function:

emp :: a -> ([b] -> a) -> [b] -> a
emp a f [] = a
emp a f (x:xs) = f (x:xs)

Or since we’re advocating one-liners:

emp a f x = if null x then a else f x

Why? In Haskell, recursion on lists often goes like this:

f []     = empty_list_case
f (x:xs) = recurse_somehow x f(xs)

The emp function let us combine these two lines into one. The fold family of functions is similar: for them, the 2nd argument handles the empty-list case, while the 1st argument is a function that describes how to process the next element. However, they are insufficiently general for our purposes.

Should we go to this trouble just to squeeze the empty-list case into the same line as the inductive step? Yes, if you share my appreciation for one-liners! Also:

this is a natural extension of the precedent set by the fold family
it’s harder to forget about the base case
single lines suit interactive Haskell (if you do type these in, remember to add "let" in front of the definitions).

Examples

Here’s foldl and foldr in one line each:

foldr f z = emp z $ \(x:xs) -> f x (foldr f z xs)
foldl f z = emp z $ \(x:xs) -> foldl f (f z x) xs

And the membership test:

elem x = emp False $ \(y:ys) -> x==y || (x `elem` ys)

All subsequences (though in an order differing from Data.List.subsequences):

sub = emp [[]] $ \(x:xs) -> sub xs ++ (map (x:) (sub xs))

How about all permutations? In C, where we can loop through an array and swap elements in place, an easy but impure recursive solution takes every element in turn, temporarily swaps it to the first position, then calls itself on the remainder of the elements, where the lowest level of recursion prints the whole buffer.

In Haskell, I found it easiest to do something similar by maintaining 2 lists on either side of a selected element. My first attempt came out as:

-- Invoke with: p "" "" "abc"
p a [] [] = [a]
p [] ys [] = []
p a ys [] = map (a++) (p [] [] ys)
p a ys (x:xs) = (if null a then (p [x] ys xs) else []) ++ (p a (x:ys) xs)

It’s unclear how to rewrite this in one line. Perhaps it’s best to break the problem into two sub-problems to get one-liners. The following is based on elegant code found on a mailing list:

f = emp [] $ \(x:xs) -> (x,xs):[(y,x:ys) | (y,ys) <- (f xs)]
perm = emp [[]] $ \xs -> [y:zs | (y,ys) <- (f xs), zs <- (perm ys)]

The helper function f is the FP version of iterating through a list and plucking an element out, and has uses outside this problem.

Integers

A similar definition for integers is also handy:

induct a f x = if 0==x then a else f

For starters, we can define emp with induct:

emp a f = induct a f . length

List all n-letter strings consisting of the letters in "BEN":

f = induct [""] $ \n -> [x:xs | x <- "BEN", xs <- f (n-1)]

Compute an n-bit Gray code:

g = induct [""] $ \n -> (map ('0':)) (g (n-1)) ++ (map ('1':)) (reverse (g (n-1)))

Though shallow, Haskell would gain from default induct and emp functions. (Perhaps there already are? I don’t know Haskell that well.) They bring the length of many interesting function defintions under a mystical threshold that makes them catchy and appealing.

CMU -= OOP, CMU++;

2011-03-27T01:50:00.001-07:00

I should have been a comedian. I have excellent timing.

I applied for Computer Science grad school during the irrationally exuberant dot-com boom, when much of my competition ran off chasing easy money. During the subsequent crash I was already a sheltered student. By the time I finished, the economy was up again. My lucky streak continued as I managed to secure a job before the global financial crisis struck.

However, I’m most thankful that I was amongst the last batch of students of my undegraduate CS program who were only taught object-oriented programming in an optional course.

It wasn’t just my alma mater. According to an interview with a CS professor emeritus at NYU, around that time, many universities bowed to pressure to switch to Java and focus less on fundamentals. This produced less capable programmers, or as the article puts it, “today’s Java-savvy college grad is tomorrow’s pizza-delivery man”. Again, my competition was decimated merely because of timing.

Apart from increased job security, I’m grateful I learned less object-oriented nonsense and more CS, as I’m deeply interested in the subject. In fact, this is why I chose to study CS; I’m just fortunate I happen to live in a time and place where coding is a marketable skill.

Now that I can afford to be less selfish, I wish universities would undo this injustice and remove object-oriented programming from introductory CS curriculums, so future students can benefit, just as Carnegie Mellon University is doing. CMU's decision inspired me to post this entry, and update my page denouncing object-oriented programming.

Business

While some applaud the move, others state that learning a language and programming paradigm rarely seen in industry leaves a student ill-prepared.

My own experience suggests otherwise. I have little trouble coding in new programming languages so long as they’re not too esoteric. Granted, the first few lines are painful, as I’ll have to constantly look up keywords in a reference while acclimatizing to error messages and other peculiarities of the development environment. But after a while, I’ll pick up the syntax for arithmetic, loops, conditionals, function calls, and so on, and that’ll be enough to keep me going. I might miss out on idioms, but I can get my point across.

The difficult part is designing the underlying data structures and algorithms. That’s where CS is most magical. Functional programming gives me an edge. It makes recursion less scary, and recursion is often a great approach to a problem: sorting, parsing, anything with trees. Also, experience with lazy evaluation increases my awareness of parallelism.

I believe it also makes my code cleaner, because treating functions as first-class citizens opens my eyes to design choices I might otherwise miss. It’s hard to say: a Java fanatic might be trained to spot perfect places for anonymous inline classes.

In interviews, I let candidates choose the language as I’m more interested in the idea being expressed. Some candidates write code comfortably, but struggle with relatively simple tasks because they can’t find the right algorithm or data structure. They’re like an author with perfect spelling but who only know boring stories.

Others quickly find a good solution, but their code may have syntax issues here and there. These mistakes hardly bother me because after a week of seeing the same compiler error messages over and over again, their syntax will be as good as mine.

Personal

Although OOP was optional for me, I studied it with relish. I read “Design Patterns” cover to cover shortly after purchasing it. Bertrand Meyer’s words were gospel. Eiffel, a pure OO language, became my favourite. I promoted OOP more fiercely than I attack it now; back then I was even more obstinate. I believed the only path to virtues such as modularity, information hiding, and code reuse was through OOP, partly because I thought OOP folks invented these concepts.

Over the years, events caused me to pause and reexamine what I had been taught. Many lines of code later, I finally discarded OOP and freed myself. I felt cheated, which is why I’m more emotionally attached to this stuff than one might expect.

There’s no harm in learning OOP as long as you avoid my mistake and arm yourself with a healthy dose of skepticism (which you should do all the time anyway, including now).

UTF-8 good, UTF-16 bad

2011-02-07T20:51:00.001-08:00

Lately I’ve been programming in Go. I started by writing a few popular Unix tools in Go, before moving on to a lexer that supports structural regular expressions and UTF-8.

Unicode support was easy to add because Go lives and breathes UTF-8. But why did the Go designers favour UTF-8, and not UTF-16? Widespread software such as Windows, Java, and Python use UTF-16 internally, so why not Go?

Further reading revealed the answer. UTF-16 is a historical accident that persists mainly due to inertia. UTF-16 has no practical advantages over UTF-8, and it is worse in some ways. The Go designers knew what they were doing, so they chose UTF-8.

Down with UTF-16

Before, from vague hunches, I had thought that UTF-16 was simpler because each character took exactly 2 bytes (so it handled only a strict subset of Unicode), and that UTF-16 was more compact for certain languages.

The first statement is patently false. UTF-16 is a variable-length encoding, and hence not much simpler than UTF-8. As for the second: consider HTML. The amount of whitespace and tags in a typical document is high enough that UTF-8 is more compact than UTF-16. This generalizes to other formats, such as Go source code.

So there’s no upside. But there are plenty of downsides to UTF-16:

We must worry about byte ordering because UTF-16 deals with 16 bits at a time. A related drawback is the loss of self-synchronization at the byte level.
We lose backwards compatibility with ASCII.
We lose backwards compatibility with code treating NUL as a string terminator.
We cannot losslessly convert from byte streams.
The encoding is inflexible: hopefully 0x110000 code points should be enough, but if it were extended (again), UTF-16 would need major surgery. In contrast, by simply allowing up to 6 bytes, UTF-8 can handle up to 2³¹ code points.
Ugly encoding: it’s the reason why U+D800 to U+DFFF is reserved (though thankfully UTF-16 is self-synchronizing with 16-bit granularity).

I tired of thinking about the drawbacks of UTF-16, but there are likely more. Thus even if we only worked with a strange set of documents where UTF-16 is more efficient, the savings are too small to justify the complexity.

A living dead standard

How did so many projects settle on such a horrible standard? It’s a sad story. The original Unicode supported exactly 0x10000 code points, making UCS-2 (the precursor to UTF-16) attractive. Each character neatly corresponded to one 16-bit word. Although UTF-8 might still be preferable thanks to byte ordering and ASCII compatibility, UCS-2 is certifiably sane. People built systems based on UCS-2, and rejoiced that the codepage Stone Age was over.

Then an unnatural disaster struck: the Unicode Consortium decided more code points were needed. The supple UTF-8 got away unscathed, but there’s no way to squeeze more than 16 bits into UCS-2. Apart from abandoning UCS-2, the only recourse was to reserve a chunk of values for encoding the higher code points. Thus UTF-16 was born. Hopefully, developers could simply tweak masses of existing UCS-2 code for the new standard. Sadly, various UTF-16 bugs suggest that much code remains unaware UTF-16 is a variable-length encoding.

Despite the trauma it would cause, they should have killed UCS-2 when they had the chance. Now we have a grotesque encoding scheme that shambles alongside UTF-8.

Gauss was here

According to Wikipedia, UTF-8 was built on ASCII by Rob Pike and Ken Thompson. ASCII was developed from telegraph codes by a committee. The telegraph codes stemmed from a Western Union code, which evolved from a code by Donald Murray, who modified a 5-bit code invented by Émile Baudot, who based his work on a code designed by Carl Friedrich Gauss and Wilhelm Weber. It’s awe-inspiring that the Prince of Mathematicians was involved. And if he were alive today, I bet he’d disparage UTF-16!

Spooked by a corrupt initrd image

2010-10-12T00:38:00.001-07:00

Halloween is approaching. It is apt I have a scary tale to tell.

I left my laptop on in the sun, on a surface with poor conductivity. As I opened it, I glimpsed it complaining of heat exhaustion before it powered off. (That’s happened to me before, too!) I let it cool off, but on booting Ubuntu, a terrifying message was all that appeared on the screen:

Error 16: Inconsistent filesystem structure

Uh oh. Did I lose everything? What haven’t I backed up lately? Indeed, what have I backed up lately?

I searched online for the error message, and took heart when others reported no data loss in various forums. Running fsck was suggested, though in at least one case they resorted to reinstalling the OS. No way I’m doing that!

My first instinct was to dust off my USB DVD writer and burn a Ubuntu rescue CD. This turned out to be unnecessary, but at least I was reassured when I used it to mount the Linux partition and found my files intact. Firing up fsck had no effect: I was still defeated by the same error message.

Playing with the GRUB command-line (by pressing “c” instead of selecting an kernel to boot) showed that the initrd image was corrupted, as selecting the newest image with the “initrd” command triggered the same error message.

The solution was easy. Boot up an older kernel, then download a fresh copy of the initrd image by running:

$ sudo apt-get install --reinstall linux-image-2.6.32-25-generic

Shameless plugs

2010-10-07T21:36:00.001-07:00

Better the head of a chicken than the tail of an ox. This Chinese proverb captures entrepreneurial thoughts I’ve long harboured. It’s a common affliction around my neck of the woods.

Unfortunately, I’m disinclined to abandon my cushy job to work my fingers to the bone for an uncertain reward. My dreams are likely doomed to remain dreams.

To compensate, I’m living vicariously through friends who are being their own boss. I’m devoting this post to them; may it contribute at least an iota to their success.

China Luxury Travel Network (CLTN.net)

Ethan lived on the ground floor of my apartment at Stanford. Early in my degree, he finished his Masters, in financial mathematics I think. I’m uncertain because we rarely chatted about school! I’m sure his latest venture will succeed, and not just because he’s capable.

I was in Ottawa for a conference in '03. I skipped half of it to hang out with Ethan, who gave me a tour of the city where he grew up, which became challenging when a widespread blackout hit the region. On top of all this, I had FedExed a visa document to his parent’s house (which I needed to return to the US), and he went out of his way to deliver it to me.

A few years later, I was in China on vacation, mainly because I wanted to see the Guangzhou Trade Fair. I met up with Ethan. I thought we’d do little more than catch up over a meal. Well, we did chat over dinner: Ethan had worked in Hong Kong’s finance sector for a while, and was now living off savings while exploring China. I was still a starving student.

But then Ethan took us to a health spa in Shenzhen which was cheaper yet far more luxurious than the hotels we had been considering. For about $20 a day I got massages, food, spas, haircuts, movies, a place to sleep, etc. I never thought I’d get a pedicure in my life, but because it was effectively free, I had to try it.

Then in Hong Kong, we crashed at his place, which saved a lot of money. He took us on a whirlwind shopping and eating tour. Soon after, we had to part ways, but not before he showed us a website offering discounted rates at hotels in Guangzhou. We got a great deal at a great hotel across the street from the trade fair. At the check-in counter, the guy in front of us was livid when he learned how little we were paying.

He offered to take me on a tour of China after the trade fair was over, but I declined. I deeply regret my decision. What’s a few weeks of missed grad school? Ethan spoke three or more Chinese languages. He knew where to go. He had contacts everywhere. Clearly, the China luxury travel business is perfect for him.

Embrace

Rahul lived a few apartments away from me in grad school. He mysteriously vanished one year. I heard later it was because he was “saving babies”. This raised yet more questions! Wasn’t he an engineer?

Certain problematic births are far less problematic when an incubator is available. Unfortunately, the cost of typical incubators often places them beyond the reach of poor remote villages, contributing to higher infant mortality. Rahul helped design a vastly cheaper incubator, and hopes to eventually supply one wherever babies are born.

Total Phase

I met Kumaran through his wife. I was a Teaching Assistant for an introductory computer science class she was taking. Kumaran wanted to meet partly because he wanted help recruiting people for his company. I was of no help: at the time, my engineer friends were already employed, and they were busy recruiting people themselves!

Total Phase’s biggest hit is a USB protocol analyzer, an invaluable tool when developing USB products. Kumaran loves being an engineer designing for engineers. They never bothered advertising since engineers tend to use logic to determine purchases, and their products are better and cheaper than those of their competitors. I saw parallels when I read about the HP200A, an audio oscillator that was profitable because it was the best and the cheapest.

Disc Eraser

My cousin Wade designed a simple tool to render CDs and DVDs unreadable. An easy motion etches deep parallel scratches into the media: Freddy Krueger for discs. Quick and safe. No batteries. No electricity. The disc stays in one piece, ready for recycling.

He used to work on hard drive platters at IBM (before they sold the division to Hitachi) so he knows what he’s doing. He verified his claims with AcoDisc, a data recovery company. After a single application of the Disc Eraser to a CD, the data was deemed unrecoverable.

I don’t burn much, let alone anything confidential, so it’s not something I need. However, I’m grateful for a sample he gave me: as a kind of therapy, I savagely mutilate CDs I receive as junk mail.

Bump

Dave was yet another electrical engineering student in my neighbourhood during grad school. I never would have guessed he would join the dark side and become a Pointy-haired Boss of a startup. Seriously though, I like tech companies with an engineer at the helm. And Dave’s hair is not pointy.

Years ago, a friend once pointed out that two people in the same room cannot easily get their laptops to talk to each other. Sure, there’s Bluetooth, ad-hoc wireless networking, and other hacks, but he was right: even now, it’s easiest for one party to verbally ask for contact details of the other. This is somehow troubling.

I remember a light-hearted news report I watched once, which described a gadget in Japan. You’d enter a few personal details, and carry it around. It would alert you if someone of the opposite sex nearby had the same gadget and had similar interests to you. What became of this? Couldn’t they do something like this so you would never have to spell out someone’s email address or type in a phone number?

Enter Bump, an app for iPhone and Android that attacks this problem in a cute way. Both sides run the app, then lightly bump their phones together to swap contact details, or other data. No physical contact is actually needed as the phones just have to be close enough, but smashing your fists together is more macho!

Millinery Kestralia

Kestrel lives a few streets away, which benefits me greatly because she is a good chef and a keen gardener. She also loves making hair accessories, and recently started selling them. Each handcrafted piece is unique and beautiful, like their creator.

Moore's Treadmill

2010-09-18T12:46:00.001-07:00

Early in my PhD, I told my advisor I had implemented a particular cryptographic algorithm with a tolerable running time. It wasn’t that fast, but I figured within 2 years, microchips would be twice as powerful, so my code might be practical even on handheld devices.

He replied: "No. Then they’ll halve the power consumption to double the battery life." Or they’ll want to run it on yet smaller devices. Laptops, phones, smart cards. I still had plenty of work to do.

For me, user interfaces are trapped on the same treadmill.

Less is more

Not so long ago, my desktop had a 14-inch CRT display, a lonely and lowly processor clocked at 200MHz, a few gigs of hard disk space, and a 14.4k net connection. The dearth of screen real estate favoured spartan user interfaces, the CPU struggled unless tools were quick and nimble, and the cramped conditions of the hard disk and net connection favoured good things in small packages.

For example, when the time came to take sides in the text editor holy war, I chose vi because it would only take several minutes to grab a few hundred kilobytes. Emacs was over 6 megabytes.

Now I often work at a PC sporting multiple cores, each over 20 times faster than my old workhorse. I have multiple monitors, each so large that I turn my head to look at different parts of a screen. Network latency is low, and bandwidth is high.

Yet I remain minmalist. Indeed, I keep finding new ways to trim the fat, despite having ample space. For instance, my first web browser had big buttons and a plethora of bars: title bar, menu bar, bookmarks bar, status bar, location bar, etc. Today, even though I can afford extra fluff, my primary browser shows little apart from the webpage: a bar for tabs (itself a space-saving measure over multiple windows), a single textbox, and a handful of buttons.

I chose my style partly because I’m a programmer to the bone: my drive to automate, simplify, and optimize carries over from coding to real life. However, there is a more compelling reason.

Technological advances mean my laptop can handle tasks that once required a desktop. But the laptop screen is even smaller than my old monitor. The net connection can be spotty, especially via tethering or a smartphone WiFi hotspot. The CPU often underclocks to save battery, and moreover, I fritter away cycles on fripperies such as visual effects: I’m a Compiz plugin junkie. I therefore encounter the same problems I faced over a decade ago.

A Voyage to Lilliput

Beyond laptops, we have netbooks, tablets, and smartphones. The world is getting smaller. Being a geek means I’ll attempt text editing, gaming, programming, etc. even as devices keep shrinking, bringing new user interfaces challenges. My current extreme case is my Nexus One, with its 3.7 inch display and no keyboard.

Rather than work on the phone directly, I ssh to a more powerful computer via ConnectBot.

In the past I praised Bash one-liners. Shelling in from a smartphone drove me to appreciate Bash one-letter aliases. I’ve grown accustomed to using them on all computers. Some favourites:

alias c=cd
alias ..="cd .."
alias v=vim
alias g=git
alias l="ls -CF --color=auto"
alias s=sudo
alias k=colormake
alias rm='echo mv to /tmp instead'

(The "rm" alias trains me to avoid this command. See "Accidents Will Happen" in The UNIX-HATERS Handbook.)

Editing is unpleasant but bearable. In these circumstances, I feel Vim’s single-letter commands work in its favour, as does its modal nature. Also double-tapping the terminal brings up an "Esc" button, which suits Vim beautifully.

I don’t intend to code from my phone often as it’s like eating with tweezers. Though for fun, I followed through a suggestion in my last post and developed a J one-liner to sum the primes less than 100 using only a ConnectBox session on my phone. Soon I had:

   +/p:i.p:^:(_1)100
1060
   +/i.&.(p:^:_1)100    NB. Cooler version.
1060
   v=:[:+/i.&.(p:^:_1)  NB. Tacit verb definition.
   v 100
1060

J and I

2010-09-09T07:09:00.001-07:00

For years, I’ve been meaning to investigate the APL programming language family. Months ago, I finally leafed through a few introductions to the new and improved APL known as J.

I liked what I saw. I enjoy paring down C code, but J makes my best efforts look as verbose as a legal contract. Introductory J examples are already cryptic enough to induce watering in the untrained eye. In the right hands, a J program can be compressed so densely that it threatens to collapse into a black hole of inscrutability.

I’ve heard about an obfuscated C tattoo, as well as a Lisp tattoo. They should have gotten J tattoos! Instead of Hello World or the Fibonacci sequence, why not sport a terse program that solves a Sudoku, or finds a QR decomposition of a matrix?

More generally, J appears to be ideal when source size matters most. For example, programming via a smartphone with a tiny screen and keyboard.

A day at play with J

J systems are freely available, but I reasoned I’d get a better feel for the language by writing my own interpreter. Thanks to J’s elegant design, I soon got the celebrated "mean=:+/%#" example working. That was enough to gain an appreciation (but also a little contempt) for J’s simple grammar, array handling, and above all, compact notation. A J symbol is worth a thousand machine words. See my J notes.

I kept picking at it for a while, but I think I’ll stop soon. It’d take substantial effort to implement types apart from doubles, not to mention error handling, memory management, arrays with axes of zero length, and fills.

Git repository: a primordial J interpreter.

The timeless beauty of shell scripts

2010-07-31T22:19:00.002-07:00

Long ago, Doug McIlroy wrote: “This is the Unix philosophy: Write programs that do one thing and do it well. Write programs to work together. Write programs to handle text streams, because that is a universal interface.”

Years later, Rob Pike observed: “Those days are dead and gone and the eulogy was delivered by Perl.” His statement mostly stands, except Python is the new Perl.

I refuse to abandon the old ways. So when a friend pointed me to the intriguing Python Challenge, I avoided Python as much as I could. Instead, I used the Bash shell to string together special-purpose tools.

The FAQ states the purpose of the challenge is to “provide an entertaining way to explore the Python Programming Language”, and “demonstrate the great power of Python’s batteries”. However, I feel it is better suited for training shell script muscles: most of the problems are of the one-shot trivial variety that suit Unix tools.

A full-featured language is often overkill. Abraham Maslow’s quote comes to mind: “It is tempting, if the only tool you have is a hammer, to treat everything as if it were a nail.” I don’t mean to disparage Python, but I feel shell scripts are often overlooked and under-appreciated, especially as they are so accessible. Technically, you’re already shell programming when you run a program from the command-line. Why not learn a bit of Bash or similar, and increase the power available at your fingertips?

Brevity is the soul of wit

While general-purpose scripting languages have their place, judging by the posted solutions, for typical riddles in the Python Challenge, a short Python script is often outdone by a shorter still Bash incantation. In fact, in the first challenge you can stay in your shell. Did you know Bash natively handles (fixed-width precision) arithmetic? For example:

$ echo $((2**42))

Naturally, if arbitrary precision were needed, we could invoke a specialized tool:

$ echo 10^100 | bc

Humble Unix tools yield the most succint solution for several challenges. For example, a Caesar shift is probably terser with tr than any popular language:

$ tr a-z l-za-m

Or extracting lowercase letters from a file:

$ tr -cd a-z

When regular expressions are involved, even though the code may look similar, the old guard such as awk, sed, and grep that feature regularly in Bash scripts have an inherent advantage over Python (and Perl, PHP, Ruby, …). Python takes exponential time to match some regular expressions whereas the classic Unix tools take polynomial time to match the same expressions.

On the downside, Bash makes some tasks tiresome. I can’t think of an easy way to convert an decimal number to an ASCII character. This Bash FAQ suggests the cumbersome:

$ for a in 66 101 110; do printf \\$(printf '%03o' $a); done; echo

Another chore is repeating a character a given number of times. Other than a loop, perhaps the easiest hack is something like:

$ printf "%042d" 0 | tr 0 x

A tiny elegant Haskell solution exists for problem 14, thanks to the transpose function and the language’s concise notation for recursion and composition. A search revealed Bash fans often employ a simple but tedious Awk script for matrix transposition, suggesting a Bash solution is necessarily significantly longer.

Happily, these blemishes are dwarfed by the successes of the Unix philosophy. More than once, my script has been simpler and briefer than any other posted solution because the complexity is hidden within a tool that does one thing, and does it well. My proudest achievement is a one-liner to compute the look-and-say sequence [hint: uniq -c].

Chinese Input

2010-07-11T22:45:00.001-07:00

Google Translate supplies a clumsy but straightforward means for entering Chinese characters with a US keyboard, especially for those learning the language. Simply type the English meaning, and copy the result. You can check the character is indeed the one you want by clicking on "Show romanization", or on the speaker icon to hear a synthesized reading.

However, sometimes I have a particular character in mind. A short-term solution is to use an online rendition of a traditional dictionary ordered by radical and stroke count, or a pinyin dictionary. Additional speed and convenience requires investment; one must learn one of the many fascinating methods for entering Chinese characters on a computer.

I’ve read that the Wubizixing input method is fastest, though as one might expect, it requires the most investment. Proficiency demands much practice with a suitably annotated keyboard.

For now, I’ve opted for the Wubihua method, which mimics how humans write characters. It may be slower, but it can be learned quickly. Also it applies when sending Chinese text messages on mobile phones.

I supplement Wubihua with a pinyin method, as I’m practically illiterate in Chinese.

Chinese input in Linux

To setup Chinese input methods in Ubuntu, I installed the scim and scim-pinyin packages, then modified my .xsession as follows. I prepended:

export XMODIFIERS="@im=SCIM"
export GTK_IM_MODULE="xim"

and appended:

scim -d

after which pressing Ctrl+Space toggles Chinese input.

"Stroke 5" is Wubihua mode. Stroke types are mapped to 5 keys along the bottom row. From right to left:

/: | (vertical; top-to-bottom)

.: \ (downwards left-to-right)

,: / (downwards right-to-left)

m: - (horizontal; left-to-right)

n: other stroke types, e.g: 乙

Perhaps one can remember this as follows: 乙 looks like a rotated N. A lowercase M takes more horizontal space than most letters, so it corresponds to the horizontal stroke. On the next two keys, the less-than and greater-than signs point left and right, so they correspond to the left and right downward strokes. Lastly, the stem of the question mark suggests a vertical stroke.

Although the pinyin method is found in the Simplified menu (智能拼音; "smart pinyin"), it also offers Traditional characters. I originally learned zhuyin (aka bopomofo), a more traditional pronounciation-based method for producing Traditional characters, but it is ill-suited for a US keyboard. Fortunately converting from zhuyin to pinyin is trivial.

Chinese to English

In a pinch, I’ll use Google Translate to learn Chinese phrases. However, browser plugins are much handier; see the Chrome Zhongwen extension and the Firefox Perapera-kun add-on.

Stack-smashing remains fun and profitable

2010-05-22T09:14:00.002-07:00

Buffer overflows have long been a rich source of security vulnerabilities. Unfortunately, its popularity led to a family of knee-jerk reactions: W^X; Data Execution Prevention (DEP); the NX (No eXecute) bit; executable space protection.

As the terms suggest, code is divorced from data. For example, an operating system may forbid execution of any instructions lying in the stack. A simple buffer exploit now causes the program to halt, rather than execute injected code.

My knee-jerk counter-reaction was suspicion and hostility. Shouldn’t we be focusing on the causes of buffer overflow disease, and not its symptoms? Also, some of the most beautiful and fundamental results in computer science involve feeding a Turing machine to a Turing machine. Data is code and code is data.

Self-modifying code considered awesome

Self-modifying code is fascinating by virtue of its self-referential nature, but it is not just a pretty face: it has practical applications. Just-in-time compilation is perhaps the best-known example. However, I find it most useful for nested functions in C.

Thomas Breuel describes how a C compiler can be modified to allow nested function via trampolining. Briefly, for each nested function, we generate its code as usual, but we also add a local variable to the scope where it is defined: we add an array of bytes, whose contents are opcodes that simply rig a pointer to make it look like we’re in the current stack frame before jumping to the nested function.

Standard C code expecting a function pointer still works when passed a pointer to this array. When they call the function pointer, they jump to the array, where they run the stack-frame-rigging code before continuing on with the call. By magic, the code in the nested function executes within the desired scope. One pointer does the work of two.

Observe we require the array to be local and populated at runtime, because only then do we know the address of the current stack frame. We cannot setup this tomfoolery in advance. In other words, we must execute code we just placed on the stack.

Like duct tape, treating data as code deftly solves a host of problems. W^X and friends block this avenue, or at least make it less efficient. Breuel writes:

"There are, however, some architectures and/or operating systems that forbid a program to generate and execute code at runtime. We consider this restriction arbitrary and consider it poor hardware or software design. Implementations of programming languages such as FORTH, Lisp, or Smalltalk can benefit significantly from the ability to generate or modify code quickly at runtime."

Return-oriented programming

Hovav Shacham recently filled me in on return-oriented programming. I’m a fan. I now have more than gut feelings to support my stance. I can gloat and say "I told you so".

Return-oriented programming skirts around stupid restrictions via one level of indirection. Instead of putting code in the stack, we put pointers to the code in the stack. We choose to point at code that soon runs into a return instruction. On typical architectures, a return instruction increments the stack pointer before jumping to the address to which it points. Hence the stack pointer becomes a sort of indirect instruction pointer: we run a snippet of code until it hits a return statement, which causes us to run the next snippet of code, and so on.

Thus using a compromised stack, attackers cleverly glue together snippets of code in executable parts of memory, such as the BIOS or the standard C library. On popular systems there’s enough stuff to do anything. Tools for automating the process exist; namely, you can write source and have it compile to a sequence of cherry-picked memory addresses. It’s the return-to-libc attack on steroids.

I had hoped return-oriented programming could cut both ways; does it allow self-modifying code even in the presence of an NX bit? Sadly, on further reflection, return-oriented programming appears to have no legitimate uses. Arbitrary code execution is only possbile within the stack frame of a function we control, and, for example, we still have no means of adjusting the static link pointer when qsort() invokes our nested function. Hopefully I overlooked a sneaky trick.

In short, thanks to return-oriented programming, executable space protection is a minor inconvenience for the bad guys, and a major inconvenience for the good guys.

Self-publishing with CreateSpace

2010-04-10T11:06:00.001-07:00

From time to time, somebody sends me a kind email saying that they only truly appreciated Git after encountering my Git guide. One such reader had already bought a few Git books, and he suggested I should therefore turn my website into a book.

I had idly thought about doing this, but why bother? Was: FREE, Now: $9.95!? However, the email made me realize that some seek information by buying books first, then look around online if they want more. Making a book out of my guide might be a good idea after all: I’m not trying to sell it to people who already know they can read it for free; rather, I’m aiming for those who might not otherwise find it until much later because they visit bookshops before search engines.

CreateSpace

Because the most renowned technical publishers already offered books on Git, I chose to self-publish on CreateSpace. Their tools are free, and they list your work on Amazon (who owns CreateSpace). I’d love to have bricks-and-mortar bookshops carry copies of the book too, but an Amazon listing should be enough for now.

In a brief search, I found controversy over CreateSpace ISBNs, but Richard Sutton’s post reassured me: firstly, for my book, the issues stemming from CreateSpace being the registered owner of the ISBN are irrelevant, and secondly, if you really want you can have an ISBN registered in your name (but you’ll have to buy it yourself).

The whole process is not quite free. After submitting your PDF file, you must order a proof copy. If you find errors, you submit a corrected PDF, and repeat. I made a stupid mistake the first time, so I went through this cycle twice and finished down about 16 bucks.

It’s not all bad though. I was surprisingly pleased to hold my book in my hand, as it felt like I had accomplished something. Also, in print form, the same old sentences become more authoritative and strangely convincing. Online, they look like stuff that some guy posted on some random website.

Preparing the book took much longer than expected. I had mentioned to a reader that I was considering making a book. I tried follow advice he gave me so it would look less amateurish. I cut a chapter and an appendix. I added an index. I renamed headings so they were more descriptive. I replaced all variables (e.g. "SHA1_HASH") in the command-line examples with values (e.g. "1b6d"). I selected a 6 inch by 9 inch form factor, which meant I had to shorten some lines to get them to fit. While doing all this, I found poorly spelled words, poorly worded paragraphs and poorly organized sections. I doubt I caught them all.

To avoid further delays, I used their Easy Cover Creator. Perhaps I’ll revisit this eventually, as I want a more spartan look: something like Kernighan and Ritchie’s "The C programming language". Or perhaps a sort of cheat sheet so the book would be useful even while shut.

I set the price to $9.95 USD, which means I get 2 bucks or so per sale. I considered a lower price, but I’ll be lucky to make my $16 back as it is! Still, it ought to be low enough that a buyer won’t be too annoyed when they find out the material is freely available on my homepage. (I would have linked to the free version from the book description, but this is forbidden.)

AsciiDoc, xsltproc, fop

I had some trouble with my tool chain that produces PDFs from text files. AsciiDoc produces a DocBook XML file out of the source text, which xsltproc turns into an XSL-FO file, which fop renders into a PDF. The design of the various formats probably have technical merit, but I found it difficult to figure out how to get what I wanted.

For example, I replaced variables with values because I could not italicize them easily with AsciiDoc. The only methods I discovered destroyed the natural beauty of the source text.

It seems the smaller the detail, the larger the effort required to tune it. Changing page sizes, font sizes and chapter heading styles was easy enough to figure out, but I still don’t know the right way to insert a blank page after the front matter so the first chapter starts on an odd page. I gave up editing some XSL file or other. Instead, I scripted a fragile search-and-replace on the XSL-FO output.

Nonetheless, I stand by my choices. There’s something appealing about source files which resemble old-school text files. Also, once the configuration nightmare is over, editing is simple: I can use any text editor, and the tool chain will automatically produce several HTML versions as well as a reasonable PDF for a book.

Shameless plug

I couldn’t possibly end this post without a link to my book: "Git Magic". It’s the most important book you’ll ever have, or my name is not Winston! Buy it now!

Nginx and FastCGI

2010-04-07T00:03:00.002-07:00

One perk I miss from my first days of grad school was my office computer with a permanent IP address. I could run all sorts of servers. (Later, the environment became harsher because unlike me, many of us ran Windows, but like me, they did not know how to do so securely. The IT team restricted most ports as the first line of defence, though you could ask for exceptions. Hopefully they didn’t tighten control further after I graduated.)

Wanting to be cool, I experimented with PHP when it started becoming popular. Until then, I had only dabbled with CGI programs in compiled languages. PHP was intoxicating. A Common Gateway drug, so to speak. In those Web 1.0 days, dynamic webpages were so easy and fun to make with PHP that I overdosed.

Years later I finally admitted to myself that my content was static apart from a few needless gimmicks, and this was unlikely to change. Using PHP was only increasing the CPU load. It didn’t matter because I received few hits, but it offended me as a computer scientist. I sobered up and returned to vanilla HTML.

I’ve been thinking how I might write a web application today, and I realized I’ve come full circle. I’ve lost my taste for LAMP stacks at a time when they are more widespread than ever, and once again espouse compiled languages.

Nginx

Firstly, I’ve moved on from Apache, which was once my favourite web server. I used to watch Netcraft's market share graphs so I could cheer on Apache against commercial products. But one day, I noticed a newcomer on the graphs. A strange jumble of letters: "nginx". I couldn’t resist looking it up.

Nginx shows how powerful pure unadulterated C can be in the right hands. Written by Igor Sysoev, this webserver runs on numerous platforms, hardly using any memory even as it handles thousands of requests at light speed. Nginx has somehow dodged Jeff Darcy’s Four Horsemen of Poor Performance.

Nginx cannot do CGI, but it can do FastCGI, which is a plus. Instead of spawning a new process for every request, FastCGI spawns a long-lived program once, which communicates with the webserver when necessary, possibly over a network. Of course, this program can run threads of its own if desired.

An advantage of LAMP stacks was that scripts could run without requiring a new process or thread. FastCGI puts all languages on the same footing. In fact, FastCGI is more flexible: for example, you can restart FastCGI programs independently of webservers. Perhaps this is why some run PHP via FastCGI.

Compiled languages

I prefer a compiled language to a scripting language like PHP because I crave speed and scalability. Also, one feature of PHP is useless to me: I discovered I lack the discipline to mix code with HTML. At first I found it was convenient, but eventually my webpages became hard to maintain. I now insist on strict separation between languages: my CSS, JavaScript, HTML, and whatever else ideally reside in distinct files.

Also, now that JavaScript is ubiquitous, it seems best to push as much work as possible to the client side: the FastCGI should do the minimum possible and supply its results (perhaps in JSON) to JavaScript which then plays with the data using the client’s CPU. This diminishes the need for a language designed to mingle with HTML.

Running a web application with a scripting language purportedly allows rapid prototyping, but it seems the only drawback to a compiled language is a compilation step and a FastCGI program restart. This is negligible provided your language has a fast compiler (like C and Go). Besides, I bet much of the development cycle involves presentation tweaks, that is, edits to CSS, HTML, and JavaScript: not the compiled language.

The L and M of LAMP

I’d still run my servers on Linux. I’ve had good results with it so far. As for MySQL, I cannot say, having never experimented much with databases. Its reputation seems solid enough.

How-to

On the latest Ubuntu, you’ll need to install the packages nginx, spawn-fcgi, libfcgi-dev. Then edit the nginx configuration file in /etc/nginx/sites-available/default. In the server clause, add something like:

location = /test {
  fastcgi_pass 127.0.0.1:9000;
  fastcgi_param QUERY_STRING $query_string;
}

The file /etc/nginx/fastcgi_params contains other parameters you might want to pass. Restart nginx, by running for example:

$ sudo /etc/init.d/nginx restart

Visiting http://localhost/test should result in a 502 error because no FastCGI program is running yet.

Let’s fix this. In C, I recommend using fcgiapp.h and not fcgi_stdio.h; it’s not much more trouble, and you avoid conflicts with the standard stdio library.

#include <fcgiapp.h>

int main() {
  FCGX_Stream *in, *out, *err;
  FCGX_ParamArray envp;
  while (FCGX_Accept(&in, &out, &err, &envp) >= 0) {
    char *q = FCGX_GetParam("QUERY_STRING", envp);
    FCGX_FPrintF(out, "Content-type: text/plain\r\n\r\n");
    if (!q) {
      FCGX_FPrintF(out,
          "no query string: check web server configuration\n");
    }
    FCGX_FPrintF(out, "Query: '%s'\n", q);
  }
  return 0;
}

Compile your code:

$ gcc a.c -lfcgi

Then spawn the binary on your machine on port 9000:

$ spawn-fcgi -a 127.0.0.1 -p 9000 -n -- a.out

Test it by visiting http://localhost/test?example.

In a real application, you might want to run the binary as a daemon, and place the process ID in a temporary file for easy access:

$ spawn-fcgi -a 127.0.0.1 -p 9000 -P /tmp/pid -- a.out

I had planned to continue this post by writing about embedding HTML files in C, and fetching data with JavaScript but it’s too long as it is. Some other time maybe.

At last

2010-04-05T18:48:00.002-07:00

I don't play much DDR anymore. Making it through Max 300 on Heavy mode was an old goal I thought I had no hope of achieving. But several days ago I had energy to burn and played a few rounds on a whim. Oddly, my game has improved despite lack of practice. The arrows felt slower than I remember. I tried Max 300 almost as a joke, and was amazed that I finally passed it.

Now I have to work my way up to an A!

It's Go time

2009-11-12T01:54:00.002-08:00

At last, the Go programming language has been publicly released so I can write about it without getting into big trouble.

Go was designed by programmers I hold in high regard. Although it is a new language, the same people already experimented with some of its ideas at least ten years ago.

Back then, I saw a demonstration of the Inferno operating system, the successor to Plan 9, which in turn was the sequel to UNIX. I remain awed that just a handful of programmers could implement a complex system so well. The venerable UNIX crew seem to make the right decision often, and make it ten years ahead of everyone else.

For example, the dis byte code ran on a register-based virtual machine and hence ran fast. In contrast, its chief competitor, Java, has a stack-based virtual machine, and it seemed to take years to realize that this was a poor solution. The problem is so severe that JIT compilation was introduced, weakening the "Write Once, Run Anywhere" mantra: the statement becomes almost meaningless if one requires some sort of compiler for every platform, as opposed to a simple byte code interpreter. Another workaround is to design a register-based virtual machine for Java from scratch.

Another case in point is Limbo, a novel programming language that accompanied Inferno. Sadly Limbo has far fewer adherents than Java, for non-engineering reasons. Like Plan 9 (which remained closed-source until 2000), Inferno was hard to obtain, whereas Java was being given away: indeed, users were once practically forced by their browsers to install Java virtual machines. The relative obscurity of Limbo is therefore expected, as with any human language possessing few speakers and few opportunities for growth.

A second chance

It’s much more exciting this time around. The powers that be have wisely made Go open source. Now that Go is playing on a level field, ideas that Limbo should have popularized finally have a chance to spread far and wide.

My favourite feature is something they left out. As with Limbo, there is no inheritance. There is no stifling type system. At least one generation of programmers has been trained to use a rigid type system, and I believe history will one day prove the inheritance mindset to be a passing fad. I have strong feelings about this topic because I was once a firm believer in inheritance, and it took years to realize my mistake.

Go instead emphasizes interfaces, and provides a simple concise syntax for them. A few neat lines perform the equivalent of several messy lines in C that deal with structs of function pointers.

Go also has strong concurrent programming features, which it shares with Limbo. Different threads (actually, "goroutines") communicate via channels (folowing the CSP model), eliminating race conditions. Channels are essentially type-safe UNIX pipes: they capture the power and delight of writing shell scripts to string together several tools.

Among lesser niceties: nested functions, anonymous functions, multiple return values, the package and import keywords, untyped numerical constants, reflection. Most of my wishes for C have been granted.

I’ll probably mostly stick with C. I’ve grown accustomed to its flaws, and I like squeezing every drop of performance out of code without dropping down to assembly. But for those tasks that require more than a shell script but less than a C project, Go might just fit the bill.

Project Euler

2009-11-08T23:57:00.002-08:00

Lately my spare time has been eaten by an MMORPG: Project Euler. Even though I have played few RPGs, I’m sure Project Euler is one of the most difficult and challenging.

Actually, it’s really not an RPG. Rather than reward the clicking of buttons, the only way to gain levels in Project Euler is to submit answers to puzzles. Each involves a little bit of computer science and a little bit of mathematics.

Along the way, I wrote a library to make it easier to do arbitrary precision arithmetic in C. For example, to solve problem 97, I could write:

  mpz_t z;
  mpz_init(z);
  mpx_eval("mpz a; a = (28433 * 2^7830457 + 1) % 10^10;", z);
  gmp_printf("%Zd\n", z);

Strangely, Project Euler only lets you try at most 25 problems over n days, where n is your current level (except at level 0, when it is 1). Perhaps I should be grateful, as bumping into this limit gives me time to post code!

mpx git repository: http://cs.stanford.edu/~blynn/scrap/mpx.git

I'm right, you're wrong

2009-11-02T00:40:00.002-08:00

I enjoy ranting about programming languages, whatever the medium: blog posts, emails to friends, colleagues and strangers, verbally to anyone within earshot. Mostly I rail against the evils of object-oriented languages, and why C is still the one true language.

Over the years, I’ve amassed enough material to fill several pages, which I’m now launching. Hopefully if I concentrate all these tirades in one place I’ll expend less energy overall on arguing!

Napkin Cryptography

2009-08-24T15:14:00.002-07:00

I was a cryptography researcher in a past life. Occasionally I experience echoes from my previous incarnation: a paper review here, a technical question there, so I still feel somewhat connected.

A couple of weeks ago I bumped into Daniel J. Bernstein and Tanja Lange, whom I had last seen in 2003 at a conference in Chicago. [Thanks to Dan for inviting me, and also for taking everyone out to the downtown bars and restaurants. I had a blast!] Only then did I realize how far I had fallen from the light. In a hurried notes-on-a-napkin conversation I tried to catch up on what was once my field:

2048 is the new 1024

Firstly, I was mildly surprised when I learned governments and standards bodies are actually heeding warnings that 1024-bit RSA keys are crackable by large corporations and botnets, thus now mandate 2048-bit keys.

Ah, the memories. Just how vulnerable are 1024-bit keys? Back in the ivory tower, this was the subject of an intense high-profile debate, with Bernstein on one side, and Lenstra, Shamir, Tomlinson and Tromer on the other. The heated arguments seemed to get personal at times, providing excellent fodder for gossip amongst us grad students.

I have no idea if the parties ever reconciled, nor if the fireworks have even subsided, but I’m relieved that everybody agrees 1024 bits is insufficient nowadays.

Fast ECC

More interesting to me are the new breed of elliptic curve cryptography (ECC) implementations. Dan instructed me to "forget everything you know about elliptic curves" before launching into the world’s fastest course on the world’s fastest algorithms for elliptic curves.

Consider a unit circle, x² + y² = 1. We can define a group operation on the points of the unit circle via angle addition. It’s easiest to describe with polar coordinates I suppose: cis(α) composed with cis(β) gives cis(α+β). Except for some reason we want (0,1) to be the identity so make that cis(α+β-π).

In Cartesian coordinates, if the two input points are (x₁, y₁) and (x₂, y₂) then we get (x₁ y₂ + x₂ y₁, y₁ y₂ - x₁ x₂). Let us denote this point by (a, b).

An Edwards curve is a deformed circle that is equivalent to an elliptic curve in some sense. There is some deal about requiring a point of order 4, which is probably related to the quadrilateral symmetry of the Edwards curve. It is parameterized by d which I’m guessing is akin to the j-invariant, and has the equation x² + y² = 1 + d x² y².

Using the above notation, group addition produces the point (a / (1 + D), b / (1 - D)) where D = d x₁ x₂ y₁ y₂. Unlike elliptic curves, the same formula applies for identical inputs, and the also for the identity element: in paricular, there is no special formula for point doubling. From this equation one can write code to multiply points at breakneck speed.

Montgomery curves are given by B y² = x³ + A x² + x, and possess fast point addition with one big string attached: you can only add P and Q if you know P - Q; this point forms the base of an addition "ladder". This is fine for exponentiations and hence ECDSA, but may be unsuitable for other cryptosystems.

The details, and more, can be found at the Explicit-Formulas Database. Also, see this highly optimized implementation of the curve 25519.

DNSCurve

To Dan, speedy ECC is merely a means to an end: a brilliant and diabolical scheme to usurp DNSSEC with DNSCurve. If DNSSEC does indeed have the drawbacks he described, then I wish him well. Kill it before it spreads! The Denial-of-Service attack amplification issue is enough to justify revoking its netizenship.

Pairings

For the PBC library, the good news is that Weierstrass curves are still the best known way to get at pairings (because of the order 4 point brouhaha), though research on alternate curves for pairing computation continues at a furious pace.

The bad news is that the sample pairing parameters I’ve been distributing are mostly too weak. Additionally, Barreto-Naehrig curves, the least-optimized case in the library, are arguably now the most important pairing type.

By the way, our discussion literally involved scribbling on a serviette:

Alas, I am not a coauthor of this paper: the handwriting belongs exclusively to Bernstein and Lange.

Tune out

2009-08-13T01:12:00.002-07:00

I had grand plans for my Android game. Apart from actually completing it, I was going to fix bugs, and add sound and music.

But my enthusiasm evaporated as fast as it had arrived, and now that I have forgotten the password to my key, it looks even less likely I’ll release new versions.

I did get around to composing a tune for use somewhere in the game. Seeing as it almost certainly never find its way to the game, I may as well dump it here:

I lacked the patience to learn how LilyPond deals with "da capo al fine". Luckily it’s clear where it belongs; this is one of those A-A-B-A melodies.

Another problem was excessive whitespace in the generated PNG image. My older post must have used lilypond-book in its original incarnation, but that was back when I wrote raw icky HTML.

There must be some lilypond option to automatically crop the output, but I found manual labyrinthine. So instead, to produce the above image I ran something like:

$ lilypond --png foo.ly
$ convert -trim -border 8x8 -bordercolor white foo.png foo.png

Other formats: benlynn.ly benlynn.ps benlynn.pdf

ZDD fun

2009-07-30T01:23:00.002-07:00

I finally released the source for my logic puzzle solvers using ZDDs. I was hoping to finish at least the Nurikabe solver first, but I lost interest.

Mirrors:

I used the code to help construct the following Slither Link puzzle:

2...23
..3...
..3..2
.2.22.
....22
1..1.1

ZDDs are fascinating data structures, and using them to solve a logic puzzle is more fun that the puzzle itself. I hope to revisit them some day.

Much Ado About Nothing

2009-06-08T01:00:00.002-07:00

Whitespace in XML files can behave unintuitively, especially when it comes to newlines. My script that converts AsciiDoc to Blogger posts entry is peppered with awful kludges meant to bring them in line, but still fails to indent source code.

After much experimentation, and as little reading of the official XML specifications as possible, I have determined the best practices for my situation:

Adding xml:space="preserve" to the opening content tag preserves the source code indentation.
It appears impossible to preserve newlines anywhere. They vanish mysteriously, not even leaving a space behind. By default XML leaves a space, so I don’t understand why; perhaps it’s an Atom thing. Thus I add "<br />" at end of each line where formatting matters, and prefix each newline with a space.

My updated script appears below, this time with indentation.

#!/bin/bash

if [[ -z "$1" ]] ; then
  echo Usage: $0 ASCIIDOC_SOURCE [LABELS...]
  exit 1
fi

if [[ ! -f "$1" ]] ; then
  echo $1 not found.
  exit 1
fi

outfile=$1.xml
# Extract = Title =, which must be on a line by itself.
title=$(grep '^ *=' -m 1 $1 | sed 's/^ *=* *//' | sed 's/ *=* *$//')

# Hmm, this draft thing used to work, but not anymore.
echo '<entry xmlns="http://www.w3.org/2005/Atom">
  <app:control xmlns:app="http://www.w3.org/2007/app">
    <app:draft>yes</app:draft>
  </app:control>
  <title type="text">'$title'</title>
  <content type="xhtml" xml:space="preserve">
    <div xmlns="http://www.w3.org/1999/xhtml">' > $outfile
# We need \n newlines for sed.
asciidoc -a newline=\\n -s -o - $1 >> $outfile
echo '
    </div>
  </content>' >> $outfile
while [[ -n $2 ]]; do
  echo '  <category scheme="http://www.blogger.com/atom/ns#" term="'"$2"'" />' >> $outfile
  shift
done
echo '</entry>' >> $outfile

# I can't figure out how to preserve line breaks in Atom XML,
# hence the following.
# Prefix each newline with a space.
sed -i 's/$/ /' $outfile
# Add <br /> to the end of all lines between <pre> and </pre>.
sed -i '/<pre>/,/<\/pre>/s/ *$/<br \/>/' $outfile
# Undo what we just did for the </pre> line.
sed -i 's/\(<\/pre>.*\)<br \/>/\1/' $outfile

if [[ -z $AUTH_TOKEN ]]; then
  stty -echo
  read -p "Blogger password: " pw
  stty echo

  token=$(curl --silent https://www.google.com/accounts/ClientLogin \
-d Email=benlynn@gmail.com -d Passwd="$pw" \
-d accountType=GOOGLE \
-d source=asciidoc2blogger \
-d service=blogger | grep Auth | cut -d = -f 2)
  AUTH_TOKEN=$token
  echo AUTH_TOKEN=$token
fi

# The URL was cut and pasted from <link rel="service.post"> from
# my blog's HTML source.
curl --silent --request POST --data "@$outfile" \
--header "Content-Type: application/atom+xml" \
--header "Authorization: GoogleLogin auth=$AUTH_TOKEN" \
"http://www.blogger.com/feeds/4222267598459829544/posts/default" \
| tidy -xml -indent -quiet

AsciiDoc To Blogger

2009-06-07T11:58:00.002-07:00

Once I grew accustomed to writing AsciiDoc, editing even tiny amounts of HTML became bothersome. The sites I maintain use custom scripts to build HTML files from AsciiDoc source, but I have less control over this blog. Up until now I’ve been using the Blogger in-browser editor to fine-tune the markup in these posts.

AsciiDoc’s author, Stuart Rackham, also wrote a tool to go from AsciiDoc to a WordPress blog. Blogger should be similar, and perhaps even easier to work with, since WordPress appears to have a few quirks.

My first thought was to use the Mail-to-Blogger feature: I could run AsciiDoc on on the source, then send it to a particular email address to publish it. This attempt floundered becaues GMail has no raw HTML mode. Of course, I could script an SMTP server instead, but this seems excessive.

Next I considered the import and export feature. But even if I could figure out how to generate suitable XMLs, I’d have to click around and solve a CAPTCHA each time I imported a post.

Finally the simplest solution hit me: use the Blogger Data API. With an HTTPS request or two, I can post raw HTML, set labels, and even choose whether to publish immediately or save as a draft. All it takes is a shell script using curl with Google data services:

#!/bin/bash

if [[ -z "$1" ]] ; then
echo Usage: $0 ASCIIDOC_SOURCE [LABELS...]
exit 1
fi

if [[ ! -f "$1" ]] ; then
echo $1 not found.
exit 1
fi

outfile=$1.xml
# Extract = Title =, which must be on a line by itself.
title=$(grep '^ *=' -m 1 $1 | sed 's/^ *=* *//' | sed 's/ *=* *$//')

# Hmm, this draft thing used to work, but not anymore.
echo '<entry xmlns="http://www.w3.org/2005/Atom">
  <app:control xmlns:app="http://www.w3.org/2007/app">
    <app:draft>yes</app:draft>
  </app:control>
  <title type="text">'$title'</title>
  <content type="xhtml">
    <div xmlns="http://www.w3.org/1999/xhtml">' > $outfile
asciidoc -f macros -s -o - $1 >> $outfile
echo '
    </div>
  </content>' >> $outfile
while [[ -n $2 ]]; do
echo '  <category scheme="http://www.blogger.com/atom/ns#" term="'"$2"'" />' >> $outfile
shift
done
echo '</entry>' >> $outfile

# I can't figure out how to preserve line breaks in Atom XML, hence the
# following workaround.
sed -i '/<pre>/,/<\/pre>/a<br \/>' $outfile

if [[ -z $AUTH_TOKEN ]]; then
stty -echo
read -p "Blogger password: " pw
stty echo

token=$(curl --silent https://www.google.com/accounts/ClientLogin \
-d Email=benlynn@gmail.com -d Passwd="$pw" \
-d accountType=GOOGLE \
-d source=asciidoc2blogger \
-d service=blogger | grep Auth | cut -d = -f 2)
AUTH_TOKEN=$token
echo AUTH_TOKEN=$token
fi

# The URL was cut and pasted from <link rel="service.post"> from my
# blog's HTML source.
curl --silent --request POST --data "@$outfile" \
--header "Content-Type: application/atom+xml" \
--header "Authorization: GoogleLogin auth=$AUTH_TOKEN" \
"http://www.blogger.com/feeds/4222267598459829544/posts/default" \
| tidy -xml -indent -quiet

Actually, that’s not quite all: to work around another weird XML whitespace issue I use the following AsciiDoc macros file.

[miscellaneous]
newline=" \n"

We insert a space before each newline to prevent words separated by a line break from being joined together.

Logic puzzles vs ZDDs

2009-05-31T14:34:00.001-07:00

I've been addicted to logical puzzles for a long time. Recently, I've become addicted to writing programs to solve addicting logic puzzles.

Years ago I whipped up a dancing links sudoku solver as popularized by Knuth, which converts sudoku instances into exact cover problems. So of course when I learned ZDDs were good at exact cover problems, again from Knuth, I immediately thought of sudokus.

I dreamt of building a ZDD representing all possible (standard) sudokus. I could then fill in some boxes, and from here, I could count the number of solutions, pick one at random uniformly, or weight the solutions with any given scheme and find the maximum or minimum solution, as well as the mean and standard deviation.

I eagerly wrote enough ZDD routines to encode the sudoku constraints. The preliminary results were encouraging: my ZDD enforcing exactly one per box and exactly one per row for each digit required only 20738 nodes. But the column constraints crushed my aspirations. No matter how I sliced it, the ZDD grew too rapidly as more constraints were added.

As a consolation prize, I hoped to at least convert my program into a solver that would rival my earlier program. Unfortunately, although the end result could solve a sudoku, it did so slowly.

Deflated, I sought reassurance by verifying Knuth's results on chessboard tilings. Thankfully my numbers agreed exactly, so I knew my implementation was sufficiently correct and efficient for basic experiments. On the other hand, it also probably means that sudokus are indeed beyond the reach of ZDDs.

I flailed around looking for another excuse to use ZDDs. It didn't take long: nonogram puzzles turn out to be no match for their power.

By the way, I obviously mean human-friendly nonograms, as the general problem is NP-complete; ZDDs aren't that revolutionary! The same applies to other NP-complete puzzles: rather than prove P = NP, my goal is to write an efficient solver for instances meant for humans, and maybe also instances that are just a bit tougher.

I didn't have much time to stress test the nonogram solver, as I rapidly moved on to a Light Up solver. Shortly after I threw together a dominosa solver, and yet more ZDD solvers for other logic puzzles are in the pipeline. I'll release the code soon.

As dominosa puzzles are easily disguised as exact cover problems, I also wrote a dancing links solver. Unsurprisingly, it is much faster; I'm sure specialized recursive search programs outperform ZDDs for the other puzzles too, but ZDDs have some advantages. Firstly, they are easy to write once the infrastructure is in place. Constraints for many logic puzzles are easily expressed in terms of ZDDs. Secondly, even if ZDDs are only practical for smaller instances, they can often answer more questions.

For example, how many dominosa problems are there if we go up to double-nine? How many are there if we then place a few particular dominoes in certain places? What does puzzle number 12345 look like? And so on.

A really fundamental data structure

2009-05-24T19:09:00.001-07:00

There are many things I wish my textbooks had taught me. It's often not the fault of the authors: in any field, even the best ideas suffer a lag between discovery and dissemination. However, even accounting for this, it seems I'm always behind the times. Some glaring omissions I belatedly redressed:

Calculus can be taught rigorously with infinitesimals, following the path traveled by its original developers, unlike the approach using limits and deltas and epsilons.
Cuckoo hashing gives hash tables with O(1) worst-case lookups and are also space-efficient.
Bob Jenkin's hash functions for hash tables are better than those many commonly encountered in textbooks.
Perfect hashes give optimal performance when the keys come from a small set that can be preprocessed beforehand.
Crit-bit trees perform similarly to hash tables but have some advantages. My favourites: good worst-case running time and lexicographical operations. Apparently they can be used to sort strings faster than quicksort or radix sort.
AA trees remove the pain from implementing balanced binary trees.

But most of all, I bemoan my ignorance of binary decision diagrams (BDDs). In his Computer Musings lecture, Don Knuth states "it's one of the only really fundamental data structures that came out in the last 25 years". He felt it was so important that he devoted the following lecture to ZDDs, a close relative of BDDs.

Take a map of the USA, and consider the following problems:

Suppose you want to visit every state capitol exactly once, traveling on highways. Which route is shortest? Which route is longest? What is the mean and standard deviation of all the routes?
Weight the states by any means, for example, by reading their two-letter code as a number in base 36. Then find a set of states such that no two members of the set are adjacent, and the total weight is maximized.
There are several ways to colour the map with four colours such that no two adjacent states have the same colour. How do we pick one of these colourings at random (uniformly)?

Or consider these:

How many ways can you tile a chessboard using 1x1, 2x1 and 3x1 rectangles? What if we also have pieces that look like 2x2 boxes with one tile missing?
List all 5-letter words that remain words after replacing a 'b' with 'o'.

Do you know how to solve these efficiently? If not, you might want to read up on BDDs, particularly Knuth's treatment, which has just hit the presses, and watch his lectures. Using these sources, I took some notes on ZDDs.

Learning about BDDs reminded me of learning about Pólya theory, another simple yet powerful technique which transforms the seemingly impossible into child's play.

Assorted sorts

2009-05-17T11:05:00.001-07:00

Let void x(int *p, int *q) be function that swaps its arguments, namely, after execution, *p is equal to the original value of *q and vice versa.

What do the following functions do?

void f(int *m, int *n) {
int *p;
for(p = m; p < n; p -= *p > p[1] ? x(p, p + 1), p != m : -1);
}

void f(int *m, int *n) {
int *p, *q;
for(p = m; p <= n; p++) for(q = p; q <= n; *p > *q ? x(p, q) : 0, q++);
}

void f(int *m, int *n) {
  int i, j, k;
  for(i = 1; (k = i) <= n - m; i++)
    while(k && m[j = k - 1 >> 1] < m[k]) x(m + j, m + k), k = j;
  for(k--; x(m, m + k--), k;) for(i = 0;
      j = 2 * i + 1, k >= (j += k > j && m[j] <= m[j + 1]) && m[j] > m[i];
      x(m + j, m + i), i = j);
}

void f(int *m, int *n) {
int *p, *q, i;
do
for (i = 0, p = q = m, ++q; q <= n; p = q++) *p > *q ? x(p, q), i = 1 : 0;
while(i);
}

void f(int *m, int *n) {
int *p, *q;
for(p = m + 1, q = n; p < q; *p > *m ? x(p, q--) : *p++);
m != n ? *m > *p ? x(m, p) : 0, f(m, --p), f(q, n) : 0;
}

void f(int *m, int *n) {
int *p, *q, i, j;
for(p = m + 1; p <= n; p++, *q = i)
for(i = *p, q = p; q > m && i < (j = *(q - 1)); *q-- = j);
}

void f(int *m, int *n) {
static short s[] = { 1, 4, 10, 23, 57, 132, 301, 701, 1750 };
int *p, *q, i, j, a, b;
for(a = sizeof(s)/sizeof(short) - 1; a && s[a] > n - m; a--);
while(a >= 0) for(p = m + (b = s[a--]); p <= n; p++, *q = i)
for(i = *p, q = p; q > m && i < (j = *(q - b)); *q = j, q -= b);
}

The title is a big hint, but if you're still not sure, experiment with a function by compiling it with the following code, and supply some integers on standard input.

#include <stdio.h>

void f(int *m, int *n);

void x(int *p, int *q) {
  int i = *p;
  *p = *q, *q = i;
}

int main() {
  enum { limit = 8192 };
  int a[limit], *n, *k;
  for(n = a; 1 == scanf("%d", n) && n - a < limit; n++);
  puts("in:");
  for (k = a; k < n; k++) printf(" %d", *k);
  puts("");
  f(a, n - 1);
  puts("out:");
  for (k = a; k < n; k++) printf(" %d", *k);
  puts("");
  return 0;
}

Can you identify each algorithm? The answers are, in some order, bubble sort, gnome sort, insertion sort, selection sort, shell sort, heapsort and quicksort.

The real puzzle is why I bothered. All I can say is you don't have to be a chef to enjoy making spaghetti: see the International Obfuscated C Code Contest.

Notable Notation

2009-05-14T19:08:00.001-07:00

Pursuing a graduate degree in computer science at Stanford offered many perks. I benefited from at least one more than some of my colleagues, as I was assigned an office only a few doors away from Don Knuth's.

I'd occasionally catch a glimpse of the legendary computer scientist, for some reason usually donning a bicycle helmet. However, the proximity of his office alone seems to have had an effect: I switched to LaTeX for typesetting. As an undergraduate I loyally used Lout, whose author, Jeff Kingston, had an office near where I worked. In seriousness, it was probably more for practical reasons than out of respect: all my co-authors used LaTeX.

I still have a soft spot for Lout with its clean and comprehensible internals. Compare with the inscrutable black-magic LaTeX style sheets built on top of TeX, which itself is tricky to grasp. However, the TeX equation syntax certainly deserves its status as the lingua franca of mathematicians communicating via email and other plain text mediums.

My workplace is no longer near Knuth or Kingston. Perhaps not entirely coincidentally, I no longer use TeX or Lout. Wanting documentation sources to be as readable as much as possible, I devised a markup language inspired by venerable ASCII typesetting tricks of heavy email users and README authors, such as *asterisks*, _underscores_, and ==Headings==, and wrote a script to translate it to HTML. Luckily I didn't get far before discovering AsciiDoc.

Equation-heavy notes, books, HTML, PDF: AsciiDoc handles them all despite using source files that look like ordinary text documents. Easy to learn, easy to type, and easy on the eyes. Fine-tuning the final layout is difficult, a blessing in disguise as users have solid excuses for ignoring those typesetting nitpicks TeXperts are expected to correct.

But I digress: back to name-dropping Donald E. Knuth. Although he was warm and friendly, I only spoke to him a few times as he was also busy. However, I had many chances to listen to him. Sometimes he'd give a talk in the meeting area outside my door, where I always had a guaranteed seat: I could simply wheel my office chair a few meters.

Regrettably I recall almost nothing. There was a story about how noticing a pattern in table of numbers yielded a PhD thesis; he made it sound so easy. I also vaguely remember a fascinating introduction to coroutines along with an obscure but accessible application: generating certain Gray code sequences. This would describe all I have left from Knuth's talks, but happily, some of his Computer Musings were recorded and are freely available online.

The Notation episode is surprisingly interesting, especially the historical tidbits. The notation for floor and ceiling functions only became standard relatively recently, a brilliant idea that usurped many inferior schemes and rapidly took over the world. Another young fad is to use "lg" for the base 2 logarithm, though now it seems we should use "lb" instead.

The highlight was Iverson's bracket convention: one places an expression within square brackets, and the whole thing evaluates to 1 if the expression is true, and 0 otherwise. For example, [k is even] means 1 when k is even, and 0 otherwise. Other examples:

sign(x) = [x > 0] - [x < 0]
[A and B] + [A or B] = [A] + [B]

"Two notes on notation" describes how to harness the power of the square bracket.

This should all sound familiar to C programmers, because many C operators evaluate to 1 when the result is true and 0 otherwise. It's simultaneously disheartening and amusing that while mathematicians and computer scientists are discovering the utility of this convention, some programming language designers actively oppose it by introducing a boolean data type that cannot be interchanged with integers.

The lecture was crammed with other ideas that deserve to be widespread. I discuss them somewhere I can use AsciiDoc and LaTeX equation notation.

Compiler Compilers

2009-02-11T04:46:00.001-08:00

Long ago I sat a set of exams designed to test the breadth of our computer science knowledge. I failed Compilers. Luckily, they had just changed the rules, and it was acceptable to fail Compilers provided you passed the Databases exam. Fortune smiled upon me, and I passed the Databases exam despite possessing even less knowledge in that field. Or perhaps fortune was actually laughing at me: I stayed away from compiler theory for the rest of my degree to my detriment. It's scandalous I still know so little.

I was especially dispirited by my failure since I had thought I knew compilers well. When I was a child, I felt moved after learning about recursive descent parsers. I had been mystified: how could a program could possibly read an expression like (1+2)*((3+4)/5)? All I could think of was to use a simple loop to iterate over the tokens in the expression and assigning them to local variables before processing them. This led nowhere, because the nesting of parentheses can be arbitrarily deep. Thus I was awestruck by the elegance of recursive descent; after the first reading the technique was indelibly etched in my mind.

Much later, in university, basic compiler theory (grammar, languages, automata, and so on) came easily to me. I implemented a compiler for a toy language which produced the smallest and fastest code in my class. I'd also written the odd recursive descent parser for pet projects.

So I thought I was a compiler expert. But I should have paid attention to my weaknesses. I found LR(1) parsers unintuitive. I leafed through their proofs of correctness and promptly forgot their details, especially since the textbook stated these parsers are rarely coded by hand and instead generated by programs such as yacc or bison. Instead of embracing these powerful tools, I stuck with trusty hand-coded parsers because I understood them completely.

Ultimately this caused me to fail my Compilers exam, which was peppered with yacc questions, and more seriously, to waste copious amounts of time coding and debugging parsers and lexical analyzers. I have at last invested energy in seriously learning flex and bison, and I urge anyone in a similar situation to do the same. All these years, instead of writing recursive descent parsers unless there was a compelling reason not to, my default attitude should have been to use flex and bison unless there was a compelling reason not to.

I wrote a compiler that converts a toy language (essentially a tiny subset of Limbo) to Dalvik bytecode. I also wrote a Dalvik assembler along the way. In both cases, flex and bison were invaluable: gone are the finicky routines I've written and rewritten a million times, like handling an unexpected end of input, and fine-tuning mutually recursive functions and logic to get the desired operator precedence and associativity.

I've put my efforts on hold. I was hoping for a relatively functional and less object-oriented input language, but it seems such a language would be tricky to shoehorn into Dalvik bytecode: function calls are abstracted, and with no control over stack frames I doubt I can implement trampolining.

Also, I greatly underestimated my ignorance of compiler theory. I know nothing about the static single assignment (SSA) form, which appears too new for the textbooks I had. Moreover, I need to refresh my memory on older optimization techniques.

On the other hand, I don't want to discard my code, particularly as it will forever remind me to consider flex/bison before coding yet another parser by hand. Below is the git repository containing my primitive compiler and assembler that turns this:

init() {
  print("Hello, World");
}

on_input(arg : string) {
  a: int;
  a:= parse_int(arg);
  print("\n");
  print(int_to_string(a * (a + 1) / 2));
}

into an Android app.

http://cs.stanford.edu/~blynn/bender.git

Minimal Dalvik Executables

2009-02-06T04:46:00.001-08:00

When I was a kid, the Windows era had yet to arrive. Floor-model PCs in shops ran MS-DOS. They'd often take steps to stop little imps like me messing around with their systems. I recall one where they even deleted the standard DOS utilities. But they had left COMMAND.COM unmodified which is enough for plenty of mischief. One can create executables via:

 $ copy con: hello.com

and then enter machine code by holding Alt while typing a number on the keypad. (It doesn't work on DOSBox by the way.) Some numbers, such as 0, must be avoided, but there are workarounds; the book from which I learned the trick, Ralph Burger's "Computer Viruses: a High-tech Disease", recommended first creating a program that read numbers in ASCII and output the corresponding binary, a sort of proto-assembler, which in turn could be used to create more complex executables.

I created a HELLO.COM program by typing the following, where the numbers are typed on the numberpad with the Alt key held:

 180 9 190 9 1 205 33 205 32 hello$

which is perhaps more recognizable to DOS programmers when converted to hex:

 B409 BA0901 CD21 CD20 hello$

It is the machine code for:

MOV AH, 09
MOV DX, 109h
INT 21h
INT 20h

This instructs DOS to print the '$'-terminated string at address 0x109 and then exit. When .COM files are loaded, DOS places their contents at address 0x100 (locations 0 to 0x100 are populated with miscellaneous information such as the command-line), hence the 0x109.

Thus with 9 bytes plus the size of the message, plus a byte for the terminator, we get a valid DOS program. We can type raw machine code from the keyboard to produce a full program.

Linux on x86 systems is less straightforward. The machine code is similar, but there must also be an ELF header (not strictly true: in some circumstances, the entire machine code can be placed within a truncated ELF header!), making binaries more tedious to construct by hand. However, certain kernel configurations allow different header types, some of them brief enough to be easily memorized and hand-rolled.

Minimalist Android

How about Android? An APK file is a ZIP file containing, among other files, the Dalvik executable in a DEX file. We're interested in minimizing this DEX file, whose full specification is well-documented.

All Android code must lie in some class, and Android applications typically inherit from a library class such as Activity, so we must also record information such as the class name, access rights, and inheritance. This, in turn, requires a strings section so we can store the class names, as well as invoked library functions and function signatures. Other overheads include the header and the map section. We can cheat a little by defining the UI with XML, so it won't contribute to the size of the DEX file.

After compiling to Java class files, most or all the R*.class files can be removed before making a DEX file,since the constants they contain are hardcoded in other class files by javac. For some projects, R$styleable must be retained, though this class appears to have since been removed from the public API.

I chose to write a program that parsed the DEX file from the HelloAndroid example and output only the necessary sections rather than attempt to create a DEX file from scratch. I found I could safely elide the source filenames, debug information and annotations. The result consists of 632 bytes, though we could trivially shrink this further by using a shorter name for the class.

0000000: 6465 780a 3033 3500 2f4f 153b 3623 8747  dex.035./O.;6#.G
0000010: 6d02 4697 5b1e 959d a8b1 2f0f 9c3a a14f  m.F.[...../..:.O
0000020: 7802 0000 7000 0000 7856 3412 0000 0000  x...p...xV4.....
0000030: 0000 0000 f001 0000 0a00 0000 7000 0000  ............p...
0000040: 0500 0000 9800 0000 0300 0000 ac00 0000  ................
0000050: 0000 0000 0000 0000 0500 0000 d000 0000  ................
0000060: 0100 0000 f800 0000 6001 0000 1801 0000  ........`.......
0000070: 6201 0000 6a01 0000 6d01 0000 8501 0000  b...j...m.......
0000080: 9a01 0000 bc01 0000 bf01 0000 c301 0000  ................
0000090: c701 0000 d101 0000 0100 0000 0200 0000  ................
00000a0: 0300 0000 0400 0000 0500 0000 0500 0000  ................
00000b0: 0400 0000 0000 0000 0600 0000 0400 0000  ................
00000c0: 5401 0000 0700 0000 0400 0000 5c01 0000  T...........\...
00000d0: 0100 0000 0000 0000 0100 0200 0800 0000  ................
00000e0: 0300 0000 0000 0000 0300 0200 0800 0000  ................
00000f0: 0300 0100 0900 0000 0300 0000 0100 0000  ................
0000100: 0100 0000 0000 0000 ffff ffff 0000 0000  ................
0000110: e101 0000 0000 0000 0100 0100 0100 0000  ................
0000120: 0000 0000 0400 0000 7010 0000 0000 0e00  ........p.......
0000130: 0300 0200 0200 0000 0000 0000 0900 0000  ................
0000140: 6f20 0100 2100 1500 037f 6e20 0400 0100  o ..!.....n ....
0000150: 0e00 0000 0100 0000 0000 0000 0100 0000  ................
0000160: 0200 063c 696e 6974 3e00 0149 0016 4c61  .....I..La
0000170: 6e64 726f 6964 2f61 7070 2f41 6374 6976  ndroid/app/Activ
0000180: 6974 793b 0013 4c61 6e64 726f 6964 2f6f  ity;..Landroid/o
0000190: 732f 4275 6e64 6c65 3b00 204c 636f 6d2f  s/Bundle;. Lcom/
00001a0: 616e 6472 6f69 642f 6865 6c6c 6f2f 4865  android/hello/He
00001b0: 6c6c 6f41 6e64 726f 6964 3b00 0156 0002  lloAndroid;..V..
00001c0: 5649 0002 564c 0008 6f6e 4372 6561 7465  VI..VL..onCreate
00001d0: 000e 7365 7443 6f6e 7465 6e74 5669 6577  ..setContentView
00001e0: 0000 0001 0102 8180 0498 0203 01b0 0200  ................
00001f0: 0b00 0000 0000 0000 0100 0000 0000 0000  ................
0000200: 0100 0000 0a00 0000 7000 0000 0200 0000  ........p.......
0000210: 0500 0000 9800 0000 0300 0000 0300 0000  ................
0000220: ac00 0000 0500 0000 0500 0000 d000 0000  ................
0000230: 0600 0000 0100 0000 f800 0000 0120 0000  ............. ..
0000240: 0200 0000 1801 0000 0110 0000 0200 0000  ................
0000250: 5401 0000 0220 0000 0a00 0000 6201 0000  T.... ......b...
0000260: 0020 0000 0100 0000 e101 0000 0010 0000  . ..............
0000270: 0100 0000 f001 0000                      ........

Only the 4 16-bit words at 0x128 and the 9 16-bit words at 0x140 are actual Dalvik bytecode. They belong to the constructor and the onCreate method respectively.

Developing Android without Eclipse or Ant

2009-01-22T20:10:00.001-08:00

The Android documentation recommends using Eclipse for development, but this is sluggish on my laptop, and feels cluttered on compact screens. A stated alternative is to use Ant, but this is also unnecessary as the build commands it invokes can be easily extracted and executed manually. This suits my preference for a minimalistic or practically non-existent IDE, especially on laptops, as well as my distaste for editing XML. As a bonus, on Ubuntu, I install one package:

$ sudo apt-get install sun-java6-jdk

along with the Android SDK and I'm ready to develop for Android. In contrast, the Ant package has several dependencies, and the required version of Eclipse is newer than the currently available Ubuntu package.

Here are the details:
$ SDKDIR=~/android-sdk-linux_x86-1.0_r2 # Where I extracted the SDK. $ PATH=$SDKDIR/tools:$PATH $ activitycreator -o somepath some.project.name $ cd somepath
At this point Ant can build the project, but masochists like me will prefer to shun Ant and run the underlying commands themselves. The following command generates R.java from the resources:
$ aapt p -m -J src -M AndroidManifest.xml -S res -I $SDKDIR/android.jar
Next, the source is compiled to .class files. This is why we need the JDK:
$ mkdir bin/classes $ javac -encoding ascii -target 1.5 -d bin/classes \ -bootclasspath $SDKDIR/android.jar src/some/project/* # When libs exist, append -classpath=libs/*.jar
These files contain instructions for the JVM. They are converted to Dalvik bytecode via:
$ dx --dex --output=bin/classes.dex bin/classes # If libs exist, append libs/*.jar
The resources and assets are packaged:
$ aapt p -f -M AndroidManifest.xml -S res -I $SDKDIR/android.jar -F bin/projectname.ap_ # When assets exist, add -A assets
This package is itself packaged with the Dalvik bytecode to make the final product:
$ apkbuilder bin/something.apk -z bin/projectname.ap_ -f bin/classes.dex -rf src -rj libs # Use -u for unsigned builds.
Now if I could only roll my own Dalvik compiler for a language I like, I could avoid the Java SDK, as well as Java itself.

Encoding videos for the G1

2009-01-04T15:54:00.001-08:00

Soon after Android's debut, initial reviews were complaining about the G1's inability to play videos. At the time I felt it was a trifling matter. Since YouTube already works on the G1, a more general video player ought to require only minor tinkering. And why is it a big deal anyway? Are people in a rush to experience Hollywood blockbusters on a tiny screen and tinny speakers?

Sure enough, video playing apps appeared quickly on Android Market. I found at least three in my last search. As for their utility: now that I've played with them, I understand why some see a video player as a must-have, and not merely yet another vehicle for demonstrating the G1's capabilities.

While breathtaking cinematography, award-winning soundtracks and state-of-the-art special effects translate poorly to a handheld device, movies that derive their strength chiefly from factors such as a witty dialogue lose little. Informational clips are another good use case. And even with scenes that only work well with a big screen: if they're my favourite scenes of all time, it's still comforting to have them at my fingertips, even if they are greatly reduced.

Which leaves the problem of converting videos to a G1-friendly format. I knew almost nothing about the black art of video encoding, but after hours of false starts and trawling the net for help, I still know almost nothing. However, I picked up enough to get started.

An unofficial FAQ states the G1 currently supports the H.264, 3GP and MPEG4 video codecs. I skimmed a few Wikipedia entries to decode this alphanumeric soup, and my interpretation is that this really means the G1 recognizes .MP4 and .3GP files (which are container formats and not video encoding methods) and understands the H.263, MPEG-4 ASP ("roughly similar" to H.263) and H.264 (aka MPEG-4 AVC) video compression standards. [Trivia: ASP expands to the somewhat oxymoronic "Advanced Simple Profile".]

The G1 only speaks the BP (Baseline Profile) dialect of H.264; videos that use more advanced features of H.264 play incorrectly, or not at all. [At last this post makes sense to me!]

On Ubuntu, the easiest way to encode videos was to use avidemux (sudo apt-get install avidemux). For audio, I only tested the AAC codec (usually at 96kbps), but several others should also work. For video, selecting MPEG-4 ASP produced videos that seemed to tax the CPU heavily on playback, often to the point of unwatchability. Perhaps this could be remedied by lowering the number of frames per second via an appropriate filter.

In any case, I prefer selecting the MPEG-4 AVC video codec and dumbing it down for the G1 by disabling the appropriate H.264 options: I changed the Max Consecutive B-Frames to 0, unchecked all options related to B-frames, and disabled CABAC along with the 8x8 Transform and 8x8 Intra search options. As before, I added the MPlayer variant of the resize filter: the G1 has a 480x320 screen in landscape mode. At 384kbps, this produced videos that played smoothly though higher bit rates should be feasible.

Now that I appreciate video more, I eagerly await the "Cupcake" Android update which is rumored to have video recording. I also hope the next generation of hardware will have video out and enough power to handle any popular codec.

G1 Miscellany

2009-01-03T04:35:00.001-08:00

What fortuitous timing! Intending to start from a clean slate, I performed a factory reset on my G1 recently. I had forgotten that, unlike the Developer Edition of the G1, even an unlocked standard issue G1 requires a SIM card with a data plan for the initial setup.

I was going to wait until I could borrow a suitable SIM from a friend for a few seconds (as after registration, I'm happy to use just WiFi for my G1 net needs for the time being), but I just heard about a new jailbreak for all G1s. It works by flashing the G1 back to RC29 where the old jailbreak can be exploited. Once done, one can register the G1 via WiFi, without a data plan or even a SIM.

Some Linux-specific notes. The G1 is touchy about the SD card for the RC29 image. The time it worked for me, I had reformatted it with "mkfs -t vfat /dev/foo", and used uppercase exclusively for the filename. To get the "adb" tool from the Android SDK working, I had to create an appropriate /etc configuration file.

I only needed two of the incantations. On the G1, I enabled adb via:
<enter>setprop persist.service.adb.enable 1<enter>

and once in the adb shell, I opened the Settings menu before registration:
$ am start -a android.intent.action.MAIN -n com.android.settings/.Settings

From here it was trivial to setup WiFi and sign in.

Some unrelated tips. When typing, Alt + Delete clears the whole line. RemoteDroid turns the G1 into a wireless keyboard and mouse; a fun application to show off.

I remain easily amused by the digital compass. The Orienteer app is often the first app I demonstrate. Also, the Sky Map app is perfect for those interested in picking out constellations in the night sky, but not interested enough to actually memorize them and figure out when and where they can be seen.

The T-Mobile G1

2008-11-26T17:52:00.001-08:00

I had intended to code more for my GP2X, starting with tweaking my version of Netwalk. But I almost certainly never will, now that I recently received a T-Mobile G1 phone. Though less suitable for gaming, its smaller size along with its phone and WiFi mean I'll actually carry it everywhere and run its apps.

I had thought it likely that I'd end up reverting to my old simple phone and only access the Internet with my laptop, as I have always done, but the G1 has enough right that I finally see why so many people are effectively surgically grafted to their smartphones. Judging by the last few days, I've become one of those addicts I formerly mocked. I've even caught myself scrolling the home view (or whatever it's called) back and forth, just to enjoy the smooth parallax action at my fingertips.

Even now I get that "shiny new toy" delight from discovering a new G1 trick. Some "Wow!"-worthy free apps:

Twisty: Interactive fiction on the go. (Not on Android Market at the moment; I installed this by allowing unknown sources and running ApkInstaller.)
ShopSavvy, CompareEverywhere: When did you last own a phone that could scan barcodes for price comparisons?
WikiTude: Try this futuristic app in a photogenic location.
StreetView: Digital-compass-enhanced deja vu on demand.
Amazed: Hone your tilting skills.
Voice Dialer: I have to put on an American accent to get digits working, but I'm impressed it recognizes my atrocious pronunciation of certain names. When will we see more voice control and text-to-speech apps?
Flashlight: Unexpectedly handy. If only I could find a colour that brings out the printer dot codes. Or even better, an app that could decode the patterns for the secret agent appeal.

Full disclosure: I work for Google, though not on Android. Not that it matters as you should approach everything you read with healthy skepticism! Anyway, I'm not completely happy with the G1...

The n things I hate about Java

If it weren't for Java, I'd already be writing Android applications instead of writing about them. I've never gotten along well with the language. I'm old enough to remember the hype surrounding its release. I instinctively distrust excessive marketing (which indirectly caused an unrelated language to be named "JavaScript") and my experiences have only reinforced my initial disdain.

When I first examined Java, I was dismayed that autoboxing was unsupported (now fixed) resulting in the "int versus Integer" mess. I also felt they had missed a golden opportunity to leave the most confusing parts of C syntax behind, instead of superficially pandering to veteran programmers. Also, my pro-multiple-inheritance stance obviously clashed with Java. It seemed to me Java was made public before it was ready. Resources spent on marketing may have been better spent on improving the language before release.

Years later, another encounter cemented my opinion. In a project where I had to use Java, I wanted a thread to perform a nonblocking read on a channel. I was mildly perturbed when I found the Java threading API describing certain functions as deprecated because they were impossible to implement safely. How could they get this wrong? Surely they could have studied any of the many previous threading APIs?

More distressing was my lengthy trial-and-error discovery that my desired nonblocking read was impossible, due to some API design detail which I've gladly forgotten. I do remember documentation claiming the issue was addressed in a newer version, but unfortunately I was constrained to an older version. When I eventually worked around the problem, I felt especially frustrated since I could do exactly what I wanted in a few lines of C.

Shifts in my beliefs have further lessened Java's appeal. I was once an object-oriented fanatic, even submitting an object-oriented entry to a programming contest in a futile attempt to "prove" it was the right way to design software. (To clarify, I'm not saying the attempt was futile because it was object-oriented; the blame lies with me.) In those days I shunned Java because it wasn't object-oriented enough. Since I renounced my object-oriented ways years ago, I now feel Java is too object-oriented!

Now, to develop for Android, I must face Java again. That I'm willing to consider this is itself a glowing endorsement of the G1. I remain unimpressed: Java's primary advantage appears to be its fame, not its features. In fact, developers are urged to avoid common object-oriented practices for performance reasons.

Additionally, the downloads are heavyweight; a good net connection is a must. The "Hello, Android" example somehow requires a nontrivial amount of code as well as an XML file. In contrast, for C, a kinda sorta C compiler fits in a few hundred lines, and "Hello, World" fits right here: int puts(const char *);int main(){return puts("Hello, World!");}

This comparison is grossly unfair, as C libraries for such a sophisticated phone would also be nontrivial, but all the same, if the Bell Labs researchers of yore were behind the drawing board, the programming interface would be terse and elegant.

One bright spot is Android's register-based Dalvik virtual machine. A prevailing attitude was (and still is?) that Java could replace C/C++ in most situations: how can this be when the standard JVM is a stack-based snail? This is yet another detail Java should have got right from the start; compare with the design of Inferno's Dis virtual machine.

I hope Dalvik bytecode compilers for more agreeable languages will spring forth soon, as that will eliminate my biggest gripe.

Hardware Hankerings

Some deficiencies can be resolved with a little money. At the top of my wishlist is a standard stereo jack so I can use it as a stand-alone music player; I'll probably get an HTC 3-in-1 USB adapter for this purpose. (New G1 buyers will get an adapter free, but that's little consolation for me.) I'll probably also fork over dough for a bigger micro SDHC card, preferably at least 8GB so I can laugh at standard 4.7GB DVDs.

Other features will have to wait for the next generation. For gaming, I'd love to have an Android device with a nice D-pad or two; see the Pandora. While I'm at it, a video camera as well. One that can face the user so you could videophone others like in many a sci-fi flick. And then I may as well ask for a video out too, so it could be a stand-alone video player. Rather than build in all these gadgets, it may be better to have a few standard ports (perhaps USB) to attach oddball devices. I can't wait to see what they'll come up with.

Notes on my notes on Git

2008-11-05T16:35:00.001-08:00

I was mildly shocked, but honoured, to find that the venerable (or at least popular!) Wikipedia references my tutorial in its article on Git. Interestingly, the entry states that Git tips and tricks are 'popularly referred to as "magic"'. I named my guide Git Magic as a homage to Arthur C. Clarke's quip featured in the preface, and also because magic happens to be a hobby of mine. If the Wikipedia comment is true, then either my title was fortuitously appropriate, or I have unwittingly coined a phrase.

More pleasant surprises followed. The guide appeared on the first page when I Googled for "git" (though sadly much lower on Yahoo). I found several pages linking to mine, whose recommendations were probably responsible. Thanks to everyone who praised and promoted my site. [I do work for Google, but I have no control over the ranking of my content.]

It almost makes me feel guilty that my enthusiasm for maintaining the guide and for source control in general has waned. But this is inevitable because of Git's power and convenience: I use Git so frequently that it has faded into the background. Fascinating new commands have gradually transformed into boring old reflexes. Documenting them has as much appeal and utility to me as documenting my exploits with, say, the ls command, or sleeping and eating. Also, there are many more Git tutorials these days. But as long as my site ranks well, I'll attempt to keep it updated.

I use Google Analytics to keep an eye on site traffic as I lack access to the logs on the Stanford server hosting Git Magic. Some observations:

On 20080412, traffic to my site, which includes Git Magic, spiked at over 10000 hits. Previously few days saw more than 100 hits. The spike rapidly diminished to 100 to 200 hits per day until 20080805, when a larger spike of 16000 hits occurred. Again, this activity tapered off quickly to a few hundred hits per day until 20081102, which featured a small spike of over 3500 hits.

It seems the first and third spikes were caused by reddit.com, and the second spike was caused by an article at LWN.net.

Since mid-September 2007, roughly when the guide was released, the top three browsers were Firefox (67.43%), Safari (12.48%) and Internet Explorer (6%). The top three operating systems were Windows (36.53%), Linux (35.15%) and Macintosh (26.9%).

A handful of hits identified themselves as mobile devices: iPhone (489), iPod (113), SymbianOS (19), DangerHiptop (11), PalmOS (4), Android (3). Some intriguing curiosities: Playstation 3 (8), Nintendo Wii (6) and OS/2 (1).

During the last spike, the top three browsers were Firefox (69.42%), Safari (12.33%) and Chrome (5.15%), and the top three operating systems were Windows (49.45%), Macintosh (27.23%) and Linux (21.73%).

Restoring GRUB after reinstalling XP

2008-11-05T02:09:00.001-08:00

For me, a common system setup is dual-boot Windows and Linux, and a common problem is an overwritten MBR (Master Boot Record) after reinstalling Windows XP, making it impossible to boot to Linux. Most sites recommend using a Linux install or rescue CD to fix this, but I prefer to install the GRUB bootloader on the Windows partition, and then use GRUB to boot into Linux to repair the boot record:

Download the latest zip file from GRUB for DOS and extract the file grldr to C:\
Run cmd and type:
cd \ attrib +r +s +h boot.ini edit boot.ini
Append the line
c:\grldr="GRUB"
to the operating systems section, which is usually last. Save and quit.
Type
attrib -r -s -h boot.ini
Reboot and select GRUB from the boot menu.
From the grub prompt we can repair the system:
find /boot/grub/stage1 root (hdX, Y) setup (hd0) reboot

Take care with boot.ini as invalidating this file can render the system unbootable. In this case you must boot by another method, e.g. network, USB, CD or floppy.

AsciiDoc and MathML

2008-09-04T21:04:00.001-07:00

Nowadays I use AsciiDoc to author HTML. I'm even converting old pages to use this convenient and presentable text format.

My mathematics notes present an interesting challenge. For MathML the AsciiDoc user guide recommends using double-dollar passthroughs around equations, but this implies at least three characters are required to delimit every equation, since ASCIIMathML or equivalent itself needs at least one character.

I'd like to have something like:

= Introduction =

Let $E: Y^2 = X^3 + a X + b$ be an elliptic curve.

to just work, so I settled on the following solution. I use itex2MML because

My old-fashioned, superstitious, purist side prefers bare-bones JavaScript-free static documents.
Familiarity.
It has a handy syntax for equations in display mode, i.e. equations in their own center-justified paragraphs as seen in mathematics texts. An invaluable feature, as I can't figure out how to center a paragraph with AsciiDoc.

It should be simple to substitute an alternative such as ASCIIMathML. Some may prefer its approach because documents are smaller, and the page source is intelligible. But I argue that most never bother viewing the source, the savings are slight, and one can always provide the AsciiDoc source if these factors matter.

Write these rules to a file named "macros":

[miscellaneous]
newline=\n

[blockdef-passthrough]
delimiter=^@{4,}$
subs=none

The first is optional. I just abhor the CR LF abomination.

Then feed the source through these commands to produce the final product, which should be a file with an .xhtml extension:

sed 's/\$$[^$]*$\$/+++$\1$+++/g' \
| sed '/\\\[/i@@@@' \
| sed '/\\\]/a@@@@' \
| asciidoc -b xhtml11 -f macros - \
| itex2MML | sed '/<!DOCTYPE/c \
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0//EN"\
"http://www.w3.org/TR/MathML2/dtd/xhtml-math11-f.dtd" [\
<!ENTITY mathml "http://www.w3.org/1998/Math/MathML"> ]>
/xhtml11.dtd/d'

The above gobbledygook [careful with some of those newlines; Blogger may have put extra cuts in my lines] performs the following:

Put the "+++" AsciiDoc inline passthrough around equations delimited by "$".
Surround display-mode equations, delimited by "\[" and "\]", with our newly defined "@@@@" block passthrough macro.
Put the resulting mess through AsciiDoc, which converts everything but our equations to an HTML 1.1 document.
Run itex2MML to convert the equations to MathML.
Fix the DOCTYPE declaration.

Caveats:

Inline equations must be closed on the line they are opened.
Expressions such as "$i$th" must be written as "$i$#th#", since AsciiDoc "+++" quotes are constrained.

I'm content with this setup, but I'm considering extending my script to detect equations automatically, a recent feature of ASCIIMathML, so that even the dollar signs are unnecessary.

Memory Mapped Files

2008-06-20T23:22:00.002-07:00

I've only recently learned about memory-mapped files in Linux. Until recently, to perform file I/O, I followed the textbook examples of using read and write calls on file descriptors or streams. It wasn't until I browsed the git source (to help with my git clone) that I came across a mysterious mmap() call.

Not only is it more efficient for the reasons given in the Wikipedia article, but it is easier to work with file contents as if they were already in memory. There's no need to learn the syntax and semantics of various read and write calls.

The only tough part is remembering the mmap syntax. But the call can be readily encapsulated. For example, to read a file, I define a function like the following:

void *map_file_to_memory(size_t *len, const char *path) {
  int fd = open_or_die(path, O_RDONLY);
  *len = get_size_of(fd);
  if (!*len) {
    close(fd);
    return NULL;
  }
  void *map = mmap(NULL, *len, PROT_READ, MAP_PRIVATE, fd, 0);
  if (MAP_FAILED == map) die("mmap failed");
  close(fd);
  return map;
}

There are concerns with large files, but hopefully madvise() is well-written and can prevent excessive page faults.

Thai Rummy

2008-05-16T01:05:00.001-07:00

I've already written about my fascination with playing cards and card games. At last I've filled in a conspicuous gap in my repertoire: a two-player card game I can play for hours.

I've somehow overlooked a family of two-player card games that require only a standard deck and are playable in many situations: Gin Rummy and friends. I had tried playing before but I never appreciated them until recently, when a veteran taught me an interesting variant, and repeatedly beat me easily. At first, that is!

Apparently, this variant is popular in Thailand, but I have yet to see these precise rules described elsewhere, though 500 Rum comes close.

Deal: I believe the first dealer is determined randomly. In following hands, the loser of the previous hand is dealer.

The dealer deals 13 cards to each player, and places the remainder, the stock, face-down. The top card of the stock is placed face-up in between the players to start the discard pile. The non-dealer goes first.

One aims to meld all cards in hand, either in sets: 3 or 4 cards of the same rank, or in runs: 3 or more cards of the same suit in sequence. A card can only be melded once, so it is impossible for it to count towards a set and a sequence. Aces are always high, and 2s are always low, so in particular A-2-3 is an invalid run.

Play: Each turn consists of three phases:

1. Draw: a player can take a card within the discard pile, if they can use it to form a set or run with at least one card in their hand and optionally using discards further up in the pile, and additionally if they take every card lying on top. They must display the meld, by laying it on the table in front of them.

In other words, they take some number of cards from the top of the discard pile, and use the bottommost card taken in a meld, which must then be exposed immediately.

If a player is unwilling or unable to take any cards from the discard pile, they must draw a card from the stock, unless the stock is exhausted in which case the player must pass. If both players pass, the hand ends.

2. Meld: the player may display on the table as many melds as desired from their hand, so long as they have at least one card left in hand. They may add cards to existing melds belonging to either player, but in both cases the cards are placed in front of the player extending the meld.

3. Discard: the player must discard one card. If it is their last card because all their other cards have been displayed, then it is placed face-down on the discard pile and the hand ends. Otherwise it is placed face-up on top of the discard pile and off to one side, so that every card in the discard pile can be seen at all times.

Scoring: A player receives 50 points for placing a card face-down on the discard pile, that is, when they have melded all their cards save one which becomes the discard. They are considered the winner of the hand, even if they ultimately have a lower score. If the game ends but both players still have cards, the winner is the player with the higher score.

A player adds the values of the cards displayed in front of them and subtracts the values of the cards remaining in their hand: cards of rank 2 to 9 are worth 5 points each, 10, J, Q, K are worth 10 points each, and Aces are 15 points each, with two exceptions. Both the Queen of Spades and Two of Clubs are worth 50 points.

Typically a hand ends because one player has melded their entire hand, and only one player subtracts the values of cards from their total. Both players subtract values of cards only when a hand ends because both players have passed.

There are two "stupidity" penalties. Firstly, if a player wins by melding their whole hand after taking just the top card of the discard pile, that is, the opponent's last discard, the opponent subtracts 50 points from their score.

Secondly, during the game, when a player discards a card that could have been used to extend an exposed meld, that player loses 50 points. The penalty is cumulative; each offence costs a player 50 points.

Lastly, there is a doubling rule: if a player does not display any melds except possibly in the final turn, their score for the hand is doubled. So if a player wins by melding their entire hand, and had not previously displayed any melds, their score is doubled. This is almost always beneficial because they usually have a positive score. And if a player wins by melding their entire hand and their opponent has not yet displayed a single meld, the opponent's score is doubled. This is always harmful to the opponent because they must have a negative score, seeing as no melds were made and cards remain in hand.

Winning: The final score is added to a running total. There are two victory conditions. If a player has -500 or fewer points, their opponent wins the game instantly. Otherwise the first player to have 500 points or more after going out wins the game.

More players: if there are a few more players, deal three fewer cards per extra player.

Distinguishing Characteristics

Summary for those familiar with rummy games:

Aces always high, 2s always low
Can take variable number of cards from top of discard pile; must use the bottommost card taken
Must make a new run or set with this card; cannot just extend existing meld
Must meld with at least one card in hand with this card
Boathouse rule: must discard when going out
Hand ends immediately after a player goes out
50 pts for going gin
-50 pts for giving opponent single discard used to go out
-50 pts for discard card that could augment a displayed meld
Score doubled for never displaying melds
Values of cards: 2-9: 5 pts, 10-K: 10 pts, A: 15, except QS, 2C: 50 pts.
-500 pts loses the game
500 pts insufficient for win; must also go out

Update 20090504: Ricky emailed me about his site, rummy.com, where you can find rules and background information for other rummy variants from around the world. You can also play them online.

Thinkpad X61 Wireless and Ubuntu

2008-03-26T21:29:00.001-07:00

At last I have resolved a long-standing gripe with Ubuntu on my ThinkPad X61.

Months ago, soon after installing Gutsy Gibbon, I found that my wireless card initially worked well. But a few minutes later, my connection was dead, and I could only restore it by unloading the iwl4965 driver, reloading it, and reconnecting to my access point. Unfortunately, after an indeterminite amount of time the problem would reoccur.

I experimented a little and discovered that by instructing my wireless router to accept anything only 802.11g, the problem vanished. When away from home and using other wireless networks, occasionally my connection would spuriously disconnect. Fortunately, the wireless networks I usually frequent somehow never cause this bug to manifest.

Yesterday my wireless connection was unbearably flaky, and several times, even reloading the driver proved fruitless. I finally decided to look for a proper solution.

Typing dmesg revealed that every time the connection dropped, a message similar to the following would be logged:

[  154.652000] wlan0: No ProbeResp from current AP 04:11:46:fe:24:b0 - assume out of range

Googling for "iwl4965 no proberesp" shows that many others have had the same trouble. Some pages were unanswered bug reports, and others contained discussion where the consensus was to reload the kernel module as a workaround. Happily, before long I stumbled across a FAQ for the ThinkPad T61 that describes a permanent fix, which I'll repeat:

Download the latest iwlwifi microcode
Replace /lib/firmware/2.6.22-14-generic/iwlwifi-4965-1.ucode.
Reload iwl4965 module

The new microcode banished my wireless woes, and the dreaded "No ProbeResp" no longer appears in the logs.

Now I'm left with one remaining significant complaint: the graphics driver. My i965 mostly behaves but there are minor annoyances involving compiz, and major ones involving Wine. I'll leave this for another time.

Cross-compiling GMP

2008-03-20T01:59:00.001-07:00

I build Windows binaries from Ubuntu, using the MinGW port (search for packages starting with mingw).

For the PBC library I need a Windows version of the GMP library, which I build using:

$ ./configure --prefix=~/cross/gmp --host=i586-mingw32msvc --build=local
$ make install

I don't fully understand how it works, but when it's over, I have libraries I can link against to produce Windows executables that can do multi-precision arithmetic.

I sometimes test the binaries with wine. Thus Windows can be completely avoided in the development cycle, from coding to building to testing. However, for an important project, I'd test on at least one real Windows box.

xrandr

2008-03-17T23:44:00.001-07:00

In the old days, to get the external VGA output working on my laptop in X, or even switch resolutions, I'd have to edit an overly complex configuration file and restart X. Nowadays, I use the X Resize and Rotate Extension via xrandr, which is considerably more convenient. I like to control displays through the command-line interface. I find typing the full command cumbersome, so I use this simple script instead:

#!/bin/bash
case "$1" in
  left)
    xrandr --output VGA --auto --left-of LVDS
    ;;
  right)
    xrandr --output VGA --auto --right-of LVDS
    ;;
  up)
    xrandr --output VGA --auto --above LVDS
    ;;
  down)
    xrandr --output VGA --auto --below LVDS
    ;;
  big)
    xrandr --output VGA --mode 1600x1200 --above LVDS
    ;;
  off)
    xrandr --output VGA --off
    ;;
  *)
    xrandr --output VGA --auto --same-as LVDS
    ;;
esac

Thinkpad X61 Volume Buttons

2008-03-15T09:58:00.001-07:00

I tried in vain to get the brightness adjustment keys to work, but at least the volume up and down buttons were easy to handle. They trigger bona fide X key events, so I added a couple of lines to .xbindkeys:

"amixer -c 0 set PCM 1dB+"
  XF86AudioRaiseVolume

"amixer -c 0 set PCM 1dB-"
  XF86AudioLowerVolume

GP2X Revisited

2008-03-04T00:01:00.001-08:00

Soon after my last post, I tried out some simple ideas for smoothing out the spurious stylus events on my GP2X. The results were promising, but unfortunately before I could experiment anymore my device began malfunctioning. The left and right edges of the screen did not respond properly, and the problem quickly worsened. Soon I could only draw on about a third of the display, in a central vertical band.

Luckily it was still under warranty. I sent it back to www.GP2Xstore.com, who promptly passed it on to GamePark Holdings for repair. A few weeks later a replacement arrived. I still can't draw on the extreme left, right and bottom edges, but it works well enough for my primitive drawing program. The improved behaviour due to jitter correction is self-evident.

touch2x-0.0.1.tar.bz2

Music Players and Game Consoles

2007-11-22T14:33:00.001-08:00

Long ago, over a long period of time, I wore out my old MP3 player, a Cowon iAudio X5. First its battery life shortened dramatically. Then after severe mistreatment during a long flight, the headphone jack loosened and became very fussy. Only by pushing the plug in a certain way was I able to achieve stereo sound.

Its condition worsened over time, and the final nail in the coffin was hammered in when, in desperation, I opened it up hoping I could readjust the socket somehow. I wound up breaking a wire.

I could solder it back, but what's the use of bringing it back from the dead if it has a run-down battery and a messed-up audio jack? Besides, I now had a great excuse to shop.

I considered getting another product in the same family, such as the A2, but in the end I took a different direction. Two different directions in fact: I wound up buying two MP3 players to replace my old one.

First, some lessons learned:

I often just pushed play, and didn't bother fiddling around with the controls. Instead I'd cram it into my pocket, and perform other tasks.
The built-in battery was annoying, especially when traveling. I'd have to find adapters and/or transformers, or have a computer around. Not to mention carry a strange, easy-to-lose connector and a power cord.
Its utility greatly decreased with its battery life.
For some situations it was too big and unwieldy, while for others, such as when reading text files and playing movies, it was too small and unwieldy.

To address some of these concerns, I bought one of those small cheap MP3 player that is little more than a USB SD card reader. It's powered by a single AAA battery, and sports a tiny display and a few buttons. It's perfect for those times when I'm focused on something and want some background music. Instead of playlists, I treat SD cards like CDs, and swap in different cards when I want to change genres.

It's convenient to travel with, due to its low cost and small footprint. Furthermore, AAA batteries are readily available anywhere. As a bonus, it can function as a low-capacity USB thumb drive.

However, there are times when I want to read text files or watch movies on the go, and times when I absolutely must listen to that song right now. I also missed my iAudio's ability to play different music formats, and its ability to run the open source firmware Rockbox.

So on an impulse, I recently picked up a GP2X F-200. It does music and video of various formats, but what really piqued my interest was that it plays games and runs Linux. It has two 200MHZ ARM9 processors, which amuses me because only three desktops ago, my system was a Pentium 200. And in line with my new philosophy, it has an SD card slot and is runs on 2 AA batteries.

I still miss the 20 gigabyte hard drive, FM radio and recording capabilities of my X5, but the GP2X offers more possibilities.

Hello, GP2X F-200
Mainstream gamers no doubt prefer the well-known brands for a hand-held gaming platform, as they have a wide selection of new titles and probably have better build quality. But my priorities are different: I mostly wanted a replacement music and video player, and the GP2X appeals to me thanks to its geek cred.

There is a highly active GP2X development scene. It mostly revolves around simple homebrew games, ports of classics, and emulators, but there are a few commerical games, and some of the freeware offerings are amazingly good.

One such gem is Cave Story, which I found on the bundled CD. I'd never heard of this game before, though it's been available for other platforms for quite some time. As a programmer and amateur game developer, I'm green with envy that one person alone was able to create this marvel.

Soon after my unit arrived, I looked into how the development process works. I followed the Open2x installation instructions at the GP2X wiki (except I placed them in a different directory) but for touchscreen support, afterwards I installed the newest version of the SDL library found on Paeryn's page.

I then set about writing the obligatory "Hello World" program. It's not good enough to print to standard output, because nothing shows up. Instead, I wrote a full-blown SDL program that uses the SDL_ttf library to render a string. Additionally, I had to write a shell script to return to the main menu after the program exits (and also sync the SD card).

hello2x.tar.bz2

Next I augmented the code to experiment with the touch screen, and the result is a simple drawing program. I'm disheartened by many spurious events, though I have a few ideas on how to clean them up. This must be done if I'm to get the most out of this feature.

touch2x.tar.bz2

Green circles represent when the stylus was placed on the screen, and red circles represents when it was lifted, corresponding to SDL's MOUSEBUTTONDOWN and MOUSEBUTTONUP events. As can be seen, there are times when it thinks you've lifted the stylus when you haven't, and a fair amount of jitter, usually in the horizontal axis.

Linux on a Thinkpad X61

2007-11-08T15:06:00.001-08:00

My X31 which I repaired a while ago died again. This time I think the system board is gone, as there are no signs of life. Nothing I do, even plugging in a power cord (and I tried several), will make any of the LEDs light up. It is functionally equivalent to a brick.

I decided to purchase a Thinkpad X61 instead of a replacement system board. I chose to stick with the Thinkpad X series for several reasons. For starters, Thinkpads endure. Well, apart from my X31, though it still outlived other brands I've tried. I even have an old Thinkpad 240 that's still running strong.

Another reason is that I want a good balance of small footprint and performance. I went through a phase long ago where I thought the biggest baddest laptop that money could buy was the right choice, but after trying it once, I discovered clunkiness destroys half the appeal of a laptop, and furthermore, a cheap desktop with accessories will give a much better computing experience.

But most importantly, Thinkpads have a good track record with Linux support. Nonetheless, I did a few quick Google searches to confirm that this was the case for the X61. Happily there are many results.

My X61 arrived last month, and with Vista installed by default. Vista is astoundingly bad. Not only is it slow, but every few actions, everything grinds to a halt until I handle some dialog box about giving permission to some process or other.

I suppose some effort was put into making the interface look slicker, but there is also plenty of extraneous rubbish that serve only as visual distractions and annoyances. Perhaps Microsoft is not entirely to blame, as some of the pop-ups are plastered with the Lenovo logo.

In any case, my new system was unusable. I had to escape from Vista. It had been a long time since I had last installed Linux, as once setup correctly, there's rarely a reason to reinstall. I spent some time learning about the latest installation methods.

Network Installation

There's no need to prepare a floppy, CD or any other kind of removable media. Visit http://www.goodbye-microsoft.com/ from any version of Windows, including Vista, and you can have Debian up and running within minutes.

Note UNetbootin is a similar program for Ubuntu, but Vista support is still in the works.

There was one small hiccup. The Debian-installer loader ran fine, but a reboot brought be back to Vista (taking forever to load of course). After further research I discovered that I had to mess with the BCDEDIT program to set a nonzero delay so I could actually select Debian from the Vista boot menu.

Then deja vu. I was reminded of the first time I tried installed a Linux desktop: back then, it must have taken me a day to get sound working, and another for the network.

The wireless didn't work. Neither did the sound. The "vesa" graphics driver performed badly: switching back to text mode resulted in a blank screen. This system is too new for Debian.

I had read success stories using the development version of Ubuntu ("Gutsy Gibbon"), and a few unsuccessful attempts at getting the wireless working I figured I'd switch.

I tried to do so with UNetbootin (run from Debian) but I must have screwed something up because I was left with an unbootable system: the Grub bootloader had taken over the master boot record, and was somehow configured badly. To salvage the situation, I used a PXE network boot, and from a menu option I installed Gutsy.

The wireless network card (Intel 4965) worked out of the box, as did the "intel" video driver for X windows. Back when I first tried this, and before Gutsy was officially released, sound didn't work and I had to download and compile the development version of ALSA's "hda_intel" driver to rectify this. But the latest version works out of the box.

Various buttons such as the brightness and volume controls have no effect, but if I were so inclined, I could fix this by scripting commands with the aid of the ibm-acpi package.

Mission Accomplished

My laptop is now usable. Not only that, but it is orders of magnitude faster and smoother than any other system I use. I have more to say, but rather than delay this post yet again, I'll save the material for future articles.

AsciiDoc

2007-09-20T20:26:00.001-07:00

It turns out I've been reinventing a wheel. A few posts ago I spoke of creating a script that converts a text file to HTML, where the text file itself is highly readable. With clever ASCII usage, headings should look like headings, emphasized words should look like emphasized words, and so on, and there should be no ugly tags peppered throughout.

I came across AsciiDoc, which does exactly this, and is far better, older, and more capable than my simple script. Interestingly, the format I came up with does not differ that much.

I've converted a few pages on my homepage to AsciiDoc. This format makes the most sense to me. HTML files with their space-hogging outlandish tags are unpleasant to read. Text files convey the same information, are easy on the eyes, and can be converted to HTML in no time.

Also, why should I spend so much time making sure I'm using the right tag, and that my tags are nested properly and so on? Computers are supposed to do the mundane stuff for us. Generally speaking, computers should automate as much as possible so long as it is efficient and the process does not hamper human comprehension.

Automating Automounting

2007-09-12T15:18:00.001-07:00

Newer, friendlier Linux distributions such as Ubuntu must surely make it easy to use CDs, CompactFlash and SD card readers, USB drives, external hard disks and so on. But I'm old-fashioned, and like to do things the hard way, that is, edit /etc/fstab and run mount and umount manually so various devices end up at places I like in my directory.

The problem is hot-pluggable devices get assigned different names in the /dev directory all the time. So I followed the first part of this guide that assigns the same name (that you choose) to the same device every time. Once this is done, you can modify /etc/fstab in the usual way.

While there, you might want to use the "noatime" mount option, or at least "relatime". See this Slashdot article.

Git Magic

2007-09-07T18:07:00.001-07:00

As I promised in a previous post, I'd write more on tricks one can perform with Git. I had so much to say that I made a site out of it: Git Magic.

It was also a great opportunity to practice my salesmanship, as can be seen from some of section titles: Ultimate Backups, Light-Speed Multitasking, Guerrilla Version Control, Uninterrupted Workflow. It was a probably a lot more fun to write than it is to read.

I'm hoping it will be useful to those new to version control, not just those new to Git. I took pains to explain the effects of Git branching. I had trouble understanding this from the official Git documentation, though it's probably better by now.

Wiki Formats

2007-09-05T16:58:00.001-07:00

For years I've dealt with raw HTML for a lot of my web pages. After some experience with various wiki sites, I've finally realized that it's a lot easier to maintain a bunch of simple text files marked up in some wiki format, and use clever scripts to convert them to HTML for publishing.

Source code should always be readable, and HTML does not quite make the cut. Reading documentation in raw HTML form is painful. Inspired by the Inform 7 language, I want my text file marked up with wiki to as close to a real document as possible. In other words, I want the source to be a pretty text file that you can read even if you don't have the HTML version. A bit like txt2html, but I want more control. Compare my homepage with it's wiki source.

And if you do need complex HTML, it's easy enough to provide a mechanism to temporarily disregard wiki tags.

I wrote a script that takes converts a text file, marked up in a certain way, and converts it to HTML with these goals in mind, and it's kept in a Git repository at

http://cs.stanford.edu/~blynn/scrap/wiki.git

[20090608: updated link]
I'll have to write instructions one day, but basically, headings are designated with equal signs around the heading, two single quotes are italics, asterisks are used to mark text as bold, a minus sign and indentation for lists. Other indentations mean text that should be displayed unformatted and as fixed width.

I'm gradually converting all my HTML to this wiki format, as it's easier to edit and maintain. An added bonus is that I can easily write scripts to output a different format, such as DocBook.

Git Revisited

2007-08-29T16:55:00.001-07:00

To my consternation, the cogito package disappeared from Debian a few updates ago. I soon discovered the reason. Contrary to Linus Torvald's prognostications, raw Git is now (verson 1.5) a user-friendly version control system and does not need wrappers.

Still, I had to learn some new syntax. Luckily I was interested in learning about Git's more advanced features so I didn't mind. I was only previously using Git via Cogito in the same way one would use CVS or Subversion, except that it was faster, more robust and easier to use.

Now I finally understand why Git can do so much more. Better late than never!

101 Ways To Use Git

Git is the duct tape of version control. When I first started using it, I only cared about a very specific problem and ignored Git's design and internals. I focused only on remembering the Cogito commands I needed to type to do what I want, oblivious to how it worked its magic. Relatively poor documentation is partly to blame, but in truth, it is extremely difficult to convey Git's extraordinary versatility.

The book "Design Patterns" showcases the diverse problems that object-oriented design can elegantly solve. I wish there were an analgous Git book, instead of explaining Git fundamentals and leaving the reader to derive the implications, gave a set of recipes to accomplish a variety of tasks.

Below are a few examples of Git recipes such a book might contain.

Instant Backup

Just as in a computer game, when I'm about to attempt something drastic I like to save the current state, so I can go back and try again should things go awry.


git-init
git-add .
git-commit -m "Initial commit"

to take a snapshot of all files in the current directory.
Then if something goes wrong type


git-reset --hard

to go back to where you were. To save the state again, type git-commit -a. You'll have to type in a description of the current state.

One benefit to doing this instead of simply copying files is that with Git's hash chaining, you can tell if a backup gets corrupted.

Undo/Redo History

More generally, you can do the above, and every so often "save the game" by typing


git-commit -a -m "description of current state"

Note if you want to keep track of newly added files or forget about deleted files you'll need to first run "git-add" or "git-delete" accordingly.

Typing git-log shows you a list of recent commits, and their SHA1 hashes. Then typing


git-commit -a
git-revert SHA1_HASH

will restore the state to the commit with the given hash. You might like to use something like the following instead:


git-revert "@{10 minutes ago}"

You can undo the undo: type git-log and you'll see that the other commits you made are still there.

To take the computer game analogy again, git-revert is like loading a game and recording this fact as another saved game, and git-reset --hard is like loading an old save and deleting all saved games newer than the one just loaded.

Sync Files Between Computers

This is the reason I first used Git. I can make tarballs or use rsync to do backups. The problem was sometimes I'd edit on my laptop, other times on my desktop, and they may not have talked to each other in between.

Initialize a Git repository and commit your files as above on one machine. Then on the other:


git-clone git+ssh://other.computer/directory

to get a second copy. From now on,


git-commit -a
git-pull git+ssh://other.computer/directory

will pull in the state of the files on the other computer into the one you're working on. If you've recently made conflicting edits in the same file, Git will let you know and you should resolve them with another edit and commit.

If you have not committed any changes on the other computer, you may type


git-push git+ssh://other.computer/directory

to push the current state to the other computer. Next time you're there, run git-reset --hard or git-checkout HEAD . to update the files.

That Git does not do the last step automatically is good in case you were in the middle of some uncommitted changes.

Tune in next time...

I've barely scratched the surface, and so far haven't shown anything you can't do with older version control systems. Next time I'll show off problems that only the new generation of version control can solve.

Elective Thinkpad X31 Surgery

2007-07-23T15:48:00.001-07:00

My trusty IBM Thinkpad X31 that Stanford bought me in 2003 has taken everything I've dished at it with only a couple of cracks in the case to show for it. At least, until recently. One awful afternoon, after hitting the power button I was briefly greeted with the message "Fan error" before it shut itself off. No amount of coaxing would bring it back.

My desktop is truly ancient, dating back to the last millennium, so I had grown accustomed to doing most tasks on my laptop instead. The first task was to retrieve my data, which is easily achieved with a SATA/IDE to USB adapter. Only one screw needs to be removed to retrieve the hard drive.

I was tempted to take the easiest but most expensive path: shell out for whatever passes for the best of the Thinkpad X series these days. But although working in industry means this remedy wouldn't sting as much as in my student days, it also means I don't spend as much time on my own machines. Now there's other things I'd prefer to get for that kind of money. Similarly, I didn't want to pay for it to be serviced.

My only recourse was to attempt a repair myself. The Lenovo webpage about servicing the Thinkpad X31 spooked me a little. What's going on in that diagram? Do I have to take it apart into a hundred pieces just to replace a fan? The table suggesting that fan replacements should not be undertaken by end users wasn't encouraging either. With a heavy heart, I ordered a 67P1443 fan anyway.

When it arrived, enthusiasm and impatience triumphed and I took out every screw I could see, but the fan remained elusive. Eventually I regained some sense, and Googled for "thinkpad x31 disassembly". The first result contained a links leading to the official Thinkpad X31 hardware maintenance manual. I should have known. What isn't online these days?

Fan replacements turn out to be almost trivial. After removing the battery and hard drive, I only had to remove the four clearly indicated keyboard screws, and then slide the keyboard out. Underneath, I discovered the reason for the fan error. Nestled in the fan blades was a tiny piece of foam, sticky on one side and rose-tinted on the other. A pink pad in my Thinkpad.

I suspect that the fan is still operational, but since I had a new one and had already removed the five screws securing it, I replaced it anyway. Also, it's easier to apply thermal paste to a new fan than clean and reapply to an old one.

The tougher part was figuring out where the pink pad belonged. There was another one in there somewhere that also looked like it had been slightly dislodged. I settled on pressing both of them against some metal frame in the center, where I presume they work best as shock absorbers.

Soon after I received my laptop I wrote a webpage about Linux on a Thinkpad X31. Only when I started blogging did I realize it would be much easier (for me at least!) to maintain with blog posts, and that's probably what I'll do in the future if I have more to add. Sure, it's nice to have all information in one place, but this can be approximated through appropriate use of tags. Furthermore, the dates on each post may also give the reader some idea of how relevant it is.

ALSA and MIDI

2007-07-01T23:02:00.001-07:00

I switched to the ALSA driver from the OSS driver for my Creative Sound Blaster Live! card long ago, but I'm still not used to how MIDI is done. I'll record the relevant commands this time, so I won't have to look them up yet again.

Lately, I've had to manually load the snd_seq kernel module.

Programs I wrote that look at /dev/midi00 should now look at /dev/snd/midiC0D0. The behaviour of this device file differs too: I had to change my code so that it could handle a read() call that returned less than the requested number of bytes.

To play MIDI files on my digital piano, I run pmidi -p 16:0 foo.mid.

To send MIDI events to fluidsynth from my digital piano, I run fluidsynth 2> /dev/null (to get rid of spurious warnings), load a soundfont, then run aconnect 16:0 128:0.

Nvidia GeForce 3 Cards on Debian

2007-06-12T01:24:00.001-07:00

For a long time I used the Debian nvidia driver packages, but GeForce 3 Ti 200 cards are now considered legacy cards, and not supported by the 97xx and newer series. After a recent upgrade, I had to remove my Debian nvidia packages and

Download the 96xx series Nvidia Linux drivers.
Run the install script as root.
Since I use the xorg X server, I had to move files around:
mv /usr/X11R6/lib/lib* /usr/lib/xorg/modules/ mv /usr/X11R6/lib/modules/drivers/* /usr/lib/xorg/modules/drivers/ mv /usr/X11R6/lib/modules/extensions/* /usr/lib/xorg/modules/extensions/

The BAD Library

2007-05-10T23:18:00.001-07:00

Not long after my last post I wrote some code to get some rough timings, and also to experiment with variations of hash tables that my textbooks never taught me: with cuckoo hashing you can have expected constant-time insertion and worst-case lookup time. Additionally, with cells, you get hash tables that can handle over 90% load. Also, hash functions recommended by classic textbooks are no good: Bob Jenkins' hash functions are much better.

Along the way I had to implement (or import from other projects of mine) other abstract data types. Soon I had crit-bit trees, hash tables, linked lists and dynamic arrays.

I finally got around to packaging it up: bad-0.0.0.tar.bz2.

BAD stands for Ben's Abstract Datatype, and also refers to the current state of the code and documentation. See the README for the preliminary results.

Trees, Hash Tables and Tries

2007-04-11T23:39:00.001-07:00

As a computer scientist, I'm supposed to possess thorough grounding in fundamental data structures and algorithms. I must be getting rusty, for lately I've been perturbed by basic facts taught to novices.

After some thought I've resolved my difficulties, but now I feel many textbooks need to be rewritten. Either that, or I've made a monumental embarrassing mistake.

Let's say you want an associative array that maps strings to something.

I've known for years that hash table lookups take O(1) time. And that binary search trees have O(logn) lookup time. (In both cases I'm assuming certain conditions are satisfied, i.e. there aren't too many hash collisions and that the binary tree is fairly well-balanced.)

More recently, I learned about crit-bit trees, aka radix trees, Patricia trees or Patricia tries. (See D. J. Bernstein's crit-bit tree page for more references. Briefly, crit-bit trees are like binary trees with two major differences. Firstly, they are tries, which means keys are not stored in any non-leaf node and instead, the position of a node on a tree represents the prefix of the keys stored in its descendant leaves. Secondly, no node has only one child: a crit-bit tree is a trie where any node with a single child has been merged with its child.)

What's the cost of a lookup in a radix tree? It sounds like it must be O(logn) because you need a tree of that depth to store n things.

But you only need to touch each bit (or character, in a k-ary tree where k is the size of the alphabet) at most once during a lookup to decide which descendant of a node to traverse. Isn't this the same as determining the hash of a string? To compute it correctly we must involve every bit of the key. (If traversing the tree is cheap enough, then crit-bit trees are faster than hash tables. Furthermore, unlike a hashing operation, only certain bits, the aptly-named critical bits, need be examined in a crit-bit tree.)

Thus the lookup cost of a radix tree must also be O(1). Therein lies a problem. Why is it that a binary tree of the same size has an O(logn) lookup time? We travel along the same number of nodes!

The answer is that usually when computer scientists analyze these data structures, as an approximation, we view computing the hash function as a constant-time operation, and similarly for a comparison in the binary tree. But to refer to n different objects, the keys must have length at least O(logn), which means it actually takes O(logn) time to hash a key, or to perform a key comparison.

So what we've been saying is that it's okay to ignore a factor of logn. This is sloppy and inconsistent. Why can't we ignore the logn steps required to walk down a binary tree as well? Why can we turn a blind eye to one logn yet scrutinize the other?

We should say that hash lookups and crit-bit tree lookups cost O(logn) (or more accurately, O(m) where m is the size of the keys, which must be at least logn), and that binary tree lookups cost O((logn)²).

This inaccuracy caused me to initially overlook that crit-bit trees could match or even outperform hash tables. It's possible that others have suffered from the same affliction: despite being described (twice, independently) in 1968, the courses and textbooks from my time do not mention radix trees at all, and I suspect the teachers and authors responsible may also not have realized how fast these data structures can be.

This is a shame because they have other advantages over hash tables too: crit-bit trees are deterministic with good worst-case times, grow and shrink as needed (they never require an expensive rehashing nor let vast tracts of an array lie fallow), and support successor and predecessor operations.

The good news is that they seem to be gaining prominence. I feel they are mentioned more on the web (and I'm helping this as well!). I've heard evidence that some CS undergraduates these days are at least aware of their existence. The fact that even I know about them now means they can't be that obscure.

Prisoner Problems

2007-03-29T01:41:00.001-07:00

Quite a few well-known logic puzzles involve a prison setting, giving them a darker tone that makes them memorable and more fun to think about.

This joke prisoner problem is amusing but impossible, as its rather surreal solution involves English homonyms.

I also won't bother describing the famous prisoner's dilemma from game theory.

Then there's the paradox about the prisoner who's told he'll be executed some time next week and that it will be a surprise. So he reasons thus: "They can't kill me on Friday, because I would know by Thursday night and it would not be a surprise."

"But this implies if they haven't killed me by Wednesday night, then I know I'm dead on Thursday because I can't be killed on Friday. Which means it wouldn't be a surprise. Hence I cannot be executed on Thursday."

"Repeating this argument a few times shows that I cannot be executed on any day next week!" he concludes triumphantly.

But on Tuesday morning he is executed, much to his surprise! What's going on?

And there's the tale about the prisoner who is to choose his method of execution: if the last statement he utters is true then he is executed in some gruesome fashion, and on the other hand, if it is false then he is executed in some different but equally gruesome fashion. (The particular methods of execution change from telling to telling. I just can't think of any right now.) What should he say?

A tougher puzzle involves one-hundred prisoners in a prison that contains one-hundred cells and a single room with a single light bulb that can be turned on or off. Every day a prisoner is chosen at random and placed in the room. At any time, any prisoner can ask for freedom. When he asks, if every prisoner has spent at least one day in the room with the light bulb then everybody is set free. (The warden has been keeping track.) Otherwise everybody is executed.

The prisoners can talk amongst themselves before entering this bizarre jail, but once inside they are kept isolated, and the light bulb becomes their only means of communication. How can they free themselves?

Lastly, there is a similar problem that is the main reason for this post. A friend told me this puzzle a few months ago and I don't want to forget it.

Again, there are one-hundred prisoners and a special room, but this time the room contains one-hundred identical boxes, each containing exactly one slip of paper bearing a prisoner's name. Every prisoner's name is present, but no one knows which box contains which name.

The prisoners are taken to the room one at a time. Once inside they are allowed to open and examine the contents of up to fifty boxes. They must then leave the room as they found it, so the boxes they chose are closed when they are done.

After all prisoners have visited the room, if each prisoner has seen his name on a slip of paper then they are all free to go. Otherwise they are all executed.

As before, they can all examine the room and boxes (but not open them) and devise a strategy together beforehand, but no communication is permitted once the process begins.

Clearly if a prisoner picks fifty boxes at random he has only a 50% chance of finding his own name, and if every prisoner does this then the chance that all of them find their names is 1/2^100. That is, they will almost certainly be executed.

How can they obtain at least a 30% chance of surviving?

Shiny Colourful Buttons

2007-03-07T01:23:00.001-08:00

Here's a trick I've seen mentioned in other geeky blogs that deserves to be more well-known and widespread: only have page icons (favicons) on the Firefox bookmarks toolbar. Simply delete the names in bookmark properties. Or try the Smart Bookmarks Bar extension. Note separators can be inserted to help organize the icons.

Not only is it stylish, but it frees up precious toolbar real estate for more bookmarks. Also I find myself drawn to the pretty little pictures. I visit those enticing links more often nowadays.

One might worry about forgetting which icon does what, but presumably the links on one's toolbar are frequently used, making this unlikely. Anyway, to find out where they go, just click on them! (i.e. the standard action following the thought: "I wonder what this button does...")

The sole drawback is that some webpages don't have icons, or have one that looks identical to another, or looks horrible. To solve this, use the Favicon Picker 2 extension to assign a good icon to that bookmark.

A related idea is to hide text on certain tabs, which can be achieved using the FaviconizeTab extension.

By the way, googling for "favicon picker" finds many of the aforementioned blog posts [1, 2, 3, 4, 5], some containing great screenshots. Not everyone is enthralled by the idea however, and some even want the opposite.

A New Beginning

2007-02-21T17:38:00.001-08:00

This is the last post that will appear on my office server at Stanford. It will be disconnected soon, after many years of faithful service.

This is also the first new post at this blog's new home at Blogger. It's good to have everything automated: timestamps, formatting, archives, permalinks, labels, etc. but part of me misses writing my own scripts to do all this, and the total control I had over everything.

Converting my old blog entries was much easier than I had anticipated, though it was not entirely smooth. For example, I have to keep source code on a separate server because this site only lets you put up HTML and images. Also, I never kept the time the old entries were posted, only the date, so I had to fabricate them.

In retrospect, I realize I've taken a rather roundabout route to blogging. I would never have gone out of my way to sign up on some website to start writing articles, out of the blue. Instead, a peripheral page on my website intended to help me keep track of changes gradually mutated into this.

I plan to relocating other parts of my site. The PBC Library already lives on a more permanent server. I recently moved xmmspipe to Google Code. This service seems quite nice but I dislike the fact that they only support Subversion: I am now an ardent git fan.

Chase the Pig

2007-02-14T01:00:00.001-08:00

I was surprised to find that Wikipedia currently lacks an entry for the card game 拱豬 (Gong Zhu). This four-player trick-taking Hearts-like game is often played by my relatives on my mother's side, and I assume it's relatively well-known amongst the Chinese.

John McLeod maintains a page describing various rulesets for Gong Zhu (in particular the variants involving exposing cards sound highly intriguing to me), but none of them exactly match the one I was taught. For posterity I'll record my family's rules here.

For the first deal, the player with the seven of spades leads the first trick. The lead can be any card, not necessarily the seven of spades. In subsequent deals, the player that took the Queen of Spades in the previous deal leads the first trick. This player is sometimes nicknamed "The Pig". As in Hearts, there are no trumps, and the winner of the trick leads the next trick.

Why the seven of spades and not the two? Because another card game popular amongst my aunts and uncles involved building sequences starting with seven, and the first card played in that game had to be a seven. They adopted this rule for consistency.

My family always played a predetermined number of hands (e.g. 4) and the winner was the player(s) with the highest total score, but the more standard convention seems to be that one keeps playing until someone has a total score of -1000 or lower, and then the player(s) with the highest score is the winner. (I'm guessing they did this because when playing for stakes, payoffs occur more frequently with this scheme.)

The values of the cards are as follows:

Jack of Diamonds, or goat (羊): +100
Queen of Spades, or pig (豬): -200
Ten of Clubs: doubles your score, unless you have won no other cards in which case it is worth +50
Hearts: two to ten are worth minus their pip value, except for four which is worth -10. The Jack is -20, Queen -30, King -40 and Ace -50. The other cards are worth nothing.

I was taught a couple of mnemonics for the Four of Hearts being -10. Firstly, 4 is an unlucky number amongst the Chinese (I was told this is because the word for 4 sounds similar to the verb "to die" in Mandarin, and also in other variants of Chinese), so that's why its penalty value is worse than it should be.

Secondly, the word for 4 and the word for 10 in Mandarin sound similar. If you know a Mandarin speaker, get them to say "44 is 44" to hear for yourself!

If a player wins all the hearts, then the values of the hearts are reversed in sign, that is, they are positive instead of negative, and it can be checked that they are worth 200 points in total. Furthermore, if that same player also wins the pig, the pig is now worth +200 points.

If you win every card with a value, then you receive 100 points for the goat, 200 for the sheep, 200 for all the hearts, and finally your score gets doubled by the Ten of Clubs, giving a total of 1000 points. This is is the best possible score. The worst possible score is -796, when all but the Jack of Diamonds and Two of Hearts is taken.

Naturally, the name of the game refers to the practice of leading low spades in an attempt to flush out the pig: eventually the holder of the Queen of Spades may be forced to play it and take the trick.

Comparison with Hearts

I prefer this game to Hearts. There is something special about every suit in this game, whereas in Hearts, the clubs and diamonds tricks feel like filler. Winning the Jack of Diamonds is always good, and winning the Ten of Clubs sometimes helps, so even if you're not going for all the hearts there is something to do.

I never liked the Hearts rule preventing players from "breaking into" hearts, and I'm glad that Gong Zhu is free from this restriction.

Scoring is more complicated as each heart has a different penalty value. However I found after several hands I enjoyed the less trivial mental arithmetic, even missing it when playing Hearts.

Generally, I feel the game experience is richer because there are more important cards than Hearts, yet the additional complexity is not overly random nor overwhelming. In contrast, while playing Hearts if I'm not trying to shoot the moon, my play feels almost forced, as my only goal is to avoid the Queen of Spades and as many hearts a possible. Sometimes I can chose who to penalize more by playing in a certain way, but this aspect of the game is limited and not very rewarding.

Even when shooting the moon, the strategy is often clear, a drawback that I feel is exacerbated by the prohibition on breaking into penalty cards.

I'm ambivalent about the Hearts convention of passing three cards before the game starts. Sometimes it's extremely helpful since some people I've played with are rather predictable, allowing me to mold hands which I can easily shoot the moon with. On the other hand, this does reduce the challenge, and in general getting extra information about opponent's hands detracts from the game experience.

The internal conflicts are more intense and exciting. I can feel my greed fight my fear. Do I save high cards to win the goat? What if this causes me to wind up with the pig and/or a bunch of high hearts as well? Do I go for the double? It's 50 points on its own, but how sure am I that I won't pick up any hearts later on?

Other Fun Card Games

I recall being enthralled when introduced to playing cards as a child. Nothing but fifty-two bits of pasteboard, yet the possibilities are legion. Games of pure skill. Games of pure chance. Games that fell in between, and it seemed that a game existed for any given skill/luck ratio. And they can be played almost anywhere, with any number of people, even alone. Such power, and I could hold it in one hand. Merely shuffling and performing sleights at once soothed and inspired me. To this day I often carry a pack of cards on my person.

One of my well-loved books from my childhood was "The Book of Games" by Richard Sharp and John Piggott (ISBN 0883653893). I read it cover to cover countless times, though not necessarily in order, marvelling at the illustrations and fascinated by the history. I tried out many of the games within, goading whoever was around me to learn their obscure rules so I could play.

(I took offence to one sentence however: in the entry on Mah Jong it describes the Chinese as "devious". I don't think they're inherently better at games than other races!)

If only the internet and Wikipedia existed back then! I was frustrated by rules they omitted, not to mention the games they left out. Sometimes the descriptions were too concise due to space limitations. Today the rules of just about any game with some following are at one's fingertips, and one can sometimes even find free programs for an instant opponent, instructor and umpire. Unfortunately, this came after my heaviest gaming days (at least, games that don't involve computers!), so the games below are mostly from the above book.

Though I'll mention card games of many species, some bias will be noticeable since I'm fond of lightweight teamless trick-taking games. Player ability varies wildly in some circles, making partner selection problematic in games such as bridge and canasta.

If there are four players, I almost always enjoy playing Hearts and Chase the Pig. Big Two is another favourite.

When there are three players, Knaves is a good choice if I'm in the mood for something like Hearts. It is also a no-trump trick-taking game with penalty cards, but also gives one an incentive to win as many tricks as possible. Sergeant Major is an entertaining diversion for three, especially for those newer to trick-taking games. My friends and family found David Parlett's Ninety-nine refreshingly unique and challenging. (We played the original rules, as described in The Book of Games.)

I never found two-player card games appealing, though I feel like I could if I dedicated more time to them. In particular, I feel like I should like Cribbage, Bezique and Piquet. I've tried some novel two-player games described in "The Pan Book of Card Games" by Hubert Philips, but never grew attached to them.

For five players or above, I'd play poker, or in a less serious crowd, Bartog.

Also, Napoleon is a five-player trick-taking game whose gimmick is the existence of a secret partnership: the identity of highest bidder, Napoleon, is known, but his secretary is determined by the holder of a particular card that is not revealed until played during a trick. Thus it is a two-versus-three game where initially no one knows the composition of the teams.

I had forgotten the details of this game. But thanks to Google, I rediscovered this old friend, and learned a lot more. Apparently, my parents left out at least half the rules when they taught it to me. Also, it seems Napoleon is a popular Japanese card game.

As for patience/solitaire for one, I'd recommend downloading a program like PySol and exploring.

Inkscape and Valgrind

2006-11-25T01:00:00.001-08:00

I spend a lot more time at the PBC (Pairing-Based Cryptography) library site than I would like since I maintain those pages. I bet most webmasters have similar complaints.

I began to tire of seeing page after page of text, so I broke the monotony by adding a site logo. It serves no other purpose, but who knows? Maybe one day I'll be hawking coffee mugs and T-shirts emblazoned with this graphic!

I went through several ideas before selecting a shape, during which I gained respect for professional logo designers. Some famous logos seem so simple that I feel I could have designed them. But on further examination, they insiduously invade and reside in one's memory, are pleasing to the eye (or at least are not eyesores), and in fact satisfy many constraints.

After a few attempts I discovered that it is extremely diffcult to find symbols with the necessary properties, and in my case, to even judge how effective a given image is. Thus I settled on a design as soon as I sketched one that I could tolerate.

I recall the path I took. At one point I was experimenting with a stylized "P(B,C)". I removed the letters to get "(,)" and played around with the parentheses and comma until I arrived at the current logo.

As for the colour scheme, to pay homage to my current university, I let Stanford's design guidelines on colour dictate my choices. Thus the logo is predominantly cardinal, with sandstone and black playing secondary roles. On most desktops, many screen elements are white and hence all four Stanford "Identity Colors" appear.

The result reminds me of a symbol featured in the movie "The Incredibles". I hope this causes people to think the PBC library is incredible, at least subconsciously!

I used Inkscape to realize my idea. I had never tried Inkscape before. I was surprised at how easy it was for a newbie to use and how quickly I became comfortable and efficient with its interface.

(Strictly speaking, this is false. Many moons ago I fired up Inkscape's ancestor Sodipodi, but I was unable to do much without reading documentation. Either Sodipodi has since made great advances, or the fork was worth the trouble.)

While I'm on my soapbox lauding software, let me also praise Valgrind. I first heard of this program years ago. If only I had tried it years ago.

Finding memory leaks in my C projects had always been troublesome. Thanks to geek machismo [isn't this an oxymoron?], I chose the hard way, namely, to code wrappers around standard memory allocation functions that recorded statistics which I would then analyze to detect leaks.

Since my leak detection code would need to be bug-free itself for this to work, I would restrict myself to primitive designs to simplify implementation details, ultimately leaving much of the sleuthing to the developer. Furthermore, toggling leak detection was so annoying I rarely checked for leaks.

As I recently discovered, Valgrind magically gives detailed reports on where the leak is and what is being leaked [insert HP joke here]. And to use Valgrind one only needs to invoke gcc with different options during compilation.

Valgrind has other features too, but I haven't tried them yet.

Pi Music

2006-10-29T01:00:00.001-07:00

I must have spent most of my life facing one keyboard or another. Over a year ago, while facing a musical kind, I was in a weird whimsical mood and I wrote a tune based on the digits of pi.

It did not surprise me when I discovered I was on a well-beaten path, as a search on Google quickly reveals. After all, many pi-inspired feats have been accomplished, such as setting Edgar Allen Poe's poem "The Raven" to the digits of pi. See also the honourable mention in this ray-tracing competition.

The pi music I found was quite abstract, whereas I want mine to sound more standard. I chose to have the digits 1-7 represent the tones of the C minor scale, altered if necessary, while 8 and 9 wrap around, that is, I encoded 8 and 1 the same way, as well as 9 and 2. Accordingly, I would have treated a 0 as a 7 but the tune ends just before reaching the first 0. (Thus 31 decimal places are encoded, this number fortunately corresponding with the first two digits of pi.)

This is akin to jianpu, a numbered musical notation system which I see in many Chinese books, but have never encountered in the Western world though supposedly it has seem some use in Europe. My scheme differs in that with jianpu, one would normally notate a minor key starting from 6, not 1.

It's a shame jianpu is not more widespread. It is well-suited for quickly and concisely jotting down simple melodies. A blank piece of paper suffices: there is no need to rule a music staff first. Writing numbers and dashes can be done extremely fast and most people are accustomed to this, unlike drawing geometric figures. More sloppiness is tolerated, as it is easier to identify scrawled digits and dashes than it is to figure out which line or space a hastily-scribbled note lies on, or whether a certain dot belongs to a note or was just a slip of then pen. Jianpu is also easy to learn due to its logic and simplicity. (Of course, jianpu performs terribly for even a slightly complex piece.)

(To be precise, jianpu-like notation is in fact employed in Western music. For example, when one writes "C6" to denote a chord, the "6" refers to the sixth note of the major scale.)

I added extra notes in order to produce a repeated motif typical of tunes. Following the digits exactly produces a melody that sounds a little too random for my tastes.

I chose conventional chord progressions. The A section uses a chromatically descending bassline, and the bridge mostly follows the cycle of fifths.

The time signature is 3/4, as this resembles 3.14 superficially. Also, in early (Western) musical notation, this time signature was represented with a circle.

I had intended to post it only once I had made some recordings (ideally after working on Bliss) but I have enough on my plate as it is. Maybe next Pi Day.

Anyway, it feels like an auspicious time to release it, as I happened to have recently released version 0.3.14 of the PBC library. And not too long ago Akira Haraguchi broke the world record after memorizing 100,000 digits of pi.

The lead sheets were created using Lilypond. The Lilypond website convincingly argues that their software automatically produces better sheet music than their major competitors, including commercial ones. It's also easy to integrate its output with HTML:

Incidently, around the same time I also penned a tune that loosely encodes a friend's name, but using a different method:

Pi: pi.pdf [pi.ps] [pi.ly]
For a friend: friend.pdf [friend.ps] [friend.ly]

CMake and Autotools

2006-09-27T01:00:00.001-07:00

I'm very grateful that somebody (Joe Cooley) contributed Autoconf and Automake files for the PBC library that I maintain. The GNU Autotools are almost essential because many people expect its presence and are used to compiling packages on Unix by typing ./configure followed by make. For the same reason, the Autotools give the project a more mature appearance. And they really do allow painless compilation on many systems.

But there is a dark side to using the GNU build system. The PBC source packages increased by several hundred kilobytes. I notice this extra weight because I often use wireless networks. Additionally, build times are at least twice as slow. On one run, it took 37 seconds to compile PBC, compared to 13 seconds with the original handwritten Makefile. And that's not counting the 13 seconds for ./configure and the 4 seconds for ./setup.

Furthermore, one has to be fluent in m4 and various configuration file formats, and understand how the toolchain works to create and maintain the build system. I was never motivated enough to learn all this, and I haven't changed. Any modifications I make to the Autoconf and Automake files are based on what I see there already, or a brief Google search.

It seems some people were sufficiently dissatisfied with the Autotools that they offered a substantial sum to anyone who wrote a better build tool. The winning project was SCons, which I experimented with last time I needed a build tool with more features than make.

But now a different tool has caught my attention, ever since I read this article. The KDE project ran into trouble with the Autotools, and began searching for alternatives. Like me, they found SCons promising, but after further investigation decided to switch to CMake.

Porting KDE to different platforms is highly nontrivial, so I reasoned that if CMake worked for such a substantial project, odds are good that it would work for my tiny library. I'm following by example I guess, and it certainly isn't the first time. I use git because it works for managing the Linux kernel source, and I use C because it works for countless important parts of the system (including of course the kernel), and for many well-respected programmers across several generations.

While researching CMake I found more arguments for switching: autoconf/automake is insane, glowing reviews of CMake (in the comments section), another endorsement and an interview with a CMake author.

I had a CMakeLists.txt file up and running fairly quickly, as the syntax is quite simple. Running times are much better: CMake took a couple of seconds to generate a Makefile, which in turn only took a second longer than my handwritten one to compile PBC. I was also pleased by the clean and colourful output.

Unfortunately, CMake is not installed on many systems. And it must be relatively untested. How does it compare to the Autotools on less mainstream platforms? And what about the more obscure tasks that the Autotools excel at? For example, is it difficult to get CMake to cross-compile a project?

For now, I'll have to maintain two sets of build configuration files in parallel, but I hope one day CMake will be equally well-known and widespread so I can jettison the autoconf/automake baggage.

A Tale of Two Hacks

2006-09-21T01:00:00.001-07:00

Years ago I wrote rcenter which has long been superseded by the LIRC project. I finally switched to LIRC myself. I wonder if anyone out there is still using rcenter.

It took me a while to figure out that LIRC does not work with OSS drivers unless Stephen Beahm's midi poll patch has been applied. I decided to switch to the ALSA drivers to avoid this issue. But then I had to set some other module options: snd-emu10k1 enable_ir=1 extin="0x3fc3" extout="0x1fff".

I wrote xmmspipe almost simultaneously, and in contrast, this project isn't obsolete yet. In fact, I recently discovered it has been an official Gentoo Linux package for some time when I received a bugfix for it.

It's times like these when I feel warm and fuzzy. I get to experience first-hand some of the touted benefits of free software. Having the source open means thankfully someone else can solve the problem. Even if I managed to fix the bug myself, I probably would've spent hours doing so.

On the other hand, I wouldn't mind if xmmspipe were obsolete and named pipes came with XMMS by default. I'm reminded of a quote from Doug McIlroy:

This is the Unix philosophy. Write programs that do one thing and do it well. Write programs to work together. Write programs to handle text streams, because that is a universal interface.

and one from Rob Pike:

There has been much talk about component architectures, but only one true success: Unix pipes.

Mental Feats

2006-09-14T01:00:00.001-07:00

Michael Curtis (who commented on a previous posting) has written several articles on mental feats involving memory and mathematics.

Coincidently, I too read about the Trachtenberg system (a method for performing mental arithmetic) many years ago.

Reading his site reminded me of a time when I'd relieve boredom during occasions such as high school assemblies by squaring 2-digit numbers in my head using the techniques I had read about.

Today, I'd still use Trachtenberg's method for numbers ending in 5, based on the equation (10 a + 5)^2 = 100 a (a+1) + 25. However I have since found faster methods for other numbers, which I haven't seen described on the web. They only require additions and subtractions, but one has more to memorize.

Let n be the 2-digit number to be squared. Then if n lies in the range:

0-25: Memorize these answers.
25-50: Work out how far n is from 50 and how far n is from 25. Then the answer is 100(n - 25) + (50 - n)^2.
50-75: Compute 100((n-50) + 25) + (n-50)^2. (This is also Trachtenberg's method for squaring fifty-somethings.)
75-100: Compute 100(100 - 2(100-n)) + (100-n)^2

While I'm at it, I'll record a method for finding square roots (of squares of 2-digit numbers):

Remove the last two digits of the square. Then the first digit of the answer is the largest digit whose square is less than this number.
The last digit of the square tells us what the last digit of the answer could be. If it is 0 or 5, then so is the last digit of the answer and we are done, otherwise:
Let the first digit of the answer is a. Compare the square with the square of 10a+5. If larger, then the last digit of the answer is between 6 and 9, and if smaller, it is between 1 and 4. Luckily, in base 10, the squares of 1 to 4 have distinct last digits. Also the squares of a and (10-a) end in the same digit, so it is now easy to determine the last digit of the answer.

The corresponding algorithm for cube roots is much simpler, because the cube of each digit has a distinct last digit (and similarly with other odd powers).

Slideshows in Firefox

2006-08-18T01:00:00.001-07:00

Like many geeks, I frequently use text-based interfaces where normal people use GUIs, with a sense of smug self-satisfaction. Instead of a WYSIAYG word processor I use typesetting software like LaTeX. No fancy website creators for me, I use gvim to edit HTML files. Spreadsheets? I keep data in flat text files and write scripts to process them.

How about presentations? I had used MagicPoint for a few, but I wasn't completely satisfied. For instance, equations were fiddly: I had to write a script that would run TeX to render the equations to encapsulated PostScript and embed the resulting image in the slideshow. I briefly thought about writing my own program. Very briefly. Then I thought about exploiting existing programs instead.

I had come across PinPoint which uses GIMP to produce great-looking slides from a few lines. GIMP was designed to manipulate and display text and images, and is scriptable. But for live presentations, and for certain features I wanted, other programs or scripts would be needed, requiring a fair amount of work.

An idea hit me. MagicPoint can convert slides to HTML. How difficult would it be to modify things slightly so that presentations can be done in a web browser? After all, web browsers also manipulate and display text and images from a simple language. Not only that, they were designed to show different pages in succession. They are also ubiquitous.

One would just need to display pages in fullscreen, and perhaps using Javascript, have certain keypresses cause certain actions such as changing slides and triggering animations and other effects. Soon after experimenting with this, I discovered I was definitely not the first to think about web-based presentations.

The Opera browser has long had a slide show feature (the Opera Show Format), but unfortunately it is not supported by other browsers. I want it to work on Firefox.

Luckily, an alternative, the S5 project, has surfaced, which creates slideshows from a few lines of XHTML, and should work on any standards-compliant browser.

S5 was just what I was looking for. Webpages can contain images, text, visual effects, animations, and so on, and in theory S5 presentations should be able to as well.

MathML in S5

I want to display equations via MathML, but at present one cannot simply embed MathML (or SVG) and change the MIME type of S5 slides accordingly, though a fix exists and will be released.

As a workaround, I use ASCIIMathML. Perhaps this is a good thing. I had intended to put LaTeX style equations in the middle of the HTML and use itex2mml to convert it to MathML, but since ASCIIMathML converts to MathML on-the-fly using JavaScript, I can skip the compilation step. (Other tools to convert human-friendly text to MathML are blahtex, TexToMathML, and TtM.)

There's still the matter of getting the equations to display on Firefox. Until the STIX Fonts are ready, extra mathematical fonts have to be manually installed.

Also, for months now, MathML does not display correctly on certain Linux systems, though a workaround exists [also described here]. And for some reason, S5 is extremely slow on my Debian system, but runs fine on the Windows build of Firefox.

Mnemonic Major Systems

2006-07-17T01:00:00.001-07:00

I discovered two things when I tried using the net to brush up on mnemonic major systems (aka phonetic number systems). (If you have no idea what they are read the article before continuing!) Firstly, the only encoding from digits to sounds I've seen online so far is the one published by Harry Lorayne. Secondly, it turned out I didn't need any brushing up at all. The mapping I learnt many years ago was so easy to remember that, not only can I still recall it, but the memory is so strong I cannot use Lorayne's system without confusion.

I came across the major system I use in a book by Jean Hugard. I argue that it is more natural and easier to learn. There were only a few rules to remember:

1,2,3 correspond to the consonants l,m,n respectively. This is easy to remember since the letters require 1,2, and 3 strokes to write. If you happen to know the British sign language alphabet, observe that you place 1, 2 or 3 fingers on the other hand's palm when signing l, n and m respectively.

Some mappings are based on the way you pronounce digits in English. 4 is r (think “fourrr”), 5 is f or v (think “five”). 0 is s or z (think “zero”).

Then there are the digits that look like letters. 6 is b or p, 7 is t, th or d. 9 is k or g. With sufficiently bad handwriting (or fonts), 6 and b are indistinguishable, as are 9 and g (or q, which in English is always pronounced starting with a k or g sound, and always as a k sound in several European languages). 7 and T are also similar.

The only rule I never liked much was the one for 8 (which is not a problem since being the odd one out makes it easy to remember!): “Eight” sounds like “aitch”, which hopefully helps you remember that the sh, ch (and j) sounds correspond to 8.

Digit	Consonant(s)	Reason
1	l	strokes
2	n	strokes
3	m	strokes
4	r	sound
5	f, v	sound
6	b, p	shape
7	d, t, th	shape
8	ch, j, sh	special
9	k, g, q	shape
0	s, z	sound

I also mostly prefer the mapping from playing cards to words as presented by Hugard. Although I dislike the aces been treated specially and agree with Lorayne assigning the names of the suits to the jacks, I believe thinking KH as a groom and QH as a bride for example is easier to learn.

However, there is at least one practical benefit to Lorayne's system. By Benford's law, it is more likely that a number one wishes to memorize begins with a 1, and it is easier to think of a word starting with d, t or th than to think of one starting with l.

Firefox and Manpages

2006-05-26T01:00:00.001-07:00

I prefer to read manpages in a web browser rather than in a terminal or a text editor. Konqueror formats manpages very nicely [screenshots here], but I use Firefox, and do not use KDE.

I wish there were a Firefox extension to handle manpages in a similar way to Konqueror. Instead, I use man2html. I setup a Smart Keyword so that typing man firefox for example retrieves the manpage for Firefox.

Unfortunately I feel its output is not as pleasing as Konqueror's. As a stopgap measure, I use the Greasemonkey Firefox extension to add some CSS to make the pages more to my liking.

script.js: Greasemonkey script that activates every time man2html is invoked on localhost. Adds a CSS file to the page.
man2html.css: CSS file that changes the look of the manpages.

Web Syndication and Atom Feeds

2006-04-11T01:00:00.001-07:00

Due to popular demand ;-) I added a web feed for my blog. [Much to my surprise I discovered today that there is at least one occasional reader of this blog besides me. Thanks for your kind words.]

I experimented with web feeds when I first heard about the Live Bookmarks feature of Firefox. It wasn't so long ago, and the process was straightforward: I created a few RSS 0.91 files, and filled them with bookmarks, each entry using a title, description and link tag.

Now I find that RSS has forked into two different formats, confusingly named “RSS 1.0” and “RSS 2.0”. (In fact, there are more versions of RSS.) A third contender, Atom has surfaced.

It seems Atom 1.0 is the most fashionable choice, so I wrote a script to generate an Atom feed for this blog.

Atom is more complicated than RSS 0.91. Dates must be included and have to be in RFC 3339 format. Unfortunately the date command in Debian stable is too old to support the --rfc-3339 switch, so instead I used

date +%Y-%m-%dT%H:%M:%S%z $* | sed 's/..$/:&/'

Some sort of ID is also required, and I'm not sure exactly what the purpose of this is. The specifications refer to some Internationalized Resource Identifier as defined by RFC 3987 but that's one standard too many for now. At the moment I use the relevant URL as the ID.

Ideally the mime-type of an Atom file should be served as “application/atom+xml”, which in Apache can be accomplished by adding

AddType application/atom+xml .atom

in a configuration file.

In a HTML file, one should add something like:

<link rel="alternate" type="application/atom+xml" title="Title" href="http://some.url/something.atom">

and perhaps also lines like:

<a href="http://some.url/something.atom"><img src="http://some.url/feed-icon-16x16.png" alt="Site Feed" height="16" width="16" /></a> <a href="http://some.url/something.atom">Site Feed</a>

where the feed icons can be downloaded from feedicons.com.

Git and Cogito

2006-04-10T01:00:00.001-07:00

Somehow, I have managed to avoid revision control systems until recently. I set it up for a typical reason: I wanted to be able to work on my thesis from different computers without worrying too much about keeping different copies in sync. Also, it's nice to be able to keep track of my progress. I don't expect to ever revert to an older version, but seeing a detailed log of changes makes me feel I've accomplished something.

Perhaps it's a good thing I put off learning about version control for so long. Back when I first thought about using it, CVS was the most popular open-source choice, Subversion was immature, and Linus Torvalds didn't use any system for the Linux kernel.

Now a new generation of source control tools has materialized, and are being improved rapidly. Development of the Linux kernel has benefitted ever since Linus started used revision control systems years ago.

So it seems it is a better time than ever to delve into version control. The old systems were plagued with various flaws and annoyances. The latest systems resolve these issues, but I wouldn't know. I never used the older systems so I have no idea what the problems were.

Things have gone smoothly for me with Cogito (basically some shell scripts based around Linus Torvalds' git tool). Even though it's designed to be a distributed source code management tool, it works well for one person editing a few files.

The only problem is that I can't easily host the repository on my Debian-stable server since git is too new, though Debian backports exist. I could just use rsync, but this method is deprecated and highly discouraged. [Also explained in this git tutorial; search for “rsync”.]

Mathematical Go

2006-03-27T01:00:00.001-08:00

I was taught to play go as a child, but it wasn't until a few years ago that I learned how complex the rules are, at least the ones used in tournaments. I had previously thought the rules were elegant and simple.

Actually, mathematicians have devised elegant and simple rules of go. Unfortunately the mathematical rules are rarely used. Instead, there are several popular rule sets with different properties.

Luckily in most games the complicated cases never arise, but it is irritating to know that in general, the outcome of the game can depend on the legality of suicide, and in many cases it is unclear whether a group is live or dead if the mathematical rules are not followed.

Evidently when the game was first invented, nobody thought about the messy corner cases. It seems as each one was discovered, an ad hoc solution was proposed, and over time these cumulative patches to the basic rules eroded the austere grace of the game.

As one might expect, starting afresh and approaching the game from a mathematician's point of view not only restores clarity and precision, but also yields unexpected results. For example, Berlekamp and Wolfe describe bizarre positions where highly nonintuitive moves are required to win. Even though such situations never occur in real play, studying them hints at the richness and depth of this ancient game.

Unsurprisingly, it was a mathematician who first drew my attention to the flaws in traditional go rule sets!

I am not sure why the mathematical rules have not caught on. Are they too difficult to implement in a tournament? Is the grip of tradition is too strong? Or is it simply that most in the go world are unfamiliar with these recent developments?

Blog Basics: Permalinks

2006-03-26T01:00:00.001-08:00

I wrote some scripts to add permalinks, which a typical blog should have. I can understand why many people use dedicated blogging software, but I'm content to reinvent this wheel, as I'm comfortable with, and even enjoy, writing shell scripts. I also have more control this way.

I have one directory for every date I've posted. Inside there is one file per blog entry, containing an HTML snippet with the title in a h2 tag, and the date within a h3 tag. One script converts this to a page to be permalinked, while another pastes the entry into the main blog HTML files.

Inspired by the official Google blog, the permalink's filename is the title converted to lowercase with spaces converted to dashes, and all other characters removed.

I should eventually look into how the popular blogging software organizes things, but this scheme appears to work well.

Geometry Algorithms

2006-03-14T01:00:00.001-08:00

Happy Pi Day!

Once in a while I visit ACM Programming Contest Problem Set Archive. Reading and trying out a problem or two reminds me of a time when I was eligible to compete. But mainly it makes me realize how little I knew back then, and how much I still can learn. For example, as mentioned in a previous post, I only came across the Dancing Links algorithm recently which comes in handy for several contest problems.

Many problems require simple geometry algorithms. Back in the day I thought I could derive what I needed on the fly for these sorts of problems. I still believe inventing algorithms is a good thing to do, but at some point one should learn what has been done before, as it is easy to miss clever and elegant optimizations.

For example, consider the simple problem of determining which side of a line a given point lies, where the line is defined by two given points. In the past, I would have naively computed the equation for the line and substituted the point in to see which side it lies on, but now I know that it is much easier to calculate the signed area.

Calculus Using Infinitesimals

2006-02-17T01:00:00.001-08:00

I only recently became aware that it is possible to formalize the methods that Newton and Leibniz first used when developing calculus. In fact, not only is it possible, but it is quite easy to understand, and the notation is more elegant than those of limits.

I had always looked down on the pseudo-proofs I was shown in physics lectures, handwavy sloppy arguments that defied the rigour and precision that centuries of mathematics fought for. I tolerated them because I needed the results. But it seems with a few definitions, you can have your cake and eat it.

One introduction to this subject is a free online book: “Elementary Calculus: An Approach Using Infinitesimals” by H. Jerome Keisler.

Unicode on Debian GNU/Linux

2006-01-14T01:00:00.001-08:00

Unicode assigns each character a unique code [Wikipedia article]. My webserver now serves pages in UTF-8, and I have also switched my desktop to use Unicode.

There was no single compelling reason for this. Instead there were many minor advantages that together pushed me to adopt it. Small annoyances would arise. I wanted to add Chinese characters [Chinese characters dictionary] [English-Chinese dictionary] to some of my pages, and also Unicode curling quotes [ in HTML]. Some of the other characters look useful. Unicode is the rapidly becoming the dominant standard: even Windows uses it now. It is also far superior to the old way, i.e. dealing with a myriad of mutually incompatible character encodings. Every programmer ought to know about Unicode.

Migrating the server was easy. A minor tweak in a configuration file (AddDefaultCharset UTF-8 in srm.conf for Apache), and changing XML headers was all that was needed.

The desktop side was more involved. For an in-depth explanation, see a step by step guide to switching Debian to UTF-8 and a guide for Unix in general.

First I reconfigured the Debian locales package (i.e. dpkg-reconfigure locales) and selected en_AU.UTF-8.

Next I checked if the programs I frequently use can handle UTF-8. Unfortunately for me, Eterm does not support Unicode.

After a brief investigation I settled on rxvt-unicode (aka urxvt). I miss some of the Eterm eyecandy, and it took me a while to supply command-line options to get urxvt looking like Eterm. On the other hand, urxvt is leaner, especially when run in client-server mode.

One minor inconvenience is that "TERM=rxvt-unicode" is not entrenched as it should be. For example, the dircolors supplied in Debian does not know about it, so either a custom file has to be written, or dircolors has to be fooled.

Solving Sudoku

2005-12-28T01:00:00.001-08:00

I cobbled together two programs to solve Sudoku puzzles. One employs tricks that people use, while the other is an implementation of Knuth's Dancing Links algorithm as described at Wikipedia. It seems the first approach is sufficient for solving mainstream Sudokus, even without implementing all the tricks.

http://cs.stanford.edu/~blynn/sudoku.git

Type git clone http://cs.stanford.edu/~blynn/sudoku.git to fetch a copy.

Quinapalus

2005-12-12T01:00:00.001-08:00

Mark Owen aka Quinapalus is the author of the number crossword I HTMLized (Ajaxed?) recently. His site contains many other puzzles, some of them also crossnumbers:

HTML Preprocessing

2005-12-07T01:00:00.002-08:00

I replaced the PHP in wingchun.stanford.edu with static HTML. To avoid repeating code I used GPP, a generic
preprocessor.

I initially selected PHP for all my webpages because I had grandiose plans to build exciting dynamic sites. It never happened, but I kept the PHP in case I came up with some ideas. The development cycle is also one step shorter, and I don't get enough traffic for the performance hit to matter.

Disabling Links to the Current Page

2005-12-06T01:00:00.001-08:00

According to Jakob Nielsen's list of The Ten Most Violated Homepage Design Guidelines, a link should never point to the current page.

I've seen high-profile sites that break this rule so I'd expect most users not to get too confused. Nevertheless, I whipped up some javascript to do disable links to the current page for this site. Ideally I'd like the links to be removed in the raw HTML and not require Javascript, but the way I've built my site makes this difficult.

A brief search revealed that some people do this by changing the onclick callback, and also the mouse cursor, but I prefer to replace the whole anchor tag with a span tag of a particular class.

Ajax Puzzle, Firefox Extensions

2005-11-21T01:00:00.001-08:00

Everyone seems to be talking about Ajax these days. By chance I was recently forced to learn Javascript, so I threw together a page that may count as using Ajax.

My page is a number crossword I encountered years ago. It might be too simple to be considered Ajax, but it is similar to the puzzles at Number-Logic.com, which do use Ajax. Anyway, dropping the word "Ajax" should get me a few extra hits at least!

I only checked the page in Firefox. It may look weird in other browsers. Speaking of Firefox, I like this list: Best Firefox Extensions

And speaking of my favourite number puzzles, I'm fond of the "Alice bit the white rabbit" cryptarithm:


 A L I C E +
     B I T
     T H E
  W H I T E
R A B B I T

I haven't been able to track down the source of this gem.

I renamed this page from "Insert Blog Name Here" to the backronym BL:OG. The "Openly Geeky" phrase was supposed to be a play on the words "openly gay", but they have more in common than I first thought: declaring yourself as either one discourages the opposite sex from pursuing you!

Party Tricks

2005-11-02T01:00:00.001-08:00

This page is developing a life of its own. It's getting updated frequently with useless random information. I'm embracing the inevitable and intend to make it look like what it has become: a blog.

Geeky party tricks:

The Doomsday Algorithm[Wikipedia article]: calculate the day of the week for any date instantly.
Do Cube Roots of 9-digit Numbers in Your Head

Elements of Style

2005-11-01T03:00:00.001-08:00

I had heard of William Strunk's Elements of Style long ago. I finally saw what all the fuss is about when I found this online HTML version of the book [alternate link].

Much of this 1918 work is still relevant today. I was surprised to find that many misused and/or hackneyed words and phrases have been around for many years.

When I write English, I borrow techniques I use to write code. I start with a syntactically correct body of text that gets the job done. I then revise and optimize: I reword, rephrase, replace and remove lines, aiming for clean, concise, efficient and effective writing.

The analogy isn't perfect. With prose, I'll throw in extra words if I like the way it sounds, but for code, I'll sacrifice style for performance.

Some of the rules in Elements of Style seem to achieve the same goals, though they are explained from a nonprogrammer's viewpoint!

Drums, Engines, Sudoku, Poker Chips, Dodecahedrons

2005-11-01T02:00:00.001-08:00

Some links I don't want to forget:

Drumkit implemented in Flash
Animated Engines.
Sudoku at Number-Logic.com: I've lost a lot of time here recently. I only recently discovered these frustrating puzzles, but according to the Wikipedia entry on Sudoku, they've been around since 1979.
Poker chip tricks have also been eating up my time of late. Note there are different ways to do poker chips tricks.
12-sided calendar: print and construct your very own dodecahedral calendar.

Web Authoring Notes

2005-11-01T01:00:00.001-08:00

My notes on creating web sites are slipshod and haphazard. This would be fine since I wrote them for myself, but it's getting to a point where even I'm having trouble wading through the chaos to find information I want.

I've started reorganizing that part of my site. Some of the material
is more suitable for a blog than a reference.

HTML Notes

2005-10-20T01:00:00.001-07:00

I switched the main website from HTML 4.01 Transitional to Strict. I can't remember why I chose to use transitional in the first place. The only deprecated HTML I had was an align attribute in an image tag.

Students in the CS105 class I'm TAing have asked about indenting using straight HTML. This reminded me of a page describing hacks to indent using HTML. (I'd use CSS to do it, but we don't expect them to know CSS well.)

Rubik's Revenge

2005-10-15T01:00:00.001-07:00

I bought a Rubik's Revenge (a 4x4x4 Rubik's Cube) a long time ago. I did figure out a solution, but it's extremely slow. The 3x3x3 method I learnt when I was a kid is also fairly inefficient.

I was curious how people speed things up for both types of cubes. After browsing for a bit, I've decided the approach best for me is:

Reduce to 3x3x3 case as described by Chris Hardwick. Now standard Rubik's Cube algorithms can be used.

Solve the cross.

Solve the first two layers except for one corner piece. Originally I had planned to follow the "ZB" system, which has you solve the first two layers except for one corner piece and one adjacent edge piece, but this leads to numerous cases for step 2 of the system. For now, I'd rather sacrifice a few moves to get one more edge piece in place to cut down the number of cases for the next step.

Perform step 2 of the ZB system to put the last first-layer corner piece in place while at the same time orienting the last-layer edges. They are the last few cases on this page. (I don't think I could ever memorize the entire ZB system. I lose a few turns putting the last middle-layer edge in place, but I only have to learn a small fraction of the cases.)

Either orient the last layer ("OLL"), and then permute the last layer ("PLL"), or for more efficiency, achieve both goals simultaneously.

One of the above sites also points to a site with videos of people posessing an amazing amount of digital dexterity.

Virtual Hosting

2005-09-30T01:00:00.001-07:00

I finally added the following to Apache's srm.conf

NameVirtualHost * <VirtualHost *> ServerName wingchun.stanford.edu DocumentRoot /var/www/wingchun </VirtualHost> <VirtualHost *> ServerName rooster.stanford.edu DocumentRoot /var/www </VirtualHost>

so now rooster.stanford.edu and wingchun.stanford.edu look like different sites. However, for reasons I don't understand yet, in order to get SSL working on my whole site, I had to add an extra DocumentRoot directive to the VirtualHost _default_:443 section needed by mod_ssl.

I reinstalled the mod_dav Apache module, this time to play with some calendar and bookmark applications. I used to have it running a long time ago (see Netcraft's history of this site).

Recently I've been exploring a frequently-changing list of interesting bookmarks, containing (among other things) links to ephemerally popular pages like how to turn your hamster into a fighting machine.

Wasting Time

2005-04-17T01:00:00.002-07:00

Instead of wasting time on my homepage, I recently wasted some time fooling around with Firefox extensions. Up until now the only extension I used on a regular basis was All-in-One Gestures.

But now I've tried ForecastFox and Adblock (both are in the list of popular extensions, and I like what I see. I stumbled upon this list of ads to block which seems to be frequently updated and effective. I started using Flashblock in concert with Adblock.

To top it off I procrastinated further by visiting pointless sites.

The Obsession Fades

2005-04-12T01:00:00.002-07:00

At last I'm starting to come to my senses. For a while I was spending almost all of my free time on my site. I created a Wikipedia-like CSS for some of pages, tweaked other CSS files, added links from pages (from my old site that are no longer accessible, and also from my bookmarks), and reorganized a little.

More Redesign

2005-04-10T01:00:00.002-07:00

Less PHP, CSS code duplication throughout site. Changed the menu style. No more submenus, and now there are unclickable headings. Found a nice colour scheme generation tool.

I shrunk the validation buttons as I felt they were getting in the way. Forgot to handle the alpha channel the first time around. They now sit humbly in the bottom right hand corner.

I experimented with a pink/purple colour scheme with a horizontal menu for the Bliss pages. Most of my site is back up, though I got rid of some of the old content. The xmmspipe site is the only one left with the original look-and-feel (not counting the old Toshiba pages), though my mathematics notes still look the same as when I first started using CSS.

Major Homepage Renovation

2005-04-09T01:00:00.002-07:00

When I first wrote my homepage, I modeled my site on Debian's site which at the time used HTML tables for layout. I had never used CSS and I also felt that plain HTML would give maximum exposure.

A while later, I had to learn CSS when I wrote pages using MathML. The XHTML/CSS approach seemed cleaner and easier, and sometimes when I added new sections to my site I'd use XHTML and CSS. But I never converted the rest of my site out of laziness, and also I was worried that my site would look wrong in IE with its numerous CSS bugs.

I now feel the time is right to use CSS on my whole site [10 reasons why tables should not be used for layout]. I've spent a while trying to learn CSS properly. Additionally I've been reading about webpage design. Apparently, sans-serif fonts are preferred to serif fonts when on screen. The best widely available on-screen sans-serif font is Verdana while for serif fonts it's Georgia[1, 2].

Note I'm still sticking to HTML for now, as XHTML is not handled properly by IE or Google yet.

Now my default CSS file gives my site a kind of bluish Slashdot.org look. My only regret is that w3m will no longer be able to render my page layout (perhaps that's the only advantage of using tables for layout?), but then again, how often do I use text mode browsers?

My site is also long overdue for a general cleanup. So far I've been working on the presentation of my page but the content will also be reorganized.