image/
animation.rs

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

image/
animation.rs
