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)>,
) -> std::collections::BTreeSet<u32> {
use std::collections::{BTreeMap, BTreeSet};
let page_private_sets: Vec<BTreeSet<ObjectRef>> = plan
.per_page_private_objects
.iter()
.map(|v| v.iter().copied().collect())
.collect();
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 (1..page_private_sets.len()).find(|&i| page_private_sets[i].contains(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_rank: &std::collections::BTreeMap<u32, u32>,
second_half_container_nums: &std::collections::BTreeSet<u32>,
open_document_container_nums: &std::collections::BTreeSet<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_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,
);
let non_page_owned = non_page_owned_containers(plan, member_to_container);
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);
}
}
}
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_ref,
page_idx,
page_count
);
shared_counts[idx] += 1;
shared_ids_per_page[idx].push(shared_idx as u32);
}
}
let shared_sort_key = |shared_idx: u32| -> (u8, u32) {
let entry = &shared_hints[shared_idx as usize];
if entry.object_ref.generation == u16::MAX {
(
1,
container_shared_rank
.get(&entry.object_ref.number)
.copied()
.unwrap_or(0),
)
} else {
(0, entry.object_ref.number)
}
};
for ids in &mut shared_ids_per_page {
ids.sort_by_key(|&shared_idx| shared_sort_key(shared_idx));
}
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, SharedObjectHintEntry};
use crate::linearization::renumber::RenumberMap;
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 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"
);
}
#[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"
);
}
}