1use std::collections::BTreeSet;
6
7use cadkit_core::{ReadOptions, Result, Warning};
8
9use crate::cfb::CompoundFile;
10use crate::cfb_tree::{
11 self, CHILD, ENTRY_LEN, NOSTREAM, OBJECT_TYPE, TreeCheck, directory_entry_offsets,
12};
13use crate::le;
14use crate::native::v8::{self, Page, V8File};
15
16#[derive(Debug, Clone, Default, PartialEq, serde::Serialize, serde::Deserialize)]
33#[serde(default)]
34#[non_exhaustive]
35pub struct StructureReport {
36 pub cfb_version: u16,
38 pub storages: u32,
40 pub red_black_trees: u32,
44 pub top_down_trees: u32,
47 pub irregular_free_entries: u32,
49 pub writer_slot_order: bool,
53 pub pages: u32,
56 pub pages_with_number_or_population: u32,
60 pub model_records_without_time: u32,
63 pub split_dictionary_pages: Vec<u32>,
65 pub warnings: Vec<Warning>,
67}
68
69impl StructureReport {
70 pub fn is_clean(&self) -> bool {
72 self.warnings.is_empty()
73 }
74}
75
76pub fn check_structure(bytes: &[u8], options: &ReadOptions) -> Result<StructureReport> {
86 let native = v8::read(bytes, options)?;
87 let mut report = StructureReport {
88 cfb_version: native.cfb_version,
89 ..StructureReport::default()
90 };
91 let cf = CompoundFile::parse(bytes)?;
92 directory(bytes, &mut report)?;
93 report.writer_slot_order = writer_slot_order(&cf);
94 pages(&native, &mut report);
95 model_counters(&cf, &native, options, &mut report);
96 Ok(report)
97}
98
99fn warn(code: &str, count: u32, what: &str, offset: Option<u64>, object: Option<u64>) -> Warning {
101 let mut w = Warning::new(code, format!("{count} {what}"));
102 w.offset = offset;
103 w.object = object;
104 w
105}
106
107fn directory(bytes: &[u8], report: &mut StructureReport) -> Result<()> {
108 let offsets = directory_entry_offsets(bytes)?;
109 let mut unordered = (0u32, None);
110 let mut unbalanced = (0u32, None);
111 let mut shared = (0u32, None);
112 let mut claimed = BTreeSet::new();
118 let mut todo = Vec::new();
119 if !offsets.is_empty() {
120 claimed.insert(0u32);
121 todo.push(0u32);
122 }
123 while let Some(slot) = todo.pop() {
124 let Some(&off) = offsets.get(slot as usize) else {
125 continue;
126 };
127 let kind = bytes.get(off + OBJECT_TYPE).copied().unwrap_or(0);
128 let child = cfb_tree::u32_le(bytes, off + CHILD).unwrap_or(NOSTREAM);
129 if child == NOSTREAM {
130 continue;
131 }
132 let (slots, overlaps) = cfb_tree::claim_tree_slots(bytes, &offsets, child, &mut claimed);
133 todo.extend(slots.iter().copied());
134 if !matches!(kind, 1 | 5) {
135 continue;
136 }
137 report.storages += 1;
138 let at = Some(off as u64);
139 if overlaps {
140 shared.0 += 1;
141 shared.1 = shared.1.or(at);
142 continue;
143 }
144 match cfb_tree::check_tree(bytes, &offsets, child) {
145 TreeCheck::RedBlack => report.red_black_trees += 1,
146 TreeCheck::Unbalanced => {
147 unbalanced.0 += 1;
148 unbalanced.1 = unbalanced.1.or(at);
149 }
150 TreeCheck::Unordered => {
151 unordered.0 += 1;
152 unordered.1 = unordered.1.or(at);
153 }
154 }
155 if cfb_tree::top_down_shape(bytes, &offsets, &slots)
156 == cfb_tree::stored_shape(bytes, &offsets, child)
157 {
158 report.top_down_trees += 1;
159 }
160 }
161 let mut irregular = None;
162 for (slot, &off) in offsets.iter().enumerate() {
163 if u32::try_from(slot).is_ok_and(|s| claimed.contains(&s)) {
164 continue;
165 }
166 let free = bytes
167 .get(off..off.saturating_add(ENTRY_LEN))
168 .is_some_and(cfb_tree::is_free_entry);
169 if !free {
170 report.irregular_free_entries += 1;
171 irregular = irregular.or(Some(off as u64));
172 }
173 }
174 for (code, (count, at), what) in [
175 (
176 "dgn.cfb_tree_unordered",
177 unordered,
178 "CFB sibling trees are not ordered by name",
179 ),
180 (
181 "dgn.cfb_tree_unbalanced",
182 unbalanced,
183 "CFB sibling trees are ordered but not red-black",
184 ),
185 (
186 "dgn.cfb_tree_shared",
187 shared,
188 "CFB storages share sibling tree entries with an earlier storage",
189 ),
190 (
191 "dgn.cfb_free_entry",
192 (report.irregular_free_entries, irregular),
193 "unused CFB directory slots are not in the free entry form",
194 ),
195 ] {
196 if count > 0 {
197 report.warnings.push(warn(code, count, what, at, None));
198 }
199 }
200 Ok(())
201}
202
203fn writer_slot_order(cf: &CompoundFile<'_>) -> bool {
205 let mut slots: Vec<(usize, &str)> = cf
206 .paths()
207 .iter()
208 .map(|p| (p.index, p.path.as_str()))
209 .collect();
210 slots.sort_unstable();
211 let contiguous = slots.iter().zip(1usize..).all(|((slot, _), n)| *slot == n);
212 contiguous
213 && slots.windows(2).all(|w| match w {
214 [(_, a), (_, b)] => cfb_tree::writer_slot_rank(a) < cfb_tree::writer_slot_rank(b),
215 _ => true,
216 })
217}
218
219fn pages(native: &V8File, report: &mut StructureReport) {
220 let mut all: Vec<&v8::PageHeader> = Vec::new();
221 let mut untimed = (0u32, None);
222 for model in &native.models {
223 all.extend(model.graphic_pages.iter().map(|p| &p.header));
224 all.extend(model.control_pages.iter().map(|p| &p.header));
225 all.extend(model.graphic_aux.iter().map(|p| &p.header));
226 all.extend(model.control_aux.iter().map(|p| &p.header));
227 for raw in model
228 .graphic_pages
229 .iter()
230 .chain(&model.control_pages)
231 .flat_map(|p: &Page| &p.elements)
232 {
233 let timed = le::f64_at(&raw.bytes, 0x18).is_some_and(|t| t.is_finite() && t > 0.0);
234 if !timed {
235 untimed.0 += 1;
236 untimed.1 = untimed.1.or(raw.id());
237 }
238 }
239 }
240 all.extend(native.named_pages.iter().map(|p| &p.header));
241 all.extend(native.named_aux.iter().map(|p| &p.header));
242 report.pages = u32::try_from(all.len()).unwrap_or(u32::MAX);
243 report.pages_with_number_or_population = u32::try_from(
244 all.iter()
245 .filter(|h| h.page_number != 0 || h.population != 0)
246 .count(),
247 )
248 .unwrap_or(u32::MAX);
249 report.model_records_without_time = untimed.0;
250 if untimed.0 > 0 {
251 report.warnings.push(warn(
252 "dgn.record_time",
253 untimed.0,
254 "graphic or control records have no positive finite time at +0x18",
255 None,
256 untimed.1,
257 ));
258 }
259 report.split_dictionary_pages = native
260 .named_pages
261 .iter()
262 .filter(|p| p.elements.first().is_some_and(|e| e.is_complex_component()))
263 .map(|p| p.number)
264 .collect();
265 if let Ok(count @ 1..) = u32::try_from(report.split_dictionary_pages.len()) {
266 report.warnings.push(warn(
267 "dgn.dictionary_page_split",
268 count,
269 "dictionary pages start with a complex component",
270 None,
271 None,
272 ));
273 }
274}
275
276fn model_counters(
278 cf: &CompoundFile<'_>,
279 native: &V8File,
280 options: &ReadOptions,
281 report: &mut StructureReport,
282) {
283 let max = usize::try_from(options.limits.max_decompressed_bytes).unwrap_or(usize::MAX);
284 for model in &native.models {
285 let Some(header) = &model.header else {
286 continue;
287 };
288 let path = format!("Dgn-Md/{}/Dgn~Mh", model.storage);
289 let Some(index) = cf.find(&path) else {
290 continue;
291 };
292 let Ok(raw) = cf.read_stream(index) else {
293 continue;
294 };
295 let inflated = crate::zlib::inflate(&raw, max);
296 let prefix = inflated.data.len().saturating_sub(header.raw.len());
297 let Some(counter) = le::u32_at(&inflated.data, 0).filter(|_| prefix >= 4) else {
298 continue;
299 };
300 let pages = model.graphic_pages.iter().chain(&model.control_pages);
301 let total = pages.clone().count();
302 let filled = pages.filter(|p| p.header.record_count > 0).count();
303 if !(filled..=total).contains(&(counter as usize)) {
304 report.warnings.push(Warning::new(
305 "dgn.model_page_counter",
306 format!(
307 "{path}: first dword {counter} lies outside {filled}..={total} graphic and control pages"
308 ),
309 ));
310 }
311 }
312}
313
314#[cfg(test)]
315mod tests {
316 #![allow(clippy::unwrap_used, clippy::indexing_slicing)]
317 use super::*;
318 use crate::native::v8::tests::{element, model_header_stream, page};
319 use cadkit_core::{Error, Limits};
320
321 fn odd_file() -> Vec<u8> {
326 let line = element(3, &[0u8; 0x68 - 0x0c + 48], &[]);
327 let component = element(0x4000_005f, &[0u8; 0x20], &[]);
328 crate::cfb::tests::build(&[
329 ("Dgn~H", vec![0u8; 64]),
330 (
331 "Dgn-Md/#000000/Dgn~Mh",
332 model_header_stream(true, 1000.0, "M"),
333 ),
334 ("Dgn-Md/#000000/Dgn^G/$1", page(std::slice::from_ref(&line))),
335 ("Dgn^Nm/$1", page(&[component])),
336 ])
337 }
338
339 #[test]
340 fn reports_every_warning_code_on_a_synthetic_file() {
341 let r = check_structure(&odd_file(), &ReadOptions::default()).unwrap();
342 assert_eq!(r.cfb_version, 3);
343 assert_eq!(r.storages, 5);
345 assert_eq!(r.red_black_trees, 0, "red tree roots");
346 assert_eq!(r.irregular_free_entries, 3);
348 assert!(!r.writer_slot_order);
349 assert_eq!((r.pages, r.pages_with_number_or_population), (2, 2));
350 assert_eq!(r.model_records_without_time, 1);
351 assert_eq!(r.split_dictionary_pages, [1]);
352 let codes: Vec<&str> = r.warnings.iter().map(|w| w.code.as_str()).collect();
353 for code in [
354 "dgn.cfb_tree_unbalanced",
355 "dgn.cfb_free_entry",
356 "dgn.record_time",
357 "dgn.dictionary_page_split",
358 "dgn.model_page_counter",
359 ] {
360 assert!(codes.contains(&code), "{code} in {codes:?}");
361 }
362 assert!(!r.is_clean());
363 }
364
365 fn shared_subtree_file(m: u32, n: u32) -> Vec<u8> {
370 const NOS: u32 = u32::MAX;
371 const EOC: u32 = 0xffff_fffe;
372 let entry = |name: &str, kind: u8, right: u32, child: u32, start: u32, size: u64| {
373 let mut e = vec![0u8; 128];
374 let units: Vec<u16> = name.encode_utf16().collect();
375 for (i, u) in units.iter().enumerate() {
376 e[2 * i..2 * i + 2].copy_from_slice(&u.to_le_bytes());
377 }
378 let len = (units.len() as u16 + 1) * 2;
379 e[0x40..0x42].copy_from_slice(&len.to_le_bytes());
380 e[0x42] = kind;
381 e[0x43] = 1;
382 e[0x44..0x48].copy_from_slice(&NOS.to_le_bytes());
383 e[0x48..0x4c].copy_from_slice(&right.to_le_bytes());
384 e[0x4c..0x50].copy_from_slice(&child.to_le_bytes());
385 e[0x74..0x78].copy_from_slice(&start.to_le_bytes());
386 e[0x78..0x80].copy_from_slice(&size.to_le_bytes());
387 e
388 };
389 let subtree = 2 + m;
390 let mut entries = vec![
391 entry("Root Entry", 5, NOS, 1, EOC, 0),
392 entry("Dgn~H", 2, if m > 0 { 2 } else { NOS }, NOS, 0, 4096),
393 ];
394 for i in 0..m {
395 let right = if i + 1 < m { 3 + i } else { NOS };
396 entries.push(entry(&format!("d{i}"), 1, right, subtree, EOC, 0));
397 }
398 for j in 0..n {
399 let right = if j + 1 < n { subtree + 1 + j } else { NOS };
400 entries.push(entry(&format!("s{j}"), 2, right, NOS, EOC, 0));
401 }
402 while entries.len() % 4 != 0 {
403 let mut free = vec![0u8; 128];
405 free[0x44..0x50].fill(0xff);
406 entries.push(free);
407 }
408 let data_sectors = 8u32;
410 let dir_sectors = (entries.len() / 4) as u32;
411 let used = data_sectors + dir_sectors;
412 let mut fat_sectors = 1u32;
413 while fat_sectors * 128 < used + fat_sectors {
414 fat_sectors += 1;
415 }
416 assert!(fat_sectors <= 109);
417 let mut fat: Vec<u32> = Vec::new();
418 for s in 0..data_sectors {
419 fat.push(if s + 1 < data_sectors { s + 1 } else { EOC });
420 }
421 for k in 0..dir_sectors {
422 let s = data_sectors + k;
423 fat.push(if k + 1 < dir_sectors { s + 1 } else { EOC });
424 }
425 fat.extend(std::iter::repeat_n(0xffff_fffd, fat_sectors as usize));
426 fat.resize(fat_sectors as usize * 128, NOS);
427 let mut out = vec![0u8; 512];
428 out[..8].copy_from_slice(&[0xd0, 0xcf, 0x11, 0xe0, 0xa1, 0xb1, 0x1a, 0xe1]);
429 for (at, v) in [
430 (0x18, 0x3eu16),
431 (0x1a, 3),
432 (0x1c, 0xfffe),
433 (0x1e, 9),
434 (0x20, 6),
435 ] {
436 out[at..at + 2].copy_from_slice(&v.to_le_bytes());
437 }
438 for (at, v) in [
439 (0x2c, fat_sectors),
440 (0x30, data_sectors),
441 (0x38, 4096),
442 (0x3c, EOC),
443 (0x44, EOC),
444 ] {
445 out[at..at + 4].copy_from_slice(&v.to_le_bytes());
446 }
447 for i in 0..109u32 {
448 let v = if i < fat_sectors { used + i } else { NOS };
449 let at = 0x4c + 4 * i as usize;
450 out[at..at + 4].copy_from_slice(&v.to_le_bytes());
451 }
452 out.extend(vec![0u8; 4096]);
453 for e in entries {
454 out.extend(e);
455 }
456 for v in fat {
457 out.extend(v.to_le_bytes());
458 }
459 out
460 }
461
462 #[test]
463 fn storages_sharing_a_subtree_are_reported_once_each_without_reanalysis() {
464 let (m, n) = (300u32, 300u32);
465 let file = shared_subtree_file(m, n);
466 let r = check_structure(&file, &ReadOptions::default()).unwrap();
467 assert_eq!(r.storages, m + 1);
471 let count = |code: &str| {
472 r.warnings
473 .iter()
474 .find(|w| w.code == code)
475 .map(|w| w.message.split(' ').next().unwrap().parse::<u32>().unwrap())
476 };
477 assert_eq!(count("dgn.cfb_tree_shared"), Some(m - 1));
478 assert_eq!(count("dgn.cfb_tree_unbalanced"), Some(1));
479 assert_eq!(count("dgn.cfb_tree_unordered"), Some(1));
481 assert_eq!(r.red_black_trees + r.top_down_trees, 0);
482 assert_eq!(r.irregular_free_entries, 0);
483 let single = check_structure(&shared_subtree_file(1, n), &ReadOptions::default()).unwrap();
485 assert!(
486 single
487 .warnings
488 .iter()
489 .all(|w| w.code != "dgn.cfb_tree_shared")
490 );
491 assert_eq!(single.storages, 2);
492 let doc = crate::read(&file, &ReadOptions::default()).unwrap();
494 assert_eq!(
495 doc.props.get("dgn.stream_count"),
496 Some(&cadkit_core::Value::Int(i64::from(n) + 1))
497 );
498 assert!(doc.models.is_empty());
499 assert_eq!(
500 v8::read(&file, &ReadOptions::default())
501 .unwrap()
502 .cfb_version,
503 3
504 );
505 }
506
507 #[test]
508 fn unordered_trees_are_reported_and_bad_input_fails() {
509 let file =
512 crate::cfb::tests::build(&[("Dgn~H", vec![0u8; 64]), ("Zz", vec![1]), ("Aa", vec![2])]);
513 let r = check_structure(&file, &ReadOptions::default()).unwrap();
514 assert!(
515 r.warnings
516 .iter()
517 .any(|w| w.code == "dgn.cfb_tree_unordered" && w.offset.is_some())
518 );
519 assert!(check_structure(b"not a compound file", &ReadOptions::default()).is_err());
520 let not_dgn = crate::cfb::tests::build(&[("WordDocument", vec![0u8; 64])]);
521 assert!(matches!(
522 check_structure(¬_dgn, &ReadOptions::default()),
523 Err(Error::UnknownFormat)
524 ));
525 let tight = ReadOptions::default().with_limits(Limits::default().with_max_input_bytes(64));
526 assert!(matches!(
527 check_structure(&odd_file(), &tight),
528 Err(Error::LimitExceeded { .. })
529 ));
530 let file = odd_file();
532 for cut in (0..file.len()).step_by(97) {
533 let _ = check_structure(&file[..cut], &ReadOptions::default());
534 }
535 for at in (0..file.len()).step_by(61) {
536 let mut flipped = file.clone();
537 flipped[at] ^= 0xa5;
538 let _ = check_structure(&flipped, &ReadOptions::default());
539 }
540 }
541}