fstool 0.4.15

//! Content-fit size estimator for FAT32.
//!
//! [`FatSizePlan`] accumulates the exact cluster allocation `Fat32::format` +
//! the populate path will use for a source tree, then searches against
//! `Fat32::geometry` to return the smallest FAT32 image that holds it.
//! Used by `fstool create -t fat32 <dir>` so the output is sized to the
//! content instead of requiring an explicit `--size`.
//!
//! The model is exact up to FAT32's own rounding:
//!
//! - **Data clusters** = `Σ ceil(file_len / cluster) + Σ dir_clusters`, where a
//!   directory holds `2` slots (`.`/`..`; root holds `1` for its volume label)
//!   plus `1 + lfn_slots(name)` per child and `1` end-marker slot, each slot 32
//!   bytes, rounded up to whole clusters (min one cluster per directory).
//! - **Cluster size** depends on the volume size, which depends on the cluster
//!   count — resolved by the same fixed-point as `geometry`.
//! - **Total** = `reserved (32) + 2 · fat_size + data_clusters · spc` sectors,
//!   floored at FAT32's `MIN_FAT32_CLUSTERS` (~33 MiB).

use std::collections::HashMap;

use super::dir::{ENTRY_SIZE, LFN_CHARS_PER_ENTRY, is_valid_83};
use super::{Fat32, MIN_FAT32_CLUSTERS, SECTOR};
use crate::fs::{FsSizePlan, split_parent_name};

/// FAT32 reserved-sector count (boot + FSInfo + backups) — matches
/// `Fat32::geometry`.
const RESERVED_SECTORS: u32 = 32;
/// Number of FAT copies — matches `Fat32::geometry`.
const NUM_FATS: u32 = 2;
/// 32-bit FAT entries per 512-byte sector.
const ENTRIES_PER_FAT_SECTOR: u32 = SECTOR / 4;

/// Number of 32-byte directory slots a child named `name` consumes: one short
/// (8.3) entry plus a long-name run when the name isn't a valid 8.3 name.
fn slots_for_name(name: &str) -> u64 {
    let lfn = if is_valid_83(name) {
        0
    } else {
        let units = name.encode_utf16().count();
        units.div_ceil(LFN_CHARS_PER_ENTRY) as u64
    };
    1 + lfn
}

/// Accumulator implementing [`FsSizePlan`] for FAT32.
#[derive(Debug, Default)]
pub struct FatSizePlan {
    /// Regular-file (and symlink-as-file) byte lengths — kept individually so
    /// per-file cluster rounding can be recomputed at the chosen cluster size.
    file_lens: Vec<u64>,
    /// Directory path → number of 32-byte slots used (entries + end marker).
    dir_slots: HashMap<String, u64>,
}

impl FatSizePlan {
    /// A fresh plan with just the root directory (seeded with its volume-label
    /// slot plus an end marker).
    #[must_use]
    pub fn new() -> Self {
        let mut dir_slots = HashMap::new();
        // Root has no `.`/`..`, but the writer stores a volume-label entry.
        dir_slots.insert("/".to_string(), 1u64);
        Self {
            file_lens: Vec::new(),
            dir_slots,
        }
    }

    /// Add one directory-entry slot run to `path`'s parent directory.
    fn charge_parent(&mut self, path: &str) {
        let (parent, name) = split_parent_name(path);
        *self.dir_slots.entry(parent.to_string()).or_insert(0) += slots_for_name(name);
    }

    /// Total clusters the content needs at sectors-per-cluster `spc`.
    fn clusters_at(&self, spc: u64) -> u64 {
        let cluster_bytes = spc * u64::from(SECTOR);
        let mut clusters = 0u64;
        for &len in &self.file_lens {
            clusters += len.div_ceil(cluster_bytes); // empty file → 0 clusters
        }
        for &slots in self.dir_slots.values() {
            // +1 slot for the trailing end-of-directory marker; at least one
            // cluster per directory.
            let bytes = (slots + 1) * ENTRY_SIZE as u64;
            clusters += bytes.div_ceil(cluster_bytes).max(1);
        }
        clusters
    }
}

impl FsSizePlan for FatSizePlan {
    fn add_dir(&mut self, path: &str) {
        self.charge_parent(path);
        // The directory itself starts with `.` and `..`.
        self.dir_slots.entry(path.to_string()).or_insert(2);
    }

    fn add_file(&mut self, path: &str, len: u64) {
        self.charge_parent(path);
        self.file_lens.push(len);
    }

    fn add_symlink(&mut self, path: &str, target: &str) {
        // FAT has no symlinks; the populate path stores the target as a small
        // file's contents at most. Charge a parent slot + the target bytes so
        // the image always fits whether the writer stores or skips it.
        self.charge_parent(path);
        self.file_lens.push(target.len() as u64);
    }

    fn add_device(&mut self, path: &str) {
        // No data clusters, but the directory entry still costs a slot.
        self.charge_parent(path);
    }

    fn total_size(&self) -> u64 {
        // Start from a closed-form lower bound, then grow the total until the
        // authoritative `Fat32::geometry` yields enough usable clusters. Using
        // the real geometry (rather than re-deriving it) guarantees the size we
        // return is one the formatter accepts — its FAT-size feedback loop
        // reserves slightly more than a naive inverse would.
        let spc0 = 1u64;
        let need0 = self.clusters_at(spc0).max(u64::from(MIN_FAT32_CLUSTERS));
        let fat0 = (need0 + 2).div_ceil(u64::from(ENTRIES_PER_FAT_SECTOR));
        let mut total = u64::from(RESERVED_SECTORS) + u64::from(NUM_FATS) * fat0 + need0 * spc0;

        for _ in 0..64 {
            let ts = u32::try_from(total).unwrap_or(u32::MAX);
            match Fat32::geometry(ts) {
                Ok((g_spc, _fat, avail)) => {
                    let g_spc = u64::from(g_spc);
                    let need = self.clusters_at(g_spc).max(u64::from(MIN_FAT32_CLUSTERS));
                    if u64::from(avail) >= need {
                        return total * u64::from(SECTOR);
                    }
                    // Grow by the cluster deficit (plus one, so FAT-size growth
                    // can't stall the loop on a boundary).
                    total += (need - u64::from(avail)) * g_spc + 1;
                }
                Err(_) => {
                    // Below the FAT32 minimum: jump to a floor that geometry
                    // will accept, then let the loop refine.
                    let floor = u64::from(RESERVED_SECTORS)
                        + u64::from(NUM_FATS) * 520
                        + u64::from(MIN_FAT32_CLUSTERS);
                    total = total.max(floor) + 1;
                }
            }
        }
        total * u64::from(SECTOR)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn empty_tree_is_fat32_minimum() {
        let plan = FatSizePlan::new();
        let size = plan.total_size();
        // Floor: MIN_FAT32_CLUSTERS data clusters at spc=1 + metadata, ~33 MiB.
        assert!(size >= u64::from(MIN_FAT32_CLUSTERS) * 512);
        assert!(
            size < 40 * 1024 * 1024,
            "empty FAT32 should be ~33 MiB, got {size}"
        );
    }

    #[test]
    fn slots_for_name_short_vs_long() {
        assert_eq!(slots_for_name("README"), 1); // valid 8.3 → no LFN
        assert_eq!(slots_for_name("KERNEL.IMG"), 1);
        // 20-char name → 1 short + ceil(20/13)=2 LFN slots.
        assert_eq!(slots_for_name("a-twenty-char-name!!"), 3);
    }

    #[test]
    fn large_content_exceeds_floor_and_grows_monotonically() {
        let mut small = FatSizePlan::new();
        for i in 0..10 {
            small.add_file(&format!("/f{i}.bin"), 1024);
        }
        let mut big = FatSizePlan::new();
        for i in 0..10 {
            big.add_file(&format!("/f{i}.bin"), 4 * 1024 * 1024 * 1024);
        }
        assert!(big.total_size() > small.total_size());
        // 40 GiB of content forces a larger sectors-per-cluster than 1.
        assert!(big.total_size() > 40u64 * 1024 * 1024 * 1024);
    }

    #[test]
    fn estimated_size_actually_fits_and_reads_back() {
        // End-to-end: size a real tree, format at exactly that size, populate,
        // and read a file back — proving the estimate is sufficient (the build
        // never runs out of space) without needing `fsck.vfat` in CI.
        use crate::block::MemoryBackend;
        use crate::fs::fat::{Fat32, FatFormatOpts};
        use crate::repack::{Source, populate_fat32_from_source};

        let dir = tempfile::tempdir().unwrap();
        std::fs::create_dir(dir.path().join("sub")).unwrap();
        for i in 0..30 {
            std::fs::write(
                dir.path().join(format!("sub/file_{i}.txt")),
                format!("contents of file {i}\n"),
            )
            .unwrap();
        }
        std::fs::write(dir.path().join("big.bin"), vec![7u8; 200_000]).unwrap();

        let src = Source::HostDir(dir.path().to_path_buf());
        let bytes = crate::analyze::size_for_source(&src, "fat32")
            .unwrap()
            .unwrap();

        let mut dev = MemoryBackend::new(bytes);
        let opts = FatFormatOpts {
            total_sectors: (bytes / 512) as u32,
            volume_id: 0,
            volume_label: *b"NO NAME    ",
        };
        let mut fat = Fat32::format(&mut dev, &opts).unwrap();
        populate_fat32_from_source(&mut dev, &mut fat, &src).expect("populate must fit");
        fat.flush(&mut dev).unwrap();

        let fat = Fat32::open(&mut dev).unwrap();
        let mut out = Vec::new();
        let mut r = fat.open_file_reader(&mut dev, "/sub/file_3.txt").unwrap();
        std::io::Read::read_to_end(&mut r, &mut out).unwrap();
        assert_eq!(out, b"contents of file 3\n");
    }

    #[test]
    fn directories_charge_their_parent() {
        let mut plan = FatSizePlan::new();
        plan.add_dir("/sub");
        plan.add_file("/sub/a.txt", 10);
        // /sub exists with its own slots, root charged for the /sub entry.
        assert!(plan.dir_slots.contains_key("/sub"));
        assert!(plan.dir_slots["/"] > 1); // volume label + /sub
    }
}