use std::collections::BTreeMap;
use std::io::Write as _;
use flate2::write::ZlibEncoder;
use flate2::Compression;
use crate::object::ObjectRef;
use crate::Result;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct XrefStreamEntry {
pub entry_type: u8,
pub field2: u64,
pub field3: u64,
}
pub(crate) type XrefWidths = [u8; 3];
pub(crate) const PREV_FIELD_WIDTH: usize = 21;
fn bytes_needed(value: u64) -> u8 {
let mut width = 1u8;
let mut remaining = value >> 8;
while remaining > 0 {
width += 1;
remaining >>= 8;
}
width
}
fn columns(widths: XrefWidths) -> usize {
widths[0] as usize + widths[1] as usize + widths[2] as usize
}
fn push_be(out: &mut Vec<u8>, value: u64, width: u8) {
let bytes = value.to_be_bytes();
out.extend_from_slice(&bytes[bytes.len() - width as usize..]);
}
fn build_rows(entries: &[XrefStreamEntry], widths: XrefWidths) -> Vec<u8> {
let mut rows = Vec::with_capacity(entries.len() * columns(widths));
for entry in entries {
push_be(&mut rows, u64::from(entry.entry_type), widths[0]);
push_be(&mut rows, entry.field2, widths[1]);
push_be(&mut rows, entry.field3, widths[2]);
}
rows
}
fn png_up_predict(rows: &[u8], cols: usize) -> Vec<u8> {
let mut out = Vec::with_capacity(rows.len() + rows.len() / cols.max(1));
let mut previous = vec![0u8; cols];
for row in rows.chunks(cols) {
out.push(2);
for (i, &byte) in row.iter().enumerate() {
out.push(byte.wrapping_sub(previous[i]));
}
previous.copy_from_slice(row);
}
out
}
fn flate_compress(data: &[u8]) -> Vec<u8> {
let mut encoder = ZlibEncoder::new(Vec::new(), Compression::default());
encoder
.write_all(data)
.expect("ZlibEncoder::write_all on Vec<u8> cannot fail");
encoder
.finish()
.expect("ZlibEncoder::finish on Vec<u8> cannot fail")
}
pub(crate) fn encode_payload(entries: &[XrefStreamEntry], widths: XrefWidths) -> Vec<u8> {
let rows = build_rows(entries, widths);
flate_compress(&png_up_predict(&rows, columns(widths)))
}
pub(crate) fn encode_payload_uncompressed(
entries: &[XrefStreamEntry],
widths: XrefWidths,
) -> Vec<u8> {
png_up_predict(&build_rows(entries, widths), columns(widths))
}
pub(crate) struct XrefStreamDict<'a> {
pub widths: XrefWidths,
pub index: Option<(u32, u32)>,
pub info: Option<ObjectRef>,
pub root: Option<ObjectRef>,
pub size: u32,
pub prev: Option<u64>,
pub id: Option<(&'a [u8], &'a [u8])>,
}
fn push_hex(out: &mut Vec<u8>, bytes: &[u8]) {
const HEX: &[u8; 16] = b"0123456789abcdef";
for &b in bytes {
out.push(HEX[(b >> 4) as usize]);
out.push(HEX[(b & 0x0f) as usize]);
}
}
fn write_object_dict_prefix(
out: &mut Vec<u8>,
object: ObjectRef,
dict: &XrefStreamDict,
payload_len: usize,
) {
out.extend_from_slice(format!("{} {} obj\n", object.number, object.generation).as_bytes());
out.extend_from_slice(b"<< /Type /XRef");
out.extend_from_slice(format!(" /Length {payload_len}").as_bytes());
out.extend_from_slice(b" /Filter /FlateDecode /DecodeParms << /Columns ");
out.extend_from_slice(columns(dict.widths).to_string().as_bytes());
out.extend_from_slice(b" /Predictor 12 >>");
out.extend_from_slice(
format!(
" /W [ {} {} {} ]",
dict.widths[0], dict.widths[1], dict.widths[2]
)
.as_bytes(),
);
if let Some((start, count)) = dict.index {
out.extend_from_slice(format!(" /Index [ {start} {count} ]").as_bytes());
}
if let Some(info) = dict.info {
out.extend_from_slice(format!(" /Info {} {} R", info.number, info.generation).as_bytes());
}
if let Some(root) = dict.root {
out.extend_from_slice(format!(" /Root {} {} R", root.number, root.generation).as_bytes());
}
out.extend_from_slice(format!(" /Size {}", dict.size).as_bytes());
if let Some(prev) = dict.prev {
out.extend_from_slice(format!(" /Prev {prev:<PREV_FIELD_WIDTH$}").as_bytes());
}
}
fn write_object_framing(out: &mut Vec<u8>, payload: &[u8]) {
out.extend_from_slice(b" >>\nstream\n");
out.extend_from_slice(payload);
out.extend_from_slice(b"\nendstream\nendobj\n");
}
pub(crate) fn write_object(
out: &mut Vec<u8>,
object: ObjectRef,
dict: &XrefStreamDict,
payload: &[u8],
) {
write_object_dict_prefix(out, object, dict, payload.len());
if let Some((id0, id1)) = dict.id {
out.extend_from_slice(b" /ID [<");
push_hex(out, id0);
out.extend_from_slice(b"><");
push_hex(out, id1);
out.extend_from_slice(b">]");
}
write_object_framing(out, payload);
}
pub(crate) fn write_object_with_id_writer(
out: &mut Vec<u8>,
object: ObjectRef,
dict: &XrefStreamDict,
payload: &[u8],
id_writer: &mut dyn FnMut(&mut Vec<u8>),
) {
write_object_dict_prefix(out, object, dict, payload.len());
out.extend_from_slice(b" /ID ");
id_writer(out);
write_object_framing(out, payload);
}
pub(crate) fn calculate_xref_stream_padding(xref_bytes: usize) -> usize {
16 + 5 * xref_bytes.div_ceil(16384)
}
pub(crate) fn first_pass_widths(
max_id: u32,
max_ostream_index: u64,
hint_length: u64,
) -> XrefWidths {
let f1 = bytes_needed((1u64 << 25) + hint_length).max(bytes_needed(u64::from(max_id)));
let f3 = if max_ostream_index > 0 {
bytes_needed(max_ostream_index)
} else {
0
};
[1, f1, f3]
}
fn first_pass_payload_len(n_entries: usize, widths: XrefWidths) -> usize {
(1 + columns(widths)) * n_entries
}
pub(crate) fn first_pass_region_len(
object: ObjectRef,
dict: &XrefStreamDict,
n_entries: usize,
) -> usize {
let payload_len = first_pass_payload_len(n_entries, dict.widths);
let mut buf = Vec::new();
write_object(&mut buf, object, dict, &vec![0u8; payload_len]);
buf.len() + calculate_xref_stream_padding(buf.len())
}
pub(crate) fn second_pass_widths(
max_offset: u64,
hint_length: u64,
max_id: u32,
max_ostream_index: u64,
) -> XrefWidths {
let f1 = bytes_needed(max_offset + hint_length).max(bytes_needed(u64::from(max_id)));
let f3 = if max_ostream_index > 0 {
bytes_needed(max_ostream_index)
} else {
0
};
[1, f1, f3]
}
pub(crate) fn build_entries(
offs: &BTreeMap<u32, usize>,
member_new: &BTreeMap<u32, (u32, u32)>,
start: u32,
count: u32,
) -> Vec<XrefStreamEntry> {
(start..start + count)
.map(|number| {
if number != 0 {
if let Some(&off) = offs.get(&number) {
return XrefStreamEntry {
entry_type: 1,
field2: off as u64,
field3: 0,
};
}
if let Some(&(container, index)) = member_new.get(&number) {
return XrefStreamEntry {
entry_type: 2,
field2: u64::from(container),
field3: u64::from(index),
};
}
}
XrefStreamEntry {
entry_type: 0,
field2: 0,
field3: 0,
}
})
.collect()
}
pub(crate) fn max_entry_offset(entries: &[XrefStreamEntry]) -> u64 {
entries
.iter()
.filter(|e| e.entry_type == 1)
.map(|e| e.field2)
.max()
.unwrap_or(0)
}
pub(crate) fn write_padded_region(
object: ObjectRef,
dict: &XrefStreamDict,
payload: &[u8],
region_len: usize,
) -> Result<Vec<u8>> {
let mut buf = Vec::with_capacity(region_len);
write_object(&mut buf, object, dict, payload);
if buf.len() > region_len {
return Err(crate::Error::Unsupported(format!(
"linearized xref stream object ({} bytes) exceeds its reserved region \
({region_len} bytes)",
buf.len()
)));
}
buf.resize(region_len, b' ');
Ok(buf)
}
#[cfg(test)]
mod tests {
use super::*;
fn three_page_obj7_entries() -> Vec<XrefStreamEntry> {
let t1 = |off: u64| XrefStreamEntry {
entry_type: 1,
field2: off,
field3: 0,
};
let t2 = |idx: u64| XrefStreamEntry {
entry_type: 2,
field2: 12,
field3: idx,
};
vec![
t1(15),
t1(216),
t1(608),
t1(677),
t1(807),
t1(1000),
t1(1153),
t2(0),
t2(1),
t2(2),
t2(3),
]
}
fn three_page_obj5_entries() -> Vec<XrefStreamEntry> {
let t1 = |off: u64| XrefStreamEntry {
entry_type: 1,
field2: off,
field3: 0,
};
vec![
XrefStreamEntry {
entry_type: 0,
field2: 0,
field3: 0,
},
t1(1540),
t1(1731),
t1(1883),
t1(2074),
t1(2226),
]
}
const ID0: [u8; 16] = [
0x31, 0x96, 0x4d, 0xf6, 0xe5, 0xb2, 0x21, 0x18, 0x59, 0xe4, 0xac, 0x9d, 0x6e, 0x86, 0x2d,
0x1a,
];
const ID1: [u8; 16] = [
0x60, 0x0e, 0x73, 0x37, 0x15, 0x98, 0x32, 0xba, 0x5a, 0xec, 0x69, 0x83, 0x87, 0xe2, 0xb7,
0x95,
];
#[test]
fn calculate_padding_matches_qpdf() {
assert_eq!(calculate_xref_stream_padding(0), 16);
assert_eq!(calculate_xref_stream_padding(370), 21);
assert_eq!(calculate_xref_stream_padding(16384), 21);
assert_eq!(calculate_xref_stream_padding(16385), 26);
}
#[test]
fn first_pass_widths_force_wide_field2() {
assert_eq!(first_pass_widths(16, 3, 130), [1, 4, 1]);
assert_eq!(first_pass_widths(16, 0, 0), [1, 4, 0]);
}
#[test]
fn first_pass_region_matches_three_page_golden() {
let widths = first_pass_widths(16, 3, 130);
assert_eq!(first_pass_payload_len(11, widths), 77);
let dict = XrefStreamDict {
widths,
index: Some((6, 11)),
info: Some(ObjectRef::new(15, 0)),
root: Some(ObjectRef::new(8, 0)),
size: 17,
prev: Some(2356),
id: Some((&ID0, &ID1)),
};
assert_eq!(first_pass_region_len(ObjectRef::new(7, 0), &dict, 11), 391);
}
#[test]
fn second_pass_widths_match_three_page() {
assert_eq!(second_pass_widths(1153, 130, 16, 3), [1, 2, 1]);
assert_eq!(second_pass_widths(2226, 0, 16, 3), [1, 2, 1]);
assert_eq!(second_pass_widths(70_000, 0, 16, 3), [1, 3, 1]);
}
#[test]
fn build_entries_reproduce_golden_object_maps() {
let mut offs = BTreeMap::new();
for (n, off) in [
(6, 15),
(7, 216),
(8, 608),
(9, 677),
(10, 807),
(11, 1000),
(12, 1153),
] {
offs.insert(n, off);
}
let mut members = BTreeMap::new();
for (n, idx) in [(13, 0u32), (14, 1), (15, 2), (16, 3)] {
members.insert(n, (12u32, idx));
}
assert_eq!(
build_entries(&offs, &members, 6, 11),
three_page_obj7_entries()
);
let mut offs2 = BTreeMap::new();
for (n, off) in [(1, 1540), (2, 1731), (3, 1883), (4, 2074), (5, 2226)] {
offs2.insert(n, off);
}
assert_eq!(
build_entries(&offs2, &BTreeMap::new(), 0, 6),
three_page_obj5_entries()
);
}
#[test]
fn build_entries_fills_gaps_with_free_entries() {
let mut offs = BTreeMap::new();
offs.insert(1u32, 100usize);
let entries = build_entries(&offs, &BTreeMap::new(), 1, 3);
assert_eq!(
entries,
vec![
XrefStreamEntry {
entry_type: 1,
field2: 100,
field3: 0
},
XrefStreamEntry {
entry_type: 0,
field2: 0,
field3: 0
},
XrefStreamEntry {
entry_type: 0,
field2: 0,
field3: 0
},
]
);
}
#[test]
fn max_entry_offset_ignores_compressed_rows() {
let entries = three_page_obj7_entries();
assert_eq!(max_entry_offset(&entries), 1153);
assert_eq!(max_entry_offset(&[]), 0);
}
#[test]
fn write_padded_region_pads_to_length() {
let dict = XrefStreamDict {
widths: [1, 2, 1],
index: None,
info: None,
root: None,
size: 6,
prev: None,
id: Some((&ID0, &ID1)),
};
let region = write_padded_region(ObjectRef::new(5, 0), &dict, b"PAYLOAD", 400).unwrap();
assert_eq!(region.len(), 400);
assert!(region.starts_with(b"5 0 obj\n<< /Type /XRef /Length 7"));
assert!(region.ends_with(b" "));
assert!(region[region.len() - 1] == b' ');
}
#[test]
fn write_padded_region_rejects_oversized_object() {
let dict = XrefStreamDict {
widths: [1, 2, 1],
index: None,
info: None,
root: None,
size: 6,
prev: None,
id: Some((&ID0, &ID1)),
};
let err = write_padded_region(ObjectRef::new(5, 0), &dict, b"PAYLOAD", 10).unwrap_err();
assert!(matches!(err, crate::Error::Unsupported(_)));
}
#[test]
fn bytes_needed_spans_byte_boundaries() {
assert_eq!(bytes_needed(0), 1);
assert_eq!(bytes_needed(255), 1);
assert_eq!(bytes_needed(256), 2);
assert_eq!(bytes_needed(65_535), 2);
assert_eq!(bytes_needed(65_536), 3);
}
#[test]
fn build_rows_packs_big_endian_fields() {
let entries = [
XrefStreamEntry {
entry_type: 1,
field2: 0x0102,
field3: 0,
},
XrefStreamEntry {
entry_type: 2,
field2: 12,
field3: 3,
},
];
assert_eq!(
build_rows(&entries, [1, 2, 1]),
vec![0x01, 0x01, 0x02, 0x00, 0x02, 0x00, 0x0c, 0x03]
);
}
#[test]
fn predictor_reproduces_golden_pre_flate_bytes() {
let obj7_predicted = "0201000f00020000c900020002880002000045000200018200020000c1\
0002000199000201fc8b00020000000102000000010200000001";
let rows = build_rows(&three_page_obj7_entries(), [1, 2, 1]);
assert_eq!(hex(&png_up_predict(&rows, 4)), obj7_predicted);
let obj5_predicted = "02000000000201060400020000bf000200019800020001bf000200009800";
let rows5 = build_rows(&three_page_obj5_entries(), [1, 2, 1]);
assert_eq!(hex(&png_up_predict(&rows5, 4)), obj5_predicted);
}
#[test]
fn encode_payload_round_trips_through_inflate() {
let rows = build_rows(&three_page_obj5_entries(), [1, 2, 1]);
let predicted = png_up_predict(&rows, 4);
let payload = encode_payload(&three_page_obj5_entries(), [1, 2, 1]);
let inflated = inflate(&payload);
assert_eq!(inflated, predicted);
}
#[test]
fn dict_key_order_matches_qpdf() {
let mut out = Vec::new();
write_object(
&mut out,
ObjectRef::new(7, 0),
&XrefStreamDict {
widths: [1, 2, 1],
index: Some((6, 11)),
info: Some(ObjectRef::new(15, 0)),
root: Some(ObjectRef::new(8, 0)),
size: 17,
prev: Some(2226),
id: Some((&ID0, &ID1)),
},
b"PAYLOAD",
);
let text = String::from_utf8(out).unwrap();
assert!(text.starts_with(
"7 0 obj\n<< /Type /XRef /Length 7 /Filter /FlateDecode \
/DecodeParms << /Columns 4 /Predictor 12 >> /W [ 1 2 1 ] \
/Index [ 6 11 ] /Info 15 0 R /Root 8 0 R /Size 17 /Prev 2226"
));
let after_prev = &text[text.find("/Prev 2226").unwrap() + "/Prev 2226".len()..];
let spaces = after_prev.chars().take_while(|c| *c == ' ').count();
assert_eq!(spaces, 18);
assert!(after_prev[spaces..].starts_with("/ID [<"));
assert!(text.ends_with(" >>\nstream\nPAYLOAD\nendstream\nendobj\n"));
}
#[test]
fn main_xref_dict_omits_chain_and_root_keys() {
let mut out = Vec::new();
write_object(
&mut out,
ObjectRef::new(5, 0),
&XrefStreamDict {
widths: [1, 2, 1],
index: None,
info: None,
root: None,
size: 6,
prev: None,
id: Some((&ID0, &ID1)),
},
b"X",
);
let text = String::from_utf8(out).unwrap();
assert!(text.contains("/W [ 1 2 1 ] /Size 6 /ID [<"));
assert!(!text.contains("/Index"));
assert!(!text.contains("/Root"));
assert!(!text.contains("/Prev"));
}
#[cfg(feature = "qpdf-zlib-compat")]
const GOLDEN_OBJ7: &[u8] = b"7 0 obj\n<< /Type /XRef /Length 43 /Filter /FlateDecode \
/DecodeParms << /Columns 4 /Predictor 12 >> /W [ 1 2 1 ] /Index [ 6 11 ] \
/Info 15 0 R /Root 8 0 R /Size 17 /Prev 2226 \
/ID [<31964df6e5b2211859e4ac9d6e862d1a><600e7337159832ba5aec698387e2b795>] >>\n\
stream\nx\x9ccbd\xe0g`b`8\t$\x98:@,W \xc1\xd8\x04b\x1d\x04\xb1f201\xfe\xe9\x06q\x19\x18\
\x11\x04\x00\x98\xa4\x05(\nendstream\nendobj\n";
#[cfg(feature = "qpdf-zlib-compat")]
const GOLDEN_OBJ5: &[u8] = b"5 0 obj\n<< /Type /XRef /Length 31 /Filter /FlateDecode \
/DecodeParms << /Columns 4 /Predictor 12 >> /W [ 1 2 1 ] /Size 6 \
/ID [<31964df6e5b2211859e4ac9d6e862d1a><600e7337159832ba5aec698387e2b795>] >>\n\
stream\nx\x9ccb\x00\x02&F6\x16\x06&\x06\x86\xfd@\x82q\x06\x88\x00\xb1\x18f0\x00\x00\
\x1c7\x02\xc8\nendstream\nendobj\n";
#[cfg(feature = "qpdf-zlib-compat")]
#[test]
fn first_half_xref_object_is_byte_identical_to_qpdf() {
let payload = encode_payload(&three_page_obj7_entries(), [1, 2, 1]);
let mut out = Vec::new();
write_object(
&mut out,
ObjectRef::new(7, 0),
&XrefStreamDict {
widths: [1, 2, 1],
index: Some((6, 11)),
info: Some(ObjectRef::new(15, 0)),
root: Some(ObjectRef::new(8, 0)),
size: 17,
prev: Some(2226),
id: Some((&ID0, &ID1)),
},
&payload,
);
assert_eq!(out, GOLDEN_OBJ7);
}
#[cfg(feature = "qpdf-zlib-compat")]
#[test]
fn main_xref_object_is_byte_identical_to_qpdf() {
let payload = encode_payload(&three_page_obj5_entries(), [1, 2, 1]);
let mut out = Vec::new();
write_object(
&mut out,
ObjectRef::new(5, 0),
&XrefStreamDict {
widths: [1, 2, 1],
index: None,
info: None,
root: None,
size: 6,
prev: None,
id: Some((&ID0, &ID1)),
},
&payload,
);
assert_eq!(out, GOLDEN_OBJ5);
}
fn hex(bytes: &[u8]) -> String {
let mut s = String::with_capacity(bytes.len() * 2);
for b in bytes {
s.push_str(&format!("{b:02x}"));
}
s
}
fn inflate(data: &[u8]) -> Vec<u8> {
use flate2::read::ZlibDecoder;
use std::io::Read as _;
let mut out = Vec::new();
ZlibDecoder::new(data)
.read_to_end(&mut out)
.expect("valid zlib payload");
out
}
}