rpdfium_parser/

hint_tables.rs

// Derived from PDFium's cpdf_hint_tables.cpp
// Original: Copyright 2014 The PDFium Authors
// Licensed under BSD-3-Clause / Apache-2.0
// See pdfium-upstream/LICENSE for the original license.

//! Linearization hint tables -- page offset and shared object hint table parsing.
//!
//! Linearized PDFs contain hint tables that allow page-at-a-time retrieval
//! without downloading the entire file. The hint stream (referenced by the `/H`
//! array in the linearization dictionary) is a bit-packed binary structure
//! containing per-page and per-shared-object metadata.
//!
//! Reference: PDF 32000-1:2008, Annex F (Linearized PDF).

use rpdfium_core::cfx_bitstream::BitReader;

/// Per-page entry in the page offset hint table.
#[derive(Debug, Clone, Default)]
pub struct PageHintEntry {
    /// Delta from the minimum number of objects for this page.
    pub objects_delta: u32,
    /// Delta from the minimum page length for this page.
    pub length_delta: u32,
    /// Number of shared objects referenced by this page.
    pub shared_objects_count: u32,
}

/// The page offset hint table (PDF spec Annex F.3).
#[derive(Debug, Clone)]
pub struct PageOffsetHintTable {
    /// Minimum number of objects in a page.
    pub min_objects: u32,
    /// Location of first page's object (offset from start of file).
    pub first_page_offset: u64,
    /// Minimum page length in bytes.
    pub min_page_length: u32,
    /// Number of bits needed to represent difference from min objects.
    pub bits_objects_delta: u8,
    /// Number of bits needed to represent difference from min length.
    pub bits_length_delta: u8,
    /// Per-page entries.
    pub entries: Vec<PageHintEntry>,
}

/// Per-shared-object entry in the shared object hint table.
#[derive(Debug, Clone, Default)]
pub struct SharedHintEntry {
    /// Length of the shared object in bytes.
    pub length: u32,
}

/// The shared object hint table (PDF spec Annex F.4).
#[derive(Debug, Clone)]
pub struct SharedObjectHintTable {
    /// First shared object number.
    pub first_object: u32,
    /// Location of first shared object.
    pub first_offset: u64,
    /// Number of shared object entries.
    pub count: u32,
    /// Per-object entries.
    pub entries: Vec<SharedHintEntry>,
}

/// Parsed hint tables from a linearized PDF.
#[derive(Debug, Clone)]
pub struct HintTables {
    /// Page offset hint table.
    pub page_offset: PageOffsetHintTable,
    /// Optional shared object hint table.
    pub shared_objects: Option<SharedObjectHintTable>,
}

impl HintTables {
    /// Parse hint tables from the decoded hint stream data.
    ///
    /// The `page_count` must be provided from the linearization dictionary (`/N`).
    ///
    /// Returns `None` if the data is too short or malformed.
    pub fn parse(data: &[u8], page_count: u32) -> Option<Self> {
        if data.is_empty() || page_count == 0 {
            return None;
        }

        let mut reader = BitReader::new(data);

        // --- Page Offset Hint Table Header (13 fields per PDF spec F.3) ---
        // 1. Minimum number of objects in a page (32 bits)
        let min_objects = reader.read_u32()?;
        // 2. Location of first page's page object (32 bits)
        let first_page_offset_low = reader.read_u32()?;
        // 3. Number of bits needed to represent diff from min objects (16 bits)
        let bits_objects_delta = reader.read_u16()? as u8;
        // 4. Minimum page length (32 bits)
        let min_page_length = reader.read_u32()?;
        // 5. Number of bits needed to represent diff from min length (16 bits)
        let bits_length_delta = reader.read_u16()? as u8;
        // 6. Minimum offset to start of content stream (32 bits)
        let _min_content_offset = reader.read_u32()?;
        // 7. Number of bits for content stream offset delta (16 bits)
        let _bits_content_offset_delta = reader.read_u16()?;
        // 8. Minimum content stream length (32 bits)
        let _min_content_length = reader.read_u32()?;
        // 9. Number of bits for content stream length delta (16 bits)
        let _bits_content_length_delta = reader.read_u16()?;
        // 10. Number of bits for number of shared object references (16 bits)
        let bits_shared_count = reader.read_u16()? as u8;
        // 11. Number of bits for shared object identifier (16 bits)
        let _bits_shared_id = reader.read_u16()?;
        // 12. Number of bits for numerator of fractional page position (16 bits)
        let _bits_numerator = reader.read_u16()?;
        // 13. Denominator of fractional page position (16 bits)
        let _denominator = reader.read_u16()?;

        // Validate bit widths won't cause issues
        if bits_objects_delta > 32 || bits_length_delta > 32 || bits_shared_count > 32 {
            return None;
        }

        // --- Per-page entries ---
        let n = page_count as usize;
        let mut entries = Vec::with_capacity(n);

        // Item 1: objects delta for each page
        let mut objects_deltas = Vec::with_capacity(n);
        for _ in 0..n {
            objects_deltas.push(reader.read_bits(bits_objects_delta)?);
        }

        // Item 2: page length delta for each page
        let mut length_deltas = Vec::with_capacity(n);
        for _ in 0..n {
            length_deltas.push(reader.read_bits(bits_length_delta)?);
        }

        // Item 3: shared object count for each page
        let mut shared_counts = Vec::with_capacity(n);
        for _ in 0..n {
            shared_counts.push(reader.read_bits(bits_shared_count)?);
        }

        // Build per-page entries
        for i in 0..n {
            entries.push(PageHintEntry {
                objects_delta: objects_deltas[i],
                length_delta: length_deltas[i],
                shared_objects_count: shared_counts[i],
            });
        }

        let page_offset = PageOffsetHintTable {
            min_objects,
            first_page_offset: u64::from(first_page_offset_low),
            min_page_length,
            bits_objects_delta,
            bits_length_delta,
            entries,
        };

        // Align to byte boundary before shared object table
        reader.byte_align();

        // --- Shared Object Hint Table (optional, PDF spec F.4) ---
        let shared_objects = Self::parse_shared_objects(&mut reader);

        Some(HintTables {
            page_offset,
            shared_objects,
        })
    }

    /// Parse the shared object hint table from the current reader position.
    fn parse_shared_objects(reader: &mut BitReader<'_>) -> Option<SharedObjectHintTable> {
        // Check if there's enough data remaining for the header (3×u32 + 1×u16 = 112 bits)
        if reader.bits_remaining() < 32 * 3 + 16 {
            return None;
        }

        // 1. First shared object number (32 bits)
        let first_object = reader.read_u32()?;
        // 2. Location of first shared object (32 bits)
        let first_offset_low = reader.read_u32()?;
        // 3. Number of shared object entries (32 bits)
        let count = reader.read_u32()?;
        // 4. Number of bits for object length (16 bits)
        let bits_length = reader.read_u16()? as u8;

        if bits_length > 32 {
            return None;
        }

        // Safety limit on count
        if count > rpdfium_core::fx_system::MAX_OBJECT_NUMBER {
            return None;
        }

        let mut entries = Vec::with_capacity(count as usize);
        for _ in 0..count {
            let length = reader.read_bits(bits_length)?;
            entries.push(SharedHintEntry { length });
        }

        Some(SharedObjectHintTable {
            first_object,
            first_offset: u64::from(first_offset_low),
            count,
            entries,
        })
    }

    /// Calculate the byte range (offset, length) for a given page index.
    ///
    /// Returns `None` if the page index is out of range.
    pub fn page_byte_range(&self, page: usize) -> Option<(u64, u32)> {
        let entry = self.page_offset.entries.get(page)?;
        let page_length = self.page_offset.min_page_length + entry.length_delta;

        // Calculate offset: first page offset + sum of all preceding page lengths
        let mut offset = self.page_offset.first_page_offset;
        for i in 0..page {
            let prev = &self.page_offset.entries[i];
            offset += u64::from(self.page_offset.min_page_length + prev.length_delta);
        }

        Some((offset, page_length))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_hint_tables_parse_with_constructed_data() {
        // Build a minimal hint stream: 2 pages, no shared objects
        let mut bits = Vec::new();

        // Page Offset Header (13 fields):
        // 1. min_objects = 3 (32 bits)
        push_u32(&mut bits, 3);
        // 2. first_page_offset = 1000 (32 bits)
        push_u32(&mut bits, 1000);
        // 3. bits_objects_delta = 2 (16 bits)
        push_u16(&mut bits, 2);
        // 4. min_page_length = 500 (32 bits)
        push_u32(&mut bits, 500);
        // 5. bits_length_delta = 4 (16 bits)
        push_u16(&mut bits, 4);
        // 6. min_content_offset = 100 (32 bits)
        push_u32(&mut bits, 100);
        // 7. bits_content_offset_delta = 0 (16 bits)
        push_u16(&mut bits, 0);
        // 8. min_content_length = 200 (32 bits)
        push_u32(&mut bits, 200);
        // 9. bits_content_length_delta = 0 (16 bits)
        push_u16(&mut bits, 0);
        // 10. bits_shared_count = 1 (16 bits)
        push_u16(&mut bits, 1);
        // 11. bits_shared_id = 0 (16 bits)
        push_u16(&mut bits, 0);
        // 12. bits_numerator = 0 (16 bits)
        push_u16(&mut bits, 0);
        // 13. denominator = 1 (16 bits)
        push_u16(&mut bits, 1);

        // Per-page items for 2 pages:
        // Item 1: objects_delta (2 bits each)
        push_bits(&mut bits, 1, 2); // page 0: delta=1
        push_bits(&mut bits, 2, 2); // page 1: delta=2

        // Item 2: length_delta (4 bits each)
        push_bits(&mut bits, 5, 4); // page 0: delta=5
        push_bits(&mut bits, 10, 4); // page 1: delta=10

        // Item 3: shared_objects_count (1 bit each)
        push_bits(&mut bits, 0, 1); // page 0: 0 shared
        push_bits(&mut bits, 1, 1); // page 1: 1 shared

        let data = bits_to_bytes(&bits);
        let tables = HintTables::parse(&data, 2).unwrap();

        assert_eq!(tables.page_offset.min_objects, 3);
        assert_eq!(tables.page_offset.first_page_offset, 1000);
        assert_eq!(tables.page_offset.min_page_length, 500);
        assert_eq!(tables.page_offset.bits_objects_delta, 2);
        assert_eq!(tables.page_offset.bits_length_delta, 4);
        assert_eq!(tables.page_offset.entries.len(), 2);

        assert_eq!(tables.page_offset.entries[0].objects_delta, 1);
        assert_eq!(tables.page_offset.entries[0].length_delta, 5);
        assert_eq!(tables.page_offset.entries[0].shared_objects_count, 0);

        assert_eq!(tables.page_offset.entries[1].objects_delta, 2);
        assert_eq!(tables.page_offset.entries[1].length_delta, 10);
        assert_eq!(tables.page_offset.entries[1].shared_objects_count, 1);
    }

    #[test]
    fn test_page_byte_range_calculation() {
        let tables = HintTables {
            page_offset: PageOffsetHintTable {
                min_objects: 3,
                first_page_offset: 1000,
                min_page_length: 500,
                bits_objects_delta: 0,
                bits_length_delta: 0,
                entries: vec![
                    PageHintEntry {
                        objects_delta: 0,
                        length_delta: 100, // page 0: 600 bytes
                        shared_objects_count: 0,
                    },
                    PageHintEntry {
                        objects_delta: 0,
                        length_delta: 200, // page 1: 700 bytes
                        shared_objects_count: 0,
                    },
                    PageHintEntry {
                        objects_delta: 0,
                        length_delta: 0, // page 2: 500 bytes
                        shared_objects_count: 0,
                    },
                ],
            },
            shared_objects: None,
        };

        // Page 0: offset=1000, length=600
        let (offset, len) = tables.page_byte_range(0).unwrap();
        assert_eq!(offset, 1000);
        assert_eq!(len, 600);

        // Page 1: offset=1000+600=1600, length=700
        let (offset, len) = tables.page_byte_range(1).unwrap();
        assert_eq!(offset, 1600);
        assert_eq!(len, 700);

        // Page 2: offset=1600+700=2300, length=500
        let (offset, len) = tables.page_byte_range(2).unwrap();
        assert_eq!(offset, 2300);
        assert_eq!(len, 500);

        // Out of range
        assert!(tables.page_byte_range(3).is_none());
    }

    #[test]
    fn test_empty_hint_stream_returns_none() {
        assert!(HintTables::parse(&[], 1).is_none());
    }

    #[test]
    fn test_zero_page_count_returns_none() {
        let data = [0u8; 100];
        assert!(HintTables::parse(&data, 0).is_none());
    }

    #[test]
    fn test_truncated_hint_stream_returns_none() {
        // Not enough data for the 13-field header
        let data = [0u8; 10];
        assert!(HintTables::parse(&data, 1).is_none());
    }

    // -----------------------------------------------------------------------
    // Test helpers for constructing bit-packed data
    // -----------------------------------------------------------------------

    fn push_u32(bits: &mut Vec<u8>, value: u32) {
        for i in (0..32).rev() {
            bits.push(((value >> i) & 1) as u8);
        }
    }

    fn push_u16(bits: &mut Vec<u8>, value: u16) {
        for i in (0..16).rev() {
            bits.push(((value >> i) & 1) as u8);
        }
    }

    fn push_bits(bits: &mut Vec<u8>, value: u32, count: u8) {
        for i in (0..count).rev() {
            bits.push(((value >> i) & 1) as u8);
        }
    }

    /// Convert a vector of individual bits (0 or 1) into packed bytes.
    fn bits_to_bytes(bits: &[u8]) -> Vec<u8> {
        let mut bytes = Vec::new();
        for chunk in bits.chunks(8) {
            let mut byte = 0u8;
            for (i, &bit) in chunk.iter().enumerate() {
                byte |= bit << (7 - i);
            }
            bytes.push(byte);
        }
        bytes
    }
}