Bug durch millis() Überlauf beim Vergleichen vermeiden

[pete (Gast)]

Um das Problem des Überlaufs der millis()-Funktion beim Arduino nach 49 
Tagen zu lösen, verwende ich bei Time-Outs immer folgenden Code:

    unsigned long timeout = millis() + 1000;
    while ( ((timeout - millis()) & 0x80000000) == 0 ) {
        ...

Ich bin mir aber nicht ganz sicher, ob das wirklich eine gute Idee bzw. 
eine gute Formulierung in C ist. Zumindest funktioniert es auch, wenn 
millis() sich 4294967295 nähert.

Hat jemand eine effizientere (= erzeugt besseren Maschienencode) oder 
schönere (= ist im Sourcecode einfach besser zu verstehen) Lösung, die 
auch funktioniert?

[derjaeger (Gast)]

Wenn du Timeouts brauchst, dann zähl doch rückwärts von Start bis 0.

Also:

timeout = x
Immer wenn millis() sich verändert hat (new != old) :  timeout--
Wenn timeout = 0: Reaktion ...

[Einer K. (Gast)]

Siehe:
Datei->Beispiele->Digital->BlinkWithoutDelay

[pete (Gast)]

@ derjaeger: Denkbar, aber dann brauche ich zusätzlich zum Vergleich von 
timeout auf 0 oder kleiner (was ja genaugenommen nicht geht, da 
unsigned) auch noch einen timeout-- (bei 32 Bit mittelmäßgi aufwändig).

[pete (Gast)]

@Arduino Fanboy D.:

  unsigned long currentMillis = millis();
 
  if(currentMillis - previousMillis > interval) {

4-Byte-Subtraktion plus 4-Byte-Vergleich = mehr CPU-Bedarf

[Einer K. (Gast)]

pete schrieb:
> @Arduino Fanboy D.:  unsigned long currentMillis = millis();
>
>   if(currentMillis - previousMillis > interval) {
> 4-Byte-Subtraktion plus 4-Byte-Vergleich = mehr CPU-Bedarf

Du möchtest was funktionierendes!
Deins funkioniert nicht.
Dieses ja.

Es gibt natürlich noch mehr Wege, sich eine Zeitbasis zu beschaffen.
Aber wenn du millis() nutzen möchtest, dann ist genau DAS der Weg.

[pete (Gast)]

Arduino Fanboy D. schrieb:
> Deins funkioniert nicht.

Aha. Und was genau funktioniert nicht?

[derjaeger (Gast)]

>Aha. Und was genau funktioniert nicht?

Nach 49 Tagen funktionierts nicht.

[pete (Gast)]

Bitte ausführen

[Einer K. (Gast)]

pete schrieb:
> 4-Byte-Subtraktion plus 4-Byte-Vergleich = mehr CPU-Bedarf

Bei dir:
 4-Byte-Subtraktion
 4-Byte And
 4-Byte Vergleich

= Noch mehr CPU-Bedarf

[pete (Gast)]

Arduino Fanboy D. schrieb:
>> 4-Byte-Subtraktion plus 4-Byte-Vergleich = mehr CPU-Bedarf
>
> Bei dir:
>  4-Byte-Subtraktion
>  4-Byte And
>  4-Byte Vergleich
>
> = Noch mehr CPU-Bedarf

Nö, denn nach der 4-Byte-Subtraktion wird einfach auf Overflow-Flag 
getestet.

Aber ich hatte draum gebeten, zu zeigen, warum mein Programmausschnitt 
nicht funktioniert:

derjaeger schrieb:
>>Aha. Und was genau funktioniert nicht?
>
> Nach 49 Tagen funktionierts nicht.

[Frank M. (ukw) (Moderator)]

derjaeger schrieb:
> Nach 49 Tagen funktionierts nicht.

Doch. Der Witz ist, dass unsigned-Subtraktionen auch bei Überläufen 
funktionieren.

Beispiel, welches das Verhalten von millis() simuliert - hier mal unter 
Linux:

#include <stdio.h>
#include <stdint.h>

int main ()
{
    uint32_t start = 0xFFFFFFFF;        // Start der Messung per millis() - kurz vor Überlauf
    uint32_t now = 1;                   // Ende der Messung per millis() - nach Überlauf

    printf ("%u\n", now - start);
    return 0;
}

Das Programm gibt 2 aus. Das funktioniert auch mit beliebigen anderen 
Werten.

[Einer K. (Gast)]

Frank M. schrieb:
> Doch. Der Witz ist, dass unsigned-Subtraktionen auch bei Überläufen
> funktionieren.

Hier eine alternative Variante des gleichen Themas:
(welche korrekt und über den gesamten Wertebereich funktioniert)

// Wieder eine Variation des BlinkWithoutDelay

    class SimpleTimer
    {
      private:
      uint32_t timeStamp;      // Zeitmerker
      bool reached;                // default Status: timer abgelaufen
    
      public:
      SimpleTimer():timeStamp(0),reached(true){}
      
      void start()
      {
        timeStamp   = millis();
        reached     = false;
      }
    
      bool operator()(const uint32_t interval) 
      {
        if(!reached) reached = millis() - timeStamp >= interval;
        return reached;
      }
    };


SimpleTimer timer; // timer Instanz anlegen

void setup()
{
  pinMode(LED_BUILTIN,OUTPUT);
}

void loop()
{
  if(timer(1000)) // wenn abgelaufen
  { 
    digitalWrite(LED_BUILTIN,!digitalRead(LED_BUILTIN));
    timer.start();
  }
}

[pete (Gast)]

pete schrieb:
> Um das Problem des Überlaufs der millis()-Funktion beim Arduino nach 49
> Tagen zu lösen, verwende ich bei Time-Outs immer folgenden Code:

>     unsigned long timeout = millis() + 1000;
>     while ( ((timeout - millis()) & 0x80000000) == 0 ) {
>         ...

Ich geh sogar soweit, dass mein Verfahren "beweisbar" richtig ist:

Ich setze für "timeout" die Definition ein, dann folgt für den 
Vergleich:

     while ( ((millis() + 1000 - millis()) & 0x80000000) == 0 ) {

und damit:

     while ( ((1000) & 0x80000000) == 0 ) {

Nun ist klar, dass mit forschreitender Zeit, die "1000" kleiner wird, 
bis es genau nach dem Wert "0" einen Underflow gibt, bei dem es zu 
0xFFFFFFFF und kleineren Werten kommt. Um genau zu sein kommt es fast 25 
Tage lang zu Werten, dessen höchstes Bit gesetzt ist.

Ergo, das funktioniert auf jeden Fall, ist nur nicht schön.

[Sebastian S. (amateur)]

Brauchst Du denn überhaupt diesen, langen Zeitraum?
Wenn nicht: Einfach, bei der aktuellen Abfrage, den letzten Wert 
speichern und dann abfragen ob der neue Wert kleiner ist. ...und 
natürlich berücksichtigen.

[Einer K. (Gast)]

pete schrieb:
> Ergo, das funktioniert auf jeden Fall, ist nur nicht schön.

Die While Schleife blockiert den restlichen Code.
Sowas braucht man doch nicht, oder?

[pete (Gast)]

Ein weiterer Vorteil meiner Methode ist, dass bei notwendigen Timeouts 
unter 32.7 Sekunden sie noch effizienter wird:

    unsigned short timeout = (unsigned short)millis() + 1000;
    while ( ((timeout - (unsigned short)millis()) & 0x8000) == 0 ) {
        ...

[pete (Gast)]

Arduino Fanboy D. schrieb:
> Die While Schleife blockiert den restlichen Code.
> Sowas braucht man doch nicht, oder?

Doch, z.B. wenn man eine zeitlang (-> timeout) auf eine Antwort warten 
muss, sie aber verloren gehen kann und man dann z.B. erneut anfragen 
muss ...

[pete (Gast)]

pete schrieb:
> Ein weiterer Vorteil meiner Methode ist, dass bei notwendigen Timeouts
> unter 32.7 Sekunden sie noch effizienter wird:

>     unsigned short timeout = (unsigned short)millis() + 1000;
>     while ( ((timeout - (unsigned short)millis()) & 0x8000) == 0 ) {
>         ...

und da fällt mir gleich eine Frage an die Profis ein. Ist das nicht eine 
schönere Formulierung:

     unsigned short timeout = (unsigned short)millis() + 1000;
     while ( (signed short)(timeout - (unsigned short)millis()) >= 0 ) {
         ...

[Frank M. (ukw) (Moderator)]

pete schrieb:
> Ich geh sogar soweit, dass mein Verfahren "beweisbar" richtig ist:
>
> Ich setze für "timeout" die Definition ein, dann folgt für den
> Vergleich:     while ( ((millis() + 1000 - millis()) & 0x80000000) == 0
> ) {
>
> und damit:     while ( ((1000) & 0x80000000) == 0 ) {

Du kannst die millis() hier nicht einfach so rausstreichen, Du kannst 
noch nichtmals timeout durch "millis() + 1000" einfach so ersetzen. Der 
erste Rückgabewert von millis() ist konstant. Der zweite Rückgabewert 
ändert sich laufend. Von daher halte ich Deinen "Beweis" für äußerst 
fragwürdig.

Ob Dein Verfahren tatsächlich weniger CPU-Power braucht als der 
klassische Weg:

unsigned long start = millis();

while (millis() - start < 1000) // ja, das ist überlauf-fest!
{
    ;
}

kann man nur beurteilen, wenn man sich den Assembler-Output des 
Compilers anschaut.

Das hier:

> und damit:     while ( ((1000) & 0x80000000) == 0 ) {

ist jedenfalls eine Endlosschleife.

[pete (Gast)]

Frank M. schrieb:
> Das hier:
>
>> und damit:     while ( ((1000) & 0x80000000) == 0 ) {
>
> ist jedenfalls eine Endlosschleife.

Klar, das war ja nur die Idee für einen richtigen Beweis. Den müsste ein 
Informatiker liefern. Das bin ich nicht.

Aber vielleicht habe ich mir die Frage selbst beantwortet, als ich 
vorige Antwort mit folgender Zeile schrieb:

     while ( (signed short)(timeout - (unsigned short)millis()) >= 0 ) {

Ich bin mir nur nicht sicher, dass es wirklich funktioniert (Unterschied 
allg. Theorie vs. konkrete Realität eines AVR 328)

[Einer K. (Gast)]

pete schrieb:
> Ergo, das funktioniert auf jeden Fall, ist nur nicht schön.
Gerade getestet...
Es funktioniert nicht!
Es versagt.
Definitiv

pete schrieb:
> Doch, z.B. wenn man eine zeitlang (-> timeout) auf eine Antwort warten
> muss, sie aber verloren gehen kann und man dann z.B. erneut anfragen
> muss ...
Wie gesagt, das ist blockierendes Warten.
Meist mehr Nachteile, als Voreile.
Damit meist unbrauchbar.

[Frank M. (ukw) (Moderator)]

pete schrieb:
> Ich bin mir nur nicht sicher, dass es wirklich funktioniert (Unterschied
> allg. Theorie vs. konkrete Realität eines AVR 328)

Einfach mal testen auf dem PC, dafür braucht man keinen AVR:

#include <stdio.h>
#include <stdint.h>

uint32_t millis1(void)
{
    return 0xFFFFFFFF;                // Startwert
}

uint32_t millis2(void)                // Laufender Wert
{
    return 999;                       // ergibt "true"
    // return 1000;                   // ergibt "false"
}

void u1 (void)
{
    unsigned short timeout = (unsigned short) millis1() + 1000;

    if ( (signed short)(timeout - (unsigned short)millis2()) >= 0 )
    {
        puts ("true");
    }
    else
    {
        puts ("false");
    }
}

int main ()
{
    u1 ();
    return 0;
}

Setze beliebige Return-Werte in millis1() und millis2() ein und bewerte 
den Output. Nach meinen Stichproben zu urteilen scheint es zu 
funktionieren.

[pete (Gast)]

Arduino Fanboy D. schrieb:
> pete schrieb:
>> Ergo, das funktioniert auf jeden Fall, ist nur nicht schön.
> Gerade getestet...
> Es funktioniert nicht!
> Es versagt.
> Definitiv

Man man man. Du lehnst Dich hier aus dem Fenster und behauptest voller 
Überzeugung etwas so dermaßen falsches! Ich habe nie verstanden, wo 
solche Leute dieses unberechtigte Selbstvertrauen hernehmen (das müßte 
man auch mal klären).

Im folgenden ein Arduino-Sketch, der die Funktionsfähigkeit des Timeout 
demonstriert:

// Test timeout via millis() with 16-bit variable and overflow

const int ledPin = 13;
char ledState = LOW;
unsigned short timeout, prev_time;

void setup() {
  Serial.begin( 115200 );
  pinMode( ledPin, OUTPUT );
  timeout = millis() + 500;     // 0.5s
}

void loop()
{
  unsigned short time = (unsigned short)millis();

  if ( (signed short)(timeout - time) <= 0 ) {
    Serial.println( time - prev_time );
    Serial.println( time );
    prev_time = time;
    timeout = time + 500;
    ledState = (ledState == LOW) ? HIGH : LOW;
    digitalWrite( ledPin, ledState );
  }
}

Damit dürfte geklärt sein, dass meine Lösung aus erstem Post 
funktioniert und dass diese Variante für Timeouts bis zu 32 Sekunden 
auch funktioniert, und wesentlich weniger CPU Takte kostet.

Meine Frage aus 1. Post ist aber nicht beantwortet.

[A. S. (Gast)]

pete schrieb:
> while ( ((timeout - millis()) & 0x80000000) == 0 ) {

Das ist faktisch das gleiche wie < 0 bei signed.

Es gibt zig Möglichkeiten, aus der Differenz signed zu machen, am Ende 
sollte man derartige Basics, weil sie immer wieder und mehrfach 
gebraucht werden, entsprechend Kapseln. Makros, Inline oder Funktionen, 
je nach Vorliebe. Mein Favorit in diesem Kontext: eine signed Funktionen 
für eine Differenz:

#dedine diff(t) ((long)(t-millis())

Oder typsicher als (inline-) Funktion.

Ich benutze natürlich als Zeitbasis eigene typedefs.

[Einer K. (Gast)]

pete schrieb:
> unberechtigte Selbstvertrauen

Ja, ich muss gestehen, dass mein Test fehlerhaft war.
Es schient zu funktionieren.

[x^2 (Gast)]

pete schrieb:
> Meine Frage aus 1. Post ist aber nicht beantwortet.

Es ist zu empfehlen (wg. Bitoperation) das Literal explizit auch als 
unsigned long zu kennzeichnen ("UL" Postfix).

Die realisierte Verzögerung ist im Worst-case +1 zur Gewünschten 
(Beispiel: Eine Verzögerung von 0 wird im Worst-case eine Verzögerung um 
1 sein). Das ist evtl. relevant wenn dieser Code mehrfach genutzt wird. 
Zum Beispiel 1000x eine Verzögerung von 1 ergibt im Worst-case 2000.

[pete (Gast)]

Arduino Fanboy D. schrieb:
> pete schrieb:
>> unberechtigte Selbstvertrauen
>
> Ja, ich muss gestehen, dass mein Test fehlerhaft war.
> Es schient zu funktionieren.

Du hast ja freundlicherweise Deinen noch großmundigeren Post selbst 
gelöscht, weil Du feststellen musstest, dass mein Code doch OK ist.

Lass das "scheint" weg, und wir sind wieder Freunde.

Ich habe in der Zwischenzeit herausgefunden, warum Dein gelöschter 
Testcode so merkwürdig arbeitet:

1) hattest Du einen Tippfehler bei (es fehlt eine 0):
>  AtomicSection timer0_millis = 0x8000000UL;  // versagt

2) Folgende Initialisierung der globalen Variable
> unsigned long timeout = millis() + 1000;
wird zu einem undefinierten Zeitpunkt vor setup() ausgeführt, so dass 
die Laufzeit von setup() von der einen Sekunde abgezogen wird.
Und komischerweise braucht die Zeile aus 1) dann so lange, dass der 
timeout bereits vorbei ist und Deine LED niemals blinkt.

3) So habe ich den timeout gar nicht gemeint, sondern wie in meinem 
Beispielprogramm.

Hier nochmal für long und mit Deiner schönen Idee, den timer zu 
verstellen, um zu testen:

#include <util/atomic.h>
#define AtomicSection ATOMIC_BLOCK(ATOMIC_RESTORESTATE)

extern volatile unsigned long timer0_millis;

const int ledPin = 13;
char ledState = LOW;
unsigned long timeout, prev_time;

void setup() {
  Serial.begin( 115200 );
  pinMode( ledPin, OUTPUT );
  // Kurz vor den beiden Zeiten (25 und 50 Tage), von denen Probleme zu erwarten sind:
  AtomicSection timer0_millis = 0x7FFFF000UL;
  // AtomicSection timer0_millis = 0xFFFFF000UL;
  timeout = millis() + 500;     // 0.5s
}

void loop()
{
  unsigned long time = millis();

  if ( ((timeout - time) & 0x80000000) != 0 ) {
  //if ( (signed long)(timeout - time) < 0 ) {   // Äquivalent
    Serial.println( time - prev_time );
    Serial.println( time );
    prev_time = time;
    timeout = time + 500;
    ledState = (ledState == LOW) ? HIGH : LOW;
    digitalWrite( ledPin, ledState );
  }
}

[pete (Gast)]

A. S. schrieb:
> pete schrieb:
>> while ( ((timeout - millis()) & 0x80000000) == 0 ) {
>
> Das ist faktisch das gleiche wie < 0 bei signed.

x^2 schrieb:
> Es ist zu empfehlen (wg. Bitoperation) das Literal explizit auch als
> unsigned long zu kennzeichnen ("UL" Postfix).
>
> Die realisierte Verzögerung ist im Worst-case +1 zur Gewünschten
> (Beispiel: Eine Verzögerung von 0 wird im Worst-case eine Verzögerung um
> 1 sein). Das ist evtl. relevant wenn dieser Code mehrfach genutzt wird.
> Zum Beispiel 1000x eine Verzögerung von 1 ergibt im Worst-case 2000.

Beides sehr wichtige Kommentare:

1) UL hinzugefügt:

    unsigned long timeout = millis() + 1000;
    while ( ((timeout - millis()) & 0x80000000UL) == 0 ) {

2) Äquivalent und schöner:

    unsigned long timeout = millis() + 1000;
    while ( (signed long)(timeout - millis()) >= 0 ) {

3)
Beides ist fast 1ms zu lang, daher die bisher beste Variante:

    unsigned long timeout = millis() + 1000;
    while ( (signed long)(timeout - millis()) > 0 ) {

[pete (Gast)]

Schade. Das Ende dieses Threads ist mit Blödsinn versaut. Wer das 
Ergebnis wissen will, schaut bei:
Beitrag "Re: Bug durch millis() Überlauf beim Vergleichen vermeiden"
Oder bei:
Beitrag "Re: Bug durch millis() Überlauf beim Vergleichen vermeiden"

@Arduino Fanboy D.: Ich hab doch sogar Deinen "#define AtomicSection" 
und "extern volatile unsigned long timer0_millis" als schöne Idee 
bezeichnet.

@Roth: Ist das alles nötig?

[A. S. (Gast)]

pete schrieb:
> Beides ist fast 1ms zu lang, daher die bisher beste Variante:

Das ist eine grundsätzliche Frage, deren Antwort man sich mit dem Aufruf 
0 bzw. 1 vergegenwärtigen sollte:

Welche Zeit mit Zeit 0 bzw. 1 erwartet wird:

0: a) 0...999µs oder b)immer sofort?
1: a) 1000 ... 1999µs oder b) 0..999µs?

a: >=0 (bzw. if diff < 0)
b: >0  (bzw. if diff <=0)

Beide Interpretationen haben ihre Berechtigung, und es macht keinen 
Sinn, eine als die einzig richtige hinzustellen. Darum sollte man immer 
wissen, wie ein Sleep(0) bzw. Sleep(1) in seinem Rtos wirkt.

[Frank M. (ukw) (Moderator)]

Ich verweise an dieser Stelle auf die Nutzungsbedingungen. Auch als Gast 
sollte man innerhalb eines Threads den Namen beibehalten und nicht 
wechseln.

Ich bitte auch, beim Thema zu bleiben.

[ch (Gast)]

Der "rollover save timer" muss genau so aussehen:

Beitrag "Re: rollover save timer in c"

Den Wertebereich kannst Du von uint8_t auf uint32_t ändern.

[Einer K. (Gast)]

ch schrieb:
> Der "rollover save timer" muss genau so aussehen:

Genau DAS ist nicht gewünscht!

[Nico W. (nico_w)]

Den Godbolt gibt es auch für den AVR-GCC...

http://avr-gcc.senthilthecoder.com/#g:!((g:!((g:!((h:codeEditor,i:(j:1,options:(colouriseAsm:'0',compileOnChange:'0'),source:'//+Type+your+code+here,+or+load+an+example.%0A%23include+%3Cstdint.h%3E%0A%0Avolatile+uint32_t+timer%3B%0Auint32_t+millis(void)+%7B+return+timer%3B+%7D%0A%0Avoid+delay_1(void)+%7B%0A++++uint32_t+timeout+%3D+millis()+%2B+1000%3B%0A++while+(+(int32_t)(timeout+-+millis())+%3E+0)%3B%0A%7D%0A%0Avoid+delay_2(void)+%7B%0A++uint32_t+start_time+%3D+millis()%3B%0A++while+(+(uint32_t)(millis()+-+start_time)+%3C+1000)+%3B%0A%7D'),l:'5',n:'1',o:'C+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:a354,filters:(b:'0',commentOnly:'0',directives:'0',intel:'0'),fontScale:0.9,options:'-O2'),l:'5',n:'0',o:'%231+with+Atmel+3.5.4+(gcc+4.9.2)',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4

Kann ja jeder für sich selbst entscheiden, was er da nehmen möchte.

[S. R. (svenska)]

Soweit ich informiert bin, ist "signed overflow" in C undefiniert, 
"unsigned overflow" hingegen nicht. Daher ist ersteres per se schlechter 
als letzteres.

Aber macht ihr nur. :-)

[DerAltePete (Gast)]

Nico W. schrieb:
> Den Godbolt gibt es auch für den AVR-GCC...
>
> Kann ja jeder für sich selbst entscheiden, was er da nehmen möchte.

Schöner Beitrag, aber wenn der gcc so dämlich ist, dann hilf ihm halt 
auf die Sprünge und schreib in Deinem Beispiel statt

    while ( (int32_t)(timeout - millis()) > 0 );

eben

    while ( (int32_t)(millis() - timeout) < 0 );

Das wird nämlich zu

.L3:
        lds r24,timer
        lds r25,timer+1
        lds r26,timer+2
        lds r27,timer+3
        sub r24,r20
        sbc r25,r21
        sbc r26,r22
        sbc r27,r23
        brmi .L3

und ist damit, wie es der gesunde Menschenverstand erwarten lässt, um 
einiges effizienter als die von Dir bevorzugte Zeile:

  while ( (uint32_t)(millis() - start_time) < 1000 );

.L7:
        lds r24,timer
        lds r25,timer+1
        lds r26,timer+2
        lds r27,timer+3
        sub r24,r20
        sbc r25,r21
        sbc r26,r22
        sbc r27,r23
        cpi r24,-24
        sbci r25,3
        cpc r26,__zero_reg__
        cpc r27,__zero_reg__
        brlo .L7

[Nico W. (nico_w)]

Ohje...

Sollte dann aber <= sein?!?

Edit: sicher nicht... Aber dennoch wiederum interessantes Verhalten.