Práce se souborovým systémem FAT16

Po zvládnutí řízení pevného disku a CF karty jsem potřeboval jednoduchý systém, jakým ukládat soubory. Pro jednoduché operace mohou být na začátku disku uloženy adresy začátků a konců souborů. Problém nastáva ve chvíli, kdy dojde ke smazání souboru. Pokud se další ukládaný soubor nevleze do vzniklé mezery, tak dochází ke ztrátě části kapacity. Čím více zápisů/mazání bude provedeno, tím více kapacity bude ztraceno.
Z tohoto důvodu byl vymyšlen systém FATxx, který dělí paměťový prostor na bloky dat - takzvané clustery. Soubor pak může být rozfragmentovaný do jednotlivých clusterů. Tímto systémem dochází ke ztrátám pouze v posledním clusteru souboru, který většinou není plně využit. V paměťovém prostoru jsou dále tzv. vstupní body, které obsahují jméno souboru, atributy, číslo prvního clusteru daného souboru nebo adresáře, délku souboru a pár dalších informací. Poslední částí sytému FATxx je vlastní alokační tabulka FAT. Každá její buňka patří k jednomu clusteru a obsahuje vždy číslo následujícího clusteru souboru nebo adresáře. Pro poslední, prázdný nebo poškozený cluster jsou v buňce speciální hodnoty. Pro FAT12 je počet clusterů omezen na přibližně 4096 (2^12), pro FAT16 je to asi 65536 (2^16) a pro FAT32 teoreticky až 4294967296 (2^32). FAT32 ve skutečnosti využívá pouze 2^28 clusterů a nejvyšší 4 bity by měly být maskovány. V případě M$ Windows se pak využívá pouze 2^22 clusterů. Velikost jednoho souboru je pro systémy FATxx omezena na 4096MB.

Je to první sektor disku (LBA adresa 0) a obsahuje informace o takzvaných partition (oddílech disku), které mohou být na disku až 4. Mimo informace o oddílech je v tomto sektoru takzvaný "Executable code", který nás ale v souvoslosti s jednočipem nemusí zajímat. Pokud sektor skutečně obsahuje MBR, tak poslední 2B sektoru obsahují takzvanou "Executable mark" 55AAh. Rozmístění dat v MBR je naznačeno v tabulce:

Z údajů ve vstupu pro každou partition jsou podstatné jen typ partition, podle kterého lze identifikovat FAT16, počet sektorů mezi MBR sektorem a boot sektorem dané partition a možná by se dala využít ještě délka partition, ale tu lze nalézt i v boot sektoru vlastní partition.

Je umístěn na adrese udané ve vstupu partition v MBR. LBA adresa se dá vypočítat jednoduše takto:
(FAT16 boot rec.) = MBR + (Počet sektorů mezi MBR a začátkem partition)

V tomto sektoru jsou všechny potřebné informace k partition. Poslední 2B jsou opět tzv. executable mark a jejich přítomnost znamená platnost FAT16 boot rec. Vícebytová čísla jsou ukládána vždy v pořadí od nejméně významného (LSB byte první). ASCII řetězce jsou ukládány opět zleva doprava (nečekaně) a jsou zarovnávny vlevo. V nevyužitých polích jsou znaky mezery (20h). Přesněji měly by být, ale třeba firmware některých digitálních fotoaprátů se s vyplněním neobtěžuje a nechá tam znaky 00h.

Nyní se pokusím trochu přiblížit formát vlastní alokační atbulky FAT. LBA adresu začátku lze vypočítat následovně:
(Začátek 1. FAT) = (FAT16 boot rec.) + (Počet sektorů mezi FAT16 boot rec. a začátkem 1. FAT)
Délka FAT je udána ve FAT16 boot recordu a je třeba vždy respektovat její maximální možnou délku 256 sektorů. Je složená až z 2^16 buněk o velikosti 2B. První buňka je vyhrazená (netuším co je zač, ale má hodnotu FFFFh), další buňka je u HDD FFF8h a LSB je opět popisovač média. Od 3. buňky už začíná vlastní FAT. Každá buňka pak náleží jednomu clusteru disku. Buňky mohou obsahovat hodnoty uvedené v tabulce.

Oproti FAT32 je celkem neobvykle (s prominutím idiotsky) vyřešen kořenový adresář. Nalézá se hned za poslední tabulkou alokace (většinou 2.FAT) a je pevně vyhrazen a má pevně danou délku, která je uvedena ve FAT16 boot recordu. Standardně je to 512 vstupů neboli 512*32B, což je 16384B nebo 32 sektorů. Začátek kořenového adresáře je tedy na LBA adrese:
(Začátek kořenového adresáře) = (začátek 1.FAT) + (délka jedné FAT)*(počet FAT)
V této oblasti tedy může být uloženo zpravidla 512 vstupů podadresářů, souborů nebo LFN. První vstup je obvykle "disk volume", takže už zbývá jen 511 vstupů. Pokud se používají dlouhá jména, tak se tento prostor velmi rychle zaplní (13 písmen = 1 vstup, každý soubor ještě navíc 1 vstup).
Jak už jsem naznačil, root u FAT16 má 2 hlavní omezení. Jednak je to jeho nepříjemně omezená velikost, což se dá vyřešit vhodným naforamátováním a vyhrazením většího prostoru (fdisk ve W98 nastavuje vždy 512). Druhá nepříjemnost je, že pro procházení položek v root musíte použít jinou rutinu, něž pro procházení podadresářů. Důvod je prostý - root neleží v oblasti dat, takže do něj nelze vstoupit přes číslo 1.clusteru jako do libovolného podadresáře a ani ho nelze procházet stejnou rutinou, protože podadresáře narozdíl od root mohou být fragmentovány. U FAT32 je tento problém odstraněn tím, že root je vytvořen stejně jako každý podadresář v oblasti dat. Číslo počátečního clusteru je uloženo přímo v boot recordu.

Následuje hned za kořenovým adresářem. Její LBA adresu lze vypočítat následovně:
(Začátek dat)=(Začátek kořenového adresáře) + (počet vstupů do root)/16
Oblast dat je rozdělena do tzv. clusterů, což jsou skupiny sektorů. Počet sektorů v clusteru lze vyčíst z FAT16 boot recordu. Počty sektorů v clusteru mohou být 1,2,4,8,16,32,64 a 128, ale i u malých disků, kde by bylo možné použít cluster velikosti menší než 4kB, se většinou používá 4kB. Z povolených hodnot platných clusterů a počtu sektorů v 1 clusteru pak vyplývá maximální kapacita FAT16 - 4095,875MB. Clustery mohou obsahovat data (části souborů) nebo položky vstupů, které náleží jednotlivým podadresářům. LBA adresu prvního sektoru v daném clusteru lze vypočítat následovně:
(1.sektor clusteru)=(Začátek dat) + (cluster - 2)*(počet sektorů na cluster)

Někdy také označované jednoduše jako položky. Každý vstup je dlouhý 32B a jsou v adresářích umisťovány jedině po násobcích 32B - ofsety 00h, 20h, 40h, 60h ... Vstupů existuje několik základních druhů. Předně je to vstup "disk volume", na který narazíte většinou hned na začátku kořenového adresáře. Ten nemá prakticky žádný význam a obsahuje v poli pro jmého souboru/adresáře 11 znaků dlouhý řetězec "disk volume" obsažený také v boot recordu. Druhým typem vstupu je vstup souboru. Dalším druhem je vstup adresáře a posledním je vstup dlouhého jména LFN. Z tabulky a grafického znázornění je vidět, co vstup obsahuje.

V poli název a přípona souboru mohou být použity jen některé znaky. Neznám je všechny, ale jsou to především velké znaky anglické abecedy, čísla a např. "~". Mezery uprostřed názvu nejsou povoleny, ale zbytek nevyužitého pole je jimi vyplněn. Názvy jsou zarovnány vlevo. Pro "disk volume" je pole přípony i názvu sloučeno do 11 znaků. Pokud dojde ke smazání adresáře nebo souboru, nebude vstup celý nahrazen nulami, ale 1. písmeno názvu (ofset 00h) bude přepsáno znakem E5h! Proto je třeba vstupy při prohledávání podle této podmínky filtrovat.
Podle prvku atribut se rozlišují jednak jednotlivé druhy vstupů a pak také parametry souborů (skrytý, systémový, ...). Nelze však rozlišovat jen jednotlivé bity. Vstup LFN má záměrně hodnotu atributu 0xF, což je nepovolená hodnota, takže ji DOS ignoruje a FAT16 je tak zpětně kompatibilní. Před testováním jednotlivých bitů je tedy třeba testovat celkovou hodnotu na 0xF. K času a datu asi není co dodat. Další pole je číslo prvního clusteru adresáře nebo souboru. Poslední 4B obsahují délku souboru (asi i adresáře - nezkoumal jsem) v Bytech.

Ke vstupu souboru již bylo řečeno víceméně vše. Zbývá pouze zopakovat, že vstup souboru nemůže obsahovat v atributu bitový příznak adresáře, disk labelu a celková hodnota nesmí být 0xF. Zda se jedná o vstup souboru, lze tedy zjistit pouze z těchto 3 podmínek.

Pro vstup adresáře platí prakticky totéž co pro soubor, pouze atribut nesmí obsahovat příznak disk label a celková hodnota nesmí být 0xF.

Jak už bylo řečeno, jedná se o vstup určený pro ukládání dlouhých jmen. Jméno je zde navíc uloženo v UTF16 kódování (odvar unicode - znaky společné pro CP1250 odpovídají unicode), takže může obsahovat nejrůznější znaky. Grafické znázornění vstupu je vidět na obrázku.

Jak je vidět, tak muselo být zachováno několik standardních položek. Hlavní z nich je již zmiňovaný atribut, který je u LFN vždy 0xF. CRC obsahuje kontrolní součet základního názvu ve formátu 8.3. Význam položky 1.cluster mi není přesně znám (nikdy jsem ho nepoužil), ale měl by zřejmě obsahovat číslo clusteru, kde řetězec položek LFN začíná (nejspíš :-). Vlastní řetězec znaků je v LFN vstupu rozdělěn na několik částí, jak je vidět z obrázku. Díky UTF16 má každý znak velikost 2B. První je uložen vždy LSB.
Celý název samozřejmě není uložen v jednom vstupu, ale je rozdělěn na více částí po 13-ti znacích. Grafické znázornění uspořádání více položek LFN je na dalším obrázku.

Jak si můžete všimnout, tak nejenže nás M$ obšťastnil tím, že jsou jednotlivé části názvu řazeny pozpátku, ale navíc jsou umístěny před vlastním krátkým vstupem adresáře nebo souboru. Toto značně komplikuje načítání. Jediné, co se pánům od M$ nepovedlo zkazit je, že LFN položky jednoho názvu a příslušný vstup souboru/adresáře musí být u sebe a nemůže mezi nimi být nic jiného. Z uvedeného příkladu je také vidět funkce 1. bytu označeného N. Ten obsahuje pořadí částí názvu souboru s tím, že poslední část obsahuje pořadové číslo zvětšené o hodnotu 40h. Z toho také vyplývá, že maximální počet znaků názvu je 832. M$ sice tvrdí, že je to 255, ale to je pouze SW omezení. Zde se také hodí připomenout, že maximální délka cesty ve Windows je tuším 260 znaků (bráno jako celá cesta např. "neco/ahoj/nictu").
Celý název je jeden řetězec obsahující jak jméno, tak i příponu a narozdíl od základního vstupu je zde i znak tečka (pokud je přítomna). Celý řetězec je zakončen znakem s hodnotou 0000h a pak už do konce položky na místě znaků následují pouze hodnoty 0xFFFF. Pokud je poslední písmeno názvu na poslední pozici (1Eh) LFN, tak už není zakončen 0000h a je to poslední část názvu LFN. Při načítání se tedy musí kontrolovat i hodnota N a pokud je větší než 40h, tak jde o poslední část názvu. Zbývá ještě doplnit jednu důležitou skutečnost - pokud název splňuje podmínky názvu 8.3 (velké znaky, 8.3, ...), tak je vytvořen jen základní vstup, nikoliv vstupy LFN!!! Proto pokud vytvoříte rutinu čtení LFN, tak nezapomeňte, že musíte být schopní načíst i 8.3 název.

Jak pracovat s FAT - jak číst fragmentovaná data

Na následujícím obrázku je naznačen jednoduchý příklad čtení souboru z tabulky alokace FAT. Barevně jsou označeny buňky, které patří vždy 1 souboru nebo adresáři. Šedě jsou označeny nepoužitelné buňky FAT. Bíle jsou označeny volné.

Nahoře je příklad vstupu se jménem "NECO.DAT". Z atributu s hodnotou 20h se dozvíme, že je nastaven pouze archiv bit a jde tedy o vstup souboru. Z ofsetu "1.cluster" si přečteme číslo 1.clusteru souboru, které je v našem případě 0002h. Nyní tedy načteme z FAT buňku číslo 0002h. V této buňce je pak uloženo číslo clusteru (a také další buňky FAT), kde soubor pokračuje a to jest 0005h. Stejným postupem pokračujeme dokud nenarazíme na buňku s hodnotou FFF8h-FFFFh, která nám udává, že jde o poslední cluster souboru. Postupně načítané čísla buňek (včetně hodnoty ze vstupu souboru) si lze buďto ukládat do zásobníku, nebo průběžně vypočítávat adresy clusterů v oblasti dat a data rovnou načítat. Záleží na tom, co se souborem potřebujeme dělat. U tohoto konkrétního souboru jsme zjistili, že je uložen ve třech clusterech. Poslední cluster však většinou není zcela zaplněn daty, a proto je třeba načíst ze vstupu souboru skutečnou délku v Bytech.
Číslo sektoru FAT s hledanou buňkou a ofset ve WORDECH v sektoru se vypočíta podle následujícího vzorce:
(Sektor hledané buňky)=(Začátek FAT) + (Hledaná buňka) div 256
(Ofset buňky v sektoru)=(Hledaná buňka) mod 256
Výpočet je jako všechny ostatní zde uvedené časově nenáročný. Dělení je celočíselné, což znamená pouze 8x rotaci čísla buňky vpravo. 8 bitů "vyrotovaných" vpravo je pak rovnou výsledek druhého vzorce, a to ofset v sektoru ve wordech. Zbývajících 8 bitů je číslo sektrou, které se přičte k LBA adrese začátku FAT. Zkušenějším jistě neuniklo, že v případě použití 8-bitových MCU je 16-bitové číslo vždy děleno do 2 registrů a tedy MSB registr + začátek FAT je první výsledek a LSB registr je rovnou ofset v Bytech. Kromě součtu tedy není třeba nic počítat.

   Systém FATxx pracuje s takzvanou stromovou strukturou. Začátkem "stromu" je kořenový adresář. Ten se pak pomocí podadresářu větví na další větvě. Každý podadresář se zase může větvit libovolně dále a v kterémkoliv adresáři mohou být uloženy soubory. Z toho mimo jiné vyplývá, že pokud přijdete o kořenový adresář, tak se těžko dostanete k podadresářům a zbytku dat.
   Podadresáře jsou v systému FATxx chápány podobně jako suobory a stejně se s nimi také pracuje. Liší se pouze atributem. V kořenovém adresáři si vyberete vstup požadovaného adresáře a stejně jako u souboru zjistíte, které clustery obsahuje. Ve všech těchto clusterech se pak mohou vyskytovat položky vstupů souborů nebo dalších podadresářů (a samozřejmě LFN vstupů). Vyhledávání položek probíha úplně stejně jako v kořenovém adresáři, ale oblast dat adresáře je dělená na více clusterů místo jednoho bloku.
   Jistě nikomu neuniklo, že v souborových manažerech je vidět adresář označený jako ".." a znamená návrat o úroveň blíž ke kořenovému adresáři. Kdo zažil DOS nebo experimentoval v příkazovém řádku s příkazem "dir", ten si jistě všiml, že je vypsán i adresář ".", který nás vrací zpět do adresáře, kde právě jsme - v čísle 1.clusteru obsahuje počáteční cluster podadresáře, kde právě jsme. Dokud jsem se však nezabýval souborovým systémem FATxx detailně, tak jsem předpokládal, že tyto 2 adresáře jsou generovány jen virtuálně, aby se bylo možné pohybovat ve struktuře adresářů pomocí příkazu cd (např. "cd .."). Když jsem však vytvořil rekurzivní funkci pro výpis stromu adresářů, tak se mi program vždy v prvním adresáři zacyklil. Podíval jsem se tedy jak přesně adresář vypadá a ejhle - adresáře "." i ".." jsou v každém adresáři fyzicky zapsány, a to hned na začátku. Pokud je tedy při procházení položek adresářů chcete filtrovat, tak po otestování atributu ješte proveďte test na 1 znak názvu. Pokud je tam znak ".", který odpovídá hodnotě 2Eh, tak vstup vyhodnoťte jako nepltaný.

Ukázkové programy a možná i celá knihovna pro AVR přibude časem. Zatím mám na svých stránkách pouze jednu konstrukci využívající FAT16 - PCM WAV player. Je to můj skoro první program s FAT16, takže většina funkcí je dost "neohrabaná", ale je snad plně funkční.

A nyní už konečně praktická část, bez které je dokumentace téměř k ničemu - nejké přklady. Použité zapojení je úplně stejné jako zapojení pro experimenty s IDE rozhraním. K popisu tedy jen velmi stručně: HDD nebo CF karta je připojena v 16-bitovém módu k MCU ATmega32 na 16MHz. Do zapojení je přidán LCD s řadičem HD44780 nebo kompatibilním pro zobrazování některých informací. Dále je zde externí SRAM o velikosti 512kB, která se u FAT16 experimentů celkem dost hodí. Ta je připojena přes rozšiřující registry 74HC574 stejně jako některé signály IDE. Pro komunikaci s vhodným terminálem v PC je zde obyčejný převdník MAX232, který umožňuje bezpečný přenos dat rychlostí až 115200bd, což bude pro naše účely plně dostačující.
Napájení musí být dostatečně tvrdé, jinak se disk nerozběhne. Napětí +12V musí zvládnout alespoň 2,5A bez poklesu napětí pod 11V. Na +5V vyhoví proud 1A.

1. ukázkový program - rekurzivní funkce na výpis stromu adreasářů

Původně mělo jít jen o výpis stromu, ale nakonec jsem tento ukázkový program rozšířil tak, že se na terminálu v PC vypíší všechny podstatné údaje o CF/HDD, následně o 1.partition, pak je vypsán zmiňovaný strom a nakonec některé informace z něj vyplývající. Na LCD je zobrazován pouze status programu a chybová hlášení. Komunikace přes COM port je standardně nastavena na 115200bd bez řízení toku, což na většině PC nedělá problémy. Pokud byste chtěli připojit místo MAX232 USB/COM převodník FT232, tak už je HW řízení toku nezbytné! Výsledný TXT soubor pak vypadá takto.
Pro zrychlení je celá FAT překopírována do externí SRAM. Využito je pouze 128kB, takže není třeba připojovat 0,5MB paměť. Pro ukázku jsem vytvořil i podporu LFN názvů, takže je strom celkem přehledný. LFN názvy jsou uloženy v kódování UTF16, takže jsou užitečné znaky převedeny na stravitelnější CP1250. CP1250 bohužel neobsahuje tabulkové znaky, takže je formátování provedeno jen odsazením.
zdroják a překlad do hex