Word Aligned

Fixing header file dependencies

tag@wordaligned.org (Thomas Guest) — 2008-07-02

DEPENDS

Without care C++ header files can deteriorate, so I was interested to find some sensible advice in the Google C++ Style Guide.

Names and Orders of Includes
Use standard order for readability and to avoid hidden dependencies: C library, C++ library, other libraries’ .h, your project’s .h.
…
The preferred ordering reduces hidden dependencies. We want every header file to be compilable on its own. The easiest way to achieve this is to make sure that every one of them is the first .h file #included in some .cc.

I agree, hidden dependencies are bad, and I’m not about to quibble with the “standard order” defined by the guide, even if I’m used to a slightly different ordering. Certainly headers should be compilable on their own; but I suggest the easiest way to achieve this is, well, to compile them on their own.

README

You don’t need a project file or even a makefile if you want to compile something. It’s easy to create a script which confirms a header has no hidden dependencies by including and compiling it^[1]. Create a file called check-header and paste in the following:

check-header

#!/bin/bash
cat <<EOF >tmp.cc && g++ $CPPFLAGS tmp.cc
#include "$1"
int main() { return 0; }
EOF

Make sure check-header is executable. Put it somewhere on your PATH. Export suitable CPPFLAGS for your codebase (here, I’m choosing to treat warnings as errors).

$ chmod a+x check-header
$ mv check-header ~/bin
$ export CPPFLAGS="-Wall -Werror"

Given a header file, check-header redirects a here document into a temporary source file. The source file contains a minimal C++ program which does nothing more than include the header. Check-header compiles that program. Compilation diagnostics, if any, appear on standard error. The exit status will be 0 if the header compiles cleanly, non-zero otherwise.

$ check-header standalone.h
$ echo $?
0
$ cat > depends_on_x.h
void f(X x);
$ check-header depends_on_x.h
depends_on_x.h:1: error: variable or field 'f' declared void
depends_on_x.h:1: error: 'X' was not declared in this scope
$ echo $?
1

INSTALL

It gets tiresome to run this command on one header at a time. Happily we can use it in a compound command to check all the headers in the current directory^[2]:

$ for header in *.h; do check-header $header; done

Or on all headers beneath the current directory:

$ find . -name "*.h" | xargs -L 1 check-header

(The -L 1 is required because check-header can only handle one file at a time.)

Make this part of your overnight build, and you’ve got an easy way to monitor dependencies in header files.

BUGS

The script shown here is about the simplest thing which could possibly work. Just a single compiler is used, the temporary file name is hard-wired, no clean-up is done, there’s a dependency on the shell environment, diagnostics are limited, there isn’t even any command-line help. A grubby header can sneak past this script by using preprocessor defines for conditional compilation, and different (versions of) compilers will disagree on what’s clean.

The truth is that I usually recreate this script and variants of it as and when required. My real intention is to demonstrate the rather obvious idea that we should use the compiler to detect compilation problems.

TODO

Once your headers include all they depend on, maybe you’d like to tackle the flip side of the problem, of determining which includes they don’t or shouldn’t depend on.

Can another tip from the Google Style Guide be automated?

Use forward declarations to minimize use of #include in .h files.

…

You can significantly minimize the number of header files you need to include in your own header files by using forward declarations. For example, if your header file uses the File class in ways that do not require access to the declaration of the File class, your header file can just forward declare class File; instead of having to #include "file/base/file.h".

I don’t think many of us would dispute this advice, though I’m not sure it belongs in a style guide — it’s just good C++ practice, the stuff you should be getting from a book. What I’d like is a refactoring tool which does it for me, something like Eclipse’s “organize imports”. A script might be able to do some of this, but it will have to be considerably more complex than check-header, and without access to the compiler internals it will be limited in power.

[1] While writing this article I discovered GCC allows you to precompile header files, reducing the need to create even a minimal script like check-header. Running gcc $CPPFLAGS header.h generates header.gch for a valid and self-contained header file, and compiler diagnostics otherwise. As the documentation says:

There are many other possibilities, limited only by your imagination, good sense, and the constraints of your build system.

[2] It would be better to tweak check-header to work on a list of input files.

Running Sums in Python

tag@wordaligned.org (Thomas Guest) — 2008-06-24

Suppose we want to generate the running sum series r formed by sums of n consecutive elements taken from a series s. For example, to sum consecutive pairs taken from the first 6 integers:

>>> n = 2
>>> s = 0, 1, 2, 3, 4, 5
>>> running_sum(s, 2)
[1, 3, 5, 7, 9]

One approach would be to combine the sum built-in function with list slices and comprehensions^[1].

>>> def running_sum(s, n):
... 	return [sum(s[lo:lo + n]) for lo in range(len(s) - n + 1)]
... 
>>> running_sum([0, 1, 2, 3, 4, 5], 2)
[1, 3, 5, 7, 9]

This is fine if:

s is finite
s supports slice access (i.e. s[lo:hi] doesn’t raise a TypeError)
n isn’t too big

With just a little extra thought we can address all these issues.

To deal with the first two points we return to the specification. What exactly do we require of s in order to generate r? Well, all that’s really needed is for s to be iterable — which is to say we can advance along it — then our running sum function can arrange to buffer n items from s and yield their sums. For maximum flexibility the result series r should also be iterable, allowing clients to choose how to consume it^[2].

In Python an object, o, becomes iterable by implementing the iterator protocol: o.__iter__() should return an iterator, i, over the container, which i.next() advances, raising a StopIteration exception when done.

>>> r = [1, 2, 3]
>>> i = r.__iter__()
>>> i.next()
1
>>> i.next()
2
>>> i.next()
3
>>> i.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Python programs typically don’t expose this protocol directly since we can build more convenient looping constructs on top of it. By using the yield statement our running sum filter needn’t implement the iterator protocol directly either. Here’s a generator function which uses itertools.islice in place of the original list slices.

Running sum for infinite series

import itertools

def running_sum(s, n):
    while True:
        r, s = itertools.tee(s)
        yield sum(itertools.islice(r, n))
        s.next()

As you can see, objects returned by this function implement the iterator protocol.

# Running sum of pairs from 0, 1, 2, 3, ...
>>> rs = running_sum(itertools.count(), 2)
>>> i = rs.__iter__()
>>> i.next()
1
>>> i.next()
3
>>> for s in rs: print s
... 
5
7
9
11
13
....
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyboardInterrupt

We have to kill the for loop by interrupting it since rs, being infinite (in this particular case), never raises a StopIteration. In fact, this particular version of running_sum() fails badly on finite inputs for reasons we’ll touch on later.

I won’t dwell on this flawed variant of running_sum(), except to note in passing that the built-in sum function doesn’t buffer n items from its input stream — it’s a lazy function which accumulates these items one at a time. There’s no magic here, though: behind the scenes, as the teed iterators r and s diverge, the in-between values must be stored somewhere!

Each slice of items from s overlaps the one before: if we visualise the sliced range sliding along the series, at each stage an element gets pushed in at the top and an element gets popped out from the bottom. Rather than repeatedly summing all the elements of these slices, we can calculate a single sum at the start of the series then adjust it as we progress^[3].

def running_sum(s, n):
    lo, hi = itertools.tee(s)
    rs = sum(itertools.islice(hi, n))
    while True:
        yield rs
        rs += hi.next() - lo.next()

Before we sign this function off, there’s a bug to fix. What if n is larger than the length of the input series? We’d expect the output series to be empty, but:

>>> list(running_sum([1, 2, 3], 4))
[6]

Oops! The problem here is in passing an itertools.islice series to sum(), which happily swallows the StopIteration exception without knowing if the sliced stream reached its end or if we reached the end of the slice, or indeed both.

>>> i = itertools.islice([1, 2, 3], 4)
>>> i.next(), i.next(), i.next()
(1, 2, 3)
>>> i.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

A fix is to pass sum a list comprehension. If n is too big a StopIteration exception gets raised before sum ever sees this list.

def running_sum(s, n):
    lo, hi = itertools.tee(s)
    rs = sum([hi.next() for _ in range(n)])
    while True:
        yield rs
        rs += hi.next() - lo.next()

As a final tweak, we can make lo and hi iterator.next functions rather than iterators, which saves a few attribute access calls.

def running_sum(s, n):
    '''Generate the series of running sums of n elements of s.
    
    >>> list(running_sum([1, 2, 3, 4], 2))
    [3, 5, 7]
    >>> rs = running_sum(itertools.count(), 3)
    >>> rs.next(), rs.next(), rs.next()
    (3, 6, 9)
    >>> list(running_sum([1, 2], 3))
    []
    '''
    lo, hi = [i.next for i in itertools.tee(s)]
    rs = sum([hi() for _ in range(n)])
    while True:
        yield rs
        rs += hi() - lo()

[1]: Thanks to doubtingthomas for pointing out an off-by-one error in the original version of this.

[2] In a recent post on his blog, Jake clears up some misconceptions about Haskell. In doing so he analyses the difference between lazy and strict types with clarity and insight. Recommended reading!

This parallel indicates pretty clearly that recursively operating on each element of a stream is an infinite loop. Stream is a control structure. It doesn’t exist to persist data across many parts of a program. It exists to feed data into a function one element at a time. In contrast, a Vector exists to persist an intermediate or final result of some 3-dimensional computation. In short, Stream is for controlling computation, and Vector is for storing data. This generalizes to lazy and strict types, respectively.

[3] There may be situations where we really want each running sum to be generated directly from n consecutive elements of the source stream: for example, if we are dealing with a series of floating point numbers, then addition is not exact and we must take care to avoid accumulated errors.

Eurovision 2008 charts

tag@wordaligned.org (Thomas Guest) — 2008-05-29

Last time I visited the Google chart API I discovered maps had been added. Since then I’ve been itching to use them. Eurovision 2008 got me scratching that itch.

As ever the API is a delight to use, if somewhat restricted. You’re limited to selecting a geographical area from a small set, but happily this set includes Europe. Chart data is supplied as a string of concatenated ISO 3166-1 alpha-2 country codes (e.g. “TV” for “Tuvalu”), and the chart value for each data point (i.e. country) maps to a colour gradient. Your palette is limited: water masses get a fill colour; a pair of colours provides the gradient used for countries in the chart data string; and omitted countries get a default colour.

To depict Eurovision results I chose suitably lurid colours. The results for Serbia, who hosted the event in 2008, are shown at the top of this page. Serbia appears in yellowy-orange, and the mauvey-bluey colours show who voted for Serbia — the darker the shade, the higher the vote^[1].

The Maps

Here are the maps in order of Eurovision 2008 scores. Hover your mouse over them to see the country and the score. If you’re wondering why you can’t see Israel, it’s because Israel isn’t in Europe.

The Script

Here’s the script I used to generate the pictures. It’s hacky, sub-optimal and packed with workarounds to get the job done. As Mark Dominus puts it:

Not everything we do is a brilliant, diamond-like jewel, polished to a luminous gloss with pages torn from one of Donald Knuth’s books.

I do think the code also shows how adept Python is at working with XML (XHTML in this case) and text processing, and why every programmer should know at least one scripting language.

As input it needs:

the Wikipedia Eurovision 2008 page
the official list of ISO-3166 alpha-2 codes

Eurovision charts

'''Generate Eurovision charts using Google chart API.

Method:
* get a mapping between country names and country codes
* find the final results table in the Wikipedia Eurovision page
* extract voting information from this table
* munge all this information into google chart URLs
'''
import string
import xml.dom

def internal_co_name(co_name):
    '''Convert a country name into a form used internally.
    
    We remove punctuation and convert to uppercase. This helps map
    between the official country names and the less standard ones used
    on the Wikipedia page.
    '''
    ascii = string.ascii_letters
    return ''.join(c.upper() for c in co_name if c in ascii)

def country_codes_dict(iso_3166_fp):
    '''Return a dict mapping country names to 3166-1-alpha-2 codes.
    
    We get these from the ISO website in a ISO-8859 encoded text file
    which contains a header followed by records of the form
    AFGHANISTAN;AF
    '''
    import re
    import codecs
    ccode_match = re.compile(r"^([^;]+);(\w\w)", re.UNICODE).match
    lines = codecs.iterdecode(iso_3166_fp, "iso-8859-1")
    co_codes = dict((internal_co_name(m.group(1)), m.group(2))
                    for m in map(ccode_match, lines) if m)
    # Add some shortened forms
    co_codes.update(dict(MACEDONIA="MK", BOSNIA="BA", RUSSIA="RU", MOLDOVA="MD"))
    # Hack! Serbia should be SR but, as at 2008-05-28, the google
    # chart api seems to want the country code for the former Serbian
    # and Montenegro.  This line can be removed once the chart api
    # matches its documentation.
    co_codes["SERBIA"] = "CS"
    return co_codes

def tree_walk(node):
    '''Recursively walk the nodes in a tree.'''
    yield node
    for node1 in node.childNodes:
        for node2 in tree_walk(node1):
            yield node2

def tree_find(root, pred):
    '''Return the first node for which the predicate holds, or None.''' 
    for node in tree_walk(root):
        if pred(node):
            return node

def next_sibling_find(node, pred):
    '''Return the first next-sibling node for which the predicate holds.'''
    while node.nextSibling:
        node = node.nextSibling
        if pred(node):
            return node

def children(node, name):
    '''Return (tag-)named child elements of a node.'''
    return node.getElementsByTagName(name)

def is_text(node):
    return node.nodeType == xml.dom.Node.TEXT_NODE

def is_element(node):
    return node.nodeType == xml.dom.Node.ELEMENT_NODE

def text(node):
    '''Return text from a node of the general form <td><b>12</b></td> or <td>0</td>'''
    while not is_text(node) and node.childNodes:
        node = node.childNodes[0]
    return node.data if is_text(node) else None

def country_votes(tr):
    '''Convert a row from the results table.
    
    Returns country name, score and votes for that country.
    '''
    td = children(tr, 'td')
    co_name, score = text(td[0]), int(text(td[1]))
    votes = [int(text(cell)) for cell in td[2:] if text(cell)]
    return co_name, score, votes

def results(wiki_table, co_code_dict):
    '''Extract the results from the Wikipedia results table.
    
    Returns the column headings country codes and a list of votes.
    '''
    import operator
    second = operator.itemgetter(1)
    trs = children(wiki_table, 'tr')
    ths = children(trs[1], 'th')[1:]
    # The title of each column header 'a' element looks like "ESCFranceJ.svg"
    # The [3:-5] slice converts this to "France", and we then look up
    # the 3166 alpha-2 code
    ICN = internal_co_name
    cols = [co_code_dict[ICN(children(th, 'a')[0].getAttribute('title')[3:-5])]
            for th in ths]
    votes = sorted((country_votes(tr) for tr in trs[2:]), 
                   key=second, reverse=True)
    return cols, votes

def results_table(wiki_page):
    '''Return the results table from the Wikipedia Eurovision results.
    
    By inspection, this is the first table after the "Final_2" node.
    '''
    import xml.dom.minidom
    def final_2(n):
        return is_element(n) and n.getAttribute('id') == 'Final_2'
    def htm_table(n):
        return is_element(n) and n.tagName == 'table'
    doc = xml.dom.minidom.parse(wiki_page)
    node = tree_find(children(doc, 'body')[0], final_2)
    return next_sibling_find(node.parentNode, htm_table)

def eurovision_vote_map(co_name, co_codes, scores, hi_score, missing):
    '''Return the URL of a map showing Eurovision votes for a country.
    '''
    # Use simple text encoding
    simple = string.uppercase + string.lowercase + string.digits
    simple_hi_ix = len(simple) - 1
    mapurl = (
        'http://chart.apis.google.com/chart?'
        'cht=t&chtm=europe&'  # Map of Europe
        'chld=%(countries)s&' # String of country codes
        'chd=s:%(values)s&'   # Values for these countries, simple encoding
        'chco=%(def_colour)s,%(lo_colour)s,%(hi_colour)s&'
        'chf=bg,s,%(sea_colour)s&'
        'chs=%(width)dx%(height)d')
    # Use a hack here to highlight the country being voted for.  Don't
    # include this country in the chart data, then it will get the
    # default colour. Assign all missing entries and zero scoring
    # entries the 'lo_colour'.
    omit = internal_co_name(co_name)
    values = ''.join(simple[simple_hi_ix * score // hi_score] for
                     score in scores) + 'A' * (len(missing)//2)
    countries = ''.join(c for c in co_codes if c != omit) + missing
    width, height = 250, 125 # The maximum map size is 440, 220
    def_colour, sea_colour = 'FFCC00', '00FFCC'
    lo_colour, hi_colour = 'FFFFFF', '000066'  
    return mapurl % locals()

def get_map_urls(wiki_results_fp, ccodes_fp):
    '''Return the URLs for Eurovision results charts, ordered by score.
    '''
    wiki_table = results_table(wiki_results_fp)
    co_codes = country_codes_dict(ccodes_fp)
    cols, votes = results(wiki_table, co_codes)
    # We only really need the countries which 1) weren't part of
    # Eurovision and 2) which appear in the Google chart of Europe, but
    # I don't have a definitive list of these. So just treat every
    # country in the world not in Eurovision as missing.
    missing = ''.join(set(co_codes.values()) - set(cols))
    hi_score = max(v for _, _, vv  in votes for v in vv)
    return "\n".join(eurovision_vote_map(co_name, cols, vv, hi_score, missing)
                    for co_name, score, vv in votes)

if __name__ == '__main__':
    # Download from: 
    # http://en.wikipedia.org/wiki/Eurovision_Song_Contest_2008
    # http://www.iso.org/iso/list-en1-semic-2.txt
    # (or use urllib.urlopen on these urls).
    print get_map_urls(open('Eurovision_Song_Contest_2008'),
                       open('list-en1-semic-2.txt'))

Serbia and Montenegro?

My program produced bizarre output at first: something was wrong with Serbia, and I assumed I’d made an off-by-one error. As I write this (2008-05-29) there seems to be a problem with the way the google chart API handles the country code for Serbia, “RS”. That’s why I’ve substituted “CS”, the old code for Serbia and Montenegro — a country which ceased to exist in 2006. I’ll have to adjust the code as the situation (both politically and googley) develops, since the maps which appear on this page are served live by google.

Terry Wogan

I’m not going to draw any conclusions from these charts except to say that I never thought I’d mention Wogan on this site, let alone link to the Telegraph. Eurovision voting is clearly a sensitive topic. I recommend a visit to this Andy Brice article, where he uses software similar to his wedding table planner to render some more detailed voting maps. The analogy of all these countries having to sit next to each other for a musical event, like grumpy inlaws at a wedding, made me laugh.

Andy Brice’s pictures were produced with C++ and Qt following the same QA procedure that I used with the code for this article:

I wrote some throwaway code to generate these images in C++ and Qt over a few hours on a wet bank holiday Sunday. QA amounted to ‘that looks about right’.

[1] Yes, I am colour-blind!

Curling for web sites

tag@wordaligned.org (Thomas Guest) — 2008-05-27

I wanted information about ISO 3166-1 alpha-2 country codes. Google found me the definitive link (http://www.iso.org/iso/country_codes/iso_3166_code_lists.htm) but clicking on it showed the ISO website to be temporarily down for maintenance.

Rather than check back again every few minutes or hunt for stale information in the google cache, I got curl and bash to notify me when the site went live.

$ url=http://www.iso.org/iso/country_codes/iso_3166_code_lists.htm
$ curl -I $url
HTTP/1.1 302 Found
Date: Tue, 27 May 2008 08:00:44 GMT
Server: BIG-IP
Location: http://www.iso.org/error/sitedown.html
Via: 1.1 www.iso.org
Connection: close
Content-Type: text/html

Curl -I fetches the page header only, which in this case uses a 302 status code to temporarily redirect clients to the sitedown.html page. Using this information I wrote a simple while loop to ping the site every minute and determine when this status changed.

$ http_status() { curl -I -s $1 | head -1 | cut -d " " -f 2; }
$ while [ $(http_status $url) == 302 ]; do sleep 60; done; open $url

Open is an OS X thing: when the loop completes open just opens the web page in a browser tab.

To run this command in the background, & it.

$ (while [ $(http_status $url) == 302 ]; do sleep 60; done; open $url)&
[1] 808

Here, the job has a handle of 1 and a process id of 808. You can recover this information using jobs.

$ jobs
[1]+  Running                 ( while [ $(http_status $url) == 302 ]; do
    sleep 300;
done; open $url ) &

If you need to kill the job, kill %1 does the trick.

Fixing Compiler Warnings the Hard Way

tag@wordaligned.org (Thomas Guest) — 2008-05-20

GCC makes a suggestion

The build server CC’d me on an ASBO email. Good old GCC, grumbling about operator precedence again. But Hey! — at least it had a positive suggestion to make.

From: buildmaster@example.com
To: lem.e.tweakit@example.com
Cc: developers@example.com
Subject: Broken build
------------------------------------
Anti Social Build Order
Version: svn://svnserver/trunk@999
Platform: Linux, GCC 4.0.1
Build Log: 
....
Warning: suggest parentheses around arithmetic
in operand of ^

I looked at the code. Here’s a much simplified version which generates the same warning.

void
unpack(unsigned char const * bits, int n_bits,
       unsigned char * buf)
{
    unsigned char bit, byte, pos;
    int b;
    
    for (b = 0; b != n_bits; ++b)
    {
        byte = bits[b / 8];
        pos = 7 - (b % 8);
        bit = byte & 2^pos;
        buf[b] = bit == 0 ? 0 : 255;
    }
}

When compiling this function GCC warns about the line in bold type:

$ gcc -Wall -c unpack_bits.c 
unpack_bits.c: In function `unpack':
unpack_bits.c:12: warning: suggest parentheses around 
             arithmetic in operand of ^

Setting a precedent

Needless to say, the actual offending code was buried in a longer function, indented more deeply, and with a few more indirections — so it was indeed tempting to take GCC’s advice and whack in a couple of brackets. Clearly the author meant to write:

bit = byte & (2^pos);

Why else omit spaces around the ^?

Fortunately I live by my own rule, to avoid unnecessary parentheses, so I wasn’t about to add any here without asking why. Worse than my stubborn principles, ^, the exclusive or operator, has lower precedence than bitwise and, &, so to keep GCC happy and retain the original behaviour we’d have to write:

bit = (byte & 2) ^ pos;

This last expression looks very bizarre. Had it ever been exercised?

GCC was right, the code was wrong, but its diagnostic showed the wrong way to right things. On this occasion GCC should have been proscriptive, not prescriptive, and left the fix in the hands of the programmer^[1].

Don’t mix bits and arithmetic

0000 0000 5589 e58b 5508 89d0 d1e8 2555
5555 5529 c289 d0c1 e802 2533 3333 3381
e233 3333 3301 d089 c2c1 ea04 01d0 250f
0f0f 0f89 c2c1 ea08 01d0 25ff 00ff 0089
c2c1 ea10 01d0 25ff ff00 005d c300 0000
5555 5555 3333 3333 0f0f 0f0f ff00 ff00

My personal rule of thumb is to avoid mixing bitwise and arithmetic operations. Although integral types support both kinds of operation, it generally feels like a type-mismatch to combine them in a single expression. An array of bits isn’t the same as a number, and vice-versa.

Of course there are some treasured bit-twiddling tricks which exploit the mapping between binary arithmetic and machine level register operations. So we can, for example, calculate 2 raised to the power of 19 with a simple left-shift, 1 << 19, or test if v is a power of 2 with !(v & (v - 1)) && v. I’m not suggesting we blacklist these ingenious hacks — in fact, anyone off to an interview for a programming job with an embedded systems company might do well to study them — but I would say their use requires thorough documentation.

On occasion, then, bitwise operations may legitimately be used for fast arithmetic; but using arithmetic to pack bits is rarely necessary. This line of code is probably wrong^[2]:

r = h << 4 + 1;

The programmer probably intended the (bitwise) shift to happen before the (arithmetic) addition, like this.

r = (h << 4) + 1;

If we stick to bitwise operations, things become clear. I’ve written the 1 in hexadecimal as a hint it’s being used as a bit pattern — sadly there’s no way of writing a binary literal directly in C.

r = h << 4 | 0x1;

Anyway, the problem line in unpack() adheres to my rule of thumb: & and ^ are indeed both bitwise operations. But after some puzzling I realised the author of the code intended 2^pos to mean 2 to the power of pos, not for its arithmetic value, but for its bit pattern — which, as every programmer knows, is a 1 followed by pos 0s. That is, a 1 left shifted pos times.

Here’s what I thought the fix should be. Note, incidentally, that I’ve used ~0 rather than 255, because it clearly says “set every bit”. I’m also using unsigned integers throughout — always a good idea when working with bits. Some programmers might prefer to parenthesise the expression byte & 1 << pos, but I prefer the form shown: it’s easy enough to remember that & groups with the logical operators and << with the (higher precedence) arithmetic ones.

void
unpack(unsigned char const * bits, unsigned n_bits,
       unsigned char * buf)
{
    unsigned char bit, byte;
    unsigned b, pos;
    
    for (b = 0; b != n_bits; ++b)
    {
        byte = bits[b / 8];
        pos = 7 - b % 8;
        bit = byte & 1 << pos;
        buf[b] = bit == 0 ? 0 : ~0;
    }
}

Despite the absence of documentation, this is now at least a coherent function. It’s a “biterator” which steps through a collection of bits (packed into bytes, the smallest memory units C offers). Each time it encounters a set/clear bit, it sets/clears all the bits in the next byte in the output buffer. That is, it expands each bit value to fill a whole byte.

This is exactly the kind of function which is surprisingly fiddly to write but simple to unit test. As already mentioned, though, the function didn’t actually exist in the form shown, and the tests were all at the module level. The responsible way for me to proceed was to create a module test which exposed the defect, then make my candidate fix, confirm it did indeed fix the defect, then check the change in.

Unit Test

Here’s how simple a unit test for unpack() could be. It may be longer than the function it’s testing, but it’s less complex. And with just a couple of test cases, it manages to cover several interesting corners of the functionality. Better still, it passes^[3]!

void
test_unpack()
{
    // Start with a varied bit-pattern.
    // Ensure each byte differs from its reversed self.
    unsigned char const bits[2] = 
    {
        1 << 7 | 1 << 5 | 1 << 4 | 1 << 0, // 10110001 binary
        1 << 6 | 1 << 5 | 1 << 3 | 1 << 0, // 01101001 binary
    };
    // The expected output expands bits to bytes (0 => 0, 1 => ~0)
    unsigned char expected[2 * 8] = 
    {
        ~0, 0, ~0, ~0, 0, 0, 0, ~0,
        0, ~0, ~0, 0, ~0, 0, 0, ~0
    };
    unsigned char buf[3 * 8] = { 0 };
    unsigned char buf_copy[3 * 8] = { 0 };
    
    size_t const buf_size = sizeof(buf);
    
    // Fill the buffer with a pattern of 1s and 0s.
    // Unpack nothing and check nothing changes.
    memset(buf, 0xa5, buf_size);
    memcpy(buf_copy, buf, buf_size);
    unpack(bits, 0, buf);
    assert(memcmp(buf, buf_copy, buf_size) == 0);
    
    // Unpack some of the bits and check the results.
    // Also check the remainder of the buffer is undamaged.
    unpack(bits, 13, buf);
    assert(memcmp(buf, expected, 13) == 0);
    assert(memcmp(buf + 13, buf_copy + 13, buf_size - 13) == 0);
}

This is white-box testing: the test knows enough about the implementation of unpack() to expose potential problems. In this case, there’s something unusual about the way the pos counter goes down as the bit counter b goes up, so we make sure that the bits we’re unpacking form asymmetric patterns.

Refactoring

Should we extract this tested unpack() function from its surrounding, larger, more complex function? Is it safe to do so? Have we time to spend making changes with no externally visible results? Should we tweak unpack() for efficiency (after all, it doesn’t need to use the division and modulus operators each time round the loop)?

These are important questions. eXtreme Programmers refactor mercilessly, confident their extensive test frameworks will provide a safety net. Java programmers select the code block in their IDE then click the “extract method” button. C and C++ programmers have less advanced tools, but Michael Feathers’ “Working Effectively with Legacy Code” offers practical advice on how to transform code safely — that is, how to put it under test.

In the real world, we judge each case on merit. A nag email from the build server shouldn’t trigger mass refactoring, even if the test infrastructure is in place. I think Feathers is right though, that poorly tested code is on its way to becoming legacy code: hard to adapt, unpleasant to work with, and a drag on continuing development.

Lessons

This new story repeats the same old lessons, and I think they bear repeating:

Set up a build server. Listen to it.
Compile on multiple platforms.
Think! Compilers are concerned with syntax, not semantics. A C compiler reads your code in order to rewrite it for the machine’s benefit; understanding the code is your job.
Write small functions. Unit test them.
Integers and bit arrays are different.
Take care when using bitwise operations as arithmetic shortcuts.
Avoid using arithmetic for bit packing.

Oh, and in C, don’t mistake ^ for exponentiation!

This article was originally published in CVu, a print journal for ACCU members, and I would like to thank all at CVu for their help with it.

[1] I’m not complaining about GCC which did an outstanding job of flagging a genuine problem in perfectly well-defined and valid code. The other compiler frequently used on this project, MSVC V8.0, compiles this cleanly, at the same time warning standard C string functions are unsafe and deprecated!

[2] I’ve taken this example directly from Andrew Koenig’s “C Traps and Pitfalls”. This is a nice little book which expands on the ideas presented in a paper of the same name [PDF].

[3] One thing I recommend, though, is to temporarily reverse the logic in the assertions and check they then fail. Unit test frameworks often provide hooks to do this reversed-result test, which confirms the test cases are actually being run.

Accidental Emacs

tag@wordaligned.org (Thomas Guest) — 2008-05-06

Nice to see Emacs getting a bit of press recently. I’ve used it for almost 20 years now and it dominates my time at the keyboard. It isn’t perfect and I’m reluctant to recommend it but I wouldn’t want to be without it. Let me explain.

The best thing about Emacs is that it can do everything (including the things it can’t do yet). The worst thing about Emacs is finding out how it does anything. I wouldn’t call it discoverable. In fact, on several occasions, I’ve learned about Emacs by accident: you press the wrong key combination (easy to do when you’re holding down a couple of keys and stretching for a third) and, look, something interesting happens!

The rest of this article describes a few of these happy accidents: modes I never knew about and tricks I wish I’d learned earlier.

Emacs the Operating System

Whenever I see the Emacs splash screen (click on the graphic for a close-up) I’m amazed anyone ever gets past it. Computer users want instant gratification and a familiar interface — thus the encouraging tip:

You can do basic editing with the menu bar and scroll bar using the mouse.

Unhappily the rest of the screen discredits this friendly proposition. Where are the menu and scroll bars^[1], and what’s with all the Control this and Meta that? If the scratchy artwork and bizarre mix of font styles don’t put new users off, the remaining content surely will, with its dark warnings about sessions crashing and how to recover^[2].

Best of all, though, is the opening proposition:

GNU Emacs is one component of the GNU operating system

which I read as a straight-faced rebuttal of the old gag:

It is a common joke, both among fans and detractors of Emacs, to describe it as an operating system masquerading as an editor^[3].

GNU hasn’t quite become an operating system but it does supply most of the standard Unix tools and Emacs works beautifully with them — even on (Cyg-)Windows. META-! executes a single shell command, for example. META-| executes a shell command on the current region and puts the output in a temporary buffer. META-X grep and META-X grep-find build search on top of grep and find. META-X shell opens up a shell window within Emacs, meaning you can run shell commands and process their output using the standard editor commands. Emacs info is a better man page browser than info. And on on.

OS integration examples

META-!
META-|
META-X grep
META-X grep-find
META-X shell

When Emacs shells out to external tools their execution is never hidden from you, so you lose none of the power of these tools. The converse of this also holds: if you don’t know how to use grep and find, even basic search commands in Emacs will seem cryptic and hard to customise. Emacs is, above all else, customisable. In fact, most of Emacs is customisation, and you’ll soon give up on it if you can’t accept this^[4].

Window Management

Over at Coding Horror, Jeff Atwood talks about “large display paradox”:

One of the advantages of small monitors, ironically, is that because they’re small, they nudge users into a simpler, windowless method of working. Instead of wasting time sizing, moving, and z-ordering windows, users only need to deal with one maximized window at a time. They can flip between maximized applications in much the same way they change channels on the television. But once your display gets to 1600 x 1200 or beyond, this easy one-app-per-display model isn’t feasible any more …

That’s the large display paradox. Having all that space can make you less productive due to all the window manipulation excise you have to deal with to make effective use of it.

Well, I reckon Emacs has this problem cracked. On a small screen you can use a single maximised window: CTRL-X B switches editor buffers (a bit like tabbed browsing) and CTRl-X CTRL-B gets you a buffer management window. On a large screen CTRL-X 3 splits the enclosing window vertically, and CTRL-X 2 splits it horizontally. Repeat these commands to slice up your work space. CTRL-X 1 gets you back to a single window. The same commands work when you haven’t got a proper windowing environment — on a stripped down server for example, or one which hasn’t booted properly. Very handy!

Buffer and window management

CTRL-X B
CTRl-X CTRL-B
CTRL-X 3
CTRL-X 2
CTRL-X 1

Remote Editing

If, for example, the stripped down server discussed in the previous section allows SSH access or similar, you don’t need to install or run Emacs natively. Just use tramp mode (Transparent Remote file Access, Multiple Protocol). Quoting from the manual:

To access the file localname on the remote machine machine you would specify the filename /machine:localname. …

You can specify protocol (ftp, rsh, smb etc.) and user name too:

So, to connect to the machine melancholia as daniel, using the ssh method to transfer files, and edit .emacs in my home directory I would specify the filename /ssh:daniel@melancholia:.emacs.

As usual, there are plenty of configuration options. I haven’t touched any of them. Tramp mode just works: if I can access a remote machine, I can edit files on it and transfer files to and from it just as if it were local.

Remote editing example

Find file: /ssh:daniel@melancholia:.emacs

Binary Editing

Programmers often need to view the raw bytes packed into a file, and occasionally to edit these byte values. That’s what Hexl mode is for. META-X hexl-find-file opens a file in this mode and META-X hexl-mode switches a buffer to this mode.

META-X hexl-find-file
META-X hexl-mode

Archive Editing

Did you know that Emacs can work on .zip, .tar, .tgz etc archives directly? I found out when I opened one by accident: Emacs presents you with a view of the archive and you can browse files, edit them, rename them, remove them from the archive, and save the modified archive without ever having to manually extract it. No special knowledge required: it just works, a bit like dired-mode.

Dired Mode

If you open a directory with Emacs it puts you in dired-mode, the Emacs take on Windows Explorer, OS X Finder and so on. Many of the Emacs users I know don’t use this mode, preferring either the native system file manager or plain old terminal windows for file operations (copy, move, list, …) but I use it all the time and it’s led to many happy Emacs accidents.

As an example, suppose you have a directory full of files with names-like-this, and you want to rename all the files to use names_like_this instead. Just switch to editable dired mode, run a standard search and replace to swap hyphens for underscores, then save the directory.

As a second example, suppose you want to view thumbnails of all the .png files in a directory. Use a pattern match % m png to “mark” them (i.e. select them) then CTRL-t d to display them. Now you can visit the thumbnails, removing, renaming, copying the associated files.

Cryptic, yes, but powerful, and no mouse required — handy for laptops.

Keyboard Macros

You can hear when someone sitting nearby doesn’t know about editor macros or is using an editor which doesn’t support them. The tedious repetition of the same sequence of keystrokes grows audible.

In Emacs you start recording a keyboard macro with CTRL-X ( and finish recording with CTRL-X ). Everything typed between these bracketed commands has been recorded as a keyboard macro which CTRL-X e executes and then e repeats. If typing all those eeeeee’s is repetitive, supply a repeat count. A repeat count of 0 processes the whole buffer, and is often what’s wanted.

There’s far more to keyboard macros but this basic use alone will save your fingers and your sanity.

CTRL-X (
CTRL-X )
CTRL-X e

An IDE for Dynamic Languages

Emacs has a proven architecture: a compact, stable core which is dynamically configured by a huge library of scripts. These scripts are written in elisp. You can edit, reload and add to them at any point, without the need to reboot the main application. Rebooting wouldn’t be such a big thing, though — Emacs starts up in less than a couple of seconds — what’s important is that Emacs is dynamic to the core.

So it’s not surprising Emacs has great modes for dynamic languages like Python, Ruby, Scheme. Here’s how to develop Python code using Emacs:

Pull up a full-screen window
Split the window vertically
Use one side for the code you’re working on
Use the other side to run an interpreted session
Switch sides as desired

You continually select regions of code to execute. You step into the interpreter and use the Python help command to get help on modules and functions — including the ones you’re creating right now. You rework a function in one window then exercise it in the other. You sketch experimental code, run it, rub it out.

The same technique works for Scheme and Ruby, and is likely to work for any other dynamic language. The gap between writing and running code disappears.

As computers grow more powerful, specialised programmers’ IDEs do what they can to support this style of working for compiled languages. I understand Eclipse parses, compiles, and executes Java code as you write it, and it’s certainly an impressive piece of software. I’d be interested to know how it fares with C++.

Emacs also works well enough with compiled languages. I’ve heard Make described as REPL for compiled languages, and make -k is the default Emacs compile command. The usual IDE things are available. For more interactive probing of a compiled executable, META-X gdb is about as good an interface to GDB as I’ve seen. But I can’t (for example) imagine Emacs persuading anyone to dispense with Visual Studio for .Net development.

Code completion for cheats

This article cherry-picks a few Emacs modes you may not have discovered which I find invaluable. I haven’t bothered listing the basics of how to open or close files, without which you won’t get anywhere. One basic command I do want to mention is META-/, which dynamically expands whatever you’re typing whatever mode you’re in. I think of it as code completion for cheats, since it doesn’t parse any source code and it works equally well on any type of file type. It’s as useful as shell TAB-completion and I discovered it by accident.

Email, Surfing, Media Editing

You can’t edit photo, video or audio content in Emacs (perhaps I should say I don’t know of an Emacs mode for doing so^[5]). I don’t use Emacs for spreadsheets or other “office” documents. You can use Emacs for ascii-art (and here’s a great flash animation showing someone do just that) but ascii-art doesn’t look much good outside source code.

Hardcore Emacs users swear by their editor as an email client and even use it as a web browser. I prefer the comfort of my second most used application, Firefox. Come to think of it, Firefox adopts a lot of what’s good about Emacs: the tabbed window, for example, which reinvents multiple buffers for the web browser; the clean, simple look^[6]; the extensible architecture.

Funnily enough, you can work with photo, video and audio using Firefox; and boring old online office suites have been news for a long while. Amazingly, you can continue to edit your rich media content even if you switch to Internet Explorer, without the need to relearn anything; a transition which puts the Vi/Emacs wars into perspective. Could the web browser be the one true editor of the future?

Notes

My thanks to Hugh Brown for pointing out a couple of errors with the original version of this article.

[1] OK, so my .emacs disables the scroll bar and menu bar before this splash screen appears, but telling people what their mouse is for hardly seems necessary.

[2] I can’t remember when Emacs last crashed on me. It’s one of the three applications I auto-start on login and I usually leave it running until I shutdown. On occasion I’ve forced it to quit but this has always been down to my own error, for example coding and executing (within Emacs) a tight loop.

[3] Quoted from Eric S. Raymond’s excellent book “The Art of Unix Programming”

[4] In “The Art of Unix Programming” Eric S. Raymond discusses the question: “Is Emacs an Argument against the Unix Tradition?”. This is a rather long quotation to include here, I know, but I’m sure the author wouldn’t want me to alter his words in any way. I highly recommend the book and suggest you buy a copy to read in full.

The central tension in the Unix tradition has always been between doing more with less and doing more with more. It recurs in a lot of different contexts, often as a struggle between designs that have the quality of clean minimalism and others that choose expressive range and power even at the cost of high complexity. For both sides, the arguments for or against Emacs have exemplified this tension since it was first ported to Unix in the early 1980s.
Programs that are both as useful and as large as Emacs make Unix programmers uncomfortable precisely because they force us to face the tension. They suggest that old-school Unix minimalism is valuable as a discipline, but that we may have fallen into the error of dogmatism.
There are two ways Unix programmers can address this problem. One is to deny that large is actually large. The other is to develop a way of thinking about complexity that is not a dogma.
Our thought experiment with replacing Lisp and the extension libraries gives us a new perspective on the oft-heard charge that Emacs is bloated because its extension library is so large. Perhaps this is as unfair as charging that /bin/sh is bloated because the collection of all shellscripts on a system is large. Emacs could be considered a virtual machine or framework around a collection of small, sharp tools (the modes) that happen to be written in Lisp
On this view, the main difference between the shell and Emacs is that Unix distributors don’t ship all the world’s shellscripts along with the shell. Objecting to Emacs because having a general-purpose language in it feels like bloat is approximately as silly as refusing to use shellscripts because shell has conditionals and for loops. Just as one doesn’t have to learn shell to use shellscripts, one doesn’t have to learn Lisp to use Emacs. If Emacs has a design problem, it’s not so much the Lisp interpreter (the framework part) as the fact that the mode library is an untidy heap of historical accretions — but that’s a source of complexity users can ignore, because they won’t be affected by what they don’t use.
This mode of argument is very comforting. It can be applied to other tool-integration frameworks, such as the (uncomfortably large) GNOME and KDE desktop projects. There is some force to it. And yet, we should be suspicious of any ‘perspective’ that offers to resolve all our doubts so neatly; it might be a rationalization, not a rationale.
Therefore, let’s avoid the possibility of falling into denial and accept that Emacs is both useful and large — that it is an argument against Unix minimalism. What does our analysis of the kinds of complexity in it, and the motives for it, suggest beyond that? And is there reason to believe that those lessons generalize?

[5] So now I know better! In a comment on this site, Johan Lindstrom says you can edit video using Emacs, http://1010.co.uk/gneve.html, and in an email Arnold Mátyási pointed me at this YouTube GNEVE demo, while over at reddit another comment mentions an audio editing mode, http://delysid.org/emacs/ecasound-el.html.

[6] Splash screen excluded!

Scatter pictures with Google Charts

tag@wordaligned.org (Thomas Guest) — 2008-04-25

In a recent post on his blog Matt Cutts asks:

I almost wanted to call this post “Stupid Google Tricks” :-) What fun diagrams can you imagine making with the Google Charts Service?

Here’s a stupid trick: you can use the Python Imaging Library to convert a picture into a URL which Google charts will render as the original picture.

Here’s the original picture:

here’s the version served up by Google charts:

here’s the code:

import Image
import string

def scatter_pixels(img_file):
    """Return the URL of a scatter plot of the supplied image
    
    The image will be rendered square and black on white. Adapt the
    code if you want something else.
    """
    # Use simple chart encoding. To make things really simple
    # use a square image where each X or Y position corresponds
    # to a single encode value.
    simple = string.uppercase + string.lowercase + string.digits
    rsimple = simple[::-1] # Google charts Y reverses PIL Y
    w = len(simple)
    W = w * 3
    img = Image.open(img_file).resize((w, w)).convert("1")
    pels = img.load()
    black_pels = [(x, y) for x in range(w) for y in range(w)
                  if pels[x, y] == 0]
    xs = "".join(simple[x] for x, _ in black_pels)
    ys = "".join(rsimple[y] for _, y in black_pels)
    sqside = 3.0
    return (
        "http://chart.apis.google.com/chart?"
        "cht=s&"                          # Draw a scatter graph
        "chd=s:%(xs)s,%(ys)s&"            # using simple encoding and
        "chm=s,000000,1,2.0,%(sqside)r,0&"# square black markers
        "chs=%(W)rx%(W)r"                 # at this size.
        ) % locals()

and here’s the url it generates:

http://chart.apis.google.com/chart?cht=s&chd=s:DDEEEEEEE…&chs=186x186

Smallprint. Google charts may return a 400 error for an image with a long URL (meaning lots of black pixels in this case). The upper limit on URL length doesn’t seem to be documented but a quick trawl through topics on the google charts group suggests others have bumped into it too. Connoisseurs of whacky pictures should pay CSS Homer Simpson a visit.