[bug #44327] eu_dst() is broken

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

[bug #44327] eu_dst() is broken

Kevin Cuzner-2
URL:
  <http://savannah.nongnu.org/bugs/?44327>

                 Summary: eu_dst() is broken
                 Project: AVR C Runtime Library
            Submitted by: None
            Submitted on: ven. 20 févr. 2015 21:27:48 UTC
                Category: Library
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Header files
                  Status: None
        Percent Complete: 0%
             Assigned to: None
        Originator Email: [hidden email]
             Open/Closed: Open
         Discussion Lock: Any
                 Release: Any
           Fixed Release: None

    _______________________________________________________

Details:

The function eu_dst(), defined in include/util/eu_dst.h, is intended to
implement the European daylight saving rules. There is an error at the
end of the function, where the comparison between the current day of the
month and the day of the last Sunday is reversed. The error is repeated
four times. This makes the function be almost always wrong in March and
October. There is also an off-by-one error earlier in the function:
whenever the last Sunday is the 25th, the function believes it's the
32nd.

I noticed those errors while trying to benchmark my own implementation
of eu_dst() against the one provided by avr-libc. Then, rather than
fixing the broken function, I suggest replacing it with my
implementation:

    int eu_dst(const time_t * timer, int32_t * z)
    {
        uint32_t t = *timer;
        if ((uint8_t)(t >> 24) >= 194) t -= 3029443200U;
        t = (t + 655513200) / 604800 * 28;
        if ((uint16_t)(t % 1461) < 856) return 3600;
        else return 0;
    }

This version is based on the fact that the European DST function is
almost periodic. Actually, it is as close to periodic as possible given
the constraint that the transitions are only allowed on Sundays at 01:00
UTC. Since this constraint is also periodic, this allows for a compact
arithmetic solution.

I tested my implementation for correctness on my PC against the system's
localtime(), for every full hour between the epoch (2000-01-01) and the
end of time (2136-02-07). I also tested it on an Arduino Uno
(ATmega328P) against a precomputed table of all the transition times,
both at the transition and the second right before.

In terms of size, this function compiles 52% smaller than the one
provided by eu_dst.h. If we account for the dependencies, it is 75%
smaller (204 vs. 826 bytes). It is also 3 times faster:
about 1250 — 1280 cycles versus 3300 – 4500.

Regards,

Edgar Bonet.




    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/bugs/?44327>

_______________________________________________
  Message posté via/par Savannah
  http://savannah.nongnu.org/


_______________________________________________
AVR-libc-dev mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/avr-libc-dev
Reply | Threaded
Open this post in threaded view
|

[bug #44327] eu_dst() is broken

Kevin Cuzner-2
Follow-up Comment #1, bug #44327 (project avr-libc):

The current algorithm misfires if the month starts on a Thursday, in which
case d is calculated to be 31, when it should have been 24.
Adding the following after line 91 fixes it:

if(d==31) d=24;



it does impact the elegance of the algorithm somewhat, and probably
performance, but only on months that start on a thursday ;)

I have attached a python script that runs the algorithm 31*7 times, simulating
each day of a month (0-30) being each day of the week (0-6), the script prints
out an error if any calculation doesn't match the hard-coded truth table.

~Mark

(file #47647)
    _______________________________________________________

Additional Item Attachment:

File name: dstCheck.py                    Size:1 KB
    <https://savannah.nongnu.org/file/dstCheck.py?file_id=47647>



    _______________________________________________________

Reply to this item at:

  <https://savannah.nongnu.org/bugs/?44327>

_______________________________________________
  Message sent via Savannah
  https://savannah.nongnu.org/


_______________________________________________
AVR-libc-dev mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/avr-libc-dev