Podpisane przepełnienie w C ++ i niezdefiniowane zachowanie (UB)

Zastanawiam się nad użyciem kodu takiego jak poniżej

int result = 0;
int factor = 1;
for (...) {
    result = ...
    factor *= 10;
}
return result;

Jeśli pętla jest iterowana w nczasie, to factorjest mnożona przez 10dokładnie nrazy. Jednak factorjest on używany tylko po pomnożeniu przez 10łączną liczbę n-1razy. Jeśli założymy, że factornigdy nie przepełnia się z wyjątkiem ostatniej iteracji pętli, ale może przepełniać się podczas ostatniej iteracji pętli, to czy taki kod powinien być akceptowalny? W takim przypadku wartość factorprawdopodobnie nigdy nie zostanie wykorzystana po wystąpieniu przepełnienia.

Mam debatę na temat tego, czy taki kod powinien zostać zaakceptowany. Byłoby możliwe umieszczenie mnożenia wewnątrz instrukcji if i po prostu nie rób mnożenia na ostatniej iteracji pętli, gdy może ona przepełnić. Minusem jest to, że zaśmieca kod i dodaje niepotrzebną gałąź, która musiałaby sprawdzić na wszystkich poprzednich iteracjach pętli. Mógłbym również wykonać iterację raz na raz i powtórzyć treść pętli raz po pętli, to jeszcze bardziej komplikuje kod.

Właściwy kod, o którym mowa, jest wykorzystywany w ciasnej pętli wewnętrznej, która pochłania dużą część całkowitego czasu procesora w aplikacji graficznej w czasie rzeczywistym.

Kompilatory zakładają, że poprawny program C ++ nie zawiera UB. Rozważ na przykład:

if (x == nullptr) {
    *x = 3;
} else {
    *x = 5;
}

Jeśli x == nullptrto, wyrejestrowanie go i przypisanie wartości to UB. Dlatego jedynym sposobem, w jaki może to zakończyć się prawidłowym programem, jest moment x == nullptr, w którym nigdy nie da się uzyskać wartości true, a kompilator może założyć, że zgodnie z zasadą jakby, powyższe jest równoważne:

*x = 5;

Teraz w twoim kodzie

int result = 0;
int factor = 1;
for (...) {      // Loop until factor overflows but not more
   result = ...
   factor *= 10;
}
return result;

Ostatnie zwielokrotnienie factornie może nastąpić w prawidłowym programie (podpisany przepełnienie jest niezdefiniowany). Stąd też przypisanie do resultnie może się zdarzyć. Ponieważ nie ma możliwości rozgałęzienia przed ostatnią iteracją, poprzednia iteracja nie może się zdarzyć. W końcu część kodu, która jest poprawna (tj. Nigdy nie zdarza się niezdefiniowane zachowanie) to:

// nothing :(

Zachowanie intprzepełnienia jest niezdefiniowane.

Nie ma znaczenia, czy czytasz factorpoza ciałem pętli; jeśli do tego czasu się przepełniło, to zachowanie kodu na, po i nieco paradoksalnie, zanim przepełnienie jest niezdefiniowane.

Jednym z problemów, które mogą pojawić się przy utrzymywaniu tego kodu, jest to, że kompilatory stają się coraz bardziej agresywne, jeśli chodzi o optymalizację. W szczególności rozwijają nawyk, w którym zakładają, że niezdefiniowane zachowanie nigdy się nie zdarza. W tym celu mogą forcałkowicie usunąć pętlę.

Czy nie możesz użyć unsignedtypu, factorchociaż musisz martwić się niechcianą konwersją intna unsignedw wyrażeniach zawierających oba?

Rozważanie optymalizatorów w świecie rzeczywistym może być wnikliwe. Rozwijanie pętli jest znaną techniką. Podstawową ideą rozwijania pętli op jest to

for (int i = 0; i != 3; ++i)
    foo()

może być lepiej zaimplementowany za kulisami

 foo()
 foo()
 foo()

Jest to łatwy przypadek ze stałym ograniczeniem. Ale współczesne kompilatory mogą to zrobić również dla zmiennych zmiennych:

for (int i = 0; i != N; ++i)
   foo();

staje się

__RELATIVE_JUMP(3-N)
foo();
foo();
foo();

Oczywiście działa to tylko wtedy, gdy kompilator wie, że N <= 3. I tu wracamy do pierwotnego pytania. Ponieważ kompilator wie, że podpisane przepełnienie nie występuje , wie, że pętla może wykonać maksymalnie 9 razy na architekturze 32-bitowej. 10^10 > 2^32. Może zatem rozwinąć pętlę iteracyjną 9. Ale zamierzonym maksimum było 10 iteracji! .

Może się zdarzyć, że otrzymasz skok względny do instrukcji asemblacji (9-N) o wartości N = 10, czyli przesunięcie -1, które jest samą instrukcją skoku. Ups Jest to doskonale poprawna optymalizacja pętli dla dobrze zdefiniowanego C ++, ale podany przykład zamienia się w ciasną nieskończoną pętlę.

Każde podpisane przepełnienie liczb całkowitych powoduje niezdefiniowane zachowanie, niezależnie od tego, czy przepełniona wartość jest lub może zostać odczytana.

Może w twoim przypadku użycia możesz podnieść pierwszą iterację z pętli, obracając ją

int result = 0;
int factor = 1;
for (int n = 0; n < 10; ++n) {
    result += n + factor;
    factor *= 10;
}
// factor "is" 10^10 > INT_MAX, UB

zaangażowany w to

int factor = 1;
int result = 0 + factor; // first iteration
for (int n = 1; n < 10; ++n) {
    factor *= 10;
    result += n + factor;
}
// factor is 10^9 < INT_MAX

Po włączeniu optymalizacji kompilator może rozwinąć drugą pętlę powyżej w jeden skok warunkowy.

To jest UB; w terminologii ISO C ++ całe zachowanie całego programu jest całkowicie nieokreślone dla wykonania, które ostatecznie uderza w UB. Klasycznym przykładem jest to, o ile chodzi o standard C ++, może sprawić, że demony wylecą z twojego nosa. (Odradzam stosowanie implementacji, w której demony nosowe są realną możliwością). Zobacz inne odpowiedzi, aby uzyskać więcej informacji.

Kompilatory mogą „powodować problemy” w czasie kompilacji dla ścieżek wykonywania, które widzą, co prowadzi do UB widocznego w czasie kompilacji, np. Zakładając, że te podstawowe bloki nigdy nie zostaną osiągnięte.

Zobacz także Co każdy programista C powinien wiedzieć o nieokreślonym zachowaniu (blog LLVM). Jak wyjaśniono tam, przepełnienie sygnatury UB pozwala kompilatorom udowodnić, że for(... i <= n ...)pętle nie są pętlami nieskończonymi, nawet dla nieznanych n. Pozwala im także „promować” liczniki pętli int do szerokości wskaźnika zamiast powtarzania rozszerzenia znaku. (Tak więc konsekwencją UB w takim przypadku może być dostęp poza niskimi elementami 64k lub 4G tablicy, jeśli spodziewałeś się podpisanego zawijania iw jego zakresie wartości.)

W niektórych przypadkach kompilatory będą wysyłały niedozwolone instrukcje, takie jak x86, ud2dla bloku, który prawdopodobnie spowoduje UB, jeśli kiedykolwiek zostanie wykonany. (Należy pamiętać, że funkcja może nigdy nie zostać wywołana, więc kompilatory nie mogą generalnie szaleć i łamać innych funkcji, a nawet możliwych ścieżek przez funkcję, która nie uderza w UB, tj. Kod maszynowy, do którego kompiluje, musi nadal działać dla wszystkie dane wejściowe, które nie prowadzą do UB.)

Prawdopodobnie najbardziej wydajnym rozwiązaniem jest ręczne oderwanie ostatniej iteracji, aby factor*=10uniknąć niepotrzebnych .

int result = 0;
int factor = 1;
for (... i < n-1) {   // stop 1 iteration early
    result = ...
    factor *= 10;
}
 result = ...      // another copy of the loop body, using the last factor
 //   factor *= 10;    // and optimize away this dead operation.
return result;

Lub jeśli ciało pętli jest duże, rozważ użycie po prostu typu bez znaku dla factor. Następnie możesz pozwolić, aby niepodpisane zwielokrotniło się, a po prostu wykona dobrze zdefiniowane zawijanie do pewnej potęgi 2 (liczba bitów wartości w typie bez znaku).

Jest to w porządku, nawet jeśli używasz go z podpisanymi typami, szczególnie jeśli konwersja niepodpisana-> podpisana nigdy się nie przepełnia.

Konwersja między niepodpisanym a 2-znakowym uzupełnieniem jest bezpłatna (taki sam wzór bitowy dla wszystkich wartości); zawijanie modulo dla int -> unsigned określone przez standard C ++ upraszcza po prostu użycie tego samego wzorca bitowego, w przeciwieństwie do uzupełnienia lub znaku / wielkości.

I niepodpisany-> podpisany jest podobnie trywialny, chociaż jest zdefiniowany implementacyjnie dla wartości większych niż INT_MAX. Jeśli nie używasz ogromnego niepodpisanego wyniku z ostatniej iteracji, nie masz się czym martwić. Ale jeśli tak, zobacz Czy konwersja z niepodpisanego do podpisanego jest niezdefiniowana? . Przypadek „nie pasuje” jest zdefiniowany w implementacji , co oznacza, że ​​implementacja musi wybrać pewne zachowanie; rozsądne po prostu obcinają (jeśli to konieczne) niepodpisany wzorzec bitów i używają go jako podpisanego, ponieważ działa to dla wartości w zakresie w ten sam sposób bez dodatkowej pracy. I zdecydowanie nie jest to UB. Tak duże wartości bez znaku mogą stać się liczbami całkowitymi ze znakiem ujemnym. np. po int x = u; gcc i clang nie optymalizujx>=0jak zawsze są prawdziwe, nawet bez -fwrapv, ponieważ określają zachowanie.

Jeśli możesz tolerować kilka dodatkowych instrukcji montażu w pętli, zamiast

int factor = 1;
for (int j = 0; j < n; ++j) {
    ...
    factor *= 10;
}

Możesz pisać:

int factor = 0;
for (...) {
    factor = 10 * factor + !factor;
    ...
}

aby uniknąć ostatniego pomnożenia. !factornie wprowadzi oddziału:

    xor     ebx, ebx
L1:                       
    xor     eax, eax              
    test    ebx, ebx              
    lea     edx, [rbx+rbx*4]      
    sete    al    
    add     ebp, 1                
    lea     ebx, [rax+rdx*2]      
    mov     edi, ebx              
    call    consume(int)          
    cmp     r12d, ebp             
    jne     .L1                   

Ten kod

int factor = 0;
for (...) {
    factor = factor ? 10 * factor : 1;
    ...
}

powoduje również montaż bez rozgałęzień po optymalizacji:

    mov     ebx, 1
    jmp     .L1                   
.L2:                               
    lea     ebx, [rbx+rbx*4]       
    add     ebx, ebx
.L1:
    mov     edi, ebx
    add     ebp, 1
    call    consume(int)
    cmp     r12d, ebp
    jne     .L2

(Kompilowany z GCC 8.3.0 -O3)

Nie pokazałeś, co jest w nawiasach foroświadczenia, ale założę, że jest to coś takiego:

for (int n = 0; n < 10; ++n) {
    result = ...
    factor *= 10;
}

Możesz po prostu przenieść przyrost licznika i sprawdzić zakończenie pętli do ciała:

for (int n = 0; ; ) {
    result = ...
    if (++n >= 10) break;
    factor *= 10;
}

Liczba instrukcji montażu w pętli pozostanie taka sama.

Zainspirowany prezentacją Andrei Alexandrescu „Speed ​​Is Found In The Minds of People”.

Rozważ funkcję:

unsigned mul_mod_65536(unsigned short a, unsigned short b)
{
  return (a*b) & 0xFFFFu;
}

Zgodnie z opublikowanym przesłanki, by oczekiwać autorzy standardu, że jeśli funkcja ta była wywoływana na (np) w banalnej 32-bitowego komputera z argumentami 0xC000 i 0xC000, promowanie operandy o *celu signed intspowoduje obliczenie uzyskując -0x10000000 , które po przekształceniu unsigneddałyby 0x90000000u- taką samą odpowiedź, jak gdyby się unsigned shortpromowały unsigned. Niemniej jednak gcc czasami zoptymalizuje tę funkcję w sposób, który zachowywałby się bezsensownie, gdyby nastąpiło przepełnienie. Każdy kod, w którym pewna kombinacja danych wejściowych może spowodować przepełnienie, musi być przetwarzany z -fwrapvopcją, chyba że dopuszczalne jest zezwolenie twórcom celowo zniekształconych danych wejściowych na wykonanie dowolnego wybranego przez siebie kodu.

Dlaczego nie to:

int result = 0;
int factor = 10;
for (...) {
    factor *= 10;
    result = ...
}
return result;

Istnieje wiele różnych twarzy niezdefiniowanego zachowania, a to, co jest dopuszczalne, zależy od użycia.

ciasna pętla wewnętrzna, która pochłania dużą część całkowitego czasu procesora w aplikacji graficznej w czasie rzeczywistym

To samo w sobie jest trochę niezwykłe, ale niech tak będzie ... jeśli tak rzeczywiście jest, to UB najprawdopodobniej mieści się w sferze „dopuszczalnej, dopuszczalnej” . Programowanie graficzne jest znane z hacków i brzydkich rzeczy. Tak długo, jak „działa” i nie trwa dłużej niż 16,6 ms, aby utworzyć ramkę, zwykle nikogo to nie obchodzi. Ale pamiętaj, co to znaczy wywołać UB.

Po pierwsze, jest standard. Z tego punktu widzenia nie ma o czym dyskutować i nie ma sposobu na uzasadnienie, twój kod jest po prostu nieprawidłowy. Nie ma ifs ani kiedy, to po prostu nie jest poprawny kod. Równie dobrze możesz powiedzieć, że jest to środkowy palec z twojego punktu widzenia, a 95-99% czasu i tak będziesz gotowy.

Następnie jest strona sprzętowa. Istnieją rzadkie, dziwne architektury, w których jest to problem. Mówię „niezwykłe, dziwne”, ponieważ w przypadku jednej architektury, która stanowi 80% wszystkich komputerów (lub dwóch architektur, które razem stanowią 95% wszystkich komputerów) przepełnienie to „tak, cokolwiek, nie przejmuj się” rzecz na poziomie sprzętowym. Na pewno dostajesz śmieci (choć nadal przewidywalne), ale nic złego się nie dzieje.
To nie jestw przypadku każdej architektury, możesz bardzo dobrze dostać pułapkę na przepełnienie (choć patrząc na to, jak mówisz o aplikacji graficznej, szanse na bycie na tak dziwnej architekturze są raczej niewielkie). Czy przenośność stanowi problem? Jeśli tak, możesz wstrzymać się od głosu.

Na koniec jest strona kompilatora / optymalizatora. Jednym z powodów, dla których przepełnienie jest niezdefiniowane, jest to, że po prostu pozostawienie go w tym miejscu było najłatwiejsze, aby poradzić sobie ze sprzętem. Ale innym powodem jest to, że na przykład x+1jest gwarantowane , aby zawsze być większy niż x, a kompilator / optymalizator może wykorzystać tę wiedzę. Teraz, dla wcześniej wspomnianego przypadku, kompilatory rzeczywiście działają w ten sposób i po prostu usuwają kompletne bloki (kilka lat temu istniał exploit na Linuksa, który był oparty na tym, że kompilator usunął martwy kod weryfikacyjny właśnie z tego powodu).
W twoim przypadku poważnie wątpiłbym, że kompilator wykonuje specjalne, nieparzyste optymalizacje. Co jednak wiesz, co ja wiem. W razie wątpliwości wypróbuj to. Jeśli to działa, możesz iść.

(I w końcu, oczywiście jest audyt kodu, być może będziesz musiał tracić czas na omawianie tego z audytorem, jeśli masz pecha.)