Projekt “Wszystkie Obrazy Świata”

2 Comments

Zaznaczę na początku, że tytuł tego posta jest mocno przesadzony. Jakiś czas temu znalazłem na Wykopie (jeśli ktoś skojarzy, proszę o podanie źródła w komentarzu) ciekawy pomysł, swego rodzaju ideę programistyczną. Może nie tylko programistyczną. Autor pomysłu zastanawiał się, co by było, gdyby wygenerować wszystkie możliwe pliki graficzne. Jakby to było zobaczyć gdzieś pośród nich swoje zdjęcie?
Pomyślałem, że to całkiem ciekawe i postanowiłem spróbować. W tym wpisie opiszę założenia tej idei, praktyczny sposób jej wykonania oraz dlaczego jest ona niemożliwa do zrealizowania :)

Zacznijmy od wyjaśnienia, co znaczy wszystkie możliwe pliki graficzne. Rozumieć to należy jako swego rodzaju generowanie brute-force, tylko odnoszące się do grafiki.

W tym miejscu miałem zrobić ogromną dygresję na temat brute-force i jej wykorzystania przy generowaniu słownika do łamania haseł haszowanych, ale… się rozmyśliłem. Powiedzmy sobie po prostu, że chodzi o wygenerowanie wszystkich możliwych słów.
Załóżmy, że nie znamy hasła, ale wiemy że ma ono długość trzech znaków i składa się z małych liter. Wiemy więc, że będzie ono znajdowało się gdzieś w zbiorze, który można streścić jako:

aaa
aab
aac
(...)
aaz
aba
abb
(...)
zzx
zzy
zzz

Zrozumiałe, prawda?

Zawęzimy teraz opcje, dla uproszczenia analogii “graficznej” to trzyliterowego hasła zkładającego się tylko z liter “a” i “b”. Wtedy do wyboru mamy:

aaa
aab
aba
abb
baa
bab
bba
bbb

…czyli generalnie rzecz ujmując, ilość możliwych haseł do sprawdzenia można określić za pomocą wzoru:
eq1

Pędźmy dalej. Przecież każdy obraz w postaci cyfrowej można opisać tak samo. Ilością liter do wyboru będzie tutaj ilość kolorów, zaś ilością możliwych kombinacji – ilość pikseli. Dla uproszczenia: jeśli weźmiemy na warsztat czarno-białe obrazy (ilość kolorów: 2) o rozmiarze 3×1 pikseli (wielkość: 3px) i np. opiszemy piksel biały jako “a”, zaś piksel czarny jako “b” – mamy powyżej wygenerowane wszystkie możliwe kombinacje obrazów o podanych właściwościach.

Tłumaczenie dla geeków: mapa bitowa.
Tłumaczenie dla wannabe-geeków: system binarny.

Enough said…

Stąd wniosek, że ogólna ilość kombinacji obrazów opisana jest jako:
eq2

Więc czemu nie spróbować… Weźmy na warsztat Właśnie czarno-białe (dla uproszczenia kodu) obrazy. Dla większego jeszcze uproszczenia – niech będą one kwadratowe. To uprości nam wzór na ilość do:
eq3

No dobrze, ale jak to zrealizować w praktyce? Używając PHP?
Zacznijmy od podstaw :) Skoro odpowiednikiem zawartości obrazka jest kod binarny (dla obrazków 2-kolorowych, bo ogólnie jest to kod w systemie o podstawie równej ilości kolorów, ale tego nie musicie wiedzieć), to generowanie kolejnych obrazków może się odbywać przez dodawanie 1 do mapy poprzedniego obrazka, zaczynając od np. 0000 (cztery bity, bo obrazki miały być kwadratowe). Dalej będzie 0001, 0010, 0011 etc.

Czyli potrzebujemy dwóch skryptów, poniżej posłużę się nazwami z mojego, gotowego przykładu:

image.php – skrypt generujący plik graficzny na podstawie mapy
index.php – skrypt generujący kolejne mapy i wywołujący image.php

Zacznijmy od pliku image.php:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<!--?php 
  $mapa = $_REQUEST['p'];
  $size = sqrt(strlen($mapa)); // dlugosc boku
 
  header("Content-type: image/png");
  $im = @imagecreate($size, $size)
    or die("Nie można zainicjalizować nowego strumienia GD");
  $background = imagecolorallocate($im, 0xFF, 0xFF, 0xFF); // biale tlo
 
  // zagniezdzony for(), przejazd kolejnych wierszy i kolumn    
  for($a = 0; $a < $size; $a++)
  {
    for($b = 0; $b < $size; $b++)
    {
      $kolor = 255 * ($mapa[($a*$size)+$b]);  // 255*1 albo 255*0
      $piksel = imagecolorallocate($im, $kolor, $kolor, $kolor);    
      imagesetpixel($im, $b, $a, $piksel);
    }
  }
 
  imagepng($im);
  imagedestroy($im);
?-->

Powyżej tworzymy plik w formacie PNG. Głębia jest domyślna, tj. 256 kolorów (patrz:
przypisanie do $kolor), z lenistwa nie kombinujemy z tworzeniem obrazu o mniejszej głębi, a z troski o serwer używamy dwóch kolorów :)

Następnie plik generujący mapy, czyli nasz index.php:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
&lt;?
  $bok = 2;  // przyklad, tworzymy obrazy 2x2
 
  // funkcja "dodajaca" 1, operujaca na stringu - dla wygody. Oczywiscie
  // mozna uzyc liczby i wyswietlania w formacie binarnym
  function oneMore($theString)
  {
    for($a = strlen($theString) - 1; $a &gt;= 0 ; $a--)
    {
      if($theString[$a] == '0')
      {
        $theString[$a] = '1';
        break;
      }
      else
        $theString[$a] = 0;
    }
    return $theString;
  }
?&gt;
1
&lt;? // tworzenie stringa o danej dlugosci $str = ''; while(strlen($str) &lt; $bok*$bok) $str .= '0'; // brzydko i na szybko - mozna tez uzyc sprintf // pierwszy obrazek: print '<img alt="" src="image.php?p=' . $str . '" />'; do { $str = oneMore($str); print '<img alt="" src="image.php?p=' . $str . '" />'; } while(is_numeric(strpos($str, '0'))); // dopoki string zawiera zera ?&gt;

To wszystko. Przykład z wyborem wielkości obrazka można zobaczyć TUTAJ. Dowcipnisiów uprzedzam – maksymalny rozmiar to na prawdę maksymalny rozmiar, więcej się nie da :)

Przejdźmy do konkretów… Dlaczego w takim razie nie zabierzemy się za generowanie? “My”? Nie wiem. Wiem, dlaczego ja tego nie zrobię :)

Najpierw rozważania czysto teoretyczne. Zakładając, że w generowanych czarno-białych obrazach na jeden piksel przypada jeden bit danych, rozmiar obrazu wyrażałby się wzorem:
eq4
Zakładamy, że opuszczamy wszelkie nagłówki, CRC i podobne.

Uzależniając rozmiar ściśle od ilości bitów, otrzymujemy ogólny rozmiar obrazu:
eq6

Czyli, dalej teoretycznie, przykładowy obraz o “sensownych” rozmiarach 800×600 w sensownej głębi 256 kolorów zajmowałby 480kB. Nie muszę mówić, ile zajmowałyby wszystkie możliwe takie obrazy, prawda?
Na szczęście tak się nie dzieje, bo wynaleziono kompresję…

Przyjrzyjmy się więc liczbom w praktyce.

Po wygenerowaniu “ręcznie” (czyt. “po losowym pomachaniu myszką w Pant.net) wyszło mi, że dla 8-bitowych plików PNG 800×600 spokojnie można przyjąć średnią wielkość ok. 60kB. No to teraz zastanówmy się, ile takich plików musielibyśmy wygenerować, żeby… były wszystkie. Posługując się kolejny raz wzorem:
eq2
Otrzymujemy:
eq7
Muszę przyznać, że kalkulator Google nie próbował nawet tego obliczyć, a handyCalc zawiesił mi na chwilę telefon, po czym wymusił zamknięcie :)

Z pomocą przyszedł mi Big number scientific calculator, który orzekł, że takich plików byłoby mniej więcej:
eq8. Tak! To znaczy 1525 i 1155952 zera!

Idźmy dalej. Ile zajmowałyby takie pliki w sumie? Przyjmując wspomnianą średnią wielkość 60kB, otrzymujemy:
eq9

Generalnie rzecz ujmując, daje nam to jakieś 4.26*10^1155947 dysków twardych o pojemności 2TB (największe, jakie znalazłem w chwili obecnej na Allegro). Trochę nieopłacalne, prawda?

Przejdźmy do czegoś bardziej ekonomicznego. Weźmiemy na warsztat pliki, na którym już coś widać, czyli pliki wielkości popularnych avatarów – 100×100 pikseli. Dodatkowo zróbmy z nich 4-bitowe (16 kolorów) GIFy. Przeciętny rozmiar takiego pliku to ok. 1.5kB. Ilość plików wynosiłaby około 1.5*10^12041, a całkowita objętość 2.2*10^12032TB. Całkiem nieźle, nie?

No to chwyćmy się brzytwy… 4-kolorowe GIFy 100×100 pikseli, też coś na nich będzie widać…
Przeciętny tego typu GIF zajmuje jakieś 750B. No i ma dużo mniej kolorów, co daje nam większe pole manewru. Obliczmy więc. Takich plików wygenerujemy ok. 4*10^6020. Dużo… Niestety, daje nam to dalej 2.7*10^6011TB!

Jak można z tego wybrnąć sensownie? Hipotetycznie rzecz ujmując, wygenerujmy wszystkie możliwe czarno-białe pliki o wymiarach 10×10 To daje “tylko” 2^100 czyli 1 267 650 600 228 229 401 496 703 205 376 plików :) Zakładając, że jeden zajmowałby średnio 60B, otrzymujemy wciąż 69 175 290 276 410 818 560 terabajtów!

Tak więc biorąc pod uwagę przykładowe rozmiary dysku twardego 2TB: 26,1mm x 101,85mm x 146,99mm, nasze pliki na tych dyskach zajęłyby jakieś 13 514 821 845 480 950 metrów sześciennych. To daje 13 514 821 kilometrów sześciennych. W sumie niby niewiele, bo 0.000 001 247 objętości Kuli Ziemskiej, ale już 0,009 751 objętości wszystkich oceanów.

Zauważmy też, że gdyby takie dyski twarde położyć obok siebie, to zajęłyby jakieś 517 809   266   110 kilometrów kwadratowych, czyli ok. 3476.6 razy więcej, niż powierzchnia lądu na Ziemi i ponad tysiąc razy więcej, niż powierzchnia całej kuli ziemskiej.

Wniosek: to wszystko bez sensu…

(grafiki wzorów wygenerowano za pomocą Roger’s Online Equation Editor)

2 thoughts on “Projekt “Wszystkie Obrazy Świata””

  1. Zachwyca mnie twoja poezja. Zupełnie na serio :)
    Trafiłem tu poprzez fenomenalną aukcję Fiesty z Allegro :D
    Sam też się kiedyś zabawiałem matematyką w podobnym tonie, choć może bez angażowania do tego php, a z rozckliwieniem i łezką w oku mieszając w Basicu na Atari65XE :) W efekcie napisałem kilka artykułów w mojej lokalnej gazecie – numery zaginęły bezpowrotnie, a szkoda :(

    Pozdrawiam :)

Leave a Reply

Your email address will not be published. Required fields are marked *