Sättigung subtrahieren / addieren für vorzeichenlose Bytes

Stellen Sie sich vor, ich habe zwei vorzeichenlose Bytes bund x. Ich muss bsubals b - xund baddals berechnen b + x. Ich möchte jedoch nicht, dass während dieser Vorgänge ein Unterlauf / Überlauf auftritt. Zum Beispiel (Pseudocode):

b = 3; x = 5;
bsub = b - x; // bsub must be 0, not 254

und

b = 250; x = 10;
badd = b + x; // badd must be 255, not 4

Der offensichtliche Weg, dies zu tun, umfasst das Verzweigen:

bsub = b - min(b, x);
badd = b + min(255 - b, x);

Ich frage mich nur, ob es bessere Möglichkeiten gibt, dies zu tun, z. B. durch einige hackige Manipulationen?

Der Artikel Branchfree Saturating Arithmetic bietet Strategien dafür:

Ihre Additionslösung ist wie folgt:

u32b sat_addu32b(u32b x, u32b y)
{
    u32b res = x + y;
    res |= -(res < x);

    return res;
}

geändert für uint8_t:

uint8_t  sat_addu8b(uint8_t x, uint8_t y)
{
    uint8_t res = x + y;
    res |= -(res < x);

    return res;
}

und ihre Subtraktionslösung ist:

u32b sat_subu32b(u32b x, u32b y)
{
    u32b res = x - y;
    res &= -(res <= x);

    return res;
}

geändert für uint8_t:

uint8_t sat_subu8b(uint8_t x, uint8_t y)
{
    uint8_t res = x - y;
    res &= -(res <= x);

    return res;
}

Eine einfache Methode besteht darin, einen Überlauf zu erkennen und den Wert wie folgt entsprechend zurückzusetzen

bsub = b - x;
if (bsub > b)
{
    bsub = 0;
}

badd = b + x;
if (badd < b)
{
    badd = 255;
}

GCC kann die Überlaufprüfung beim Kompilieren mit -O2 in eine bedingte Zuordnung optimieren.

Ich habe gemessen, wie viel Optimierung im Vergleich zu anderen Lösungen. Bei mehr als 1000000000 Operationen auf meinem PC waren diese Lösung und die von @ShafikYaghmour durchschnittlich 4,2 Sekunden und die von @chux durchschnittlich 4,8 Sekunden. Diese Lösung ist auch besser lesbar.

Zur Subtraktion:

diff = (a - b)*(a >= b);

Zusatz:

sum = (a + b) | -(a > (255 - b))

Evolution

// sum = (a + b)*(a <= (255-b)); this fails
// sum = (a + b) | -(a <= (255 - b)) falis too

Dank an @R_Kapp

Dank an @NathanOliver

Diese Übung zeigt den Wert der einfachen Codierung.

sum = b + min(255 - b, a);

Wenn Sie eine aktuelle genug Version von gcc oder Klirren (vielleicht auch einige andere) verwenden könnten Sie Einbauten erkennen Überlauf.

if (__builtin_add_overflow(a,b,&c))
{
  c = UINT_MAX;
}

Zur Ergänzung:

unsigned temp = a+b;  // temp>>8 will be 1 if overflow else 0
unsigned char c = temp | -(temp >> 8);

Zur Subtraktion:

unsigned temp = a-b;  // temp>>8 will be 0xFF if neg-overflow else 0
unsigned char c = temp & ~(temp >> 8);

Keine Vergleichsoperatoren oder Multiplikationen erforderlich.

Wenn Sie bereit sind, Assembly oder Intrinsics zu verwenden, habe ich meiner Meinung nach eine optimale Lösung.

Zur Subtraktion:

Wir können die verwenden sbb Anweisung verwenden

In MSVC können wir die intrinsische Funktion _subborrow_u64 verwenden (auch in anderen Bitgrößen verfügbar).

So wird es verwendet:

// *c = a - (b + borrow)
// borrow_flag is set to 1 if (a < (b + borrow))
borrow_flag = _subborrow_u64(borrow_flag, a, b, c);

So können wir es auf Ihre Situation anwenden

uint64_t sub_no_underflow(uint64_t a, uint64_t b){
    uint64_t result;
    borrow_flag = _subborrow_u64(0, a, b, &result);
    return result * !borrow_flag;
}

Zur Ergänzung:

Wir können dieadcx Anweisung verwenden

In MSVC können wir die intrinsische Funktion _addcarry_u64 verwenden (auch in anderen Bitgrößen verfügbar).

So wird es verwendet:

// *c = a + b + carry
// carry_flag is set to 1 if there is a carry bit
carry_flag = _addcarry_u64(carry_flag, a, b, c);

So können wir es auf Ihre Situation anwenden

uint64_t add_no_overflow(uint64_t a, uint64_t b){
    uint64_t result;
    carry_flag = _addcarry_u64(0, a, b, &result);
    return !carry_flag * result - carry_flag;
}

Ich mag dieses nicht so sehr wie das Subtraktions-, aber ich denke, es ist ziemlich geschickt.

Wenn das Hinzufügen überläuft , carry_flag = 1. Wenn Sie nichts carry_flagsagen, erhalten Sie 0, !carry_flag * result = 0wenn also ein Überlauf vorliegt. Und da 0 - 1der vorzeichenlose Integralwert auf sein Maximum gesetzt wird, gibt die Funktion das Ergebnis der Addition zurück, wenn kein Übertrag vorliegt, und das Maximum des gewählten Integralwerts zurück, wenn ein Übertrag vorhanden ist.

was ist damit:

bsum = a + b;
bsum = (bsum < a || bsum < b) ? 255 : bsum;

bsub = a - b;
bsub = (bsub > a || bsub > b) ? 0 : bsub;

Alles kann in vorzeichenloser Bytearithmetik erfolgen

// Addition without overflow
return (b > 255 - a) ? 255 : a + b

// Subtraction without underflow
return (b > a) ? 0 : a - b;

Wenn Sie dies mit zwei Bytes tun möchten, verwenden Sie den einfachsten Code, der möglich ist.

Wenn Sie dies mit 20 Milliarden Bytes tun möchten, überprüfen Sie, welche Vektoranweisungen auf Ihrem Prozessor verfügbar sind und ob sie verwendet werden können. Möglicherweise kann Ihr Prozessor 32 dieser Vorgänge mit einer einzigen Anweisung ausführen.

Sie können auch die sichere numerische Bibliothek von Boost Library Incubator verwenden . Es bietet Drop-In-Ersatz für int, long usw., die garantieren, dass Sie niemals einen unerkannten Überlauf, Unterlauf usw. erhalten.

Wenn Sie diese Methoden häufig aufrufen, ist der schnellste Weg nicht die Bitmanipulation, sondern wahrscheinlich eine Nachschlagetabelle. Definieren Sie für jede Operation ein Array mit der Länge 511. Beispiel für Minus (Subtraktion)

static unsigned char   maxTable[511];
memset(maxTable, 0, 255);           // If smaller, emulates cutoff at zero
maxTable[255]=0;                    // If equal     - return zero
for (int i=0; i<256; i++)
    maxTable[255+i] = i;            // If greater   - return the difference

Das Array ist statisch und wird nur einmal initialisiert. Jetzt kann Ihre Subtraktion als Inline-Methode oder mithilfe des Pre-Compilers definiert werden:

#define MINUS(A,B)    maxTable[A-B+255];

Wie es funktioniert? Nun, Sie möchten alle möglichen Subtraktionen für vorzeichenlose Zeichen vorberechnen. Die Ergebnisse variieren von -255 bis +255, insgesamt 511 verschiedene Ergebnisse. Wir definieren ein Array aller möglichen Ergebnisse, aber da wir in C nicht über negative Indizes darauf zugreifen können, verwenden wir +255 (in [A-B + 255]). Sie können diese Aktion entfernen, indem Sie einen Zeiger auf die Mitte des Arrays definieren.

const unsigned char *result = maxTable+255;
#define MINUS(A,B)    result[A-B];

benutze es wie:

bsub  = MINUS(13,15); // i.e 13-15 with zero cutoff as requested

Beachten Sie, dass die Ausführung extrem schnell ist. Nur eine Subtraktion und eine Zeiger-Deferenz, um das Ergebnis zu erhalten. Keine Verzweigung. Die statischen Arrays sind sehr kurz, sodass sie vollständig in den CPU-Cache geladen werden, um die Berechnung weiter zu beschleunigen

Das Gleiche würde für die Addition funktionieren, jedoch mit einer etwas anderen Tabelle (die ersten 256 Elemente sind die Indizes und die letzten 255 Elemente sind gleich 255, um den Cutoff über 255 hinaus zu emulieren.

Wenn Sie auf einer Bitoperation bestehen, sind die Antworten, die (a> b) verwenden, falsch. Dies kann weiterhin als Verzweigung implementiert werden. Verwenden Sie die Vorzeichen-Bit-Technik

// (num1>num2) ? 1 : 0
#define        is_int_biggerNotEqual( num1,num2) ((((__int32)((num2)-(num1)))&0x80000000)>>31)

Jetzt können Sie es zur Berechnung der Subtraktion und Addition verwenden.

Wenn Sie die Funktionen max (), min () ohne Verzweigung emulieren möchten, verwenden Sie:

inline __int32 MIN_INT(__int32 x, __int32 y){   __int32 d=x-y; return y+(d&(d>>31)); }              

inline __int32 MAX_INT(__int32 x, __int32 y){   __int32 d=x-y; return x-(d&(d>>31)); }

Meine obigen Beispiele verwenden 32-Bit-Ganzzahlen. Sie können es in 64 ändern, obwohl ich glaube, dass 32-Bit-Berechnungen etwas schneller ablaufen. Wie du willst