16 lines
4.2 KiB
Plaintext
16 lines
4.2 KiB
Plaintext
The Rollover of Doom: a Trap for Good Programmers
|
|
<p>GPS, the Global positioning System, was designed in the 1970s under hardware-cost constraints that would seem ridiculous today. This makes interpreting the data it sends into a black art, and produces some really painful edge cases.</p>
|
|
<p>There’s one edge case in particular that I’ve come to think of as the Rollover of Doom. This morning I came up with an evil, clever hack for getting around it. I call it clever because you have to think your way out of a conceptual box to see it. As to why it’s evil…well, you’ll see. If you can figure it out.</p>
|
|
<p><span id="more-2869"></span></p>
|
|
<p>The root cause of the Rollover of Doom is the peculiar time reference that GPS uses. Times are expressed as two numbers: a count of weeks since the start of 1980, and a count of seconds in the week. So far so good – except that, for hysterical raisins, the week counter is only 10 bits long. The first week rollover was in 1999; the second will be in 2019.</p>
|
|
<p>So, what happens on your GPS when you reach week counter zero? Why, the time it reports warps back to the date of the last rollover, currently 1999. Obviously, if you’re logging or computing anything time-dependent through a rollover and relying on GPS time, you’re screwed.</p>
|
|
<p>Now, we do get one additional piece of time information: the current leap-second offset. The object of this exercise is to figure out what you can do with it.</p>
|
|
<p>For those of you unfamiliar with calendrical arcana, a leap-second is a shim inserted in calendars to cope with variability in the Earth’s rotation, which is slowing very gradually due to <a href="http://bowie.gsfc.nasa.gov/ggfc/tides/intro.html">tidal braking</a>.</p>
|
|
<p>If you start an atomic clock running – say, in a GPS satellite – and you want to compute Earth time such as <a href="http://en.wikipedia.org/wiki/Coordinated_Universal_Time">UTC</a> with it, and you want days and weeks and months in UTC to stay in sync with astronomical time (when the sun rises and sets), then you occasionally have to stuff a second in somewhere so the Earth’s gradually-slowing rotation has time to spin it to where you would have expected it to be if the spin were truly constant.</p>
|
|
<p>So, in order to allow UTC to be computed from the GPS-week/GPS-second pair, the satellite also broadcasts a cumulative leap-second offset. The offset was 0 when the system first went live; in January 2010 it is 15 seconds. It’s updated every 6 months based on spin measurements by the <a href="http://www.iers.org/">IERS</a>.</p>
|
|
<p>For purposes of this exercise, you get to assume that you have a table of leap seconds handy, in Unix time (seconds since midnight before 1 Jan 1970, UTC corrected). You do *not* get to assume that your table of leap seconds is current to date, only up to when you shipped your software.</p>
|
|
<p>For extra evilness, you also do not get to assume that the week rollover period is constant. The not-yet-deployed Block III satellites will have 13-bit week rollover counters, pushing the next rollover back to 2173CE.</p>
|
|
<p>For extra-special evilness, there are two different ways your GPS date could be clobbered. after a rollover. If your receiver firmware was designed by an idiot, all GPS week/second pairs will be translated into an offset from the last rollover, and date reporting will go wonky precisely on the next rollover. If your designer is slightly more clever, GPS dates between the last rollover and the ship date of the receiver firmware will be mapped into offsets from the <em>next</em> rollover, and date reporting will stay sane for an entire 19 years from that ship date.</p>
|
|
<p>You are presented with a GPS time (a week-counter/seconds-in-week pair), and a leap-second offset. You also have your (incomplete) table of leap seconds. The GPS week counter may invalid due to the Rollover of Doom. Specify an algorithm that detects rollover cases as often as possible, and explain which cases you cannot detect.</p>
|
|
<p>Hint: This problem is a Chinese finger-trap for careful and conscientious programmers. The better you are, the worse this problem is likely to hurt your brain. Embrace the suck.</p>
|