use super::plan::LinearizationPlan;
use super::renumber::RenumberMap;
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>,
}
impl PageOffsetHintTable {
pub fn from_plan(plan: &LinearizationPlan, _renumber: &RenumberMap) -> 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 object_counts: Vec<u32> = plan.page_hints.iter().map(|h| h.object_count).collect();
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 plan.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 greatest_shared_count = shared_counts.iter().copied().max().unwrap_or(0);
let greatest_shared_id = plan.shared_hints.len().saturating_sub(1) 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(greatest_shared_id),
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);
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);
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);
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);
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);
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);
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);
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);
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);
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);
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);
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);
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);
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);
assert_eq!(table.header.bits_shared_object_id, 2);
}
#[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);
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);
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);
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);
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);
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);
}
}
}