use crate::tokenizer::{is_delimiter, is_ws};
use crate::{Error, Result};
#[derive(Debug, Clone)]
struct ObjStmMember {
num: u32,
body_start: usize,
}
#[derive(Debug, Clone)]
enum ObjectBody {
Plain {
stream_len: Option<usize>,
length_holder: Option<u32>,
ignore_newline: bool,
},
ObjStm {
type_line_end: usize,
first_marker_start: usize,
endstream_kw: usize,
members: Vec<ObjStmMember>,
extends: Option<Vec<u8>>,
},
XRefStream {
type_line_end: usize,
content_start: usize,
},
}
#[derive(Debug, Clone)]
struct ObjectSpan {
num: u32,
gen: u32,
obj_line_start: usize,
end: usize,
body: ObjectBody,
}
fn find_next_obj(input: &[u8], from: usize) -> Option<(u32, u32, usize, usize)> {
let mut line_start = from;
while line_start < input.len() {
let line_end = memchr_nl(input, line_start).unwrap_or(input.len());
let line = &input[line_start..line_end];
if let Some((num, gen, kw_end)) = parse_obj_header(line) {
return Some((num, gen, line_start, line_start + kw_end));
}
if is_xref_keyword_line(input, line_start) {
return None;
}
line_start = line_end + 1;
if line_end >= input.len() {
break;
}
}
None
}
fn is_xref_keyword_line(input: &[u8], line_start: usize) -> bool {
input[line_start..].starts_with(b"xref\n")
}
fn memchr_nl(buf: &[u8], from: usize) -> Option<usize> {
buf[from..]
.iter()
.position(|&b| b == b'\n')
.map(|i| from + i)
}
fn parse_obj_header(line: &[u8]) -> Option<(u32, u32, usize)> {
let line = if line.last() == Some(&b'\r') {
&line[..line.len() - 1]
} else {
line
};
let s = std::str::from_utf8(line).ok()?;
let mut it = s.split_ascii_whitespace();
let num: u32 = it.next()?.parse().ok()?;
let gen: u32 = it.next()?.parse().ok()?;
if gen != 0 {
return None;
}
if it.next()? != "obj" {
return None;
}
if it.next().is_some() {
return None;
}
let kw_end = s.rfind("obj")? + 3;
Some((num, gen, kw_end))
}
fn find_name_token(hay: &[u8], name: &[u8]) -> Option<usize> {
find_name_token_from(hay, name, 0)
}
fn find_name_token_from(hay: &[u8], name: &[u8], from: usize) -> Option<usize> {
let mut i = from;
while i < hay.len() {
match hay[i] {
b'%' => {
while i < hay.len() && hay[i] != b'\n' && hay[i] != b'\r' {
i += 1;
}
}
b'<' if hay.get(i + 1) == Some(&b'<') => i += 2,
b'>' if hay.get(i + 1) == Some(&b'>') => i += 2,
b'<' => {
i += 1;
while i < hay.len() && hay[i] != b'>' {
i += 1;
}
i += 1;
}
b'(' => {
i += 1;
let mut depth = 1usize;
while i < hay.len() && depth > 0 {
match hay[i] {
b'\\' => i += 1, b'(' => depth += 1,
b')' => depth -= 1,
_ => {}
}
i += 1;
}
}
b'/' if hay[i..].starts_with(name) => {
let after = hay.get(i + name.len());
if after.is_none_or(|&b| is_ws(b) || is_delimiter(b)) {
return Some(i);
}
i += 1; }
_ => i += 1,
}
}
None
}
enum LengthKind {
Indirect(u32),
IndirectUnsupportedGeneration,
Direct,
None,
}
fn classify_length(dict: &[u8]) -> LengthKind {
let needle = b"/Length";
let Some(p) = find_name_token(dict, needle) else {
return LengthKind::None;
};
let rest = &dict[p + needle.len()..];
let s = match std::str::from_utf8(rest) {
Ok(s) => s,
Err(_) => return LengthKind::None,
};
let mut it = s.split_ascii_whitespace();
let Some(first) = it.next() else {
return LengthKind::None;
};
if first.parse::<u32>().is_err() {
return LengthKind::None;
}
let second = it.next();
let third = it.next();
if let (Some(g), Some(r)) = (second, third) {
if let (Ok(gen), "R") = (g.parse::<u32>(), r) {
return if gen == 0 {
LengthKind::Indirect(first.parse().unwrap())
} else {
LengthKind::IndirectUnsupportedGeneration
};
}
}
LengthKind::Direct
}
fn find_subslice(hay: &[u8], needle: &[u8]) -> Option<usize> {
if needle.is_empty() || hay.len() < needle.len() {
return None;
}
hay.windows(needle.len()).position(|w| w == needle)
}
fn has_ignore_newline_marker(separator: &[u8]) -> bool {
separator
.split_inclusive(|&b| b == b'\n')
.any(|line| line == b"%QDF: ignore_newline\n")
}
fn find_raw_type_line(dict: &[u8], needle: &[u8]) -> Option<usize> {
let mut line_start = 0;
while line_start < dict.len() {
let line_end = memchr_nl(dict, line_start)
.map(|p| p + 1)
.unwrap_or(dict.len());
if let Some(off) = find_subslice(&dict[line_start..line_end], needle) {
return Some(line_start + off);
}
line_start = line_end;
}
None
}
fn line_end_after(input: &[u8], pos: usize) -> usize {
memchr_nl(input, pos).map(|p| p + 1).unwrap_or(input.len())
}
fn parse_ostream_marker(line: &[u8]) -> Option<u32> {
let rest = line.strip_prefix(b"%% Object stream: object ")?;
let digits = rest.iter().take_while(|b| b.is_ascii_digit()).count();
if digits == 0 {
return None;
}
std::str::from_utf8(&rest[..digits]).ok()?.parse().ok()
}
fn scan_objstm_members(
input: &[u8],
content_start: usize,
endstream_kw: usize,
) -> Option<(usize, Vec<ObjStmMember>)> {
let mut first_marker_start = None;
let mut members = Vec::new();
let mut line_start = content_start;
while line_start < endstream_kw {
let line_end = line_end_after(input, line_start).min(endstream_kw);
if let Some(num) = parse_ostream_marker(&input[line_start..line_end]) {
first_marker_start.get_or_insert(line_start);
members.push(ObjStmMember {
num,
body_start: line_end,
});
}
line_start = line_end;
}
first_marker_start.map(|start| (start, members))
}
fn find_extends(region: &[u8]) -> Option<Vec<u8>> {
let pos = find_subslice(region, b"/Extends ")?;
let rest = ®ion[pos + b"/Extends ".len()..];
let digits = rest.iter().take_while(|b| b.is_ascii_digit()).count();
if digits == 0 {
return None;
}
let after_digits = &rest[digits..];
if !after_digits.starts_with(b" 0 R") {
return None;
}
Some(rest[..digits + b" 0 R".len()].to_vec())
}
fn byte_width(mut v: u64) -> usize {
let mut n = 0;
while v > 0 {
v >>= 8;
n += 1;
}
n
}
fn write_binary(out: &mut Vec<u8>, val: u64, bytes: usize) {
for i in (0..bytes).rev() {
out.push(((val >> (8 * i)) & 0xff) as u8);
}
}
fn emit_objstm(
out: &mut Vec<u8>,
input: &[u8],
first_marker_start: usize,
endstream_kw: usize,
members: &[ObjStmMember],
extends: &Option<Vec<u8>>,
) {
use std::fmt::Write as _;
let base = members[0].body_start;
let mut offsets = String::new();
for m in members {
let _ = writeln!(offsets, "{} {}", m.num, m.body_start - base);
}
let marker0_len = base - first_marker_start;
let first = offsets.len() + marker0_len;
let stream_length = offsets.len() + (endstream_kw - first_marker_start);
out.extend_from_slice(
format!(
" /Length {stream_length}\n /N {}\n /First {first}\n",
members.len()
)
.as_bytes(),
);
if let Some(ext) = extends {
out.extend_from_slice(b" /Extends ");
out.extend_from_slice(ext);
out.push(b'\n');
}
out.extend_from_slice(b">>\nstream\n");
out.extend_from_slice(offsets.as_bytes());
out.extend_from_slice(&input[first_marker_start..endstream_kw]);
}
fn emit_xref_stream(
out: &mut Vec<u8>,
input: &[u8],
type_line_end: usize,
content_start: usize,
entries: &[crate::XrefEntry],
size: usize,
this_offset: usize,
) {
let f1_nbytes = byte_width(this_offset as u64);
let max_index = entries
.iter()
.filter_map(|e| match e {
crate::XrefEntry::Compressed { index, .. } => Some(*index),
crate::XrefEntry::Uncompressed { .. } | crate::XrefEntry::Free { .. } => None,
})
.max()
.unwrap_or(0);
let f2_nbytes = byte_width(u64::from(max_index)).max(1);
out.extend_from_slice(
format!(
" /Length {}\n /W [ 1 {f1_nbytes} {f2_nbytes} ]\n",
(1 + entries.len()) * (1 + f1_nbytes + f2_nbytes)
)
.as_bytes(),
);
let mut line_start = type_line_end;
while line_start < content_start {
let line_end = line_end_after(input, line_start).min(content_start);
let line = &input[line_start..line_end];
if find_subslice(line, b"/Length").is_some() || find_subslice(line, b"/W").is_some() {
} else if find_subslice(line, b"/Size").is_some() {
out.extend_from_slice(format!(" /Size {size}\n").as_bytes());
} else {
out.extend_from_slice(line);
}
line_start = line_end;
}
write_binary(out, 0, 1);
write_binary(out, 0, f1_nbytes);
write_binary(out, 0, f2_nbytes);
for e in entries {
match e {
crate::XrefEntry::Uncompressed { offset } => {
write_binary(out, 1, 1);
write_binary(out, *offset, f1_nbytes);
write_binary(out, 0, f2_nbytes);
}
crate::XrefEntry::Compressed { stream, index } => {
write_binary(out, 2, 1);
write_binary(out, u64::from(*stream), f1_nbytes);
write_binary(out, u64::from(*index), f2_nbytes);
}
crate::XrefEntry::Free { .. } => {
unreachable!("qdf_fix's entries vector only ever holds Uncompressed/Compressed")
} }
}
out.extend_from_slice(b"\nendstream\nendobj\n\n");
out.extend_from_slice(b"startxref\n");
out.extend_from_slice(format!("{this_offset}\n").as_bytes());
out.extend_from_slice(b"%%EOF\n");
}
fn check_sequential(num: u32, last: u32, err_offset: usize) -> Result<u32> {
if num != last + 1 {
return Err(Error::parse(
err_offset,
"fix_qdf: non-sequential object numbering \
(canonical QDF numbers objects 1..N in order)",
));
}
Ok(num)
}
pub fn fix_qdf(input: &[u8]) -> Result<Vec<u8>> {
let mut objects: Vec<ObjectSpan> = Vec::new();
let mut is_xref_stream_form = false;
let mut cursor = 0usize;
while let Some((num, gen, line_start, kw_end)) = find_next_obj(input, cursor) {
let mut stream_info: Option<(usize, usize, usize)> = None; let mut early_xref_body: Option<(ObjectBody, usize)> = None; let after_dict = find_subslice(&input[kw_end..], b"<<")
.map(|o| kw_end + o)
.and_then(|d| find_matching_dict_close(input, d))
.map(|c| c + 2);
if let Some(stream_kw) =
after_dict.and_then(|sf| find_line_keyword_from(input, b"stream", sf))
{
let first_endobj = find_line_keyword_from(input, b"endobj", kw_end);
let stream_is_ours = match first_endobj {
None => true,
Some(eob) => stream_kw < eob,
};
if stream_is_ours {
let mut content_start = stream_kw + b"stream".len();
if input.get(content_start) == Some(&b'\r') {
content_start += 1;
}
if input.get(content_start) == Some(&b'\n') {
content_start += 1;
}
let dict = &input[kw_end..stream_kw];
if let Some(type_pos) = find_raw_type_line(dict, b"/Type /XRef") {
let type_line_end = line_end_after(input, kw_end + type_pos);
early_xref_body = Some((
ObjectBody::XRefStream {
type_line_end,
content_start,
},
content_start,
));
} else if let Some(endstream_kw) =
find_line_keyword_from(input, b"endstream", content_start)
{
stream_info = Some((stream_kw, content_start, endstream_kw));
}
}
}
let (body, end) = if let Some(early) = early_xref_body {
early
} else {
let endobj_search_from = match stream_info {
Some((_, _, endstream_kw)) => endstream_kw + b"endstream".len(),
None => kw_end,
};
let endobj =
find_line_keyword_from(input, b"endobj", endobj_search_from).ok_or_else(|| {
Error::parse(line_start, "fix_qdf: object without matching `endobj`")
})?;
let end = endobj + b"endobj".len();
let body =
if let Some((stream_kw_abs, content_start_abs, endstream_kw_abs)) = stream_info {
let dict = &input[kw_end..stream_kw_abs];
if let Some(type_pos) = find_raw_type_line(dict, b"/Type /ObjStm") {
let type_line_end = line_end_after(input, kw_end + type_pos);
let Some((first_marker_start, members)) =
scan_objstm_members(input, content_start_abs, endstream_kw_abs)
else {
return Err(Error::parse(
line_start,
"fix_qdf: object stream (/Type /ObjStm) has no \
`%% Object stream: object N` marker lines",
));
};
let extends = find_extends(&input[type_line_end..stream_kw_abs]);
ObjectBody::ObjStm {
type_line_end,
first_marker_start,
endstream_kw: endstream_kw_abs,
members,
extends,
}
} else {
let mut length_holder = None;
match classify_length(dict) {
LengthKind::Indirect(m) => length_holder = Some(m),
LengthKind::IndirectUnsupportedGeneration => {
return Err(Error::parse(
line_start,
"fix_qdf: stream /Length holder with non-zero generation \
is not supported (canonical QDF uses generation 0)",
));
}
LengthKind::Direct | LengthKind::None => {
}
}
ObjectBody::Plain {
stream_len: Some(endstream_kw_abs - content_start_abs),
length_holder,
ignore_newline: false,
}
}
} else {
ObjectBody::Plain {
stream_len: None,
length_holder: None,
ignore_newline: false,
}
};
(body, end)
};
is_xref_stream_form = matches!(body, ObjectBody::XRefStream { .. });
objects.push(ObjectSpan {
num,
gen,
obj_line_start: line_start,
end,
body,
});
if is_xref_stream_form {
break;
}
cursor = end;
}
if objects.is_empty() {
return Err(Error::parse(0, "fix_qdf: no objects found before xref"));
}
if !is_xref_stream_form
&& objects
.iter()
.any(|o| matches!(o.body, ObjectBody::ObjStm { .. }))
{
return Err(Error::Unsupported(
"fix_qdf: an object stream (/Type /ObjStm) in a file whose tail is a classic \
`xref` table (rather than a cross-reference stream) is not supported"
.into(),
));
}
let mut last_obj: u32 = 0;
for obj in &objects {
last_obj = check_sequential(obj.num, last_obj, obj.obj_line_start)?;
if let ObjectBody::ObjStm { members, .. } = &obj.body {
for m in members {
last_obj = check_sequential(m.num, last_obj, obj.obj_line_start)?;
}
}
}
let size = last_obj as usize + 1;
for i in 0..objects.len().saturating_sub(1) {
let next_num = objects[i + 1].num;
let end = objects[i].end;
let next_start = objects[i + 1].obj_line_start;
if let ObjectBody::Plain {
length_holder: Some(h),
ignore_newline,
..
} = &mut objects[i].body
{
if *h == next_num {
let separator = &input[end..next_start];
*ignore_newline = has_ignore_newline_marker(separator);
}
}
}
let gen0_bodies: std::collections::HashMap<u32, &ObjectBody> = objects
.iter()
.filter(|o| o.gen == 0)
.map(|o| (o.num, &o.body))
.collect();
let mut new_len_body: std::collections::HashMap<u32, usize> = std::collections::HashMap::new();
for obj in &objects {
if let ObjectBody::Plain {
stream_len: Some(measured_len),
length_holder: Some(holder),
ignore_newline,
} = &obj.body
{
let len = if *ignore_newline {
measured_len.saturating_sub(1)
} else {
*measured_len
};
match gen0_bodies.get(holder) {
None => {
return Err(Error::parse(
obj.obj_line_start,
"fix_qdf: stream's indirect /Length holder object (M 0) is missing",
));
}
Some(ObjectBody::ObjStm { .. } | ObjectBody::XRefStream { .. }) => {
return Err(Error::parse(
obj.obj_line_start,
"fix_qdf: stream's indirect /Length holder object (M 0) is an \
object stream or cross-reference stream, not a plain integer",
));
}
Some(ObjectBody::Plain { .. }) => {}
}
if let Some(&prev) = new_len_body.get(holder) {
if prev != len {
return Err(Error::parse(
obj.obj_line_start,
"fix_qdf: indirect /Length holder reused with conflicting lengths",
));
}
}
new_len_body.insert(*holder, len);
}
}
let mut out: Vec<u8> = Vec::with_capacity(input.len() + 16);
let first_obj_start = objects[0].obj_line_start;
out.extend_from_slice(&input[..first_obj_start]);
let mut new_offsets: Vec<(u32, u32, usize)> = Vec::with_capacity(objects.len());
let mut entries: Vec<crate::XrefEntry> = Vec::with_capacity(last_obj as usize);
for (i, obj) in objects.iter().enumerate() {
if i > 0 {
let prev_end = objects[i - 1].end;
out.extend_from_slice(&input[prev_end..obj.obj_line_start]);
}
let this_offset = out.len();
new_offsets.push((obj.num, obj.gen, this_offset));
entries.push(crate::XrefEntry::Uncompressed {
offset: this_offset as u64,
});
match &obj.body {
ObjectBody::Plain { .. } => {
if let Some(&new_len) = new_len_body.get(&obj.num).filter(|_| obj.gen == 0) {
rewrite_length_holder(&mut out, &input[obj.obj_line_start..obj.end], new_len)?;
} else {
out.extend_from_slice(&input[obj.obj_line_start..obj.end]);
}
}
ObjectBody::ObjStm {
type_line_end,
first_marker_start,
endstream_kw,
members,
extends,
} => {
out.extend_from_slice(&input[obj.obj_line_start..*type_line_end]);
emit_objstm(
&mut out,
input,
*first_marker_start,
*endstream_kw,
members,
extends,
);
out.extend_from_slice(&input[*endstream_kw..obj.end]);
for (idx, _) in members.iter().enumerate() {
entries.push(crate::XrefEntry::Compressed {
stream: obj.num,
index: idx as u32,
});
}
}
ObjectBody::XRefStream {
type_line_end,
content_start,
} => {
out.extend_from_slice(&input[obj.obj_line_start..*type_line_end]);
emit_xref_stream(
&mut out,
input,
*type_line_end,
*content_start,
&entries,
size,
this_offset,
);
return Ok(out);
}
}
}
let last_end = objects.last().unwrap().end;
let xref_pos = find_line_keyword_from(input, b"xref", last_end)
.ok_or_else(|| Error::parse(last_end, "fix_qdf: no classic `xref` table found"))?;
out.extend_from_slice(&input[last_end..xref_pos]);
let startxref_value = out.len();
out.extend_from_slice(b"xref\n");
out.extend_from_slice(format!("0 {size}\n").as_bytes());
out.extend_from_slice(b"0000000000 65535 f \n");
for &(_, gen, off) in &new_offsets {
out.extend_from_slice(format!("{off:010} {gen:05} n \n").as_bytes());
}
let trailer_kw = find_subslice(&input[xref_pos..], b"trailer")
.map(|p| xref_pos + p)
.ok_or_else(|| Error::parse(xref_pos, "fix_qdf: no `trailer` keyword"))?;
let dict_open = find_subslice(&input[trailer_kw..], b"<<")
.map(|p| trailer_kw + p)
.ok_or_else(|| Error::parse(trailer_kw, "fix_qdf: trailer has no dictionary"))?;
let dict_close = find_matching_dict_close(input, dict_open)
.ok_or_else(|| Error::parse(dict_open, "fix_qdf: unterminated trailer dictionary"))?;
let trailer_dict = &input[trailer_kw..dict_close + 2];
let rewritten_trailer = rewrite_size(trailer_dict, size);
out.extend_from_slice(&rewritten_trailer);
let after_dict = dict_close + 2;
let startxref_kw = find_subslice(&input[after_dict..], b"startxref")
.map(|p| after_dict + p)
.ok_or_else(|| Error::parse(after_dict, "fix_qdf: no `startxref` keyword"))?;
out.extend_from_slice(&input[after_dict..startxref_kw]);
out.extend_from_slice(b"startxref\n");
out.extend_from_slice(format!("{startxref_value}\n").as_bytes());
find_subslice(&input[startxref_kw..], b"%%EOF")
.ok_or_else(|| Error::parse(startxref_kw, "fix_qdf: no `%%EOF` marker"))?;
out.extend_from_slice(b"%%EOF\n");
Ok(out)
}
fn find_line_keyword_from(input: &[u8], kw: &[u8], from: usize) -> Option<usize> {
let mut i = from;
while i + kw.len() <= input.len() {
if &input[i..i + kw.len()] == kw {
let at_line_start = i == 0 || input[i - 1] == b'\n' || input[i - 1] == b'\r';
let after_ok = match input.get(i + kw.len()) {
None => true,
Some(&c) => c == b'\n' || c == b'\r' || c == b' ' || c == b'\t',
};
if at_line_start && after_ok {
return Some(i);
}
}
i += 1;
}
None
}
fn rewrite_length_holder(out: &mut Vec<u8>, obj_bytes: &[u8], new_len: usize) -> Result<()> {
let nl = obj_bytes
.iter()
.position(|&b| b == b'\n')
.ok_or_else(|| Error::parse(0, "fix_qdf: malformed length object header"))?;
out.extend_from_slice(&obj_bytes[..=nl]);
let endobj_rel = find_line_keyword_from(obj_bytes, b"endobj", nl + 1)
.ok_or_else(|| Error::parse(0, "fix_qdf: length object missing endobj"))?;
let body = &obj_bytes[nl + 1..endobj_rel];
let lead = body
.iter()
.take_while(|&&b| b.is_ascii_whitespace())
.count();
let after_int = body[lead..]
.iter()
.position(|&b| !b.is_ascii_digit())
.map(|p| lead + p)
.unwrap_or(body.len());
if after_int == lead || !body[lead..after_int].iter().all(|b| b.is_ascii_digit()) {
return Err(Error::parse(
0,
"fix_qdf: length-holder body is not a plain integer",
));
}
out.extend_from_slice(&body[..lead]);
out.extend_from_slice(new_len.to_string().as_bytes());
out.extend_from_slice(&body[after_int..]);
out.extend_from_slice(&obj_bytes[endobj_rel..]);
Ok(())
}
fn find_matching_dict_close(input: &[u8], open: usize) -> Option<usize> {
let mut depth = 0usize;
let mut i = open;
while i < input.len() {
match input[i] {
b'%' => {
while i < input.len() && input[i] != b'\n' && input[i] != b'\r' {
i += 1;
}
}
b'<' if input.get(i + 1) == Some(&b'<') => {
depth += 1;
i += 2;
}
b'>' if input.get(i + 1) == Some(&b'>') => {
depth -= 1;
if depth == 0 {
return Some(i);
}
i += 2;
}
b'<' => {
i += 1;
while i < input.len() && input[i] != b'>' {
i += 1;
}
i += 1;
}
b'(' => {
i += 1;
let mut sdepth = 1usize;
while i < input.len() && sdepth > 0 {
match input[i] {
b'\\' => i += 1, b'(' => sdepth += 1,
b')' => sdepth -= 1,
_ => {}
}
i += 1;
}
}
_ => i += 1,
}
}
None
}
fn rewrite_size(trailer: &[u8], size: usize) -> Vec<u8> {
let Some(p) = find_name_token(trailer, b"/Size") else {
return trailer.to_vec();
};
let mut out = Vec::with_capacity(trailer.len() + 4);
out.extend_from_slice(&trailer[..p + b"/Size".len()]);
let rest = &trailer[p + b"/Size".len()..];
let ws = rest
.iter()
.take_while(|&&b| b.is_ascii_whitespace())
.count();
let digits = rest[ws..].iter().take_while(|b| b.is_ascii_digit()).count();
out.extend_from_slice(&rest[..ws]);
out.extend_from_slice(size.to_string().as_bytes());
out.extend_from_slice(&rest[ws + digits..]);
out
}