Domanda Come fare l'aggiunta di saturazione in C?


Qual è il modo migliore (più pulito, più efficiente) per scrivere l'aggiunta di saturazione in C?

La funzione o la macro dovrebbe aggiungere due input non firmati (richiedono entrambe le versioni a 16 e 32 bit) e restituire all-bits-one (0xFFFF o 0xFFFFFFFF) se la somma trabocca.

Target è x86 e ARM che utilizza gcc (4.1.2) e Visual Studio (solo per la simulazione, quindi un'implementazione fallback è OK).


38
2017-09-23 14:12


origine


risposte:


Probabilmente vuoi un codice C portatile qui, che il tuo compilatore diventerà un assembly ARM corretto. ARM ha mosse condizionali, e queste possono essere condizionate dall'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;
}

Si noti che questo differisce dagli altri algoritmi in quanto corregge l'overflow, invece di affidarsi a un altro calcolo per rilevare l'overflow.

x86-64 clang 3.7 -O3 output per adds32: significativamente migliore di qualsiasi altra risposta:

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

ARMv7: gcc 4.8 -O3 -mcpu=cortex-a15 -fverbose-asm output per adds32:

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

16 bit: ancora non usa l'istruzione di aggiunta di saturazione non firmata 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  @

14
2017-10-03 11:22



In chiaro 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 macroizzato e trasmette direttamente il significato.


24
2017-09-23 16:57



In IA32 senza salti condizionali:

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
}

17
2017-09-23 14:31



In ARM potresti già avere un built-in aritmetico saturo. Le estensioni DSP ARMv5 possono saturare i registri su qualsiasi lunghezza di bit. Inoltre, la saturazione ARM è solitamente economica perché è possibile escludere la maggior parte delle istruzioni.

ARMv6 ha anche aggiunto saturo, sottrazione e tutte le altre cose per 32 bit e numeri confezionati.

Sull'86 si ottiene l'aritmetica satura tramite MMX o SSE.

Tutto ciò ha bisogno di un assemblatore, quindi non è quello che hai chiesto.

Ci sono trucchi a C per fare anche aritmetica satura. Questo piccolo codice aggiunge saturata su quattro byte di una dword. Si basa sull'idea di calcolare 32 semi-sommatori in parallelo, ad es. aggiungere numeri senza trasportare overflow.

Questo è fatto prima. Quindi i carry vengono calcolati, aggiunti e sostituiti con una maschera se l'addizione 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;
}

È possibile ottenere lo stesso per 16 bit (o qualsiasi tipo di campo di bit) modificando la costante di signmask 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;
}

Sopra il codice fa lo stesso per i valori a 16 e 32 bit.

Se non hai bisogno della funzione che le funzioni aggiungono e saturino più valori in parallelo, basta mascherare i bit di cui hai bisogno. Su ARM, inoltre, si desidera modificare la costante signmask perché ARM non può caricare tutte le possibili costanti a 32 bit in un singolo ciclo.

Modificare: Le versioni parallele sono molto probabilmente più lente dei metodi straight forward, ma sono più veloci se devi saturare più di un valore alla volta.


11
2017-09-23 14:26



Se ti importa delle prestazioni, tu veramente voglio fare questo genere di cose in SIMD, dove x86 ha un'aritmetica di saturazione nativa.

A causa di questa mancanza di aritmetica satura nella matematica scalare, si possono ottenere casi in cui le operazioni eseguite su SIMD a 4 variabili sono Di Più 4 volte più veloce rispetto all'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

10
2017-09-23 17:07



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 ottimizzerà questo per evitare di fare qualsiasi aritmetica effettiva a 64 bit (s>>32 sarà semplicemente la bandiera portante, e -(s>>32) è il risultato di sbb %eax,%eax).

In x86 asm (sintassi AT & T, a e b in eax e ebx, risultato in 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.


9
2017-08-07 19:12



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 */

Modificare: Ora che hai pubblicato la tua versione, non sono sicuro che il mio sia più pulito / migliore / più efficiente / più pratico.


7
2017-09-23 14:17



Non sono sicuro che sia più veloce della soluzione di Skizz (sempre profilo), ma ecco una soluzione di assemblaggio senza ramo alternativo. Nota che questo 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
    }
}

3
2017-09-23 15:37



L'attuale implementazione che stiamo utilizzando è:

#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)))

2
2017-09-23 14:18