I only solved one problem in GCJ 2013 round 1A, and that’s problem A, Bullseye. I really liked my solution to this problem (written in Racket):

(define (rings r t)
  (quotient (- (integer-sqrt (+ (* 4 r r) (* -4 r) (* 8 t) 1))
               r r -1)
            4))

Is the problem really that simple? Why, yes! It’s much simpler than many other entries I’ve seen, so I wanted to explain my solution approach.

So, let’s look at the problem step by step:

1. You are given t units of paint, and each unit of paint fills in a circle of radius 1.
2. This means that it takes 4 units of paint to fill in a circle of radius 2, 9 units for radius 3, etc., and generally, n² units to fill in a circle of radius n.
3. For a black ring with inner boundary r, and outer boundary r + 1, the total units used is, thus, (r + 1)² - r², or fully expanded as 2r + 1.
4. The next black ring has inner boundary r + 2, and outer boundary r + 3. More generally, for ring i, the inner boundary is r + 2i - 2, and the outer boundary is r + 2i - 1.
5. The total paint used for the first k rings is thus (2r + 1) + (2r + 5) + (2r + 9) + … + (2r + 4k - 3).
6. This is the same as k(2r - 3) + 4(1 + 2 + … + k), or in other words, k(2r - 3) + 2k(k + 1), which then becomes 2k² + (2r - 1)k.
7. You want to find the largest k is that satisfies 2k² + (2r - 1)k ≤ t, or in other words, 2k² + (2r - 1)k - t ≤ 0.
8. Solving this is easy: just use the quadratic formula! In this case, the factors used are a = 2, b = 2r - 1, and c = -t. Plugging this into the quadratic formula gives ((1 - 2r) ± sqrt((2r - 1)² + 8t)) / 4.
9. We only care about the positive (you can’t have a negative number of rings), so this simplifies to (sqrt(4r² - 4r + 8t + 1) - 2r + 1) / 4, which is almost exactly the code you see.
10. Finally, we are asked to disregard partial rings, so we simply floor the result. Done.

Apparently, I just read that some people actually keep their work code after they leave a company. Really?!

Maybe because I’m so gung-ho about copyright, I would never consider such a thing. Even having read that thread, I still would never consider such a thing. When I quit a job, I do not retain work code for any purpose. If I had any work code on my personal machine, I would wipe the machine clean before moving on.

My personal sense of ethics would not permit otherwise.

I’ve written some stuff for work that I would consider pretty technically impressive. But the past is the past; I know that I will write even better things in future. Tomorrow is another day.

Prior to Jelly Bean, if you wanted to type on your Android device using Dvorak or Colemak, you’d have to use a third-party keyboard app. (My favourite is SwiftKey, by the way.) But from Jelly Bean onwards, Dvorak and Colemak support is built in! No more third-party apps required! Here’s how:

1. Hold down the comma key, then select “Android keyboard settings”.

   

2. Scroll to the bottom and choose “Advanced settings”, then “Custom input styles”. (On factory default settings, the German QWERTY and French QWERTZ layouts are already present. You can remove them, of course.) Choose “Add style”.

   

3. Choose your desired language and layout, then add it.

   

4. You’ll now be prompted to enable it.

   

5. Untick the “Use system language” box, then tick the Dvorak or Colemak layout that you’ve chosen. Finally, you may also wish to untick the QWERTY layout if you never use it.

   

6. That’s it! Your shiny new Dvorak or Colemak layout is ready for you to use.

   

In the last post, I showed how to set up disk encryption in CBC-ESSIV mode in Debian and Ubuntu. This mode was used by default because partman-crypto did not support LRW and XTS modes. Now, I’ll show how to make it use XTS instead, which is more secure.

First, get to this screen:

Then, load the XTS kernel module. A big hassle here is that the installer .udebs do not contain the requisite xts module (and its dependency gf128mul). That means we have to extract this by hand (press Alt-F2 to get to a console, and Alt-F1 to return to the installer):

mkdir -p /tmp/linux
cd /tmp/linux
ar x /cdrom/pool/main/l/linux/linux-image-*.deb
tar xjf data.tar.bz2

(You can’t use udpkg --unpack for this, since it doesn’t support bzip2 archives.)

Now, we can go and load those modules:

cd lib/modules/*/kernel/crypto
insmod gf128mul.ko
insmod xts.ko

Now that the module is loaded, we can then perform the partman tweaks:

cd $(dirname /var/lib/partman/devices/=dev=sda/*/ivalgorithm)
echo xts-plain > ivalgorithm
echo 256 > keysize

(For XTS, keysize 256 means AES-128; you can also use 384 for AES-192 and 512 for AES-256.)

If you did everything right, then when you leave that crypto selection screen and come back to it, you should see this:

Recently, work has begun issuing new, high-end laptops to engineers, and I felt it was a good time to emphasise the need to encrypt everything on the laptop. There is virtually no overhead for doing this—it’s just a matter of getting it set up.

Below, I describe how to do this on Ubuntu 12.04 (precise). The procedure is all the same on recent versions of Debian and Ubuntu, though—they all just use partman-crypto to do the configuration.

On Ubuntu, you need to use the alternate CD, not the desktop one. On Debian, just use the standard text-mode installer. Do the configuration up to the disk partitioning section:

If you normally use guided partitioning, just use the “Guided—use entire disk and set up encrypted LVM”. The only extra thing you have to do is type in the encryption passphrase. It’s as simple as that, and you can stop reading here. :-)

The rest of this article is for people who like to do manual partitioning. Because of this, I will go into a fair amount of detail, so you can see how to control the whole process. (However, to be kind to my workmates, I am doing this using non-expert mode. The steps may be different for expert mode.)

The general principle of the process is this:

1. Set up a /boot volume so that the initramfs containing the crypto bootstrap code has somewhere to live. (This is the Achilles’ heel of the whole system, and I don’t know how to work around it.)
2. Encrypt the whole rest of the disk.
3. The “rest of the disk” cannot have a partition table, so we will use LVM to do the volume management.

Okay, so, here we go. :-)

First, create an empty partition table on your disk if necessary, then add a small partition for /boot. I usually use 64 MB.

So now, we should have most of our disk still free:

Set up that free space for encryption:

You can choose between AES-128, AES-192, and AES-256. I think AES-128 is sufficient, but that’s your choice.

The encryption mode (listed as “IV algorithm”) in that window is more significant. Wikipedia has a good overview of the various modes, but the long and short is that there are only three modes that you are supposed to use:

• cbc-essiv
• lrw-benbi
• xts-plain

Of the three, XTS is the most secure and is the industry standard for disk encryption. (BTW, never use cbc-plain or lrw-plain; they are insecure modes.) However, partman-crypto does not currently support LRW or XTS modes, so if you want to use XTS, there is more work to do (covered in a later article). However, if industry standard is not a big deal for you, ESSIV is probably sufficient.

Okay, let’s set up the encrypted volume’s passphrase:

There, just select “Configure encrypted volumes”, then “Finish”, and you’ll be prompted for the passphrase to use. Then we’re ready for LVM setup:

Select the line after “Encrypted volume”, then set that up as “physical volume for LVM”. Then we’re ready to configure LVM:

Create a volume group containing the encrypted volume:

Then add the volumes you want to use. For example, some people might want to have root, swap, usr, var, opt, and home. At a minimum, you will need root and swap, so that’s what I’ve used for the next screenshot for simplicity. When done, you should see the following:

Now just set up each of the LVM volumes with filesystem or swap volumes, and you’re done:

At Clojure/conj, Mark from Heroku did a talk on “Logs as Data”. At the question-and-answer session, Rich Hickey made a comment about date serialisation, and that got me started on the topic of TAI64. Afterwards, a handful of people came up to me to ask for more details, so I thought I’d take the opportunity to explain about TAI64 in a blog post.

The central point of TAI64 is that dates should be stored in a stable format, independent of how it would be displayed to a human.

This means that the date is stored as a 64-bit number, the bottom 63 bits being the number of seconds since 1970-01-01 in TAI, offset by 2⁶². In essence, this makes the value quite similar to time_t (which uses UTC), except for two things:

• There are 63 bits to play with, not just 32 (no year-2038 problems!).
• The timestamp is always monotonic, counting all leap seconds.

That second item is what people asked questions about, so I’ll explain it further.

Under POSIX, a day is defined to be exactly 86400 seconds. This is supposed to make calculating the number of days in a timestamp interval easy, in the sense that you can take the interval and just divide by 86400. Unfortunately, reality isn’t so simple when UTC has leap seconds; on specific days, there will be an extra second, 23:59:60, called a leap second, that brings the total second count to 86401.

So, whenever a leap second happens, time_t is rewound one second after the leap second, in order to maintain the illusion that a day is always 86400 seconds. This means:

• The timestamp is non-monotonic.
• It is impossible to distinguish whether an event happened on the leap second, or the second following it.
• Even worse, the interval between two time_t values is not a true representation of the real number of seconds within, but is instead negatively offset by the number of leap seconds within.

The last point means that the bigger the interval, the bigger the inaccuracy. After a while, this isn’t “just one second’s difference”; those seconds add up.

TAI64 was designed as a time format that accurately represents time as a quantity of seconds, without “losing time” as time_t does. The principle behind this is that timestamps must remain accurate far in the future; after all, the format is expected to work way beyond year 2038, when time_t would wrap.

So, what to do about leap seconds? Under the TAI64 system, leap seconds are to be handled by the date/time library, when displaying dates, or otherwise breaking the date down into its calendrical components. Since the occurrence of leap seconds is not algorithmic, a table containing all known leap seconds is used when deciding how many leap seconds to adjust for in the time breakdown.

Yes, this means that the table must be regularly updated. No, it’s not as onerous as it may sound. Indeed, many operating systems already provide regular updates to their time zone data as part of regular system updates; for example, Ubuntu updates its tzdata package regularly to keep in line with the ever-changing time-related laws internationally.

Further, the Olsen timezone data (the basis of the tzdata package, and the timezone information for possibly every other operating system) contains information on leap seconds, under the right/* timezone files. Using the those timezone files, you can keep your system clock as TAI, rather than POSIX, and have all the time display/breakdown facilities work correctly.

Keeping your system clock as TAI effectively makes your time_t map one-to-one with TAI64. You no longer lose leap seconds, or have non-monotonic time. However, your time_t is no longer POSIX-conformant, and it’s not possible to get the number of days in a time interval by simply dividing by 86400. Is that a bad thing? I argue that it’s not.

The reality is, a day is not always 86400 seconds, and had not been since the introduction of UTC. It’s not useful to try to pretend otherwise. Losing one second may not be a big deal for some applications, but for long-term logging data, those seconds do add up quickly, gradually diminishing the usefulness of the log timestamp.

For that reason, I believe that logs should use TAI64, or another TAI-based timestamp system.

TAI64 has the advantage that its format is fully specified, and thus interoperable with other TAI64 libraries; this means your log timestamps will remain readable for many years into the future. Further, for applications that need more precision than a second, there are two extension formats, TAI64N and TAI64NA, that provide nanosecond and attosecond precision respectively, each adding a 32-bit quantity to the timestamp data.

Attosecond precision, as provided by TAI64NA, has 18 decimal places. Even though TAI64NA is 128 bits long, it provides more precision than quite possibly any other timestamp system in common use. And 128 bits still just 16 bytes; far shorter than any human-readable string-based date serialisation format of comparable precision.

So, which format do I recommend for serialising timestamps for logging data? Either TAI64, TAI64N, or TAI64NA, depending on your precision requirements. I do not believe there is any other format that has quite the same compactness and generality as these.

I thought my last post was the end of the humble pies, but apparently not!

So, for the last few days, I was doing a ginormous merge of a significant portion of code that Mike and I were independently working on over the course of a month. On Sunday, I got the last touches done and checked it all in, then ran the build.

The build failed with two tests flunking. That was odd, because the failed tests did not correspond with the tests in my code tree. I was like, what the hell, why is the build server using old code? It must have gone nuts! The build server needs a lobotomy, stat!

When Mike set up the build server, he set it up to be locked down so that developers don’t log into it directly. Of course, that didn’t help me figure why it was using old code, so I whinged about it until a workmate got me access to the server.

Once I got in, I noticed something very strange. The old code was indeed there, but, strangely, running git status didn’t return anything out of order. Well, let’s trudge on anyway. I could think of only a small change to make to the failing test; I didn’t think it would make a difference, but I could at least try.

So I committed the change and proceeded to push it. Then our git server rejected the push.

For context, our git server is set up with a pre-commit hook, that checks for basic sanity: code files should not have stray tabs or conflict markers or end-of-line whitespace, and the commit message should start with “Redmine #XXX”, so that it’s easy to tell which ticket any given commit is associated with.

It turned out that my big merge checkin had a typo: instead of Redmine, I somehow typed Redmite instead. (This is a Dvorak-specific typo, for people not familiar with the Dvorak layout.) So that whole merge didn’t successfully push. And that was, in fact, why the build server was using the old code. Not because it went bonkers. :-P

So, that big hissy fit I threw was much ado about nothing. FML.