Skip to main content

cadkit_dgn/native/
structure.rs

1//! Structural report of a DGN V8 file: the compound file directory and the pages, as far as
2//! a host checks them before handing a file on (see `docs/dgn/FORMAT_NOTES.md`,
3//! "Structural report").
4
5use 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/// Structural facts of a DGN V8 file's container and pages.
17///
18/// The report states what the file holds; it does not claim that any application accepts
19/// the file. Counts that differ between observed writers (the page header's number and
20/// population, the directory slot order) are information, not warnings. Recoverable
21/// problems are listed in [`warnings`](Self::warnings) with stable codes:
22///
23/// | Code | Meaning |
24/// |---|---|
25/// | `dgn.cfb_tree_unordered` | a sibling tree is not ordered by CFB name ([MS-CFB] 2.6.4), reaches a slot twice or points outside the directory: lookups by name can miss entries |
26/// | `dgn.cfb_tree_unbalanced` | a sibling tree is ordered, but its colours are not a red-black tree (MS-CFB permits this, an all-black tree for instance) |
27/// | `dgn.cfb_tree_shared` | a storage's sibling tree reaches entries an earlier storage's tree holds (an entry with two parents, which [MS-CFB] does not allow); the tree is counted in [`storages`](Self::storages) but not analysed |
28/// | `dgn.cfb_free_entry` | a slot the root does not reach is not in the free form of [MS-CFB] 2.6.3 |
29/// | `dgn.record_time` | a graphic or control record has no positive finite time at `+0x18` |
30/// | `dgn.dictionary_page_split` | a `Dgn^Nm` page starts with a complex component |
31/// | `dgn.model_page_counter` | the first dword of a model header stream lies outside [pages holding records, pages] of its graphic and control pages |
32#[derive(Debug, Clone, Default, PartialEq, serde::Serialize, serde::Deserialize)]
33#[serde(default)]
34#[non_exhaustive]
35pub struct StructureReport {
36    /// Compound file major version (3: 512-byte sectors, 4: 4096-byte sectors).
37    pub cfb_version: u16,
38    /// Storages, the root included, whose child (sibling) tree is not empty.
39    pub storages: u32,
40    /// Of [`storages`](Self::storages), the trees that are ordered red-black trees: colours
41    /// 0 or 1, a black tree root, no red node with a red child and the same number of black
42    /// nodes on every path.
43    pub red_black_trees: u32,
44    /// Of [`storages`](Self::storages), the trees whose shape equals top-down 2-3-4
45    /// red-black insertion of the children in slot order, the shape the writer produces.
46    pub top_down_trees: u32,
47    /// Directory slots the root does not reach that are not in the MS-CFB free form.
48    pub irregular_free_entries: u32,
49    /// Whether the reachable entries fill slots 1, 2, ... without a gap in the order the
50    /// writer uses. That order is one seed lineage's; observed files differ, and readers
51    /// find entries through the sibling trees, not by slot.
52    pub writer_slot_order: bool,
53    /// Page streams (`$n`) of every model's graphic, control and auxiliary storages and of
54    /// `Dgn^Nm` / `Dgn^NmA`.
55    pub pages: u32,
56    /// Of [`pages`](Self::pages), those whose header stores a page number or population
57    /// (`+0x08` / `+0x0C`) other than 0. Public files written by other applications store
58    /// both; this is not a defect.
59    pub pages_with_number_or_population: u32,
60    /// Graphic and control records whose time (`f64` at `+0x18`, milliseconds since 1970)
61    /// is not positive and finite.
62    pub model_records_without_time: u32,
63    /// Numbers of the `Dgn^Nm` pages that start with a complex component.
64    pub split_dictionary_pages: Vec<u32>,
65    /// Recoverable problems, see the table above.
66    pub warnings: Vec<Warning>,
67}
68
69impl StructureReport {
70    /// Whether the report holds no warning.
71    pub fn is_clean(&self) -> bool {
72        self.warnings.is_empty()
73    }
74}
75
76/// Reports the structure of a DGN V8 file without changing it.
77///
78/// Reads the compound file directory and every page with the limits of `options`.
79/// Recoverable problems are [`StructureReport::warnings`].
80///
81/// # Errors
82///
83/// `Err` when `bytes` is not a readable DGN V8 compound file or a limit of `options` is
84/// exceeded.
85pub 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
99/// A warning for `count` occurrences of one problem, located at the first one.
100fn 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    // The root and the storages it reaches, each child tree walked once: every slot is
113    // claimed by the first tree that reaches it, and a tree reaching a claimed slot (a
114    // subtree several storages share) is reported, not analysed again, so the work stays
115    // proportional to the directory. A stale storage entry in an unused slot is an
116    // irregular free entry instead.
117    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
203/// Whether the entries below the root occupy slots 1..=n in the writer's order.
204fn 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
276/// Checks the first dword of every model header stream against the model's pages.
277fn 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    /// A file the test container builder lays out: sibling trees as red right-leaning chains
322    /// in insertion order, zeroed slots after the last entry, page headers with number and
323    /// population, records without a time, a dictionary page opening with a component and a
324    /// model header whose first dword (0) undercounts the one graphic page.
325    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        // Root, Dgn-Md, #000000, Dgn^G and Dgn^Nm hold child trees.
344        assert_eq!(r.storages, 5);
345        assert_eq!(r.red_black_trees, 0, "red tree roots");
346        // Nine entries in three 4-slot sectors: three zeroed unused slots.
347        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    /// A version 3 compound file whose root holds `Dgn~H` and `m` storages that all point at
366    /// one subtree of `n` streams (a right-leaning chain of black entries). cadkit's reader
367    /// visits every slot once and accepts it; a checker that analyses the subtree per storage
368    /// does `m` times the work.
369    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            // The MS-CFB 2.6.3 free form: zeros, sibling and child ids NOSTREAM.
404            let mut free = vec![0u8; 128];
405            free[0x44..0x50].fill(0xff);
406            entries.push(free);
407        }
408        // Sectors: 8 for the 4096-byte `Dgn~H`, then the directory, then the FAT.
409        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        // The root and every storage hold a child tree; the shared subtree is analysed for
468        // the first storage that reaches it only (one all-black chain: ordered, not
469        // red-black), and the other m - 1 storages are reported instead of analysed.
470        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        // The root's chain ("Dgn~H" before the shorter "d0") is not in name order.
480        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        // One storage only: nothing is shared, and the tree is analysed as before.
484        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        // The reader visits every slot once: it accepts the file with the n + 1 streams.
493        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        // The builder chains siblings to the right in insertion order: "Zz" before "Aa"
510        // breaks the name order.
511        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(&not_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        // Truncated and bit-flipped input returns without panicking.
531        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}