Nasycenie odejmowania / dodawania dla bajtów bez znaku

Wyobraź sobie, że mam dwa bajty bez znaku bi x. Muszę obliczyć bsubjako b - xi baddjako b + x. Jednak nie chcę, aby podczas tych operacji wystąpił niedomiar / przepełnienie. Na przykład (pseudokod):

b = 3; x = 5;
bsub = b - x; // bsub must be 0, not 254

i

b = 250; x = 10;
badd = b + x; // badd must be 255, not 4

Oczywistym sposobem na to jest rozgałęzienie:

bsub = b - min(b, x);
badd = b + min(255 - b, x);

Zastanawiam się tylko, czy są jakieś lepsze sposoby, aby to zrobić, np. Przez jakieś hackerskie manipulacje?

Artykuł Branchfree Saturating Arithmetic przedstawia strategie w tym zakresie:

Ich rozwiązanie do dodawania jest następujące:

u32b sat_addu32b(u32b x, u32b y)
{
    u32b res = x + y;
    res |= -(res < x);

    return res;
}

zmodyfikowany dla uint8_t:

uint8_t  sat_addu8b(uint8_t x, uint8_t y)
{
    uint8_t res = x + y;
    res |= -(res < x);

    return res;
}

a ich rozwiązanie odejmowania to:

u32b sat_subu32b(u32b x, u32b y)
{
    u32b res = x - y;
    res &= -(res <= x);

    return res;
}

zmodyfikowany dla uint8_t:

uint8_t sat_subu8b(uint8_t x, uint8_t y)
{
    uint8_t res = x - y;
    res &= -(res <= x);

    return res;
}

Prostą metodą jest wykrycie przepełnienia i odpowiednie zresetowanie wartości, jak poniżej

bsub = b - x;
if (bsub > b)
{
    bsub = 0;
}

badd = b + x;
if (badd < b)
{
    badd = 255;
}

GCC może zoptymalizować sprawdzanie przepełnienia do przypisania warunkowego podczas kompilacji z -O2.

Zmierzyłem, ile optymalizacji w porównaniu z innymi rozwiązaniami. Przy 1000000000+ operacjach na moim komputerze rozwiązanie to i @ShafikYaghmour wynosiło średnio 4,2 sekundy, a @chux średnio 4,8 sekundy. To rozwiązanie jest również bardziej czytelne.

Do odejmowania:

diff = (a - b)*(a >= b);

Dodanie:

sum = (a + b) | -(a > (255 - b))

Ewolucja

// sum = (a + b)*(a <= (255-b)); this fails
// sum = (a + b) | -(a <= (255 - b)) falis too

Dzięki @R_Kapp

Dzięki @NathanOliver

To ćwiczenie pokazuje wartość prostego kodowania.

sum = b + min(255 - b, a);

Jeśli używasz wystarczająco aktualnej wersji gcc lub clang (może także innych), możesz użyć wbudowanych funkcji do wykrywania przepełnienia.

if (__builtin_add_overflow(a,b,&c))
{
  c = UINT_MAX;
}

Dodatkowo:

unsigned temp = a+b;  // temp>>8 will be 1 if overflow else 0
unsigned char c = temp | -(temp >> 8);

Do odejmowania:

unsigned temp = a-b;  // temp>>8 will be 0xFF if neg-overflow else 0
unsigned char c = temp & ~(temp >> 8);

Nie są wymagane żadne operatory porównania ani mnożenia.

Jeśli chcesz skorzystać z montażu lub intrinsics, myślę, że mam optymalne rozwiązanie.

Do odejmowania:

Możemy skorzystać z sbbinstrukcji

W MSVC możemy użyć funkcji wewnętrznej _subborrow_u64 (dostępnej również w innych rozmiarach bitowych).

Oto, jak jest używany:

// *c = a - (b + borrow)
// borrow_flag is set to 1 if (a < (b + borrow))
borrow_flag = _subborrow_u64(borrow_flag, a, b, c);

Oto, jak możemy to zastosować w twojej sytuacji

uint64_t sub_no_underflow(uint64_t a, uint64_t b){
    uint64_t result;
    borrow_flag = _subborrow_u64(0, a, b, &result);
    return result * !borrow_flag;
}

Dodatkowo:

Możemy skorzystać z adcxinstrukcji

W MSVC możemy użyć funkcji wewnętrznej _addcarry_u64 (dostępnej również w innych rozmiarach bitowych).

Oto, jak jest używany:

// *c = a + b + carry
// carry_flag is set to 1 if there is a carry bit
carry_flag = _addcarry_u64(carry_flag, a, b, c);

Oto, jak możemy to zastosować w twojej sytuacji

uint64_t add_no_overflow(uint64_t a, uint64_t b){
    uint64_t result;
    carry_flag = _addcarry_u64(0, a, b, &result);
    return !carry_flag * result - carry_flag;
}

Nie lubię tego tak bardzo, jak odejmowania, ale myślę, że jest całkiem fajny.

Jeśli dodatek przelewa, carry_flag = 1. Noting carry_flagdaje 0, więc !carry_flag * result = 0gdy występuje przepełnienie. A ponieważ 0 - 1ustawi wartość całki bez znaku na maksimum, funkcja zwróci wynik dodawania, jeśli nie ma przeniesienia, i zwróci maksimum wybranej wartości całkowitej, jeśli istnieje przeniesienie.

a co z tym:

bsum = a + b;
bsum = (bsum < a || bsum < b) ? 255 : bsum;

bsub = a - b;
bsub = (bsub > a || bsub > b) ? 0 : bsub;

Wszystko można wykonać w arytmetyce bajtów bez znaku

// Addition without overflow
return (b > 255 - a) ? 255 : a + b

// Subtraction without underflow
return (b > a) ? 0 : a - b;

Jeśli chcesz to zrobić z dwoma bajtami, użyj najprostszego możliwego kodu.

Jeśli chcesz to zrobić z dwudziestoma miliardami bajtów, sprawdź, jakie instrukcje wektorowe są dostępne w twoim procesorze i czy można ich użyć. Może się okazać, że twój procesor może wykonać 32 z tych operacji za pomocą jednej instrukcji.

Możesz także skorzystać z bezpiecznej biblioteki numerycznej w Boost Library Incubator . Zapewnia zamienniki typu drop-in dla int, long itp., Które gwarantują, że nigdy nie dostaniesz niewykrytego przepełnienia, niedomiaru itp.

Jeśli będziesz często wywoływał te metody, najszybszym sposobem nie byłaby manipulacja bitami, ale prawdopodobnie tabela przeglądowa. Zdefiniuj tablicę o długości 511 dla każdej operacji. Przykład na minus (odejmowanie)

static unsigned char   maxTable[511];
memset(maxTable, 0, 255);           // If smaller, emulates cutoff at zero
maxTable[255]=0;                    // If equal     - return zero
for (int i=0; i<256; i++)
    maxTable[255+i] = i;            // If greater   - return the difference

Tablica jest statyczna i inicjowana tylko raz. Teraz odejmowanie można zdefiniować jako metodę inline lub za pomocą prekompilatora:

#define MINUS(A,B)    maxTable[A-B+255];

Jak to działa? Cóż, chcesz wstępnie obliczyć wszystkie możliwe odejmowania dla znaków bez znaku. Wyniki wahają się od -255 do +255, łącznie 511 różnych wyników. Definiujemy tablicę wszystkich możliwych wyników, ale ponieważ w C nie mamy do niej dostępu z ujemnych indeksów, używamy +255 (w [A-B + 255]). Możesz usunąć tę akcję, definiując wskaźnik do środka tablicy.

const unsigned char *result = maxTable+255;
#define MINUS(A,B)    result[A-B];

użyj go jak:

bsub  = MINUS(13,15); // i.e 13-15 with zero cutoff as requested

Zwróć uwagę, że wykonanie jest niezwykle szybkie. Tylko jedno odejmowanie i jedno uwzględnienie wskaźnika, aby otrzymać wynik. Bez rozgałęzień. Tablice statyczne są bardzo krótkie, więc zostaną w pełni załadowane do pamięci podręcznej procesora, aby jeszcze bardziej przyspieszyć obliczenia

To samo zadziała w przypadku dodawania, ale z nieco inną tabelą (pierwsze 256 elementów będzie indeksami, a ostatnie 255 elementów będzie równe 255, aby emulować odcięcie powyżej 255.

Jeśli nalegasz na operację na bitach, odpowiedzi, które używają (a> b) są błędne. To nadal może być realizowane jako rozgałęzienie. Użyj techniki znaków bitowych

// (num1>num2) ? 1 : 0
#define        is_int_biggerNotEqual( num1,num2) ((((__int32)((num2)-(num1)))&0x80000000)>>31)

Teraz możesz go użyć do obliczenia odejmowania i dodawania.

Jeśli chcesz emulować funkcje max (), min () bez rozgałęziania użyj:

inline __int32 MIN_INT(__int32 x, __int32 y){   __int32 d=x-y; return y+(d&(d>>31)); }              

inline __int32 MAX_INT(__int32 x, __int32 y){   __int32 d=x-y; return x-(d&(d>>31)); }

W powyższych przykładach używam 32-bitowych liczb całkowitych. Możesz zmienić to na 64, chociaż uważam, że 32-bitowe obliczenia działają nieco szybciej. Zależy od Ciebie