|
leapc
|
This repo delves into the intricacies of leap years, exploring their historical context, the rules governing their occurrence, and practical methods for calculating them in embedded systems. We discuss the significance of leap years in maintaining calendar accuracy and provide efficient algorithms suitable for resource-constrained environments. The article also highlights common pitfalls and best practices for implementing leap year calculations in C programming, ensuring reliability and precision in timekeeping applications.
What is a leap year? In simple mathematical terms,
$$ f_{leap}(year) = ( year \bmod 4 = 0 ) \land \left[ (year \bmod 100 \neq 0) \lor (year \bmod 400 = 0) \right] $$
where $x\bmod y$ is the integer “modulo” operation: the remainder after dividing a numerator by a denominator; the modulo operation computes the “modulus.”
Developing a super-simple library for manipulating Gregorian epoch times that account for leap years is the goal of this article. Such a library has no low-level dependencies. It depends only on raw C, making it suitable for embedded systems.
In basic C, the is_leap function answers true or false:
Notice that $year$ exists in integer space: $year\in\mathbb{Z}$. This is by design and not just for performance. A year is a whole number for the purpose of leap determination. For contemporary embedded systems, an integer is typically a signed 32-bit number; this provides more than enough resolution for epoch years, which would normally fall between $1970$ and $2025$, the current year.
Computing leap years through a range requires a specialised quotient-modulo function that handles negative divisors correctly. The following sections expand on this issue and walk through the complete implementation.
Another way of looking at the leap year formula exists. For some $year$, the following sum gives the total number of “leap years” through the range $thru_{leap}\in\left[0, year\right)$.
$$ thru_{leap}\in\left[0, year\right)=f_{quo}(year, 4) - f_{quo}(year, 100) + f_{quo}(year, 400) $$
Note carefully: the exclusive upper boundary. This is important. The sum does not include the given year; it includes all the years up to the year, but not the year itself. The $f_{quo}$ function computes the integer quotient of its two arguments.
The $f_{quo}(x, y)$ function amounts to, in C:
The implementation tracks Lua’s module operator. The sign differs. In C, the sign of the modulus follows the sign of the numerator, but for Lua, it follows the sign of the divisor. The C implementation needs a small correction; add the divisor if the signs differ between the modulus and the divisor.
$$ \begin{aligned} m' &= x \bmod y \ m &= \begin{cases} m' + y & \text{if } m' \neq 0 \text{ and } \text{sgn}(m') \neq \text{sgn}(y) \ m' & \text{otherwise} \end{cases} \ q &= \frac{x - m}{y} \end{aligned} $$
Properties include:
$$ \begin{aligned} 0 \leq m < y & \quad \text{when } y > 0 \ y < m \leq 0 & \quad \text{when } y < 0 \end{aligned} $$
And the invariant $x = y \cdot q + m$ applies. The simple reason for this disparity between Lua and C boils down to the fact that Lua uses only floating-point numbers at version $5.1$. For that reason, it computes % in $\mathbb{R}$ space using division and “floor” as follows.
$$ \text{luai}_{nummod}(a, b) = a - \left\lfloor \frac{a}{b} \right\rfloor \cdot b $$
The “leap years through some year” function in C amounts to a simple sum of quotients.
The implementation expands the quotient terms for clarity; they make debugging easier since each term appears separately in the debugger. The following unit tests verify the implementation.
Now that the leap library can compute the number of leap years in the range $[0,year)$, the number of days in that range becomes readily derived. Start by assuming $365$ days per year without adjustment. Apply the leap-through adjustment for all the preceding years. The result is the number of epoch days starting at year $0$ and ending at the given $year$.
The $+1$ in leap_day anchors the epoch so that the start of year $0$ maps to day $0$ while still counting year $0$ as a leap year. The closed-form term year * 365 + leap_thru(year - 1) counts $365$-day years plus leap days up to (but not including) the target year; because year $0$ itself is a leap year in the proleptically[^1] applied Gregorian model, that formula alone would put leap_day(0) at $-1$ and undercount every subsequent absolute day number by one. Adding $1$ fixes the baseline: leap_day(0) becomes $0$, leap_day(1) becomes $366$[^2] and differences between years remain correct because the constant offsets cancel in subtractions.
The leap_off function (see implementation below) normalises an arbitrary day offset relative to a given year into a canonical $(year, day_{of_{year}})$ pair where $0 \le day_{of_{year}} < days_{in_{year}}$. Its algorithm works as follows:
days = 365 + leap_add(year).year0 = year + quo_mod(day, days).quo.day += leap_day(year) - leap_day(year0).year to year0 and recompute days for that year.(struct leap_off){year, day} which is within the year’s bounds.Notes:
quo_mod uses Lua-style modulo semantics, so negative offsets jump the correct number of whole years in the negative direction.leap_day(year) cancel the constant epoch offset, ensuring exact rebasing regardless of the $+1$ anchor in leap_day.Notice that the day_off parameter is zero-based: the first day of the year is day $0$. This argument is a day offset relative to some year, not a one-based day of the month. This is an important distinction. The day is a zero-based offset in days compared to some base year. The function returns a struct leap_off containing the adjusted year and day; also an offset.
This is a key function for manipulating epoch days in embedded systems where no standard library exists. It allows day offsets to be normalised into year-and-day pairs that embedded applications can use for date calculations. Relative leap-year computations become straightforward, as in the following example.
Given some $year$ and some $1\le month\le12$ ordinal, computing the days in the month or the days of the year for that month becomes straightforward, and a date (year, month ordinal, day of month ordinal) from a year-day offset conversion falls out.
The year-day offset to date normalisation function applies the following algorithm for Converting a (year, day-of-year cardinal offset) pair into a (year, month ordinal, day-of-month ordinal) triple.
We can now translate year-day pairs to year-month-day triples.
The leapc (leap years in C) mini-library provides a lightweight, self-contained implementation of leap year calculations suitable for embedded systems with minimal dependencies. The implementation is fast and portable, relying only on basic integer arithmetic and division—no heavy floating-point operations or external libraries required. This makes it ideal for embedded firmware deployments where code footprint and computational efficiency matter.
The library operates at day-level granularity, which covers most calendar applications. Extending to timestamps is straightforward: divide a time value in seconds by $86400$ (seconds per day) to obtain a quotient and remainder. The remainder gives the time-of-day (seconds since midnight), and the quotient represents the epoch day.
To convert to a specific epoch—such as Unix time (1970-01-01) just subtract leap_day(1970) from the quotient. This flexibility is a key strength: the library itself is epoch-agnostic. Callers can anchor to any convenient year: leap_day(1900) for the Gregorian epoch, leap_day(2000) for Windows NT time, or any other reference point. This design avoids baking a single epoch assumption into the core algorithms.
The implementation handles positive years and works well for contemporary applications spanning 1970 through 9999. It assumes the proleptically-extended Gregorian calendar (applying modern leap rules backward to year 0). Handling negative years (B.C. dates) or extending beyond year 9999 would require minor adjustments but is not addressed in this version.
The complete implementation, test suite, and usage examples are available on GitHub. For embedded developers seeking a minimal, efficient leap year library, leapc offers a practical solution.
The library has limitations: it does not handle negative B.C. years. Nor does it address timezone considerations.
[^1]: The computations apply the Gregorian model back to Julian time. Pope Gregory XIII’s issued the papal bull in 1582.
[^2]: $365$ regular days plus the leap day of year $0$
1.9.8