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

image/
animation.rs
