Podpisano nasycony dodatek 64-bitowy ints?

Question

Szukam kodu C dla podpisanego nasyconego 64-bitowego dodatku, który kompiluje się do wydajnego kodu X86-64 z optymalizatorem gcc. Kod przenośny byłby idealny, chociaż w razie potrzeby można by zastosować rozwiązanie asm.

static const int64 kint64max = 0x7fffffffffffffffll; 
static const int64 kint64min = 0x8000000000000000ll; 

int64 signed_saturated_add(int64 x, int64 y) { 
    bool x_is_negative = (x & kint64min) != 0; 
    bool y_is_negative = (y & kint64min) != 0; 
    int64 sum = x+y; 
    bool sum_is_negative = (sum & kint64min) != 0; 
    if (x_is_negative != y_is_negative) return sum; // can't overflow 
    if (x_is_negative && !sum_is_negative) return kint64min; 
    if (!x_is_negative && sum_is_negative) return kint64max; 
    return sum; 
} 

Funkcja w formie pisemnej wytwarza dość długie wyjście zespołu z kilkoma odgałęzieniami. Wszelkie wskazówki dotyczące optymalizacji? Wygląda na to, że powinno być możliwe do wdrożenia za pomocą tylko ADD z kilkoma instrukcjami CMOV, ale jestem trochę zardzewiały z tego typu rzeczy.

Answer 1

ciągle szukam godnej przenośnego rozwiązania, ale to jest tak dobre, jak wpadliśmy do tej pory:

propozycje zmian?

int64 saturated_add(int64 x, int64 y) { 
#if __GNUC__ && __X86_64__ 
    asm("add %1, %0\n\t" 
     "jno 1f\n\t" 
     "cmovge %3, %0\n\t" 
     "cmovl %2, %0\n" 
     "1:" : "+r"(x) : "r"(y), "r"(kint64min), "r"(kint64max)); 
    return x; 
#else 
    return portable_saturated_add(x, y); 
#endif 
} 

Answer 2

Można to zoptymalizować, ale tutaj jest to przenośne rozwiązanie. Nie wywołuje niezdefiniowanego zachowania i sprawdza przed przepełnieniem, czy mogło wystąpić.

#include <stdint.h> 

int64_t sadd64(int64_t a, int64_t b) 
{ 
    if (a > 0) { 
     if (b > INT64_MAX - a) { 
      return INT64_MAX; 
     } 
    } else if (b < INT64_MIN - a) { 
      return INT64_MIN; 
    } 

    return a + b; 
} 

Answer 3

Jest to rozwiązanie, które trwa nadal w temacie podanym w jednym z komentarzy i zostało również zastosowane w rozwiązaniu ouah. tutaj wygenerowany kod powinien być bez skoków warunkowych

int64_t signed_saturated_add(int64_t x, int64_t y) { 
    // determine the lower or upper bound of the result 
    int64_t ret = (x < 0) ? INT64_MIN : INT64_MAX; 
    // this is always well defined: 
    // if x < 0 this adds a positive value to INT64_MIN 
    // if x > 0 this subtracts a positive value from INT64_MAX 
    int64_t comp = ret - x; 
    // the condition is equivalent to 
    // ((x < 0) && (y > comp)) || ((x >=0) && (y <= comp)) 
    if ((x < 0) == (y > comp)) ret = x + y; 
    return ret; 
} 

Pierwsze wygląda tak, jakby nie byłoby warunkowe przejście do zrobienia, ale ze względu na szczególne walory mój kompilator wysiada z dodatkiem: w 2 uzupełnień INT64_MIN jest INT64_MAX+1 . Jest wtedy tylko jeden ruch warunkowy dla przypisania sumy, na wypadek, gdyby cokolwiek było w porządku.

Wszystko to nie ma UB, ponieważ w abstrakcyjnej maszynie stanów suma jest wykonywana tylko wtedy, gdy nie ma przepełnienia.