floobydust wrote:
barrym95838 wrote:
Anyway, here's my untested mod for the BIOS [timekeeping]...
Okay, this looks quite interesting. I should have some free time later today to put this into the BIOS and give it a test. I'll report back with results once I have some test time completed. Thanks again for sharing this...
Another, potentially more efficient, way to keep time is to use an ever-increasing binary count of the number of seconds and fractions of a second from "some time long ago" (epoch). The archetype would be UNIX time, which is maintained as a 32 bit signed integer, type
time_t. In current versions of UNIX and Linux
time_t is a 64 bit unsigned integer, a change used to circumvent the "year 2038" problem associated with the 32-bit
time_t field. The epoch in both cases is
Thursday January 1 00:00:00.0 GMT 1970. Any date prior to the epoch is represented by a negative integer.
The UNIX/Linux kernel only increments the time fields, of which there are at least two: the time of day, which is traditionally set to the
time_t equivalent of
UTC+0 when the system comes up; and system uptime, which is initialized to zero at boot time. Both fields are incremented once per second (on systems using the MPU's HPET, there may be another field that records fractions of a second).
An important concept with this method of timekeeping is the kernel does not perform conversions between broken-down time (
BDT, which is human-readable) and the internal formats, which are binary integers. Format conversion is handled by user-space functions, e.g.,
mktime(), that are run whenever a conversion is needed. Functions such as
mktime() refer to an environment variable,
TZ, which represents the local time zone ("local" relative to the logged-in user). Hence the
UTC+0 internal format is compensated for the local time zone during the conversion. Additional compensation for daylight saving time (DST) is also available by reference to another time zone environment variable that describes the different between DST and standard time. This is done because there are some locales where the difference between standard time and DST isn't an even hour.
This intentional divvying of timekeeping responsibilities between kernel and user space means the kernel interrupt code used to maintain the internal time fields can be very succinct. For example, on an x86-64 machine running the 64 bit Linux kernel, incrementing the time-of-day field can be carried out via a single instruction, since the MPU can handle a 64 bit data type in one register. Even on a 65C02 machine, a 64-bit
time_t field can be managed with reasonably succinct code:
Code:
;increment 64-bit time_t with a 65C02...
;
dec jiffyct ;current jiffy IRQ count
bne l0000020 ;not time to update
;
lda #hz ;jiffy IRQ frequency (e.g., 100 Hz)
sta jiffyct ;reset
ldx #0 ;time field index
ldy #s_time_t ;time field size (8 bytes)
;
l0000010 inc tod,x ;bump time-of-day
bne l0000020 ;done w/time-of-day
;
inx
dey
bne l0000010 ;next
;
l0000020 ...program continues...
The above would be executed in the interrupt service routine (ISR) once per jiffy IRQ. The 64-bit
tod field, as well as the
jiffyct jiffy IRQ counter, would be maintained on page zero for best performance. Centiseconds may be derived from
hz - jiffyct, where
hz is the jiffy IRQ frequency.
In POC V1.1, I developed a timekeeping method that is similar to the UNIX archetype, but with some changes. As earlier noted, the archetype's 32-bit
time_t value is signed, which complicates conversion to/from
BDT. This was a choice forced on Ken Thompson by the PDP-11's native word type: a signed 32-bit quantity. Unfortunately, when Linux came about,
time_t had to remain signed in order to maintain compatibility with older systems. Even when
time_t was expanded to 64 bits it had to remain signed.
Over the years as I've developed large-scale database applications, I've came to the realization that most information encapsulated in databases doesn't use dates earlier than the 20th century (persons' dates-of-birth, for example), which suggested to me that a different epoch could be used along with an unsigned integer. Doing away with a signed integer would simplify the conversion process, as signed arithmetic is not efficiently implemented on the 6502 family. Accordingly, I moved the epoch to
Sunday October 1 00:00:00.00 UTC 1752, which corresponds to a
time_t value of zero. As all dates are unsigned, a non-zero
time_t value represents some point in time after the epoch. This particular epoch was chosen to avoid having to deal with September 1752, which month was truncated when the British Empire switched from the Julian calendar to the Gregorian one.
As well as the new epoch, I changed
time_t to a 48-bit unsigned integer, in which bits
0-39 are the number of seconds that have elapsed since the epoch and bits
40-47 are padding to align the field size to an even number of bytes—word alignment simplifies handling with the 65C816, and can be omitted with the 65C02. The maximum useful date that can be represented by a 40-bit
time_t field is
Friday December 31 23:59:59.99 UTC 9999, a range of 8247 years. Compare that to the original UNIX 32-bit
time_t, which has a useful range of a bit more than 136 years, half of which is prior to the epoch.
Conversion from the seconds count of the
time_t format to
BDT involves a series of operations on the
time_t field that successively extract each
BDT field. My algorithm is based upon a Julian date conversion algorithm that I modified and adapted:
Code:
p = S + 2393283
q = 4 * p / 146097
r = p - (146097 * q + 3) / 4
s = 4000 * (r + 1) / 1461001
t = r - 1461 * s / 4 + 31
u = 80 * t / 2447
v = u / 11
Y = 100 * (q - 49) + s + v → broken-down year (1752-9999)
M = u + 2 - 12 * v → broken-down month (1-12)
D = t - 2447 * u / 80 → broken-down day of month (1 to 31, depending on month and whether Y is a leap year)
In the above,
S is the
time_t date reduced to an integral multiple of 86,400, resulting in
S effectively representing the number of days that have elapsed since the epoch. As I implemented it, the reduction process extracts the hour, minutes and seconds value for the current day by iterative means.
The
BDT values are returned as binary integers. For processing convenience, I decided to make all
BDT fields 16 bits.
The algorithm I used to convert from
BDT to
time_t format is also based upon a Julian day algorithm, with adaptations for the date range and epoch:
Code:
m1 = (M - 14) / 12
y1 = Y + 4800
S = 1461 * (y1 + m1) / 4 + 367 * (M - 2 - 12 * m1) / 12 - (3 * ((y1 + m1 + 100) / 100)) / 4 + D - 2393284
The input date is in
D (day-of-month, same range as
D in the previous algorithm),
M (month, 1-12) and
Y (year, 1752-9999).
S is the resulting
time_t value.
S is undefined if nonsensical input values are provided—the function calling the conversion is responsible for trapping garbage input.
The time-of-day can be added to the
S field as follows:
Code:
tm = S + HOUR * 3600 + MIN * 60 + SEC
where the time-of-day value represented by
HOUR,
MIN and
SEC is 24-hour format (00:00:00-23:59:59), and
tm is the final
time_t value. Again, nonsensical values will produce undefined results.
All terms in the above algorithms are positive integers and arithmetic operations follow the standard rules of algebraic precedence. Due to the range that the
time_t date encompasses, arithmetic operations must be 64 bit to avoid overflow during multiplication. The quotient of each division operation is as if the
floorl() C function has been applied—same as
int(x) in BASIC.
64 bit addition and subtraction on the 65C02 is straightforward. 64 bit multiplication and division is not as trivial to implement but can be accomplished by scaling up existing algorithms. Although the math won't be very speedy, it only has to be carried out when a conversion is needed, not as a matter of routine kernel processing.
Food for your thought.
Login
Register
FAQ
Search
