HW6: Koření musí proudit
Odevzdávání částí A a B je ukončeno.
Autor zadání Roman Lacko
Odevzdávané soubory src/*
Konec odevzdání části A 2026-05-11 24:00
Konec odevzdání části B 2026-06-01 24:00
Kostru k úkolu nelze stáhnout

Představení úkolu

Hluboko v lidském nevědomí je všudypřítomná potřeba logického vesmíru, který dává smysl. Ale skutečný vesmír je vždy o krok za logikou.
— Frank Herbert

První část (A)

„Nenechali nám nic, jenom tyto rozbité krámy,“ povzdechl si Vévoda při odletu prvního sběrače. „Pokud nezvládneme vytěžit dostatek koření, je po nás.“

Vašim úkolem je zjistit, kolik koření se vytěží v průběhu dne. Hardware řídicí věže a servery nejsou po nadvládě soupeřící rodiny nad planetou v nejlepším stavu, proto je v tom poněkud nepořádek.

Každý sběrač se vůči řídicí věži identifikuje 32-bitovým sériovým a 32-bitovým identifikačním číslem. Pak odesílá 64-bitové události, popsané níže, které věž přímo zapisuje do souboru s příponou .dat. Souborů pro stejný sběrač může být víc, například když dojde k dočasnému přerušení spojení kvůli písečné bouři. Některé události informují i o vyprázdnění nádrže s kořením, a tyto jsou právě důležité pro odhad efektivity těžby.

Formát záznamu událostí

Název souboru se záznamem událostí začíná znakem jiným než . a má příponu .dat, např. 57a3f.dat. Obsah souboru je binární a má následující formát:

  • 32-bitové celé číslo, sériové číslo modelu sběrače.

  • 32-bitové celé číslo, identifikační číslo.

  • Pak následuje 0 nebo více 64-bitových událostí:

    • 32-bitové celé číslo, časová známka.

    • 16-bitové celé číslo, typ události.

    • 8-bitové celé číslo, první argument události.

    • 8-bitové celé číslo, druhý argument události.

Všechna čísla jsou bez znaménka a jsou uložena jako Little Endian.

Typ události určuje význam argumentů:

Událost Význam První argument Druhý argument

0x00

PING

Zeměpisná Dunopisná šířka

Dunopisná délka

0x01

LAND, sběrač přistál

Ignoruje se

Ignoruje se

0x02

LIFT, sběrač vzlétl

Ignoruje se

Ignoruje se

0x03

CARGO, sběrač vyprázdnil nádrž s kořením

Číslo nádrže (0 - 15)

Zaplnění nádrže

0x04

SANDWORM, hlídka vidí písečného červa

Odhadovaná velikost červa

Odhadovaná vzdálenost od sběrače

Jiné

Neznámé události ignorujte

-

-

Tyto soubory nejsou textové, proto je nelze rozumně vypsat nebo editovat pomocí programů, které očekávají text. Následující ukázka souboru test/data/simple/example.dat proto popisuje obsah souboru jako textově zapsané bajty.

Zkuste soubor vypsat programy hexdump (hexdump -C FILE) nebo xxd (xxd FILE). 
30 20 00 00  01 00 00 00    # Sériové a produktové číslo 0x00002030 0x00000001

# Čas        Typ   A1 A2
01 00 00 00  01 00 00 00    # t=1, LAND
02 00 00 00  00 00 28 23    # t=2, PING z pozice 40, 35
03 00 00 00  03 00 00 55    # t=3, CARGO nádrž 0, zaplnění 85
04 00 00 00  03 00 01 05    # t=4, CARGO nádrž 1, zaplnění 5
05 00 00 00  04 00 1e 46    # t=5, SANDWORM velikosti 30 ve vzdálenosti 70
06 00 00 00  00 00 29 25    # t=6, PING z pozice 41, 37
07 00 00 00  02 00 00 00    # t=7, LIFT

Cílem je najít všechny takovéto soubory a zjistit celkový objem koření, které se vytěžilo. V tomto případě je celkový vytěžený objem koření 85+5, tedy 90.

Dále,

  • Sběrač může mít nanejvýš 16 nádrží označených 0 až 15. Pokud je v záznamu nádrž s jiným označením, poznamenejte si chybu, a pokračujte zpracováním dalších záznamů v tomto souboru.

  • Po vyprázdnění nádrže ji může sběrač naplnit znovu.

  • Sběrač může vytvořit více než jeden soubor.

  • Pokud soubor obsahuje nekompletní událost, poznamenejte si chybu.

Popis rozhraní

Implementujte funkci:

struct rv {
    size_t records;
    size_t errors;
    double value;
};

struct rv spice_stats(const char *dir);

Funkce otevře adresář zadaný jako argument dir a rekurzivně (tj. sestoupí i do podadresářů) analyzuje všechny záznamy.

  • Funkce ignoruje cokoliv, co není adresář nebo soubor.

  • Funkce navíc ignoruje všechny skryté adresáře i soubory; tedy ty, které začínají ..

  • Záznam pro sběrač začíná znakem jiným než . a má příponu .dat, ostatní soubory se nepokouší číst.

  • Každý sběrač má nejvýše 16 nádrží na koření označených 0 až 15.

  • Pokud se nepovede některý soubor nebo adresář otevřít, poznamenejte si chybu, a pokračujte dalším záznamem v souborovém systému.

Pro každou chybu vypište na standardní chybový výstup i důvod. Chybové výpisy se netestují, ale program se vám bude lépe ladit.

Funkce vrátí strukturu struct rv s těmito atributy:

  • records je počet zpracovaných sběračů, tj. souborů, ze kterých se povedlo přečíst alespoň sériové a produktové číslo. Pokud sběrač vyprodukuje více souborů, započítá se pouze jeden.

  • errors je počítadlo chyb. Pro rekapitulaci, za chyby se považuje:

    • Nelze otevřít adresář (skryté adresáře se ignorují).

    • Nelze otevřít soubor se záznamy (skryté a jiné soubory se ignorují).

    • Soubor se záznamy není kompletní nebo obsahuje špatné informace (pro soubor s více chybami zvyšte errors pouze jednou).

  • value je celkové množství vytěženého koření.

Pro testovací adresář test/data/simple program nalezne basic.drv a ignoruje jej; nalezne i example.dat a tento soubor přečte. Další soubory ani adresáře tam nejsou, a tak vrátí

  • records = 1

  • errors = 0

  • value = 90.0

Proč double value?

Návratový typ double umí reprezentovat i absurdně velká čísla nad limit UINT64_MAX, byť se ztrátou přesnosti. Vévoda zatím nečeká, že se tolik koření vytěží, ale jednoho dne snad ano.

Druhá část

„Účet od Kosmické gildy nesedí,“ říká Vévoda čta výstup programu. „Než si předvolám Navigátora, mentate, prověř data ještě jednou.“ Po snídani plné koření a procházení specifikace sběračů vykřiknete slovo již tisíce let mrtvého jazyka, „Εὕρηκα!“ Různé modely sběračů mají přece jinou kapacitu nádrží!

Událost 0x03 (CARGO) pro vyprázdnění nádrže má jako druhý parametr zaplnění nádrže v prvním parametru. Není to však objem ani hmotnost, nýbrž procentuální zaplnění, kde maximum je 255. Například hodnota 85 z příkladu v části A znamená \$85/255 approx 33%\$. Skutečný objem koření tak závisí od celkové kapacity nádrže, která závisí od modelu sběrače.

Řídicí věž udržuje ovladače pro sběrače ve stejném excelentním chaosu jako záznamy od sběračů. Rozšiřte řešení z části A o načítání těchto ovladačů a upravte výpočet celkového objemu vytěženého koření.

Formát ovladačů

Název souboru s ovladačem (popisem) sběrače začíná znakem jiným než . a má příponu .drv, např. WCygCcVm.drv. Obsah souboru je binární a má následující formát:

  • 32-bitové celé číslo, sériové číslo modelu sběrače.

  • Pak následuje 0 nebo více dvojic 16-bitových čísel:

    • První 16-bitové celé číslo reprezentuje číslo nádrže.

    • Druhé 16-bitové celé číslo reprezentuje kapacitu nádrže.

Všechna čísla jsou bez znaménka a jsou uložena jako Little Endian.

Následuje ukázka souboru test/data/simple/basic.drv, který máte v datasetu již z části A:

30 20 00 00                 # Ovladač sběračů se sériovým číslem 0x00002030

# Nádrž      Kapacita
00 00        1e 00          # 0: Kapacita 30
01 00        66 00          # 1: Kapacita 102

Sběrač z ukázky v části A vysypal nádrž 0 se zaplněním 85/255 a nádrž 1 se zaplněním 5/255, než ho vyrušil písečný červ. Celkový vytěžený objem koření spočítáme jako 30 * (85/255) + 102 * (5/255), tedy celkem 12.

Dále,

  • Číslo nádrže musí být 0 až 15 včetně a kapacita musí být větší než 0; jinak si poznamenejte chybu a pokračujte zpracováním dalšího záznamu.

  • Protože je v ovladačích poněkud nepořádek, pokud by ve stejném souboru nebo mezi dvěma soubory se stejným sériovým číslem došlo ke konfliktu v kapacitě nádrže, použijte větší kapacitu.

  • Ovladač nemusí popisovat objem všech nádrží, protože modely nemusí některé nádrže vůbec mít. Pokud však sběrač vyprázdní nádrž, pro kterou není v ovladači uvedená kapacita, započítejte chybu a nádrž ignorujte.

Názvy souborů (kromě přípony) nenesou žádnou podstatnou informaci.
Nelze se spoléhat, že z názvu souboru se záznamem sběrače nebo ze sériového a produktového čísla lze odvodit název souboru s ovladačem. Taky není zaručeno, že existuje deterministické řazení souborů tak, aby se ovladače nalezli dříve než záznamy sběračů. Raději považujte názvy souborů před příponou za zcela náhodné.

Poznámky

  • Můžete používat funkce ze standardu POSIX.1-2008.

  • Pokud nevíte, kde začít, podívejte se na opendir(3), readdir(3) a stat(3).

  • Testování nepřístupných adresářů a souborů je poněkud složitější kvůli tomu, že uvnitř GitLab CI kontejneru má proces svůj jmenný prostor a v něm privilegovaná práva, jako kdyby byl root. Takovému procesu nelze zabránit v přístupu k souborům a adresářům pouhým chmod(1). Lze využít několik alternativ, které jsou stručně popsané i v test/example.c:

    1. Omezit přístup pouze na vybrané soubory v GitLab CI lze pomocí námi dodané funkce restrict_access(). Tato funkce vyžaduje podporu Landlock v jádře; pokud to na vašem počítači nefunguje, zkuste Aisu.

    2. Lokálně můžete omezit dataset pomocí chmod(1), pak však tento test „vypněte“ pomocí kontroly geteuid() z unistd.h.

  • Ukázkové testy z části A lze upravit pro část B změnou dvou hodnot:

    1. V testu example::from_main upravte cr_expect(epsilon_eq(dbl, rv.value, 90.0, ε)); na hodnotu 12.0.

    2. V testu example::inaccessible upravte cr_expect(epsilon_eq(dbl, rv.value, 90.0, ε)); na hodnotu 0.0; v tomto datasetu není žádný ovladač.

Vytváření vlastních binárních souborů

Vytvořit vlastní binární soubory pro testování lze několika způsoby:

  • Napište si pomocný program v C.

  • Použijte program xxd. Například sériové a produktové číslo z příkladu výše lze vytvořit takto:

    echo '30 20 00 00 01 00 00 00' | xxd -r -p >harvester.dat

  • Použijte modul struct v Python. Hlavičku a první dvě události z příkladu v části A lze zapsat takto:

    import struct

with open("output.dat", "wb") as f:
    f.write(struct.pack("<I I", 0x2030, 0x01))
    f.write(struct.pack("<I H B B", 1, 1, 0, 0))
    f.write(struct.pack("<I H B B", 2, 0, 40, 35))

    Ukázkový soubor ovladače z části B lze zapsat takto:

    import struct

with open("output.drv", "wb") as f:
    f.write(struct.pack("<I", 0x2030))
    f.write(struct.pack("<H H", 0, 30))
    f.write(struct.pack("<H H", 1, 102))
vygenerováno 2026-07-15 08:01 upravit