Skip to content

FilmCraft: An open-source, nonlinear video editor written by scratch in pure Rust

16.8 KB
Raw Blame
//! Writing compound files ([MS-CFB] §2.2–2.6).
//!
//! Layout written by [`Writer::finish`] (sector numbers ascending): the sectors of every stream of
//! 4096 bytes or more, the mini stream, the mini FAT, the directory, the FAT, then DIFAT sectors
//! when the FAT needs more than the 109 header slots. Every chain is contiguous. Sibling trees are
//! balanced binary search trees coloured as valid red-black trees (§2.6.4).

use std::collections::HashSet;

use crate::{DIFSECT, ENDOFCHAIN, FATSECT, FREESECT, MINI_SECTOR_SIZE, MINI_STREAM_CUTOFF, NOSTREAM, Result, SIGNATURE, compare_names, validate_name};

/// File format version.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub enum Version {
    /// Version 3: 512-byte sectors.
    V3,
    /// Version 4: 4096-byte sectors (AAF's "4K" files).
    #[default]
    V4,
}

impl Version {
    fn sector_size(self) -> usize {
        match self {
            Version::V3 => 512,
            Version::V4 => 4096,
        }
    }
}

/// A storage or stream added to a [`Writer`].
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct NodeId(pub usize);

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Kind {
    Root,
    Storage,
    Stream,
}

#[derive(Clone, Debug)]
struct Node {
    name: String,
    kind: Kind,
    clsid: [u8; 16],
    data: Vec<u8>,
    children: Vec<usize>,
    /// The children's names, upper-cased as sibling order compares them: an O(1) duplicate check.
    /// (Scanning every sibling with `compare_names`, which allocates, made adding n children O(n^2):
    /// 20 000 AAF markers took a minute.)
    child_keys: HashSet<Vec<u16>>,
}

/// A name as sibling comparison sees it: its UTF-16 code units, upper-cased.
fn name_key(name: &str) -> Vec<u16> {
    name.encode_utf16().map(crate::upper).collect()
}

/// Builds a compound file in memory.
#[derive(Clone, Debug)]
pub struct Writer {
    version: Version,
    nodes: Vec<Node>,
}

impl Default for Writer {
    fn default() -> Self {
        Writer::new(Version::default())
    }
}

impl Writer {
    /// The root storage.
    pub const ROOT: NodeId = NodeId(0);

    pub fn new(version: Version) -> Self {
        Writer {
            version,
            nodes: vec![Node {
                name: "Root Entry".into(),
                kind: Kind::Root,
                clsid: [0; 16],
                data: Vec::new(),
                children: Vec::new(),
                child_keys: HashSet::new(),
            }],
        }
    }

    fn add(&mut self, parent: NodeId, name: &str, kind: Kind, clsid: [u8; 16], data: Vec<u8>) -> Result<NodeId> {
        validate_name(name)?;
        let p = self.nodes.get(parent.0).ok_or_else(|| crate::Error::NotFound(format!("node {}", parent.0)))?;
        if p.kind == Kind::Stream {
            return Err(crate::Error::Invalid(format!("{:?} is a stream, not a storage", p.name)));
        }
        let key = name_key(name);
        if p.child_keys.contains(&key) {
            return Err(crate::Error::BadName(format!("duplicate name {name}")));
        }
        let id = self.nodes.len();
        self.nodes.push(Node { name: name.to_string(), kind, clsid, data, children: Vec::new(), child_keys: HashSet::new() });
        let p = &mut self.nodes[parent.0];
        p.children.push(id);
        p.child_keys.insert(key);
        Ok(NodeId(id))
    }

    /// Add a storage below `parent`.
    pub fn storage(&mut self, parent: NodeId, name: &str, clsid: [u8; 16]) -> Result<NodeId> {
        self.add(parent, name, Kind::Storage, clsid, Vec::new())
    }

    /// Add a stream below `parent`.
    pub fn stream(&mut self, parent: NodeId, name: &str, data: Vec<u8>) -> Result<NodeId> {
        self.add(parent, name, Kind::Stream, [0; 16], data)
    }

    /// Set the class id of a storage (or the root).
    pub fn set_clsid(&mut self, node: NodeId, clsid: [u8; 16]) {
        if let Some(n) = self.nodes.get_mut(node.0) {
            n.clsid = clsid;
        }
    }

    /// Lay the file out and return its bytes.
    pub fn finish(self) -> Vec<u8> {
        let ss = self.version.sector_size();
        let layout = self.layout();
        let fat = layout.fat(ss / 4);
        let minifat = layout.mini_fat(ss / 4);
        let dir = self.directory(&layout);
        let mut out = self.header(&layout);

        // Sectors.
        let pad = |out: &mut Vec<u8>| {
            let r = out.len() % ss;
            if r != 0 {
                out.resize(out.len() + ss - r, 0);
            }
        };
        for &n in &layout.order {
            let node = &self.nodes[n];
            if node.kind == Kind::Stream && node.data.len() as u64 >= MINI_STREAM_CUTOFF as u64 {
                out.extend_from_slice(&node.data);
                pad(&mut out);
            }
        }
        for &n in &layout.order {
            let node = &self.nodes[n];
            if node.kind == Kind::Stream && !node.data.is_empty() && (node.data.len() as u64) < MINI_STREAM_CUTOFF as u64 {
                out.extend_from_slice(&node.data);
                let r = node.data.len() % MINI_SECTOR_SIZE;
                if r != 0 {
                    out.resize(out.len() + MINI_SECTOR_SIZE - r, 0);
                }
            }
        }
        pad(&mut out);
        for v in &minifat {
            out.extend_from_slice(&v.to_le_bytes());
        }
        out.extend_from_slice(&dir);
        for v in &fat {
            out.extend_from_slice(&v.to_le_bytes());
        }
        layout.write_difat(&mut out, ss);
        debug_assert_eq!(out.len(), (layout.total + 1) * ss);
        out
    }

    /// Directory order (depth-first pre-order from the root) and sector placement of every stream.
    fn layout(&self) -> Layout {
        let ss = self.version.sector_size();
        let per_sector = ss / 4;
        let mut order = Vec::with_capacity(self.nodes.len());
        let mut stack = vec![0usize];
        while let Some(n) = stack.pop() {
            order.push(n);
            for &c in self.nodes[n].children.iter().rev() {
                stack.push(c);
            }
        }
        let mut dir_index = vec![0u32; self.nodes.len()];
        for (i, &n) in order.iter().enumerate() {
            dir_index[n] = i as u32;
        }

        // Stream placement.
        let mut start = vec![ENDOFCHAIN; self.nodes.len()];
        let mut next_sector = 0u32;
        let mut big_chains: Vec<(u32, u32)> = Vec::new(); // (first, count)
        for &n in &order {
            let node = &self.nodes[n];
            if node.kind == Kind::Stream && node.data.len() as u64 >= MINI_STREAM_CUTOFF as u64 {
                let count = node.data.len().div_ceil(ss) as u32;
                start[n] = next_sector;
                big_chains.push((next_sector, count));
                next_sector += count;
            }
        }
        let mut next_mini = 0u32;
        let mut mini_chains: Vec<(u32, u32)> = Vec::new();
        for &n in &order {
            let node = &self.nodes[n];
            if node.kind == Kind::Stream && !node.data.is_empty() && (node.data.len() as u64) < MINI_STREAM_CUTOFF as u64 {
                let count = node.data.len().div_ceil(MINI_SECTOR_SIZE) as u32;
                start[n] = next_mini;
                mini_chains.push((next_mini, count));
                next_mini += count;
            }
        }
        let mini_bytes = next_mini as usize * MINI_SECTOR_SIZE;
        let mini_stream_sectors = mini_bytes.div_ceil(ss) as u32;
        let mini_stream_start = if mini_stream_sectors > 0 { next_sector } else { ENDOFCHAIN };
        next_sector += mini_stream_sectors;
        let minifat_sectors = (next_mini as usize * 4).div_ceil(ss) as u32;
        let minifat_start = if minifat_sectors > 0 { next_sector } else { ENDOFCHAIN };
        next_sector += minifat_sectors;
        let dir_sectors = (order.len() * 128).div_ceil(ss) as u32;
        let dir_start = next_sector;
        next_sector += dir_sectors;
        let (fat_n, difat_n) = fat_sector_counts(next_sector as usize, per_sector);
        let fat_start = next_sector;
        let difat_start = fat_start + fat_n as u32;
        Layout {
            order,
            dir_index,
            start,
            big_chains,
            mini_chains,
            mini_bytes,
            mini_stream_sectors,
            mini_stream_start,
            minifat_sectors,
            minifat_start,
            dir_sectors,
            dir_start,
            fat_n,
            difat_n,
            fat_start,
            difat_start,
            total: next_sector as usize + fat_n + difat_n,
        }
    }

    /// The directory sectors: one 128-byte entry per node in directory order, then unused entries.
    fn directory(&self, l: &Layout) -> Vec<u8> {
        let ss = self.version.sector_size();
        let mut tree = vec![(NOSTREAM, NOSTREAM, NOSTREAM, 1u8); self.nodes.len()]; // left, right, child, colour
        for (p, node) in self.nodes.iter().enumerate() {
            if node.kind == Kind::Stream || node.children.is_empty() {
                continue;
            }
            let mut kids = node.children.clone();
            kids.sort_by(|&a, &b| compare_names(&self.nodes[a].name, &self.nodes[b].name));
            let height = usize::BITS - (kids.len() + 1).leading_zeros() - 1; // floor(log2(n + 1))
            let perfect = (1usize << height) - 1 == kids.len();
            let root = build_tree(&kids, 0, perfect, height as usize, &mut tree, &l.dir_index);
            tree[p].2 = root;
        }
        let mut dir = Vec::with_capacity(l.dir_sectors as usize * ss);
        for &n in &l.order {
            dir.extend_from_slice(&self.dir_entry(l, n, tree[n]));
        }
        while dir.len() < l.dir_sectors as usize * ss {
            let mut e = [0u8; 128];
            e[68..80].copy_from_slice(&[0xFF; 12]);
            dir.extend_from_slice(&e);
        }
        dir
    }

    /// The directory entry of node `n`; `links` are its (left, right, child, colour).
    fn dir_entry(&self, l: &Layout, n: usize, links: (u32, u32, u32, u8)) -> [u8; 128] {
        let node = &self.nodes[n];
        let mut e = [0u8; 128];
        let units: Vec<u16> = node.name.encode_utf16().collect();
        for (i, u) in units.iter().enumerate() {
            e[i * 2..i * 2 + 2].copy_from_slice(&u.to_le_bytes());
        }
        e[64..66].copy_from_slice(&(((units.len() + 1) * 2) as u16).to_le_bytes());
        e[66] = match node.kind {
            Kind::Root => 5,
            Kind::Storage => 1,
            Kind::Stream => 2,
        };
        let (left, right, child, colour) = links;
        e[67] = if node.kind == Kind::Root { 1 } else { colour };
        e[68..72].copy_from_slice(&left.to_le_bytes());
        e[72..76].copy_from_slice(&right.to_le_bytes());
        e[76..80].copy_from_slice(&child.to_le_bytes());
        e[80..96].copy_from_slice(&node.clsid);
        let (st, size) = match node.kind {
            Kind::Root => (l.mini_stream_start, l.mini_bytes as u64),
            Kind::Storage => (0, 0),
            Kind::Stream => (if node.data.is_empty() { ENDOFCHAIN } else { l.start[n] }, node.data.len() as u64),
        };
        e[116..120].copy_from_slice(&st.to_le_bytes());
        e[120..128].copy_from_slice(&size.to_le_bytes());
        e
    }

    /// The header sector.
    fn header(&self, l: &Layout) -> Vec<u8> {
        let ss = self.version.sector_size();
        let v3 = self.version == Version::V3;
        let mut out = Vec::with_capacity((l.total + 1) * ss);
        out.extend_from_slice(&SIGNATURE);
        out.extend_from_slice(&[0; 16]);
        out.extend_from_slice(&0x003Eu16.to_le_bytes());
        out.extend_from_slice(&(if v3 { 3u16 } else { 4u16 }).to_le_bytes());
        out.extend_from_slice(&0xFFFEu16.to_le_bytes());
        out.extend_from_slice(&(if v3 { 9u16 } else { 12u16 }).to_le_bytes());
        out.extend_from_slice(&6u16.to_le_bytes());
        out.extend_from_slice(&[0; 6]);
        out.extend_from_slice(&(if v3 { 0 } else { l.dir_sectors }).to_le_bytes());
        out.extend_from_slice(&(l.fat_n as u32).to_le_bytes());
        out.extend_from_slice(&l.dir_start.to_le_bytes());
        out.extend_from_slice(&0u32.to_le_bytes());
        out.extend_from_slice(&MINI_STREAM_CUTOFF.to_le_bytes());
        out.extend_from_slice(&l.minifat_start.to_le_bytes());
        out.extend_from_slice(&l.minifat_sectors.to_le_bytes());
        out.extend_from_slice(&(if l.difat_n > 0 { l.difat_start } else { ENDOFCHAIN }).to_le_bytes());
        out.extend_from_slice(&(l.difat_n as u32).to_le_bytes());
        for i in 0..109 {
            let v = if i < l.fat_n { l.fat_start + i as u32 } else { FREESECT };
            out.extend_from_slice(&v.to_le_bytes());
        }
        out.resize(ss, 0);
        out
    }
}

/// Where everything lands in the file: directory order, stream starts and the sector counts.
struct Layout {
    /// Node indices in directory order.
    order: Vec<usize>,
    /// Directory index of each node.
    dir_index: Vec<u32>,
    /// First (mini) sector of each stream.
    start: Vec<u32>,
    /// (first, count) of each stream held in regular sectors.
    big_chains: Vec<(u32, u32)>,
    /// (first, count) of each stream held in mini sectors.
    mini_chains: Vec<(u32, u32)>,
    mini_bytes: usize,
    mini_stream_sectors: u32,
    mini_stream_start: u32,
    minifat_sectors: u32,
    minifat_start: u32,
    dir_sectors: u32,
    dir_start: u32,
    fat_n: usize,
    difat_n: usize,
    fat_start: u32,
    difat_start: u32,
    /// Sectors after the header.
    total: usize,
}

/// FAT and DIFAT sector counts for `base` other sectors (the FAT must also map itself).
fn fat_sector_counts(base: usize, per_sector: usize) -> (usize, usize) {
    let (mut fat_n, mut difat_n) = (1usize, 0usize);
    loop {
        let total = base + fat_n + difat_n;
        let need_fat = total.div_ceil(per_sector);
        let need_difat = if need_fat > 109 { (need_fat - 109).div_ceil(per_sector - 1) } else { 0 };
        if need_fat == fat_n && need_difat == difat_n {
            return (fat_n, difat_n);
        }
        fat_n = need_fat.max(fat_n);
        difat_n = need_difat.max(difat_n);
    }
}

impl Layout {
    fn fat(&self, per_sector: usize) -> Vec<u32> {
        let mut fat = vec![FREESECT; self.fat_n * per_sector];
        let chain = |first: u32, count: u32, fat: &mut [u32]| {
            for i in 0..count {
                fat[(first + i) as usize] = if i + 1 == count { ENDOFCHAIN } else { first + i + 1 };
            }
        };
        for &(f, c) in &self.big_chains {
            chain(f, c, &mut fat);
        }
        if self.mini_stream_sectors > 0 {
            chain(self.mini_stream_start, self.mini_stream_sectors, &mut fat);
        }
        if self.minifat_sectors > 0 {
            chain(self.minifat_start, self.minifat_sectors, &mut fat);
        }
        chain(self.dir_start, self.dir_sectors, &mut fat);
        for i in 0..self.fat_n {
            fat[self.fat_start as usize + i] = FATSECT;
        }
        for i in 0..self.difat_n {
            fat[self.difat_start as usize + i] = DIFSECT;
        }
        debug_assert!(self.total <= fat.len());
        fat
    }

    fn mini_fat(&self, per_sector: usize) -> Vec<u32> {
        let mut minifat = vec![FREESECT; self.minifat_sectors as usize * per_sector];
        for &(f, c) in &self.mini_chains {
            for i in 0..c {
                minifat[(f + i) as usize] = if i + 1 == c { ENDOFCHAIN } else { f + i + 1 };
            }
        }
        minifat
    }

    /// Append the DIFAT sectors: the FAT sector numbers beyond the header's 109 slots.
    fn write_difat(&self, out: &mut Vec<u8>, ss: usize) {
        let per_sector = ss / 4;
        let mut remaining: Vec<u32> = (109..self.fat_n).map(|i| self.fat_start + i as u32).collect();
        for i in 0..self.difat_n {
            let mut s = Vec::with_capacity(ss);
            let take = remaining.len().min(per_sector - 1);
            for v in remaining.drain(..take) {
                s.extend_from_slice(&v.to_le_bytes());
            }
            while s.len() < ss - 4 {
                s.extend_from_slice(&FREESECT.to_le_bytes());
            }
            let next = if i + 1 < self.difat_n { self.difat_start + i as u32 + 1 } else { ENDOFCHAIN };
            s.extend_from_slice(&next.to_le_bytes());
            out.extend_from_slice(&s);
        }
    }
}

/// Balanced BST of `kids[..]` (sorted). Nodes on the bottom level of an imperfect tree are red,
/// so every root-to-leaf path has the same number of black nodes.
fn build_tree(kids: &[usize], depth: usize, perfect: bool, height: usize, tree: &mut [(u32, u32, u32, u8)], dir_index: &[u32]) -> u32 {
    if kids.is_empty() {
        return NOSTREAM;
    }
    let mid = kids.len() / 2;
    let n = kids[mid];
    let left = build_tree(&kids[..mid], depth + 1, perfect, height, tree, dir_index);
    let right = build_tree(&kids[mid + 1..], depth + 1, perfect, height, tree, dir_index);
    tree[n].0 = left;
    tree[n].1 = right;
    tree[n].3 = if !perfect && depth == height { 0 } else { 1 };
    dir_index[n]
}