Implement FAT12 Filesystem Reader: Parse Boot Sector and FAT

Topic Overview

FAT12 Boot Sector Layout

FAT12 is the classic DOS floppy format: boot sector, FAT tables, root directory, then data region. The BIOS loads the boot sector; your reader parses BPB fields to locate FAT and root dir.

On-Disk Geometry

From boot sector:

• Bytes per sector: usually 512
• Sectors per cluster
• Reserved sectors, FAT count, root entry count

For example, a 1.44 MB floppy has 224 root directory slots and 9 sectors per FAT copy.

Why This Matters in Production

FAT12 is the exact filesystem GRUB's stage-1 bootloader and real 1.44MB floppy images use, and its FAT-chain design is the direct ancestor of the FAT32 still mandated for every UEFI system partition today. Get the 12-bit packing math wrong (two entries jammed into three bytes) and you silently follow a corrupted cluster chain into someone else's file data.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will parse the BPB, walk the FAT chain, and read a root directory entry. This exercise requires converting 8.3 filenames to a readable string and following 0xFFF end-of-chain markers.

Your Task

Read a FAT12 disk image, the filesystem of floppy disks and the ancestor of the FAT32 used by every UEFI system partition. Parse the boot sector's BIOS Parameter Block, locate the FAT, the root directory and the data area, list the files, and read a file by following its cluster chain. FAT12 packs two 12-bit entries into three bytes, and getting that unpacking right is the heart of the task.

Input

The image as a sparse hex dump: lines OFFSET: b0 b1 ... b15 (offset in hex; 16 bytes per line). Lines that would be all zero are omitted, so every missing byte is 0. The dump ends with a line end. Commands follow, one per line:

cCopy
Loading…

Format

Boot sector (little-endian): OEM name at 3 (8 bytes), bytes/sector at 11 (u16), sectors/cluster at 13 (u8), reserved sectors at 14 (u16), number of FATs at 16 (u8), root entries at 17 (u16), total sectors at 19 (u16), sectors per FAT at 22 (u16), volume label at 43 (11 bytes), filesystem type at 54 (8 bytes).

• The FAT starts at sector reserved. The root directory starts after all FAT copies and holds root entries × 32 bytes. The data area follows it, and cluster n (from 2) begins at the data area plus (n − 2) × sectors/cluster sectors.
• FAT12 entry n: take the 16-bit little-endian word at byte ⌊3n/2⌋ of the FAT. If n is even, the entry is its low 12 bits, otherwise its high 12 bits. 0 means free, 0xFF7 bad, and ≥ 0xFF8 end of chain.
• Directory entry (32 bytes): name at 0 (8 bytes, space-padded), extension at 8 (3), attributes at 11, first cluster at 26 (u16), size at 28 (u32). A first byte of 0x00 ends the directory and 0xE5 marks a deleted entry. Skip entries with the volume-label bit (0x08) or long-name attributes (0x0F). Bit 0x10 marks a directory.
• The data-area cluster count is (total sectors × bytes/sector − data start in bytes) / (bytes/sector × sectors/cluster), rounded down.

Names are BASE.EXT with padding removed, or just BASE when the extension is empty.

Output

cCopy
Loading…

• ls prints one line per live entry, in directory order, with the name left-aligned in 12 columns: NAME SIZE bytes, cluster C, or NAME <DIR> cluster C for a directory. It ends with N entries.
• chain NAME: 5 -> 2 -> 9 -> EOF. A broken chain ends with the reason instead of EOF: free cluster in chain, bad cluster in chain, loop in chain (the next cluster is already in the chain), or cluster out of range.
• cat NAME: "..." prints exactly size bytes, escaping newline as \n, " and \ with a backslash, and other non-printable bytes as \xHH. A broken chain prints cat NAME: REASON.
• chain/cat of a missing (or deleted) file prints COMMAND NAME: not found.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Load the dump into a byte array, then decode every field from it with little-endian helpers (u16, u32) and a fat_entry(n) function.
2. cat must follow the chain and stop after size bytes, not read clusters in numeric order.

Hidden tests cover a fragmented file whose clusters are out of order (and entries at odd cluster numbers), a deleted entry, a subdirectory entry, a chain that hits a free cluster, and a chain that loops.