Benötigt: Wrappable Zähler, wobei do „das Richtige“

Question

Ich brauche den Code zu einem couter, die überlaufen durften und wo <> weiter frühere Werte von den späten Wert sagen, für einig definierten Intervall.

Um zu klären, eine mögliche Implementierung wäre:

Betrachten wir zwei solche Zähler cur und dut (Prüfling), betrachten wir zwei Funktionen:

bool isEarlier(cur, dut)    // Is dut earlier than cur?
bool isLater(cur, dut)

cur und dut 16 Bit sind, cur gerade überschwemmt haben, sein aktueller Wert ist, lassen Sie sich 5 sagen. Je nach dem Wert von dut würde geben die Funktionen

• 0-16384: isEarlier -> (cur < dut), isLater -> (cur > dut)
• 16.384-32.768: isEarlier -> false, isLater -> true
• 32.768-49.152: ungültig, melden Fehler
• 49.152-65.536: isEarlier -> true, isLater -> false

Ich kann den Code selbst schreiben, kein Problem. Ich bin einfach nur faul. Ich weiß, dass es so etwas wie, dass in PostgreSQL (Transaktions-IDs Wrap), ich konnte einfach nicht die Funktion finden, die es tatsächlich der Fall ist. Ich bin mir ziemlich sicher, dass es so etwas wie das in dem Linux-Kernel ist, wahrscheinlich ein Makro. Aber neighther Google Codesearch, noch grep über / usr / include / linux könnte es wieder auftauchen. Irgendwelche Ideen, wo es ist?

geklärte Rolle des Köters und dut. Die „ungültig“ ist dort als Schutz. Da die Unterschiede zwischen cur und dut wird größer, klagt die Funktion schließlich.

Answer 1

Ich glaube, Sie sprechen die Wraparound des Nummernkreises korrekt über den Umgang. Es ist ganz einfach, eigentlich.

Dies ist nicht genau das, was Sie gesagt haben (nicht sicher, warum Sie, dass „Ausnahme“ Intervall), aber:

typedef unsigned short uint16_t;
typedef signed short int16_t;
// abstract out 16-bit types in case "short" doesn't correspond to 16bits

bool isEarlier(uint16_t a, uint16_t b)
{
   int16_t diff = a-b;
   return diff < 0;
}
bool isLater(uint16_t a, uint16_t b)
{
   int16_t diff = a-b;
   return diff > 0;
}

Bearbeiten : dies hat einen "Verzweigungspunkt" bei diff = -32768, so dass, wenn a = 5 und b = 32772, diff = -32767, der kleiner als 0 ist und somit 5 " früher“als 32772. Wenn a = 5 und b = 32774, diff = -32.769 = 32767, die größer als 0 ist und daher 5 ist‚später‘als 32774. Dies definiert‚früher‘und‚später‘im Sinne von (a ) die einfachste mathematische und (b), weil wraparound Zähler als mit mehreren Lösungen mod 65536 interpretiert werden kann, nimmt er die Lösung von a und b, die „am nächsten“ zu einander in Bezug auf die Anzahl Kreises sind.

Wenn a und b von 32768 unterscheiden sich dann gleich sind sie weit voneinander entfernt und die einfache mathematische verwendet wird, am einfachsten zu holen ... diese „gegen“ die antisymmetrische Eigenschaft von „früher“ und „später“ in dem Sinne, dass isLater (5 , 32773) wahr ist und isLater (32773,5) ist auch wahr. Aber wie Sie wissen, ob „5“ steht für eine Anzahl von 5 oder „5“ steht für eine Anzahl von 65.541? (Nur als abs (-32768) == -32768 gibt eine ungerade unsinnige Antwort) Wenn Sie antisymmetry zum Beispiel erhalten wollen isLater (b, a) == isEarlier (a, b), dann können Sie immer tun:

bool isLater(uint16_t a, uint16_t b)
{
   int16_t diff = b-a;
   return diff < 0;
}

Wenn Sie Bias wünschen der Verzweigungspunkt in einer Richtung bei -32768 + K passieren, dann ist diese verwenden, anstatt:

bool isEarlier(uint16_t a, uint16_t b)
{
   int16_t diff = a-b-K;
   return diff < -K;
}
bool isLater(uint16_t a, uint16_t b)
{
   int16_t diff = b-a-K;
   return diff < -K;
}

Dies verwendet nicht mehr am nächsten; Wenn zum Beispiel K = 12768, und a = 5, dann b = 6,7,8,9, ... 20005, isEarlier (a, b) und isLater (b, a) wird wahr sein, und für b = 20006, 20007, ... 65534, 65535, 0, 1, 2, 3, 4, 5 isEarlier (a, b) und isLater (b, a) wird falsch sein.

Sie haben eine besondere Wahl der Intervalle, die aus der Begründung ich mit Rundum-Nummern verwenden, unterschiedlich ist. Die Funktionen hier definiert würde Ihre Anforderungen nicht erfüllen, wie angegeben, aber ich finde diese Entscheidungen des Intervalls ein wenig eigenartig. Vielleicht könnten Sie erklären, wie man sie bestimmt?

Answer 2

Sie zuerst die Differenz berechnen, dann überprüfen, in die Fenster fällt.

Da es so einfach ist, und die Größen der Vergangenheit / Zukunft / Fehler Fenster variieren, haben Sie es selbst zu tun.

Answer 3

Ok, für das Protokoll. Hier ist meine Lösung ist, das ist, was ich meinte:

#include <stdint.h>


void increase_cyclic_counter (uint16_t *cnt)
{
#ifdef CYCLIC_COUNTER_EXPLICIT_WRAP
    if (*cnt < 2^16-1)
        *cnt++;
    else
        *cnt = 0;
#else
    *cnt++;
#endif
}


#define SAME 1
#define LATER 0
#define EARLIER 2
#define FORBIDDEN -1

/* dut (device under test) is tested against cur
 * returns:
 *    EARLIER (LATER) if dut happened earlier (later) in the sequence than cur
 *    SAME            if dut == cur
 *    FORBIDDEN       if dut and cur are that far away in the cyclic sequence
 *                    that no unambigious jugement is possible
 *
 * The basic idea is the same as with two-character year codes, where 
 * '97' stands for 1997 and '11' stands for 2011. '50' is regarded as 
 * too ambigous and therefore rejected.
 *
 * The implementation splits the short integer range 0-65535 into 4 parts:
 *   0-16383, 16384-32767, 32768-49151, 49152-65536
 * With cur and dut in the same range, normal arithmetics apply, else the 
 * ranges are compared to each other.
 */

int test_cyclic_counter (uint16_t cur, uint16_t dut)
{
    switch (((int)(cur>>14)) - ((int)(dut>>14)))
    {
        case 0:  // same range
            if (dut < cur) 
                return EARLIER;
            else if (dut == cur)
                return SAME;
            else 
                return LATER;

        case 1:
        case -3:
            return EARLIER;

        case 3:
        case -1:        
            return LATER;

        default: 
            return FORBIDDEN;
    }
}

Answer 4

Es scheint mir einfach es geschrieben :). Warum Ihr Beitrag in C-Code nicht übersetzen?

Answer 5

Beachten Sie, dass Sie nicht bekommen kann „>“ und „<“ zu tun, was man in C. wollen Sie gelten für nur Zahlen, und es gibt keine Überladen von Operatoren. Das gleiche gilt für Ihre Ausnahme; C keine Ausnahmen haben.

Sie können einige Zugriffsfunktionen schreiben, die nicht signierte ganzzahlige Typen auf diese Weise behandeln würden, und das wäre nicht schwierig sein. (In C, Überlauf ist für signierten ganzzahlige Typen nicht definiert, obwohl auf den meisten modernen Systemen ist es umschlingt.) Es wäre nicht so schwierig sein.