Files
craft-libs/crates/prc/src/arrays.rs
Dylan M. Taylor 7db4645d1f Add craft-prc: the PRC 3D model reader from PdfCraft (#945)
PdfCraft's pdfcraft-prc crate (revision
80e26e674d1aa33078e83c8139875047f3289eb6), moved whole with its tests. It reads
PRC (ISO 14739-1), the model format of PDF 3D annotations: the container, the
bit-level primitives, the schema, tessellations and the product tree.

The code is unchanged. The package and its README are renamed, the doctests
and tests import craft_prc, and the Double code table taken from prc-rs (MIT)
has its row in ATTRIBUTION.md and its licence in licenses/prc-rs.
2026-11-11 18:55:20 -05:00

421 lines
16 KiB
Rust

//! The array primitives of compressed tessellation [WD 11.6-11.9] and the Huffman payload
//! they may carry [WD 12.2].
//!
//! The WD gives only the Huffman writer. The reader decodes what producers write: each
//! leaf's code length is read in the width the payload's 8-bit field states (the WD writes a
//! fixed 8 bits), stored codes carry a leading root bit, and the payload is read LSB-first
//! although the stream around it is MSB-first.
use std::collections::HashMap;
use crate::PrcError;
use crate::bits::BitReader;
/// Longest Huffman code [WD 12.2].
const MAX_CODE_BITS: u32 = 32;
/// Widest Huffman symbol a caller asks for: the arrays hold 2- to 16-bit values.
const MAX_SYMBOL_BITS: u32 = 16;
fn malformed(what: &str) -> PrcError {
PrcError::Malformed(what.to_owned())
}
/// An LSB-first cursor over a Huffman payload.
struct Lsb<'a> {
data: &'a [u8],
pos: usize,
end: usize,
}
impl Lsb<'_> {
fn bit(&mut self) -> Result<u32, PrcError> {
if self.pos >= self.end {
return Err(PrcError::Truncated("a Huffman payload"));
}
let byte = self.data.get(self.pos / 8).ok_or(PrcError::Truncated("a Huffman payload"))?;
let b = u32::from((byte >> (self.pos % 8)) & 1);
self.pos += 1;
Ok(b)
}
/// `n` ≤ 32 bits, the first read being the least significant.
fn bits(&mut self, n: u32) -> Result<u32, PrcError> {
let mut v = 0u32;
for i in 0..n.min(32) {
v |= self.bit()? << i;
}
Ok(v)
}
fn remaining(&self) -> usize {
self.end.saturating_sub(self.pos)
}
}
/// The low `n` (1..=16) bits of `v` as a symbol, two's complement when `signed`.
fn symbol(v: u32, n: u32, signed: bool) -> i32 {
let v = i64::from(v);
let wide = if signed && n > 0 && v & (1 << (n - 1)) != 0 { v - (1i64 << n) } else { v };
// n <= 16, so `wide` is within ±2^16.
i32::try_from(wide).unwrap_or(0)
}
/// The Huffman container of a compressed Character/Short array [WD 11.6, 11.7, 12.2]:
/// symbols are `nbits` wide, sign-extended when `signed`.
fn huffman(r: &mut BitReader<'_>, nbits: u32, signed: bool) -> Result<Vec<i32>, PrcError> {
if nbits == 0 || nbits > MAX_SYMBOL_BITS {
return Err(malformed("Huffman symbol width"));
}
let words = r.unsigned_integer()? as usize;
if words == 0 {
return Ok(Vec::new());
}
if words.saturating_mul(32) > r.remaining() {
return Err(PrcError::Truncated("a Huffman payload"));
}
// words * 32 bits remain, so words * 4 bytes cannot overflow.
let blob = (0..words * 4).map(|_| r.character()).collect::<Result<Vec<u8>, _>>()?;
let last = r.unsigned_integer()?;
if last > 32 {
return Err(malformed("Huffman last-word bit count above 32"));
}
let end = (words - 1) * 32 + last as usize;
let mut b = Lsb { data: &blob, pos: 0, end };
let codes = huffman_leaves(&mut b, nbits, signed)?;
if codes.is_empty() {
return Ok(Vec::new());
}
let count = b.bits(32)? as usize;
// Every element is at least one bit.
if count > b.remaining() {
return Err(PrcError::Truncated("a Huffman element count"));
}
r.take_elements(count)?;
let mut out = Vec::with_capacity(count.min(1024));
for _ in 0..count {
out.push(huffman_symbol(&mut b, &codes)?);
}
Ok(out)
}
/// The leaf table: `(code length, stored code)` to symbol.
fn huffman_leaves(b: &mut Lsb<'_>, nbits: u32, signed: bool) -> Result<HashMap<(u32, u32), i32>, PrcError> {
let leaves = b.bits(nbits + 1)?;
if leaves == 0 {
return Ok(HashMap::new());
}
// prc-rs: the code-length width is read from the payload, not fixed at 8 bits.
let len_width = b.bits(8)?;
if len_width == 0 || len_width > MAX_CODE_BITS {
return Err(malformed("Huffman code-length width"));
}
// Every leaf is at least nbits + 2 bits, so the payload bounds the table.
if (leaves as usize).saturating_mul((nbits + 2) as usize) > b.remaining() {
return Err(PrcError::Truncated("a Huffman payload"));
}
let mut codes = HashMap::new();
for _ in 0..leaves {
let s = symbol(b.bits(nbits)?, nbits, signed);
let len = b.bits(len_width)?;
if len == 0 || len > MAX_CODE_BITS {
return Err(malformed("Huffman code length"));
}
let code = b.bits(len)?;
if codes.insert((len, code), s).is_some() {
return Err(malformed("duplicate Huffman code"));
}
}
// A leaf whose code begins another's would end that code early, leaving its unread bits
// in front of the next element.
let shadowed = codes.keys().any(|&(len, code)| (1..len).any(|l| codes.contains_key(&(l, code >> (len - l)))));
if shadowed {
return Err(malformed("a Huffman code that is a prefix of another"));
}
Ok(codes)
}
/// One element: code bits, most significant first, until a leaf matches.
fn huffman_symbol(b: &mut Lsb<'_>, codes: &HashMap<(u32, u32), i32>) -> Result<i32, PrcError> {
// prc-rs: the stored code's first bit read is its most significant (the root bit).
let (mut code, mut len) = (0u32, 0u32);
while len < MAX_CODE_BITS {
code = (code << 1) | b.bit()?;
len += 1;
if let Some(&s) = codes.get(&(len, code)) {
return Ok(s);
}
}
Err(malformed("a Huffman code matching no leaf"))
}
/// A `CharacterArray(nbits)` [WD 11.6]. `compressed` is `None` when the flag is written,
/// else the caller's implicit value. Uncompressed elements are whole bytes, sign-extended
/// from 8 bits when `signed`.
pub(crate) fn character_array(r: &mut BitReader<'_>, nbits: u32, compressed: Option<bool>, signed: bool) -> Result<Vec<i32>, PrcError> {
let compressed = match compressed {
Some(c) => c,
None => r.bit()?,
};
if compressed {
return huffman(r, nbits, signed);
}
let n = r.unsigned_integer()? as usize;
if n.saturating_mul(8) > r.remaining() {
return Err(PrcError::Truncated("a character array"));
}
r.take_elements(n)?;
(0..n)
.map(|_| {
let c = r.character()?;
Ok(if signed { i32::from(c.cast_signed()) } else { i32::from(c) })
})
.collect()
}
/// A `ShortArray(nbits)` [WD 11.7]: uncompressed elements are a low then a high byte, read
/// unsigned.
pub(crate) fn short_array(r: &mut BitReader<'_>, nbits: u32) -> Result<Vec<i32>, PrcError> {
if r.bit()? {
return huffman(r, nbits, false);
}
let n = r.unsigned_integer()? as usize;
if n.saturating_mul(16) > r.remaining() {
return Err(PrcError::Truncated("a short array"));
}
r.take_elements(n)?;
(0..n)
.map(|_| {
let lo = r.character()?;
let hi = r.character()?;
Ok(i32::from(u16::from_le_bytes([lo, hi])))
})
.collect()
}
/// A `CompressedIntegerArray` [WD 11.8]: a CharacterArray(6) of widths, then one
/// `IntegerWithVariableBitNumber` per width.
pub(crate) fn compressed_integer_array(r: &mut BitReader<'_>) -> Result<Vec<i64>, PrcError> {
let widths = character_array(r, 6, None, false)?;
widths
.into_iter()
.map(|w| {
let w = u32::try_from(w).map_err(|_| malformed("integer width"))?;
r.integer_vbn(w)
})
.collect()
}
/// A `CompressedIndiceArray` [WD 11.9], read as producers write it: the stored signed 6-bit
/// values are width differences summed into each element's width, and each element is a
/// delta from the previous (the WD's own reading desyncs from the third element). Indices
/// are never negative.
pub(crate) fn compressed_indice_array(r: &mut BitReader<'_>, compressed: Option<bool>) -> Result<Vec<u32>, PrcError> {
let diffs = character_array(r, 6, compressed, true)?;
let mut out = Vec::with_capacity(diffs.len());
let (mut width, mut prev) = (0i64, 0i64);
for d in diffs {
// prc-rs: widths are running sums of the stored differences, values running deltas.
width = width.checked_add(i64::from(d)).ok_or_else(|| malformed("indice width"))?;
let w = u32::try_from(width).map_err(|_| malformed("indice width"))?;
let v = prev.checked_add(r.integer_vbn(w)?).ok_or_else(|| malformed("indice delta"))?;
out.push(u32::try_from(v).map_err(|_| malformed("an index outside 0..2^32"))?);
prev = v;
}
Ok(out)
}
/// An `UncompressedBoolArray` of `n` raw bits (no length prefix).
pub(crate) fn bool_array(r: &mut BitReader<'_>, n: usize) -> Result<Vec<bool>, PrcError> {
if n > r.remaining() {
return Err(PrcError::Truncated("a boolean array"));
}
r.take_elements(n)?;
(0..n).map(|_| r.bit()).collect()
}
#[cfg(test)]
mod tests {
#![allow(clippy::unwrap_used)]
use super::*;
use crate::testw::W;
fn read<T>(w: &W, f: impl FnOnce(&mut BitReader<'_>) -> Result<T, PrcError>) -> T {
let bytes = w.bytes();
let mut r = BitReader::new(&bytes);
let v = f(&mut r).unwrap();
assert_eq!(r.position(), w.len(), "bits consumed");
v
}
#[test]
fn huffman_decodes_the_wd_example_with_root_bits() {
// WD 12.2's input {1,3,5,7,7,9,5,3,3}; codes carry the root bit.
let leaves = [(3, 0b100, 3), (7, 0b101, 3), (5, 0b110, 3), (1, 0b1110, 4), (9, 0b1111, 4)];
let values = [1, 3, 5, 7, 7, 9, 5, 3, 3];
let mut w = W::default();
w.bit(true).huffman(4, 3, &leaves, &values);
assert_eq!(read(&w, |r| character_array(r, 4, None, false)), values);
}
#[test]
fn huffman_symbols_sign_extend_only_when_signed() {
let leaves = [(0b111110, 0b10, 2), (1, 0b11, 2)];
let mut w = W::default();
w.huffman(6, 2, &leaves, &[62, 1, 62]);
assert_eq!(read(&w, |r| huffman(r, 6, true)), [-2, 1, -2]);
assert_eq!(read(&w, |r| huffman(r, 6, false)), [62, 1, 62]);
}
#[test]
fn huffman_rejects_codes_that_match_no_leaf_and_empty_payloads_are_empty() {
let mut bad = W::default();
bad.huffman_raw(2, 2, &[(1, 0b10, 2)], &[(0b11, 2)]);
let bytes = bad.bytes();
assert!(matches!(huffman(&mut BitReader::new(&bytes), 2, false), Err(PrcError::Malformed(_) | PrcError::Truncated(_))));
let mut empty = W::default();
empty.uint(0);
assert!(read(&empty, |r| huffman(r, 2, false)).is_empty());
}
#[test]
fn a_huffman_element_count_past_the_payload_is_truncated_not_allocated() {
// One leaf, then an element count of 2^32 - 1 with no elements behind it.
let mut w = W::default();
w.huffman_count(2, 2, &[(1, 0b10, 2)], u32::MAX);
let bytes = w.bytes();
assert!(matches!(huffman(&mut BitReader::new(&bytes), 2, false), Err(PrcError::Truncated("a Huffman element count"))));
}
#[test]
fn a_huffman_code_that_begins_another_is_malformed() {
// `10` would end every `100` one bit early.
let mut w = W::default();
w.huffman(2, 2, &[(1, 0b10, 2), (2, 0b100, 3)], &[2, 1]);
let bytes = w.bytes();
let r = huffman(&mut BitReader::new(&bytes), 2, false);
assert!(malformed_by(r, "a Huffman code that is a prefix of another"));
}
#[test]
fn huffman_widths_out_of_range_are_errors() {
// Well-formed payloads at each width, which only the width check refuses.
for nbits in [0, 17] {
let mut w = W::default();
w.huffman(nbits, 2, &[(1, 0b10, 2)], &[1]);
let bytes = w.bytes();
assert!(matches!(huffman(&mut BitReader::new(&bytes), nbits, false), Err(PrcError::Malformed(_))), "{nbits}");
}
}
#[test]
fn uncompressed_arrays() {
let mut w = W::default();
w.bit(false).uint(2).put(0xfe, 8).put(3, 8);
assert_eq!(read(&w, |r| character_array(r, 6, None, true)), [-2, 3]);
let mut s = W::default();
s.bit(false).uint(1).put(0x34, 8).put(0x12, 8);
assert_eq!(read(&s, |r| short_array(r, 16)), [0x1234]);
}
#[test]
fn integer_array_reads_one_width_per_value() {
let mut w = W::default();
w.bit(false).uint(3).put(3, 8).put(0, 8).put(4, 8);
w.bit(true).put(3, 2); // -3 in 3 bits
w.bit(false).put(5, 3); // 5 in 4 bits
assert_eq!(read(&w, compressed_integer_array), [-3, 0, 5]);
}
#[test]
fn indice_array_sums_widths_and_deltas() {
// Values 5, 6, 4: widths 4, 2, 3 stored as diffs 4, -2, +1.
let mut w = W::default();
w.bit(false).uint(3).put(4, 8).put(0xfe, 8).put(1, 8);
w.bit(false).put(5, 3); // 5
w.bit(false).put(1, 1); // +1
w.bit(true).put(2, 2); // -2
assert_eq!(read(&w, |r| compressed_indice_array(r, None)), [5, 6, 4]);
// The implicit-flag form reads no flag bit.
let mut i = W::default();
i.uint(1).put(2, 8).bit(false).put(1, 1);
assert_eq!(read(&i, |r| compressed_indice_array(r, Some(false))), [1]);
// A negative running index is damage.
let mut n = W::default();
n.bit(false).uint(1).put(2, 8).bit(true).put(1, 1);
let bytes = n.bytes();
assert!(compressed_indice_array(&mut BitReader::new(&bytes), None).is_err());
}
#[test]
fn a_bool_array_longer_than_the_data_is_truncated() {
assert!(matches!(bool_array(&mut BitReader::new(&[0]), 9), Err(PrcError::Truncated(_))));
assert_eq!(bool_array(&mut BitReader::new(&[0x80]), 2).unwrap(), [true, false]);
}
#[test]
fn decoded_elements_are_charged_against_one_allowance() {
// One bit can decode to a 4-byte element, so the byte cap alone does not bound memory.
let leaves = [(0b111110, 0b10, 2), (1, 0b11, 2)];
let mut w = W::default();
w.huffman(6, 2, &leaves, &[62, 1, 62]);
let bytes = w.bytes();
let mut r = BitReader::with_elements(&bytes, 2);
assert!(matches!(huffman(&mut r, 6, false), Err(PrcError::TooManyElements { .. })));
let mut r = BitReader::with_elements(&bytes, 4);
assert_eq!(huffman(&mut r, 6, false).unwrap(), [62, 1, 62]);
assert_eq!(r.elements_left(), 1);
assert!(matches!(bool_array(&mut BitReader::with_elements(&[0], 1), 2), Err(PrcError::TooManyElements { .. })));
}
/// Uncompressed character and short arrays are charged against the allowance too, and a
/// character count past the data is refused by name before anything is read.
#[test]
fn uncompressed_arrays_are_charged_and_their_counts_checked() {
let mut w = W::default();
w.uint(3).put(0, 8).put(1, 8).put(2, 8);
let chars = w.bytes();
let read = |n| character_array(&mut BitReader::with_elements(&chars, n), 8, Some(false), false);
assert!(matches!(read(2), Err(PrcError::TooManyElements { .. })));
assert_eq!(read(3).unwrap(), [0, 1, 2]);
let mut w = W::default();
w.bit(false).uint(2).put(1, 8).put(0, 8).put(2, 8).put(0, 8);
let shorts = w.bytes();
assert!(matches!(short_array(&mut BitReader::with_elements(&shorts, 1), 8), Err(PrcError::TooManyElements { .. })));
assert_eq!(short_array(&mut BitReader::with_elements(&shorts, 2), 8).unwrap(), [1, 2]);
let mut w = W::default();
w.uint(1000).put(7, 8);
let short_of_data = w.bytes();
let res = character_array(&mut BitReader::new(&short_of_data), 8, Some(false), false);
assert!(matches!(res, Err(PrcError::Truncated("a character array"))), "{res:?}");
}
fn malformed_by(res: Result<Vec<i32>, PrcError>, what: &str) -> bool {
matches!(res, Err(PrcError::Malformed(m)) if m == what)
}
#[test]
fn a_zero_code_length_width_or_length_is_refused_by_name() {
let mut w = W::default();
w.huffman_raw(2, 0, &[(1, 0, 0)], &[]);
let bytes = w.bytes();
assert!(malformed_by(huffman(&mut BitReader::new(&bytes), 2, false), "Huffman code-length width"));
let mut w = W::default();
w.huffman_raw(2, 2, &[(1, 0, 0)], &[]);
let bytes = w.bytes();
assert!(malformed_by(huffman(&mut BitReader::new(&bytes), 2, false), "Huffman code length"));
}
#[test]
fn a_boolean_array_past_the_data_is_refused_before_it_is_read() {
let mut w = W::default();
w.put(0b1011, 4);
let bytes = w.bytes();
let mut r = BitReader::new(&bytes);
let n = r.remaining() + 1;
assert_eq!(bool_array(&mut r, n), Err(PrcError::Truncated("a boolean array")));
assert_eq!(r.position(), 0, "nothing read");
}
}