Effizient Datum und Uhrzeit vergleichen

[Thomas (Gast)]

Ich suche nach einem Weg zwei Timestamps effizient miteinander zu 
vergleichen.

Ich verwende einen Atmega32
Habe folgende Struktur um einen Timestamp abzubilden:

  typedef struct 
  {
                uint16_t          u16_Year :12;
                enum e_months     e_Month  :4;
                uint8_t           u8_Day   :5;
                uint8_t           u8_Hour  :5;
                uint8_t           u8_Minute:6;
                uint8_t           u8_Second:6;
                uint8_t           u8_Unused:3;
  }Clock_SType_TimeAndDate;

nun möchte ich zwei Variablen diesen Typs miteinander vergleichen um 
herauszufinden ob der Timestamp kleiner, gleich oder größer ist.

Wie kann ich das effizient anstellen?
Ich komme bisher nur auf unbefriedigende Ideen, z.B.:

- Union über diese Struktur und uint64_t und anschließend uint64_t 
Variable vergleichen -> Klappt wegen Little Endian nicht. Meines 
Erachtens wäre dies die effizienteste Lösung. Komme nur nicht mit dem 
Little Endian Format zurecht.

- Verschachtelte If Abfrage (zu viele Ifs und scheint mir ineffizient)

- per Schiebeoperator die Elemente der Struktur im richtigen Abstand 
aneinanderhängen und die entstehende 64Bit Zahl dann miteinander 
vergleichen. (auch ineffizient)

Habt ihr eine Idee?

[Peter II (Gast)]

Thomas schrieb:
> Habt ihr eine Idee?

warum nicht einfach memcmp?

es hat übrigens ein Grund warum PC die Zeit nur als ein int32 speichern, 
dann hat man das Problem nicht mehr.

[Huhu (Gast)]

Thomas schrieb:
> Habt ihr eine Idee?

Das ganze in Unixzeit umrechnen (dafür gibts fertige Funktionen in jedem 
System), dann kannst du ganz bequem vergleichen (gleich/größer/kleiner).

[B. S. (bestucki)]

Thomas schrieb:
> - Verschachtelte If Abfrage (zu viele Ifs und scheint mir ineffizient)

Entweder das, oder die Zeit in Unixzeit umrechnen. Ist es denn zu 
ineffizient oder glaubst du das nur? Wie viele tausend Mal pro Sekunde 
musst du die Uhrzeit vergleichen?

Noch was:
Bitfelder sind nach Standard nur für bool, int und unsigned int 
definiert, die meisten Compiler unterstützen aber auch andere Typen.

[(prx) A. K. (prx)]

Peter II schrieb:
> warum nicht einfach memcmp?

Solche Lösungen funktionieren nur, wenn man sicher sein kann, dass alle 
unbelegten Bits in der Struktur den gleichen Wert haben. Überdies sind 
sie abhängig von der Bit- und Byteorder.

[Peter II (Gast)]

A. K. schrieb:
> Solche Lösungen funktionieren nur, wenn man sicher sein kann, dass alle
> unbelegten Bits in der Struktur den gleichen Wert haben. Überdies sind
> sie abhängig von der Bit- und Byteorder.

wenn man nur auf "gleich" vergleicht, spielt die Byteorder kaum eine 
rolle.


und gegen unbelegte bits hilft beim anlegen ein memset.

[Erwin D. (Gast)]

Peter II schrieb:
> wenn man nur auf "gleich" vergleicht, spielt die Byteorder kaum eine
> rolle.

Thomas schrieb:
> nun möchte ich zwei Variablen diesen Typs miteinander vergleichen um
> herauszufinden ob der Timestamp kleiner, gleich oder größer ist.
                                  ---------------------------

;-(

[(prx) A. K. (prx)]

Wenn das unterste Bit der Sekunde verzichtbar ist, dann kommt auch das 
FAT Timestamp-Format in Frage. Das packt alle Info in 32 Bits (2x16). 
Wenn man das nicht als Bitfeld realisiert, sondern mit Shifts, dann ist 
es zudem unabhängig von Bit/Byteorder.

[Peter II (Gast)]

wie ist das überhaupt mit dem byteorder bei solchen bitfields?


 uint16_t          u16_Year :12;

immerhin ist das uint16_t gar kein uint16_t.

[Rolf M. (rmagnus)]

Was heißt denn effizient? Wieviele Millionen solcher Vergleiche sollen 
den pro Sekunde stattfinden?

Generell scheint mir die Strukt eher ineffizient in der Benutzung zu 
sein, weil durch die Aufteilung sehr viel Bitgeschupse nötig wird. Und 
warum gerade 41 Bits insgesamt?
Ich würde auch sowas wie einen Unix-Timestamp vorschlagen und den dann 
nur zur Ausgabe umrechnen.

[Fritz G. (fritzg)]

Ich hätte auch gesagt in Unixzeit umrechnen. Allerdings braucht das 
viele Multiplikationen.
Wenn du verschachtelte If Abfragen nimmst in der Reihenfolge 
Jahr/Monat/Tag... dann kannst du ev. frühzeitig aus dem if Block 
rausspringen. Rechenzeitmäßig dürfte es um einiges schneller sein, als 2 
structs in Unixzeit umzurechnen.

[(prx) A. K. (prx)]

Peter II schrieb:
> wie ist das überhaupt mit dem byteorder bei solchen bitfields?

Sinnvollerweise orientiert sich die Bitorder in Bitfeldern an der 
Byteorder. Little-Endians fangen also in den Worten rechts an, 
Big-Endians links. In IBMs Prozessoren hat das höchstwertige Bit daher 
die Nummer 0.

Motorola lief in diese Falle, als sie bei der Big-Endian 68000 trotzdem 
die Bits von rechts nach links nummerierten. Als sie bei der 68020 
Bitfeld-Befehle hinzufügten merkten sie, dass das nicht funktioniert. 
Und drehten bei denen die Bitnummerierung um.

[Peter II (Gast)]

Fritz G. schrieb:
> Rechenzeitmäßig dürfte es um einiges schneller sein, als 2
> structs in Unixzeit umzurechnen.

wenn er intern direkt mi Unixzeit arbeitet, dann muss er es nur für die 
anzeige umrechnen. Dafür werden die vergleiche einfacher und das 
incrementieren der Zeit.

[Fritz G. (fritzg)]

Es ist die Frage, wie diese Struktur überhaupt zusammenkommt. Zählst du 
jedesmal händisch eine Sekunde dazu? Dann kannst du eine Variable 
zusätzlich für die Sekunden seit Programmstart nehmen, diese jede 
Sekunden miterhöhen und brauchst nur diese zu vergleichen. Praktisch 
eine Unixzeit für Arme.

[(prx) A. K. (prx)]

Peter II schrieb:
> wenn er intern direkt mi Unixzeit arbeitet, dann muss er es nur für die
> anzeige umrechnen. Dafür werden die vergleiche einfacher und das
> incrementieren der Zeit.

Je nach einzukalkulierendem Alter, sowohl der Technik als auch dem 
eigenen, sollte man dabei freilich im Auge behalten, dass bei 32 Bits 
dann im Jahr 2038 das Ende der Welt erreicht ist.

[Peter II (Gast)]

A. K. schrieb:
> Je nach einzukalkulierendem Alter, sowohl der Technik als auch dem
> eigenen, sollte man dabei freilich im Auge behalten, dass bei 32 Bits
> dann im Jahr 2038 das Ende der Welt erreicht ist.

er muss ja nicht bei 1970 anfangen.

[B. S. (bestucki)]

A. K. schrieb:
> Je nach einzukalkulierendem Alter, sowohl der Technik als auch dem
> eigenen, sollte man dabei freilich im Auge behalten, dass bei 32 Bits
> dann im Jahr 2038 das Ende der Welt erreicht ist.

Wenn man einen uint32_t benutzt, kann man das Ende bis 2106 
hinauszögern.

[Axel S. (a-za-z0-9)]

Thomas schrieb:

> Habe folgende Struktur um einen Timestamp abzubilden:
>
>

>   typedef struct
>   {
>                 uint16_t          u16_Year :12;
>                 enum e_months     e_Month  :4;
>                 uint8_t           u8_Day   :5;
>                 uint8_t           u8_Hour  :5;
>                 uint8_t           u8_Minute:6;
>                 uint8_t           u8_Second:6;
>                 uint8_t           u8_Unused:3;
>   }Clock_SType_TimeAndDate;
>

Was muß man denn geraucht haben, um auf sowas zu kommen?
<kopfschüttel>

> nun möchte ich zwei Variablen diesen Typs miteinander vergleichen um
> herauszufinden ob der Timestamp kleiner, gleich oder größer ist.
> Wie kann ich das effizient anstellen?

Indem du Bitfelder vermeidest.

Ansonsten kann der AVR mit seiner 8-Bit ALU sowieso immer nur 8 Bit auf 
einen Rutsch vergleichen. Jegliches Gecaste nach uint64_t u.ä. bringt 
also überhaupt gar nichts. Denn auch zwei uint64_t muß die ALU von links 
nach rechts byteweise vergleichen (von links nach rechts, um außer 
Gleichheit auch größer und kleiner korrekt zu erkennen). Dann kannst du 
genauso gut auch gleich komponentenweise vergleichen. Außer natürlich 
daß das bei Verwendung von Bitfeldern auch Bitschieberei beinhaltet.

Andererseits müßte man auch mal fragen, worin dieser Eifer auf besonders 
effizienten Vergleich begründet liegt. Vermutlich wieder nur ein Fall 
von vorauseilender Optimierung.

Auch der Hinweis auf UNIX Timestamps kam vollkommen zurecht. Nicht nur 
ist diese Form der Codierung simpelst zu vergleichen, sie ist auch 
maximal speichereffizient.

[Rurik (Gast)]

Mit 32 Bit = 4 Byte lässt sich jedes Jahr in ms auflösen
und mit weiteren 2 Byte jedes geschichtlich vorstellbare
Jahr von den Neandertalern bis in 30.000 Jahren darstellen.
Da droht so schnell kein Y2K.

Noch schöner: Das Jahr NULL gibt es nicht!
Also: Year = NULL ist eindeutig NOT A DATE. :-)

Schon klar - ist keine Allerwelts-Konvention, also will dafür
niemand den Rechner für eine ms zum Umrechnen beschäftigen.
Auch wenn damit jeder Vergleich zur µs-Sache wird.

Die Astronomen sind da mit ihrem Julianischen Datum schlauer.
Darum fielen die auch weder auf Y2K, noch auf das "Erfundene
Mittelalter" rein...

[B. S. (bestucki)]

Rurik schrieb:
> Mit 32 Bit = 4 Byte lässt sich jedes Jahr in ms auflösen

Ne, nur 49.7 Tage.

[Rolf M. (rmagnus)]

Be S. schrieb:
> Rurik schrieb:
>> Mit 32 Bit = 4 Byte lässt sich jedes Jahr in ms auflösen
>
> Ne, nur 49.7 Tage.

Ist deshalb nicht auch genau nach dieser Zeit Windows 98 immer 
abgestürzt?

Aber es sind ja hier eh nur Sekunden gefordert. Dann reicht es für gut 
136 Jahre - länger als die Lebenserwartung des Homo Sapiens.

[Hannes J. (Firma: _⌨_) (pnuebergang)]

> Die Astronomen sind da mit ihrem Julianischen Datum schlauer.

Ein bisschen was an der Waffel haben die auch. Beim julianischen Datum 
ist der Übergang zwischen zwei Tagen nicht um Mitternacht, sondern um 12 
Uhr Mittags. Die haben 0,5 Tage Offset.

Trotzdem kann man die Formeln zur Umrechnung zwischen Kalenderzeit und 
julianischem Datum auch zur Umrechnung von Kalenderzeit auf Unixzeit 
benutzen. 2440587,5 vom julianischen Datum abziehen und mit 86400 
multiplizieren. Ist die Basis nicht UTC, und braucht man die Genauigkeit 
muss man noch für Schaltsekunden korrigieren.

> Darum fielen die auch weder auf Y2K,

Die Unix-Leute haben über Y2K eher gelacht, deren Dommsday kommt noch, 
19. Januar 2038, wenn die früher üblichen 32 Bit nicht mehr reichen. Das 
kann sogar auf modernen Systemen mit 64 Bit Sekundenzähler passieren 
wenn da drauf zum Beispiel noch alte Anwendungen laufen, die intern Zeit 
in 32 Bit speichern.

[(prx) A. K. (prx)]

Hannes J. schrieb:
> Die Unix-Leute haben über Y2K eher gelacht, deren Dommsday kommt noch

... wenn deren Herzschrittmacher aussetzen.

Tatsächlich hatte das aber nichts mit dem Betriebssystem zu tun. Es ist 
die Frage, wie Anwendungen in ihrer Datenspeicherung mit der Jahreszahl 
umgehen. Ob beispielsweise in Datenbanken und Eingabemasken 2- oder 
4-stellig angegeben wird. In einer Eingabemaske ist die Unix-Zeit 
unpraktisch. Und in einer Datenbank alle Daten aus dem Jahr 2015 zu 
suchen ist einfacher, wenn da das Datum zerlegt drinsteht - kein Risiko, 
dass dir irgendwelche schief gerechneten Schaltsekunden die 
Steuererklärung durcheinander bringen.

[W.S. (Gast)]

Ob nun Unix-Zeit oder MSDOS-Zeit oder irgend ein anderer Startpunkt 
genommen wird, ist eigentlich egal. Ich benutze schlichtweg nen 32 Bit 
Zähler für die Sekunden seit dem 1.1.2000 und das reicht für die 
Lebenszeit eines durchschnittlichen Gerätes allemal aus.

Und wenn es um Zeitabläufe im µC geht, dann werden die Millisekunden ab 
Mitternacht gezählt und zur nächsten Mitternacht zurückgestellt. Das 
geht problemlos, wenn man NICHT auf den Gedanken kommt, anhand des 
Millisekundenzählers per Trampelschleife warten zu wollen, sondern das 
Verwalten von Zeiten und das Generieren von Timer-Ereignissen der 
programminternen Systemuhr überläßt. Die ist für sowas nämlich da.

W.S.

[Peter D. (peda)]

Fritz G. schrieb:
> Ich hätte auch gesagt in Unixzeit umrechnen. Allerdings braucht das
> viele Multiplikationen.

Na und, der Atmega32 hat nen MUL-Befehl.

[Fritz G. (fritzg)]

Peter D. schrieb:
> Fritz G. schrieb:
>> Ich hätte auch gesagt in Unixzeit umrechnen. Allerdings braucht das
>> viele Multiplikationen.
>
> Na und, der Atmega32 hat nen MUL-Befehl.

Habe grad nachgesehen, 2 Takte. Hui, ist das hurtig! Früher[TM] dauerte 
so etwas erheblich länger.

[Timm T. (Gast)]

Hannes J. schrieb:
> Beim julianischen Datum
> ist der Übergang zwischen zwei Tagen nicht um Mitternacht, sondern um 12
> Uhr Mittags. Die haben 0,5 Tage Offset.

Das könnte für jemanden, der vorzugsweise Nachts beobachtet, durchaus 
sinnvoll sein, meinst Du nicht? Naja, zumindest Herschel meinte das...

Axel S. schrieb:
> Auch der Hinweis auf UNIX Timestamps kam vollkommen zurecht. Nicht nur
> ist diese Form der Codierung simpelst zu vergleichen

Auch eine in Nibbles gepackte BCD-Codierung, wie sie viele RTCs 
rausgeben ist simpelst zu vergleichen, da der AVR wie oben schon erwähnt 
eh Byteweise vergleicht.

Zusätzlich ist sie noch simpelst zu lesen (direkt als Hexzahl), als 
Konstante anzugeben (als Hexzahl), in einzelne Ziffern aufzulösen (mit 
Swap) für Displayausgabe und zu manipulieren (Uhrzeit stellen up/down), 
erfordert alles minimale Rechenzeit ohne Multiplikation und Division.

Was bescheiden geht sind Zeitdifferenzen zu berechnen. Und der 
Speicherbedarf ist halt etwas höher, 7 Byte reichen aber für hh:mm:ss, 
dd.nn.yy und wday.

[Joachim B. (jar)]

erkläre Effizient

da in meinen Prograammen eh immer Date und Time als String vorliegt 
benutze ich strcmp ==, > oder <

ist nicht elegant aber einfach

yyyy_mo_ta__hh_mm_ss

[Fan von Standards (Gast)]

>
> yyyy_mo_ta__hh_mm_ss

Jetzt noch die richtigen Trennzeichen und Du bist Standardkonform zu 
ISO-8601:

  yyyy-mo-taThh:mm:ss

PS1: bei Richtigen[TM] Dateisysteme ist ':' in Dateinamen 
selbstverständlich zulässig.

PS2: date --iso=s und man date

[Ralph S. (jjflash)]

Peter Danneger hat sowas vor Jahren hier gepostet:

Beitrag "Berechnung Datum + Uhrzeit + Sommerzeit"

32 Bit Variable für Sekunden beginnend ab einem bestimmten Datum.

Dann ist das Vergleichen auf größer, kleiner oder gleich kein Problem.

Gruß,

Ralph

[J. W. (dilbert)]

Da hier so viele die Verwendung des Unix-Timestamps vorgeschlagen haben:

Was ist denn ein für Mikrocontroller geeigneter Algorithmus?

@Thomas,
ob die Verwendung von Bitfeldern einen Vorteil bringt (und nicht eher 
einen Nachteil), bezweifle ich. Du könntest den Zeit-struct verwenden, 
der auf jedem(?) Unix-System in /usr/include/time.h definiert ist:

struct tm
{
  int tm_sec;                   /* Seconds.     [0-60] (1 leap second) */
  int tm_min;                   /* Minutes.     [0-59] */
  int tm_hour;                  /* Hours.       [0-23] */
  int tm_mday;                  /* Day.         [1-31] */
  int tm_mon;                   /* Month.       [0-11] */
  int tm_year;                  /* Year - 1900.  */
  ...
}

[(prx) A. K. (prx)]

J. W. schrieb:
> ob die Verwendung von Bitfeldern einen Vorteil bringt (und nicht eher
> einen Nachteil), bezweifle ich.

Kommt auf die Anwendung drauf an. In einem begrenzten Logspeicher ist 
man mit 4 Bytes Timestamp, egal ob Sekunden oder zerlegt, jedenfalls 
besser dran als mit ASCII oder struct tm.

[Thomas (Gast)]

Also ich bin jetzt voll und ganz von der Unixtime überzeugt.

Ich habe auch schon eine Funktion mit der ich mit dem Atmega32 und 16MHz 
in 150µs von meiner Struktur in Unixtime umrechnen kann.

uint32_t convertDateTimeFromHumanToUnix(Clock_SType_TimeAndDate as_DateTime)
{
    
    uint32_t lu32_year = as_DateTime.u16_Year;
    uint32_t lu32_month = as_DateTime.e_Month;
    uint32_t lu32_day = as_DateTime.u8_Day;
    uint32_t lu32_hour = as_DateTime.u8_Hour;
    uint32_t lu32_minute = as_DateTime.u8_Minute;
    uint32_t lu32_second = as_DateTime.u8_Second;
    
    const uint32_t lu16_DaysByMonths[12] = {0,31,59,90,120,151,181,212,243,273,304,334};

    uint32_t lu32_LeapYears = ((lu32_year-1)-1968)/4
                         - ((lu32_year-1)-1900)/100
                         + ((lu32_year-1)-1600)/400;

    uint32_t lu32_daysSince1970 = (lu32_year-1970)*365 + lu32_LeapYears + lu16_DaysByMonths[lu32_month-1] + lu32_day-1;

    if (    (lu32_month > 2)
         && (    (  lu32_year % 4 == 0                              ) 
              && ( (lu32_year % 100 != 0) || (lu32_year % 400 == 0) )    )    )
    {
        lu32_daysSince1970 += 1; 
    }

    return lu32_second + 60 * ( lu32_minute + 60 * (lu32_hour + 24 * lu32_daysSince1970) );
}

Es scheitert allerdings nun daran, die Unixzeit wieder in ein Datum 
umzurechnen (Stunden Minuten und Sekunden sind nicht das Problem)
Hat hier jemand einen effizienten Ansatz?

Meiner ist bisher dieser. Verbesserungsvorschläge willkommen!

Clock_SType_TimeAndDate convertDateTimeFromUnixToHuman(uint32_t au32_UnixTime)
{
    Clock_SType_TimeAndDate lt_ReturnValue;
    uint32_t lu32_daysFrom1970 = au32_UnixTime / 86400;
    uint32_t lu32_SecondsToday       = au32_UnixTime % 86400;
    lt_ReturnValue.u8_Hour   = lu32_SecondsToday / 3600;
    lt_ReturnValue.u8_Minute = (lu32_SecondsToday / 60) % 60;
    lt_ReturnValue.u8_Second = lu32_SecondsToday % 60;
    uint16_t lu16_ApproximateYear = lu32_daysFrom1970 / 365;
        
    uint8_t lu8_schaltjahre = ((lu16_ApproximateYear + 1970-1)-1968)/4      /* Anzahl der Schaltjahre seit 1970 (ohne das evtl. laufende Schaltjahr) */
                            - ((lu16_ApproximateYear + 1970-1)-1900)/100
                            + ((lu16_ApproximateYear + 1970-1)-1600)/400;

    uint32_t lu32_daysWithoutLeapDays = lu32_daysFrom1970 - lu8_schaltjahre;
    uint16_t lu16_Year = (lu32_daysWithoutLeapDays / 365) + 1970;
    uint16_t lu16_DaysThisYear = (lu32_daysWithoutLeapDays % 365);
    lu16_DaysThisYear += 1;
    lt_ReturnValue.u16_Year = lu16_Year;
    
    
    uint8_t lu8_CurrentYearIsLeapYear = 0;
    if(lu16_Year % 4 == 0)
    {
        if(lu16_Year % 100 == 0)
        {
            if(lu16_Year % 400 == 0)
            {
                lu8_CurrentYearIsLeapYear = 1;
            }
        }
        else
        {
            lu8_CurrentYearIsLeapYear = 1;
        }
    }

    uint8_t lu8_Month = 0;
    uint8_t lu8_Day = 0;
    if(lu16_DaysThisYear <= 31)
    {
        lu8_Month = 1;
        lu8_Day = lu16_DaysThisYear;
    }
    else if(lu16_DaysThisYear <= 59)
    {
        lu8_Month = 2;
        lu8_Day = lu16_DaysThisYear - 31;
    }
    else if((lu16_DaysThisYear == 60) && (lu8_CurrentYearIsLeapYear == 1))
    {
        lu8_Month = 2;
        lu8_Day = lu16_DaysThisYear - 31;
    }
    else
    {
        const uint16_t lu16_DaysByMonths[12] = {0,31,59,90,120,151,181,212,243,273,304,334};
        lu16_DaysThisYear -= lu8_CurrentYearIsLeapYear;
        
        for(lu8_Month = 3; lu8_Month < 12; lu8_Month++)
        {
            if(lu16_DaysThisYear <= lu16_DaysByMonths[lu8_Month])
            {
                break;
            }
        }

        lu8_Day = lu16_DaysThisYear - lu16_DaysByMonths[lu8_Month-1];
    }

    lt_ReturnValue.u8_Day = lu8_Day;
    lt_ReturnValue.e_Month = lu8_Month;   
    
    return lt_ReturnValue;
}

Zudem hab ich irgendwo ein Problem beim Umrechnen ab dem 2016-12-20 bis 
2016-12-31. Wenn ich das Datum erst in eine Unixtime rechne und dann 
wieder zurück.

[Wolfgang (Gast)]

Thomas schrieb:
> enum e_months     e_Month  :4;

> kleiner, gleich oder größer

Wie willst du das unter einen Hut bringen.

[Gerd E. (robberknight)]

Was mir hier in den ganzen Structs, Formeln und Code fehlt ist die 
Behandlung von Sommerzeit und Winterzeit. Denn bei der Umstellung von 
Sommerzeit auf Winterzeit wird die Zeit um 1 h zurückgestellt, also die 
Zeit von 2-3h 2x hintereinander durchlaufen. Wenn man das beim Vergleich 
nicht berücksichtigt geht das genau dann schief. An sowas sind schon 
viele Programme gescheitert.

Daher ist Unixtime in UTC, da gibt es keine Sommerzeit.