Debian Codegraph @

.cargo/vendor/tiff/src/decoder/cycles.rs

raw
1 use crate::{tags::IfdPointer, TiffError, TiffFormatError};
2 use std::collections::HashMap;
3
4 /// The IFD structure of a TIFF file should be limited to a forest of entries, and a tree when we
5 /// only consider having a primary IFD and its children. There is up to one primary child of a node
6 /// that is the `next` entry in an IFD itself. Since we offer iteration over this chain we want to
7 /// detect when a new edge would introduce a cycle, such that callers can be guaranteed to
8 /// terminate iteration at some point even in malicious images.
9 ///
10 /// However, we are not necessarily visiting the IFDs in their topological order.
11 ///
12 /// Since we only consider one child, we run union find to assign each pointer to a known chain.
13 /// Then, when we insert a new edge we check if they belong to the same component.
14 #[derive(Default, Debug)]
15 pub struct IfdCycles {
16 /// The root of each component union.
17 component_union: HashMap<ComponentId, ComponentId>,
18 links: HashMap<IfdPointer, u64>,
19 chains: HashMap<IfdPointer, ComponentId>,
20 }
21
22 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
23 struct ComponentId(u64);
24
25 impl IfdCycles {
26 pub fn new() -> Self {
27 IfdCycles::default()
28 }
29
30 pub fn insert_next(
31 &mut self,
32 from: IfdPointer,
33 to: Option<IfdPointer>,
34 ) -> Result<bool, TiffError> {
35 let to_offset = to.map_or(0, |p| p.0);
36
37 // For some reason we got
38 match self.links.get(&from) {
39 Some(existing) if *existing == to_offset => return Ok(false),
40 // We got here twice with two different reads of the same IFD. That is .. unusual and
41 // we interpret it as a cycle.
42 Some(_) => return Err(TiffError::FormatError(TiffFormatError::CycleInOffsets)),
43 None => self.links.insert(from, to_offset),
44 };
45
46 self.ensure_node(from);
47
48 if let Some(to) = to {
49 self.ensure_node(to);
50
51 let parent = self.nominal_component(from);
52 let child = self.nominal_component(to);
53
54 if parent == child {
55 return Err(TiffError::FormatError(TiffFormatError::CycleInOffsets));
56 }
57
58 self.component_union.insert(child, parent);
59 }
60
61 Ok(true)
62 }
63
64 fn ensure_node(&mut self, ifd: IfdPointer) {
65 self.chains.entry(ifd).or_insert_with(|| {
66 let id = ComponentId(self.component_union.len() as u64);
67 self.component_union.insert(id, id);
68 id
69 });
70 }
71
72 fn nominal_component(&mut self, node: IfdPointer) -> ComponentId {
73 let id = self.chains[&node];
74
75 let nomimal = {
76 let mut iter = id;
77
78 loop {
79 let parent = self.component_union[&iter];
80
81 if parent == iter {
82 break parent;
83 }
84
85 iter = parent;
86 }
87 };
88
89 if nomimal != id {
90 // Compress.
91 let mut iter = id;
92
93 loop {
94 let parent = self.component_union[&iter];
95
96 if parent == iter {
97 break;
98 }
99
100 self.component_union.insert(iter, nomimal);
101 iter = parent;
102 }
103 }
104
105 nomimal
106 }
107 }
108
109 #[test]
110 fn cycles_are_detected() {
111 let mut cycles = IfdCycles::new();
112
113 cycles
114 .insert_next(IfdPointer(0x20), Some(IfdPointer(0x800)))
115 .expect("non-existing link is valid");
116
117 cycles
118 .insert_next(IfdPointer(0x800), Some(IfdPointer(0x20)))
119 .expect_err("cycle must be detected");
120 }
121
122 #[test]
123 fn reflective_cycle() {
124 let mut cycles = IfdCycles::new();
125
126 cycles
127 .insert_next(IfdPointer(0x20), Some(IfdPointer(0x20)))
128 .expect_err("self-referential cycle must be detected");
129 }
130
131 #[test]
132 fn late_cycle() {
133 let mut cycles = IfdCycles::new();
134
135 cycles
136 .insert_next(IfdPointer(0x20), Some(IfdPointer(0x40)))
137 .expect("non-existing link is valid");
138
139 cycles
140 .insert_next(IfdPointer(0x60), Some(IfdPointer(0x80)))
141 .expect("non-existing link is valid");
142 cycles
143 .insert_next(IfdPointer(0x80), Some(IfdPointer(0x20)))
144 .expect("non-existing link is valid");
145
146 cycles
147 .insert_next(IfdPointer(0x40), Some(IfdPointer(0x60)))
148 .expect_err("non-existing link is valid");
149 }
150
151 #[test]
152 fn odd_cycle() {
153 let mut cycles = IfdCycles::new();
154
155 cycles
156 .insert_next(IfdPointer(0x20), Some(IfdPointer(0x40)))
157 .expect("non-existing link is valid");
158
159 cycles
160 .insert_next(IfdPointer(0x60), Some(IfdPointer(0x80)))
161 .expect("non-existing link is valid");
162 cycles
163 .insert_next(IfdPointer(0x80), Some(IfdPointer(0x20)))
164 .expect("non-existing link is valid");
165
166 cycles
167 .insert_next(IfdPointer(0x40), Some(IfdPointer(0x80)))
168 .expect_err("non-existing link is valid");
169 }