Sättigung subtrahieren / addieren für vorzeichenlose Bytes

83

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?

ovk
quelle
13
y ^ ((x ^ y) & -(x < y))für intTypen wird min(x, y)ohne Verzweigung ausgewertet . Dies könnte Teil einer möglichen Lösung sein, basierend auf dem, was Sie bisher haben.
Bathseba
3
Vielleicht Clamped Increment Integer? ist hilfreich.
Shafik Yaghmour
8
Ist das eine C- oder eine C ++ - Frage? Bitte wähle eines.
Fuz
9
@AlanCampbell heißt es Saturating Arithmetic .
Shafik Yaghmour
7
Benötigen Sie es, um tragbar zu sein? Denn wenn Sie sich eine bestimmte Architektur ansehen, gibt es wahrscheinlich eine nette einzelne Anweisung. Ich weiß, dass ARM eine Sättigungsvektoraddition und -subtraktion für Bytes hat. Auf X86 führt das _mm_adds_epi8Intrinsic eine Sättigungsaddition von 16 Bytes in einem einzelnen Befehl durch.
Porglezomp

Antworten:

86

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;
}
Shafik Yaghmour
quelle
2
@ user1969104 das mag der Fall sein, aber wie der Kommentar im Artikel zeigt, wird dies durch Casting in unsigned gelöst, bevor unäres Minus angewendet wird. In der Praxis ist es unwahrscheinlich, dass Sie sich mit etwas anderem als dem Zweierkomplement befassen müssen .
Shafik Yaghmour
2
Dies mag eine gute C-Antwort sein, ist aber keine sehr gute C ++ - Antwort.
Yakk - Adam Nevraumont
4
@ Yakk Was macht dies zu einer "schlechten" C ++ - Antwort? Dies sind grundlegende mathematische Operationen, und ich sehe nicht, wie sie nur als C oder schlechtes C ++ interpretiert werden würden.
JPhi1618
4
@ JPhi1618 Eine bessere C ++ - Antwort könnte template<class T>struct sat{T t;};mit überladenen Operatoren sein, die gesättigt sind? Richtige Verwendung von Namespaces. Meistens Zucker.
Yakk - Adam Nevraumont
6
@ Yakk, Ah, ok. Ich habe dies nur als minimales Beispiel gesehen, das das OP nach Bedarf anpassen kann. Ich würde nicht erwarten, dass eine Implementierung vollständig ist. Danke fürs klarstellen.
JPhi1618
40

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.

user1969104
quelle
5
@ user694733 Es wird nicht entfernt, sondern in Abhängigkeit vom Übertragsflag in eine bedingte Zuordnung optimiert.
Fuz
2
Ja user694733 ist richtig. Es wird in eine bedingte Zuordnung optimiert.
user1969104
Dies würde nicht in allen Fällen funktionieren, zum Beispiel badd: b = 155 x = 201, als badd = 156, und das ist größer als b. Sie müssten das Ergebnis mit dem min () oder max () der beiden Variablen vergleichen, abhängig von der Operation
Cristian F
@CristianF Wie berechnet man 155 + 201 = 156? Ich denke, es muss 155 + 201 = 356% 256 = 100 sein. Ich denke nicht, dass min (), max () in irgendeiner Kombination von b, x-Werten benötigt wird.
user1969104
16

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);
chux - Monica wieder einsetzen
quelle
Für sumvielleicht (a + b) | -(a <= (255 - b))?
R_Kapp
Sie könnten es tun sum = ((a + b) | (!!((a + b) & ~0xFF) * 0xFF)) & 0xFF, vorausgesetzt sizeof(int) > sizeof(unsigned char), aber das sieht so komplex aus, dass ich nicht weiß, ob Sie damit etwas gewinnen würden (außer Kopfschmerzen).
user694733
@ user694733 Ja und vielleicht sogar (a+b+1)*(a <= (255-b)) - 1.
chux
@ NathanOliver Danke für das Versehen - der entscheidende Aspekt dabei ist, dass das subso einfach war wie das Limit 0. Andere Grenzwerte stellen jedoch Komplikationen dar und folgen dem Kommentar von user2079303 .
chux
1
@ user1969104 OP war weder bei "besser" (Codebereich vs. Geschwindigkeitsleistung) noch bei der Zielplattform oder dem Compiler klar. Die Geschwindigkeitsbewertung ist im Zusammenhang mit dem nicht veröffentlichten größeren Problem am sinnvollsten.
chux
13

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;
}
erebos
quelle
Dies ist die beste Antwort. Die Verwendung von Compiler-Integrationen anstelle von Bitmagie ist nicht nur schneller, sondern auch klarer und macht den Code wartbarer.
Kopffüßer
Vielen Dank, @erebos. Ich werde dies auf jeden Fall auf Plattformen versuchen, auf denen es verfügbar ist.
ovk
3
Ich kann gcc nicht dazu bringen, brachlosen Code mit diesem zu generieren, was ein bisschen enttäuschend ist. Das besonders Unglückliche dabei ist, dass Clang für diese unterschiedliche Namen verwendet .
Shafik Yaghmour
1
@Cephalopod Und es ist völlig plattformübergreifend, zum Teufel funktioniert es höchstwahrscheinlich nicht einmal auf einem anderen Compiler. Keine gute Lösung für das 21. Jahrhundert.
Ela782
1
@ Ela782 Es ist genau umgekehrt: Eingebaute sind keine gute Lösung für das 20. Jahrhundert. Willkommen in der Zukunft!
Kopffüßer
3

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.

Superkatze
quelle
3

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.

MichaelMitchell
quelle
1
Vielleicht möchten Sie erwähnen, dass diese Antwort für eine bestimmte Befehlssatzarchitektur (x86?) Gilt und für jede Zielarchitektur (SPARC, MIPS, ARM usw.) eine Neuimplementierung erfordert
Toby Speight,
2

was ist damit:

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

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

quelle
Ich habe den (offensichtlichen?) Tippfehler behoben, aber ich denke immer noch nicht, dass dies richtig ist.
Bathseba
Dies schließt auch die Verzweigung ein.
Fuz
Ich werde diese Antwort nur eine kurze Frage in der Baugruppe ohne Optimierung löschen. Was ist der Unterschied zwischen dem ternären Operator und der if / else-Anweisung?
@ GRC Es gibt keinen Unterschied.
Fuz
@GRC FUZxxl ist richtig, aber wie immer versuchen Sie es selbst. Selbst wenn Sie die Montage nicht kennen (Sie könnten hier auf SO eine Frage stellen, wenn Ihnen etwas nicht klar ist), überprüfen Sie einfach die Länge / Anweisungen, die Sie kennen.
Edmz
2

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;
Yves Daoust
quelle
1
Dies ist tatsächlich eine der besten Lösungen. Alle anderen, die zuvor die Subtraktion oder Addition vorgenommen haben, erstellen tatsächlich ein undefiniertes Verhalten in C ++, was dazu führt, dass der Compiler tun kann, was er will. In der Praxis kann man meistens vorhersagen, was passieren wird, aber immer noch.
Adrien Hamelin
2

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.

gnasher729
quelle
2

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.

Robert Ramey
quelle
7
Wenn Sie ein Beispiel für die Verwendung der Bibliothek angeben, ist dies eine bessere Antwort. Bieten sie außerdem eine Garantie ohne Brachless?
Shafik Yaghmour
Die Bibliothek verfügt über umfangreiche Dokumentationen und Beispiele. Aber am Ende des Tages ist es so einfach, den entsprechenden Header einzuschließen und int durch safe <int> zu ersetzen.
Robert Ramey
verzweigt? Ich denke du Mann ohne Zweig. Die Bibliothek verwendet die Metaprogrammierung von Vorlagen, um Laufzeitprüfungen nur bei Bedarf einzuschließen. Zum Beispiel führt ein vorzeichenloses Zeichen zu einem vorzeichenlosen int. Dies kann niemals überlaufen, so dass überhaupt keine Überprüfung durchgeführt werden muss. Auf der anderen Seite können vorzeichenlose Zeiten ohne Vorzeichen überlaufen, sodass sie zur Laufzeit überprüft werden müssen.
Robert Ramey
1

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

DanielHsH
quelle
2
Wahrscheinlich nicht: Erstens ist das Laden des Tisches natürlich langsam. Bitoperationen dauern 1 Zyklus, das Laden aus dem Speicher dauert ungefähr 80 ns; Selbst aus dem L1-Cache liegen wir im Bereich von 20 ns, was fast 7 Zyklen auf einer 3-GHz-CPU entspricht.
Edmz
Sie sind nicht ganz richtig. Die LUT-Methode benötigt einige Zyklen, aber die Bitmanipulation ist auch kein einzelner Zyklus. Es gibt einige aufeinanderfolgende Aktionen. Zum Beispiel erfordert nur die Berechnung von MAX () zwei Subtraktionen und eine logische Operation sowie eine Verschiebung nach rechts. Und vergessen Sie nicht die ganzzahlige Beförderung / Herabstufung
DanielHsH
1
Ich wollte damit sagen, dass einzelne bitweise Operationen 1 Zyklus dauern, wobei natürlich Registeroperanden angenommen werden. Mit dem Code, den Shafik zeigte, gibt clang 4 elementare Anweisungen aus. Auch (x > y)ist verzweigt.
Edmz
Erstens könnte (x> y) eine Verzweigung verwenden. Sie wissen nicht, auf welcher Architektur Sie ausgeführt werden. Ich stimme eher zu, dass es in der Intel-Architektur möglicherweise verzweigungslos ist. Die meisten Smartphones sind nicht Intel. Dies ist auch der Grund, warum Sie nicht wissen können, wie viele Montageanweisungen es geben wird. Probieren Sie meine Lösung auf Ihrem PC aus. Ich bin daran interessiert, die Ergebnisse zu hören.
DanielHsH
1
Der L1-Cache ist viel schneller als 20 ns und liegt in der Größenordnung von 4 Prozessorzyklen. Und wird wahrscheinlich eine ansonsten nicht verwendete Ausführungseinheit verwenden und trotzdem vollständig über eine Pipeline verfügen. Messe Es. Und 20 ns sind 60 Zyklen in einer 3-GHz-CPU.
gnasher729