Jeśli dotarłeś lub dotarłaś do tego pliku - gratulacje! Masz szansę wziąć udział w wielkim wyzwaniu CIF, w którym to nerdy biją się o to kto potrafi lepiej zoptymalizować program.
Wyzwanie polega na napisaniu najszybszego możliwie dekodera formatu CIF w dowolnie obranym przez siebie języku. Jeśli nie masz pomysłu, to proponuję jeden z poniższych:
Specjalnie wybrałem tutaj języki mniej znane, bo w wyzwaniu chodzi o to, żeby było… cóż, wyzwaniem, a niekoniecznie szlifowaniem skilli w językach które się już zna. Nauczenie się nowego języka ma dużo zalet, np. zobaczenie innych perspektyw na świat programowania, więc gorąco zachęcam.
Ja wybrałem C ponieważ spędzając czas głównie w językach dość nowoczesnych moje umiejętności programowania w C są niezbyt rozwinięte.
Oto definicja formalna składni CIF, zapisana w notacji PEG.
file ← magic version dimensions metadata pixels
flag ← 'polish'
flags ← flag (',' ws flag)*
magic ← 'CIF:' ws flags nl
version ← 'WERSJA' ws int nl
width ← 'szerokość:' ws int
height ← 'wysokość:' ws int
bpp ← 'bitów_na_piksel:' ws int
dimensions ← 'ROZMIAR' ws width ',' ws height ',' ws bpp nl
mdkey ← [^ ]
mdvalue ← [^\n]
metadatum ← 'METADANE' ws mdkey ws mdvalue nl
metadata ← metadatum*
pixel ← int ';' ws int ';' ws int (';' ws int)? nl
pixels ← pixel*
hundreds ←
'sto' / 'dwieście' / 'trzysta' / 'czterysta' / 'pięćset' /
'sześćset' / 'siedemset' / 'osiemset' / 'dziewięćset'
nteens ←
'dziesięć' / 'jedenaście' / 'dwanaście' / 'trzynaście' /
'czternaście' / 'piętnaście' / 'szesnaście' / 'siedemnaście' /
'osiemnaście' / 'dziewiętnaście'
tens ←
'dwadzieścia' / 'trzydzieści' / 'czterdzieści' / 'pięćdziesiąt' /
'sześćdziesiąt' / 'siedemdziesiąt' / 'osiemdziesiąt' / 'dziewięćdziesiąt'
ones ←
'jeden' / 'dwa' / 'trzy' / 'cztery' / 'pięć' /
'sześć' / 'siedem' / 'osiem' / 'dziewięć'
zero ← 'zero'
thousand ← 'tysiąc'
thousands1pair ←
(hundreds ws)? (tens ws)? ('dwa' / 'trzy' / 'cztery') ws 'tysiące'
thousands2pair ←
(hundreds ws)?
((tens ws)? ('pięć' / 'sześć' / 'siedem' / 'osiem' / 'dziewięć') / nteens)
ws 'tysięcy'
thousands ← thousand / thousands1pair / thousands2pair
int100 ←
hundreds ws nteens /
hundreds ws tens ws ones /
hundreds /
nteens /
tens ws ones /
tens /
ones
int ←
zero /
thousands ws int100 /
int100
ws ← ' '+
nl ← '\n'+
Symbole terminalne:
'abc'
- ciąg znaków - sprawdza dosłowny ciąg znaków w pliku[abc]
- zbiór znaków - sprawdza czy znak należy do zbioru[^abc]
- dopełnienie zbioru znaku - sprawdza czy znak nie należy do zbioru
Uprzedzam że nie testowałem powyższej specyfikacji i posiada ona charakter czysto poglądowy. Mogą się w niej znajdować drobne błędy.
Termin wysyłania dekoderów to 14 lutego 2022. Dekodery wysłane do mnie po terminie nie ukażą się w benchmarku.
Niestety w Polsce jest bieda aż piszczy więc za udział w wyzwaniu nie ma nagród pieniężnych. Za nagrodę możecie uznać swój udział, kod który napiszecie, oraz wynik w benchmarku. Jeśli będzie to implementacja szczycąca się w pewnych aspektach (szybkość, czytelność kodu, kompaktowość) to polecam dopisać ją sobie do portfolio.
Każdy kto się zgłosi z działającym, przechodzącym suitę testów dekoderem, zostanie umieszczony w filmie podsumującym, który powinien ukazać się w lutym (może się nie ukazać ponieważ jestem leniem, zwłaszcza gdy są ferie).
Zanim pojawi się film, wyniki benchmarku będą podane na tej stronie.
- Dekoder musi być open source. Kod źródłowy nie musi być publiczny podczas trwania konkursu (nie sądzę aby ktokolwiek chciał zostać okradnięty z kodu), ale po minięciu terminu kod źródłowy musi zostać otwarty pod jedną z licencji wolnego oprogramowania.
- Dekoder musi być w stanie bezstratnie zdekodować dowolny obrazek CIF do pliku formatu BMP lub PNG.
Obrazki testowe można znaleźć w repozytorium comes-group/cif-tests. Znajduje się tam również skrypt do automatycznego testowania dowolnego dekodera, który przydziela ocenę w zależności od tego ile testów przeszedł. Jeżeli ktoś dostanie dekoder z oceną Silver, to po terminie wysyłania dekoderów sprawdzę czy dekoder nadaje się do oceny Gold (nie próbuje obejść testów).
Benchmark wykonam po nadaniu ocen Gold dekoderom kwalifikującym się na tę ocenę. Będzie on wykonywany na różnych obrazkach które nie pochodzą z folderu cif-tests, więc dekodery powinny być przygotowane na wszystko.
Własne obrazki można generować enkoderem cif.nim. Nie jest on demonem szybkości, ale lepszy rydz niż nic. Swoją drogą cif.nim posiada również dekoder którego można użyć jako podstawę do napisania własnego, choć wątpię żeby przechodził wszystkie testy bez zająknięcia (nie sprawdzałem.)
- Używaj https://godbolt.org
- Traktuj plik wejściowy jako strumień. Nie fragmentuj go na dalsze kawałki
split
em czy też innymi funkcjami które alokują pamięć. - (Nad)używaj optymalizacji kompilatora. Zwłaszcza CSE (common subexpression elimination)
Cześć okej. To jest mój dekoder: https://github.com/liquidev/cif123
Pozdrawiam. Polecam. Oglądam.
PS. Tak naprawdę to mój dekoder zostanie upubliczniony
[TODO: wstaw termin tutaj]14 lutego 2022, jak skończy się konkurs. https://github.com/comes-group/djcifex