Compact encoding of the leap seconds list
« previous entry | next entry »
8th Jan 2017 | 00:58
The list of leap seconds is published in a number of places. Most authoritative is the IERS list published from the Paris Observatory and most useful is the version published by NIST. However neither of them are geared up for distributing leap seconds to (say) every NTP server.
For a couple of years, I have published the leap second list in the DNS as a set of fairly human-readable AAAA records. There's an example in my message to the LEAPSECS list though I have changed the format to avoid making any of them look like real IPv6 addresses.
Poul-Henning Kamp also publishes leap second information in the DNS though he only publishes an encoding of the most recent Bulletin C rather than the whole history.
I have recently added a set of PHK-style A records at
leapsecond.dotat.at listing every leap second, plus an "illegal"
record representing the point after which the difference between TAI
and UTC is unknown. I have also added a
which should be the same as PHK's
There are also some HINFO records that briefly explain the other
One advantage of using the DNS is that the response can be signed and
validated using DNSSEC. One disadvantage is that big lists of
addresses rapidly get quite unwieldy. There can also be problems with
DNS messages larger than 512 bytes. For
answers can get a bit chunky:
I've thought up a simple and brief way to list the leap seconds, which looks like this:
leaps = *leap end leap = gap delta end = gap "?" delta = "-" / "+" gap = 1*DIGIT
Each leap second is represented as a decimal number, which counts the months since the previous leap second, followed by a "+" or a "-" to indicate a positive or negative leap second. The sequence starts at the beginning of 1972, when TAI-UTC was 10s.
So the first leap is "6+", meaning that 6 months after the start of 1972, a leap second increases TAI-UTC to 11s. The "84+" leap represents the gap between the leap seconds at the end of 1998 and end of 2005 (7 * 12 months).
The list is terminated by a "?" to indicate that the IERS have not announced what TAI-UTC will be after that time.
ITU recommendation TF.460-6 specifies in paragraph 2.1 that leap seconds can happen at the end of any month, though in practice the preference for the end of December or June has never been overridden. Negative leap seconds are also so far only a theoretical possibility.
So, counting months between leaps is the largest radix permitted, giving the smallest (shortest) numbers.
I decided to use decimal and mnemonic separators to keep it simple.
If you want something super compact, then bit-banging is the way to do it. Here's a binary version of the leap second list, 29 bytes displayed as hexadecimal in network byte order.
46464c4c 4c4c4c4c 4c524c4c 585e584c 524c4c52 52523c58 646a6452 85
Each byte has a 2-bit two's complement signed delta in the most significant bits, and a 6-bit unsigned month count in the least significant bits.
The meaning of the delta field is as follows (including the hex, binary, and decimal values):
- 0x40 = 01 = +1 = positive leap second
- 0x00 = 00 = 0 = no leap second
- 0xC0 = 11 = -1 = negative leap second
- 0x80 = 10 = -2 = end of list, like "?"
So, for example, a 6 month gap followed by a positive leap second is 0x40 + 6 == 0x46. A 12 month gap is 0x40 + 12 == 0x4c.
The "no leap second" option comes into play when the gap between leap seconds is too large to fit in 6 bits, i.e. more than 63 months, e.g. the 84 month gap between the ends of 1998 and 2005. In this situation you encode a number of "no leap second" gaps until the remaining gap is less than 63.
I have encoded the 84 month gap as 0x3c58, i.e. 0x00 + 0x3c is 60 months followed by no leap second, then 0x40 + 0x18 is 24 months followed by a positive leap second.
There's still quite a lot of redundancy in the binary encoding. It can be reduced to 24 bytes using RFC 1951 DEFLATE compression.
There is now a TXT record at
leapsecond.dotat.at containing the
human-readable terse form of the leap seconds list. This is gives you
a 131 byte plain DNS response, or a 338 byte DNSSEC signed response.
I've published the deflated binary version using a private-use TYPE65432 record which saves 58 bytes.
There is code to download and check the consistency of the leapseconds files from the IERS, NIST, and USNO, generate the DNS records, and update the DNS if necessary, at http://dotat.at/cgi/git/leapseconds.git.