Debian Codegraph @

.cargo/vendor/image/src/animation.rs

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