Wie führt man eine vorzeichenlose Sättigungsaddition in C durch?

Question 1

Was ist der beste (sauberste, effizienteste) Weg, um eine Sättigungsaddition in C zu schreiben?

Die Funktion oder das Makro sollte zwei vorzeichenlose Eingaben hinzufügen (benötigt sowohl 16- als auch 32-Bit-Versionen) und alle Bits-Eins (0xFFFF oder 0xFFFFFFFF) zurückgeben, wenn die Summe überläuft.

Ziel ist x86 und ARM mit gcc (4.1.2) und Visual Studio (nur zur Simulation, daher ist eine Fallback-Implementierung dort in Ordnung).

Question 2

Wahrscheinlich möchten Sie hier portablen C-Code, den Ihr Compiler in eine richtige ARM-Assembly umwandelt. ARM hat bedingte Bewegungen, und diese können vom Überlauf abhängig sein. Der Algorithmus lautet dann: Füge das Ziel hinzu und setze es bedingt auf unsigned(-1), wenn ein Überlauf erkannt wurde.

uint16_t add16(uint16_t a, uint16_t b)
{
  uint16_t c = a + b;
  if (c < a)  /* Can only happen due to overflow */
    c = -1;
  return c;
}

Beachten Sie, dass sich dies von den anderen Algorithmen darin unterscheidet, dass es einen Überlauf korrigiert, anstatt sich auf eine andere Berechnung zu verlassen, um einen Überlauf zu erkennen.

x86-64 clang 3.7 -O3-Ausgabe für adds32: deutlich besser als jede andere Antwort:

add     edi, esi
mov     eax, -1
cmovae  eax, edi
ret

ARMv7: gcc 4.8 -O3 -mcpu=cortex-a15 -fverbose-asm Ausgabe für adds32:

adds    r0, r0, r1      @ c, a, b
it      cs
movcs   r0, #-1         @ conditional-move
bx      lr

16bit: verwendet immer noch nicht den unsigned-saturating add-Befehl von ARM (UADD16)

add     r1, r1, r0        @ tmp114, a
movw    r3, #65535      @ tmp116,
uxth    r1, r1  @ c, tmp114
cmp     r0, r1    @ a, c
ite     ls        @
movls   r0, r1        @,, c
movhi   r0, r3        @,, tmp116
bx      lr  @

Question 3

In normalem C:

uint16_t sadd16(uint16_t a, uint16_t b) {
  return (a > 0xFFFF - b) ? 0xFFFF : a + b;
}
     
uint32_t sadd32(uint32_t a, uint32_t b) {
  return (a > 0xFFFFFFFF - b) ? 0xFFFFFFFF : a + b;
}

die fast makroisiert ist und die Bedeutung direkt vermittelt.

Question 4

In IA32 ohne bedingte Sprünge:

uint32_t sadd32(uint32_t a, uint32_t b)
{
#if defined IA32
  __asm
  {
    mov eax,a
    xor edx,edx
    add eax,b
    setnc dl
    dec edx
    or eax,edx
  }
#elif defined ARM
  // ARM code
#else
  // non-IA32/ARM way, copy from above
#endif
}

Question 5

In ARM ist möglicherweise bereits gesättigte Arithmetik integriert. Die ARMv5 DSP-Erweiterungen können Register auf jede Bitlänge sättigen. Auch auf ARM ist die Sättigung meist günstig, da man die meisten Befehle bedingt ausführen kann.

ARMv6 hat sogar gesättigte Addition, Subtraktion und all das andere Zeug für 32 Bit und gepackte Zahlen.

Auf dem x86 erhalten Sie entweder über MMX oder SSE gesättigte Arithmetik.

All dies erfordert Assembler, also ist es nicht das, wonach Sie gefragt haben.

Es gibt auch C-Tricks für gesättigte Arithmetik. Dieser kleine Code führt eine gesättigte Addition von vier Bytes eines Doppelworts durch. Es basiert auf der Idee, 32 Halbaddierer parallel zu berechnen, also zB Zahlen ohne Übertrag zu addieren.

Dies wird zuerst erledigt. Dann werden die Überträge berechnet, addiert und durch eine Maske ersetzt, falls die Addition überlaufen würde.

uint32_t SatAddUnsigned8(uint32_t x, uint32_t y) 
{
  uint32_t signmask = 0x80808080;
  uint32_t t0 = (y ^ x) & signmask;
  uint32_t t1 = (y & x) & signmask;
  x &= ~signmask;
  y &= ~signmask;
  x += y;
  t1 |= t0 & x;
  t1 = (t1 << 1) - (t1 >> 7);
  return (x ^ t0) | t1;
}

Sie können dasselbe für 16 Bit (oder jede Art von Bitfeld) erhalten, indem Sie die Zeichenmaskenkonstante und die Verschiebungen unten wie folgt ändern:

uint32_t SatAddUnsigned16(uint32_t x, uint32_t y) 
{
  uint32_t signmask = 0x80008000;
  uint32_t t0 = (y ^ x) & signmask;
  uint32_t t1 = (y & x) & signmask;
  x &= ~signmask;
  y &= ~signmask;
  x += y;
  t1 |= t0 & x;
  t1 = (t1 << 1) - (t1 >> 15);
  return (x ^ t0) | t1;
}

uint32_t SatAddUnsigned32 (uint32_t x, uint32_t y)
{
  uint32_t signmask = 0x80000000;
  uint32_t t0 = (y ^ x) & signmask;
  uint32_t t1 = (y & x) & signmask;
  x &= ~signmask;
  y &= ~signmask;
  x += y;
  t1 |= t0 & x;
  t1 = (t1 << 1) - (t1 >> 31);
  return (x ^ t0) | t1;
}

Der obige Code macht dasselbe für 16- und 32-Bit-Werte.

Wenn Sie die Funktion nicht benötigen, dass die Funktionen mehrere Werte parallel addieren und sättigen, maskieren Sie einfach die benötigten Bits. Auf ARM möchten Sie auch die Signmask-Konstante ändern, da ARM nicht alle möglichen 32-Bit-Konstanten in einem einzigen Zyklus laden kann.

Bearbeiten: Die parallelen Versionen sind höchstwahrscheinlich langsamer als die direkten Methoden, aber sie sind schneller, wenn Sie mehr als einen Wert gleichzeitig sättigen müssen.

Question 6

Wenn Sie Wert auf Leistung legen, Sie Ja wirklich Ich möchte solche Sachen in SIMD machen, wo x86 eine native Sättigungsarithmetik hat.

Aufgrund dieses Mangels an sättigender Arithmetik in der Skalarmathematik kann es Fälle geben, in denen Operationen auf SIMD mit 4 Variablen durchgeführt werden mehr als 4-mal schneller als das entsprechende C (und entsprechend wahr mit 8-Variablen-breitem SIMD):

sub8x8_dct8_c: 1332 clocks
sub8x8_dct8_mmx: 182 clocks
sub8x8_dct8_sse2: 127 clocks

Question 7

Zero-Branch-Lösung:

uint32_t sadd32(uint32_t a, uint32_t b)
{
    uint64_t s = (uint64_t)a+b;
    return -(s>>32) | (uint32_t)s;
}

Ein guter Compiler wird dies optimieren, um zu vermeiden, dass tatsächlich 64-Bit-Arithmetik durchgeführt wird (s>>32 wird lediglich das Carry-Flag sein, und -(s>>32) ist das Ergebnis von sbb %eax,%eax).

In x86 asm (AT&T-Syntax, a und b in eax und ebxergeben eax):

add %eax,%ebx
sbb %eax,%eax
or %ebx,%eax

8- und 16-Bit-Versionen sollten offensichtlich sein. Die signierte Version erfordert möglicherweise etwas mehr Arbeit.

Question 8

uint32_t saturate_add32(uint32_t a, uint32_t b)
{
    uint32_t sum = a + b;
    if ((sum < a) || (sum < b))
        return ~((uint32_t)0);
    else
        return sum;
} /* saturate_add32 */

uint16_t saturate_add16(uint16_t a, uint16_t b)
{
    uint16_t sum = a + b;
    if ((sum < a) || (sum < b))
        return ~((uint16_t)0);
    else
        return sum;
} /* saturate_add16 */

Bearbeiten: Jetzt, da Sie Ihre Version gepostet haben, bin ich mir nicht sicher, ob meine sauberer/besser/effizienter/studierter ist.