use super::plan::LinearizationPlan;
use super::renumber::RenumberMap;
use crate::ObjectRef;
pub fn bits_needed(value: u64) -> u32 {
if value == 0 {
0
} else {
64 - value.leading_zeros()
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PageOffsetHeader {
pub least_object_count: u32,
pub location_of_first_page: u64,
pub bits_object_count_delta: u32,
pub least_page_length: u64,
pub bits_page_length_delta: u32,
pub least_content_offset: u64,
pub bits_content_offset_delta: u32,
pub least_content_length: u64,
pub bits_content_length_delta: u32,
pub bits_shared_object_count: u32,
pub bits_shared_object_id: u32,
pub bits_numerator: u32,
pub denominator: u32,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PageOffsetEntry {
pub object_count_minus_least: u32,
pub page_length_minus_least: u64,
pub shared_object_count: u32,
pub shared_object_ids: Vec<u32>,
pub shared_object_numerators: Vec<u32>,
pub content_stream_offset: u64,
pub content_stream_length: u64,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PageOffsetHintTable {
pub header: PageOffsetHeader,
pub entries: Vec<PageOffsetEntry>,
}
fn page0_object_count_with_objstm(
plan: &LinearizationPlan,
member_to_container: &std::collections::BTreeMap<ObjectRef, (u32, u32)>,
second_half_container_nums: &std::collections::BTreeSet<u32>,
open_document_container_nums: &std::collections::BTreeSet<u32>,
) -> u32 {
let exclude: std::collections::BTreeSet<u32> = second_half_container_nums
.union(open_document_container_nums)
.copied()
.collect();
objstm_folded_count(
plan.part2_objects
.iter()
.chain(&plan.part3_objects)
.chain(&plan.outline_first_page_members),
member_to_container,
&exclude,
)
}
pub(crate) fn non_page_owned_containers(
plan: &LinearizationPlan,
member_to_container: &std::collections::BTreeMap<ObjectRef, (u32, u32)>,
source_container_by_member: &std::collections::BTreeMap<u32, u32>,
) -> std::collections::BTreeSet<u32> {
use std::collections::{BTreeMap, BTreeSet};
let fallback_source_membership = if source_container_by_member.is_empty() {
plan.preserve_source_membership().unwrap_or_default()
} else {
BTreeMap::new()
};
let source_container_by_member = if source_container_by_member.is_empty() {
&fallback_source_membership
} else {
source_container_by_member
};
let page_private_owner = |member: ObjectRef| -> Option<usize> {
if let Some(optimization) = plan.optimization.as_ref() {
let owner = source_container_by_member
.get(&member.number)
.copied()
.map(|source| ObjectRef::new(source, 0))
.unwrap_or(member);
return optimization
.other_page_private_owner(owner)
.map(|page| page as usize);
}
plan.per_page_private_objects
.iter()
.enumerate()
.skip(1)
.find_map(|(page, members)| members.contains(&member).then_some(page))
};
let mut container_pages: BTreeMap<u32, BTreeSet<usize>> = BTreeMap::new();
let mut has_nonpage_member: BTreeSet<u32> = BTreeSet::new();
let mut all_containers: BTreeSet<u32> = BTreeSet::new();
for (member, &(cnum, _)) in member_to_container {
all_containers.insert(cnum);
match page_private_owner(*member) {
Some(i) => {
container_pages.entry(cnum).or_default().insert(i);
}
None => {
has_nonpage_member.insert(cnum);
}
}
}
all_containers
.into_iter()
.filter(|c| {
let single_page = container_pages.get(c).is_some_and(|s| s.len() == 1);
!single_page || has_nonpage_member.contains(c)
})
.collect()
}
fn objstm_folded_count<'a>(
objects: impl Iterator<Item = &'a ObjectRef>,
member_to_container: &std::collections::BTreeMap<ObjectRef, (u32, u32)>,
exclude: &std::collections::BTreeSet<u32>,
) -> u32 {
use std::collections::BTreeSet;
let mut plain = 0u32;
let mut containers: BTreeSet<u32> = BTreeSet::new();
for r in objects {
match member_to_container.get(r) {
Some(&(container_num, _)) => {
if !exclude.contains(&container_num) {
containers.insert(container_num);
}
}
None => plain += 1,
}
}
plain + containers.len() as u32
}
impl PageOffsetHintTable {
pub fn from_plan(
plan: &LinearizationPlan,
renumber: &RenumberMap,
member_to_container: &std::collections::BTreeMap<ObjectRef, (u32, u32)>,
container_shared_sort_key: &std::collections::BTreeMap<u32, (u8, u32)>,
second_half_container_nums: &std::collections::BTreeSet<u32>,
open_document_container_nums: &std::collections::BTreeSet<u32>,
) -> Self {
Self::from_plan_with_source_membership(
plan,
renumber,
member_to_container,
container_shared_sort_key,
second_half_container_nums,
open_document_container_nums,
&std::collections::BTreeMap::new(),
)
}
pub(crate) fn from_plan_with_source_membership(
plan: &LinearizationPlan,
renumber: &RenumberMap,
member_to_container: &std::collections::BTreeMap<ObjectRef, (u32, u32)>,
container_shared_sort_key: &std::collections::BTreeMap<u32, (u8, u32)>,
second_half_container_nums: &std::collections::BTreeSet<u32>,
open_document_container_nums: &std::collections::BTreeSet<u32>,
source_container_by_member: &std::collections::BTreeMap<u32, u32>,
) -> Self {
assert!(
!plan.page_hints.is_empty(),
"PageOffsetHintTable::from_plan requires at least one page in the plan"
);
assert!(
plan.page_hints.iter().all(|hint| hint.object_count > 0),
"PageOffsetHintTable::from_plan requires finalized per-page object counts \
(every page_hints[i].object_count must be > 0; ensure LinearizationPlan \
populates counts for all pages, not just page 0)"
);
let page_count = plan.page_hints.len();
let shared_hints = plan.canonical_raw_shared_hints(
member_to_container,
renumber,
second_half_container_nums,
open_document_container_nums,
);
let mut object_counts: Vec<u32> = plan.page_hints.iter().map(|h| h.object_count).collect();
if !member_to_container.is_empty() {
object_counts[0] = page0_object_count_with_objstm(
plan,
member_to_container,
second_half_container_nums,
open_document_container_nums,
);
object_counts[0] += plan
.raw
.part2_objects
.iter()
.chain(&plan.raw.part3_objects)
.chain(&plan.raw.part6_outline_objects)
.filter(|object_gen| object_gen.to_object_ref().is_none())
.count() as u32;
let non_page_owned =
non_page_owned_containers(plan, member_to_container, source_container_by_member);
for (i, count) in object_counts.iter_mut().enumerate().skip(1) {
if let Some(privates) = plan.per_page_private_objects.get(i) {
*count =
objstm_folded_count(privates.iter(), member_to_container, &non_page_owned);
}
*count += plan
.raw
.per_page_private_objects
.get(i)
.into_iter()
.flatten()
.filter(|object_gen| object_gen.to_object_ref().is_none())
.count() as u32;
}
}
let least_object_count = object_counts.iter().copied().min().unwrap_or(0);
let greatest_object_count = object_counts.iter().copied().max().unwrap_or(0);
let object_count_delta = (greatest_object_count - least_object_count) as u64;
let mut shared_counts: Vec<u32> = vec![0u32; page_count];
let mut shared_ids_per_page: Vec<Vec<u32>> = vec![Vec::new(); page_count];
for (shared_idx, shared_hint) in shared_hints.iter().enumerate() {
for &page_idx in &shared_hint.referencing_pages {
let idx = page_idx as usize;
assert!(
idx < page_count,
"shared hint object {:?} references out-of-range page index {} (page_count={})",
shared_hint.object,
page_idx,
page_count
);
shared_counts[idx] += 1;
shared_ids_per_page[idx].push(shared_idx as u32);
}
}
if !member_to_container.is_empty() {
let post_optimization_plain = plan
.optimization
.as_ref()
.and_then(|optimization| optimization.pre_optimization_object_refs());
let shared_sort_key = |shared_idx: u32| -> (u8, u32) {
let entry = &shared_hints[shared_idx as usize];
if let Some(container) = entry.container {
container_shared_sort_key
.get(&container)
.copied()
.unwrap_or((1, 0))
} else {
let object = entry
.object
.expect("raw shared hint entry must have an object or container");
let phase = post_optimization_plain.is_some_and(|refs| {
object
.to_object_ref()
.is_none_or(|object_ref| !refs.contains(&object_ref))
});
let output_number = if phase {
renumber
.new_for_raw(object)
.map_or(u32::MAX, |object_ref| object_ref.number)
} else {
u32::try_from(object.get_obj()).unwrap_or(u32::MAX)
};
(if phase { 2 } else { 0 }, output_number)
}
};
for ids in &mut shared_ids_per_page {
let plain_aliases: std::collections::BTreeSet<u32> = ids
.iter()
.filter_map(|&shared_idx| {
let entry = &shared_hints[shared_idx as usize];
entry
.object
.map(|object| u32::try_from(object.get_obj()).unwrap_or(u32::MAX))
})
.collect();
ids.sort_by_key(|&shared_idx| {
let entry = &shared_hints[shared_idx as usize];
let key = shared_sort_key(shared_idx);
if let Some(container) = entry.container {
if key.0 == 0 && plain_aliases.contains(&container) {
return (key.0, key.1.max(container).saturating_add(1));
}
}
{
key
}
});
}
} else {
for ids in &mut shared_ids_per_page {
if plan.has_raw_projection_gap() {
ids.sort_unstable_by_key(|&shared_idx| {
shared_hints[shared_idx as usize]
.object
.expect("raw shared hint entry must retain its qpdf object identity")
});
} else {
ids.sort_unstable_by_key(|&shared_idx| {
plan.writer_object_order_key(
shared_hints[shared_idx as usize]
.object
.and_then(|object| object.to_object_ref())
.expect("checked shared hint must project to ObjectRef"),
)
});
}
}
}
let greatest_shared_count = shared_counts.iter().copied().max().unwrap_or(0);
let shared_hint_count = shared_hints.len() as u64;
let header = PageOffsetHeader {
least_object_count,
location_of_first_page: 0, bits_object_count_delta: bits_needed(object_count_delta),
least_page_length: 0, bits_page_length_delta: 0, least_content_offset: 0, bits_content_offset_delta: 0, least_content_length: 0, bits_content_length_delta: 0, bits_shared_object_count: bits_needed(greatest_shared_count as u64),
bits_shared_object_id: bits_needed(shared_hint_count),
bits_numerator: 0, denominator: 4, };
let entries: Vec<PageOffsetEntry> = (0..page_count)
.map(|i| {
let obj_count = object_counts[i];
let obj_count_minus_least = obj_count.saturating_sub(least_object_count);
let count = shared_counts[i];
let ids = shared_ids_per_page[i].clone();
let numerators = vec![0u32; ids.len()];
PageOffsetEntry {
object_count_minus_least: obj_count_minus_least,
page_length_minus_least: 0, shared_object_count: count,
shared_object_ids: ids,
shared_object_numerators: numerators,
content_stream_offset: 0, content_stream_length: 0, }
})
.collect();
Self { header, entries }
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::linearization::plan::{
LinearizationPlan, PageHintEntry, RawLinearizationPlan, RawSharedObjectHintEntry,
SharedObjectHintEntry,
};
use crate::linearization::renumber::RenumberMap;
use crate::qpdf_obj_gen::QpdfObjGen;
use crate::ObjectRef;
fn single_page_plan() -> LinearizationPlan {
let page_ref = ObjectRef::new(3, 0);
LinearizationPlan {
part2_objects: vec![
ObjectRef::new(3, 0),
ObjectRef::new(2, 0),
ObjectRef::new(1, 0),
],
total_object_count: 3,
page_hints: vec![PageHintEntry {
page_ref,
first_object_index: 0,
object_count: 3,
byte_length: 0,
}],
..Default::default()
}
}
fn two_page_plan_with_shared() -> LinearizationPlan {
LinearizationPlan {
part2_objects: vec![ObjectRef::new(3, 0), ObjectRef::new(6, 0)],
part3_objects: vec![ObjectRef::new(5, 0), ObjectRef::new(8, 0)],
part4_other_pages_private: vec![ObjectRef::new(4, 0), ObjectRef::new(7, 0)],
total_object_count: 8,
page_hints: vec![
PageHintEntry {
page_ref: ObjectRef::new(3, 0),
first_object_index: 0,
object_count: 4, byte_length: 0,
},
PageHintEntry {
page_ref: ObjectRef::new(4, 0),
first_object_index: 0,
object_count: 5,
byte_length: 0,
},
],
shared_hints: vec![
SharedObjectHintEntry {
object_ref: ObjectRef::new(3, 0),
referencing_pages: vec![],
},
SharedObjectHintEntry {
object_ref: ObjectRef::new(6, 0),
referencing_pages: vec![],
},
SharedObjectHintEntry {
object_ref: ObjectRef::new(5, 0),
referencing_pages: vec![1], },
SharedObjectHintEntry {
object_ref: ObjectRef::new(8, 0),
referencing_pages: vec![1], },
],
..Default::default()
}
}
#[test]
fn raw_shared_identifiers_follow_qpdf_objgen_order_across_linearization_parts() {
let checked_first = QpdfObjGen::new(6, 0);
let raw_second = QpdfObjGen::new(20, 65_536);
let plan = LinearizationPlan {
part2_objects: vec![ObjectRef::new(1, 0)],
part3_objects: vec![ObjectRef::new(6, 0)],
page_hints: vec![
PageHintEntry {
page_ref: ObjectRef::new(1, 0),
first_object_index: 0,
object_count: 1,
byte_length: 0,
},
PageHintEntry {
page_ref: ObjectRef::new(2, 0),
first_object_index: 0,
object_count: 1,
byte_length: 0,
},
],
raw: RawLinearizationPlan {
part2_objects: vec![QpdfObjGen::new(1, 0)],
part3_objects: vec![checked_first],
part4_other_pages_shared: vec![raw_second],
shared_hints: vec![
RawSharedObjectHintEntry {
object: Some(checked_first),
container: None,
referencing_pages: vec![1],
},
RawSharedObjectHintEntry {
object: Some(raw_second),
container: None,
referencing_pages: vec![1],
},
],
projection_gap: true,
..Default::default()
},
..Default::default()
};
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(
table.entries[1].shared_object_ids,
vec![0, 1],
"qpdf walks page shared users by raw object identity, even when output slots reverse the order"
);
}
#[test]
fn bits_needed_zero() {
assert_eq!(bits_needed(0), 0);
}
#[test]
fn bits_needed_one() {
assert_eq!(bits_needed(1), 1);
}
#[test]
fn bits_needed_two() {
assert_eq!(bits_needed(2), 2);
}
#[test]
fn bits_needed_three() {
assert_eq!(bits_needed(3), 2);
}
#[test]
fn bits_needed_seven() {
assert_eq!(bits_needed(7), 3);
}
#[test]
fn bits_needed_eight() {
assert_eq!(bits_needed(8), 4);
}
#[test]
fn bits_needed_large() {
assert_eq!(bits_needed(255), 8);
assert_eq!(bits_needed(256), 9);
assert_eq!(bits_needed(u64::MAX), 64);
}
#[test]
fn single_page_entries_len_is_one() {
let plan = single_page_plan();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(
table.entries.len(),
1,
"single-page must have exactly 1 entry"
);
}
#[test]
fn single_page_all_deltas_zero_so_bit_widths_zero() {
let plan = single_page_plan();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.header.bits_object_count_delta, 0);
assert_eq!(table.header.bits_shared_object_count, 0);
assert_eq!(table.header.bits_shared_object_id, 0);
}
#[test]
fn single_page_least_object_count() {
let plan = single_page_plan();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.header.least_object_count, 3);
}
#[test]
fn single_page_entry_object_count_minus_least_is_zero() {
let plan = single_page_plan();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.entries[0].object_count_minus_least, 0);
}
#[test]
fn single_page_placeholder_fields_are_zero() {
let plan = single_page_plan();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.header.location_of_first_page, 0);
assert_eq!(table.header.least_page_length, 0);
assert_eq!(table.header.least_content_offset, 0);
assert_eq!(table.header.least_content_length, 0);
assert_eq!(table.entries[0].page_length_minus_least, 0);
assert_eq!(table.entries[0].content_stream_offset, 0);
assert_eq!(table.entries[0].content_stream_length, 0);
}
#[test]
fn single_page_denominator_is_four() {
let plan = single_page_plan();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(
table.header.denominator, 4,
"denominator must be 4 (qpdf default)"
);
}
#[test]
fn single_page_no_shared_objects() {
let plan = single_page_plan();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.entries[0].shared_object_count, 0);
assert!(table.entries[0].shared_object_ids.is_empty());
assert!(table.entries[0].shared_object_numerators.is_empty());
}
#[test]
fn two_page_entries_len_is_two() {
let plan = two_page_plan_with_shared();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.entries.len(), 2, "two-page plan must have 2 entries");
}
#[test]
fn two_page_least_object_count() {
let plan = two_page_plan_with_shared();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.header.least_object_count, 4);
}
#[test]
fn two_page_bits_object_count_delta() {
let plan = two_page_plan_with_shared();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.header.bits_object_count_delta, 1);
}
#[test]
fn two_page_entry_object_count_minus_least() {
let plan = two_page_plan_with_shared();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.entries[0].object_count_minus_least, 0);
assert_eq!(table.entries[1].object_count_minus_least, 1);
}
#[test]
fn two_page_shared_object_count_per_page() {
let plan = two_page_plan_with_shared();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.entries[0].shared_object_count, 0);
assert_eq!(table.entries[1].shared_object_count, 2);
}
#[test]
fn two_page_bits_shared_object_count() {
let plan = two_page_plan_with_shared();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.header.bits_shared_object_count, 2);
}
#[test]
fn two_page_bits_shared_object_id() {
let plan = two_page_plan_with_shared();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.header.bits_shared_object_id, 3);
}
#[test]
fn two_page_shared_object_ids_are_hint_indices() {
let plan = two_page_plan_with_shared();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert!(
table.entries[0].shared_object_ids.is_empty(),
"page 0 must not list shared identifiers"
);
let mut ids1 = table.entries[1].shared_object_ids.clone();
ids1.sort_unstable();
assert_eq!(
ids1,
vec![2, 3],
"page 1 shared object ids must be 0-based indices 2 and 3 into shared_hints"
);
}
fn two_page_plan_with_reordered_shared_objects() -> LinearizationPlan {
LinearizationPlan {
part2_objects: vec![ObjectRef::new(3, 0), ObjectRef::new(6, 0)],
part3_objects: vec![ObjectRef::new(50, 0), ObjectRef::new(8, 0)],
part4_other_pages_private: vec![ObjectRef::new(4, 0), ObjectRef::new(7, 0)],
total_object_count: 8,
page_hints: vec![
PageHintEntry {
page_ref: ObjectRef::new(3, 0),
first_object_index: 0,
object_count: 4,
byte_length: 0,
},
PageHintEntry {
page_ref: ObjectRef::new(4, 0),
first_object_index: 0,
object_count: 5,
byte_length: 0,
},
],
shared_hints: vec![
SharedObjectHintEntry {
object_ref: ObjectRef::new(3, 0),
referencing_pages: vec![],
},
SharedObjectHintEntry {
object_ref: ObjectRef::new(6, 0),
referencing_pages: vec![],
},
SharedObjectHintEntry {
object_ref: ObjectRef::new(50, 0),
referencing_pages: vec![1],
},
SharedObjectHintEntry {
object_ref: ObjectRef::new(8, 0),
referencing_pages: vec![1],
},
],
..Default::default()
}
}
#[test]
fn two_page_pre_optimization_plain_objects_sort_by_source_number_even_with_folded_container() {
let plan = two_page_plan_with_reordered_shared_objects();
let renumber = RenumberMap::from_plan(&plan);
let mut member_to_container = std::collections::BTreeMap::new();
member_to_container.insert(ObjectRef::new(6, 0), (99, 0));
let mut container_shared_sort_key = std::collections::BTreeMap::new();
container_shared_sort_key.insert(99, (1u8, 0u32));
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&member_to_container,
&container_shared_sort_key,
&Default::default(),
&Default::default(),
);
assert_eq!(
table.entries[1].shared_object_ids,
vec![2, 1],
"pre-optimization plain shared objects must sort by source \
object number, not physical output number, even when this \
page also references a folded ObjStm container"
);
}
#[test]
fn preserve_container_source_key_collision_keeps_plain_alias_before_container() {
let mut plan = two_page_plan_with_reordered_shared_objects();
plan.shared_hints[1].referencing_pages = vec![1];
let renumber = RenumberMap::from_plan(&plan);
let member_to_container =
std::collections::BTreeMap::from([(ObjectRef::new(6, 0), (8, 0))]);
let container_shared_sort_key = std::collections::BTreeMap::from([(8, (0u8, 7u32))]);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&member_to_container,
&container_shared_sort_key,
&Default::default(),
&Default::default(),
);
let folded = plan.canonical_shared_hints(
&member_to_container,
&renumber,
&Default::default(),
&Default::default(),
);
let plain_idx = folded
.iter()
.position(|entry| {
entry.object_ref == ObjectRef::new(8, 0) && entry.referencing_pages == vec![1]
})
.expect("plain object alias is in the shared hint list") as u32;
let container_idx = folded
.iter()
.position(|entry| {
entry.object_ref == ObjectRef::new(8, u16::MAX)
&& entry.referencing_pages == vec![1]
})
.expect("folded container alias is in the shared hint list")
as u32;
let ids = &table.entries[1].shared_object_ids;
assert!(
ids.iter().position(|&id| id == plain_idx)
< ids.iter().position(|&id| id == container_idx),
"a Preserve source-key collision must keep the plain alias before its folded container"
);
}
fn two_page_plan_with_folded_container_and_post_optimization_mint() -> LinearizationPlan {
let mut plan = two_page_plan_with_shared();
let mut optimization = crate::optimization::Optimization::default();
optimization.set_pre_optimization_object_refs(
[
ObjectRef::new(3, 0),
ObjectRef::new(6, 0),
ObjectRef::new(5, 0),
ObjectRef::new(4, 0),
ObjectRef::new(7, 0),
]
.into_iter()
.collect(),
);
plan.optimization = Some(optimization);
plan
}
#[test]
fn two_page_post_optimization_mint_sorts_after_folded_container() {
let plan = two_page_plan_with_folded_container_and_post_optimization_mint();
let renumber = RenumberMap::from_plan(&plan);
let mut member_to_container = std::collections::BTreeMap::new();
member_to_container.insert(ObjectRef::new(5, 0), (12, 0));
let mut container_shared_sort_key = std::collections::BTreeMap::new();
container_shared_sort_key.insert(12, (1u8, 0u32));
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&member_to_container,
&container_shared_sort_key,
&Default::default(),
&Default::default(),
);
assert_eq!(
table.entries[1].shared_object_ids,
vec![3, 2],
"the folded container must sort before the post-optimization mint"
);
}
#[test]
fn non_page_owned_containers_use_setup_source_membership() {
let member = ObjectRef::new(7, 0);
let setup_source = ObjectRef::new(70, 0);
let plan_source = ObjectRef::new(71, 0);
let mut optimization = crate::optimization::Optimization::default();
optimization.record_for_test(crate::optimization::ObjectUser::Page(2), setup_source);
let plan = LinearizationPlan {
optimization: Some(optimization),
preserve_objstm_plan: Some(crate::writer::object_streams::ObjectStreamPlan {
groups: vec![
crate::writer::object_streams::ObjectStreamGroup::SourceBacked {
source: plan_source,
members: vec![member],
},
],
removed_refs: std::collections::BTreeSet::new(),
source_membership_present: true,
}),
..LinearizationPlan::default()
};
let member_to_container = std::collections::BTreeMap::from([(member, (99, 0))]);
let source_container_by_member =
std::collections::BTreeMap::from([(member.number, setup_source.number)]);
assert!(non_page_owned_containers(
&plan,
&member_to_container,
&source_container_by_member,
)
.is_empty());
}
#[test]
fn two_page_shared_numerators_are_zero() {
let plan = two_page_plan_with_shared();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
for entry in &table.entries {
for &num in &entry.shared_object_numerators {
assert_eq!(num, 0, "numerators must all be 0 (qpdf convention)");
}
}
}
#[test]
fn numerators_len_matches_shared_count() {
let plan = two_page_plan_with_shared();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
for entry in &table.entries {
assert_eq!(
entry.shared_object_numerators.len(),
entry.shared_object_ids.len(),
"numerators count must match shared_object_ids count"
);
}
}
#[test]
fn two_page_denominator_is_four() {
let plan = two_page_plan_with_shared();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.header.denominator, 4);
}
#[test]
fn two_page_placeholder_fields_are_zero() {
let plan = two_page_plan_with_shared();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.header.location_of_first_page, 0);
assert_eq!(table.header.least_page_length, 0);
assert_eq!(table.header.least_content_offset, 0);
assert_eq!(table.header.least_content_length, 0);
for entry in &table.entries {
assert_eq!(entry.page_length_minus_least, 0);
assert_eq!(entry.content_stream_offset, 0);
assert_eq!(entry.content_stream_length, 0);
}
}
#[test]
fn bits_shared_object_id_zero_shared_hints() {
let plan = single_page_plan();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.header.bits_shared_object_id, 0);
}
#[test]
fn bits_shared_object_id_four_shared_hints_matches_qpdf() {
let plan = two_page_plan_with_shared();
let renumber = RenumberMap::from_plan(&plan);
let table = PageOffsetHintTable::from_plan(
&plan,
&renumber,
&Default::default(),
&Default::default(),
&Default::default(),
&Default::default(),
);
assert_eq!(table.header.bits_shared_object_id, 3);
}
#[test]
fn page0_count_mixes_plain_and_packed_part3() {
let page = ObjectRef::new(3, 0);
let content = ObjectRef::new(9, 0);
let packed_a = ObjectRef::new(1, 0);
let packed_b = ObjectRef::new(2, 0);
let plain_part3 = ObjectRef::new(5, 0);
let plan = LinearizationPlan {
part2_objects: vec![page, content],
part3_objects: vec![packed_a, packed_b, plain_part3],
..Default::default()
};
let mut m2c: std::collections::BTreeMap<ObjectRef, (u32, u32)> =
std::collections::BTreeMap::new();
m2c.insert(packed_a, (12, 0));
m2c.insert(packed_b, (12, 1));
assert_eq!(
page0_object_count_with_objstm(&plan, &m2c, &Default::default(), &Default::default()),
4
);
}
#[test]
fn page0_count_includes_outline_container_when_first_page() {
let outline_ref = ObjectRef::new(10, 0);
let container_num = 99u32;
let plan = LinearizationPlan {
part2_objects: vec![ObjectRef::new(5, 0)],
outline_first_page_members: vec![outline_ref],
..Default::default()
};
let mut m2c: std::collections::BTreeMap<ObjectRef, (u32, u32)> =
std::collections::BTreeMap::new();
m2c.insert(outline_ref, (container_num, 0));
assert_eq!(
page0_object_count_with_objstm(&plan, &m2c, &Default::default(), &Default::default()),
2,
"outline container must be counted when outline_first_page_members is non-empty"
);
}
}