Page 3 of 4
Re: CALENDRIC & TEMPORAL PROGRAMMING
Posted: Sun Dec 19, 2021 4:19 am
by unclouded
Thank you for writing all this BDD. A fascinating subject, exhaustively documented and elegantly explained. Bravo!
Re: CALENDRIC & TEMPORAL PROGRAMMING
Posted: Sun Dec 19, 2021 6:22 am
by BigDumbDinosaur
Thank you for writing all this BDD. A fascinating subject, exhaustively documented and elegantly explained. Bravo!
Thanks! Dunno about the elegant part, but I tried to get the speeling and gramurr korect. 
CALENDRIC & TEMPORAL PROGRAMMING: Algorithms
Posted: Mon Jan 03, 2022 5:17 am
by BigDumbDinosaur
Following a long period of dormancy, I have resumed working on this topic and should have something ready to post in a few days.
Nearly three years after I posted that, I really do have some new material. 
Past discussion has been on the principle of maintaining the time-of-day and calendar date as an integer count of the number of seconds that have elapsed from a distant point in the past referred to as the “epoch.” This timekeeping method is conventionally referred to as “POSIX time” or “UNIX time,” and is in widespread use. The following discussion will elaborate on methods for converting between human-readable and machine-readable time formats.
On UNIX-like systems, the operating system kernel only works with the machine-readable date and time, which is often referred to as time_t (pedantically speaking, time_t defines the data type, not the data itself). All internal timekeeping operations, e.g., time-stamping directories and files when modified, are performed using only the date and time as defined by time_t. The current time_t value is always assumed to be set to coordinated universal time (UTC or “Zulu” time). The kernel timekeeping functions know nothing about time zones or daylight saving time (DST, aka “summer time”).
An issue with the original UNIX timekeeping method, which defined time_t as a 32-bit signed integer, is its limited range. The maximum positive value that can be represented with such a data type is 2^31. Incrementing past 2^31 will result in time_t becoming a negative value. As UNIX and Linux both define the epoch as January 1 00:00:00 GMT 1970, the date will regress from January 19, 2038 to December 13, 1901, creating what is referred to as the “year 2038” problem. This problem has been addressed by expanding time_t to a 64-bit signed integer in modern implementations, producing a usable range of billions of years...as well as an incompatible time_t type.
In my reimagining of POSIX time, I use an unsigned integer in place of the POSIX time_t format. Among other things, this change facilitates the use of four-function integer arithmetic in performing conversions. Since my notion of time is unsigned and doesn’t conform to the POSIX data type in size, I decided to refer to it as “binary sequential time” or BST.¹ It works on the same principle as POSIX time, but without the need for signed arithmetic (with one exception).
As previously discussed, BST is updated at periodic intervals by code within the kernel’s interrupt request service routine (ISR) while responding to a jiffy IRQ generated by the time base, which is typically a hardware timer. Since BST is just an integer, updating it requires little code and few MPU cycles, even with a 65C02’s byte-at-a-time processing. Kernel calls are used to fetch or set BST, but no kernel calls exist to convert between human- and machine-readable time formats. During system startup, it is customary for the real-time clock (RTC) hardware to be read and its output converted to BST format to set the system’s notion of the current date and time.
The human-readable date and time format is referred to by POSIX as “broken-down time” (BDT), which term I continue to use. The date in BDT is assumed to conform to the rules of the civil Gregorian calendar. Conversion between BDT and BST is handled by library functions that are not part of the kernel and are called as needed. These functions understand time zones and DST, and hence are able to produce a BDT that has been “localized.”
Interesting issues can arise with the use of the Gregorian calendar. The first official implementation was on the day following October 4, 1582 in the Julian calendar. At that time, the date was advanced to October 15 to compensate for Julian calendar drift relative to the vernal equinox. Only states that were politically aligned with the Roman Catholic Church (especially the Dicio Pontificia) made the switch at that time. Other nations didn’t switch until much later. For example, the British Empire didn’t adopt the Gregorian calendar until September 3, 1752, following “Chesterfield’s Act,” which also legally defined the start of the year as January 1.² As compensation for Julian calendar drift, September had to lose 11 days:
Code: Select all
September 1752
——————————————
Su Mo Tu We Th Fr Sa
1 2 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
Due to the above mangling of September, as well as the fact that the Gregorian calendar went into effect some 1500 years after the start of Anno Domini (aka the “Common Era”), I had a dilemma in defining the epoch, as well as in devising conversion algorithms.
UNIX-like conversion supports the notion of a “proleptic Gregorian calendar,” which refers to dates prior to October 15, 1582—such dates technically have never existed in the Gregorian calendar. When I first embarked on this little programming exercise, I considered supporting the proleptic calendar. However, doing so would have meant having to muck around with September 1752. The resulting corner-case complicated conversion too much. So I defined Sunday October 1 00:00:00.00 GMT 1752 as the epoch, corresponding to BST = 0.
A time zone definition includes an offset in seconds (defined by the variable TZD) that must be added to local time to get the UTC equivalent. If the offset is non-zero and positive, the time zone is west of UTC. On the other hand, if the offset is negative, the time zone is east of UTC. This rule implies that TZD must be a signed integer.
In order to handle the full range of possible time zone offsets, I have defined TZD as a 32-bit signed integer, using twos-complement form. For example, the standard time zone in which I live is UTC - 6. Therefore, TZD would be 21,600 ($00005460, equal to 6 × 3600). As another example, New Zealand’s standard time zone is UTC + 12. Therefore,TZD would be -43,200 or $FFFF5740.
Along with a TZD for standard time, there may be a separate one for when a locale observes DST—I refer to said variable as DTZD. If DST is observed then some additional information is needed to tell the conversion functions when DST is in effect—a time zone database is typically used for that purpose.
In POSIX-compliant systems, broken-down time (BDT) is conventionally defined in ANSI C as a data structure referred to as tm. The fields in tm are:
Code: Select all
tm_sec - seconds (0-59)
tm_min - minutes (0-59)
tm_hour - hour (0-23)
tm_mday - day of the month (1-31, depending on month and year)
tm_mon - month (1-12)
tm_year - year (1901-2038 if BST is a 32-bit integer)
tm_wday - day of week (0-6, with Sunday being 0)
tm_yday - day of the year (0-365 in common years; 0-366 in leap years)
tm_isDST - daylight saving time flag; see text
In C, all fields are defined as unsigned int, which type is typically 16 bits in size—that size is required to accommodate the full range of tm_year and tm_yday.
The above structure is readily transferable to 6502 assembly language:
Code: Select all
tm_sec =0 ;seconds : 0-59
tm_min =tm_sec+s_int ;minutes : 0-59
tm_hour =tm_min+s_int ;hour : 0-23
tm_mday =tm_hour+s_int ;day-of-month: 1-31
tm_mon =tm_mday+s_int ;month : 1-12
tm_year =tm_mon+s_int ;year : 1752-9999
tm_wday =tm_year+s_int ;day-of-week : 1-7
tm_yday =tm_wday+s_int ;day-of-year : 1-366
tm_isdst =tm_yday+s_int ;DST flag...
;
; x0000000x0000000
; | |
; +———————+——————————> 0: standard time in effect
; 1: daylight saving time in effect
;
s_tm =tm_isdst+s_int ;size of tm structure
In the above, s_int is 2.
In the POSIX definition of the tm structure, tm_isdst is set to 0 to indicate DST is not in effect, set to a positive value if DST is in effect, or set to a negative value to indicate that the DST status is unknown. To this day, I don’t understand the point of the “unknown” definition—either a locale observes DST or it doesn’t. For convenient testing in assembly language, I changed tm_isdst so bits 7 and 15 are set when DST is in effect.
Refocusing on BST, I defined it as a 48-bit, unsigned integer in customary 6502 little-endian format. 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. Such alignment simplifies handling with the 65C816 using 16-bit operations, but may be omitted with the 65C02 if memory consumption is a concern—of course, doing so makes the 65C02 version of BST partially incompatible with the 65C816 version.
Although my reimagining of POSIX time into BST gives a theoretical date range of approximately 17,420 years before overflow, the conversion functions that I have developed falter beyond Friday December 31 23:59:59.99 UTC 9999, which is 8247 years after the epoch and 7977 years from the date of this post. If I’m still upright with a pulse in 9999 and someone asks, I’ll revisit the algorithm.
Conversion from BST to BDT involves a series of operations that successively extract each BDT field. My algorithm is loosely based upon a Julian date conversion algorithm, but implementable with integer arithmetic (Julian dates, which are used by astronomers and are unrelated to the aforementioned Julian calendar, contain fractional content—the beginning of a Julian day is actually at noon 
). In the following equations, all terms are unsigned integers. Due to the range that the BST date encompasses, 64-bit arithmetic operations are de rigueur to avoid overflow. The quotient of each division operation is as if the floorl() C function has been applied to a positive value. The usual algebraic precedence rules apply.
Code: Select all
p = (BST + 2393283) ÷ 86400
q = 4 × p ÷ 146097
r = p - (146097 × q + 3) ÷ 4
s = 4000 × (r + 1) ÷ 1461
t = r - 1461 × s ÷ 4 + 31
u = 80 × t ÷ 2447
v = u × 11
Y = 100 × (q - 49) + s + v (broken-down year)
M = u + 2 - 12 × v (broken-down month)
D = t - 2447 × u ÷ 80 (broken-down day-of-month)
The above returns the broken-down calendar date—trivial code and a look-up table may be used to convert the month value to a month name.
The following steps break down the time-of-day:
Code: Select all
ds = BST ÷ 86400 (elapsed days since epoch)
ds = ds × 86400 (elapsed seconds to start of current day)
ds = BST - ds (elapsed seconds since midnight of current day)
H = ds ÷ 3600 (broken-down hour)
ds = ds - H × 3600 (elapsed seconds to broken-down hour)
M = ds ÷ 60 (broken-down minutes)
S = ds - M ÷ 60 (broken-down seconds)
The algorithm I devised to convert from BDT to BST is also loosely based upon Julian dates. It uses the notion that the first month of the year is March, not January, which simplifies the handling of February:
Code: Select all
y = Y — ((14 — M) ÷ 12)
m = ((M + 12 × ((14 — M) ÷ 12) — 3) × 153 + 2) ÷ 5
y1 = y × 365
y2 = y ÷ 4
y3 = y ÷ 100
y4 = y ÷ 400
BST = (D + m + y1 + y2 — y3 + y4 — 2393284) × 86400
The input date to the above is in D (day-of-month, same range as D in the previous algorithm), M (month, 1-12) and Y (year, 1752-9999). Garbage in will produce garbage out—the function calling the conversion is responsible for qualifying input values. If you decide to try out this algorithm, you can see the garbage-in-garbage-out “feature” in action by feeding it February 29, 2023 and converting the resulting BST back to BDT.
The time-of-day can be added to BST as follows...
Code: Select all
BST = BST + 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).
The math required to perform the conversions isn’t real speedy—mostly because the 65xx family has no multiply or divide instructions, but it only has to be carried out when a conversion is needed. During the initial testing of the conversion algorithms, I was using an old math library I had written when I was still running the 65C816 in emulation mode, which, of course, couldn’t use 16-bit registers. Following the development of my native-mode library, which does all arithmetical operations with the accumulator set to 16-bits, I realized an approximate 75 percent speedup in the time required to convert BST to BDT, which is the slower of the two conversion functions.
So far, my calendric stuff is in library form and requires INCLUDE files and macros, along with the 64-bit, integer math library, in order to be integrated with a program. If someone expresses an interest, I could cobble together a package that I can post here.
————————————————————
¹In private conversation with someone concerning this topic, I used the term “binary sequential time” (BST) to refer to what I’ve previously described as “UNIX” or “POSIX” time. My timekeeping implementation intentionally doesn’t conform to the POSIX time_t definition, so I thought it would be better to devise a new term for the 48-bit integer that represents the date and time.
————————————————————
²Chesterfield’s act didn’t explicitly refer to the Gregorian calendar, as the British monarchy and the Roman Catholic church weren’t exactly on speaking terms at the time. So the act’s language was carefully written to give the appearance that the revised calendar was an original design, not a copy of something devised by the “Papists.”
————————————————————
EDIT: I finally got around to fixing some typos and other errors in this post that I had noted long ago.
Re: CALENDRIC & TEMPORAL PROGRAMMING
Posted: Mon Jan 03, 2022 7:46 am
by BillG
Re: CALENDRIC & TEMPORAL PROGRAMMING
Posted: Mon Jan 03, 2022 9:43 am
by BigEd
The first day of the year was also redefined in 1752, or to be careful, on the day after 31st December 1751. (Scotland made this change much earlier.) I'm sure I've seen some reference to Old Style and New Style dates in some nineteenth century literature but I can't find it.
Wikipedia.
(Edit: old and new style dates are
apparently concealed (as a hidden puzzle for the careful reader) in Austen's
Emma, which takes place in 1814/15 - some time after the official calendar change.)
(Edit: Some people in Ulster and Appalachia held on to Old Christmas into the twentieth C,
it seems.)
Re: CALENDRIC & TEMPORAL PROGRAMMING
Posted: Mon Jan 03, 2022 9:48 am
by BigDumbDinosaur
Re: CALENDRIC & TEMPORAL PROGRAMMING
Posted: Mon Jan 03, 2022 9:57 am
by BigDumbDinosaur
The first day of the year was also redefined in 1752, or to be careful, on the day after 31st December 1751. (Scotland made this change much earlier.) I'm sure I've seen some reference to Old Style and New Style dates in some nineteenth century literature but I can't find it.
Wikipedia.
(Edit: old and new style dates are
apparently concealed (as a hidden puzzle for the careful reader) in Austen's
Emma, which takes place in 1814/15 - some time after the official calendar change.)
Old style calendars are primarily of historical interest. My presentation was about a practical date-and-time reckoning method that works with the current calendar.
As for the calendric gyrations that occurred in the UK during the 18th century, they were why I chose October 1, 1752 as the epoch.
Re: CALENDRIC & TEMPORAL PROGRAMMING
Posted: Mon Jan 03, 2022 1:36 pm
by BillG
I was wondering how the POSIX/UNIX/Linux world dealt with them.
Would a file created at exactly midnight today show the same on all systems? Unlikely since leap seconds can be added whenever "the science" decides they are needed.
Re: CALENDRIC & TEMPORAL PROGRAMMING
Posted: Mon Jan 03, 2022 7:20 pm
by BigDumbDinosaur
I was wondering how the POSIX/UNIX/Linux world dealt with them.
Would a file created at exactly midnight today show the same on all systems? Unlikely since leap seconds can be added whenever "the science" decides they are needed.
Adding or, more rarely, subtracting a leap second is an ad hoc sort of thing that isn't readily programmed. In fact, under current timekeeping policies, the maximum period of notification for a pending leap second is six months.
In the case of Linux, UNIX, Window$, etc., access to a stratum-2 or stratum-3 Internet time server would be the most reliable means of dealing with leap seconds. Those time servers will “know” about a leap second within microseconds of one being inserted into or removed from the time stream.
Re: CALENDRIC & TEMPORAL PROGRAMMING
Posted: Tue Jan 04, 2022 8:34 am
by BigEd
There is perhaps a possible and interesting wrinkle. Positive leap seconds (the only kind we've yet seen used) make for a 61 second minute, and therefore a slightly longer day and a slightly longer year. So, if a program aimed to report differences by assuming days are always of standard length, it could end up with an out-by-one compared to a program which had a record of the historical leap seconds. That is, if there are any such programs.
It does feel like treating all minutes as being 60 seconds is not going to get you in trouble, except for astronomical purposes.
There's a great deal more scope for fun and games when you try to account for summer time and time zones. Both of them have definitions which change as legislation changes.
There was also the amusing period during my working life when BST was taken to be Bering Strait Time rather than British Summer Time, by at least some software, giving us both a time and a date confusion.
Edit: another gotcha, perhaps slightly more likely for homebrew setups, is that GPS time has no leap seconds, instead having an offset from UTC, which is presently 18 seconds AFAICT. GLONASS, Galileo, and BeiDou are potentially all different, although I think presently Galileo and GPS have the same tactics.
Edit: also, some NTP sources will smear a leap second, to avoid a sudden change, which means a period of many hours when various NTP sources may differ by up to a second.
Re: CALENDRIC & TEMPORAL PROGRAMMING
Posted: Tue Jan 04, 2022 8:47 am
by GARTHWILSON
Also interesting is that quite a few countries didn't adopt the Gregorian calendar until the 20th century. (What made me think of it was that our athletes were almost late reaching Greece for the Olympics in 1896, as they missed the part about Greece still not being on the same calendar yet. Greece got onboard in 1923, according to https://en.wikipedia.org/wiki/Adoption_ ... n_calendar ).
Re: CALENDRIC & TEMPORAL PROGRAMMING
Posted: Tue Jan 04, 2022 10:02 am
by BigDumbDinosaur
There is perhaps a possible and interesting wrinkle. Positive leap seconds (the only kind we've yet seen used) make for a 61 second minute, and therefore a slightly longer day and a slightly longer year.
Since the earth's axial rotation is irregular and also slowing down, the solar day is lengthening at a variable rate of around 1.5 milliseconds per century. So we can expect leap seconds to be a permanent part of the timekeeping landscape.
So, if a program aimed to report differences by assuming days are always of standard length, it could end up with an out-by-one compared to a program which had a record of the historical leap seconds. That is, if there are any such programs.
In practice, I've observed from years of writing database software that that isn't likely to be a problem. When a leap second is needed, it is inserted at 23:59:59. Since database searches seldom narrow down to an exact moment in time, the seeming day drift doesn't affect mosts searches.
Leap seconds are used to correct the difference between observed solar time and international atomic time (TAI). TAI, of course, is extremely stable—current cesium-beam standards have no known drift, whereas observed solar time fluctuates. Since UTC is derived from TAI, there is a tendency for UTC to run a little fast relative to solar time.
Ultimately, the Gregorian calendar will start to get out of sync with the seasons, just as the Julian calendar did and a new definition of the length of a day and a new set of leap year rules will be required.
It does feel like treating all minutes as being 60 seconds is not going to get you in trouble, except for astronomical purposes.
I suppose there are some scientific activities where being off a femtosecond or two might give you grief.
There's a great deal more scope for fun and games when you try to account for summer time and time zones. Both of them have definitions which change as legislation changes.
Here in the USA, the daylight saving (summer) time (DST) mess is just that. Individual states are not legally required to observe DST, but if they do, they are obligated to use the national definition of when DST starts and ends. That definition has change three times in my lifetime, the last one being in 2007.
Re: CALENDRIC & TEMPORAL PROGRAMMING
Posted: Tue Jan 04, 2022 10:24 am
by BigEd
Indeed...
...we can expect leap seconds to be a permanent part of the timekeeping landscape.
! One alternative is to use leap hours, very much less often. There are pros and cons, and it's a
current topic of (slow) discussion:
The scientific community has so far failed to reach an agreement on this topic.
In 2003, a meeting named “ITU-R SRG 7A Colloquium on the UTC timescale” took place in Torino, Italy, where it was suggested that time be decoupled from the Earth’s rotation and leap seconds be abolished. No decision was reached.
In 2005, US scientists proposed to eliminate leap seconds and replace them with leap hours. The proposal was criticized for its lack of consistent public information and adequate justification.
In 2012, delegates of the World Radiocommunication Assembly in Geneva, Switzerland, decided once more to postpone the decision to abolish leap seconds and scheduled a new vote for 2015.
In 2015, the decision was again deferred to 2023.
Edit: another amusing phenomenon, "
Leap seconds: Causing Bugs Even When They Don’t Happen" which also contains a hint that we might yet see the first negative leap second within a decade.
Re: CALENDRIC & TEMPORAL PROGRAMMING
Posted: Sun Mar 12, 2023 1:03 am
by jgharston
At
DayOfTheWeek there is a useful snippet of 6502 code to calculate the day of the week for an 8-bit year offset from 1900. As 1900 is not a leap year it only gives correct results from 01-March-1900 onwards. Some time ago I tweeked the code to extend it back to 01-Jan-1900.
I also ported the code to various other CPUs. While snowed in over the last few days I've been tidying up my documentation and doing a few bits of optimisation. The results so far are at:
Dates.
On some other CPUs the 1900 tweek is fairly simple (especially if the registers are larger than 8 bits). On the 6502 I worked out three different methods, all of which took six bytes, so in the published code I used the tweek that places it logically in the flow of the code.
Re: CALENDRIC & TEMPORAL PROGRAMMING
Posted: Sun Mar 12, 2023 6:00 am
by BigDumbDinosaur
At
DayOfTheWeek there is a useful snippet of 6502 code to calculate the day of the week for an 8-bit year offset from 1900. As 1900 is not a leap year it only gives correct results from 01-March-1900 onwards. Some time ago I tweeked the code to extend it back to 01-Jan-1900.
Have you looked at this?