affine/
ratio.rs

1// Copyright 2026 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use zerocopy::{FromBytes, Immutable, IntoBytes};
6use zr::static_assert;
7
8#[derive(Debug, Clone, Copy, PartialEq, Eq)]
9pub enum Exact {
10    No,
11    Yes,
12}
13
14/// Rounding Behaviors used when scaling.
15///
16/// | val  | N   | D   | Down | Up  | TowardsZero | AwayFromZero |
17/// | :--- | :-- | :-- | :--- | :-- | :---------- | :----------- |
18/// | 7    | 1   | 2   | 3    | 4   | 3           | 4            |
19/// | -7   | 1   | 2   | -4   | -3  | -3          | -4           |
20pub struct Round;
21impl Round {
22    pub const DOWN: u8 = 0;
23    pub const UP: u8 = 1;
24    pub const TOWARDS_ZERO: u8 = 2;
25    pub const AWAY_FROM_ZERO: u8 = 3;
26}
27
28#[repr(C)]
29#[derive(Debug, Clone, Copy, PartialEq, Eq, FromBytes, IntoBytes, Immutable)]
30pub struct Ratio {
31    numerator: u32,
32    denominator: u32,
33}
34
35static_assert!(core::mem::size_of::<Ratio>() == 8);
36static_assert!(core::mem::align_of::<Ratio>() == 4);
37
38impl Default for Ratio {
39    fn default() -> Self {
40        Self::const_default()
41    }
42}
43
44impl Ratio {
45    pub const OVERFLOW: i64 = i64::MAX;
46    pub const UNDERFLOW: i64 = i64::MIN;
47
48    pub const fn const_default() -> Self {
49        Ratio { numerator: 1, denominator: 1 }
50    }
51
52    pub const fn new(numerator: u32, denominator: u32) -> Self {
53        debug_assert!(denominator != 0);
54        Ratio { numerator, denominator }
55    }
56
57    pub const fn numerator(&self) -> u32 {
58        self.numerator
59    }
60
61    pub const fn denominator(&self) -> u32 {
62        self.denominator
63    }
64
65    pub const fn invertible(&self) -> bool {
66        self.numerator != 0
67    }
68
69    pub const fn inverse(&self) -> Self {
70        debug_assert!(self.invertible());
71        Ratio { numerator: self.denominator, denominator: self.numerator }
72    }
73
74    /// Reduces the ratio of numerator/denominator in-place (32-bit).
75    pub fn reduce_u32(numerator: &mut u32, denominator: &mut u32) {
76        assert!(*denominator != 0);
77        if *numerator == 0 {
78            *denominator = 1;
79            return;
80        }
81        let gcd = binary_gcd(*numerator as u64, *denominator as u64) as u32;
82        *numerator /= gcd;
83        *denominator /= gcd;
84    }
85
86    /// Reduces the ratio of numerator/denominator in-place (64-bit).
87    pub fn reduce_u64(numerator: &mut u64, denominator: &mut u64) {
88        assert!(*denominator != 0);
89        if *numerator == 0 {
90            *denominator = 1;
91            return;
92        }
93        let gcd = binary_gcd(*numerator, *denominator);
94        *numerator /= gcd;
95        *denominator /= gcd;
96    }
97
98    /// Reduces the ratio instance in-place.
99    pub fn reduce(&mut self) {
100        Self::reduce_u32(&mut self.numerator, &mut self.denominator);
101    }
102
103    /// Produces the product of two ratios.
104    ///
105    /// If `exact` is `Exact::Yes`, this panics on loss of precision.
106    /// If `exact` is `Exact::No`, it attempts to find the best 32-bit approximation.
107    pub fn product_raw(
108        a_numerator: u32,
109        a_denominator: u32,
110        b_numerator: u32,
111        b_denominator: u32,
112        exact: Exact,
113    ) -> (u32, u32) {
114        let mut numerator = a_numerator as u64 * b_numerator as u64;
115        let mut denominator = a_denominator as u64 * b_denominator as u64;
116
117        Self::reduce_u64(&mut numerator, &mut denominator);
118
119        if numerator > u32::MAX as u64 || denominator > u32::MAX as u64 {
120            assert!(exact == Exact::No, "Precision loss in exact Ratio::product");
121
122            // Try to find the best approximation of the ratio that we can. Our
123            // approach is as follows. Figure out the number of bits to the right
124            // we need to shift the numerator and denominator, rounding up or down
125            // in the process, such that the result can be reduced to fit into 32
126            // bits.
127            //
128            // This approach tends to beat out a just-shift-until-it-fits approach,
129            // as well as an always-shift-then-reduce approach, but _none_ of these
130            // approaches always finds the best solution.
131            //
132            // TODO(johngro): figure out if it is reasonable to actually compute
133            // the best solution. Alternatively, consider implementing a "just
134            // shift until it fits" solution if the approximate results are good
135            // enough.
136            for i in 1..=32 {
137                // Produce a version of the numerator and denominator which have
138                // each been divided by 2^i, rounding up/down as appropriate
139                // (instead of truncating).
140                let rounded_numerator = (numerator + (1u64 << (i - 1))) >> i;
141                let rounded_denominator = (denominator + (1u64 << (i - 1))) >> i;
142
143                if rounded_denominator == 0 {
144                    // Product is larger than we can represent. Return the largest value we
145                    // can represent.
146                    return (u32::MAX, 1);
147                }
148
149                if rounded_numerator == 0 {
150                    // Product is smaller than we can represent. Return 0.
151                    return (0, 1);
152                }
153
154                let mut rn = rounded_numerator;
155                let mut rd = rounded_denominator;
156                Self::reduce_u64(&mut rn, &mut rd);
157                if rn <= u32::MAX as u64 && rd <= u32::MAX as u64 {
158                    return (rn as u32, rd as u32);
159                }
160            }
161            // Fallback (should be unreachable)
162            return (numerator as u32, denominator as u32);
163        }
164
165        (numerator as u32, denominator as u32)
166    }
167
168    pub fn product(a: Ratio, b: Ratio, exact: Exact) -> Ratio {
169        let (n, d) =
170            Self::product_raw(a.numerator, a.denominator, b.numerator, b.denominator, exact);
171        Ratio { numerator: n, denominator: d }
172    }
173
174    /// Scales an `i64` value by the ratio of numerator/denominator.
175    ///
176    /// Returns a saturated value (`OVERFLOW` or `UNDERFLOW`) on overflow/underflow.
177    /// The rounding behavior is determined by the `ROUND` const generic.
178    pub fn scale_with_round<const ROUND: u8>(value: i64, numerator: u32, denominator: u32) -> i64 {
179        assert!(denominator != 0);
180
181        if value >= 0 {
182            const LIMIT: u64 = i64::MAX as u64; // 0x7FFFFFFFFFFFFFFF
183            let value = value as u64;
184            let scaled = match ROUND {
185                Round::UP | Round::AWAY_FROM_ZERO => {
186                    scale_unsigned::<true, LIMIT>(value, numerator, denominator)
187                }
188                _ => scale_unsigned::<false, LIMIT>(value, numerator, denominator),
189            };
190            scaled as i64
191        } else {
192            // LIMIT == 0x8000000000000000
193            //
194            // Note:  We are attempting to pass the unsigned distance from zero into
195            // our ScaleUInt64 function.  In the case of negative numbers, we pass
196            // the twos compliment into the scale function, and then flip the sign
197            // again on the way out.
198            //
199            // We are taking the advantage of the fact that the twos compliment of
200            // MIN is itself for any signed integer type, and that casting this
201            // value to an unsigned integer of the same size properly produces the
202            // original value's distance from zero.  Clamping the limit to the
203            // distance of MIN from zero means that saturated results will likewise
204            // get properly flipped back to MIN during the return.
205            //
206            const LIMIT: u64 = 0x8000000000000000; // i64::MIN.unsigned_abs()
207            let value = value.unsigned_abs();
208            let scaled = match ROUND {
209                Round::DOWN | Round::AWAY_FROM_ZERO => {
210                    scale_unsigned::<true, LIMIT>(value, numerator, denominator)
211                }
212                _ => scale_unsigned::<false, LIMIT>(value, numerator, denominator),
213            };
214            if scaled == LIMIT { i64::MIN } else { -(scaled as i64) }
215        }
216    }
217
218    /// Scales an `i64` value by this ratio.
219    ///
220    /// Returns a saturated value (`OVERFLOW` or `UNDERFLOW`) on overflow/underflow.
221    /// The rounding behavior is determined by the `ROUND` const generic.
222    pub fn scale<const ROUND: u8>(&self, value: i64) -> i64 {
223        Self::scale_with_round::<ROUND>(value, self.numerator, self.denominator)
224    }
225}
226
227// Calculates the greatest common denominator (factor) of two values.
228fn binary_gcd(mut a: u64, mut b: u64) -> u64 {
229    debug_assert!(a != 0 && b != 0);
230
231    // Remove and count the common factors of 2.
232    let mut twos = 0;
233    while ((a | b) & 1) == 0 {
234        a >>= 1;
235        b >>= 1;
236        twos += 1;
237    }
238
239    // Get rid of the non-common factors of 2 in a. a is non-zero, so this
240    // terminates.
241    while (a & 1) == 0 {
242        a >>= 1;
243    }
244
245    loop {
246        // Get rid of the non-common factors of 2 in b. b is non-zero, so this
247        // terminates.
248        while (b & 1) == 0 {
249            b >>= 1;
250        }
251
252        // Apply the Euclid subtraction method.
253        if a > b {
254            core::mem::swap(&mut a, &mut b);
255        }
256
257        b -= a;
258        if b == 0 {
259            break;
260        }
261    }
262
263    // Multiply in the common factors of two.
264    a << twos
265}
266
267// Scales a u64 value by the ratio of two u32 values. If ROUND_UP is true, the
268// result is rounded up rather than down. Saturates at LIMIT on overflow.
269fn scale_unsigned<const ROUND_UP: bool, const LIMIT: u64>(
270    value: u64,
271    numerator: u32,
272    denominator: u32,
273) -> u64 {
274    let numerator = numerator as u64;
275    let denominator = denominator as u64;
276    const LOW_32_BITS: u64 = u32::MAX as u64;
277
278    // high and low are the product of the numerator and the high and low halves
279    // (respectively) of value, with the high end of low moved into the low end
280    // of high.
281    let low_product = numerator * (value & LOW_32_BITS);
282    let high = numerator * (value >> 32) + (low_product >> 32);
283    let mut low = low_product & LOW_32_BITS;
284
285    // Ignoring overflow and remainder, the result we want is:
286    // ((high << 32) + low) / denominator.
287
288    // Compute the divmod of high/D
289    let high_q = high / denominator;
290    let high_r = high % denominator;
291
292    // If high_q is larger than the overflow limit, then we can just get out now.
293    // The overflow limit will be different depending on whether we are scaling
294    // a non-negative number (0x7FFFFFFF) or a negative number (0x80000000)
295    if high_q > LIMIT >> 32 {
296        return LIMIT;
297    }
298
299    // The remainder of high/D are the high bits of low. Or them in, and do the
300    // divmod for the low portion
301    low |= high_r << 32;
302
303    let low_q = low / denominator;
304    let low_r = low % denominator;
305    let result = (high_q << 32) | low_q;
306    if result >= LIMIT {
307        return LIMIT;
308    }
309
310    // `result` is strictly less than LIMIT, so `result + 1` neither overflows
311    // nor exceeds LIMIT; if it is exactly LIMIT, that is the saturated value we
312    // would have returned anyway.
313    if ROUND_UP && low_r != 0 {
314        return result + 1;
315    }
316
317    result
318}
319
320// Operators
321
322impl core::ops::Mul for Ratio {
323    type Output = Self;
324    fn mul(self, rhs: Self) -> Self::Output {
325        Ratio::product(self, rhs, Exact::Yes)
326    }
327}
328
329// Division of fractions is multiplication by the reciprocal.
330#[allow(clippy::suspicious_arithmetic_impl)]
331impl core::ops::Div for Ratio {
332    type Output = Self;
333    fn div(self, rhs: Self) -> Self::Output {
334        self * rhs.inverse()
335    }
336}
337
338impl core::ops::Mul<i64> for Ratio {
339    type Output = i64;
340    fn mul(self, rhs: i64) -> Self::Output {
341        self.scale::<{ Round::DOWN }>(rhs)
342    }
343}
344
345impl core::ops::Mul<Ratio> for i64 {
346    type Output = i64;
347    fn mul(self, rhs: Ratio) -> Self::Output {
348        rhs.scale::<{ Round::DOWN }>(self)
349    }
350}
351
352// Division of fractions is multiplication by the reciprocal.
353#[allow(clippy::suspicious_arithmetic_impl)]
354impl core::ops::Div<Ratio> for i64 {
355    type Output = i64;
356    fn div(self, rhs: Ratio) -> Self::Output {
357        rhs.inverse().scale::<{ Round::DOWN }>(self)
358    }
359}
360
361#[cfg(test)]
362mod tests {
363    use super::*;
364
365    #[test]
366    fn test_construction() {
367        let valid_vectors = [(0, 1), (1, 1), (23, 41)];
368        for &(n, d) in &valid_vectors {
369            let r = Ratio::new(n, d);
370            assert_eq!(r.numerator(), n);
371            assert_eq!(r.denominator(), d);
372        }
373
374        // Ratio::default() produces 1/1
375        let r = Ratio::default();
376        assert_eq!(r.numerator(), 1);
377        assert_eq!(r.denominator(), 1);
378
379        // Reduction is NOT automatically performed
380        let r = Ratio::new(9, 21);
381        assert_eq!(r.numerator(), 9);
382        assert_eq!(r.denominator(), 21);
383    }
384
385    #[test]
386    fn test_reduction_32() {
387        let mut vectors = [
388            (1, 1, 1, 1),
389            (10, 10, 1, 1),
390            (10, 2, 5, 1),
391            (0, 1, 0, 1),
392            (0, 500, 0, 1),
393            (48000, 44100, 160, 147),
394            (44100, 48000, 147, 160),
395            (1000007, 1000000, 1000007, 1000000),
396        ];
397
398        for v in &mut vectors {
399            let mut n = v.0;
400            let mut d = v.1;
401            Ratio::reduce_u32(&mut n, &mut d);
402            assert_eq!((n, d), (v.2, v.3));
403
404            let mut r = Ratio::new(v.0, v.1);
405            r.reduce();
406            assert_eq!((r.numerator(), r.denominator()), (v.2, v.3));
407        }
408    }
409
410    #[test]
411    fn test_reduction_64() {
412        let mut vectors = [
413            (1, 1, 1, 1),
414            (10, 10, 1, 1),
415            (10, 2, 5, 1),
416            (0, 1, 0, 1),
417            (0, 500, 0, 1),
418            (48000, 44100, 160, 147),
419            (44100, 48000, 147, 160),
420            (1000007, 1000000, 1000007, 1000000),
421            (48000336000, 44100000000, 1000007, 918750),
422        ];
423
424        for v in &mut vectors {
425            let mut n = v.0;
426            let mut d = v.1;
427            Ratio::reduce_u64(&mut n, &mut d);
428            assert_eq!((n, d), (v.2, v.3));
429        }
430    }
431
432    #[test]
433    fn test_product() {
434        struct TestVector {
435            a_n: u32,
436            a_d: u32,
437            b_n: u32,
438            b_d: u32,
439            expected_n: u32,
440            expected_d: u32,
441            exact: Exact,
442        }
443
444        let test_vectors = [
445            TestVector {
446                a_n: 1,
447                a_d: 1,
448                b_n: 1,
449                b_d: 1,
450                expected_n: 1,
451                expected_d: 1,
452                exact: Exact::Yes,
453            },
454            TestVector {
455                a_n: 0,
456                a_d: 1,
457                b_n: 1,
458                b_d: 1,
459                expected_n: 0,
460                expected_d: 1,
461                exact: Exact::Yes,
462            },
463            TestVector {
464                a_n: 0,
465                a_d: 500,
466                b_n: 1,
467                b_d: 1,
468                expected_n: 0,
469                expected_d: 1,
470                exact: Exact::Yes,
471            },
472            TestVector {
473                a_n: 3,
474                a_d: 4,
475                b_n: 5,
476                b_d: 9,
477                expected_n: 5,
478                expected_d: 12,
479                exact: Exact::Yes,
480            },
481            TestVector {
482                a_n: 48000,
483                a_d: 44100,
484                b_n: 1000007,
485                b_d: 1000000,
486                expected_n: 1000007,
487                expected_d: 918750,
488                exact: Exact::Yes,
489            },
490            TestVector {
491                a_n: 3465653567,
492                a_d: 2327655023,
493                b_n: 1291540343,
494                b_d: 3698423317,
495                expected_n: 317609835,
496                expected_d: 610852072,
497                exact: Exact::No,
498            },
499            TestVector {
500                a_n: 0xFFFFFFFF,
501                a_d: 1,
502                b_n: 0xFFFFFFFF,
503                b_d: 1,
504                expected_n: 0xFFFFFFFF,
505                expected_d: 1,
506                exact: Exact::No,
507            },
508            TestVector {
509                a_n: 1,
510                a_d: 0xFFFFFFFF,
511                b_n: 1,
512                b_d: 0xFFFFFFFF,
513                expected_n: 0,
514                expected_d: 1,
515                exact: Exact::No,
516            },
517        ];
518
519        for v in &test_vectors {
520            let a = Ratio::new(v.a_n, v.a_d);
521            let b = Ratio::new(v.b_n, v.b_d);
522
523            let res = Ratio::product(a, b, v.exact);
524            assert_eq!(
525                (res.numerator(), res.denominator()),
526                (v.expected_n, v.expected_d),
527                "Expected {}/{} * {}/{} to produce {}/{}; got {}/{} instead (static)",
528                v.a_n,
529                v.a_d,
530                v.b_n,
531                v.b_d,
532                v.expected_n,
533                v.expected_d,
534                res.numerator(),
535                res.denominator()
536            );
537
538            let res = Ratio::product(b, a, v.exact);
539            assert_eq!(
540                (res.numerator(), res.denominator()),
541                (v.expected_n, v.expected_d),
542                "Expected {}/{} * {}/{} to produce {}/{}; got {}/{} instead (commutative static)",
543                v.b_n,
544                v.b_d,
545                v.a_n,
546                v.a_d,
547                v.expected_n,
548                v.expected_d,
549                res.numerator(),
550                res.denominator()
551            );
552
553            if v.exact == Exact::Yes {
554                let res = a * b;
555                assert_eq!((res.numerator(), res.denominator()), (v.expected_n, v.expected_d));
556
557                let res = b * a;
558                assert_eq!((res.numerator(), res.denominator()), (v.expected_n, v.expected_d));
559
560                if b.invertible() {
561                    let res = a / b.inverse();
562                    assert_eq!((res.numerator(), res.denominator()), (v.expected_n, v.expected_d));
563                }
564
565                if a.invertible() {
566                    let res = b / a.inverse();
567                    assert_eq!((res.numerator(), res.denominator()), (v.expected_n, v.expected_d));
568                }
569            }
570        }
571    }
572
573    #[test]
574    fn test_product_raw() {
575        struct TestVector {
576            a_n: u32,
577            a_d: u32,
578            b_n: u32,
579            b_d: u32,
580            expected_n: u32,
581            expected_d: u32,
582            exact: Exact,
583        }
584
585        let test_vectors = [
586            TestVector {
587                a_n: 1,
588                a_d: 1,
589                b_n: 1,
590                b_d: 1,
591                expected_n: 1,
592                expected_d: 1,
593                exact: Exact::Yes,
594            },
595            TestVector {
596                a_n: 0,
597                a_d: 1,
598                b_n: 1,
599                b_d: 1,
600                expected_n: 0,
601                expected_d: 1,
602                exact: Exact::Yes,
603            },
604            TestVector {
605                a_n: 0,
606                a_d: 500,
607                b_n: 1,
608                b_d: 1,
609                expected_n: 0,
610                expected_d: 1,
611                exact: Exact::Yes,
612            },
613            TestVector {
614                a_n: 3,
615                a_d: 4,
616                b_n: 5,
617                b_d: 9,
618                expected_n: 5,
619                expected_d: 12,
620                exact: Exact::Yes,
621            },
622            TestVector {
623                a_n: 48000,
624                a_d: 44100,
625                b_n: 1000007,
626                b_d: 1000000,
627                expected_n: 1000007,
628                expected_d: 918750,
629                exact: Exact::Yes,
630            },
631            TestVector {
632                a_n: 3465653567,
633                a_d: 2327655023,
634                b_n: 1291540343,
635                b_d: 3698423317,
636                expected_n: 317609835,
637                expected_d: 610852072,
638                exact: Exact::No,
639            },
640            TestVector {
641                a_n: 0xFFFFFFFF,
642                a_d: 1,
643                b_n: 0xFFFFFFFF,
644                b_d: 1,
645                expected_n: 0xFFFFFFFF,
646                expected_d: 1,
647                exact: Exact::No,
648            },
649            TestVector {
650                a_n: 1,
651                a_d: 0xFFFFFFFF,
652                b_n: 1,
653                b_d: 0xFFFFFFFF,
654                expected_n: 0,
655                expected_d: 1,
656                exact: Exact::No,
657            },
658        ];
659
660        for v in &test_vectors {
661            let res = Ratio::product_raw(v.a_n, v.a_d, v.b_n, v.b_d, v.exact);
662            assert_eq!(
663                res,
664                (v.expected_n, v.expected_d),
665                "Expected {}/{} * {}/{} to produce {}/{}; got {}/{} instead",
666                v.a_n,
667                v.a_d,
668                v.b_n,
669                v.b_d,
670                v.expected_n,
671                v.expected_d,
672                res.0,
673                res.1
674            );
675        }
676    }
677
678    fn test_scale_helper<const ROUND: u8>() {
679        struct TestVector {
680            val: i64,
681            n: u32,
682            d: u32,
683            expected: i64,
684            fractional_result: bool,
685        }
686
687        let test_vectors = [
688            TestVector { val: 0, n: 0, d: 1, expected: 0, fractional_result: false },
689            TestVector { val: 1234567890, n: 0, d: 1, expected: 0, fractional_result: false },
690            TestVector { val: 0, n: 1, d: 1, expected: 0, fractional_result: false },
691            TestVector {
692                val: 1234567890,
693                n: 1,
694                d: 1,
695                expected: 1234567890,
696                fractional_result: false,
697            },
698            TestVector { val: 198, n: 48000, d: 44100, expected: 215, fractional_result: true },
699            TestVector { val: -198, n: 48000, d: 44100, expected: -216, fractional_result: true },
700            TestVector {
701                val: 49 * 198,
702                n: 48000,
703                d: 44100,
704                expected: 10560,
705                fractional_result: false,
706            },
707            TestVector {
708                val: -(49 * 198),
709                n: 48000,
710                d: 44100,
711                expected: -10560,
712                fractional_result: false,
713            },
714            TestVector {
715                val: (49 * 198) + 1,
716                n: 48000,
717                d: 44100,
718                expected: 10561,
719                fractional_result: true,
720            },
721            TestVector {
722                val: -((49 * 198) + 1),
723                n: 48000,
724                d: 44100,
725                expected: -10562,
726                fractional_result: true,
727            },
728            TestVector {
729                val: 0x1517ffffeae80,
730                n: 0xbebc200,
731                d: 0x33333333,
732                expected: 0x4e94914f0000,
733                fractional_result: false,
734            },
735            TestVector {
736                val: -0x1517ffffeae80,
737                n: 0xbebc200,
738                d: 0x33333333,
739                expected: -0x4e94914f0000,
740                fractional_result: false,
741            },
742            TestVector {
743                val: i64::MAX,
744                n: 1000001,
745                d: 1000000,
746                expected: Ratio::OVERFLOW,
747                fractional_result: false,
748            },
749            TestVector {
750                val: i64::MIN,
751                n: 1000001,
752                d: 1000000,
753                expected: Ratio::UNDERFLOW,
754                fractional_result: false,
755            },
756            TestVector {
757                val: -0x2000000000000001,
758                n: 4,
759                d: 1,
760                expected: Ratio::UNDERFLOW,
761                fractional_result: false,
762            },
763        ];
764
765        for v in &test_vectors {
766            let res_static = Ratio::scale_with_round::<ROUND>(v.val, v.n, v.d);
767            let r = Ratio::new(v.n, v.d);
768            let res_inst = r.scale::<ROUND>(v.val);
769
770            let adjusted_expected = if !v.fractional_result || ROUND == Round::DOWN {
771                v.expected
772            } else if v.val >= 0 {
773                if ROUND == Round::TOWARDS_ZERO { v.expected } else { v.expected + 1 }
774            } else {
775                if ROUND == Round::AWAY_FROM_ZERO { v.expected } else { v.expected + 1 }
776            };
777
778            assert_eq!(
779                res_static, adjusted_expected,
780                "Static: Expected {} * {}/{} to produce {}; got {}",
781                v.val, v.n, v.d, adjusted_expected, res_static
782            );
783            assert_eq!(
784                res_inst, adjusted_expected,
785                "Instanced: Expected {} * {}/{} to produce {}; got {}",
786                v.val, v.n, v.d, adjusted_expected, res_inst
787            );
788
789            if ROUND == Round::DOWN {
790                let res_op1 = r * v.val;
791                let res_op2 = v.val * r;
792                assert_eq!(res_op1, adjusted_expected);
793                assert_eq!(res_op2, adjusted_expected);
794
795                if r.invertible() {
796                    let res_op3 = v.val / r.inverse();
797                    assert_eq!(res_op3, adjusted_expected);
798                }
799            }
800        }
801    }
802
803    #[test]
804    fn test_scale_round_down() {
805        test_scale_helper::<{ Round::DOWN }>();
806    }
807    #[test]
808    fn test_scale_round_up() {
809        test_scale_helper::<{ Round::UP }>();
810    }
811    #[test]
812    fn test_scale_round_towards_zero() {
813        test_scale_helper::<{ Round::TOWARDS_ZERO }>();
814    }
815    #[test]
816    fn test_scale_round_away_from_zero() {
817        test_scale_helper::<{ Round::AWAY_FROM_ZERO }>();
818    }
819
820    #[test]
821    fn test_inverse() {
822        let test_vectors = [(1, 1), (123456, 987654)];
823        for &(n, d) in &test_vectors {
824            let r = Ratio::new(n, d);
825            let inv = r.inverse();
826            assert_eq!(inv.numerator(), d);
827            assert_eq!(inv.denominator(), n);
828        }
829
830        let r = Ratio::new(0, 1);
831        assert!(!r.invertible());
832    }
833
834    // The two limits used by `Ratio::scale_with_round`; the limit for
835    // non-negative values, and the limit for the distance from zero of
836    // negative values.
837    const POSITIVE_LIMIT: u64 = i64::MAX as u64; // 0x7fffffffffffffff
838    const NEGATIVE_LIMIT: u64 = 0x8000000000000000; // i64::MIN.unsigned_abs()
839
840    // Invokes `scale_unsigned` and checks its result.  The rounding direction
841    // and the limit are const generic parameters, so they are spelled as
842    // literals here rather than being gathered into a table of test vectors.
843    macro_rules! check_scale_unsigned {
844        ($value:expr, $numerator:expr, $denominator:expr, $round_up:expr, $limit:expr,
845         $expected:expr $(,)?) => {{
846            let value: u64 = $value;
847            let numerator: u32 = $numerator;
848            let denominator: u32 = $denominator;
849            let expected: u64 = $expected;
850            let res = scale_unsigned::<{ $round_up }, { $limit }>(value, numerator, denominator);
851            assert_eq!(
852                res, expected,
853                "Expected scale_unsigned::<{}, {:#x}>({:#x}, {}, {}) to produce {:#x}; got {:#x}",
854                $round_up, $limit, value, numerator, denominator, expected, res
855            );
856        }};
857    }
858
859    // Exercises the `high_q > (LIMIT >> 32)` early-out, which both saturates
860    // and keeps the subsequent `high_q << 32` from overflowing.
861    #[test]
862    fn test_scale_unsigned_early_out() {
863        // high_q == 0x80000000, which is one more than POSITIVE_LIMIT >> 32;
864        // take the early out.
865        check_scale_unsigned!(0x8000000000000000, 1, 1, false, POSITIVE_LIMIT, POSITIVE_LIMIT);
866
867        // The same value against the negative limit; high_q is now exactly
868        // NEGATIVE_LIMIT >> 32, so there is no early out and the value is
869        // scaled exactly.
870        check_scale_unsigned!(0x8000000000000000, 1, 1, false, NEGATIVE_LIMIT, 0x8000000000000000);
871
872        // high_q == POSITIVE_LIMIT >> 32 exactly; no early out, and the result
873        // is well under the limit.
874        check_scale_unsigned!(0x7fffffff00000000, 1, 1, false, POSITIVE_LIMIT, 0x7fffffff00000000);
875
876        // The largest possible intermediates: high and low are each just shy of
877        // 2^64.  The first takes the early out; the second has
878        // high_q == (u64::MAX >> 32) and so does not.
879        check_scale_unsigned!(u64::MAX, u32::MAX, 1, true, POSITIVE_LIMIT, POSITIVE_LIMIT);
880        check_scale_unsigned!(u64::MAX, u32::MAX, u32::MAX, false, u64::MAX, u64::MAX);
881    }
882
883    // Exercises the `result >= LIMIT` saturation, which is only reachable when
884    // high_q is exactly `LIMIT >> 32` and the low half pushes the result past
885    // the limit.
886    #[test]
887    fn test_scale_unsigned_result_saturation() {
888        // result == NEGATIVE_LIMIT + 1, reached without the early out.
889        check_scale_unsigned!(0x8000000000000001, 1, 1, false, NEGATIVE_LIMIT, NEGATIVE_LIMIT);
890
891        // result == NEGATIVE_LIMIT exactly, which also saturates (to the same
892        // value it would have produced).
893        check_scale_unsigned!(0x4000000000000000, 2, 1, false, NEGATIVE_LIMIT, NEGATIVE_LIMIT);
894
895        // result == POSITIVE_LIMIT exactly.
896        check_scale_unsigned!(POSITIVE_LIMIT, 1, 1, true, POSITIVE_LIMIT, POSITIVE_LIMIT);
897
898        // Saturation of a small limit, where high_q is 0 and low_q alone
899        // exceeds the limit.
900        check_scale_unsigned!(1000, 3, 1, false, 100, 100);
901    }
902
903    // Exercises the rounding-up path, in particular the case where rounding up
904    // would produce exactly the limit.
905    #[test]
906    fn test_scale_unsigned_round_up_at_limit() {
907        // result == NEGATIVE_LIMIT - 1 with a non-zero remainder; rounding up
908        // produces exactly the limit.
909        check_scale_unsigned!(u64::MAX, 1, 2, true, NEGATIVE_LIMIT, NEGATIVE_LIMIT);
910
911        // The same inputs without rounding up produce the truncated value.
912        check_scale_unsigned!(u64::MAX, 1, 2, false, NEGATIVE_LIMIT, NEGATIVE_LIMIT - 1);
913
914        // result == POSITIVE_LIMIT - 1 with a non-zero remainder; rounding up
915        // produces exactly the limit.
916        check_scale_unsigned!(0xfffffffffffffffd, 1, 2, true, POSITIVE_LIMIT, POSITIVE_LIMIT);
917
918        // result == POSITIVE_LIMIT - 2 with a non-zero remainder; rounding up
919        // stays below the limit.
920        check_scale_unsigned!(0xfffffffffffffffb, 1, 2, true, POSITIVE_LIMIT, POSITIVE_LIMIT - 1);
921
922        // An exact result is never rounded up.
923        check_scale_unsigned!(0xfffffffffffffffc, 1, 2, true, POSITIVE_LIMIT, POSITIVE_LIMIT - 1);
924
925        // Rounding up a small result.
926        check_scale_unsigned!(198, 48000, 44100, true, POSITIVE_LIMIT, 216);
927        check_scale_unsigned!(198, 48000, 44100, false, POSITIVE_LIMIT, 215);
928    }
929
930    // A straightforward 128-bit reference implementation of the scaling
931    // operation, used to validate the 64-bit implementation.
932    fn scale_unsigned_reference(
933        value: u64,
934        numerator: u32,
935        denominator: u32,
936        round_up: bool,
937        limit: u64,
938    ) -> u64 {
939        let prod = (value as u128) * (numerator as u128);
940        let q = prod / (denominator as u128);
941        let r = prod % (denominator as u128);
942
943        if q >= (limit as u128) {
944            return limit;
945        }
946
947        let mut result = q as u64;
948        if round_up && r != 0 {
949            result += 1;
950            if result >= limit {
951                return limit;
952            }
953        }
954
955        result
956    }
957
958    // Compares `scale_unsigned` against the reference implementation across a
959    // range of values, numerators, and denominators, for one particular
960    // rounding direction and limit.
961    fn check_against_reference<const ROUND_UP: bool, const LIMIT: u64>() {
962        let values = [
963            0,
964            1,
965            2,
966            0xffff_ffff,
967            0x1_0000_0000,
968            0x1_0000_0001,
969            0x7fff_ffff_ffff_fffe,
970            POSITIVE_LIMIT,
971            NEGATIVE_LIMIT,
972            0x8000_0000_0000_0001,
973            0xffff_ffff_ffff_fffd,
974            u64::MAX,
975            0x1517ffffeae80,
976            1234567890,
977        ];
978        let numerators = [0, 1, 2, 3, 48000, 44100, 1000001, 0x7fff_ffff, u32::MAX];
979        let denominators = [1, 2, 3, 7, 44100, 1000000, 0x7fff_ffff, u32::MAX];
980
981        for &value in &values {
982            for &numerator in &numerators {
983                for &denominator in &denominators {
984                    let res = scale_unsigned::<ROUND_UP, LIMIT>(value, numerator, denominator);
985                    let expected =
986                        scale_unsigned_reference(value, numerator, denominator, ROUND_UP, LIMIT);
987                    assert_eq!(
988                        res, expected,
989                        "Expected scale_unsigned::<{}, {:#x}>({:#x}, {}, {}) to produce \
990                         {:#x}; got {:#x}",
991                        ROUND_UP, LIMIT, value, numerator, denominator, expected, res
992                    );
993                }
994            }
995        }
996    }
997
998    #[test]
999    fn test_scale_unsigned_matches_reference() {
1000        macro_rules! check_against_reference_for_limits {
1001            ($($limit:expr),* $(,)?) => {
1002                $(
1003                    check_against_reference::<false, { $limit }>();
1004                    check_against_reference::<true, { $limit }>();
1005                )*
1006            };
1007        }
1008
1009        check_against_reference_for_limits!(0, 1, 2, 100, POSITIVE_LIMIT, NEGATIVE_LIMIT, u64::MAX,);
1010    }
1011}
affine/ratio.rs

affine/
ratio.rs
