John Graham-Cumming

I've mothballed my blog.

All the posts are here; comments are disabled.

Taking a break from personal online things.

If a person who debugs code is a debugger then the person who wrote the bugs must be a... 

I gave a talk at the UKHAS 2013 Conference in September on debugging for high-altitude balloon enthusiasts. It applies more generally than that and may be interesting to others (especially if you are relatively inexperienced at programming and debugging).


The talk covers the basics of debugging without any specific programming language and is intended to be humorous but also useful. The folks at UKHAS were super organized and recorded the talks and synchronized the slides. You can listen to me give this talk by going to the BATC File Archive and then select HAB2013: my talk is HAB2013 03 Debugging.

If you care less about debugging and more about other high-altitude balloon stuff then check out my talk from last year, called HAB Software Woes, and my GAGA-1 high altitude balloon flight. Here's a shot of the moon taken by GAGA-1:

I gave a talk at the Go London User Group meeting in September on Go Memory. Here's the presentation itself:


Go memory from jgrahamc
It's worth reading the CloudFlare blog post Recycling memory buffers in Go as it goes into more detail.

UPDATE: Read the comments below for the solution.

If you've worked your way through the GCHQ Can you find it? recruitment challenge you'll have reached the last part and discovered that you have to do... nothing. The code word is accepted and you get to give your details for the competition. But you didn't do anything in part five.

That bothers me.

And there's another thing that bothers me. The second part includes a very obvious link to a web site (apparently correct) hidden inside an RSA private key, but the private key is messed up and messed up in a very specific manner.

Here's the key file dumped out:

$ openssl rsa -in comp1.key -text -noout
Private-Key: (1022 bit)
modulus:
37:c0:04:af:3e:8e:80:cb:75:b1:53:0c:9f:b2:dc:
    f4:d3:ce:4a:82:8b:52:f6:a8:48:e0:c5:d8:35:8b:
    26:6c:84:94:de:29:47:24:49:85:72:28:17:8e:06:
    d0:77:17:0c:2a:5d:56:ba:88:d1:07:25:e2:c5:7b:
    01:44:ea:e9:44:38:87:1a:b5:5a:75:d5:98:34:89:
    b3:1f:9e:a4:e2:bd:b7:7a:b7:cf:f3:dc:ac:ea:ac:
    …

Recent news stories about how NSA and GCHQ operate have brought to light the world of SIGINT: signal intelligence. And many people are surprised that these secret organizations gather so much information looking for 'bad guys'. Putting aside the ethical or political considerations it's worth understanding that what's come to light does not appear to be particularly new. And so the intelligent reader might want to know more about this secret world.

There are a number of books to recommend on the subject.

Spycatcher

Although Spycatcher, Peter Wright's memoir, is mostly about his suspicion that Sir Roger Hollis was a Soviet spy, the book contains quite a bit of detail about electronic eavesdropping. Here's a small part about dealing with The Troubles:
The only major recommendation I made was that we should devise a system of tapping the telephone lines of the Irish Republic. Lines across the border were well covered, but vital Provisional IRA communications flowed…

O'Reilly have put up a YouTube video of my keynote from today entitled "Turing's Curse". It's a short talk about the history of computing and about how history repeats itself.

A few weeks ago I started wondering about 'the test that occasionally and randomly breaks' in a large test suite at my job. The test, called 'overloaded origin', tests a situation where a web server becomes overwhelmed with requests and a proxy server (the code being tested) has to handle the situation gracefully.

The test works by having a dummy web server that could randomly decide to (a) return a normal web page for a request (b) read the HTTP headers and then do nothing for 30 seconds and (c) read the HTTP headers, wait 30 seconds and then send a valid response. The proxy server is hit by 5,000 clients simultaneously requesting the same URL.

And sometimes, every now and again, this test failed.

And like many engineers I'd ignored it for a long time. But it kept worrying me because it must have meant something: computers are deterministic, after all. I was spurred to action by a colleague suggesting that the test be disabled because it was 'flaky'.

It t…

Over the years I've become more and more verbose in commit messages. For example, here's a recent commit message for something I'm working on at CloudFlare (I've obscured some details). This is actually a one line change to a Makefile but gives a good example of what I'm aiming for.
commit 6769d6679019623a6749783ea285043d9449d009 Author: John Graham-Cumming Date: Mon Jul 1 13:04:05 2013 -0700 Sort the output of $(wildcard) as it is unsorted in GNU Make 3.82+ The Makefile was relying on the output of $(wildcard) to be sorted. This is important because the XXXXXXXXXXXX rules have files that are numbered and must be handled in order. The XXXXXXX relies on this order to build the rules in the correct order (and set the order attributes in the JSON files). This worked with GNU Make 3.81 In GNU Make 3.82 the code that globs has been changed to add the GLOB_NOSORT option and so the output of $(wildcard) is no longer ordered and the bu…

Due to revelations about access to private email (and other electronic communication) by the NSA and GCHQ some people have been suggesting that we all need to start using encrypted email. I've had PGP/GPG keys since about 1995 and I have only ever received a handful of encrypted mails.

So, how do you make people send you encrypted mail? I think an 'economic' incentive is necessary.

If you send me an unencrypted email it will be delayed by 12 hours before it is delivered. Encrypted email will be delivered immediately.

This is actually pretty easy to accomplish. An SMTP server can examine the contents of an incoming email and determine if it is encrypted or not. If it's not encrypted it can be placed in a delay queue and delivered after the appropriate delay; at the same time the server can send a message warning the sender of the delay and perhaps educating them about how to send encrypted mail.

This scheme could be called the Plain Text Tarpit (PTT) or perhaps the Plai…

You might be familiar with the triangular numbers: the number of objects that form equilateral triangles like this:

The sequence is 3, 6, 10, 15, 21, ... The first one, 3, is 1 + 2, the second one, 6, is 1 + 2 + 3, the third one, 10, is 1 + 2 + 3 + 4 and so on. For a triangle with a base of \(n\) blobs the number of blobs in the triangle is \(n * (n + 1) / 2\) (which can be proved by various means and was famously figured out by the mathematician Gauss while a school boy).

But what about the hollow triangular numbers? The ones where you take the middle blobs out of the triangles and just leave the border. Like this:
The pattern there is very simple. They are all multiples of three. And the formula would be that the hollow triangle with a base of size \(n\) has \(3 * (n-1)\) blobs in it (and since that's a multiple of three so is the number of blobs in a hollow triangle).

Here are three ways to prove that that formula is correct.

Subtracting the middle

Because we already have a for…

In the past I've written a couple of blog posts titled Some things I've learnt about programming and Some things I've learnt about writing. People seem to have enjoyed those posts (judging by the page view counts and comments) and so I thought I'd write something about public speaking and specifically about conference speaking.

0. It really does help to know what you are talking about

If you know your subject well then you will be able to talk well within the limits of your knowledge and be interesting and informative. You'll also be more comfortable and your comfort will come across to the audience.

If, on the other hand, you are giving a talk about a subject you know little about you are likely to come across poorly. This is partly because you won't have confidence in what you are saying and partly because it helps to leave audience wanting more. Also, when you are ill informed it's easy to be repetitive and therefore tedious.

I like when there's a ve…

I posted a puzzle about coins and change and promised a prize (a copy of The Geek Atlas) to one of the solutions picked by me. The following people provided solutions:

1. Matt

2. Michael Bauer

3. Asger Drewsen

4. vext01

5. Dubya

6. Josh

7. Anatoli Plotnikov

8. Matt Hickford

As that's a convenient 8 people I've chosen a winner by the roll of a d8.


 So the winner is #7, Anatoli Plotnikov.

Today, May 5 is written 5/12 in the US and 512 is a power of 2, it's \(2^9\). I tweeted that and received a rapid reply from Peter Inglesby that in UK-style dates it's 12/5 which is 125 which is \(5^3\). Which made me wonder whether there were other dates that had the same property in the US and UK on the same day.

Peter wrote a quick script:
and determined that there are four such dates:

March 24: US 3/24; \(324 = 18^2\). UK 24/3; \(243 = 3^5\)

May 12: US 5/12; \(512 = 2^9\). UK 12/5; \(125 = 5^3\)

June 25: US 6/25; \(625 = 5^4\). UK 25/6; \(256 = 2^8\)

December 5: US 12/5; \(125 = 5^3\). UK 5/12. \(512 = 2^9\)

Now I just need to think up a mystical significance to this, start a religion and retire on the proceeds.

One of my slow burn projects has been to make and display a periodic table of elements using element samples that I have been able to find or make myself. This is what it currently looks like:


The poster itself is actually a blown up version of the poster that comes with the quirky book Wonderful Life with the Elements: The Periodic Table Personified by Bunpei Yorifuji. Each element is represented by a person (or robot) and characteristics of the person reflect the element itself (such as its state at 'room temperature', its radioactivity, and when it was discovered).

Having got the poster enlarged I had a custom frame made using the cheapest online source I could find. To store each element I'm using 1/2 dram clear glass vials with black polypropylene caps that are lined with polyvinyl. This vial are very small (they are pictured here with my international object sizing tool) so that the overall periodic table is not too large.


It is possible to buy samples of the elemen…

Back in the 1980s I went to Oxford University and studied Mathematics and Computation (this was almost the entire Mathematics course plus Computer Science added on; the degrees offered today are a little different).  Having sat the mathematics entrance exam and gone through all the mathematics interviews I had interviews in the Programming Research Group (now the Department of Computer Science). During those interviews two specific programming/algorithm design questions were posed. Here they are (I made up names for them).

The Z Machine

A computer is constructed with a simple memory layout. It has an unlimited amount of memory and each memory location is numbered so that a program can refer to it. Each memory location can store a single number or be uninitialized. In the following diagram memory locations that are blank are uninitialized some other memory locations have numbers in them.


The computer's CPU only has three instructions Z, I and J as follows:

Z. This instruction zeroes…

Following on from my popular blog post about coding by hand in 1985 I dug into my pile of old stuff to look at how myself and another boy at school reverse engineered the Research Machines CHAIN network and built everything from networking protocols to a network management system in assembly language.

In 1982 Research Machines in the UK launched the LINK 480Z Z80 based machine that had an optional 800kbps proprietary network called CHAIN. My upper school got a small network of them linked to a file server running MP/M. The 480Z's would boot from the file server across the network.


Unfortunately, the entire network protocol was undocumented by Research Machines and unpublished. Myself and another boy, P, decided to reverse engineer because we wanted boot control and we wanted network access. Disassembling the running operating system (often using its front panel, which was on screen and not via flashing lights) we were able to determine that the Z80RST 8 instruction was used to se…

Back in 1985 I worked on the computerization of a machine designed to stick labels on bottles. The company that made the machines was using electromechanical controls to spool labels off a reel and onto products (such as bottles of shampoo) passing by on a conveyor. The entire thing needed to work with mm accuracy because consumers don't like labels that aren't perfectly aligned.

Unfortunately, electromechanical controls aren't as flexible as computer controls and so the company had contracted a local technical college (where I was studying electronics) to prototype computer control using a KIM-1. Another student had put together the machine with a conveyor, a mechanism for delivering the labels, control of stepper motors, and infrared sensors for detecting labels and products.


My job was to write the software in 6502 assembly. Unfortunately, there wasn't an assembler and the KIM-1 just had a hex keypad and small display. So, it meant writing the code by hand, hand as…

I have in my pocket the following British coins: one £2, two £1, two 50p, three 20p, one 10p, two 5p, two 2p and two 1p. I wish to buy a copy of today's paper at a cost of £1.70.

What is the maximum number of coins I can use to pay for the paper? With the restriction that I pay in a reasonable manner (e.g. I could give exactly £1.70 or an amount greater than that but without giving extraneous coins: e.g. giving the seller all the coins would not be acceptable, but giving him one £1 an two 50ps and expecting 30p in change is OK). The reasonable manner is simply: if I give the seller a set of coins he should not be able to return any to me without the sum of the remaining coins dropping below £1.70.

Looks like it's: two 50p, three 20p, one 5p, two 2p and one 1p. That gives away 9 coins from the 15 coins I have.

The general statement of this problem is as follows.  There are \(n\) coins in a currency: \(d_0\) to \(d_{n-1}\) are the denominations of the coins (normalize all to a …

Some time ago I integrated OpenSSL's MD5, SHA1 and RC4 functions into Go because Go's native implementations were slow. The Go team has made great strides in fixing this (for 386 and AMD64) with Go 1.1 with faster RC4, SHA1 and MD5.

Rerunning my tester program shows the following:

MD5SHA1RC4Native Go (pre-1.1)404 MB/s123 MB/s111 MB/sVia OpenSSL607 MB/s636 MB/s744 MB/sGo 1.1602 MB/s383 MB/s662 MB/sGo 1.1 vs. OpenSSL0.99x0.6x0.89x
So, the Go team has essentially reached parity with OpenSSL on MD5, is close on RC4, but could still do work to get the SHA1 performance close. (All testing of Go 1.1 was done with 84e21a8c2137 on Ubuntu 12.04 2.4Ghz Intel Core i7; 4 cores with 2GB of RAM).

As a further comparison Go's own benchmark tests shows the following.

MD5, via OpenSSL: BenchmarkHash8K (593 MB/s), BenchmarkHash8KUnaligned (581 MB/s); MD5, Go 1.1: BenchmarkHash8K (584 MB/s), BenchmarkHash8KUnaligned (589 MB/s)

SHA1, via OpenSSL: BenchmarkHash8K (606 MB/s); SHA1, Go 1.1: Benchm…

Last February myself, Professor Darrel Ince and Professor Les Hatton had a paper published in Nature arguing for openness in the code used for scientific papers. The paper is called The Case for Open Computer Programs.

In a coda to that piece Darrel wrote the following:
Our intent was not to criticise; indeed we have admiration for scientists who have to cope with the difficult problems we describe. One thesis of the article is that errors occur within many systems and does not arise from incompetence or lack of care. Developing a computer system is a complex process and problems will, almost invariably, occur. By providing the ability for code to be easily perused improvement will happen. This is the result detailed in both the boxes in the article: the Met Office data is more accurate, admittedly by a small amount, and because of feedback to developers the geophysical software was considerably improved. Recently, an important paper in economics has been in the news because its conc…

My four blog posts on this subject (starting here) have been very popular with well over 100,000 page views in four days. Because of their popularity, and because some people may wish to share the story of Alice and Bob in a different format I've put together an 11 page PDF and eBook containing and edited, illustrated and slightly expanded version of the posts.

You can buy it for $1.99 as a PDF or as ePub. It's 11 pages of detailed explanation for less than a latte!


It's for sale, rather than free, as a way of supporting this blog. There are no ads here and I intend to keep it that way.

This is part 4 of a series of blog posts about one-way functions and their use in securing passwords. If you have not read the other parts start here.

Bob doesn't usually let his wife Carla help him with crosswords. That's because, due to some unusual quirk of brain topology, Carla is a savant and she's memorized the entire Shorter Oxford English Dictionary. So, she's able to recall the definition of any word almost instantly. But, like many people with similar abilities, her talent is limited, she can't perform the opposite: given a definition she's just as slow as her husband at finding the corresponding word.

Carla's ability means that she can calculate Alice's one-way function from crossword solution through five definitions very quickly. She's about 100 times faster than Bob because she has no need to find words in the physical book. But she's no faster at performing the reverse.

Alice calls and Bob challenges her for the solution to 25A. …

This is part 3 of a series of blog posts about one way functions and their use in securing passwords. If you haven't read the first two parts start here.

Now Alice is angry. She realizes that Bob has defeated her clever one way function with his reverse dictionary and that now that Bob's created it he can use it over and again. All his initial effort will be amortized day after day as he steals crossword answers from Alice.

And so Alice strikes back.

The following day she calls Bob and says that she's making a small change to her one way function. It'll still involve looking up five words in the dictionary and following the definitions, but the order will change. In fact, she'll get to pick the order.

In the original scheme the first word of the first definition was used, the second word of the second and so on. Alice proposes to verify that she knows the answer to 4D (TANGLE) by giving Bob the final word (just as before) but also five numbers indicating which wor…