Operacja bitowa powoduje nieoczekiwany rozmiar zmiennej

24

Kontekst

Przenosimy kod C, który został pierwotnie skompilowany przy użyciu 8-bitowego kompilatora C dla mikrokontrolera PIC. Typowy idiom, który był używany, aby zapobiec cofaniu się globalnych zmiennych bez znaku (na przykład liczników błędów), jest następujący:

if(~counter) counter++;

Operator bitowy odwraca tutaj wszystkie bity, a instrukcja jest prawdziwa tylko wtedy, gdy counterjest mniejsza niż wartość maksymalna. Co ważne, działa to niezależnie od wielkości zmiennej.

Problem

Obecnie celujemy w 32-bitowy procesor ARM za pomocą GCC. Zauważyliśmy, że ten sam kod daje różne wyniki. O ile możemy stwierdzić, wygląda na to, że bitowe uzupełnienie zwraca wartość o innym rozmiarze niż się spodziewalibyśmy. Aby to odtworzyć, kompilujemy w GCC:

uint8_t i = 0;
int sz;

sz = sizeof(i);
printf("Size of variable: %d\n", sz); // Size of variable: 1

sz = sizeof(~i);
printf("Size of result: %d\n", sz); // Size of result: 4

W pierwszym wierszu danych wyjściowych otrzymujemy to, czego byśmy oczekiwali: i1 bajt. Jednak bitowe uzupełnienie ito w rzeczywistości cztery bajty, co powoduje problem, ponieważ porównania z tym teraz nie przyniosą oczekiwanych rezultatów. Na przykład, jeśli robisz (gdzie ijest poprawnie zainicjowany uint8_t):

if(~i) i++;

Zobaczymy i„zawinięcie” z 0xFF z powrotem do 0x00. To zachowanie jest inne w GCC w porównaniu do tego, kiedy działało tak, jak zamierzaliśmy w poprzednim kompilatorze i 8-bitowym mikrokontrolerze PIC.

Wiemy, że możemy rozwiązać ten problem, przesyłając w ten sposób:

if((uint8_t)~i) i++;

Lub przez

if(i < 0xFF) i++;

Jednak w obu tych obejściach wielkość zmiennej musi być znana i podatna na błędy dla twórców oprogramowania. Tego rodzaju kontrole górnych granic występują w całej bazie kodu. Istnieje wiele zmiennych rozmiarach (np. uint16_tI unsigned charitd.) I zmieniając je w kodzie inaczej roboczej nie jest coś czekamy na.

Pytanie

Czy nasze rozumienie problemu jest prawidłowe i czy są dostępne opcje rozwiązania tego problemu, które nie wymagają ponownego odwiedzania każdego przypadku, w którym użyliśmy tego idiomu? Czy nasze założenie jest prawidłowe, że operacja taka jak bitowe uzupełnienie powinna zwrócić wynik o takim samym rozmiarze jak operand? Wygląda na to, że ulegnie to awarii, w zależności od architektury procesorów. Czuję, że biorę szalone pigułki i że C powinno być trochę bardziej przenośne niż to. Ponownie nasze rozumienie tego może być błędne.

Z pozoru może to nie wydawać się wielkim problemem, ale ten wcześniej działający idiom jest używany w setkach lokalizacji i chętnie to rozumiemy, zanim przejdziemy do drogich zmian.


Uwaga: Wydaje się, że na pozór podobne, ale nie do końca zduplikowane pytanie: Bitowa operacja na char daje 32-bitowy wynik

Nie widziałem prawdziwego sedna omawianego problemu, a mianowicie, że rozmiar wyniku bitowego uzupełnienia różni się od tego, co przekazano operatorowi.

Charlie Salts
źródło
14
„Czy nasze założenie jest prawidłowe, że operacja taka jak bitowe uzupełnienie powinna zwrócić wynik o takim samym rozmiarze jak operand?” Nie, to nie jest poprawne, obowiązują promocje na liczby całkowite.
Thomas Jager
2
Chociaż z pewnością jest to istotne, nie jestem przekonany, że są duplikatami tego konkretnego pytania, ponieważ nie zapewniają rozwiązania problemu.
Cody Gray
3
Czuję, że biorę szalone pigułki i że C powinno być trochę bardziej przenośne niż to. Jeśli nie otrzymałeś promocji liczb całkowitych na typach 8-bitowych, oznacza to, że Twój kompilator nie jest zgodny ze standardem C. W takim przypadku uważam, że powinieneś przejść wszystkie obliczenia, aby je sprawdzić i naprawić w razie potrzeby.
user694733
1
Czy tylko ja zastanawiam się, jaką logikę, oprócz naprawdę nieistotnych liczników, można doprowadzić do „zwiększenia, jeśli jest wystarczająco dużo miejsca, w przeciwnym razie zapomnij”? Jeśli przenosisz kod, czy możesz użyć int (4 bajty) zamiast uint_8? W wielu przypadkach zapobiegłoby to problemowi.
krążek
1
@puck Masz rację, moglibyśmy zmienić go na 4 bajty, ale to zepsułoby kompatybilność podczas komunikacji z istniejącymi systemami. Chodzi o to, aby wiedzieć, kiedy wystąpiły jakieś błędy, więc 1-bajtowy licznik był początkowo wystarczający i tak pozostanie.
Charlie Salts

Odpowiedzi:

26

To, co widzisz, jest wynikiem promocji liczb całkowitych . W większości przypadków, gdy w wyrażeniu używana jest wartość całkowita, jeśli typ wartości jest mniejszy niż intpromowana jest wartość int. Jest to udokumentowane w sekcji 6.3.1.1p2 normy C :

Poniższe mogą być użyte w wyrażeniu, gdziekolwiek intlub unsigned intmogą być użyte

  • Obiekt lub wyrażenie z typem całkowitym (innym niż intlub unsigned int), którego stopień konwersji liczb całkowitych jest mniejszy lub równy szeregowi inti unsigned int.
  • Pole bitowe typu _Bool, int ,podpisane int , orunsigned int`.

Jeśli an intmoże reprezentować wszystkie wartości oryginalnego typu (ograniczone przez szerokość dla pola bitowego), wartość jest konwertowana na int; w przeciwnym razie jest konwertowany na unsigned int. Są to tak zwane promocje liczb całkowitych . Wszystkie pozostałe typy są niezmienione przez promocje liczb całkowitych.

Więc jeśli zmienna ma typ uint8_ti wartość 255, użycie dowolnego operatora innego niż rzutowanie lub przypisanie spowoduje najpierw konwersję na typ into wartości 255 przed wykonaniem operacji. Dlatego sizeof(~i)daje 4 zamiast 1.

Sekcja 6.5.3.3 opisuje, że promocje na liczby całkowite dotyczą ~operatora:

Wynik ~operatora jest bitowym uzupełnieniem jego (promowanego) operandu (to znaczy każdy bit wyniku jest ustawiany tylko wtedy, gdy odpowiedni bit w skonwertowanym operandzie nie jest ustawiony). Promocje na liczbach całkowitych są wykonywane na operandzie, a wynik ma promowany typ. Jeśli promowany typ jest typem bez znaku, wyrażenie ~Ejest równoważne maksymalnej wartości reprezentowanej w tym typie minus E.

Więc zakładając 32 bit int, jeśli counterma wartość 8 bitów 0xff, jest konwertowany na wartość 32 bitów 0x000000ff, a zastosowanie ~do niego daje ci 0xffffff00.

Prawdopodobnie najprostszym sposobem na poradzenie sobie z tym bez konieczności znajomości typu jest sprawdzenie, czy po zwiększeniu wartość wynosi 0, a jeśli tak, to zmniejsz.

if (!++counter) counter--;

Zawijanie liczb całkowitych bez znaku działa w obu kierunkach, więc zmniejszenie wartości 0 daje największą wartość dodatnią.

dbush
źródło
1
if (!++counter) --counter;może być mniej dziwny dla niektórych programistów niż używanie przecinka.
Eric Postpischil
1
Inną alternatywą jest ++counter; counter -= !counter;.
Eric Postpischil
@EricPostpischil Właściwie to bardziej podoba mi się twoja pierwsza opcja. Edytowane.
dbush
15
Jest to brzydkie i nieczytelne bez względu na to, jak je napiszesz. Jeśli musisz użyć takiego idiomu, zrób przysługę każdemu programistowi konserwacji i zawiń go jako funkcję wbudowaną : coś w rodzaju increment_unsigned_without_wraparoundlub increment_with_saturation. Osobiście użyłbym ogólnej clampfunkcji trójoperandowej .
Cody Gray
5
Nie można również ustawić tej funkcji, ponieważ musi ona zachowywać się inaczej w przypadku różnych typów argumentów. Musisz użyć makra ogólnego .
user2357112 obsługuje Monikę
7

w rozmiarze (i); żądasz wielkości zmiennej i , więc 1

w sizeof (~ i); poprosić o wielkości od rodzaju ekspresji, która jest int , w przypadku 4


Używać

jeśli (~ i)

wiedzieć, czy ja nie cenią 255 (w przypadku z AN uint8_t) nie jest bardzo czytelny, zrób

if (i != 255)

i będziesz mieć przenośny i czytelny kod


Istnieje wiele rozmiarów zmiennych (np. Uint16_t i unsigned char itp.)

Aby zarządzać dowolnym znakiem niepodpisanym:

if (i != (((uintmax_t) 2 << (sizeof(i)*CHAR_BIT-1)) - 1))

Wyrażenie jest stałe, więc obliczane w czasie kompilacji.

#include <limits.h> dla CHAR_BIT i #include <stdint.h> dla uintmax_t

bruno
źródło
3
Pytanie wyraźnie stwierdza, że ​​mają do czynienia z wieloma rozmiarami, więc != 255jest niewystarczające.
Eric Postpischil
@EricPostpischil ah tak, zapominam o tym, więc „if (i! = ((1u << sizeof (i) * 8) - 1))” przypuśćmy, że zawsze niepodpisany?
bruno
1
Nie będzie to zdefiniowane dla unsignedobiektów, ponieważ przesunięcia pełnej szerokości obiektu nie są zdefiniowane przez standard C, ale można to naprawić za pomocą (2u << sizeof(i)*CHAR_BIT-1) - 1.
Eric Postpischil
och tak ofc, CHAR_BIT, mój zły
bruno
2
Dla bezpieczeństwa szerszych typów można użyć ((uintmax_t) 2 << sizeof(i)*CHAR_BIT-1) - 1.
Eric Postpischil
5

Oto kilka opcji implementacji „Dodaj 1, xale ogranicz do maksymalnej reprezentatywnej wartości”, biorąc pod uwagę, że xjest to pewien typ liczb całkowitych bez znaku:

  1. Dodaj jedną, jeśli i tylko jeśli xjest mniejsza niż maksymalna wartość reprezentowana w jej typie:

    x += x < Maximum(x);

    Definicja: patrz następująca pozycja Maximum. Ta metoda ma dużą szansę na zoptymalizowanie przez kompilator pod kątem wydajnych instrukcji, takich jak porównanie, jakaś forma warunkowego zestawu lub przeniesienia oraz dodanie.

  2. Porównaj z największą wartością tego typu:

    if (x < ((uintmax_t) 2u << sizeof x * CHAR_BIT - 1) - 1) ++x

    (Oblicza to 2 N , gdzie N jest liczbą bitów w środku x, poprzez przesunięcie 2 o N −1 bitów. Robimy to zamiast przesunięcia 1 N bitów, ponieważ przesunięcie o liczbę bitów w typie nie jest zdefiniowane przez C standard. CHAR_BITMakro może być dla niektórych nieznane; jest to liczba bitów w bajcie, podobnie sizeof x * CHAR_BITjak liczba bitów w rodzaju x.)

    Można to owinąć w makro zgodnie z potrzebami pod względem estetyki i przejrzystości:

    #define Maximum(x) (((uintmax_t) 2u << sizeof (x) * CHAR_BIT - 1) - 1)
    if (x < Maximum(x)) ++x;
  3. Zwiększ xi popraw, jeśli zawija się do zera, używając if:

    if (!++x) --x; // !++x is true if ++x wraps to zero.
  4. Zwiększ xi popraw, jeśli zawija się do zera, używając wyrażenia:

    ++x; x -= !x;

    Jest to nominalnie bezgałęziowe (czasem korzystne dla wydajności), ale kompilator może zaimplementować go tak samo jak powyżej, używając w razie potrzeby rozgałęzienia, ale być może z bezwarunkowymi instrukcjami, jeśli architektura docelowa ma odpowiednie instrukcje.

  5. Opcja bez rozgałęzienia, wykorzystująca powyższe makro, to:

    x += 1 - x/Maximum(x);

    Jeśli xjest to maksimum tego typu, wartość ta jest obliczana na x += 1-1. W przeciwnym razie tak jest x += 1-0. Jednak podział na wiele architektur jest nieco powolny. Kompilator może zoptymalizować to do instrukcji bez podziału, w zależności od kompilatora i architektury docelowej.

Eric Postpischil
źródło
1
Po prostu nie mogę zmusić się do głosowania za odpowiedzią, która zaleca użycie makra. C ma funkcje wbudowane. W tej definicji makr nie robisz nic, czego nie można łatwo zrobić w funkcji wbudowanej. A jeśli zamierzasz użyć makra, upewnij się, że strategicznie nawiasujesz dla zachowania przejrzystości: operator << ma bardzo niski priorytet. Clang ostrzega przed tym za pomocą -Wshift-op-parentheses. Dobrą wiadomością jest to, że optymalizujący kompilator nie wygeneruje tutaj podziału, więc nie musisz się martwić, że będzie powolny.
Cody Gray
1
@CodyGray, jeśli uważasz, że możesz to zrobić za pomocą funkcji, napisz odpowiedź.
Carsten S
2
@CodyGray: sizeof xnie można zaimplementować w funkcji C, ponieważ xmusiałby to być parametr (lub inne wyrażenie) z jakimś stałym typem. Nie można wygenerować rozmiaru dowolnego typu argumentu używanego przez program wywołujący. Makro może.
Eric Postpischil
2

Przed wersją stdint.h zmienne rozmiary mogą się różnić w zależności od kompilatora, a rzeczywiste typy zmiennych w C są nadal int, długie itp. I są nadal definiowane przez autora kompilatora co do ich wielkości. Brak niektórych założeń standardowych lub docelowych. Autor (autorzy) muszą następnie utworzyć plik stdint.h, aby zmapować dwa światy, to jest cel pliku stdint.h, aby zmapować uint_this na int, długi, krótki.

Jeśli przenosisz kod z innego kompilatora i używa on znaków char, short, int, long, musisz przejść przez każdy typ i zrobić port sam, nie ma możliwości obejścia tego. I albo otrzymujesz odpowiedni rozmiar zmiennej, deklaracja się zmienia, ale kod jak napisany działa ...

if(~counter) counter++;

lub ... podaj maskę lub rzut bezpośrednio

if((~counter)&0xFF) counter++;
if((uint_8)(~counter)) counter++;

Na koniec dnia, jeśli chcesz, aby ten kod działał, musisz przenieść go na nową platformę. Twój wybór jak. Tak, musisz poświęcić czas na trafienie w każdą sprawę i zrobić to dobrze, w przeciwnym razie będziesz wracał do tego kodu, który jest jeszcze droższy.

Jeśli wyodrębnisz typy zmiennych w kodzie przed przeniesieniem i jaki jest rozmiar typów zmiennych, to wyodrębnij zmienne, które to robią (powinny być łatwe do grepowania) i zmień ich deklaracje za pomocą definicji stdint.h, które, mam nadzieję, nie zmienią się w przyszłości, i byłbyś zaskoczony, ale czasami używane są niewłaściwe nagłówki, więc nawet czeków, abyś mógł lepiej spać w nocy

if(sizeof(uint_8)!=1) return(FAIL);

I chociaż ten styl kodowania działa (if (~ counter) counter ++;), dla przenośności teraz i w przyszłości najlepiej jest użyć maski, aby konkretnie ograniczyć rozmiar (i nie polegać na deklaracji), rób to, gdy kod jest zapisywany w pierwszej kolejności lub po prostu dokończ port, a później nie będziesz musiał go ponownie portować. Lub, aby kod był bardziej czytelny, zrób to, jeśli x <0xFF wtedy lub x! = 0xFF lub coś takiego, to kompilator może zoptymalizować go do tego samego kodu, który byłby dla każdego z tych rozwiązań, po prostu czyni go bardziej czytelnym i mniej ryzykownym ...

Zależy od tego, jak ważny jest produkt lub od tego, ile razy chcesz wysyłać łatki / aktualizacje, toczyć ciężarówkę lub iść do laboratorium, aby ustalić, czy próbujesz szybko znaleźć rozwiązanie, czy po prostu dotknąć dotkniętych linii kodu. jeśli jest tylko sto lub kilka, to nie jest tak duży port.

old_timer
źródło
0
6.5.3.3 Jednoargumentowe operatory arytmetyczne
...
4 Wynik ~operatora jest bitowym uzupełnieniem jego (promowanego) operandu (to znaczy każdy bit w wyniku jest ustawiany wtedy i tylko wtedy, gdy odpowiedni bit w skonwertowanym operandzie nie jest ustawiony ). Promocje na liczbach całkowitych są wykonywane na operandzie, a wynik ma promowany typ . Jeśli promowany typ jest typem bez znaku, wyrażenie ~Ejest równoważne maksymalnej wartości reprezentowanej w tym typie minus E.

C 2011 Online Draft

Problem polega na tym, że operand ~jest promowany intprzed zastosowaniem operatora.

Niestety nie sądzę, aby można było z tego łatwo wyjść. Pisanie

if ( counter + 1 ) counter++;

nie pomoże, ponieważ obowiązują tam również promocje. Jedyne, co mogę zasugerować, to utworzenie stałych symbolicznych dla maksymalnej wartości, którą ten obiekt ma reprezentować, i przetestowanie na tym:

#define MAX_COUNTER 255
...
if ( counter < MAX_COUNTER-1 ) counter++;
John Bode
źródło
Doceniam sens promocji liczb całkowitych - wygląda na to, że na to wpadamy. Warto jednak zauważyć, że w drugim przykładzie kodu -1nie jest on potrzebny, ponieważ spowodowałoby to, że licznik osiągnąłby wartość 254 (0xFE). W każdym razie takie podejście, jak wspomniano w moim pytaniu, nie jest idealne ze względu na różne wielkości zmiennych w bazie kodu, które uczestniczą w tym idiomie.
Charlie Salts