Wie unsigned sättigende zusätzlich in C zu tun?
https://stackoverflow.com/questions/121240
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Was ist die beste (saubersten, effizientesten) Art und Weise zu sättigen zusätzlich in C zu schreiben?
Die Funktion oder Makro sollte zwei unsigned Eingänge hinzufügen (müssen sowohl 16- als auch 32-Bit-Versionen) und kehren alle Bits-on (0xFFFF oder 0xFFFFFFFF), wenn die Summe überläuft.
Ziel ist x86 und ARM mit gcc (4.1.2) und Visual Studio (für die Simulation nur, so dass ein Rückfall Implementierung ist OK dort).
Lösung
Sie wahrscheinlich tragbaren C Code wollen hier, die der Compiler in die richtige ARM Montage verwandeln wird. ARM hat bedingte Bewegungen, und diese können bei Überlauf abhängig gemacht werden. Der Algorithmus wird dann hinzufügen, und legen Sie bedingt das Ziel ohne Vorzeichen (-1), wenn Ü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 dies unterscheidet sich von den anderen Algorithmen, dass es Überlauf korrigiert, sondern auf eine andere Berechnung der Berufung Überlauf zu erfassen.
x86-64 klappern 3.7 O3 Ausgang 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 Ausgang für adds32 :
adds r0, r0, r1 @ c, a, b
it cs
movcs r0, #-1 @ conditional-move
bx lr
16bit: noch nicht verwendet ARM unsigned sättigende hinzufügen Anweisung (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 @
Andere Tipps
Im Klar 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 Makro-ized und vermittelt direkt die Bedeutung.
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
}
In ARM können Sie bereits Arithmetik Einbau-gesättigt. Die ARMv5 DSP-Erweiterungen können Register in jedem Bit-Länge sättigen. Auch für ARM-Sättigung ist in der Regel billig, weil Sie die meisten Befehle bedingt excute können.
ARMv6 hat sogar gesättigte Addition, Subtraktion und all die anderen Sachen für 32 Bit und gepackte Zahlen.
Auf der x86 Sie Arithmetik erhalten entweder über MMX oder SSE gesättigt.
All dies muss Assembler, so ist es nicht, was Sie gefragt haben.
Es gibt C-Tricks sowie gesättigte Arithmetik zu tun. Dieser kleine Code nicht gesättigt zusätzlich auf vier Bytes eines dword. Es basiert auf der Idee 32 Halbaddierer parallel zu berechnen, z.B. Addieren von Zahlen ohne Übertrag Überlauf.
Dies wird zuerst getan. Dann führen die berechnet werden, hinzugefügt und mit einer Maske ersetzt, wenn die Zugabe überfluten 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 das gleiche bekommen für 16 Bits (oder jede Art von Bit-Feld) durch die signmask konstant verändert und die Verschiebungen am Ende wie folgt aus:
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;
}
über Code macht das gleiche für 16 und 32-Bit-Werte.
Wenn Sie die Funktion nicht benötigen, dass die Funktionen hinzufügen und mehrere Werte parallel sättigen nur die Bits maskieren Sie benötigen. Auf ARM wollen Sie auch die signmask konstant ändern, da ARM nicht alle möglichen 32-Bit-Konstanten in einem einzigen Zyklus geladen werden kann.
Edit:. Die parallelen Versionen sind wahrscheinlich langsamer als die gerade nach vorne Methoden, aber sie sind schneller, wenn Sie mehr als einen Wert zu einem Zeitpunkt, zu sättigen haben
Wenn Sie über die Leistung kümmern, Sie wirklich will in SIMD diese Art von Sachen zu tun, wo x86 nativen sättigende Arithmetik hat.
Aufgrund dieser fehlenden Arithmetik in skalare mathematische sättigt, kann man bekommen Fälle, in denen auf 4-variable weiten SIMD getan Operationen mehr als 4-mal schneller als das Äquivalent C (und entsprechend wahr mit 8-Variable weite SIMD):
sub8x8_dct8_c: 1332 clocks
sub8x8_dct8_mmx: 182 clocks
sub8x8_dct8_sse2: 127 clocks
Nullbranchenlö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 diese Optimierung tun eine tatsächliche 64-Bit-Arithmetik (s>>32 wird lediglich das Carry-Flag sein, und -(s>>32) ist das Ergebnis sbb %eax,%eax) zu vermeiden.
In x86 asm (AT & T-Syntax, a und b in eax und ebx, führt in eax):
add %eax,%ebx
sbb %eax,%eax
or %ebx,%eax
8- und 16-Bit-Versionen sollten klar sein. Signed Version könnte ein bisschen mehr Arbeit erfordern.
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 */
Edit:. Nun, da Sie Ihre Version geschrieben habe, ich bin nicht sicher, ob ich ist jeder Reiniger / besser / effiziente / mehr studly
Ich bin mir nicht sicher, ob dies ist schneller als Skizz-Lösung (immer Profil), aber hier ist eine Alternative No-Abzweigungszusammenbau Lösung. Beachten Sie, dass dies die bedingte Bewegung (CMOV) Instruktion erfordert, die ich bin nicht sicher, auf Ihr Ziel verfügbar ist.
uint32_t sadd32(uint32_t a, uint32_t b)
{
__asm
{
movl eax, a
addl eax, b
movl edx, 0xffffffff
cmovc eax, edx
}
}
Die aktuelle Implementierung wir verwenden, ist:
#define sadd16(a, b) (uint16_t)( ((uint32_t)(a)+(uint32_t)(b)) > 0xffff ? 0xffff : ((a)+(b)))
#define sadd32(a, b) (uint32_t)( ((uint64_t)(a)+(uint64_t)(b)) > 0xffffffff ? 0xffffffff : ((a)+(b)))
Die beste Leistung wird in der Regel Inline-Assembler beinhaltet (wie einige bereits festgestellt haben).
Aber für tragbare C, diese Funktionen beinhalten nur einen Vergleich und keinen Typen-Casting (und somit glaube ich optimal):
unsigned saturate_add_uint(unsigned x, unsigned y)
{
if (y>UINT_MAX-x) return UINT_MAX;
return x+y;
}
unsigned short saturate_add_ushort(unsigned short x, unsigned short y)
{
if (y>USHRT_MAX-x) return USHRT_MAX;
return x+y;
}
Als Makros, sie werden:
SATURATE_ADD_UINT(x, y) (((y)>UINT_MAX-(x)) ? UINT_MAX : ((x)+(y)))
SATURATE_ADD_USHORT(x, y) (((y)>SHRT_MAX-(x)) ? USHRT_MAX : ((x)+(y)))
Ich lasse Versionen für ‚unsigned long‘ und ‚unsigned long long‘ als eine Übung für den Leser. ; -)
Für den Fall, jemand will eine Implementierung wissen, ohne 32-Bit-Integer mit 2-Komplement-Verzweigung.
Achtung! Dieser Code verwendet die undefinierte Operation: „nach rechts verschieben mit -1“ und daher nutzt die Eigenschaft des Intel Pentium SAL Anweisung die Zählwertoperand auf 5 Bits zu maskieren.
int32_t sadd(int32_t a, int32_t b){
int32_t sum = a+b;
int32_t overflow = ((a^sum)&(b^sum))>>31;
return (overflow<<31)^(sum>>overflow);
}
Es ist die beste Umsetzung mir bekannt
Ich nehme an, der beste Weg für x86 ist Inline-Assembler zu verwenden, Überlauf-Flag nach der Zugabe zu überprüfen. So etwas wie:
add eax, ebx
jno @@1
or eax, 0FFFFFFFFh
@@1:
.......
Es ist nicht sehr tragbar, aber IMHO die effizienteste Art und Weise.
Eine Alternative zu der freien Zweig x86 ASM Lösung (AT & T-Syntax, a und b in EAX und EBX, führt in EAX):
add %eax,%ebx
sbb $0,%ebx
Mit C ++ Sie eine flexiblere Variante schreiben könnte Remo.D 's Lösung:
template<typename T>
T sadd(T first, T second)
{
static_assert(std::is_integral<T>::value, "sadd is not defined for non-integral types");
return first > std::numeric_limits<T>::max() - second ? std::numeric_limits<T>::max() : first + second;
}
Dies kann leicht zu C übersetzt werden - die Grenzen in limits.h definiert ist. Bitte beachten Sie auch, dass die auf Ihrem System möglicherweise nicht zur Verfügung.
//function-like macro to add signed vals,
//then test for overlow and clamp to max if required
#define SATURATE_ADD(a,b,val) ( {\
if( (a>=0) && (b>=0) )\
{\
val = a + b;\
if (val < 0) {val=0x7fffffff;}\
}\
else if( (a<=0) && (b<=0) )\
{\
val = a + b;\
if (val > 0) {val=-1*0x7fffffff;}\
}\
else\
{\
val = a + b;\
}\
})
habe ich einen schnellen Test und scheint zu funktionieren, aber nicht extensiv es noch heftig geschlagen! Dies funktioniert mit signierten 32-Bit. op: der Editor auf der Webseite verwendet wird, nicht lassen Sie mich ein Makro schreiben, dh es ist nicht zu verstehen, nicht gegliederte Syntax etc
int saturating_add(int x, int y)
{
int w = sizeof(int) << 3;
int msb = 1 << (w-1);
int s = x + y;
int sign_x = msb & x;
int sign_y = msb & y;
int sign_s = msb & s;
int nflow = sign_x && sign_y && !sign_s;
int pflow = !sign_x && !sign_y && sign_s;
int nmask = (~!nflow + 1);
int pmask = (~!pflow + 1);
return (nmask & ((pmask & s) | (~pmask & ~msb))) | (~nmask & msb);
}
Diese Implementierung verfügt selbst nicht fließt, campare Operatoren (==, !=) und der ?: Betreiber. Es verwendet nur bitweise Operatoren und logische Operatoren.
Sättigungsarithmetik ist für C nicht Standard, aber es ist oft über Compiler-Spezifika implementiert, so dass der effizienteste Weg, nicht das sauberste sein. Sie müssen #ifdef Blöcke wählen Sie die richtige Art und Weise hinzuzufügen. MSalters Antwort ist die schnellste für x86-Architektur. Für ARM müssen Sie __qadd16 Funktion (ARM Compiler) von _arm_qadd16 (Microsoft Visual Studio) für 16-Bit-Version und __qadd für 32-Bit-Version verwenden. Sie werden automatisch auf einen ARM-Befehl übersetzt werden.
Links:
