collective
Browse / github.com/storytold/pdfcraft / patch
perf(cos): rebuild a damaged cross-reference index without parsing every object
cos: rebuilding the xref of a damaged file is 2.4x slower than needed (parses every object, slow byte search) ## Problem When the cross-reference data is unusable, `Document::reconstruct` (crates/cos/src/document.rs) rebuilds the index from object headers. It is slow on large damaged files: 1. For every object it searches the next 1,024 bytes for `/XRef` with `windows(5).position(..)`, a byte-by-byte compare. 2. It then calls `try_get` on every object to see whether it is an `/ObjStm`, so the whole file is parsed once just for the rebuild. 3. The scan for `trailer` over the whole file uses the same slow `windows(7)` search. ## Numbers Same 28 MB file with `startxref` pointed at a wrong offset (so
- Status
- open
- Score
- 0.00
- Adopters
- 0 other operators
- Author
- vangel76 (imported from pull request #4874, open)
- Base
e9fc890a862ea2d8c895ea32ddecda98580483cd- Size
- +291 −4 in 4 files
- Review
- pending
- Shared
- 2026-10-28
- Id
44729368a6a9159f6287c419
How it went
No other operator has reported using it yet.
Diff
raw · crates/cos/src/document/reader.rs crates/cos/src/document/tests.rs crates/cos/tests/it/main.rs crates/cos/tests/it/reconstruct.rs
@@ -619,10 +619,28 @@ impl Document { // Offsets of objects that may be cross-reference streams: their dictionaries are the // trailers of files that have no `trailer` keyword (§7.5.8). let mut xref_streams = Vec::new();- for (num, offset, generation, body) in object_headers(&data) {+ // Objects whose bytes (the last object of a number wins, as in `entries`) could hold an+ // `/ObjStm` type; the others are not parsed for the object-stream check below.+ let mut candidates: HashSet<u32> = HashSet::new();+ let headers = object_headers(&data);+ // Where `/XRef` occurs in the file, found in one pass.+ let mut xref_marks = Vec::new();+ let mut mark_from = 0;+ while let Some(p) = find(&data, b"/XRef", mark_from, data.len()) {+ xref_marks.push(p);+ mark_from = p + 1;+ }+ for &(num, offset, generation, body) in &headers { entries.insert(num, XrefEntry::InFile { offset, generation }); objstms.push(num);- if find(&data, b"/XRef", body, body.saturating_add(1024)).is_some()+ if may_be_object_stream(&data, body) {+ candidates.insert(num);+ } else {+ candidates.remove(&num);+ }+ // `/XRef` within the 1024 bytes after the header (the first one that is there).+ let first = xref_marks.partition_point(|&p| p < body);+ if xref_marks.get(first).is_some_and(|&p| p + 5 <= body.saturating_add(1024).min(data.len())) && let Ok(at) = usize::try_from(offset) { xref_streams.push(at);@@ -635,7 +653,8 @@ impl Document { self.cache.lock().map_err(|_| CosError::Poisoned)?.clear(); // Objects inside object streams. for num in objstms {- if let Ok(o) = self.try_get(num)+ if candidates.contains(&num)+ && let Ok(o) = self.try_get(num) && let Object::Stream(s) = &*o && s.dict.name(b"Type") == Some(b"ObjStm") && let Ok(stm) = self.objstm(num)@@ -732,6 +751,109 @@ fn shifted_subsection_end(data: &[u8], at: usize) -> Option<u32> { } } +/// Longest dictionary [`may_be_object_stream`] reads before it gives up and says "maybe".+const DICTIONARY_SCAN_LIMIT: usize = 1 << 20;++/// Where the dictionary that starts at `data[from..]` (after `N G obj`) ends, reading it as the+/// parser does: strings, hex strings, comments, names and nested dictionaries. `Some(None)`: the+/// object is not a dictionary, so it is never a stream. `None`: the end is not certain (no end+/// within the limit, a hex string with a bad digit, a `>>` inside an array); the caller must+/// then treat the object as a possible object stream.+fn dictionary_end(data: &[u8], from: usize) -> Option<Option<usize>> {+ let limit = data.len().min(from.saturating_add(DICTIONARY_SCAN_LIMIT));+ let mut i = from;+ while i < limit && (is_whitespace(data[i]) || data[i] == b'%') {+ if data[i] == b'%' {+ while i < limit && !matches!(data[i], b'\n' | b'\r') {+ i += 1;+ }+ } else {+ i += 1;+ }+ }+ if data.get(i..i + 2) != Some(b"<<") {+ return if i < limit { Some(None) } else { None };+ }+ i += 2;+ let (mut dicts, mut arrays) = (1usize, 0usize);+ while i < limit {+ match data[i] {+ b'(' => {+ let mut depth = 1usize;+ i += 1;+ while i < limit && depth > 0 {+ match data[i] {+ b'\\' => i += 1,+ b'(' => depth += 1,+ b')' => depth -= 1,+ _ => {}+ }+ i += 1;+ }+ if depth > 0 {+ return None;+ }+ }+ b'<' if data.get(i + 1) == Some(&b'<') => {+ dicts += 1;+ i += 2;+ }+ b'<' => {+ i += 1;+ while i < limit && data[i] != b'>' {+ if !data[i].is_ascii_hexdigit() && !is_whitespace(data[i]) {+ return None;+ }+ i += 1;+ }+ i += 1;+ }+ b'>' if data.get(i + 1) == Some(&b'>') => {+ if arrays > 0 {+ return None;+ }+ dicts -= 1;+ i += 2;+ if dicts == 0 {+ return Some(Some(i));+ }+ }+ b'%' => {+ while i < limit && !matches!(data[i], b'\n' | b'\r') {+ i += 1;+ }+ }+ b'[' => {+ arrays += 1;+ i += 1;+ }+ b']' => {+ arrays = arrays.saturating_sub(1);+ i += 1;+ }+ _ => i += 1,+ }+ }+ None+}++/// Whether the object whose body starts at `data[from..]` could be an object stream: its+/// dictionary holds `ObjStm`, or a `#` (a name may hide its letters as `#xx`, as in+/// `/Obj#53tm`). Only the dictionary is searched, not the data of a stream. Where the+/// dictionary ends is read by [`dictionary_end`], so text inside a string (an object header, a+/// `stream` keyword) is not taken for syntax; when that is not certain the object counts as a+/// candidate, so a doubtful object is parsed as it always was.+pub(super) fn may_be_object_stream(data: &[u8], from: usize) -> bool {+ match dictionary_end(data, from) {+ Some(None) => false,+ None => true,+ Some(Some(end)) => {+ let dict = &data[from..end];+ dict.contains(&b'#') || find(dict, b"ObjStm", 0, dict.len()).is_some()+ }+ }+}+ /// Every `N G obj` header in `data`, in file order, as (number, offset, generation, position /// after `obj`). fn object_headers(data: &[u8]) -> Vec<(u32, u64, u16, usize)> {@@ -808,7 +930,33 @@ pub(crate) fn find(hay: &[u8], needle: &[u8], from: usize, to: usize) -> Option< if from >= to || needle.is_empty() || to - from < needle.len() { return None; }- hay[from..to].windows(needle.len()).position(|w| w == needle).map(|p| p + from)+ let hay = &hay[from..to];+ // Look for the needle's rarest byte first, a plain byte scan, and compare the rest only there.+ const COMMON: &[u8] = b" etaoinsrhldcumfpgwybvkxjqz";+ let (k, rare) =+ needle.iter().copied().enumerate().max_by_key(|&(_, b)| COMMON.iter().position(|&c| c == b).unwrap_or(COMMON.len())).unwrap_or((0, 0));+ let mut i = k;+ while let Some(p) = hay.get(i..).and_then(|rest| position_of(rest, rare)) {+ let start = i + p - k;+ if hay.get(start..start + needle.len()) == Some(needle) {+ return Some(start + from);+ }+ i += p + 1;+ }+ None+}++/// The first position of `byte` in `hay`. Whole 32-byte blocks are tested without branching, which+/// the compiler turns into vector compares; only a block that holds the byte is searched.+fn position_of(hay: &[u8], byte: u8) -> Option<usize> {+ const BLOCK: usize = 32;+ let (blocks, rest) = hay.as_chunks::<BLOCK>();+ for (i, block) in blocks.iter().enumerate() {+ if block.iter().fold(false, |any, &b| any | (b == byte)) {+ return block.iter().position(|&b| b == byte).map(|p| i * BLOCK + p);+ }+ }+ rest.iter().position(|&b| b == byte).map(|p| blocks.len() * BLOCK + p) } pub(super) fn rfind(hay: &[u8], needle: &[u8], from: usize) -> Option<usize> {@@ -1,3 +1,4 @@+use super::reader::may_be_object_stream; use super::*; #[test]@@ -1187,6 +1188,81 @@ fn a_prev_reference_to_an_object_holding_the_offset_reads_that_offset() { /// cross-reference data, as in #2365), is rebuilt from its object headers. The rebuild used /// to look only for the `trailer` keyword, so /Info and /ID were lost, and a full save after /// editing one Info field dropped every other.+/// Whether parsing `body` as an object gives a stream whose /Type is /ObjStm.+fn parses_as_object_stream(file: &[u8]) -> bool {+ matches!(parse_indirect(file, 0, &|_| None), Ok((_, Object::Stream(s))) if s.dict.name(b"Type") == Some(b"ObjStm"))+}++#[test]+fn the_object_stream_pre_check_never_rejects_what_parses_as_one() {+ // Two inputs from review: header-shaped text, and `>>` + `stream` + newline, inside a+ // string that comes before the /Type.+ for dict in [+ "<< /Note (9 0 obj\n) /Type /ObjStm /N 0 /First 0 >>",+ "<< /Note (>>stream\n) /Type /ObjStm /N 0 /First 0 >>",+ "<< /Note (a (nested\n9 0 obj\nstream) \\) )) /Type /ObjStm >>",+ "<< /Note <3e3e> /Other << /A (>>\nstream\n) >> /Type /ObjStm >>",+ ] {+ let file = format!("1 0 obj\n{dict}\nstream\nxx\nendstream\nendobj\n").into_bytes();+ assert!(parses_as_object_stream(&file), "test input must be an object stream: {dict}");+ assert!(may_be_object_stream(&file, 7), "{dict}");+ }+ // Ordinary streams stay out; their data is never read.+ let plain = b"1 0 obj\n<< /Length 9 >>\nstream\nObjStm # \nendstream\nendobj\n";+ assert!(!may_be_object_stream(plain, 7));+ assert!(!may_be_object_stream(b"1 0 obj\n[ /ObjStm ]\nendobj\n", 7));+ // Unterminated: not certain, so a candidate.+ assert!(may_be_object_stream(b"1 0 obj\n<< /Note (open ", 7));+ // Random dictionaries built from tricky pieces: whatever parses as an object stream is+ // a candidate.+ let pieces: [&str; 22] = [+ "/Type /ObjStm",+ "/Type/ObjStm",+ "/Type /Obj#53tm",+ "/T#79pe /ObjStm",+ "(",+ ")",+ "\\",+ "(>>stream\n)",+ "(9 0 obj\n)",+ "<3e3e>",+ "<",+ ">",+ ">>",+ "<<",+ "[",+ "]",+ "% c\n",+ "% >>\n",+ "/N 0",+ " ",+ "\n",+ "<zz>",+ ];+ let mut seed = 0x2545_F491_4F6C_DD1Du64;+ let mut next = move || {+ seed ^= seed << 13;+ seed ^= seed >> 7;+ seed ^= seed << 17;+ seed+ };+ let mut hits = 0;+ for _ in 0..200_000 {+ let mut dict = String::from("<<");+ for _ in 0..(next() % 9) {+ dict.push_str(pieces[(next() % pieces.len() as u64) as usize]);+ dict.push(' ');+ }+ dict.push_str(if next() % 8 == 0 { "" } else { ">>" });+ let file = format!("1 0 obj\n{dict}\nstream\nxx\nendstream\nendobj\n").into_bytes();+ if parses_as_object_stream(&file) {+ hits += 1;+ assert!(may_be_object_stream(&file, 7), "rejected an object stream: {dict:?}");+ }+ }+ assert!(hits > 1000, "the generator must produce object streams ({hits})");+}+ #[test] fn reconstruction_takes_the_trailer_from_a_cross_reference_stream() { let table = build(@@ -4,5 +4,6 @@ mod bounded_writer; mod corpus; mod encryption; mod proptests;+mod reconstruct; mod shared_streams; mod writer;new file mode 100644@@ -0,0 +1,62 @@+//! Rebuilding the cross-reference index of a damaged file finds the objects inside object+//! streams however the stream's type is written.++use std::sync::Arc;++use pdfcraft_cos::{Document, Object};++/// A file whose `startxref` points nowhere, with three object streams (type written plainly, as+/// `/Obj#53tm`, and after a string that contains the word `stream`), and one ordinary stream+/// whose data mentions `ObjStm` and `#`.+fn damaged() -> Vec<u8> {+ let mut out = b"%PDF-1.5\n".to_vec();+ let mut add = |n: u32, body: &[u8]| {+ out.extend_from_slice(format!("{n} 0 obj\n").as_bytes());+ out.extend_from_slice(body);+ out.extend_from_slice(b"\nendobj\n");+ };+ let objstm = |dict_prefix: &str, members: &[(u32, &str)]| {+ let mut header = String::new();+ let mut body = String::new();+ for (n, text) in members {+ header.push_str(&format!("{n} {} ", body.len()));+ body.push_str(text);+ body.push('\n');+ }+ let mut b =+ format!("<< {dict_prefix} /N {} /First {} /Length {} >>\nstream\n", members.len(), header.len(), header.len() + body.len()).into_bytes();+ b.extend_from_slice(header.as_bytes());+ b.extend_from_slice(body.as_bytes());+ b.extend_from_slice(b"\nendstream");+ b+ };+ add(1, b"<< /Type /Catalog /Pages 2 0 R >>");+ add(2, b"<< /Type /Pages /Kids [] /Count 0 >>");+ add(3, &objstm("/Type /ObjStm", &[(10, "<< /From 3 >>"), (11, "[3]")]));+ add(4, &objstm("/Type /Obj#53tm", &[(12, "<< /From 4 >>")]));+ add(5, &objstm("/Note (a stream) /Type /ObjStm", &[(13, "<< /From 5 >>")]));+ let data = b"/Type /ObjStm # 14 0 << /From 6 >>";+ let mut plain = format!("<< /Length {} >>\nstream\n", data.len()).into_bytes();+ plain.extend_from_slice(data);+ plain.extend_from_slice(b"\nendstream");+ add(6, &plain);+ // Strings before the type that look like an object header, or like the end of the+ // dictionary and the `stream` keyword, and a hex string and a comment.+ add(7, &objstm("/Note (\n99 0 obj\n) /Type /ObjStm", &[(15, "<< /From 7 >>")]));+ add(8, &objstm("/Note (>>stream\n) /Type /ObjStm", &[(16, "<< /From 8 >>")]));+ add(9, &objstm("/Note <3e3e> /Other << /A (a (b) \\) >>\nstream\n) >> % >>\nstream\n\n/Type /ObjStm", &[(17, "<< /From 9 >>")]));+ out.extend_from_slice(b"trailer\n<< /Size 20 /Root 1 0 R >>\nstartxref\n99999999\n%%EOF\n");+ out+}++#[test]+fn objects_in_object_streams_are_found_however_the_type_is_written() {+ let doc = Document::open(Arc::new(damaged())).expect("opens");+ assert!(doc.reconstructed());+ for n in [10, 11, 12, 13, 15, 16, 17] {+ let o = doc.try_get(n).unwrap_or_else(|e| panic!("object {n}: {e}"));+ assert!(matches!(&*o, Object::Dict(_) | Object::Array(_)), "object {n} is {o:?}");+ }+ // The data of an ordinary stream is not an object stream, whatever it says.+ assert!(!doc.object_numbers().contains(&14));+}