W zasadzie zanim przejdę dalej, gritzy za j00ru, który razem ze mną kombinował jak to inaczej zapisać ;>
Problem był prosty: zapisać za pomocą działań matematycznych poniższą, składającą się z dwóch inline if'ów, linijkę kodu (osoby związane z grafiką komputerową od strony programowania, pewnie nie raz widziały taką czy podobną linię kodu):
r = r > 255 ? 255 : r < 0 ? 0 : r; // int r, CPU = x86, sizeof(int) = 4
Kod ten działa w taki oto sposób:
Jeżeli r jest większe od 255, r = 255
Jeżeli r jest mniejsze od 0, r = 0
Jeżeli r jest z przedziału domkniętego [0,255], r ma pozostać bez zmian
Zanim przejdę dalej, ważna uwaga - we wszystkich poniższych operacjach 'r' traktuje jak unsigned int - czyli w razie czego należy dokonać cast z int na unsigned int (nie chce aby kompilator korzystał z instrukcji dopełniających najbardziej znaczący bit przy niektórych operacjach).
Zacznijmy od części 'jeżeli r jest mniejsze od 0, r = 0' - czyli, dla każdej liczby ujemnej, r ma być równe 0. Jako że liczba 0 jest dość charakterystyczna (wszystkie bity ustawione na 0), możemy spróbować zrobić mnożenie lub AND bitowe na r liczby 0 jeżeli r jest ujemne, lub 0xff (255 = 0xff, 0xff = 1111 1111, 8 bitów bo do zapisania 255 i tak więcej nam nie potrzeba) jeśli r jest dodatnie, czyli np.:
r = r & (r < 0 ? 0 : 0xff)
Oczywiście ten inline if tam nas nie zadowala, więc postarajmy się go zastąpić czymś innym.
Jak wiadomo, każda liczba ujemna zapisana w systemie U2 (z którego korzysta x86 w przypadku intów) będzie miała najbardziej znaczący bit (tj. 31 bit, licząc od 0) zapalony. Korzystając z tego, możemy napisać:
(r >> 31)
Po tej operacji, r będzie równe 0 jeżeli liczba była dodatnia, a 1 jeżeli była ujemna. Jednak my chcemy uzyskać 0 dla ujemnych, a 0xff dla dodatnich. Możemy to zrobić po prostu odejmując 1.
(r >> 31) - 1)
Teraz, dla liczb dodatnich, będzie to (0 - 1) czyli -1, a więc w systemie U2 0xffffffff, a dla liczb ujemnych, będzie to (1 - 1), czyli 0. Oczywiście teraz wystarczy zrobić AND bitowe z 0xff, i dostajemy 0xff dla dodatnich, i 0 dla ujemnych, czyli dokładnie to co zwraca (r < 0 ? 0 : 0xff). Możemy więc napisać:
r = r & (((r >> 31) - 1) & 0xff)
OK, dolna część liczb załatwiona, teraz czas na pozostałe dwa warunki, czyli 'dla liczb > 255, zwróć 255, a dla liczb mniejszych od 255, zwróć daną liczbę'. Całość możemy sprowadzić do instrukcji OR bitowego z liczbą 0xff jeżeli liczba jest większa od 255, lub 0 jeżeli liczba jest mniejsza, i do AND bitowego z 0xff.
r = (r | (r > 255 ? 0xff : 0)) & 0xff
Jeżeli r będzie większe niż 255, to zostanie wykonany OR bitowy z 255, czyli bity od 0 do 7 zostaną zapalone, a następnie AND bitowy przytnie wszystkie pozostałe bity, tak aby zostało tylko to 1111 1111, czyli 255. Ale znowu mamy inline if'a.
Jak się go pozbyć ? Możemy tutaj skorzystać z faktu że jeżeli liczba jest większa niż 255, to na pewno będzie zapalony któryś bit powyżej 7dmego (jak pisałem wcześniej, 255 to 1111 1111, czyli bity od 0 do 7 zapalone, tak więc każda większa liczba będzie musiała zapalić któryś dalszy bit, np. 8smy czy 30sty). Skorzystajmy więc z negacji liczby (!) aby osiągnąć wartości 0 lub jeden, jeżeli któreś górne bity r są zapalone:
!(r >> 8)
Teraz, dla r > 255, dostaniemy !(liczba większa lub równa 1), czyli 0, a dla r <= 255, dostaniemy !(0), czyli 1. Ponownie skorzystamy z odejmowania aby dostać wszystkie bity zapalone lub zgaszone, i ponownie użyjemy AND bitowego do obcięcia bitów zapalonych do dolnych ośmiu.
(((!(r >> 8)) - 1) & 0xff)
Po tej operacji dla dodatnich r > 255 dostajemy liczbę 0xff, a dla dodatnich r <= 255, dostajemy 0. Czyli możemy podmienić powyższego if'a.
r = (r | (((!(r >> 8)) - 1) & 0xff)) & 0xff
Oczywiście powyższy zapis nie działa za dobrze dla liczb ujemnych, które przecież wszystkie mają zapalony bit numer 31, więc zostaną potraktowane jak liczby większe od 255. Ale spokojnie możemy to zignorować - druga część równania (czyli to co wyprowadziliśmy wcześniej) się tym zajmie.
OK, a teraz łączymy obie części równania - jest to dość proste - za pierwsze 'r' w pierwszym równaniu wystarczy podstawić drugie równanie, dzięki czemu otrzymamy:
r = (r | (((!(r >> 8)) - 1) & 0xff)) & 0xff & (((r >> 31) - 1) & 0xff)
Oczywiście tak na prawdę wystarczy jedno & 0xff, więc reszty możemy się pozbyć - zostawmy tylko ostatnie.
r = (r | ((!(r >> 8)) - 1)) & (((r >> 31) - 1) & 0xff)
Możemy jeszcze napisać jakiś programik testowy, i zobaczyć że to na prawdę działa:
#include <stdio.h>
int func(unsigned int r)
{
r = (r | ((!(r >> 8)) - 1)) & (((r >> 31) - 1) & 0xff);
return r;
}
int
main(void)
{
int i;
for(i = -1024; i <= 1024; i++)
printf("%i = %i\n", i, func((unsigned int)i));
return 0;
}
Kompilacja i output:
$ g++ t1.cpp
$ ./a.out
-1024 = 0
-1023 = 0
-1022 = 0
-1021 = 0
[...]
-3 = 0
-2 = 0
-1 = 0
0 = 0
1 = 1
2 = 2
3 = 3
4 = 4
[...]
252 = 252
253 = 253
254 = 254
255 = 255
256 = 255
257 = 255
258 = 255
[...]
1020 = 255
1021 = 255
1022 = 255
1023 = 255
1024 = 255
Powyższy post stanowi dowód na to że można część ifów zapisać jako operacje matematyczne, ale prawie że na pewno nie należy tego robić ze względu na znaczną utratę czytelności kodu ;>
Natomiast niewątpliwie jest to pouczające doświadczenie ;>
By the way...
There are more blog posts you might like on my company's blog: https://hexarcana.ch/b/
Pytanie na koniec - czy będzie to rzeczywiście szybsze od dwóch if'ów? Hmm... może na starszych komputerach, ale teraz, nie sądzę ;> (niemniej jednak zachęcam do testów)
I tyle...
P.S. dodam że niektóre (tak, GCC) kompilatory operacje ! zapisują jako:
test eax, eax
jne L2
mov DWORD PTR [ebp-4], 0
jmp L4
L2:
mov DWORD PTR [ebp-4], -1
L4:
Tak więc ćwiczenie dla zainteresowanych - jak się pozbyć ! z działań ?;>
Comments:
xor ecx,ecx
inc ecx ; ecx = 1
test eax,eax
cmovnz eax,edx
cmovz eax,ecx
; eax = input
mov edx, 255
sub edx, eax
sbb ecx, ecx
and ecx, edx
add eax, ecx
i wiele innych ciekawych przykladow...
a i wykonanie ciekawe ;)
Pozdrawiam,
Ciekawy wpis, skad Gynvael bierzesz takie "szalone" pomysly? ;p
Mala ciekawostka, malo kto zdaje sobie sprawe ze popularny operator trojargumentowy w C++ moze byc uzyty jako lvalue:
(a ? b : c) = 3;
Ja wiem, co można z tym branchem przy negacji zrobić. Włączyć optymalizacje ;). Żaden szanujący się kompilator nie zrobi czegoś takiego z włączonymi optymalizacjami.
Swoją drogą - to może być szybsze niż wersja z ifami - mispredicted branch potrafi zaboleć...
co nie zmienia faktu, że analiza matematyczna to spora przesada i paskudne wspomnienie.
@Malcom
raz kiedyś użyłem takiej konstrukcji :)
Add a comment: