use cadkit_core::{Error, Result};
use crate::le;
pub const SIGNATURE: [u8; 8] = [0xD0, 0xCF, 0x11, 0xE0, 0xA1, 0xB1, 0x1A, 0xE1];
const HEADER_LEN: usize = 512;
const DIR_ENTRY_LEN: usize = 128;
const MAX_REGSECT: u32 = 0xFFFF_FFFA;
const ENDOFCHAIN: u32 = 0xFFFF_FFFE;
const NOSTREAM: u32 = 0xFFFF_FFFF;
const MAX_TREE_DEPTH: usize = 64;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum EntryKind {
Empty,
Storage,
Stream,
Root,
Other(u8),
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DirEntry {
pub name: String,
pub kind: EntryKind,
pub left: u32,
pub right: u32,
pub child: u32,
pub start: u32,
pub size: u64,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PathEntry {
pub path: String,
pub index: usize,
pub kind: EntryKind,
pub size: u64,
}
#[derive(Debug, Clone)]
pub struct CompoundFile<'a> {
data: &'a [u8],
pub major_version: u16,
sector_size: usize,
mini_sector_size: usize,
mini_cutoff: u64,
fat: Vec<u32>,
mini_fat: Vec<u32>,
mini_stream: Vec<u8>,
entries: Vec<DirEntry>,
paths: Vec<PathEntry>,
}
impl<'a> CompoundFile<'a> {
pub fn parse(data: &'a [u8]) -> Result<Self> {
Self::parse_impl(data, true)
}
fn parse_impl(data: &'a [u8], load_mini: bool) -> Result<Self> {
let header = data.get(..HEADER_LEN).ok_or(Error::Truncated {
offset: 0,
needed: (HEADER_LEN.saturating_sub(data.len())) as u64,
})?;
if header.get(..8) != Some(&SIGNATURE[..]) {
return Err(Error::UnknownFormat);
}
let field = |off: usize| le::u32_at(header, off).unwrap_or(0);
let major_version = le::u16_at(header, 0x1A).unwrap_or(0);
let sector_shift = le::u16_at(header, 0x1E).unwrap_or(0);
let mini_shift = le::u16_at(header, 0x20).unwrap_or(0);
let sector_size = match sector_shift {
9 => 512usize,
12 => 4096,
s => {
return Err(Error::invalid(
0x1E,
format!("unsupported CFB sector shift {s}"),
));
}
};
if mini_shift != 6 {
return Err(Error::invalid(
0x20,
format!("unsupported CFB mini sector shift {mini_shift}"),
));
}
let mini_sector_size = 64usize;
let num_fat = field(0x2C);
let first_dir = field(0x30);
let mini_cutoff = u64::from(field(0x38));
let first_mini_fat = field(0x3C);
let first_difat = field(0x44);
let num_difat = field(0x48);
let max_sectors = data.len() / sector_size;
let mut difat: Vec<u32> = (0..109)
.filter_map(|i| le::u32_at(header, 0x4C + 4 * i))
.collect();
let per_difat = sector_size / 4 - 1;
let mut next = first_difat;
let mut seen = 0usize;
while next <= MAX_REGSECT && seen < (num_difat as usize).min(max_sectors) {
let sec = sector_slice(data, sector_size, next).ok_or_else(|| {
Error::invalid(
sector_offset(sector_size, next),
"DIFAT sector outside the file",
)
})?;
difat.extend((0..per_difat).filter_map(|i| le::u32_at(sec, 4 * i)));
next = le::u32_at(sec, 4 * per_difat).unwrap_or(ENDOFCHAIN);
seen += 1;
}
let num_fat = (num_fat as usize).min(max_sectors).min(difat.len());
let mut fat: Vec<u32> = Vec::with_capacity(num_fat.saturating_mul(sector_size / 4));
for &sid in difat.iter().take(num_fat) {
if sid > MAX_REGSECT {
continue;
}
match sector_slice(data, sector_size, sid) {
Some(sec) => {
fat.extend((0..sector_size / 4).filter_map(|i| le::u32_at(sec, 4 * i)))
}
None => {
return Err(Error::invalid(
sector_offset(sector_size, sid),
"FAT sector outside the file",
));
}
}
}
let mut cf = Self {
data,
major_version,
sector_size,
mini_sector_size,
mini_cutoff,
fat,
mini_fat: Vec::new(),
mini_stream: Vec::new(),
entries: Vec::new(),
paths: Vec::new(),
};
let dir = cf.read_chain(first_dir, None)?;
let entries: Vec<DirEntry> = dir
.as_chunks::<DIR_ENTRY_LEN>()
.0
.iter()
.map(|entry| parse_dir_entry(entry))
.collect();
if entries.first().map(|e| e.kind) != Some(EntryKind::Root) {
return Err(Error::invalid(
sector_offset(sector_size, first_dir),
"CFB directory has no root entry",
));
}
cf.entries = entries;
cf.paths = cf.collect_paths();
if !load_mini {
return Ok(cf);
}
if first_mini_fat <= MAX_REGSECT {
let mf = cf.read_chain(first_mini_fat, None)?;
cf.mini_fat = mf
.as_chunks::<4>()
.0
.iter()
.filter_map(|c| le::u32_at(c, 0))
.collect();
}
if let Some(root) = cf.entries.first().cloned()
&& root.start <= MAX_REGSECT
&& root.size > 0
{
cf.mini_stream = cf.read_chain(root.start, Some(root.size))?;
}
Ok(cf)
}
pub fn entries(&self) -> &[DirEntry] {
&self.entries
}
pub fn paths(&self) -> &[PathEntry] {
&self.paths
}
fn collect_paths(&self) -> Vec<PathEntry> {
let mut out = Vec::new();
if let Some(root) = self.entries.first() {
let mut visited = vec![false; self.entries.len()];
if let Some(v) = visited.first_mut() {
*v = true;
}
self.collect(root.child, "", 0, &mut visited, &mut out);
}
out
}
fn collect(
&self,
start: u32,
prefix: &str,
depth: usize,
visited: &mut [bool],
out: &mut Vec<PathEntry>,
) {
if depth > MAX_TREE_DEPTH {
return;
}
let mut stack: Vec<u32> = Vec::new();
let mut cur = start;
loop {
while let Some(e) = self.entry_once(cur, visited) {
stack.push(cur);
cur = e.left;
}
let Some(id) = stack.pop() else { break };
let Some(e) = self.entries.get(id as usize) else {
break;
};
let path = if prefix.is_empty() {
e.name.clone()
} else {
format!("{prefix}/{}", e.name)
};
out.push(PathEntry {
path: path.clone(),
index: id as usize,
kind: e.kind,
size: e.size,
});
if e.kind == EntryKind::Storage {
self.collect(e.child, &path, depth + 1, visited, out);
}
cur = e.right;
}
}
fn entry_once(&self, id: u32, visited: &mut [bool]) -> Option<&DirEntry> {
if id == NOSTREAM {
return None;
}
let slot = visited.get_mut(id as usize)?;
if *slot {
return None;
}
*slot = true;
self.entries
.get(id as usize)
.filter(|e| e.kind != EntryKind::Empty)
}
pub fn find(&self, path: &str) -> Option<usize> {
let want = path.trim_start_matches('/');
self.paths
.iter()
.find(|p| p.path.eq_ignore_ascii_case(want))
.map(|p| p.index)
}
pub fn read_stream(&self, index: usize) -> Result<Vec<u8>> {
let e = self
.entries
.get(index)
.ok_or_else(|| Error::invalid(0, format!("no CFB directory entry {index}")))?;
if e.kind != EntryKind::Stream {
return Err(Error::invalid(
0,
format!("CFB entry {} is not a stream", e.name),
));
}
if e.size == 0 {
return Ok(Vec::new());
}
if e.size > self.data.len() as u64 {
return Err(Error::invalid(
0,
format!("CFB stream {} is larger than the file", e.name),
));
}
if e.size < self.mini_cutoff {
self.read_mini_chain(e.start, e.size)
} else {
self.read_chain(e.start, Some(e.size))
}
}
fn read_chain(&self, start: u32, size: Option<u64>) -> Result<Vec<u8>> {
let max_sectors = self.data.len() / self.sector_size;
let mut out = Vec::new();
let mut sid = start;
let mut count = 0usize;
while sid <= MAX_REGSECT {
if count >= max_sectors {
return Err(Error::invalid(
sector_offset(self.sector_size, sid),
"CFB sector chain loops",
));
}
let sec = sector_slice(self.data, self.sector_size, sid)
.or_else(|| self.short_final_sector(sid, size, out.len()))
.ok_or_else(|| {
Error::invalid(
sector_offset(self.sector_size, sid),
"CFB sector outside the file",
)
})?;
out.extend_from_slice(sec);
count += 1;
if let Some(s) = size
&& out.len() as u64 >= s
{
break;
}
sid = self.fat.get(sid as usize).copied().unwrap_or(ENDOFCHAIN);
}
finish(out, size)
}
fn short_final_sector(&self, sid: u32, size: Option<u64>, read: usize) -> Option<&'a [u8]> {
let needed = size?.checked_sub(read as u64)?;
let needed = usize::try_from(needed)
.ok()
.filter(|&n| n > 0 && n < self.sector_size)?;
let off = usize::try_from(sector_offset(self.sector_size, sid)).ok()?;
le::bytes(self.data, off, needed)
}
fn read_mini_chain(&self, start: u32, size: u64) -> Result<Vec<u8>> {
let max = self.mini_stream.len() / self.mini_sector_size + 1;
let mut out = Vec::new();
let mut sid = start;
let mut count = 0usize;
while sid <= MAX_REGSECT {
if count >= max {
return Err(Error::invalid(0, "CFB mini sector chain loops"));
}
let off = (sid as usize).saturating_mul(self.mini_sector_size);
let sec = le::bytes(&self.mini_stream, off, self.mini_sector_size)
.ok_or_else(|| Error::invalid(0, "CFB mini sector outside the mini stream"))?;
out.extend_from_slice(sec);
count += 1;
if out.len() as u64 >= size {
break;
}
sid = self
.mini_fat
.get(sid as usize)
.copied()
.unwrap_or(ENDOFCHAIN);
}
finish(out, Some(size))
}
}
fn finish(mut out: Vec<u8>, size: Option<u64>) -> Result<Vec<u8>> {
if let Some(s) = size {
let s = usize::try_from(s).unwrap_or(usize::MAX);
if out.len() < s {
return Err(Error::Truncated {
offset: 0,
needed: (s - out.len()) as u64,
});
}
out.truncate(s);
}
Ok(out)
}
fn sector_offset(sector_size: usize, sid: u32) -> u64 {
(u64::from(sid) + 1).saturating_mul(sector_size as u64)
}
fn sector_slice(data: &[u8], sector_size: usize, sid: u32) -> Option<&[u8]> {
let off = usize::try_from(sector_offset(sector_size, sid)).ok()?;
le::bytes(data, off, sector_size)
}
fn parse_dir_entry(e: &[u8]) -> DirEntry {
let name_len = usize::from(le::u16_at(e, 64).unwrap_or(0)).min(64);
let units: Vec<u16> = e
.get(..name_len.saturating_sub(2))
.unwrap_or(&[])
.as_chunks::<2>()
.0
.iter()
.filter_map(|c| le::u16_at(c, 0))
.collect();
let kind = match le::u8_at(e, 66).unwrap_or(0) {
0 => EntryKind::Empty,
1 => EntryKind::Storage,
2 => EntryKind::Stream,
5 => EntryKind::Root,
k => EntryKind::Other(k),
};
DirEntry {
name: String::from_utf16_lossy(&units),
kind,
left: le::u32_at(e, 68).unwrap_or(NOSTREAM),
right: le::u32_at(e, 72).unwrap_or(NOSTREAM),
child: le::u32_at(e, 76).unwrap_or(NOSTREAM),
start: le::u32_at(e, 116).unwrap_or(ENDOFCHAIN),
size: u64::from(le::u32_at(e, 120).unwrap_or(0)),
}
}
pub fn root_contains(data: &[u8], name: &str) -> bool {
let Ok(cf) = CompoundFile::parse_impl(data, false) else {
return false;
};
let Some(root) = cf.entries.first() else {
return false;
};
let mut visited = vec![false; cf.entries.len()];
let mut stack = vec![root.child];
while let Some(id) = stack.pop() {
let Some(e) = cf.entry_once(id, &mut visited) else {
continue;
};
if e.name.eq_ignore_ascii_case(name) {
return true;
}
stack.push(e.left);
stack.push(e.right);
}
false
}
#[cfg(test)]
pub(crate) mod tests {
use super::*;
pub(crate) fn build(streams: &[(&str, Vec<u8>)]) -> Vec<u8> {
build_with(streams, 4096)
}
pub(crate) fn build_with(streams: &[(&str, Vec<u8>)], cutoff: u32) -> Vec<u8> {
const SS: usize = 512;
struct Node {
name: String,
kind: u8,
children: Vec<usize>,
data: Vec<u8>,
}
let mut nodes = vec![Node {
name: "Root Entry".into(),
kind: 5,
children: vec![],
data: vec![],
}];
for (path, data) in streams {
let mut parent = 0usize;
let parts: Vec<&str> = path.split('/').collect();
for (i, part) in parts.iter().enumerate() {
let last = i + 1 == parts.len();
let found = nodes[parent]
.children
.iter()
.copied()
.find(|&c| nodes[c].name == *part);
parent = match found {
Some(c) => c,
None => {
nodes.push(Node {
name: (*part).into(),
kind: if last { 2 } else { 1 },
children: vec![],
data: if last { data.clone() } else { vec![] },
});
let id = nodes.len() - 1;
nodes[parent].children.push(id);
id
}
};
}
}
let mut sectors: Vec<Vec<u8>> = Vec::new();
let mut fat: Vec<u32> = Vec::new();
let alloc = |data: &[u8], sectors: &mut Vec<Vec<u8>>, fat: &mut Vec<u32>| -> u32 {
if data.is_empty() {
return ENDOFCHAIN;
}
let start = sectors.len() as u32;
let n = data.len().div_ceil(SS);
for i in 0..n {
let mut s = data[i * SS..((i + 1) * SS).min(data.len())].to_vec();
s.resize(SS, 0);
sectors.push(s);
fat.push(if i + 1 == n {
ENDOFCHAIN
} else {
start + i as u32 + 1
});
}
start
};
sectors.push(vec![0; SS]);
fat.push(0xFFFF_FFFD);
let mut mini = Vec::new();
let mut minifat: Vec<u32> = Vec::new();
let mut starts = vec![(ENDOFCHAIN, 0u64); nodes.len()];
for (i, n) in nodes.iter().enumerate() {
if n.kind == 2 && !n.data.is_empty() && (n.data.len() as u32) < cutoff {
let start = (mini.len() / 64) as u32;
let k = n.data.len().div_ceil(64);
for j in 0..k {
minifat.push(if j + 1 == k {
ENDOFCHAIN
} else {
start + j as u32 + 1
});
}
mini.extend_from_slice(&n.data);
mini.resize(mini.len().div_ceil(64) * 64, 0);
starts[i] = (start, n.data.len() as u64);
}
}
let mut mf_bytes = Vec::new();
for v in &minifat {
mf_bytes.extend_from_slice(&v.to_le_bytes());
}
let minifat_start = alloc(&mf_bytes, &mut sectors, &mut fat);
let mini_start = alloc(&mini, &mut sectors, &mut fat);
starts[0] = (mini_start, mini.len() as u64);
for (i, n) in nodes.iter().enumerate() {
if n.kind == 2 && n.data.len() as u32 >= cutoff {
let s = alloc(&n.data, &mut sectors, &mut fat);
starts[i] = (s, n.data.len() as u64);
}
}
let mut dir = Vec::new();
for (i, n) in nodes.iter().enumerate() {
let mut e = vec![0u8; 128];
let units: Vec<u16> = n.name.encode_utf16().collect();
for (j, u) in units.iter().enumerate() {
e[j * 2..j * 2 + 2].copy_from_slice(&u.to_le_bytes());
}
e[64..66].copy_from_slice(&((units.len() as u16 + 1) * 2).to_le_bytes());
e[66] = n.kind;
let parent = nodes.iter().position(|p| p.children.contains(&i));
let right = parent
.and_then(|p| {
let sib = &nodes[p].children;
let pos = sib.iter().position(|&c| c == i)?;
sib.get(pos + 1).copied()
})
.map(|r| r as u32)
.unwrap_or(NOSTREAM);
e[68..72].copy_from_slice(&NOSTREAM.to_le_bytes());
e[72..76].copy_from_slice(&right.to_le_bytes());
let child = n.children.first().map(|&c| c as u32).unwrap_or(NOSTREAM);
e[76..80].copy_from_slice(&child.to_le_bytes());
e[116..120].copy_from_slice(&starts[i].0.to_le_bytes());
e[120..124].copy_from_slice(&(starts[i].1 as u32).to_le_bytes());
dir.extend_from_slice(&e);
}
let dir_start = alloc(&dir, &mut sectors, &mut fat);
const PER_FAT: usize = SS / 4;
let mut fat_sectors = vec![0u32];
while fat_sectors.len() * PER_FAT < fat.len() {
fat_sectors.push(sectors.len() as u32);
sectors.push(vec![0; SS]);
fat.push(0xFFFF_FFFD);
}
assert!(
fat_sectors.len() <= 109,
"test builder supports header DIFAT only"
);
fat.resize(fat_sectors.len() * PER_FAT, NOSTREAM);
for (k, &sec) in fat_sectors.iter().enumerate() {
let mut fat_sec = vec![0u8; SS];
for (i, v) in fat[k * PER_FAT..(k + 1) * PER_FAT].iter().enumerate() {
fat_sec[i * 4..i * 4 + 4].copy_from_slice(&v.to_le_bytes());
}
sectors[sec as usize] = fat_sec;
}
let mut h = vec![0u8; 512];
h[..8].copy_from_slice(&SIGNATURE);
h[0x18..0x1A].copy_from_slice(&0x3Eu16.to_le_bytes());
h[0x1A..0x1C].copy_from_slice(&3u16.to_le_bytes());
h[0x1C..0x1E].copy_from_slice(&0xFFFEu16.to_le_bytes());
h[0x1E..0x20].copy_from_slice(&9u16.to_le_bytes());
h[0x20..0x22].copy_from_slice(&6u16.to_le_bytes());
h[0x2C..0x30].copy_from_slice(&(fat_sectors.len() as u32).to_le_bytes());
h[0x30..0x34].copy_from_slice(&dir_start.to_le_bytes());
h[0x38..0x3C].copy_from_slice(&cutoff.to_le_bytes());
h[0x3C..0x40].copy_from_slice(&minifat_start.to_le_bytes());
h[0x40..0x44].copy_from_slice(&((mf_bytes.len().div_ceil(SS)) as u32).to_le_bytes());
h[0x44..0x48].copy_from_slice(&ENDOFCHAIN.to_le_bytes());
for i in 0..109 {
let v: u32 = fat_sectors.get(i).copied().unwrap_or(NOSTREAM);
h[0x4C + i * 4..0x50 + i * 4].copy_from_slice(&v.to_le_bytes());
}
let mut out = h;
for s in sectors {
out.extend_from_slice(&s);
}
out
}
#[test]
fn reads_mini_and_regular_streams() {
let big: Vec<u8> = (0..10_000u32).map(|i| (i % 251) as u8).collect();
let file = build(&[
("A/small", b"hello".to_vec()),
("A/B/big", big.clone()),
("top", vec![1, 2, 3]),
]);
let cf = CompoundFile::parse(&file).unwrap();
let paths: Vec<String> = cf.paths().iter().map(|p| p.path.clone()).collect();
assert!(paths.contains(&"A/small".to_string()));
assert!(paths.contains(&"A/B/big".to_string()));
let small = cf.find("/A/small").unwrap();
assert_eq!(cf.read_stream(small).unwrap(), b"hello");
assert_eq!(cf.read_stream(cf.find("a/b/BIG").unwrap()).unwrap(), big);
assert!(root_contains(&file, "top"));
assert!(root_contains(&file, "A"));
assert!(!root_contains(&file, "small"));
}
#[test]
fn reads_stream_whose_final_sector_is_cut_short() {
let data: Vec<u8> = (0..5000u32).map(|i| (i % 253) as u8).collect();
let mut file = build(&[("s", data.clone())]);
let cf = CompoundFile::parse(&file).unwrap();
let start = cf.entries()[cf.find("s").unwrap()].start as usize;
let count = data.len().div_ceil(512);
let (prev, last) = (start + count - 2, start + count - 1);
let moved = (file.len() - 512) / 512;
let used = data.len() - (count - 1) * 512;
let tail = file[(last + 1) * 512..(last + 1) * 512 + used].to_vec();
let fat = |sid: usize| 512 + sid * 4;
file[fat(prev)..fat(prev) + 4].copy_from_slice(&(moved as u32).to_le_bytes());
file[fat(last)..fat(last) + 4].copy_from_slice(&NOSTREAM.to_le_bytes());
file[fat(moved)..fat(moved) + 4].copy_from_slice(&ENDOFCHAIN.to_le_bytes());
file.extend_from_slice(&tail);
assert_ne!(file.len() % 512, 0);
let cf = CompoundFile::parse(&file).unwrap();
assert_eq!(cf.read_stream(cf.find("s").unwrap()).unwrap(), data);
file.pop();
let cf = CompoundFile::parse(&file).unwrap();
assert!(cf.read_stream(cf.find("s").unwrap()).is_err());
}
#[test]
fn rejects_non_cfb_and_survives_corruption() {
assert!(CompoundFile::parse(b"not a compound file").is_err());
assert!(!root_contains(&[0u8; 600], "x"));
let file = build(&[("s", vec![9u8; 5000])]);
for cut in [0, 100, 512, 700, 1024, file.len() - 1] {
let _ = CompoundFile::parse(&file[..cut]).map(|cf| {
for p in cf.paths() {
let _ = cf.read_stream(p.index);
}
});
}
let mut looped = file.clone();
let fat_off = 512;
for i in 1..20 {
looped[fat_off + i * 4..fat_off + i * 4 + 4].copy_from_slice(&(i as u32).to_le_bytes());
}
if let Ok(cf) = CompoundFile::parse(&looped) {
for p in cf.paths() {
let _ = cf.read_stream(p.index);
}
}
}
}