Kilka dni temu wziąłem udział w moim pierwszym code golfie, gdzie stawką była wejściówka na tegoroczną konferencję Confidence. Ostatecznie nie udało się wygrać, choć okazuje się, że byłem całkiem blisko. Umknął mi tylko jeden mały szczegół…

Jednak od początku. Zadanie polegało na napisaniu programu w jednym z trzech zaproponowanych języków (C++/Python 3.x/JS), który wygeneruje grafikę identyczną jak wzorcowa. Zwycięzcą zostaje osoba której program będzie najmniejszy, w rozumieniu zajmowanego miejsca na dysku. Ja zdecydowałem się na Python 3.

Założenia

Założeniami było, że program będzie uruchamiany poleceniem python3 na Ubuntu Server (19.04) jednak w domyślnej konfiguracji, a tym samym bez żadnych dodatkowych lib-ów oraz bez dostępu do Internetu. Wyjściowa grafika ma być identyczna co wzorcowa po sprowadzeniu do RAW (obie grafiki zostaną sprowadzone do RAW przy użyciu IrfanView, a następnie porównane). Więcej informacji na blogu Gynvaela.

Podejście

Oczywistym było, że wzorcową grafikę trzeba będzie jakoś osadzić w kodzie źródłowym programu i najpewniej skompresować, jednak z uwagi na brak dostępu do Internetu na maszynie testowej, trzeba skorzystać z bibliotek natywnych w Pythonie 3. Pierwsze co przyszło mi do głowy, to biblioteka zlib z funkcją compress, która pozwala na kompresję danych binarnych. Jednak jak się okazało szybko okazało, sama kompresja, nawet z najwyższym stopniem, to zdecydowanie za mało:

import zlib
with open('confidence_2019_golf.png','rb') as f:
a = zlib.compress(f.read(),9)
print(len(a))

19:02:29:nism0@rubik:~/python$ python3 png.py
1569

Po przewróceniu do góry nogami Google-a w poszukiwaniu lepszych metod kompresji w python3 pod linuxem, wpadłem na pomysł, że może warto nieco podrasować sam plik wzorcowy PNG.

Metadane

Pierwsza rzecz jakiej mogłem się pozbyć z pliku PNG, tak aby faktycznie nie zmienić go po konwersji do RAW, to metadane. Szybki rzut okiem czy dostarczony plik zawiera jakiekolwiek:

19:08:15:nism0@rubik:~/python$ exiftool confidence_2019_golf.png
ExifTool Version Number : 10.40
File Name : confidence_2019_golf.png
Directory : .
File Size : 11 kB
File Modification Date/Time : 2019:05:22 19:02:11+02:00
File Access Date/Time : 2019:05:22 19:02:24+02:00
File Inode Change Date/Time : 2019:05:22 19:02:20+02:00
File Permissions : rw-r--r--
File Type : PNG
File Type Extension : png
MIME Type : image/png
Image Width : 1920
Image Height : 1080
Bit Depth : 8
Color Type : RGB with Alpha
Compression : Deflate/Inflate
Filter : Adaptive
Interlace : Noninterlaced
Significant Bits : 8 8 8 8
Pixels Per Unit X : 3780
Pixels Per Unit Y : 3780
Pixel Units : meters
Software : www.inkscape.org
Image Size : 1920x1080
Megapixels : 2.1

Sprawdźmy ile zajmują metadane w tym obrazie:

19:16:02:nism0@rubik:~/python$ ls -ltr confidence_2019_golf.png
-rw-r--r-- 1 nism0 nism0 11746 maj 22 19:16 confidence_2019_golf.png
19:16:25:nism0@rubik:~/python$ exiftool -all= confidence_2019_golf.png
1 image files updated
19:16:32:nism0@rubik:~/python$ ls -ltr confidence_2019_golf.png
-rw-r--r-- 1 nism0 nism0 11688 maj 22 19:16 confidence_2019_golf.png
19:16:36:nism0@rubik:~/python$

58 bajtów, to niewiele jak na 11kB plik, ale liczy się każdy bajt. Czego jeszcze możemy się pozbyć z pliku, aby nie nie zmienić finalnego obrazu? Rzućmy okiem na informacje o pliku, już bez metadanych:

19:19:36:nism0@rubik:~/python$ file confidence_2019_golf.png
confidence_2019_golf.png: PNG image data, 1920 x 1080, 8-bit/color RGBA, non-interlaced

Widzimy, że plik zawiera cztery składowe pikseli – RGBA, jednak nawiązując do informacji nt temat tego jak pliki będą porównywane:

Q: Jak dokładnie będą grafiki porównywane?
A: Grafika testowana oraz wzorcowa zostaną sprowadzone do plików „raw” (czysta beznagłówkowa bitmapa 24bpp), po czym zawartość plików zostanie porównana (nie może być żadnych różnic).

Wobec powyższego, spróbujmy się pozbyć kanału alpha, przy użyciu Gimp-a. Efekt? 8943 bajty z początkowych 11746. To całkiem niezły wynik.

Encoding

Teraz wystarczy skompresować tak przygotowany obraz, zakodować i osadzić go w kodzie źródłowym. Pierwsza metoda kodowania jaka przychodzi do głowy to base64, ale biblioteka base64 dostarcza także kilka innych metod, w tym base85 będące znacznie bardziej efektywne niż base64. Ostateczny wynik danych do osadzenia to:

import zlib,base64
with open('confidence_2019_golf.png','rb') as f:
a = f.read()
ax = zlib.compress(a,9)
print('len(ax) = {}'.format(len(ax)))
ac = base64.b85encode(ax)
print(ac)

19:31:52:nism0@rubik:~/python$ python3 png.py
1358

Kod zgłoszenia

Finalnie, kod mógłby wyglądać np tak:

import zlib,base64
open('confidence.png','wb').write(zlib.decompress(base64.b85decode("c-rd>@N?(olHy`uVBq!ia0y~yU~gbxV6os}0*a(>3=?5sP+;(MaSW-r_2!mg(d{&;hQ#JY$96XUifJh2+rVBRztV4gk@DF!Po})vKJC(PiFKuoUtVtSa1)uRH~Y}X3XlCQ3O4@zKM(fXJA6{Tw}+8o6pVtw3gWsBasa7mFKf1%u_TDSE01<=m>DGrNwlntQXs0Kg@G4DJ2*A4foKIq2WAjGL0|z`od?GSuyPfa3@|OkWCEr+sjEFHmqq{n&r`QqKB#`*y;cz@bb$K_Crzy!)lP5iM{aR2#4S7f!2ZzsZJ!F+4*b9Sep?#@!-t@{P11ugQI2XK)jq0y2x$k_A`CU!({CU5ytdcEa_-$V@8-=HGhOW*_x{qo`#>_}ch)M~%ya91-?GoR%iJg1miRvTc;TFsyG!rBuKBksp3y*m-k|jVnqG#6{k!kjy{moG{`I!!xu5TTX1-6>_w!5N{!S)+>z3kq%A2e17SDTJT5@97_uX&bd^={*S1oVNb9m9Z#m?V8%j{q6Q+h6V?QTgM_2c#to)I<G#edEjoIZV>1MCis!4<vP$_#y(#y{@A&YsKLT>Q^V{#yRqli_b3Jt=vg{C?hiwaD^5zL{4;-s^vRVlP*HVAo-n`Kj$|tos&ce`vLSvinqs-uC`9)&u4b!_5b2Dm`=e>9@l7$@XjROFhsoD=gaeePj7~|L$2=L#`i6i-`Q*I{Vce{+pBeALqSKJ|BMhkBe2xUCVo~m)#0aKWuPvm%ZKJjo&x!pI2vo(o%lYyZ4V@cyln+e`Fb~nexxw^~>+St$ow)U++_N4j7%lbbI&nWtHbOg+*DD<rBk#_wL_Q1I)Otch#R;tX_Ioo&TnE@tyO*b3ZHIU%zbAmiMI$B{qzMv51oBVX#>C`RXl!eV5Wc$Un^fX7G-O@jGupf9ZXTO`8w;KS=&jE5pn9y)5lv-FDL!<qz7dqvbW}<pBdj#Ip9n?JKVD{>U?}mi55JpI=x<!;SRzcLnFUw#2~o-<Q9B?Yj4#zxn&zPs%^8f4%zV+|T-ax8Gc1FYda0U%hf){*HLY4Jq?R6DP@moWOFxaPInRZ3ohG+fx6k|1x+d_O<GMY`pKLcgJVn1_t{5y!yy1TQ_W}ZT&s<y7m3{()Ka`ZBFi*pLg%~JmwFqp#HB+qxxt_k7}ozc0&oq0-xurw<>;!oShi?zq79X>w92I?Kj_Uw)6Fi&2q=)n)3lmhObvuUeDvb{D<XV$>+Mj_v@>z4a7&2D>cG=)_<4!9sepPmHz)dUpoJn_P2MxvL=<*@BW)wwz*28eDmzj$7e^+zVkIZJ~6)b;NQI0zU&Y5hd}AvV1Ik-;>jJ28V!q5JngR~G5*dMUbkTB5{B%XMsE~V{^c?kr5al<Z#p@<@xW8Y(X2aMw5usIJdljh|GaYF_pjgTR=xlG@6V?b{}0|i{<a|f-_7#(Tz)6&3vy0xt9rs<b7M3dNp57MurSy(zfLt{`LTHV%ZlBs-)oBt8JZ)vT@_%c*uXfNK1tNxd6R>I;aI`_?T6=9-V76GXJBC7JQ|9l+DEkye(hv|cT-==GB7X|fYt(xP85#<dVm8D>KIvhg?A=C{i6Zmd%F6$taD0e0syX(nPd")))

Jak widać to tylko 2 linie, które dają w sumie 1680 bajtów. Jak się okazało, to jednak za mało żeby zwyciężyć w code golfie, gdyby nie jeden mały szczegół…

Optymalizacja

Tak bardzo się skupiłem na minifikacji kodu, że zupełnie zapomniałem o optymalizacji samego pliku wzorcowego. Wprawdzie zastanawiałem się, czy nie występują w nim jakieś opcjonalne sekcje, bez których plik mógłby dalej wyglądać tak samo po przekonwertowaniu do RAW, ale ostatecznie wystarczyło użyć optipng aby przyciąć skecję IDAT:

11:30:31:nism0@debian:~/Python$ optipng -o 7 confidence_2019_golf.png
** Processing: confidence_2019_golf.png
1920x1080 pixels, 3x8 bits/pixel, RGB
Reducing image to 4 bits/pixel, 8 colors in palette
Input IDAT size = 8816 bytes
Input file size = 8943 bytes

Trying:
zc = 9 zm = 9 zs = 0 f = 0 IDAT size = 4190
zc = 9 zm = 8 zs = 0 f = 0 IDAT size = 4190
zc = 9 zm = 9 zs = 1 f = 0 IDAT size = 4190
zc = 9 zm = 8 zs = 1 f = 0 IDAT size = 4190
zc = 9 zm = 9 zs = 0 f = 2 IDAT size = 2658
zc = 9 zm = 8 zs = 0 f = 2 IDAT size = 2658
zc = 9 zm = 9 zs = 1 f = 2 IDAT size = 2658
zc = 9 zm = 8 zs = 1 f = 2 IDAT size = 2658
zc = 9 zm = 9 zs = 0 f = 4 IDAT size = 2657
zc = 9 zm = 8 zs = 0 f = 4 IDAT size = 2657
zc = 9 zm = 9 zs = 1 f = 4 IDAT size = 2657
zc = 9 zm = 8 zs = 1 f = 4 IDAT size = 2657
zc = 9 zm = 9 zs = 0 f = 5 IDAT size = 2454
zc = 9 zm = 8 zs = 0 f = 5 IDAT size = 2454
zc = 9 zm = 9 zs = 1 f = 5 IDAT size = 2454
zc = 9 zm = 8 zs = 1 f = 5 IDAT size = 2454

Selecting parameters:
zc = 9 zm = 8 zs = 1 f = 5 IDAT size = 2454

Output IDAT size = 2454 bytes (6362 bytes decrease)
Output file size = 2600 bytes (6343 bytes = 70.93% decrease)

To w rezultacie daje efekt końcowy w postaci 1185 bajtów

[UPDATE]

Z ciekawości

Ciekaw byłem, jak poradzą sobie inne narzędzia dostępne spod Linuxa, do optymalizacji plików PNG. Poniżej przedstawione 2 z nich, operujące na pliku confidence_2019_golf.png już bez metadanych oraz bez kanału alfa (8943 bajty).

11:39:46:nism0@debian:~/Python$ ./zopflipng confidence_2019_golf.png confidence_2019_golf.png
Optimizing confidence_2019_golf.png
Input size: 8943 (8K)
Result size: 2463 (2K). Percentage of original: 27.541%
Result is smaller
File confidence_2019_golf.png exists, overwrite? (y/N) y

Po zakodowaniu kompresji i zakodowaniu w base85 plik confidence.py ma rozmiar 1061 bajtów. To już wystarczyło do wygranej, ponieważ zwycięzca uzyskał 1133 bajtów (ogłoszenie wyników tutaj)

I na koniec, pngout:

11:48:19:nism0@debian:~/Python$ ./pngout confidence_2019_golf.png
In: 8943 bytes confidence_2019_golf.png /c2 /f5
Out: 4159 bytes confidence_2019_golf.png /c3 /f0 /d4, 8 colors
Chg: -4784 bytes ( 46% of original)

Read More