Come eseguire l'aggiunta saturata senza segno in C?
https://stackoverflow.com/questions/121240
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Qual è il modo migliore (più pulito, più efficiente) per scrivere un'aggiunta satura in C?
La funzione o la macro dovrebbe aggiungere due input non firmati (sono necessarie entrambe le versioni a 16 e 32 bit) e restituire all-bit-one (0xFFFF o 0xFFFFFFFF) se la somma trabocca.
La destinazione è x86 e ARM con gcc (4.1.2) e Visual Studio (solo per simulazione, quindi un'implementazione di fallback è OK lì).
Soluzione
Probabilmente vuoi qui il codice C portatile, che il tuo compilatore trasformerà in un corretto assemblaggio ARM. ARM ha mosse condizionate e queste possono essere condizionate da un overflow. L'algoritmo diventa quindi add e imposta la destinazione su unsigned (-1) in modo condizionale se viene rilevato un overflow.
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;
}
Nota che questo differisce dagli altri algoritmi in quanto corregge l'overflow, invece di fare affidamento su un altro calcolo per rilevare l'overflow.
x86-64 clang 3.7 -O3 output per add3232 : significativamente migliore di qualsiasi altra risposta:
add edi, esi
mov eax, -1
cmovae eax, edi
ret
ARMv7: gcc 4.8 -O3 -mcpu = output cortx-a15 -fverbose-asm per add32 :
adds r0, r0, r1 @ c, a, b
it cs
movcs r0, #-1 @ conditional-move
bx lr
16 bit: continua a non utilizzare l'istruzione add di saturazione senza segno di 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 @
Altri suggerimenti
In semplice 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;}
che è quasi macronizzato e trasmette direttamente il significato.
In IA32 senza salti condizionati:
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 potresti avere già un'aritmetica saturata integrata. Le estensioni DSP ARMv5 possono saturare i registri a qualsiasi lunghezza di bit. Anche su ARM la saturazione è generalmente economica perché è possibile eseguire la maggior parte delle istruzioni condizionali.
ARMv6 ha anche addizioni, sottrazioni e tutte le altre cose sature per 32 bit e numeri compressi.
Sull'x86 si ottiene un'aritmetica satura tramite MMX o SSE.
Tutto ciò ha bisogno dell'assemblatore, quindi non è quello che hai chiesto.
Ci sono anche trucchi C per eseguire l'aritmetica satura. Questo piccolo codice fa un'aggiunta satura su quattro byte di una dword. Si basa sull'idea di calcolare 32 semicompositori in parallelo, ad es. aggiungere numeri senza carry overflow.
Questo viene fatto per primo. Quindi i carry vengono calcolati, aggiunti e sostituiti con una maschera se l'aggiunta dovesse traboccare.
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;
}
Puoi ottenere lo stesso per 16 bit (o qualsiasi tipo di campo di bit) modificando la costante della maschera di segno e gli spostamenti in basso in questo modo:
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;
}
Il codice sopra riportato fa lo stesso per i valori a 16 e 32 bit.
Se non hai bisogno della funzione che le funzioni aggiungono e saturano più valori in parallelo, maschera semplicemente i bit di cui hai bisogno. Su ARM vuoi anche cambiare la costante della maschera di segno perché ARM non può caricare tutte le possibili costanti a 32 bit in un singolo ciclo.
Modifica: Le versioni parallele sono molto probabilmente più lente dei metodi diretti, ma sono più veloci se devi saturare più di un valore alla volta.
Se ti preoccupi delle prestazioni, davvero vuoi fare questo genere di cose in SIMD, dove x86 ha un'aritmetica di saturazione nativa.
A causa di questa mancanza di saturazione dell'aritmetica nella matematica scalare, si possono ottenere casi in cui le operazioni eseguite su SIMD a 4 variabili di larghezza sono più di 4 volte più veloci dell'equivalente C (e corrispondentemente vero con SIMD a 8 variabili):
sub8x8_dct8_c: 1332 clocks
sub8x8_dct8_mmx: 182 clocks
sub8x8_dct8_sse2: 127 clocks
Soluzione zero branch:
uint32_t sadd32(uint32_t a, uint32_t b)
{
uint64_t s = (uint64_t)a+b;
return -(s>>32) | (uint32_t)s;
}
Un buon compilatore lo ottimizzerà per evitare di fare qualsiasi aritmetica a 64 bit ( s > > 32 sarà semplicemente il flag carry, e - (s > > 32) è il risultato di sbb% eax,% eax ).
In x86 asm (sintassi AT & amp; T, a e b in eax e ebx , si ottiene EAX ):
add %eax,%ebx
sbb %eax,%eax
or %ebx,%eax
Le versioni a 8 e 16 bit dovrebbero essere ovvie. La versione firmata potrebbe richiedere un po 'più di lavoro.
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 */
Modifica: Ora che hai pubblicato la tua versione, non sono sicuro che la mia sia più pulita / migliore / più efficiente / più studly.
Non sono sicuro che sia più veloce della soluzione di Skizz (sempre profilo), ma ecco una soluzione di assemblaggio senza diramazioni alternativa. Nota che ciò richiede l'istruzione di spostamento condizionale (CMOV), che non sono sicuro sia disponibile sul tuo obiettivo.
uint32_t sadd32(uint32_t a, uint32_t b)
{
__asm
{
movl eax, a
addl eax, b
movl edx, 0xffffffff
cmovc eax, edx
}
}
L'attuale implementazione che stiamo usando è:
#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)))
Le migliori prestazioni in genere coinvolgono l'assemblaggio in linea (come alcuni hanno già affermato).
Ma per il C portatile, queste funzioni implicano solo un confronto e nessun tipo di casting (e quindi credo ottimale):
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;
}
Come macro, diventano:
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)))
Lascio le versioni per 'unsigned long' e 'unsigned long long' come esercizio al lettore. ; -)
Nel caso in cui qualcuno voglia conoscere un'implementazione senza diramazione usando gli interi a 32 bit del complemento di 2.
Attenzione! Questo codice utilizza l'operazione non definita: "sposta a destra di -1" e quindi sfrutta la proprietà dell ' Istruzione Intel Pentium SAL per mascherare l'operando di conteggio a 5 bit.
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);
}
È la migliore implementazione a me nota
Suppongo che il modo migliore per x86 sia usare l'assemblatore in linea per controllare il flag di overflow dopo l'aggiunta. Qualcosa del tipo:
add eax, ebx
jno @@1
or eax, 0FFFFFFFFh
@@1:
.......
Non è molto portatile, ma IMHO è il modo più efficiente.
Un'alternativa alla soluzione x86 asm senza branch è (sintassi AT & amp; T, aeb in eax ed ebx, risulta in eax):
add %eax,%ebx
sbb <*>,%ebx
Usando C ++ potresti scrivere una variante più flessibile della soluzione di Remo.D :
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;
}
Questo può essere facilmente tradotto in C - usando i limiti definiti in limits.h . Tieni inoltre presente che i tipi di numeri interi a larghezza fissa potrebbero non essere disponibili sul tuo sistema.
//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;\
}\
})
Ho fatto un test rapido e sembra funzionare, ma non l'ho ancora ampiamente provato! Funziona con SIGNED 32 bit. op: l'editor utilizzato nella pagina Web non mi consente di pubblicare una macro, ovvero la sua non comprensione della sintassi non indentata, ecc.!
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);
}
Questa implementazione non utilizza flussi di controllo, operatori campare ( == , ! = ) e l'operatore ?: . Utilizza solo operatori bit per bit e operatori logici.
L'aritmetica della saturazione non è standard per C, ma è spesso implementata tramite intrinseci del compilatore, quindi il modo più efficiente non sarà il più pulito. È necessario aggiungere blocchi #ifdef per selezionare il modo corretto. La risposta di MSalters è la più veloce per l'architettura x86. Per ARM è necessario utilizzare la funzione __qadd16 (compilatore ARM) di _arm_qadd16 (Microsoft Visual Studio) per la versione a 16 bit e __qadd per 32-bit versione. Verranno automaticamente tradotti in un'istruzione ARM.
Link:
