Skip to main content

pdf2/
filter.rs

1//! Stream filters (§7.4): Flate, LZW, ASCIIHex, ASCII85, RunLength and the
2//! predictor functions that Flate/LZW payloads may be wrapped in.
3//!
4//! Decoding is pure: [`decode_chain`] takes bytes and returns bytes, so a
5//! filter can be tested without a document. Resolving indirect `/Filter`,
6//! `/DecodeParms` or `/Length` entries is [`crate::Document`]'s job.
7
8use alloc::vec;
9use alloc::vec::Vec;
10
11use miniz_oxide::inflate::stream::{InflateState, inflate};
12use miniz_oxide::{DataFormat, MZFlush, MZStatus};
13
14use crate::error::{Error, Result};
15use crate::lexer::{hex_value, is_whitespace};
16use crate::object::{Dictionary, Object, Stream};
17
18/// A filter named by `/Filter`.
19#[derive(Debug, Clone, Copy, PartialEq, Eq)]
20pub enum Filter {
21    /// `/FlateDecode` — zlib-wrapped DEFLATE.
22    FlateDecode,
23    /// `/LZWDecode` — LZW with variable code width.
24    LzwDecode,
25    /// `/ASCIIHexDecode` — hex digits, `>` terminates.
26    AsciiHexDecode,
27    /// `/ASCII85Decode` — base-85, `~>` terminates.
28    Ascii85Decode,
29    /// `/RunLengthDecode` — literal and repeat runs.
30    RunLengthDecode,
31}
32
33impl Filter {
34    /// Map a `/Filter` name to a filter.
35    pub fn from_name(name: &[u8]) -> Result<Self> {
36        match name {
37            b"FlateDecode" | b"Fl" => Ok(Self::FlateDecode),
38            b"LZWDecode" | b"LZW" => Ok(Self::LzwDecode),
39            b"ASCIIHexDecode" | b"AHx" => Ok(Self::AsciiHexDecode),
40            b"ASCII85Decode" | b"A85" => Ok(Self::Ascii85Decode),
41            b"RunLengthDecode" | b"RL" => Ok(Self::RunLengthDecode),
42            other => Err(Error::Malformed {
43                what: match other {
44                    b"CCITTFaxDecode" | b"DCTDecode" | b"JPXDecode" | b"JBIG2Decode" => {
45                        "image filters are out of scope"
46                    }
47                    b"Crypt" => "the /Crypt filter is Q9's job",
48                    _ => "unknown /Filter name",
49                },
50                offset: None,
51            }),
52        }
53    }
54
55    /// The canonical `/Filter` name.
56    pub fn name(self) -> &'static str {
57        match self {
58            Self::FlateDecode => "FlateDecode",
59            Self::LzwDecode => "LZWDecode",
60            Self::AsciiHexDecode => "ASCIIHexDecode",
61            Self::Ascii85Decode => "ASCII85Decode",
62            Self::RunLengthDecode => "RunLengthDecode",
63        }
64    }
65}
66
67/// One entry of the filter chain: the filter plus its `/DecodeParms`.
68#[derive(Debug, Clone, PartialEq)]
69pub struct FilterSpec {
70    /// The filter to apply.
71    pub filter: Filter,
72    /// The dictionary from `/DecodeParms` for this filter, if any.
73    pub parms: Option<Dictionary>,
74}
75
76impl FilterSpec {
77    /// Read `/Filter` and `/DecodeParms` from a stream dictionary.
78    ///
79    /// Only direct values are followed; an indirect `/Filter` or
80    /// `/DecodeParms` needs [`crate::Document::decode_stream`] to resolve it
81    /// first.
82    pub fn from_dict(dict: &Dictionary) -> Result<Vec<Self>> {
83        let filters = match dict.get(b"Filter") {
84            None | Some(Object::Null) => return Ok(Vec::new()),
85            Some(Object::Name(name)) => vec![Filter::from_name(name)?],
86            Some(Object::Array(items)) => items
87                .iter()
88                .map(|item| match item {
89                    Object::Name(name) => Filter::from_name(name),
90                    _ => Err(Error::Malformed {
91                        what: "/Filter array entries must be names",
92                        offset: None,
93                    }),
94                })
95                .collect::<Result<Vec<_>>>()?,
96            Some(Object::Reference(_)) => {
97                return Err(Error::Malformed {
98                    what: "indirect /Filter needs the document",
99                    offset: None,
100                });
101            }
102            Some(_) => {
103                return Err(Error::Malformed {
104                    what: "/Filter must be a name or an array of names",
105                    offset: None,
106                });
107            }
108        };
109        let parms = match dict.get(b"DecodeParms") {
110            None | Some(Object::Null) => Vec::new(),
111            Some(Object::Dictionary(parms)) => vec![Some(parms.clone())],
112            Some(Object::Array(items)) => items
113                .iter()
114                .map(|item| match item {
115                    Object::Null => Ok(None),
116                    Object::Dictionary(parms) => Ok(Some(parms.clone())),
117                    _ => Err(Error::Malformed {
118                        what: "/DecodeParms array entries must be dictionaries or null",
119                        offset: None,
120                    }),
121                })
122                .collect::<Result<Vec<_>>>()?,
123            Some(Object::Reference(_)) => {
124                return Err(Error::Malformed {
125                    what: "indirect /DecodeParms needs the document",
126                    offset: None,
127                });
128            }
129            Some(_) => {
130                return Err(Error::Malformed {
131                    what: "/DecodeParms must be a dictionary or an array",
132                    offset: None,
133                });
134            }
135        };
136        Ok(filters
137            .into_iter()
138            .enumerate()
139            .map(|(index, filter)| FilterSpec {
140                filter,
141                parms: parms.get(index).cloned().flatten(),
142            })
143            .collect())
144    }
145}
146
147/// The most bytes one stream may decode to, unless a document sets another
148/// budget ([`crate::Document::set_decoded_limit`]).
149///
150/// 256 MiB, chosen to match mupdf's `FZ_STORE_DEFAULT` rather than invented:
151/// real files are orders of magnitude below it, and a decompression bomb is
152/// orders of magnitude above. Without a cap a 1 MiB file expands to a gigabyte
153/// (measured: 0.43 s into 1 073 741 824 bytes), which in a browser tab is a
154/// denial of service rather than a rendering failure.
155pub const DEFAULT_DECODE_LIMIT: usize = 256 << 20;
156
157/// Apply a filter chain in order: the first `/Filter` is the outermost.
158pub fn decode_chain(data: &[u8], chain: &[FilterSpec]) -> Result<Vec<u8>> {
159    decode_chain_with_limit(data, chain, DEFAULT_DECODE_LIMIT)
160}
161
162/// Apply a filter chain with an explicit byte budget on its output.
163pub fn decode_chain_with_limit(data: &[u8], chain: &[FilterSpec], limit: usize) -> Result<Vec<u8>> {
164    if data.len() > limit {
165        return Err(Error::Limit {
166            what: "the unfiltered stream",
167            limit,
168        });
169    }
170    let mut current = data.to_vec();
171    for spec in chain {
172        current = decode_filter_with_limit(spec.filter, &current, spec.parms.as_ref(), limit)?;
173    }
174    Ok(current)
175}
176
177/// Apply one filter, then its predictor when the filter has one.
178pub fn decode_filter(filter: Filter, data: &[u8], parms: Option<&Dictionary>) -> Result<Vec<u8>> {
179    decode_filter_with_limit(filter, data, parms, DEFAULT_DECODE_LIMIT)
180}
181
182/// Apply one filter under a byte budget, then its predictor under the same one.
183///
184/// Flate is capped *while* inflating; the other filters
185/// expand by a bounded factor and are checked once they return, so the budget
186/// still refuses them before the result reaches a caller.
187pub fn decode_filter_with_limit(
188    filter: Filter,
189    data: &[u8],
190    parms: Option<&Dictionary>,
191    limit: usize,
192) -> Result<Vec<u8>> {
193    let decoded = match filter {
194        Filter::FlateDecode => flate_decode(data, limit)?,
195        Filter::LzwDecode => lzw_decode(data, early_change(parms)?)?,
196        Filter::AsciiHexDecode => ascii_hex_decode(data)?,
197        Filter::Ascii85Decode => ascii85_decode(data)?,
198        Filter::RunLengthDecode => run_length_decode(data)?,
199    };
200    if decoded.len() > limit {
201        return Err(Error::Limit {
202            what: filter.name(),
203            limit,
204        });
205    }
206    match filter {
207        Filter::FlateDecode | Filter::LzwDecode => {
208            let predictor = Predictor::from_dict(parms)?;
209            let expanded = apply_predictor(&decoded, predictor)?;
210            if expanded.len() > limit {
211                return Err(Error::Limit {
212                    what: filter.name(),
213                    limit,
214                });
215            }
216            Ok(expanded)
217        }
218        _ => Ok(decoded),
219    }
220}
221
222/// `/CCITTFaxDecode`: the parameters live in `/DecodeParms` (7.4.6).
223pub(crate) fn fax_decode(data: &[u8], parms: Option<&Dictionary>, limit: usize) -> Result<Vec<u8>> {
224    let mut params = crate::fax::Params::default();
225    if let Some(dict) = parms {
226        if let Some(k) = dict.get(b"K").and_then(Object::as_integer) {
227            params.k = k;
228        }
229        if let Some(columns) = dict.get(b"Columns").and_then(Object::as_integer) {
230            params.columns = u32::try_from(columns)
231                .map_err(|_| Error::malformed("fax /Columns must not be negative"))?;
232        }
233        if let Some(rows) = dict.get(b"Rows").and_then(Object::as_integer) {
234            params.rows = u32::try_from(rows)
235                .map_err(|_| Error::malformed("fax /Rows must not be negative"))?;
236        }
237        params.end_of_line = flag(dict, b"EndOfLine");
238        params.encoded_byte_align = flag(dict, b"EncodedByteAlign");
239        params.end_of_block = match dict.get(b"EndOfBlock") {
240            Some(Object::Boolean(value)) => *value,
241            _ => true,
242        };
243        params.black_is_1 = flag(dict, b"BlackIs1");
244    }
245    crate::fax::decode(data, &params, limit)
246}
247
248fn flag(dict: &Dictionary, key: &[u8]) -> bool {
249    matches!(dict.get(key), Some(Object::Boolean(true)))
250}
251
252impl Stream {
253    /// Decode this stream's payload with its own `/Filter` and `/DecodeParms`.
254    ///
255    /// Fails when either entry is indirect — use
256    /// [`crate::Document::decode_stream`] for that case.
257    pub fn decode(&self) -> Result<Vec<u8>> {
258        let chain = FilterSpec::from_dict(self.dict())?;
259        decode_chain(self.data(), &chain)
260    }
261}
262
263/// `/DecodeParms` predictor settings, with the defaults from §7.4.4.4.
264#[derive(Debug, Clone, Copy, PartialEq, Eq)]
265pub struct Predictor {
266    /// 1 = none, 2 = TIFF, 10–15 = PNG filters.
267    pub predictor: u8,
268    /// Colour components per pixel, default 1.
269    pub colors: u8,
270    /// Bits per component, default 8.
271    pub bits_per_component: u8,
272    /// Bytes per row divided by the pixel size, default 1.
273    pub columns: u16,
274}
275
276impl Default for Predictor {
277    fn default() -> Self {
278        Self {
279            predictor: 1,
280            colors: 1,
281            bits_per_component: 8,
282            columns: 1,
283        }
284    }
285}
286
287impl Predictor {
288    /// Read predictor settings from a `/DecodeParms` dictionary.
289    pub fn from_dict(parms: Option<&Dictionary>) -> Result<Self> {
290        let Some(parms) = parms else {
291            return Ok(Self::default());
292        };
293        let mut predictor = Self::default();
294        if let Some(Object::Integer(value)) = parms.get(b"Predictor") {
295            predictor.predictor = u8::try_from(*value).map_err(|_| Error::Malformed {
296                what: "/Predictor out of range",
297                offset: None,
298            })?;
299        }
300        if let Some(Object::Integer(value)) = parms.get(b"Colors") {
301            predictor.colors = u8::try_from(*value).map_err(|_| Error::Malformed {
302                what: "/Colors out of range",
303                offset: None,
304            })?;
305        }
306        if let Some(Object::Integer(value)) = parms.get(b"BitsPerComponent") {
307            predictor.bits_per_component = u8::try_from(*value).map_err(|_| Error::Malformed {
308                what: "/BitsPerComponent out of range",
309                offset: None,
310            })?;
311        }
312        if let Some(Object::Integer(value)) = parms.get(b"Columns") {
313            predictor.columns = u16::try_from(*value).map_err(|_| Error::Malformed {
314                what: "/Columns out of range",
315                offset: None,
316            })?;
317        }
318        Ok(predictor)
319    }
320}
321
322fn flate_decode(data: &[u8], limit: usize) -> Result<Vec<u8>> {
323    // PDF Flate streams are zlib-wrapped, but some writers emit raw DEFLATE.
324    match inflate_capped(data, DataFormat::Zlib, limit) {
325        Ok(out) => return Ok(out),
326        // A budget failure is final: retrying the same bytes as raw DEFLATE
327        // would double the work and then report the wrong reason.
328        Err(Error::Limit { limit, .. }) => {
329            return Err(Error::Limit {
330                what: "a Flate stream",
331                limit,
332            });
333        }
334        Err(_) => {}
335    }
336    match inflate_capped(data, DataFormat::Raw, limit) {
337        Ok(out) => Ok(out),
338        Err(Error::Limit { limit, .. }) => Err(Error::Limit {
339            what: "a Flate stream",
340            limit,
341        }),
342        Err(_) => Err(Error::Malformed {
343            what: "FlateDecode payload",
344            offset: None,
345        }),
346    }
347}
348
349/// Inflate with an output budget, stopping as soon as it is passed.
350///
351/// This is the part that makes a bomb harmless: `decompress_to_vec` grows a
352/// vector until the stream ends, so the budget would only be checked after a
353/// gigabyte had already been allocated.
354fn inflate_capped(data: &[u8], format: DataFormat, limit: usize) -> Result<Vec<u8>> {
355    let mut state = InflateState::new(format);
356    // Reserve what the input implies (zlib rarely beats 1:4 on real streams)
357    // and inflate into a stack buffer: a heap chunk per stream was 110 kB of
358    // the benchmark's allocations on a one-page document.
359    let mut out: Vec<u8> = Vec::with_capacity(limit.min(data.len().saturating_mul(4).max(64)));
360    let mut chunk = [0u8; 32 * 1024];
361    let mut consumed = 0usize;
362    loop {
363        let flush = if consumed >= data.len() {
364            MZFlush::Finish
365        } else {
366            MZFlush::None
367        };
368        let result = inflate(&mut state, &data[consumed..], &mut chunk, flush);
369        consumed += result.bytes_consumed;
370        if result.bytes_written > 0 {
371            if out.len().saturating_add(result.bytes_written) > limit {
372                return Err(Error::Limit {
373                    what: "a Flate stream",
374                    limit,
375                });
376            }
377            out.extend_from_slice(&chunk[..result.bytes_written]);
378        }
379        match result.status {
380            Ok(MZStatus::StreamEnd) => return Ok(out),
381            Ok(MZStatus::Ok) => {
382                // No progress with no input left means a truncated stream.
383                if consumed >= data.len() && result.bytes_written == 0 {
384                    return Err(Error::Malformed {
385                        what: "FlateDecode payload",
386                        offset: None,
387                    });
388                }
389            }
390            _ => {
391                return Err(Error::Malformed {
392                    what: "FlateDecode payload",
393                    offset: None,
394                });
395            }
396        }
397    }
398}
399
400fn early_change(parms: Option<&Dictionary>) -> Result<bool> {
401    match parms.and_then(|parms| parms.get(b"EarlyChange")) {
402        None => Ok(true),
403        Some(Object::Integer(0)) => Ok(false),
404        Some(Object::Integer(1)) => Ok(true),
405        Some(_) => Err(Error::Malformed {
406            what: "/EarlyChange must be 0 or 1",
407            offset: None,
408        }),
409    }
410}
411
412fn ascii_hex_decode(data: &[u8]) -> Result<Vec<u8>> {
413    let mut out = Vec::new();
414    let mut high: Option<u8> = None;
415    for (offset, &byte) in data.iter().enumerate() {
416        if byte == b'>' {
417            break;
418        }
419        if is_whitespace(byte) {
420            continue;
421        }
422        let value = hex_value(byte).ok_or(Error::UnexpectedByte {
423            byte,
424            offset,
425            what: "ASCIIHexDecode payload",
426        })?;
427        match high.take() {
428            Some(high) => out.push((high << 4) | value),
429            None => high = Some(value),
430        }
431    }
432    if let Some(high) = high {
433        // An odd final digit is the high nibble of a byte padded with 0.
434        out.push(high << 4);
435    }
436    Ok(out)
437}
438
439fn ascii85_decode(data: &[u8]) -> Result<Vec<u8>> {
440    let mut out = Vec::new();
441    let mut group = [0_u8; 5];
442    let mut count = 0;
443    let start = if data.starts_with(b"<~") { 2 } else { 0 };
444    let mut offset = start;
445    while offset < data.len() {
446        let byte = data[offset];
447        offset += 1;
448        if byte == b'~' {
449            break;
450        }
451        if is_whitespace(byte) {
452            continue;
453        }
454        if byte == b'z' {
455            if count != 0 {
456                return Err(Error::Malformed {
457                    what: "ASCII85Decode `z` inside a group",
458                    offset: None,
459                });
460            }
461            out.extend_from_slice(&[0, 0, 0, 0]);
462            continue;
463        }
464        if !(b'!'..=b'u').contains(&byte) {
465            return Err(Error::UnexpectedByte {
466                byte,
467                offset: offset - 1,
468                what: "ASCII85Decode payload",
469            });
470        }
471        group[count] = byte - b'!';
472        count += 1;
473        if count == 5 {
474            push_ascii85_group(&mut out, &group, 4)?;
475            count = 0;
476        }
477    }
478    if count > 0 {
479        if count == 1 {
480            return Err(Error::Malformed {
481                what: "ASCII85Decode final group of one character",
482                offset: None,
483            });
484        }
485        for slot in group.iter_mut().skip(count) {
486            *slot = 84; // `u`, the largest digit, pads the group
487        }
488        push_ascii85_group(&mut out, &group, count - 1)?;
489    }
490    Ok(out)
491}
492
493fn push_ascii85_group(out: &mut Vec<u8>, group: &[u8; 5], emit: usize) -> Result<()> {
494    let mut value = 0_u64;
495    for &digit in group {
496        value = value * 85 + u64::from(digit);
497    }
498    let value = u32::try_from(value).map_err(|_| Error::Malformed {
499        what: "ASCII85Decode group overflows 32 bits",
500        offset: None,
501    })?;
502    out.extend_from_slice(&value.to_be_bytes()[..emit]);
503    Ok(())
504}
505
506fn run_length_decode(data: &[u8]) -> Result<Vec<u8>> {
507    let mut out = Vec::new();
508    let mut offset = 0;
509    while offset < data.len() {
510        let length = data[offset];
511        offset += 1;
512        match length {
513            // 128 ends the data.
514            128 => break,
515            // A length up to 127 is followed by that many plus one literal bytes.
516            0..=127 => {
517                let count = usize::from(length) + 1;
518                let chunk = data
519                    .get(offset..offset + count)
520                    .ok_or(Error::unexpected_eof("RunLengthDecode literal run"))?;
521                out.extend_from_slice(chunk);
522                offset += count;
523            }
524            // 129–255 repeats the next byte 257 minus the length times.
525            _ => {
526                let byte = *data
527                    .get(offset)
528                    .ok_or(Error::unexpected_eof("RunLengthDecode repeat run"))?;
529                offset += 1;
530                out.resize(out.len() + (257 - usize::from(length)), byte);
531            }
532        }
533    }
534    Ok(out)
535}
536
537const LZW_CLEAR: u16 = 256;
538const LZW_EOD: u16 = 257;
539const LZW_MAX_CODE: usize = 4096;
540
541fn lzw_decode(data: &[u8], early_change: bool) -> Result<Vec<u8>> {
542    let mut out = Vec::new();
543    let mut table: Vec<Vec<u8>> = (0..=255_u16).map(|byte| vec![byte as u8]).collect();
544    table.push(Vec::new()); // 256: clear table
545    table.push(Vec::new()); // 257: end of data
546    let mut code_width = 9_u8;
547    let mut previous: Option<Vec<u8>> = None;
548    let mut bit = 0_usize;
549    while let Some(code) = read_lzw_code(data, &mut bit, code_width) {
550        if code == LZW_EOD {
551            break;
552        }
553        if code == LZW_CLEAR {
554            table.truncate(258);
555            code_width = 9;
556            previous = None;
557            continue;
558        }
559        let sequence = match table.get(usize::from(code)) {
560            Some(entry) if !entry.is_empty() => entry.clone(),
561            // The one-code-ahead case: the code names the sequence about to be
562            // added, which is the previous sequence plus its own first byte.
563            _ if usize::from(code) == table.len() => match &previous {
564                Some(previous) => {
565                    let mut sequence = previous.clone();
566                    sequence.push(previous[0]);
567                    sequence
568                }
569                None => {
570                    return Err(Error::Malformed {
571                        what: "LZWDecode code without a base sequence",
572                        offset: None,
573                    });
574                }
575            },
576            _ => {
577                return Err(Error::Malformed {
578                    what: "LZWDecode code out of range",
579                    offset: None,
580                });
581            }
582        };
583        out.extend_from_slice(&sequence);
584        if let Some(previous) = previous
585            && table.len() < LZW_MAX_CODE
586        {
587            let mut entry = previous;
588            entry.push(sequence[0]);
589            table.push(entry);
590            if table.len() + usize::from(early_change) == 512 {
591                code_width = 10;
592            } else if table.len() + usize::from(early_change) == 1024 {
593                code_width = 11;
594            } else if table.len() + usize::from(early_change) == 2048 {
595                code_width = 12;
596            }
597        }
598        previous = Some(sequence);
599    }
600    Ok(out)
601}
602
603fn read_lzw_code(data: &[u8], bit: &mut usize, width: u8) -> Option<u16> {
604    if *bit + usize::from(width) > data.len() * 8 {
605        return None;
606    }
607    let mut value = 0_u16;
608    for _ in 0..width {
609        let byte = data[*bit / 8];
610        let bit_in_byte = 7 - (*bit % 8);
611        value = (value << 1) | u16::from((byte >> bit_in_byte) & 1);
612        *bit += 1;
613    }
614    Some(value)
615}
616
617fn apply_predictor(data: &[u8], predictor: Predictor) -> Result<Vec<u8>> {
618    match predictor.predictor {
619        1 => Ok(data.to_vec()),
620        2 => tiff_predictor(data, predictor),
621        10..=15 => png_predictor(data, predictor),
622        _ => Err(Error::Malformed {
623            what: "unsupported /Predictor",
624            offset: None,
625        }),
626    }
627}
628
629fn png_predictor(data: &[u8], predictor: Predictor) -> Result<Vec<u8>> {
630    let colors = usize::from(predictor.colors.max(1));
631    let bits = usize::from(predictor.bits_per_component.max(1));
632    let columns = usize::from(predictor.columns.max(1));
633    let bpp = (colors * bits).div_ceil(8);
634    let row_bytes = (columns * colors * bits).div_ceil(8);
635    let mut out = Vec::with_capacity(data.len());
636    let mut previous = vec![0_u8; row_bytes];
637    let mut offset = 0;
638    while offset < data.len() {
639        let filter = data[offset];
640        offset += 1;
641        let row = data
642            .get(offset..offset + row_bytes)
643            .ok_or(Error::unexpected_eof("PNG predictor row"))?;
644        offset += row_bytes;
645        let mut current = vec![0_u8; row_bytes];
646        for index in 0..row_bytes {
647            let left = if index >= bpp {
648                current[index - bpp]
649            } else {
650                0
651            };
652            let up = previous[index];
653            let up_left = if index >= bpp {
654                previous[index - bpp]
655            } else {
656                0
657            };
658            current[index] = match filter {
659                0 => row[index],
660                1 => row[index].wrapping_add(left),
661                2 => row[index].wrapping_add(up),
662                3 => row[index].wrapping_add(((u16::from(left) + u16::from(up)) / 2) as u8),
663                4 => row[index].wrapping_add(paeth(left, up, up_left)),
664                _ => {
665                    return Err(Error::Malformed {
666                        what: "PNG predictor row filter must be 0–4",
667                        offset: None,
668                    });
669                }
670            };
671        }
672        out.extend_from_slice(&current);
673        previous = current;
674    }
675    Ok(out)
676}
677
678fn paeth(left: u8, up: u8, up_left: u8) -> u8 {
679    let left = i32::from(left);
680    let up = i32::from(up);
681    let up_left = i32::from(up_left);
682    let prediction = left + up - up_left;
683    let distance_left = (prediction - left).abs();
684    let distance_up = (prediction - up).abs();
685    let distance_up_left = (prediction - up_left).abs();
686    if distance_left <= distance_up && distance_left <= distance_up_left {
687        left as u8
688    } else if distance_up <= distance_up_left {
689        up as u8
690    } else {
691        up_left as u8
692    }
693}
694
695fn tiff_predictor(data: &[u8], predictor: Predictor) -> Result<Vec<u8>> {
696    if predictor.bits_per_component != 8 {
697        return Err(Error::Malformed {
698            what: "TIFF predictor needs 8 bits per component",
699            offset: None,
700        });
701    }
702    let colors = usize::from(predictor.colors.max(1));
703    let columns = usize::from(predictor.columns.max(1));
704    let row_bytes = colors * columns;
705    let mut out = data.to_vec();
706    for row in out.chunks_mut(row_bytes) {
707        for index in colors..row.len() {
708            row[index] = row[index].wrapping_add(row[index - colors]);
709        }
710    }
711    Ok(out)
712}
713
714#[cfg(test)]
715mod tests {
716    use super::{
717        Filter, FilterSpec, Predictor, apply_predictor, ascii_hex_decode, ascii85_decode,
718        decode_chain, lzw_decode, run_length_decode,
719    };
720    use crate::error::Error;
721    use crate::object::{Dictionary, Object};
722
723    fn parms(entries: &[(&str, Object)]) -> Dictionary {
724        let mut dict = Dictionary::new();
725        for (name, value) in entries {
726            dict.insert(name.as_bytes(), value.clone());
727        }
728        dict
729    }
730
731    #[test]
732    fn filter_names_map_to_filters() {
733        assert_eq!(
734            Filter::from_name(b"FlateDecode").expect("flate"),
735            Filter::FlateDecode
736        );
737        assert_eq!(
738            Filter::from_name(b"Fl").expect("flate"),
739            Filter::FlateDecode
740        );
741        assert_eq!(
742            Filter::from_name(b"LZWDecode").expect("lzw"),
743            Filter::LzwDecode
744        );
745        assert_eq!(
746            Filter::from_name(b"ASCIIHexDecode").expect("ahx"),
747            Filter::AsciiHexDecode
748        );
749        assert_eq!(
750            Filter::from_name(b"ASCII85Decode").expect("a85"),
751            Filter::Ascii85Decode
752        );
753        assert_eq!(
754            Filter::from_name(b"RunLengthDecode").expect("rl"),
755            Filter::RunLengthDecode
756        );
757        assert_eq!(Filter::FlateDecode.name(), "FlateDecode");
758        let image = Filter::from_name(b"DCTDecode").expect_err("image filter");
759        assert!(image.to_string().contains("out of scope"), "{image}");
760        assert!(Filter::from_name(b"Nope").is_err());
761    }
762
763    #[test]
764    fn ascii_hex_decodes_with_and_without_the_terminator() {
765        assert_eq!(ascii_hex_decode(b"48656C6C6F>").expect("hex"), b"Hello");
766        assert_eq!(ascii_hex_decode(b"48 65 6c 6C 6f").expect("hex"), b"Hello");
767        assert_eq!(
768            ascii_hex_decode(b"414").expect("odd digit"),
769            vec![0x41, 0x40]
770        );
771        assert_eq!(ascii_hex_decode(b">").expect("empty"), Vec::<u8>::new());
772        assert!(ascii_hex_decode(b"48G").is_err());
773    }
774
775    #[test]
776    fn ascii85_decodes_groups_shortcuts_and_partials() {
777        // "Hello" as ASCII85 is "87cURDZ".
778        assert_eq!(ascii85_decode(b"87cURDZ~>").expect("ascii85"), b"Hello");
779        assert_eq!(ascii85_decode(b"87cURDZ").expect("no terminator"), b"Hello");
780        assert_eq!(ascii85_decode(b"@:E^").expect("three bytes"), b"abc");
781        assert_eq!(ascii85_decode(b"z~>").expect("z shortcut"), [0, 0, 0, 0]);
782        assert_eq!(ascii85_decode(b"<~87cURDZ~>").expect("prefix"), b"Hello");
783        assert_eq!(ascii85_decode(b"").expect("empty"), Vec::<u8>::new());
784        assert!(ascii85_decode(b"87{UR").is_err(), "character out of range");
785        assert_eq!(ascii85_decode(b"87").expect("partial").len(), 1);
786        assert!(ascii85_decode(b"8").is_err(), "single trailing character");
787        assert!(ascii85_decode(b"zZ~>").is_err(), "z inside a group");
788    }
789
790    #[test]
791    fn run_length_decodes_literal_and_repeat_runs() {
792        // 2 literal bytes "AB", then 3 copies of 'x' (257-254=3), then EOD.
793        assert_eq!(
794            run_length_decode(&[1, b'A', b'B', 254, b'x', 128]).expect("runlength"),
795            b"ABxxx"
796        );
797        assert_eq!(run_length_decode(&[128]).expect("empty"), Vec::<u8>::new());
798        assert!(
799            run_length_decode(&[5, b'A']).is_err(),
800            "truncated literal run"
801        );
802        assert!(run_length_decode(&[254]).is_err(), "truncated repeat run");
803    }
804
805    #[test]
806    fn lzw_decodes_a_hand_computed_vector() {
807        // 9-bit MSB-first codes 65 ('A'), 66 ('B'), 67 ('C'), 257 (EOD).
808        let data = [0x20, 0x90, 0x88, 0x70, 0x10];
809        assert_eq!(lzw_decode(&data, true).expect("lzw"), b"ABC");
810        assert_eq!(lzw_decode(&data, false).expect("lzw"), b"ABC");
811    }
812
813    #[test]
814    fn lzw_handles_clear_codes_and_growing_code_widths() {
815        // Produced by an independent encoder: clear code, 9-bit codes, width
816        // growth at the EarlyChange boundaries, end-of-data. Decoding 360 bytes
817        // of text exercises the 9 -> 10 bit step.
818        let text: Vec<u8> = b"The quick brown fox jumps over the lazy dog. ".repeat(8);
819        let encoded = bytes(concat!(
820            "80150d065101c4ea69319ac4062391bcee6e10198de78101a8ea6d381cc406f3",
821            "b194e4203a40c406c309e8f220321bcce2e1040a09068442a190e8844a29168c",
822            "46a391e9048a4926944aa592e82c1e130b86c3e23138ac5e331b8ec7e43049fc",
823            "9e532b96c8a614799d2a6d4d9cd42795391c96ad42accbe8d32a4cd69938a7ce",
824            "ea53eb3506b144addb2694b9bd3a75519ed52eb57a1d6ad748bdd7ee17fb1dd2",
825            "8184b4d166388af5befd62b9e0b1f68808"
826        ));
827        assert_eq!(lzw_decode(&encoded, true).expect("lzw"), text);
828    }
829
830    fn bytes(hex: &str) -> Vec<u8> {
831        hex.as_bytes()
832            .chunks(2)
833            .map(|pair| {
834                u8::from_str_radix(core::str::from_utf8(pair).expect("hex"), 16).expect("hex")
835            })
836            .collect()
837    }
838
839    #[test]
840    fn png_predictors_undo_every_row_filter() {
841        // Two rows of three bytes with explicit PNG filter bytes.
842        let none = [0, 1, 2, 3, 0, 4, 5, 6];
843        let sub = [1, 1, 1, 1, 1, 4, 1, 1];
844        let up = [2, 1, 2, 3, 2, 3, 3, 3];
845        let average = [3, 1, 2, 2, 3, 4, 2, 2];
846        let paeth = [4, 1, 1, 1, 4, 3, 1, 1];
847        let settings = Predictor {
848            predictor: 15,
849            colors: 1,
850            bits_per_component: 8,
851            columns: 3,
852        };
853        for encoded in [none, sub, up, average, paeth] {
854            assert_eq!(
855                apply_predictor(&encoded, settings).expect("predictor"),
856                vec![1, 2, 3, 4, 5, 6],
857                "encoded {encoded:?}"
858            );
859        }
860        assert!(
861            apply_predictor(&[9, 1, 2, 3], settings).is_err(),
862            "bad filter byte"
863        );
864    }
865
866    #[test]
867    fn tiff_predictor_is_horizontal_differencing() {
868        let encoded = [10, 10, 10, 1, 0, 0];
869        let settings = Predictor {
870            predictor: 2,
871            colors: 1,
872            bits_per_component: 8,
873            columns: 3,
874        };
875        assert_eq!(
876            apply_predictor(&encoded, settings).expect("tiff"),
877            vec![10, 20, 30, 1, 1, 1]
878        );
879        let rgb = Predictor {
880            predictor: 2,
881            colors: 3,
882            bits_per_component: 8,
883            columns: 2,
884        };
885        assert_eq!(
886            apply_predictor(&[1, 2, 3, 10, 10, 10], rgb).expect("tiff rgb"),
887            vec![1, 2, 3, 11, 12, 13]
888        );
889        let unsupported = Predictor {
890            predictor: 2,
891            bits_per_component: 4,
892            ..Predictor::default()
893        };
894        assert!(apply_predictor(&[0, 0], unsupported).is_err());
895        assert!(
896            apply_predictor(
897                &[0],
898                Predictor {
899                    predictor: 7,
900                    ..Predictor::default()
901                }
902            )
903            .is_err()
904        );
905    }
906
907    #[test]
908    fn decoders_report_bad_payloads() {
909        assert!(matches!(
910            super::decode_filter(Filter::FlateDecode, b"not deflate at all", None),
911            Err(Error::Malformed { .. })
912        ));
913        assert!(matches!(
914            super::decode_filter(Filter::Ascii85Decode, b"87{UR", None),
915            Err(Error::UnexpectedByte { .. })
916        ));
917    }
918
919    #[test]
920    fn filter_specs_read_names_arrays_and_parms() {
921        let dict = parms(&[("Filter", Object::name("FlateDecode"))]);
922        let specs = FilterSpec::from_dict(&dict).expect("single filter");
923        assert_eq!(specs.len(), 1);
924        assert_eq!(specs[0].filter, Filter::FlateDecode);
925        assert!(specs[0].parms.is_none());
926
927        let dict = parms(&[
928            (
929                "Filter",
930                Object::array([Object::name("ASCII85Decode"), Object::name("FlateDecode")]),
931            ),
932            (
933                "DecodeParms",
934                Object::array([
935                    Object::Null,
936                    Object::Dictionary(parms(&[("Predictor", Object::Integer(12))])),
937                ]),
938            ),
939        ]);
940        let specs = FilterSpec::from_dict(&dict).expect("filter array");
941        assert_eq!(specs.len(), 2);
942        assert_eq!(specs[0].filter, Filter::Ascii85Decode);
943        assert!(specs[0].parms.is_none());
944        assert_eq!(specs[1].filter, Filter::FlateDecode);
945        assert!(specs[1].parms.is_some());
946
947        let indirect = parms(&[("Filter", Object::reference(crate::ObjectId::new(9, 0)))]);
948        assert!(FilterSpec::from_dict(&indirect).is_err());
949        let bad_entry = parms(&[("Filter", Object::array([Object::Integer(1)]))]);
950        assert!(FilterSpec::from_dict(&bad_entry).is_err());
951    }
952
953    #[test]
954    fn chains_apply_in_order() {
955        // "Hello" -> ASCII85 -> and back again through a one-filter chain.
956        let encoded = b"87cURDZ~>";
957        let chain = [FilterSpec {
958            filter: Filter::Ascii85Decode,
959            parms: None,
960        }];
961        assert_eq!(decode_chain(encoded, &chain).expect("chain"), b"Hello");
962        assert_eq!(decode_chain(b"Hello", &[]).expect("empty chain"), b"Hello");
963    }
964
965    #[test]
966    fn predictor_defaults_are_inert() {
967        assert_eq!(
968            Predictor::from_dict(None).expect("defaults"),
969            Predictor::default()
970        );
971        assert_eq!(
972            apply_predictor(b"abc", Predictor::default()).expect("none"),
973            b"abc"
974        );
975    }
976}