Dzisiaj będzie o pewnym ciekawym błędzie znalezionym w kodzie znajomego, oraz o pewnym linku znalezionym w refererach. Link prowadził do...

Art of file 3D (by irid)
Muszę przyznać że reakcja sceny na mój post o graficznej interpretacji plików mnie zaskoczyła. Najpierw zostałem poproszony przez qubodup'a o wypuszczenie źródeł na licencji open source, co skończyło się popełnieniem portu mojej aplikacyjki przez KlAaze na *nixy, a teraz irid stworzył w Pythonie wersję 3D:
- topic na reddit (link do źródełek tam leży)
- filmik na yt



Cool :)
W sumie nawet kiedyś (długo przed wersją 2D) eksperymentowałem z 3D, ale niestety, mój wybór plików (wybrałem wyjątkowo nudne pliki) spowodował że zrezygnowałem z zabawy. Cieszę się że irid nie popełnił tego samego błędu, bo niektóre pliki wyglądają na prawdę super w 3D.

Ciekawy błąd dot. rand()
Wpadł mi w ręce ostatnio pewien ciekawy kod stworzony przez znajomego, którego fragment (kodu, nie znajomego) pozwolę sobie zacytować (trochę niedokładnie, ale sens pozostanie bez zmian):

 int my_rand_limit = 60000;
 srand(time(0));
 #ifdef RAND_MAX
 #  undef RAND_MAX
 #endif
 #define RAND_MAX my_rand_limit

 int rand_value = rand();


Zaciekawiony poprosiłem znajomego o wyjaśnienie mi tego fragmentu, uzyskując w odpowiedzi cytat z dokumentacji:

Funkcja rand() zwraca pseudolosową liczbę całkowitą z zakresu pomiędzy 0 a RAND_MAX.

Czyli sens powyższego kodu jest następujący: "chcę żeby rand() zwrócił mi wartość od 0 do 60000, więc zmienię RAND_MAX na 60000". Muszę przyznać że logika rozumowania mojego znajomego jest bez zarzutu.
Niestety, powyższy kod mimo pozornie prawidłowego ciągu myślowego, i tak nie zadziała jak należy - powód jest prosty: RAND_MAX jest niejako "tylko-do-odczytu", a dokładniej rzecz biorąc, jest to stałą zadeklarowana przez programistę tworzącego bibliotekę, której wartość jest równa maksymalnej możliwej wartości jaki funkcja rand() może zwrócić, z uwagi na swoją implementację. Czyli, jest to jedynie informacja - rand() z tego nie korzysta, więc zmiana RAND_MAX nie zmieni działania funkcji rand().

Oczywiście, poprawnym użyciem funkcji rand() w tym wypadku było by rand_value = rand() % (my_rand_limit + 1).

Natomiast co ciekawe, można uzyskać przypadek w którym powyższy kod by rzeczywiście zadziałał! Stanie się tak gdy przed powyższym kodem dodamy taką oto dyrektywę preprocesora:

#define rand() (rand() % RAND_MAX)

Prawdę mówiąc gdy znajomy powiedział mi że jego kod został przetestowany i zwracał wartości ze spodziewanej granicy, to zacząłem przeszukiwać standardowe headery kompilatory właśnie w poszukiwaniu takiego oto makra - którego jednak nie znalazłem. Jak się okazało później wniosek znajomego opierał się na prostym fakcie: dobrany my_rand_limit był nieznacznie większy niż RAND_MAX, przez co faktycznie mogło by się wydawać (bez bardziej wnikliwych testów) iż rand() faktycznie zwraca liczby z przedziału [0, my_rand_limit], mimo iż faktycznie zwracał z przedziału [0, RAND_MAX] który po prostu się zawierał w przedziale [0, my_rand_limit].

I to tyle na teraz...

Comments:

2009-07-11 13:42:27 = Jurgi
{
Y, fajny ten pokaz w 3D. Nadał by się do takiego typowego filmu o hackerach - można by fajnie pokazać analizowanie plików, zamiast lecących cyferek. :) A mogłeś to opatentować i kroić kasę od Hollywoodów.
}
2009-07-11 20:33:04 = bAzyl
{
Wyrażenie rand() % (my_rand_limit + 1) nie jest dobrym pomysłem, ponieważ korzysta z niższych bitów zwracanych przez rand(), które są z reguły mniej losowe niż wyższe. Lepszym sposobem jest wygenerowanie losowej wartości z przedziału [0, 1) i pomnożone przez stałą my_rand_limit np. : r = ( (double)rand() / ((double)(RAND_MAX)+(double)(1)) ), a potem odpowiednio rand_value= (r * my_rand_limit). Dokładnie jest to opisane na stronie http://members.cox.net/srice1/random/crandom.html .
}
2009-07-12 01:55:18 = krlm
{
Kolega bAzyl mial sluszne intencje, ale chyba nie do konca wie dlaczego. Problem lezy w zakloceniu rozladku funkcji losowej po przez modulo. Zdecydowaniem lepszym pomyslem jest przeskalowanie zakresu losowania na interesujacy nas zakres. Pozdrawaiam.
}
2009-07-12 15:45:27 = Malcom
{
Niezly kolega ;p
W istocie zadzialoby to, gdyby rand() byl rozwijany w czasie kompilacji.
}
2009-07-13 09:07:47 = mik01aj
{
Ad analizy plików - czy lcamtuf nie robił podobnych obrazków dla generatorów liczb losowych? (vide "Cisza w sieci") Też były w 3d, i chyba nawet były na tej samej zasadzie tworzone, jeśli dobrze pamiętam.
}
2009-07-14 07:14:09 = Gynvael Coldwind
{
@Jurgi
Hehehe dobry pomysł ;D

@bAzyl, @krlm
Pomysł z [0,1) * limit aka "przeskalowanie" jest dobry, i faktycznie problem wywoływany przez modulo znika (pytanie brzmi czy nie pojawia się jakiś inny problemik ;> jakieś pomysły?).
Natomiast nie oszukujmy się, jeśli chcemy liczbę z na prawdę dobrą entropią, to rand() i tak nie znajdzie tutaj zastosowania. A jeżeli nam to zbytniej różnicy nie robi, byle by było chociaż trochę losowe, to rand() % limit wystarcza w zupełności. Wszystko jest kwestią tego ile chcemy na to 'energii' (linii kodu / mocy obliczeniowej) stracić.

@Malcom
Ano ;>

@mik01aj
Jeśli chodzi o 3D zaprezentowane wyżej, to różni się ono (nieznacznie) od tego co lcamtuf w "Ciszy..." pisał - on tam robił X,Y,Z, a tutaj jest X,Y,Offset.
Natomiast bez bicia przyznaje pomysł zinterpretowania plików w 2D metodą X,Y przyszedł mi do głowy po lekturze "Ciszy..." (chociaż tam dotyczył on RNG, a nie samych danych) ;>
}
2009-07-16 20:20:06 = mulander
{
Chętnie bym zobaczył taki sposób reprezentacji wykorzystany do generowania thumbnailów w menadżerach plików :)
}
2009-07-18 16:52:45 = Gynvael Coldwind
{
@bAzyl, @krlm
Po angielskiej stronie lustra pojawił się comment proponujący inne rozwiązanie: odrzucić wszystkie liczby większe od maksymalnej oczekiwanej wartości i losować ponownie w tym wypadku (pętla niestety wymagana).
Po przemyśleniu sprawy faktycznie muszę przyznać że ten pomysł jest dużo lepszy, ponieważ nawet po przeskalowaniu wyniku i tak pewne liczby będą pojawiać się częściej niż inne.
Oczywiście nie jest to w pewnych przypadkach konieczne, a konkretniej wtedy gdy RAND_MAX dzieli się bez reszty przez nasz oczekiwany limit.

@mulander
Ja też ;>>>

}
2009-08-20 20:00:13 = XANi
{
@bAzyl, @krim
z man rand:
" Wersje rand() i srand() w bibliotece C Linuksa korzystają z tego samego
generatora liczb losowych, co random() i srandom(), więc mniej znaczące
bity powinny być tak samo losowe jak bity bardziej znaczące. Jednakże,
w starszych implementacjach rand() bity mniej znaczące są znacznie
mniej losowe niż bity bardziej znaczące.
"
}

Add a comment:

Nick:
URL (optional):
Math captcha: 6 ∗ 5 + 6 =