1use std::cmp::Ordering;
2use std::time::Duration;
3
4use crate::error::ImageResult;
5use crate::RgbaImage;
6
7/// An implementation dependent iterator, reading the frames as requested
8pub struct Frames<'a> {
9 iterator: Box<dyn Iterator<Item = ImageResult<Frame>> + 'a>,
10}
11
12impl<'a> Frames<'a> {
13 /// Creates a new `Frames` from an implementation specific iterator.
14 #[must_use]
15 pub fn new(iterator: Box<dyn Iterator<Item = ImageResult<Frame>> + 'a>) -> Self {
16 Frames { iterator }
17 }
18
19 /// Steps through the iterator from the current frame until the end and pushes each frame into
20 /// a `Vec`.
21 /// If en error is encountered that error is returned instead.
22 ///
23 /// Note: This is equivalent to `Frames::collect::<ImageResult<Vec<Frame>>>()`
24 pub fn collect_frames(self) -> ImageResult<Vec<Frame>> {
25 self.collect()
26 }
27}
28
29impl Iterator for Frames<'_> {
30 type Item = ImageResult<Frame>;
31
32 fn next(&mut self) -> Option<ImageResult<Frame>> {
33 self.iterator.next()
34 }
35}
36
37/// A single animation frame
38pub struct Frame {
39 /// Delay between the frames in milliseconds
40 delay: Delay,
41 /// x offset
42 left: u32,
43 /// y offset
44 top: u32,
45 buffer: RgbaImage,
46}
47
48impl Clone for Frame {
49 fn clone(&self) -> Self {
50 Self {
51 delay: self.delay,
52 left: self.left,
53 top: self.top,
54 buffer: self.buffer.clone(),
55 }
56 }
57
58 fn clone_from(&mut self, source: &Self) {
59 self.delay = source.delay;
60 self.left = source.left;
61 self.top = source.top;
62 self.buffer.clone_from(&source.buffer);
63 }
64}
65
66/// The delay of a frame relative to the previous one.
67#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd)]
68pub struct Delay {
69 ratio: Ratio,
70}
71
72impl Frame {
73 /// Constructs a new frame without any delay.
74 #[must_use]
75 pub fn new(buffer: RgbaImage) -> Frame {
76 Frame {
77 delay: Delay::from_ratio(Ratio { numer: 0, denom: 1 }),
78 left: 0,
79 top: 0,
80 buffer,
81 }
82 }
83
84 /// Constructs a new frame
85 #[must_use]
86 pub fn from_parts(buffer: RgbaImage, left: u32, top: u32, delay: Delay) -> Frame {
87 Frame {
88 delay,
89 left,
90 top,
91 buffer,
92 }
93 }
94
95 /// Delay of this frame
96 #[must_use]
97 pub fn delay(&self) -> Delay {
98 self.delay
99 }
100
101 /// Returns the image buffer
102 #[must_use]
103 pub fn buffer(&self) -> &RgbaImage {
104 &self.buffer
105 }
106
107 /// Returns a mutable image buffer
108 pub fn buffer_mut(&mut self) -> &mut RgbaImage {
109 &mut self.buffer
110 }
111
112 /// Returns the image buffer
113 #[must_use]
114 pub fn into_buffer(self) -> RgbaImage {
115 self.buffer
116 }
117
118 /// Returns the x offset
119 #[must_use]
120 pub fn left(&self) -> u32 {
121 self.left
122 }
123
124 /// Returns the y offset
125 #[must_use]
126 pub fn top(&self) -> u32 {
127 self.top
128 }
129}
130
131impl Delay {
132 /// Create a delay from a ratio of milliseconds.
133 ///
134 /// # Examples
135 ///
136 /// ```
137 /// use image::Delay;
138 /// let delay_10ms = Delay::from_numer_denom_ms(10, 1);
139 /// ```
140 #[must_use]
141 pub fn from_numer_denom_ms(numerator: u32, denominator: u32) -> Self {
142 Delay {
143 ratio: Ratio::new(numerator, denominator),
144 }
145 }
146
147 /// Convert from a duration, clamped between 0 and an implemented defined maximum.
148 ///
149 /// The maximum is *at least* `i32::MAX` milliseconds. It should be noted that the accuracy of
150 /// the result may be relative and very large delays have a coarse resolution.
151 ///
152 /// # Examples
153 ///
154 /// ```
155 /// use std::time::Duration;
156 /// use image::Delay;
157 ///
158 /// let duration = Duration::from_millis(20);
159 /// let delay = Delay::from_saturating_duration(duration);
160 /// ```
161 #[must_use]
162 pub fn from_saturating_duration(duration: Duration) -> Self {
163 // A few notes: The largest number we can represent as a ratio is u32::MAX but we can
164 // sometimes represent much smaller numbers.
165 //
166 // We can represent duration as `millis+a/b` (where a < b, b > 0).
167 // We must thus bound b with `b·millis + (b-1) <= u32::MAX` or
168 // > `0 < b <= (u32::MAX + 1)/(millis + 1)`
169 // Corollary: millis <= u32::MAX
170
171 const MILLIS_BOUND: u128 = u32::MAX as u128;
172
173 let millis = duration.as_millis().min(MILLIS_BOUND);
174 let submillis = (duration.as_nanos() % 1_000_000) as u32;
175
176 let max_b = if millis > 0 {
177 ((MILLIS_BOUND + 1) / (millis + 1)) as u32
178 } else {
179 MILLIS_BOUND as u32
180 };
181 let millis = millis as u32;
182
183 let (a, b) = Self::closest_bounded_fraction(max_b, submillis, 1_000_000);
184 Self::from_numer_denom_ms(a + b * millis, b)
185 }
186
187 /// The numerator and denominator of the delay in milliseconds.
188 ///
189 /// This is guaranteed to be an exact conversion if the `Delay` was previously created with the
190 /// `from_numer_denom_ms` constructor.
191 #[must_use]
192 pub fn numer_denom_ms(self) -> (u32, u32) {
193 (self.ratio.numer, self.ratio.denom)
194 }
195
196 pub(crate) fn from_ratio(ratio: Ratio) -> Self {
197 Delay { ratio }
198 }
199
200 pub(crate) fn into_ratio(self) -> Ratio {
201 self.ratio
202 }
203
204 /// Given some fraction, compute an approximation with denominator bounded.
205 ///
206 /// Note that `denom_bound` bounds nominator and denominator of all intermediate
207 /// approximations and the end result.
208 fn closest_bounded_fraction(denom_bound: u32, nom: u32, denom: u32) -> (u32, u32) {
209 use std::cmp::Ordering::*;
210 assert!(0 < denom);
211 assert!(0 < denom_bound);
212 assert!(nom < denom);
213
214 // Avoid a few type troubles. All intermediate results are bounded by `denom_bound` which
215 // is in turn bounded by u32::MAX. Representing with u64 allows multiplication of any two
216 // values without fears of overflow.
217
218 // Compare two fractions whose parts fit into a u32.
219 fn compare_fraction((an, ad): (u64, u64), (bn, bd): (u64, u64)) -> Ordering {
220 (an * bd).cmp(&(bn * ad))
221 }
222
223 // Computes the nominator of the absolute difference between two such fractions.
224 fn abs_diff_nom((an, ad): (u64, u64), (bn, bd): (u64, u64)) -> u64 {
225 let c0 = an * bd;
226 let c1 = ad * bn;
227
228 let d0 = c0.max(c1);
229 let d1 = c0.min(c1);
230 d0 - d1
231 }
232
233 let exact = (u64::from(nom), u64::from(denom));
234 // The lower bound fraction, numerator and denominator.
235 let mut lower = (0u64, 1u64);
236 // The upper bound fraction, numerator and denominator.
237 let mut upper = (1u64, 1u64);
238 // The closest approximation for now.
239 let mut guess = (u64::from(nom * 2 > denom), 1u64);
240
241 // loop invariant: ad, bd <= denom_bound
242 // iterates the Farey sequence.
243 loop {
244 // Break if we are done.
245 if compare_fraction(guess, exact) == Equal {
246 break;
247 }
248
249 // Break if next Farey number is out-of-range.
250 if u64::from(denom_bound) - lower.1 < upper.1 {
251 break;
252 }
253
254 // Next Farey approximation n between a and b
255 let next = (lower.0 + upper.0, lower.1 + upper.1);
256 // if F < n then replace the upper bound, else replace lower.
257 if compare_fraction(exact, next) == Less {
258 upper = next;
259 } else {
260 lower = next;
261 }
262
263 // Now correct the closest guess.
264 // In other words, if |c - f| > |n - f| then replace it with the new guess.
265 // This favors the guess with smaller denominator on equality.
266
267 // |g - f| = |g_diff_nom|/(gd*fd);
268 let g_diff_nom = abs_diff_nom(guess, exact);
269 // |n - f| = |n_diff_nom|/(nd*fd);
270 let n_diff_nom = abs_diff_nom(next, exact);
271
272 // The difference |n - f| is smaller than |g - f| if either the integral part of the
273 // fraction |n_diff_nom|/nd is smaller than the one of |g_diff_nom|/gd or if they are
274 // the same but the fractional part is larger.
275 if match (n_diff_nom / next.1).cmp(&(g_diff_nom / guess.1)) {
276 Less => true,
277 Greater => false,
278 // Note that the nominator for the fractional part is smaller than its denominator
279 // which is smaller than u32 and can't overflow the multiplication with the other
280 // denominator, that is we can compare these fractions by multiplication with the
281 // respective other denominator.
282 Equal => {
283 compare_fraction(
284 (n_diff_nom % next.1, next.1),
285 (g_diff_nom % guess.1, guess.1),
286 ) == Less
287 }
288 } {
289 guess = next;
290 }
291 }
292
293 (guess.0 as u32, guess.1 as u32)
294 }
295}
296
297impl From<Delay> for Duration {
298 fn from(delay: Delay) -> Self {
299 let ratio: Ratio = delay.into_ratio();
300 let ms: u32 = ratio.to_integer();
301 let rest: u32 = ratio.numer % ratio.denom;
302 let nanos: u64 = (u64::from(rest) * 1_000_000) / u64::from(ratio.denom);
303 Duration::from_millis(ms.into()) + Duration::from_nanos(nanos)
304 }
305}
306
307#[derive(Copy, Clone, Debug)]
308pub(crate) struct Ratio {
309 numer: u32,
310 denom: u32,
311}
312
313impl Ratio {
314 #[inline]
315 pub(crate) fn new(numerator: u32, denominator: u32) -> Self {
316 assert_ne!(denominator, 0);
317 Self {
318 numer: numerator,
319 denom: denominator,
320 }
321 }
322
323 #[inline]
324 pub(crate) fn to_integer(self) -> u32 {
325 self.numer / self.denom
326 }
327}
328
329impl PartialEq for Ratio {
330 fn eq(&self, other: &Self) -> bool {
331 self.cmp(other) == Ordering::Equal
332 }
333}
334
335impl Eq for Ratio {}
336
337impl PartialOrd for Ratio {
338 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
339 Some(self.cmp(other))
340 }
341}
342
343impl Ord for Ratio {
344 fn cmp(&self, other: &Self) -> Ordering {
345 // The following comparison can be simplified:
346 // a / b <cmp> c / d
347 // We multiply both sides by `b`:
348 // a <cmp> c * b / d
349 // We multiply both sides by `d`:
350 // a * d <cmp> c * b
351
352 let a: u32 = self.numer;
353 let b: u32 = self.denom;
354 let c: u32 = other.numer;
355 let d: u32 = other.denom;
356
357 // We cast the types from `u32` to `u64` in order
358 // to not overflow the multiplications.
359
360 (u64::from(a) * u64::from(d)).cmp(&(u64::from(c) * u64::from(b)))
361 }
362}
363
364#[cfg(test)]
365mod tests {
366 use super::{Delay, Duration, Ratio};
367
368 #[test]
369 fn simple() {
370 let second = Delay::from_numer_denom_ms(1000, 1);
371 assert_eq!(Duration::from(second), Duration::from_secs(1));
372 }
373
374 #[test]
375 fn fps_30() {
376 let thirtieth = Delay::from_numer_denom_ms(1000, 30);
377 let duration = Duration::from(thirtieth);
378 assert_eq!(duration.as_secs(), 0);
379 assert_eq!(duration.subsec_millis(), 33);
380 assert_eq!(duration.subsec_nanos(), 33_333_333);
381 }
382
383 #[test]
384 fn duration_outlier() {
385 let oob = Duration::from_secs(0xFFFF_FFFF);
386 let delay = Delay::from_saturating_duration(oob);
387 assert_eq!(delay.numer_denom_ms(), (0xFFFF_FFFF, 1));
388 }
389
390 #[test]
391 fn duration_approx() {
392 let oob = Duration::from_millis(0xFFFF_FFFF) + Duration::from_micros(1);
393 let delay = Delay::from_saturating_duration(oob);
394 assert_eq!(delay.numer_denom_ms(), (0xFFFF_FFFF, 1));
395
396 let inbounds = Duration::from_millis(0xFFFF_FFFF) - Duration::from_micros(1);
397 let delay = Delay::from_saturating_duration(inbounds);
398 assert_eq!(delay.numer_denom_ms(), (0xFFFF_FFFF, 1));
399
400 let fine =
401 Duration::from_millis(0xFFFF_FFFF / 1000) + Duration::from_micros(0xFFFF_FFFF % 1000);
402 let delay = Delay::from_saturating_duration(fine);
403 // Funnily, 0xFFFF_FFFF is divisble by 5, thus we compare with a `Ratio`.
404 assert_eq!(delay.into_ratio(), Ratio::new(0xFFFF_FFFF, 1000));
405 }
406
407 #[test]
408 fn precise() {
409 // The ratio has only 32 bits in the numerator, too imprecise to get more than 11 digits
410 // correct. But it may be expressed as 1_000_000/3 instead.
411 let exceed = Duration::from_secs(333) + Duration::from_nanos(333_333_333);
412 let delay = Delay::from_saturating_duration(exceed);
413 assert_eq!(Duration::from(delay), exceed);
414 }
415
416 #[test]
417 fn small() {
418 // Not quite a delay of `1 ms`.
419 let delay = Delay::from_numer_denom_ms(1 << 16, (1 << 16) + 1);
420 let duration = Duration::from(delay);
421 assert_eq!(duration.as_millis(), 0);
422 // Not precisely the original but should be smaller than 0.
423 let delay = Delay::from_saturating_duration(duration);
424 assert_eq!(delay.into_ratio().to_integer(), 0);
425 }
426}
427